Why do we need Accumulators?

[Shymaa-Arafat]

Since I read this paper
https://eprint.iacr.org/2016/683.pdf
and the idea of shortening the proof length by doing more calculations, a question keeps popping up in my head and I try to hold the hypothesis as it feels like I lost all I understood and people will tell me u r doomed to go back to lesson 1 again.

However, when I learned about graftroot O(1) signature verify and the debatable comparison with MAST, maybe it does make sense to ask:

Why do we need bridge servers to store a Merkle strucutre of UTXOS and send proofs?

Why not send directly the stored UTXO hash (maybe concatenated with the block no & encrypted if needed) for the stateless node to use it to verify just as a typical full node would do???

[Shymaa-Arafat]

Maybe the bid is that the needed UTXOS to verify by a block say M UTXOS (about 2-3k) are all contiguous in the Merkle strucutre and they will need a total of less than M nodes proofs as they constitute one large subtree and they all could be proved by one or two paths; ie O( log (the total UTXO set)), let's call it O(log N)

But since in practice most of the time u prove like 2k UTXOS using about 10K nodes and u consider this an achievement (comparing to the average of 2k * log (76*20⁶)
Then why don't u just send the stored 2k hashes, maybe with a one accumulated hash of them all as a caution from transmission errors?

[Shymaa-Arafat]

I'm sorry for keeping this post for sometime, or for posting it originally maybe,

It's for giving a proof you as a node posses part of it

Meaning SPV clients depend on full nodes to send them TX proofs, but need to ask more than one full node,...etc

If I'm going to tell u as a bridge that hashes of UTXOS say A,B are correct, but that of C is wrong why would you trust me?

If u have a piece of the proof stored with u from earlier, you will be more sure ( that's more of a proof cryptographically)

-If we just like onion hash them all and I store the accumulated hash, it is secure if u could verify but how? you will need the whole set this way. That's why we use a Merkle Tree so that u need only O(log N) hashes to verify.

-That's also why Utreexo & append right Merkleization in general (not based on the hash value as a key) does not provide proof of non-inclusion:

- They could tell u "doesn't exist", trust me just like that.
-However, keyed on hash Merkle strucutres could give u the two adjacent proofs of closest existing hashes before& after this one and u can verify for urself (with the root value u have from before) that these 2 leaves are adjacent and no way there is another leaf in the middle (in this tree according to this root)
....
I must thank Bolton Bailey the author of "Merkle Trees Optimized for Stateless Nodes in Bitcoin" for being patient in answering and explaining and I was just can't get it don't know why now after it became clear.
Honestly, I think maybe he is going to use the thread as a part of training data for developing an AI smart teaching assistant to answer learners; after all he has some work in machine learning.

[NotATether]

I'm not going to pretend that I understand the paper or anything but if bitcoin were to implement a UTXO Merkle tree, there wouldn't be any sparse leaves because the UTXOs are sorted and paired into two, to generate the branches.

That means the compact merkle tree you'd get from this is the smallest possible one, any larger sized Merkle tree would have to have "holes" in place of UTXOs for leaves to make it sparse - to store these in the vector of UTXOs (the data structure the UTXOs are represented in now) would actually waste space.

[Shymaa-Arafat]

Maybe the bid is that the needed UTXOS to verify by a block say M UTXOS (about 2-3k) are all contiguous in the Merkle strucutre and they will need a total of less than M nodes proofs as they constitute one large subtree and they all could be proved by one or two paths; ie O( log (the total UTXO set)), let's call it O(log N)

But since in practice most of the time u prove like 2k UTXOS using about 10K nodes and u consider this an achievement (comparing to the average of 2k * log (76*20⁶) applinked
Then why don't u just send the stored 2k hashes, maybe with a one accumulated hash of them all as a caution from transmission errors?

I agree with you.

I'm sorry but this was not right to agree with?!
I corrected it in the next reply, we use Merkle proofs because with them nodes have a piece of the proof (the root) and will verify by themselves the correctness of the UTXO hash. If the server just sent to you yes the hash you have is valid, or no it is not, how would you be sure the server is not lying?
(That's why SPV clients usually ask more than one node)

This is doesn't contradict with the fact that we hope to get shorter proofs if we manage to make the required to proof UTXOS adjacent in the tree
.

& yes the paper is not about Bitcoin Blockchain, but it gave me an intuition somehow because the difference between: 1-Append to right Merkle Trees, like Utreexo & MMR, where u can make all ur trees complete ( if the UTXOS are arranged according to creation time, u can assign them in order to power of 2 complete trees)

2-Keyed on hash Merkle Trees, these trees are not complete by nature. The paper assumes a complete large power of 2 tree with some default value leaves say 0, then the true tree becomes like a sparse subset tree from this big complete one.
-Then the paper, solving different problem with different constraints, compare storing this tree as B, B+,B-, and another previously known method (maybe hash tables, I don't remember now) for space-time trade offs.