NamespaceProof API compability with the Go implementation

[zvolin]

Hi, I have a question about the API. When it comes to proving, in Go implementation I can see those methods:

// VerifyNamespace verifies a whole namespace, i.e. 1) it verifies inclusion of
// the provided `data` in the tree (or the proof.leafHash in case of absence
// proof) 2) it verifies that the namespace is complete i.e., the data items
// matching the namespace ID `nID`  are within the range [`proof.start`,
// `proof.end`) and no data of that namespace was left out. VerifyNamespace
// deems an empty `proof` valid if the queried `nID` falls outside the namespace
// range of the supplied `root` or if the `root` is empty
//
// `h` MUST be the same as the underlying hash function used to generate the
// proof. Otherwise, the verification will fail. `nID` is the namespace ID for
// which the namespace `proof` is generated. `data` contains the namespaced data
// items (but not namespace hash)  underlying the leaves of the tree in the
// range of [`proof.start`, `proof.end`). For an absence `proof`, the `data` is
// empty. `data` items MUST be ordered according to their index in the tree,
// with `data[0]` corresponding to the namespaced data at index `start`,
//
//  and the last element in `data` corresponding to the data item at index
//  `end-1` of the tree.
//
// `root` is the root of the NMT against which the `proof` is verified.
func (proof Proof) VerifyNamespace(h hash.Hash, nID namespace.ID, leaves [][]byte, root []byte) bool {

// The VerifyLeafHashes function checks whether the given proof is a valid Merkle
// range proof for the leaves in the leafHashes input. It returns true or false accordingly.
// If there is an issue during the proof verification e.g., a node does not conform to the namespace hash format, then a proper error is returned to indicate the root cause of the issue.
// The leafHashes parameter is a list of leaf hashes, where each leaf hash is represented
// by a byte slice.
// If the verifyCompleteness parameter is set to true, the function also checks
// the completeness of the proof by verifying that there is no leaf in the
// tree represented by the root parameter that matches the namespace ID nID
// but is not present in the leafHashes list.
func (proof Proof) VerifyLeafHashes(nth *Hasher, verifyCompleteness bool, nID namespace.ID, leafHashes [][]byte, root []byte) (bool, error) {

// VerifyInclusion checks that the inclusion proof is valid by using leaf data
// and the provided proof to regenerate and compare the root. Note that the leavesWithoutNamespace data should not contain the prefixed namespace, unlike the tree.Push method,
// which takes prefixed data. All leaves implicitly have the same namespace ID:
// `nid`.
// VerifyInclusion does not verify the completeness of the proof, so it's possible for leavesWithoutNamespace to be a subset of the leaves in the tree that have the namespace ID nid.
func (proof Proof) VerifyInclusion(h hash.Hash, nid namespace.ID, leavesWithoutNamespace [][]byte, root []byte) bool {

How does those compare to the interface exposed by this crate? Can I achieve the same functionality as in Go using those methods? From NamespacedProof:

/// Verify that the provided *raw* leaves occur in the provided namespace, using this proof
pub fn verify_complete_namespace(
    self,
    root: &NamespacedHash<NS_ID_SIZE>,
    raw_leaves: &[impl AsRef<[u8]>],
    namespace: NamespaceId<NS_ID_SIZE>,
) -> Result<(), RangeProofError> {

/// Verify a range proof
pub fn verify_range(
    self,
    root: &NamespacedHash<NS_ID_SIZE>,
    raw_leaves: &[impl AsRef<[u8]>],
    leaf_namespace: NamespaceId<NS_ID_SIZE>,
) -> Result<(), RangeProofError> {

From NamespacedMerkleTree

fn verify_namespace(
    &self,
    root: &NamespacedHash<NS_ID_SIZE>,
    raw_leaves: &[impl AsRef<[u8]>],
    namespace: NamespaceId<NS_ID_SIZE>,
    proof: NamespaceProof<M, NS_ID_SIZE>,
) -> Result<(), RangeProofError> {

[preston-evans98]

@zvolin If I'm understanding correctly that the go version operates on raw (unhashed) leaves, then NamespacedProof.verify_complete_namespace should be semantically identical to the go function VerifyNamespace except that the hasher is set at compile time.

NamespacedProofverify_range is currently equivalent to VerifyLeafHashes(false, ...) except that it operates on raw (unhashed) leaves. We should be able to make it exactly equivalent with a by removing the logic that hashes the inputs, adding the verify_completeness parameter, and making a small change to the function body:

// Change lines 74-80 of nmt_proof.rs from...

    tree.inner.check_range_proof(
        root,
        &mut &leaf_hashes[..],
        &mut siblings,
        start_idx as usize,
    )?;

// to...

   let range_proof_type = tree.check_range_proof(
        root,
        &mut &leaf_hashes[..],
        &mut siblings,
        start_idx as usize,
    )?;
    if verify_completeness {
        if let RangeProofType::Partial = range_proof_type {
            return Err(RangeProofError::MissingLeaf);
        }
    }

VerifyInclusion looks to me like it's identical to NamespacedProof.verify_range

[preston-evans98]

I'm happy to accept a PR to adjust the APIs as necessary here. If you do plan to expose methods that verify namespace completeness, though, lets make sure those APIs have test coverage.

[zvolin]

So with those 2 PR's that I linked, we're currently fine verifying all the proofs received from celestia share/blob API, tho there may be other things needed in the future that we don't see yet

[preston-evans98]

@zvolin, is there any remaining work to be done on this issue?

[zvolin]

no that I'm aware of, so far we haven't spot anything else, thanks