Repository: celestiaorg/nmt
Pull request #268 (2024-07-26 19:22:13)

fix: check the correctness of the leaf ranges
<!--
Please read and fill out this form before submitting your PR.

Please make sure you have reviewed our contributors guide before submitting your
first PR.
-->

## Overview

Closes: https://github.com/celestiaorg/nmt/issues/267

<!-- This is an auto-generated comment: release notes by coderabbit.ai -->
## Summary by CodeRabbit


- **New Features**
	- Strengthened error handling for subtree root verification and leaf range calculations to improve robustness against invalid inputs.

- **Bug Fixes**
	- Enhanced validation processes to prevent incorrect operations and ensure reliable range processing.

- **Tests**
	- Refined test cases to focus on relevant scenarios and added new tests for improved coverage of edge cases related to error handling.

<!-- end of auto-generated comment: release notes by coderabbit.ai -->

coderabbitai[bot]: <!-- This is an auto-generated comment: summarize by coderabbit.ai -->
<!-- This is an auto-generated comment: summarize review in progress by coderabbit.ai -->

> [!NOTE]
> Currently processing new changes in this PR. This may take a few minutes, please wait...
> 
> 	<details>
> <summary>Commits</summary>
> 
> Files that changed from the base of the PR and between 1278ba26e5727df0b5567ec95fb3ca07536b5aaf and 003362bee0db48f4a35556415a519a4b0b1b1b18.
> 
> </details>
> 
> 
> <details>
> <summary>Files selected for processing (2)</summary>
> 
> * proof.go (2 hunks)
> * proof_test.go (5 hunks)
> 
> </details>
> 
> 	```ascii
>  __________________________________________________________________________________
> < Controlling complexity is the essence of computer programming. - Brian Kernighan >
>  ----------------------------------------------------------------------------------
>   \
>    \   \
>         \ /\
>         ( )
>       .( o ).
> ```

<!-- end of auto-generated comment: summarize review in progress by coderabbit.ai --><!-- usage_tips_start -->

> [!TIP]
> <details>
> <summary>You can disable sequence diagrams in the walkthrough.</summary>
> 
> Disable the `reviews.sequence_diagrams` setting in your project's settings in CodeRabbit to remove sequence diagrams from the walkthrough.
> 
> </details>

<!-- usage_tips_end --><!-- product_reason_start -->



Thank you for using CodeRabbit. We offer it for free to the OSS community and would appreciate your support in helping us grow. If you find it useful, would you consider giving us a shout-out on your favorite social media?

<details>
<summary>Share</summary>

