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