How Bitcoin checks a spending script

251        {
252            pc = pc + b.size();
253            ++nFound;
254        }
255        pc2 = pc;
256    }
257    while (script.GetOp(pc, opcode));
258
259    if (nFound > 0) {
260        result.insert(result.end(), pc2, end);
261        script = std::move(result);
262    }
263
264    return nFound;
265}
266
267namespace {
268/** A data type to abstract out the condition stack during script execution.
269 *
270 * Conceptually it acts like a vector of booleans, one for each level of nested
271 * IF/THEN/ELSE, indicating whether we're in the active or inactive branch of
272 * each.
273 *
274 * The elements on the stack cannot be observed individually; we only need to
275 * expose whether the stack is empty and whether or not any false values are
276 * present at all. To implement OP_ELSE, a toggle_top modifier is added, which
277 * flips the last value without returning it.
278 *
279 * This uses an optimized implementation that does not materialize the
280 * actual stack. Instead, it just stores the size of the would-be stack,
281 * and the position of the first false value in it.
282 */
283class ConditionStack {
284private:
285    //! A constant for m_first_false_pos to indicate there are no falses.
286    static constexpr uint32_t NO_FALSE = std::numeric_limits<uint32_t>::max();
287
288    //! The size of the implied stack.
289    uint32_t m_stack_size = 0;
290    //! The position of the first false value on the implied stack, or NO_FALSE if all true.
291    uint32_t m_first_false_pos = NO_FALSE;
292
293public:
294    bool empty() const { return m_stack_size == 0; }
295    bool all_true() const { return m_first_false_pos == NO_FALSE; }
296    void push_back(bool f)
297    {
298        if (m_first_false_pos == NO_FALSE && !f) {
299            // The stack consists of all true values, and a false is added.
300            // The first false value will appear at the current size.
301            m_first_false_pos = m_stack_size;
302        }
303        ++m_stack_size;
304    }
305    void pop_back()
306    {
307        assert(m_stack_size > 0);
308        --m_stack_size;
309        if (m_first_false_pos == m_stack_size) {
310            // When popping off the first false value, everything becomes true.
311            m_first_false_pos = NO_FALSE;
312        }
313    }
314    void toggle_top()
315    {
316        assert(m_stack_size > 0);
317        if (m_first_false_pos == NO_FALSE) {
318            // The current stack is all true values; the first false will be the top.
319            m_first_false_pos = m_stack_size - 1;
320        } else if (m_first_false_pos == m_stack_size - 1) {
321            // The top is the first false value; toggling it will make everything true.
322            m_first_false_pos = NO_FALSE;
323        } else {
324            // There is a false value, but not on top. No action is needed as toggling
325            // anything but the first false value is unobservable.
326        }
327    }
328};
329}
330
331static bool EvalChecksigPreTapscript(const valtype& vchSig, const valtype& vchPubKey, CScript::const_iterator pbegincodehash, CScript::const_iterator pend, script_verify_flags flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptError* serror, bool& fSuccess)
332{
333    assert(sigversion == SigVersion::BASE || sigversion == SigVersion::WITNESS_V0);
334
335    // Subset of script starting at the most recent codeseparator
336    CScript scriptCode(pbegincodehash, pend);
337
338    // Drop the signature in pre-segwit scripts but not segwit scripts
339    if (sigversion == SigVersion::BASE) {
340        int found = FindAndDelete(scriptCode, CScript() << vchSig);
341        if (found > 0 && (flags & SCRIPT_VERIFY_CONST_SCRIPTCODE))
342            return set_error(serror, SCRIPT_ERR_SIG_FINDANDDELETE);
343    }
344
345    if (!CheckSignatureEncoding(vchSig, flags, serror) || !CheckPubKeyEncoding(vchPubKey, flags, sigversion, serror)) {
346        //serror is set
347        return false;
348    }
349    fSuccess = checker.CheckECDSASignature(vchSig, vchPubKey, scriptCode, sigversion);
350
351    if (!fSuccess && (flags & SCRIPT_VERIFY_NULLFAIL) && vchSig.size())
352        return set_error(serror, SCRIPT_ERR_SIG_NULLFAIL);
353
354    return true;
355}
356
357static bool EvalChecksigTapscript(const valtype& sig, const valtype& pubkey, ScriptExecutionData& execdata, script_verify_flags flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptError* serror, bool& success)
358{
359    assert(sigversion == SigVersion::TAPSCRIPT);
360
361    /*
362     *  The following validation sequence is consensus critical. Please note how --
363     *    upgradable public key versions precede other rules;
364     *    the script execution fails when using empty signature with invalid public key;
365     *    the script execution fails when using non-empty invalid signature.
366     */
367    success = !sig.empty();
368    if (success) {
369        // Implement the sigops/witnesssize ratio test.
370        // Passing with an upgradable public key version is also counted.
371        assert(execdata.m_validation_weight_left_init);
372        execdata.m_validation_weight_left -= VALIDATION_WEIGHT_PER_SIGOP_PASSED;
373        if (execdata.m_validation_weight_left < 0) {
374            return set_error(serror, SCRIPT_ERR_TAPSCRIPT_VALIDATION_WEIGHT);
375        }
376    }
377    if (pubkey.size() == 0) {
378        return set_error(serror, SCRIPT_ERR_TAPSCRIPT_EMPTY_PUBKEY);
379    } else if (pubkey.size() == 32) {
380        if (success && !checker.CheckSchnorrSignature(sig, pubkey, sigversion, execdata, serror)) {
381            return false; // serror is set
382        }
383    } else {
384        /*
385         *  New public key version softforks should be defined before this `else` block.
386         *  Generally, the new code should not do anything but failing the script execution. To avoid
387         *  consensus bugs, it should not modify any existing values (including `success`).
388         */
389        if ((flags & SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_PUBKEYTYPE) != 0) {
390            return set_error(serror, SCRIPT_ERR_DISCOURAGE_UPGRADABLE_PUBKEYTYPE);
391        }
392    }
393
394    return true;
395}
396
397/** Helper for OP_CHECKSIG, OP_CHECKSIGVERIFY, and (in Tapscript) OP_CHECKSIGADD.
398 *
399 * A return value of false means the script fails entirely. When true is returned, the
400 * success variable indicates whether the signature check itself succeeded.
401 */
402static bool EvalChecksig(const valtype& sig, const valtype& pubkey, CScript::const_iterator pbegincodehash, CScript::const_iterator pend, ScriptExecutionData& execdata, script_verify_flags flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptError* serror, bool& success)
403{
404    switch (sigversion) {
405    case SigVersion::BASE:
406    case SigVersion::WITNESS_V0:
407        return EvalChecksigPreTapscript(sig, pubkey, pbegincodehash, pend, flags, checker, sigversion, serror, success);
408    case SigVersion::TAPSCRIPT:
409        return EvalChecksigTapscript(sig, pubkey, execdata, flags, checker, sigversion, serror, success);
410    case SigVersion::TAPROOT:
411        // Key path spending in Taproot has no script, so this is unreachable.
412        break;
413    }
414    assert(false);
415}
416
417bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& script, script_verify_flags flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptExecutionData& execdata, ScriptError* serror)
418{
419    static const CScriptNum bnZero(0);
420    static const CScriptNum bnOne(1);
421    // static const CScriptNum bnFalse(0);
422    // static const CScriptNum bnTrue(1);
423    static const valtype vchFalse(0);
424    // static const valtype vchZero(0);
425    static const valtype vchTrue(1, 1);
426
427    // sigversion cannot be TAPROOT here, as it admits no script execution.
428    assert(sigversion == SigVersion::BASE || sigversion == SigVersion::WITNESS_V0 || sigversion == SigVersion::TAPSCRIPT);
429
430    CScript::const_iterator pc = script.begin();
431    CScript::const_iterator pend = script.end();
432    CScript::const_iterator pbegincodehash = script.begin();
433    opcodetype opcode;
434    valtype vchPushValue;
435    ConditionStack vfExec;
436    std::vector<valtype> altstack;
437    set_error(serror, SCRIPT_ERR_UNKNOWN_ERROR);
438    if ((sigversion == SigVersion::BASE || sigversion == SigVersion::WITNESS_V0) && script.size() > MAX_SCRIPT_SIZE) {
439        return set_error(serror, SCRIPT_ERR_SCRIPT_SIZE);
440    }
441    int nOpCount = 0;
442    bool fRequireMinimal = (flags & SCRIPT_VERIFY_MINIMALDATA) != 0;
443    uint32_t opcode_pos = 0;
444    execdata.m_codeseparator_pos = 0xFFFFFFFFUL;
445    execdata.m_codeseparator_pos_init = true;
446
447    try
448    {
449        for (; pc < pend; ++opcode_pos) {
450            bool fExec = vfExec.all_true();
451
452            //
453            // Read instruction
454            //
455            if (!script.GetOp(pc, opcode, vchPushValue))
456                return set_error(serror, SCRIPT_ERR_BAD_OPCODE);
457            if (vchPushValue.size() > MAX_SCRIPT_ELEMENT_SIZE)
458                return set_error(serror, SCRIPT_ERR_PUSH_SIZE);
459
460            if (sigversion == SigVersion::BASE || sigversion == SigVersion::WITNESS_V0) {
461                // Note how OP_RESERVED does not count towards the opcode limit.
462                if (opcode > OP_16 && ++nOpCount > MAX_OPS_PER_SCRIPT) {
463                    return set_error(serror, SCRIPT_ERR_OP_COUNT);
464                }
465            }
466
467            if (opcode == OP_CAT ||
468                opcode == OP_SUBSTR ||
469                opcode == OP_LEFT ||
470                opcode == OP_RIGHT ||
471                opcode == OP_INVERT ||
472                opcode == OP_AND ||
473                opcode == OP_OR ||
474                opcode == OP_XOR ||
475                opcode == OP_2MUL ||
476                opcode == OP_2DIV ||
477                opcode == OP_MUL ||
478                opcode == OP_DIV ||
479                opcode == OP_MOD ||
480                opcode == OP_LSHIFT ||
481                opcode == OP_RSHIFT)
482                return set_error(serror, SCRIPT_ERR_DISABLED_OPCODE); // Disabled opcodes (CVE-2010-5137).
483
484            // With SCRIPT_VERIFY_CONST_SCRIPTCODE, OP_CODESEPARATOR in non-segwit script is rejected even in an unexecuted branch
485            if (opcode == OP_CODESEPARATOR && sigversion == SigVersion::BASE && (flags & SCRIPT_VERIFY_CONST_SCRIPTCODE))
486                return set_error(serror, SCRIPT_ERR_OP_CODESEPARATOR);
487
488            if (fExec && 0 <= opcode && opcode <= OP_PUSHDATA4) {
489                if (fRequireMinimal && !CheckMinimalPush(vchPushValue, opcode)) {
490                    return set_error(serror, SCRIPT_ERR_MINIMALDATA);
491                }
492                stack.push_back(vchPushValue);
493            } else if (fExec || (OP_IF <= opcode && opcode <= OP_ENDIF))
494            switch (opcode)
495            {
496                //
497                // Push value
498                //
499                case OP_1NEGATE:
500                case OP_1: