Repository: celestiaorg/nmt (go)

Issue:
buildRangeProof can panic upon invalid input range
# Problem
The [buildRangeProof](https://github.com/celestiaorg/nmt/blob/master/nmt.go#L244) can panic if the `start` and `end` arguments are invalid. 

# Acceptance Criteria
Add an initial check for the input range, and make an early return if invalid. 

Pull request:
feat: returns error on invalid proof range in buildRangeProof
## Overview

Closes #142 

## 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


Patch:
diff --git a/nmt.go b/nmt.go
index 5e5ce8d..2683957 100644
--- a/nmt.go
+++ b/nmt.go
@@ -170,8 +170,8 @@ func (n *NamespacedMerkleTree) ProveRange(start, end int) (Proof, error) {
 	isMaxNsIgnored := n.treeHasher.IsMaxNamespaceIDIgnored()
 	// TODO: store nodes and re-use the hashes instead recomputing parts of the
 	// tree here
-	if start < 0 || start >= end || end > len(n.leafHashes) {
-		return NewEmptyRangeProof(isMaxNsIgnored), ErrInvalidRange
+	if err := n.validateRange(start, end); err != nil {
+		return NewEmptyRangeProof(isMaxNsIgnored), err
 	}
 	proof, err := n.buildRangeProof(start, end)
 	if err != nil {
@@ -245,6 +245,15 @@ func (n *NamespacedMerkleTree) ProveNamespace(nID namespace.ID) (Proof, error) {
 	return NewAbsenceProof(proofStart, proofEnd, proof, n.leafHashes[proofStart], isMaxNsIgnored), nil
 }
 
+// validateRange validates the range [start, end) against the size of the tree.
+// start is inclusive and end is non-inclusive.
+func (n *NamespacedMerkleTree) validateRange(start, end int) error {
+	if start < 0 || start >= end || end > len(n.leaves) {
+		return ErrInvalidRange
+	}
+	return nil
+}
+
 // buildRangeProof returns the nodes (as byte slices) in the range proof of the
 // supplied range i.e., [proofStart, proofEnd) where proofEnd is non-inclusive.
 // The nodes are ordered according to in order traversal of the namespaced tree.
@@ -253,6 +262,11 @@ func (n *NamespacedMerkleTree) buildRangeProof(proofStart, proofEnd int) ([][]by
 	proof := [][]byte{} // it is the list of nodes hashes (as byte slices) with no index
 	var recurse func(start, end int, includeNode bool) ([]byte, error)
 
+	// validate the range
+	if err := n.validateRange(proofStart, proofEnd); err != nil {
+		return nil, err
+	}
+
 	// start, end are indices of leaves in the tree hence they should be within
 	// the size of the tree i.e., less than or equal to the len(n.leaves)
 	// includeNode indicates whether the hash of the current subtree (covering


Test patch:
diff --git a/nmt_test.go b/nmt_test.go
index 8b677d9..0fc7677 100644
--- a/nmt_test.go
+++ b/nmt_test.go
@@ -863,17 +863,22 @@ func swap(slice [][]byte, i int, j int) {
 
 // Test_buildRangeProof_Err tests that buildRangeProof returns an error when the underlying tree has an invalid state e.g., leaves are not ordered by namespace ID or a leaf hash is corrupted.
 func Test_buildRangeProof_Err(t *testing.T) {
+	nIDList := []byte{1, 2, 3, 4, 5, 6, 7, 8}
+	nIDSize := 2
+
 	// create a nmt, 8 leaves namespaced sequentially from 1-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()]
 
 	// create an NMT with 8 sequentially namespaced leaves, numbered from 1 to 8.
-	treeWithUnorderedLeafHashes := exampleNMT(2, 1, 2, 3, 4, 5, 6, 7, 8)
+	treeWithUnorderedLeafHashes := exampleNMT(nIDSize, nIDList...)
 	// swap the positions of the 4th and 5th leaves
 	swap(treeWithUnorderedLeafHashes.leaves, 4, 5)
 	swap(treeWithUnorderedLeafHashes.leafHashes, 4, 5)
 
+	validTree := exampleNMT(nIDSize, nIDList...)
+
 	tests := []struct {
 		name                 string
 		tree                 *NamespacedMerkleTree
@@ -887,6 +892,10 @@ func Test_buildRangeProof_Err(t *testing.T) {
 		// not just the corrupted range.
 		{"unordered leaf hashes: the last leaf", treeWithUnorderedLeafHashes, 7, 8, true, ErrUnorderedSiblings}, // for a tree with an unordered set of leaves, the buildRangeProof function  should produce an error for any input range,
 		// not just the corrupted range.
+		{"invalid proof range: start > end", validTree, 5, 4, true, ErrInvalidRange},
+		{"invalid proof range: start = end", validTree, 5, 5, true, ErrInvalidRange},
+		{"invalid proof range: start < 0", validTree, -1, 4, true, ErrInvalidRange},
+		{"invalid proof range: end > number of leaves", validTree, 0, len(validTree.leaves) + 1, true, ErrInvalidRange},
 	}
 	for _, tt := range tests {
 		t.Run(tt.name, func(t *testing.T) {