feat: merged proof #5193
Merged
feat: merged proof #5193
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
stringhandler
added
P-conflicts
stringhandler
approved these changes
Mar 6, 2023
This was referenced Mar 6, 2023
stringhandler
pushed a commit
that referenced
this pull request
Mar 7, 2023
Description --- Removes panics from [merged balanced binary Merkle tree](#5193) proofs. Changes proof format to avoid a hash output size assumption. Minor renaming and typo fixes for clarity. Closes [issue 5220](#5220). Motivation and Context --- Recent work implements merged balanced binary Merkle tree proofs. However, the verifier depended on a specific hash output length (32 bytes) to differentiate node hashes from proof indexes. This would lead to a panic if this size restriction was not met; it was not enforced because of how hashers are used in the design. Separately, proof semantics were not checked by the verifier, which could lead to other panics. This PR addresses both of these points. Instead of relying on hash output size, merged path data now includes a flag to indicate if each step references a proof index or a node hash. The verifier now returns a `Result`, producing an error if the proof semantics are incorrect. If they are correct, its return value can be unwrapped as a `bool` to assert the verification passes. It also fixes a few typos and does some minor renaming for clarity. Note that the design still retains an original assumption of a universal `usize` that may be problematic. Non-merged proofs contain a `usize` index to the node in question, and merged proofs additionally contain `usize` vectors to indicate path lengths and proof indexes. This may lead to unexpected and inconsistent behavior, and should be carefully examined separately. How Has This Been Tested? --- Existing unit tests pass.
stringhandler
pushed a commit
that referenced
this pull request
Mar 8, 2023
### ⚠ BREAKING CHANGES * **peer_db:** more accurate peer stats per address (5142) * use consensus hashing API for validator node MMR (5207) * **consensus:** add balanced binary merkle tree (5189) ### Features * add favourite flag to contact ([5217](#5217)) ([0371b60](0371b60)) * add indexer config ([5210](#5210)) ([cf95601](cf95601)) * add merge proof for balanced binary merkle tree ([5193](#5193)) ([8962909](8962909)) * **consensus:** add balanced binary merkle tree ([5189](#5189)) ([8d34e8a](8d34e8a)) * log to base dir ([#5197](#5197)) ([5147b5c](5147b5c)) * **peer_db:** more accurate peer stats per address ([5142](#5142)) ([fdad1c6](fdad1c6)) ### Bug Fixes * add grpc commitment signature proto type ([5200](#5200)) ([d523f1e](d523f1e)) * peer seeds for esme/igor ([5202](#5202)) ([1bc226c](1bc226c)) * remove panics from merged BBMT verification ([5221](#5221)) ([a4c5fce](a4c5fce)) * source coverage ci failure ([5209](#5209)) ([80294a1](80294a1)) * use consensus hashing API for validator node MMR ([5207](#5207)) ([de28115](de28115)) * wallet reuse existing tor address ([5092](#5092)) ([576f44e](576f44e)) * **wallet:** avoids empty addresses in node identity ([5224](#5224)) ([1a66312](1a66312))
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
This change introduces merged merkle proofs over balanced binary trees. It works by merging and cutting the paths of individual proofs. So only one proof will be stored with the same length as provided. All others will join this proof along the way. When a proof joins any other proof it will store the join index. And the other path instead of storing the hash of the sibling will store the index of this joined proof. So it will uses it's hash.
Motivation and Context
Save space and time for merkle proofs. The original MMR didn't support merged proofs.
How Has This Been Tested?
There are cargo tests in the proof file.