VerifyInclusion over the subtree roots

[vgonkivs]

Currently, the node team is implementing a Blob Module that requires proof verification. We haveIncluded method that ensures that the requested blob was included in the DAH at a certain height. As our light nodes do not store leaves, it
will be very complicated for them because they will have to request all leaves from other nodes and verify the inclusion.
In fact, verifyInclusion reconstructs the Merkle tree root from leaves and Nodes and compares it with the passed one.
It will be very helpful for us if we could verify the inclusion using subtree roots(built from leaves). These subtree roots will be constructed on 1 level above the leaves.

                a
              /   \
            /       \
          /           \
        b              c
      /   \         /     \
    d      e       f       g
  /  \    /  \   /   \   /   \
[S1][S2][S3][S4][S5][S6][S7][S8]

For example, we want to reconstruct the tree using f and g subtree roots(b will be stored in Nodes in the nmt.Proof)

[Wondertan]

+1, for now, we went with the approach that fetches all the leaves to optimize later. Once the Blob module lands, it will become blocking.

[evan-forbes]

to check my understanding of what is needed: if we know which nodes and leaves are needed, then the only remaining thing is to stick them in the nmt.Proof struct in the correct order, right?

[vgonkivs]

Yes, so VerifyInclusion(1) will reconstruct the Merkle Root from f and g subtree roots(and not from S5,S6,S7,S8 leaves)

[rootulp]

Yes, so VerifyInclusion(1) will reconstruct the Merkle Root from f and g subtree roots(and not from S5,S6,S7,S8 leaves)

Which parameter does the argument 1 refer to in this example? Ref:

nmt/proof.go

Lines 301 to 305 in be509c3

	// 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`.
	func (proof Proof) VerifyInclusion(h hash.Hash, nid namespace.ID, leavesWithoutNamespace [][]byte, root []byte) bool {

[vgonkivs]

Meant that this is the second implementation of VerifyInclusion. Sorry for the confusion 😅

[rootulp]

I have a clarifying question. I interpret the diagram for an NMT like so:

                a
              /   \
            /       \
          /           \
        b              c
      /   \         /     \
    d      e       f       g
  /  \    /  \   /   \   /   \
  h   i   j  k   l   m   n   o
  |   |   |  |   |   |   |   |
[S1][S2][S3][S4][S5][S6][S7][S8]

where S1 is share 1 and h is the namespaced hash of S1 (see HashNode). Given such a diagram, does this proposal describe using the namespaced hash for each share (i.e. h through o) rather than f - g?

[vgonkivs]

Previously my idea was to calculate over f and g but h-o sounds good to me. And we discussed with @rootulp that it could be even better.

[Wondertan]

@vgonkivs, so should we close this one?

[vgonkivs]

why? The idea is the same: we should be able to reconstruct the tree using subtree roots. @rootulp suggested a better approach.

[Wondertan]

suggested a better approach

From our private discussion, I had an impression that the approach is already implemented. But if not, then nvm

[vgonkivs]

the approach is already implemented

No, I meant it will be easier to implement it than my

[staheri14]

@vgonkivs If what is described in this proposal is sufficient for your use-case, then we already have a private method verifyLeafHashes in the nmt lib that can take the hash of leaves, instead of the leaves, and can verify their inclusion, however, there is a constraint and that is all the leaf hashes should belong to the same namespace ID. We just need to make that method public.

[vgonkivs]

@staheri14, all leaf hashes will belong to the same nID.

We just need to make that method public.

yeah, I had the same thoughts.