Merkle tree proof based data storage
Merkle tree proof based data storage and verification for bitcoin sv script.
In the proposal of layer 1 token contract (https://medium.com/coinmonks/layer-1-tokens-on-bitcoin-sv-e78c8abf270d), the entire data set is stored and transitioned in every utxo chain. It's unrealistic to scale to something like 1 million accounts.
In general, we need to find a way for contract's data storage with relatively small data in every contract utxo.
I'll use token contract as an example to show the idea. The idea is to have stakeholders to do the calculation and data storage. The contract (bitcoin script code) only does the verification. As for data storage verification, a merkle tree is a good match for that.
The contract stores the merkle root of every state in utxo. For each state change (transfer/mint/burn,...etc), the new merkle root will be stored in a new utxo.
The spender will need to index the data, construct the merkle tree and provide data record (leaf content), signature and the merkle proof to the contract, the contract will verify the content and merkle proof against the state merkle root to ensure the leaf exists in current state (merkle root).
A transfer will need to update the merkle tree. The contract will also need to verify the merkle tree update (insert/delete/update) submitted by the spender. A new merkle root will be calculated and stored in the utxo.