2023-03-30 Celestia Namespaced Merkle Tree Library Audit

Security Audit Report

Celestia Q1 2023: NMT

Authors: Ivan Gavran, Andrija Mitrovic

Table of Contents Audit overview............................................................................................................. 1 The Project 1 Conclusions 1 Disclaimer 1 Overview of the audit results...................................................................................... 2 Specification overview 2 Code review 2 Formal Model in Quint 2 Findings ....................................................................................................................... 4 Check of the namespace ordering missing in HashNode 6 IgnoreMaxNS leads to false computing maxNs 7 The function verifyLeafHashes will panic if called from VerifyInclusion function over an empty proof 9 Wrapper Push function will panic if the data is invalid 10 ValidateInclusion function can panic if it is called with an invalid nid 11 VerifyNamespace panics if called on an empty range, but with non-empty nodes 13 Left and right child swapped in the documentation 14 Description of calculateAbsenceIndex function in code comments incorrect 15 The assumption that leaves are ordered is not used consistently 16 Typo in the spec: end instead of end-1 17 The code-comment about the return value for ProveNamespace function does not correspond the code 18 Duplication of code in the HashNode function 19 Hasher initialization and reset should be done after validity checks 20 Overly specific helper functions that can be replaced by one generic function 21 Unclear explanation of namespace calculation when the option IgnoreMaxNamespace is set 22 Computing leaf hashes should be done after the range check 23 Duplicated test cases 24 Sanity check should be done immediately after tree creation 25 Proof struct is missing a function for range verification 26 An incomplete test 27 © 2023 Informal Systems Celestia Q1 2023: NMT

Audit overview The Project In March 2023, Informal Systems has conducted a security audit for Celestia of their NMT (Namespaced Merkle Tree) library. The focus of the audit was 1) checking the documentation of the library, 2) checking the implementation and the usage within the NMT wrapper, and 3) delivering the formal model of the NMT proofs. The audited commit hashes for relevant repositories are:

• celestiaorg/nmt : 8be15c4 • celestiaorg/celestia-app (the wrapper around NMT): 9266e3f

The audit took place from March 1, 2023 through March 30, 2023 by the following personnel: • Ivan Gavran • Andrija Mitrovic

Conclusions The audit consisted of proof-reading the documentation to make sure it is sound and complete, inspecting the code, and capturing a part of the NMT functionality with a formal model. Overall, we found the library to be well developed and documented. During the audit process, we reported 20 findings: 1 of high severity, 5 of the severity, and the rest of low or informational severity. The issues were promptly resolved. An additional outcome of the audit was the Quint model (link) from which we derived (model based) tests.

Disclaimer This report is subject to the terms and conditions (including without limitation, description of services, confidentiality, disclaimer and limitation of liability, etc.) set forth in the associated Services Agreement. This report provided in connection with the Services set forth in the Services Agreement shall be used by the Company only to the extent permitted under the terms and conditions set forth in the Agreement. This audit report is provided on an “as is” basis, with no guarantee of the completeness, accuracy, timeliness or of the results obtained by use of the information provided. Informal has relied upon information and data provided by the client, and is not responsible for any errors or omissions in such information and data or results obtained from the use of that information or conclusions in this report. Informal makes no warranty of any kind, express or implied, regarding the accuracy, adequacy, validity, reliability, availability or completeness of this report. This report should not be considered or utilized as a complete assessment of the overall utility, security or bug free status of the code. This audit report contains confidential information and is only intended for use by the client. Reuse or republication of the audit report other than as authorized by the client is prohibited. This report is not, nor should it be considered, an “endorsement”, “approval” or “disapproval” of any particular project or team. This report is not, nor should it be considered, an indication of the economics or value of any “product” or “asset” created by any team or project that contracts with Informal to perform a security assessment. This report does not provide any warranty or guarantee regarding the absolute bug-free nature of the technology analyzed, nor does it provide any indication of the client’s business, business model or legal compliance. This report should not be used in any way to make decisions around investment or involvement with any particular project. This report in no way provides investment advice, nor should it be leveraged as investment advice of any sort. Blockchain technology and cryptographic assets in general and by definition present a high level of ongoing risk. Client is responsible for its own due diligence and continuing security in this regard.

Overview of the audit results The audit process was comprised of three parts:

