Skip to content
This repository has been archived by the owner on Mar 24, 2023. It is now read-only.

Specifiy non-membership proofs for sparse Merkle tree #53

Open
musalbas opened this issue Jul 24, 2020 · 3 comments
Open

Specifiy non-membership proofs for sparse Merkle tree #53

musalbas opened this issue Jul 24, 2020 · 3 comments
Labels
documentation Improvements or additions to documentation

Comments

@musalbas
Copy link
Member

musalbas commented Jul 24, 2020

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 adlerjohn self-assigned this Jul 24, 2020
@adlerjohn adlerjohn added the documentation Improvements or additions to documentation label Jul 24, 2020
@adlerjohn
Copy link
Member

Related to #48.

@adlerjohn adlerjohn added this to the Pre-implementation draft milestone Jul 24, 2020
@adlerjohn
Copy link
Member

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
Copy link
Member Author

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.

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
documentation Improvements or additions to documentation
Projects
No open projects
Status: No status
Development

No branches or pull requests

2 participants