Repository: celestiaorg/nmt
Pull request #186 (2023-04-28 17:46:49)

feat: verifies input range in the computeRoot to avoid panic
## Overview
Closes https://github.com/celestiaorg/nmt/issues/137

## Checklist

- [x] New and updated code has appropriate documentation
- [x] New and updated code has new and/or updated testing
- [x] Required CI checks are passing
- [x] Visual proof for any user facing features like CLI or documentation updates
- [x] Linked issues closed with keywords


codecov[bot]: ## [Codecov](https://codecov.io/gh/celestiaorg/nmt/pull/186?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg) Report
> Merging [#186](https://codecov.io/gh/celestiaorg/nmt/pull/186?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg) (a35a4e2) into [master](https://codecov.io/gh/celestiaorg/nmt/commit/f05092f978f48dc8c8527c7451de7b7c63e28e85?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg) (f05092f) will **increase** coverage by `0.84%`.
> The diff coverage is `76.47%`.

```diff
@@            Coverage Diff             @@
##           master     #186      +/-   ##
==========================================
+ Coverage   94.14%   94.99%   +0.84%     
==========================================
  Files           5        5              
  Lines         547      559      +12     
==========================================
+ Hits          515      531      +16     
+ Misses         18       16       -2     
+ Partials       14       12       -2     
```


| [Impacted Files](https://codecov.io/gh/celestiaorg/nmt/pull/186?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg) | Coverage Δ | |
|---|---|---|
| [hasher.go](https://codecov.io/gh/celestiaorg/nmt/pull/186?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg#diff-aGFzaGVyLmdv) | `94.40% <33.33%> (-3.15%)` | :arrow_down: |
| [nmt.go](https://codecov.io/gh/celestiaorg/nmt/pull/186?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg#diff-bm10Lmdv) | `98.01% <100.00%> (+0.01%)` | :arrow_up: |
| [proof.go](https://codecov.io/gh/celestiaorg/nmt/pull/186?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg#diff-cHJvb2YuZ28=) | `93.70% <100.00%> (+6.20%)` | :arrow_up: |



Patch:
diff --git a/nmt.go b/nmt.go
index 2683957..9f52d03 100644
--- a/nmt.go
+++ b/nmt.go
@@ -482,6 +482,11 @@ func (n *NamespacedMerkleTree) MaxNamespace() (namespace.ID, error) {
 // encompasses the leaves within the range of [start, end).
 // Any errors returned by this method are irrecoverable and indicate an illegal state of the tree (n).
 func (n *NamespacedMerkleTree) computeRoot(start, end int) ([]byte, error) {
+	// in computeRoot, start may be equal to end which indicates an empty tree hence empty root.
+	// Due to this, we need to perform custom range check instead of using validateRange() in which start=end is considered invalid.
+	if start < 0 || start > end || end > len(n.leaves) {
+		return nil, fmt.Errorf("failed to compute root [%d, %d): %w", start, end, ErrInvalidRange)
+	}
 	switch end - start {
 	case 0:
 		rootHash := n.treeHasher.EmptyRoot()
diff --git a/proof.go b/proof.go
index 01034a9..6fb8aee 100644
--- a/proof.go
+++ b/proof.go
@@ -212,14 +212,14 @@ func (proof Proof) VerifyNamespace(h hash.Hash, nID namespace.ID, leaves [][]byt
 		return false
 	}
 	// with verifyCompleteness set to true:
-	res, err := proof.verifyLeafHashes(nth, true, nID, gotLeafHashes, root)
+	res, err := proof.VerifyLeafHashes(nth, true, nID, gotLeafHashes, root)
 	if err != nil {
 		return false
 	}
 	return res
 }
 
-// The verifyLeafHashes function checks whether the given proof is a valid Merkle
+// The VerifyLeafHashes function checks whether the given proof is a valid Merkle
 // range proof for the leaves in the leafHashes input. It returns true or false accordingly.
 // If there is an issue during the proof verification e.g., a node does not conform to the namespace hash format, then a proper error is returned to indicate the root cause of the issue.
 // The leafHashes parameter is a list of leaf hashes, where each leaf hash is represented
@@ -228,7 +228,7 @@ func (proof Proof) VerifyNamespace(h hash.Hash, nID namespace.ID, leaves [][]byt
 // the completeness of the proof by verifying that there is no leaf in the
 // tree represented by the root parameter that matches the namespace ID nID
 // but is not present in the leafHashes list.
-func (proof Proof) verifyLeafHashes(nth *Hasher, verifyCompleteness bool, nID namespace.ID, leafHashes [][]byte, root []byte) (bool, error) {
+func (proof Proof) VerifyLeafHashes(nth *Hasher, verifyCompleteness bool, nID namespace.ID, leafHashes [][]byte, root []byte) (bool, error) {
 	// check that the proof range is valid
 	if proof.Start() < 0 || proof.Start() >= proof.End() {
 		return false, fmt.Errorf("proof range [proof.start=%d, proof.end=%d) is not valid: %w", proof.Start(), proof.End(), ErrInvalidRange)
@@ -401,7 +401,7 @@ func (proof Proof) VerifyInclusion(h hash.Hash, nid namespace.ID, leavesWithoutN
 		hashes[i] = res
 	}
 
-	res, err := proof.verifyLeafHashes(nth, false, nid, hashes, root)
+	res, err := proof.VerifyLeafHashes(nth, false, nid, hashes, root)
 	if err != nil {
 		return false
 	}


Test patch:
diff --git a/nmt_test.go b/nmt_test.go
index 0fc7677..1acb0b2 100644
--- a/nmt_test.go
+++ b/nmt_test.go
@@ -1019,17 +1019,23 @@ func Test_Root_Error(t *testing.T) {
 
 // Test_computeRoot_Error tests that the computeRoot method returns an error when the underlying tree is in an invalid state, such as when the leaves are not ordered by namespace ID or when a leaf is corrupt.
 func Test_computeRoot_Error(t *testing.T) {
+	nIDSize := 2
+	nIDList := []byte{1, 2, 3, 4, 5, 6, 7, 8}
+
 	// create an NMT with 8 sequentially namespaced leaves, numbered from 1 to 8.
-	treeWithCorruptLeafHash := exampleNMT(2, 1, 2, 3, 4, 5, 6, 7, 8)
+	treeWithCorruptLeafHash := exampleNMT(nIDSize, nIDList...)
 	// corrupt a leaf hash
 	treeWithCorruptLeafHash.leafHashes[4] = treeWithCorruptLeafHash.leafHashes[4][:treeWithCorruptLeafHash.NamespaceSize()-1]
 
 	// create an NMT with 8 sequentially namespaced leaves, numbered from 1 to 8.
-	treeWithUnorderedLeaves := exampleNMT(2, 1, 2, 3, 4, 5, 6, 7, 8)
+	treeWithUnorderedLeaves := exampleNMT(nIDSize, nIDList...)
 	// swap the positions of the 4th and 5th leaves
 	swap(treeWithUnorderedLeaves.leaves, 4, 5)
 	swap(treeWithUnorderedLeaves.leafHashes, 4, 5)
 
+	// create an NMT with 8 sequentially namespaced leaves, numbered from 1 to 8.
+	validTree := exampleNMT(nIDSize, nIDList...)
+
 	tests := []struct {
 		name       string
 		tree       *NamespacedMerkleTree
@@ -1037,12 +1043,15 @@ func Test_computeRoot_Error(t *testing.T) {
 		wantErr    bool
 		errType    error
 	}{
-		{"corrupt leaf hash: the entire tree", treeWithCorruptLeafHash, 0, 7, true, ErrInvalidNodeLen},
-		{"corrupt leaf: from the corrupt node until the end of the tree", treeWithCorruptLeafHash, 4, 7, true, ErrInvalidNodeLen},
-		{"corrupt leaf: the corrupt node and the node to its left", treeWithCorruptLeafHash, 3, 5, true, ErrInvalidNodeLen},
-		{"unordered leaves: the entire tree", treeWithUnorderedLeaves, 0, 7, true, ErrUnorderedSiblings},
-		{"unordered leaves: the unordered portion", treeWithUnorderedLeaves, 4, 6, true, ErrUnorderedSiblings},
-		{"unordered leaves: a portion of the tree containing the unordered leaves", treeWithUnorderedLeaves, 3, 7, true, ErrUnorderedSiblings},
+		{"invalid tree with corrupt leaf hash. Query: the entire tree", treeWithCorruptLeafHash, 0, 7, true, ErrInvalidNodeLen},
+		{"invalid tree with corrupt leaf. Query: from the corrupt node until the end of the tree", treeWithCorruptLeafHash, 4, 7, true, ErrInvalidNodeLen},
+		{"invalid tree with corrupt leaf. Query: the corrupt node and the node to its left", treeWithCorruptLeafHash, 3, 5, true, ErrInvalidNodeLen},
+		{"invalid tree with unordered leaves. Query: the entire tree", treeWithUnorderedLeaves, 0, 7, true, ErrUnorderedSiblings},
+		{"invalid tree with unordered leaves. Query: the unordered portion", treeWithUnorderedLeaves, 4, 6, true, ErrUnorderedSiblings},
+		{"invalid tree with unordered leaves. Query: a portion of the tree containing the unordered leaves", treeWithUnorderedLeaves, 3, 7, true, ErrUnorderedSiblings},
+		{"valid tree. Query: start < 0", validTree, -1, 1, true, ErrInvalidRange},
+		{"valid tree. Query: start > end", validTree, 3, 1, true, ErrInvalidRange},
+		{"valid tree. Query: end > total number of leaves", validTree, 3, len(validTree.leaves) + 1, true, ErrInvalidRange},
 	}
 	for _, tt := range tests {
 		t.Run(tt.name, func(t *testing.T) {
diff --git a/proof_test.go b/proof_test.go
index 1178bf5..da5c371 100644
--- a/proof_test.go
+++ b/proof_test.go
@@ -350,7 +350,7 @@ func TestVerifyLeafHashes_Err(t *testing.T) {
 	}
 	for _, tt := range tests {
 		t.Run(tt.name, func(t *testing.T) {
-			_, err := tt.proof.verifyLeafHashes(tt.Hasher, tt.verifyCompleteness, tt.nID, tt.leafHashes, tt.root)
+			_, err := tt.proof.VerifyLeafHashes(tt.Hasher, tt.verifyCompleteness, tt.nID, tt.leafHashes, tt.root)
 			assert.Equal(t, tt.wantErr, err != nil)
 		})
 	}
@@ -556,19 +556,19 @@ func TestVerifyLeafHashes_False(t *testing.T) {
 		args   args
 		result bool
 	}{
-		{"nID size of proof < nID size of verifyLeafHashes' nmt hasher", proof4_1, args{2, nid4_2, [][]byte{leafHash2}, root2}, false},
-		{"nID size of proof > nID size of verifyLeafHashes' nmt hasher", proof4_2, args{1, nid4_1, [][]byte{leafHash1}, root1}, false},
-		{"nID size of root < nID size of verifyLeafHashes' nmt hasher", proof4_2, args{2, nid4_2, [][]byte{leafHash2}, root1}, false},
-		{"nID size of root > nID size of verifyLeafHashes' nmt hasher", proof4_1, args{1, nid4_1, [][]byte{leafHash1}, root2}, false},
-		{"size of queried nID > nID size of verifyLeafHashes' nmt hasher", proof4_1, args{1, nid4_2, [][]byte{leafHash1}, root1}, false},
-		{"size of queried nID < nID size of verifyLeafHashes' nmt hasher", proof4_2, args{2, nid4_1, [][]byte{leafHash2}, root2}, false},
-		{"nID size of leafHash < nID size of verifyLeafHashes' nmt hasher", proof4_2, args{2, nid4_2, [][]byte{leafHash1}, root2}, false},
-		{"nID size of leafHash > nID size of verifyLeafHashes' nmt hasher", proof4_1, args{1, nid4_1, [][]byte{leafHash2}, root1}, false},
+		{"nID size of proof < nID size of VerifyLeafHashes' nmt hasher", proof4_1, args{2, nid4_2, [][]byte{leafHash2}, root2}, false},
+		{"nID size of proof > nID size of VerifyLeafHashes' nmt hasher", proof4_2, args{1, nid4_1, [][]byte{leafHash1}, root1}, false},
+		{"nID size of root < nID size of VerifyLeafHashes' nmt hasher", proof4_2, args{2, nid4_2, [][]byte{leafHash2}, root1}, false},
+		{"nID size of root > nID size of VerifyLeafHashes' nmt hasher", proof4_1, args{1, nid4_1, [][]byte{leafHash1}, root2}, false},
+		{"size of queried nID > nID size of VerifyLeafHashes' nmt hasher", proof4_1, args{1, nid4_2, [][]byte{leafHash1}, root1}, false},
+		{"size of queried nID < nID size of VerifyLeafHashes' nmt hasher", proof4_2, args{2, nid4_1, [][]byte{leafHash2}, root2}, false},
+		{"nID size of leafHash < nID size of VerifyLeafHashes' nmt hasher", proof4_2, args{2, nid4_2, [][]byte{leafHash1}, root2}, false},
+		{"nID size of leafHash > nID size of VerifyLeafHashes' nmt hasher", proof4_1, args{1, nid4_1, [][]byte{leafHash2}, root1}, false},
 	}
 	for _, tt := range tests {
 		t.Run(tt.name, func(t *testing.T) {
 			hasher := NewNmtHasher(sha256.New(), tt.args.nIDSize, true)
-			got, _ := tt.proof.verifyLeafHashes(hasher, true, tt.args.nID, tt.args.leaves, tt.args.root)
+			got, _ := tt.proof.VerifyLeafHashes(hasher, true, tt.args.nID, tt.args.leaves, tt.args.root)
 			assert.Equal(t, tt.result, got)
 		})
 	}