Specification overview • NMT spec • Wrapper spec
Code review • NMT spec • Wrapper spec
Generation of formal specification using Quint

Specification overview • NMT specification overview: • Checking the alignment between the specification, underlying documents (Lazy Ledger) and the code comments • Checking the clarity of the documentation • Issues: #IF-41, #IF-40, #NMT-122, #NMT-133 • Wrapper specification overview • Checking the alignment between the specification and the code comments • Checking the clarity of the documentation

Code review • Manual code review (with the help of tools like semgrep and CodeQl): • Best coding practices • Issues: #NMT-130, #NMT-131, #NMT-132, #NMT-139, #NMT-147 • Inspecting code logic and alignment with specification and comments • Issues: #NMT-148, #NMT-121, #NMT-123, #NMT-154 • Analyzing edge cases and searching for flaws • NMT functions • Empty tree case • Tree with one namespace (special case with ParityNamespace) • Tree with a different namespace at the very beginning or the very end (special case with ParityNamespace) • Proof functions • Empty proof • Issue: #NMT-140 • Invalid data input • Corrupted namespace id and data • Wrong data or namespace id size • Issues: #NMT-144, #NMT-157 • Wrong ordering of namespace id • Issue: #NMT-129 • Corrupted proofs • Issue: #NMT-164 • Review of tests • Analyzing coverage by test cases • Issues: #NMT-146, #NMT-158 • Debugging tests

Formal Model in Quint • Generating a formal model with Quint for the following NMT functionalities (PR)

• Generating Inclusion Proofs • Verifying Inclusion Proofs • Using the generated specification to create simulation tests (resulting in the mentioned issue #NMT-164) • Happy path tests • Edge cases tests

Findings Title Type Severity Status

Check of the namespace ordering Implementation 3 High RESOLVED missing in HashNode

IgnoreMaxNS leads to false computing Implementation 2 Medium RESOLVED maxNs

The function verifyLeafHashes will Implementation 2 Medium RESOLVED panic if called from VerifyInclusion function over an empty proof

Wrapper Push function will panic if the Implementation 2 Medium RESOLVED data is invalid

ValidateInclusion function can panic if Implementation 2 Medium RESOLVED it is called with an invalid nid

VerifyNamespace panics if called on an Implementation 2 Medium RESOLVED empty range, but with non-empty nodes

Left and right child swapped in the Documentation 1 Low RESOLVED documentation

Description of calculateAbsenceIndex Documentation 1 Low RESOLVED function in code comments incorrect

The assumption that leaves are Implementation 0 Informational RESOLVED ordered is not used consistently

Typo in the spec: end instead of end-1 Documentation 0 Informational RESOLVED

The code-comment about the return Implementation 0 Informational RESOLVED value for ProveNamespace function does not correspond the code

Duplication of code in the HashNode Implementation 0 Informational RESOLVED function

Hasher initialization and reset should Practice 0 Informational RESOLVED be done after validity checks

Title Type Severity Status

Overly specific helper functions that Practice 0 Informational RESOLVED can be replaced by one generic function

Unclear explanation of namespace Documentation 0 Informational RESOLVED calculation when the option IgnoreMaxNamespace is set

Computing leaf hashes should be done Implementation 0 Informational RESOLVED after the range check

Duplicated test cases Practice 0 Informational RESOLVED

Sanity check should be done Practice 0 Informational RESOLVED immediately after tree creation

Proof struct is missing a function for Practice 0 Informational ACKNOWLEDGED range verification

An incomplete test Implementation 0 Informational RESOLVED

Check of the namespace ordering missing in HashNode Title Check of the namespace ordering missing in HashNode

Project Celestia Q1 2023: NMT

Type IMPLEMENTATION

Severity 3 HIGH

Impact 2 MEDIUM

Exploitability 3 HIGH

Issue https://github.com/celestiaorg/nmt/issues/129

Description Function validateSiblingsNamespaceOrder) only checks if the maximum namespace id of the left child is less or equal to the minimum of the right minimum namespace id. It does not check the of leftMinNs, leftMaxNs, rightMinNs and rightMaxNs among children nodes. Evan if the ordering of namespaces will guaranteed by the Push function it would be wise to check the whole ordering for the sake of completeness. There is a testCase that submits children nodes with invalid namespace ordering to HashNode function. The left child node has minNs larger than the maxNs of the same node, and in addition to that leftMinNs is even larger then the rightMinNs. The test, with invalid data, will pass because validateSiblingsNamespaceOrder does not check the complete ordering of namespaces.

