Bargad is a Trillian like data integrity framework for building efficient blockchains (like Ethereum Plasma does), transparency logs (e.g Certificate Transparency), secure file systems and more.
It Written in Elixir with focus on reliability, concurrency and scalability.
Author here, thanks for reading through the paper.
I think the confusion is because I wrote the pseudocode in a functional programming style so there are a few keywords being used which are causing confusion. ( Which i mentioned in the paper. )
The insert function uses the left.key and right.key to calculate the minimum distance for the key to be inserted.
And there is a cond statement which will execute only of the conditions.
And the pseudocode I wrote was in a functional programming style so the arguments in both the functions are same, just the name of the last argument is different, i.e root and leaf as I wanted to imply pattern matching happens.
The interesting part of the paper is that it outlines a new way to create a Sparse merkle tree, which inherently becomes ordered due to the insertion algorithm used. This ordered property is exploited to find the non-membership proof in a new way which does not require empty hashes and is compact. History independence also follows from the insertion algorithm used.
I'll be releasing an implementation for this paper soon so the proofs can be checked empirically as well.
Perhaps you missed it, in Section 5 I've mentioned that the hash function SHA256 behaves as an ideal hash function, an assumption in cryptography called Random Oracle Model.
By virtue of this model, the proofs for Structure, Space and Max-Proof of SMT are implied.
I'm also working on an implementation for the concepts mentioned in the paper so the proofs can also be verified emperically.
It's not the reader's job to fill in implied proofs. It's your job as the author to give them enough information to check your argument. In some cases "this follows from results A, B, C" is sufficient, but it's often not.
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?
