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.
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.
To prove a certain value Y doesn't exist in the tree, the closest two values X and Z which bound Y form the non-membership proof.
This method avoids using empty hashes and the repetitive computation which comes with it.
And Merkle Patricia Trie currently does not support Non-membership proofs.
Interesting ideas. I understand the high-level idea of using X and Z to bound Y.
Questions: Can you clarify what it means to use empty hashes for non-membership proofs? / For the Merkle-Patricia Tree structure, if the branches are ordered, wouldn't it be possible to use bounding for non-membership proofs?
