Approximate costs (relative):

# Approximate costs (relative):
ECDSA verification (secp256k1, optimized): ~50-100 microseconds
Schnorr verification (secp256k1, optimized): ~40-80 microseconds

# A block with 3,000 transactions:
Average 2 inputs per transaction = 6,000 signature verifications
Total time without optimization: ~300-600 milliseconds per block

# With optimization target: <100ms per block
→ Caching is essential

class ScriptInterpreter:
    def __init__(self):
        self.stack = []
        self.altstack = []
        self.flags = ScriptVerifyFlags()

    def execute(self, script_bytes, tx, input_index):
        """Execute a script against a transaction."""
        ops = parse_script(script_bytes)

        for op in ops:
            if op.is_push_data():
                self.stack.append(op.data)
            else:
                self.execute_opcode(op.code, tx, input_index)

        # Script succeeds if top of stack is truthy
        return bool(self.stack) and cast_to_bool(self.stack[-1])

    def execute_opcode(self, opcode, tx, input_index):
        if opcode == OP_CHECKSIG:
            pubkey = self.stack.pop()
            sig = self.stack.pop()
            result = self.check_sig(sig, pubkey, tx, input_index)
            self.stack.append(b'\x01' if result else b'')

// Simplified C++ (from Bitcoin Core concept):

class CSignatureCache {
    // Hash set for O(1) lookup
    // Stores hashes of (signature, pubkey, sighash) triples
    std::unordered_set<uint256> valid_sigs;

    uint256 compute_cache_key(
        const std::vector<unsigned char>& sig,
        const CPubKey& pubkey,
        const uint256& sighash
    ) {
        // Hash the three components together
        CHashWriter ss(SER_GETHASH, 0);
        ss << sig << pubkey << sighash;
        return ss.GetHash();
    }

public:
    bool get(const std::vector<unsigned char>& sig,
             const CPubKey& pubkey,
             const uint256& sighash) {
        uint256 key = compute_cache_key(sig, pubkey, sighash);
        return valid_sigs.count(key) > 0;
    }

    void set(const std::vector<unsigned char>& sig,
             const CPubKey& pubkey,
             const uint256& sighash) {
        uint256 key = compute_cache_key(sig, pubkey, sighash);
        valid_sigs.insert(key);
    }
};

OP_CHECKSIG execution with cache:

1. Pop pubkey and signature from stack

2. Compute sighash (serialize transaction, hash it)

3. Compute cache key = HASH(sig || pubkey || sighash)

4. Check cache:
   a. Cache HIT → return cached result immediately (no ECDSA verification)
   b. Cache MISS → perform full ECDSA/Schnorr verification
                   store result in cache
                   return result

Performance:
  Cache hit:  < 1 microsecond (hash lookup)
  Cache miss: 50-100 microseconds (full ECC verification)
python
def checksig_with_cache(sig, pubkey, tx, input_index, sig_cache):
    """OP_CHECKSIG implementation with caching."""
    # 1. Compute the sighash
    sighash_type = sig[-1]
    sighash = compute_sighash(tx, input_index, sighash_type)

    # 2. Check cache
    cache_key = hash_cache_entry(sig, pubkey, sighash)

    if sig_cache.get(cache_key):
        return True  # Fast path: already verified

    # 3. Full verification (slow path)
    result = ecdsa_verify(sig[:-1], pubkey, sighash)

    # 4. Cache the result if valid
    if result:
        sig_cache.set(cache_key, True)

    return result

Reason: An attacker could generate many deliberately invalid signatures,
        caching them all and eventually evicting valid cached entries.
        By only caching valid sigs, the cache serves as a "known good" set.

Collision resistance: The cache key is a 256-bit hash of three components.
        The probability of accidental collision is negligible (2^-256).
        An intentional preimage attack would require breaking SHA-256.

Block arrives with N transactions:
├── Thread 1: validates tx_0, tx_1, ..., tx_(N/4)
├── Thread 2: validates tx_(N/4+1), ..., tx_(N/2)
├── Thread 3: validates tx_(N/2+1), ..., tx_(3N/4)
└── Thread 4: validates tx_(3N/4+1), ..., tx_N

Shared signature cache with mutex:
  Thread 1 verifies sig_A, caches it
  Thread 3 encounters same sig_A → cache hit, no reverification

Scenario: Transaction T enters the mempool.
  → Scripts executed, signatures verified
  → Valid signatures cached

Later: Block containing T arrives.
  → Scripts must be re-executed (consensus requires it)
  → But signature cache has the sig/pubkey/sighash entries
  → OP_CHECKSIG returns immediately with cached result
  → Block validation is dramatically faster

This is the main practical benefit of signature caching:
transactions validated in the mempool don't need full sig verification
when they later appear in a block.

# Consensus limits on script execution:
MAX_SCRIPT_SIZE         = 10,000 bytes
MAX_STACK_SIZE          = 1,000 elements
MAX_SCRIPT_ELEMENT_SIZE = 520 bytes per stack element
MAX_OPS_PER_SCRIPT      = 201 opcodes (not counting pushdata)
MAX_PUBKEYS_PER_MULTISIG = 20

# Signature operation (sigop) counting:
P2PKH input:         1 sigop
P2PK input:          1 sigop
OP_CHECKMULTISIG:    N sigops (or 20 if N is unknown)
MAX_BLOCK_SIGOPS:    20,000 per block

# Tapscript limits (looser due to Schnorr efficiency):
MAX_OPS_PER_SCRIPT: No limit (individual opcodes don't count toward limit)
Sigops: Counted differently — each OP_CHECKSIG/ADD counts as 50 "weight units"

def batch_verify_schnorr(sigs_and_keys: list, message_hashes: list) -> bool:
    """
    Verify multiple Schnorr signatures at once.
    Faster than individual verification when len(sigs_and_keys) > 1.
    """
    # Collect all (R, s, P, msg) tuples
    # Use random linear combination to check all at once
    # The batch verification equation:
    #   Σ(a_i * s_i) * G == Σ(a_i * R_i) + Σ(a_i * H(R_i||P_i||m_i) * P_i)
    # Where a_i are random scalars for each signature

    # Speed improvement:
    # Individual: n * 2 scalar multiplications
    # Batch:      ~1.5 * n scalar multiplications (using Pippenger's algorithm)
    # → ~25% speedup at n=100, ~50% at n=1000+

    ...

When a Bitcoin node receives a transaction:

1. Syntax check: Is the script valid bytecode?

2. Push/pop validation: Do all opcodes have correct stack inputs?

3. Standard scripts check: Is this a recognizable script type?
   (P2PKH, P2SH, P2WPKH, P2WSH, P2TR — others may be non-standard)

4. Execute scriptSig

5. Execute scriptPubKey

6. For P2SH: deserialize and execute redeemScript

7. For SegWit: validate witness program and data

8. For Taproot:
   a. Key path: verify single Schnorr signature against output key
   b. Script path: verify Merkle proof, then execute leaf script

9. Final stack check: top of stack must be truthy (non-zero, non-empty)

At step 6-8: OP_CHECKSIG/CHECKSIGADD consulted the signature cache
  → Cache hit: instant result
  → Cache miss: full ECC verification, then cache the valid result