Merge bitcoin/bitcoin#23394: Taproot wallet test vectors (generation+tests)

f1c33ee4ac1056289f2e67b75755388549ada4ca tests: implement BIP341 test vectors (Pieter Wuille)
ac3037df1196b1d95ade2dfad4699ad3a6074903 tests: BIP341 test vector generation (Pieter Wuille)
ca83ffc2ea5fe08f16fff7df71c040d067f2afb0 tests: add deterministic signing mode to ECDSA (Pieter Wuille)
c98c53f20cadeda53f6a9323f72363593d174f68 tests: abstract out precomputed BIP341 signature hash elements (Pieter Wuille)
a5bde018b42cd38979fee71d870e0140b10c73d6 tests: give feature_taproot access to sighash preimages (Pieter Wuille)
51408250969e7ed171378369a995c90d4f813189 tests: add more fields to TaprootInfo (Pieter Wuille)
2478c6730a81dda3c56cb99087caf6abe49c85f5 Make signing follow BIP340 exactly w.r.t. aux randomness (Pieter Wuille)

Pull request description:

  This PR adds code to `test/functional/feature_taproot.py` which runs through a (deterministic) scenario covering several aspects of the wallet side of BIP341 (scriptPubKey computation from keys/scripts, control block computation, key path spending), with the ability to output test vectors in mediawiki format based on this scenario. The generated tests are then also included directly in `src/test/script_tests.cpp` and `src/test/script_standard_tests.cpp`.

  I intend to add these test vectors to BIP341 itself: https://github.com/bitcoin/bips/pull/1225

ACKs for top commit:
  laanwj:
    Code review ACK f1c33ee4ac1056289f2e67b75755388549ada4ca

Tree-SHA512: fcf7109539cb214d3190516b205cd32d2b1b452f14aa66f4107acfaa8bfc7d368f626857f1935665a4342eabc0b9ee8aba608a7c0a2494bec0b498e723439c9d

2 files changed, 75 insertions, 29 deletions

diff --git a/test/functional/test_framework/key.py b/test/functional/test_framework/key.py
index 26526e35fa..e5dea66963 100644
--- a/test/functional/test_framework/key.py
+++ b/test/functional/test_framework/key.py
@@ -8,6 +8,7 @@ keys, and is trivially vulnerable to side channel attacks. Do not use for
 anything but tests."""
 import csv
 import hashlib
+import hmac
 import os
 import random
 import unittest
@@ -326,6 +327,16 @@ def generate_privkey():
     """Generate a valid random 32-byte private key."""
     return random.randrange(1, SECP256K1_ORDER).to_bytes(32, 'big')
 
+def rfc6979_nonce(key):
+    """Compute signing nonce using RFC6979."""
+    v = bytes([1] * 32)
+    k = bytes([0] * 32)
+    k = hmac.new(k, v + b"\x00" + key, 'sha256').digest()
+    v = hmac.new(k, v, 'sha256').digest()
+    k = hmac.new(k, v + b"\x01" + key, 'sha256').digest()
+    v = hmac.new(k, v, 'sha256').digest()
+    return hmac.new(k, v, 'sha256').digest()
+
 class ECKey():
     """A secp256k1 private key"""
 
@@ -368,15 +379,18 @@ class ECKey():
         ret.compressed = self.compressed
         return ret
 
-    def sign_ecdsa(self, msg, low_s=True):
+    def sign_ecdsa(self, msg, low_s=True, rfc6979=False):
         """Construct a DER-encoded ECDSA signature with this key.
 
         See https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm for the
         ECDSA signer algorithm."""
         assert(self.valid)
         z = int.from_bytes(msg, 'big')
-        # Note: no RFC6979, but a simple random nonce (some tests rely on distinct transactions for the same operation)
-        k = random.randrange(1, SECP256K1_ORDER)
+        # Note: no RFC6979 by default, but a simple random nonce (some tests rely on distinct transactions for the same operation)
+        if rfc6979:
+            k = int.from_bytes(rfc6979_nonce(self.secret.to_bytes(32, 'big') + msg), 'big')
+        else:
+            k = random.randrange(1, SECP256K1_ORDER)
         R = SECP256K1.affine(SECP256K1.mul([(SECP256K1_G, k)]))
         r = R[0] % SECP256K1_ORDER
         s = (modinv(k, SECP256K1_ORDER) * (z + self.secret * r)) % SECP256K1_ORDER
diff --git a/test/functional/test_framework/script.py b/test/functional/test_framework/script.py
index 3c9b8a6e69..de71e19251 100644
--- a/test/functional/test_framework/script.py
+++ b/test/functional/test_framework/script.py
@@ -619,16 +619,15 @@ def FindAndDelete(script, sig):
         r += script[last_sop_idx:]
     return CScript(r)
 
-def LegacySignatureHash(script, txTo, inIdx, hashtype):
-    """Consensus-correct SignatureHash
+def LegacySignatureMsg(script, txTo, inIdx, hashtype):
+    """Preimage of the signature hash, if it exists.
 
-    Returns (hash, err) to precisely match the consensus-critical behavior of
-    the SIGHASH_SINGLE bug. (inIdx is *not* checked for validity)
+    Returns either (None, err) to indicate error (which translates to sighash 1),
+    or (msg, None).
     """
-    HASH_ONE = b'\x01\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'
 
     if inIdx >= len(txTo.vin):
-        return (HASH_ONE, "inIdx %d out of range (%d)" % (inIdx, len(txTo.vin)))
+        return (None, "inIdx %d out of range (%d)" % (inIdx, len(txTo.vin)))
     txtmp = CTransaction(txTo)
 
     for txin in txtmp.vin:
@@ -645,7 +644,7 @@ def LegacySignatureHash(script, txTo, inIdx, hashtype):
     elif (hashtype & 0x1f) == SIGHASH_SINGLE:
         outIdx = inIdx
         if outIdx >= len(txtmp.vout):
-            return (HASH_ONE, "outIdx %d out of range (%d)" % (outIdx, len(txtmp.vout)))
+            return (None, "outIdx %d out of range (%d)" % (outIdx, len(txtmp.vout)))
 
         tmp = txtmp.vout[outIdx]
         txtmp.vout = []
@@ -665,15 +664,27 @@ def LegacySignatureHash(script, txTo, inIdx, hashtype):
     s = txtmp.serialize_without_witness()
     s += struct.pack(b"<I", hashtype)
 
-    hash = hash256(s)
+    return (s, None)
+
+def LegacySignatureHash(*args, **kwargs):
+    """Consensus-correct SignatureHash
+
+    Returns (hash, err) to precisely match the consensus-critical behavior of
+    the SIGHASH_SINGLE bug. (inIdx is *not* checked for validity)
+    """
 
-    return (hash, None)
+    HASH_ONE = b'\x01\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'
+    msg, err = LegacySignatureMsg(*args, **kwargs)
+    if msg is None:
+        return (HASH_ONE, err)
+    else:
+        return (hash256(msg), err)
 
 # TODO: Allow cached hashPrevouts/hashSequence/hashOutputs to be provided.
 # Performance optimization probably not necessary for python tests, however.
 # Note that this corresponds to sigversion == 1 in EvalScript, which is used
 # for version 0 witnesses.
-def SegwitV0SignatureHash(script, txTo, inIdx, hashtype, amount):
+def SegwitV0SignatureMsg(script, txTo, inIdx, hashtype, amount):
 
     hashPrevouts = 0
     hashSequence = 0
@@ -711,8 +722,10 @@ def SegwitV0SignatureHash(script, txTo, inIdx, hashtype, amount):
     ss += ser_uint256(hashOutputs)
     ss += struct.pack("<i", txTo.nLockTime)
     ss += struct.pack("<I", hashtype)
+    return ss
 
-    return hash256(ss)
+def SegwitV0SignatureHash(*args, **kwargs):
+    return hash256(SegwitV0SignatureMsg(*args, **kwargs))
 
 class TestFrameworkScript(unittest.TestCase):
     def test_bn2vch(self):
@@ -742,7 +755,22 @@ class TestFrameworkScript(unittest.TestCase):
         for value in values:
             self.assertEqual(CScriptNum.decode(CScriptNum.encode(CScriptNum(value))), value)
 
-def TaprootSignatureHash(txTo, spent_utxos, hash_type, input_index = 0, scriptpath = False, script = CScript(), codeseparator_pos = -1, annex = None, leaf_ver = LEAF_VERSION_TAPSCRIPT):
+def BIP341_sha_prevouts(txTo):
+    return sha256(b"".join(i.prevout.serialize() for i in txTo.vin))
+
+def BIP341_sha_amounts(spent_utxos):
+    return sha256(b"".join(struct.pack("<q", u.nValue) for u in spent_utxos))
+
+def BIP341_sha_scriptpubkeys(spent_utxos):
+    return sha256(b"".join(ser_string(u.scriptPubKey) for u in spent_utxos))
+
+def BIP341_sha_sequences(txTo):
+    return sha256(b"".join(struct.pack("<I", i.nSequence) for i in txTo.vin))
+
+def BIP341_sha_outputs(txTo):
+    return sha256(b"".join(o.serialize() for o in txTo.vout))
+
+def TaprootSignatureMsg(txTo, spent_utxos, hash_type, input_index = 0, scriptpath = False, script = CScript(), codeseparator_pos = -1, annex = None, leaf_ver = LEAF_VERSION_TAPSCRIPT):
     assert (len(txTo.vin) == len(spent_utxos))
     assert (input_index < len(txTo.vin))
     out_type = SIGHASH_ALL if hash_type == 0 else hash_type & 3
@@ -752,12 +780,12 @@ def TaprootSignatureHash(txTo, spent_utxos, hash_type, input_index = 0, scriptpa
     ss += struct.pack("<i", txTo.nVersion)
     ss += struct.pack("<I", txTo.nLockTime)
     if in_type != SIGHASH_ANYONECANPAY:
-        ss += sha256(b"".join(i.prevout.serialize() for i in txTo.vin))
-        ss += sha256(b"".join(struct.pack("<q", u.nValue) for u in spent_utxos))
-        ss += sha256(b"".join(ser_string(u.scriptPubKey) for u in spent_utxos))
-        ss += sha256(b"".join(struct.pack("<I", i.nSequence) for i in txTo.vin))
+        ss += BIP341_sha_prevouts(txTo)
+        ss += BIP341_sha_amounts(spent_utxos)
+        ss += BIP341_sha_scriptpubkeys(spent_utxos)
+        ss += BIP341_sha_sequences(txTo)
     if out_type == SIGHASH_ALL:
-        ss += sha256(b"".join(o.serialize() for o in txTo.vout))
+        ss += BIP341_sha_outputs(txTo)
     spend_type = 0
     if annex is not None:
         spend_type |= 1
@@ -783,7 +811,10 @@ def TaprootSignatureHash(txTo, spent_utxos, hash_type, input_index = 0, scriptpa
         ss += bytes([0])
         ss += struct.pack("<i", codeseparator_pos)
     assert len(ss) ==  175 - (in_type == SIGHASH_ANYONECANPAY) * 49 - (out_type != SIGHASH_ALL and out_type != SIGHASH_SINGLE) * 32 + (annex is not None) * 32 + scriptpath * 37
-    return TaggedHash("TapSighash", ss)
+    return ss
+
+def TaprootSignatureHash(*args, **kwargs):
+    return TaggedHash("TapSighash", TaprootSignatureMsg(*args, **kwargs))
 
 def taproot_tree_helper(scripts):
     if len(scripts) == 0:
@@ -805,20 +836,20 @@ def taproot_tree_helper(scripts):
         h = TaggedHash("TapLeaf", bytes([version]) + ser_string(code))
         if name is None:
             return ([], h)
-        return ([(name, version, code, bytes())], h)
+        return ([(name, version, code, bytes(), h)], h)
     elif len(scripts) == 2 and callable(scripts[1]):
         # Two entries, and the right one is a function
         left, left_h = taproot_tree_helper(scripts[0:1])
         right_h = scripts[1](left_h)
-        left = [(name, version, script, control + right_h) for name, version, script, control in left]
+        left = [(name, version, script, control + right_h, leaf) for name, version, script, control, leaf in left]
         right = []
     else:
         # Two or more entries: descend into each side
         split_pos = len(scripts) // 2
         left, left_h = taproot_tree_helper(scripts[0:split_pos])
         right, right_h = taproot_tree_helper(scripts[split_pos:])
-        left = [(name, version, script, control + right_h) for name, version, script, control in left]
-        right = [(name, version, script, control + left_h) for name, version, script, control in right]
+        left = [(name, version, script, control + right_h, leaf) for name, version, script, control, leaf in left]
+        right = [(name, version, script, control + left_h, leaf) for name, version, script, control, leaf in right]
     if right_h < left_h:
         right_h, left_h = left_h, right_h
     h = TaggedHash("TapBranch", left_h + right_h)
@@ -830,13 +861,14 @@ def taproot_tree_helper(scripts):
 # - negflag: whether the pubkey in the scriptPubKey was negated from internal_pubkey+tweak*G (bool).
 # - tweak: the tweak (32 bytes)
 # - leaves: a dict of name -> TaprootLeafInfo objects for all known leaves
-TaprootInfo = namedtuple("TaprootInfo", "scriptPubKey,internal_pubkey,negflag,tweak,leaves")
+# - merkle_root: the script tree's Merkle root, or bytes() if no leaves are present
+TaprootInfo = namedtuple("TaprootInfo", "scriptPubKey,internal_pubkey,negflag,tweak,leaves,merkle_root,output_pubkey")
 
 # A TaprootLeafInfo object has the following fields:
 # - script: the leaf script (CScript or bytes)
 # - version: the leaf version (0xc0 for BIP342 tapscript)
 # - merklebranch: the merkle branch to use for this leaf (32*N bytes)
-TaprootLeafInfo = namedtuple("TaprootLeafInfo", "script,version,merklebranch")
+TaprootLeafInfo = namedtuple("TaprootLeafInfo", "script,version,merklebranch,leaf_hash")
 
 def taproot_construct(pubkey, scripts=None):
     """Construct a tree of Taproot spending conditions
@@ -858,8 +890,8 @@ def taproot_construct(pubkey, scripts=None):
     ret, h = taproot_tree_helper(scripts)
     tweak = TaggedHash("TapTweak", pubkey + h)
     tweaked, negated = tweak_add_pubkey(pubkey, tweak)
-    leaves = dict((name, TaprootLeafInfo(script, version, merklebranch)) for name, version, script, merklebranch in ret)
-    return TaprootInfo(CScript([OP_1, tweaked]), pubkey, negated + 0, tweak, leaves)
+    leaves = dict((name, TaprootLeafInfo(script, version, merklebranch, leaf)) for name, version, script, merklebranch, leaf in ret)
+    return TaprootInfo(CScript([OP_1, tweaked]), pubkey, negated + 0, tweak, leaves, h, tweaked)
 
 def is_op_success(o):
     return o == 0x50 or o == 0x62 or o == 0x89 or o == 0x8a or o == 0x8d or o == 0x8e or (o >= 0x7e and o <= 0x81) or (o >= 0x83 and o <= 0x86) or (o >= 0x95 and o <= 0x99) or (o >= 0xbb and o <= 0xfe)