4 ms·

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

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/bae5b547495f9dddbd4ddeecfdcb00cb89d99d76 https://gitlab.com/NebulousLabs/merkletree/-/commit/bae5b547...

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 ago
  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/bae5b547495f9dddbd4ddeecfdcb00cb89d99d76/range_test.go#L205 https://gitlab.com/NebulousLabs/merkletree/-/blob/bae5b54749...
  - irwt 7y ago
    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/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 ago
      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. :)

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 ago
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/bae5b547495f9dddbd4ddeecfdcb00cb89d99d76/range_test.go#L205 https://gitlab.com/NebulousLabs/merkletree/-/blob/bae5b54749...
- irwt 7y ago
  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/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 ago
    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. :)