3 ms·
I don't want to be rude, but after checking your code I can say that what you did is most definitely not the same thing as the compact Merkle multiproof idea..
by irwt 7y ago
I don't want to be rude, but after checking your code I can say that what you did is most definitely not the same thing as the compact Merkle multiproof idea..
- nemo1618 7y agoCan you elaborate? Like yours, my proofs verify the presence of k arbitrary leaves within a tree, and require only the indices of those k leaves. Here's a test case illustrating such a proof: https://gitlab.com/NebulousLabs/merkletree/-/blob/bae5b547495f9dddbd4ddeecfdcb00cb89d99d76/range_test.go#L205 https://gitlab.com/NebulousLabs/merkletree/-/blob/bae5b54749...
- irwt 7y agoYou son of a gun, good job. I initially looked at the wrong part of the code, my apologies. This part describes it very well: https://gitlab.com/NebulousLabs/merkletree/-/blob/master/range.go#L197 https://gitlab.com/NebulousLabs/merkletree/-/blob/master/ran... It's basically the same thing. Implementation wise it's slightly different, but it's the same idea. During the upcoming days I'll add to the paper that you were the first to propose this algorithm.
- nemo1618 7y agoHa, thanks. Our algorithms differ slightly in that mine deals with ranges (rather than individual leaves) and processes the tree "left to right" rather than "bottom to top". As such, your algorithm is probably better suited to generic trees, whereas mine was specifically designed for "complete" binary trees. But otherwise, they are quite similar. :)