Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

feat: verify the range of the namespace IDs of left and right nodes in the Hasher #95

Closed
1 task
staheri14 opened this issue Feb 3, 2023 · 2 comments · Fixed by #102
Closed
1 task

feat: verify the range of the namespace IDs of left and right nodes in the Hasher #95

staheri14 opened this issue Feb 3, 2023 · 2 comments · Fixed by #102
Assignees
@staheri14

Comments

@staheri14
Copy link
Contributor

staheri14 commented Feb 3, 2023 •
edited
Loading

Problem

The Hasher implementation does not verify the range of namespace IDs in the left and right nodes with respect to each other, which is crucial for proper ordering of leaves based on their namespace IDs and for detecting invalidly constructed trees and proofs.

Quoting from Lazy Ledger paper:

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

The issue was identified as part of celestiaorg/celestia-app#1296

Acceptance Criteria

  • To modify the Hasher implementation by incorporating this additional namespace ID range check for the supplied children nodes. Possibly, the Hasher can return an error for invalid inputs. Subsequent refactor needs to take place to properly consume this change.
@staheri14 staheri14 self-assigned this Feb 3, 2023
@liamsi liamsi mentioned this issue Feb 9, 2023
Closed
@liamsi
Copy link
Member

liamsi commented Feb 9, 2023

Somewhat related. I think these functions can also be deleted: #87 (comment)

@staheri14 staheri14 mentioned this issue Feb 16, 2023
Merged
5 tasks
@staheri14
Copy link
Contributor Author

Somewhat related. I think these functions can also be deleted: #87 (comment)

@liamsi I addressed your comment in a separate pull request #103, rather than the one that is closing this issue. Mainly in favour of creating small, single-purpose commits that would make it easier to revert changes if necessary in the future.

@staheri14 staheri14 mentioned this issue Feb 16, 2023
Merged
5 tasks
staheri14 added a commit that referenced this issue Feb 17, 2023
@staheri14
chore!: remove unused API functions Sha256Namespace8FlaggedLeaf and S…
fa98a59 
…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 that referenced this issue Feb 23, 2023
@staheri14
feat: verify the range of the namespace IDs of the children in the Ha…
1d69de9 
…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
@staheri14 staheri14 mentioned this issue Mar 9, 2023
Closed
2 tasks
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@staheri14 staheri14

Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

feat: verify the range of the namespace IDs of the children in the HashNode celestiaorg/nmt
2 participants
@liamsi @staheri14