consensus: Add BIP-341 specified constraints in ComputeTaprootMerkleRoot
#25132
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
ca6f952 to
166e7b4
Compare
ComputeTaprootMerkelRoot
Contributor
|
Concept ACK |
theStack
reviewed
May 16, 2022
src/script/interpreter.cpp
Outdated
Comment on lines
1835
to
1837
| assert(control.size() >= TAPROOT_CONTROL_BASE_SIZE | ||
| && control.size() <= TAPROOT_CONTROL_MAX_SIZE | ||
| && ((control.size() - TAPROOT_CONTROL_BASE_SIZE) % TAPROOT_CONTROL_NODE_SIZE == 0)); |
Contributor
There was a problem hiding this comment.
nit: Probably it would make sense to split those three conditions (too small, too large, length not 33 + 32m) up, so in the case that this ever throws, we can yield more information about the size of the control block:
Suggested change
| assert(control.size() >= TAPROOT_CONTROL_BASE_SIZE | |
| && control.size() <= TAPROOT_CONTROL_MAX_SIZE | |
| && ((control.size() - TAPROOT_CONTROL_BASE_SIZE) % TAPROOT_CONTROL_NODE_SIZE == 0)); | |
| assert(control.size() >= TAPROOT_CONTROL_BASE_SIZE); | |
| assert(control.size() <= TAPROOT_CONTROL_MAX_SIZE); | |
| assert((control.size() - TAPROOT_CONTROL_BASE_SIZE) % TAPROOT_CONTROL_NODE_SIZE == 0); |
Contributor
Author
There was a problem hiding this comment.
Applied suggestion, thanks.
ComputeTaprootMerkelRootComputeTaprootMerkleRoot
Contributor
|
Concept ACK |
a4cd92c to
bfb39f2
Compare
Contributor
Author
|
CI failure "[no wallet, libbitcoinkernel] [bionic] Failing after 15m — Task Summary" possibly #24575? |
BIP 341 specifies constraints on the size of the control block _c_ used to compute the taproot merkle root. > The last stack element is called the control block _c_, and must have > length _33 + 32m_, for a value of m that is an integer between 0 and > 128, inclusive. Fail if it does not have such a length. (See BIP-341 "Script Validation Rules" here: https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki#script-validation-rules)
bfb39f2 to
bd7c5e2
Compare
Contributor
Author
|
Last two merges: First was a squash, second was to kick the CI to fix a spurious check fail. |
Member
|
ACK bd7c5e2 I think it makes sense to spell out these assumptions explicitly. |
theStack
approved these changes
May 25, 2022
sidhujag
pushed a commit
to syscoin/syscoin
that referenced
this pull request
May 28, 2022
…`ComputeTaprootMerkleRoot` bd7c5e2 Add BIP-341 specified constraints to `ComputeTaprootMerkleRoot` (David Bakin) Pull request description: [**N.B.:** This PR **_does not change the consensus_**. It only adds `assert` statements according to the current consensus in consensus-sensitive code (`interpreter.cpp`). So that's why the bot added the "consensus" tag and I prefixed the PR title with "consensus".] BIP 341 specifies [constraints on the size of the control block _c_ used to compute the taproot merkle root](https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki#script-validation-rules). > The last stack element is called the control block _c_, and must have length _33 + 32m_, for a value of _m_ that is an integer between 0 and 128, inclusive. Fail if it does not have such a length. The actual merkle root is computed in `ComputeTaprootMerkleRoot` ([interpreter.cpp@1833](https://github.com/bitcoin/bitcoin/blob/master/src/script/interpreter.cpp#L1833)) - this code does _not_ check these constraints. All the callers do check the constraints before calling `ComputeTaprootMerkleRoot`. But in the future there may be more callers, and these checks may be inadvertently omitted at those future calls. Also, code at/near the current call sites may also change and skip these checks. Therefore _this PR adds those checks as `asserts` directly in `ComputeTaprootMerkleRoot`_ to help prevent that error. No unit tests provided: they'd have to be death tests as these are `assert` statements which raise `SIGABRT` and kill the program. Boost Test has a way to implement death tests (see the in-progress draft PR bitcoin#25097 at [this code (you may have to click to expand the diff)](https://github.com/bitcoin/bitcoin/pull/25097/files#diff-21483d0e032747850208f21325b29cde89e9c1f55f83a7a166a388cc5c27115aR1089) and could be added here if desired by reviewers. Current callers of `ComputeTaprootMerkleRoot`: - `InferTaprootTree` ([standard.cpp@1552](https://github.com/bitcoin/bitcoin/blob/master/src/script/standard.cpp#L546)) - `VerifyTaprootCommittment` ([interpreter.cpp@1859](https://github.com/bitcoin/bitcoin/blob/master/src/script/interpreter.cpp#L1859)) does a partial check, but it is called from `VerifyWitnessProgram` ([interpreter.cpp@1922](https://github.com/bitcoin/bitcoin/blob/master/src/script/interpreter.cpp#L1918)) where a full check is done ACKs for top commit: sipa: ACK bd7c5e2 theStack: ACK bd7c5e2 Tree-SHA512: cec5aebfdf9fc9d13011abdf8427c934edf1df1ffc32b3e7cc5580f12809f24cf83e64ab0c843fabfce3591873bfcfa248277b30820fd786684319a196e4e550
Sign up for free
to subscribe to this conversation on GitHub.
Already have an account?
Sign in.
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.
[N.B.: This PR does not change the consensus. It only adds
assertstatements according to the current consensus in consensus-sensitive code (interpreter.cpp). So that's why the bot added the "consensus" tag and I prefixed the PR title with "consensus".]BIP 341 specifies constraints on the size of the control block c used to compute the taproot merkle root.
The actual merkle root is computed in
ComputeTaprootMerkleRoot(interpreter.cpp@1833) - this code does not check these constraints.All the callers do check the constraints before calling
ComputeTaprootMerkleRoot. But in the future there may be more callers, and these checks may be inadvertently omitted at those future calls. Also, code at/near the current call sites may also change and skip these checks. Therefore this PR adds those checks asassertsdirectly inComputeTaprootMerkleRootto help prevent that error.No unit tests provided: they'd have to be death tests as these are
assertstatements which raiseSIGABRTand kill the program. Boost Test has a way to implement death tests (see the in-progress draft PR #25097 at this code (you may have to click to expand the diff) and could be added here if desired by reviewers.Current callers of
ComputeTaprootMerkleRoot:InferTaprootTree(standard.cpp@1552)VerifyTaprootCommittment(interpreter.cpp@1859) does a partial check, but it is called fromVerifyWitnessProgram(interpreter.cpp@1922) where a full check is done