New verify and create functions are needed for NamespaceMerkleTreeInclusionProof.

[nusret1996]

A new verify function is needed to verify a single share via a NamespaceMerkleTreeInclusionProof defined in celestia-specs.

This function should take (i) a NMT root of type namespace.IntervalDigest, (ii) a hash function of type hash.Hash, (iii) a proof of type NamespaceMerkleTreeInclusionProof and (iv) a share of type Share, and output a boolean and an error that is (true, nil) if the share is committed by the NMT root inside the NMT and the proof of type NamespaceMerkleTreeInclusionProof is correct.

Similarly, a new create function is needed to create a NamespaceMerkleTreeInclusionProof. This function should take the index of the Share inside the NMT and output the NamespaceMerkleTreeInclusionProof corresponding to the share.

[liamsi]

What is wrong with the existing verify method? I think this was implemented even before the spec defined this.

nmt/proof.go

Line 209 in 1d72cff

func (proof Proof) VerifyInclusion(h hash.Hash, nid namespace.ID, data []byte, root []byte) bool {

This function should take (i) a NMT root of type namespace.IntervalDigest

Note that this type got removed as per #48.

Similarly, a new create function is needed to create a NamespaceMerkleTreeInclusionProof. [...]

Similarly, what is wrong with:

nmt/nmt.go

Line 122 in 1d72cff

func (n NamespacedMerkleTree) Prove(index int) (Proof, error) {

[nusret1996]

NamespaceMerkleTreeInclusionProof as defined in celestia-specs is different from the proof of type Proof that is currently defined. @evan-forbes and I were actually thinking that NamespaceMerkleTreeInclusionProof as defined in the specs should be changed to match the existing Proof struct rather than writing two new functions and defining a new proof struct matching the specs. This should be discussed with @adlerjohn who has written the spec.

[liamsi]

I think what is missing in the specs is a range proof for the whole namespace which is needed for what is called application proofs in the LL paper.
IMO, implementation-wise it does not make much sense to then implement the single inclusion proof not as a range proof then as well (with (proof.start, proof.end) = (i, i+1), a range including one leaf only). Both should be isomorphic and it is easier to change this in the spec than in the implementation.

This is also related: celestiaorg/celestia-specs#48

[staheri14]

Is the requested modification in this issue still required?

[adlerjohn]

I don't think so. cc @evan-forbes for confirmation