Scalable State Storage in BSV Smart Contracts

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.

Token Table as a Merkle Tree¹

Implementation

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.

State 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.

Store state itself vs Merkle root of it on chain

Temporal Scalability

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.

Summary

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.

Acknowledgement

Full credits for the idea and code go to @zhangweis.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
sCrypt

sCrypt

sCrypt (https://scrypt.io) is a company with a mission to provide integrated on-chain smart contracting solutions on Bitcoin SV