NMT mainnet readiness

[staheri14]

This meta-issue is created with the objective of determining the priority of the NMT issues concerning the mainnet. It is important to note the current list provides a snapshot of the issues and is subject to change as further issues are detected.

In progress

• feat: compute leaf hashes immediately after data items are pushed #108
• Explain normal Merkle inclusion and range proof in the NMT specification #128
• redundant hashing in the computeRoot  #143

Error handling [Mainnet]

• Capture index range error in the computeRoot helper #137
• validateSiblingsNamespaceOrder can panic upon invalid inputs #138
• verifyLeafHashes function will panic if called from VerifyInclusion function over an empty proof #140
• VerifyLeafHashes can panic in the completeness check if proof.nodes are not namespaced #141
• buildRangeProof can panic upon invalid input range #142
• ValidateInclusion function can panic if it is called with an invalid nid #157
• VerifyNamespace panics if called on an empty range, but with non-empty nodes #164

Code correctness [Mainnet]

• Check ordering of namespace among child nodes in HashNode function #129
• Assumption that leaves are ordered is not used consistently #121
• IgnoreMaxNS leads to false computing maxNs #148
• ValidateNode does not check the exact size of the non-leaf nodes #153
• The updateMinMaxID method disregards the IgnoreMaxNamespace semantic #159
• overlap between empty proofs and absence proofs #181
• Inconsistency in the EmptyRoot values #196
• Vulnerability in VerifyNamespace: Partial Absence Proofs  #110 and Assessment of Soundness for the NMT Partial Namespace Absence Proof  #118

Code cleanup

• Duplication of code #130
• Introducing a generic function for generating example trees #132
• Create accessory method for consistent tree size retrieval #160

Docs

• chore: add a link to the nmt specification inside the nmt implementation #98

• What are the benefits of IgnoreMaxNamespace? #117

• The VerifyInclusion() function does not check proof completeness  #161

[staheri14]

A few of the issues previously outlined in this epic have been deemed non-critical. Therefore, they've been removed from the main description. However, they are now captured within this comment for future reference.

Docs

• Incorporating test-vectors in the NMT specs #111

Long term

• Explore if we want to store inner nodes (in memory) too #17
• Implement NMT in Rust + make it easy to use from other languages #84
• Use the go-internal fuzzer soon. #60

Additional features

• api: Push for data/shares with decoupled namespace #55
• Proof struct is missing a function for range verification #154
• api: Make the api consistent #59
• New verify and create functions are needed for NamespaceMerkleTreeInclusionProof. #46

Implementation robustness

• namespace: PrefixedData/PrefixedData8 are easy to misuse #71 (nice to have for the mainnet)
• NamespacedMerkleTree.foundInRange should not narrow uint64 to int #70 (nice to have for the mainnet)
• clarify go-routine safety  #39 (nice to have for the mainnet, even lower than the above two)

[staheri14]

Omitting the following two issues from the description of this epic, and with that, we can close the current epic:

• Verification functions do not check the consistency between the NID of the supplied leaves and the queried NID #183: While this issue is currently under investigation, it has not been deemed critical for this epic. The primary objective of this epic was to prepare the nmt module for the latest release of the core/app, which has already been accomplished.
• NamespacedMerkleTree.foundInRange should not narrow uint64 to int #70 (nice to have for mainnet): This issue has been partially resolved in this PR, where the potential for panic has been mitigated through comprehensive code refactoring. Consequently, within the scope of this epic, appropriate measures have been implemented.

New features [Good for Mainnet, not necessary though]

• Defining and Clarifying the Verification Process for NMT Proofs Generated from Non-Lexicographically Ordered Trees #97

Note that while removing these issues from this epic, we may later follow them up in another fresh epic with a new set of features more targeted for the mainnet.