blvm_consensus/script/
templates.rs

1//! Structural script-template scanner.
2//!
3//! Matches frequent script *shapes* (unexecuted IF + CHECKSIG remainder, OP_RETURN
4//! prefixes, data-like n-of-m). Matching a template is not a protocol change and
5//! does not interpret application-layer meaning.
6
7use crate::error::Result;
8use crate::opcodes::*;
9use crate::script::{is_op_success, is_push_opcode, op_advance};
10use crate::types::{ByteString, Transaction};
11
12/// Known `OP_RETURN` payload prefixes (bytes after the push opcode, not brand names).
13pub const NULLDATA_CNTRPRTY: &[u8] = b"CNTRPRTY";
14pub const NULLDATA_OMNI: &[u8] = b"omni";
15/// OpenTimestamps Bitcoin attestation tag (TimeAttestation.TAG).
16pub const NULLDATA_OTS: &[u8] = &[0x05, 0x88, 0x96, 0x0d, 0x73, 0xd7, 0x19, 0x01];
17
18const NULLDATA_MAGICS: &[&[u8]] = &[NULLDATA_CNTRPRTY, NULLDATA_OMNI, NULLDATA_OTS];
19
20/// Parse result for a single script (spans live here, not on policy labels).
21#[derive(Debug, Clone, PartialEq, Eq)]
22pub enum ScriptTemplate {
23    UnexecIf {
24        start: usize,
25        end: usize,
26        remainder: UnexecIfRemainder,
27    },
28    NullDataOp13,
29    NullDataMagic {
30        prefix: &'static [u8],
31    },
32    DataLikeMs {
33        n: u8,
34        m: u8,
35        data_like_keys: usize,
36    },
37    Unknown,
38}
39
40#[derive(Debug, Clone, Copy, PartialEq, Eq)]
41pub enum UnexecIfRemainder {
42    TapChecksig { pubkey: [u8; 32] },
43}
44
45/// Scan one script (tapscript, scriptPubKey, or witness element).
46pub fn scan(script: &[u8]) -> ScriptTemplate {
47    if script.is_empty() {
48        return ScriptTemplate::Unknown;
49    }
50    if let Some(t) = scan_unexec_if(script) {
51        return t;
52    }
53    if let Some(t) = scan_nulldata(script) {
54        return t;
55    }
56    if let Some(t) = scan_data_like_ms(script) {
57        return t;
58    }
59    ScriptTemplate::Unknown
60}
61
62/// Scan each witness element; first non-Unknown wins (UnexecIf is preferred).
63pub fn scan_witness<'a, I>(elements: I) -> ScriptTemplate
64where
65    I: IntoIterator<Item = &'a [u8]>,
66{
67    let mut first_other = ScriptTemplate::Unknown;
68    for el in elements {
69        match scan(el) {
70            u @ ScriptTemplate::UnexecIf { .. } => return u,
71            ScriptTemplate::Unknown => {}
72            other => {
73                if matches!(first_other, ScriptTemplate::Unknown) {
74                    first_other = other;
75                }
76            }
77        }
78    }
79    first_other
80}
81
82/// Classify a transaction: witnesses first, then outputs. First non-Unknown wins.
83pub fn scan_tx(tx: &Transaction, witnesses: Option<&[crate::witness::Witness]>) -> ScriptTemplate {
84    if let Some(wits) = witnesses {
85        for w in wits {
86            let hit = scan_witness(w.iter().map(|e| e.as_ref()));
87            if !matches!(hit, ScriptTemplate::Unknown) {
88                return hit;
89            }
90        }
91    }
92    for out in &tx.outputs {
93        let hit = scan(out.script_pubkey.as_ref());
94        if !matches!(hit, ScriptTemplate::Unknown) {
95            return hit;
96        }
97    }
98    ScriptTemplate::Unknown
99}
100
101fn has_op_success(script: &[u8]) -> bool {
102    let mut pc = 0usize;
103    while pc < script.len() {
104        if is_op_success(script[pc]) {
105            return true;
106        }
107        let adv = op_advance(script, pc);
108        if adv == 0 {
109            return true;
110        }
111        pc = pc.saturating_add(adv);
112        if pc > script.len() {
113            return true;
114        }
115    }
116    false
117}
118
119fn scan_unexec_if(script: &[u8]) -> Option<ScriptTemplate> {
120    if has_op_success(script) {
121        return None;
122    }
123    let (start, end) = find_single_unexec_if(script)?;
124    let remainder = match_tap_checksig_remainder(script, start, end)?;
125    Some(ScriptTemplate::UnexecIf {
126        start,
127        end,
128        remainder,
129    })
130}
131
132/// Exactly one `OP_0 OP_IF` … `OP_ENDIF` whose interior is data pushes only.
133fn find_single_unexec_if(script: &[u8]) -> Option<(usize, usize)> {
134    let mut pc = 0usize;
135    let mut found: Option<(usize, usize)> = None;
136    while pc < script.len() {
137        if pc + 1 < script.len() && script[pc] == OP_0 && script[pc + 1] == OP_IF {
138            let mut inner = pc + 2;
139            loop {
140                if inner >= script.len() {
141                    return None;
142                }
143                let op = script[inner];
144                if op == OP_ENDIF {
145                    let end = inner + 1;
146                    if found.is_some() {
147                        return None;
148                    }
149                    found = Some((pc, end));
150                    pc = end;
151                    break;
152                }
153                if op == OP_IF || op == OP_NOTIF || op == OP_ELSE {
154                    return None;
155                }
156                if !is_push_opcode(op) {
157                    return None;
158                }
159                let adv = op_advance(script, inner);
160                if adv == 0 || inner + adv > script.len() {
161                    return None;
162                }
163                inner += adv;
164            }
165        } else {
166            let adv = op_advance(script, pc);
167            if adv == 0 || pc + adv > script.len() {
168                return None;
169            }
170            pc += adv;
171        }
172    }
173    found
174}
175
176fn match_tap_checksig_remainder(
177    script: &[u8],
178    start: usize,
179    end: usize,
180) -> Option<UnexecIfRemainder> {
181    const LEAF_LEN: usize = 34;
182    if start == LEAF_LEN && end == script.len() {
183        return tap_checksig_leaf(&script[0..LEAF_LEN]);
184    }
185    if start == 0 && end + LEAF_LEN == script.len() {
186        return tap_checksig_leaf(&script[end..]);
187    }
188    None
189}
190
191fn tap_checksig_leaf(leaf: &[u8]) -> Option<UnexecIfRemainder> {
192    if leaf.len() != 34 || leaf[0] != PUSH_32_BYTES || leaf[33] != OP_CHECKSIG {
193        return None;
194    }
195    let mut pubkey = [0u8; 32];
196    pubkey.copy_from_slice(&leaf[1..33]);
197    Some(UnexecIfRemainder::TapChecksig { pubkey })
198}
199
200fn scan_nulldata(script: &[u8]) -> Option<ScriptTemplate> {
201    if script.is_empty() || script[0] != OP_RETURN {
202        return None;
203    }
204    if script.len() == 1 {
205        return None;
206    }
207    // `OP_RETURN OP_13` then zero or more pushes (runestone wrapper).
208    if script[1] == OP_13 {
209        let mut pc = 2usize;
210        while pc < script.len() {
211            if !is_push_opcode(script[pc]) {
212                return None;
213            }
214            let adv = op_advance(script, pc);
215            if adv == 0 || pc + adv > script.len() {
216                return None;
217            }
218            pc += adv;
219        }
220        return Some(ScriptTemplate::NullDataOp13);
221    }
222    let payload = push_payload_after_op_return(script)?;
223    for magic in NULLDATA_MAGICS {
224        if payload.starts_with(magic) {
225            return Some(ScriptTemplate::NullDataMagic { prefix: magic });
226        }
227    }
228    None
229}
230
231/// Bytes after `OP_RETURN` and its first push opcode (compact-size or small-int push).
232fn push_payload_after_op_return(script: &[u8]) -> Option<&[u8]> {
233    if script.len() < 2 {
234        return None;
235    }
236    let op = script[1];
237    match op {
238        0x01..=0x4b => {
239            let n = op as usize;
240            if script.len() < 2 + n {
241                return None;
242            }
243            Some(&script[2..2 + n])
244        }
245        0x4c => {
246            if script.len() < 3 {
247                return None;
248            }
249            let n = script[2] as usize;
250            if script.len() < 3 + n {
251                return None;
252            }
253            Some(&script[3..3 + n])
254        }
255        0x4d => {
256            if script.len() < 4 {
257                return None;
258            }
259            let n = u16::from_le_bytes([script[2], script[3]]) as usize;
260            if script.len() < 4 + n {
261                return None;
262            }
263            Some(&script[4..4 + n])
264        }
265        OP_1..=OP_16 | OP_0 => Some(&[]),
266        _ => None,
267    }
268}
269
270fn scan_data_like_ms(script: &[u8]) -> Option<ScriptTemplate> {
271    let (m, n, keys) = parse_bare_multisig_keys(script)?;
272    if keys.is_empty() {
273        return None;
274    }
275    let data_like = keys.iter().filter(|k| !looks_compressed_pubkey(k)).count();
276    if data_like != keys.len() {
277        return None;
278    }
279    Some(ScriptTemplate::DataLikeMs {
280        n,
281        m,
282        data_like_keys: data_like,
283    })
284}
285
286fn looks_compressed_pubkey(key: &[u8]) -> bool {
287    key.len() == 33 && (key[0] == 0x02 || key[0] == 0x03)
288}
289
290fn parse_bare_multisig_keys(script: &[u8]) -> Option<(u8, u8, Vec<&[u8]>)> {
291    if script.len() < 4 || script[script.len() - 1] != OP_CHECKMULTISIG {
292        return None;
293    }
294    let n_op = script[script.len() - 2];
295    if !(OP_1..=OP_16).contains(&n_op) {
296        return None;
297    }
298    let n = n_op - OP_1 + 1;
299    let m_op = script[0];
300    if !(OP_1..=OP_16).contains(&m_op) {
301        return None;
302    }
303    let m = m_op - OP_1 + 1;
304    if m == 0 || m > n {
305        return None;
306    }
307    let mut i = 1usize;
308    let mut keys = Vec::with_capacity(n as usize);
309    let trailer = script.len() - 2;
310    for _ in 0..n {
311        if i >= trailer {
312            return None;
313        }
314        let first = script[i];
315        let (start, len) = if (0x01..=0x4b).contains(&first) {
316            (i + 1, first as usize)
317        } else {
318            return None;
319        };
320        if start + len > trailer {
321            return None;
322        }
323        keys.push(&script[start..start + len]);
324        i = start + len;
325    }
326    if i != trailer {
327        return None;
328    }
329    Some((m, n, keys))
330}
331
332/// P2TR script-path: one UnexecIf + PUSH32 CHECKSIG remainder. Skips the interpreter walk.
333#[cfg(feature = "production")]
334#[allow(clippy::too_many_arguments)]
335pub fn try_verify_p2tr_unexec_if_fast_path(
336    script_sig: &ByteString,
337    script_pubkey: &[u8],
338    witness: &crate::witness::Witness,
339    _flags: u32,
340    tx: &Transaction,
341    input_index: usize,
342    prevout_values: &[i64],
343    prevout_script_pubkeys: &[&[u8]],
344    block_height: Option<u64>,
345    network: crate::types::Network,
346    schnorr_collector: Option<&crate::bip348::SchnorrSignatureCollector>,
347) -> Option<Result<bool>> {
348    use crate::activation::taproot_active_at_height;
349    use crate::taproot::parse_taproot_script_path_witness;
350
351    if !taproot_active_at_height(block_height, network) {
352        return None;
353    }
354    if script_pubkey.len() != 34 || script_pubkey[0] != OP_1 || script_pubkey[1] != PUSH_32_BYTES {
355        return None;
356    }
357    if !script_sig.is_empty() {
358        return None;
359    }
360    if witness.len() < 2 {
361        return None;
362    }
363    let mut output_key = [0u8; 32];
364    output_key.copy_from_slice(&script_pubkey[2..34]);
365    let (witness_body, annex_hash) = crate::taproot::strip_taproot_annex(witness);
366    let parsed = match parse_taproot_script_path_witness(&witness_body, &output_key) {
367        Ok(Some(p)) => p,
368        Ok(None) | Err(_) => return None,
369    };
370    let (tapscript, stack_items, control_block) = parsed;
371    if control_block.leaf_version != crate::taproot::TAPROOT_LEAF_VERSION_TAPSCRIPT {
372        return None;
373    }
374    if stack_items.len() != 1 {
375        return None;
376    }
377    let ScriptTemplate::UnexecIf {
378        remainder: UnexecIfRemainder::TapChecksig { pubkey },
379        ..
380    } = scan(tapscript.as_ref())
381    else {
382        return None;
383    };
384    let (sig_bytes, sighash_type) =
385        crate::bip348::try_parse_taproot_schnorr_witness_sig(stack_items[0].as_ref())?;
386    let sighash = crate::taproot::compute_tapscript_signature_hash(
387        tx,
388        input_index,
389        prevout_values,
390        prevout_script_pubkeys,
391        tapscript.as_ref(),
392        control_block.leaf_version,
393        0xffff_ffff,
394        sighash_type,
395        annex_hash.as_ref(),
396    )
397    .ok()?;
398    let result = crate::bip348::verify_tapscript_schnorr_signature(
399        &sighash,
400        &pubkey,
401        &sig_bytes,
402        schnorr_collector,
403    );
404    Some(result)
405}
406
407#[cfg(test)]
408mod tests {
409    use super::*;
410
411    fn push32_checksig(pk: [u8; 32]) -> Vec<u8> {
412        let mut s = vec![PUSH_32_BYTES];
413        s.extend_from_slice(&pk);
414        s.push(OP_CHECKSIG);
415        s
416    }
417
418    fn envelope(body: &[u8]) -> Vec<u8> {
419        let mut s = vec![OP_0, OP_IF];
420        s.extend_from_slice(body);
421        s.push(OP_ENDIF);
422        s
423    }
424
425    #[test]
426    fn unexec_if_suffix_checksig() {
427        let pk = [0x11u8; 32];
428        let mut script = envelope(&[0x03, b'o', b'r', b'd']);
429        script.extend(push32_checksig(pk));
430        match scan(&script) {
431            ScriptTemplate::UnexecIf {
432                remainder: UnexecIfRemainder::TapChecksig { pubkey },
433                ..
434            } => assert_eq!(pubkey, pk),
435            other => panic!("expected UnexecIf, got {other:?}"),
436        }
437    }
438
439    #[test]
440    fn unexec_if_prefix_checksig() {
441        let pk = [0x22u8; 32];
442        let mut script = push32_checksig(pk);
443        script.extend(envelope(&[0x03, b'o', b'r', b'd']));
444        match scan(&script) {
445            ScriptTemplate::UnexecIf {
446                remainder: UnexecIfRemainder::TapChecksig { pubkey },
447                ..
448            } => assert_eq!(pubkey, pk),
449            other => panic!("expected UnexecIf, got {other:?}"),
450        }
451    }
452
453    #[test]
454    fn two_envelopes_unknown() {
455        let mut script = envelope(&[0x01, 0xaa]);
456        script.extend(envelope(&[0x01, 0xbb]));
457        script.extend(push32_checksig([0x33; 32]));
458        assert_eq!(scan(&script), ScriptTemplate::Unknown);
459    }
460
461    #[test]
462    fn nested_if_unknown() {
463        let mut script = vec![OP_0, OP_IF, OP_0, OP_IF, OP_ENDIF, OP_ENDIF];
464        script.extend(push32_checksig([0x44; 32]));
465        assert_eq!(scan(&script), ScriptTemplate::Unknown);
466    }
467
468    #[test]
469    fn leftover_opcode_unknown() {
470        let mut script = envelope(&[0x01, 0xaa]);
471        script.push(OP_DUP);
472        script.extend(push32_checksig([0x55; 32]));
473        assert_eq!(scan(&script), ScriptTemplate::Unknown);
474    }
475
476    #[test]
477    fn leftover_after_checksig_unknown() {
478        let mut script = envelope(&[0x01, 0xaa]);
479        script.extend(push32_checksig([0x55; 32]));
480        script.push(OP_DROP);
481        assert_eq!(scan(&script), ScriptTemplate::Unknown);
482    }
483
484    #[test]
485    fn op_success_unknown() {
486        // 0xba is OP_SUCCESS in tapscript (187..=254).
487        let mut script = vec![OP_0, OP_IF, 0xba, OP_ENDIF];
488        script.extend(push32_checksig([0x66; 32]));
489        assert_eq!(scan(&script), ScriptTemplate::Unknown);
490    }
491
492    #[test]
493    fn nulldata_op13() {
494        let script = vec![OP_RETURN, OP_13, 0x01, 0xff];
495        assert_eq!(scan(&script), ScriptTemplate::NullDataOp13);
496    }
497
498    #[test]
499    fn nulldata_cntrprty() {
500        let mut script = vec![OP_RETURN, NULLDATA_CNTRPRTY.len() as u8];
501        script.extend_from_slice(NULLDATA_CNTRPRTY);
502        match scan(&script) {
503            ScriptTemplate::NullDataMagic { prefix } => assert_eq!(prefix, NULLDATA_CNTRPRTY),
504            other => panic!("expected NullDataMagic, got {other:?}"),
505        }
506    }
507
508    #[test]
509    fn data_like_ms_all_invalid_prefix() {
510        // 1-of-2 with 8-byte "keys" (not 02/03+32).
511        let mut script = vec![OP_1, 0x08];
512        script.extend_from_slice(&[0x11; 8]);
513        script.push(0x08);
514        script.extend_from_slice(&[0x22; 8]);
515        script.push(OP_2);
516        script.push(OP_CHECKMULTISIG);
517        match scan(&script) {
518            ScriptTemplate::DataLikeMs {
519                n,
520                m,
521                data_like_keys,
522            } => {
523                assert_eq!((m, n, data_like_keys), (1, 2, 2));
524            }
525            other => panic!("expected DataLikeMs, got {other:?}"),
526        }
527    }
528
529    #[test]
530    fn real_compressed_key_not_data_like() {
531        let mut script = vec![OP_1, PUSH_33_BYTES, 0x02];
532        script.extend_from_slice(&[0xab; 32]);
533        script.push(OP_1);
534        script.push(OP_CHECKMULTISIG);
535        assert_eq!(scan(&script), ScriptTemplate::Unknown);
536    }
537}
blvm_consensus/script/templates.rs

blvm_consensus/script/
templates.rs
