Implement BIP 340-342 validation (Schnorr/taproot/tapscript) #17977

pull sipa wants to merge 13 commits into bitcoin:master from sipa:taproot changing 38 files +2544 −115
  1. sipa commented at 11:14 pm on January 21, 2020: member

    This is an implementation of the Schnorr/taproot consensus rules proposed by BIPs 340, 341, and 342.

    It consists of:

    • Addition of Schnorr signatures and 32-byte pubkey support to libsecp256k1 subtree (https://github.com/bitcoin-core/secp256k1/pull/558 PR 558), following BIP 340.
    • The taproot validation specified in BIP 341.
    • Script validation under taproot (aka tapscript), specified in BIP 342.
    • Addition of signing logic for Schnorr/Taproot to the Python test framework, and tests for the above.

    This does not include any wallet support.

    Related PRs and PRs that were extracted from this and submitted separately: #18002 #16902 #18388 #18401 #18422 #18675 #19228

    Dependencies:

    • Merge BIP340 support in libsecp256k1
    • Update libsecp256k1 subtree in master (#19944)

    TODO:

    • Tests for pre-activation (verify that consensus behavior doesn’t change until flag is enabled)
    • Extract small & fast BIP341/BIP342 test vectors with good coverage out of the programmatic & slow feature_taproot.py test
  2. fanquake added the label Consensus on Jan 21, 2020
  3. sipa force-pushed on Jan 21, 2020
  4. sipa force-pushed on Jan 21, 2020
  5. sipa force-pushed on Jan 21, 2020
  6. sipa force-pushed on Jan 21, 2020
  7. DrahtBot commented at 11:47 pm on January 21, 2020: member

    The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

    Conflicts

    Reviewers, this pull request conflicts with the following ones:

    • #19792 (rpc: Add dumpcoinstats by fjahr)
    • #19695 ([do not merge] Test impact of secp256k1 endianness detection change by sipa)
    • #19521 (Coinstats Index (without UTXO set hash) by fjahr)
    • #19438 (Introduce deploymentstatus by ajtowns)
    • #18788 (tests: Update more tests to work with descriptor wallets by achow101)
    • #16546 (External signer support - Wallet Box edition by Sjors)
    • #13533 ([tests] Reduced number of validations in tx_validationcache_tests by lucash-dev)
    • #13062 (Make script interpreter independent from storage type CScript by sipa)

    If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

  8. sipa force-pushed on Jan 22, 2020
  9. sipa force-pushed on Jan 22, 2020
  10. in src/script/interpreter.cpp:1369 in 1f499c5b67 outdated
    1365+uint256 HashAgain(const uint256& hash)
    1366+{
    1367+    uint256 result;
    1368+    CSHA256().Write(hash.begin(), 32).Finalize(result.begin());
    1369+    return result;
    1370 }
    


    junderw commented at 6:35 am on January 22, 2020:

    Slightly confusing name… HashAgainSHA256?

    I understand why it exists, and I can’t think of a much better name… but having something in the name to denote we’re hashing with SHA256 might make it a tiny bit more readable.


    sipa commented at 8:12 pm on January 22, 2020:
    Changed into SHA256Uint256, and moved to hash.{h,cpp}.
  11. in src/chainparams.cpp:88 in 1f499c5b67 outdated
    82@@ -83,6 +83,11 @@ class CMainParams : public CChainParams {
    83         consensus.vDeployments[Consensus::DEPLOYMENT_TESTDUMMY].nStartTime = 1199145601; // January 1, 2008
    84         consensus.vDeployments[Consensus::DEPLOYMENT_TESTDUMMY].nTimeout = 1230767999; // December 31, 2008
    85 
    86+        // Deployment of Taproot
    87+        consensus.vDeployments[Consensus::DEPLOYMENT_TAPROOT].bit = 2;
    88+        consensus.vDeployments[Consensus::DEPLOYMENT_TESTDUMMY].nStartTime = 1199145601; // January 1, 2008
    


    kallewoof commented at 11:45 am on January 22, 2020:
    s/TESTDUMMY/TAPROOT/ here and in testnet (regtest is fine). Also think you want to set timeout to something less expired.

    sipa commented at 8:13 pm on January 22, 2020:
    Nice catch, fixed. I don’t know what “less expired” means; all dates in the past are equally expired.

    kallewoof commented at 1:47 am on January 23, 2020:
    Sorry, I meant it should expire in the future or the taproot deployment will fail to activate.

    sipa commented at 1:49 am on January 23, 2020:
    This PR intentionally doesn’t include mainnet activation; the values here are just a dummy. Apart from the fact that no activation time (or mechanism) has been established yet, that activation logic will likely be included in a different release than the validation logic (thus needing a separate PR anyway).
  12. in src/consensus/params.h:17 in 1f499c5b67 outdated
    13@@ -14,6 +14,7 @@ namespace Consensus {
    14 enum DeploymentPos
    15 {
    16     DEPLOYMENT_TESTDUMMY,
    17+    DEPLOYMENT_TAPROOT, // Deployment of bip-taproot/bip-tapscript/bip-schnorr
    


    MaxHillebrand commented at 2:31 pm on January 22, 2020:
    0    DEPLOYMENT_TAPROOT, // Deployment of BIP-340/BIP-341/BIP-342
    

    sipa commented at 8:13 pm on January 22, 2020:
    Fixed.
  13. in src/hash.h:221 in 1f499c5b67 outdated
    217@@ -204,4 +218,12 @@ unsigned int MurmurHash3(unsigned int nHashSeed, const std::vector<unsigned char
    218 
    219 void BIP32Hash(const ChainCode &chainCode, unsigned int nChild, unsigned char header, const unsigned char data[32], unsigned char output[64]);
    220 
    221+/** Return a CHashWriter primed for computing bip-schnorr compatible tagged hashes.
    


    MaxHillebrand commented at 2:32 pm on January 22, 2020:
    0/** Return a CHashWriter primed for computing BIP-340 compatible tagged hashes.
    

    sipa commented at 8:13 pm on January 22, 2020:
    Fixed.
  14. in src/secp256k1/include/secp256k1_schnorrsig.h:11 in 1f499c5b67 outdated
     6+#ifdef __cplusplus
     7+extern "C" {
     8+#endif
     9+
    10+/** This module implements a variant of Schnorr signatures compliant with
    11+ * BIP-schnorr
    


    MaxHillebrand commented at 2:38 pm on January 22, 2020:
    0 * BIP-340
    

    sipa commented at 8:14 pm on January 22, 2020:
  15. in test/functional/test_framework/key.py:458 in 1f499c5b67 outdated
    452@@ -384,3 +453,33 @@ def sign_ecdsa(self, msg, low_s=True):
    453         rb = r.to_bytes((r.bit_length() + 8) // 8, 'big')
    454         sb = s.to_bytes((s.bit_length() + 8) // 8, 'big')
    455         return b'\x30' + bytes([4 + len(rb) + len(sb), 2, len(rb)]) + rb + bytes([2, len(sb)]) + sb
    456+
    457+    def sign_schnorr(self, msg):
    458+        """Construct a bip-schnorr compatible signature with this key."""
    


    MaxHillebrand commented at 2:45 pm on January 22, 2020:
    0        """Construct a BIP-340 compatible Schnorr signature with this key."""
    

    sipa commented at 8:14 pm on January 22, 2020:
    Fixed.
  16. MaxHillebrand commented at 2:48 pm on January 22, 2020: none

    As the BIPs have now been assigned numbers, this changes…:

    • BIP-Schnorr to BIP-340
    • BIP-Taproot to BIP-341
    • BIP-Tapscript to BIP-342
  17. in src/secp256k1/include/secp256k1_schnorrsig.h:12 in 1f499c5b67 outdated
     7+extern "C" {
     8+#endif
     9+
    10+/** This module implements a variant of Schnorr signatures compliant with
    11+ * BIP-schnorr
    12+ * (https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki).
    


    MaxHillebrand commented at 2:58 pm on January 22, 2020:
    0 * (https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki).
    

    This link is broken until the BIP PR is merged.


    sipa commented at 8:14 pm on January 22, 2020:
  18. in src/secp256k1/include/secp256k1_schnorrsig.h:72 in 1f499c5b67 outdated
    67+ * Returns 1 on success, 0 on failure.
    68+ *  Args:    ctx: pointer to a context object, initialized for signing (cannot be NULL)
    69+ *  Out:     sig: pointer to the returned signature (cannot be NULL)
    70+ *  In:    msg32: the 32-byte message being signed (cannot be NULL)
    71+ *        seckey: pointer to a 32-byte secret key (cannot be NULL)
    72+ *       noncefp: pointer to a nonce generation function. If NULL, secp256k1_nonce_function_bipschnorr is used
    


    MaxHillebrand commented at 2:59 pm on January 22, 2020:
    0 *       noncefp: pointer to a nonce generation function. If NULL, secp256k1_nonce_function_bip340 is used
    

    Not sure if this breaks anything? :confused:


    sipa commented at 8:15 pm on January 22, 2020:

    MaxHillebrand commented at 8:40 pm on January 22, 2020:
    I have suggested the changes there
  19. in src/secp256k1/src/modules/schnorrsig/main_impl.h:67 in 1f499c5b67 outdated
    62+    ARG_CHECK(sig != NULL);
    63+    ARG_CHECK(msg32 != NULL);
    64+    ARG_CHECK(seckey != NULL);
    65+
    66+    if (noncefp == NULL) {
    67+        noncefp = secp256k1_nonce_function_bipschnorr;
    


    MaxHillebrand commented at 3:00 pm on January 22, 2020:
    0        noncefp = secp256k1_nonce_function_bip-340;
    

    Not sure if this breaks anything :confused:


    sipa commented at 8:15 pm on January 22, 2020:
    This belongs in https://github.com/bitcoin-core/secp256k1/pull/558. Also, that would be invalid C code.
  20. in src/secp256k1/src/modules/schnorrsig/main_impl.h:87 in 1f499c5b67 outdated
    82+    if (!secp256k1_fe_is_quad_var(&pk.y)) {
    83+        secp256k1_scalar_negate(&x, &x);
    84+    }
    85+
    86+    secp256k1_scalar_get_b32(seckey_tmp, &x);
    87+    if (!noncefp(buf, msg32, seckey_tmp, (unsigned char *) "BIPSchnorrDerive", (void*)ndata, 0)) {
    


    MaxHillebrand commented at 3:00 pm on January 22, 2020:
    0    if (!noncefp(buf, msg32, seckey_tmp, (unsigned char *) "BIP340Derive", (void*)ndata, 0)) {
    

    Not sure if this breaks anything :confused:


    sipa commented at 8:15 pm on January 22, 2020:
    Changing that would violate the spec.
  21. in src/policy/policy.cpp:240 in 1f499c5b67 outdated
    235+        // Check P2TR standard limits
    236+        if (witnessversion == 1 && witnessprogram.size() == WITNESS_V1_TAPROOT_SIZE && !prevScript.IsPayToScriptHash()) {
    237+            // Taproot spend
    238+            const auto& stack = tx.vin[i].scriptWitness.stack;
    239+            size_t stack_size = stack.size();
    240+            if (stack_size >= 2 && !stack[stack_size - 1].empty() && stack[stack_size - 1][0] == ANNEX_TAG) {
    


    skwp commented at 3:32 pm on January 22, 2020:
    Is there a name for this condition that can be explained with a function name or at least a comment?

    kallewoof commented at 4:13 pm on January 22, 2020:
    I don’t see the problem, personally.

    skwp commented at 5:47 pm on January 22, 2020:

    hey kalle, please see my comment below to pieter. I’m seeing if people are open to using a more consistent single level of abstraction to make the source easier to read.

    e.g. this can be evaluated by a newb (ignore if I got the concepts wrong, I’m trying to illustrate a more literate / single level of abstraction style as per http://principles-wiki.net/principles:single_level_of_abstraction)

    0if (payToTapRoot)
    1  if annexOnStack
    2    stack_size--; // ignore annex
    3  else 
    4    if (OpWhateverOnStack)
    5      checkWhateverConditionWithLoop
    6    end
    

    Again I could have totally gotten the details wrong but if the program looked like that at a single level of abstraction, with magic numbers given names and conditionals given names, many more people could actually participate in the PR process and grok what’s going on.


    sipa commented at 8:16 pm on January 22, 2020:
    I’ve added some comments. Better now?

    skwp commented at 9:12 pm on January 22, 2020:
    Thanks definitely helps, though I would still love to see some vars extracted to named for readability and deduplication. I’m not gonna nitpick your code for style, I’m just a humble bitcoin pleb. But I do know what it’s like to scale codebases to be friendly to onboarding new devs. I do think readability should be a concern if we want more devs in bitcoin. e.g. stack[stack_size - 1] is repeated all over the place. call it top_of_stack and so much more readable! 🤷‍♂ 😄

    sipa commented at 9:22 pm on January 22, 2020:
    Well the reason is that the stack_size variable changes, so a “top_of_stack” one would need to be updated, kinda defeating its meaning.

    sipa commented at 1:42 am on January 23, 2020:
    I’ve changed this code quite a bit. What do you think?
  22. in src/policy/policy.cpp:245 in 1f499c5b67 outdated
    240+            if (stack_size >= 2 && !stack[stack_size - 1].empty() && stack[stack_size - 1][0] == ANNEX_TAG) {
    241+                stack_size--; // Ignore annex
    242+            }
    243+            if (stack_size >= 2) {
    244+                // Script path spend
    245+                if ((stack[stack_size - 1][0] & 0xfe) == 0xc0) {
    


    skwp commented at 3:35 pm on January 22, 2020:

    why nested conditional here, but not nested above (line 240)? both branches have “stack_size >= 2” as well. without understanding what any of this means, would it be clearer to write like this, removing the duplication and nesting?

    0// precondition for taproot (?)
    1if (stack_size < 2) { return }
    2
    3if (!stack[stack_size - 1].empty() && stack[stack_size - 1][0] == ANNEX_TAG) {
    4// whatever this is
    5
    6} else if ((stack[stack_size - 1][0] & 0xfe) == 0xc0)) {
    7// script path spend
    8
    9}
    

    sipa commented at 5:26 pm on January 22, 2020:
    @skwp I’ll add some comments to clarify, but what you’re suggesting would be incorrect.

    skwp commented at 5:39 pm on January 22, 2020:
    Thanks @sipa. I’m not trying to nitpick, rather looking at ways to lower the barrier for reviewers and thus help get more eyes on things. I find that complex conditionals with lots of low level details can make bugs hard to spot and make it daunting for people new to the source to contribute. There might be good reason for the style employed throughout the code and we probably can’t change everything overnight, but even things like magic numbers (0xfe?? 0xc0??) everywhere makes it really hard to reason about, imho. Seems like we can make the source easier to read as we go with named conditionals, constants, etc.

    skwp commented at 5:52 pm on January 22, 2020:

    In fact I see that these magic numbers are already given names elsewhere. Can we use them here? This is way more readable and expresses intent

    0(stack[stack_size - 1][0] & TAPROOT_LEAF_MASK) == TAPROOT_LEAF_TAPSCRIPT
    

    sipa commented at 8:18 pm on January 22, 2020:

    Changed it to use the constants, that’s obviously the better way.

    The reason why the annex does not use a nested conditional is because it’s a single if statement that tests the presence of the annex (as in: both conditions are needed to have an annex). The tapscript conditional is split up into the logical “this is a script path spending” condition and the “this is a leaf version 0xc0 script”.

  23. sipa commented at 5:25 pm on January 22, 2020: member

    @MaxHillebrand A few overall comments:

    • I don’t think all references to (bip-)taproot/tapscript/schnorr should be changed to the BIP numbers; in some cases maybe we should just drop the “bip-” prefix (e.g. I think talking about a “taproot spend” is more clear than “bip341 spend”).
    • All changes in the src/secp256k1 directory should go to https://github.com/bitcoin-core/secp256k1/pull/558 instead (the src/secp256k1 is a git subtree imported from there).
    • The “BIPSchnorr” and “BIPSchnorrDerive” tagged hash tags are part of the spec, which I don’t think should be changed.
  24. MaxHillebrand commented at 5:34 pm on January 22, 2020: none
    Thanks @sipa, I agree with your comments. I have deleted my suggestions to change the tagged hashes, the others are still open. Please ACK/NACK and commit what you think is correct.
  25. in src/hash.cpp:94 in 1f499c5b67 outdated
    82+CHashWriter TaggedHash(const std::string& tag)
    83+{
    84+    CHashWriter writer(SER_GETHASH, 0);
    85+    uint256 taghash;
    86+    CSHA256().Write((unsigned char*)tag.data(), tag.size()).Finalize(taghash.begin());
    87+    writer << taghash << taghash;
    


    constcast-glitch commented at 7:42 pm on January 22, 2020:
    taghash is written twice. Is this intentional?

    sipa commented at 7:45 pm on January 22, 2020:
    Yes, please read the spec.
  26. in src/hash.cpp:86 in 1f499c5b67 outdated
    77@@ -77,3 +78,12 @@ void BIP32Hash(const ChainCode &chainCode, unsigned int nChild, unsigned char he
    78     num[3] = (nChild >>  0) & 0xFF;
    79     CHMAC_SHA512(chainCode.begin(), chainCode.size()).Write(&header, 1).Write(data, 32).Write(num, 4).Finalize(output);
    80 }
    81+
    82+CHashWriter TaggedHash(const std::string& tag)
    83+{
    84+    CHashWriter writer(SER_GETHASH, 0);
    85+    uint256 taghash;
    86+    CSHA256().Write((unsigned char*)tag.data(), tag.size()).Finalize(taghash.begin());
    


    Empact commented at 7:49 pm on January 22, 2020:

    nit: reinterpret_cast<unsigned char*>(const_cast<char*>(?

    The const_cast could be removed with C++17 and a switch to rvalue references.


    sipa commented at 8:11 pm on January 22, 2020:
    This should just be (const char*)tag.data. We don’t usually use C++ style casts for primitive types (they’re all equivalent anyway, and the C++ style ones are very verbose).
  27. sipa force-pushed on Jan 22, 2020
  28. in src/consensus/params.h:17 in 9f578bfcc7 outdated
    13@@ -14,6 +14,7 @@ namespace Consensus {
    14 enum DeploymentPos
    15 {
    16     DEPLOYMENT_TESTDUMMY,
    17+    DEPLOYMENT_TAPROOT, // Deployment of taproot (BIPs 340-342)
    


    nopara73 commented at 8:15 pm on January 22, 2020:

    Unify Taproot capitalization in comments.

    0    DEPLOYMENT_TAPROOT, // Deployment of Taproot (BIPs 340-342)
    

    sipa commented at 1:43 am on January 23, 2020:
    Updated.

    nopara73 commented at 3:13 am on January 23, 2020:
    Btw, I wasn’t planning to waste your time on this by suggesting to manually fix it up. You can just click apply suggestion on GitHub and it’ll create a shared commit.
  29. in src/script/interpreter.h:128 in 9f578bfcc7 outdated
    119@@ -114,32 +120,98 @@ enum
    120     // Making OP_CODESEPARATOR and FindAndDelete fail any non-segwit scripts
    121     //
    122     SCRIPT_VERIFY_CONST_SCRIPTCODE = (1U << 16),
    123+
    124+    // Taproot validation
    125+    //
    126+    SCRIPT_VERIFY_TAPROOT = (1U << 17),
    127+
    128+    // Making unknown taproot leaf versions non-standard
    


    nopara73 commented at 8:16 pm on January 22, 2020:

    Unify Taproot capitalization in comments.

    0    // Making unknown Taproot leaf versions non-standard
    

    sipa commented at 1:43 am on January 23, 2020:
    Updated.
  30. in src/script/script.cpp:141 in 9f578bfcc7 outdated
    137@@ -138,6 +138,9 @@ const char* GetOpName(opcodetype opcode)
    138     case OP_NOP9                   : return "OP_NOP9";
    139     case OP_NOP10                  : return "OP_NOP10";
    140 
    141+    // taproot
    


    nopara73 commented at 8:17 pm on January 22, 2020:

    Unify Taproot capitalization in comments.

    0    // Taproot
    

    sipa commented at 1:43 am on January 23, 2020:
    Updated.
  31. in src/script/script.h:201 in 9f578bfcc7 outdated
    197@@ -187,6 +198,9 @@ enum opcodetype
    198     OP_NOP9 = 0xb8,
    199     OP_NOP10 = 0xb9,
    200 
    201+    // taproot
    


    nopara73 commented at 8:17 pm on January 22, 2020:

    Unify Taproot capitalization in comments.

    0    // Taproot
    

    sipa commented at 1:44 am on January 23, 2020:
    Updated.
  32. in test/functional/p2p_segwit.py:1369 in 9f578bfcc7 outdated
    1364@@ -1364,7 +1365,11 @@ def test_segwit_versions(self):
    1365         assert_equal(len(self.nodes[1].getrawmempool()), 0)
    1366         for version in list(range(OP_1, OP_16 + 1)) + [OP_0]:
    1367             # First try to spend to a future version segwit script_pubkey.
    1368-            script_pubkey = CScript([CScriptOp(version), witness_hash])
    1369+            if version == OP_1:
    1370+                # Don't use 32-byte v1 witness (used by taproot)
    


    nopara73 commented at 8:18 pm on January 22, 2020:

    Unify Taproot capitalization in comments.

    0                # Don't use 32-byte v1 witness (used by Taproot)
    

    sipa commented at 1:44 am on January 23, 2020:
    Updated.
  33. in test/functional/feature_taproot.py:5 in 9f578bfcc7 outdated
    0@@ -0,0 +1,600 @@
    1+#!/usr/bin/env python3
    2+# Copyright (c) 2019 The Bitcoin Core developers
    3+# Distributed under the MIT software license, see the accompanying
    4+# file COPYING or http://www.opensource.org/licenses/mit-license.php.
    5+# Test taproot softfork.
    


    nopara73 commented at 8:24 pm on January 22, 2020:

    Unify Taproot capitalization in comments.

    0# Test Taproot softfork.
    

    sipa commented at 1:44 am on January 23, 2020:
    Updated.
  34. in src/script/interpreter.cpp:1449 in 9f578bfcc7 outdated
    1449+    // Epoch
    1450+    uint8_t epoch = 0;
    1451+    ss << epoch;
    1452+
    1453+    // Hash type
    1454+    if ((hash_type > 3) && (hash_type < 0x81 || hash_type > 0x83)) return false;
    


    Empact commented at 8:29 pm on January 22, 2020:

    nit: Perhaps more readable if we avoid magic numbers with something like:

    0static_assert(SIGHASH_TAPOUTPUTMASK < SIGHASH_TAPINPUTMASK);
    1if ((hash_type > SIGHASH_TAPOUTPUTMASK) && (hash_type <= SIGHASH_TAPINPUTMASK || hash_type > (SIGHASH_TAPINPUTMASK | SIGHASH_TAPOUTPUTMASK))) return false;
    

    Alternatively, a comment could be helpful.


    gmaxwell commented at 4:36 pm on January 23, 2020:
    I find that much less readable, particularly since the symbolic values you define wouldn’t be used anywhere else. More comments, however, would be fine.

    sipa commented at 2:32 am on January 25, 2020:
    I’ve rewritten this code in an overall more readable way, I think.
  35. in src/script/interpreter.cpp:1472 in 9f578bfcc7 outdated
    1472+    // Data about the input/prevout being spent
    1473+    const CScript& scriptPubKey = cache.m_spent_outputs[in_pos].scriptPubKey;
    1474+    uint8_t spend_type = 0;
    1475+    assert(execdata.m_annex_init);
    1476+    if (execdata.m_annex_present) {
    1477+        spend_type |= 1;
    


    Empact commented at 8:30 pm on January 22, 2020:
    nit: is it clearer to use or comment e.g. WITNESS_V0, and TAPROOT below?

    sipa commented at 2:33 am on January 25, 2020:
    I’ve rewritten this code to match the BIP specification more closely.
  36. in src/policy/policy.cpp:246 in 9f578bfcc7 outdated
    241+                stack_size--; // Ignore annex if present
    242+            }
    243+            if (stack_size >= 2) {
    244+                // Script path spend (2 or more stack elements are removing optional annex)
    245+                if ((stack[stack_size - 1][0] & TAPROOT_LEAF_MASK) == TAPROOT_LEAF_TAPSCRIPT) {
    246+                    // Leaf version 0xc0 (aka tapscript, see BIP 342)
    


    MaxHillebrand commented at 8:41 pm on January 22, 2020:
    0                    // Leaf version 0xc0 (aka Tapscript, see BIP 342)
    

    sipa commented at 2:48 am on January 23, 2020:
    Updated.
  37. in src/policy/policy.h:43 in 9f578bfcc7 outdated
    39@@ -40,6 +40,8 @@ static const bool DEFAULT_PERMIT_BAREMULTISIG = true;
    40 static const unsigned int MAX_STANDARD_P2WSH_STACK_ITEMS = 100;
    41 /** The maximum size of each witness stack item in a standard P2WSH script */
    42 static const unsigned int MAX_STANDARD_P2WSH_STACK_ITEM_SIZE = 80;
    43+/** The maximum size of each witness stack item in a standard tapscript */
    


    MaxHillebrand commented at 8:42 pm on January 22, 2020:
    0/** The maximum size of each witness stack item in a standard Tapscript */
    

    sipa commented at 2:47 am on January 23, 2020:
    Updated.
  38. in src/script/interpreter.h:139 in 9f578bfcc7 outdated
    134+    SCRIPT_VERIFY_DISCOURAGE_UNKNOWN_ANNEX = (1U << 19),
    135+
    136+    // Making unknown OP_SUCCESS non-standard
    137+    SCRIPT_VERIFY_DISCOURAGE_OP_SUCCESS = (1U << 20),
    138+
    139+    // Making unknown public key versions in tapscript non-standard
    


    MaxHillebrand commented at 8:42 pm on January 22, 2020:
    0    // Making unknown public key versions in Tapscript non-standard
    

    sipa commented at 2:47 am on January 23, 2020:
    Updated.
  39. in src/script/script.h:52 in 9f578bfcc7 outdated
    43@@ -44,6 +44,17 @@ static const unsigned int LOCKTIME_THRESHOLD = 500000000; // Tue Nov  5 00:53:20
    44 // SEQUENCE_FINAL).
    45 static const uint32_t LOCKTIME_MAX = 0xFFFFFFFFU;
    46 
    47+// Tag for input annex. If there are at least two witness elements for a transaction input,
    48+// and the first byte of the last element is 0x50, this last element is called annex, and
    49+// has meanings independent of the script
    50+static const unsigned int ANNEX_TAG = 0x50;
    51+
    52+// Validation weight per passing signature (tapscript only).
    


    MaxHillebrand commented at 8:42 pm on January 22, 2020:
    0// Validation weight per passing signature (Tapscript only).
    

    sipa commented at 2:48 am on January 23, 2020:
    Updated.
  40. in src/script/script.h:55 in 9f578bfcc7 outdated
    50+static const unsigned int ANNEX_TAG = 0x50;
    51+
    52+// Validation weight per passing signature (tapscript only).
    53+static constexpr uint64_t VALIDATION_WEIGHT_PER_SIGOP_PASSED = 50;
    54+
    55+// How much weight budget is added to the witness size (tapscript only).
    


    MaxHillebrand commented at 8:42 pm on January 22, 2020:
    0// How much weight budget is added to the witness size (Tapscript only).
    

    sipa commented at 2:48 am on January 23, 2020:
    Updated.
  41. in test/functional/test_framework/script.py:232 in 9f578bfcc7 outdated
    228@@ -223,11 +229,8 @@ def __new__(cls, n):
    229 OP_NOP9 = CScriptOp(0xb8)
    230 OP_NOP10 = CScriptOp(0xb9)
    231 
    232-# template matching params
    233-OP_SMALLINTEGER = CScriptOp(0xfa)
    234-OP_PUBKEYS = CScriptOp(0xfb)
    235-OP_PUBKEYHASH = CScriptOp(0xfd)
    236-OP_PUBKEY = CScriptOp(0xfe)
    237+# tapscript
    


    MaxHillebrand commented at 8:43 pm on January 22, 2020:
    0# Tapscript
    

    sipa commented at 2:48 am on January 23, 2020:
    Updated.
  42. MaxHillebrand commented at 8:46 pm on January 22, 2020: none
    Similar to Taproot, this unifies the upper case Tapscript consistently in the comments.
  43. in src/policy/policy.cpp:240 in 9f578bfcc7 outdated
    235+        // Check P2TR standard limits
    236+        if (witnessversion == 1 && witnessprogram.size() == WITNESS_V1_TAPROOT_SIZE && !prevScript.IsPayToScriptHash()) {
    237+            // Taproot spend (non-P2SH-wrapped, version 1, witness program size 32; see BIP 341)
    238+            const auto& stack = tx.vin[i].scriptWitness.stack;
    239+            size_t stack_size = stack.size();
    240+            if (stack_size >= 2 && !stack[stack_size - 1].empty() && stack[stack_size - 1][0] == ANNEX_TAG) {
    


    Empact commented at 8:56 pm on January 22, 2020:

    nit: stack.back()

    Neglected to examine the full context.


    sipa commented at 8:56 pm on January 22, 2020:
    No, that would be incorrect.
  44. sipa force-pushed on Jan 22, 2020
  45. in src/pubkey.cpp:177 in 2c55acda1c outdated
    166@@ -166,6 +167,23 @@ static int ecdsa_signature_parse_der_lax(const secp256k1_context* ctx, secp256k1
    167     return 1;
    168 }
    169 
    170+bool XOnlyPubKey::VerifySchnorr(const uint256 &hash, const std::vector<unsigned char>& sigbytes) const {
    171+    if (sigbytes.size() != 64) return false;
    


    Empact commented at 9:08 pm on January 22, 2020:
    nit: how about != sizeof(((secp256k1_schnorrsig){0}).data), a static_assert, or similar?

    real-or-random commented at 10:50 pm on January 22, 2020:
    In the end, all of this is probably personal taste but I think there is a reason why a lot of those magic numbers are just literals. This number will never need to change. sizeof(((secp256k1_schnorrsig){0}).data) just makes the code harder to read and review (because you need to look up the definition of secp256k1_schnorrsig, and it would be a little bit like having a constant BITS_IN_UINT256 = 256.

    Empact commented at 11:44 pm on January 22, 2020:

    The notion is that by tying one constant to a formal description, we can make explicit and enforced a connection that would otherwise be implicit and unenforced. IMO, that such a thing can’t be violated is always better than that it won’t be violated.

    There are ways to do that without making the code markedly more complex, such as offloading it to a constant + static_assert.


    gmaxwell commented at 4:30 pm on January 23, 2020:

    I agree with real-or-random.

    secp256k1_schnorrsig should be “functionally opaque”– like the other secp256k1_ types it isn’t actually an opaque struct only so it can be allocated on the stack. Library users should not be messing around with the internals of these types, and the library API makes no promise that the internal representation won’t change (and for some of them it’s even currently different on different platforms– although not this one).

    If the representation of secp256k1_schnorrsig were to change, signatures with sizes other than 64 bytes wouldn’t suddenly become valid in Bitcoin.

    If you were talking about a ‘64’ who’s purposes was to allocate memory to store a secp256k1_schnorrsig then your reflex to interrogate it with sizeof would be well placed– but that isn’t the case here. The data field in a secp256k1_schnorrsig could change length pretty arbitrarily (for example, storing R decompressed) and this line wouldn’t change).


    sipa commented at 1:48 am on January 25, 2020:

    I agree as well. The size of serialized signatures is not inherently related to the in-memory representation of secp256k1_schnorrsig.

    The BIP says something about sizes 64 and 65. The code does the exact same thing. You could introduce a constant, but I think that’s just distracting. You’d need to go look up the constant to verify the code is correct, while now you can just directly compare it with the BIP.

  46. in src/script/interpreter.cpp:459 in 2c55acda1c outdated
    456+        return set_error(serror, SCRIPT_ERR_STACK_SIZE);
    457+    }
    458     int nOpCount = 0;
    459     bool fRequireMinimal = (flags & SCRIPT_VERIFY_MINIMALDATA) != 0;
    460+    uint32_t opcode_pos = 0;
    461+    execdata.m_codeseparator_pos = 0xFFFFFFFFUL;
    


    Empact commented at 10:15 pm on January 22, 2020:
    nit: a NONE_EXECUTED constant would be expressive

    gmaxwell commented at 4:16 pm on January 23, 2020:
    It’s never reused. Renaming it just makes you look up a definition. Adding a comment like “// Fall-through value if none are executed.” would be both more informative and not create a reason to bounce around the code.

    Empact commented at 4:52 pm on January 23, 2020:
    Fair enough, it’s a matter of opinion as to which is more legible - though I see a few uses, e.g.: https://github.com/bitcoin/bitcoin/pull/17977/files#diff-b81dfdd8a5bd80fe9f82b5a40c4c991eR180

    sipa commented at 2:33 am on January 25, 2020:
    That initialization wasn’t needed actually, I’ve removed it. The constant in just in one place now.
  47. in test/functional/test_framework/key.py:368 in 2c55acda1c outdated
    363+            return False
    364+        s = int.from_bytes(sig[32:64], 'big')
    365+        if s >= SECP256K1_ORDER:
    366+            return False
    367+        e = int.from_bytes(TaggedHash("BIPSchnorr", sig[0:32] + self.get_bytes()[1:33] + msg), 'big') % SECP256K1_ORDER
    368+        if self.is_positive:
    


    jnewbery commented at 10:59 pm on January 22, 2020:

    This seems weird to me. How can we verify a signature for a point which does not have a square Y? Such public keys are not defined in bip-schnorr.

    I think it’d be clearer to assert that the pubkey has a square Y before verifying. I’d also suggest adding a get_xonly_pubkey() method to ECKey so we can directly get the valid bip-schnorr pubkey.


    real-or-random commented at 11:39 pm on January 22, 2020:

    This seems weird to me. How can we verify a signature for a point which does not have a square Y? Such public keys are not defined in bip-schnorr.

    Hm in fact it’s different in yet another way.

    • The very pedantic version: bip-schnorr defines public keys to be byte arrays of length 32. “square y” does not make sense for byte arrays.
    • The less pedantic version: Even if you interpret the byte array as an integer, it’s supposed to encode an x-coordinate only. “square y” does not make sense for an x-coordinate.

    See also https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr/reference.py#L99

    If we want to be compatible with the existing code here, I’m not sure what the best approach is. Maybe it makes more sense to accept a byte string, then parse it into a point and then use the existing code? edit: Well okay, I think in the end that’s already happening in the code, but I think it will still be cleaner if the verify_schnorr function would not take points directly.


    jnewbery commented at 2:18 pm on January 23, 2020:
    verify_schnorr has been updated to be a function that takes a pubkey (32-byte array) instead of being a method on ECPubKey.

    sipa commented at 2:34 am on January 25, 2020:
    I’ve completely rewritten the Python Schnorr code now, not using ECKey/ECPubKey at all.
  48. sipa force-pushed on Jan 23, 2020
  49. sipa force-pushed on Jan 23, 2020
  50. in src/script/interpreter.h:30 in 41acd620b5 outdated
    25@@ -24,6 +26,10 @@ enum
    26     SIGHASH_NONE = 2,
    27     SIGHASH_SINGLE = 3,
    28     SIGHASH_ANYONECANPAY = 0x80,
    29+
    30+    SIGHASH_TAPDEFAULT = 0,
    


    v1048576 commented at 9:51 am on January 23, 2020:

    Use taproot instead of tap? SIGHASH_TAPROOT_DEFAULT TAPROOT like other instances, e.g. TAPROOT_PROGRAM_SIZE.

    Also, SignatureHashTap() renamed to SignatureHashTaproot()? Similar to VerifyTaprootCommitment.


    sipa commented at 2:37 am on January 25, 2020:

    Agree, those enum values were weird. Changed to SIGHASH_INPUT_MASK, SIGHASH_OUTPUT_MASK, and SIGHASH_DEFAULT; even though they’re Taproot specific for now, that’s not inherently the case.

    SignatureHashTap wasn’t actually necessary, it was a leftover from older code. I’ve removed it.

  51. in src/script/script.cpp:337 in 41acd620b5 outdated
    328@@ -326,3 +329,11 @@ bool GetScriptOp(CScriptBase::const_iterator& pc, CScriptBase::const_iterator en
    329     opcodeRet = static_cast<opcodetype>(opcode);
    330     return true;
    331 }
    332+
    333+bool IsOpSuccess(const opcodetype& opcode)
    334+{
    335+    return (opcode == 0x50 || opcode == 0x62 || opcode == 0x89 ||
    


    v1048576 commented at 9:59 am on January 23, 2020:
    Why not check against opcode defines?

    gmaxwell commented at 4:32 pm on January 23, 2020:
    Because they’re all “OP_SUCCESS”? They aren’t other opcodes right now. Some of them share values with non-tapscript opcodes, but the usage is different.

    v1048576 commented at 5:28 pm on January 23, 2020:
    I was expecting something along the lines of OP_SUCCESS80, …, OP_SUCCESS254. OP_SUCCESSx mapping explicitly shows the shared opcodes?

    sipa commented at 2:08 am on January 25, 2020:
    I considered that, but I don’t think the amount of code needed is worth it, or would be more readable (if there isn’t a normative IsOpSuccess function, you’d be adding 87 constants to the enum, and instead writing “opcode == OP_SUCCESS80 || opcode == OP_SUCCESS98 || opcode == OP_SUCCESS126 || …” in ExecuteWitnessProgram directly).

    v1048576 commented at 3:42 pm on January 25, 2020:
    Ah yes, good point about 87 constants, thanks for the clarification.
  52. in test/functional/feature_taproot.py:403 in 41acd620b5 outdated
    398+        for annex in [None, bytes([ANNEX_TAG]) + random_bytes(random.randrange(0, 250))]:
    399+            standard = annex is None
    400+            sec1, sec2 = ECKey(), ECKey()
    401+            sec1.generate()
    402+            sec2.generate()
    403+            pub1, pub2 = sec1.get_pubkey(), sec2.get_pubkey()
    


    jnewbery commented at 2:27 pm on January 23, 2020:
    Should these be updated to be BIP schnorr pubkeys (32-byte arrays)?

    sipa commented at 2:38 am on January 25, 2020:
    Done by completely rewriting the Schnorr Python code.
  53. in src/script/sigcache.cpp:101 in 41acd620b5 outdated
    86@@ -79,15 +87,25 @@ void InitSignatureCache()
    87             (nElems*sizeof(uint256)) >>20, (nMaxCacheSize*2)>>20, nElems);
    88 }
    89 
    90-bool CachingTransactionSignatureChecker::VerifySignature(const std::vector<unsigned char>& vchSig, const CPubKey& pubkey, const uint256& sighash) const
    91+bool CachingTransactionSignatureChecker::VerifyECDSASignature(const std::vector<unsigned char>& vchSig, const CPubKey& pubkey, const uint256& sighash) const
    


    constcast-glitch commented at 4:49 pm on January 23, 2020:
    nit: This function (VerifyECDSASignature) is formatted different than VerifySchnorrSignature which have the single line if-statements on one line. Maybe use same formatting for consistency since the functions are very similar in layout. I guess it’s because this function already existed and don’t want to make unrelated formatting changes. New here so not sure if this is a valid remark. Please excuse me if so.

    sipa commented at 2:11 am on January 25, 2020:

    This is intentional, see https://github.com/bitcoin/bitcoin/blob/master/doc/developer-notes.md#coding-style-general:

    When writing patches, favor the new style over attempting to mimic the surrounding style, except for move-only commits.

    Do not submit patches solely to modify the style of existing code.

    So the new Schnorr code follows the preferred style, even though the ECDSA one retains the style it had before.

  54. sipa force-pushed on Jan 23, 2020
  55. sipa force-pushed on Jan 25, 2020
  56. in test/functional/feature_taproot.py:9 in b8048b8148 outdated
    0@@ -0,0 +1,594 @@
    1+#!/usr/bin/env python3
    2+# Copyright (c) 2019 The Bitcoin Core developers
    3+# Distributed under the MIT software license, see the accompanying
    4+# file COPYING or http://www.opensource.org/licenses/mit-license.php.
    5+# Test Taproot softfork (BIPs 340-342)
    6+
    7+from test_framework.blocktools import create_coinbase, create_block, add_witness_commitment
    8+from test_framework.messages import CTransaction, CTxIn, CTxOut, COutPoint, CTxInWitness
    9+from test_framework.script import CScript, TaprootSignatureHash, taproot_construct, OP_0, OP_1, OP_CHECKSIG, OP_CHECKSIGVERIFY, OP_CHECKSIGADD, OP_IF, OP_CODESEPARATOR, OP_ELSE, OP_ENDIF, OP_DROP, LEAF_VERSION_TAPSCRIPT, SIGHASH_SINGLE, is_op_success, CScriptOp, OP_RETURN, OP_VERIF, OP_1NEGATE, OP_EQUAL, OP_SWAP, OP_CHECKMULTISIG, OP_CHECKMULTISIGVERIFY, OP_NOTIF, OP_2DROP, OP_NOT, OP_2DUP, OP_1SUB, OP_DUP, MAX_SCRIPT_ELEMENT_SIZE, LOCKTIME_THRESHOLD, ANNEX_TAG
    


    kallewoof commented at 2:35 am on January 25, 2020:
     0from test_framework.script import (
     1    ANNEX_TAG,
     2    CScript,
     3    CScriptOp,
     4    LEAF_VERSION_TAPSCRIPT,
     5    LOCKTIME_THRESHOLD,
     6    MAX_SCRIPT_ELEMENT_SIZE,
     7    OP_0,
     8    OP_1,
     9    OP_1SUB,
    10    OP_1NEGATE,
    11    OP_2DROP,
    12    OP_2DUP,
    13    OP_CHECKMULTISIG,
    14    OP_CHECKMULTISIGVERIFY,
    15    OP_CHECKSIG,
    16    OP_CHECKSIGADD,
    17    OP_CHECKSIGVERIFY,
    18    OP_CODESEPARATOR,
    19    OP_DROP,
    20    OP_DUP,
    21    OP_ELSE,
    22    OP_ENDIF,
    23    OP_EQUAL,
    24    OP_IF,
    25    OP_NOT,
    26    OP_NOTIF,
    27    OP_RETURN,
    28    OP_SWAP,
    29    OP_VERIF,
    30    SIGHASH_SINGLE,
    31    TaprootSignatureHash,
    32    is_op_success,
    33    taproot_construct,
    34)
    

    sipa commented at 2:39 am on January 25, 2020:
    What a waste of lines. Is this more readable?

    kallewoof commented at 2:52 am on January 25, 2020:
    Lines don’t really cost anything. This is definitely readable, compared to the big blob it replaces.

    sipa commented at 2:55 am on January 25, 2020:
    They cost screen space, and this isn’t something that really requires reading.

    kallewoof commented at 3:00 am on January 25, 2020:
    It feels like people can just scroll down if they aren’t interested, or not if they are. I prefer to let the reader decide whether they desire to read or not. Anyway, it’s not big enough to waste time over. Do ignore.

    sipa commented at 6:56 pm on March 21, 2020:
    Done.
  57. in src/script/interpreter.cpp:1777 in b8048b8148 outdated
    1775+    if (tapleaf_hash) *tapleaf_hash = k;
    1776+    for (int i = 0; i < path_len; ++i) {
    1777+        CHashWriter ss_branch = HasherTapBranch;
    1778+        auto node_begin = control.data() + TAPROOT_CONTROL_BASE_SIZE + TAPROOT_CONTROL_NODE_SIZE * i;
    1779+        if (std::lexicographical_compare(k.begin(), k.end(), node_begin, node_begin + TAPROOT_CONTROL_NODE_SIZE)) {
    1780+           ss_branch << k << Span<const unsigned char>(node_begin, TAPROOT_CONTROL_NODE_SIZE);
    


    kallewoof commented at 6:10 am on January 25, 2020:
    Nit: indentation (here and L1781).

    sipa commented at 6:58 pm on March 21, 2020:
    Done.
  58. fanquake deleted a comment on Jan 25, 2020
  59. in src/script/interpreter.h:182 in b8048b8148 outdated
    179+    //! The tapleaf hash.
    180+    uint256 m_tapleaf_hash;
    181+
    182+    //! Whether m_codeseparator_pos is initialized.
    183+    bool m_codeseparator_pos_init = false;
    184+    //! Opcode position of the last executed OP_CODESEPARATOR (or -1 if none executed).
    


    JeremyRubin commented at 6:30 pm on January 25, 2020:
    documentation nit: preference to not use -1 to indicate a sentinel for a unsigned type.

    sipa commented at 6:58 pm on March 21, 2020:
    Done.
  60. in src/script/interpreter.h:195 in b8048b8148 outdated
    185+    uint32_t m_codeseparator_pos;
    186+
    187+    //! Whether m_annex_present and m_annex_hash are initialized.
    188+    bool m_annex_init = false;
    189+    //! Whether an annex is present.
    190+    bool m_annex_present;
    


    JeremyRubin commented at 6:32 pm on January 25, 2020:
    UB nit: while this is safe, I believe, as it is used, it would be better to initialize this to either true or false should there be a bug, it would at least not invoke UB.

    sipa commented at 6:35 pm on January 25, 2020:
    Not initializing it means giving valgrind a chance to detect incorrect use. I prefer to keep values uninitialized if they’re actually intended to not be used.

    JeremyRubin commented at 6:49 pm on January 25, 2020:

    That’s an interesting point I hadn’t considered! Could be an interesting separate project idea to have a macro of something like

    DEFINED_CONSENSUS(param) ---> if not VALGRIND_BUILD param endig

    to make sure that we define these things when we build for consensus, but to leave them undefined for valigrind.

    This could be expanded to, for class members which you want to have this check, to union/wrap and define an accessor function via macro to avoid class initialization and be able to check initialization for arbitrary things not just primitives.


    sipa commented at 6:59 pm on January 25, 2020:

    Does that really add anything? Yes, it technically removes UB in this case, but replaces it with incorrect consensus code. Furthermore, there already is a runtime check to avoid it (the _init) flag, and the ability to detect it during tests through Valgrind/ubsan/… (in the even less likely case the _init flag is set incorrectly).

    I feel this is all overkill, and we should just stick to the common practice of not initializing variables that deliberately hold no value.


    JeremyRubin commented at 7:12 pm on January 25, 2020:

    My point was more that we don’t get the valgrind checkability for non primitive types, which seems like a good property if we want it for primitive types. A 0’d hash should be treated as undefined so that valgrind could pick it up.

    But I’m resolving this convo here as it’s a sidetrack, as noted above, “Could be an interesting separate project idea”.

  61. in src/script/interpreter.h:180 in b8048b8148 outdated
    170+    WITNESS_V0 = 1,  //!< Witness v0 (P2WPKH and P2WSH); see BIP 141
    171+    TAPROOT = 2,     //!< Witness v1 with non-P2SH 32 byte program (Taproot), key path spending; see BIP 341
    172+    TAPSCRIPT = 3,   //!< Witness v1 with non-P2SH 32 byte program (Taproot), script path spending, leaf version 0xc0 (Tapscript); see BIP 342
    173+};
    174+
    175+struct ScriptExecutionData
    


    JeremyRubin commented at 6:43 pm on January 25, 2020:

    I’m generally not a fan of these Data interfaces which have all the bool x_init fields.

    As an alternative, we could use an optional type wrapper.

    However, optional types depend on boost until c++17, which we shouldn’t introduce consensus dependencies on.

    My proposal would be to copy the definition of c++17 optional into https://github.com/bitcoin/bitcoin/blob/99813a9745fe10a58bedd7a4cb721faf14f907a4/src/optional.h and drop the boost dependency, and then use this here. This can be done as a PR separate from Taproot so as not to further burden this PR.

    Here, optionals express both the nothing set and not initialized state (hence dual-wrapped options) but perhaps we’d be OK in collapsing the wrapped ones to represent (not initialized or not set) OR value.

    0 struct ScriptExecutionData
    1 {
    2     //! The tapleaf hash.
    3     Option<uint256> m_tapleaf_hash;
    4     Option<Option<uint32_t>> m_codeseparator_pos;
    5     //! Hash of the annex data, if any
    6     Option<Option<uint256>> m_annex_hash;
    7     /** How much validation weight is left (decremented for every successful signature check). */
    8     Option<int64_t> m_validation_weight_left;
    9 };
    

    This would seem, to me, to make the interface quite a bit safer and eliminates a bunch of initialization logic & prevents UB from cropping up.

    It would also be, in my opinion, a larger project (perhaps worthwhile) to generally rethink this state object to be accessed through an interface that guarantees the fields are accessed correctly – e.g., once a m_validation_weight_left is set it can only be read or decreased, and the function to decrease can set error if the condition isn’t met on underflow. Maybe not worth that large of a refactor though, I think optionals would already be an improvement.


    sipa commented at 7:13 pm on January 25, 2020:

    I agree to an extent that all the _init variables are ugly, but I don’t think that they’re that bad if you see them as just runtime checks for invalid code. The same can be accomplished without them using ubsan/valgrind, in many cases.

    About using Option… It’s arguably the right tool for the job, but there is no singular “definition of c++17 optional”; there is the libstdc++ implementation, and the libc++ one, both of which may be relying on platform specific extensions (I haven’t checked). Even ignoring that, the libstdc++ one is 1500 lines of code, which I think is really overkill for what we’d get. Since the Boost one can’t be used in libconsensus, I think the current code is not too bad.


    StEvUgnIn commented at 7:07 am on January 27, 2020:
    I examined libstdc++ implementation for RISC-V architechture and it seems portable and independent from any physical architecture https://github.com/riscv/riscv-gcc/commits/riscv-gcc-8.3.0/libstdc%2B%2B-v3

    sipa commented at 6:37 pm on January 27, 2020:
    @StEvUgnIn We can’t just copy GPL code, unfortunately. Using libc++’s version may be an option, but it still seems overkill to me (it also contains lots of libc++ specific macros, that may require additional files to be included).

    elichai commented at 5:01 pm on January 30, 2020:
    @JeremyRubin Don’t forget that the std namespace get special treatment from the compiler. so copying code from libstd without checking it might actually contain implementation defined behavior that won’t necessarily work correctly with a different compiler(or even just by being outside of the std namespace).

    sipa commented at 5:39 pm on March 21, 2020:
    This seems to be more of a potential improvement for later.
  62. in src/secp256k1/src/secp256k1.c:440 in b8048b8148 outdated
    435+
    436+    if (counter != 0) {
    437+        return 0;
    438+    }
    439+    /* Tag the hash with algo16 which is important to avoid nonce reuse across
    440+     * algorithms. If the this nonce function is used in BIP-schnorr signing as
    


    constcast-glitch commented at 9:14 pm on January 26, 2020:
    I believe “If the this nonce function …” should be “If this nonce function …”.

    gmaxwell commented at 9:30 pm on January 26, 2020:
    Can you repeat this comment here: https://github.com/bitcoin-core/secp256k1/pull/558 ?

    constcast-glitch commented at 9:37 pm on January 26, 2020:
    Done
  63. in src/pubkey.h:220 in b8048b8148 outdated
    212+
    213+    /** Verify a 64-byte Schnorr signature.
    214+     *
    215+     * If the signature is not 64 bytes, or the public key is not fully valid, false is returned.
    216+     */
    217+    bool VerifySchnorr(const uint256& hash, const std::vector<unsigned char>& vchSig) const;
    


    kallewoof commented at 6:07 am on January 27, 2020:
    It would be nice if there was an IsValid() function to check if the pubkey is actually valid, as opposed to the signature being invalid.

    sipa commented at 6:27 am on January 27, 2020:

    There should be no need.

    Public keys as specified by BIP340 are 32-byte arrays, not points or X coordinates or whatever. The signature validation algorithm takes as input a 32-byte public key, and 64-byte signature, and a 32-byte message.

    This is intentionally different from how ECDSA works, where differences between encoding errors and invalid signatures are significant, and arguably the cause of all the trouble we went through with ECDSA encodings, and BIP66…

    So, to be clear: there should never be a behavior difference between an invalid signature and invalidity due to invalid public keys. Both are just inputs for which the verification returns false. Having a way to distinguish the two would be a risk.


    StEvUgnIn commented at 6:44 am on January 27, 2020:

    It would be nice if there was an IsValid() function to check if the pubkey is actually valid, as opposed to the signature being invalid.

     0class XOnlyPubKey {
     1private:
     2    uint256 m_keydata;
     3
     4public:
     5    XOnlyPubKey(const uint256& in) : m_keydata(in) {}
     6
     7    /** Verify a 64-byte Schnorr signature.
     8     *
     9     * If the signature is not 64 bytes, or the public key is not fully valid, false is returned.
    10     */
    11    bool VerifySchnorr(const uint256& hash, const std::vector<unsigned char>& vchSig) const;
    12    bool CheckPayToContract(const XOnlyPubKey& base, const uint256& hash, bool sign) const;
    13
    14    const unsigned char& operator[](int pos) const { return *(m_keydata.begin() + pos); }
    15    const unsigned char* data() const { return m_keydata.begin(); }
    16    size_t size() const { return 32; }
    17};
    

    This on-line instruction is already doing the job XOnlyPubKey(const uint256& in) : m_keydata(in) {}


    kallewoof commented at 7:25 am on January 27, 2020:
    @sipa It is not useful to be able to distinguish between an invalid pubkey and an invalid signature? I don’t understand the reasoning there. Indeed it should be helpful to be able to tell a user which part they fat fingered, if any.

    kallewoof commented at 7:27 am on January 27, 2020:
    @StEvUgnIn No, I am talking about the call to secp256k1_xonly_pubkey_parse failing.

    sipa commented at 7:29 am on January 27, 2020:
    Sure, for users it may be useful to have a sanity check. But consensus code should never distinguish between invalid public key and invalid signature.

    StEvUgnIn commented at 7:51 am on January 31, 2020:

    sipa commented at 5:43 pm on March 21, 2020:
    @kallewoof So, I suggest that maybe we add a way to test if a pubkey is valid later when wallet support is added. But as the current PR is solely consensus/validation code, I think it’s simpler and safer to not expose that distinction for now.
  64. in src/script/interpreter.cpp:1451 in b8048b8148 outdated
    1451+        break;
    1452+    default:
    1453+        assert(false);
    1454+    }
    1455+    assert(in_pos < tx_to.vin.size());
    1456+    assert(cache.ready && cache.m_amounts_spent_ready);
    


    kallewoof commented at 7:40 am on January 28, 2020:

    This assertion will be hit, because cache is null when using the below constructor:

    https://github.com/bitcoin/bitcoin/blob/b8048b814821913b1f4c1c2070ec68b0c9001ec8/src/script/interpreter.h#L258

    Maybe checking if txdata is non-null and complain if it isn’t, at

    https://github.com/bitcoin/bitcoin/blob/b8048b814821913b1f4c1c2070ec68b0c9001ec8/src/script/interpreter.cpp#L1638


    sipa commented at 8:12 am on January 28, 2020:
    Well yes it would assert because that would be invalid. It seems it’s just doing its job?

    kallewoof commented at 8:21 am on January 28, 2020:
    I’m not arguing against the assert, I’m saying that we should catch ‘cache is null’ before this point.

    kallewoof commented at 8:33 am on January 28, 2020:

    Because it’s misleading and confusing. The assert is not triggering for the right reasons (I don’t even think it’s triggering at all, though tbh I’m not sure how C++ deals with being passed a null value for a referenced non-reference like this).

    It’s checking whether the cache is ready, but in reality the cache is null. This method does not even take a ref to begin with. The one place it’s called is L1638, which could just do an assert(txdata) before calling SignatureHashSchnorr.


    sipa commented at 8:33 am on January 28, 2020:

    I don’t think that helps. If you reach this point without the cache initialized, you’re using the code incorrectly.

    What is perhaps not clear is that this is not just a cache - we can’t recompute data in it if it missing based on other sources. We rely on it to pass in essential information about the spending that cannot be retrieved otherwise.


    sipa commented at 8:36 am on January 28, 2020:
    Oh, you’re talking about null vs uninitialized. I’ll investigate tomorrow. Dereferencing or invoking a member function of a null pointer is UB; if that can happen we should indeed catch it earlier. I can’t check the code right now.

    kallewoof commented at 8:44 am on January 28, 2020:

    Hm.. for v0 this is actually accomodated for

    0        const bool cacheready = cache && cache->ready;
    

    whereas for v1 this is mandatory. I still think it’s unnecessarily unhelpful, and a bit scary to have non-ref null values in code paths (even if as you say this is a hint of a bigger problem).


    sipa commented at 8:47 am on January 28, 2020:

    What do “non-ref null values” mean?

    A reference to nullptr is illegal, always. Only pointers can be nullptr.


    kallewoof commented at 8:58 am on January 28, 2020:
    In SignatureHashSchnorr, the last parameter, defined as const PrecomputedTransactionData& cache, is 0x0000000000000000 for the case where *this->txdata == nullptr above. This may be using the code incorrectly, but it seems worth catching before that call above.

    sipa commented at 6:57 pm on March 21, 2020:
    Nice catch, I finally looked into this, and I agree this is too fragile. I’ve changed SignatureHashSchnorr to take a pointer to a PrecomputedTramsactionData instead, and assert fail when it’s null.
  65. in src/script/interpreter.cpp:1401 in b8048b8148 outdated
    1398-PrecomputedTransactionData::PrecomputedTransactionData(const T& txTo)
    1399+void PrecomputedTransactionData::Init(const T& txTo, std::vector<CTxOut> spent_outputs)
    1400 {
    1401+    m_spent_outputs = std::move(spent_outputs);
    1402+
    1403+    if (ready) return;
    


    kallewoof commented at 8:07 am on January 28, 2020:

    If someone does txdata = PrecomputedTransactionData(tx); and then later tries to do txdata.Init(tx, spent_outputs); this line will terminate, despite m_amounts_spent_ready not being updated based on the new spent_outputs. Perhaps

    0if (ready && spent_outputs.empty()) return;
    

    Edit: maybe even split into if !ready, make hashes and if !m_amounts_spend_ready, do spent stuff. (also fixed description; m_spent_outputs is updated, but the bool is not)


    sipa commented at 6:58 pm on March 21, 2020:
    Done. I’ve rewritten this to effectively treat ready as referring to the pre-taproot stuff and m_amounts_spend_ready for the rest.
  66. in src/script/interpreter.h:216 in b8048b8148 outdated
    213 
    214 template <class T>
    215 uint256 SignatureHash(const CScript& scriptCode, const T& txTo, unsigned int nIn, int nHashType, const CAmount& amount, SigVersion sigversion, const PrecomputedTransactionData* cache = nullptr);
    216 
    217+template <class T>
    218+bool SignatureHashTap(uint256& hash_out, const ScriptExecutionData& execdata, const T& tx_to, unsigned int in_pos, uint8_t hash_type, SigVersion sigversion, const PrecomputedTransactionData& cache);
    


    kallewoof commented at 5:57 am on January 30, 2020:
    I believe this should be called SignatureHashSchnorr and be <typename T> to match interpreter.cpp v.

    sipa commented at 6:57 pm on March 21, 2020:
    It’s not called anywhere externally, so I’ve just dropped it from the header file.
  67. in src/policy/policy.cpp:236 in b8048b8148 outdated
    230@@ -231,6 +231,30 @@ bool IsWitnessStandard(const CTransaction& tx, const CCoinsViewCache& mapInputs)
    231                     return false;
    232             }
    233         }
    234+
    235+        // Check P2TR standard limits
    236+        if (witnessversion == 1 && witnessprogram.size() == WITNESS_V1_TAPROOT_SIZE && !prevScript.IsPayToScriptHash()) {
    


    pinheadmz commented at 1:19 pm on February 26, 2020:
    Is the P2SH check necessary here? There is a test for prevScript.IsWitnessProgram() a few lines up, is there anyway the script could still be P2SH at this point? Or should this actually test prev.scriptPubKey.IsPayToScriptHash() which is the actual previous TX output script, defined before prevScript is updated to the redeem script.

    sipa commented at 7:00 pm on March 21, 2020:
    @pinheadmz Good point, this is wrong; it’s supposed to test prev.scriptPubKey instead of prevScript. I’ve changed it to keep track of p2sh-ness above, and then test that instead.
  68. in src/script/interpreter.cpp:1820 in b8048b8148 outdated
    1826 
    1827-    // Disallow stack item size > MAX_SCRIPT_ELEMENT_SIZE in witness stack
    1828-    for (unsigned int i = 0; i < stack.size(); i++) {
    1829-        if (stack.at(i).size() > MAX_SCRIPT_ELEMENT_SIZE)
    1830-            return set_error(serror, SCRIPT_ERR_PUSH_SIZE);
    1831+    if (witversion == 1 && program.size() == TAPROOT_PROGRAM_SIZE && !is_p2sh) {
    


    jnewbery commented at 9:44 pm on March 9, 2020:
    Adding the !is_p2sh here means that any transaction input spending a P2SH-wrapped segwit v1 output will be valid, but will fail standardness withSCRIPT_ERR_DISCOURAGE_UPGRADABLE_WITNESS_PROGRAM (“Witness version reserved for soft-fork upgrades”) which seems like the wrong error message. We’re not expecting P2SH-wrapped segwit v1 outputs to reinterpreted by a future soft-fork, we’re simply leaving them unencumbered for safety reasons. I think for correctness we should return a new error type in that case.

    sipa commented at 7:01 pm on March 21, 2020:
    Maybe we can just change the error message to also encompass things that we don’t expect will ever be used? (for example, we don’t expect witness programs with size below 32 - and certainly not ones with size below 20 - to be used, but they’re still available for future extensions)
  69. laanwj referenced this in commit e5cb0dffd5 on Mar 13, 2020
  70. DrahtBot added the label Needs rebase on Mar 13, 2020
  71. sidhujag referenced this in commit 82fee8186d on Mar 14, 2020
  72. jnewbery commented at 9:18 pm on March 17, 2020: member

    I’ve rebased this on master, and taken the most recent version of https://github.com/bitcoin-core/secp256k1/pull/558 (which I’ve saved at https://github.com/jnewbery/secp256k1/tree/819c3a6c1 since the PR will have commits squashed and further small changes made). The rebased branch is at https://github.com/jnewbery/bitcoin/tree/pr17977.1. Changes:

    • O(1) OP_IF/NOTIF/ELSE/ENDIF script implementation and Abstract out script execution out of VerifyWitnessProgram() have both been merged into master (#16902 and #18002) so are no longer part of this PR.
    • The interface to secp256k1_xonly_pubkey_tweak_test has been changed to take the 32 bytes serialized output pubkey.
    • 32 bytes pubkeys are now implicit even y, not implicit square y
    • tagged hashes have changed

    I haven’t implemented the synthetic nonce/auxiliary randomness from https://github.com/bitcoin/bips/pull/893 in the test code. That could be done separately (but there’s nothing to be done in bitcoind for this - it’d be more as demonstration code in the test framework).

    The [MOVEONLY] Move single-sig checking EvalScript code to EvalChecksig and [REFACTOR] Initialize PrecomputedTransactionData in CheckInputs commits could be sliced off into their own PRs. There’s not any benefit from those changes outside Taproot, but if people think it’d be useful to reduce the size of this PR, I’m happy to open and maintain those PRs.

  73. sipa force-pushed on Mar 18, 2020
  74. sipa force-pushed on Mar 18, 2020
  75. sipa commented at 5:43 am on March 18, 2020: member

    Rebased, and included @jnewbery’s changes from above.

    Here is what I did:

    • I created a rebase myself (with the old libsecp256k1, and old square pubkey rule).
    • Compared the final tree with John’s version, allowing me to review the even-pubkey changes; everything looked correct, but I saw a few minor improvements.
    • I switched to John’s version, apart from this patch:
     0diff --git a/src/pubkey.cpp b/src/pubkey.cpp
     1index 246c19a8f8..2231a4ee71 100644
     2--- a/src/pubkey.cpp
     3+++ b/src/pubkey.cpp
     4@@ -178,9 +178,8 @@ bool XOnlyPubKey::VerifySchnorr(const uint256 &hash, const std::vector<unsigned
     5 
     6 bool XOnlyPubKey::CheckPayToContract(const XOnlyPubKey& base, const uint256& hash, bool negated) const
     7 {
     8-    secp256k1_xonly_pubkey base_point, output_point;
     9+    secp256k1_xonly_pubkey base_point;
    10     if (!secp256k1_xonly_pubkey_parse(secp256k1_context_verify, &base_point, base.data())) return false;
    11-    if (!secp256k1_xonly_pubkey_parse(secp256k1_context_verify, &output_point, m_keydata.begin())) return false;
    12     return secp256k1_xonly_pubkey_tweak_test(secp256k1_context_verify, m_keydata.begin(), negated, &base_point, hash.begin());
    13 }
    14 
    15diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp
    16index 12ad6e7236..c3dd00de43 100644
    17--- a/src/script/interpreter.cpp
    18+++ b/src/script/interpreter.cpp
    19@@ -1812,7 +1812,6 @@ static bool VerifyWitnessProgram(const CScriptWitness& witness, int witversion,
    20         } else {
    21             return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_WRONG_LENGTH);
    22         }
    23-        assert(false); // Unreachable code
    24     } else if (witversion == 1 && program.size() == TAPROOT_PROGRAM_SIZE && !is_p2sh) {
    25         if (!(flags & SCRIPT_VERIFY_TAPROOT)) return set_success(serror);
    26         auto stack = witness.stack;
    27@@ -1857,7 +1856,6 @@ static bool VerifyWitnessProgram(const CScriptWitness& witness, int witversion,
    28             }
    29             return set_success(serror);
    30         }
    31-        assert(false); // Unreachable code
    32     } else {
    33         if (flags & SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_WITNESS_PROGRAM) {
    34             return set_error(serror, SCRIPT_ERR_DISCOURAGE_UPGRADABLE_WITNESS_PROGRAM);
    
    • Also added a commit 61bdc448dffdc41ef03cb775bfb67e0dac1dca09, after noticing that an unnecessary stack copy was being made in VerifyWitnessProgram.
    • Pushed to the PR branch, and noticed that a new rebase was necessary.
    • Did another rebase.
    • Noticed the tests were failing, due to a bug introduced in #17319; fixed in 1d293165551dbc6403dba59c2e5a896c5ae5366e (submitted separately as #18374).
  76. DrahtBot removed the label Needs rebase on Mar 18, 2020
  77. sipa force-pushed on Mar 18, 2020
  78. sipa force-pushed on Mar 19, 2020
  79. sipa force-pushed on Mar 20, 2020
  80. sipa force-pushed on Mar 20, 2020
  81. sipa force-pushed on Mar 21, 2020
  82. sipa force-pushed on Mar 21, 2020
  83. sipa force-pushed on Mar 21, 2020
  84. in src/hash.cpp:9 in 7641c52162 outdated
    5@@ -6,6 +6,7 @@
    6 #include <crypto/common.h>
    7 #include <crypto/hmac_sha512.h>
    8 
    9+#include <string>
    


    Empact commented at 9:55 pm on March 21, 2020:
    nit: I’m not 100% clear on ourinclude guidelines - string is included via hash.h, so if that’s sufficient this line is unnecessary, if that’s not sufficient, then we should also include uint256.h, etc here.

    kallewoof commented at 11:36 pm on March 21, 2020:
    Guidelines say to include what you use, so including seems correct to me.
  85. sipa force-pushed on Mar 21, 2020
  86. sipa force-pushed on Mar 22, 2020
  87. in src/script/interpreter.cpp:1833 in 98ad33ac24 outdated
    1837+            execdata.m_annex_present = false;
    1838+        }
    1839+        execdata.m_annex_init = true;
    1840+        if (stack.size() == 1) {
    1841+            // Key path spending (stack size is 1 after removing optional annex)
    1842+            if (!checker.CheckSigSchnorr(stack[0], program, SigVersion::TAPROOT, execdata)) {
    


    jnewbery commented at 7:12 pm on March 24, 2020:
    should stack.front() be preferred over stack[0]?

    sipa commented at 8:30 pm on March 26, 2020:
    Done.
  88. sipa force-pushed on Mar 26, 2020
  89. sipa force-pushed on Mar 26, 2020
  90. sipa commented at 8:31 pm on March 26, 2020: member
    Rebased on top of #18388, #18422, and #18401, and addressed a number of comments.
  91. sipa force-pushed on Mar 26, 2020
  92. fanquake referenced this in commit 54646167db on Mar 27, 2020
  93. DrahtBot added the label Needs rebase on Mar 27, 2020
  94. sipa force-pushed on Mar 27, 2020
  95. sipa commented at 8:48 pm on March 27, 2020: member
    Rebased now that #18388 (Span stack) is merged.
  96. DrahtBot removed the label Needs rebase on Mar 27, 2020
  97. in src/script/interpreter.h:193 in b1e76bda23 outdated
    183+    bool m_codeseparator_pos_init = false;
    184+    //! Opcode position of the last executed OP_CODESEPARATOR (or 0xFFFFFFFF if none executed).
    185+    uint32_t m_codeseparator_pos;
    186+
    187+    //! Whether m_annex_present and m_annex_hash are initialized.
    188+    bool m_annex_init = false;
    


    jnewbery commented at 4:24 pm on March 28, 2020:
    nit: could these two bools be replaced with an Optional<bool>? Optional is std from c++17 but currently implemented using boost::optional. Do we prefer to keep that out of consensus code?

    sipa commented at 6:37 pm on March 28, 2020:
    We can’t use boost in libconsensus (well we could if we add a dependency mess to it, but I suspect we rather not). There was an earlier discussion in this PR about this, including the option of including a simple native Optional type definition. I think this is overkill, and this approach is fine for now - we can switch to std::optional once it’s available.

    instagibbs commented at 8:48 pm on July 14, 2020:
    Would be nice when time comes.
  98. in src/script/interpreter.h:206 in b1e76bda23 outdated
    203+static constexpr size_t WITNESS_V1_TAPROOT_SIZE = 32;
    204+
    205+
    206+static constexpr uint8_t TAPROOT_LEAF_MASK = 0xfe;
    207+static constexpr uint8_t TAPROOT_LEAF_TAPSCRIPT = 0xc0;
    208+static constexpr size_t TAPROOT_PROGRAM_SIZE = 32;
    


    jnewbery commented at 4:46 pm on March 28, 2020:
    Is this just a duplicate of WITNESS_V1_TAPROOT_SIZE? It’s only used once in VerifyWitnessProgram(). Can we replace that usage with WITNESS_V1_TAPROOT_SIZE?

    sipa commented at 6:38 pm on March 28, 2020:
    The constants happen to be identical, but there is no a-priori reason why they would be (if you wouldn’t know the BIP, say). They’re separate concepts, so merging the constants would IMO defeat the purpose of having a named constant in the first place.

    jnewbery commented at 8:54 pm on March 28, 2020:

    I’m confused by what the difference is.

    In policy.cpp:

    0        if (witnessversion == 1 && witnessprogram.size() == WITNESS_V1_TAPROOT_SIZE && !p2sh) {
    

    In interpreter.cpp:

    0    } else if (witversion == 1 && program.size() == TAPROOT_PROGRAM_SIZE && !is_p2sh) {
    

    Are those not comparing the same data to the same constant, just with different constant names?

    (those functions use the same constant names for segwit V0 scripthash program sizes:

    0        if (program.size() == WITNESS_V0_SCRIPTHASH_SIZE) {
    

    and

    0        if (witnessversion == 0 && witnessprogram.size() == WITNESS_V0_SCRIPTHASH_SIZE) {
    

    )


    sipa commented at 9:12 pm on March 28, 2020:
    Oh, of course! Sorry, I misread; thinking that one was the constant for (v0) P2WSH. Will merge them into one.

    sipa commented at 10:26 pm on March 28, 2020:
    Done.
  99. sipa force-pushed on Mar 28, 2020
  100. sipa commented at 10:27 pm on March 28, 2020: member
    Made another change: the policy-checking code now also uses Span stacks.
  101. MarcoFalke referenced this in commit a9213bbe75 on Apr 10, 2020
  102. DrahtBot added the label Needs rebase on Apr 10, 2020
  103. jnewbery commented at 8:30 pm on April 10, 2020: member
    Don’t rebase yet. I hope to get #18401 merged soon.
  104. in src/script/interpreter.h:147 in e83b1772d0 outdated
    142 
    143 bool CheckSignatureEncoding(const std::vector<unsigned char> &vchSig, unsigned int flags, ScriptError* serror);
    144 
    145 struct PrecomputedTransactionData
    146 {
    147+    //! Single-SHA256 versions
    


    michaelfolkson commented at 11:23 am on April 11, 2020:
    Optional nit (feel free to ignore): Refer to the BIP (341) explaining why single hashes are added. https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki#cite_note-15
  105. sidhujag referenced this in commit 042234f7f3 on Apr 13, 2020
  106. MarcoFalke referenced this in commit e16718a8b3 on Apr 16, 2020
  107. sidhujag referenced this in commit 8e77630a77 on Apr 16, 2020
  108. jnewbery commented at 7:19 pm on April 16, 2020: member

    I’ve rebased this branch on master here: https://github.com/jnewbery/bitcoin/tree/pr17977.2 (using the same libsecp commit).

    This did require one additional commit https://github.com/jnewbery/bitcoin/commit/df38ebef99229a29c16cda571ded4a3613ead743 due to the new assert added in PrecomputedTransactionData::Init(). I’ll PR that separately.

  109. MarcoFalke referenced this in commit a998c5185b on Apr 19, 2020
  110. jnewbery commented at 3:21 pm on April 19, 2020: member
  111. sipa force-pushed on Apr 19, 2020
  112. sipa commented at 9:34 pm on April 19, 2020: member
    @jnewbery Did the rebase myself, and ended up with an almost identical tree as yours. Yours was slightly cleaner, so I used that one, rebased it on a new secp256k1 subtree merge, and pushed it.
  113. DrahtBot removed the label Needs rebase on Apr 19, 2020
  114. sidhujag referenced this in commit 729d3bbcee on Apr 20, 2020
  115. JeremyRubin commented at 7:14 pm on April 21, 2020: contributor
    BTW if willing #18071 plucks out some of the changes from taproot & should be a relatively easy rebase. A couple symbol names are changed for clarity as the crypto return value has changed from the double hash to the single.
  116. DrahtBot added the label Needs rebase on Apr 27, 2020
  117. sipa force-pushed on May 2, 2020
  118. sipa commented at 9:19 pm on May 2, 2020: member
    Rebased, updated libsecp256k1 branch, and converted the Schnorr framework test to a Python unittest (see #18576).
  119. DrahtBot removed the label Needs rebase on May 2, 2020
  120. in test/functional/test_framework/address.py:10 in c547a9683b outdated
     5@@ -6,6 +6,7 @@
     6 
     7 import enum
     8 
     9+from .base58 import byte_to_base58
    10 from .script import hash256, hash160, sha256, CScript, OP_0
    


    MarcoFalke commented at 10:58 pm on May 2, 2020:
    0test/functional/test_framework/address.py:10:1: F401 '.script.hash256' imported but unused
    

    sipa commented at 7:34 am on May 6, 2020:
    Fixed.
  121. sipa force-pushed on May 6, 2020
  122. fanquake commented at 8:40 am on May 22, 2020: member

    @sipa IIUC, the secp256k1 changes here are currently updating our subtree to upstream @ https://github.com/bitcoin-core/secp256k1/commit/e9fccd4de1f2b382545dfbadeae54868447e2cdf; with https://github.com/bitcoin-core/secp256k1/pull/558 on top.

    Given there’s been another push to https://github.com/bitcoin-core/secp256k1/pull/558, as well as additional merges to secp256k1 master, and, it’s now been more than a year since we last updated our subtree, could you pull the secp256k1 subtree update out of here, and PR it separately? Then we’d have less change here, and what’s left would just be Schnorr related (#558). It’s also a good time as we are early in the 0.21 cycle.

  123. sipa force-pushed on May 22, 2020
  124. sipa commented at 8:17 pm on May 22, 2020: member
    Rebased to include the new bitcoin-core/secp256k1#558. @fanquake Will do, as soon as a few recent improvements are merged in the secp256k1 repository.
  125. sipa force-pushed on May 22, 2020
  126. sipa force-pushed on May 23, 2020
  127. sipa commented at 0:14 am on May 23, 2020: member
    Updated now to include the changes in https://github.com/bitcoin/bips/pull/920.
  128. Viral approved
  129. DrahtBot added the label Needs rebase on May 30, 2020
  130. sipa commented at 0:49 am on June 10, 2020: member
    Rebased on top of #19228
  131. sipa force-pushed on Jun 10, 2020
  132. fanquake removed the label Needs rebase on Jun 10, 2020
  133. ComputerCraftr referenced this in commit a600f3b1f9 on Jun 10, 2020
  134. MarcoFalke referenced this in commit 6762a627ec on Jun 10, 2020
  135. DrahtBot added the label Needs rebase on Jun 10, 2020
  136. sidhujag referenced this in commit 13869fcaee on Jun 10, 2020
  137. MarcoFalke referenced this in commit 85f7db2284 on Jun 11, 2020
  138. sidhujag referenced this in commit b195ad9d5c on Jun 11, 2020
  139. sipa force-pushed on Jun 18, 2020
  140. sipa commented at 4:27 pm on June 18, 2020: member
    Rebased after merge of #19228 and #18468.
  141. Viral approved
  142. DrahtBot removed the label Needs rebase on Jun 18, 2020
  143. sipa force-pushed on Jun 20, 2020
  144. in src/script/interpreter.cpp:1900 in a9f418aeb0 outdated
    1721+                return set_error(serror, SCRIPT_ERR_TAPROOT_WRONG_CONTROL_SIZE);
    1722+            }
    1723+            if (!VerifyTaprootCommitment(control, program, scriptPubKey)) {
    1724+                return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_MISMATCH);
    1725+            }
    1726+            if (flags & SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_TAPROOT_VERSION) {
    


    theuni commented at 4:45 pm on July 1, 2020:
    Any reason not to put the cheap policy check before VerifyTaprootCommitment() ?

    JeremyRubin commented at 7:19 pm on July 16, 2020:
    Also perhaps this is checked elsewhere by the logic that sets this SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_TAPROOT_VERSION flag, but don’t we need to check the flag version is not currently defined here?

    JeremyRubin commented at 7:22 pm on July 16, 2020:
    Ah I think @theuni commented from an earlier commit, so it wasn’t showing that a version is defined.

    sipa commented at 8:16 pm on July 19, 2020:
    @theuni I think it’s preferable to do checks for consensus-invalidity first, so that the error code you get is more consistent. As it isn’t inherently more expensive for an attacker to create a policy-invalid spend instead of one that just has an invalid signature say, I don’t think it matters for DoS resistance either. @JeremyRubin I have no idea what you’re trying to say.

    JeremyRubin commented at 8:41 pm on July 19, 2020:

    image @theuni comment shows up on this line, which is later amended to

    image

    So I was simply confused from the tagged snippet as to why it did not check the taproot leaf version.

    But the reason is because @theuni dropped his comment on an earlier commit, and github didn’t tag it as outdated.


    sipa commented at 8:53 pm on July 19, 2020:
    Ah, I see. That also explains why it may look like these two could easily be swapped @theuni - it’s only in a later commit that something is added in between them (and the order matters).

    JeremyRubin commented at 9:09 pm on July 19, 2020:
    I think in theory @theuni’s point stands, we could add a cheap check ahead of verifytaprootcommitment that checks and aborts if it’s an unknown leaf version, but yes the final state makes more sense as is.
  145. in src/hash.cpp:94 in 146952354b outdated
    86@@ -87,3 +87,10 @@ CHashWriter TaggedHash(const std::string& tag)
    87     writer << taghash << taghash;
    88     return writer;
    89 }
    90+
    91+uint256 SHA256Uint256(const uint256& hash)
    92+{
    93+    uint256 result;
    94+    CSHA256().Write(hash.begin(), 32).Finalize(result.begin());
    


    instagibbs commented at 7:57 pm on July 14, 2020:
    s/32/hash.size()/ if you don’t mind

    sipa commented at 9:15 pm on July 19, 2020:
    Done.
  146. in src/script/interpreter.cpp:1417 in 146952354b outdated
    1324+        hashPrevouts = SHA256Uint256(m_prevouts_hash);
    1325+        m_sequences_hash = GetSequenceHash(txTo);
    1326+        hashSequence = SHA256Uint256(m_sequences_hash);
    1327+        m_outputs_hash = GetOutputsHash(txTo);
    1328+        hashOutputs = SHA256Uint256(m_outputs_hash);
    1329+        if (!m_spent_outputs.empty()) {
    


    instagibbs commented at 8:02 pm on July 14, 2020:
    Is this ever expected to not hit?

    Sjors commented at 4:06 pm on July 16, 2020:
    Afaik no, because CheckInputScripts returns early for coinbase transactions. An assert here would make more sense

    sipa commented at 8:23 pm on July 19, 2020:
    I believe this is fine right now, but if this code ends up being reused in signing logic, it will actually be empty in cases where not all spent outputs are known (e.g. legacy signing through some RPCs).
  147. in src/script/interpreter.cpp:1420 in 146952354b outdated
    1327+        m_outputs_hash = GetOutputsHash(txTo);
    1328+        hashOutputs = SHA256Uint256(m_outputs_hash);
    1329+        if (!m_spent_outputs.empty()) {
    1330+            m_spent_amounts_hash = GetSpentAmountsHash(m_spent_outputs);
    1331+            m_spent_scripts_hash = GetSpentScriptsHash(m_spent_outputs);
    1332+            m_spent_outputs_ready = true;
    


    instagibbs commented at 8:03 pm on July 14, 2020:
    Is this for simply catching assertion condition?

    sipa commented at 8:24 pm on July 19, 2020:
    Yes. It’s an alternative to using optional here (which would otherwise pull in boost stuff into libconsensus, unless we wait for c++17).
  148. in src/pubkey.h:220 in 05b00d5eab outdated
    215+     * If the signature is not 64 bytes, or the public key is not fully valid, false is returned.
    216+     */
    217+    bool VerifySchnorr(const uint256& hash, const std::vector<unsigned char>& vchSig) const;
    218+
    219+    const unsigned char& operator[](int pos) const { return *(m_keydata.begin() + pos); }
    220+    size_t size() const { return 32; }
    


    instagibbs commented at 8:08 pm on July 14, 2020:
    s/32/m_keydata.size()/

    sipa commented at 9:15 pm on July 19, 2020:
    Done.
  149. in src/script/interpreter.cpp:1781 in a9f418aeb0 outdated
    1777@@ -1724,7 +1778,7 @@ bool VerifyScript(const CScript& scriptSig, const CScript& scriptPubKey, const C
    1778                 // The scriptSig must be _exactly_ CScript(), otherwise we reintroduce malleability.
    1779                 return set_error(serror, SCRIPT_ERR_WITNESS_MALLEATED);
    1780             }
    1781-            if (!VerifyWitnessProgram(*witness, witnessversion, witnessprogram, flags, checker, serror)) {
    1782+            if (!VerifyWitnessProgram(*witness, witnessversion, witnessprogram, flags, checker, serror, false)) {
    


    instagibbs commented at 8:28 pm on July 14, 2020:
    please annotate /* is_p2sh */

    sipa commented at 9:15 pm on July 19, 2020:
    Done.
  150. in src/script/interpreter.cpp:1826 in a9f418aeb0 outdated
    1822@@ -1769,7 +1823,7 @@ bool VerifyScript(const CScript& scriptSig, const CScript& scriptPubKey, const C
    1823                     // reintroduce malleability.
    1824                     return set_error(serror, SCRIPT_ERR_WITNESS_MALLEATED_P2SH);
    1825                 }
    1826-                if (!VerifyWitnessProgram(*witness, witnessversion, witnessprogram, flags, checker, serror)) {
    1827+                if (!VerifyWitnessProgram(*witness, witnessversion, witnessprogram, flags, checker, serror, true)) {
    


    instagibbs commented at 8:28 pm on July 14, 2020:
    please annotate /* is_p2sh */

    sipa commented at 9:15 pm on July 19, 2020:
    Done.
  151. in src/script/script_error.cpp:101 in a9f418aeb0 outdated
    94@@ -91,6 +95,10 @@ std::string ScriptErrorString(const ScriptError serror)
    95             return "Witness provided for non-witness script";
    96         case SCRIPT_ERR_WITNESS_PUBKEYTYPE:
    97             return "Using non-compressed keys in segwit";
    98+        case SCRIPT_ERR_TAPROOT_INVALID_SIG:
    99+            return "Invalid signature for Taproot key path spending";
    


    instagibbs commented at 8:33 pm on July 14, 2020:
    Could mention the key could be busted too.

    sipa commented at 8:30 pm on July 19, 2020:
    Do you have a suggested string?
  152. in src/script/interpreter.cpp:1396 in da73c5e3eb outdated
    1390@@ -1391,9 +1391,9 @@ bool SignatureHashSchnorr(uint256& hash_out, const T& tx_to, const uint32_t in_p
    1391     }
    1392 
    1393     // Data about the input/prevout being spent
    1394-    const auto* witstack = &tx_to.vin[in_pos].scriptWitness.stack;
    1395-    bool have_annex = witstack->size() > 1 && witstack->back().size() > 0 && witstack->back()[0] == 0xff;
    1396-    const uint8_t spend_type = (ext_flag << 1) + (have_annex ? 1 : 0); // The low bit indicates whether an annex is present.
    1397+    assert(execdata.m_annex_init);
    1398+    bool have_annex = execdata.m_annex_present;
    1399+    uint8_t spend_type = (ext_flag << 1) + (have_annex ? 1 : 0); // The low bit indicates whether an annex is present.
    


    instagibbs commented at 8:45 pm on July 14, 2020:
    did I miss why the const is dropped here?

    sipa commented at 9:15 pm on July 19, 2020:
    Nope, fixed.
  153. in src/script/interpreter.cpp:376 in 7cdc010c70 outdated
    367@@ -371,6 +368,67 @@ static bool EvalChecksig(const valtype& vchSig, const valtype& vchPubKey, CScrip
    368     return true;
    369 }
    370 
    371+static bool EvalChecksigTapscript(const valtype& sig, const valtype& pubkey, ScriptExecutionData& execdata, unsigned int flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptError* serror, bool& success)
    372+{
    373+    assert(sigversion == SigVersion::TAPSCRIPT);
    374+
    375+    /*
    376+     *  The following validation sequence is consensus critical. Please note how --
    


    instagibbs commented at 8:52 pm on July 14, 2020:

    The following validation sequence is consensus critical.

    You don’t say


    sipa commented at 9:16 pm on July 19, 2020:
    I know, right?

    Sjors commented at 5:22 pm on July 24, 2020:

    Perhaps the comment can be expanded to clarify how success is used by the caller:

    0If script execution doesn't trigger an error, success is added to the stack.
    1OP_CHECKSIGVERIFY immediately fails if success is false, whereas with
    2OP_CHECKSIG(_ADD) it's up to the rest of the script to
    3decide what to do with the signature result, typically based on the number
    4of non-empty signatures.
    

    Renaming success to did_sign makes its purpose more clear (but we’re kinda stuck with this variable name).

  154. in src/script/interpreter.cpp:1111 in 7cdc010c70 outdated
    1105+
    1106+                    // (sig num pubkey -- num)
    1107+                    if (stack.size() < 3) return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
    1108+
    1109+                    const valtype& sig = stacktop(-3);
    1110+                    const CScriptNum num(stacktop(-2), fRequireMinimal);
    


    instagibbs commented at 9:16 pm on July 14, 2020:
    N.B.: Let’s make sure there’s a test that catches the >4 bytes rule for addition

    sipa commented at 9:16 pm on July 19, 2020:
    Good idea.

    instagibbs commented at 1:24 am on July 20, 2020:
    I ended up writing that test, in the branch I posted.

    sipa commented at 6:13 pm on August 7, 2020:
    Marking as resolved.
  155. in src/script/interpreter.cpp:475 in 7cdc010c70 outdated
    472@@ -408,9 +473,12 @@ bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript&
    473             if (vchPushValue.size() > MAX_SCRIPT_ELEMENT_SIZE)
    474                 return set_error(serror, SCRIPT_ERR_PUSH_SIZE);
    475 
    476-            // Note how OP_RESERVED does not count towards the opcode limit.
    477-            if (opcode > OP_16 && ++nOpCount > MAX_OPS_PER_SCRIPT)
    478-                return set_error(serror, SCRIPT_ERR_OP_COUNT);
    479+            if (sigversion == SigVersion::BASE || sigversion == SigVersion::WITNESS_V0) {
    


    instagibbs commented at 9:28 pm on July 14, 2020:
    The various peppering of sigversion == SigVersion::BASE || sigversion == SigVersion::WITNESS_V0 and sigversion != SigVersion::TAPSCRIPT makes me a little uneasy. Synchronize these checks?

    sipa commented at 9:16 pm on July 19, 2020:
    There was only one sigversion != SigVersion::TAPSCRIPT so I’ve changed that to the other one.
  156. in src/script/interpreter.cpp:1743 in 7cdc010c70 outdated
    1739@@ -1634,6 +1740,25 @@ static bool ExecuteWitnessScript(const Span<const valtype>& stack_span, const CS
    1740 {
    1741     std::vector<valtype> stack{stack_span.begin(), stack_span.end()};
    1742 
    1743+    // OP_SUCCESSx processing overrides everything, including stack element size limits
    


    instagibbs commented at 1:16 pm on July 15, 2020:
    this would be easy/nice to split out for unit tests

    sipa commented at 8:48 pm on July 19, 2020:

    This is a bit annoying, as this loop has multiple distinct return branches, and it returning success can mean either continue execution or not.

    Happy to take some code if you have a suggestion, though.


    instagibbs commented at 1:08 am on July 20, 2020:
    Yeah found out the hard way after trying a few times.
  157. in src/script/interpreter.cpp:1659 in a9f418aeb0 outdated
    1655+    XOnlyPubKey p{uint256(std::vector<unsigned char>(control.begin() + 1, control.begin() + TAPROOT_CONTROL_BASE_SIZE))};
    1656+    XOnlyPubKey q{uint256(program)};
    1657+    uint256 k = (CHashWriter(HasherTapLeaf) << uint8_t(control[0] & TAPROOT_LEAF_MASK) << script).GetSHA256();
    1658+    for (int i = 0; i < path_len; ++i) {
    1659+        CHashWriter ss_branch = HasherTapBranch;
    1660+        auto node_begin = control.data() + TAPROOT_CONTROL_BASE_SIZE + TAPROOT_CONTROL_NODE_SIZE * i;
    


    instagibbs commented at 1:25 pm on July 15, 2020:
    I think it’d be cleaner to just make the Span here, then use it for next 4 lines?

    sipa commented at 9:17 pm on July 19, 2020:
    Good idea, done.
  158. in src/policy/policy.cpp:237 in 43cbfab02a outdated
    232@@ -231,6 +233,34 @@ bool IsWitnessStandard(const CTransaction& tx, const CCoinsViewCache& mapInputs)
    233                     return false;
    234             }
    235         }
    236+
    237+        // Check Taproot standardness limits
    


    instagibbs commented at 1:37 pm on July 15, 2020:
    Currently this only enforces MAX_STANDARD_TAPSCRIPT_STACK_ITEM_SIZE on top of consensus checks, yes?

    sipa commented at 9:16 pm on July 19, 2020:
    Indeed, updated comment.
  159. in test/functional/test_framework/key.py:437 in 98ea8e9b9b outdated
    432+    if x == 0 or x >= SECP256K1_ORDER:
    433+        return (None, None)
    434+    P = SECP256K1.affine(SECP256K1.mul([(SECP256K1_G, x)]))
    435+    return (P[0].to_bytes(32, 'big'), not SECP256K1.has_even_y(P))
    436+
    437+def tweak_privkey(key, tweak, negated=False):
    


    instagibbs commented at 1:40 pm on July 15, 2020:
    Should mention/rename it to show it’s “add” not “mult”

    sipa commented at 9:17 pm on July 19, 2020:
    Done.
  160. in test/functional/test_framework/key.py:459 in 98ea8e9b9b outdated
    451+    x = (x + t) % SECP256K1_ORDER
    452+    if x == 0:
    453+        return None
    454+    return x.to_bytes(32, 'big')
    455+
    456+def tweak_pubkey(key, tweak):
    


    instagibbs commented at 1:40 pm on July 15, 2020:
    Should mention/rename it to show it’s “add” not “mult”

    sipa commented at 9:17 pm on July 19, 2020:
    Done.

    jnewbery commented at 9:55 am on July 24, 2020:
    should this be tweak_add_pubkey?

    instagibbs commented at 1:01 pm on July 24, 2020:
    yeah looks like this didn’t change

    sipa commented at 11:41 pm on July 28, 2020:
    Oops, done now.
  161. instagibbs commented at 1:43 pm on July 15, 2020: member
    Did a higher level pass. Pretty easy to follow and review. 👍
  162. Sjors commented at 4:14 pm on July 16, 2020: member

    Code reviewed:

    • 284ca85e3fc4d30f60e7fbb903303b4dc935d82c: see #19055 (review)
    • 906819fb3a356c2c49fc6ae66bcd0d6157a7f216
    • 7469f0a078dbaae52848277c92b0592d2628df4f needs description, e.g.: A BIP-341 signature message may commit to the scriptPubKeys of all spent outputs, so store them all instead of processing sequentially..

    Regarding the “revert” commits in the secp256k1 branch. Are those to minimise the diff to just Schnorr related changes? Is the plan to do another subtree update like #19228 after https://github.com/bitcoin-core/secp256k1/pull/558 is merged?

    You can link to the BIP pages themselves now in the description.

  163. instagibbs commented at 2:13 pm on July 17, 2020: member

    I reviewed the tests(way more comprehensive than I thought), and made some commits which I believe increase readability quite a bit and test case(s): https://github.com/instagibbs/bitcoin/commits/taproot_tests

    Tests cases I’d like covered:

    • Invalid CScriptNum( too large) as input to CHECKSIGADD
    • Tests prior to activation of taproot (ideally you could run all the tests again, make sure they always pass block validity, even “damaged” cases? Future Work since no activation method is specified anyways yet.)
    • Too large for script push prior to OP_SUCCESSX causes failure(but not after)
    • If OP_SUCCESSX is hit, stack element sizes don’t exist
    • OP_CHECKSIGADD does the correct thing with valid inputs
    • Test that taproot/tapscript sigs don’t count towards legacy/segwitv0 block sig limits.
    • Adapt tests to explicitly check for reject message reasons for txns/blocks where possible
    • “Signature opcodes with unknown public key type and non-empty signature are also counted.”
    • Test empty signatures executed don’t count towards txin sigop limit … will update list as I go
  164. in test/functional/feature_taproot.py:311 in 23985b72be outdated
    306+        self.skip_if_no_wallet()
    307+
    308+    def set_test_params(self):
    309+        self.num_nodes = 1
    310+        self.setup_clean_chain = True
    311+        self.extra_args = [["-whitelist=127.0.0.1", "-acceptnonstdtxn=0", "-par=1"]]
    


    instagibbs commented at 6:29 pm on July 17, 2020:
    FYI nonstandard txns are rejected by default in regtest now ( I don’t mind explicit args in tests so meh)

    sipa commented at 9:17 pm on July 19, 2020:
    Done.
  165. sipa force-pushed on Jul 19, 2020
  166. sipa commented at 9:22 pm on July 19, 2020: member
    Rebased, updated to latest version of https://github.com/bitcoin-core/secp256k1/pull/558, and addressed a number of comments above. @Sjors The revert commits are a side-effect of using git subtree to switch to https://github.com/bitcoin-core/secp256k1/pull/558 (which itself is not based on secp256k1 master, so things in master but not there get reverted). Yes, the plan is to merge the Schnorr code in libsecp256k1, and then update subtree in this repo, before actually merging this PR. @instagibbs All of those test improvements look great! I’d prefer not picking up dozens of tiny commits for them though; do you want me to just squash them into the relevant commit here, or do you want to wait until you’ve done more? One nit: when adding overall comments about what a Python function does, use """bla""" docstrings instead of # comments.
  167. instagibbs commented at 1:09 am on July 20, 2020: member

    @sipa take the tests in any form you’d like, I just thought it would be easier for you to review the changes.

    I’m done for now, so feel free to check off any un-ticked boxes yourself.

  168. sipa force-pushed on Jul 20, 2020
  169. sipa commented at 1:57 am on July 20, 2020: member
    @instagibbs All your test improvements squashed into the relevant commits here.
  170. in test/functional/feature_taproot.py:701 in 42bda3592c outdated
    650+                CScript([CScriptNum(oversize_number-1), pub2, OP_CHECKSIGADD]),
    651+                # 29) CHECKSIGADD that must fail because numeric argument number is >4 bytes
    652+                CScript([CScriptNum(oversize_number), pub2, OP_CHECKSIGADD]),
    653+            ]
    654+            # For the next test we must predict the exact witness size
    655+            witness_size = 141 + (hashtype != 0) + (0 if annex is None else len(annex) + 1)
    


    instagibbs commented at 2:11 am on July 20, 2020:
    Wondering if you could un-magic this constant a bit. I was going to attempt to write another case for unknown pubkey using this template, but ran out of motivation to reverse engineer it.

    sipa commented at 4:49 am on July 28, 2020:
    I still have to do this.

    sipa commented at 11:40 pm on July 28, 2020:
    Better now? I’ve extended the test further too, and moved it to its own section.
  171. sipa force-pushed on Jul 20, 2020
  172. sipa force-pushed on Jul 20, 2020
  173. sipa force-pushed on Jul 21, 2020
  174. sipa commented at 8:55 pm on July 21, 2020: member
    Squashed in some more functional test improvements by @instagibbs. The failed spenders no check for expected error messages in block validation.
  175. in src/script/interpreter.cpp:1362 in 41d08f5d77 outdated
    1264@@ -1265,7 +1265,7 @@ uint256 GetPrevoutHash(const T& txTo)
    1265     for (const auto& txin : txTo.vin) {
    1266         ss << txin.prevout;
    1267     }
    1268-    return ss.GetHash();
    1269+    return ss.GetSHA256();
    


    Sjors commented at 2:43 pm on July 23, 2020:

    41d08f5d77f52bec0e31bb081d85fff2d67d0467: let’s document that uint256 GetPrevoutHash and GetSequenceHash (now) return a single SHA256 hash.

    Perhaps we should rename them to GetPrevoutsHash and GetSequencesHash, consistent with GetSpentAmountsHash and GetSpentScriptsHash.

    In BIP-341 the phrasing is slightly ambiguous: “sha_prevouts (32): the SHA256 of the serialization of all input outpoints.” It could be more clear that this means concatenate all previous and then hash them, rather than to concatenate the hashes. Changing the variable name helps with that clarity too.


    JeremyRubin commented at 9:38 pm on July 23, 2020:
    @Sjors please review https://github.com/bitcoin/bitcoin/pull/18071/files which proposes something similar.

    sipa commented at 4:50 am on July 28, 2020:
    Added some extra comments.
  176. in src/script/interpreter.cpp:1321 in 41d08f5d77 outdated
    1316@@ -1299,9 +1317,17 @@ void PrecomputedTransactionData::Init(const T& txTo, std::vector<CTxOut> spent_o
    1317 
    1318     // Cache is calculated only for transactions with witness
    1319     if (txTo.HasWitness()) {
    1320-        hashPrevouts = GetPrevoutHash(txTo);
    1321-        hashSequence = GetSequenceHash(txTo);
    1322-        hashOutputs = GetOutputsHash(txTo);
    1323+        m_prevouts_hash = GetPrevoutHash(txTo);
    1324+        hashPrevouts = SHA256Uint256(m_prevouts_hash);
    


    Sjors commented at 3:16 pm on July 23, 2020:

    41d08f5d77f52bec0e31bb081d85fff2d67d0467: maybe rename to m_prevouts_hash_v0 or m_prevouts_double_hash?

    In addition, shouldn’t we skip calculating hashes we don’t need depending on the witness version? Or is that negligible for validation performance (sorry, too lazy to bench this myself)?


    JeremyRubin commented at 9:42 pm on July 23, 2020:

    these are computed at the txn level, so you’d need to add some code which detects if there is no input of that type. Maybe worthwhile?

    But keep in mind that taproot isn’t calculating anything new, just caching the intermediate results…


    Sjors commented at 9:25 am on July 24, 2020:
    Don’t m_spent_amounts_hash and m_spent_scripts_hash (below) add two extra hash operations when verifying SegWit transactions?

    JeremyRubin commented at 7:32 pm on July 24, 2020:
    ah yes those are extra, but only when haswitness. I suppose we could add a function hasv1witness?

    sipa commented at 4:50 am on July 28, 2020:
    I’ve made some significant changes here; the code will now detect if a transaction needs BIP341 and/or BIP143 sighashing, and then only precompute what is needed for the existing ones.

    JeremyRubin commented at 3:09 am on August 28, 2020:

    I think it’s after this comment that the hash names began containing bip341?

    I don’t think it’s worth changing at this point, but I don’t love that naming convention because it’s more clear to name them based on what they are (e.g., m_prevouts_sha256 or m_prevouts_d_sha256) than to name based on a BIP, especially since 143 and 341 are digit wise reversed it tripped me up a bit when re-reviewing.

    This is also confusing because CTV & anyprevout will also use these same single hashes, so then it’s not even really accurate to call them bip341 hashes – that’s actually why I noticed, because rebasing CTV on taproot needed to be adjusted for the new names.

    Again, not worth changing at this point, but if you decide to rename them again later might be worth going to non bip name.

  177. in src/script/interpreter.cpp:1348 in 41d08f5d77 outdated
    1344@@ -1319,6 +1345,76 @@ template void PrecomputedTransactionData::Init(const CMutableTransaction& txTo,
    1345 template PrecomputedTransactionData::PrecomputedTransactionData(const CTransaction& txTo);
    1346 template PrecomputedTransactionData::PrecomputedTransactionData(const CMutableTransaction& txTo);
    1347 
    1348+static const CHashWriter HasherTapSighash = TaggedHash("TapSighash");
    


    Sjors commented at 3:21 pm on July 23, 2020:
    41d08f5d77f52bec0e31bb081d85fff2d67d0467 : TapSighash is written in camel case (TapSigHash) most of the time in BIP 341 (which would be my preference too).

    fjahr commented at 4:54 pm on July 24, 2020:
    I think these runtime constants tend to be formatted like normal variables in the rest of the code base, i.e. snake case. But there does not seem to be a particular rule on these in the style guide.

    Sjors commented at 7:30 am on July 25, 2020:
    Assuming this is in reply to #17977 (review) The string “TapSighash” itself, not the variable name, is consensus critical, because it gets hashed into transactions. So the code style guidelines aren’t relevant.

    sipa commented at 4:51 am on July 28, 2020:

    The constant itself is consensus-critical.

    The name of the variable was a style violation; it’s a constant, it should be ALL_CAPS. Did that.


    sipa commented at 4:58 am on July 28, 2020:
    Changed the variable name.

    sipa commented at 8:54 pm on July 28, 2020:
    See https://github.com/bitcoin/bips/pull/954 for fixing the consensus-critical inconsistency.
  178. in src/script/interpreter.cpp:1496 in 41d08f5d77 outdated
    1362+    assert(cache != nullptr && cache->m_ready && cache->m_spent_outputs_ready);
    1363+
    1364+    CHashWriter ss = HasherTapSighash;
    1365+
    1366+    // Epoch
    1367+    static constexpr uint8_t EPOCH = 0;
    


    Sjors commented at 6:42 pm on July 23, 2020:
    41d08f5d77f52bec0e31bb081d85fff2d67d0467: EPOCH is explained in BIP-341, but missing from “the message is the concatenation of the following data, in order”

    sipa commented at 4:52 am on July 28, 2020:
    The epoch is explained in footnote 19 of BIP341. Not sure what is missing.
  179. in src/script/interpreter.cpp:1514 in 41d08f5d77 outdated
    1381+        ss << cache->m_prevouts_hash;
    1382+        ss << cache->m_spent_amounts_hash;
    1383+        ss << cache->m_spent_scripts_hash;
    1384+        ss << cache->m_sequences_hash;
    1385+    }
    1386+    if (output_type == SIGHASH_ALL) {
    


    Sjors commented at 7:00 pm on July 23, 2020:
    41d08f5: this could lead to confusion if a later upgrade adds and permits a new SIGHASH type, given that the BIP specifies this as a negative: “If hash_type & 3 does not equal SIGHASH_NONE or SIGHASH_SINGLE”.

    sipa commented at 4:53 am on July 28, 2020:
    If this code is reused for a new sighash algorithm, this will be the least of our problems.
  180. in src/script/interpreter.cpp:1392 in 41d08f5d77 outdated
    1387+        ss << cache->m_outputs_hash;
    1388+    }
    1389+
    1390+    // Data about the input/prevout being spent
    1391+    const auto* witstack = &tx_to.vin[in_pos].scriptWitness.stack;
    1392+    bool have_annex = witstack->size() > 1 && witstack->back().size() > 0 && witstack->back()[0] == 0xff;
    


    Sjors commented at 7:02 pm on July 23, 2020:
    41d08f5: The BIP (still?) says 0x50 (I see this completely changes in a later commit, so will revisit then)

    sipa commented at 4:53 am on July 28, 2020:
    Good catch, fixed.
  181. in src/script/interpreter.cpp:1403 in 41d08f5d77 outdated
    1398+        ss << tx_to.vin[in_pos].nSequence;
    1399+    } else {
    1400+        ss << in_pos;
    1401+    }
    1402+    if (have_annex) {
    1403+        ss << (CHashWriter(SER_GETHASH, 0) << witstack->back()).GetSHA256();
    


    Sjors commented at 7:12 pm on July 23, 2020:
    41d08f5d77f52bec0e31bb081d85fff2d67d0467 : isn’t this missing a compact_size(size of annex) prefix?

    instagibbs commented at 7:26 pm on July 23, 2020:
    I thought that was implicit with vector serializations like this.

    Sjors commented at 7:44 pm on July 23, 2020:
    Having bumped my head against (missing) size bytes in serialisations, e.g with libwally, let’s at least add a comment to that effect.

    sipa commented at 7:50 pm on July 23, 2020:
    Vectors are serialized everywhere this way. Do we need to add comments also to block, transaction inputs, transaction outputs, ADDR messages, all lists in the protocol, …?

    Sjors commented at 9:26 am on July 24, 2020:
    No, you’re right, it’s actually the BIP that explicitly mentions it only here.
  182. Sjors commented at 7:18 pm on July 23, 2020: member
    Reviewed 41d08f5d77f52bec0e31bb081d85fff2d67d0467 Implement Taproot signature hashing (BIP 341)
  183. in src/secp256k1/src/modules/schnorrsig/main_impl.h:162 in ad51604f57 outdated
    156+        secp256k1_scalar_negate(&k, &k);
    157+    }
    158+    secp256k1_fe_normalize_var(&r.x);
    159+    secp256k1_fe_get_b32(&sig64[0], &r.x);
    160+
    161+    /* tagged hash(r.x, pk.x, msg32) */
    


    brmdbr commented at 10:47 pm on July 23, 2020:
    Hate to do this: capitalisation. Tagged hash

    sipa commented at 4:54 am on July 28, 2020:
    Comments for the libsecp256k1 changes should go to the PR there: https://github.com/bitcoin-core/secp256k1/pull/558
  184. in src/hash.cpp:91 in ad51604f57 outdated
    86+    CSHA256().Write((const unsigned char*)tag.data(), tag.size()).Finalize(taghash.begin());
    87+    writer << taghash << taghash;
    88+    return writer;
    89+}
    90+
    91+uint256 SHA256Uint256(const uint256& hash)
    


    jnewbery commented at 9:25 am on July 24, 2020:
    hash is the wrong name for this param. It should be input to match the header declaration (although I think preimage would be better still).

    sipa commented at 4:54 am on July 28, 2020:
    I’ve changed it to data. I think preimage is more useful when you’re talking about a hash input that generates a specified output.
  185. in src/script/interpreter.h:155 in ad51604f57 outdated
    147+    //! Single-SHA256 versions
    148+    uint256 m_prevouts_hash, m_sequences_hash, m_outputs_hash, m_spent_amounts_hash, m_spent_scripts_hash;
    149+    bool m_spent_outputs_ready = false;
    150+
    151+    //! Double-SHA256 versions
    152     uint256 hashPrevouts, hashSequence, hashOutputs;
    


    jnewbery commented at 9:44 am on July 24, 2020:
    I agree with @Sjors (https://github.com/bitcoin/bitcoin/pull/17977#discussion_r459527853) that these should be renamed. m_prevouts_hash and hashPrevouts doesn’t communicate that one of these members is the SHA256 digest and the other is the dSHA256 digest. I’d propose m_prevouts_sha256 and m_prevouts_double_sha256, but anything that communicates what these are would be an improvement.

    sipa commented at 4:55 am on July 28, 2020:
    Renamed the BIP341 ones with just a _bip341_ in the name, which is as specific as it can be, I think. I’m trying not to touch too much other stuff, so the others keep their name.
  186. in test/functional/test_framework/key.py:11 in ad51604f57 outdated
     6@@ -7,6 +7,17 @@
     7 keys, and is trivially vulnerable to side channel attacks. Do not use for
     8 anything but tests."""
     9 import random
    10+import hashlib
    


    jnewbery commented at 9:52 am on July 24, 2020:
    nit: sort :)

    sipa commented at 6:13 pm on August 7, 2020:
    Done.
  187. in src/script/interpreter.cpp:432 in cbcaab9a66 outdated
    370@@ -371,7 +371,7 @@ static bool EvalChecksig(const valtype& vchSig, const valtype& vchPubKey, CScrip
    371     return true;
    372 }
    373 
    374-bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& script, unsigned int flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptError* serror)
    375+bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& script, unsigned int flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptError* serror, ScriptExecutionData execdata)
    


    fjahr commented at 2:15 pm on July 24, 2020:
    nit: I would prefer the execdata before serror. Would also be more consistent with ExecuteWitnessScript.

    sipa commented at 4:58 am on July 28, 2020:
    Meh.

    sipa commented at 6:16 pm on August 7, 2020:
    Not going to do this, as it would mean changing more call sites (which currently pass serror, but wouldn’t have an execdata to pass).
  188. in src/script/interpreter.h:177 in b7a7f6ab2c outdated
    157@@ -146,14 +158,21 @@ struct PrecomputedTransactionData
    158 
    159 enum class SigVersion
    160 {
    161-    BASE = 0,
    162-    WITNESS_V0 = 1,
    163-    TAPROOT = 2,
    164+    BASE = 0,        //!< Bare scripts and P2SH redeemscripts; see BIP 16
    


    Sjors commented at 2:33 pm on July 24, 2020:
    b7a7f6ab2ccc30e323a5396c27cb82ffd613550b nit: these comments could be introduced in 41d08f5d77f52bec0e31bb081d85fff2d67d0467 (which adds TAPROOT = 2)

    sipa commented at 4:55 am on July 28, 2020:
    Indeed, done.
  189. in src/script/interpreter.h:168 in cbcaab9a66 outdated
    162@@ -163,6 +163,16 @@ enum class SigVersion
    163     TAPROOT = 2,     //!< Witness v1 with non-P2SH 32 byte program (Taproot), key path spending; see BIP 341
    164 };
    165 
    166+struct ScriptExecutionData
    167+{
    168+    //! Whether m_annex_present and m_annex_hash are initialized.
    


    Sjors commented at 4:35 pm on July 24, 2020:

    cbcaab9a66f82fa5bcc2711a5fee2adc47004cc8 nit: m_annex_hash is only initialized if m_annex_present is true, though I doubt it will confuse anyone. Alternate wordings:

    0//! Whether m_annex_present is initialized
    

    Or:

    0 //! Whether m_annex_present and (when needed) m_annex_hash are initialized.
    

    JeremyRubin commented at 9:02 pm on July 24, 2020:
    #17977#pullrequestreview-348338789

    sipa commented at 4:57 am on July 28, 2020:
    Done.
  190. in src/validation.cpp:1546 in 14d2178048 outdated
    1539@@ -1540,13 +1540,19 @@ bool CheckInputScripts(const CTransaction& tx, TxValidationState &state, const C
    1540     }
    1541 
    1542     if (!txdata.m_ready) {
    1543-        txdata.Init(tx);
    1544+        std::vector<CTxOut> spent_outputs;
    1545+        spent_outputs.reserve(tx.vin.size());
    1546+
    1547+        for (unsigned int i = 0; i < tx.vin.size(); i++) {
    


    fjahr commented at 4:56 pm on July 24, 2020:

    styleguide nit:

    0        for (unsigned int i = 0; i < tx.vin.size(); ++i) {
    

    sipa commented at 4:58 am on July 28, 2020:
    Done.
  191. in src/script/interpreter.cpp:381 in 988d7a795c outdated
    376+     *  The following validation sequence is consensus critical. Please note how --
    377+     *    upgradable public key versions precede other rules;
    378+     *    the script execution fails when using empty signature with invalid public key;
    379+     *    the script execution fails when using non-empty invalid signature.
    380+     */
    381+    success = !sig.empty();
    


    Sjors commented at 6:14 pm on July 24, 2020:
    I would find it marginally more readable to use !sig.empty() in the if statements below and move success = !sig.empty(); all the way to the bottom.

    sipa commented at 4:57 am on July 28, 2020:
    I’m not sure. The result is always exactly equal to !sig.empty() if no failure occurs, so I think this makes sense.
  192. in src/script/interpreter.cpp:411 in 988d7a795c outdated
    406+    }
    407+
    408+    return true;
    409+}
    410+
    411+/** Helper for OP_CHECKSIG and OP_CHECKSIGVERIFY
    


    Sjors commented at 6:22 pm on July 24, 2020:
    0/** Helper for OP_CHECKSIG, OP_CHECKSIGVERIFY and OP_CHECKSIGADD
    

    sipa commented at 4:58 am on July 28, 2020:
    Done.
  193. in src/script/interpreter.cpp:1780 in 988d7a795c outdated
    1741+        // OP_SUCCESSx processing overrides everything, including stack element size limits
    1742+        CScript::const_iterator pc = scriptPubKey.begin();
    1743+        while (pc < scriptPubKey.end()) {
    1744+            opcodetype opcode;
    1745+            if (!scriptPubKey.GetOp(pc, opcode)) {
    1746+                // Note how this condition would not be reached if an unknown OP_SUCCESSx was found
    


    Sjors commented at 7:03 pm on July 24, 2020:
    But only if OP_SUCCESSx occurred earlier? Is it worth the effort to check the whole script for OP_SUCCESSx before and then do second pass for other conditions?

    JeremyRubin commented at 7:40 pm on July 24, 2020:
    Nope, the spec is defined as first parsing the script into opcodes to check for OP_SUCCESSx, and then executing.

    JeremyRubin commented at 7:40 pm on July 24, 2020:
    so you should check for e.g. unexecuted branches as well.

    Sjors commented at 7:23 am on July 25, 2020:
    Afaik this code fails if it finds an unknown OPCODE before OP_SUCCESSx, so then it doesn’t match the spec?

    sipa commented at 7:30 am on July 25, 2020:
    If by unknown opcode you mean undecodable, no - because if an opcode can’t be decoded, there are also no other opcodes decodable after it.

    Sjors commented at 10:59 am on July 25, 2020:
    It wasn’t entirely clear to me what GetScriptOp does, in particular what happens if an opcode does not occur in the opcodetype enum, but apparently this is fine.
  194. Sjors commented at 7:17 pm on July 24, 2020: member

    Also reviewed 8594b77415c290089d2e88fd2c09dbfecef995ba (BIP 340) until 988d7a795cfc29b37c3ea3359fb69412ab04de53 (BIP 342)

    There’s two future anticipated features the BIPs: batch-verification and annexes. Is there any proof of concept code that can be used to sanity check this PR (and the BIPs themselves)?

  195. real-or-random commented at 8:25 pm on July 24, 2020: member

    Also reviewed 8594b77 (BIP 340) until 988d7a7 (BIP 342)

    There’s two future anticipated features the BIPs: batch-verification and annexes. Is there any proof of concept code that can be used to sanity check this PR (and the BIPs themselves)?

    Not sure if this is helpful but there’s https://github.com/bitcoin-core/secp256k1/pull/760.

  196. fjahr commented at 10:28 pm on July 24, 2020: member
    Initial review of 6c98ca63df45bebe2b87c69244f36d75f1ab4c82 to c05ec93cf9affc44c9c548f69685500c7648691e, everything but schnorr and tests, mainly focussed on comparing code and the BIPs. Only leaving a few nits, feel free to ignore. Will still review the tests more thoroughly.
  197. sipa force-pushed on Jul 28, 2020
  198. sipa commented at 5:02 am on July 28, 2020: member

    Rebased, updated to latest libsecp256k1 Schnorr PR, addressed a number of comments (though there are a few left). The biggest change is that the sighash precomputation now takes into account whether a transaction contains/needs taproot precomputation or not.

    I also improved the functional tests. It now includes P2PKH/P2WPKH/P2SH-P2WPKH spends as well, just to make sure transactions with mixes have their sighashes computed correctly still. The framework now also tracks (pre-taproot) sigops, to accurately fill the block with them.

    The BIP340 implementation in the test framework is also updated to the latest spec (including support for the auxiliary randomness), and implements/contains the BIP’s test vectors now (which are verified against the secp256k1 implementation as well).

  199. sipa force-pushed on Jul 28, 2020
  200. sipa renamed this:
    [WIP] Implement BIP 340-342 validation (Schnorr/taproot/tapscript)
    Implement BIP 340-342 validation (Schnorr/taproot/tapscript)
    on Jul 28, 2020
  201. in test/functional/feature_taproot.py:1156 in 92d3928ed1 outdated
    405+
    406+    def block_submit(self, node, txs, msg, err_msg, cb_pubkey=None, fees=0, sigops_weight=0, witness=False, accept=False):
    407+
    408+        # Deplete block of any non-tapscript sigops using a single additional 0-value coinbase output.
    409+        # It is not impossible to fit enough tapscript sigops to hit the old 80k limit without
    410+        # busting txin-level limits. We simply have to account for the p2pk outputs in all
    


    instagibbs commented at 2:01 pm on July 28, 2020:
    Last sentence here is outdated.

    sipa commented at 9:17 pm on August 6, 2020:
    How so?

    instagibbs commented at 0:53 am on August 7, 2020:
    I was taking p2pk literally but I guess it could be read more generally.

    sipa commented at 6:18 pm on August 7, 2020:
    You can take it literally. P2PK (and other bare-public-key-in-output types, but there aren’t any of those in this test) are the only ones that cost sigops.

    instagibbs commented at 6:22 pm on August 7, 2020:
    ok I misunderstood your comment, will just review instead.
  202. in test/functional/feature_taproot.py:1158 in 92d3928ed1 outdated
    407+
    408+        # Deplete block of any non-tapscript sigops using a single additional 0-value coinbase output.
    409+        # It is not impossible to fit enough tapscript sigops to hit the old 80k limit without
    410+        # busting txin-level limits. We simply have to account for the p2pk outputs in all
    411+        # transactions.
    412+        extra_output_script = CScript([OP_CHECKSIG]*((MAX_BLOCK_SIGOPS_WEIGHT - sigops_weight) // WITNESS_SCALE_FACTOR))
    


    instagibbs commented at 2:04 pm on July 28, 2020:
    nice, you may get 1 to 3 sigops weight left over by chance, but tests will blow that out regularly.

    sipa commented at 8:21 pm on July 28, 2020:

    Yeah, I know, but it’s a lot harder to test that accurately (it needs creating outputs and spending them using witness spends, …).

    Ideally, we’d also test that if you have one sigop too many, things also fail. Otherwise it could be the case that some of the sigops estimates in the test are overestimates.

  203. instagibbs commented at 2:06 pm on July 28, 2020: member
    Looks great, love the mixed input types. test delta ACK
  204. sipa force-pushed on Jul 28, 2020
  205. gmaxwell commented at 2:25 am on July 29, 2020: contributor

    im in ur codebase 0pt1miz1ng ur lines.

    u can tell diz code waz unoptimal cuz feature_taproot.py still passes with this optimization

     0diff --git a/src/secp256k1/src/modules/schnorrsig/main_impl.h b/src/secp256k1/src/modules/schnorrsig/main_impl.h
     1index 2ec1cea5b..5efdee4b4 100644
     2--- a/src/secp256k1/src/modules/schnorrsig/main_impl.h
     3+++ b/src/secp256k1/src/modules/schnorrsig/main_impl.h
     4@@ -223,8 +223,7 @@ int secp256k1_schnorrsig_verify(const secp256k1_context* ctx, const unsigned cha
     5     secp256k1_gej_set_ge(&pkj, &pk);
     6     secp256k1_ecmult(&ctx->ecmult_ctx, &rj, &pkj, &e, &s);
     7 
     8-    return secp256k1_gej_has_quad_y_var(&rj) /* fails if rj is infinity */
     9-            && secp256k1_gej_eq_x_var(&rx, &rj);
    10+    return secp256k1_gej_eq_x_var(&rx, &rj);
    11 }
    12 
    13 #endif
    

    (yes, libsecp256k1’s tests catches this, but this an an important and easily botched consensus rule too)

    moar optimization “fixes” coming soon

  206. gmaxwell commented at 2:45 am on July 29, 2020: contributor

    all numb3erz r equally blessed in eyes of ur tests

     0diff --git a/src/secp256k1/src/modules/extrakeys/main_impl.h b/src/secp256k1/src/modules/extrakeys/main_impl.h
     1index a2abc6afa..04c84bde5 100644
     2--- a/src/secp256k1/src/modules/extrakeys/main_impl.h
     3+++ b/src/secp256k1/src/modules/extrakeys/main_impl.h
     4@@ -30,9 +30,8 @@ int secp256k1_xonly_pubkey_parse(const secp256k1_context* ctx, secp256k1_xonly_p
     5     if (!secp256k1_fe_set_b32(&x, input32)) {
     6         return 0;
     7     }
     8-    if (!secp256k1_ge_set_xo_var(&pk, &x, 0)) {
     9-        return 0;
    10-    }
    11+    secp256k1_ge_set_xo_var(&pk, &x, 0);
    12+
    13     secp256k1_xonly_pubkey_save(pubkey, &pk);
    14     secp256k1_ge_clear(&pk);