Previously, we introduced a general technique to maintain state in Bitcoin smart contracts. It stores state in a single UTXO directly. For example, we used the technique for a Layer-1 token solution, where the state is the global token balance table. It quickly becomes prohibitively expensive when the number of user grows large, since each UTXO and thus each transaction carries the entire state.
We present a breakthrough to maintain state efficiently. Instead the state itself, only its Merkle root needs to be stored in a UTXO, while still enforcing all state-transition rules at Layer 1. It reduces UTXO size from O(n) to O(log n), where n is the size of the state, rendering storing large state economically practical.
Sharding and Merkle Tree
State is sharded into multiple chunks, which are organized into a Merkle tree. The same technique is used in Bitcoin to commit transactions to a root hash in the block header.
Only root hash of the Merkle tree is stored in the contract/UTXO. When validating state transition, only involved chunks and their merkle paths are needed, not the entire state. This drastically reduces the space complexity of the contract to the depth of the Merkle tree, which is O(log n).
A reference implementation of tokens is here. It can be seen that only Merkle root of the state (32 bytes) is stored inside the contract, instead of the state itself in the original token contract. When transferring, only sender and receiver entry, and their Merkle paths, are needed. Amazingly, all transfer rules are still enforced in the contract, even though the entire state is never known to the contract at any given transition.
In the old model, state itself is stored on chain and the latest state can be fetched by following the state transition chain to the tip. While in the new model, only Merkle root of the state is stored on chain. The state itself is stored off chain. The latest state can be reconstructed by following the state chain and applying each transaction sequentially till the tip. This can be done by a user himself or outsourcing it to some third party. In the latter case, the user can still independently verify using Merkle proof, as long as he can retrieve the latest Merkle root. This is very similar to Simplified Payment Verification in Bitcoin.
The proposal solves spatial scalability of stateful contracts. At first glance, it may seem all transactions of such stateful contracts need to be sequentially processed, since there is only one global chain tip at any given time. However, after being spliced together off chain, they are independent from miners’ perspective. Thus they can be processed in parallel at Layer 1², like any other chained transactions. The off chain part is mostly sha256 hashing to compute txid, which can be done extremely fast even on commodity hardware.
We discover an extremely efficient way to store state in Bitcoin contracts, making storing extremely large state a reality. We demonstrate its power by implementing an efficient Layer-1 token.
 Credit of Long Li.
 Currently subject to unconfirmed chained transaction limit, which will be raised and eventually removed.