Hacker News Reader

Comment by nemo1618 | Hacker News Reader

Huh. I think I created this independently about a year ago. My implementation also works in streaming fashion, so you can compute proofs without holding all of the data in memory. I didn't think it was novel enough to write a paper about. ¯\_(ツ)_/¯

Maybe I should publish a paper about the "diff proofs" I also came up with, for proving arbitrary modifications to a Merkle tree?

https://gitlab.com/NebulousLabs/merkletree/-/commit/bae5b547...

View on HN

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

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