4 ms·

My two cents: 1. That seems to work for complete binary Merkle trees only. 2. Authors mention "significantly reducing the size of multiproofs" while not provi

by krcz 7y ago

My two cents: 1. That seems to work for complete binary Merkle trees only. 2. Authors mention "significantly reducing the size of multiproofs" while not providing any data. Assuming using 256-bit hashes, a tree with 2^63 leafs would be needed to claim 20% reduce in size (64-bit indices, so droping them saves at most 64/(64 + 256)%). That's assuming storing hashes for proved leafs, but disregarding them wouldn't change much - as there are much more non-proved hashes to be stored.

irwt 7y ago
About the second point: I think you misunderstood something. Imagine that we have a tree with 1000 leaves and we want to have a Merkle proof that can prove the presence of, let's say 5 elements. The sparse Merkle multiproof will require an index for every non-leaf hash, so worst case around 30-40 indices (that's just an estimate, as every multiproof can have different sizes, depending on the location of the leaves). The compact Merkle multiproof on the other hand requires only 5 indices.
- krcz 7y ago
  You still need one hash for every non-leaf node, so 30-40 hashes of 256 bits each. What this algorithm saves is 30-40 indices, which is 11 bits each for a 1000-leaf tree. Even aligning to 16 bits it's doesn't seem a great optimization. Unless I misunderstood something and we are not trying to minimize the size of whole proof, but just its structure - but I see no reason why it could be useful. But I can see there are two other papers: one on distributed Bloom filters [1] and the other on Bloom trees [2], maybe these can shed some light on it, I'll check later today. [1] https://arxiv.org/pdf/1910.07782.pdf https://arxiv.org/pdf/1910.07782.pdf [2] https://arxiv.org/pdf/2002.03057.pdf https://arxiv.org/pdf/2002.03057.pdf EDIT: I haven't noticed you are one of the authors! I liked the paper, it is very clear and visualizes how Merkle (multi)proofs work in a nice way. The only thing that worries me is claim of significant reduce in the size without providing any hard data in that topic.
  - irwt 7y ago
    I am glad that you liked our paper :) (the distributed bloom filter paper requires serious editing though). Current sparse Merkle multiproofs require an index and a hash inside the proof. So in our hypothetical example that would be 30-40 indices and 30-40 hashes. Only then can a recipient of the proof perform the operations in the right order to recreate the original merkle root. With our proposal on the other hand, for this hypothetical example, we would need 30-40 hashes, and only 5 indices for a recipient to be able to recreate the correct Merkle root. Here's by the way a great repo that can create sparse Merkle multiproofs https://github.com/wealdtech/go-merkletree https://github.com/wealdtech/go-merkletree

by krcz 7y ago

irwt 7y ago

About the second point: I think you misunderstood something. Imagine that we have a tree with 1000 leaves and we want to have a Merkle proof that can prove the presence of, let's say 5 elements. The sparse Merkle multiproof will require an index for every non-leaf hash, so worst case around 30-40 indices (that's just an estimate, as every multiproof can have different sizes, depending on the location of the leaves). The compact Merkle multiproof on the other hand requires only 5 indices.

krcz 7y ago
You still need one hash for every non-leaf node, so 30-40 hashes of 256 bits each. What this algorithm saves is 30-40 indices, which is 11 bits each for a 1000-leaf tree. Even aligning to 16 bits it's doesn't seem a great optimization. Unless I misunderstood something and we are not trying to minimize the size of whole proof, but just its structure - but I see no reason why it could be useful. But I can see there are two other papers: one on distributed Bloom filters [1] and the other on Bloom trees [2], maybe these can shed some light on it, I'll check later today. [1] https://arxiv.org/pdf/1910.07782.pdf https://arxiv.org/pdf/1910.07782.pdf [2] https://arxiv.org/pdf/2002.03057.pdf https://arxiv.org/pdf/2002.03057.pdf EDIT: I haven't noticed you are one of the authors! I liked the paper, it is very clear and visualizes how Merkle (multi)proofs work in a nice way. The only thing that worries me is claim of significant reduce in the size without providing any hard data in that topic.
- irwt 7y ago
  I am glad that you liked our paper :) (the distributed bloom filter paper requires serious editing though). Current sparse Merkle multiproofs require an index and a hash inside the proof. So in our hypothetical example that would be 30-40 indices and 30-40 hashes. Only then can a recipient of the proof perform the operations in the right order to recreate the original merkle root. With our proposal on the other hand, for this hypothetical example, we would need 30-40 hashes, and only 5 indices for a recipient to be able to recreate the correct Merkle root. Here's by the way a great repo that can create sparse Merkle multiproofs https://github.com/wealdtech/go-merkletree https://github.com/wealdtech/go-merkletree