subcoin_script/
interpreter.rs

1mod eval;
2
3use crate::constants::{
4    MAX_SCRIPT_ELEMENT_SIZE, MAX_STACK_SIZE, VALIDATION_WEIGHT_OFFSET, WITNESS_V0_KEYHASH_SIZE,
5    WITNESS_V0_SCRIPTHASH_SIZE, WITNESS_V0_TAPROOT_SIZE,
6};
7use crate::error::Error;
8use crate::signature_checker::{SECP, SignatureChecker};
9use crate::stack::Stack;
10use crate::{SchnorrSignature, ScriptExecutionData, SigVersion, VerifyFlags};
11use bitcoin::hashes::Hash;
12use bitcoin::opcodes::all::{OP_CHECKSIG, OP_DUP, OP_EQUALVERIFY, OP_HASH160};
13use bitcoin::script::{Builder, Instruction, PushBytesBuf};
14use bitcoin::taproot::{
15    ControlBlock, LeafVersion, TAPROOT_ANNEX_PREFIX, TAPROOT_CONTROL_BASE_SIZE,
16    TAPROOT_CONTROL_MAX_SIZE, TAPROOT_CONTROL_NODE_SIZE, TAPROOT_LEAF_MASK, TAPROOT_LEAF_TAPSCRIPT,
17};
18use bitcoin::{Script, TapLeafHash, Witness, WitnessProgram, WitnessVersion, XOnlyPublicKey};
19
20pub use self::eval::{CheckMultiSigError, CheckSigError, eval_script};
21
22/// Verifies the script validity.
23///
24/// - `Ok(())`: `return true` in C++.
25/// - `Err(err)`: `return false` with `serror` set.
26pub fn verify_script<SC: SignatureChecker>(
27    script_sig: &Script,
28    script_pubkey: &Script,
29    witness: &Witness,
30    flags: &VerifyFlags,
31    checker: &mut SC,
32) -> Result<(), Error> {
33    if flags.intersects(VerifyFlags::SIGPUSHONLY) && !script_sig.is_push_only() {
34        return Err(Error::SigPushOnly);
35    }
36
37    // scriptSig and scriptPubKey must be evaluated sequentially on the same stack rather
38    // than being simply concatnated (see CVE-2010-5141).
39    let mut stack = Stack::with_flags(flags);
40
41    eval_script(
42        &mut stack,
43        script_sig,
44        flags,
45        checker,
46        SigVersion::Base,
47        &mut ScriptExecutionData::default(),
48    )?;
49
50    let stack_copy_for_p2sh = if flags.intersects(VerifyFlags::P2SH) {
51        Some(stack.clone())
52    } else {
53        None
54    };
55
56    eval_script(
57        &mut stack,
58        script_pubkey,
59        flags,
60        checker,
61        SigVersion::Base,
62        &mut ScriptExecutionData::default(),
63    )?;
64
65    if stack.is_empty() {
66        tracing::debug!("[verify_script] Invalid script: empty stack");
67        return Err(Error::EvalFalse);
68    }
69
70    if !stack.peek_bool()? {
71        tracing::debug!(%stack, "[verify_script] Invalid script: false stack element");
72        return Err(Error::EvalFalse);
73    }
74
75    let mut had_witness = false;
76
77    // Bare witness program
78    if flags.intersects(VerifyFlags::WITNESS) {
79        if let Some(witness_program) = parse_witness_program(script_pubkey)? {
80            had_witness = true;
81
82            // script_sig must be empty for all native witness programs, otherwise
83            // we introduce malleability.
84            if !script_sig.is_empty() {
85                return Err(Error::WitnessMalleated);
86            }
87
88            verify_witness_program(witness, witness_program, flags, checker, false)?;
89
90            // Bypass the cleanstack check at the end. The actual stack is obviously not clean
91            // for witness programs.
92            stack.truncate(1);
93        }
94    }
95
96    // Additional validation for spend-to-script-hash transactions:
97    match stack_copy_for_p2sh {
98        Some(mut stack_copy) if script_pubkey.is_p2sh() => {
99            // scriptSig must be literals-only or validation fails.
100            if !script_sig.is_push_only() {
101                return Err(Error::SigPushOnly);
102            }
103
104            // Restore stack.
105            std::mem::swap(&mut stack, &mut stack_copy);
106
107            // stack cannot be empty here, because if it was the
108            // P2SH  HASH <> EQUAL  scriptPubKey would be evaluated with
109            // an empty stack and the EvalScript above would return false.
110            assert!(!stack.is_empty());
111
112            let pubkey_serialized = stack.pop()?;
113            let pubkey2 = Script::from_bytes(&pubkey_serialized);
114
115            eval_script(
116                &mut stack,
117                pubkey2,
118                flags,
119                checker,
120                SigVersion::Base,
121                &mut ScriptExecutionData::default(),
122            )?;
123
124            if stack.is_empty() {
125                return Err(Error::EvalFalse);
126            }
127
128            if !stack.peek_bool()? {
129                return Err(Error::EvalFalse);
130            }
131
132            // P2SH witness program
133            if flags.intersects(VerifyFlags::WITNESS) {
134                if let Some(witness_program) = parse_witness_program(pubkey2)? {
135                    had_witness = true;
136                    let mut push_bytes = PushBytesBuf::new();
137                    push_bytes
138                        .extend_from_slice(pubkey2.as_bytes())
139                        .expect("Failed to convert pubkey to PushBytes");
140                    let redeem_script = Builder::default().push_slice(push_bytes).into_script();
141
142                    if script_sig != &redeem_script {
143                        // The scriptSig must be _exactly_ a single push of the redeemScript. Otherwise
144                        // we reintroduce malleability.
145                        return Err(Error::WitnessMalleatedP2SH);
146                    }
147
148                    verify_witness_program(witness, witness_program, flags, checker, true)?;
149
150                    // Bypass the cleanstack check at the end. The actual stack is obviously not clean
151                    // for witness programs.
152                    stack.truncate(1);
153                }
154            }
155        }
156        _ => {}
157    }
158
159    // The CLEANSTACK check is only performed after potential P2SH evaluation,
160    // as the non-P2SH evaluation of a P2SH script will obviously not result in
161    // a clean stack (the P2SH inputs remain). The same holds for witness evaluation.
162    if flags.intersects(VerifyFlags::CLEANSTACK) {
163        // Disallow CLEANSTACK without P2SH, as otherwise a switch CLEANSTACK->P2SH+CLEANSTACK
164        // would be possible, which is not a softfork (and P2SH should be one).
165        assert!(
166            flags.verify_p2sh() && flags.verify_witness(),
167            "Disallow CLEANSTACK without P2SH"
168        );
169        if stack.len() != 1 {
170            return Err(Error::CleanStack);
171        }
172    }
173
174    if flags.intersects(VerifyFlags::WITNESS) {
175        // We can't check for correct unexpected witness data if P2SH was off, so require
176        // that WITNESS implies P2SH. Otherwise, going from WITNESS->P2SH+WITNESS would be
177        // possible, which is not a softfork.
178        assert!(flags.verify_p2sh());
179        if !had_witness && !witness.is_empty() {
180            return Err(Error::WitnessUnexpected);
181        }
182    }
183
184    // Only return Ok(()) at the end after all checks pass.
185    Ok(())
186}
187
188fn parse_witness_program(script_pubkey: &Script) -> Result<Option<WitnessProgram>, Error> {
189    use bitcoin::script::witness_program::Error as WitnessProgramError;
190
191    match script_pubkey.witness_version() {
192        Some(version) => match WitnessProgram::new(version, &script_pubkey.as_bytes()[2..]) {
193            Ok(witness_program) => Ok(Some(witness_program)),
194            Err(
195                WitnessProgramError::InvalidLength(_)
196                | WitnessProgramError::InvalidSegwitV0Length(_),
197            ) => Err(Error::WitnessProgramWrongLength),
198            Err(err) => unreachable!("Unknown witness program error: {err:?}"),
199        },
200        None => Ok(None),
201    }
202}
203
204fn verify_witness_program(
205    witness: &Witness,
206    witness_program: WitnessProgram,
207    flags: &VerifyFlags,
208    checker: &mut impl SignatureChecker,
209    is_p2sh: bool,
210) -> Result<(), Error> {
211    // TODO: since we clone the entire witness data, we use stack.pop() later instead of
212    // SpanPopBack(stack) in Bitcoin Core. Perhaps avoid this allocation later.
213    let mut witness_stack = Stack::with_data(witness.to_vec());
214
215    let witness_version = witness_program.version();
216    let program = witness_program.program();
217
218    if witness_version == WitnessVersion::V0 {
219        let program_size = program.len();
220
221        if program_size == WITNESS_V0_SCRIPTHASH_SIZE {
222            // BIP141 P2WSH: 32-byte witness v0 program (which encodes SHA256(script))
223            if witness_stack.is_empty() {
224                return Err(Error::WitnessProgramWitnessEmpty);
225            }
226
227            let witness_script = witness_stack.pop()?;
228            let exec_script = Script::from_bytes(&witness_script);
229
230            let exec_script_hash: [u8; 32] = exec_script.wscript_hash().to_byte_array();
231
232            if exec_script_hash.as_slice() != program.as_bytes() {
233                return Err(Error::WitnessProgramMismatch);
234            }
235
236            execute_witness_script(
237                &witness_stack,
238                exec_script,
239                flags,
240                SigVersion::WitnessV0,
241                checker,
242                &mut ScriptExecutionData::default(),
243            )?;
244        } else if program_size == WITNESS_V0_KEYHASH_SIZE {
245            // BIP141 P2WPKH: 20-byte witness v0 program (which encodes Hash160(pubkey))
246            //
247            // ScriptPubKey: 0 <20-byte-PublicKeyHash>
248            // ScriptSig: (empty)
249            // Witness: <Signature> <PublicKey>
250            if witness_stack.len() != 2 {
251                return Err(Error::WitnessProgramMismatch);
252            }
253
254            let exec_script = Builder::default()
255                .push_opcode(OP_DUP)
256                .push_opcode(OP_HASH160)
257                .push_slice(program)
258                .push_opcode(OP_EQUALVERIFY)
259                .push_opcode(OP_CHECKSIG)
260                .into_script();
261
262            execute_witness_script(
263                &witness_stack,
264                &exec_script,
265                flags,
266                SigVersion::WitnessV0,
267                checker,
268                &mut ScriptExecutionData::default(),
269            )?;
270        } else {
271            unreachable!(
272                "Witness program length must be correct as checked in WitnessProgram::new(); qed"
273            )
274        }
275    } else if witness_version == WitnessVersion::V1
276        && program.len() == WITNESS_V0_TAPROOT_SIZE
277        && !is_p2sh
278    {
279        // BIP 341 Taproot: 32-byte non-P2SH witness v1 program (which encodes a P2C-tweaked pubkey)
280        // https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki#script-validation-rules
281        if !flags.intersects(VerifyFlags::TAPROOT) {
282            return Ok(());
283        }
284
285        if witness_stack.is_empty() {
286            return Err(Error::WitnessProgramWitnessEmpty);
287        }
288
289        let mut exec_data = if witness_stack.len() >= 2
290            && !witness_stack.last()?.is_empty()
291            && witness_stack.last()?[0] == TAPROOT_ANNEX_PREFIX
292        {
293            // Drop annex (this is non-standard; see IsWitnessStandard
294            let annex = witness_stack.pop()?;
295            ScriptExecutionData {
296                annex_hash: bitcoin::hashes::sha256::Hash::hash(&annex),
297                annex_present: true,
298                annex: Some(annex),
299                ..Default::default()
300            }
301        } else {
302            ScriptExecutionData::default()
303        };
304
305        exec_data.annex_init = true;
306
307        if witness_stack.len() == 1 {
308            // Key path spending (stack size is 1 after removing optional annex).
309            let sig = witness_stack.last()?;
310            let sig = SchnorrSignature::from_slice(sig).map_err(Error::SchnorrSignature)?;
311            let pubkey =
312                XOnlyPublicKey::from_slice(program.as_bytes()).map_err(Error::Secp256k1)?;
313            checker.check_schnorr_signature(&sig, &pubkey, SigVersion::Taproot, &exec_data)?;
314        } else {
315            // Script path spending (stack size is >1 after removing optional annex).
316            let control = witness_stack.pop()?;
317            let script = witness_stack.pop()?;
318
319            if control.len() < TAPROOT_CONTROL_BASE_SIZE
320                || control.len() > TAPROOT_CONTROL_MAX_SIZE
321                || ((control.len() - TAPROOT_CONTROL_BASE_SIZE) % TAPROOT_CONTROL_NODE_SIZE != 0)
322            {
323                return Err(Error::TaprootWrongControlSize);
324            }
325
326            let script = Script::from_bytes(&script);
327
328            let leaf_version = control[0] & TAPROOT_LEAF_MASK;
329
330            // ComputeTapleafHash
331            exec_data.tapleaf_hash = TapLeafHash::from_script(
332                script,
333                LeafVersion::from_consensus(leaf_version).expect("Failed to compute leaf version"),
334            );
335
336            // VerifyTaprootCommitment
337            let control_block = ControlBlock::decode(&control).map_err(Error::Taproot)?;
338            let output_key =
339                XOnlyPublicKey::from_slice(program.as_bytes()).map_err(Error::Secp256k1)?;
340            if !control_block.verify_taproot_commitment(&SECP, output_key, script) {
341                return Err(Error::WitnessProgramMismatch);
342            }
343            exec_data.tapleaf_hash_init = true;
344
345            if leaf_version == TAPROOT_LEAF_TAPSCRIPT {
346                // Tapscript (leaf version 0xc0)
347                exec_data.validation_weight_left = witness.size() as i64 + VALIDATION_WEIGHT_OFFSET;
348                exec_data.validation_weight_left_init = true;
349                let exec_script = script;
350                return execute_witness_script(
351                    &witness_stack,
352                    exec_script,
353                    flags,
354                    SigVersion::Tapscript,
355                    checker,
356                    &mut exec_data,
357                );
358            }
359
360            if flags.intersects(VerifyFlags::DISCOURAGE_UPGRADABLE_TAPROOT_VERSION) {
361                return Err(Error::DiscourageUpgradableTaprootVersion);
362            }
363        }
364    } else if flags.intersects(VerifyFlags::DISCOURAGE_UPGRADABLE_WITNESS_PROGRAM) {
365        return Err(Error::DiscourageUpgradableWitnessProgram);
366    }
367
368    // Other version/size/p2sh combinations returns true for future softfork compatibility.
369    // Ok(true)?
370    Ok(())
371}
372
373fn execute_witness_script(
374    stack_span: &[Vec<u8>],
375    exec_script: &Script,
376    flags: &VerifyFlags,
377    sig_version: SigVersion,
378    checker: &mut impl SignatureChecker,
379    exec_data: &mut ScriptExecutionData,
380) -> Result<(), Error> {
381    let mut stack = Stack::new(stack_span.to_vec(), true);
382
383    if sig_version == SigVersion::Tapscript {
384        // OP_SUCCESSx processing overrides everything, including stack element size limits
385        for instruction in exec_script.instructions() {
386            match instruction.map_err(Error::ReadInstruction)? {
387                Instruction::Op(opcode) => {
388                    // New opcodes will be listed here. May use a different sigversion to modify existing opcodes.
389                    if is_op_success(opcode.to_u8()) {
390                        if flags.intersects(VerifyFlags::DISCOURAGE_OP_SUCCESS) {
391                            return Err(Error::DiscourageOpSuccess);
392                        }
393                        return Ok(());
394                    }
395                }
396                Instruction::PushBytes(_) => return Err(Error::BadOpcode),
397            }
398        }
399
400        // Tapscript enforces initial stack size limits (altstack is empty here)
401        if stack.len() > MAX_STACK_SIZE {
402            return Err(Error::StackSize);
403        }
404    }
405
406    // Disallow stack item size > MAX_SCRIPT_ELEMENT_SIZE in witness stack
407    if stack
408        .iter()
409        .any(|elem| elem.len() > MAX_SCRIPT_ELEMENT_SIZE)
410    {
411        return Err(Error::PushSize);
412    }
413
414    // Run the script interpreter.
415    eval_script(
416        &mut stack,
417        exec_script,
418        flags,
419        checker,
420        sig_version,
421        exec_data,
422    )?;
423
424    // Scripts inside witness implicitly require cleanstack behavior
425    if stack.len() != 1 {
426        return Err(Error::CleanStack);
427    }
428
429    if !stack.peek_bool()? {
430        return Err(Error::EvalFalse);
431    }
432
433    Ok(())
434}
435
436fn is_op_success(opcode: u8) -> bool {
437    (opcode == 0x50) || (0x7b..=0xb9).contains(&opcode)
438}
subcoin_script/interpreter.rs

subcoin_script/
interpreter.rs
