aboutsummaryrefslogtreecommitdiff
path: root/test
diff options
context:
space:
mode:
Diffstat (limited to 'test')
-rwxr-xr-xtest/functional/feature_taproot.py1458
-rwxr-xr-xtest/functional/p2p_segwit.py11
-rwxr-xr-xtest/functional/rpc_blockchain.py14
-rw-r--r--test/functional/test_framework/bip340_test_vectors.csv16
-rw-r--r--test/functional/test_framework/blocktools.py19
-rw-r--r--test/functional/test_framework/key.py193
-rw-r--r--test/functional/test_framework/script.py133
-rwxr-xr-xtest/functional/test_runner.py2
8 files changed, 1822 insertions, 24 deletions
diff --git a/test/functional/feature_taproot.py b/test/functional/feature_taproot.py
new file mode 100755
index 0000000000..7b534c1c2f
--- /dev/null
+++ b/test/functional/feature_taproot.py
@@ -0,0 +1,1458 @@
+#!/usr/bin/env python3
+# Copyright (c) 2019-2020 The Bitcoin Core developers
+# Distributed under the MIT software license, see the accompanying
+# file COPYING or http://www.opensource.org/licenses/mit-license.php.
+# Test Taproot softfork (BIPs 340-342)
+
+from test_framework.blocktools import (
+ create_coinbase,
+ create_block,
+ add_witness_commitment,
+ MAX_BLOCK_SIGOPS_WEIGHT,
+ WITNESS_SCALE_FACTOR,
+)
+from test_framework.messages import (
+ COutPoint,
+ CTransaction,
+ CTxIn,
+ CTxInWitness,
+ CTxOut,
+ ToHex,
+)
+from test_framework.script import (
+ ANNEX_TAG,
+ CScript,
+ CScriptNum,
+ CScriptOp,
+ LEAF_VERSION_TAPSCRIPT,
+ LegacySignatureHash,
+ LOCKTIME_THRESHOLD,
+ MAX_SCRIPT_ELEMENT_SIZE,
+ OP_0,
+ OP_1,
+ OP_2,
+ OP_3,
+ OP_4,
+ OP_5,
+ OP_6,
+ OP_7,
+ OP_8,
+ OP_9,
+ OP_10,
+ OP_11,
+ OP_12,
+ OP_16,
+ OP_2DROP,
+ OP_2DUP,
+ OP_CHECKMULTISIG,
+ OP_CHECKMULTISIGVERIFY,
+ OP_CHECKSIG,
+ OP_CHECKSIGADD,
+ OP_CHECKSIGVERIFY,
+ OP_CODESEPARATOR,
+ OP_DROP,
+ OP_DUP,
+ OP_ELSE,
+ OP_ENDIF,
+ OP_EQUAL,
+ OP_EQUALVERIFY,
+ OP_HASH160,
+ OP_IF,
+ OP_NOP,
+ OP_NOT,
+ OP_NOTIF,
+ OP_PUSHDATA1,
+ OP_RETURN,
+ OP_SWAP,
+ OP_VERIFY,
+ SIGHASH_DEFAULT,
+ SIGHASH_ALL,
+ SIGHASH_NONE,
+ SIGHASH_SINGLE,
+ SIGHASH_ANYONECANPAY,
+ SegwitV0SignatureHash,
+ TaprootSignatureHash,
+ is_op_success,
+ taproot_construct,
+)
+from test_framework.test_framework import BitcoinTestFramework
+from test_framework.util import assert_raises_rpc_error, assert_equal
+from test_framework.key import generate_privkey, compute_xonly_pubkey, sign_schnorr, tweak_add_privkey, ECKey
+from test_framework.address import (
+ hash160,
+ sha256,
+)
+from collections import OrderedDict, namedtuple
+from io import BytesIO
+import json
+import hashlib
+import os
+import random
+
+# === Framework for building spending transactions. ===
+#
+# The computation is represented as a "context" dict, whose entries store potentially-unevaluated expressions that
+# refer to lower-level ones. By overwriting these expression, many aspects - both high and low level - of the signing
+# process can be overridden.
+#
+# Specifically, a context object is a dict that maps names to compositions of:
+# - values
+# - lists of values
+# - callables which, when fed the context object as argument, produce any of these
+#
+# The DEFAULT_CONTEXT object specifies a standard signing process, with many overridable knobs.
+#
+# The get(ctx, name) function can evaluate a name, and cache its result in the context.
+# getter(name) can be used to construct a callable that evaluates name. For example:
+#
+# ctx1 = {**DEFAULT_CONTEXT, inputs=[getter("sign"), b'\x01']}
+#
+# creates a context where the script inputs are a signature plus the bytes 0x01.
+#
+# override(expr, name1=expr1, name2=expr2, ...) can be used to cause an expression to be evaluated in a selectively
+# modified context. For example:
+#
+# ctx2 = {**DEFAULT_CONTEXT, sighash=override(default_sighash, hashtype=SIGHASH_DEFAULT)}
+#
+# creates a context ctx2 where the sighash is modified to use hashtype=SIGHASH_DEFAULT. This differs from
+#
+# ctx3 = {**DEFAULT_CONTEXT, hashtype=SIGHASH_DEFAULT}
+#
+# in that ctx3 will globally use hashtype=SIGHASH_DEFAULT (including in the hashtype byte appended to the signature)
+# while ctx2 only uses the modified hashtype inside the sighash calculation.
+
+def deep_eval(ctx, expr):
+ """Recursively replace any callables c in expr (including inside lists) with c(ctx)."""
+ while callable(expr):
+ expr = expr(ctx)
+ if isinstance(expr, list):
+ expr = [deep_eval(ctx, x) for x in expr]
+ return expr
+
+# Data type to represent fully-evaluated expressions in a context dict (so we can avoid reevaluating them).
+Final = namedtuple("Final", "value")
+
+def get(ctx, name):
+ """Evaluate name in context ctx."""
+ assert name in ctx, "Missing '%s' in context" % name
+ expr = ctx[name]
+ if not isinstance(expr, Final):
+ # Evaluate and cache the result.
+ expr = Final(deep_eval(ctx, expr))
+ ctx[name] = expr
+ return expr.value
+
+def getter(name):
+ """Return a callable that evaluates name in its passed context."""
+ return lambda ctx: get(ctx, name)
+
+def override(expr, **kwargs):
+ """Return a callable that evaluates expr in a modified context."""
+ return lambda ctx: deep_eval({**ctx, **kwargs}, expr)
+
+# === Implementations for the various default expressions in DEFAULT_CONTEXT ===
+
+def default_hashtype(ctx):
+ """Default expression for "hashtype": SIGHASH_DEFAULT for taproot, SIGHASH_ALL otherwise."""
+ mode = get(ctx, "mode")
+ if mode == "taproot":
+ return SIGHASH_DEFAULT
+ else:
+ return SIGHASH_ALL
+
+def default_tapleaf(ctx):
+ """Default expression for "tapleaf": looking up leaf in tap[2]."""
+ return get(ctx, "tap").leaves[get(ctx, "leaf")]
+
+def default_script_taproot(ctx):
+ """Default expression for "script_taproot": tapleaf.script."""
+ return get(ctx, "tapleaf").script
+
+def default_leafversion(ctx):
+ """Default expression for "leafversion": tapleaf.version"""
+ return get(ctx, "tapleaf").version
+
+def default_negflag(ctx):
+ """Default expression for "negflag": tap.negflag."""
+ return get(ctx, "tap").negflag
+
+def default_pubkey_inner(ctx):
+ """Default expression for "pubkey_inner": tap.inner_pubkey."""
+ return get(ctx, "tap").inner_pubkey
+
+def default_merklebranch(ctx):
+ """Default expression for "merklebranch": tapleaf.merklebranch."""
+ return get(ctx, "tapleaf").merklebranch
+
+def default_controlblock(ctx):
+ """Default expression for "controlblock": combine leafversion, negflag, pubkey_inner, merklebranch."""
+ return bytes([get(ctx, "leafversion") + get(ctx, "negflag")]) + get(ctx, "pubkey_inner") + get(ctx, "merklebranch")
+
+def default_sighash(ctx):
+ """Default expression for "sighash": depending on mode, compute BIP341, BIP143, or legacy sighash."""
+ tx = get(ctx, "tx")
+ idx = get(ctx, "idx")
+ hashtype = get(ctx, "hashtype_actual")
+ mode = get(ctx, "mode")
+ if mode == "taproot":
+ # BIP341 signature hash
+ utxos = get(ctx, "utxos")
+ annex = get(ctx, "annex")
+ if get(ctx, "leaf") is not None:
+ codeseppos = get(ctx, "codeseppos")
+ leaf_ver = get(ctx, "leafversion")
+ script = get(ctx, "script_taproot")
+ return TaprootSignatureHash(tx, utxos, hashtype, idx, scriptpath=True, script=script, leaf_ver=leaf_ver, codeseparator_pos=codeseppos, annex=annex)
+ else:
+ return TaprootSignatureHash(tx, utxos, hashtype, idx, scriptpath=False, annex=annex)
+ elif mode == "witv0":
+ # BIP143 signature hash
+ scriptcode = get(ctx, "scriptcode")
+ utxos = get(ctx, "utxos")
+ return SegwitV0SignatureHash(scriptcode, tx, idx, hashtype, utxos[idx].nValue)
+ else:
+ # Pre-segwit signature hash
+ scriptcode = get(ctx, "scriptcode")
+ return LegacySignatureHash(scriptcode, tx, idx, hashtype)[0]
+
+def default_tweak(ctx):
+ """Default expression for "tweak": None if a leaf is specified, tap[0] otherwise."""
+ if get(ctx, "leaf") is None:
+ return get(ctx, "tap").tweak
+ return None
+
+def default_key_tweaked(ctx):
+ """Default expression for "key_tweaked": key if tweak is None, tweaked with it otherwise."""
+ key = get(ctx, "key")
+ tweak = get(ctx, "tweak")
+ if tweak is None:
+ return key
+ else:
+ return tweak_add_privkey(key, tweak)
+
+def default_signature(ctx):
+ """Default expression for "signature": BIP340 signature or ECDSA signature depending on mode."""
+ sighash = get(ctx, "sighash")
+ if get(ctx, "mode") == "taproot":
+ key = get(ctx, "key_tweaked")
+ flip_r = get(ctx, "flag_flip_r")
+ flip_p = get(ctx, "flag_flip_p")
+ return sign_schnorr(key, sighash, flip_r=flip_r, flip_p=flip_p)
+ else:
+ key = get(ctx, "key")
+ return key.sign_ecdsa(sighash)
+
+def default_hashtype_actual(ctx):
+ """Default expression for "hashtype_actual": hashtype, unless mismatching SIGHASH_SINGLE in taproot."""
+ hashtype = get(ctx, "hashtype")
+ mode = get(ctx, "mode")
+ if mode != "taproot":
+ return hashtype
+ idx = get(ctx, "idx")
+ tx = get(ctx, "tx")
+ if hashtype & 3 == SIGHASH_SINGLE and idx >= len(tx.vout):
+ return (hashtype & ~3) | SIGHASH_NONE
+ return hashtype
+
+def default_bytes_hashtype(ctx):
+ """Default expression for "bytes_hashtype": bytes([hashtype_actual]) if not 0, b"" otherwise."""
+ return bytes([x for x in [get(ctx, "hashtype_actual")] if x != 0])
+
+def default_sign(ctx):
+ """Default expression for "sign": concatenation of signature and bytes_hashtype."""
+ return get(ctx, "signature") + get(ctx, "bytes_hashtype")
+
+def default_inputs_keypath(ctx):
+ """Default expression for "inputs_keypath": a signature."""
+ return [get(ctx, "sign")]
+
+def default_witness_taproot(ctx):
+ """Default expression for "witness_taproot", consisting of inputs, script, control block, and annex as needed."""
+ annex = get(ctx, "annex")
+ suffix_annex = []
+ if annex is not None:
+ suffix_annex = [annex]
+ if get(ctx, "leaf") is None:
+ return get(ctx, "inputs_keypath") + suffix_annex
+ else:
+ return get(ctx, "inputs") + [bytes(get(ctx, "script_taproot")), get(ctx, "controlblock")] + suffix_annex
+
+def default_witness_witv0(ctx):
+ """Default expression for "witness_witv0", consisting of inputs and witness script, as needed."""
+ script = get(ctx, "script_witv0")
+ inputs = get(ctx, "inputs")
+ if script is None:
+ return inputs
+ else:
+ return inputs + [script]
+
+def default_witness(ctx):
+ """Default expression for "witness", delegating to "witness_taproot" or "witness_witv0" as needed."""
+ mode = get(ctx, "mode")
+ if mode == "taproot":
+ return get(ctx, "witness_taproot")
+ elif mode == "witv0":
+ return get(ctx, "witness_witv0")
+ else:
+ return []
+
+def default_scriptsig(ctx):
+ """Default expression for "scriptsig", consisting of inputs and redeemscript, as needed."""
+ scriptsig = []
+ mode = get(ctx, "mode")
+ if mode == "legacy":
+ scriptsig = get(ctx, "inputs")
+ redeemscript = get(ctx, "script_p2sh")
+ if redeemscript is not None:
+ scriptsig += [bytes(redeemscript)]
+ return scriptsig
+
+# The default context object.
+DEFAULT_CONTEXT = {
+ # == The main expressions to evaluate. Only override these for unusual or invalid spends. ==
+ # The overall witness stack, as a list of bytes objects.
+ "witness": default_witness,
+ # The overall scriptsig, as a list of CScript objects (to be concatenated) and bytes objects (to be pushed)
+ "scriptsig": default_scriptsig,
+
+ # == Expressions you'll generally only override for intentionally invalid spends. ==
+ # The witness stack for spending a taproot output.
+ "witness_taproot": default_witness_taproot,
+ # The witness stack for spending a P2WPKH/P2WSH output.
+ "witness_witv0": default_witness_witv0,
+ # The script inputs for a taproot key path spend.
+ "inputs_keypath": default_inputs_keypath,
+ # The actual hashtype to use (usually equal to hashtype, but in taproot SIGHASH_SINGLE is not always allowed).
+ "hashtype_actual": default_hashtype_actual,
+ # The bytes object for a full signature (including hashtype byte, if needed).
+ "bytes_hashtype": default_bytes_hashtype,
+ # A full script signature (bytes including hashtype, if needed)
+ "sign": default_sign,
+ # An ECDSA or Schnorr signature (excluding hashtype byte).
+ "signature": default_signature,
+ # The 32-byte tweaked key (equal to key for script path spends, or key+tweak for key path spends).
+ "key_tweaked": default_key_tweaked,
+ # The tweak to use (None for script path spends, the actual tweak for key path spends).
+ "tweak": default_tweak,
+ # The sighash value (32 bytes)
+ "sighash": default_sighash,
+ # The information about the chosen script path spend (TaprootLeafInfo object).
+ "tapleaf": default_tapleaf,
+ # The script to push, and include in the sighash, for a taproot script path spend.
+ "script_taproot": default_script_taproot,
+ # The inner pubkey for a taproot script path spend (32 bytes).
+ "pubkey_inner": default_pubkey_inner,
+ # The negation flag of the inner pubkey for a taproot script path spend.
+ "negflag": default_negflag,
+ # The leaf version to include in the sighash (this does not affect the one in the control block).
+ "leafversion": default_leafversion,
+ # The Merkle path to include in the control block for a script path spend.
+ "merklebranch": default_merklebranch,
+ # The control block to push for a taproot script path spend.
+ "controlblock": default_controlblock,
+ # Whether to produce signatures with invalid P sign (Schnorr signatures only).
+ "flag_flip_p": False,
+ # Whether to produce signatures with invalid R sign (Schnorr signatures only).
+ "flag_flip_r": False,
+
+ # == Parameters that can be changed without invalidating, but do have a default: ==
+ # The hashtype (as an integer).
+ "hashtype": default_hashtype,
+ # The annex (only when mode=="taproot").
+ "annex": None,
+ # The codeseparator position (only when mode=="taproot").
+ "codeseppos": -1,
+ # The redeemscript to add to the scriptSig (if P2SH; None implies not P2SH).
+ "script_p2sh": None,
+ # The script to add to the witness in (if P2WSH; None implies P2WPKH)
+ "script_witv0": None,
+ # The leaf to use in taproot spends (if script path spend; None implies key path spend).
+ "leaf": None,
+ # The input arguments to provide to the executed script
+ "inputs": [],
+
+ # == Parameters to be set before evaluation: ==
+ # - mode: what spending style to use ("taproot", "witv0", or "legacy").
+ # - key: the (untweaked) private key to sign with (ECKey object for ECDSA, 32 bytes for Schnorr).
+ # - tap: the TaprootInfo object (see taproot_construct; needed in mode=="taproot").
+ # - tx: the transaction to sign.
+ # - utxos: the UTXOs being spent (needed in mode=="witv0" and mode=="taproot").
+ # - idx: the input position being signed.
+ # - scriptcode: the scriptcode to include in legacy and witv0 sighashes.
+}
+
+def flatten(lst):
+ ret = []
+ for elem in lst:
+ if isinstance(elem, list):
+ ret += flatten(elem)
+ else:
+ ret.append(elem)
+ return ret
+
+def spend(tx, idx, utxos, **kwargs):
+ """Sign transaction input idx of tx, provided utxos is the list of outputs being spent.
+
+ Additional arguments may be provided that override any aspect of the signing process.
+ See DEFAULT_CONTEXT above for what can be overridden, and what must be provided.
+ """
+
+ ctx = {**DEFAULT_CONTEXT, "tx":tx, "idx":idx, "utxos":utxos, **kwargs}
+
+ def to_script(elem):
+ """If fed a CScript, return it; if fed bytes, return a CScript that pushes it."""
+ if isinstance(elem, CScript):
+ return elem
+ else:
+ return CScript([elem])
+
+ scriptsig_list = flatten(get(ctx, "scriptsig"))
+ scriptsig = CScript(b"".join(bytes(to_script(elem)) for elem in scriptsig_list))
+ witness_stack = flatten(get(ctx, "witness"))
+ return (scriptsig, witness_stack)
+
+
+# === Spender objects ===
+#
+# Each spender is a tuple of:
+# - A scriptPubKey which is to be spent from (CScript)
+# - A comment describing the test (string)
+# - Whether the spending (on itself) is expected to be standard (bool)
+# - A tx-signing lambda returning (scriptsig, witness_stack), taking as inputs:
+# - A transaction to sign (CTransaction)
+# - An input position (int)
+# - The spent UTXOs by this transaction (list of CTxOut)
+# - Whether to produce a valid spend (bool)
+# - A string with an expected error message for failure case if known
+# - The (pre-taproot) sigops weight consumed by a successful spend
+# - Whether this spend cannot fail
+# - Whether this test demands being placed in a txin with no corresponding txout (for testing SIGHASH_SINGLE behavior)
+
+Spender = namedtuple("Spender", "script,comment,is_standard,sat_function,err_msg,sigops_weight,no_fail,need_vin_vout_mismatch")
+
+def make_spender(comment, *, tap=None, witv0=False, script=None, pkh=None, p2sh=False, spk_mutate_pre_p2sh=None, failure=None, standard=True, err_msg=None, sigops_weight=0, need_vin_vout_mismatch=False, **kwargs):
+ """Helper for constructing Spender objects using the context signing framework.
+
+ * tap: a TaprootInfo object (see taproot_construct), for Taproot spends (cannot be combined with pkh, witv0, or script)
+ * witv0: boolean indicating the use of witness v0 spending (needs one of script or pkh)
+ * script: the actual script executed (for bare/P2WSH/P2SH spending)
+ * pkh: the public key for P2PKH or P2WPKH spending
+ * p2sh: whether the output is P2SH wrapper (this is supported even for Taproot, where it makes the output unencumbered)
+ * spk_mutate_pre_psh: a callable to be applied to the script (before potentially P2SH-wrapping it)
+ * failure: a dict of entries to override in the context when intentionally failing to spend (if None, no_fail will be set)
+ * standard: whether the (valid version of) spending is expected to be standard
+ * err_msg: a string with an expected error message for failure (or None, if not cared about)
+ * sigops_weight: the pre-taproot sigops weight consumed by a successful spend
+ """
+
+ conf = dict()
+
+ # Compute scriptPubKey and set useful defaults based on the inputs.
+ if witv0:
+ assert tap is None
+ conf["mode"] = "witv0"
+ if pkh is not None:
+ # P2WPKH
+ assert script is None
+ pubkeyhash = hash160(pkh)
+ spk = CScript([OP_0, pubkeyhash])
+ conf["scriptcode"] = CScript([OP_DUP, OP_HASH160, pubkeyhash, OP_EQUALVERIFY, OP_CHECKSIG])
+ conf["script_witv0"] = None
+ conf["inputs"] = [getter("sign"), pkh]
+ elif script is not None:
+ # P2WSH
+ spk = CScript([OP_0, sha256(script)])
+ conf["scriptcode"] = script
+ conf["script_witv0"] = script
+ else:
+ assert False
+ elif tap is None:
+ conf["mode"] = "legacy"
+ if pkh is not None:
+ # P2PKH
+ assert script is None
+ pubkeyhash = hash160(pkh)
+ spk = CScript([OP_DUP, OP_HASH160, pubkeyhash, OP_EQUALVERIFY, OP_CHECKSIG])
+ conf["scriptcode"] = spk
+ conf["inputs"] = [getter("sign"), pkh]
+ elif script is not None:
+ # bare
+ spk = script
+ conf["scriptcode"] = script
+ else:
+ assert False
+ else:
+ assert script is None
+ conf["mode"] = "taproot"
+ conf["tap"] = tap
+ spk = tap.scriptPubKey
+
+ if spk_mutate_pre_p2sh is not None:
+ spk = spk_mutate_pre_p2sh(spk)
+
+ if p2sh:
+ # P2SH wrapper can be combined with anything else
+ conf["script_p2sh"] = spk
+ spk = CScript([OP_HASH160, hash160(spk), OP_EQUAL])
+
+ conf = {**conf, **kwargs}
+
+ def sat_fn(tx, idx, utxos, valid):
+ if valid:
+ return spend(tx, idx, utxos, **conf)
+ else:
+ assert failure is not None
+ return spend(tx, idx, utxos, **{**conf, **failure})
+
+ return Spender(script=spk, comment=comment, is_standard=standard, sat_function=sat_fn, err_msg=err_msg, sigops_weight=sigops_weight, no_fail=failure is None, need_vin_vout_mismatch=need_vin_vout_mismatch)
+
+def add_spender(spenders, *args, **kwargs):
+ """Make a spender using make_spender, and add it to spenders."""
+ spenders.append(make_spender(*args, **kwargs))
+
+# === Helpers for the test ===
+
+def random_checksig_style(pubkey):
+ """Creates a random CHECKSIG* tapscript that would succeed with only the valid signature on witness stack."""
+ return bytes(CScript([pubkey, OP_CHECKSIG]))
+ opcode = random.choice([OP_CHECKSIG, OP_CHECKSIGVERIFY, OP_CHECKSIGADD])
+ if (opcode == OP_CHECKSIGVERIFY):
+ ret = CScript([pubkey, opcode, OP_1])
+ elif (opcode == OP_CHECKSIGADD):
+ num = random.choice([0, 0x7fffffff, -0x7fffffff])
+ ret = CScript([num, pubkey, opcode, num + 1, OP_EQUAL])
+ else:
+ ret = CScript([pubkey, opcode])
+ return bytes(ret)
+
+def random_bytes(n):
+ """Return a random bytes object of length n."""
+ return bytes(random.getrandbits(8) for i in range(n))
+
+def bitflipper(expr):
+ """Return a callable that evaluates expr and returns it with a random bitflip."""
+ def fn(ctx):
+ sub = deep_eval(ctx, expr)
+ assert isinstance(sub, bytes)
+ return (int.from_bytes(sub, 'little') ^ (1 << random.randrange(len(sub) * 8))).to_bytes(len(sub), 'little')
+ return fn
+
+def zero_appender(expr):
+ """Return a callable that evaluates expr and returns it with a zero added."""
+ return lambda ctx: deep_eval(ctx, expr) + b"\x00"
+
+def byte_popper(expr):
+ """Return a callable that evaluates expr and returns it with its last byte removed."""
+ return lambda ctx: deep_eval(ctx, expr)[:-1]
+
+# Expected error strings
+
+ERR_SIG_SIZE = {"err_msg": "Invalid Schnorr signature size"}
+ERR_SIG_HASHTYPE = {"err_msg": "Invalid Schnorr signature hash type"}
+ERR_SIG_SCHNORR = {"err_msg": "Invalid Schnorr signature"}
+ERR_OP_RETURN = {"err_msg": "OP_RETURN was encountered"}
+ERR_CONTROLBLOCK_SIZE = {"err_msg": "Invalid Taproot control block size"}
+ERR_WITNESS_PROGRAM_MISMATCH = {"err_msg": "Witness program hash mismatch"}
+ERR_PUSH_LIMIT = {"err_msg": "Push value size limit exceeded"}
+ERR_DISABLED_OPCODE = {"err_msg": "Attempted to use a disabled opcode"}
+ERR_TAPSCRIPT_CHECKMULTISIG = {"err_msg": "OP_CHECKMULTISIG(VERIFY) is not available in tapscript"}
+ERR_MINIMALIF = {"err_msg": "OP_IF/NOTIF argument must be minimal in tapscript"}
+ERR_UNKNOWN_PUBKEY = {"err_msg": "Public key is neither compressed or uncompressed"}
+ERR_STACK_SIZE = {"err_msg": "Stack size limit exceeded"}
+ERR_CLEANSTACK = {"err_msg": "Stack size must be exactly one after execution"}
+ERR_STACK_EMPTY = {"err_msg": "Operation not valid with the current stack size"}
+ERR_SIGOPS_RATIO = {"err_msg": "Too much signature validation relative to witness weight"}
+ERR_UNDECODABLE = {"err_msg": "Opcode missing or not understood"}
+ERR_NO_SUCCESS = {"err_msg": "Script evaluated without error but finished with a false/empty top stack element"}
+ERR_EMPTY_WITNESS = {"err_msg": "Witness program was passed an empty witness"}
+ERR_CHECKSIGVERIFY = {"err_msg": "Script failed an OP_CHECKSIGVERIFY operation"}
+
+VALID_SIGHASHES_ECDSA = [
+ SIGHASH_ALL,
+ SIGHASH_NONE,
+ SIGHASH_SINGLE,
+ SIGHASH_ANYONECANPAY + SIGHASH_ALL,
+ SIGHASH_ANYONECANPAY + SIGHASH_NONE,
+ SIGHASH_ANYONECANPAY + SIGHASH_SINGLE
+]
+
+VALID_SIGHASHES_TAPROOT = [SIGHASH_DEFAULT] + VALID_SIGHASHES_ECDSA
+
+VALID_SIGHASHES_TAPROOT_SINGLE = [
+ SIGHASH_SINGLE,
+ SIGHASH_ANYONECANPAY + SIGHASH_SINGLE
+]
+
+VALID_SIGHASHES_TAPROOT_NO_SINGLE = [h for h in VALID_SIGHASHES_TAPROOT if h not in VALID_SIGHASHES_TAPROOT_SINGLE]
+
+SIGHASH_BITFLIP = {"failure": {"sighash": bitflipper(default_sighash)}}
+SIG_POP_BYTE = {"failure": {"sign": byte_popper(default_sign)}}
+SINGLE_SIG = {"inputs": [getter("sign")]}
+SIG_ADD_ZERO = {"failure": {"sign": zero_appender(default_sign)}}
+
+DUST_LIMIT = 600
+MIN_FEE = 50000
+
+# === Actual test cases ===
+
+
+def spenders_taproot_active():
+ """Return a list of Spenders for testing post-Taproot activation behavior."""
+
+ secs = [generate_privkey() for _ in range(8)]
+ pubs = [compute_xonly_pubkey(sec)[0] for sec in secs]
+
+ spenders = []
+
+ # == Tests for BIP340 signature validation. ==
+ # These are primarily tested through the test vectors implemented in libsecp256k1, and in src/tests/key_tests.cpp.
+ # Some things are tested programmatically as well here.
+
+ tap = taproot_construct(pubs[0])
+ # Test with key with bit flipped.
+ add_spender(spenders, "sig/key", tap=tap, key=secs[0], failure={"key_tweaked": bitflipper(default_key_tweaked)}, **ERR_SIG_SCHNORR)
+ # Test with sighash with bit flipped.
+ add_spender(spenders, "sig/sighash", tap=tap, key=secs[0], failure={"sighash": bitflipper(default_sighash)}, **ERR_SIG_SCHNORR)
+ # Test with invalid R sign.
+ add_spender(spenders, "sig/flip_r", tap=tap, key=secs[0], failure={"flag_flip_r": True}, **ERR_SIG_SCHNORR)
+ # Test with invalid P sign.
+ add_spender(spenders, "sig/flip_p", tap=tap, key=secs[0], failure={"flag_flip_p": True}, **ERR_SIG_SCHNORR)
+ # Test with signature with bit flipped.
+ add_spender(spenders, "sig/bitflip", tap=tap, key=secs[0], failure={"signature": bitflipper(default_signature)}, **ERR_SIG_SCHNORR)
+
+ # == Tests for signature hashing ==
+
+ # Run all tests once with no annex, and once with a valid random annex.
+ for annex in [None, lambda _: bytes([ANNEX_TAG]) + random_bytes(random.randrange(0, 250))]:
+ # Non-empty annex is non-standard
+ no_annex = annex is None
+
+ # Sighash mutation tests (test all sighash combinations)
+ for hashtype in VALID_SIGHASHES_TAPROOT:
+ common = {"annex": annex, "hashtype": hashtype, "standard": no_annex}
+
+ # Pure pubkey
+ tap = taproot_construct(pubs[0])
+ add_spender(spenders, "sighash/purepk", tap=tap, key=secs[0], **common, **SIGHASH_BITFLIP, **ERR_SIG_SCHNORR)
+
+ # Pubkey/P2PK script combination
+ scripts = [("s0", CScript(random_checksig_style(pubs[1])))]
+ tap = taproot_construct(pubs[0], scripts)
+ add_spender(spenders, "sighash/keypath_hashtype_%x" % hashtype, tap=tap, key=secs[0], **common, **SIGHASH_BITFLIP, **ERR_SIG_SCHNORR)
+ add_spender(spenders, "sighash/scriptpath_hashtype_%x" % hashtype, tap=tap, leaf="s0", key=secs[1], **common, **SINGLE_SIG, **SIGHASH_BITFLIP, **ERR_SIG_SCHNORR)
+
+ # Test SIGHASH_SINGLE behavior in combination with mismatching outputs
+ if hashtype in VALID_SIGHASHES_TAPROOT_SINGLE:
+ add_spender(spenders, "sighash/keypath_hashtype_mis_%x" % hashtype, tap=tap, key=secs[0], annex=annex, standard=no_annex, hashtype_actual=random.choice(VALID_SIGHASHES_TAPROOT_NO_SINGLE), failure={"hashtype_actual": hashtype}, **ERR_SIG_HASHTYPE, need_vin_vout_mismatch=True)
+ add_spender(spenders, "sighash/scriptpath_hashtype_mis_%x" % hashtype, tap=tap, leaf="s0", key=secs[1], annex=annex, standard=no_annex, hashtype_actual=random.choice(VALID_SIGHASHES_TAPROOT_NO_SINGLE), **SINGLE_SIG, failure={"hashtype_actual": hashtype}, **ERR_SIG_HASHTYPE, need_vin_vout_mismatch=True)
+
+ # Test OP_CODESEPARATOR impact on sighashing.
+ hashtype = lambda _: random.choice(VALID_SIGHASHES_TAPROOT)
+ common = {"annex": annex, "hashtype": hashtype, "standard": no_annex}
+ scripts = [
+ ("pk_codesep", CScript(random_checksig_style(pubs[1]) + bytes([OP_CODESEPARATOR]))), # codesep after checksig
+ ("codesep_pk", CScript(bytes([OP_CODESEPARATOR]) + random_checksig_style(pubs[1]))), # codesep before checksig
+ ("branched_codesep", CScript([random_bytes(random.randrange(511)), OP_DROP, OP_IF, OP_CODESEPARATOR, pubs[0], OP_ELSE, OP_CODESEPARATOR, pubs[1], OP_ENDIF, OP_CHECKSIG])), # branch dependent codesep
+ ]
+ random.shuffle(scripts)
+ tap = taproot_construct(pubs[0], scripts)
+ add_spender(spenders, "sighash/pk_codesep", tap=tap, leaf="pk_codesep", key=secs[1], **common, **SINGLE_SIG, **SIGHASH_BITFLIP, **ERR_SIG_SCHNORR)
+ add_spender(spenders, "sighash/codesep_pk", tap=tap, leaf="codesep_pk", key=secs[1], codeseppos=0, **common, **SINGLE_SIG, **SIGHASH_BITFLIP, **ERR_SIG_SCHNORR)
+ add_spender(spenders, "sighash/branched_codesep/left", tap=tap, leaf="branched_codesep", key=secs[0], codeseppos=3, **common, inputs=[getter("sign"), b'\x01'], **SIGHASH_BITFLIP, **ERR_SIG_SCHNORR)
+ add_spender(spenders, "sighash/branched_codesep/right", tap=tap, leaf="branched_codesep", key=secs[1], codeseppos=6, **common, inputs=[getter("sign"), b''], **SIGHASH_BITFLIP, **ERR_SIG_SCHNORR)
+
+ # Reusing the scripts above, test that various features affect the sighash.
+ add_spender(spenders, "sighash/annex", tap=tap, leaf="pk_codesep", key=secs[1], hashtype=hashtype, standard=False, **SINGLE_SIG, annex=bytes([ANNEX_TAG]), failure={"sighash": override(default_sighash, annex=None)}, **ERR_SIG_SCHNORR)
+ add_spender(spenders, "sighash/script", tap=tap, leaf="pk_codesep", key=secs[1], **common, **SINGLE_SIG, failure={"sighash": override(default_sighash, script_taproot=tap.leaves["codesep_pk"].script)}, **ERR_SIG_SCHNORR)
+ add_spender(spenders, "sighash/leafver", tap=tap, leaf="pk_codesep", key=secs[1], **common, **SINGLE_SIG, failure={"sighash": override(default_sighash, leafversion=random.choice([x & 0xFE for x in range(0x100) if x & 0xFE != 0xC0]))}, **ERR_SIG_SCHNORR)
+ add_spender(spenders, "sighash/scriptpath", tap=tap, leaf="pk_codesep", key=secs[1], **common, **SINGLE_SIG, failure={"sighash": override(default_sighash, leaf=None)}, **ERR_SIG_SCHNORR)
+ add_spender(spenders, "sighash/keypath", tap=tap, key=secs[0], **common, failure={"sighash": override(default_sighash, leaf="pk_codesep")}, **ERR_SIG_SCHNORR)
+
+ # Test that invalid hashtypes don't work, both in key path and script path spends
+ hashtype = lambda _: random.choice(VALID_SIGHASHES_TAPROOT)
+ for invalid_hashtype in [x for x in range(0x100) if x not in VALID_SIGHASHES_TAPROOT]:
+ add_spender(spenders, "sighash/keypath_unk_hashtype_%x" % invalid_hashtype, tap=tap, key=secs[0], hashtype=hashtype, failure={"hashtype": invalid_hashtype}, **ERR_SIG_HASHTYPE)
+ add_spender(spenders, "sighash/scriptpath_unk_hashtype_%x" % invalid_hashtype, tap=tap, leaf="pk_codesep", key=secs[1], **SINGLE_SIG, hashtype=hashtype, failure={"hashtype": invalid_hashtype}, **ERR_SIG_HASHTYPE)
+
+ # Test that hashtype 0 cannot have a hashtype byte, and 1 must have one.
+ add_spender(spenders, "sighash/hashtype0_byte_keypath", tap=tap, key=secs[0], hashtype=SIGHASH_DEFAULT, failure={"bytes_hashtype": bytes([SIGHASH_DEFAULT])}, **ERR_SIG_HASHTYPE)
+ add_spender(spenders, "sighash/hashtype0_byte_scriptpath", tap=tap, leaf="pk_codesep", key=secs[1], **SINGLE_SIG, hashtype=SIGHASH_DEFAULT, failure={"bytes_hashtype": bytes([SIGHASH_DEFAULT])}, **ERR_SIG_HASHTYPE)
+ add_spender(spenders, "sighash/hashtype1_byte_keypath", tap=tap, key=secs[0], hashtype=SIGHASH_ALL, failure={"bytes_hashtype": b''}, **ERR_SIG_SCHNORR)
+ add_spender(spenders, "sighash/hashtype1_byte_scriptpath", tap=tap, leaf="pk_codesep", key=secs[1], **SINGLE_SIG, hashtype=SIGHASH_ALL, failure={"bytes_hashtype": b''}, **ERR_SIG_SCHNORR)
+ # Test that hashtype 0 and hashtype 1 cannot be transmuted into each other.
+ add_spender(spenders, "sighash/hashtype0to1_keypath", tap=tap, key=secs[0], hashtype=SIGHASH_DEFAULT, failure={"bytes_hashtype": bytes([SIGHASH_ALL])}, **ERR_SIG_SCHNORR)
+ add_spender(spenders, "sighash/hashtype0to1_scriptpath", tap=tap, leaf="pk_codesep", key=secs[1], **SINGLE_SIG, hashtype=SIGHASH_DEFAULT, failure={"bytes_hashtype": bytes([SIGHASH_ALL])}, **ERR_SIG_SCHNORR)
+ add_spender(spenders, "sighash/hashtype1to0_keypath", tap=tap, key=secs[0], hashtype=SIGHASH_ALL, failure={"bytes_hashtype": b''}, **ERR_SIG_SCHNORR)
+ add_spender(spenders, "sighash/hashtype1to0_scriptpath", tap=tap, leaf="pk_codesep", key=secs[1], **SINGLE_SIG, hashtype=SIGHASH_ALL, failure={"bytes_hashtype": b''}, **ERR_SIG_SCHNORR)
+
+ # Test aspects of signatures with unusual lengths
+ for hashtype in [SIGHASH_DEFAULT, random.choice(VALID_SIGHASHES_TAPROOT)]:
+ scripts = [
+ ("csv", CScript([pubs[2], OP_CHECKSIGVERIFY, OP_1])),
+ ("cs_pos", CScript([pubs[2], OP_CHECKSIG])),
+ ("csa_pos", CScript([OP_0, pubs[2], OP_CHECKSIGADD, OP_1, OP_EQUAL])),
+ ("cs_neg", CScript([pubs[2], OP_CHECKSIG, OP_NOT])),
+ ("csa_neg", CScript([OP_2, pubs[2], OP_CHECKSIGADD, OP_2, OP_EQUAL]))
+ ]
+ random.shuffle(scripts)
+ tap = taproot_construct(pubs[3], scripts)
+ # Empty signatures
+ add_spender(spenders, "siglen/empty_keypath", tap=tap, key=secs[3], hashtype=hashtype, failure={"sign": b""}, **ERR_SIG_SIZE)
+ add_spender(spenders, "siglen/empty_csv", tap=tap, key=secs[2], leaf="csv", hashtype=hashtype, **SINGLE_SIG, failure={"sign": b""}, **ERR_CHECKSIGVERIFY)
+ add_spender(spenders, "siglen/empty_cs", tap=tap, key=secs[2], leaf="cs_pos", hashtype=hashtype, **SINGLE_SIG, failure={"sign": b""}, **ERR_NO_SUCCESS)
+ add_spender(spenders, "siglen/empty_csa", tap=tap, key=secs[2], leaf="csa_pos", hashtype=hashtype, **SINGLE_SIG, failure={"sign": b""}, **ERR_NO_SUCCESS)
+ add_spender(spenders, "siglen/empty_cs_neg", tap=tap, key=secs[2], leaf="cs_neg", hashtype=hashtype, **SINGLE_SIG, sign=b"", failure={"sign": lambda _: random_bytes(random.randrange(1, 63))}, **ERR_SIG_SIZE)
+ add_spender(spenders, "siglen/empty_csa_neg", tap=tap, key=secs[2], leaf="csa_neg", hashtype=hashtype, **SINGLE_SIG, sign=b"", failure={"sign": lambda _: random_bytes(random.randrange(66, 100))}, **ERR_SIG_SIZE)
+ # Appending a zero byte to signatures invalidates them
+ add_spender(spenders, "siglen/padzero_keypath", tap=tap, key=secs[3], hashtype=hashtype, **SIG_ADD_ZERO, **(ERR_SIG_HASHTYPE if hashtype == SIGHASH_DEFAULT else ERR_SIG_SIZE))
+ add_spender(spenders, "siglen/padzero_csv", tap=tap, key=secs[2], leaf="csv", hashtype=hashtype, **SINGLE_SIG, **SIG_ADD_ZERO, **(ERR_SIG_HASHTYPE if hashtype == SIGHASH_DEFAULT else ERR_SIG_SIZE))
+ add_spender(spenders, "siglen/padzero_cs", tap=tap, key=secs[2], leaf="cs_pos", hashtype=hashtype, **SINGLE_SIG, **SIG_ADD_ZERO, **(ERR_SIG_HASHTYPE if hashtype == SIGHASH_DEFAULT else ERR_SIG_SIZE))
+ add_spender(spenders, "siglen/padzero_csa", tap=tap, key=secs[2], leaf="csa_pos", hashtype=hashtype, **SINGLE_SIG, **SIG_ADD_ZERO, **(ERR_SIG_HASHTYPE if hashtype == SIGHASH_DEFAULT else ERR_SIG_SIZE))
+ add_spender(spenders, "siglen/padzero_cs_neg", tap=tap, key=secs[2], leaf="cs_neg", hashtype=hashtype, **SINGLE_SIG, sign=b"", **SIG_ADD_ZERO, **(ERR_SIG_HASHTYPE if hashtype == SIGHASH_DEFAULT else ERR_SIG_SIZE))
+ add_spender(spenders, "siglen/padzero_csa_neg", tap=tap, key=secs[2], leaf="csa_neg", hashtype=hashtype, **SINGLE_SIG, sign=b"", **SIG_ADD_ZERO, **(ERR_SIG_HASHTYPE if hashtype == SIGHASH_DEFAULT else ERR_SIG_SIZE))
+ # Removing the last byte from signatures invalidates them
+ add_spender(spenders, "siglen/popbyte_keypath", tap=tap, key=secs[3], hashtype=hashtype, **SIG_POP_BYTE, **(ERR_SIG_SIZE if hashtype == SIGHASH_DEFAULT else ERR_SIG_SCHNORR))
+ add_spender(spenders, "siglen/popbyte_csv", tap=tap, key=secs[2], leaf="csv", hashtype=hashtype, **SINGLE_SIG, **SIG_POP_BYTE, **(ERR_SIG_SIZE if hashtype == SIGHASH_DEFAULT else ERR_SIG_SCHNORR))
+ add_spender(spenders, "siglen/popbyte_cs", tap=tap, key=secs[2], leaf="cs_pos", hashtype=hashtype, **SINGLE_SIG, **SIG_POP_BYTE, **(ERR_SIG_SIZE if hashtype == SIGHASH_DEFAULT else ERR_SIG_SCHNORR))
+ add_spender(spenders, "siglen/popbyte_csa", tap=tap, key=secs[2], leaf="csa_pos", hashtype=hashtype, **SINGLE_SIG, **SIG_POP_BYTE, **(ERR_SIG_SIZE if hashtype == SIGHASH_DEFAULT else ERR_SIG_SCHNORR))
+ add_spender(spenders, "siglen/popbyte_cs_neg", tap=tap, key=secs[2], leaf="cs_neg", hashtype=hashtype, **SINGLE_SIG, sign=b"", **SIG_POP_BYTE, **(ERR_SIG_SIZE if hashtype == SIGHASH_DEFAULT else ERR_SIG_SCHNORR))
+ add_spender(spenders, "siglen/popbyte_csa_neg", tap=tap, key=secs[2], leaf="csa_neg", hashtype=hashtype, **SINGLE_SIG, sign=b"", **SIG_POP_BYTE, **(ERR_SIG_SIZE if hashtype == SIGHASH_DEFAULT else ERR_SIG_SCHNORR))
+ # Verify that an invalid signature is not allowed, not even when the CHECKSIG* is expected to fail.
+ add_spender(spenders, "siglen/invalid_cs_neg", tap=tap, key=secs[2], leaf="cs_neg", hashtype=hashtype, **SINGLE_SIG, sign=b"", failure={"sign": default_sign, "sighash": bitflipper(default_sighash)}, **ERR_SIG_SCHNORR)
+ add_spender(spenders, "siglen/invalid_csa_neg", tap=tap, key=secs[2], leaf="csa_neg", hashtype=hashtype, **SINGLE_SIG, sign=b"", failure={"sign": default_sign, "sighash": bitflipper(default_sighash)}, **ERR_SIG_SCHNORR)
+
+ # == Test that BIP341 spending only applies to witness version 1, program length 32, no P2SH ==
+
+ for p2sh in [False, True]:
+ for witver in range(1, 17):
+ for witlen in [20, 31, 32, 33]:
+ def mutate(spk):
+ prog = spk[2:]
+ assert len(prog) == 32
+ if witlen < 32:
+ prog = prog[0:witlen]
+ elif witlen > 32:
+ prog += bytes([0 for _ in range(witlen - 32)])
+ return CScript([CScriptOp.encode_op_n(witver), prog])
+ scripts = [("s0", CScript([pubs[0], OP_CHECKSIG])), ("dummy", CScript([OP_RETURN]))]
+ tap = taproot_construct(pubs[1], scripts)
+ if not p2sh and witver == 1 and witlen == 32:
+ add_spender(spenders, "applic/keypath", p2sh=p2sh, spk_mutate_pre_p2sh=mutate, tap=tap, key=secs[1], **SIGHASH_BITFLIP, **ERR_SIG_SCHNORR)
+ add_spender(spenders, "applic/scriptpath", p2sh=p2sh, leaf="s0", spk_mutate_pre_p2sh=mutate, tap=tap, key=secs[0], **SINGLE_SIG, failure={"leaf": "dummy"}, **ERR_OP_RETURN)
+ else:
+ add_spender(spenders, "applic/keypath", p2sh=p2sh, spk_mutate_pre_p2sh=mutate, tap=tap, key=secs[1], standard=False)
+ add_spender(spenders, "applic/scriptpath", p2sh=p2sh, leaf="s0", spk_mutate_pre_p2sh=mutate, tap=tap, key=secs[0], **SINGLE_SIG, standard=False)
+
+ # == Test various aspects of BIP341 spending paths ==
+
+ # A set of functions that compute the hashing partner in a Merkle tree, designed to exercise
+ # edge cases. This relies on the taproot_construct feature that a lambda can be passed in
+ # instead of a subtree, to compute the partner to be hashed with.
+ PARTNER_MERKLE_FN = [
+ # Combine with itself
+ lambda h: h,
+ # Combine with hash 0
+ lambda h: bytes([0 for _ in range(32)]),
+ # Combine with hash 2^256-1
+ lambda h: bytes([0xff for _ in range(32)]),
+ # Combine with itself-1 (BE)
+ lambda h: (int.from_bytes(h, 'big') - 1).to_bytes(32, 'big'),
+ # Combine with itself+1 (BE)
+ lambda h: (int.from_bytes(h, 'big') + 1).to_bytes(32, 'big'),
+ # Combine with itself-1 (LE)
+ lambda h: (int.from_bytes(h, 'little') - 1).to_bytes(32, 'big'),
+ # Combine with itself+1 (LE)
+ lambda h: (int.from_bytes(h, 'little') + 1).to_bytes(32, 'little'),
+ # Combine with random bitflipped version of self.
+ lambda h: (int.from_bytes(h, 'little') ^ (1 << random.randrange(256))).to_bytes(32, 'little')
+ ]
+ # Start with a tree of that has depth 1 for "128deep" and depth 2 for "129deep".
+ scripts = [("128deep", CScript([pubs[0], OP_CHECKSIG])), [("129deep", CScript([pubs[0], OP_CHECKSIG])), random.choice(PARTNER_MERKLE_FN)]]
+ # Add 127 nodes on top of that tree, so that "128deep" and "129deep" end up at their designated depths.
+ for _ in range(127):
+ scripts = [scripts, random.choice(PARTNER_MERKLE_FN)]
+ tap = taproot_construct(pubs[0], scripts)
+ # Test that spends with a depth of 128 work, but 129 doesn't (even with a tree with weird Merkle branches in it).
+ add_spender(spenders, "spendpath/merklelimit", tap=tap, leaf="128deep", **SINGLE_SIG, key=secs[0], failure={"leaf": "129deep"}, **ERR_CONTROLBLOCK_SIZE)
+ # Test that flipping the negation bit invalidates spends.
+ add_spender(spenders, "spendpath/negflag", tap=tap, leaf="128deep", **SINGLE_SIG, key=secs[0], failure={"negflag": lambda ctx: 1 - default_negflag(ctx)}, **ERR_WITNESS_PROGRAM_MISMATCH)
+ # Test that bitflips in the Merkle branch invalidate it.
+ add_spender(spenders, "spendpath/bitflipmerkle", tap=tap, leaf="128deep", **SINGLE_SIG, key=secs[0], failure={"merklebranch": bitflipper(default_merklebranch)}, **ERR_WITNESS_PROGRAM_MISMATCH)
+ # Test that bitflips in the inner pubkey invalidate it.
+ add_spender(spenders, "spendpath/bitflippubkey", tap=tap, leaf="128deep", **SINGLE_SIG, key=secs[0], failure={"pubkey_inner": bitflipper(default_pubkey_inner)}, **ERR_WITNESS_PROGRAM_MISMATCH)
+ # Test that empty witnesses are invalid.
+ add_spender(spenders, "spendpath/emptywit", tap=tap, leaf="128deep", **SINGLE_SIG, key=secs[0], failure={"witness": []}, **ERR_EMPTY_WITNESS)
+ # Test that adding garbage to the control block invalidates it.
+ add_spender(spenders, "spendpath/padlongcontrol", tap=tap, leaf="128deep", **SINGLE_SIG, key=secs[0], failure={"controlblock": lambda ctx: default_controlblock(ctx) + random_bytes(random.randrange(1, 32))}, **ERR_CONTROLBLOCK_SIZE)
+ # Test that truncating the control block invalidates it.
+ add_spender(spenders, "spendpath/trunclongcontrol", tap=tap, leaf="128deep", **SINGLE_SIG, key=secs[0], failure={"controlblock": lambda ctx: default_merklebranch(ctx)[0:random.randrange(1, 32)]}, **ERR_CONTROLBLOCK_SIZE)
+
+ scripts = [("s", CScript([pubs[0], OP_CHECKSIG]))]
+ tap = taproot_construct(pubs[1], scripts)
+ # Test that adding garbage to the control block invalidates it.
+ add_spender(spenders, "spendpath/padshortcontrol", tap=tap, leaf="s", **SINGLE_SIG, key=secs[0], failure={"controlblock": lambda ctx: default_controlblock(ctx) + random_bytes(random.randrange(1, 32))}, **ERR_CONTROLBLOCK_SIZE)
+ # Test that truncating the control block invalidates it.
+ add_spender(spenders, "spendpath/truncshortcontrol", tap=tap, leaf="s", **SINGLE_SIG, key=secs[0], failure={"controlblock": lambda ctx: default_merklebranch(ctx)[0:random.randrange(1, 32)]}, **ERR_CONTROLBLOCK_SIZE)
+ # Test that truncating the control block to 1 byte ("-1 Merkle length") invalidates it
+ add_spender(spenders, "spendpath/trunc1shortcontrol", tap=tap, leaf="s", **SINGLE_SIG, key=secs[0], failure={"controlblock": lambda ctx: default_merklebranch(ctx)[0:1]}, **ERR_CONTROLBLOCK_SIZE)
+
+ # == Test BIP342 edge cases ==
+
+ csa_low_val = random.randrange(0, 17) # Within range for OP_n
+ csa_low_result = csa_low_val + 1
+
+ csa_high_val = random.randrange(17, 100) if random.getrandbits(1) else random.randrange(-100, -1) # Outside OP_n range
+ csa_high_result = csa_high_val + 1
+
+ OVERSIZE_NUMBER = 2**31
+ assert_equal(len(CScriptNum.encode(CScriptNum(OVERSIZE_NUMBER))), 6)
+ assert_equal(len(CScriptNum.encode(CScriptNum(OVERSIZE_NUMBER-1))), 5)
+
+ big_choices = []
+ big_scriptops = []
+ for i in range(1000):
+ r = random.randrange(len(pubs))
+ big_choices.append(r)
+ big_scriptops += [pubs[r], OP_CHECKSIGVERIFY]
+
+
+ def big_spend_inputs(ctx):
+ """Helper function to construct the script input for t33/t34 below."""
+ # Instead of signing 999 times, precompute signatures for every (key, hashtype) combination
+ sigs = {}
+ for ht in VALID_SIGHASHES_TAPROOT:
+ for k in range(len(pubs)):
+ sigs[(k, ht)] = override(default_sign, hashtype=ht, key=secs[k])(ctx)
+ num = get(ctx, "num")
+ return [sigs[(big_choices[i], random.choice(VALID_SIGHASHES_TAPROOT))] for i in range(num - 1, -1, -1)]
+
+ # Various BIP342 features
+ scripts = [
+ # 0) drop stack element and OP_CHECKSIG
+ ("t0", CScript([OP_DROP, pubs[1], OP_CHECKSIG])),
+ # 1) normal OP_CHECKSIG
+ ("t1", CScript([pubs[1], OP_CHECKSIG])),
+ # 2) normal OP_CHECKSIGVERIFY
+ ("t2", CScript([pubs[1], OP_CHECKSIGVERIFY, OP_1])),
+ # 3) Hypothetical OP_CHECKMULTISIG script that takes a single sig as input
+ ("t3", CScript([OP_0, OP_SWAP, OP_1, pubs[1], OP_1, OP_CHECKMULTISIG])),
+ # 4) Hypothetical OP_CHECKMULTISIGVERIFY script that takes a single sig as input
+ ("t4", CScript([OP_0, OP_SWAP, OP_1, pubs[1], OP_1, OP_CHECKMULTISIGVERIFY, OP_1])),
+ # 5) OP_IF script that needs a true input
+ ("t5", CScript([OP_IF, pubs[1], OP_CHECKSIG, OP_ELSE, OP_RETURN, OP_ENDIF])),
+ # 6) OP_NOTIF script that needs a true input
+ ("t6", CScript([OP_NOTIF, OP_RETURN, OP_ELSE, pubs[1], OP_CHECKSIG, OP_ENDIF])),
+ # 7) OP_CHECKSIG with an empty key
+ ("t7", CScript([OP_0, OP_CHECKSIG])),
+ # 8) OP_CHECKSIGVERIFY with an empty key
+ ("t8", CScript([OP_0, OP_CHECKSIGVERIFY, OP_1])),
+ # 9) normal OP_CHECKSIGADD that also ensures return value is correct
+ ("t9", CScript([csa_low_val, pubs[1], OP_CHECKSIGADD, csa_low_result, OP_EQUAL])),
+ # 10) OP_CHECKSIGADD with empty key
+ ("t10", CScript([csa_low_val, OP_0, OP_CHECKSIGADD, csa_low_result, OP_EQUAL])),
+ # 11) OP_CHECKSIGADD with missing counter stack element
+ ("t11", CScript([pubs[1], OP_CHECKSIGADD, OP_1, OP_EQUAL])),
+ # 12) OP_CHECKSIG that needs invalid signature
+ ("t12", CScript([pubs[1], OP_CHECKSIGVERIFY, pubs[0], OP_CHECKSIG, OP_NOT])),
+ # 13) OP_CHECKSIG with empty key that needs invalid signature
+ ("t13", CScript([pubs[1], OP_CHECKSIGVERIFY, OP_0, OP_CHECKSIG, OP_NOT])),
+ # 14) OP_CHECKSIGADD that needs invalid signature
+ ("t14", CScript([pubs[1], OP_CHECKSIGVERIFY, OP_0, pubs[0], OP_CHECKSIGADD, OP_NOT])),
+ # 15) OP_CHECKSIGADD with empty key that needs invalid signature
+ ("t15", CScript([pubs[1], OP_CHECKSIGVERIFY, OP_0, OP_0, OP_CHECKSIGADD, OP_NOT])),
+ # 16) OP_CHECKSIG with unknown pubkey type
+ ("t16", CScript([OP_1, OP_CHECKSIG])),
+ # 17) OP_CHECKSIGADD with unknown pubkey type
+ ("t17", CScript([OP_0, OP_1, OP_CHECKSIGADD])),
+ # 18) OP_CHECKSIGVERIFY with unknown pubkey type
+ ("t18", CScript([OP_1, OP_CHECKSIGVERIFY, OP_1])),
+ # 19) script longer than 10000 bytes and over 201 non-push opcodes
+ ("t19", CScript([OP_0, OP_0, OP_2DROP] * 10001 + [pubs[1], OP_CHECKSIG])),
+ # 20) OP_CHECKSIGVERIFY with empty key
+ ("t20", CScript([pubs[1], OP_CHECKSIGVERIFY, OP_0, OP_0, OP_CHECKSIGVERIFY, OP_1])),
+ # 21) Script that grows the stack to 1000 elements
+ ("t21", CScript([pubs[1], OP_CHECKSIGVERIFY, OP_1] + [OP_DUP] * 999 + [OP_DROP] * 999)),
+ # 22) Script that grows the stack to 1001 elements
+ ("t22", CScript([pubs[1], OP_CHECKSIGVERIFY, OP_1] + [OP_DUP] * 1000 + [OP_DROP] * 1000)),
+ # 23) Script that expects an input stack of 1000 elements
+ ("t23", CScript([OP_DROP] * 999 + [pubs[1], OP_CHECKSIG])),
+ # 24) Script that expects an input stack of 1001 elements
+ ("t24", CScript([OP_DROP] * 1000 + [pubs[1], OP_CHECKSIG])),
+ # 25) Script that pushes a MAX_SCRIPT_ELEMENT_SIZE-bytes element
+ ("t25", CScript([random_bytes(MAX_SCRIPT_ELEMENT_SIZE), OP_DROP, pubs[1], OP_CHECKSIG])),
+ # 26) Script that pushes a (MAX_SCRIPT_ELEMENT_SIZE+1)-bytes element
+ ("t26", CScript([random_bytes(MAX_SCRIPT_ELEMENT_SIZE+1), OP_DROP, pubs[1], OP_CHECKSIG])),
+ # 27) CHECKSIGADD that must fail because numeric argument number is >4 bytes
+ ("t27", CScript([CScriptNum(OVERSIZE_NUMBER), pubs[1], OP_CHECKSIGADD])),
+ # 28) Pushes random CScriptNum value, checks OP_CHECKSIGADD result
+ ("t28", CScript([csa_high_val, pubs[1], OP_CHECKSIGADD, csa_high_result, OP_EQUAL])),
+ # 29) CHECKSIGADD that succeeds with proper sig because numeric argument number is <=4 bytes
+ ("t29", CScript([CScriptNum(OVERSIZE_NUMBER-1), pubs[1], OP_CHECKSIGADD])),
+ # 30) Variant of t1 with "normal" 33-byte pubkey
+ ("t30", CScript([b'\x03' + pubs[1], OP_CHECKSIG])),
+ # 31) Variant of t2 with "normal" 33-byte pubkey
+ ("t31", CScript([b'\x02' + pubs[1], OP_CHECKSIGVERIFY, OP_1])),
+ # 32) Variant of t28 with "normal" 33-byte pubkey
+ ("t32", CScript([csa_high_val, b'\x03' + pubs[1], OP_CHECKSIGADD, csa_high_result, OP_EQUAL])),
+ # 33) 999-of-999 multisig
+ ("t33", CScript(big_scriptops[:1998] + [OP_1])),
+ # 34) 1000-of-1000 multisig
+ ("t34", CScript(big_scriptops[:2000] + [OP_1])),
+ # 35) Variant of t9 that uses a non-minimally encoded input arg
+ ("t35", CScript([bytes([csa_low_val]), pubs[1], OP_CHECKSIGADD, csa_low_result, OP_EQUAL])),
+ # 36) Empty script
+ ("t36", CScript([])),
+ ]
+ # Add many dummies to test huge trees
+ for j in range(100000):
+ scripts.append((None, CScript([OP_RETURN, random.randrange(100000)])))
+ random.shuffle(scripts)
+ tap = taproot_construct(pubs[0], scripts)
+ common = {
+ "hashtype": hashtype,
+ "key": secs[1],
+ "tap": tap,
+ }
+ # Test that MAX_SCRIPT_ELEMENT_SIZE byte stack element inputs are valid, but not one more (and 80 bytes is standard but 81 is not).
+ add_spender(spenders, "tapscript/inputmaxlimit", leaf="t0", **common, standard=False, inputs=[getter("sign"), random_bytes(MAX_SCRIPT_ELEMENT_SIZE)], failure={"inputs": [getter("sign"), random_bytes(MAX_SCRIPT_ELEMENT_SIZE+1)]}, **ERR_PUSH_LIMIT)
+ add_spender(spenders, "tapscript/input80limit", leaf="t0", **common, inputs=[getter("sign"), random_bytes(80)])
+ add_spender(spenders, "tapscript/input81limit", leaf="t0", **common, standard=False, inputs=[getter("sign"), random_bytes(81)])
+ # Test that OP_CHECKMULTISIG and OP_CHECKMULTISIGVERIFY cause failure, but OP_CHECKSIG and OP_CHECKSIGVERIFY work.
+ add_spender(spenders, "tapscript/disabled_checkmultisig", leaf="t1", **common, **SINGLE_SIG, failure={"leaf": "t3"}, **ERR_TAPSCRIPT_CHECKMULTISIG)
+ add_spender(spenders, "tapscript/disabled_checkmultisigverify", leaf="t2", **common, **SINGLE_SIG, failure={"leaf": "t4"}, **ERR_TAPSCRIPT_CHECKMULTISIG)
+ # Test that OP_IF and OP_NOTIF do not accept non-0x01 as truth value (the MINIMALIF rule is consensus in Tapscript)
+ add_spender(spenders, "tapscript/minimalif", leaf="t5", **common, inputs=[getter("sign"), b'\x01'], failure={"inputs": [getter("sign"), b'\x02']}, **ERR_MINIMALIF)
+ add_spender(spenders, "tapscript/minimalnotif", leaf="t6", **common, inputs=[getter("sign"), b'\x01'], failure={"inputs": [getter("sign"), b'\x03']}, **ERR_MINIMALIF)
+ add_spender(spenders, "tapscript/minimalif", leaf="t5", **common, inputs=[getter("sign"), b'\x01'], failure={"inputs": [getter("sign"), b'\x0001']}, **ERR_MINIMALIF)
+ add_spender(spenders, "tapscript/minimalnotif", leaf="t6", **common, inputs=[getter("sign"), b'\x01'], failure={"inputs": [getter("sign"), b'\x0100']}, **ERR_MINIMALIF)
+ # Test that 1-byte public keys (which are unknown) are acceptable but nonstandard with unrelated signatures, but 0-byte public keys are not valid.
+ add_spender(spenders, "tapscript/unkpk/checksig", leaf="t16", standard=False, **common, **SINGLE_SIG, failure={"leaf": "t7"}, **ERR_UNKNOWN_PUBKEY)
+ add_spender(spenders, "tapscript/unkpk/checksigadd", leaf="t17", standard=False, **common, **SINGLE_SIG, failure={"leaf": "t10"}, **ERR_UNKNOWN_PUBKEY)
+ add_spender(spenders, "tapscript/unkpk/checksigverify", leaf="t18", standard=False, **common, **SINGLE_SIG, failure={"leaf": "t8"}, **ERR_UNKNOWN_PUBKEY)
+ # Test that 33-byte public keys (which are unknown) are acceptable but nonstandard with valid signatures, but normal pubkeys are not valid in that case.
+ add_spender(spenders, "tapscript/oldpk/checksig", leaf="t30", standard=False, **common, **SINGLE_SIG, sighash=bitflipper(default_sighash), failure={"leaf": "t1"}, **ERR_SIG_SCHNORR)
+ add_spender(spenders, "tapscript/oldpk/checksigadd", leaf="t31", standard=False, **common, **SINGLE_SIG, sighash=bitflipper(default_sighash), failure={"leaf": "t2"}, **ERR_SIG_SCHNORR)
+ add_spender(spenders, "tapscript/oldpk/checksigverify", leaf="t32", standard=False, **common, **SINGLE_SIG, sighash=bitflipper(default_sighash), failure={"leaf": "t28"}, **ERR_SIG_SCHNORR)
+ # Test that 0-byte public keys are not acceptable.
+ add_spender(spenders, "tapscript/emptypk/checksig", leaf="t1", **SINGLE_SIG, **common, failure={"leaf": "t7"}, **ERR_UNKNOWN_PUBKEY)
+ add_spender(spenders, "tapscript/emptypk/checksigverify", leaf="t2", **SINGLE_SIG, **common, failure={"leaf": "t8"}, **ERR_UNKNOWN_PUBKEY)
+ add_spender(spenders, "tapscript/emptypk/checksigadd", leaf="t9", **SINGLE_SIG, **common, failure={"leaf": "t10"}, **ERR_UNKNOWN_PUBKEY)
+ add_spender(spenders, "tapscript/emptypk/checksigadd", leaf="t35", standard=False, **SINGLE_SIG, **common, failure={"leaf": "t10"}, **ERR_UNKNOWN_PUBKEY)
+ # Test that OP_CHECKSIGADD results are as expected
+ add_spender(spenders, "tapscript/checksigaddresults", leaf="t28", **SINGLE_SIG, **common, failure={"leaf": "t27"}, err_msg="unknown error")
+ add_spender(spenders, "tapscript/checksigaddoversize", leaf="t29", **SINGLE_SIG, **common, failure={"leaf": "t27"}, err_msg="unknown error")
+ # Test that OP_CHECKSIGADD requires 3 stack elements.
+ add_spender(spenders, "tapscript/checksigadd3args", leaf="t9", **SINGLE_SIG, **common, failure={"leaf": "t11"}, **ERR_STACK_EMPTY)
+ # Test that empty signatures do not cause script failure in OP_CHECKSIG and OP_CHECKSIGADD (but do fail with empty pubkey, and do fail OP_CHECKSIGVERIFY)
+ add_spender(spenders, "tapscript/emptysigs/checksig", leaf="t12", **common, inputs=[b'', getter("sign")], failure={"leaf": "t13"}, **ERR_UNKNOWN_PUBKEY)
+ add_spender(spenders, "tapscript/emptysigs/nochecksigverify", leaf="t12", **common, inputs=[b'', getter("sign")], failure={"leaf": "t20"}, **ERR_UNKNOWN_PUBKEY)
+ add_spender(spenders, "tapscript/emptysigs/checksigadd", leaf="t14", **common, inputs=[b'', getter("sign")], failure={"leaf": "t15"}, **ERR_UNKNOWN_PUBKEY)
+ # Test that scripts over 10000 bytes (and over 201 non-push ops) are acceptable.
+ add_spender(spenders, "tapscript/no10000limit", leaf="t19", **SINGLE_SIG, **common)
+ # Test that a stack size of 1000 elements is permitted, but 1001 isn't.
+ add_spender(spenders, "tapscript/1000stack", leaf="t21", **SINGLE_SIG, **common, failure={"leaf": "t22"}, **ERR_STACK_SIZE)
+ # Test that an input stack size of 1000 elements is permitted, but 1001 isn't.
+ add_spender(spenders, "tapscript/1000inputs", leaf="t23", **common, inputs=[getter("sign")] + [b'' for _ in range(999)], failure={"leaf": "t24", "inputs": [getter("sign")] + [b'' for _ in range(1000)]}, **ERR_STACK_SIZE)
+ # Test that pushing a MAX_SCRIPT_ELEMENT_SIZE byte stack element is valid, but one longer is not.
+ add_spender(spenders, "tapscript/pushmaxlimit", leaf="t25", **common, **SINGLE_SIG, failure={"leaf": "t26"}, **ERR_PUSH_LIMIT)
+ # Test that 999-of-999 multisig works (but 1000-of-1000 triggers stack size limits)
+ add_spender(spenders, "tapscript/bigmulti", leaf="t33", **common, inputs=big_spend_inputs, num=999, failure={"leaf": "t34", "num": 1000}, **ERR_STACK_SIZE)
+ # Test that the CLEANSTACK rule is consensus critical in tapscript
+ add_spender(spenders, "tapscript/cleanstack", leaf="t36", tap=tap, inputs=[b'\x01'], failure={"inputs": [b'\x01', b'\x01']}, **ERR_CLEANSTACK)
+
+ # == Test for sigops ratio limit ==
+
+ # Given a number n, and a public key pk, functions that produce a (CScript, sigops). Each script takes as
+ # input a valid signature with the passed pk followed by a dummy push of bytes that are to be dropped, and
+ # will execute sigops signature checks.
+ SIGOPS_RATIO_SCRIPTS = [
+ # n OP_CHECKSIGVERFIYs and 1 OP_CHECKSIG.
+ lambda n, pk: (CScript([OP_DROP, pk] + [OP_2DUP, OP_CHECKSIGVERIFY] * n + [OP_CHECKSIG]), n + 1),
+ # n OP_CHECKSIGVERIFYs and 1 OP_CHECKSIGADD, but also one unexecuted OP_CHECKSIGVERIFY.
+ lambda n, pk: (CScript([OP_DROP, pk, OP_0, OP_IF, OP_2DUP, OP_CHECKSIGVERIFY, OP_ENDIF] + [OP_2DUP, OP_CHECKSIGVERIFY] * n + [OP_2, OP_SWAP, OP_CHECKSIGADD, OP_3, OP_EQUAL]), n + 1),
+ # n OP_CHECKSIGVERIFYs and 1 OP_CHECKSIGADD, but also one unexecuted OP_CHECKSIG.
+ lambda n, pk: (CScript([random_bytes(220), OP_2DROP, pk, OP_1, OP_NOTIF, OP_2DUP, OP_CHECKSIG, OP_VERIFY, OP_ENDIF] + [OP_2DUP, OP_CHECKSIGVERIFY] * n + [OP_4, OP_SWAP, OP_CHECKSIGADD, OP_5, OP_EQUAL]), n + 1),
+ # n OP_CHECKSIGVERFIYs and 1 OP_CHECKSIGADD, but also one unexecuted OP_CHECKSIGADD.
+ lambda n, pk: (CScript([OP_DROP, pk, OP_1, OP_IF, OP_ELSE, OP_2DUP, OP_6, OP_SWAP, OP_CHECKSIGADD, OP_7, OP_EQUALVERIFY, OP_ENDIF] + [OP_2DUP, OP_CHECKSIGVERIFY] * n + [OP_8, OP_SWAP, OP_CHECKSIGADD, OP_9, OP_EQUAL]), n + 1),
+ # n+1 OP_CHECKSIGs, but also one OP_CHECKSIG with an empty signature.
+ lambda n, pk: (CScript([OP_DROP, OP_0, pk, OP_CHECKSIG, OP_NOT, OP_VERIFY, pk] + [OP_2DUP, OP_CHECKSIG, OP_VERIFY] * n + [OP_CHECKSIG]), n + 1),
+ # n OP_CHECKSIGADDs and 1 OP_CHECKSIG, but also an OP_CHECKSIGADD with an empty signature.
+ lambda n, pk: (CScript([OP_DROP, OP_0, OP_10, pk, OP_CHECKSIGADD, OP_10, OP_EQUALVERIFY, pk] + [OP_2DUP, OP_16, OP_SWAP, OP_CHECKSIGADD, b'\x11', OP_EQUALVERIFY] * n + [OP_CHECKSIG]), n + 1),
+ ]
+ for annex in [None, bytes([ANNEX_TAG]) + random_bytes(random.randrange(1000))]:
+ for hashtype in [SIGHASH_DEFAULT, SIGHASH_ALL]:
+ for pubkey in [pubs[1], random_bytes(random.choice([x for x in range(2, 81) if x != 32]))]:
+ for fn_num, fn in enumerate(SIGOPS_RATIO_SCRIPTS):
+ merkledepth = random.randrange(129)
+
+
+ def predict_sigops_ratio(n, dummy_size):
+ """Predict whether spending fn(n, pubkey) with dummy_size will pass the ratio test."""
+ script, sigops = fn(n, pubkey)
+ # Predict the size of the witness for a given choice of n
+ stacklen_size = 1
+ sig_size = 64 + (hashtype != SIGHASH_DEFAULT)
+ siglen_size = 1
+ dummylen_size = 1 + 2 * (dummy_size >= 253)
+ script_size = len(script)
+ scriptlen_size = 1 + 2 * (script_size >= 253)
+ control_size = 33 + 32 * merkledepth
+ controllen_size = 1 + 2 * (control_size >= 253)
+ annex_size = 0 if annex is None else len(annex)
+ annexlen_size = 0 if annex is None else 1 + 2 * (annex_size >= 253)
+ witsize = stacklen_size + sig_size + siglen_size + dummy_size + dummylen_size + script_size + scriptlen_size + control_size + controllen_size + annex_size + annexlen_size
+ # sigops ratio test
+ return witsize + 50 >= 50 * sigops
+ # Make sure n is high enough that with empty dummy, the script is not valid
+ n = 0
+ while predict_sigops_ratio(n, 0):
+ n += 1
+ # But allow picking a bit higher still
+ n += random.randrange(5)
+ # Now pick dummy size *just* large enough that the overall construction passes
+ dummylen = 0
+ while not predict_sigops_ratio(n, dummylen):
+ dummylen += 1
+ scripts = [("s", fn(n, pubkey)[0])]
+ for _ in range(merkledepth):
+ scripts = [scripts, random.choice(PARTNER_MERKLE_FN)]
+ tap = taproot_construct(pubs[0], scripts)
+ standard = annex is None and dummylen <= 80 and len(pubkey) == 32
+ add_spender(spenders, "tapscript/sigopsratio_%i" % fn_num, tap=tap, leaf="s", annex=annex, hashtype=hashtype, key=secs[1], inputs=[getter("sign"), random_bytes(dummylen)], standard=standard, failure={"inputs": [getter("sign"), random_bytes(dummylen - 1)]}, **ERR_SIGOPS_RATIO)
+
+ # Future leaf versions
+ for leafver in range(0, 0x100, 2):
+ if leafver == LEAF_VERSION_TAPSCRIPT or leafver == ANNEX_TAG:
+ # Skip the defined LEAF_VERSION_TAPSCRIPT, and the ANNEX_TAG which is not usable as leaf version
+ continue
+ scripts = [
+ ("bare_c0", CScript([OP_NOP])),
+ ("bare_unkver", CScript([OP_NOP]), leafver),
+ ("return_c0", CScript([OP_RETURN])),
+ ("return_unkver", CScript([OP_RETURN]), leafver),
+ ("undecodable_c0", CScript([OP_PUSHDATA1])),
+ ("undecodable_unkver", CScript([OP_PUSHDATA1]), leafver),
+ ("bigpush_c0", CScript([random_bytes(MAX_SCRIPT_ELEMENT_SIZE+1), OP_DROP])),
+ ("bigpush_unkver", CScript([random_bytes(MAX_SCRIPT_ELEMENT_SIZE+1), OP_DROP]), leafver),
+ ("1001push_c0", CScript([OP_0] * 1001)),
+ ("1001push_unkver", CScript([OP_0] * 1001), leafver),
+ ]
+ random.shuffle(scripts)
+ tap = taproot_construct(pubs[0], scripts)
+ add_spender(spenders, "unkver/bare", standard=False, tap=tap, leaf="bare_unkver", failure={"leaf": "bare_c0"}, **ERR_CLEANSTACK)
+ add_spender(spenders, "unkver/return", standard=False, tap=tap, leaf="return_unkver", failure={"leaf": "return_c0"}, **ERR_OP_RETURN)
+ add_spender(spenders, "unkver/undecodable", standard=False, tap=tap, leaf="undecodable_unkver", failure={"leaf": "undecodable_c0"}, **ERR_UNDECODABLE)
+ add_spender(spenders, "unkver/bigpush", standard=False, tap=tap, leaf="bigpush_unkver", failure={"leaf": "bigpush_c0"}, **ERR_PUSH_LIMIT)
+ add_spender(spenders, "unkver/1001push", standard=False, tap=tap, leaf="1001push_unkver", failure={"leaf": "1001push_c0"}, **ERR_STACK_SIZE)
+ add_spender(spenders, "unkver/1001inputs", standard=False, tap=tap, leaf="bare_unkver", inputs=[b'']*1001, failure={"leaf": "bare_c0"}, **ERR_STACK_SIZE)
+
+ # OP_SUCCESSx tests.
+ hashtype = lambda _: random.choice(VALID_SIGHASHES_TAPROOT)
+ for opval in range(76, 0x100):
+ opcode = CScriptOp(opval)
+ if not is_op_success(opcode):
+ continue
+ scripts = [
+ ("bare_success", CScript([opcode])),
+ ("bare_nop", CScript([OP_NOP])),
+ ("unexecif_success", CScript([OP_0, OP_IF, opcode, OP_ENDIF])),
+ ("unexecif_nop", CScript([OP_0, OP_IF, OP_NOP, OP_ENDIF])),
+ ("return_success", CScript([OP_RETURN, opcode])),
+ ("return_nop", CScript([OP_RETURN, OP_NOP])),
+ ("undecodable_success", CScript([opcode, OP_PUSHDATA1])),
+ ("undecodable_nop", CScript([OP_NOP, OP_PUSHDATA1])),
+ ("undecodable_bypassed_success", CScript([OP_PUSHDATA1, OP_2, opcode])),
+ ("bigpush_success", CScript([random_bytes(MAX_SCRIPT_ELEMENT_SIZE+1), OP_DROP, opcode])),
+ ("bigpush_nop", CScript([random_bytes(MAX_SCRIPT_ELEMENT_SIZE+1), OP_DROP, OP_NOP])),
+ ("1001push_success", CScript([OP_0] * 1001 + [opcode])),
+ ("1001push_nop", CScript([OP_0] * 1001 + [OP_NOP])),
+ ]
+ random.shuffle(scripts)
+ tap = taproot_construct(pubs[0], scripts)
+ add_spender(spenders, "opsuccess/bare", standard=False, tap=tap, leaf="bare_success", failure={"leaf": "bare_nop"}, **ERR_CLEANSTACK)
+ add_spender(spenders, "opsuccess/unexecif", standard=False, tap=tap, leaf="unexecif_success", failure={"leaf": "unexecif_nop"}, **ERR_CLEANSTACK)
+ add_spender(spenders, "opsuccess/return", standard=False, tap=tap, leaf="return_success", failure={"leaf": "return_nop"}, **ERR_OP_RETURN)
+ add_spender(spenders, "opsuccess/undecodable", standard=False, tap=tap, leaf="undecodable_success", failure={"leaf": "undecodable_nop"}, **ERR_UNDECODABLE)
+ add_spender(spenders, "opsuccess/undecodable_bypass", standard=False, tap=tap, leaf="undecodable_success", failure={"leaf": "undecodable_bypassed_success"}, **ERR_UNDECODABLE)
+ add_spender(spenders, "opsuccess/bigpush", standard=False, tap=tap, leaf="bigpush_success", failure={"leaf": "bigpush_nop"}, **ERR_PUSH_LIMIT)
+ add_spender(spenders, "opsuccess/1001push", standard=False, tap=tap, leaf="1001push_success", failure={"leaf": "1001push_nop"}, **ERR_STACK_SIZE)
+ add_spender(spenders, "opsuccess/1001inputs", standard=False, tap=tap, leaf="bare_success", inputs=[b'']*1001, failure={"leaf": "bare_nop"}, **ERR_STACK_SIZE)
+
+ # Non-OP_SUCCESSx (verify that those aren't accidentally treated as OP_SUCCESSx)
+ for opval in range(0, 0x100):
+ opcode = CScriptOp(opval)
+ if is_op_success(opcode):
+ continue
+ scripts = [
+ ("normal", CScript([OP_RETURN, opcode] + [OP_NOP] * 75)),
+ ("op_success", CScript([OP_RETURN, CScriptOp(0x50)]))
+ ]
+ tap = taproot_construct(pubs[0], scripts)
+ add_spender(spenders, "alwaysvalid/notsuccessx", tap=tap, leaf="op_success", inputs=[], standard=False, failure={"leaf": "normal"}) # err_msg differs based on opcode
+
+ # == Legacy tests ==
+
+ # Also add a few legacy spends into the mix, so that transactions which combine taproot and pre-taproot spends get tested too.
+ for compressed in [False, True]:
+ eckey1 = ECKey()
+ eckey1.set(generate_privkey(), compressed)
+ pubkey1 = eckey1.get_pubkey().get_bytes()
+ eckey2 = ECKey()
+ eckey2.set(generate_privkey(), compressed)
+ for p2sh in [False, True]:
+ for witv0 in [False, True]:
+ for hashtype in VALID_SIGHASHES_ECDSA + [random.randrange(0x04, 0x80), random.randrange(0x84, 0x100)]:
+ standard = (hashtype in VALID_SIGHASHES_ECDSA) and (compressed or not witv0)
+ add_spender(spenders, "legacy/pk-wrongkey", hashtype=hashtype, p2sh=p2sh, witv0=witv0, standard=standard, script=CScript([pubkey1, OP_CHECKSIG]), **SINGLE_SIG, key=eckey1, failure={"key": eckey2}, sigops_weight=4-3*witv0, **ERR_NO_SUCCESS)
+ add_spender(spenders, "legacy/pkh-sighashflip", hashtype=hashtype, p2sh=p2sh, witv0=witv0, standard=standard, pkh=pubkey1, key=eckey1, **SIGHASH_BITFLIP, sigops_weight=4-3*witv0, **ERR_NO_SUCCESS)
+
+ # Verify that OP_CHECKSIGADD wasn't accidentally added to pre-taproot validation logic.
+ for p2sh in [False, True]:
+ for witv0 in [False, True]:
+ for hashtype in VALID_SIGHASHES_ECDSA + [random.randrange(0x04, 0x80), random.randrange(0x84, 0x100)]:
+ standard = hashtype in VALID_SIGHASHES_ECDSA and (p2sh or witv0)
+ add_spender(spenders, "compat/nocsa", hashtype=hashtype, p2sh=p2sh, witv0=witv0, standard=standard, script=CScript([OP_IF, OP_11, pubkey1, OP_CHECKSIGADD, OP_12, OP_EQUAL, OP_ELSE, pubkey1, OP_CHECKSIG, OP_ENDIF]), key=eckey1, sigops_weight=4-3*witv0, inputs=[getter("sign"), b''], failure={"inputs": [getter("sign"), b'\x01']}, **ERR_UNDECODABLE)
+
+ return spenders
+
+def spenders_taproot_inactive():
+ """Spenders for testing that pre-activation Taproot rules don't apply."""
+
+ spenders = []
+
+ sec = generate_privkey()
+ pub, _ = compute_xonly_pubkey(sec)
+ scripts = [
+ ("pk", CScript([pub, OP_CHECKSIG])),
+ ("future_leaf", CScript([pub, OP_CHECKSIG]), 0xc2),
+ ("op_success", CScript([pub, OP_CHECKSIG, OP_0, OP_IF, CScriptOp(0x50), OP_ENDIF])),
+ ]
+ tap = taproot_construct(pub, scripts)
+
+ # Test that keypath spending is valid & standard if compliant, but valid and nonstandard otherwise.
+ add_spender(spenders, "inactive/keypath_valid", key=sec, tap=tap)
+ add_spender(spenders, "inactive/keypath_invalidsig", key=sec, tap=tap, standard=False, sighash=bitflipper(default_sighash))
+ add_spender(spenders, "inactive/keypath_empty", key=sec, tap=tap, standard=False, witness=[])
+
+ # Same for scriptpath spending (but using future features like annex, leaf versions, or OP_SUCCESS is nonstandard).
+ add_spender(spenders, "inactive/scriptpath_valid", key=sec, tap=tap, leaf="pk", inputs=[getter("sign")])
+ add_spender(spenders, "inactive/scriptpath_invalidsig", key=sec, tap=tap, leaf="pk", standard=False, inputs=[getter("sign")], sighash=bitflipper(default_sighash))
+ add_spender(spenders, "inactive/scriptpath_invalidcb", key=sec, tap=tap, leaf="pk", standard=False, inputs=[getter("sign")], controlblock=bitflipper(default_controlblock))
+ add_spender(spenders, "inactive/scriptpath_valid_unkleaf", key=sec, tap=tap, leaf="future_leaf", standard=False, inputs=[getter("sign")])
+ add_spender(spenders, "inactive/scriptpath_invalid_unkleaf", key=sec, tap=tap, leaf="future_leaf", standard=False, inputs=[getter("sign")], sighash=bitflipper(default_sighash))
+ add_spender(spenders, "inactive/scriptpath_valid_opsuccess", key=sec, tap=tap, leaf="op_success", standard=False, inputs=[getter("sign")])
+ add_spender(spenders, "inactive/scriptpath_valid_opsuccess", key=sec, tap=tap, leaf="op_success", standard=False, inputs=[getter("sign")], sighash=bitflipper(default_sighash))
+
+ return spenders
+
+# Consensus validation flags to use in dumps for tests with "legacy/" or "inactive/" prefix.
+LEGACY_FLAGS = "P2SH,DERSIG,CHECKLOCKTIMEVERIFY,CHECKSEQUENCEVERIFY,WITNESS,NULLDUMMY"
+# Consensus validation flags to use in dumps for all other tests.
+TAPROOT_FLAGS = "P2SH,DERSIG,CHECKLOCKTIMEVERIFY,CHECKSEQUENCEVERIFY,WITNESS,NULLDUMMY,TAPROOT"
+
+def dump_json_test(tx, input_utxos, idx, success, failure):
+ spender = input_utxos[idx].spender
+ # Determine flags to dump
+ flags = LEGACY_FLAGS if spender.comment.startswith("legacy/") or spender.comment.startswith("inactive/") else TAPROOT_FLAGS
+
+ fields = [
+ ("tx", tx.serialize().hex()),
+ ("prevouts", [x.output.serialize().hex() for x in input_utxos]),
+ ("index", idx),
+ ("flags", flags),
+ ("comment", spender.comment)
+ ]
+
+ # The "final" field indicates that a spend should be always valid, even with more validation flags enabled
+ # than the listed ones. Use standardness as a proxy for this (which gives a conservative underestimate).
+ if spender.is_standard:
+ fields.append(("final", True))
+
+ def dump_witness(wit):
+ return OrderedDict([("scriptSig", wit[0].hex()), ("witness", [x.hex() for x in wit[1]])])
+ if success is not None:
+ fields.append(("success", dump_witness(success)))
+ if failure is not None:
+ fields.append(("failure", dump_witness(failure)))
+
+ # Write the dump to $TEST_DUMP_DIR/x/xyz... where x,y,z,... are the SHA1 sum of the dump (which makes the
+ # file naming scheme compatible with fuzzing infrastructure).
+ dump = json.dumps(OrderedDict(fields)) + ",\n"
+ sha1 = hashlib.sha1(dump.encode("utf-8")).hexdigest()
+ dirname = os.environ.get("TEST_DUMP_DIR", ".") + ("/%s" % sha1[0])
+ os.makedirs(dirname, exist_ok=True)
+ with open(dirname + ("/%s" % sha1), 'w', encoding="utf8") as f:
+ f.write(dump)
+
+# Data type to keep track of UTXOs, where they were created, and how to spend them.
+UTXOData = namedtuple('UTXOData', 'outpoint,output,spender')
+
+class TaprootTest(BitcoinTestFramework):
+ def add_options(self, parser):
+ parser.add_argument("--dumptests", dest="dump_tests", default=False, action="store_true",
+ help="Dump generated test cases to directory set by TEST_DUMP_DIR environment variable")
+
+ def skip_test_if_missing_module(self):
+ self.skip_if_no_wallet()
+
+ def set_test_params(self):
+ self.num_nodes = 2
+ self.setup_clean_chain = True
+ # Node 0 has Taproot inactive, Node 1 active.
+ self.extra_args = [["-whitelist=127.0.0.1", "-par=1", "-vbparams=taproot:1:1"], ["-whitelist=127.0.0.1", "-par=1"]]
+
+ def block_submit(self, node, txs, msg, err_msg, cb_pubkey=None, fees=0, sigops_weight=0, witness=False, accept=False):
+
+ # Deplete block of any non-tapscript sigops using a single additional 0-value coinbase output.
+ # It is not impossible to fit enough tapscript sigops to hit the old 80k limit without
+ # busting txin-level limits. We simply have to account for the p2pk outputs in all
+ # transactions.
+ extra_output_script = CScript([OP_CHECKSIG]*((MAX_BLOCK_SIGOPS_WEIGHT - sigops_weight) // WITNESS_SCALE_FACTOR))
+
+ block = create_block(self.tip, create_coinbase(self.lastblockheight + 1, pubkey=cb_pubkey, extra_output_script=extra_output_script, fees=fees), self.lastblocktime + 1)
+ block.nVersion = 4
+ for tx in txs:
+ tx.rehash()
+ block.vtx.append(tx)
+ block.hashMerkleRoot = block.calc_merkle_root()
+ witness and add_witness_commitment(block)
+ block.rehash()
+ block.solve()
+ block_response = node.submitblock(block.serialize(True).hex())
+ if err_msg is not None:
+ assert block_response is not None and err_msg in block_response, "Missing error message '%s' from block response '%s': %s" % (err_msg, "(None)" if block_response is None else block_response, msg)
+ if (accept):
+ assert node.getbestblockhash() == block.hash, "Failed to accept: %s (response: %s)" % (msg, block_response)
+ self.tip = block.sha256
+ self.lastblockhash = block.hash
+ self.lastblocktime += 1
+ self.lastblockheight += 1
+ else:
+ assert node.getbestblockhash() == self.lastblockhash, "Failed to reject: " + msg
+
+ def test_spenders(self, node, spenders, input_counts):
+ """Run randomized tests with a number of "spenders".
+
+ Steps:
+ 1) Generate an appropriate UTXO for each spender to test spend conditions
+ 2) Generate 100 random addresses of all wallet types: pkh/sh_wpkh/wpkh
+ 3) Select random number of inputs from (1)
+ 4) Select random number of addresses from (2) as outputs
+
+ Each spender embodies a test; in a large randomized test, it is verified
+ that toggling the valid argument to each lambda toggles the validity of
+ the transaction. This is accomplished by constructing transactions consisting
+ of all valid inputs, except one invalid one.
+ """
+
+ # Construct a bunch of sPKs that send coins back to the host wallet
+ self.log.info("- Constructing addresses for returning coins")
+ host_spks = []
+ host_pubkeys = []
+ for i in range(16):
+ addr = node.getnewaddress(address_type=random.choice(["legacy", "p2sh-segwit", "bech32"]))
+ info = node.getaddressinfo(addr)
+ spk = bytes.fromhex(info['scriptPubKey'])
+ host_spks.append(spk)
+ host_pubkeys.append(bytes.fromhex(info['pubkey']))
+
+ # Initialize variables used by block_submit().
+ self.lastblockhash = node.getbestblockhash()
+ self.tip = int(self.lastblockhash, 16)
+ block = node.getblock(self.lastblockhash)
+ self.lastblockheight = block['height']
+ self.lastblocktime = block['time']
+
+ # Create transactions spending up to 50 of the wallet's inputs, with one output for each spender, and
+ # one change output at the end. The transaction is constructed on the Python side to enable
+ # having multiple outputs to the same address and outputs with no assigned address. The wallet
+ # is then asked to sign it through signrawtransactionwithwallet, and then added to a block on the
+ # Python side (to bypass standardness rules).
+ self.log.info("- Creating test UTXOs...")
+ random.shuffle(spenders)
+ normal_utxos = []
+ mismatching_utxos = [] # UTXOs with input that requires mismatching output position
+ done = 0
+ while done < len(spenders):
+ # Compute how many UTXOs to create with this transaction
+ count_this_tx = min(len(spenders) - done, (len(spenders) + 4) // 5, 10000)
+
+ fund_tx = CTransaction()
+ # Add the 50 highest-value inputs
+ unspents = node.listunspent()
+ random.shuffle(unspents)
+ unspents.sort(key=lambda x: int(x["amount"] * 100000000), reverse=True)
+ if len(unspents) > 50:
+ unspents = unspents[:50]
+ random.shuffle(unspents)
+ balance = 0
+ for unspent in unspents:
+ balance += int(unspent["amount"] * 100000000)
+ txid = int(unspent["txid"], 16)
+ fund_tx.vin.append(CTxIn(COutPoint(txid, int(unspent["vout"])), CScript()))
+ # Add outputs
+ cur_progress = done / len(spenders)
+ next_progress = (done + count_this_tx) / len(spenders)
+ change_goal = (1.0 - 0.6 * next_progress) / (1.0 - 0.6 * cur_progress) * balance
+ self.log.debug("Create %i UTXOs in a transaction spending %i inputs worth %.8f (sending ~%.8f to change)" % (count_this_tx, len(unspents), balance * 0.00000001, change_goal * 0.00000001))
+ for i in range(count_this_tx):
+ avg = (balance - change_goal) / (count_this_tx - i)
+ amount = int(random.randrange(int(avg*0.85 + 0.5), int(avg*1.15 + 0.5)) + 0.5)
+ balance -= amount
+ fund_tx.vout.append(CTxOut(amount, spenders[done + i].script))
+ # Add change
+ fund_tx.vout.append(CTxOut(balance - 10000, random.choice(host_spks)))
+ # Ask the wallet to sign
+ ss = BytesIO(bytes.fromhex(node.signrawtransactionwithwallet(ToHex(fund_tx))["hex"]))
+ fund_tx.deserialize(ss)
+ # Construct UTXOData entries
+ fund_tx.rehash()
+ for i in range(count_this_tx):
+ utxodata = UTXOData(outpoint=COutPoint(fund_tx.sha256, i), output=fund_tx.vout[i], spender=spenders[done])
+ if utxodata.spender.need_vin_vout_mismatch:
+ mismatching_utxos.append(utxodata)
+ else:
+ normal_utxos.append(utxodata)
+ done += 1
+ # Mine into a block
+ self.block_submit(node, [fund_tx], "Funding tx", None, random.choice(host_pubkeys), 10000, MAX_BLOCK_SIGOPS_WEIGHT, True, True)
+
+ # Consume groups of choice(input_coins) from utxos in a tx, testing the spenders.
+ self.log.info("- Running %i spending tests" % done)
+ random.shuffle(normal_utxos)
+ random.shuffle(mismatching_utxos)
+ assert done == len(normal_utxos) + len(mismatching_utxos)
+
+ left = done
+ while left:
+ # Construct CTransaction with random nVersion, nLocktime
+ tx = CTransaction()
+ tx.nVersion = random.choice([1, 2, random.randint(-0x80000000, 0x7fffffff)])
+ min_sequence = (tx.nVersion != 1 and tx.nVersion != 0) * 0x80000000 # The minimum sequence number to disable relative locktime
+ if random.choice([True, False]):
+ tx.nLockTime = random.randrange(LOCKTIME_THRESHOLD, self.lastblocktime - 7200) # all absolute locktimes in the past
+ else:
+ tx.nLockTime = random.randrange(self.lastblockheight + 1) # all block heights in the past
+
+ # Decide how many UTXOs to test with.
+ acceptable = [n for n in input_counts if n <= left and (left - n > max(input_counts) or (left - n) in [0] + input_counts)]
+ num_inputs = random.choice(acceptable)
+
+ # If we have UTXOs that require mismatching inputs/outputs left, include exactly one of those
+ # unless there is only one normal UTXO left (as tests with mismatching UTXOs require at least one
+ # normal UTXO to go in the first position), and we don't want to run out of normal UTXOs.
+ input_utxos = []
+ while len(mismatching_utxos) and (len(input_utxos) == 0 or len(normal_utxos) == 1):
+ input_utxos.append(mismatching_utxos.pop())
+ left -= 1
+
+ # Top up until we hit num_inputs (but include at least one normal UTXO always).
+ for _ in range(max(1, num_inputs - len(input_utxos))):
+ input_utxos.append(normal_utxos.pop())
+ left -= 1
+
+ # The first input cannot require a mismatching output (as there is at least one output).
+ while True:
+ random.shuffle(input_utxos)
+ if not input_utxos[0].spender.need_vin_vout_mismatch:
+ break
+ first_mismatch_input = None
+ for i in range(len(input_utxos)):
+ if input_utxos[i].spender.need_vin_vout_mismatch:
+ first_mismatch_input = i
+ assert first_mismatch_input is None or first_mismatch_input > 0
+
+ # Decide fee, and add CTxIns to tx.
+ amount = sum(utxo.output.nValue for utxo in input_utxos)
+ fee = min(random.randrange(MIN_FEE * 2, MIN_FEE * 4), amount - DUST_LIMIT) # 10000-20000 sat fee
+ in_value = amount - fee
+ tx.vin = [CTxIn(outpoint=utxo.outpoint, nSequence=random.randint(min_sequence, 0xffffffff)) for utxo in input_utxos]
+ tx.wit.vtxinwit = [CTxInWitness() for _ in range(len(input_utxos))]
+ sigops_weight = sum(utxo.spender.sigops_weight for utxo in input_utxos)
+ self.log.debug("Test: %s" % (", ".join(utxo.spender.comment for utxo in input_utxos)))
+
+ # Add 1 to 4 random outputs (but constrained by inputs that require mismatching outputs)
+ num_outputs = random.choice(range(1, 1 + min(4, 4 if first_mismatch_input is None else first_mismatch_input)))
+ assert in_value >= 0 and fee - num_outputs * DUST_LIMIT >= MIN_FEE
+ for i in range(num_outputs):
+ tx.vout.append(CTxOut())
+ if in_value <= DUST_LIMIT:
+ tx.vout[-1].nValue = DUST_LIMIT
+ elif i < num_outputs - 1:
+ tx.vout[-1].nValue = in_value
+ else:
+ tx.vout[-1].nValue = random.randint(DUST_LIMIT, in_value)
+ in_value -= tx.vout[-1].nValue
+ tx.vout[-1].scriptPubKey = random.choice(host_spks)
+ sigops_weight += CScript(tx.vout[-1].scriptPubKey).GetSigOpCount(False) * WITNESS_SCALE_FACTOR
+ fee += in_value
+ assert fee >= 0
+
+ # Select coinbase pubkey
+ cb_pubkey = random.choice(host_pubkeys)
+ sigops_weight += 1 * WITNESS_SCALE_FACTOR
+
+ # Precompute one satisfying and one failing scriptSig/witness for each input.
+ input_data = []
+ for i in range(len(input_utxos)):
+ fn = input_utxos[i].spender.sat_function
+ fail = None
+ success = fn(tx, i, [utxo.output for utxo in input_utxos], True)
+ if not input_utxos[i].spender.no_fail:
+ fail = fn(tx, i, [utxo.output for utxo in input_utxos], False)
+ input_data.append((fail, success))
+ if self.options.dump_tests:
+ dump_json_test(tx, input_utxos, i, success, fail)
+
+ # Sign each input incorrectly once on each complete signing pass, except the very last.
+ for fail_input in list(range(len(input_utxos))) + [None]:
+ # Skip trying to fail at spending something that can't be made to fail.
+ if fail_input is not None and input_utxos[fail_input].spender.no_fail:
+ continue
+ # Expected message with each input failure, may be None(which is ignored)
+ expected_fail_msg = None if fail_input is None else input_utxos[fail_input].spender.err_msg
+ # Fill inputs/witnesses
+ for i in range(len(input_utxos)):
+ tx.vin[i].scriptSig = input_data[i][i != fail_input][0]
+ tx.wit.vtxinwit[i].scriptWitness.stack = input_data[i][i != fail_input][1]
+ # Submit to mempool to check standardness
+ is_standard_tx = fail_input is None and all(utxo.spender.is_standard for utxo in input_utxos) and tx.nVersion >= 1 and tx.nVersion <= 2
+ tx.rehash()
+ msg = ','.join(utxo.spender.comment + ("*" if n == fail_input else "") for n, utxo in enumerate(input_utxos))
+ if is_standard_tx:
+ node.sendrawtransaction(tx.serialize().hex(), 0)
+ assert node.getmempoolentry(tx.hash) is not None, "Failed to accept into mempool: " + msg
+ else:
+ assert_raises_rpc_error(-26, None, node.sendrawtransaction, tx.serialize().hex(), 0)
+ # Submit in a block
+ self.block_submit(node, [tx], msg, witness=True, accept=fail_input is None, cb_pubkey=cb_pubkey, fees=fee, sigops_weight=sigops_weight, err_msg=expected_fail_msg)
+
+ if (len(spenders) - left) // 200 > (len(spenders) - left - len(input_utxos)) // 200:
+ self.log.info(" - %i tests done" % (len(spenders) - left))
+
+ assert left == 0
+ assert len(normal_utxos) == 0
+ assert len(mismatching_utxos) == 0
+ self.log.info(" - Done")
+
+ def run_test(self):
+ self.connect_nodes(0, 1)
+
+ # Post-taproot activation tests go first (pre-taproot tests' blocks are invalid post-taproot).
+ self.log.info("Post-activation tests...")
+ self.nodes[1].generate(101)
+ self.test_spenders(self.nodes[1], spenders_taproot_active(), input_counts=[1, 2, 2, 2, 2, 3])
+
+ # Transfer % of funds to pre-taproot node.
+ addr = self.nodes[0].getnewaddress()
+ self.nodes[1].sendtoaddress(address=addr, amount=int(self.nodes[1].getbalance() * 70000000) / 100000000)
+ self.nodes[1].generate(1)
+ self.sync_blocks()
+
+ # Pre-taproot activation tests.
+ self.log.info("Pre-activation tests...")
+ self.test_spenders(self.nodes[0], spenders_taproot_inactive(), input_counts=[1, 2, 2, 2, 2, 3])
+
+
+if __name__ == '__main__':
+ TaprootTest().main()
diff --git a/test/functional/p2p_segwit.py b/test/functional/p2p_segwit.py
index d79ed449e5..29735b0fb3 100755
--- a/test/functional/p2p_segwit.py
+++ b/test/functional/p2p_segwit.py
@@ -55,6 +55,7 @@ from test_framework.script import (
MAX_SCRIPT_ELEMENT_SIZE,
OP_0,
OP_1,
+ OP_2,
OP_16,
OP_2DROP,
OP_CHECKMULTISIG,
@@ -1400,7 +1401,11 @@ class SegWitTest(BitcoinTestFramework):
assert_equal(len(self.nodes[1].getrawmempool()), 0)
for version in list(range(OP_1, OP_16 + 1)) + [OP_0]:
# First try to spend to a future version segwit script_pubkey.
- script_pubkey = CScript([CScriptOp(version), witness_hash])
+ if version == OP_1:
+ # Don't use 32-byte v1 witness (used by Taproot; see BIP 341)
+ script_pubkey = CScript([CScriptOp(version), witness_hash + b'\x00'])
+ else:
+ script_pubkey = CScript([CScriptOp(version), witness_hash])
tx.vin = [CTxIn(COutPoint(self.utxo[0].sha256, self.utxo[0].n), b"")]
tx.vout = [CTxOut(self.utxo[0].nValue - 1000, script_pubkey)]
tx.rehash()
@@ -1413,9 +1418,9 @@ class SegWitTest(BitcoinTestFramework):
self.sync_blocks()
assert len(self.nodes[0].getrawmempool()) == 0
- # Finally, verify that version 0 -> version 1 transactions
+ # Finally, verify that version 0 -> version 2 transactions
# are standard
- script_pubkey = CScript([CScriptOp(OP_1), witness_hash])
+ script_pubkey = CScript([CScriptOp(OP_2), witness_hash])
tx2 = CTransaction()
tx2.vin = [CTxIn(COutPoint(tx.sha256, 0), b"")]
tx2.vout = [CTxOut(tx.vout[0].nValue - 1000, script_pubkey)]
diff --git a/test/functional/rpc_blockchain.py b/test/functional/rpc_blockchain.py
index 35cea85c07..f965677408 100755
--- a/test/functional/rpc_blockchain.py
+++ b/test/functional/rpc_blockchain.py
@@ -146,7 +146,19 @@ class BlockchainTest(BitcoinTestFramework):
'possible': True,
},
},
- 'active': False}
+ 'active': False
+ },
+ 'taproot': {
+ 'type': 'bip9',
+ 'bip9': {
+ 'status': 'active',
+ 'start_time': -1,
+ 'timeout': 9223372036854775807,
+ 'since': 0
+ },
+ 'height': 0,
+ 'active': True
+ }
})
def _test_getchaintxstats(self):
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)
diff --git a/test/functional/test_runner.py b/test/functional/test_runner.py
index 6b746b1fee..8cd82649b6 100755
--- a/test/functional/test_runner.py
+++ b/test/functional/test_runner.py
@@ -70,6 +70,7 @@ TEST_FRAMEWORK_MODULES = [
"address",
"blocktools",
"muhash",
+ "key",
"script",
"segwit_addr",
"util",
@@ -107,6 +108,7 @@ BASE_SCRIPTS = [
'mempool_updatefromblock.py',
'wallet_dump.py',
'wallet_listtransactions.py',
+ 'feature_taproot.py',
# vv Tests less than 60s vv
'p2p_sendheaders.py',
'wallet_importmulti.py',
generated by cgit v1.2.3 (git 2.26.2) at 2024-11-20 14:18:17 +0000