Inside Bitcoin

1#!/usr/bin/env python3
2# Copyright (c) 2019-present The Bitcoin Core developers
3# Distributed under the MIT software license, see the accompanying
4# file COPYING or http://www.opensource.org/licenses/mit-license.php.
5# Test Taproot softfork (BIPs 340-342)
6
7from test_framework.blocktools import (
8    COINBASE_MATURITY,
9    create_coinbase,
10    create_block,
11    add_witness_commitment,
12    MAX_BLOCK_SIGOPS_WEIGHT,
13)
14from test_framework.messages import (
15    COutPoint,
16    CTransaction,
17    CTxIn,
18    CTxInWitness,
19    CTxOut,
20    SEQUENCE_FINAL,
21    tx_from_hex,
22    TX_MAX_STANDARD_VERSION,
23    WITNESS_SCALE_FACTOR,
24)
25from test_framework.script import (
26    ANNEX_TAG,
27    BIP341_sha_amounts,
28    BIP341_sha_outputs,
29    BIP341_sha_prevouts,
30    BIP341_sha_scriptpubkeys,
31    BIP341_sha_sequences,
32    CScript,
33    CScriptNum,
34    CScriptOp,
35    hash256,
36    LEAF_VERSION_TAPSCRIPT,
37    LegacySignatureMsg,
38    LOCKTIME_THRESHOLD,
39    MAX_SCRIPT_ELEMENT_SIZE,
40    OP_0,
41    OP_1,
42    OP_2,
43    OP_3,
44    OP_4,
45    OP_5,
46    OP_6,
47    OP_7,
48    OP_8,
49    OP_9,
50    OP_10,
51    OP_11,
52    OP_12,
53    OP_16,
54    OP_2DROP,
55    OP_2DUP,
56    OP_CHECKMULTISIG,
57    OP_CHECKMULTISIGVERIFY,
58    OP_CHECKSIG,
59    OP_CHECKSIGADD,
60    OP_CHECKSIGVERIFY,
61    OP_CODESEPARATOR,
62    OP_DROP,
63    OP_DUP,
64    OP_ELSE,
65    OP_ENDIF,
66    OP_EQUAL,
67    OP_EQUALVERIFY,
68    OP_IF,
69    OP_NOP,
70    OP_NOT,
71    OP_NOTIF,
72    OP_PUSHDATA1,
73    OP_RETURN,
74    OP_SWAP,
75    OP_TUCK,
76    OP_VERIFY,
77    SIGHASH_DEFAULT,
78    SIGHASH_ALL,
79    SIGHASH_NONE,
80    SIGHASH_SINGLE,
81    SIGHASH_ANYONECANPAY,
82    SegwitV0SignatureMsg,
83    TaggedHash,
84    TaprootSignatureMsg,
85    is_op_success,
86    taproot_construct,
87)
88from test_framework.script_util import (
89    key_to_p2pk_script,
90    key_to_p2pkh_script,
91    key_to_p2wpkh_script,
92    keyhash_to_p2pkh_script,
93    script_to_p2sh_script,
94    script_to_p2wsh_script,
95)
96from test_framework.test_framework import BitcoinTestFramework
97from test_framework.util import (
98    assert_not_equal,
99    assert_raises_rpc_error,
100    assert_equal,
101)
102from test_framework.wallet import NodeSigner
103from test_framework.wallet_util import generate_keypair
104from test_framework.key import (
105    generate_privkey,
106    compute_xonly_pubkey,
107    sign_schnorr,
108    tweak_add_privkey,
109    ECKey,
110)
111from test_framework.crypto import secp256k1
112from test_framework.address import (
113    hash160,
114    program_to_witness,
115)
116from collections import OrderedDict, namedtuple
117import json
118import hashlib
119import os
120import random
121
122# Whether or not to output generated test vectors, in JSON format.
123GEN_TEST_VECTORS = False
124
125# === Framework for building spending transactions. ===
126#
127# The computation is represented as a "context" dict, whose entries store potentially-unevaluated expressions that
128# refer to lower-level ones. By overwriting these expression, many aspects - both high and low level - of the signing
129# process can be overridden.
130#
131# Specifically, a context object is a dict that maps names to compositions of:
132# - values
133# - lists of values
134# - callables which, when fed the context object as argument, produce any of these
135#
136# The DEFAULT_CONTEXT object specifies a standard signing process, with many overridable knobs.
137#
138# The get(ctx, name) function can evaluate a name, and cache its result in the context.
139# getter(name) can be used to construct a callable that evaluates name. For example:
140#
141#   ctx1 = {**DEFAULT_CONTEXT, inputs=[getter("sign"), b'\x01']}
142#
143# creates a context where the script inputs are a signature plus the bytes 0x01.
144#
145# override(expr, name1=expr1, name2=expr2, ...) can be used to cause an expression to be evaluated in a selectively
146# modified context. For example:
147#
148#   ctx2 = {**DEFAULT_CONTEXT, sighash=override(default_sighash, hashtype=SIGHASH_DEFAULT)}
149#
150# creates a context ctx2 where the sighash is modified to use hashtype=SIGHASH_DEFAULT. This differs from
151#
152#   ctx3 = {**DEFAULT_CONTEXT, hashtype=SIGHASH_DEFAULT}
153#
154# in that ctx3 will globally use hashtype=SIGHASH_DEFAULT (including in the hashtype byte appended to the signature)
155# while ctx2 only uses the modified hashtype inside the sighash calculation.
156
157def deep_eval(ctx, expr):
158    """Recursively replace any callables c in expr (including inside lists) with c(ctx)."""
159    while callable(expr):
160        expr = expr(ctx)
161    if isinstance(expr, list):
162        expr = [deep_eval(ctx, x) for x in expr]
163    return expr
164
165# Data type to represent fully-evaluated expressions in a context dict (so we can avoid reevaluating them).
166Final = namedtuple("Final", "value")
167
168def get(ctx, name):
169    """Evaluate name in context ctx."""
170    assert name in ctx, "Missing '%s' in context" % name
171    expr = ctx[name]
172    if not isinstance(expr, Final):
173        # Evaluate and cache the result.
174        expr = Final(deep_eval(ctx, expr))
175        ctx[name] = expr
176    return expr.value
177
178def getter(name, **kwargs):
179    """Return a callable that evaluates name in its passed context."""
180    return lambda ctx: get({**ctx, **kwargs}, name)
181
182def override(expr, **kwargs):
183    """Return a callable that evaluates expr in a modified context."""
184    return lambda ctx: deep_eval({**ctx, **kwargs}, expr)
185
186# === Implementations for the various default expressions in DEFAULT_CONTEXT ===
187
188def default_hashtype(ctx):
189    """Default expression for "hashtype": SIGHASH_DEFAULT for taproot, SIGHASH_ALL otherwise."""
190    mode = get(ctx, "mode")
191    if mode == "taproot":
192        return SIGHASH_DEFAULT
193    else:
194        return SIGHASH_ALL
195
196def default_tapleaf(ctx):
197    """Default expression for "tapleaf": looking up leaf in tap[2]."""
198    return get(ctx, "tap").leaves[get(ctx, "leaf")]
199
200def default_script_taproot(ctx):
201    """Default expression for "script_taproot": tapleaf.script."""
202    return get(ctx, "tapleaf").script
203
204def default_leafversion(ctx):
205    """Default expression for "leafversion": tapleaf.version"""
206    return get(ctx, "tapleaf").version
207
208def default_negflag(ctx):
209    """Default expression for "negflag": tap.negflag."""
210    return get(ctx, "tap").negflag
211
212def default_pubkey_internal(ctx):
213    """Default expression for "pubkey_internal": tap.internal_pubkey."""
214    return get(ctx, "tap").internal_pubkey
215
216def default_merklebranch(ctx):
217    """Default expression for "merklebranch": tapleaf.merklebranch."""
218    return get(ctx, "tapleaf").merklebranch
219
220def default_controlblock(ctx):
221    """Default expression for "controlblock": combine leafversion, negflag, pubkey_internal, merklebranch."""
222    return bytes([get(ctx, "leafversion") + get(ctx, "negflag")]) + get(ctx, "pubkey_internal") + get(ctx, "merklebranch")
223
224def default_scriptcode_suffix(ctx):
225    """Default expression for "scriptcode_suffix", the actually used portion of the scriptcode."""
226    scriptcode = get(ctx, "scriptcode")
227    codesepnum = get(ctx, "codesepnum")
228    if codesepnum == -1:
229        return scriptcode
230    codeseps = 0
231    for (opcode, data, sop_idx) in scriptcode.raw_iter():
232        if opcode == OP_CODESEPARATOR:
233            if codeseps == codesepnum:
234                return CScript(scriptcode[sop_idx+1:])
235            codeseps += 1
236    assert False
237
238def default_sigmsg(ctx):
239    """Default expression for "sigmsg": depending on mode, compute BIP341, BIP143, or legacy sigmsg."""
240    tx = get(ctx, "tx")
241    idx = get(ctx, "idx")
242    hashtype = get(ctx, "hashtype_actual")
243    mode = get(ctx, "mode")
244    if mode == "taproot":
245        # BIP341 signature hash
246        utxos = get(ctx, "utxos")
247        annex = get(ctx, "annex")
248        if get(ctx, "leaf") is not None:
249            codeseppos = get(ctx, "codeseppos")
250            leaf_ver = get(ctx, "leafversion")