LearnBitcoin

Bitcoin Dev Archive 2021

Providing "non-inclusion proofs" to "append to the right Merkles" with minimized overhead

1 message, 11 Nov 2021. Started by shymaa arafat.

shymaa arafat

Permalink Original thread on gnusha.org

shymaa arafat permalink original

Dear Bitcoin Developers, Hi everybody, Please allow me to suggest this idea, hope you find it worth reading & commenting....

While append to the right UTXO Merkles have the much needed advantage of locality of reference that leads to shorter batch proofs, they're criticized by some for not providing non-inclusion proofs. This is a suggestion to slightly change the needed anyway map/dictionary to map the UTXOS to their positions as leaves given their hash value, so that it can provide non-inclusion proofs....

1-A 2⁶⁴ (could be tuned*) pointer vector is allocated to put the UTXO in a bucket according to its hash. 2-Due to the Cryptographic hash robustness & bit randomness UTXO hashes should fall uniformly as all buckets are equiprobable and each bucket is expected to contain 1-2 UTXOS (less than Go lang map load factor which is 6.5-8, 2³² entry may lead to the same) 3-Insertion is adding a node (in order)to the bucket linked list, deletion is deleting a node from the bucket list; the vector bucket pointer maybe adjusted in the process from or to NULL value. . The strucutre should be as in attached figure: Vector of pointers to buckets that could be linked lists with the following fields in each node: -A pointer to the UTXO leaf in the main Merkle -The value of the remaining hash bits, or could be omitted with its value with the leaf node. -two bit flag that will be explained shortly. . 4-To save computation time, we may calculate and send the accumulated root value of this secondary tree only once per block; either at the end if valid or when encountering an invalid UTXO to send the non-inclusion proof and abort the whole block. Like the Tx Merkle, maybe no need to store the tree or maybe it will save time for the non changed parts (experimental). 5-The non-inclusion proof will be send according to the previous block accumulated root, so during batch preparation a newly inserted UTXO will be flagged 1, a deleted UTXO is flagged -1, and 0 means value the same as previous block. 6-If the block is valid, update and reset flags to 0 while computing the new root. A hash of a bucket is the concatenation of all its nodes(expected to be2), and empty buckets are substituted by a default NULL hash value. 7-If we had an invalid UTXO, we have two cases: a)-The hash doesn't exist in any case ( not even with a deleted flag), in this case we send the usual non-inclusion proof considering old status before any UTXO from this block. b)-The UTXO hash is there, but has a deleted flag (it was spent before during this block); ie, a double spend within the same block. Now, in this case I do have some doubts and suggestions or comments are welcomed: I think we should resend the previous inclusion proof along saying something like "TX ID ....spent it with proof...." I guess this an implementation detail of how to point out to a previous proof in the same block ( I assume such a block is going to be aborted anyways after the invalid UTXO and old status will be resumed, if this is wrong please say so) . That's all, thank you for your time, Shymaa M. Arafat