From: shymaa arafat <shymaa.arafat@gmail•com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists•linuxfoundation.org>
Subject: [bitcoin-dev] Providing "non-inclusion proofs" to "append to the right Merkles" with minimized overhead
Date: Fri, 12 Nov 2021 00:28:39 +0200 [thread overview]
Message-ID: <CAM98U8nTn+fG-rR16q1yf=uvzbRHmxve0g+szJPsvUfmKJP7Cg@mail.gmail.com> (raw)
[-- 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 --]
reply other threads:[~2021-11-11 22:28 UTC|newest]
Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CAM98U8nTn+fG-rR16q1yf=uvzbRHmxve0g+szJPsvUfmKJP7Cg@mail.gmail.com' \
--to=shymaa.arafat@gmail$(echo .)com \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox