[bitcoin-dev] Providing "non-inclusion proofs" to "append to the right Merkles" with minimized overhead

[bitcoin-dev] Providing "non-inclusion proofs" to "append to the right Merkles" with minimized overhead

[shymaa arafat]

[-- Attachment #1.1: Type: text/plain, Size: 3155 bytes --]

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

[-- Attachment #1.2: Type: text/html, Size: 3778 bytes --]

[-- Attachment #2: IMG_20211109_003226.jpg --]
[-- Type: image/jpeg, Size: 182701 bytes --]