Closed vgonkivs closed 1 year ago
+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.
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?
Yes, so VerifyInclusion(1)
will reconstruct the Merkle Root from f and g subtree roots(and not from S5,S6,S7,S8 leaves)
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:
https://github.com/celestiaorg/nmt/blob/be509c3dcc3282ee8c6b5c951e11ee1e34ad614b/proof.go#L301-L305
Meant that this is the second implementation of VerifyInclusion. Sorry for the confusion 😅
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
?
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.
@vgonkivs, so should we close this one?
why? The idea is the same: we should be able to reconstruct the tree using subtree roots. @rootulp suggested a better approach.
suggested a better approach
From our private discussion, I had an impression that the approach is already implemented. But if not, then nvm
the approach is already implemented
No, I meant it will be easier to implement it than my
@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.
@staheri14, all leaf hashes will belong to the same nID.
We just need to make that method public.
yeah, I had the same thoughts.
Currently, the node team is implementing a Blob Module that requires proof verification. We have
Included
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 andNodes
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.For example, we want to reconstruct the tree using
f
andg
subtree roots(b will be stored inNodes
in the nmt.Proof)