consensus: Add BIP-341 specified constraints in ComputeTaprootMerkleRoot #25132

1. 
   david-bakin commented at 5:21 am on May 14, 2022: contributor

   [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.

   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) - 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 #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 from VerifyWitnessProgram (interpreter.cpp@1922) where a full check is done
2. DrahtBot added the label Consensus on May 14, 2022
3. david-bakin force-pushed on May 14, 2022
4. david-bakin renamed this:
   Add BIP-341 specified constraints as asserts in `ComputeTaprootMerkel…
   consensus: Add BIP-341 specified constraints in `ComputeTaprootMerkelRoot`
   on May 14, 2022
5. 
   jamesob commented at 1:26 pm on May 16, 2022: member

   Concept ACK
6. in src/script/interpreter.cpp:1837 in 166e7b49c6 outdated

   1831@@ -1832,6 +1832,10 @@ uint256 ComputeTapleafHash(uint8_t leaf_version, const CScript& script)
   1832 
   1833 uint256 ComputeTaprootMerkleRoot(Span<const unsigned char> control, const uint256& tapleaf_hash)
   1834 {
   1835+    assert(control.size() >= TAPROOT_CONTROL_BASE_SIZE
   1836+           && control.size() <= TAPROOT_CONTROL_MAX_SIZE
   1837+           && ((control.size() - TAPROOT_CONTROL_BASE_SIZE) % TAPROOT_CONTROL_NODE_SIZE == 0));
   

   ---

   ---

   

   theStack commented at 1:45 pm on May 16, 2022:

   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:

   0    assert(control.size() >= TAPROOT_CONTROL_BASE_SIZE);
   1    assert(control.size() <= TAPROOT_CONTROL_MAX_SIZE);
   2    assert((control.size() - TAPROOT_CONTROL_BASE_SIZE) % TAPROOT_CONTROL_NODE_SIZE == 0);
   

   ---

   

   david-bakin commented at 3:12 am on May 17, 2022:

   Applied suggestion, thanks.
7. 
   theStack commented at 1:46 pm on May 16, 2022: member

   Concept ACK
8. david-bakin renamed this:
   consensus: Add BIP-341 specified constraints in `ComputeTaprootMerkelRoot`
   consensus: Add BIP-341 specified constraints in `ComputeTaprootMerkleRoot`
   on May 18, 2022
9. 
   dunxen commented at 7:33 pm on May 24, 2022: contributor

   Concept ACK
10. david-bakin force-pushed on May 24, 2022
11. 
    david-bakin commented at 9:22 pm on May 24, 2022: contributor

    CI failure “[no wallet, libbitcoinkernel] [bionic] Failing after 15m — Task Summary” possibly #24575?
12. Add BIP-341 specified constraints to `ComputeTaprootMerkleRoot`

    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)

    bd7c5e2f0a
13. david-bakin force-pushed on May 25, 2022
14. 
    david-bakin commented at 9:24 pm on May 25, 2022: contributor

    Last two merges: First was a squash, second was to kick the CI to fix a spurious check fail.
15. 
    sipa commented at 9:42 pm on May 25, 2022: member

    ACK bd7c5e2f0a1b572decdf3a4bafe4ee990e1f4953

    I think it makes sense to spell out these assumptions explicitly.

16. theStack approved
17. 
    theStack commented at 11:38 pm on May 25, 2022: member

    ACK bd7c5e2f0a1b572decdf3a4bafe4ee990e1f4953
18. laanwj merged this on May 26, 2022
19. laanwj closed this on May 26, 2022

    ---

20. david-bakin deleted the branch on May 28, 2022
21. sidhujag referenced this in commit 85b89f3426 on May 28, 2022
22. DrahtBot locked this on May 28, 2023

Contributors
david-bakin jamesob theStack dunxen sipa

Labels
Consensus