miniscript_debug/interpreter/
mod.rs

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

miniscript_debug/interpreter/
mod.rs
