Review of Smart Contract Concepts for Bitcoin

Day 7: Rubin's Bitcoin Advent Calendar

Tweet

Welcome to day 7 of my Bitcoin Advent Calendar. You can see an index of all the posts here or subscribe at judica.org/join to get new posts in your inbox

In this post we’ll review a concepts for thinking about different types of smart contract capabilities and the implications of their availability.

Recursive v.s. Non Recursive

Recursive is pretty much just a fancy way of saying “loops”. This is sometimes also called “Turing Complete”. That’s an even fancier way of saying loops. For example, imagine a bitcoin contract with the following logic:

When Alice requests moving 1 coin to Bob by broadcasting a transaction with the request, Alice has 24 hours to completely cancel the transfer by broadcasting another transaction.

This is a looping contract because after cancelling Alice can immediately re-request the transfer. An example of non-looping but similar logic would be:

When Alice requests moving 1 coin to Bob, Alice has 24 hours to cancel the transfer by sending the coins to Alice’s backup key.

Here, the contract terminates after one canceled request by moving the coin elsewhere. It’s possible to emulate recursive behavior a limited amount by “unrolling” a loop. For example:

When Alice requests moving 1 coin to Bob, Alice has 24 hours to cancel the transfer by sending the coins to (when Alice requests moving 1 coin to Bob, Alice has 24 hours to cancel the transfer by sending the coins to Alice’s backup key).

Here we substituted the backup key with a copy of the original logic. Now Alice can make 2 cancellable requests before sending the money to the backup. This looks recursive, and it can be expressed by a recursive meta-program. Meta program is just a fancy term for a program that makes programs. But when we put the contract into writing (e.g., an address on the chain), it has to be unrolled for the specific number of iterations we want possible.

Unrolling is a very useful technique, and can be used in a broad variety of circumstances. For example, imagine we unroll a contract a million times and specify that transactions can only happen every 10 blocks. That covers like 200 years of contract execution. However, unrolling has it’s limits. When choices (action A or B) are introduced, unrolling can be less effective since you have and exponential blowup (that means unrolling even like 32 steps might be too many). However, there are some tricks that can be employed by a clever and careful programmer to reduce this complexity through, for example, memoization.

Fully Enumerated v.s. Open Ended

Suppose I have a contract which is supposed to strike an American option¹ and transfer a token. It might look like this:

If Alice is paid 1 BTC by December 25th, 2021 Midnight, then transfer 100 tokens to Bob’s Control.

A fully enumerated contract would be expressed as:

If Alice is paid 1 BTC by December 25th, 2021 Midnight, then transfer 100 tokens to Bob’s Address B.

Whereas an Open Ended contract would be expressed as:

If Alice is paid 1 BTC by December 25th, 2021 Midnight, then transfer 100 tokens to the address Bob requested with the payment.

The key difference being that in the fully enumerated case we must know the exact specifics of the contract and how it will execute, and in the open ended contract case there are bits and pieces we can dynamically specify.

There are ways that a fully enumerated contract can emulate dynamic choice. For example:

If Alice is paid 1 BTC by December 25th, 2021 Midnight, then transfer 100 tokens to one of Bob’s Address B1, B2, or B3 at Bob’s discretion.

Now Bob can pick from one of three destinations in the future. However, these options must have been known in advance (a priori). With an open ended contract, the address could be generated after the fact (post hoc).

This is a separate concept from recursive or non recursive. A contract that loops could loop through a set of fully enumerated states until reaching some terminal predetermined “exit” state (e.g., a plain address). The option contract described above is non-recursive, but can be open ended.

Client v.s. Consensus Validation

When you have a Bitcoin in an output, anyone who has run, say, Bitcoin Core can tell that it is valid by seeing it in the UTXO set. But what happens if you want to issue a token on top of Bitcoin with some set of unique rules? Bitcoin does not know anything about these tokens, and so it would be possible to make an invalid transaction (e.g., spending more value than you have). In order to ensure the token is valid and not corrupt, one must trace every prior transaction back to some “axiomatic” genesis transaction(s) minting the token. These traces can be cached, but by default Bitcoin software will not enforce that only valid transfers be made. We say that the token is Client validated while the Bitcoin is Consensus validated.

Is one worse than the other? Not necessarily. While permitting invalid transactions in the chain seems bad, as long as the invalid transactions can be uniformly excluded by all who care about the token it is not much worse than the work you do to run a Bitcoin full node anyways. There does seem to be some value in the Bitcoin network preventing you from making invalid transactions, but the network doesn’t stop you from making bad transactions (e.g., you could send money to the wrong place).

Client side validation can check all sorts of properties, not just tokens. For example, you could write a contract for an on-chain governed company and check transactions for valid state transitions amending the rules.

