bells_miniscript/interpreter/
mod.rs

1// Written in 2019 by Sanket Kanjular and Andrew Poelstra
2// SPDX-License-Identifier: CC0-1.0
3
4//! Interpreter
5//!
6//! Provides a Miniscript-based script interpreter which can be used to
7//! iterate over the set of conditions satisfied by a spending transaction,
8//! assuming that the spent coin was descriptor controlled.
9//!
10
11use core::fmt;
12use core::str::FromStr;
13
14use bellscoin::hashes::{hash160, ripemd160, sha256, Hash};
15use bellscoin::{absolute, secp256k1, sighash, taproot, Sequence, TxOut, Witness};
16
17use crate::miniscript::context::{NoChecks, SigType};
18use crate::miniscript::ScriptContext;
19use crate::prelude::*;
20use crate::{hash256, Descriptor, Miniscript, Terminal, ToPublicKey};
21
22mod error;
23mod inner;
24mod stack;
25
26pub use self::error::Error;
27use self::error::PkEvalErrInner;
28use self::stack::Stack;
29use crate::MiniscriptKey;
30
31/// An iterable Miniscript-structured representation of the spending of a coin
32pub struct Interpreter<'txin> {
33    inner: inner::Inner,
34    stack: Stack<'txin>,
35    /// For non-Taproot spends, the scriptCode; for Taproot script-spends, this
36    /// is the leaf script; for key-spends it is `None`.
37    script_code: Option<bellscoin::ScriptBuf>,
38    age: Sequence,
39    lock_time: absolute::LockTime,
40}
41
42// A type representing functions for checking signatures that accept both
43// Ecdsa and Schnorr signatures
44
45/// A type for representing signatures supported as of bitcoin core 22.0
46#[derive(Debug, Clone, Copy, PartialEq, Eq)]
47pub enum KeySigPair {
48    /// A Full public key and corresponding Ecdsa signature
49    Ecdsa(bellscoin::PublicKey, bellscoin::ecdsa::Signature),
50    /// A x-only key and corresponding Schnorr signature
51    Schnorr(
52        bellscoin::key::XOnlyPublicKey,
53        bellscoin::taproot::Signature,
54    ),
55}
56
57impl KeySigPair {
58    /// Obtain a pair of ([`bellscoin::PublicKey`], [`bellscoin::ecdsa::Signature`]) from [`KeySigPair`]
59    pub fn as_ecdsa(&self) -> Option<(bellscoin::PublicKey, bellscoin::ecdsa::Signature)> {
60        match self {
61            KeySigPair::Ecdsa(pk, sig) => Some((*pk, *sig)),
62            KeySigPair::Schnorr(_, _) => None,
63        }
64    }
65
66    /// Obtain a pair of ([`bellscoin::secp256k1::XOnlyPublicKey`], [`bellscoin::taproot::Signature`]) from [`KeySigPair`]
67    pub fn as_schnorr(
68        &self,
69    ) -> Option<(
70        bellscoin::key::XOnlyPublicKey,
71        bellscoin::taproot::Signature,
72    )> {
73        match self {
74            KeySigPair::Ecdsa(_, _) => None,
75            KeySigPair::Schnorr(pk, sig) => Some((*pk, *sig)),
76        }
77    }
78}
79
80// Internally used enum for different types of bitcoin keys
81// Even though we implement MiniscriptKey for BitcoinKey, we make sure that there
82// are little mis-use
83// - The only constructors for this are only called in from_txdata that take care
84//   using the correct enum variant
85// - This does not implement ToPublicKey to avoid context dependant encoding/decoding of 33/32
86//   byte keys. This allows us to keep a single NoChecks context instead of a context for
87//   for NoChecksSchnorr/NoChecksEcdsa.
88// Long term TODO: There really should be not be any need for Miniscript<Pk: MiniscriptKey> struct
89// to have the Pk: MiniscriptKey bound. The bound should be on all of it's methods. That would
90// require changing Miniscript struct to three generics Miniscript<Pk, Pkh, Ctx> and bound on
91// all of the methods of Miniscript to ensure that Pkh = Pk::Hash
92#[derive(Hash, Eq, Ord, PartialEq, PartialOrd, Clone, Copy, Debug)]
93enum BitcoinKey {
94    // Full key
95    Fullkey(bellscoin::PublicKey),
96    // Xonly key
97    XOnlyPublicKey(bellscoin::key::XOnlyPublicKey),
98}
99
100impl BitcoinKey {
101    fn to_pubkeyhash(self, sig_type: SigType) -> hash160::Hash {
102        match self {
103            BitcoinKey::Fullkey(pk) => pk.to_pubkeyhash(sig_type),
104            BitcoinKey::XOnlyPublicKey(pk) => pk.to_pubkeyhash(sig_type),
105        }
106    }
107}
108
109// Displayed in full 33 byte representation. X-only keys are displayed with 0x02 prefix
110impl fmt::Display for BitcoinKey {
111    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
112        match self {
113            BitcoinKey::Fullkey(pk) => pk.to_public_key().fmt(f),
114            BitcoinKey::XOnlyPublicKey(pk) => pk.to_public_key().fmt(f),
115        }
116    }
117}
118
119impl From<bellscoin::PublicKey> for BitcoinKey {
120    fn from(pk: bellscoin::PublicKey) -> Self {
121        BitcoinKey::Fullkey(pk)
122    }
123}
124
125impl From<bellscoin::key::XOnlyPublicKey> for BitcoinKey {
126    fn from(xpk: bellscoin::key::XOnlyPublicKey) -> Self {
127        BitcoinKey::XOnlyPublicKey(xpk)
128    }
129}
130
131impl MiniscriptKey for BitcoinKey {
132    type Sha256 = sha256::Hash;
133    type Hash256 = hash256::Hash;
134    type Ripemd160 = ripemd160::Hash;
135    type Hash160 = hash160::Hash;
136
137    fn num_der_paths(&self) -> usize {
138        0
139    }
140}
141
142impl<'txin> Interpreter<'txin> {
143    /// Constructs an interpreter from the data of a spending transaction
144    ///
145    /// Accepts a signature-validating function. If you are willing to trust
146    /// that ECSDA signatures are valid, this can be set to the constant true
147    /// function; otherwise, it should be a closure containing a sighash and
148    /// secp context, which can actually verify a given signature.
149    pub fn from_txdata(
150        spk: &bellscoin::ScriptBuf,
151        script_sig: &'txin bellscoin::Script,
152        witness: &'txin Witness,
153        age: Sequence,                 // CSV, relative lock time.
154        lock_time: absolute::LockTime, // CLTV, absolute lock time.
155    ) -> Result<Self, Error> {
156        let (inner, stack, script_code) = inner::from_txdata(spk, script_sig, witness)?;
157        Ok(Interpreter {
158            inner,
159            stack,
160            script_code,
161            age,
162            lock_time,
163        })
164    }
165
166    /// Same as [`Interpreter::iter`], but allows for a custom verification function.
167    /// See [Self::iter_assume_sigs] for a simpler API without information about Prevouts
168    /// but skips the signature verification
169    pub fn iter_custom<'iter>(
170        &'iter self,
171        verify_sig: Box<dyn FnMut(&KeySigPair) -> bool + 'iter>,
172    ) -> Iter<'txin, 'iter> {
173        Iter {
174            verify_sig,
175            public_key: if let inner::Inner::PublicKey(ref pk, _) = self.inner {
176                Some(pk)
177            } else {
178                None
179            },
180            state: if let inner::Inner::Script(ref script, _) = self.inner {
181                vec![NodeEvaluationState {
182                    node: script,
183                    n_evaluated: 0,
184                    n_satisfied: 0,
185                }]
186            } else {
187                vec![]
188            },
189            // Cloning the references to elements of stack should be fine as it allows
190            // call interpreter.iter() without mutating interpreter
191            stack: self.stack.clone(),
192            age: self.age,
193            lock_time: self.lock_time,
194            has_errored: false,
195            sig_type: self.sig_type(),
196        }
197    }
198
199    /// Verify a signature for a given transaction and prevout information
200    /// This is a low level API, [`Interpreter::iter`] or [`Interpreter::iter_assume_sigs`]
201    /// should satisfy most use-cases.
202    /// Returns false if
203    /// - the signature verification fails
204    /// - the input index is out of range
205    /// - Insufficient sighash information is present
206    /// - sighash single without corresponding output
207    // TODO: Create a good first isse to change this to error
208    pub fn verify_sig<C: secp256k1::Verification, T: Borrow<TxOut>>(
209        &self,
210        secp: &secp256k1::Secp256k1<C>,
211        tx: &bellscoin::Transaction,
212        input_idx: usize,
213        prevouts: &sighash::Prevouts<T>,
214        sig: &KeySigPair,
215    ) -> bool {
216        fn get_prevout<'u, T: Borrow<TxOut>>(
217            prevouts: &'u sighash::Prevouts<'u, T>,
218            input_index: usize,
219        ) -> Option<&'u T> {
220            match prevouts {
221                sighash::Prevouts::One(index, prevout) => {
222                    if input_index == *index {
223                        Some(prevout)
224                    } else {
225                        None
226                    }
227                }
228                sighash::Prevouts::All(prevouts) => prevouts.get(input_index),
229            }
230        }
231        let mut cache = bellscoin::sighash::SighashCache::new(tx);
232        match sig {
233            KeySigPair::Ecdsa(key, ecdsa_sig) => {
234                let script_pubkey = self.script_code.as_ref().expect("Legacy have script code");
235                let msg = if self.is_legacy() {
236                    let sighash_u32 = ecdsa_sig.hash_ty.to_u32();
237                    let sighash =
238                        cache.legacy_signature_hash(input_idx, script_pubkey, sighash_u32);
239                    sighash.map(|hash| {
240                        secp256k1::Message::from_slice(hash.as_byte_array()).expect("32 byte")
241                    })
242                } else if self.is_segwit_v0() {
243                    let amt = match get_prevout(prevouts, input_idx) {
244                        Some(txout) => txout.borrow().value,
245                        None => return false,
246                    };
247                    let sighash = cache.segwit_signature_hash(
248                        input_idx,
249                        script_pubkey,
250                        amt,
251                        ecdsa_sig.hash_ty,
252                    );
253                    sighash.map(|hash| {
254                        secp256k1::Message::from_slice(hash.as_byte_array()).expect("32 byte")
255                    })
256                } else {
257                    // taproot(or future) signatures in segwitv0 context
258                    return false;
259                };
260
261                let success =
262                    msg.map(|msg| secp.verify_ecdsa(&msg, &ecdsa_sig.sig, &key.inner).is_ok());
263                success.unwrap_or(false) // unwrap_or checks for errors, while success would have checksig results
264            }
265            KeySigPair::Schnorr(xpk, schnorr_sig) => {
266                let sighash_msg = if self.is_taproot_v1_key_spend() {
267                    cache.taproot_key_spend_signature_hash(input_idx, prevouts, schnorr_sig.hash_ty)
268                } else if self.is_taproot_v1_script_spend() {
269                    let tap_script = self.script_code.as_ref().expect(
270                        "Internal Hack: Saving leaf script instead\
271                        of script code for script spend",
272                    );
273                    let leaf_hash = taproot::TapLeafHash::from_script(
274                        tap_script,
275                        taproot::LeafVersion::TapScript,
276                    );
277                    cache.taproot_script_spend_signature_hash(
278                        input_idx,
279                        prevouts,
280                        leaf_hash,
281                        schnorr_sig.hash_ty,
282                    )
283                } else {
284                    // schnorr sigs in ecdsa descriptors
285                    return false;
286                };
287                let msg = sighash_msg.map(|hash| {
288                    secp256k1::Message::from_slice(hash.as_byte_array()).expect("32 byte")
289                });
290                let success =
291                    msg.map(|msg| secp.verify_schnorr(&schnorr_sig.sig, &msg, xpk).is_ok());
292                success.unwrap_or(false) // unwrap_or_default checks for errors, while success would have checksig results
293            }
294        }
295    }
296
297    /// Creates an iterator over the satisfied spending conditions
298    ///
299    /// Returns all satisfied constraints, even if they were redundant (i.e. did
300    /// not contribute to the script being satisfied). For example, if a signature
301    /// were provided for an `and_b(Pk,false)` fragment, that signature will be
302    /// returned, even though the entire and_b must have failed and must not have
303    /// been used.
304    ///
305    /// In case the script is actually dissatisfied, this may return several values
306    /// before ultimately returning an error.
307    ///
308    /// Not all fields are used by legacy/segwitv0 descriptors; if you are sure this is a legacy
309    /// spend (you can check with the `is_legacy\is_segwitv0` method) you can provide dummy data for
310    /// the amount/prevouts.
311    /// - For legacy outputs, no information about prevouts is required
312    /// - For segwitv0 outputs, prevout at corresponding index with correct amount must be provided
313    /// - For taproot outputs, information about all prevouts must be supplied
314    pub fn iter<'iter, C: secp256k1::Verification, T: Borrow<TxOut>>(
315        &'iter self,
316        secp: &'iter secp256k1::Secp256k1<C>,
317        tx: &'txin bellscoin::Transaction,
318        input_idx: usize,
319        prevouts: &'iter sighash::Prevouts<T>, // actually a 'prevouts, but 'prevouts: 'iter
320    ) -> Iter<'txin, 'iter> {
321        self.iter_custom(Box::new(move |sig| {
322            self.verify_sig(secp, tx, input_idx, prevouts, sig)
323        }))
324    }
325
326    /// Creates an iterator over the satisfied spending conditions without checking signatures
327    pub fn iter_assume_sigs<'iter>(&'iter self) -> Iter<'txin, 'iter> {
328        self.iter_custom(Box::new(|_| true))
329    }
330
331    /// Outputs a "descriptor" string which reproduces the spent coins
332    ///
333    /// This may not represent the original descriptor used to produce the transaction,
334    /// since it cannot distinguish between sorted and unsorted multisigs (and anyway
335    /// it can only see the final keys, keyorigin info is lost in serializing to Bitcoin).
336    ///
337    /// If you are using the interpreter as a sanity check on a transaction,
338    /// it is worthwhile to try to parse this as a descriptor using `from_str`
339    /// which will check standardness and consensus limits, which the interpreter
340    /// does not do on its own. Or use the `inferred_descriptor` method which
341    /// does this for you.
342    pub fn inferred_descriptor_string(&self) -> String {
343        match self.inner {
344            inner::Inner::PublicKey(ref pk, inner::PubkeyType::Pk) => format!("pk({})", pk),
345            inner::Inner::PublicKey(ref pk, inner::PubkeyType::Pkh) => format!("pkh({})", pk),
346            inner::Inner::PublicKey(ref pk, inner::PubkeyType::Wpkh) => format!("wpkh({})", pk),
347            inner::Inner::PublicKey(ref pk, inner::PubkeyType::ShWpkh) => {
348                format!("sh(wpkh({}))", pk)
349            }
350            inner::Inner::PublicKey(ref pk, inner::PubkeyType::Tr) => {
351                // In tr descriptors, normally the internal key is represented inside the tr part
352                // But there is no way to infer the internal key from output descriptor status
353                // instead we infer a rawtr.
354                // Note that rawtr is parsing is currently not supported.
355                format!("rawtr_not_supported_yet({})", pk)
356            }
357            inner::Inner::Script(ref ms, inner::ScriptType::Bare) => format!("{}", ms),
358            inner::Inner::Script(ref ms, inner::ScriptType::Sh) => format!("sh({})", ms),
359            inner::Inner::Script(ref ms, inner::ScriptType::Wsh) => format!("wsh({})", ms),
360            inner::Inner::Script(ref ms, inner::ScriptType::ShWsh) => format!("sh(wsh({}))", ms),
361            inner::Inner::Script(ref ms, inner::ScriptType::Tr) => {
362                // Hidden paths are still under discussion, once the spec is finalized, we can support
363                // rawnode and raw leaf.
364                format!("tr(hidden_paths_not_yet_supported,{})", ms)
365            }
366        }
367    }
368
369    /// Whether this is a pre-segwit spend
370    pub fn is_legacy(&self) -> bool {
371        match self.inner {
372            inner::Inner::PublicKey(_, inner::PubkeyType::Pk) => true,
373            inner::Inner::PublicKey(_, inner::PubkeyType::Pkh) => true,
374            inner::Inner::PublicKey(_, inner::PubkeyType::Wpkh) => false,
375            inner::Inner::PublicKey(_, inner::PubkeyType::ShWpkh) => false, // lol "sorta"
376            inner::Inner::PublicKey(_, inner::PubkeyType::Tr) => false,     // lol "sorta"
377            inner::Inner::Script(_, inner::ScriptType::Bare) => true,
378            inner::Inner::Script(_, inner::ScriptType::Sh) => true,
379            inner::Inner::Script(_, inner::ScriptType::Wsh) => false,
380            inner::Inner::Script(_, inner::ScriptType::ShWsh) => false, // lol "sorta"
381            inner::Inner::Script(_, inner::ScriptType::Tr) => false,
382        }
383    }
384
385    /// Whether this is a segwit spend
386    pub fn is_segwit_v0(&self) -> bool {
387        match self.inner {
388            inner::Inner::PublicKey(_, inner::PubkeyType::Pk) => false,
389            inner::Inner::PublicKey(_, inner::PubkeyType::Pkh) => false,
390            inner::Inner::PublicKey(_, inner::PubkeyType::Wpkh) => true,
391            inner::Inner::PublicKey(_, inner::PubkeyType::ShWpkh) => true, // lol "sorta"
392            inner::Inner::PublicKey(_, inner::PubkeyType::Tr) => false,
393            inner::Inner::Script(_, inner::ScriptType::Bare) => false,
394            inner::Inner::Script(_, inner::ScriptType::Sh) => false,
395            inner::Inner::Script(_, inner::ScriptType::Wsh) => true,
396            inner::Inner::Script(_, inner::ScriptType::ShWsh) => true, // lol "sorta"
397            inner::Inner::Script(_, inner::ScriptType::Tr) => false,
398        }
399    }
400
401    /// Whether this is a taproot key spend
402    pub fn is_taproot_v1_key_spend(&self) -> bool {
403        match self.inner {
404            inner::Inner::PublicKey(_, inner::PubkeyType::Pk) => false,
405            inner::Inner::PublicKey(_, inner::PubkeyType::Pkh) => false,
406            inner::Inner::PublicKey(_, inner::PubkeyType::Wpkh) => false,
407            inner::Inner::PublicKey(_, inner::PubkeyType::ShWpkh) => false,
408            inner::Inner::PublicKey(_, inner::PubkeyType::Tr) => true,
409            inner::Inner::Script(_, inner::ScriptType::Bare) => false,
410            inner::Inner::Script(_, inner::ScriptType::Sh) => false,
411            inner::Inner::Script(_, inner::ScriptType::Wsh) => false,
412            inner::Inner::Script(_, inner::ScriptType::ShWsh) => false,
413            inner::Inner::Script(_, inner::ScriptType::Tr) => false,
414        }
415    }
416
417    /// Whether this is a taproot script spend
418    pub fn is_taproot_v1_script_spend(&self) -> bool {
419        match self.inner {
420            inner::Inner::PublicKey(_, inner::PubkeyType::Pk) => false,
421            inner::Inner::PublicKey(_, inner::PubkeyType::Pkh) => false,
422            inner::Inner::PublicKey(_, inner::PubkeyType::Wpkh) => false,
423            inner::Inner::PublicKey(_, inner::PubkeyType::ShWpkh) => false,
424            inner::Inner::PublicKey(_, inner::PubkeyType::Tr) => false,
425            inner::Inner::Script(_, inner::ScriptType::Bare) => false,
426            inner::Inner::Script(_, inner::ScriptType::Sh) => false,
427            inner::Inner::Script(_, inner::ScriptType::Wsh) => false,
428            inner::Inner::Script(_, inner::ScriptType::ShWsh) => false,
429            inner::Inner::Script(_, inner::ScriptType::Tr) => true,
430        }
431    }
432
433    /// Signature type of the spend
434    pub fn sig_type(&self) -> SigType {
435        match self.inner {
436            inner::Inner::PublicKey(_, inner::PubkeyType::Tr) => SigType::Schnorr,
437            inner::Inner::Script(_, inner::ScriptType::Tr) => SigType::Schnorr,
438            inner::Inner::PublicKey(_, inner::PubkeyType::Pk)
439            | inner::Inner::PublicKey(_, inner::PubkeyType::Pkh)
440            | inner::Inner::PublicKey(_, inner::PubkeyType::Wpkh)
441            | inner::Inner::PublicKey(_, inner::PubkeyType::ShWpkh)
442            | inner::Inner::Script(_, inner::ScriptType::Bare)
443            | inner::Inner::Script(_, inner::ScriptType::Sh)
444            | inner::Inner::Script(_, inner::ScriptType::Wsh)
445            | inner::Inner::Script(_, inner::ScriptType::ShWsh) => SigType::Ecdsa,
446        }
447    }
448
449    /// Outputs a "descriptor" which reproduces the spent coins
450    ///
451    /// This may not represent the original descriptor used to produce the transaction,
452    /// since it cannot distinguish between sorted and unsorted multisigs (and anyway
453    /// it can only see the final keys, keyorigin info is lost in serializing to Bitcoin).
454    /// x-only keys are translated to [`bellscoin::PublicKey`] with 0x02 prefix.
455    pub fn inferred_descriptor(&self) -> Result<Descriptor<bellscoin::PublicKey>, crate::Error> {
456        Descriptor::from_str(&self.inferred_descriptor_string())
457    }
458}
459
460/// Type of HashLock used for SatisfiedConstraint structure
461#[derive(Copy, Clone, Debug, Eq, PartialEq)]
462pub enum HashLockType {
463    ///SHA 256 hashlock
464    Sha256(sha256::Hash),
465    ///Hash 256 hashlock
466    Hash256(hash256::Hash),
467    ///Hash160 hashlock
468    Hash160(hash160::Hash),
469    ///Ripemd160 hashlock
470    Ripemd160(ripemd160::Hash),
471}
472
473/// A satisfied Miniscript condition (Signature, Hashlock, Timelock)
474/// 'intp represents the lifetime of descriptor and `stack represents
475/// the lifetime of witness
476#[derive(Copy, Clone, Debug, Eq, PartialEq)]
477pub enum SatisfiedConstraint {
478    ///Public key and corresponding signature
479    PublicKey {
480        /// KeySig pair
481        key_sig: KeySigPair,
482    },
483    ///PublicKeyHash, corresponding pubkey and signature
484    PublicKeyHash {
485        /// The pubkey hash
486        keyhash: hash160::Hash,
487        /// public key and signature
488        key_sig: KeySigPair,
489    },
490    ///Hashlock and preimage for SHA256
491    HashLock {
492        /// The type of Hashlock
493        hash: HashLockType,
494        /// The preimage used for satisfaction
495        preimage: [u8; 32],
496    },
497    ///Relative Timelock for CSV.
498    RelativeTimelock {
499        /// The value of RelativeTimelock
500        n: Sequence,
501    },
502    ///Absolute Timelock for CLTV.
503    AbsoluteTimelock {
504        /// The value of Absolute timelock
505        n: absolute::LockTime,
506    },
507}
508
509///This is used by the interpreter to know which evaluation state a AstemElem is.
510///This is required because whenever a same node(for eg. OrB) appears on the stack, we don't
511///know if the left child has been evaluated or not. And based on the result on
512///the top of the stack, we need to decide whether to execute right child or not.
513///This is also useful for wrappers and thresholds which push a value on the stack
514///depending on evaluation of the children.
515struct NodeEvaluationState<'intp> {
516    ///The node which is being evaluated
517    node: &'intp Miniscript<BitcoinKey, NoChecks>,
518    ///number of children evaluated
519    n_evaluated: usize,
520    ///number of children satisfied
521    n_satisfied: usize,
522}
523
524/// Iterator over all the constraints satisfied by a completed scriptPubKey
525/// and witness stack
526///
527/// Returns all satisfied constraints, even if they were redundant (i.e. did
528/// not contribute to the script being satisfied). For example, if a signature
529/// were provided for an `and_b(Pk,false)` fragment, that signature will be
530/// returned, even though the entire and_b must have failed and must not have
531/// been used.
532///
533/// In case the script is actually dissatisfied, this may return several values
534/// before ultimately returning an error.
535pub struct Iter<'intp, 'txin: 'intp> {
536    verify_sig: Box<dyn FnMut(&KeySigPair) -> bool + 'intp>,
537    public_key: Option<&'intp BitcoinKey>,
538    state: Vec<NodeEvaluationState<'intp>>,
539    stack: Stack<'txin>,
540    age: Sequence,
541    lock_time: absolute::LockTime,
542    has_errored: bool,
543    sig_type: SigType,
544}
545
546///Iterator for Iter
547impl<'intp, 'txin: 'intp> Iterator for Iter<'intp, 'txin>
548where
549    NoChecks: ScriptContext,
550{
551    type Item = Result<SatisfiedConstraint, Error>;
552
553    fn next(&mut self) -> Option<Self::Item> {
554        if self.has_errored {
555            // Stop yielding values after the first error
556            None
557        } else {
558            let res = self.iter_next();
559            if let Some(Err(_)) = res {
560                self.has_errored = true;
561            }
562            res
563        }
564    }
565}
566
567impl<'intp, 'txin: 'intp> Iter<'intp, 'txin>
568where
569    NoChecks: ScriptContext,
570{
571    /// Helper function to push a NodeEvaluationState on state stack
572    fn push_evaluation_state(
573        &mut self,
574        node: &'intp Miniscript<BitcoinKey, NoChecks>,
575        n_evaluated: usize,
576        n_satisfied: usize,
577    ) {
578        self.state.push(NodeEvaluationState {
579            node,
580            n_evaluated,
581            n_satisfied,
582        })
583    }
584
585    /// Helper function to step the iterator
586    fn iter_next(&mut self) -> Option<Result<SatisfiedConstraint, Error>> {
587        while let Some(node_state) = self.state.pop() {
588            //non-empty stack
589            match node_state.node.node {
590                Terminal::True => {
591                    debug_assert_eq!(node_state.n_evaluated, 0);
592                    debug_assert_eq!(node_state.n_satisfied, 0);
593                    self.stack.push(stack::Element::Satisfied);
594                }
595                Terminal::False => {
596                    debug_assert_eq!(node_state.n_evaluated, 0);
597                    debug_assert_eq!(node_state.n_satisfied, 0);
598                    self.stack.push(stack::Element::Dissatisfied);
599                }
600                Terminal::PkK(ref pk) => {
601                    debug_assert_eq!(node_state.n_evaluated, 0);
602                    debug_assert_eq!(node_state.n_satisfied, 0);
603                    let res = self.stack.evaluate_pk(&mut self.verify_sig, *pk);
604                    if res.is_some() {
605                        return res;
606                    }
607                }
608                Terminal::PkH(ref pk) => {
609                    debug_assert_eq!(node_state.n_evaluated, 0);
610                    debug_assert_eq!(node_state.n_satisfied, 0);
611                    let res = self.stack.evaluate_pkh(
612                        &mut self.verify_sig,
613                        pk.to_pubkeyhash(self.sig_type),
614                        self.sig_type,
615                    );
616                    if res.is_some() {
617                        return res;
618                    }
619                }
620                Terminal::RawPkH(ref pkh) => {
621                    debug_assert_eq!(node_state.n_evaluated, 0);
622                    debug_assert_eq!(node_state.n_satisfied, 0);
623                    let res = self
624                        .stack
625                        .evaluate_pkh(&mut self.verify_sig, *pkh, self.sig_type);
626                    if res.is_some() {
627                        return res;
628                    }
629                }
630                Terminal::After(ref n) => {
631                    debug_assert_eq!(node_state.n_evaluated, 0);
632                    debug_assert_eq!(node_state.n_satisfied, 0);
633                    let res = self
634                        .stack
635                        .evaluate_after(&absolute::LockTime::from(*n), self.lock_time);
636                    if res.is_some() {
637                        return res;
638                    }
639                }
640                Terminal::Older(ref n) => {
641                    debug_assert_eq!(node_state.n_evaluated, 0);
642                    debug_assert_eq!(node_state.n_satisfied, 0);
643                    let res = self.stack.evaluate_older(n, self.age);
644                    if res.is_some() {
645                        return res;
646                    }
647                }
648                Terminal::Sha256(ref hash) => {
649                    debug_assert_eq!(node_state.n_evaluated, 0);
650                    debug_assert_eq!(node_state.n_satisfied, 0);
651                    let res = self.stack.evaluate_sha256(hash);
652                    if res.is_some() {
653                        return res;
654                    }
655                }
656                Terminal::Hash256(ref hash) => {
657                    debug_assert_eq!(node_state.n_evaluated, 0);
658                    debug_assert_eq!(node_state.n_satisfied, 0);
659                    let res = self.stack.evaluate_hash256(hash);
660                    if res.is_some() {
661                        return res;
662                    }
663                }
664                Terminal::Hash160(ref hash) => {
665                    debug_assert_eq!(node_state.n_evaluated, 0);
666                    debug_assert_eq!(node_state.n_satisfied, 0);
667                    let res = self.stack.evaluate_hash160(hash);
668                    if res.is_some() {
669                        return res;
670                    }
671                }
672                Terminal::Ripemd160(ref hash) => {
673                    debug_assert_eq!(node_state.n_evaluated, 0);
674                    debug_assert_eq!(node_state.n_satisfied, 0);
675                    let res = self.stack.evaluate_ripemd160(hash);
676                    if res.is_some() {
677                        return res;
678                    }
679                }
680                Terminal::Alt(ref sub) | Terminal::Swap(ref sub) | Terminal::Check(ref sub) => {
681                    debug_assert_eq!(node_state.n_evaluated, 0);
682                    debug_assert_eq!(node_state.n_satisfied, 0);
683                    self.push_evaluation_state(sub, 0, 0);
684                }
685                Terminal::DupIf(ref sub) if node_state.n_evaluated == 0 => match self.stack.pop() {
686                    Some(stack::Element::Dissatisfied) => {
687                        self.stack.push(stack::Element::Dissatisfied);
688                    }
689                    Some(stack::Element::Satisfied) => {
690                        self.push_evaluation_state(node_state.node, 1, 1);
691                        self.push_evaluation_state(sub, 0, 0);
692                    }
693                    Some(stack::Element::Push(_v)) => {
694                        return Some(Err(Error::UnexpectedStackElementPush))
695                    }
696                    None => return Some(Err(Error::UnexpectedStackEnd)),
697                },
698                Terminal::DupIf(ref _sub) if node_state.n_evaluated == 1 => {
699                    self.stack.push(stack::Element::Satisfied);
700                }
701                Terminal::ZeroNotEqual(ref sub) | Terminal::Verify(ref sub)
702                    if node_state.n_evaluated == 0 =>
703                {
704                    self.push_evaluation_state(node_state.node, 1, 0);
705                    self.push_evaluation_state(sub, 0, 0);
706                }
707                Terminal::Verify(ref _sub) if node_state.n_evaluated == 1 => {
708                    match self.stack.pop() {
709                        Some(stack::Element::Satisfied) => (),
710                        Some(_) => return Some(Err(Error::VerifyFailed)),
711                        None => return Some(Err(Error::UnexpectedStackEnd)),
712                    }
713                }
714                Terminal::ZeroNotEqual(ref _sub) if node_state.n_evaluated == 1 => {
715                    match self.stack.pop() {
716                        Some(stack::Element::Dissatisfied) => {
717                            self.stack.push(stack::Element::Dissatisfied)
718                        }
719                        Some(_) => self.stack.push(stack::Element::Satisfied),
720                        None => return Some(Err(Error::UnexpectedStackEnd)),
721                    }
722                }
723                Terminal::NonZero(ref sub) => {
724                    debug_assert_eq!(node_state.n_evaluated, 0);
725                    debug_assert_eq!(node_state.n_satisfied, 0);
726                    match self.stack.last() {
727                        Some(&stack::Element::Dissatisfied) => (),
728                        Some(_) => self.push_evaluation_state(sub, 0, 0),
729                        None => return Some(Err(Error::UnexpectedStackEnd)),
730                    }
731                }
732                Terminal::AndV(ref left, ref right) => {
733                    debug_assert_eq!(node_state.n_evaluated, 0);
734                    debug_assert_eq!(node_state.n_satisfied, 0);
735                    self.push_evaluation_state(right, 0, 0);
736                    self.push_evaluation_state(left, 0, 0);
737                }
738                Terminal::OrB(ref left, ref _right) | Terminal::AndB(ref left, ref _right)
739                    if node_state.n_evaluated == 0 =>
740                {
741                    self.push_evaluation_state(node_state.node, 1, 0);
742                    self.push_evaluation_state(left, 0, 0);
743                }
744                Terminal::OrB(ref _left, ref right) | Terminal::AndB(ref _left, ref right)
745                    if node_state.n_evaluated == 1 =>
746                {
747                    match self.stack.pop() {
748                        Some(stack::Element::Dissatisfied) => {
749                            self.push_evaluation_state(node_state.node, 2, 0);
750                            self.push_evaluation_state(right, 0, 0);
751                        }
752                        Some(stack::Element::Satisfied) => {
753                            self.push_evaluation_state(node_state.node, 2, 1);
754                            self.push_evaluation_state(right, 0, 0);
755                        }
756                        Some(stack::Element::Push(_v)) => {
757                            return Some(Err(Error::UnexpectedStackElementPush))
758                        }
759                        None => return Some(Err(Error::UnexpectedStackEnd)),
760                    }
761                }
762                Terminal::AndB(ref _left, ref _right) if node_state.n_evaluated == 2 => {
763                    match self.stack.pop() {
764                        Some(stack::Element::Satisfied) if node_state.n_satisfied == 1 => {
765                            self.stack.push(stack::Element::Satisfied)
766                        }
767                        Some(_) => self.stack.push(stack::Element::Dissatisfied),
768                        None => return Some(Err(Error::UnexpectedStackEnd)),
769                    }
770                }
771                Terminal::AndOr(ref left, ref _right, _)
772                | Terminal::OrC(ref left, ref _right)
773                | Terminal::OrD(ref left, ref _right)
774                    if node_state.n_evaluated == 0 =>
775                {
776                    self.push_evaluation_state(node_state.node, 1, 0);
777                    self.push_evaluation_state(left, 0, 0);
778                }
779                Terminal::OrB(ref _left, ref _right) if node_state.n_evaluated == 2 => {
780                    match self.stack.pop() {
781                        Some(stack::Element::Dissatisfied) if node_state.n_satisfied == 0 => {
782                            self.stack.push(stack::Element::Dissatisfied)
783                        }
784                        Some(_) => {
785                            self.stack.push(stack::Element::Satisfied);
786                        }
787                        None => return Some(Err(Error::UnexpectedStackEnd)),
788                    }
789                }
790                Terminal::OrC(ref _left, ref right) if node_state.n_evaluated == 1 => {
791                    match self.stack.pop() {
792                        Some(stack::Element::Satisfied) => (),
793                        Some(stack::Element::Dissatisfied) => {
794                            self.push_evaluation_state(right, 0, 0)
795                        }
796                        Some(stack::Element::Push(_v)) => {
797                            return Some(Err(Error::UnexpectedStackElementPush))
798                        }
799                        None => return Some(Err(Error::UnexpectedStackEnd)),
800                    }
801                }
802                Terminal::OrD(ref _left, ref right) if node_state.n_evaluated == 1 => {
803                    match self.stack.pop() {
804                        Some(stack::Element::Satisfied) => {
805                            self.stack.push(stack::Element::Satisfied)
806                        }
807                        Some(stack::Element::Dissatisfied) => {
808                            self.push_evaluation_state(right, 0, 0)
809                        }
810                        Some(stack::Element::Push(_v)) => {
811                            return Some(Err(Error::UnexpectedStackElementPush))
812                        }
813                        None => return Some(Err(Error::UnexpectedStackEnd)),
814                    }
815                }
816                Terminal::AndOr(_, ref left, ref right) | Terminal::OrI(ref left, ref right) => {
817                    match self.stack.pop() {
818                        Some(stack::Element::Satisfied) => self.push_evaluation_state(left, 0, 0),
819                        Some(stack::Element::Dissatisfied) => {
820                            self.push_evaluation_state(right, 0, 0)
821                        }
822                        Some(stack::Element::Push(_v)) => {
823                            return Some(Err(Error::UnexpectedStackElementPush))
824                        }
825                        None => return Some(Err(Error::UnexpectedStackEnd)),
826                    }
827                }
828                Terminal::Thresh(ref _k, ref subs) if node_state.n_evaluated == 0 => {
829                    self.push_evaluation_state(node_state.node, 1, 0);
830                    self.push_evaluation_state(&subs[0], 0, 0);
831                }
832                Terminal::Thresh(k, ref subs) if node_state.n_evaluated == subs.len() => {
833                    match self.stack.pop() {
834                        Some(stack::Element::Dissatisfied) if node_state.n_satisfied == k => {
835                            self.stack.push(stack::Element::Satisfied)
836                        }
837                        Some(stack::Element::Satisfied) if node_state.n_satisfied == k - 1 => {
838                            self.stack.push(stack::Element::Satisfied)
839                        }
840                        Some(stack::Element::Satisfied) | Some(stack::Element::Dissatisfied) => {
841                            self.stack.push(stack::Element::Dissatisfied)
842                        }
843                        Some(stack::Element::Push(_v)) => {
844                            return Some(Err(Error::UnexpectedStackElementPush))
845                        }
846                        None => return Some(Err(Error::UnexpectedStackEnd)),
847                    }
848                }
849                Terminal::Thresh(ref _k, ref subs) if node_state.n_evaluated != 0 => {
850                    match self.stack.pop() {
851                        Some(stack::Element::Dissatisfied) => {
852                            self.push_evaluation_state(
853                                node_state.node,
854                                node_state.n_evaluated + 1,
855                                node_state.n_satisfied,
856                            );
857                            self.push_evaluation_state(&subs[node_state.n_evaluated], 0, 0);
858                        }
859                        Some(stack::Element::Satisfied) => {
860                            self.push_evaluation_state(
861                                node_state.node,
862                                node_state.n_evaluated + 1,
863                                node_state.n_satisfied + 1,
864                            );
865                            self.push_evaluation_state(&subs[node_state.n_evaluated], 0, 0);
866                        }
867                        Some(stack::Element::Push(_v)) => {
868                            return Some(Err(Error::UnexpectedStackElementPush))
869                        }
870                        None => return Some(Err(Error::UnexpectedStackEnd)),
871                    }
872                }
873                Terminal::MultiA(k, ref subs) => {
874                    if node_state.n_evaluated == subs.len() {
875                        if node_state.n_satisfied == k {
876                            self.stack.push(stack::Element::Satisfied);
877                        } else {
878                            self.stack.push(stack::Element::Dissatisfied);
879                        }
880                    } else {
881                        // evaluate each key with as a pk
882                        // note that evaluate_pk will error on non-empty incorrect sigs
883                        // push 1 on satisfied sigs and push 0 on empty sigs
884                        match self
885                            .stack
886                            .evaluate_pk(&mut self.verify_sig, subs[node_state.n_evaluated])
887                        {
888                            Some(Ok(x)) => {
889                                self.push_evaluation_state(
890                                    node_state.node,
891                                    node_state.n_evaluated + 1,
892                                    node_state.n_satisfied + 1,
893                                );
894                                match self.stack.pop() {
895                                    Some(..) => return Some(Ok(x)),
896                                    None => return Some(Err(Error::UnexpectedStackEnd)),
897                                }
898                            }
899                            None => {
900                                self.push_evaluation_state(
901                                    node_state.node,
902                                    node_state.n_evaluated + 1,
903                                    node_state.n_satisfied,
904                                );
905                                match self.stack.pop() {
906                                    Some(..) => {} // not-satisfied, look for next key
907                                    None => return Some(Err(Error::UnexpectedStackEnd)),
908                                }
909                            }
910                            x => return x, //forward errors as is
911                        }
912                    }
913                }
914                Terminal::Multi(ref k, ref subs) if node_state.n_evaluated == 0 => {
915                    let len = self.stack.len();
916                    if len < k + 1 {
917                        return Some(Err(Error::InsufficientSignaturesMultiSig));
918                    } else {
919                        //Non-sat case. If the first sig is empty, others k elements must
920                        //be empty.
921                        match self.stack.last() {
922                            Some(&stack::Element::Dissatisfied) => {
923                                //Remove the extra zero from multi-sig check
924                                let sigs = self.stack.split_off(len - (k + 1));
925                                let nonsat = sigs
926                                    .iter()
927                                    .map(|sig| *sig == stack::Element::Dissatisfied)
928                                    .filter(|empty| *empty)
929                                    .count();
930                                if nonsat == *k + 1 {
931                                    self.stack.push(stack::Element::Dissatisfied);
932                                } else {
933                                    return Some(Err(Error::MissingExtraZeroMultiSig));
934                                }
935                            }
936                            None => return Some(Err(Error::UnexpectedStackEnd)),
937                            _ => {
938                                match self
939                                    .stack
940                                    .evaluate_multi(&mut self.verify_sig, &subs[subs.len() - 1])
941                                {
942                                    Some(Ok(x)) => {
943                                        self.push_evaluation_state(
944                                            node_state.node,
945                                            node_state.n_evaluated + 1,
946                                            node_state.n_satisfied + 1,
947                                        );
948                                        return Some(Ok(x));
949                                    }
950                                    None => self.push_evaluation_state(
951                                        node_state.node,
952                                        node_state.n_evaluated + 1,
953                                        node_state.n_satisfied,
954                                    ),
955                                    x => return x, //forward errors as is
956                                }
957                            }
958                        }
959                    }
960                }
961                Terminal::Multi(k, ref subs) => {
962                    if node_state.n_satisfied == k {
963                        //multi-sig bug: Pop extra 0
964                        if let Some(stack::Element::Dissatisfied) = self.stack.pop() {
965                            self.stack.push(stack::Element::Satisfied);
966                        } else {
967                            return Some(Err(Error::MissingExtraZeroMultiSig));
968                        }
969                    } else if node_state.n_evaluated == subs.len() {
970                        return Some(Err(Error::MultiSigEvaluationError));
971                    } else {
972                        match self.stack.evaluate_multi(
973                            &mut self.verify_sig,
974                            &subs[subs.len() - node_state.n_evaluated - 1],
975                        ) {
976                            Some(Ok(x)) => {
977                                self.push_evaluation_state(
978                                    node_state.node,
979                                    node_state.n_evaluated + 1,
980                                    node_state.n_satisfied + 1,
981                                );
982                                return Some(Ok(x));
983                            }
984                            None => self.push_evaluation_state(
985                                node_state.node,
986                                node_state.n_evaluated + 1,
987                                node_state.n_satisfied,
988                            ),
989                            x => return x, //forward errors as is
990                        }
991                    }
992                }
993                //All other match patterns should not be reached in any valid
994                //type checked Miniscript
995                _ => return Some(Err(Error::CouldNotEvaluate)),
996            };
997        }
998
999        //state empty implies that either the execution has terminated or we have a
1000        //Pk based descriptor
1001        if let Some(pk) = self.public_key {
1002            if let Some(stack::Element::Push(sig)) = self.stack.pop() {
1003                if let Ok(key_sig) = verify_sersig(&mut self.verify_sig, pk, sig) {
1004                    //Signature check successful, set public_key to None to
1005                    //terminate the next() function in the subsequent call
1006                    self.public_key = None;
1007                    self.stack.push(stack::Element::Satisfied);
1008                    Some(Ok(SatisfiedConstraint::PublicKey { key_sig }))
1009                } else {
1010                    Some(Err(Error::PkEvaluationError(PkEvalErrInner::from(*pk))))
1011                }
1012            } else {
1013                Some(Err(Error::UnexpectedStackEnd))
1014            }
1015        } else {
1016            //All the script has been executed.
1017            //Check that the stack must contain exactly 1 satisfied element
1018            if self.stack.pop() == Some(stack::Element::Satisfied) && self.stack.is_empty() {
1019                None
1020            } else {
1021                Some(Err(Error::ScriptSatisfactionError))
1022            }
1023        }
1024    }
1025}
1026
1027/// Helper function to verify serialized signature
1028fn verify_sersig<'txin>(
1029    verify_sig: &mut Box<dyn FnMut(&KeySigPair) -> bool + 'txin>,
1030    pk: &BitcoinKey,
1031    sigser: &[u8],
1032) -> Result<KeySigPair, Error> {
1033    match pk {
1034        BitcoinKey::Fullkey(pk) => {
1035            let ecdsa_sig = bellscoin::ecdsa::Signature::from_slice(sigser)?;
1036            let key_sig_pair = KeySigPair::Ecdsa(*pk, ecdsa_sig);
1037            if verify_sig(&key_sig_pair) {
1038                Ok(key_sig_pair)
1039            } else {
1040                Err(Error::InvalidEcdsaSignature(*pk))
1041            }
1042        }
1043        BitcoinKey::XOnlyPublicKey(x_only_pk) => {
1044            let schnorr_sig = bellscoin::taproot::Signature::from_slice(sigser)?;
1045            let key_sig_pair = KeySigPair::Schnorr(*x_only_pk, schnorr_sig);
1046            if verify_sig(&key_sig_pair) {
1047                Ok(key_sig_pair)
1048            } else {
1049                Err(Error::InvalidSchnorrSignature(*x_only_pk))
1050            }
1051        }
1052    }
1053}
1054
1055#[cfg(test)]
1056mod tests {
1057
1058    use bellscoin;
1059    use bellscoin::hashes::{hash160, ripemd160, sha256, Hash};
1060    use bellscoin::secp256k1::{self, Secp256k1};
1061
1062    use super::inner::ToNoChecks;
1063    use super::*;
1064    use crate::miniscript::analyzable::ExtParams;
1065    use crate::miniscript::context::NoChecks;
1066    use crate::{Miniscript, ToPublicKey};
1067
1068    fn setup_keys_sigs(
1069        n: usize,
1070    ) -> (
1071        Vec<bellscoin::PublicKey>,
1072        Vec<Vec<u8>>,
1073        Vec<bellscoin::ecdsa::Signature>,
1074        secp256k1::Message,
1075        Secp256k1<secp256k1::All>,
1076        Vec<bellscoin::key::XOnlyPublicKey>,
1077        Vec<bellscoin::taproot::Signature>,
1078        Vec<Vec<u8>>,
1079    ) {
1080        let secp = secp256k1::Secp256k1::new();
1081        let msg = secp256k1::Message::from_slice(&b"Yoda: btc, I trust. HODL I must!"[..])
1082            .expect("32 bytes");
1083        let mut pks = vec![];
1084        let mut ecdsa_sigs = vec![];
1085        let mut der_sigs = vec![];
1086        let mut x_only_pks = vec![];
1087        let mut schnorr_sigs = vec![];
1088        let mut ser_schnorr_sigs = vec![];
1089
1090        let mut sk = [0; 32];
1091        for i in 1..n + 1 {
1092            sk[0] = i as u8;
1093            sk[1] = (i >> 8) as u8;
1094            sk[2] = (i >> 16) as u8;
1095
1096            let sk = secp256k1::SecretKey::from_slice(&sk[..]).expect("secret key");
1097            let pk = bellscoin::PublicKey {
1098                inner: secp256k1::PublicKey::from_secret_key(&secp, &sk),
1099                compressed: true,
1100            };
1101            let sig = secp.sign_ecdsa(&msg, &sk);
1102            ecdsa_sigs.push(bellscoin::ecdsa::Signature {
1103                sig,
1104                hash_ty: bellscoin::sighash::EcdsaSighashType::All,
1105            });
1106            let mut sigser = sig.serialize_der().to_vec();
1107            sigser.push(0x01); // sighash_all
1108            pks.push(pk);
1109            der_sigs.push(sigser);
1110
1111            let keypair = bellscoin::key::KeyPair::from_secret_key(&secp, &sk);
1112            let (x_only_pk, _parity) = bellscoin::key::XOnlyPublicKey::from_keypair(&keypair);
1113            x_only_pks.push(x_only_pk);
1114            let schnorr_sig = secp.sign_schnorr_with_aux_rand(&msg, &keypair, &[0u8; 32]);
1115            let schnorr_sig = bellscoin::taproot::Signature {
1116                sig: schnorr_sig,
1117                hash_ty: bellscoin::sighash::TapSighashType::Default,
1118            };
1119            ser_schnorr_sigs.push(schnorr_sig.to_vec());
1120            schnorr_sigs.push(schnorr_sig);
1121        }
1122        (
1123            pks,
1124            der_sigs,
1125            ecdsa_sigs,
1126            msg,
1127            secp,
1128            x_only_pks,
1129            schnorr_sigs,
1130            ser_schnorr_sigs,
1131        )
1132    }
1133
1134    #[test]
1135    fn sat_constraints() {
1136        let (pks, der_sigs, ecdsa_sigs, sighash, secp, xpks, schnorr_sigs, ser_schnorr_sigs) =
1137            setup_keys_sigs(10);
1138        let secp_ref = &secp;
1139        let vfyfn = |pksig: &KeySigPair| match pksig {
1140            KeySigPair::Ecdsa(pk, ecdsa_sig) => secp_ref
1141                .verify_ecdsa(&sighash, &ecdsa_sig.sig, &pk.inner)
1142                .is_ok(),
1143            KeySigPair::Schnorr(xpk, schnorr_sig) => secp_ref
1144                .verify_schnorr(&schnorr_sig.sig, &sighash, xpk)
1145                .is_ok(),
1146        };
1147
1148        fn from_stack<'txin, 'elem>(
1149            verify_fn: Box<dyn FnMut(&KeySigPair) -> bool + 'elem>,
1150            stack: Stack<'txin>,
1151            ms: &'elem Miniscript<BitcoinKey, NoChecks>,
1152        ) -> Iter<'elem, 'txin> {
1153            Iter {
1154                verify_sig: verify_fn,
1155                stack,
1156                public_key: None,
1157                state: vec![NodeEvaluationState {
1158                    node: ms,
1159                    n_evaluated: 0,
1160                    n_satisfied: 0,
1161                }],
1162                age: Sequence::from_height(1002),
1163                lock_time: absolute::LockTime::from_height(1002).unwrap(),
1164                has_errored: false,
1165                sig_type: SigType::Ecdsa,
1166            }
1167        }
1168
1169        let pk = no_checks_ms(&format!("c:pk_k({})", pks[0]));
1170        let pkh = no_checks_ms(&format!("c:pk_h({})", pks[1]));
1171        //Time
1172        let after = no_checks_ms(&format!("after({})", 1000));
1173        let older = no_checks_ms(&format!("older({})", 1000));
1174        //Hashes
1175        let preimage = [0xab; 32];
1176        let sha256_hash = sha256::Hash::hash(&preimage);
1177        let sha256 = no_checks_ms(&format!("sha256({})", sha256_hash));
1178        let hash256_hash = hash256::Hash::hash(&preimage);
1179        let hash256 = no_checks_ms(&format!("hash256({})", hash256_hash));
1180        let hash160_hash = hash160::Hash::hash(&preimage);
1181        let hash160 = no_checks_ms(&format!("hash160({})", hash160_hash));
1182        let ripemd160_hash = ripemd160::Hash::hash(&preimage);
1183        let ripemd160 = no_checks_ms(&format!("ripemd160({})", ripemd160_hash));
1184
1185        let stack = Stack::from(vec![stack::Element::Push(&der_sigs[0])]);
1186        let constraints = from_stack(Box::new(vfyfn), stack, &pk);
1187        let pk_satisfied: Result<Vec<SatisfiedConstraint>, Error> = constraints.collect();
1188        assert_eq!(
1189            pk_satisfied.unwrap(),
1190            vec![SatisfiedConstraint::PublicKey {
1191                key_sig: KeySigPair::Ecdsa(pks[0], ecdsa_sigs[0])
1192            }]
1193        );
1194
1195        //Check Pk failure with wrong signature
1196        let stack = Stack::from(vec![stack::Element::Dissatisfied]);
1197        let constraints = from_stack(Box::new(vfyfn), stack, &pk);
1198        let pk_err: Result<Vec<SatisfiedConstraint>, Error> = constraints.collect();
1199        assert!(pk_err.is_err());
1200
1201        //Check Pkh
1202        let pk_bytes = pks[1].to_public_key().to_bytes();
1203        let stack = Stack::from(vec![
1204            stack::Element::Push(&der_sigs[1]),
1205            stack::Element::Push(&pk_bytes),
1206        ]);
1207        let constraints = from_stack(Box::new(vfyfn), stack, &pkh);
1208        let pkh_satisfied: Result<Vec<SatisfiedConstraint>, Error> = constraints.collect();
1209        assert_eq!(
1210            pkh_satisfied.unwrap(),
1211            vec![SatisfiedConstraint::PublicKeyHash {
1212                keyhash: pks[1].to_pubkeyhash(SigType::Ecdsa),
1213                key_sig: KeySigPair::Ecdsa(pks[1], ecdsa_sigs[1])
1214            }]
1215        );
1216
1217        //Check After
1218        let stack = Stack::from(vec![]);
1219        let constraints = from_stack(Box::new(vfyfn), stack, &after);
1220        let after_satisfied: Result<Vec<SatisfiedConstraint>, Error> = constraints.collect();
1221        assert_eq!(
1222            after_satisfied.unwrap(),
1223            vec![SatisfiedConstraint::AbsoluteTimelock {
1224                n: absolute::LockTime::from_height(1000).unwrap()
1225            }]
1226        );
1227
1228        //Check Older
1229        let stack = Stack::from(vec![]);
1230        let constraints = from_stack(Box::new(vfyfn), stack, &older);
1231        let older_satisfied: Result<Vec<SatisfiedConstraint>, Error> = constraints.collect();
1232        assert_eq!(
1233            older_satisfied.unwrap(),
1234            vec![SatisfiedConstraint::RelativeTimelock {
1235                n: Sequence::from_height(1000)
1236            }]
1237        );
1238
1239        //Check Sha256
1240        let stack = Stack::from(vec![stack::Element::Push(&preimage)]);
1241        let constraints = from_stack(Box::new(vfyfn), stack, &sha256);
1242        let sah256_satisfied: Result<Vec<SatisfiedConstraint>, Error> = constraints.collect();
1243        assert_eq!(
1244            sah256_satisfied.unwrap(),
1245            vec![SatisfiedConstraint::HashLock {
1246                hash: HashLockType::Sha256(sha256_hash),
1247                preimage,
1248            }]
1249        );
1250
1251        //Check Shad256
1252        let stack = Stack::from(vec![stack::Element::Push(&preimage)]);
1253        let constraints = from_stack(Box::new(vfyfn), stack, &hash256);
1254        let sha256d_satisfied: Result<Vec<SatisfiedConstraint>, Error> = constraints.collect();
1255        assert_eq!(
1256            sha256d_satisfied.unwrap(),
1257            vec![SatisfiedConstraint::HashLock {
1258                hash: HashLockType::Hash256(hash256_hash),
1259                preimage,
1260            }]
1261        );
1262
1263        //Check hash160
1264        let stack = Stack::from(vec![stack::Element::Push(&preimage)]);
1265        let constraints = from_stack(Box::new(vfyfn), stack, &hash160);
1266        let hash160_satisfied: Result<Vec<SatisfiedConstraint>, Error> = constraints.collect();
1267        assert_eq!(
1268            hash160_satisfied.unwrap(),
1269            vec![SatisfiedConstraint::HashLock {
1270                hash: HashLockType::Hash160(hash160_hash),
1271                preimage,
1272            }]
1273        );
1274
1275        //Check ripemd160
1276        let stack = Stack::from(vec![stack::Element::Push(&preimage)]);
1277        let constraints = from_stack(Box::new(vfyfn), stack, &ripemd160);
1278        let ripemd160_satisfied: Result<Vec<SatisfiedConstraint>, Error> = constraints.collect();
1279        assert_eq!(
1280            ripemd160_satisfied.unwrap(),
1281            vec![SatisfiedConstraint::HashLock {
1282                hash: HashLockType::Ripemd160(ripemd160_hash),
1283                preimage,
1284            }]
1285        );
1286
1287        //Check AndV
1288        let pk_bytes = pks[1].to_public_key().to_bytes();
1289        let stack = Stack::from(vec![
1290            stack::Element::Push(&der_sigs[1]),
1291            stack::Element::Push(&pk_bytes),
1292            stack::Element::Push(&der_sigs[0]),
1293        ]);
1294        let elem = no_checks_ms(&format!("and_v(vc:pk_k({}),c:pk_h({}))", pks[0], pks[1]));
1295        let constraints = from_stack(Box::new(vfyfn), stack, &elem);
1296
1297        let and_v_satisfied: Result<Vec<SatisfiedConstraint>, Error> = constraints.collect();
1298        assert_eq!(
1299            and_v_satisfied.unwrap(),
1300            vec![
1301                SatisfiedConstraint::PublicKey {
1302                    key_sig: KeySigPair::Ecdsa(pks[0], ecdsa_sigs[0])
1303                },
1304                SatisfiedConstraint::PublicKeyHash {
1305                    keyhash: pks[1].to_pubkeyhash(SigType::Ecdsa),
1306                    key_sig: KeySigPair::Ecdsa(pks[1], ecdsa_sigs[1])
1307                }
1308            ]
1309        );
1310
1311        //Check AndB
1312        let stack = Stack::from(vec![
1313            stack::Element::Push(&preimage),
1314            stack::Element::Push(&der_sigs[0]),
1315        ]);
1316        let elem = no_checks_ms(&format!(
1317            "and_b(c:pk_k({}),sjtv:sha256({}))",
1318            pks[0], sha256_hash
1319        ));
1320        let constraints = from_stack(Box::new(vfyfn), stack, &elem);
1321
1322        let and_b_satisfied: Result<Vec<SatisfiedConstraint>, Error> = constraints.collect();
1323        assert_eq!(
1324            and_b_satisfied.unwrap(),
1325            vec![
1326                SatisfiedConstraint::PublicKey {
1327                    key_sig: KeySigPair::Ecdsa(pks[0], ecdsa_sigs[0])
1328                },
1329                SatisfiedConstraint::HashLock {
1330                    hash: HashLockType::Sha256(sha256_hash),
1331                    preimage,
1332                }
1333            ]
1334        );
1335
1336        //Check AndOr
1337        let stack = Stack::from(vec![
1338            stack::Element::Push(&preimage),
1339            stack::Element::Push(&der_sigs[0]),
1340        ]);
1341        let elem = no_checks_ms(&format!(
1342            "andor(c:pk_k({}),jtv:sha256({}),c:pk_h({}))",
1343            pks[0], sha256_hash, pks[1],
1344        ));
1345        let constraints = from_stack(Box::new(vfyfn), stack, &elem);
1346
1347        let and_or_satisfied: Result<Vec<SatisfiedConstraint>, Error> = constraints.collect();
1348        assert_eq!(
1349            and_or_satisfied.unwrap(),
1350            vec![
1351                SatisfiedConstraint::PublicKey {
1352                    key_sig: KeySigPair::Ecdsa(pks[0], ecdsa_sigs[0])
1353                },
1354                SatisfiedConstraint::HashLock {
1355                    hash: HashLockType::Sha256(sha256_hash),
1356                    preimage,
1357                }
1358            ]
1359        );
1360
1361        //AndOr second satisfaction path
1362        let pk_bytes = pks[1].to_public_key().to_bytes();
1363        let stack = Stack::from(vec![
1364            stack::Element::Push(&der_sigs[1]),
1365            stack::Element::Push(&pk_bytes),
1366            stack::Element::Dissatisfied,
1367        ]);
1368        let constraints = from_stack(Box::new(vfyfn), stack, &elem);
1369
1370        let and_or_satisfied: Result<Vec<SatisfiedConstraint>, Error> = constraints.collect();
1371        assert_eq!(
1372            and_or_satisfied.unwrap(),
1373            vec![SatisfiedConstraint::PublicKeyHash {
1374                keyhash: pks[1].to_pubkeyhash(SigType::Ecdsa),
1375                key_sig: KeySigPair::Ecdsa(pks[1], ecdsa_sigs[1])
1376            }]
1377        );
1378
1379        //Check OrB
1380        let stack = Stack::from(vec![
1381            stack::Element::Push(&preimage),
1382            stack::Element::Dissatisfied,
1383        ]);
1384        let elem = no_checks_ms(&format!(
1385            "or_b(c:pk_k({}),sjtv:sha256({}))",
1386            pks[0], sha256_hash
1387        ));
1388        let constraints = from_stack(Box::new(vfyfn), stack, &elem);
1389
1390        let or_b_satisfied: Result<Vec<SatisfiedConstraint>, Error> = constraints.collect();
1391        assert_eq!(
1392            or_b_satisfied.unwrap(),
1393            vec![SatisfiedConstraint::HashLock {
1394                hash: HashLockType::Sha256(sha256_hash),
1395                preimage,
1396            }]
1397        );
1398
1399        //Check OrD
1400        let stack = Stack::from(vec![stack::Element::Push(&der_sigs[0])]);
1401        let elem = no_checks_ms(&format!(
1402            "or_d(c:pk_k({}),jtv:sha256({}))",
1403            pks[0], sha256_hash
1404        ));
1405        let constraints = from_stack(Box::new(vfyfn), stack, &elem);
1406
1407        let or_d_satisfied: Result<Vec<SatisfiedConstraint>, Error> = constraints.collect();
1408        assert_eq!(
1409            or_d_satisfied.unwrap(),
1410            vec![SatisfiedConstraint::PublicKey {
1411                key_sig: KeySigPair::Ecdsa(pks[0], ecdsa_sigs[0])
1412            }]
1413        );
1414
1415        //Check OrC
1416        let stack = Stack::from(vec![
1417            stack::Element::Push(&der_sigs[0]),
1418            stack::Element::Dissatisfied,
1419        ]);
1420        let elem = no_checks_ms(&format!(
1421            "t:or_c(jtv:sha256({}),vc:pk_k({}))",
1422            sha256_hash, pks[0]
1423        ));
1424        let constraints = from_stack(Box::new(vfyfn), stack, &elem);
1425
1426        let or_c_satisfied: Result<Vec<SatisfiedConstraint>, Error> = constraints.collect();
1427        assert_eq!(
1428            or_c_satisfied.unwrap(),
1429            vec![SatisfiedConstraint::PublicKey {
1430                key_sig: KeySigPair::Ecdsa(pks[0], ecdsa_sigs[0])
1431            }]
1432        );
1433
1434        //Check OrI
1435        let stack = Stack::from(vec![
1436            stack::Element::Push(&der_sigs[0]),
1437            stack::Element::Dissatisfied,
1438        ]);
1439        let elem = no_checks_ms(&format!(
1440            "or_i(jtv:sha256({}),c:pk_k({}))",
1441            sha256_hash, pks[0]
1442        ));
1443        let constraints = from_stack(Box::new(vfyfn), stack, &elem);
1444
1445        let or_i_satisfied: Result<Vec<SatisfiedConstraint>, Error> = constraints.collect();
1446        assert_eq!(
1447            or_i_satisfied.unwrap(),
1448            vec![SatisfiedConstraint::PublicKey {
1449                key_sig: KeySigPair::Ecdsa(pks[0], ecdsa_sigs[0])
1450            }]
1451        );
1452
1453        //Check Thres
1454        let stack = Stack::from(vec![
1455            stack::Element::Push(&der_sigs[0]),
1456            stack::Element::Push(&der_sigs[1]),
1457            stack::Element::Push(&der_sigs[2]),
1458            stack::Element::Dissatisfied,
1459            stack::Element::Dissatisfied,
1460        ]);
1461        let elem = no_checks_ms(&format!(
1462            "thresh(3,c:pk_k({}),sc:pk_k({}),sc:pk_k({}),sc:pk_k({}),sc:pk_k({}))",
1463            pks[4], pks[3], pks[2], pks[1], pks[0],
1464        ));
1465        let constraints = from_stack(Box::new(vfyfn), stack, &elem);
1466
1467        let thresh_satisfied: Result<Vec<SatisfiedConstraint>, Error> = constraints.collect();
1468        assert_eq!(
1469            thresh_satisfied.unwrap(),
1470            vec![
1471                SatisfiedConstraint::PublicKey {
1472                    key_sig: KeySigPair::Ecdsa(pks[2], ecdsa_sigs[2])
1473                },
1474                SatisfiedConstraint::PublicKey {
1475                    key_sig: KeySigPair::Ecdsa(pks[1], ecdsa_sigs[1])
1476                },
1477                SatisfiedConstraint::PublicKey {
1478                    key_sig: KeySigPair::Ecdsa(pks[0], ecdsa_sigs[0])
1479                }
1480            ]
1481        );
1482
1483        // Check multi
1484        let stack = Stack::from(vec![
1485            stack::Element::Dissatisfied,
1486            stack::Element::Push(&der_sigs[2]),
1487            stack::Element::Push(&der_sigs[1]),
1488            stack::Element::Push(&der_sigs[0]),
1489        ]);
1490        let elem = no_checks_ms(&format!(
1491            "multi(3,{},{},{},{},{})",
1492            pks[4], pks[3], pks[2], pks[1], pks[0],
1493        ));
1494        let constraints = from_stack(Box::new(vfyfn), stack, &elem);
1495
1496        let multi_satisfied: Result<Vec<SatisfiedConstraint>, Error> = constraints.collect();
1497        assert_eq!(
1498            multi_satisfied.unwrap(),
1499            vec![
1500                SatisfiedConstraint::PublicKey {
1501                    key_sig: KeySigPair::Ecdsa(pks[0], ecdsa_sigs[0])
1502                },
1503                SatisfiedConstraint::PublicKey {
1504                    key_sig: KeySigPair::Ecdsa(pks[1], ecdsa_sigs[1])
1505                },
1506                SatisfiedConstraint::PublicKey {
1507                    key_sig: KeySigPair::Ecdsa(pks[2], ecdsa_sigs[2])
1508                },
1509            ]
1510        );
1511
1512        // Error multi: Invalid order of sigs
1513        let stack = Stack::from(vec![
1514            stack::Element::Dissatisfied,
1515            stack::Element::Push(&der_sigs[0]),
1516            stack::Element::Push(&der_sigs[2]),
1517            stack::Element::Push(&der_sigs[1]),
1518        ]);
1519        let elem = no_checks_ms(&format!(
1520            "multi(3,{},{},{},{},{})",
1521            pks[4], pks[3], pks[2], pks[1], pks[0],
1522        ));
1523        let constraints = from_stack(Box::new(vfyfn), stack, &elem);
1524
1525        let multi_error: Result<Vec<SatisfiedConstraint>, Error> = constraints.collect();
1526        assert!(multi_error.is_err());
1527
1528        // multi_a tests
1529        let stack = Stack::from(vec![
1530            stack::Element::Dissatisfied,
1531            stack::Element::Dissatisfied,
1532            stack::Element::Push(&ser_schnorr_sigs[2]),
1533            stack::Element::Push(&ser_schnorr_sigs[1]),
1534            stack::Element::Push(&ser_schnorr_sigs[0]),
1535        ]);
1536
1537        let elem = x_only_no_checks_ms(&format!(
1538            "multi_a(3,{},{},{},{},{})",
1539            xpks[0], xpks[1], xpks[2], xpks[3], xpks[4],
1540        ));
1541        let constraints = from_stack(Box::new(vfyfn), stack, &elem);
1542
1543        let multi_a_satisfied: Result<Vec<SatisfiedConstraint>, Error> = constraints.collect();
1544        assert_eq!(
1545            multi_a_satisfied.unwrap(),
1546            vec![
1547                SatisfiedConstraint::PublicKey {
1548                    key_sig: KeySigPair::Schnorr(xpks[0], schnorr_sigs[0])
1549                },
1550                SatisfiedConstraint::PublicKey {
1551                    key_sig: KeySigPair::Schnorr(xpks[1], schnorr_sigs[1])
1552                },
1553                SatisfiedConstraint::PublicKey {
1554                    key_sig: KeySigPair::Schnorr(xpks[2], schnorr_sigs[2])
1555                },
1556            ]
1557        );
1558
1559        // multi_a tests: wrong order of sigs
1560        let stack = Stack::from(vec![
1561            stack::Element::Dissatisfied,
1562            stack::Element::Push(&ser_schnorr_sigs[2]),
1563            stack::Element::Push(&ser_schnorr_sigs[1]),
1564            stack::Element::Push(&ser_schnorr_sigs[0]),
1565            stack::Element::Dissatisfied,
1566        ]);
1567
1568        let elem = x_only_no_checks_ms(&format!(
1569            "multi_a(3,{},{},{},{},{})",
1570            xpks[0], xpks[1], xpks[2], xpks[3], xpks[4],
1571        ));
1572        let constraints = from_stack(Box::new(vfyfn), stack.clone(), &elem);
1573
1574        let multi_a_error: Result<Vec<SatisfiedConstraint>, Error> = constraints.collect();
1575        assert!(multi_a_error.is_err());
1576
1577        // multi_a wrong thresh: k = 2, but three sigs
1578        let elem = x_only_no_checks_ms(&format!(
1579            "multi_a(2,{},{},{},{},{})",
1580            xpks[0], xpks[1], xpks[2], xpks[3], xpks[4],
1581        ));
1582        let constraints = from_stack(Box::new(vfyfn), stack.clone(), &elem);
1583
1584        let multi_a_error: Result<Vec<SatisfiedConstraint>, Error> = constraints.collect();
1585        assert!(multi_a_error.is_err());
1586
1587        // multi_a correct thresh, but small stack
1588        let elem = x_only_no_checks_ms(&format!(
1589            "multi_a(3,{},{},{},{},{},{})",
1590            xpks[0], xpks[1], xpks[2], xpks[3], xpks[4], xpks[5]
1591        ));
1592        let constraints = from_stack(Box::new(vfyfn), stack, &elem);
1593
1594        let multi_a_error: Result<Vec<SatisfiedConstraint>, Error> = constraints.collect();
1595        assert!(multi_a_error.is_err());
1596    }
1597
1598    // By design there is no support for parse a miniscript with BitcoinKey
1599    // because it does not implement FromStr
1600    fn no_checks_ms(ms: &str) -> Miniscript<BitcoinKey, NoChecks> {
1601        // Parsing should allow raw hashes in the interpreter
1602        let elem: Miniscript<bellscoin::PublicKey, NoChecks> =
1603            Miniscript::from_str_ext(ms, &ExtParams::allow_all()).unwrap();
1604        elem.to_no_checks_ms()
1605    }
1606
1607    fn x_only_no_checks_ms(ms: &str) -> Miniscript<BitcoinKey, NoChecks> {
1608        let elem: Miniscript<bellscoin::key::XOnlyPublicKey, NoChecks> =
1609            Miniscript::from_str_ext(ms, &ExtParams::allow_all()).unwrap();
1610        elem.to_no_checks_ms()
1611    }
1612}
bells_miniscript/interpreter/mod.rs

bells_miniscript/interpreter/
mod.rs
