bitcoin_script_analyzer/
expr.rs

1use crate::{
2    context::{ScriptContext, ScriptRules, ScriptVersion},
3    opcode::{opcodes, Opcode},
4    script::convert::{
5        check_int, decode_bool, decode_int_unchecked, encode_bool, encode_int, FALSE, TRUE,
6    },
7    script_error::ScriptError,
8    util::checksig::{
9        check_pub_key, is_valid_signature_encoding, PubKeyCheckResult, SIG_HASH_TYPES,
10    },
11};
12use bitcoin_hashes::{ripemd160, sha1, sha256, Hash};
13use core::{cmp::Ordering, fmt, mem::replace, ops::Deref};
14
15#[derive(Clone, Debug, PartialEq, Eq)]
16pub enum Expr {
17    Op(OpExpr),
18    Stack(StackExpr),
19    Bytes(BytesExpr),
20}
21
22impl Expr {
23    pub fn stack(pos: u32) -> Self {
24        Self::Stack(StackExpr {
25            pos,
26            //data: ExprData::new(),
27        })
28    }
29
30    pub fn bytes(bytes: &[u8]) -> Self {
31        Self::Bytes(BytesExpr(bytes.to_vec().into_boxed_slice()))
32    }
33
34    pub fn bytes_owned(bytes: Box<[u8]>) -> Self {
35        Self::Bytes(BytesExpr(bytes))
36    }
37}
38
39#[derive(Clone, Copy, Debug, PartialEq, Eq)]
40#[allow(non_camel_case_types)]
41pub enum Opcode1 {
42    OP_SIZE = 0x82,
43
44    OP_ABS = 0x90,
45    OP_NOT = 0x91,
46    OP_0NOTEQUAL = 0x92,
47
48    OP_RIPEMD160 = 0xa6,
49    OP_SHA1 = 0xa7,
50    OP_SHA256 = 0xa8,
51
52    OP_CHECKLOCKTIMEVERIFY = 0xb1,
53    OP_CHECKSEQUENCEVERIFY = 0xb2,
54
55    OP_INTERNAL_NOT = 0xfe,
56}
57
58impl Opcode1 {
59    pub fn expr(self, arg: Box<[Expr; 1]>) -> Expr {
60        Expr::Op(OpExpr::new(OpExprArgs::Args1(self, arg), None))
61    }
62}
63
64#[derive(Clone, Copy, Debug, PartialEq, Eq)]
65#[allow(non_camel_case_types)]
66pub enum Opcode2 {
67    OP_EQUAL = 0x87,
68
69    OP_ADD = 0x93,
70    OP_SUB = 0x94,
71
72    OP_BOOLAND = 0x9a,
73    OP_BOOLOR = 0x9b,
74    OP_NUMEQUAL = 0x9c,
75    OP_NUMNOTEQUAL = 0x9e,
76    OP_LESSTHAN = 0x9f,
77    OP_LESSTHANOREQUAL = 0xa1,
78    OP_MIN = 0xa3,
79    OP_MAX = 0xa4,
80
81    OP_CHECKSIG = 0xac,
82}
83
84impl Opcode2 {
85    pub fn expr(self, args: Box<[Expr; 2]>) -> Expr {
86        Expr::Op(OpExpr::new(OpExprArgs::Args2(self, args), None))
87    }
88
89    pub fn expr_with_error(self, args: Box<[Expr; 2]>, error: ScriptError) -> Expr {
90        Expr::Op(OpExpr::new(OpExprArgs::Args2(self, args), Some(error)))
91    }
92}
93
94#[derive(Clone, Copy, Debug, PartialEq, Eq)]
95#[allow(non_camel_case_types)]
96pub enum Opcode3 {
97    OP_WITHIN = 0xa5,
98}
99
100impl Opcode3 {
101    pub fn expr(self, args: Box<[Expr; 3]>) -> Expr {
102        Expr::Op(OpExpr::new(OpExprArgs::Args3(self, args), None))
103    }
104}
105
106#[derive(Clone, Debug, PartialEq, Eq)]
107pub struct MultisigArgs {
108    exprs: Box<[Expr]>,
109    pk_offset: usize,
110}
111
112impl MultisigArgs {
113    pub fn expr(exprs: Box<[Expr]>, pk_offset: usize) -> Expr {
114        Expr::Op(OpExpr::new(
115            OpExprArgs::Multisig(Self { exprs, pk_offset }),
116            None,
117        ))
118    }
119
120    /// Used with [`replace`] instead of [`take`] because implementing [`Default`] and returning
121    /// this does not make sense.
122    ///
123    /// [`replace`]: core::mem::replace
124    /// [`take`]: core::mem::take
125    pub fn valid_garbage() -> Self {
126        Self {
127            exprs: Box::new([]),
128            pk_offset: 0,
129        }
130    }
131}
132
133impl MultisigArgs {
134    pub fn sigs(&self) -> &[Expr] {
135        &self.exprs[..self.pk_offset]
136    }
137
138    pub fn keys(&self) -> &[Expr] {
139        &self.exprs[self.pk_offset..]
140    }
141
142    pub fn into_vecs(self) -> (Vec<Expr>, Vec<Expr>) {
143        let mut sigs = self.exprs.into_vec();
144        let pks = sigs.split_off(self.pk_offset);
145
146        (sigs, pks)
147    }
148}
149
150#[derive(Clone, Debug, PartialEq, Eq)]
151pub enum OpExprArgs {
152    Args1(Opcode1, Box<[Expr; 1]>),
153    Args2(Opcode2, Box<[Expr; 2]>),
154    Args3(Opcode3, Box<[Expr; 3]>),
155    Multisig(MultisigArgs),
156}
157
158#[derive(Clone, Debug, PartialEq, Eq)]
159pub struct OpExpr {
160    pub args: OpExprArgs,
161    error: Option<ScriptError>,
162    //data: ExprData,
163}
164
165impl OpExpr {
166    pub fn new(args: OpExprArgs, error: Option<ScriptError>) -> Self {
167        Self { args, error }
168    }
169
170    pub fn opcode(&self) -> Opcode {
171        Opcode {
172            opcode: match self.args {
173                OpExprArgs::Args1(op, _) => op as u8,
174                OpExprArgs::Args2(op, _) => op as u8,
175                OpExprArgs::Args3(op, _) => op as u8,
176                OpExprArgs::Multisig(_) => return opcodes::OP_CHECKMULTISIG,
177            },
178        }
179    }
180
181    pub fn args(&self) -> &[Expr] {
182        match &self.args {
183            OpExprArgs::Args1(_, args) => &**args,
184            OpExprArgs::Args2(_, args) => &**args,
185            OpExprArgs::Args3(_, args) => &**args,
186            OpExprArgs::Multisig(m) => &m.exprs,
187        }
188    }
189
190    pub fn args_mut(&mut self) -> &mut [Expr] {
191        match &mut self.args {
192            OpExprArgs::Args1(_, args) => &mut **args,
193            OpExprArgs::Args2(_, args) => &mut **args,
194            OpExprArgs::Args3(_, args) => &mut **args,
195            OpExprArgs::Multisig(m) => &mut m.exprs,
196        }
197    }
198}
199
200#[derive(Clone, Debug, PartialEq, Eq)]
201pub struct StackExpr {
202    pos: u32,
203    //data: ExprData,
204}
205
206#[derive(Clone, Debug, PartialEq, Eq)]
207pub struct BytesExpr(Box<[u8]>);
208
209impl Deref for BytesExpr {
210    type Target = [u8];
211
212    fn deref(&self) -> &Self::Target {
213        &self.0
214    }
215}
216
217#[derive(Clone, Debug, PartialEq, Eq)]
218pub struct ExprData {
219    uses: Vec<ExprUsage>,
220    // TODO lenghts, values
221}
222
223/*
224impl ExprData {
225    pub fn new() -> Self {
226        Self { uses: Vec::new() }
227    }
228}*/
229
230// TODO do something with this
231#[derive(Clone, Debug, PartialEq, Eq)]
232pub enum ExprUsage {
233    //Pubkey,
234    //Preimage,
235    //Signature,
236}
237
238impl fmt::Display for OpExpr {
239    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
240        fn write_args(f: &mut fmt::Formatter<'_>, args: &[Expr]) -> fmt::Result {
241            let mut first = true;
242
243            for e in args {
244                if !first {
245                    write!(f, ", ")?;
246                }
247                first = false;
248                write!(f, "{e}")?;
249            }
250
251            Ok(())
252        }
253
254        write!(f, "{}(", self.opcode())?;
255
256        if let OpExprArgs::Multisig(args) = &self.args {
257            write!(f, "sigs=[")?;
258            write_args(f, args.sigs())?;
259            write!(f, "], pubkeys=[")?;
260            write_args(f, args.keys())?;
261            write!(f, "]")?;
262        } else {
263            write_args(f, self.args())?;
264        }
265
266        write!(f, ")")
267    }
268}
269
270impl fmt::Display for StackExpr {
271    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
272        write!(f, "<stack item #{}>", self.pos)
273    }
274}
275
276impl fmt::Display for BytesExpr {
277    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
278        write!(f, "<")?;
279        for byte in &**self {
280            write!(f, "{:02x}", byte)?;
281        }
282        write!(f, ">")
283    }
284}
285
286impl fmt::Display for Expr {
287    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
288        match self {
289            Expr::Op(e) => write!(f, "{e}"),
290            Expr::Stack(e) => write!(f, "{e}"),
291            Expr::Bytes(e) => write!(f, "{e}"),
292        }
293    }
294}
295
296impl PartialOrd for Expr {
297    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
298        Some(self.cmp(other))
299    }
300}
301
302impl Ord for Expr {
303    fn cmp(&self, other: &Self) -> Ordering {
304        match (self, other) {
305            (Self::Op(a), Self::Op(b)) => {
306                // smallest opcode first
307                match a.opcode().cmp(&b.opcode()) {
308                    Ordering::Equal => {}
309                    ord => return ord,
310                }
311
312                // TODO opcodes are equal, so amount of args is equal, except for checkmultisig, check this
313                match a.args().len().cmp(&b.args().len()) {
314                    Ordering::Equal => {}
315                    ord => return ord,
316                }
317
318                for i in 0..a.args().len() {
319                    match a.args()[i].cmp(&b.args()[i]) {
320                        Ordering::Equal => {}
321                        ord => return ord,
322                    }
323                }
324
325                Ordering::Equal
326            }
327            (Self::Stack(a), Self::Stack(b)) => a.pos.cmp(&b.pos),
328            (Self::Bytes(a), Self::Bytes(b)) => a.cmp(b),
329            (a, b) => b.priority().cmp(&a.priority()),
330        }
331    }
332}
333
334impl Expr {
335    pub fn priority(&self) -> u8 {
336        match self {
337            Expr::Bytes(_) => 0,
338            Expr::Stack(_) => 1,
339            Expr::Op(_) => 2,
340        }
341    }
342
343    /// Used with [`replace`] instead of [`take`] because implementing [`Default`] and returning
344    /// this does not make sense.
345    ///
346    /// [`replace`]: core::mem::replace
347    /// [`take`]: core::mem::take
348    pub fn valid_garbage() -> Self {
349        Self::Stack(StackExpr { pos: u32::MAX })
350    }
351
352    pub fn sort_recursive(exprs: &mut [Expr]) {
353        Self::sort_recursive_(exprs, true);
354    }
355
356    pub fn sort_recursive_(exprs: &mut [Expr], sort_current: bool) {
357        if sort_current {
358            exprs.sort_unstable();
359        }
360        for expr in exprs {
361            if let Self::Op(expr) = expr {
362                let sort_next = expr.opcode().can_reorder_args();
363                Self::sort_recursive_(expr.args_mut(), sort_next);
364            }
365        }
366    }
367
368    pub fn eval(&mut self, ctx: ScriptContext) -> Result<bool, ScriptError> {
369        self.eval_(ctx, 0)
370    }
371
372    fn eval_(&mut self, ctx: ScriptContext, depth: usize) -> Result<bool, ScriptError> {
373        let mut changed = false;
374        if let Expr::Op(ref mut op) = self {
375            for arg in op.args_mut() {
376                changed |= arg.eval_(ctx, depth + 1)?;
377            }
378            match &mut op.args {
379                OpExprArgs::Args1(op, args) => {
380                    let arg = &mut args[0];
381                    match op {
382                        Opcode1::OP_SIZE => {
383                            match arg {
384                                Expr::Bytes(b) => {
385                                    *self = Expr::bytes_owned(encode_int(b.len() as i64));
386                                    return Ok(true);
387                                }
388                                Expr::Op(op) if op.opcode().returns_boolean() => {
389                                    *self = replace(arg, Self::valid_garbage());
390                                    return Ok(true);
391                                }
392                                _ => {}
393                            };
394                        }
395
396                        Opcode1::OP_RIPEMD160 | Opcode1::OP_SHA1 | Opcode1::OP_SHA256 => {
397                            if let Expr::Bytes(b) = arg {
398                                let hash: Box<[u8]> = match op {
399                                    Opcode1::OP_RIPEMD160 | Opcode1::OP_SHA1 => {
400                                        let hash = match op {
401                                            Opcode1::OP_RIPEMD160 => {
402                                                ripemd160::Hash::hash(b).to_byte_array()
403                                            }
404                                            Opcode1::OP_SHA1 => sha1::Hash::hash(b).to_byte_array(),
405                                            _ => unreachable!(),
406                                        };
407                                        Box::new(hash)
408                                    }
409                                    Opcode1::OP_SHA256 => {
410                                        let hash = sha256::Hash::hash(b).to_byte_array();
411                                        Box::new(hash)
412                                    }
413                                    _ => unreachable!(),
414                                };
415
416                                *self = Expr::bytes_owned(hash);
417                                return Ok(true);
418                            }
419                        }
420
421                        Opcode1::OP_INTERNAL_NOT | Opcode1::OP_NOT => {
422                            if let Expr::Bytes(arg) = arg {
423                                return if *op == Opcode1::OP_NOT && arg.len() > 4 {
424                                    Err(ScriptError::SCRIPT_ERR_NUM_OVERFLOW)
425                                } else {
426                                    *self = Expr::bytes(encode_bool(!decode_bool(arg)));
427                                    Ok(true)
428                                };
429                            }
430                            if let Expr::Op(arg) = arg {
431                                if let OpExprArgs::Args1(op, arg) = &arg.args {
432                                    if (*op == Opcode1::OP_NOT || *op == Opcode1::OP_INTERNAL_NOT)
433                                        && match &arg[0] {
434                                            Expr::Op(op) => op.opcode().returns_boolean(),
435                                            Expr::Stack(_) => depth == 0,
436                                            _ => false,
437                                        }
438                                    {
439                                        *self = arg[0].clone();
440                                        return Ok(true);
441                                    }
442                                }
443                            }
444                            if let Expr::Op(arg) = arg {
445                                if depth == 0 && ctx.rules == ScriptRules::All {
446                                    if let OpExprArgs::Args2(Opcode2::OP_CHECKSIG, args) = &arg.args
447                                    {
448                                        // assumes valid pubkey TODO fix
449                                        *self = Opcode2::OP_EQUAL
450                                            .expr(Box::new([args[0].clone(), Expr::bytes(FALSE)]));
451                                        return Ok(true);
452                                    }
453                                }
454                            }
455                        }
456
457                        _ => {}
458                    }
459                }
460
461                OpExprArgs::Args2(op, args) => {
462                    match op {
463                        Opcode2::OP_ADD | Opcode2::OP_SUB => {
464                            let [ref a1, ref a2] = **args;
465                            if let Expr::Bytes(a1) = a1 {
466                                check_int(a1, 4)?;
467                            }
468                            if let Expr::Bytes(a2) = a2 {
469                                check_int(a2, 4)?;
470                            }
471                            if let (Expr::Bytes(a1), Expr::Bytes(a2)) = (a1, a2) {
472                                let a = decode_int_unchecked(a1);
473                                let b = decode_int_unchecked(a2);
474                                *self = Expr::bytes_owned(encode_int(match op {
475                                    Opcode2::OP_ADD => a + b,
476                                    _ => a - b,
477                                }));
478                                return Ok(true);
479                            }
480                        }
481
482                        Opcode2::OP_EQUAL => {
483                            let [ref a1_, ref a2] = **args;
484                            match (a1_, a2) {
485                                (Expr::Bytes(a1), Expr::Bytes(a2)) => {
486                                    *self = Expr::bytes(encode_bool(a1 == a2));
487                                    return Ok(true);
488                                }
489                                (Expr::Op(a1), Expr::Bytes(a2)) => {
490                                    if a1.opcode().returns_boolean() {
491                                        if **a2 == *TRUE {
492                                            *self = a1_.clone()
493                                        } else if **a2 == *FALSE {
494                                            *self = Opcode1::OP_NOT.expr(Box::new([a1_.clone()]))
495                                        } else {
496                                            *self = Expr::bytes(FALSE)
497                                        }
498                                        return Ok(true);
499                                    }
500                                }
501                                _ => {}
502                            }
503                        }
504
505                        Opcode2::OP_CHECKSIG => {
506                            let [ref sig, ref pubkey] = **args;
507                            if ctx.version == ScriptVersion::SegwitV1 {
508                                if let Expr::Bytes(pubkey) = pubkey {
509                                    if pubkey.len() == 0 {
510                                        return Err(ScriptError::SCRIPT_ERR_PUBKEYTYPE);
511                                    } else if pubkey.len() != 32 {
512                                        return if ctx.rules == ScriptRules::All {
513                                            Err(ScriptError::SCRIPT_ERR_DISCOURAGE_UPGRADABLE_PUBKEYTYPE)
514                                        } else {
515                                            *self = Expr::bytes(TRUE);
516                                            Ok(true)
517                                        };
518                                    }
519                                    if let Expr::Bytes(sig) = sig {
520                                        if sig.len() == 0 {
521                                            *self = Expr::bytes(FALSE);
522                                            return Ok(true);
523                                        } else if sig.len() != 64 && sig.len() != 65 {
524                                            return Err(ScriptError::SCRIPT_ERR_SCHNORR_SIG_SIZE);
525                                        } else if sig.len() == 65
526                                            && !SIG_HASH_TYPES.contains(&sig[64])
527                                        {
528                                            return Err(
529                                                ScriptError::SCRIPT_ERR_SCHNORR_SIG_HASHTYPE,
530                                            );
531                                        }
532                                    }
533                                }
534                            } else if let Expr::Bytes(pubkey) = pubkey {
535                                // TODO CheckPubKeyEncoding without SCRIPT_VERIFY_STRICTENC?
536                                match check_pub_key(pubkey) {
537                                    PubKeyCheckResult::Invalid => {
538                                        return Err(ScriptError::SCRIPT_ERR_PUBKEYTYPE);
539                                    }
540                                    PubKeyCheckResult::Valid { compressed } => {
541                                        if !compressed
542                                            && ctx.version == ScriptVersion::SegwitV0
543                                            && ctx.rules == ScriptRules::All
544                                        {
545                                            return Err(ScriptError::SCRIPT_ERR_WITNESS_PUBKEYTYPE);
546                                        }
547                                    }
548                                }
549                                if let Expr::Bytes(sig) = sig {
550                                    if sig.len() == 0 {
551                                        *self = Expr::bytes(FALSE);
552                                        return Ok(true);
553                                    }
554                                    if ctx.rules == ScriptRules::All {
555                                        // TODO low s
556                                        if !is_valid_signature_encoding(sig) {
557                                            return Err(ScriptError::SCRIPT_ERR_SIG_DER);
558                                        } else if !SIG_HASH_TYPES.contains(&sig[sig.len() - 1]) {
559                                            return Err(ScriptError::SCRIPT_ERR_SIG_HASHTYPE);
560                                        }
561                                    }
562                                }
563                            }
564                        }
565
566                        _ => {}
567                    }
568                }
569
570                OpExprArgs::Args3(_, _) => {}
571
572                OpExprArgs::Multisig(m) => {
573                    if m.keys().len() == m.sigs().len() {
574                        let (sigs, pks) = replace(m, MultisigArgs::valid_garbage()).into_vecs();
575
576                        *self = sigs
577                            .into_iter()
578                            .zip(pks)
579                            .map(|(sig, pk)| Opcode2::OP_CHECKSIG.expr(Box::new([sig, pk])))
580                            .reduce(|a, b| Opcode2::OP_BOOLAND.expr(Box::new([a, b])))
581                            .unwrap_or_else(|| Expr::bytes(TRUE));
582
583                        return Ok(true);
584                    }
585                    // TODO check pubkeys, sigs like with checksig, maybe cache check results to
586                    // not repeat them multiple times
587                }
588            }
589        }
590
591        Ok(changed)
592    }
593
594    pub fn replace_all(&mut self, search: &Expr, replace: &Expr) -> bool {
595        if search == self {
596            *self = replace.clone();
597            true
598        } else if let Expr::Op(ref mut op) = self {
599            let mut changed = false;
600            for arg in op.args_mut() {
601                changed |= arg.replace_all(search, replace);
602            }
603            changed
604        } else {
605            false
606        }
607    }
608}
bitcoin_script_analyzer/expr.rs

bitcoin_script_analyzer/
expr.rs