- [X](https://twitter.com/intent/tweet?text=I%20just%20used%20%40coderabbitai%20for%20my%20code%20review%2C%20and%20it%27s%20fantastic%21%20It%27s%20free%20for%20OSS%20and%20offers%20a%20free%20trial%20for%20the%20proprietary%20code.%20Check%20it%20out%3A&url=https%3A//coderabbit.ai)
- [Mastodon](https://mastodon.social/share?text=I%20just%20used%20%40coderabbitai%20for%20my%20code%20review%2C%20and%20it%27s%20fantastic%21%20It%27s%20free%20for%20OSS%20and%20offers%20a%20free%20trial%20for%20the%20proprietary%20code.%20Check%20it%20out%3A%20https%3A%2F%2Fcoderabbit.ai)
- [Reddit](https://www.reddit.com/submit?title=Great%20tool%20for%20code%20review%20-%20CodeRabbit&text=I%20just%20used%20CodeRabbit%20for%20my%20code%20review%2C%20and%20it%27s%20fantastic%21%20It%27s%20free%20for%20OSS%20and%20offers%20a%20free%20trial%20for%20proprietary%20code.%20Check%20it%20out%3A%20https%3A//coderabbit.ai)
- [LinkedIn](https://www.linkedin.com/sharing/share-offsite/?url=https%3A%2F%2Fcoderabbit.ai&mini=true&title=Great%20tool%20for%20code%20review%20-%20CodeRabbit&summary=I%20just%20used%20CodeRabbit%20for%20my%20code%20review%2C%20and%20it%27s%20fantastic%21%20It%27s%20free%20for%20OSS%20and%20offers%20a%20free%20trial%20for%20proprietary%20code)

</details>

<!-- product_reason_end -->
codecov[bot]: ## [Codecov](https://app.codecov.io/gh/celestiaorg/nmt/pull/268?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg) Report
Attention: Patch coverage is `71.42857%` with `2 lines` in your changes missing coverage. Please review.
> Project coverage is 68.01%. Comparing base [(`1278ba2`)](https://app.codecov.io/gh/celestiaorg/nmt/commit/1278ba26e5727df0b5567ec95fb3ca07536b5aaf?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg) to head [(`003362b`)](https://app.codecov.io/gh/celestiaorg/nmt/commit/003362bee0db48f4a35556415a519a4b0b1b1b18?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg).

| [Files](https://app.codecov.io/gh/celestiaorg/nmt/pull/268?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg) | Patch % | Lines |
|---|---|---|
| [proof.go](https://app.codecov.io/gh/celestiaorg/nmt/pull/268?src=pr&el=tree&filepath=proof.go&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg#diff-cHJvb2YuZ28=) | 71.42% | [1 Missing and 1 partial :warning: ](https://app.codecov.io/gh/celestiaorg/nmt/pull/268?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg) |

<details><summary>Additional details and impacted files</summary>


```diff
@@            Coverage Diff             @@
##             main     #268      +/-   ##
==========================================
+ Coverage   67.84%   68.01%   +0.16%     
==========================================
  Files           6        6              
  Lines        1132     1138       +6     
==========================================
+ Hits          768      774       +6     
  Misses        337      337              
  Partials       27       27              
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/celestiaorg/nmt/pull/268?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg).


Patch:
diff --git a/proof.go b/proof.go
index bde6723..b260e17 100644
--- a/proof.go
+++ b/proof.go
@@ -528,6 +528,10 @@ func (proof Proof) VerifySubtreeRootInclusion(nth *NmtHasher, subtreeRoots [][]b
 			return popIfNonEmpty(&subtreeRoots), nil
 		}
 
+		if end-start == 1 {
+			return nil, fmt.Errorf("the provided range [%d, %d) does not reference a valid inner node", proof.start, proof.end)
+		}
+
 		// Recursively get left and right subtree
 		k := getSplitPoint(end - start)
 		left, err := computeRoot(start, start+k)
@@ -634,7 +638,13 @@ func nextLeafRange(currentStart, currentEnd, subtreeWidth int) (LeafRange, error
 	if err != nil {
 		return LeafRange{}, err
 	}
-	return LeafRange{Start: currentStart, End: currentStart + currentRange}, nil
+	rangeEnd := currentStart + currentRange
+	idealTreeSize := nextSubtreeSize(uint64(currentStart), uint64(rangeEnd))
+	if currentStart+idealTreeSize != rangeEnd {
+		// this will happen if the calculated range does not correctly reference an inner node in the tree.
+		return LeafRange{}, fmt.Errorf("provided subtree width %d doesn't allow creating a valid leaf range [%d, %d)", subtreeWidth, currentStart, rangeEnd)
+	}
+	return LeafRange{Start: currentStart, End: rangeEnd}, nil
 }
 
 // largestPowerOfTwo calculates the largest power of two


Test patch:
diff --git a/proof_test.go b/proof_test.go
index b2ea98f..cb208cd 100644
--- a/proof_test.go
+++ b/proof_test.go
@@ -1332,18 +1332,6 @@ func TestNextLeafRange(t *testing.T) {
 			subtreeRootMaximumLeafRange: 8,
 			expectedRange:               LeafRange{Start: 4, End: 8},
 		},
-		{
-			currentStart:                4,
-			currentEnd:                  20,
-			subtreeRootMaximumLeafRange: 16,
-			expectedRange:               LeafRange{Start: 4, End: 20},
-		},
-		{
-			currentStart:                4,
-			currentEnd:                  20,
-			subtreeRootMaximumLeafRange: 1,
-			expectedRange:               LeafRange{Start: 4, End: 5},
-		},
 		{
 			currentStart:                4,
 			currentEnd:                  20,
@@ -1356,12 +1344,6 @@ func TestNextLeafRange(t *testing.T) {
 			subtreeRootMaximumLeafRange: 4,
 			expectedRange:               LeafRange{Start: 4, End: 8},
 		},
-		{
-			currentStart:                4,
-			currentEnd:                  20,
-			subtreeRootMaximumLeafRange: 8,
-			expectedRange:               LeafRange{Start: 4, End: 12},
-		},
 		{
 			currentStart:                0,
 			currentEnd:                  1,
@@ -1392,6 +1374,36 @@ func TestNextLeafRange(t *testing.T) {
 			subtreeRootMaximumLeafRange: 0,
 			expectError:                 true,
 		},
+		{ // A range not referencing any inner node
+			currentStart:                1,
+			currentEnd:                  3,
+			subtreeRootMaximumLeafRange: 4,
+			expectError:                 true,
+		},
+		{ // A range not referencing any inner node
+			currentStart:                1,
+			currentEnd:                  5,
+			subtreeRootMaximumLeafRange: 4,
+			expectError:                 true,
+		},
+		{ // A range not referencing any inner node
+			currentStart:                1,
+			currentEnd:                  6,
+			subtreeRootMaximumLeafRange: 4,
+			expectError:                 true,
+		},
+		{ // A range not referencing any inner node
+			currentStart:                1,
+			currentEnd:                  7,
+			subtreeRootMaximumLeafRange: 4,
+			expectError:                 true,
+		},
+		{ // A range not referencing any inner node
+			currentStart:                2,
+			currentEnd:                  8,
+			subtreeRootMaximumLeafRange: 4,
+			expectError:                 true,
+		},
 	}
 
 	for _, tt := range tests {
@@ -1798,7 +1810,6 @@ func TestVerifySubtreeRootInclusion(t *testing.T) {
 			root:         root,
 			expectError:  true,
 		},
-
 		{
 			proof: func() Proof {
 				p, err := tree.ProveRange(0, 8)
@@ -1828,3 +1839,31 @@ func TestVerifySubtreeRootInclusion(t *testing.T) {
 		})
 	}
 }
+
+// TestVerifySubtreeRootInclusion_infiniteRecursion is motivated by a failing test
+// case in celestia-node
+func TestVerifySubtreeRootInclusion_infiniteRecursion(t *testing.T) {
+	namespaceIDs := bytes.Repeat([]byte{1}, 64)
+	tree := exampleNMT(1, true, namespaceIDs...)
+	root, err := tree.Root()
+	require.NoError(t, err)
+
+	nmthasher := tree.treeHasher
+	hasher := nmthasher.(*NmtHasher)
+	subtreeRoot, err := tree.ComputeSubtreeRoot(0, 4)
+	require.NoError(t, err)
+	subtreeRoots := [][]byte{subtreeRoot, subtreeRoot, subtreeRoot, subtreeRoot, subtreeRoot, subtreeRoot, subtreeRoot}
+	subtreeWidth := 8
+
+	proof, err := tree.ProveRange(19, 64)
+	require.NoError(t, err)
+
+	require.NotPanics(t, func() {
+		// This previously hits:
+		// runtime: goroutine stack exceeds 1000000000-byte limit
+		// runtime: sp=0x14020160480 stack=[0x14020160000, 0x14040160000]
+		// fatal error: stack overflow
+		_, err = proof.VerifySubtreeRootInclusion(hasher, subtreeRoots, subtreeWidth, root)
+		require.Error(t, err)
+	})
+}