EPIC: Specify data root construction using rsmt2d, nmt, and the nmt wrapper #1296
Closed
2 tasks done
Assignees
Labels
epic
item groups other items for easier tracking
Comments
|
Adding some resources relevant to this EPIC:
|
staheri14
added a commit
to celestiaorg/nmt
that referenced
this issue
Jan 30, 2023
## Overview While reviewing the nmt codebase (as part of this [EPIC](celestiaorg/celestia-app#1296)) I realized the description of the `HashLeaf` function does not match its implementation (w.r.t. referred variable names) which causes confusion when comprehending the code. This PR aims to correct and revise that description. Also, the illustration of an nmt provided in the [Readme file](https://github.com/celestiaorg/nmt/blob/master/README.md) seems not aligned with the leaf hash calculation, where in the `node_0.0` the `d_0.0=H(data_0)` while it should be `d_0.0=H(0x00, nid_0, data_0)`. I was not able to edit the image as its source code is not available. Co-authored-by: sanaz <[email protected]>
|
The status of my advancement with respect to the EPIC and its subsidiary tasks is recorded in the following Notion page. Please be advised that this is an ongoing effort and includes my preliminary observations, inquiries, and outcomes as I review various repositories and relevant resources. |
This was referenced Feb 3, 2023
feat: verify the range of the namespace IDs of left and right nodes in the Hasher
celestiaorg/nmt#95
Closed
staheri14
added a commit
to celestiaorg/nmt
that referenced
this issue
Feb 14, 2023
A PR inline with EPIC celestiaorg/celestia-app#1296 Aiming at improving the documentation of the NMT library. As part of this PR, some variables have been renamed to more accurately reflect their values.
This was referenced Feb 15, 2023
staheri14
added a commit
to celestiaorg/nmt
that referenced
this issue
Feb 17, 2023
…ha256Namespace8FlaggedInner from the hasher (#103) ## Overview The following two functions `Sha256Namespace8FlaggedLeaf` and `Sha256Namespace8FlaggedInner` are part of the public APIs, however, they are no longer needed as mentioned by @liamsi in #87 (comment). I also verified it against the main branch and the latest release (v0.7.0-rc4@8b9937f) of celestia-node codebase and no usage was found. Likewise, no usage was available in the clestia-core repo. **Summary of changes:** - This PR deletes these `Sha256Namespace8FlaggedLeaf` and `Sha256Namespace8FlaggedInner` functions and the relevant tests. - After performing this update, it was found that there was no longer any use case for the `defaultHasher` in the main hasher file, and it is now only being used in the test file. As a result, it has been moved accordingly. ## 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 (based on the responses from code-owners, it is safe to say there is no mention to these functions in any doc) - [x] Linked issues closed with keywords This change is inline with celestiaorg/celestia-app#1296 and #95.
staheri14
added a commit
to celestiaorg/nmt
that referenced
this issue
Feb 21, 2023
## Overview This pull request aligns with the celestiaorg/celestia-app#1296 EPIC and introduces an NMT specification that includes a description of NMT as a data structure, an explanation of the NMT library, and a sample code. In terms of description of the NMT library, the focus was on the portions that are used in the NMT wrapper to establish the foundation for the NMT wrapper specification. The NMT methods are illustrated through a running code example that was originally included in the Readme file of the NMT repository (with a minor change in namespace ID of one of the leaves in order to be able to provide an example of absence proof). This example has been expanded to provide a more detailed description of each method call, an interpretation of the parameters, and its relationship to the NMT high-level logic. The The corresponding NMT for the code example is also visualized to facilitate a better understanding and examination of the expected behavior of the library.
staheri14
added a commit
to celestiaorg/nmt
that referenced
this issue
Feb 23, 2023
…shNode (#102) ## Overview This PR closes #95. Inline with celestiaorg/celestia-app#1296. The implementation of this pull request does not exactly follow the original suggestion in the LazyLedge paper. Specifically, it does not treat `leftMaxNs = rightMinNs` as a violation of leaf ordering. The reason for this is that a namespace may span across multiple subtrees. cc: @liamsi Quoting from the article: > An adversarial consensus node may attempt to produce a block that contains a Merkle tree with children that are not ordered correctly. To prevent this, we can set a condition in nsHash such that there is no valid hash when **leftMaxNs ≥ rightMinNs**, and thus there would be no valid Merkle root for incorrectly ordered children ## 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
|
The specification for the NMT wrapper is currently under development. You can find the latest version on the following Notion page: https://www.notion.so/celestiaorg/NMT-Wrapper-4ae9ee77898e4d3d80f9a9b1c5465f87#link-to-the-nmt-spec-for-the-inclusion-proof. |
5 tasks
staheri14
added a commit
that referenced
this issue
Mar 8, 2023
## Overview This PR addresses issue #1296 by adding the specification for the NMT wrapper. The specification is based on the state of implementation after the inclusion of the changes made in pull request #1438. ## 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
This was referenced Mar 9, 2023
Closed
|
Closing this issue as the constituents tasks are done. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Having a spec for the construction of the data root, particularly one that is consistent with the current implementation, would be very valuable. It would help on boarding others (internally such as new engineers, and externally via auditors and research enthusiasts) on how celestia functions at a low level. Ideally, someone should be able to write a fully compatible separate implementation using such a spec.
Currently, a lot of this information is disparate or implied. We need to compile the various sources of information, make sure they follow the implementation, and then write the missing pieces.
Notably, some of the missing pieces include (incomplete list) todo: flesh out
Other issues that are addressed or identified as part of this EPIC:
Treemethod from the NMT wrapper and introduces theProveRangeAPI #1438The text was updated successfully, but these errors were encountered: