Inside Bitcoin

1501            random.shuffle(unspents)
1502            unspents.sort(key=lambda x: int(x["amount"] * 100000000), reverse=True)
1503            if len(unspents) > 50:
1504                unspents = unspents[:50]
1505            random.shuffle(unspents)
1506            balance = 0
1507            for unspent in unspents:
1508                balance += int(unspent["amount"] * 100000000)
1509                txid = int(unspent["txid"], 16)
1510                fund_tx.vin.append(CTxIn(COutPoint(txid, int(unspent["vout"])), CScript()))
1511            # Add outputs
1512            cur_progress = done / len(spenders)
1513            next_progress = (done + count_this_tx) / len(spenders)
1514            change_goal = (1.0 - 0.6 * next_progress) / (1.0 - 0.6 * cur_progress) * balance
1515            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))
1516            for i in range(count_this_tx):
1517                avg = (balance - change_goal) / (count_this_tx - i)
1518                amount = int(random.randrange(int(avg*0.85 + 0.5), int(avg*1.15 + 0.5)) + 0.5)
1519                balance -= amount
1520                fund_tx.vout.append(CTxOut(amount, spenders[done + i].script))
1521            # Add change
1522            fund_tx.vout.append(CTxOut(balance - 10000, random.choice(host_spks)))
1523            # Ask the node to sign
1524            fund_tx = tx_from_hex(self.nodesigner.signrawtransaction(fund_tx.serialize().hex(), unspents)["hex"])
1525            # Construct UTXOData entries
1526            for i in range(count_this_tx):
1527                utxodata = UTXOData(outpoint=COutPoint(fund_tx.txid_int, i), output=fund_tx.vout[i], spender=spenders[done])
1528                if utxodata.spender.need_vin_vout_mismatch:
1529                    mismatching_utxos.append(utxodata)
1530                else:
1531                    normal_utxos.append(utxodata)
1532                done += 1
1533            # Mine into a block
1534            self.block_submit(node, [fund_tx], "Funding tx", None, random.choice(host_pubkeys), 10000, MAX_BLOCK_SIGOPS_WEIGHT, True, True)
1535
1536        # Consume groups of choice(input_coins) from utxos in a tx, testing the spenders.
1537        self.log.info("- Running %i spending tests" % done)
1538        random.shuffle(normal_utxos)
1539        random.shuffle(mismatching_utxos)
1540        assert_equal(done, len(normal_utxos) + len(mismatching_utxos))
1541
1542        left = done
1543        while left:
1544            # Construct CTransaction with random version, nLocktime
1545            tx = CTransaction()
1546            tx.version = random.choice(TX_STANDARD_VERSIONS + [0, TX_MAX_STANDARD_VERSION + 1, random.getrandbits(32)])
1547            min_sequence = (tx.version != 1 and tx.version != 0) * 0x80000000  # The minimum sequence number to disable relative locktime
1548            if random.choice([True, False]):
1549                tx.nLockTime = random.randrange(LOCKTIME_THRESHOLD, self.lastblocktime - 7200)  # all absolute locktimes in the past
1550            else:
1551                tx.nLockTime = random.randrange(self.lastblockheight + 1)  # all block heights in the past
1552
1553            # Decide how many UTXOs to test with.
1554            acceptable = [n for n in input_counts if n <= left and (left - n > max(input_counts) or (left - n) in [0] + input_counts)]
1555            num_inputs = random.choice(acceptable)
1556
1557            # If we have UTXOs that require mismatching inputs/outputs left, include exactly one of those
1558            # unless there is only one normal UTXO left (as tests with mismatching UTXOs require at least one
1559            # normal UTXO to go in the first position), and we don't want to run out of normal UTXOs.
1560            input_utxos = []
1561            while len(mismatching_utxos) and (len(input_utxos) == 0 or len(normal_utxos) == 1):
1562                input_utxos.append(mismatching_utxos.pop())
1563                left -= 1
1564
1565            # Top up until we hit num_inputs (but include at least one normal UTXO always).
1566            for _ in range(max(1, num_inputs - len(input_utxos))):
1567                input_utxos.append(normal_utxos.pop())
1568                left -= 1
1569
1570            # The first input cannot require a mismatching output (as there is at least one output).
1571            while True:
1572                random.shuffle(input_utxos)
1573                if not input_utxos[0].spender.need_vin_vout_mismatch:
1574                    break
1575            first_mismatch_input = None
1576            for i in range(len(input_utxos)):
1577                if input_utxos[i].spender.need_vin_vout_mismatch:
1578                    first_mismatch_input = i
1579            assert first_mismatch_input is None or first_mismatch_input > 0
1580
1581            # Decide fee, and add CTxIns to tx.
1582            amount = sum(utxo.output.nValue for utxo in input_utxos)
1583            fee = min(random.randrange(MIN_FEE * 2, MIN_FEE * 4), amount - DUST_LIMIT)  # 10000-20000 sat fee
1584            in_value = amount - fee
1585            tx.vin = [CTxIn(outpoint=utxo.outpoint, nSequence=random.randint(min_sequence, 0xffffffff)) for utxo in input_utxos]
1586            tx.wit.vtxinwit = [CTxInWitness() for _ in range(len(input_utxos))]
1587            sigops_weight = sum(utxo.spender.sigops_weight for utxo in input_utxos)
1588            self.log.debug("Test: %s" % (", ".join(utxo.spender.comment for utxo in input_utxos)))
1589
1590            # Add 1 to 4 random outputs (but constrained by inputs that require mismatching outputs)
1591            num_outputs = random.choice(range(1, 1 + min(4, 4 if first_mismatch_input is None else first_mismatch_input)))
1592            assert in_value >= 0 and fee - num_outputs * DUST_LIMIT >= MIN_FEE
1593            for i in range(num_outputs):
1594                tx.vout.append(CTxOut())
1595                if in_value <= DUST_LIMIT:
1596                    tx.vout[-1].nValue = DUST_LIMIT
1597                elif i < num_outputs - 1:
1598                    tx.vout[-1].nValue = in_value
1599                else:
1600                    tx.vout[-1].nValue = random.randint(DUST_LIMIT, in_value)
1601                in_value -= tx.vout[-1].nValue
1602                tx.vout[-1].scriptPubKey = random.choice(host_spks)
1603                sigops_weight += CScript(tx.vout[-1].scriptPubKey).GetSigOpCount(False) * WITNESS_SCALE_FACTOR
1604            fee += in_value
1605            assert fee >= 0
1606
1607            # Select coinbase pubkey
1608            cb_pubkey = random.choice(host_pubkeys)
1609            sigops_weight += 1 * WITNESS_SCALE_FACTOR
1610
1611            # Precompute one satisfying and one failing scriptSig/witness for each input.
1612            input_data = []
1613            for i in range(len(input_utxos)):
1614                fn = input_utxos[i].spender.sat_function
1615                fail = None
1616                success = fn(tx, i, [utxo.output for utxo in input_utxos], True)
1617                if not input_utxos[i].spender.no_fail:
1618                    fail = fn(tx, i, [utxo.output for utxo in input_utxos], False)
1619                input_data.append((fail, success))
1620                if self.options.dump_tests:
1621                    dump_json_test(tx, input_utxos, i, success, fail)
1622
1623            # Sign each input incorrectly once on each complete signing pass, except the very last.
1624            for fail_input in list(range(len(input_utxos))) + [None]:
1625                # Skip trying to fail at spending something that can't be made to fail.
1626                if fail_input is not None and input_utxos[fail_input].spender.no_fail:
1627                    continue
1628                # Expected message with each input failure, may be None(which is ignored)
1629                expected_fail_msg = None if fail_input is None else input_utxos[fail_input].spender.err_msg
1630                # Fill inputs/witnesses
1631                for i in range(len(input_utxos)):
1632                    tx.vin[i].scriptSig = input_data[i][i != fail_input][0]
1633                    tx.wit.vtxinwit[i].scriptWitness.stack = input_data[i][i != fail_input][1]
1634                # Submit to mempool to check standardness
1635                is_standard_tx = (
1636                    fail_input is None  # Must be valid to be standard
1637                    and (all(utxo.spender.is_standard for utxo in input_utxos))  # All inputs must be standard
1638                    and tx.version in TX_STANDARD_VERSIONS # The tx version must be standard
1639                    and not (tx.version == 3 and tx.get_vsize() > TRUC_MAX_VSIZE)  # Topological standardness rules must be followed
1640                )
1641                msg = ','.join(utxo.spender.comment + ("*" if n == fail_input else "") for n, utxo in enumerate(input_utxos))
1642                if is_standard_tx:
1643                    node.sendrawtransaction(tx.serialize().hex(), 0)
1644                    assert node.getmempoolentry(tx.txid_hex) is not None, "Failed to accept into mempool: " + msg
1645                else:
1646                    assert_raises_rpc_error(-26, None, node.sendrawtransaction, tx.serialize().hex(), 0)
1647                # Submit in a block
1648                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)
1649
1650            if (len(spenders) - left) // 200 > (len(spenders) - left - len(input_utxos)) // 200:
1651                self.log.info("  - %i tests done" % (len(spenders) - left))
1652
1653        assert_equal(left, 0)
1654        assert_equal(len(normal_utxos), 0)
1655        assert_equal(len(mismatching_utxos), 0)
1656        self.log.info("  - Done")
1657
1658    def gen_test_vectors(self):
1659        """Run a scenario that corresponds (and optionally produces) to BIP341 test vectors."""
1660
1661        self.log.info("Unit test scenario...")
1662
1663        # Deterministically mine coins to OP_TRUE in block 1
1664        assert_equal(self.nodes[0].getblockcount(), 0)
1665        coinbase = CTransaction()
1666        coinbase.version = 1
1667        coinbase.vin = [CTxIn(COutPoint(0, 0xffffffff), CScript([OP_1, OP_1]), SEQUENCE_FINAL)]
1668        coinbase.vout = [CTxOut(5000000000, CScript([OP_1]))]
1669        coinbase.nLockTime = 0
1670        assert_equal(coinbase.txid_hex, "f60c73405d499a956d3162e3483c395526ef78286458a4cb17b125aa92e49b20")
1671        # Mine it
1672        block = create_block(hashprev=int(self.nodes[0].getbestblockhash(), 16), coinbase=coinbase)
1673        block.solve()
1674        self.nodes[0].submitblock(block.serialize().hex())
1675        assert_equal(self.nodes[0].getblockcount(), 1)
1676        self.generatetoaddress(self.nodes[0], COINBASE_MATURITY, self.nodesigner.getnewaddress()[2])
1677
1678        SEED = 317
1679        VALID_LEAF_VERS = list(range(0xc0, 0x100, 2)) + [0x66, 0x7e, 0x80, 0x84, 0x96, 0x98, 0xba, 0xbc, 0xbe]
1680        # Generate private keys
1681        prvs = [hashlib.sha256(SEED.to_bytes(2, 'big') + bytes([i])).digest() for i in range(100)]
1682        # Generate corresponding public x-only pubkeys
1683        pubs = [compute_xonly_pubkey(prv)[0] for prv in prvs]
1684        # Generate taproot objects
1685        inner_keys = [pubs[i] for i in range(7)]
1686
1687        script_lists = [
1688            None,
1689            [("0", CScript([pubs[50], OP_CHECKSIG]), LEAF_VERSION_TAPSCRIPT)],
1690            [("0", CScript([pubs[51], OP_CHECKSIG]), LEAF_VERSION_TAPSCRIPT)],
1691            [("0", CScript([pubs[52], OP_CHECKSIG]), LEAF_VERSION_TAPSCRIPT), ("1", CScript([b"BIP341"]), VALID_LEAF_VERS[pubs[99][0] % 41])],
1692            [("0", CScript([pubs[53], OP_CHECKSIG]), LEAF_VERSION_TAPSCRIPT), ("1", CScript([b"Taproot"]), VALID_LEAF_VERS[pubs[99][1] % 41])],
1693            [("0", CScript([pubs[54], OP_CHECKSIG]), LEAF_VERSION_TAPSCRIPT),
1694                [("1", CScript([pubs[55], OP_CHECKSIG]), LEAF_VERSION_TAPSCRIPT), ("2", CScript([pubs[56], OP_CHECKSIG]), LEAF_VERSION_TAPSCRIPT)]
1695            ],
1696            [("0", CScript([pubs[57], OP_CHECKSIG]), LEAF_VERSION_TAPSCRIPT),
1697                [("1", CScript([pubs[58], OP_CHECKSIG]), LEAF_VERSION_TAPSCRIPT), ("2", CScript([pubs[59], OP_CHECKSIG]), LEAF_VERSION_TAPSCRIPT)]
1698            ],
1699        ]
1700        taps = [taproot_construct(inner_keys[i], script_lists[i]) for i in range(len(inner_keys))]
1701
1702        # Require negated taps[0]
1703        assert taps[0].negflag
1704        # Require one negated and one non-negated in taps 1 and 2.
1705        assert_not_equal(taps[1].negflag, taps[2].negflag)
1706        # Require one negated and one non-negated in taps 3 and 4.
1707        assert_not_equal(taps[3].negflag, taps[4].negflag)
1708        # Require one negated and one non-negated in taps 5 and 6.
1709        assert_not_equal(taps[5].negflag, taps[6].negflag)
1710
1711        cblks = [{leaf: get({**DEFAULT_CONTEXT, 'tap': taps[i], 'leaf': leaf}, 'controlblock') for leaf in taps[i].leaves} for i in range(7)]
1712        # Require one swapped and one unswapped in taps 3 and 4.
1713        assert_not_equal((cblks[3]['0'][33:65] < cblks[3]['1'][33:65]), (cblks[4]['0'][33:65] < cblks[4]['1'][33:65]))
1714        # Require one swapped and one unswapped in taps 5 and 6, both at the top and child level.
1715        assert_not_equal((cblks[5]['0'][33:65] < cblks[5]['1'][65:]), (cblks[6]['0'][33:65] < cblks[6]['1'][65:]))
1716        assert_not_equal((cblks[5]['1'][33:65] < cblks[5]['2'][33:65]), (cblks[6]['1'][33:65] < cblks[6]['2'][33:65]))
1717        # Require within taps 5 (and thus also 6) that one level is swapped and the other is not.
1718        assert_not_equal((cblks[5]['0'][33:65] < cblks[5]['1'][65:]), (cblks[5]['1'][33:65] < cblks[5]['2'][33:65]))
1719
1720        # Compute a deterministic set of scriptPubKeys
1721        tap_spks = []
1722        old_spks = []
1723        spend_info = {}
1724        # First, taproot scriptPubKeys, for the tap objects constructed above
1725        for i, tap in enumerate(taps):
1726            tap_spks.append(tap.scriptPubKey)
1727            d = {'key': prvs[i], 'tap': tap, 'mode': 'taproot'}
1728            spend_info[tap.scriptPubKey] = d
1729        # Then, a number of deterministically generated (keys 0x1,0x2,0x3) with 2x P2PKH, 1x P2WPKH spks.
1730        for i in range(1, 4):
1731            prv = ECKey()
1732            prv.set(i.to_bytes(32, 'big'), True)
1733            pub = prv.get_pubkey().get_bytes()
1734            d = {"key": prv}
1735            d["scriptcode"] = key_to_p2pkh_script(pub)
1736            d["inputs"] = [getter("sign"), pub]
1737            if i < 3:
1738                # P2PKH
1739                d['spk'] = key_to_p2pkh_script(pub)
1740                d['mode'] = 'legacy'
1741            else:
1742                # P2WPKH
1743                d['spk'] = key_to_p2wpkh_script(pub)
1744                d['mode'] = 'witv0'
1745            old_spks.append(d['spk'])
1746            spend_info[d['spk']] = d
1747
1748        # Construct a deterministic chain of transactions creating UTXOs to the test's spk's (so that they
1749        # come from distinct txids).
1750        txn = []