Speedup Bitcoin stateful contract updates using pre-authorizing signatures

Getting your Trinity Audio player ready...

This post was first published on Medium.

State update contention

Bitcoin smart contracts store states in the outputs of a chain of transactions. State transition occurs when a transaction spends the output containing the old state and creates an output containing the new state. At any given time, a single output/UTXO at the tip of the transaction chain has the latest state.

An issue arises when multiple transactions contend to update the shared state at the same time. To see why, let us consider a simple ERC-20 like token smart contract with the following state[1]:

The state records how many tokens each user has. Suppose Alice sends a transaction to transfer 5 tokens to Charlie, updating the state to state3A, while Bob sends another transaction to transfer 10 tokens to Dave simultaneously, updating it instead to state3B. One of the transactions will fail because they are double spending a single UTXO containing state2.

Suppose Bob’s transaction fails. He has to create a new transaction spending the new UTXO state3A, instead of state2, and retry. It is not hard to see when there are many users trying to update at about the same time, it may take many attempts for one’s update transaction to succeed, causing unpredictable delay and degrading user experience.

To avoid the contention, a naive approach is to send all update transactions to an intermediate coordinator, called sequencer, who orders them and broadcasts them to the blockchain.

Unfortunately, this approach does not work because the batched transactions can spend a single UTXO, as Alice and Bob’ transactions in Fig. 2 do. When the sequencer reorders them sequentially in a chain to avoid double-spent as in Fig. 3, the signature in Bob’s original transaction, state3B, becomes invalidated. If the sequencer has to ask a user to re-sign every time a transaction gets re-ordered, there will be unpredictable delay again and we are back to square one.

Pre-authorizing signatures

Signatures are used to pre-authorize state updates. We need a way to sign each transaction, which would not be invalidated even if the sequencer re-orders it by changing its input. None of the SIGHASH flags allows it.

Inspired by our previous work to emulate SIGHASH_NOINPUT, which excludes the input being spent from the signature, we only sign a message containing specific details about the action being authorized.

In our token contract, we only sign the receiver and amount. For example, Alice would sign to authorize transfer of 5 tokens to Charlie.

ERC20 Contract with pre-authorized signature

Replay attacks

Note that tokens can be transferred as long as a valid signature is provided. There is nothing in Alice’s signed message that could prevent the same signature from being used repeatedly.

Bob (in fact anyone) could reuse the same signature and send to himself another 5 tokens from Alice. He can even repeat this many times till Alice’s balance is drained.

To combat the replay attack, we can use an application-level nonce. “Nonce” is short-hand for “number used once” in cryptography. We can use a nonce for every signature and store the next nonce inside the contract.

ERC20 Contract with nonce signed

Contract level

If two contracts use the same encoding of messages (e.g., there is another fungible token contract), a signature used by one contract may also be valid for the other, even with nonce. We need some identifying information about the contract to prevent this type of replay attack.

We stipulate that no public key/address used in such a stateful contract can be reused in other contracts. This is consistent with the standard practice of generating a new address for each new bitcoin transaction.

Censorship resistant

If a sequencer censors a user’s transaction, the user can always submit it directly to the stateful contract on chain.

Also there can be multiple sequencers for a given stateful contract, a user can submit to alternative sequencers if one refuses to process his transaction. These sequencers can be coordinated in an overlay network outside of the miner network. Standard scheduling techniques like round-robin can be employed to resolve contention among them when accessing the latest state.

***

[1] A state can be compressed by storing each table entry in a Merkle tree and only store root of the tree as the state in the smart contract.

Watch: The BSV Global Blockchain Convention presentation, Smart Contracts and Computation on BSV