Compact Sparse Merkle Trees – Efficient Non-Membership Proofs

Post by sitkack » Tue, Oct 09, 2018, 5:24 AM UTC

chriswarbo wrote: post #8

rjzzleep wrote: post #5

Serious question, can someone explain to me why these things are latex documents with a little bit of code?

CS papers mostly try to explain an idea or an experimental result, describe why it is important, how it relates to existing approaches, what situations it may be useful for, what the drawbacks are, how those might be addressed in future work, etc. Pretty much none of those things are code. When some algorithm, metric, etc. does need to be presented, it's important to make it as understandable as possible to the reade…

Post by nayuki » Wed, Oct 10, 2018, 11:45 PM UTC

farazhaider wrote: post #13

nayuki wrote: post #10

There is another method to support compact membership proofs and have history-independence. Ethereum uses a Patricia-Merkle tree structure to store its state snapshots. I'm not sure if it supports compact non-membership proofs though.

Author here. There are certain implementations out there which support non-membership proofs but most of them use empty hashes to find the non-membership proofs and the underlying SMT is unordered. The approach taken in the above paper is novel in the sense that the way in which values in SMT are inserted make it ordered and this property is exploited to find the non-membership proofs through a window based method. T…