How Bitcoin checks a spending script

1751    return true;
1752}
1753
1754template <class T>
1755bool GenericTransactionSignatureChecker<T>::CheckLockTime(const CScriptNum& nLockTime) const
1756{
1757    // There are two kinds of nLockTime: lock-by-blockheight
1758    // and lock-by-blocktime, distinguished by whether
1759    // nLockTime < LOCKTIME_THRESHOLD.
1760    //
1761    // We want to compare apples to apples, so fail the script
1762    // unless the type of nLockTime being tested is the same as
1763    // the nLockTime in the transaction.
1764    if (!(
1765        (txTo->nLockTime <  LOCKTIME_THRESHOLD && nLockTime <  LOCKTIME_THRESHOLD) ||
1766        (txTo->nLockTime >= LOCKTIME_THRESHOLD && nLockTime >= LOCKTIME_THRESHOLD)
1767    ))
1768        return false;
1769
1770    // Now that we know we're comparing apples-to-apples, the
1771    // comparison is a simple numeric one.
1772    if (nLockTime > (int64_t)txTo->nLockTime)
1773        return false;
1774
1775    // Finally the nLockTime feature can be disabled in IsFinalTx()
1776    // and thus CHECKLOCKTIMEVERIFY bypassed if every txin has
1777    // been finalized by setting nSequence to maxint. The
1778    // transaction would be allowed into the blockchain, making
1779    // the opcode ineffective.
1780    //
1781    // Testing if this vin is not final is sufficient to
1782    // prevent this condition. Alternatively we could test all
1783    // inputs, but testing just this input minimizes the data
1784    // required to prove correct CHECKLOCKTIMEVERIFY execution.
1785    if (CTxIn::SEQUENCE_FINAL == txTo->vin[nIn].nSequence)
1786        return false;
1787
1788    return true;
1789}
1790
1791template <class T>
1792bool GenericTransactionSignatureChecker<T>::CheckSequence(const CScriptNum& nSequence) const
1793{
1794    // Relative lock times are supported by comparing the passed
1795    // in operand to the sequence number of the input.
1796    const int64_t txToSequence = (int64_t)txTo->vin[nIn].nSequence;
1797
1798    // Fail if the transaction's version number is not set high
1799    // enough to trigger BIP 68 rules.
1800    if (txTo->version < 2)
1801        return false;
1802
1803    // Sequence numbers with their most significant bit set are not
1804    // consensus constrained. Testing that the transaction's sequence
1805    // number do not have this bit set prevents using this property
1806    // to get around a CHECKSEQUENCEVERIFY check.
1807    if (txToSequence & CTxIn::SEQUENCE_LOCKTIME_DISABLE_FLAG)
1808        return false;
1809
1810    // Mask off any bits that do not have consensus-enforced meaning
1811    // before doing the integer comparisons
1812    const uint32_t nLockTimeMask = CTxIn::SEQUENCE_LOCKTIME_TYPE_FLAG | CTxIn::SEQUENCE_LOCKTIME_MASK;
1813    const int64_t txToSequenceMasked = txToSequence & nLockTimeMask;
1814    const CScriptNum nSequenceMasked = nSequence & nLockTimeMask;
1815
1816    // There are two kinds of nSequence: lock-by-blockheight
1817    // and lock-by-blocktime, distinguished by whether
1818    // nSequenceMasked < CTxIn::SEQUENCE_LOCKTIME_TYPE_FLAG.
1819    //
1820    // We want to compare apples to apples, so fail the script
1821    // unless the type of nSequenceMasked being tested is the same as
1822    // the nSequenceMasked in the transaction.
1823    if (!(
1824        (txToSequenceMasked <  CTxIn::SEQUENCE_LOCKTIME_TYPE_FLAG && nSequenceMasked <  CTxIn::SEQUENCE_LOCKTIME_TYPE_FLAG) ||
1825        (txToSequenceMasked >= CTxIn::SEQUENCE_LOCKTIME_TYPE_FLAG && nSequenceMasked >= CTxIn::SEQUENCE_LOCKTIME_TYPE_FLAG)
1826    )) {
1827        return false;
1828    }
1829
1830    // Now that we know we're comparing apples-to-apples, the
1831    // comparison is a simple numeric one.
1832    if (nSequenceMasked > txToSequenceMasked)
1833        return false;
1834
1835    return true;
1836}
1837
1838// explicit instantiation
1839template class GenericTransactionSignatureChecker<CTransaction>;
1840template class GenericTransactionSignatureChecker<CMutableTransaction>;
1841
1842static bool ExecuteWitnessScript(const std::span<const valtype>& stack_span, const CScript& exec_script, script_verify_flags flags, SigVersion sigversion, const BaseSignatureChecker& checker, ScriptExecutionData& execdata, ScriptError* serror)
1843{
1844    std::vector<valtype> stack{stack_span.begin(), stack_span.end()};
1845
1846    if (sigversion == SigVersion::TAPSCRIPT) {
1847        // OP_SUCCESSx processing overrides everything, including stack element size limits
1848        CScript::const_iterator pc = exec_script.begin();
1849        while (pc < exec_script.end()) {
1850            opcodetype opcode;
1851            if (!exec_script.GetOp(pc, opcode)) {
1852                // Note how this condition would not be reached if an unknown OP_SUCCESSx was found
1853                return set_error(serror, SCRIPT_ERR_BAD_OPCODE);
1854            }
1855            // New opcodes will be listed here. May use a different sigversion to modify existing opcodes.
1856            if (IsOpSuccess(opcode)) {
1857                if (flags & SCRIPT_VERIFY_DISCOURAGE_OP_SUCCESS) {
1858                    return set_error(serror, SCRIPT_ERR_DISCOURAGE_OP_SUCCESS);
1859                }
1860                return set_success(serror);
1861            }
1862        }
1863
1864        // Tapscript enforces initial stack size limits (altstack is empty here)
1865        if (stack.size() > MAX_STACK_SIZE) return set_error(serror, SCRIPT_ERR_STACK_SIZE);
1866    }
1867
1868    // Disallow stack item size > MAX_SCRIPT_ELEMENT_SIZE in witness stack
1869    for (const valtype& elem : stack) {
1870        if (elem.size() > MAX_SCRIPT_ELEMENT_SIZE) return set_error(serror, SCRIPT_ERR_PUSH_SIZE);
1871    }
1872
1873    // Run the script interpreter.
1874    if (!EvalScript(stack, exec_script, flags, checker, sigversion, execdata, serror)) return false;
1875
1876    // Scripts inside witness implicitly require cleanstack behaviour
1877    if (stack.size() != 1) return set_error(serror, SCRIPT_ERR_CLEANSTACK);
1878    if (!CastToBool(stack.back())) return set_error(serror, SCRIPT_ERR_EVAL_FALSE);
1879    return true;
1880}
1881
1882uint256 ComputeTapleafHash(uint8_t leaf_version, std::span<const unsigned char> script)
1883{
1884    return (HashWriter{HASHER_TAPLEAF} << leaf_version << CompactSizeWriter(script.size()) << script).GetSHA256();
1885}
1886
1887uint256 ComputeTapbranchHash(std::span<const unsigned char> a, std::span<const unsigned char> b)
1888{
1889    HashWriter ss_branch{HASHER_TAPBRANCH};
1890    if (std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end())) {
1891        ss_branch << a << b;
1892    } else {
1893        ss_branch << b << a;
1894    }
1895    return ss_branch.GetSHA256();
1896}
1897
1898uint256 ComputeTaprootMerkleRoot(std::span<const unsigned char> control, const uint256& tapleaf_hash)
1899{
1900    assert(control.size() >= TAPROOT_CONTROL_BASE_SIZE);
1901    assert(control.size() <= TAPROOT_CONTROL_MAX_SIZE);
1902    assert((control.size() - TAPROOT_CONTROL_BASE_SIZE) % TAPROOT_CONTROL_NODE_SIZE == 0);
1903
1904    const int path_len = (control.size() - TAPROOT_CONTROL_BASE_SIZE) / TAPROOT_CONTROL_NODE_SIZE;
1905    uint256 k = tapleaf_hash;
1906    for (int i = 0; i < path_len; ++i) {
1907        std::span node{std::span{control}.subspan(TAPROOT_CONTROL_BASE_SIZE + TAPROOT_CONTROL_NODE_SIZE * i, TAPROOT_CONTROL_NODE_SIZE)};
1908        k = ComputeTapbranchHash(k, node);
1909    }
1910    return k;
1911}
1912
1913static bool VerifyTaprootCommitment(const std::vector<unsigned char>& control, const std::vector<unsigned char>& program, const uint256& tapleaf_hash)
1914{
1915    assert(control.size() >= TAPROOT_CONTROL_BASE_SIZE);
1916    assert(program.size() >= uint256::size());
1917    //! The internal pubkey (x-only, so no Y coordinate parity).
1918    const XOnlyPubKey p{std::span{control}.subspan(1, TAPROOT_CONTROL_BASE_SIZE - 1)};
1919    //! The output pubkey (taken from the scriptPubKey).
1920    const XOnlyPubKey q{program};
1921    // Compute the Merkle root from the leaf and the provided path.
1922    const uint256 merkle_root = ComputeTaprootMerkleRoot(control, tapleaf_hash);
1923    // Verify that the output pubkey matches the tweaked internal pubkey, after correcting for parity.
1924    return q.CheckTapTweak(p, merkle_root, control[0] & 1);
1925}
1926
1927static bool VerifyWitnessProgram(const CScriptWitness& witness, int witversion, const std::vector<unsigned char>& program, script_verify_flags flags, const BaseSignatureChecker& checker, ScriptError* serror, bool is_p2sh)
1928{
1929    CScript exec_script; //!< Actually executed script (last stack item in P2WSH; implied P2PKH script in P2WPKH; leaf script in P2TR)
1930    std::span stack{witness.stack};
1931    ScriptExecutionData execdata;
1932
1933    if (witversion == 0) {
1934        if (program.size() == WITNESS_V0_SCRIPTHASH_SIZE) {
1935            // BIP141 P2WSH: 32-byte witness v0 program (which encodes SHA256(script))
1936            if (stack.size() == 0) {
1937                return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_WITNESS_EMPTY);
1938            }
1939            const valtype& script_bytes = SpanPopBack(stack);
1940            exec_script = CScript(script_bytes.begin(), script_bytes.end());
1941            uint256 hash_exec_script;
1942            CSHA256().Write(exec_script.data(), exec_script.size()).Finalize(hash_exec_script.begin());
1943            if (memcmp(hash_exec_script.begin(), program.data(), 32)) {
1944                return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_MISMATCH);
1945            }
1946            return ExecuteWitnessScript(stack, exec_script, flags, SigVersion::WITNESS_V0, checker, execdata, serror);
1947        } else if (program.size() == WITNESS_V0_KEYHASH_SIZE) {
1948            // BIP141 P2WPKH: 20-byte witness v0 program (which encodes Hash160(pubkey))
1949            if (stack.size() != 2) {
1950                return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_MISMATCH); // 2 items in witness
1951            }
1952            exec_script << OP_DUP << OP_HASH160 << program << OP_EQUALVERIFY << OP_CHECKSIG;
1953            return ExecuteWitnessScript(stack, exec_script, flags, SigVersion::WITNESS_V0, checker, execdata, serror);
1954        } else {
1955            return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_WRONG_LENGTH);
1956        }
1957    } else if (witversion == 1 && program.size() == WITNESS_V1_TAPROOT_SIZE && !is_p2sh) {
1958        // BIP341 Taproot: 32-byte non-P2SH witness v1 program (which encodes a P2C-tweaked pubkey)
1959        if (!(flags & SCRIPT_VERIFY_TAPROOT)) return set_success(serror);
1960        if (stack.size() == 0) return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_WITNESS_EMPTY);
1961        if (stack.size() >= 2 && !stack.back().empty() && stack.back()[0] == ANNEX_TAG) {
1962            // Drop annex (this is non-standard; see IsWitnessStandard)
1963            const valtype& annex = SpanPopBack(stack);
1964            execdata.m_annex_hash = (HashWriter{} << annex).GetSHA256();
1965            execdata.m_annex_present = true;
1966        } else {
1967            execdata.m_annex_present = false;
1968        }
1969        execdata.m_annex_init = true;
1970        if (stack.size() == 1) {
1971            // Key path spending (stack size is 1 after removing optional annex)
1972            if (!checker.CheckSchnorrSignature(stack.front(), program, SigVersion::TAPROOT, execdata, serror)) {
1973                return false; // serror is set
1974            }
1975            return set_success(serror);
1976        } else {
1977            // Script path spending (stack size is >1 after removing optional annex)
1978            const valtype& control = SpanPopBack(stack);
1979            const valtype& script = SpanPopBack(stack);
1980            if (control.size() < TAPROOT_CONTROL_BASE_SIZE || control.size() > TAPROOT_CONTROL_MAX_SIZE || ((control.size() - TAPROOT_CONTROL_BASE_SIZE) % TAPROOT_CONTROL_NODE_SIZE) != 0) {
1981                return set_error(serror, SCRIPT_ERR_TAPROOT_WRONG_CONTROL_SIZE);
1982            }
1983            execdata.m_tapleaf_hash = ComputeTapleafHash(control[0] & TAPROOT_LEAF_MASK, script);
1984            if (!VerifyTaprootCommitment(control, program, execdata.m_tapleaf_hash)) {
1985                return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_MISMATCH);
1986            }
1987            execdata.m_tapleaf_hash_init = true;
1988            if ((control[0] & TAPROOT_LEAF_MASK) == TAPROOT_LEAF_TAPSCRIPT) {
1989                // Tapscript (leaf version 0xc0)
1990                exec_script = CScript(script.begin(), script.end());
1991                execdata.m_validation_weight_left = ::GetSerializeSize(witness.stack) + VALIDATION_WEIGHT_OFFSET;
1992                execdata.m_validation_weight_left_init = true;
1993                return ExecuteWitnessScript(stack, exec_script, flags, SigVersion::TAPSCRIPT, checker, execdata, serror);
1994            }
1995            if (flags & SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_TAPROOT_VERSION) {
1996                return set_error(serror, SCRIPT_ERR_DISCOURAGE_UPGRADABLE_TAPROOT_VERSION);
1997            }
1998            return set_success(serror);
1999        }
2000    } else if (!is_p2sh && CScript::IsPayToAnchor(witversion, program)) {