search

celestiaorg / celestia-specs

Celestia Specifications
Creative Commons Zero v1.0 Universal
51 stars 14 forks source link

Specifiy non-membership proofs for sparse Merkle tree #53

Open musalbas opened 4 years ago

musalbas commented 4 years ago

In the current compute-optimised SMT implementation, this simply requires an extra field in the proof for the data of the leaf found at the position of the key that non-membership is being proven for, if that leaf is not a placeholder. https://github.com/lazyledger/smt/blob/2d392fe132b6304df772fa06ab83b6d984277f06/proofs.go#L11

adlerjohn commented 4 years ago

Related to #48.

adlerjohn commented 4 years ago

I don't think any changes are needed, since the SMT proof already has a leaf value field leaf (https://github.com/lazyledger/lazyledger-specs/blob/37d911cb1ededb401d9d6a7cea7cf3a784d26bd3/specs/data_structures.md#sparse-merkle-tree-proofs), which can be used for the other leaf's value.

musalbas commented 4 years ago

In the case of a non-membership proof, the proven leaf value is nil. However, we also need a field for what the value of the leaf is that is found at the path of that key, to prove that the key at this path is not the key that the proof is for.