fix: remove statement from sparse Merkle tree proofs #5768
Merged
Conversation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
refactor: rework proof data structures The SMT proof data structures have been reworked. There is now a type for In- and ExclusionProofs. The proofs are created with the respective `::from_tree(...)` methods. Both types have a `validate` method that lets a verifier validate the proof. For inclusion proofs, the verifier provides the expected key, value and root hash. For exclusion proofs, they provide the expcted key and root hash. This implementation also returns a `NonviableProof` error when trying to create an inclusion proof on a key that does not exist, or vice-versa for exclusion proofs. This is probably more in line with expected behaviour. Implementation notes: There is a fair degree of overlaps between the two types, so we introduce a trait, `MerkleProofDigest` that captures the common behaviour. Some unused functions in bit_utils have been removed. We introduce `PathIterator`, that converts a key into a iterator of traversal directions. This is DoubleEndedIterator, so it can be reversed etc. Side note, implementing DEI has some nasty gotchas (like you must override the default nth_back, len and size_hint methods, or else connector iters like take and rev just don't work). This was surprising and took a few hours to debug. docs: add docstrings to proof structures
ghpbot-tari-project
added
P-acks_required
CjS77
approved these changes
Sep 14, 2023
sdbondi
reviewed
Sep 14, 2023
| } | ||
|
|
||
| fn nth_back(&mut self, n: usize) -> Option<Self::Item> { | ||
| self.cursor_back -= n; |
There was a problem hiding this comment.
Could underflow. Should check for this case and return None.
ghpbot-tari-project
removed
the
P-reviews_required
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
Description
Removes the key and value hashes from sparse Merkle tree proofs. Adds a path check to inclusion proof verification. Closes #5527.
Motivation and Context
Currently, sparse Merkle tree proofs include the key and value hashes for the proof. As these are effectively the proof statement, it doesn't really make sense to include them in the proof structure.
Including them means additional work for the verifier for both inclusion and exclusion proofs that isn't needed. This design also seems like a footgun that could lead an implementer to unintentionally trust the statement from a malicious prover.
This PR removes the key and value hashes from the proof structure altogether, and updates relevant functions accordingly. It also adds a path check to the inclusion proof verifier for consistency with the exclusion proof verifier, which may also help with faster detection of invalid proofs.
How Has This Been Tested?
Existing tests pass.
What process can a PR reviewer use to test or verify this change?
Check that the new verification logic is correct.
Breaking Changes
None. While this changes the structure of sparse Merkle tree proofs, they are not currently used and do not have serialization defined.