@zhangweis is on PowPing!

PowPing is a place where you can earn Bitcoin simply by socializing, for FREE.
Never tried Bitcoin? It's OK! Just come, socialize, and earn Bitcoin.
Check out zhangweis's activities

Bitcoin Script

visit channel home
Total Economy: 1.36 USD

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.

powered by powpress
link Tip
Share
tx
translate
venezia tipped:
acmonides tipped:
unwriter tipped:
xhliu tipped:
1hao tipped:
cbeast tipped:
fullcycle tipped:
eyeone tipped:
Jsut found Craig had expressed the similiar idea in an interview. https://youtube.com/watch?v=zmLfZ599oAY
@1:02:05
Wrote a intro blog in Chinese. https://shimo.im/docs/RCPTxPx8vQxxYTww/ The tech can be used on Token and Oracle. Zhang, Great Job.
https://gist.github.com/zhangweis/f651b7e12acaa7171ab087888e116dc6 It may not run but I think it's enough to express the idea.
venezia tipped:
xhliu tipped:
I read the text carefully again, and I like this solution very much. The user of this token only needs to maintain the balance table of this token off-chain. Then verify the ledger update he received, by subscribing the latest merkleroot from blockchain.
zhangweis replied:
Yes, the table is off-chain. But I'm afraid the user may need to handle all the txs related to this contract as he/she needs to build merkle path for his own balance and merkle root is not enough. Of course it can be done by a 3rd party server but as contract doesn't do that it has to be done by someone.
zhangweis replied:
The good news is that if you choose to delegate blockchain tx subscribing and merkle tree building to a 3rd party, you don't need to trust it. The merkle path can be verified against the latest merkle root and you won't be cheated by it.
zhangweis replied:
It does have some issues with the idea through. As the contract uses utxo chain, there might need some coordinator to ensure there's no double spend when 2 users send tokens at the same time. Also your balance's merkle path will be changed every time there's a state change on chain and that means you'll need to use the latest merkle path when you transfer token. I know the scrypt team has another approach of using utxo as token output but I suspect the contract can't verify the tokens on chain in that case.
MerkleProofs.com 100 BSV
Awesome! I once had a similar idea, but I don't know how to implement it. Can't wait to learn more.
zhangweis replied:
There's no working code yet. But I'm thinking of something like below: 1. The verification part is simple. It's something like: public verifyLeaf(bytes leaf, bytes merklePath, int merklePathLength, bytes merkleRoot) { int i = 0; bytes merkleValue = leaf loop (10) { i++; if (i<merklePathLength) { int left = unpack(merklePath[i*33+33]); if (left) merkleValue = sha256(merkleValue, merklePath[i*33:i*33+32]); else merkleValue = sha256(merklePath[i*33:i*33+32], merkleValue); } } require(merkleValue==merkleRoot); } 2. The update of merkle tree is trickier. We need to keep the tree structure balanced, or we'll have vulnerability of unbalanced tree. I think a full binary tree with restriction n<2^branchLength will be good. As the contract only does the verification, we can just check that for every update/delete/insert to ensure it's in good shape: require(n <= (2<<branchLength)); But the contract still needs to calculate update/insert/delete of node. Update is something quite similiar to verification: function updateLeaf(bytes leaf, bytes merklePath, int merklePathLength, bytes merklePathsToUpdate): bytes { int i = 0; bytes merkleValue = leaf loop (10) { i++; if (i<merklePathLength) { int left = unpack(merklePath[i*33+33]); if (left) merkleValue = sha256(merkleValue, merklePath[i*33:i*33+32]); else merkleValue = sha256(merklePath[i*33:i*33+32], merkleValue); } } //to be done update affected paths bytes updatedPath=b''; //bytes updatedPath = updateAffectedMerklePath(merklePathsToUpdate); return merkleValue + updatedPath } Deletion and insertion will be trickier as they'll need to update the tree structure but anyway I'm thinking of deletion like: function deleteLeaf(bytes siblingLeaf, bytes merklePath, int merklePathLength, bytes merkleRoot): bytes { int i = 0; bytes merkleValue = siblingLeaf; return this.updateLeaf(siblingLeaf, merklePath[33:], merklePathLength - 1); } function swapLeaf(byte leaf1, bytes merklePath1, int merklePathLength1, byte leaf2, bytes merklePath2, int merklePathLength2) { bytes result = this.updateLeaf(leaf2, merklePath1, merklePathLength1, num2bin(merklePathLength2) ++ merklePath2); bytes updatedMerklePath2 = result[33:]; return this.updateLeaf(leaf1, updatedMerklePath2, merklePathLength2); } Deletion can happen as deleteLeaf or swapLeaf+deleteLeaf to tune the tree structure but the good news is that we can let the sender taking care of the selection as we only verify the structure is still good. Insertion is actually turning a leaf to a node with 2 children. function insertLeaf(bytes leaf, byte onLeaf, bytes merklePath, bytes merklePathsToUpdate, bytes merklePathsToUpdate) { bytes newNode = sha256(onLeaf++leaf); return this.updateLeaf(newNode, merklePath, merklePathLength1, num2bin(merklePathLength2) ++ merklePath2); } It's just some pseudo code in my head and hope it helps.
venezia tipped:
venezia replied:
@unwriter we truly need markdown : )
unwriter tipped: