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

miniscript/interpreter/
mod.rs
