P.S.:
After I re-found this site and my previous comment on it
https://ethresear.ch/t/compact-fraud-proofs-for-utxo-chains-without-intermediate-state-serialization/5885
Although I haven't re-read it thoroughly yet, I followed the link of BIP-141 future work part they said Gmaxwell notified them of
https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki#Compact_fraud_proof_for_SPV_nodes
I think here this is not to much related:
1-It is from2015 and about from full nodes to SPV clients; ie, before the concept of Stateless clients had emerged and not concerned about it.
2-It talks about an idea that, I think, was mentioned in the MIT lecture 23 about research direction (with Peter Wuillie name too) of putting the whole link information of the creating TX, keeping a tree of already spent UTXOS,...etc
In my proposal, I can tell only if this is a double spending attempt (meaning the UTXO was there but got spent; not just a non-inclusion proof, ie proof it is not there )if the spent was in a previous TX in the same block which makes the whole block invalid in this case.
.
But strange they chose to publish it in the Ethereum research community?
Topic: Providing non-inclusion proofs and Locality of reference in the UTXOS set at the (Read 96 times)
November 13, 2021, 01:53:41 AM
November 06, 2021, 05:09:18 AM
I know most of my posts are about the UTXOS Merkle especially, but I really could use the brainstorming and Developers Bitcoin experience available in this discussion platform ...
.
1-I've learned from about a month the point behind "non-inclusion proofs" and that all append right Merkle strucutres do not provide them, still they're preferred because they provide much more Locality of reference especially for proof batching (all proofs needed to verify a block for example)
.
2-I've also learned that in the actual implementation such append right Merkle strucutres use a MAP because they receive queries from stateless nodes based on the UTXO hash as a key (and eventually answers in the same way). They don't consider keeping a map (a Go lang MAP for Utreexo) a big deal because it is on the bridge server where memory is not the main constrain.
.
3-So my idea is if we replace the language built-in MAP with a self made data structure; array of nearest po power of 2 hash entries leading to buckets.
-Due to the guaranteed bit randomness (for each bit prob(0)=prob(1)=1/2) of the robust Cryptographic hash signatures, we can except uniform distribution of UTXOS in buckets, with about 25-27bits of the hash we can reach a load factor similar to Go lang MAP of 6.5-8 with no extra book keeping data,
and constant access time (just through an index equation in the hash bits mask)
....
-This hash strucutre could be used to provide non-inclusion proofs if a complete tree was built on the table entries as leaves.
-Min inclusion proofs will have an almost fixed logN nodes this way, and are send once per block in the worstcase (valid blocks won't invoke them; invalid blocks won't continue verifying TXs after discovering an invalid one)
.
-The extra storage, still in the bridge server, won't exceed the book keeping of the built-in MAP so much
-The maintianance of the array is done anyway, however an extra timing will be consumed once per block in updating the complete tree build upon the hash and send the new Fraud Proof accumulator value
.
-Why not suffice with it? Because it's proofs are expected to be longer due to the lack of locality, we already know that, but here such proofs will be sent once per block in the worst case
(If a block contains an invalid UTXO it will be aborted, nodes will not keep validating the rest of each nodes)
.
-Finally, the non-inclusion proof will lead to a default NULL hash value agreed on in advance, and this way deletions doesn't involve swaps, we just replace the UTXO hash with the NULL hash (done in other kinds of Blockchains)
.
-Also, maybe to minimize the overhead time, the secondary Merkle tree is only calculated once per block either to send the new accumulator value or to provide a non-inclusion proof.
-If a UTXO is invalid because it got spent (and thus deleted) in this same block, the Stateless node will not have the new accumulator value that proves the non-existence. However, in this case maybe the non-inclusion proof would be "got spent in TX ID ... in this same block, with the previous proof so&so sent to you"
I will think again about possible options in this case....
.
1-I've learned from about a month the point behind "non-inclusion proofs" and that all append right Merkle strucutres do not provide them, still they're preferred because they provide much more Locality of reference especially for proof batching (all proofs needed to verify a block for example)
.
2-I've also learned that in the actual implementation such append right Merkle strucutres use a MAP because they receive queries from stateless nodes based on the UTXO hash as a key (and eventually answers in the same way). They don't consider keeping a map (a Go lang MAP for Utreexo) a big deal because it is on the bridge server where memory is not the main constrain.
.
3-So my idea is if we replace the language built-in MAP with a self made data structure; array of nearest po power of 2 hash entries leading to buckets.
-Due to the guaranteed bit randomness (for each bit prob(0)=prob(1)=1/2) of the robust Cryptographic hash signatures, we can except uniform distribution of UTXOS in buckets, with about 25-27bits of the hash we can reach a load factor similar to Go lang MAP of 6.5-8 with no extra book keeping data,
Quote
(If someone have any comments or corrections to what is written here please write it, the 6.5-8 load factor from one more medium reference I found in Google but it doesn't open as a whole so I didn't add it because I only read the highlighted part from Google
https://cs.stackexchange.com/questions/144081/how-does-the-go-language-implements-maps/144082?noredirect=1#comment304249_144082)
https://cs.stackexchange.com/questions/144081/how-does-the-go-language-implements-maps/144082?noredirect=1#comment304249_144082)
and constant access time (just through an index equation in the hash bits mask)
....
-This hash strucutre could be used to provide non-inclusion proofs if a complete tree was built on the table entries as leaves.
-Min inclusion proofs will have an almost fixed logN nodes this way, and are send once per block in the worstcase (valid blocks won't invoke them; invalid blocks won't continue verifying TXs after discovering an invalid one)
.
-The extra storage, still in the bridge server, won't exceed the book keeping of the built-in MAP so much
-The maintianance of the array is done anyway, however an extra timing will be consumed once per block in updating the complete tree build upon the hash and send the new Fraud Proof accumulator value
.
-Why not suffice with it? Because it's proofs are expected to be longer due to the lack of locality, we already know that, but here such proofs will be sent once per block in the worst case
(If a block contains an invalid UTXO it will be aborted, nodes will not keep validating the rest of each nodes)
.
-Finally, the non-inclusion proof will lead to a default NULL hash value agreed on in advance, and this way deletions doesn't involve swaps, we just replace the UTXO hash with the NULL hash (done in other kinds of Blockchains)
.
-Also, maybe to minimize the overhead time, the secondary Merkle tree is only calculated once per block either to send the new accumulator value or to provide a non-inclusion proof.
-If a UTXO is invalid because it got spent (and thus deleted) in this same block, the Stateless node will not have the new accumulator value that proves the non-existence. However, in this case maybe the non-inclusion proof would be "got spent in TX ID ... in this same block, with the previous proof so&so sent to you"
I will think again about possible options in this case....
Jump to: