tinyminiscript/
satisfy.rs

1use core::ops::Deref;
2
3use bitcoin::Witness;
4
5use crate::{
6    Vec, bitcoin_definition_link,
7    parser::{AST, Fragment, ParserContext, keys::KeyToken},
8};
9
10use alloc::string::String;
11
12pub trait Satisfier {
13    /// CheckOlder checks if the OP_CHECKSEQUENCEVERIFY call is satisfied in the context of a
14    /// transaction.
15    fn check_older(&self, locktime: u32) -> Option<bool>;
16
17    /// CheckAfter checks if the OP_CHECKLOCKTIMEVERIFY call is satisfied in the context of a
18    /// transaction.
19    fn check_after(&self, locktime: u32) -> Option<bool>;
20
21    /// Sign generates a signature for the given public key.
22    fn sign(&self, pubkey: &KeyToken) -> Option<(Vec<u8>, bool)>;
23
24    /// Preimage returns the preimage of the hash value. hashFunc is one of "sha256", "ripemd160",
25    /// "hash256", "hash160".
26    fn preimage(&self, hash_func: HashFunc, hash: &[u8]) -> Option<(Vec<u8>, bool)>;
27}
28
29#[cfg_attr(feature = "debug", derive(Debug))]
30#[repr(u8)]
31pub enum HashFunc {
32    Sha256,
33    Ripemd160,
34    Hash256,
35    Hash160,
36}
37
38impl HashFunc {
39    pub const fn expected_length(&self) -> usize {
40        // match self {
41        //     HashFunc::Sha256 | HashFunc::Hash256 => 32,
42        //     HashFunc::Ripemd160 | HashFunc::Hash160 => 20,
43        // }
44        32
45    }
46}
47
48/// Satisfaction is a struct that represents a satisfaction of a miniscript expression.
49#[doc = bitcoin_definition_link!("8333aa5302902f6be929c30b3c2b4e91c6583224", "script/miniscript.h", 294)]
50#[derive(Clone)]
51#[cfg_attr(feature = "debug", derive(Debug))]
52pub struct Satisfaction {
53    pub witness: Witness,
54    pub available: bool,
55    pub malleable: bool,
56    pub has_sig: bool,
57}
58
59impl Satisfaction {
60    pub fn new(data: &[u8], available: bool, malleable: bool, has_sig: bool) -> Self {
61        let mut witness = Witness::new();
62        witness.push(data);
63        Self {
64            witness,
65            available,
66            malleable,
67            has_sig,
68        }
69    }
70
71    pub fn set_available(mut self, available: bool) -> Self {
72        self.available = available;
73        self
74    }
75
76    pub fn with_sig(mut self) -> Self {
77        self.has_sig = true;
78        self
79    }
80
81    pub fn set_malleable(mut self, malleable: bool) -> Self {
82        self.malleable = malleable;
83        self
84    }
85
86    pub fn and(&self, other: &Self) -> Self {
87        Self {
88            witness: Witness::from_slice(
89                self.witness
90                    .into_iter()
91                    .chain(other.witness.into_iter())
92                    .collect::<Vec<_>>()
93                    .as_slice(),
94            ),
95            available: self.available && other.available,
96            malleable: self.malleable || other.malleable,
97            has_sig: self.has_sig || other.has_sig,
98        }
99    }
100
101    pub fn or(&self, other: &Self) -> Self {
102        let mut _self = self.clone();
103        let mut _other = other.clone();
104
105        // If only one (or neither) is valid, pick the other one.
106        if !_self.available {
107            return _other;
108        }
109        if !_other.available {
110            return _self;
111        }
112        // If only one of the solutions has a signature, we must pick the other one.
113        if !_self.has_sig && _other.has_sig {
114            return _self;
115        }
116        if _self.has_sig && !_other.has_sig {
117            return _other;
118        }
119        // If neither solution requires a signature, the result is inevitably malleable.
120        if !_self.has_sig && !_other.has_sig {
121            _self.malleable = true;
122            _other.malleable = true;
123        } else {
124            // If both options require a signature, prefer the non-malleable one.
125            if _other.malleable && !_self.malleable {
126                return _self;
127            }
128            if _self.malleable && !_other.malleable {
129                return _other;
130            }
131        }
132        // Both avaiable, pick smaller one.
133        if _self.available && _other.available {
134            if _self.witness.size() <= _other.witness.size() {
135                return _self;
136            }
137            return _other;
138        }
139        // If only one available, return that one. If both unavailable, the result is unavailable.
140        if _self.available {
141            return _self;
142        }
143        return _other;
144    }
145}
146
147#[cfg_attr(feature = "debug", derive(Debug))]
148
149pub struct Satisfactions {
150    pub dsat: Satisfaction,
151    pub sat: Satisfaction,
152}
153
154impl Satisfactions {
155    #[inline]
156    pub const fn new(dsat: Satisfaction, sat: Satisfaction) -> Self {
157        Self { dsat, sat }
158    }
159}
160
161#[cfg_attr(feature = "debug", derive(Debug))]
162pub enum SatisfyError {
163    MissingSignature(String),
164    MissingLockTime(u32),
165    MissingPreimage(HashFunc),
166    InvalidPreimage(HashFunc),
167    NonDefiniteKey(String),
168    TaprootNotSupported,
169}
170
171const EMPTY: Satisfaction = Satisfaction {
172    witness: Witness::new(),
173    available: true,
174    malleable: false,
175    has_sig: false,
176};
177
178const UNAVAILABLE: Satisfaction = Satisfaction {
179    witness: Witness::new(),
180    available: false,
181    malleable: false,
182    has_sig: false,
183};
184
185/// Satisfy is a function that satisfies a miniscript expression.
186#[doc = bitcoin_definition_link!("8333aa5302902f6be929c30b3c2b4e91c6583224", "script/miniscript.h", 1186)]
187pub(crate) fn satisfy<'a>(
188    ctx: &ParserContext<'a>,
189    satisfier: &dyn Satisfier,
190    node: &AST,
191) -> Result<Satisfactions, SatisfyError> {
192    let zero = || Satisfaction::new(&[], true, false, false);
193    let one = || Satisfaction::new(&[1], true, false, false);
194    let witness = |w: &[u8]| Satisfaction::new(w, true, false, false);
195
196    match &node.fragment {
197        Fragment::False => Ok(Satisfactions::new(EMPTY, UNAVAILABLE)),
198        Fragment::True => Ok(Satisfactions::new(UNAVAILABLE, EMPTY)),
199        Fragment::PkK { key } => {
200            let (sig, avail) = satisfier
201                .sign(key)
202                .ok_or(SatisfyError::MissingSignature(key.identifier()))?;
203            Ok(Satisfactions::new(
204                zero(),
205                witness(sig.as_slice()).with_sig().set_available(avail),
206            ))
207        }
208        Fragment::PkH { key } => {
209            let (sig, avail) = satisfier
210                .sign(key)
211                .ok_or(SatisfyError::MissingSignature(key.identifier()))?;
212
213            let key = match key.as_definite_key() {
214                Some(k) => k,
215                None => return Err(SatisfyError::NonDefiniteKey(key.identifier())),
216            };
217
218            Ok(Satisfactions::new(
219                zero().and(&witness(&key.to_bytes())),
220                witness(sig.as_slice())
221                    .set_available(avail)
222                    .and(&witness(&key.to_bytes())),
223            ))
224        }
225        Fragment::Older { n } => {
226            let avail = satisfier
227                .check_older(*n)
228                .ok_or(SatisfyError::MissingLockTime(*n))?;
229
230            if avail {
231                Ok(Satisfactions::new(UNAVAILABLE, EMPTY))
232            } else {
233                Ok(Satisfactions::new(UNAVAILABLE, UNAVAILABLE))
234            }
235        }
236        Fragment::After { n } => {
237            let avail = satisfier
238                .check_after(*n)
239                .ok_or(SatisfyError::MissingLockTime(*n))?;
240
241            if avail {
242                Ok(Satisfactions::new(UNAVAILABLE, EMPTY))
243            } else {
244                Ok(Satisfactions::new(UNAVAILABLE, UNAVAILABLE))
245            }
246        }
247        Fragment::Sha256 { h } => {
248            let (preimage, avail) = satisfier
249                .preimage(HashFunc::Sha256, h.as_slice())
250                .ok_or(SatisfyError::MissingPreimage(HashFunc::Sha256))?;
251
252            if avail && preimage.len() != HashFunc::Sha256.expected_length() {
253                return Err(SatisfyError::InvalidPreimage(HashFunc::Sha256));
254            }
255            Ok(Satisfactions::new(
256                witness(&[0; HashFunc::Sha256.expected_length()]).set_malleable(true),
257                witness(preimage.as_slice()).set_available(avail),
258            ))
259        }
260        Fragment::Hash256 { h } => {
261            let (preimage, avail) = satisfier
262                .preimage(HashFunc::Hash256, h.as_slice())
263                .ok_or(SatisfyError::MissingPreimage(HashFunc::Hash256))?;
264            if avail && preimage.len() != HashFunc::Hash256.expected_length() {
265                return Err(SatisfyError::InvalidPreimage(HashFunc::Hash256));
266            }
267            Ok(Satisfactions::new(
268                witness(&[0; HashFunc::Hash256.expected_length()]).set_malleable(true),
269                witness(preimage.as_slice()).set_available(avail),
270            ))
271        }
272        Fragment::Ripemd160 { h } => {
273            let (preimage, avail) = satisfier
274                .preimage(HashFunc::Ripemd160, h.as_slice())
275                .ok_or(SatisfyError::MissingPreimage(HashFunc::Ripemd160))?;
276            if avail && preimage.len() != HashFunc::Ripemd160.expected_length() {
277                return Err(SatisfyError::InvalidPreimage(HashFunc::Ripemd160));
278            }
279            Ok(Satisfactions::new(
280                witness(&[0; HashFunc::Ripemd160.expected_length()]).set_malleable(true),
281                witness(preimage.as_slice()).set_available(avail),
282            ))
283        }
284        Fragment::Hash160 { h } => {
285            let (preimage, avail) = satisfier
286                .preimage(HashFunc::Hash160, h.as_slice())
287                .ok_or(SatisfyError::MissingPreimage(HashFunc::Hash160))?;
288            if avail && preimage.len() != HashFunc::Hash160.expected_length() {
289                return Err(SatisfyError::InvalidPreimage(HashFunc::Hash160));
290            }
291            Ok(Satisfactions::new(
292                witness(&[0; HashFunc::Hash160.expected_length()]).set_malleable(true),
293                witness(preimage.as_slice()).set_available(avail),
294            ))
295        }
296        Fragment::AndOr { x, y, z } => {
297            let x = satisfy(ctx, satisfier, &ctx.get_node(*x))?;
298            let y = satisfy(ctx, satisfier, &ctx.get_node(*y))?;
299            let z = satisfy(ctx, satisfier, &ctx.get_node(*z))?;
300            Ok(Satisfactions::new(
301                z.dsat.and(&x.dsat).or(&y.dsat.and(&x.sat)),
302                y.sat.and(&x.sat).or(&z.sat.and(&x.dsat)),
303            ))
304        }
305        Fragment::AndV { x, y } => {
306            let x = satisfy(ctx, satisfier, &ctx.get_node(*x))?;
307            let y = satisfy(ctx, satisfier, &ctx.get_node(*y))?;
308            Ok(Satisfactions::new(y.dsat.and(&x.sat), y.sat.and(&x.sat)))
309        }
310        Fragment::AndB { x, y } => {
311            let x = satisfy(ctx, satisfier, &ctx.get_node(*x))?;
312            let y = satisfy(ctx, satisfier, &ctx.get_node(*y))?;
313            Ok(Satisfactions::new(
314                y.dsat
315                    .and(&x.dsat)
316                    .or(&y.sat.and(&x.dsat).set_malleable(true))
317                    .or(&y.dsat.and(&x.sat).set_malleable(true)),
318                y.sat.and(&x.sat),
319            ))
320        }
321        Fragment::OrB { x, z } => {
322            let x = satisfy(ctx, satisfier, &ctx.get_node(*x))?;
323            let z = satisfy(ctx, satisfier, &ctx.get_node(*z))?;
324            Ok(Satisfactions::new(
325                z.dsat.and(&x.dsat),
326                z.dsat
327                    .and(&x.sat)
328                    .or(&z.sat.and(&x.dsat))
329                    .or(&z.sat.and(&x.sat).set_malleable(true)),
330            ))
331        }
332        Fragment::OrC { x, z } => {
333            let x = satisfy(ctx, satisfier, &ctx.get_node(*x))?;
334            let z = satisfy(ctx, satisfier, &ctx.get_node(*z))?;
335            Ok(Satisfactions::new(
336                UNAVAILABLE,
337                x.sat.or(&z.sat.and(&x.dsat)),
338            ))
339        }
340        Fragment::OrD { x, z } => {
341            let x = satisfy(ctx, satisfier, &ctx.get_node(*x))?;
342            let z = satisfy(ctx, satisfier, &ctx.get_node(*z))?;
343            Ok(Satisfactions::new(
344                z.dsat.and(&x.dsat),
345                x.sat.or(&z.sat.and(&x.dsat)),
346            ))
347        }
348        Fragment::OrI { x, z } => {
349            let x = satisfy(ctx, satisfier, &ctx.get_node(*x))?;
350            let z = satisfy(ctx, satisfier, &ctx.get_node(*z))?;
351            Ok(Satisfactions::new(
352                x.dsat.and(&one()).or(&z.dsat.and(&zero())),
353                x.sat.and(&one()).or(&z.sat.and(&zero())),
354            ))
355        }
356        Fragment::Thresh { k, xs } => {
357            let n = xs.len();
358            let mut sub_sats = Vec::new();
359            for arg in xs {
360                let sat = satisfy(ctx, satisfier, &ctx.get_node(*arg))?;
361                sub_sats.push(sat);
362            }
363
364            // sats[k] represents the best stack that satisfies k out of the *last* i subexpressions.
365            // In the loop below, these stacks are built up using a dynamic programming approach.
366            // sats[0] starts off empty.
367            let mut sats = Vec::new();
368            sats.push(EMPTY);
369
370            for i in 0..n {
371                // Introduce an alias for the i'th last satisfaction/dissatisfaction.
372                let res = &sub_sats[n - i - 1];
373
374                // Compute the next sats vector: next_sats[0] is sats[0] plus res.nsat (thus containing all dissatisfactions
375                // so far. next_sats[j] is either sats[j] + res.nsat (reusing j earlier satisfactions) or sats[j-1] + res.sat
376                // (reusing j-1 earlier satisfactions plus a new one). The very last next_sats[j] is all satisfactions.
377                let mut next_sats = Vec::new();
378                next_sats.push(sats[0].and(&res.dsat));
379
380                for j in 1..sats.len() {
381                    next_sats.push((sats[j].and(&res.dsat)).or(&sats[j - 1].and(&res.sat)));
382                }
383                next_sats.push(sats[sats.len() - 1].and(&res.sat));
384
385                // Switch over.
386                sats = next_sats;
387            }
388
389            // At this point, sats[k].sat is the best satisfaction for the overall thresh() node. The best dissatisfaction
390            // is computed by gathering all sats[i].nsat for i != k.
391            let mut nsat = EMPTY.set_available(false);
392            for i in 0..sats.len() {
393                // i==k is the satisfaction; i==0 is the canonical dissatisfaction;
394                // the rest are non-canonical (a no-signature dissatisfaction - the i=0
395                // form - is always available) and malleable (due to overcompleteness).
396                // Marking the solutions malleable here is not strictly necessary, as they
397                // should already never be picked in non-malleable solutions due to the
398                // availability of the i=0 form.
399                if i != 0 && i != *k as usize {
400                    sats[i] = sats[i].clone().set_malleable(true);
401                }
402                // Include all dissatisfactions (even these non-canonical ones) in nsat.
403                if i != *k as usize {
404                    nsat = nsat.or(&sats[i]);
405                }
406            }
407
408            // Safety check: k should be valid
409            if *k as usize >= sats.len() {
410                return Err(SatisfyError::MissingLockTime(*k as u32));
411            }
412
413            Ok(Satisfactions::new(nsat, sats[*k as usize].clone()))
414        }
415        Fragment::Multi { k, keys } => {
416            // sats[j] represents the best stack containing j valid signatures (out of the first i keys).
417            // In the loop below, these stacks are built up using a dynamic programming approach.
418            // sats[0] starts off being {0}, due to the CHECKMULTISIG bug that pops off one element too many.
419            let mut sats = Vec::new();
420            sats.push(zero());
421
422            for i in 0..keys.len() {
423                let (sig, avail) = satisfier
424                    .sign(&keys[i])
425                    .ok_or(SatisfyError::MissingSignature(keys[i].identifier()))?;
426
427                // Compute signature stack for just the i'th key.
428                let sat = witness(&sig).with_sig().set_available(avail);
429
430                // Compute the next sats vector: next_sats[0] is a copy of sats[0] (no signatures). All further
431                // next_sats[j] are equal to either the existing sats[j], or sats[j-1] plus a signature for the
432                // current (i'th) key. The very last element needs all signatures filled.
433                let mut next_sats = Vec::new();
434                next_sats.push(sats[0].clone());
435
436                for j in 1..sats.len() {
437                    next_sats.push(sats[j].or(&sats[j - 1].and(&sat)));
438                }
439                next_sats.push(sats[sats.len() - 1].and(&sat));
440
441                // Switch over.
442                sats = next_sats;
443            }
444
445            // The dissatisfaction consists of k+1 stack elements all equal to 0.
446            let mut nsat = zero();
447            for _ in 0..*k {
448                nsat = nsat.and(&zero());
449            }
450
451            // Safety check: k should be valid
452            if *k as usize >= sats.len() {
453                return Err(SatisfyError::MissingLockTime(*k as u32));
454            }
455
456            Ok(Satisfactions::new(nsat, sats[*k as usize].clone()))
457        }
458        Fragment::Identity { identity_type, x } => {
459            let x_pair = satisfy(ctx, satisfier, &ctx.get_node(*x))?;
460            match identity_type {
461                crate::parser::IdentityType::D => {
462                    Ok(Satisfactions::new(zero(), x_pair.sat.and(&one())))
463                }
464                crate::parser::IdentityType::V => Ok(Satisfactions::new(UNAVAILABLE, x_pair.sat)),
465                crate::parser::IdentityType::J => Ok(Satisfactions::new(
466                    zero().set_malleable(x_pair.dsat.available && !x_pair.dsat.has_sig),
467                    x_pair.sat,
468                )),
469                _ => return satisfy(ctx, satisfier, &ctx.get_node(*x)),
470            }
471        }
472        Fragment::MultiA { k, keys } => {
473            let n = keys.len();
474            // sats[j] represents the best stack containing j valid signatures (out of the first i keys).
475            // In the loop below, these stacks are built up using a dynamic programming approach.
476            let mut sats = Vec::new();
477            sats.push(EMPTY);
478
479            for i in 0..n {
480                // Get the signature for the i'th key in reverse order (the signature for the first key needs to
481                // be at the top of the stack, contrary to CHECKMULTISIG's satisfaction).
482                let key_idx = n - 1 - i;
483                let key_type = &keys[key_idx];
484                let (sig, avail) = satisfier
485                    .sign(&key_type)
486                    .ok_or(SatisfyError::MissingSignature(key_type.identifier()))?;
487
488                // Compute signature stack for just this key.
489                let sat = witness(&sig).with_sig().set_available(avail);
490
491                // Compute the next sats vector: next_sats[0] is a copy of sats[0] (no signatures). All further
492                // next_sats[j] are equal to either the existing sats[j] + ZERO, or sats[j-1] plus a signature
493                // for the current (i'th) key. The very last element needs all signatures filled.
494                let mut next_sats = Vec::new();
495                next_sats.push(sats[0].and(&zero()));
496
497                for j in 1..sats.len() {
498                    next_sats.push((sats[j].and(&zero())).or(&sats[j - 1].and(&sat)));
499                }
500                next_sats.push(sats[sats.len() - 1].and(&sat));
501
502                // Switch over.
503                sats = next_sats;
504            }
505
506            // The dissatisfaction consists of as many empty vectors as there are keys, which is the same as
507            // satisfying 0 keys.
508            let nsat = sats[0].clone();
509
510            // Safety check: k should be valid
511            if *k <= 0 || *k as usize >= sats.len() {
512                return Err(SatisfyError::MissingSignature(keys[0].identifier()));
513            }
514
515            Ok(Satisfactions::new(nsat, sats[*k as usize].clone()))
516        }
517        Fragment::Descriptor { descriptor, inner } => {
518            satisfy(ctx, satisfier, &ctx.get_node(*inner))
519        }
520        Fragment::RawPkH { key } => {
521            let (sig, avail) = satisfier
522                .sign(key)
523                .ok_or(SatisfyError::MissingSignature(key.identifier()))?;
524
525            let key = match key.as_definite_key() {
526                Some(k) => k,
527                None => return Err(SatisfyError::NonDefiniteKey(key.identifier())),
528            };
529
530            Ok(Satisfactions::new(
531                zero().and(&witness(&key.to_bytes())),
532                witness(sig.as_slice())
533                    .set_available(avail)
534                    .and(&witness(&key.to_bytes())),
535            ))
536        }
537        Fragment::RawTr { key, inner } => {
538            return Err(SatisfyError::TaprootNotSupported);
539        }
540        Fragment::RawPk { key } => {
541            let (sig, avail) = satisfier
542                .sign(key)
543                .ok_or(SatisfyError::MissingSignature(key.identifier()))?;
544            Ok(Satisfactions::new(
545                zero(),
546                witness(sig.as_slice()).with_sig().set_available(avail),
547            ))
548        }
549    }
550}
tinyminiscript/satisfy.rs

tinyminiscript/
satisfy.rs
