search

celestiaorg / nmt

Namespaced Merkle Tree
Apache License 2.0
107 stars 39 forks source link

feat: add support for subtree root verification #260

Closed rach-id closed 6 days ago

rach-id commented 1 month ago

Overview

Closes https://github.com/celestiaorg/nmt/issues/256

I added this change here so that we have a reference implementation of the algorithm that we will implement in Solidity.

Also, adds a method to generate the subtree roots, which didn't exist before and will be needed during proof generation in Celestia-node.

The codecov missing coverage complaints are for conditions that are checked twice in different contexts. So there is no way to bypass the first check to arrive at the second check. So, I guess they're fine.

Summary by CodeRabbit

coderabbitai[bot] commented 1 month ago

Walkthrough

The changes introduce methods to compute and verify inner nodes' roots in a Namespaced Merkle Tree (NMT). This includes adding methods for subtree root computation (ComputeSubtreeRoot), validation (VerifySubtreeRootInclusion), and accompanying utility functions. The updates also refactor related struct field names and enhance testing with new test cases for the added functionality.

Changes

Files Change Summary
nmt.go Added ComputeSubtreeRoot method, isPowerOfTwo function, and updated struct field names.
nmt_test.go Added exampleNMT2 and TestComputeSubtreeRoot functions for testing subtree root computation.
proof.go Added VerifySubtreeRootInclusion, ToLeafRanges, nextLeafRange, and other utility functions.
proof_test.go Added multiple test functions to verify new utility functions and subtree root inclusion.

Assessment against linked issues

Objective (Issue #256) Addressed Explanation
Support inner nodes proving/verification ✅
Computation and validation of subtree roots ✅

Poem

In the realm of code where bytes dance free,
A tree gains wisdom, roots we now see.
With leaves that whisper of proofs and might,
Inner nodes' secrets come to light.
Hail to the Merkle, strong and true,
Verified roots, a dream come through. 🌳🚀

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?

Share - [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)
Tips ### 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 .` - `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 Configration 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.
codecov[bot] commented 1 month ago

Codecov Report

Attention: Patch coverage is 82.14286% with 20 lines in your changes missing coverage. Please review.

Project coverage is 67.84%. Comparing base (3539dc8) to head (680faca).

Files Patch % Lines
proof.go 82.22% 8 Missing and 8 partials :warning:
nmt.go 81.81% 2 Missing and 2 partials :warning:
Additional details and impacted files ```diff @@ Coverage Diff @@ ## main #260 +/- ## ========================================== + Coverage 66.43% 67.84% +1.40% ========================================== Files 6 6 Lines 1028 1132 +104 ========================================== + Hits 683 768 +85 - Misses 328 337 +9 - Partials 17 27 +10 ```

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

rach-id commented 1 month ago

Making this a draft because I want to finish the implementation downstream to be sure this PR contains all the changes needed

rach-id commented 1 month ago

have we thought about combining the leaf proving mech w/ this one? We would still maintain the same apis for users, but use the same backend

Certainly doable. However, my worry is for people who will not be familiar with this and need to maintain the repo. They will need extra time to get used to the ranges, how they're calculated etc. Getting onboarded to the NMT implementation itself takes some time. Adding the ranges might make it even harder. And if someone only wants to change something regarding the leaves proving, they would also need to understand how the ranges work, subtree roots, ADR-013 to be able to do that change.

However, if you guys prefer it to be that way, I can open an issue to combine them both.

cmwaters commented 1 month ago

Haven't yet reviewed but will this mean we will be able to fill out this missing section of the specs: https://celestiaorg.github.io/celestia-app/specs/fraud_proofs.html#blob-inclusion

rach-id commented 1 month ago

@cmwaters yes. With this, we will be able to have compact fraud proofs. But this is just the proving part, I am not sure if the remaining logic like creating the proof, propagating it and acting upon it is implemented.

cmwaters commented 1 month ago

Compact fraud proofs of what? My understanding was this was a more compact way of proving the inclusion of a blob by proving the inclusion of sub tree roots (rather than all the leaf nodes themselves).

Also will this repo host the logic for creating these proofs as well. I would have through that creation and validation will have been done side by side

rach-id commented 1 month ago

Compact fraud proofs of what? My understanding was this was a more compact way of proving the inclusion of a blob by proving the inclusion of sub tree roots (rather than all the leaf nodes themselves).

Yes. And blobstream rollups for example, if they choose to use the share commitments instead of the sequence of spans to reference the location of their data, they can use this to verify inclusion of a share commitment to a data root tuple root. Then, prove the inclusion of a share to a subtree roots. And then, parse the share to verify if the state transitions there are valid or not.

Also will this repo host the logic for creating these proofs as well. I would have through that creation and validation will have been done side by side

I think the creation and validation will be done in other repos. This only provides a way to verify the inclusion of subtree roots.