In contrast to traditional contracts, cryptocurrency-based smart contracts can provide improved business automation and more transparency. However, not all cryptocurrencies support expressive contracts. For example, Bitcoin only supports a restricted scripting language that is not expressive enough to realize many contracts. Ethereum supports a Turing-complete programming language, but the types of contracts that can be implemented are still severely constrained due to gas limits. Recent research has explored ways to add contract support to legacy currencies like Bitcoin or enable more complex contracts on systems like Ethereum, but such previous solutions have significant security and functional limitations. In this paper we propose Bitcontracts, a novel solution to enable generic and expressive smart contracts on legacy cryptocurrencies. The starting point of our solution is a common off-chain execution model, where the contract's issuers appoints a set of service providers to execute the contract's code; the contract's execution results are accepted if a quorum of service providers reports the same result; and clients are free to choose which such contracts they trust and use. The main technical challenge of this paper is how to realize such a trust model securely and efficiently without modifying the underlying blockchain. Bitcontracts achieves this using two main techniques. First, the state of each contract is stored on the chain which avoids the need to run expensive consensus protocols between the service providers. Second, the validity of each execution result is bound to the latest state of the chain to prevent double-spending attacks. Bitcontracts can be used to retrofit contracts to currencies like Bitcoin or to extend the contract execution capabilities of systems like Ethereum. We also identify a set of generic properties that a blockchain system must support so that expressive smart contracts can be added safely and efficiently, and analyze existing blockchains based on these criteria.