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.

https://github.com/celestiaorg/nmt/blob/1d72cffd9fb40ecea93660be2e19ca3c1ecea53f/proof.go#L209

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:

https://github.com/celestiaorg/nmt/blob/1d72cffd9fb40ecea93660be2e19ca3c1ecea53f/nmt.go#L122

[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: https://github.com/celestiaorg/celestia-specs/issues/48

[staheri14]

Is the requested modification in this issue still required?

[adlerjohn]

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