[segwit3 hard-fork] Fast Merkle trees #49
Closed
Conversation
This file contains hidden or 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
Contains refactorings by Eric Lombrozo. Contains fixup by Nicolas Dorier.
Includes simplifications by Eric Lombrozo.
Includes support for pushkeyhash wit v0 by Alex Morcos.
Includes fixup by Thomas Kerin.
The witness root is allowed to be placed at an arbitrary position up to seven layers deep in a Merkle tree structure. The witness nonce is now the branch through the commitment tree to the witness root, and a single byte is added to the commitment output specifying this path in compact form. This allows other consensus commitments to be added in the future with a minimal number of bytes and without requiring a certain position for each commitment in the tree.
This allows the intermediate state of a SHA-256 run to be saved for future resumption, or in the case of fast Merkle trees to perform a non-padded hash.
A fast Merkle branch uses midstate to perform a single SHA-256 compression per branch, and is not vulnerable to CVE-2012-2459. It produces different hashes though, so can only be used for new hash trees going forward.
|
What is the benefit of doing this? |
Author
|
A slightly better than 3x run-time improvement to validating commitments. It is a particularly useful optimization for chained verifications, such as compact SPV header proofs. |
Owner
|
Performance matters, but is there no way that doesn't require midstate-hacking SHA256? |
sipa
force-pushed
the
segwit
branch
2 times, most recently
from
61a90de to
2a16578
Compare
Author
|
You could reduce the security by truncating hashes. But is it really fair to call this a hack? It's just SHA256 without the mandated padding. |
Owner
|
I do consider this a hack, sorry. I'm really not keen on doing such things to give a constant factor improvement for an already-fast operation. |
sipa
pushed a commit
that referenced
this pull request
Oct 1, 2021
0d624261ef Merge bitcoin-core/crc32c-subtree#2: Merge upstream cac7ca830b Merge commit 'fa5ade41ee480003d9c5af6f43567ba22e4e17e6' into bitcoin-fork fa5ade41ee Fix compilation warnings on ARM64 with old GCC versions. (#52) db08d22129 Updated Travis-CI configuration. (#51) e31619a5b7 Fix GitHub links. (#50) 7fa4c263e8 Update Travis CI config. (#49) a3d9e6d1a4 Updated third_party/ and Travis CI config. (#48) git-subtree-dir: src/crc32c git-subtree-split: 0d624261ef83ab08c953c196540ed18f355add4c
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
7 participants
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.
Switch to fast Merkle trees for witness.
A fast Merkle branch uses midstate to perform a single SHA-256 compression per branch, and is not vulnerable to CVE-2012-2459. It produces different hashes though, so can only be used for new hash trees going forward.
Builds off #48 but could be separable.