Repository: celestiaorg/nmt
Pull request #271 (2024-07-30 21:52:07)

chore(deps): bump github.com/tidwall/gjson from 1.17.1 to 1.17.3
Bumps [github.com/tidwall/gjson](https://github.com/tidwall/gjson) from 1.17.1 to 1.17.3.
<details>
<summary>Commits</summary>
<ul>
<li><a href="https://github.com/tidwall/gjson/commit/5ab551f3ac05551c469e5f5ab26154a49f69afcf"><code>5ab551f</code></a> Add flag for disabling HTML escaping</li>
<li><a href="https://github.com/tidwall/gjson/commit/28d458b14c40df6321bba23bcb39579d468f5e97"><code>28d458b</code></a> Disable html escaping</li>
<li><a href="https://github.com/tidwall/gjson/commit/c2bc5a409a229e55cd1ba59b6cfd5fe1488d6f0f"><code>c2bc5a4</code></a> dark mode logo</li>
<li><a href="https://github.com/tidwall/gjson/commit/2ba56cc0866e91e3197b23b758f7a433713cd2ec"><code>2ba56cc</code></a> Merge pull request <a href="https://redirect.github.com/tidwall/gjson/issues/354">#354</a> from rustfix/master</li>
<li><a href="https://github.com/tidwall/gjson/commit/5d0d40c89f4c6e3c4370788873210e8b1f1a5ecf"><code>5d0d40c</code></a> chore: fix some typos in comments</li>
<li>See full diff in <a href="https://github.com/tidwall/gjson/compare/v1.17.1...v1.17.3">compare view</a></li>
</ul>
</details>
<br />


[![Dependabot compatibility score](https://dependabot-badges.githubapp.com/badges/compatibility_score?dependency-name=github.com/tidwall/gjson&package-manager=go_modules&previous-version=1.17.1&new-version=1.17.3)](https://docs.github.com/en/github/managing-security-vulnerabilities/about-dependabot-security-updates#about-compatibility-scores)

Dependabot will resolve any conflicts with this PR as long as you don't alter it yourself. You can also trigger a rebase manually by commenting `@dependabot rebase`.

[//]: # (dependabot-automerge-start)
[//]: # (dependabot-automerge-end)

---

<details>
<summary>Dependabot commands and options</summary>
<br />

You can trigger Dependabot actions by commenting on this PR:
- `@dependabot rebase` will rebase this PR
- `@dependabot recreate` will recreate this PR, overwriting any edits that have been made to it
- `@dependabot merge` will merge this PR after your CI passes on it
- `@dependabot squash and merge` will squash and merge this PR after your CI passes on it
- `@dependabot cancel merge` will cancel a previously requested merge and block automerging
- `@dependabot reopen` will reopen this PR if it is closed
- `@dependabot close` will close this PR and stop Dependabot recreating it. You can achieve the same result by closing it manually
- `@dependabot show <dependency name> ignore conditions` will show all of the ignore conditions of the specified dependency
- `@dependabot ignore this major version` will close this PR and stop Dependabot creating any more for this major version (unless you reopen the PR or upgrade to it yourself)
- `@dependabot ignore this minor version` will close this PR and stop Dependabot creating any more for this minor version (unless you reopen the PR or upgrade to it yourself)
- `@dependabot ignore this dependency` will close this PR and stop Dependabot creating any more for this dependency (unless you reopen the PR or upgrade to it yourself)


</details>

dependabot[bot]: The following labels could not be found: `dependencies`.
coderabbitai[bot]: <!-- This is an auto-generated comment: summarize by coderabbit.ai -->
<!-- This is an auto-generated comment: skip review by coderabbit.ai -->

> [!IMPORTANT]
> ## Review skipped
> 
> Bot user detected.
> 
> To trigger a single review, invoke the `@coderabbitai review` command.
> 
> You can disable this status message by setting the `reviews.review_status` to `false` in the CodeRabbit configuration file.

<!-- end of auto-generated comment: skip review by coderabbit.ai --><!-- tips_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>

<details>
<summary>Tips</summary>

### Chat

There are 3 ways to chat with [CodeRabbit](https://coderabbit.ai):

- Review comments: Directly reply to a review comment made by CodeRabbit. Example:
	- `I pushed a fix in commit <commit_id>.`
	- `Generate unit testing code for this file.`
	- `Open a follow-up GitHub issue for this discussion.`
- Files and specific lines of code (under the "Files changed" tab): Tag `@coderabbitai` in a new review comment at the desired location with your query. Examples:
	- `@coderabbitai generate unit testing code for this file.`
	-	`@coderabbitai modularize this function.`
- PR comments: Tag `@coderabbitai` in a new PR comment to ask questions about the PR branch. For the best results, please provide a very specific query, as very limited context is provided in this mode. Examples:
	- `@coderabbitai generate interesting stats about this repository and render them as a table.`
	- `@coderabbitai show all the console.log statements in this repository.`
	- `@coderabbitai read src/utils.ts and generate unit testing code.`
	- `@coderabbitai read the files in the src/scheduler package and generate a class diagram using mermaid and a README in the markdown format.`
	- `@coderabbitai help me debug CodeRabbit configuration file.`

Note: Be mindful of the bot's finite context window. It's strongly recommended to break down tasks such as reading entire modules into smaller chunks. For a focused discussion, use review comments to chat about specific files and their changes, instead of using the PR comments.

### CodeRabbit Commands (invoked as PR comments)

- `@coderabbitai pause` to pause the reviews on a PR.
- `@coderabbitai resume` to resume the paused reviews.
- `@coderabbitai review` to trigger an incremental review. This is useful when automatic reviews are disabled for the repository.
- `@coderabbitai full review` to do a full review from scratch and review all the files again.
- `@coderabbitai summary` to regenerate the summary of the PR.
- `@coderabbitai resolve` resolve all the CodeRabbit review comments.
- `@coderabbitai configuration` to show the current CodeRabbit configuration for the repository.
- `@coderabbitai help` to get help.


Additionally, you can add `@coderabbitai ignore` anywhere in the PR description to prevent this PR from being reviewed.

### CodeRabbit Configuration File (`.coderabbit.yaml`)

- You can programmatically configure CodeRabbit by adding a `.coderabbit.yaml` file to the root of your repository.
- Please see the [configuration documentation](https://docs.coderabbit.ai/guides/configure-coderabbit) for more information.
- If your editor has YAML language server enabled, you can add the path at the top of this file to enable auto-completion and validation: `# yaml-language-server: $schema=https://coderabbit.ai/integrations/schema.v2.json`

### Documentation and Community

- Visit our [Documentation](https://coderabbit.ai/docs) for detailed information on how to use CodeRabbit.
- Join our [Discord Community](https://discord.com/invite/GsXnASn26c) to get help, request features, and share feedback.
- Follow us on [X/Twitter](https://twitter.com/coderabbitai) for updates and announcements.

</details>

<!-- tips_end -->

Patch:
diff --git a/go.mod b/go.mod
index 1aed400..a5bba77 100644
--- a/go.mod
+++ b/go.mod
@@ -6,7 +6,7 @@ require (
 	github.com/gogo/protobuf v1.3.2
 	github.com/google/gofuzz v1.2.0
 	github.com/stretchr/testify v1.9.0
-	github.com/tidwall/gjson v1.17.1
+	github.com/tidwall/gjson v1.17.3
 )
 
 require (
diff --git a/go.sum b/go.sum
index 05a3151..dd3dfd0 100644
--- a/go.sum
+++ b/go.sum
@@ -10,8 +10,8 @@ github.com/pmezard/go-difflib v1.0.0 h1:4DBwDE0NGyQoBHbLQYPwSUPoCMWR5BEzIk/f1lZb
 github.com/pmezard/go-difflib v1.0.0/go.mod h1:iKH77koFhYxTK1pcRnkKkqfTogsbg7gZNVY4sRDYZ/4=
 github.com/stretchr/testify v1.9.0 h1:HtqpIVDClZ4nwg75+f6Lvsy/wHu+3BoSGCbBAcpTsTg=
 github.com/stretchr/testify v1.9.0/go.mod h1:r2ic/lqez/lEtzL7wO/rwa5dbSLXVDPFyf8C91i36aY=
-github.com/tidwall/gjson v1.17.1 h1:wlYEnwqAHgzmhNUFfw7Xalt2JzQvsMx2Se4PcoFCT/U=
-github.com/tidwall/gjson v1.17.1/go.mod h1:/wbyibRr2FHMks5tjHJ5F8dMZh3AcwJEMf5vlfC0lxk=
+github.com/tidwall/gjson v1.17.3 h1:bwWLZU7icoKRG+C+0PNwIKC6FCJO/Q3p2pZvuP0jN94=
+github.com/tidwall/gjson v1.17.3/go.mod h1:/wbyibRr2FHMks5tjHJ5F8dMZh3AcwJEMf5vlfC0lxk=
 github.com/tidwall/match v1.1.1 h1:+Ho715JplO36QYgwN9PGYNhgZvoUSc9X2c80KVTi+GA=
 github.com/tidwall/match v1.1.1/go.mod h1:eRSPERbgtNPcGhD8UCthc6PmLEQXEWd3PRB5JTxsfmM=
 github.com/tidwall/pretty v1.2.0/go.mod h1:ITEVvHYasfjBbM0u2Pg8T2nJnzm8xPwvNhhsoaGGjNU=
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)
+	})
+}