elements_miniscript/interpreter/
stack.rs

1// Written in 2020 by Sanket Kanjular and Andrew Poelstra
2// SPDX-License-Identifier: CC0-1.0
3
4//! Interpreter stack
5
6use std::ops::Index;
7
8use elements::hashes::{hash160, ripemd160, sha256, Hash};
9use elements::{self, opcodes, script, LockTime, Sequence};
10
11use super::error::PkEvalErrInner;
12use super::{verify_sersig, BitcoinKey, Error, HashLockType, KeySigPair, SatisfiedConstraint};
13use crate::miniscript::context::SigType;
14use crate::{hash256, Extension};
15
16/// Definition of Stack Element of the Stack used for interpretation of Miniscript.
17///
18/// All stack elements with `vec![]` go to `Element::Dissatisfied` and `vec![1]` are marked to
19/// `Element::Satisfied`. Others are directly pushed as witness.
20#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash)]
21pub enum Element<'txin> {
22    /// Result of a satisfied Miniscript fragment
23    /// Translated from `vec![1]` from input stack
24    Satisfied,
25    /// Result of a dissatisfied Miniscript fragment
26    /// Translated from `vec![]` from input stack
27    Dissatisfied,
28    /// Input from the witness stack
29    Push(&'txin [u8]),
30}
31
32impl<'txin> From<&'txin Vec<u8>> for Element<'txin> {
33    fn from(v: &'txin Vec<u8>) -> Element<'txin> {
34        From::from(&v[..])
35    }
36}
37
38impl<'txin> From<&'txin [u8]> for Element<'txin> {
39    fn from(v: &'txin [u8]) -> Element<'txin> {
40        if *v == [1] {
41            Element::Satisfied
42        } else if v.is_empty() {
43            Element::Dissatisfied
44        } else {
45            Element::Push(v)
46        }
47    }
48}
49
50impl<'txin> Element<'txin> {
51    /// Converts a Bitcoin `script::Instruction` to a stack element
52    ///
53    /// Supports `OP_1` but no other numbers since these are not used by Miniscript
54    pub fn from_instruction(
55        ins: Result<script::Instruction<'txin>, elements::script::Error>,
56    ) -> Result<Self, Error> {
57        match ins {
58            //Also covers the dissatisfied case as PushBytes0
59            Ok(script::Instruction::PushBytes(v)) => Ok(Element::from(v)),
60            Ok(script::Instruction::Op(opcodes::all::OP_PUSHNUM_1)) => Ok(Element::Satisfied),
61            _ => Err(Error::ExpectedPush),
62        }
63    }
64
65    /// Errs when the element is not a push
66    pub(crate) fn try_push(&self) -> Result<&[u8], Error> {
67        match self {
68            Element::Push(x) => Ok(x),
69            _ => Err(Error::ExpectedPush),
70        }
71    }
72
73    /// Convert element into slice
74    pub(crate) fn into_slice(self) -> &'txin [u8] {
75        match self {
76            Element::Satisfied => &[1],
77            Element::Dissatisfied => &[],
78            Element::Push(v) => v,
79        }
80    }
81
82    // Get push element as slice, returning UnexpectedBool otherwise
83    pub(super) fn as_push(&self) -> Result<&[u8], Error> {
84        if let Element::Push(sl) = *self {
85            Ok(sl)
86        } else {
87            Err(Error::UnexpectedStackBoolean)
88        }
89    }
90}
91
92/// Stack Data structure representing the stack input to Miniscript. This Stack
93/// is created from the combination of ScriptSig and Witness stack.
94#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash, Default)]
95pub struct Stack<'txin>(pub(super) Vec<Element<'txin>>);
96
97impl<'txin> From<Vec<Element<'txin>>> for Stack<'txin> {
98    fn from(v: Vec<Element<'txin>>) -> Self {
99        Stack(v)
100    }
101}
102
103impl<'txin> Index<usize> for Stack<'txin> {
104    type Output = Element<'txin>;
105
106    fn index(&self, index: usize) -> &Self::Output {
107        &self.0[index]
108    }
109}
110
111impl<'txin> Stack<'txin> {
112    /// Whether the stack is empty
113    pub fn is_empty(&self) -> bool {
114        self.0.is_empty()
115    }
116
117    /// Number of elements on the stack
118    pub fn len(&self) -> usize {
119        self.0.len()
120    }
121
122    /// Removes the top stack element, if the stack is nonempty
123    pub fn pop(&mut self) -> Option<Element<'txin>> {
124        self.0.pop()
125    }
126
127    /// Pushes an element onto the top of the stack
128    pub fn push(&mut self, elem: Element<'txin>) {
129        self.0.push(elem);
130    }
131
132    /// Returns a new stack representing the top `k` elements of the stack,
133    /// removing these elements from the original
134    pub fn split_off(&mut self, k: usize) -> Vec<Element<'txin>> {
135        self.0.split_off(k)
136    }
137
138    /// Returns a reference to the top stack element, if the stack is nonempty
139    pub fn last(&self) -> Option<&Element<'txin>> {
140        self.0.last()
141    }
142
143    /// Helper function to evaluate a Pk Node which takes the
144    /// top of the stack as input signature and validates it.
145    /// Sat: If the signature witness is correct, 1 is pushed
146    /// Unsat: For empty witness a 0 is pushed
147    /// Err: All of other witness result in errors.
148    /// `pk` CHECKSIG
149    pub(super) fn evaluate_pk<'intp, Ext: Extension>(
150        &mut self,
151        verify_sig: &mut Box<dyn FnMut(&KeySigPair) -> bool + 'intp>,
152        pk: BitcoinKey,
153    ) -> Option<Result<SatisfiedConstraint<Ext>, Error>> {
154        if let Some(sigser) = self.pop() {
155            match sigser {
156                Element::Dissatisfied => {
157                    self.push(Element::Dissatisfied);
158                    None
159                }
160                Element::Push(sigser) => {
161                    let key_sig = verify_sersig(verify_sig, &pk, sigser);
162                    match key_sig {
163                        Ok(key_sig) => {
164                            self.push(Element::Satisfied);
165                            Some(Ok(SatisfiedConstraint::PublicKey { key_sig }))
166                        }
167                        Err(e) => Some(Err(e)),
168                    }
169                }
170                Element::Satisfied => Some(Err(Error::PkEvaluationError(PkEvalErrInner::from(pk)))),
171            }
172        } else {
173            Some(Err(Error::UnexpectedStackEnd))
174        }
175    }
176
177    /// Helper function to evaluate a Pkh Node. Takes input as pubkey and sig
178    /// from the top of the stack and outputs Sat if the pubkey, sig is valid
179    /// Sat: If the pubkey hash matches and signature witness is correct,
180    /// Unsat: For an empty witness
181    /// Err: All of other witness result in errors.
182    /// `DUP HASH160 <keyhash> EQUALVERIY CHECKSIG`
183    pub(super) fn evaluate_pkh<'intp, Ext: Extension>(
184        &mut self,
185        verify_sig: &mut Box<dyn FnMut(&KeySigPair) -> bool + 'intp>,
186        pkh: hash160::Hash,
187        sig_type: SigType,
188    ) -> Option<Result<SatisfiedConstraint<Ext>, Error>> {
189        // Parse a bitcoin key from witness data slice depending on hash context
190        // when we encounter a pkh(hash)
191        // Depending on the tag of hash, we parse the as full key or x-only-key
192        // TODO: All keys parse errors are currently captured in a single BadPubErr
193        // We don't really store information about which key error.
194        fn bitcoin_key_from_slice(sl: &[u8], sig_type: SigType) -> Option<BitcoinKey> {
195            let key: BitcoinKey = match sig_type {
196                SigType::Schnorr => bitcoin::key::XOnlyPublicKey::from_slice(sl).ok()?.into(),
197                SigType::Ecdsa => bitcoin::PublicKey::from_slice(sl).ok()?.into(),
198            };
199            Some(key)
200        }
201        if let Some(Element::Push(pk)) = self.pop() {
202            let pk_hash = hash160::Hash::hash(pk);
203            if pk_hash != pkh {
204                return Some(Err(Error::PkHashVerifyFail(pkh)));
205            }
206            match bitcoin_key_from_slice(pk, sig_type) {
207                Some(pk) => {
208                    if let Some(sigser) = self.pop() {
209                        match sigser {
210                            Element::Dissatisfied => {
211                                self.push(Element::Dissatisfied);
212                                None
213                            }
214                            Element::Push(sigser) => {
215                                let key_sig = verify_sersig(verify_sig, &pk, sigser);
216                                match key_sig {
217                                    Ok(key_sig) => {
218                                        self.push(Element::Satisfied);
219                                        Some(Ok(SatisfiedConstraint::PublicKeyHash {
220                                            keyhash: pkh,
221                                            key_sig,
222                                        }))
223                                    }
224                                    Err(e) => Some(Err(e)),
225                                }
226                            }
227                            Element::Satisfied => Some(Err(Error::PkEvaluationError(pk.into()))),
228                        }
229                    } else {
230                        Some(Err(Error::UnexpectedStackEnd))
231                    }
232                }
233                None => Some(Err(Error::PubkeyParseError)),
234            }
235        } else {
236            Some(Err(Error::UnexpectedStackEnd))
237        }
238    }
239
240    /// Helper function to evaluate a After Node. Takes no argument from stack
241    /// `n CHECKLOCKTIMEVERIFY 0NOTEQUAL` and `n CHECKLOCKTIMEVERIFY`
242    /// Ideally this should return int value as n: build_scriptint(t as i64)),
243    /// The reason we don't need to copy the Script semantics is that
244    /// Miniscript never evaluates integers and it is safe to treat them as
245    /// booleans
246    pub(super) fn evaluate_after<Ext: Extension>(
247        &mut self,
248        n: &LockTime,
249        lock_time: LockTime,
250    ) -> Option<Result<SatisfiedConstraint<Ext>, Error>> {
251        use LockTime::*;
252
253        let is_satisfied = match (*n, lock_time) {
254            (Blocks(n), Blocks(lock_time)) => n <= lock_time,
255            (Seconds(n), Seconds(lock_time)) => n <= lock_time,
256            _ => {
257                return Some(Err(Error::AbsoluteLocktimeComparisonInvalid(
258                    n.to_consensus_u32(),
259                    lock_time.to_consensus_u32(),
260                )))
261            }
262        };
263
264        if is_satisfied {
265            self.push(Element::Satisfied);
266            Some(Ok(SatisfiedConstraint::AbsoluteTimelock { n: *n }))
267        } else {
268            Some(Err(Error::AbsoluteLocktimeNotMet(n.to_consensus_u32())))
269        }
270    }
271
272    /// Helper function to evaluate a Older Node. Takes no argument from stack
273    /// `n CHECKSEQUENCEVERIFY 0NOTEQUAL` and `n CHECKSEQUENCEVERIFY`
274    /// Ideally this should return int value as n: build_scriptint(t as i64)),
275    /// The reason we don't need to copy the Script semantics is that
276    /// Miniscript never evaluates integers and it is safe to treat them as
277    /// booleans
278    pub(super) fn evaluate_older<Ext: Extension>(
279        &mut self,
280        n: &Sequence,
281        age: Sequence,
282    ) -> Option<Result<SatisfiedConstraint<Ext>, Error>> {
283        if age >= *n {
284            self.push(Element::Satisfied);
285            Some(Ok(SatisfiedConstraint::RelativeTimelock { n: *n }))
286        } else {
287            Some(Err(Error::RelativeLocktimeNotMet(n.to_consensus_u32())))
288        }
289    }
290
291    /// Helper function to evaluate a Sha256 Node.
292    /// `SIZE 32 EQUALVERIFY SHA256 h EQUAL`
293    pub(super) fn evaluate_sha256<Ext: Extension>(
294        &mut self,
295        hash: &sha256::Hash,
296    ) -> Option<Result<SatisfiedConstraint<Ext>, Error>> {
297        if let Some(Element::Push(preimage)) = self.pop() {
298            if preimage.len() != 32 {
299                return Some(Err(Error::HashPreimageLengthMismatch));
300            }
301            if sha256::Hash::hash(preimage) == *hash {
302                self.push(Element::Satisfied);
303                Some(Ok(SatisfiedConstraint::HashLock {
304                    hash: HashLockType::Sha256(*hash),
305                    preimage: preimage_from_sl(preimage),
306                }))
307            } else {
308                self.push(Element::Dissatisfied);
309                None
310            }
311        } else {
312            Some(Err(Error::UnexpectedStackEnd))
313        }
314    }
315
316    /// Helper function to evaluate a Hash256 Node.
317    /// `SIZE 32 EQUALVERIFY HASH256 h EQUAL`
318    pub(super) fn evaluate_hash256<Ext: Extension>(
319        &mut self,
320        hash: &hash256::Hash,
321    ) -> Option<Result<SatisfiedConstraint<Ext>, Error>> {
322        if let Some(Element::Push(preimage)) = self.pop() {
323            if preimage.len() != 32 {
324                return Some(Err(Error::HashPreimageLengthMismatch));
325            }
326            if hash256::Hash::hash(preimage) == *hash {
327                self.push(Element::Satisfied);
328                Some(Ok(SatisfiedConstraint::HashLock {
329                    hash: HashLockType::Hash256(*hash),
330                    preimage: preimage_from_sl(preimage),
331                }))
332            } else {
333                self.push(Element::Dissatisfied);
334                None
335            }
336        } else {
337            Some(Err(Error::UnexpectedStackEnd))
338        }
339    }
340
341    /// Helper function to evaluate a Hash160 Node.
342    /// `SIZE 32 EQUALVERIFY HASH160 h EQUAL`
343    pub(super) fn evaluate_hash160<Ext: Extension>(
344        &mut self,
345        hash: &hash160::Hash,
346    ) -> Option<Result<SatisfiedConstraint<Ext>, Error>> {
347        if let Some(Element::Push(preimage)) = self.pop() {
348            if preimage.len() != 32 {
349                return Some(Err(Error::HashPreimageLengthMismatch));
350            }
351            if hash160::Hash::hash(preimage) == *hash {
352                self.push(Element::Satisfied);
353                Some(Ok(SatisfiedConstraint::HashLock {
354                    hash: HashLockType::Hash160(*hash),
355                    preimage: preimage_from_sl(preimage),
356                }))
357            } else {
358                self.push(Element::Dissatisfied);
359                None
360            }
361        } else {
362            Some(Err(Error::UnexpectedStackEnd))
363        }
364    }
365
366    /// Helper function to evaluate a RipeMd160 Node.
367    /// `SIZE 32 EQUALVERIFY RIPEMD160 h EQUAL`
368    pub(super) fn evaluate_ripemd160<Ext: Extension>(
369        &mut self,
370        hash: &ripemd160::Hash,
371    ) -> Option<Result<SatisfiedConstraint<Ext>, Error>> {
372        if let Some(Element::Push(preimage)) = self.pop() {
373            if preimage.len() != 32 {
374                return Some(Err(Error::HashPreimageLengthMismatch));
375            }
376            if ripemd160::Hash::hash(preimage) == *hash {
377                self.push(Element::Satisfied);
378                Some(Ok(SatisfiedConstraint::HashLock {
379                    hash: HashLockType::Ripemd160(*hash),
380                    preimage: preimage_from_sl(preimage),
381                }))
382            } else {
383                self.push(Element::Dissatisfied);
384                None
385            }
386        } else {
387            Some(Err(Error::UnexpectedStackEnd))
388        }
389    }
390
391    /// Helper function to evaluate a checkmultisig which takes the top of the
392    /// stack as input signatures and validates it in order of pubkeys.
393    /// For example, if the first signature is satisfied by second public key,
394    /// other signatures are not checked against the first pubkey.
395    /// `multi(2,pk1,pk2)` would be satisfied by `[0 sig2 sig1]` and Err on
396    /// `[0 sig2 sig1]`
397    pub(super) fn evaluate_multi<'intp, Ext: Extension>(
398        &mut self,
399        verify_sig: &mut Box<dyn FnMut(&KeySigPair) -> bool + 'intp>,
400        pk: &'intp BitcoinKey,
401    ) -> Option<Result<SatisfiedConstraint<Ext>, Error>> {
402        if let Some(witness_sig) = self.pop() {
403            if let Element::Push(sigser) = witness_sig {
404                let key_sig = verify_sersig(verify_sig, pk, sigser);
405                match key_sig {
406                    Ok(key_sig) => Some(Ok(SatisfiedConstraint::PublicKey { key_sig })),
407                    Err(..) => {
408                        self.push(witness_sig);
409                        None
410                    }
411                }
412            } else {
413                Some(Err(Error::UnexpectedStackBoolean))
414            }
415        } else {
416            Some(Err(Error::UnexpectedStackEnd))
417        }
418    }
419}
420
421// Helper function to compute preimage from slice
422fn preimage_from_sl(sl: &[u8]) -> [u8; 32] {
423    if sl.len() != 32 {
424        unreachable!("Internal: Preimage length checked to be 32")
425    } else {
426        let mut preimage = [0u8; 32];
427        preimage.copy_from_slice(sl);
428        preimage
429    }
430}
elements_miniscript/interpreter/stack.rs

elements_miniscript/interpreter/
stack.rs
