Hacker News Reader

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..

View on HN

Can 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/bae5b54749...

You 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/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.

Ha, 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. :)

Reply on news.ycombinator.com