Problem Scenarios This leads to wrong ordering of namespace ids.

Status Resolved.

IgnoreMaxNS leads to false computing maxNs

Description Title IgnoreMaxNS leads to false computing maxNs

Project Celestia Q1 2023: NMT

Type IMPLEMENTATION

Severity 2 MEDIUM

Impact 2 MEDIUM

Exploitability 3 HIGH

Issue https://github.com/celestiaorg/nmt/issues/148

Description The logic for determining the maxNs with n.ignoreMaxNS set to true, is closely dependent on the fact that if the one namespace ID ( minNs or maxNs ) is equal to the n.precomputedMaxNs then both of them are. The documentation is not clear enough on this logic, and this behavior makes the Namespaced Merkle Tree library dependant on the data input. If the nmt is used with the data that does not follow the previously mentioned fact, there is an issue with computing maxNs here. This issue can lead to setting maxNs to n.precomputedMaxNs even if it could be set to a namespace ID that is smaller than n.precomputedMaxNs .

If we assume the following:

• n.ignoreMaxNS = true • leftMinNs != n.precomputedMaxNs • rightMaxNs = n.precomputedMaxNs • rightMinNs < n.precomputedMaxNs • rightMinNs>leftMaxNs .

Than the maxNs will be set to n.precomputedMaxNs even if it should be set to rightMinNs because it is the largest namespaceId smaller than n.precomputedMaxNs .

Example with numbers (presented also in the image at the end): Lets assume that following: • precomputedMaxNs = 10 • ignoreMaxNS = true • leftNode: left{minNs: 7; maxNs:8 } • rightNode: right{minNs: 9; maxNs:10 }

