Speedup Bitcoin stateful contract updates using pre-authorizing signatures

This post was first published on Medium.

State update claim

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

A problem arises when multiple transactions compete to update the shared state at the same time. To see why, let’s 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, and updates the state to condition 3Awhile Bob sends another transaction to transfer 10 tokens to Dave at the same time and instead updates it to condition3B. One of the transactions will fail because they duplicate a single UTXO containing state2.

Suppose Bob’s transaction fails. He needs to create a new transaction to use the new UTXO state3A, instead of state2, and try again. It’s not hard to see when there are many users trying to update around the same time, it can take many attempts for one’s update transaction to succeed, causing unpredictable delay and degrading the user experience.

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

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

Pre-approval of signatures

Signatures are used to pre-authorize state updates. We need a way to sign each transaction that won’t be invalidated even if the sequencer re-orders it by changing the input. None of the SIGHASH flags allow it.

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

In our symbolic contract, we only sign the recipient and the amount. For example, Alice will sign to authorize the transfer of 5 tokens to Charlie.

ERC20 Contract with pre-authorized signature

Replay attack

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

Bob (actually anyone) could reuse the same signature and send himself another 5 tokens from Alice. He can even repeat this many times until Alice’s balance is depleted.

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

ERC20 Contract with not signed

Contract level

If two contracts use the same encoding of messages (eg there is another fungible token contract), a signature used by one contract may also be valid for the other, even with the 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 condition contract can be reused in other contracts. This is in accordance with the standard practice of generating a new address for each new bitcoin transaction.

Resistant to censorship

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

There can also be multiple sequencers for a given static contract, a user can submit to alternative sequencers if one refuses to process their transaction. These sequencers can be coordinated in an overlay network outside the mining network. Standard scheduling techniques such as round-robin can be used to resolve contention between them when accessing the latest state.

***

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

See: The presentation of the BSV Global Blockchain Convention, Smart Contracts and Computation on BSV

width=”562″ height=”315″ frameborder=”0″ allowfullscreen=”allowfullscreen”>

New to Bitcoin? Check out CoinGeeks Bitcoin for beginners section, the ultimate resource guide for learning more about Bitcoin – as originally envisioned by Satoshi Nakamoto – and blockchain.