diff options
author | W. J. van der Laan <laanwj@protonmail.com> | 2021-11-15 18:27:49 +0100 |
---|---|---|
committer | W. J. van der Laan <laanwj@protonmail.com> | 2021-11-15 20:32:42 +0100 |
commit | 5ccab7187b35142e03c15dd55390e45b3d233c52 (patch) | |
tree | 14c15a51221682a2c07c78026096b89fa83e2689 /test/functional/feature_taproot.py | |
parent | 7f0f853373703a020529dd9394fca525475086b7 (diff) | |
parent | f1c33ee4ac1056289f2e67b75755388549ada4ca (diff) | |
download | bitcoin-5ccab7187b35142e03c15dd55390e45b3d233c52.tar.xz |
Merge bitcoin/bitcoin#23394: Taproot wallet test vectors (generation+tests)
f1c33ee4ac1056289f2e67b75755388549ada4ca tests: implement BIP341 test vectors (Pieter Wuille)
ac3037df1196b1d95ade2dfad4699ad3a6074903 tests: BIP341 test vector generation (Pieter Wuille)
ca83ffc2ea5fe08f16fff7df71c040d067f2afb0 tests: add deterministic signing mode to ECDSA (Pieter Wuille)
c98c53f20cadeda53f6a9323f72363593d174f68 tests: abstract out precomputed BIP341 signature hash elements (Pieter Wuille)
a5bde018b42cd38979fee71d870e0140b10c73d6 tests: give feature_taproot access to sighash preimages (Pieter Wuille)
51408250969e7ed171378369a995c90d4f813189 tests: add more fields to TaprootInfo (Pieter Wuille)
2478c6730a81dda3c56cb99087caf6abe49c85f5 Make signing follow BIP340 exactly w.r.t. aux randomness (Pieter Wuille)
Pull request description:
This PR adds code to `test/functional/feature_taproot.py` which runs through a (deterministic) scenario covering several aspects of the wallet side of BIP341 (scriptPubKey computation from keys/scripts, control block computation, key path spending), with the ability to output test vectors in mediawiki format based on this scenario. The generated tests are then also included directly in `src/test/script_tests.cpp` and `src/test/script_standard_tests.cpp`.
I intend to add these test vectors to BIP341 itself: https://github.com/bitcoin/bips/pull/1225
ACKs for top commit:
laanwj:
Code review ACK f1c33ee4ac1056289f2e67b75755388549ada4ca
Tree-SHA512: fcf7109539cb214d3190516b205cd32d2b1b452f14aa66f4107acfaa8bfc7d368f626857f1935665a4342eabc0b9ee8aba608a7c0a2494bec0b498e723439c9d
Diffstat (limited to 'test/functional/feature_taproot.py')
-rwxr-xr-x | test/functional/feature_taproot.py | 301 |
1 files changed, 283 insertions, 18 deletions
diff --git a/test/functional/feature_taproot.py b/test/functional/feature_taproot.py index 5f90e49de1..c78e289f74 100755 --- a/test/functional/feature_taproot.py +++ b/test/functional/feature_taproot.py @@ -22,11 +22,17 @@ from test_framework.messages import ( ) from test_framework.script import ( ANNEX_TAG, + BIP341_sha_amounts, + BIP341_sha_outputs, + BIP341_sha_prevouts, + BIP341_sha_scriptpubkeys, + BIP341_sha_sequences, CScript, CScriptNum, CScriptOp, + hash256, LEAF_VERSION_TAPSCRIPT, - LegacySignatureHash, + LegacySignatureMsg, LOCKTIME_THRESHOLD, MAX_SCRIPT_ELEMENT_SIZE, OP_0, @@ -70,13 +76,15 @@ from test_framework.script import ( SIGHASH_NONE, SIGHASH_SINGLE, SIGHASH_ANYONECANPAY, - SegwitV0SignatureHash, - TaprootSignatureHash, + SegwitV0SignatureMsg, + TaggedHash, + TaprootSignatureMsg, is_op_success, taproot_construct, ) from test_framework.script_util import ( key_to_p2pk_script, + key_to_p2pkh_script, key_to_p2wpkh_script, keyhash_to_p2pkh_script, script_to_p2sh_script, @@ -87,6 +95,7 @@ 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, + program_to_witness ) from collections import OrderedDict, namedtuple from io import BytesIO @@ -95,6 +104,9 @@ import hashlib import os import random +# Whether or not to output generated test vectors, in JSON format. +GEN_TEST_VECTORS = False + # === Framework for building spending transactions. === # # The computation is represented as a "context" dict, whose entries store potentially-unevaluated expressions that @@ -194,8 +206,8 @@ def default_controlblock(ctx): """Default expression for "controlblock": combine leafversion, negflag, pubkey_internal, merklebranch.""" return bytes([get(ctx, "leafversion") + get(ctx, "negflag")]) + get(ctx, "pubkey_internal") + get(ctx, "merklebranch") -def default_sighash(ctx): - """Default expression for "sighash": depending on mode, compute BIP341, BIP143, or legacy sighash.""" +def default_sigmsg(ctx): + """Default expression for "sigmsg": depending on mode, compute BIP341, BIP143, or legacy sigmsg.""" tx = get(ctx, "tx") idx = get(ctx, "idx") hashtype = get(ctx, "hashtype_actual") @@ -208,18 +220,30 @@ def default_sighash(ctx): 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) + return TaprootSignatureMsg(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) + return TaprootSignatureMsg(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) + return SegwitV0SignatureMsg(scriptcode, tx, idx, hashtype, utxos[idx].nValue) else: # Pre-segwit signature hash scriptcode = get(ctx, "scriptcode") - return LegacySignatureHash(scriptcode, tx, idx, hashtype)[0] + return LegacySignatureMsg(scriptcode, tx, idx, hashtype)[0] + +def default_sighash(ctx): + """Default expression for "sighash": depending on mode, compute tagged hash or dsha256 of sigmsg.""" + msg = get(ctx, "sigmsg") + mode = get(ctx, "mode") + if mode == "taproot": + return TaggedHash("TapSighash", msg) + else: + if msg is None: + return (1).to_bytes(32, 'little') + else: + return hash256(msg) def default_tweak(ctx): """Default expression for "tweak": None if a leaf is specified, tap[0] otherwise.""" @@ -239,14 +263,18 @@ def default_key_tweaked(ctx): def default_signature(ctx): """Default expression for "signature": BIP340 signature or ECDSA signature depending on mode.""" sighash = get(ctx, "sighash") + deterministic = get(ctx, "deterministic") 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) + aux = bytes([0] * 32) + if not deterministic: + aux = random.getrandbits(256).to_bytes(32, 'big') + return sign_schnorr(key, sighash, flip_r=flip_r, flip_p=flip_p, aux=aux) else: key = get(ctx, "key") - return key.sign_ecdsa(sighash) + return key.sign_ecdsa(sighash, rfc6979=deterministic) def default_hashtype_actual(ctx): """Default expression for "hashtype_actual": hashtype, unless mismatching SIGHASH_SINGLE in taproot.""" @@ -340,6 +368,8 @@ DEFAULT_CONTEXT = { "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 sigmsg value (preimage of sighash) + "sigmsg": default_sigmsg, # The sighash value (32 bytes) "sighash": default_sighash, # The information about the chosen script path spend (TaprootLeafInfo object). @@ -376,6 +406,8 @@ DEFAULT_CONTEXT = { "leaf": None, # The input arguments to provide to the executed script "inputs": [], + # Use deterministic signing nonces + "deterministic": False, # == Parameters to be set before evaluation: == # - mode: what spending style to use ("taproot", "witv0", or "legacy"). @@ -396,6 +428,7 @@ def flatten(lst): 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. @@ -1253,6 +1286,14 @@ class TaprootTest(BitcoinTestFramework): else: assert node.getbestblockhash() == self.lastblockhash, "Failed to reject: " + msg + def init_blockinfo(self, node): + # 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'] + def test_spenders(self, node, spenders, input_counts): """Run randomized tests with a number of "spenders". @@ -1279,12 +1320,7 @@ class TaprootTest(BitcoinTestFramework): 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'] + self.init_blockinfo(node) # 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 @@ -1458,10 +1494,239 @@ class TaprootTest(BitcoinTestFramework): assert len(mismatching_utxos) == 0 self.log.info(" - Done") + def gen_test_vectors(self): + """Run a scenario that corresponds (and optionally produces) to BIP341 test vectors.""" + + self.log.info("Unit test scenario...") + + # Deterministically mine coins to OP_TRUE in block 1 + assert self.nodes[1].getblockcount() == 0 + coinbase = CTransaction() + coinbase.nVersion = 1 + coinbase.vin = [CTxIn(COutPoint(0, 0xffffffff), CScript([OP_1, OP_1]), 0xffffffff)] + coinbase.vout = [CTxOut(5000000000, CScript([OP_1]))] + coinbase.nLockTime = 0 + coinbase.rehash() + assert coinbase.hash == "f60c73405d499a956d3162e3483c395526ef78286458a4cb17b125aa92e49b20" + # Mine it + block = create_block(hashprev=int(self.nodes[1].getbestblockhash(), 16), coinbase=coinbase) + block.rehash() + block.solve() + self.nodes[1].submitblock(block.serialize().hex()) + assert self.nodes[1].getblockcount() == 1 + self.generate(self.nodes[1], COINBASE_MATURITY) + + SEED = 317 + VALID_LEAF_VERS = list(range(0xc0, 0x100, 2)) + [0x66, 0x7e, 0x80, 0x84, 0x96, 0x98, 0xba, 0xbc, 0xbe] + # Generate private keys + prvs = [hashlib.sha256(SEED.to_bytes(2, 'big') + bytes([i])).digest() for i in range(100)] + # Generate corresponding public x-only pubkeys + pubs = [compute_xonly_pubkey(prv)[0] for prv in prvs] + # Generate taproot objects + inner_keys = [pubs[i] for i in range(7)] + + script_lists = [ + None, + [("0", CScript([pubs[50], OP_CHECKSIG]), 0xc0)], + [("0", CScript([pubs[51], OP_CHECKSIG]), 0xc0)], + [("0", CScript([pubs[52], OP_CHECKSIG]), 0xc0), ("1", CScript([b"BIP341"]), VALID_LEAF_VERS[pubs[99][0] % 41])], + [("0", CScript([pubs[53], OP_CHECKSIG]), 0xc0), ("1", CScript([b"Taproot"]), VALID_LEAF_VERS[pubs[99][1] % 41])], + [("0", CScript([pubs[54], OP_CHECKSIG]), 0xc0), [("1", CScript([pubs[55], OP_CHECKSIG]), 0xc0), ("2", CScript([pubs[56], OP_CHECKSIG]), 0xc0)]], + [("0", CScript([pubs[57], OP_CHECKSIG]), 0xc0), [("1", CScript([pubs[58], OP_CHECKSIG]), 0xc0), ("2", CScript([pubs[59], OP_CHECKSIG]), 0xc0)]], + ] + taps = [taproot_construct(inner_keys[i], script_lists[i]) for i in range(len(inner_keys))] + + # Require negated taps[0] + assert taps[0].negflag + # Require one negated and one non-negated in taps 1 and 2. + assert taps[1].negflag != taps[2].negflag + # Require one negated and one non-negated in taps 3 and 4. + assert taps[3].negflag != taps[4].negflag + # Require one negated and one non-negated in taps 5 and 6. + assert taps[5].negflag != taps[6].negflag + + cblks = [{leaf: get({**DEFAULT_CONTEXT, 'tap': taps[i], 'leaf': leaf}, 'controlblock') for leaf in taps[i].leaves} for i in range(7)] + # Require one swapped and one unswapped in taps 3 and 4. + assert (cblks[3]['0'][33:65] < cblks[3]['1'][33:65]) != (cblks[4]['0'][33:65] < cblks[4]['1'][33:65]) + # Require one swapped and one unswapped in taps 5 and 6, both at the top and child level. + assert (cblks[5]['0'][33:65] < cblks[5]['1'][65:]) != (cblks[6]['0'][33:65] < cblks[6]['1'][65:]) + assert (cblks[5]['1'][33:65] < cblks[5]['2'][33:65]) != (cblks[6]['1'][33:65] < cblks[6]['2'][33:65]) + # Require within taps 5 (and thus also 6) that one level is swapped and the other is not. + assert (cblks[5]['0'][33:65] < cblks[5]['1'][65:]) != (cblks[5]['1'][33:65] < cblks[5]['2'][33:65]) + + # Compute a deterministic set of scriptPubKeys + tap_spks = [] + old_spks = [] + spend_info = {} + # First, taproot scriptPubKeys, for the tap objects constructed above + for i, tap in enumerate(taps): + tap_spks.append(tap.scriptPubKey) + d = {'key': prvs[i], 'tap': tap, 'mode': 'taproot'} + spend_info[tap.scriptPubKey] = d + # Then, a number of deterministically generated (keys 0x1,0x2,0x3) with 2x P2PKH, 1x P2WPKH spks. + for i in range(1, 4): + prv = ECKey() + prv.set(i.to_bytes(32, 'big'), True) + pub = prv.get_pubkey().get_bytes() + d = {"key": prv} + d["scriptcode"] = key_to_p2pkh_script(pub) + d["inputs"] = [getter("sign"), pub] + if i < 3: + # P2PKH + d['spk'] = key_to_p2pkh_script(pub) + d['mode'] = 'legacy' + else: + # P2WPKH + d['spk'] = key_to_p2wpkh_script(pub) + d['mode'] = 'witv0' + old_spks.append(d['spk']) + spend_info[d['spk']] = d + + # Construct a deterministic chain of transactions creating UTXOs to the test's spk's (so that they + # come from distinct txids). + txn = [] + lasttxid = coinbase.sha256 + amount = 5000000000 + for i, spk in enumerate(old_spks + tap_spks): + val = 42000000 * (i + 7) + tx = CTransaction() + tx.nVersion = 1 + tx.vin = [CTxIn(COutPoint(lasttxid, i & 1), CScript([]), 0xffffffff)] + tx.vout = [CTxOut(val, spk), CTxOut(amount - val, CScript([OP_1]))] + if i & 1: + tx.vout = list(reversed(tx.vout)) + tx.nLockTime = 0 + tx.rehash() + amount -= val + lasttxid = tx.sha256 + txn.append(tx) + spend_info[spk]['prevout'] = COutPoint(tx.sha256, i & 1) + spend_info[spk]['utxo'] = CTxOut(val, spk) + # Mine those transactions + self.init_blockinfo(self.nodes[1]) + self.block_submit(self.nodes[1], txn, "Crediting txn", None, sigops_weight=10, accept=True) + + # scriptPubKey computation + tests = {"version": 1} + spk_tests = tests.setdefault("scriptPubKey", []) + for i, tap in enumerate(taps): + test_case = {} + given = test_case.setdefault("given", {}) + given['internalPubkey'] = tap.internal_pubkey.hex() + + def pr(node): + if node is None: + return None + elif isinstance(node, tuple): + return {"id": int(node[0]), "script": node[1].hex(), "leafVersion": node[2]} + elif len(node) == 1: + return pr(node[0]) + elif len(node) == 2: + return [pr(node[0]), pr(node[1])] + else: + assert False + + given['scriptTree'] = pr(script_lists[i]) + intermediary = test_case.setdefault("intermediary", {}) + if len(tap.leaves): + leafhashes = intermediary.setdefault('leafHashes', [None] * len(tap.leaves)) + for leaf in tap.leaves: + leafhashes[int(leaf)] = tap.leaves[leaf].leaf_hash.hex() + intermediary['merkleRoot'] = tap.merkle_root.hex() if tap.merkle_root else None + intermediary['tweak'] = tap.tweak.hex() + intermediary['tweakedPubkey'] = tap.output_pubkey.hex() + expected = test_case.setdefault("expected", {}) + expected['scriptPubKey'] = tap.scriptPubKey.hex() + expected['bip350Address'] = program_to_witness(1, bytes(tap.output_pubkey), True) + if len(tap.leaves): + control_blocks = expected.setdefault("scriptPathControlBlocks", [None] * len(tap.leaves)) + for leaf in tap.leaves: + ctx = {**DEFAULT_CONTEXT, 'tap': tap, 'leaf': leaf} + control_blocks[int(leaf)] = get(ctx, "controlblock").hex() + spk_tests.append(test_case) + + # Construct a deterministic transaction spending all outputs created above. + tx = CTransaction() + tx.nVersion = 2 + tx.vin = [] + inputs = [] + input_spks = [tap_spks[0], tap_spks[1], old_spks[0], tap_spks[2], tap_spks[5], old_spks[2], tap_spks[6], tap_spks[3], tap_spks[4]] + sequences = [0, 0xffffffff, 0xffffffff, 0xfffffffe, 0xfffffffe, 0, 0, 0xffffffff, 0xffffffff] + hashtypes = [SIGHASH_SINGLE, SIGHASH_SINGLE|SIGHASH_ANYONECANPAY, SIGHASH_ALL, SIGHASH_ALL, SIGHASH_DEFAULT, SIGHASH_ALL, SIGHASH_NONE, SIGHASH_NONE|SIGHASH_ANYONECANPAY, SIGHASH_ALL|SIGHASH_ANYONECANPAY] + for i, spk in enumerate(input_spks): + tx.vin.append(CTxIn(spend_info[spk]['prevout'], CScript(), sequences[i])) + inputs.append(spend_info[spk]['utxo']) + tx.vout.append(CTxOut(1000000000, old_spks[1])) + tx.vout.append(CTxOut(3410000000, pubs[98])) + tx.nLockTime = 500000000 + precomputed = { + "hashAmounts": BIP341_sha_amounts(inputs), + "hashPrevouts": BIP341_sha_prevouts(tx), + "hashScriptPubkeys": BIP341_sha_scriptpubkeys(inputs), + "hashSequences": BIP341_sha_sequences(tx), + "hashOutputs": BIP341_sha_outputs(tx) + } + keypath_tests = tests.setdefault("keyPathSpending", []) + tx_test = {} + global_given = tx_test.setdefault("given", {}) + global_given['rawUnsignedTx'] = tx.serialize().hex() + utxos_spent = global_given.setdefault("utxosSpent", []) + for i in range(len(input_spks)): + utxos_spent.append({"scriptPubKey": inputs[i].scriptPubKey.hex(), "amountSats": inputs[i].nValue}) + global_intermediary = tx_test.setdefault("intermediary", {}) + for key in sorted(precomputed.keys()): + global_intermediary[key] = precomputed[key].hex() + test_list = tx_test.setdefault('inputSpending', []) + for i in range(len(input_spks)): + ctx = { + **DEFAULT_CONTEXT, + **spend_info[input_spks[i]], + 'tx': tx, + 'utxos': inputs, + 'idx': i, + 'hashtype': hashtypes[i], + 'deterministic': True + } + if ctx['mode'] == 'taproot': + test_case = {} + given = test_case.setdefault("given", {}) + given['txinIndex'] = i + given['internalPrivkey'] = get(ctx, 'key').hex() + if get(ctx, "tap").merkle_root != bytes(): + given['merkleRoot'] = get(ctx, "tap").merkle_root.hex() + else: + given['merkleRoot'] = None + given['hashType'] = get(ctx, "hashtype") + intermediary = test_case.setdefault("intermediary", {}) + intermediary['internalPubkey'] = get(ctx, "tap").internal_pubkey.hex() + intermediary['tweak'] = get(ctx, "tap").tweak.hex() + intermediary['tweakedPrivkey'] = get(ctx, "key_tweaked").hex() + sigmsg = get(ctx, "sigmsg") + intermediary['sigMsg'] = sigmsg.hex() + intermediary['precomputedUsed'] = [key for key in sorted(precomputed.keys()) if sigmsg.count(precomputed[key])] + intermediary['sigHash'] = get(ctx, "sighash").hex() + expected = test_case.setdefault("expected", {}) + expected['witness'] = [get(ctx, "sign").hex()] + test_list.append(test_case) + tx.wit.vtxinwit.append(CTxInWitness()) + tx.vin[i].scriptSig = CScript(flatten(get(ctx, "scriptsig"))) + tx.wit.vtxinwit[i].scriptWitness.stack = flatten(get(ctx, "witness")) + aux = tx_test.setdefault("auxiliary", {}) + aux['fullySignedTx'] = tx.serialize().hex() + keypath_tests.append(tx_test) + assert_equal(hashlib.sha256(tx.serialize()).hexdigest(), "24bab662cb55a7f3bae29b559f651674c62bcc1cd442d44715c0133939107b38") + # Mine the spending transaction + self.block_submit(self.nodes[1], [tx], "Spending txn", None, sigops_weight=10000, accept=True, witness=True) + + if GEN_TEST_VECTORS: + print(json.dumps(tests, indent=4, sort_keys=False)) + + def run_test(self): + self.gen_test_vectors() + # Post-taproot activation tests go first (pre-taproot tests' blocks are invalid post-taproot). self.log.info("Post-activation tests...") - self.generate(self.nodes[1], COINBASE_MATURITY + 1) self.test_spenders(self.nodes[1], spenders_taproot_active(), input_counts=[1, 2, 2, 2, 2, 3]) # Re-connect nodes in case they have been disconnected |