Merge #19953: Implement BIP 340-342 validation (Schnorr/taproot/tapscript)

0e2a5e448f426219a6464b9aaadcc715534114e6 tests: dumping and minimizing of script assets data (Pieter Wuille)
4567ba034c5ae6e6cc161360f7425c9e844738f0 tests: add generic qa-asset-based script verification unit test (Pieter Wuille)
f06e6d03452cf5e0b1a0863afb08c9e6d3ef452e tests: functional tests for Schnorr/Taproot/Tapscript (Pieter Wuille)
3c226639eb134314a0640d34e4ccb6148dbde22f tests: add BIP340 Schnorr signature support to test framework (Pieter Wuille)
206fb180ec6ee5f916afc6f574000d716daf79b7 --- [TAPROOT] Tests --- (Pieter Wuille)
d7ff237f2996a4c11fdf9399187c2d2b26bf9809 Activate Taproot/Tapscript on regtest (BIP 341, BIP 342) (Pieter Wuille)
e9a021d7e6a454d610a45cb9b3995f0d96a5fbb6 Make Taproot spends standard + policy limits (Pieter Wuille)
865d2c37e2e44678498b7f425b65e01b1e231cde --- [TAPROOT] Regtest activation and policy --- (Pieter Wuille)
72422ce396b8eba7b1a72c171c2f07dae691d1b5 Implement Tapscript script validation rules (BIP 342) (Johnson Lau)
330de894a9a48515d9a473448b6c67adc3d188be Use ScriptExecutionData to pass through annex hash (Pieter Wuille)
8bbed4b7acf4c76eaea8c0e10f3cbf6ba4e53809 Implement Taproot validation (BIP 341) (Pieter Wuille)
0664f5fe1f77f08d235aa3750b59428257b0b91d Support for Schnorr signatures and integration in SignatureCheckers (BIP 340) (Pieter Wuille)
5de246ca8159dcffaa4c136a60c8bfed2028e2ee Implement Taproot signature hashing (BIP 341) (Johnson Lau)
9eb590894f15ff40806039bfd32972fbc260e30d Add TaggedHash function (BIP 340) (Pieter Wuille)
450d2b23710ad296eede81339195376021ab5500 --- [TAPROOT] BIP340/341/342 consensus rules --- (Pieter Wuille)
5d62e3a68b6ea9bb03556ee1fbf5678f20be01a2 refactor: keep spent outputs in PrecomputedTransactionData (Pieter Wuille)
8bd2b4e78452ff69c08c37acf164a6b80e503f13 refactor: rename scriptPubKey in VerifyWitnessProgram to exec_script (Pieter Wuille)
107b57df9fa8b2d625d2b342dc77722282a6ae4c scripted-diff: put ECDSA in name of signature functions (Pieter Wuille)
f8c099e2207c90d758e7a659d6a55fa7ccb7ceaa --- [TAPROOT] Refactors --- (Pieter Wuille)

Pull request description:

  This is an implementation of the Schnorr/taproot consensus rules proposed by BIPs [340](https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki), [341](https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki), and [342](https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki).

  See the list of commits [below](https://github.com/bitcoin/bitcoin/pull/19953#issuecomment-691815830). No signing or wallet support of any kind is included, as testing is done entirely through the Python test framework.

  This is a successor to https://github.com/bitcoin/bitcoin/pull/17977 (see discussion following [this comment](https://github.com/bitcoin/bitcoin/pull/17977#issuecomment-682285983)), and will have further changes squashed/rebased. The history of this PR can be found in #19997.

ACKs for top commit:
  instagibbs:
    reACK https://github.com/bitcoin/bitcoin/pull/19953/commits/0e2a5e448f426219a6464b9aaadcc715534114e6
  benthecarman:
    reACK 0e2a5e4
  kallewoof:
    reACK 0e2a5e448f426219a6464b9aaadcc715534114e6
  jonasnick:
    ACK 0e2a5e448f426219a6464b9aaadcc715534114e6 almost only looked at bip340/libsecp related code
  jonatack:
    ACK 0e2a5e448f426219a6464b9aaadcc715534114e6 modulo the last four commits (tests) that I plan to finish reviewing tomorrow
  fjahr:
    reACK 0e2a5e448f426219a6464b9aaadcc715534114e6
  achow101:
    ACK 0e2a5e448f426219a6464b9aaadcc715534114e6

Tree-SHA512: 1b00314450a2938a22bccbb4e177230cf08bd365d72055f9d526891f334b364c997e260c10bc19ca78440b6767712c9feea7faad9a1045dd51a5b96f7ca8146e

4 files changed, 341 insertions, 20 deletions

diff --git a/test/functional/test_framework/bip340_test_vectors.csv b/test/functional/test_framework/bip340_test_vectors.csv
new file mode 100644
index 0000000000..e068322deb
--- /dev/null
+++ b/test/functional/test_framework/bip340_test_vectors.csv
@@ -0,0 +1,16 @@
+index,secret key,public key,aux_rand,message,signature,verification result,comment
+0,0000000000000000000000000000000000000000000000000000000000000003,F9308A019258C31049344F85F89D5229B531C845836F99B08601F113BCE036F9,0000000000000000000000000000000000000000000000000000000000000000,0000000000000000000000000000000000000000000000000000000000000000,E907831F80848D1069A5371B402410364BDF1C5F8307B0084C55F1CE2DCA821525F66A4A85EA8B71E482A74F382D2CE5EBEEE8FDB2172F477DF4900D310536C0,TRUE,
+1,B7E151628AED2A6ABF7158809CF4F3C762E7160F38B4DA56A784D9045190CFEF,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,0000000000000000000000000000000000000000000000000000000000000001,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,6896BD60EEAE296DB48A229FF71DFE071BDE413E6D43F917DC8DCF8C78DE33418906D11AC976ABCCB20B091292BFF4EA897EFCB639EA871CFA95F6DE339E4B0A,TRUE,
+2,C90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B14E5C9,DD308AFEC5777E13121FA72B9CC1B7CC0139715309B086C960E18FD969774EB8,C87AA53824B4D7AE2EB035A2B5BBBCCC080E76CDC6D1692C4B0B62D798E6D906,7E2D58D8B3BCDF1ABADEC7829054F90DDA9805AAB56C77333024B9D0A508B75C,5831AAEED7B44BB74E5EAB94BA9D4294C49BCF2A60728D8B4C200F50DD313C1BAB745879A5AD954A72C45A91C3A51D3C7ADEA98D82F8481E0E1E03674A6F3FB7,TRUE,
+3,0B432B2677937381AEF05BB02A66ECD012773062CF3FA2549E44F58ED2401710,25D1DFF95105F5253C4022F628A996AD3A0D95FBF21D468A1B33F8C160D8F517,FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF,FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF,7EB0509757E246F19449885651611CB965ECC1A187DD51B64FDA1EDC9637D5EC97582B9CB13DB3933705B32BA982AF5AF25FD78881EBB32771FC5922EFC66EA3,TRUE,test fails if msg is reduced modulo p or n
+4,,D69C3509BB99E412E68B0FE8544E72837DFA30746D8BE2AA65975F29D22DC7B9,,4DF3C3F68FCC83B27E9D42C90431A72499F17875C81A599B566C9889B9696703,00000000000000000000003B78CE563F89A0ED9414F5AA28AD0D96D6795F9C6376AFB1548AF603B3EB45C9F8207DEE1060CB71C04E80F593060B07D28308D7F4,TRUE,
+5,,EEFDEA4CDB677750A420FEE807EACF21EB9898AE79B9768766E4FAA04A2D4A34,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,6CFF5C3BA86C69EA4B7376F31A9BCB4F74C1976089B2D9963DA2E5543E17776969E89B4C5564D00349106B8497785DD7D1D713A8AE82B32FA79D5F7FC407D39B,FALSE,public key not on the curve
+6,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,FFF97BD5755EEEA420453A14355235D382F6472F8568A18B2F057A14602975563CC27944640AC607CD107AE10923D9EF7A73C643E166BE5EBEAFA34B1AC553E2,FALSE,has_even_y(R) is false
+7,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,1FA62E331EDBC21C394792D2AB1100A7B432B013DF3F6FF4F99FCB33E0E1515F28890B3EDB6E7189B630448B515CE4F8622A954CFE545735AAEA5134FCCDB2BD,FALSE,negated message
+8,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,6CFF5C3BA86C69EA4B7376F31A9BCB4F74C1976089B2D9963DA2E5543E177769961764B3AA9B2FFCB6EF947B6887A226E8D7C93E00C5ED0C1834FF0D0C2E6DA6,FALSE,negated s value
+9,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,0000000000000000000000000000000000000000000000000000000000000000123DDA8328AF9C23A94C1FEECFD123BA4FB73476F0D594DCB65C6425BD186051,FALSE,sG - eP is infinite. Test fails in single verification if has_even_y(inf) is defined as true and x(inf) as 0
+10,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,00000000000000000000000000000000000000000000000000000000000000017615FBAF5AE28864013C099742DEADB4DBA87F11AC6754F93780D5A1837CF197,FALSE,sG - eP is infinite. Test fails in single verification if has_even_y(inf) is defined as true and x(inf) as 1
+11,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,4A298DACAE57395A15D0795DDBFD1DCB564DA82B0F269BC70A74F8220429BA1D69E89B4C5564D00349106B8497785DD7D1D713A8AE82B32FA79D5F7FC407D39B,FALSE,sig[0:32] is not an X coordinate on the curve
+12,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F69E89B4C5564D00349106B8497785DD7D1D713A8AE82B32FA79D5F7FC407D39B,FALSE,sig[0:32] is equal to field size
+13,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,6CFF5C3BA86C69EA4B7376F31A9BCB4F74C1976089B2D9963DA2E5543E177769FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141,FALSE,sig[32:64] is equal to curve order
+14,,FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC30,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,6CFF5C3BA86C69EA4B7376F31A9BCB4F74C1976089B2D9963DA2E5543E17776969E89B4C5564D00349106B8497785DD7D1D713A8AE82B32FA79D5F7FC407D39B,FALSE,public key is not a valid X coordinate because it exceeds the field size
diff --git a/test/functional/test_framework/blocktools.py b/test/functional/test_framework/blocktools.py
index afc1995009..4be8b7d80b 100644
--- a/test/functional/test_framework/blocktools.py
+++ b/test/functional/test_framework/blocktools.py
@@ -43,7 +43,9 @@ from .script import (
 from .util import assert_equal
 from io import BytesIO
 
+WITNESS_SCALE_FACTOR = 4
 MAX_BLOCK_SIGOPS = 20000
+MAX_BLOCK_SIGOPS_WEIGHT = MAX_BLOCK_SIGOPS * WITNESS_SCALE_FACTOR
 
 # Genesis block time (regtest)
 TIME_GENESIS_BLOCK = 1296688602
@@ -101,22 +103,31 @@ def script_BIP34_coinbase_height(height):
     return CScript([CScriptNum(height)])
 
 
-def create_coinbase(height, pubkey=None):
-    """Create a coinbase transaction, assuming no miner fees.
+def create_coinbase(height, pubkey=None, extra_output_script=None, fees=0):
+    """Create a coinbase transaction.
 
     If pubkey is passed in, the coinbase output will be a P2PK output;
-    otherwise an anyone-can-spend output."""
+    otherwise an anyone-can-spend output.
+
+    If extra_output_script is given, make a 0-value output to that
+    script. This is useful to pad block weight/sigops as needed. """
     coinbase = CTransaction()
     coinbase.vin.append(CTxIn(COutPoint(0, 0xffffffff), script_BIP34_coinbase_height(height), 0xffffffff))
     coinbaseoutput = CTxOut()
     coinbaseoutput.nValue = 50 * COIN
     halvings = int(height / 150)  # regtest
     coinbaseoutput.nValue >>= halvings
-    if (pubkey is not None):
+    coinbaseoutput.nValue += fees
+    if pubkey is not None:
         coinbaseoutput.scriptPubKey = CScript([pubkey, OP_CHECKSIG])
     else:
         coinbaseoutput.scriptPubKey = CScript([OP_TRUE])
     coinbase.vout = [coinbaseoutput]
+    if extra_output_script is not None:
+        coinbaseoutput2 = CTxOut()
+        coinbaseoutput2.nValue = 0
+        coinbaseoutput2.scriptPubKey = extra_output_script
+        coinbase.vout.append(coinbaseoutput2)
     coinbase.calc_sha256()
     return coinbase
 
diff --git a/test/functional/test_framework/key.py b/test/functional/test_framework/key.py
index adbffb7dc7..17b869e542 100644
--- a/test/functional/test_framework/key.py
+++ b/test/functional/test_framework/key.py
@@ -1,4 +1,4 @@
-# Copyright (c) 2019 Pieter Wuille
+# Copyright (c) 2019-2020 Pieter Wuille
 # Distributed under the MIT software license, see the accompanying
 # file COPYING or http://www.opensource.org/licenses/mit-license.php.
 """Test-only secp256k1 elliptic curve implementation
@@ -6,10 +6,24 @@
 WARNING: This code is slow, uses bad randomness, does not properly protect
 keys, and is trivially vulnerable to side channel attacks. Do not use for
 anything but tests."""
+import csv
+import hashlib
+import os
 import random
+import sys
+import unittest
 
 from .util import modinv
 
+def TaggedHash(tag, data):
+    ss = hashlib.sha256(tag.encode('utf-8')).digest()
+    ss += ss
+    ss += data
+    return hashlib.sha256(ss).digest()
+
+def xor_bytes(b0, b1):
+    return bytes(x ^ y for (x, y) in zip(b0, b1))
+
 def jacobi_symbol(n, k):
     """Compute the Jacobi symbol of n modulo k
 
@@ -68,6 +82,10 @@ class EllipticCurve:
         inv_3 = (inv_2 * inv) % self.p
         return ((inv_2 * x1) % self.p, (inv_3 * y1) % self.p, 1)
 
+    def has_even_y(self, p1):
+        """Whether the point p1 has an even Y coordinate when expressed in affine coordinates."""
+        return not (p1[2] == 0 or self.affine(p1)[1] & 1)
+
     def negate(self, p1):
         """Negate a Jacobian point tuple p1."""
         x1, y1, z1 = p1
@@ -86,13 +104,13 @@ class EllipticCurve:
         return jacobi_symbol(x_3 + self.a * x + self.b, self.p) != -1
 
     def lift_x(self, x):
-        """Given an X coordinate on the curve, return a corresponding affine point."""
+        """Given an X coordinate on the curve, return a corresponding affine point for which the Y coordinate is even."""
         x_3 = pow(x, 3, self.p)
         v = x_3 + self.a * x + self.b
         y = modsqrt(v, self.p)
         if y is None:
             return None
-        return (x, y, 1)
+        return (x, self.p - y if y & 1 else y, 1)
 
     def double(self, p1):
         """Double a Jacobian tuple p1
@@ -197,7 +215,8 @@ class EllipticCurve:
                     r = self.add(r, p)
         return r
 
-SECP256K1 = EllipticCurve(2**256 - 2**32 - 977, 0, 7)
+SECP256K1_FIELD_SIZE = 2**256 - 2**32 - 977
+SECP256K1 = EllipticCurve(SECP256K1_FIELD_SIZE, 0, 7)
 SECP256K1_G = (0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8, 1)
 SECP256K1_ORDER = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
 SECP256K1_ORDER_HALF = SECP256K1_ORDER // 2
@@ -223,7 +242,7 @@ class ECPubKey():
                 p = SECP256K1.lift_x(x)
                 # if the oddness of the y co-ord isn't correct, find the other
                 # valid y
-                if (p[1] & 1) != (data[0] & 1):
+                if data[0] & 1:
                     p = SECP256K1.negate(p)
                 self.p = p
                 self.valid = True
@@ -307,6 +326,10 @@ class ECPubKey():
             return False
         return True
 
+def generate_privkey():
+    """Generate a valid random 32-byte private key."""
+    return random.randrange(1, SECP256K1_ORDER).to_bytes(32, 'big')
+
 class ECKey():
     """A secp256k1 private key"""
 
@@ -324,7 +347,7 @@ class ECKey():
 
     def generate(self, compressed=True):
         """Generate a random private key (compressed or uncompressed)."""
-        self.set(random.randrange(1, SECP256K1_ORDER).to_bytes(32, 'big'), compressed)
+        self.set(generate_privkey(), compressed)
 
     def get_bytes(self):
         """Retrieve the 32-byte representation of this key."""
@@ -369,3 +392,161 @@ class ECKey():
         rb = r.to_bytes((r.bit_length() + 8) // 8, 'big')
         sb = s.to_bytes((s.bit_length() + 8) // 8, 'big')
         return b'\x30' + bytes([4 + len(rb) + len(sb), 2, len(rb)]) + rb + bytes([2, len(sb)]) + sb
+
+def compute_xonly_pubkey(key):
+    """Compute an x-only (32 byte) public key from a (32 byte) private key.
+
+    This also returns whether the resulting public key was negated.
+    """
+
+    assert len(key) == 32
+    x = int.from_bytes(key, 'big')
+    if x == 0 or x >= SECP256K1_ORDER:
+        return (None, None)
+    P = SECP256K1.affine(SECP256K1.mul([(SECP256K1_G, x)]))
+    return (P[0].to_bytes(32, 'big'), not SECP256K1.has_even_y(P))
+
+def tweak_add_privkey(key, tweak):
+    """Tweak a private key (after negating it if needed)."""
+
+    assert len(key) == 32
+    assert len(tweak) == 32
+
+    x = int.from_bytes(key, 'big')
+    if x == 0 or x >= SECP256K1_ORDER:
+        return None
+    if not SECP256K1.has_even_y(SECP256K1.mul([(SECP256K1_G, x)])):
+       x = SECP256K1_ORDER - x
+    t = int.from_bytes(tweak, 'big')
+    if t >= SECP256K1_ORDER:
+        return None
+    x = (x + t) % SECP256K1_ORDER
+    if x == 0:
+        return None
+    return x.to_bytes(32, 'big')
+
+def tweak_add_pubkey(key, tweak):
+    """Tweak a public key and return whether the result had to be negated."""
+
+    assert len(key) == 32
+    assert len(tweak) == 32
+
+    x_coord = int.from_bytes(key, 'big')
+    if x_coord >= SECP256K1_FIELD_SIZE:
+        return None
+    P = SECP256K1.lift_x(x_coord)
+    if P is None:
+        return None
+    t = int.from_bytes(tweak, 'big')
+    if t >= SECP256K1_ORDER:
+        return None
+    Q = SECP256K1.affine(SECP256K1.mul([(SECP256K1_G, t), (P, 1)]))
+    if Q is None:
+        return None
+    return (Q[0].to_bytes(32, 'big'), not SECP256K1.has_even_y(Q))
+
+def verify_schnorr(key, sig, msg):
+    """Verify a Schnorr signature (see BIP 340).
+
+    - key is a 32-byte xonly pubkey (computed using compute_xonly_pubkey).
+    - sig is a 64-byte Schnorr signature
+    - msg is a 32-byte message
+    """
+    assert len(key) == 32
+    assert len(msg) == 32
+    assert len(sig) == 64
+
+    x_coord = int.from_bytes(key, 'big')
+    if x_coord == 0 or x_coord >= SECP256K1_FIELD_SIZE:
+        return False
+    P = SECP256K1.lift_x(x_coord)
+    if P is None:
+        return False
+    r = int.from_bytes(sig[0:32], 'big')
+    if r >= SECP256K1_FIELD_SIZE:
+        return False
+    s = int.from_bytes(sig[32:64], 'big')
+    if s >= SECP256K1_ORDER:
+        return False
+    e = int.from_bytes(TaggedHash("BIP0340/challenge", sig[0:32] + key + msg), 'big') % SECP256K1_ORDER
+    R = SECP256K1.mul([(SECP256K1_G, s), (P, SECP256K1_ORDER - e)])
+    if not SECP256K1.has_even_y(R):
+        return False
+    if ((r * R[2] * R[2]) % SECP256K1_FIELD_SIZE) != R[0]:
+        return False
+    return True
+
+def sign_schnorr(key, msg, aux=None, flip_p=False, flip_r=False):
+    """Create a Schnorr signature (see BIP 340)."""
+
+    if aux is None:
+        aux = bytes(32)
+
+    assert len(key) == 32
+    assert len(msg) == 32
+    assert len(aux) == 32
+
+    sec = int.from_bytes(key, 'big')
+    if sec == 0 or sec >= SECP256K1_ORDER:
+        return None
+    P = SECP256K1.affine(SECP256K1.mul([(SECP256K1_G, sec)]))
+    if SECP256K1.has_even_y(P) == flip_p:
+        sec = SECP256K1_ORDER - sec
+    t = (sec ^ int.from_bytes(TaggedHash("BIP0340/aux", aux), 'big')).to_bytes(32, 'big')
+    kp = int.from_bytes(TaggedHash("BIP0340/nonce", t + P[0].to_bytes(32, 'big') + msg), 'big') % SECP256K1_ORDER
+    assert kp != 0
+    R = SECP256K1.affine(SECP256K1.mul([(SECP256K1_G, kp)]))
+    k = kp if SECP256K1.has_even_y(R) != flip_r else SECP256K1_ORDER - kp
+    e = int.from_bytes(TaggedHash("BIP0340/challenge", R[0].to_bytes(32, 'big') + P[0].to_bytes(32, 'big') + msg), 'big') % SECP256K1_ORDER
+    return R[0].to_bytes(32, 'big') + ((k + e * sec) % SECP256K1_ORDER).to_bytes(32, 'big')
+
+class TestFrameworkKey(unittest.TestCase):
+    def test_schnorr(self):
+        """Test the Python Schnorr implementation."""
+        byte_arrays = [generate_privkey() for _ in range(3)] + [v.to_bytes(32, 'big') for v in [0, SECP256K1_ORDER - 1, SECP256K1_ORDER, 2**256 - 1]]
+        keys = {}
+        for privkey in byte_arrays:  # build array of key/pubkey pairs
+            pubkey, _ = compute_xonly_pubkey(privkey)
+            if pubkey is not None:
+                keys[privkey] = pubkey
+        for msg in byte_arrays:  # test every combination of message, signing key, verification key
+            for sign_privkey, sign_pubkey in keys.items():
+                sig = sign_schnorr(sign_privkey, msg)
+                for verify_privkey, verify_pubkey in keys.items():
+                    if verify_privkey == sign_privkey:
+                        self.assertTrue(verify_schnorr(verify_pubkey, sig, msg))
+                        sig = list(sig)
+                        sig[random.randrange(64)] ^= (1 << (random.randrange(8)))  # damaging signature should break things
+                        sig = bytes(sig)
+                    self.assertFalse(verify_schnorr(verify_pubkey, sig, msg))
+
+    def test_schnorr_testvectors(self):
+        """Implement the BIP340 test vectors (read from bip340_test_vectors.csv)."""
+        num_tests = 0
+        with open(os.path.join(sys.path[0], 'test_framework', 'bip340_test_vectors.csv'), newline='', encoding='utf8') as csvfile:
+            reader = csv.reader(csvfile)
+            next(reader)
+            for row in reader:
+                (i_str, seckey_hex, pubkey_hex, aux_rand_hex, msg_hex, sig_hex, result_str, comment) = row
+                i = int(i_str)
+                pubkey = bytes.fromhex(pubkey_hex)
+                msg = bytes.fromhex(msg_hex)
+                sig = bytes.fromhex(sig_hex)
+                result = result_str == 'TRUE'
+                if seckey_hex != '':
+                    seckey = bytes.fromhex(seckey_hex)
+                    pubkey_actual = compute_xonly_pubkey(seckey)[0]
+                    self.assertEqual(pubkey.hex(), pubkey_actual.hex(), "BIP340 test vector %i (%s): pubkey mismatch" % (i, comment))
+                    aux_rand = bytes.fromhex(aux_rand_hex)
+                    try:
+                        sig_actual = sign_schnorr(seckey, msg, aux_rand)
+                        self.assertEqual(sig.hex(), sig_actual.hex(), "BIP340 test vector %i (%s): sig mismatch" % (i, comment))
+                    except RuntimeError as e:
+                        self.assertFalse("BIP340 test vector %i (%s): signing raised exception %s" % (i, comment, e))
+                result_actual = verify_schnorr(pubkey, sig, msg)
+                if result:
+                    self.assertEqual(result, result_actual, "BIP340 test vector %i (%s): verification failed" % (i, comment))
+                else:
+                    self.assertEqual(result, result_actual, "BIP340 test vector %i (%s): verification succeeded unexpectedly" % (i, comment))
+                num_tests += 1
+        self.assertTrue(num_tests >= 15) # expect at least 15 test vectors
diff --git a/test/functional/test_framework/script.py b/test/functional/test_framework/script.py
index 5e35ba0fce..8e5848d493 100644
--- a/test/functional/test_framework/script.py
+++ b/test/functional/test_framework/script.py
@@ -6,11 +6,15 @@
 
 This file is modified from python-bitcoinlib.
 """
+
+from collections import namedtuple
 import hashlib
 import struct
 import unittest
 from typing import List, Dict
 
+from .key import TaggedHash, tweak_add_pubkey
+
 from .messages import (
     CTransaction,
     CTxOut,
@@ -22,8 +26,13 @@ from .messages import (
 )
 
 MAX_SCRIPT_ELEMENT_SIZE = 520
+LOCKTIME_THRESHOLD = 500000000
+ANNEX_TAG = 0x50
+
 OPCODE_NAMES = {}  # type: Dict[CScriptOp, str]
 
+LEAF_VERSION_TAPSCRIPT = 0xc0
+
 def hash160(s):
     return hashlib.new('ripemd160', sha256(s)).digest()
 
@@ -239,11 +248,8 @@ OP_NOP8 = CScriptOp(0xb7)
 OP_NOP9 = CScriptOp(0xb8)
 OP_NOP10 = CScriptOp(0xb9)
 
-# template matching params
-OP_SMALLINTEGER = CScriptOp(0xfa)
-OP_PUBKEYS = CScriptOp(0xfb)
-OP_PUBKEYHASH = CScriptOp(0xfd)
-OP_PUBKEY = CScriptOp(0xfe)
+# BIP 342 opcodes (Tapscript)
+OP_CHECKSIGADD = CScriptOp(0xba)
 
 OP_INVALIDOPCODE = CScriptOp(0xff)
 
@@ -359,10 +365,7 @@ OPCODE_NAMES.update({
     OP_NOP8: 'OP_NOP8',
     OP_NOP9: 'OP_NOP9',
     OP_NOP10: 'OP_NOP10',
-    OP_SMALLINTEGER: 'OP_SMALLINTEGER',
-    OP_PUBKEYS: 'OP_PUBKEYS',
-    OP_PUBKEYHASH: 'OP_PUBKEYHASH',
-    OP_PUBKEY: 'OP_PUBKEY',
+    OP_CHECKSIGADD: 'OP_CHECKSIGADD',
     OP_INVALIDOPCODE: 'OP_INVALIDOPCODE',
 })
 
@@ -593,6 +596,7 @@ class CScript(bytes):
         return n
 
 
+SIGHASH_DEFAULT = 0 # Taproot-only default, semantics same as SIGHASH_ALL
 SIGHASH_ALL = 1
 SIGHASH_NONE = 2
 SIGHASH_SINGLE = 3
@@ -615,7 +619,6 @@ def FindAndDelete(script, sig):
         r += script[last_sop_idx:]
     return CScript(r)
 
-
 def LegacySignatureHash(script, txTo, inIdx, hashtype):
     """Consensus-correct SignatureHash
 
@@ -738,3 +741,113 @@ class TestFrameworkScript(unittest.TestCase):
         values = [0, 1, -1, -2, 127, 128, -255, 256, (1 << 15) - 1, -(1 << 16), (1 << 24) - 1, (1 << 31), 1 - (1 << 32), 1 << 40, 1500, -1500]
         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):
+    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
+    in_type = hash_type & SIGHASH_ANYONECANPAY
+    spk = spent_utxos[input_index].scriptPubKey
+    ss = bytes([0, hash_type]) # epoch, hash_type
+    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))
+    if out_type == SIGHASH_ALL:
+        ss += sha256(b"".join(o.serialize() for o in txTo.vout))
+    spend_type = 0
+    if annex is not None:
+        spend_type |= 1
+    if (scriptpath):
+        spend_type |= 2
+    ss += bytes([spend_type])
+    if in_type == SIGHASH_ANYONECANPAY:
+        ss += txTo.vin[input_index].prevout.serialize()
+        ss += struct.pack("<q", spent_utxos[input_index].nValue)
+        ss += ser_string(spk)
+        ss += struct.pack("<I", txTo.vin[input_index].nSequence)
+    else:
+        ss += struct.pack("<I", input_index)
+    if (spend_type & 1):
+        ss += sha256(ser_string(annex))
+    if out_type == SIGHASH_SINGLE:
+        if input_index < len(txTo.vout):
+            ss += sha256(txTo.vout[input_index].serialize())
+        else:
+            ss += bytes(0 for _ in range(32))
+    if (scriptpath):
+        ss += TaggedHash("TapLeaf", bytes([leaf_ver]) + ser_string(script))
+        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)
+
+def taproot_tree_helper(scripts):
+    if len(scripts) == 0:
+        return ([], bytes(0 for _ in range(32)))
+    if len(scripts) == 1:
+        # One entry: treat as a leaf
+        script = scripts[0]
+        assert(not callable(script))
+        if isinstance(script, list):
+            return taproot_tree_helper(script)
+        assert(isinstance(script, tuple))
+        version = LEAF_VERSION_TAPSCRIPT
+        name = script[0]
+        code = script[1]
+        if len(script) == 3:
+            version = script[2]
+        assert version & 1 == 0
+        assert isinstance(code, bytes)
+        h = TaggedHash("TapLeaf", bytes([version]) + ser_string(code))
+        if name is None:
+            return ([], h)
+        return ([(name, version, code, bytes())], 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]
+        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]
+    if right_h < left_h:
+        right_h, left_h = left_h, right_h
+    h = TaggedHash("TapBranch", left_h + right_h)
+    return (left + right, h)
+
+TaprootInfo = namedtuple("TaprootInfo", "scriptPubKey,inner_pubkey,negflag,tweak,leaves")
+TaprootLeafInfo = namedtuple("TaprootLeafInfo", "script,version,merklebranch")
+
+def taproot_construct(pubkey, scripts=None):
+    """Construct a tree of Taproot spending conditions
+
+    pubkey: an ECPubKey object for the internal pubkey
+    scripts: a list of items; each item is either:
+             - a (name, CScript) tuple
+             - a (name, CScript, leaf version) tuple
+             - another list of items (with the same structure)
+             - a function, which specifies how to compute the hashing partner
+               in function of the hash of whatever it is combined with
+
+    Returns: script (sPK or redeemScript), tweak, {name:(script, leaf version, negation flag, innerkey, merklepath), ...}
+    """
+    if scripts is None:
+        scripts = []
+
+    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)
+
+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)