The main drawback to client side validation comes when you want your contract to interoperate with Bitcoin values. While client side validation can burn tokens that are transferred invalidly, imagine an exchange contract that swaps Bitcoin for Token. If the exchange contract sends more Bitcoin than it should, the clients can tell that it was an invalid transaction but the Bitcoin is still gone. Thus Client validated contracts are best left to things that don’t hold Bitcoin. The exception to this rule is if the Client validated contracts admit a custodian, a special monitor or set of monitors that handle the contracts Bitcoin balances in e.g. a multisig. The monitors can client-side validate the contracts and sign off on any balance transfers. The drawback to this approach is trust, but in certain applications that we’ll see later the monitor could be all of the participants themselves, which makes the application of the rules trustless.

Validation v.s. Computation

Validation and Computation are two sides of the same coin. A simple example to demonstrate:

Type	Task	Input	Output
Computation	Sort the numbers [4,5,1]	None	[1,4,5]
Validation	Check that [4,5,1] is sorted by indexes A	A = [2,0,1]	True

Validation is a computation, but hopefully it’s easier to perform the validation computation than the computation itself.

In a Bitcoin transaction we are always validating that the transaction was approved. A transaction in Bitcoin makes a clear precondition (the coins spent) and postcondition (the coins sent). Even in cases where we have to do a lot of computation to check the authorization, we still know the proposed outcome.

Compare to an Ethereum transaction: We pass some input to a function, and the EVM verifies that our input was authorized (e.g., send 1 Eth to contract X with message “hello”). Then, the side effects of that action are computed dynamically by the EVM. For certain contracts, we might be able to predict what the side effect will be (e.g., a 1:1 token exchange like Eth to Wrapped Eth), but for other contracts (e.g., a floating exchange rate for Eth to Wrapped BTC) we will get an outcome that can’t be fully predicted. It is possible for contracts to choose to engineer themselves in a way to create more predictability, however in Ethereum this does not result in an Invalid transaction, it results in a valid transaction (that e.g. still costs gas) that has a result which is not taken. For example, a transaction which says “Buy 1 WBTC for 15 ETH” might fail to acquire WBTC since the price is now 16ETH, but the transaction would be valid that you tried to make the trade and failed. This is because Ethereum’s base layer is computational in nature with little validation: validation must be built on top.

Sidenote: Malleability

For certain Bitcoin “covenant” transactions the validation/computation line can be thin. Transactions must always be transactions in a block, but it’s possible that in the future miners could receive “details” of a transaction and be responsible for generating the appropriate transaction themselves. For example, Blockstream released details on a noninteractive feebumping transaction, whereby a miner can dynamically compute a transaction that pays them more fees the longer it takes to confirm.

In the case of malleability like this, it’s not as simple as saying “don’t do it”, because miners have an incentive to extract the value if it is available.

Dynamic State

Contracts can have different types of state. State is just a fancy term for information available to execution.

Global state is information that is observable from anywhere. An example of this in Bitcoin is the UTXO Set: any transaction could spend any coin, and can “pull it into scope” by naming it’s Outpoint (whether or not the transaction is valid is another question). Another example of global state is the current block height, used for validating things like lock times. In Ethereum, there is a much expanded concept of Global state whereby contracts persist and allow read/write access from other contracts, and unlike Bitcoin’s UTXO set, observing a piece of information doesn’t destroy it like spending a coin does.

Local State is information observable only within your own context. For example, a contract might hold balances for 3 different people, but the current values of those split balances is not something queryable by outside parties. This also includes implicit state, such as “the contract is currently pending an Action from Alice” that are not explicitly coded.

Lastly, certain things are not State. An example of this is an authorizing signature, which is ephemeral data that is used in the transaction execution but does not have relevance for the continued execution of the contract and is not particularly observable (which signature we use shouldn’t matter).

General v.s. Specific

A General contract primitive is something that can be used across many different types of contract. A Specific contract implements well defined logic. In Bitcoin and Ethereum, the focus is on General contract primitives that can be used many ways. In some other ecosystems (e.g. NXT, Stellar), contract primitives have much more specific functionality.

General/Specific ends up being more of a spectrum than a binary. Certain contract primitives might be very specific but find general use, similarly some general primitives might be more general than others.

For example, the Lightning Network on Bitcoin has pursued a path of using general purpose extensions to Bitcoin so as not to “special case” payment channels. But is that worth it? Might Payment Channels be cheaper, easier to use, etc if we just designed built-in channels from the get-go? Perhaps yes, but then it might be harder to embed other things or incorporate new innovations into Lightning if it had to fit a single mold.

---

This isn’t an exhaustive list of topics by any means, but it should be a good primer for thinking about upgrade proposals that people discuss in Bitcoin. You’ll find out more about that in… tomorrow’s post!.