Closed staheri14 closed 1 year ago
@liamsi I would appreciate your thoughts on this 🙏
Ok, so this is not intentional and should be easy to fix: the private fields tree.minNID
and tree.maxNID
were only introduced to keep track of the latest pushed min/max namespace and accidentally started to be used in namespaced proofs computation (as you explained above).
An easy fix would be to use n.MinNamespace()
and n.MaxNamespace()
in ProveNamespace
respectively. We should also update the comment on the private fields such that it is clear they are not supposed to be used for anything else.
@Wondertan @vgonkivs does this impact Celestia node's logic in any way? tldr are the proofs for parity namespaces expected to be non-empty in node?
Ok, so this is not intentional and should be easy to fix: the private fields
tree.minNID
andtree.maxNID
were only introduced to keep track of the latest pushed min/max namespace and accidentally started to be used in namespaced proofs computation (as you explained above). An easy fix would be to usen.MinNamespace()
andn.MaxNamespace()
inProveNamespace
respectively. We should also update the comment on the private fields such that it is clear they are not supposed to be used for anything else.
Thanks @liamsi for your input and clarification. So, given that this is has not been an intential behaviour of the nmt, I am going to implement the fix.
@Wondertan @vgonkivs does this impact Celestia node's logic in any way? tldr are the proofs for parity namespaces expected to be non-empty in node?
Agree with this, it is important to understand the implications of this fix on celestia-node.
@liamsi Another question regarding the IgnoreMaxNamespace
flag is whether it is necessary to have a method to return the actual namespace range of the tree when this flag is turned on. Currently, all leaves with the maximum NID are somewhat concealed within the tree, giving the appearance that they do not exist. The reason is that the NMT struct lacks a method to return the actual range of the namespace tree without considering the IgnoreMaxNamespace
flag. Should we consider adding such a method? would it be useful?
Another question regarding the IgnoreMaxNamespace flag is whether it is necessary to have a method to return the actual namespace range of the tree when this flag is turned on.
I am not sure why that would that be needed? In Celestia: for the first half of the tree, the namespace range is reflected in the root. For the second half, the namespace is always the same and also known: it's the parity/max namespace.
It should be possible to prove that a parity leaf is part of the tree though 🤔
Reposting my comment from Slack in here:
I am not sure why that would that be needed? In Celestia: for the first half of the tree, the namespace range is reflected in the root. For the second half, the namespace is always the same and also known: it's the parity/max namespace.
I understand your point about Celestia's data square rows and columns. When all shares are pushed to the NMT, the tree structure has a specific structure known to the application. However, if one wants to determine the NMT's namespace range at an arbitrary point in the code (not only when all the shares are pushed), the tree alone does not provide information about the actual NID range. Therefore, the application must keep track of the data that has been added to the tree to determine the NID range. However, it seems there is no practical use case for this. So, thank you, I got my answer. :+1:
It should be possible to prove that a parity leaf is part of the tree though 🤔
Right, and it is possible using the index of a parity share i.e., the index of the leaf in the NMT.
Celestia-node uses IgnoreMaxNamespace
, but I looked through the code to understand all possible implications precisely. In short, this bug does not affect celestia-node because our tests would fail with false negatives.
The maxNID is only used by ProveNamespace which is untouched by Celestia-node. Instead, we build inclusion proofs with the lower level NewInclusionProof, by reading out proofs from disk.
Problem
The utility method updateMinMaxID in nmt.go does not consider the
IgnoreMaxNamespace
semantic when updating themaxNID
field of theNamespacedMerkleTree
after each leaf is pushed using Push. This leads to inconsistency between the name ID range stored byNamespacedMerkleTree.minID
andNamespacedMerkleTree.maxID
and the name ID range extracted from the NMT via its MaxNamespace() method, which looks at the NMT's root name ID range affected by theignoreMaxNamespace
logic. Note that the valuesNamespacedMerkleTree.minID
andNamespacedMerkleTree.maxID
are used to compare queried NIDs when creating namespace proofs, as shown in this part of the code. This means that queries for the max namespace ID (i.e., parity share name ID), wont be responded by an empty proof. This is against the original purpose of theIgnoreMaxNamespace
flag.Below is a sample test to demonstrate the inconsistency set out in this issue:
Acceptance Criteria
This issue is to decide on the correct behavior (is this inconsistency intentional or not) and make the necessary changes to resolve this inconsistency (or document the rationale of this inconsistency).