Based on this logic in HashNode the minNs and `maxNs' for the node that is being calculated will take the following values: • minNs = 7 (because it is the lowest value) • maxNs = 10 or the precomputedMaxNs (because the else branch of the if statement will be executed and there 10 will obviously be chosen even if the right.minNs is larger then left.maxNs but not equal to precomputedMaxNs ).

This numerical example with the current behavior and the behavior we expect is graphically presented in the following image.

Problem Scenarios Wrong calculation of the value of maxNS .

Recommendation We recommend to document well this behavior, and align the code with the documentation.

Status Resolved.

The function verifyLeafHashes will panic if called from VerifyInclusion function over an empty proof Title The function verifyLeafHashes will panic if called from VerifyInclusion function over an empty proof

Project Celestia Q1 2023: NMT

Type IMPLEMENTATION

Severity 2 MEDIUM

Impact 3 HIGH

Exploitability 1 LOW

Issue https://github.com/celestiaorg/nmt/issues/140

Description verifyLeafHashes function will panic when called over an empty proof. Panic will happen when getSplitPoint(proof.end) is called because an empty proof has proof.end = 0 that will lead to panic within getSplitPoint function here.

This can happen if the VerifyInclusion function is called over an empty proof. This function will not process the empty proof before calling verifyLeafHashes .

In contrast to when called from VerifyInclusion , verifyLeafHashes will not be called with an empty proof from the VerifyNamespace which handles empty proof before calling verifyLeafHashes (here and here).

Problem Scenarios verifyLeafHashes function will panic when called over an empty proof.

Recommendation VerifyInclusion should process the empty proof before calling verifyLeafHashes , but we suggest an additional protection in verifyLeafHashes .

Status Resolved

Wrapper Push function will panic if the data is invalid Title Wrapper Push function will panic if the data is invalid

Project Celestia Q1 2023: NMT

Type IMPLEMENTATION

Severity 2 MEDIUM

Impact 3 HIGH

Exploitability 1 LOW

Issue https://github.com/celestiaorg/nmt/issues/144

Description Push function from ErasuredNamespacedMerkleTree will panic if it is called with data whose size is smaller than the NamespaceSize . The panic will happen on this line. This is because the slice data[:appconsts.NamespaceSize] is out of bounds of the byte array.

Recommendation Check data size before slicing.

Status Resolved.

ValidateInclusion function can panic if it is called with an invalid nid Title ValidateInclusion function can panic if it is called with an invalid nid

Project Celestia Q1 2023: NMT

Type IMPLEMENTATION

Severity 2 MEDIUM

Impact 3 HIGH

Exploitability 1 LOW

Issue https://github.com/celestiaorg/nmt/issues/157

Description If the ValidateInclusion function is called with an nID which size is not equal to the namespace size of the proof.nodes , the function could panic.

If this happened, the the nth hasher will be constructed with a different namespace size than the one that the proof was calculated with. This could lead to a panic in verifyLeafHashes function within the HashNode at this panic. Panic occurs because validateSiblingsNamespaceOrder could return an ErrUnorderedSiblings error because:

leftMaxNs := namespace.ID(left[n.NamespaceLen:totalNamespaceLen]) rightMinNs := namespace.ID(right[:n.NamespaceLen])

one of the leftMaxNs or rightMinNs is wrongly sliced due to different namespace sizes at their construction and thus parsed so that the following check is true and error is returned:

if rightMinNs.Less(leftMaxNs) { return fmt.Errorf("%w: the maximum namespace of the left child %x is greater than the min namespace of the right child %x", ErrUnorderedSiblings, leftMaxNs, rightMinNs) }

Simple check like this one in the VerifyNamespace should be enough.

Problem Scenarios Function ValidateInclusion could panic if called with invalid namespace id size.

Recommendation Check if the passed nid parameter length is equal with the length on namespaces within the root parameter or the proof.nodes field.

Status Resolved.

VerifyNamespace panics if called on an empty range, but with non-empty nodes Title VerifyNamespace panics if called on an empty range, but with non- empty nodes

Project Celestia Q1 2023: NMT

Type IMPLEMENTATION

Severity 2 MEDIUM

Impact 3 HIGH

Exploitability 1 LOW

Issue https://github.com/celestiaorg/nmt/issues/164

Description If VerifyNamespace is called with a proof that has an empty range (e.g., start=end=0 ), but non-empty nodes , it will panic. An example proof that would cause the panic is

customNode := []byte{7} panickingProof := Proof{ start: 0, end: 0, nodes: [][]byte{customNode}, leafHash: []byte{}, isMaxNamespaceIDIgnored: true, }

VerifyNamespace does check for empty range, but only together with empty nodes. The panic happens in the getSplitPoint function.

Recommendation VerifyNamespace should process the this edge case.

Status Resolved.

Left and right child swapped in the documentation Title Left and right child swapped in the documentation

Project Celestia Q1 2023: NMT

Type DOCUMENTATION

Severity 1 LOW

Impact 1 LOW

Exploitability 0 NONE

Issue https://github.com/informalsystems/audit-celestia/issues/41

Description In the nmt specification the names ( r and l ) of the children of the Non-leaf Node n have been switched when introducing them. In the following code block:

Non-leaf Nodes: For an intermediary node n of the NMT with children

r = l.minNs || l.maxNs || l.hash and

l = r.minNs || r.maxNs || r.hash

r is used for the left node and the l is used for the right node, while it should be reversed.

Problem Scenarios This issue affects the clarity of the specification.

Status Resolved.

Description of calculateAbsenceIndex function in code comments incorrect Title Description of calculateAbsenceIndex function in code comments incorrect

Project Celestia Q1 2023: NMT

Type DOCUMENTATION

Severity 1 LOW

Impact 1 LOW

Exploitability 0 NONE

Issue https://github.com/informalsystems/audit-celestia/issues/40

Description Description above the calculateAbsenceIndex function about index and leaf hash in case of absence proof is misaligned with the documentation and code. Description states that the index of a leaf in the case of absence proof, should be the one with largest namespace ID smaller than the requested namespace, while the documentation states that the index should be the one with the smallest namespace ID that is larger than the requested namespace ID. The code is aligned with the documentation. The same issue with the descriptions about index and leaf hash in case of absence proof was addressed trough this commit in two places to be aligned with the documentation, but was missed above before mentioned function.

Problem Scenarios This issue affects the clarity of code.

Status Resolved.

The assumption that leaves are ordered is not used consistently Title The assumption that leaves are ordered is not used

Excerpt (19999 of 29480 characters). Read the whole page on informalsystems/audits ↗

← Back to Documentation