elements_miniscript/miniscript/
astelem.rs

1// Written in 2019 by Andrew Poelstra <apoelstra@wpsoftware.net>
2// SPDX-License-Identifier: CC0-1.0
3
4//! AST Elements
5//!
6//! Datatype describing a Miniscript "script fragment", which are the
7//! building blocks of all Miniscripts. Each fragment has a unique
8//! encoding in Bitcoin script, as well as a datatype. Full details
9//! are given on the Miniscript website.
10
11use std::fmt;
12use std::str::FromStr;
13use std::sync::Arc;
14
15use bitcoin::hashes::hash160;
16use elements::{opcodes, script, Sequence};
17
18use super::limits::{MAX_SCRIPT_ELEMENT_SIZE, MAX_STANDARD_P2WSH_STACK_ITEM_SIZE};
19use crate::extensions::ParseableExt;
20use crate::miniscript::context::SigType;
21use crate::miniscript::types;
22use crate::miniscript::ScriptContext;
23use crate::util::MsKeyBuilder;
24use crate::{
25    errstr, expression, script_num_size, AbsLockTime, Error, ExtTranslator, Extension, ForEachKey,
26    Miniscript, MiniscriptKey, Terminal, ToPublicKey, TranslateExt, TranslatePk, Translator,
27};
28
29impl<Pk: MiniscriptKey, Ctx: ScriptContext, Ext: Extension> Terminal<Pk, Ctx, Ext> {
30    /// Internal helper function for displaying wrapper types; returns
31    /// a character to display before the `:` as well as a reference
32    /// to the wrapped type to allow easy recursion
33    fn wrap_char(&self) -> Option<(char, &Arc<Miniscript<Pk, Ctx, Ext>>)> {
34        match *self {
35            Terminal::Alt(ref sub) => Some(('a', sub)),
36            Terminal::Swap(ref sub) => Some(('s', sub)),
37            Terminal::Check(ref sub) => Some(('c', sub)),
38            Terminal::DupIf(ref sub) => Some(('d', sub)),
39            Terminal::Verify(ref sub) => Some(('v', sub)),
40            Terminal::NonZero(ref sub) => Some(('j', sub)),
41            Terminal::ZeroNotEqual(ref sub) => Some(('n', sub)),
42            Terminal::AndV(ref sub, ref r) if r.node == Terminal::True => Some(('t', sub)),
43            Terminal::OrI(ref sub, ref r) if r.node == Terminal::False => Some(('u', sub)),
44            Terminal::OrI(ref l, ref sub) if l.node == Terminal::False => Some(('l', sub)),
45            _ => None,
46        }
47    }
48}
49
50impl<Pk, Q, Ctx, Ext> TranslatePk<Pk, Q> for Terminal<Pk, Ctx, Ext>
51where
52    Pk: MiniscriptKey,
53    Q: MiniscriptKey,
54    Ctx: ScriptContext,
55    Ext: Extension,
56{
57    type Output = Terminal<Q, Ctx, Ext>;
58
59    /// Converts an AST element with one public key type to one of another public key type.
60    fn translate_pk<T, E>(&self, translate: &mut T) -> Result<Self::Output, E>
61    where
62        T: Translator<Pk, Q, E>,
63    {
64        self.real_translate_pk(translate)
65    }
66}
67
68impl<Pk, Ctx, Ext, QExt> TranslateExt<Ext, QExt> for Terminal<Pk, Ctx, Ext>
69where
70    Pk: MiniscriptKey,
71    Ctx: ScriptContext,
72    Ext: Extension,
73    QExt: Extension,
74    Ext: TranslateExt<Ext, QExt, Output = QExt>,
75{
76    type Output = Terminal<Pk, Ctx, <Ext as TranslateExt<Ext, QExt>>::Output>;
77
78    fn translate_ext<T, E>(&self, translator: &mut T) -> Result<Self::Output, E>
79    where
80        T: ExtTranslator<Ext, QExt, E>,
81    {
82        self.real_translate_ext(translator)
83    }
84}
85
86impl<Pk: MiniscriptKey, Ctx: ScriptContext, Ext: Extension> Terminal<Pk, Ctx, Ext> {
87    pub(super) fn real_for_each_key<'a, F: FnMut(&'a Pk) -> bool>(&'a self, pred: &mut F) -> bool
88    where
89        Pk: 'a,
90    {
91        match *self {
92            Terminal::PkK(ref p) => pred(p),
93            Terminal::PkH(ref p) => pred(p),
94            Terminal::RawPkH(..)
95            | Terminal::After(..)
96            | Terminal::Older(..)
97            | Terminal::Sha256(..)
98            | Terminal::Hash256(..)
99            | Terminal::Ripemd160(..)
100            | Terminal::Hash160(..)
101            | Terminal::True
102            | Terminal::False => true,
103            Terminal::Alt(ref sub)
104            | Terminal::Swap(ref sub)
105            | Terminal::Check(ref sub)
106            | Terminal::DupIf(ref sub)
107            | Terminal::Verify(ref sub)
108            | Terminal::NonZero(ref sub)
109            | Terminal::ZeroNotEqual(ref sub) => sub.real_for_each_key(pred),
110            Terminal::AndV(ref left, ref right)
111            | Terminal::AndB(ref left, ref right)
112            | Terminal::OrB(ref left, ref right)
113            | Terminal::OrD(ref left, ref right)
114            | Terminal::OrC(ref left, ref right)
115            | Terminal::OrI(ref left, ref right) => {
116                left.real_for_each_key(&mut *pred) && right.real_for_each_key(pred)
117            }
118            Terminal::AndOr(ref a, ref b, ref c) => {
119                a.real_for_each_key(&mut *pred)
120                    && b.real_for_each_key(&mut *pred)
121                    && c.real_for_each_key(pred)
122            }
123            Terminal::Thresh(_, ref subs) => subs.iter().all(|sub| sub.real_for_each_key(pred)),
124            Terminal::Multi(_, ref keys) | Terminal::MultiA(_, ref keys) => keys.iter().all(pred),
125            Terminal::Ext(ref _e) => true,
126        }
127    }
128
129    pub(super) fn real_translate_pk<Q, CtxQ, T, E>(
130        &self,
131        t: &mut T,
132    ) -> Result<Terminal<Q, CtxQ, Ext>, E>
133    where
134        Q: MiniscriptKey,
135        CtxQ: ScriptContext,
136        T: Translator<Pk, Q, E>,
137    {
138        let frag: Terminal<Q, CtxQ, _> = match *self {
139            Terminal::PkK(ref p) => Terminal::PkK(t.pk(p)?),
140            Terminal::PkH(ref p) => Terminal::PkH(t.pk(p)?),
141            Terminal::RawPkH(ref p) => Terminal::RawPkH(*p),
142            Terminal::After(n) => Terminal::After(n),
143            Terminal::Older(n) => Terminal::Older(n),
144            Terminal::Sha256(ref x) => Terminal::Sha256(t.sha256(x)?),
145            Terminal::Hash256(ref x) => Terminal::Hash256(t.hash256(x)?),
146            Terminal::Ripemd160(ref x) => Terminal::Ripemd160(t.ripemd160(x)?),
147            Terminal::Hash160(ref x) => Terminal::Hash160(t.hash160(x)?),
148            Terminal::True => Terminal::True,
149            Terminal::False => Terminal::False,
150            Terminal::Alt(ref sub) => Terminal::Alt(Arc::new(sub.real_translate_pk(t)?)),
151            Terminal::Swap(ref sub) => Terminal::Swap(Arc::new(sub.real_translate_pk(t)?)),
152            Terminal::Check(ref sub) => Terminal::Check(Arc::new(sub.real_translate_pk(t)?)),
153            Terminal::DupIf(ref sub) => Terminal::DupIf(Arc::new(sub.real_translate_pk(t)?)),
154            Terminal::Verify(ref sub) => Terminal::Verify(Arc::new(sub.real_translate_pk(t)?)),
155            Terminal::NonZero(ref sub) => Terminal::NonZero(Arc::new(sub.real_translate_pk(t)?)),
156            Terminal::ZeroNotEqual(ref sub) => {
157                Terminal::ZeroNotEqual(Arc::new(sub.real_translate_pk(t)?))
158            }
159            Terminal::AndV(ref left, ref right) => Terminal::AndV(
160                Arc::new(left.real_translate_pk(t)?),
161                Arc::new(right.real_translate_pk(t)?),
162            ),
163            Terminal::AndB(ref left, ref right) => Terminal::AndB(
164                Arc::new(left.real_translate_pk(t)?),
165                Arc::new(right.real_translate_pk(t)?),
166            ),
167            Terminal::AndOr(ref a, ref b, ref c) => Terminal::AndOr(
168                Arc::new(a.real_translate_pk(t)?),
169                Arc::new(b.real_translate_pk(t)?),
170                Arc::new(c.real_translate_pk(t)?),
171            ),
172            Terminal::OrB(ref left, ref right) => Terminal::OrB(
173                Arc::new(left.real_translate_pk(t)?),
174                Arc::new(right.real_translate_pk(t)?),
175            ),
176            Terminal::OrD(ref left, ref right) => Terminal::OrD(
177                Arc::new(left.real_translate_pk(t)?),
178                Arc::new(right.real_translate_pk(t)?),
179            ),
180            Terminal::OrC(ref left, ref right) => Terminal::OrC(
181                Arc::new(left.real_translate_pk(t)?),
182                Arc::new(right.real_translate_pk(t)?),
183            ),
184            Terminal::OrI(ref left, ref right) => Terminal::OrI(
185                Arc::new(left.real_translate_pk(t)?),
186                Arc::new(right.real_translate_pk(t)?),
187            ),
188            Terminal::Thresh(k, ref subs) => {
189                let subs: Result<Vec<Arc<Miniscript<Q, _, _>>>, _> = subs
190                    .iter()
191                    .map(|s| s.real_translate_pk(t).map(Arc::new))
192                    .collect();
193                Terminal::Thresh(k, subs?)
194            }
195            Terminal::Multi(k, ref keys) => {
196                let keys: Result<Vec<Q>, _> = keys.iter().map(|k| t.pk(k)).collect();
197                Terminal::Multi(k, keys?)
198            }
199            Terminal::MultiA(k, ref keys) => {
200                let keys: Result<Vec<Q>, _> = keys.iter().map(|k| t.pk(k)).collect();
201                Terminal::MultiA(k, keys?)
202            }
203            // Translate Pk does not translate extensions
204            // use TranslateExt
205            Terminal::Ext(ref e) => Terminal::Ext(e.clone()),
206        };
207        Ok(frag)
208    }
209
210    pub(super) fn real_translate_ext<T, E, ExtQ>(
211        &self,
212        t: &mut T,
213    ) -> Result<Terminal<Pk, Ctx, ExtQ>, E>
214    where
215        ExtQ: Extension,
216        T: ExtTranslator<Ext, ExtQ, E>,
217        Ext: TranslateExt<Ext, ExtQ, Output = ExtQ>,
218    {
219        let frag: Terminal<Pk, Ctx, ExtQ> = match *self {
220            Terminal::PkK(ref p) => Terminal::PkK(p.clone()),
221            Terminal::PkH(ref p) => Terminal::PkH(p.clone()),
222            Terminal::RawPkH(ref h) => Terminal::RawPkH(*h),
223            Terminal::After(n) => Terminal::After(n),
224            Terminal::Older(n) => Terminal::Older(n),
225            Terminal::Sha256(ref x) => Terminal::Sha256(x.clone()),
226            Terminal::Hash256(ref x) => Terminal::Hash256(x.clone()),
227            Terminal::Ripemd160(ref x) => Terminal::Ripemd160(x.clone()),
228            Terminal::Hash160(ref x) => Terminal::Hash160(x.clone()),
229            Terminal::True => Terminal::True,
230            Terminal::False => Terminal::False,
231            Terminal::Alt(ref sub) => Terminal::Alt(Arc::new(sub.real_translate_ext(t)?)),
232            Terminal::Swap(ref sub) => Terminal::Swap(Arc::new(sub.real_translate_ext(t)?)),
233            Terminal::Check(ref sub) => Terminal::Check(Arc::new(sub.real_translate_ext(t)?)),
234            Terminal::DupIf(ref sub) => Terminal::DupIf(Arc::new(sub.real_translate_ext(t)?)),
235            Terminal::Verify(ref sub) => Terminal::Verify(Arc::new(sub.real_translate_ext(t)?)),
236            Terminal::NonZero(ref sub) => Terminal::NonZero(Arc::new(sub.real_translate_ext(t)?)),
237            Terminal::ZeroNotEqual(ref sub) => {
238                Terminal::ZeroNotEqual(Arc::new(sub.real_translate_ext(t)?))
239            }
240            Terminal::AndV(ref left, ref right) => Terminal::AndV(
241                Arc::new(left.real_translate_ext(t)?),
242                Arc::new(right.real_translate_ext(t)?),
243            ),
244            Terminal::AndB(ref left, ref right) => Terminal::AndB(
245                Arc::new(left.real_translate_ext(t)?),
246                Arc::new(right.real_translate_ext(t)?),
247            ),
248            Terminal::AndOr(ref a, ref b, ref c) => Terminal::AndOr(
249                Arc::new(a.real_translate_ext(t)?),
250                Arc::new(b.real_translate_ext(t)?),
251                Arc::new(c.real_translate_ext(t)?),
252            ),
253            Terminal::OrB(ref left, ref right) => Terminal::OrB(
254                Arc::new(left.real_translate_ext(t)?),
255                Arc::new(right.real_translate_ext(t)?),
256            ),
257            Terminal::OrD(ref left, ref right) => Terminal::OrD(
258                Arc::new(left.real_translate_ext(t)?),
259                Arc::new(right.real_translate_ext(t)?),
260            ),
261            Terminal::OrC(ref left, ref right) => Terminal::OrC(
262                Arc::new(left.real_translate_ext(t)?),
263                Arc::new(right.real_translate_ext(t)?),
264            ),
265            Terminal::OrI(ref left, ref right) => Terminal::OrI(
266                Arc::new(left.real_translate_ext(t)?),
267                Arc::new(right.real_translate_ext(t)?),
268            ),
269            Terminal::Thresh(k, ref subs) => {
270                let subs: Result<Vec<Arc<Miniscript<Pk, _, _>>>, _> = subs
271                    .iter()
272                    .map(|s| s.real_translate_ext(t).map(Arc::new))
273                    .collect();
274                Terminal::Thresh(k, subs?)
275            }
276            Terminal::Multi(k, ref keys) => Terminal::Multi(k, keys.clone()),
277            Terminal::MultiA(k, ref keys) => Terminal::MultiA(k, keys.clone()),
278            Terminal::Ext(ref e) => Terminal::Ext(e.translate_ext(t)?),
279        };
280        Ok(frag)
281    }
282}
283
284impl<Pk, Ctx, Ext> ForEachKey<Pk> for Terminal<Pk, Ctx, Ext>
285where
286    Pk: MiniscriptKey,
287    Ctx: ScriptContext,
288    Ext: Extension,
289{
290    fn for_each_key<'a, F: FnMut(&'a Pk) -> bool>(&'a self, mut pred: F) -> bool
291    where
292        Pk: 'a,
293    {
294        self.real_for_each_key(&mut pred)
295    }
296}
297
298impl<Pk, Ctx, Ext> fmt::Debug for Terminal<Pk, Ctx, Ext>
299where
300    Pk: MiniscriptKey,
301    Ctx: ScriptContext,
302    Ext: Extension,
303{
304    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
305        f.write_str("[")?;
306        if let Ok(type_map) = types::Type::type_check(self) {
307            f.write_str(match type_map.corr.base {
308                types::Base::B => "B",
309                types::Base::K => "K",
310                types::Base::V => "V",
311                types::Base::W => "W",
312            })?;
313            fmt::Write::write_char(f, '/')?;
314            f.write_str(match type_map.corr.input {
315                types::Input::Zero => "z",
316                types::Input::One => "o",
317                types::Input::OneNonZero => "on",
318                types::Input::Any => "",
319                types::Input::AnyNonZero => "n",
320            })?;
321            if type_map.corr.dissatisfiable {
322                fmt::Write::write_char(f, 'd')?;
323            }
324            if type_map.corr.unit {
325                fmt::Write::write_char(f, 'u')?;
326            }
327            f.write_str(match type_map.mall.dissat {
328                types::Dissat::None => "f",
329                types::Dissat::Unique => "e",
330                types::Dissat::Unknown => "",
331            })?;
332            if type_map.mall.safe {
333                fmt::Write::write_char(f, 's')?;
334            }
335            if type_map.mall.non_malleable {
336                fmt::Write::write_char(f, 'm')?;
337            }
338        } else {
339            f.write_str("TYPECHECK FAILED")?;
340        }
341        f.write_str("]")?;
342        if let Some((ch, sub)) = self.wrap_char() {
343            fmt::Write::write_char(f, ch)?;
344            if sub.node.wrap_char().is_none() {
345                fmt::Write::write_char(f, ':')?;
346            }
347            write!(f, "{:?}", sub)
348        } else {
349            match *self {
350                Terminal::PkK(ref pk) => write!(f, "pk_k({:?})", pk),
351                Terminal::PkH(ref pk) => write!(f, "pk_h({:?})", pk),
352                Terminal::RawPkH(ref pkh) => write!(f, "expr_raw_pk_h({:?})", pkh),
353                Terminal::After(t) => write!(f, "after({})", t),
354                Terminal::Older(t) => write!(f, "older({})", t),
355                Terminal::Sha256(ref h) => write!(f, "sha256({})", h),
356                Terminal::Hash256(ref h) => write!(f, "hash256({})", h),
357                Terminal::Ripemd160(ref h) => write!(f, "ripemd160({})", h),
358                Terminal::Hash160(ref h) => write!(f, "hash160({})", h),
359                Terminal::True => f.write_str("1"),
360                Terminal::False => f.write_str("0"),
361                Terminal::Ext(ref e) => write!(f, "{:?}", e),
362                Terminal::AndV(ref l, ref r) => write!(f, "and_v({:?},{:?})", l, r),
363                Terminal::AndB(ref l, ref r) => write!(f, "and_b({:?},{:?})", l, r),
364                Terminal::AndOr(ref a, ref b, ref c) => {
365                    if c.node == Terminal::False {
366                        write!(f, "and_n({:?},{:?})", a, b)
367                    } else {
368                        write!(f, "andor({:?},{:?},{:?})", a, b, c)
369                    }
370                }
371                Terminal::OrB(ref l, ref r) => write!(f, "or_b({:?},{:?})", l, r),
372                Terminal::OrD(ref l, ref r) => write!(f, "or_d({:?},{:?})", l, r),
373                Terminal::OrC(ref l, ref r) => write!(f, "or_c({:?},{:?})", l, r),
374                Terminal::OrI(ref l, ref r) => write!(f, "or_i({:?},{:?})", l, r),
375                Terminal::Thresh(k, ref subs) => {
376                    write!(f, "thresh({}", k)?;
377                    for s in subs {
378                        write!(f, ",{:?}", s)?;
379                    }
380                    f.write_str(")")
381                }
382                Terminal::Multi(k, ref keys) => {
383                    write!(f, "multi({}", k)?;
384                    for k in keys {
385                        write!(f, ",{:?}", k)?;
386                    }
387                    f.write_str(")")
388                }
389                Terminal::MultiA(k, ref keys) => {
390                    write!(f, "multi_a({}", k)?;
391                    for k in keys {
392                        write!(f, ",{}", k)?;
393                    }
394                    f.write_str(")")
395                }
396                _ => unreachable!(),
397            }
398        }
399    }
400}
401
402impl<Pk, Ctx, Ext> fmt::Display for Terminal<Pk, Ctx, Ext>
403where
404    Pk: MiniscriptKey,
405    Ctx: ScriptContext,
406    Ext: Extension,
407{
408    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
409        match *self {
410            Terminal::PkK(ref pk) => write!(f, "pk_k({})", pk),
411            Terminal::PkH(ref pk) => write!(f, "pk_h({})", pk),
412            Terminal::RawPkH(ref pkh) => write!(f, "expr_raw_pk_h({})", pkh),
413            Terminal::After(t) => write!(f, "after({})", t),
414            Terminal::Older(t) => write!(f, "older({})", t),
415            Terminal::Sha256(ref h) => write!(f, "sha256({})", h),
416            Terminal::Hash256(ref h) => write!(f, "hash256({})", h),
417            Terminal::Ripemd160(ref h) => write!(f, "ripemd160({})", h),
418            Terminal::Hash160(ref h) => write!(f, "hash160({})", h),
419            Terminal::True => f.write_str("1"),
420            Terminal::False => f.write_str("0"),
421            Terminal::Ext(ref e) => write!(f, "{}", e),
422            Terminal::AndV(ref l, ref r) if r.node != Terminal::True => {
423                write!(f, "and_v({},{})", l, r)
424            }
425            Terminal::AndB(ref l, ref r) => write!(f, "and_b({},{})", l, r),
426            Terminal::AndOr(ref a, ref b, ref c) => {
427                if c.node == Terminal::False {
428                    write!(f, "and_n({},{})", a, b)
429                } else {
430                    write!(f, "andor({},{},{})", a, b, c)
431                }
432            }
433            Terminal::OrB(ref l, ref r) => write!(f, "or_b({},{})", l, r),
434            Terminal::OrD(ref l, ref r) => write!(f, "or_d({},{})", l, r),
435            Terminal::OrC(ref l, ref r) => write!(f, "or_c({},{})", l, r),
436            Terminal::OrI(ref l, ref r)
437                if l.node != Terminal::False && r.node != Terminal::False =>
438            {
439                write!(f, "or_i({},{})", l, r)
440            }
441            Terminal::Thresh(k, ref subs) => {
442                write!(f, "thresh({}", k)?;
443                for s in subs {
444                    write!(f, ",{}", s)?;
445                }
446                f.write_str(")")
447            }
448            Terminal::Multi(k, ref keys) => {
449                write!(f, "multi({}", k)?;
450                for k in keys {
451                    write!(f, ",{}", k)?;
452                }
453                f.write_str(")")
454            }
455            Terminal::MultiA(k, ref keys) => {
456                write!(f, "multi_a({}", k)?;
457                for k in keys {
458                    write!(f, ",{}", k)?;
459                }
460                f.write_str(")")
461            }
462            // wrappers
463            _ => {
464                if let Some((ch, sub)) = self.wrap_char() {
465                    if ch == 'c' {
466                        if let Terminal::PkK(ref pk) = sub.node {
467                            // alias: pk(K) = c:pk_k(K)
468                            return write!(f, "pk({})", pk);
469                        } else if let Terminal::RawPkH(ref pkh) = sub.node {
470                            // `RawPkH` is currently unsupported in the descriptor spec
471                            // alias: pkh(K) = c:pk_h(K)
472                            // We temporarily display there using raw_pkh, but these descriptors
473                            // are not defined in the spec yet. These are prefixed with `expr`
474                            // in the descriptor string.
475                            // We do not support parsing these descriptors yet.
476                            return write!(f, "expr_raw_pkh({})", pkh);
477                        } else if let Terminal::PkH(ref pk) = sub.node {
478                            // alias: pkh(K) = c:pk_h(K)
479                            return write!(f, "pkh({})", pk);
480                        }
481                    }
482
483                    fmt::Write::write_char(f, ch)?;
484                    match sub.node.wrap_char() {
485                        None => {
486                            fmt::Write::write_char(f, ':')?;
487                        }
488                        // Add a ':' wrapper if there are other wrappers apart from c:pk_k()
489                        // tvc:pk_k() -> tv:pk()
490                        Some(('c', ms)) => match ms.node {
491                            Terminal::PkK(_) | Terminal::PkH(_) | Terminal::RawPkH(_) => {
492                                fmt::Write::write_char(f, ':')?
493                            }
494                            _ => {}
495                        },
496                        _ => {}
497                    };
498                    write!(f, "{}", sub)
499                } else {
500                    unreachable!();
501                }
502            }
503        }
504    }
505}
506
507impl_from_tree!(
508    ;Ctx; ScriptContext,
509    Arc<Terminal<Pk, Ctx, Ext>>,
510    => Ext ; Extension,
511    fn from_tree(top: &expression::Tree<'_>) -> Result<Arc<Terminal<Pk, Ctx, Ext>>, Error> {
512        Ok(Arc::new(expression::FromTree::from_tree(top)?))
513    }
514);
515
516impl_from_tree!(
517    ;Ctx; ScriptContext,
518    Terminal<Pk, Ctx, Ext>,
519    => Ext ; Extension,
520    fn from_tree(top: &expression::Tree<'_>) -> Result<Terminal<Pk, Ctx, Ext>, Error> {
521        let mut aliased_wrap;
522        let frag_name;
523        let frag_wrap;
524        let mut name_split = top.name.split(':');
525        match (name_split.next(), name_split.next(), name_split.next()) {
526            (None, _, _) => {
527                frag_name = "";
528                frag_wrap = "";
529            }
530            (Some(name), None, _) => {
531                if name == "pk" {
532                    frag_name = "pk_k";
533                    frag_wrap = "c";
534                } else if name == "pkh" {
535                    frag_name = "pk_h";
536                    frag_wrap = "c";
537                } else {
538                    frag_name = name;
539                    frag_wrap = "";
540                }
541            }
542            (Some(wrap), Some(name), None) => {
543                if wrap.is_empty() {
544                    return Err(Error::Unexpected(top.name.to_owned()));
545                }
546                if name == "pk" {
547                    frag_name = "pk_k";
548                    aliased_wrap = wrap.to_owned();
549                    aliased_wrap.push('c');
550                    frag_wrap = &aliased_wrap;
551                } else if name == "pkh" {
552                    frag_name = "pk_h";
553                    aliased_wrap = wrap.to_owned();
554                    aliased_wrap.push('c');
555                    frag_wrap = &aliased_wrap;
556                } else {
557                    frag_name = name;
558                    frag_wrap = wrap;
559                }
560            }
561            (Some(_), Some(_), Some(_)) => {
562                return Err(Error::MultiColon(top.name.to_owned()));
563            }
564        }
565        let mut unwrapped = match (frag_name, top.args.len()) {
566            ("expr_raw_pkh", 1) => expression::terminal(&top.args[0], |x| {
567                hash160::Hash::from_str(x).map(Terminal::RawPkH)
568            }),
569            ("pk_k", 1) => {
570                expression::terminal(&top.args[0], |x| Pk::from_str(x).map(Terminal::PkK))
571            }
572            ("pk_h", 1) => expression::terminal(&top.args[0], |x| Pk::from_str(x).map(Terminal::PkH)),
573            ("after", 1) => expression::terminal(&top.args[0], |x| {
574                expression::parse_num::<u32>(x).map(|x| Terminal::After(AbsLockTime::from_consensus(x)))
575            }),
576            ("older", 1) => expression::terminal(&top.args[0], |x| {
577                expression::parse_num::<u32>(x).map(|x| Terminal::Older(Sequence::from_consensus(x)))
578            }),
579            ("sha256", 1) => expression::terminal(&top.args[0], |x| {
580                Pk::Sha256::from_str(x).map(Terminal::Sha256)
581            }),
582            ("hash256", 1) => expression::terminal(&top.args[0], |x| {
583                Pk::Hash256::from_str(x).map(Terminal::Hash256)
584            }),
585            ("ripemd160", 1) => expression::terminal(&top.args[0], |x| {
586                Pk::Ripemd160::from_str(x).map(Terminal::Ripemd160)
587            }),
588            ("hash160", 1) => expression::terminal(&top.args[0], |x| {
589                Pk::Hash160::from_str(x).map(Terminal::Hash160)
590            }),
591            ("1", 0) => Ok(Terminal::True),
592            ("0", 0) => Ok(Terminal::False),
593            ("and_v", 2) => expression::binary(top, Terminal::AndV),
594            ("and_b", 2) => expression::binary(top, Terminal::AndB),
595            ("and_n", 2) => Ok(Terminal::AndOr(
596                expression::FromTree::from_tree(&top.args[0])?,
597                expression::FromTree::from_tree(&top.args[1])?,
598                Arc::new(Miniscript::from_ast(Terminal::False)?),
599            )),
600            ("andor", 3) => Ok(Terminal::AndOr(
601                expression::FromTree::from_tree(&top.args[0])?,
602                expression::FromTree::from_tree(&top.args[1])?,
603                expression::FromTree::from_tree(&top.args[2])?,
604            )),
605            ("or_b", 2) => expression::binary(top, Terminal::OrB),
606            ("or_d", 2) => expression::binary(top, Terminal::OrD),
607            ("or_c", 2) => expression::binary(top, Terminal::OrC),
608            ("or_i", 2) => expression::binary(top, Terminal::OrI),
609            ("thresh", n) => {
610                if n == 0 {
611                    return Err(errstr("no arguments given"));
612                }
613                let k = expression::terminal(&top.args[0], expression::parse_num::<u32>)? as usize;
614                if k > n - 1 {
615                    return Err(errstr("higher threshold than there are subexpressions"));
616                }
617                if n == 1 {
618                    return Err(errstr("empty thresholds not allowed in descriptors"));
619                }
620
621                let subs: Result<Vec<Arc<Miniscript<Pk, Ctx, Ext>>>, _> = top.args[1..]
622                    .iter()
623                    .map(expression::FromTree::from_tree)
624                    .collect();
625
626                Ok(Terminal::Thresh(k, subs?))
627            }
628            ("multi", n) | ("multi_a", n) => {
629                if n == 0 {
630                    return Err(errstr("no arguments given"));
631                }
632                let k = expression::terminal(&top.args[0], expression::parse_num::<u32>)? as usize;
633                if k > n - 1 {
634                    return Err(errstr("higher threshold than there were keys in multi"));
635                }
636
637                let pks: Result<Vec<Pk>, _> = top.args[1..]
638                    .iter()
639                    .map(|sub| expression::terminal(sub, Pk::from_str))
640                    .collect();
641
642                if frag_name == "multi" {
643                    pks.map(|pks| Terminal::Multi(k, pks))
644                } else {
645                    // must be multi_a
646                    pks.map(|pks| Terminal::MultiA(k, pks))
647                }
648            }
649            (name, _num_child) => {
650                // If nothing matches try to parse as extension
651                match Ext::from_name_tree(name, &top.args) {
652                    Ok(e) => Ok(Terminal::Ext(e)),
653                    Err(..) => Err(Error::Unexpected(format!(
654                        "{}({} args) while parsing Miniscript",
655                        top.name,
656                        top.args.len(),
657                    ))),
658                }
659            }
660        }?;
661        for ch in frag_wrap.chars().rev() {
662            // Check whether the wrapper is valid under the current context
663            let ms = Miniscript::from_ast(unwrapped)?;
664            Ctx::check_global_validity(&ms)?;
665            match ch {
666                'a' => unwrapped = Terminal::Alt(Arc::new(ms)),
667                's' => unwrapped = Terminal::Swap(Arc::new(ms)),
668                'c' => unwrapped = Terminal::Check(Arc::new(ms)),
669                'd' => unwrapped = Terminal::DupIf(Arc::new(ms)),
670                'v' => unwrapped = Terminal::Verify(Arc::new(ms)),
671                'j' => unwrapped = Terminal::NonZero(Arc::new(ms)),
672                'n' => unwrapped = Terminal::ZeroNotEqual(Arc::new(ms)),
673                't' => {
674                    unwrapped = Terminal::AndV(
675                        Arc::new(ms),
676                        Arc::new(Miniscript::from_ast(Terminal::True)?),
677                    )
678                }
679                'u' => {
680                    unwrapped = Terminal::OrI(
681                        Arc::new(ms),
682                        Arc::new(Miniscript::from_ast(Terminal::False)?),
683                    )
684                }
685                'l' => {
686                    if ms.node == Terminal::False {
687                        return Err(Error::LikelyFalse);
688                    }
689                    unwrapped = Terminal::OrI(
690                        Arc::new(Miniscript::from_ast(Terminal::False)?),
691                        Arc::new(ms),
692                    )
693                }
694                x => return Err(Error::UnknownWrapper(x)),
695            }
696        }
697        // Check whether the unwrapped miniscript is valid under the current context
698        let ms = Miniscript::from_ast(unwrapped)?;
699        Ctx::check_global_validity(&ms)?;
700        Ok(ms.node)
701    }
702);
703
704/// Helper trait to add a `push_astelem` method to `script::Builder`
705trait PushAstElem<Pk: ToPublicKey, Ctx: ScriptContext, Ext: ParseableExt> {
706    fn push_astelem(self, ast: &Miniscript<Pk, Ctx, Ext>) -> Self;
707}
708
709impl<Pk: ToPublicKey, Ctx: ScriptContext, Ext: ParseableExt> PushAstElem<Pk, Ctx, Ext>
710    for script::Builder
711{
712    fn push_astelem(self, ast: &Miniscript<Pk, Ctx, Ext>) -> Self {
713        ast.node.encode(self)
714    }
715}
716
717/// Additional operations required on Script
718/// for supporting Miniscript fragments that
719/// have access to a global context
720pub trait StackCtxOperations: Sized {
721    /// pick an element indexed from the bottom of
722    /// the stack. This cannot check whether the idx is within
723    /// stack limits.
724    /// Copies the element at index idx to the top of the stack
725    /// Checks item equality against the specified target
726    fn check_item_eq(self, idx: u32, target: &[u8]) -> Self;
727
728    /// Since, there is a policy restriction that initial pushes must be
729    /// only 80 bytes, we need user to provide suffix in separate items
730    /// There can be atmost 7 cats, because the script element must be less
731    /// than 520 bytes total in order to compute an hash256 on it.
732    /// Even if the witness does not require 7 pushes, the user should push
733    /// 7 elements with possibly empty values.
734    ///
735    /// Copies the script item at position and compare the hash256
736    /// with it
737    fn check_item_pref(self, idx: u32, pref: &[u8]) -> Self;
738}
739
740impl StackCtxOperations for script::Builder {
741    fn check_item_eq(self, idx: u32, target: &[u8]) -> Self {
742        self.push_opcode(opcodes::all::OP_DEPTH)
743            .push_int(idx as i64)
744            .push_opcode(opcodes::all::OP_SUB)
745            .push_opcode(opcodes::all::OP_PICK)
746            .push_slice(target)
747            .push_opcode(opcodes::all::OP_EQUAL)
748    }
749
750    fn check_item_pref(self, idx: u32, pref: &[u8]) -> Self {
751        let mut builder = self;
752        // Initial Witness
753        // The nuumber of maximum witness elements in the suffix
754        let max_elems = MAX_SCRIPT_ELEMENT_SIZE / MAX_STANDARD_P2WSH_STACK_ITEM_SIZE + 1;
755        for _ in 0..(max_elems - 1) {
756            builder = builder.push_opcode(opcodes::all::OP_CAT);
757        }
758        builder = builder
759            .push_slice(pref)
760            .push_opcode(opcodes::all::OP_SWAP)
761            .push_opcode(opcodes::all::OP_CAT);
762        // Now the stack top is serialization of all the outputs
763        builder = builder.push_opcode(opcodes::all::OP_HASH256);
764
765        builder
766            .push_opcode(opcodes::all::OP_DEPTH)
767            .push_int(idx as i64)
768            .push_opcode(opcodes::all::OP_SUB)
769            .push_opcode(opcodes::all::OP_PICK)
770            .push_opcode(opcodes::all::OP_EQUAL)
771    }
772}
773
774impl<Pk: MiniscriptKey, Ctx: ScriptContext, Ext: Extension> Terminal<Pk, Ctx, Ext> {
775    /// Encode the element as a fragment of Bitcoin Script. The inverse
776    /// function, from Script to an AST element, is implemented in the
777    /// `parse` module.
778    pub fn encode(&self, mut builder: script::Builder) -> script::Builder
779    where
780        Pk: ToPublicKey,
781        Ext: ParseableExt,
782    {
783        match *self {
784            Terminal::PkK(ref pk) => builder.push_ms_key::<_, Ctx>(pk),
785            Terminal::PkH(ref pk) => builder
786                .push_opcode(opcodes::all::OP_DUP)
787                .push_opcode(opcodes::all::OP_HASH160)
788                .push_ms_key_hash::<_, Ctx>(pk)
789                .push_opcode(opcodes::all::OP_EQUALVERIFY),
790            Terminal::RawPkH(ref hash) => builder
791                .push_opcode(opcodes::all::OP_DUP)
792                .push_opcode(opcodes::all::OP_HASH160)
793                .push_slice(hash.as_ref())
794                .push_opcode(opcodes::all::OP_EQUALVERIFY),
795            Terminal::After(t) => builder
796                .push_int(t.to_u32().into())
797                .push_opcode(opcodes::all::OP_CLTV),
798            Terminal::Older(t) => builder
799                .push_int(t.to_consensus_u32().into())
800                .push_opcode(opcodes::all::OP_CSV),
801            Terminal::Sha256(ref h) => builder
802                .push_opcode(opcodes::all::OP_SIZE)
803                .push_int(32)
804                .push_opcode(opcodes::all::OP_EQUALVERIFY)
805                .push_opcode(opcodes::all::OP_SHA256)
806                .push_slice(Pk::to_sha256(h).as_ref())
807                .push_opcode(opcodes::all::OP_EQUAL),
808            Terminal::Hash256(ref h) => builder
809                .push_opcode(opcodes::all::OP_SIZE)
810                .push_int(32)
811                .push_opcode(opcodes::all::OP_EQUALVERIFY)
812                .push_opcode(opcodes::all::OP_HASH256)
813                .push_slice(Pk::to_hash256(h).as_ref())
814                .push_opcode(opcodes::all::OP_EQUAL),
815            Terminal::Ripemd160(ref h) => builder
816                .push_opcode(opcodes::all::OP_SIZE)
817                .push_int(32)
818                .push_opcode(opcodes::all::OP_EQUALVERIFY)
819                .push_opcode(opcodes::all::OP_RIPEMD160)
820                .push_slice(Pk::to_ripemd160(h).as_ref())
821                .push_opcode(opcodes::all::OP_EQUAL),
822            Terminal::Hash160(ref h) => builder
823                .push_opcode(opcodes::all::OP_SIZE)
824                .push_int(32)
825                .push_opcode(opcodes::all::OP_EQUALVERIFY)
826                .push_opcode(opcodes::all::OP_HASH160)
827                .push_slice(Pk::to_hash160(h).as_ref())
828                .push_opcode(opcodes::all::OP_EQUAL),
829            Terminal::True => builder.push_opcode(opcodes::OP_TRUE),
830            Terminal::False => builder.push_opcode(opcodes::OP_FALSE),
831            Terminal::Alt(ref sub) => builder
832                .push_opcode(opcodes::all::OP_TOALTSTACK)
833                .push_astelem(sub)
834                .push_opcode(opcodes::all::OP_FROMALTSTACK),
835            Terminal::Swap(ref sub) => builder.push_opcode(opcodes::all::OP_SWAP).push_astelem(sub),
836            Terminal::Check(ref sub) => builder
837                .push_astelem(sub)
838                .push_opcode(opcodes::all::OP_CHECKSIG),
839            Terminal::DupIf(ref sub) => builder
840                .push_opcode(opcodes::all::OP_DUP)
841                .push_opcode(opcodes::all::OP_IF)
842                .push_astelem(sub)
843                .push_opcode(opcodes::all::OP_ENDIF),
844            Terminal::Verify(ref sub) => builder.push_astelem(sub).push_verify(),
845            Terminal::NonZero(ref sub) => builder
846                .push_opcode(opcodes::all::OP_SIZE)
847                .push_opcode(opcodes::all::OP_0NOTEQUAL)
848                .push_opcode(opcodes::all::OP_IF)
849                .push_astelem(sub)
850                .push_opcode(opcodes::all::OP_ENDIF),
851            Terminal::ZeroNotEqual(ref sub) => builder
852                .push_astelem(sub)
853                .push_opcode(opcodes::all::OP_0NOTEQUAL),
854            Terminal::AndV(ref left, ref right) => builder.push_astelem(left).push_astelem(right),
855            Terminal::AndB(ref left, ref right) => builder
856                .push_astelem(left)
857                .push_astelem(right)
858                .push_opcode(opcodes::all::OP_BOOLAND),
859            Terminal::AndOr(ref a, ref b, ref c) => builder
860                .push_astelem(a)
861                .push_opcode(opcodes::all::OP_NOTIF)
862                .push_astelem(c)
863                .push_opcode(opcodes::all::OP_ELSE)
864                .push_astelem(b)
865                .push_opcode(opcodes::all::OP_ENDIF),
866            Terminal::OrB(ref left, ref right) => builder
867                .push_astelem(left)
868                .push_astelem(right)
869                .push_opcode(opcodes::all::OP_BOOLOR),
870            Terminal::OrD(ref left, ref right) => builder
871                .push_astelem(left)
872                .push_opcode(opcodes::all::OP_IFDUP)
873                .push_opcode(opcodes::all::OP_NOTIF)
874                .push_astelem(right)
875                .push_opcode(opcodes::all::OP_ENDIF),
876            Terminal::OrC(ref left, ref right) => builder
877                .push_astelem(left)
878                .push_opcode(opcodes::all::OP_NOTIF)
879                .push_astelem(right)
880                .push_opcode(opcodes::all::OP_ENDIF),
881            Terminal::OrI(ref left, ref right) => builder
882                .push_opcode(opcodes::all::OP_IF)
883                .push_astelem(left)
884                .push_opcode(opcodes::all::OP_ELSE)
885                .push_astelem(right)
886                .push_opcode(opcodes::all::OP_ENDIF),
887            Terminal::Thresh(k, ref subs) => {
888                builder = builder.push_astelem(&subs[0]);
889                for sub in &subs[1..] {
890                    builder = builder.push_astelem(sub).push_opcode(opcodes::all::OP_ADD);
891                }
892                builder
893                    .push_int(k as i64)
894                    .push_opcode(opcodes::all::OP_EQUAL)
895            }
896            Terminal::Multi(k, ref keys) => {
897                debug_assert!(Ctx::sig_type() == SigType::Ecdsa);
898                builder = builder.push_int(k as i64);
899                for pk in keys {
900                    builder = builder.push_key(&pk.to_public_key());
901                }
902                builder
903                    .push_int(keys.len() as i64)
904                    .push_opcode(opcodes::all::OP_CHECKMULTISIG)
905            }
906            Terminal::MultiA(k, ref keys) => {
907                debug_assert!(Ctx::sig_type() == SigType::Schnorr);
908                // keys must be atleast len 1 here, guaranteed by typing rules
909                builder = builder.push_ms_key::<_, Ctx>(&keys[0]);
910                builder = builder.push_opcode(opcodes::all::OP_CHECKSIG);
911                for pk in keys.iter().skip(1) {
912                    builder = builder.push_ms_key::<_, Ctx>(pk);
913                    builder = builder.push_opcode(opcodes::all::OP_CHECKSIGADD);
914                }
915                builder
916                    .push_int(k as i64)
917                    .push_opcode(opcodes::all::OP_NUMEQUAL)
918            }
919            Terminal::Ext(ref e) => e.push_to_builder(builder),
920        }
921    }
922
923    /// Size, in bytes of the script-pubkey. If this Miniscript is used outside
924    /// of segwit (e.g. in a bare or P2SH descriptor), this quantity should be
925    /// multiplied by 4 to compute the weight.
926    ///
927    /// In general, it is not recommended to use this function directly, but
928    /// to instead call the corresponding function on a `Descriptor`, which
929    /// will handle the segwit/non-segwit technicalities for you.
930    pub fn script_size(&self) -> usize {
931        match *self {
932            Terminal::PkK(ref pk) => Ctx::pk_len(pk),
933            Terminal::PkH(..) | Terminal::RawPkH(..) => 24,
934            Terminal::After(n) => script_num_size(n.to_u32() as usize) + 1,
935            Terminal::Older(n) => script_num_size(n.to_consensus_u32() as usize) + 1,
936            Terminal::Sha256(..) => 33 + 6,
937            Terminal::Hash256(..) => 33 + 6,
938            Terminal::Ripemd160(..) => 21 + 6,
939            Terminal::Hash160(..) => 21 + 6,
940            Terminal::True => 1,
941            Terminal::False => 1,
942            Terminal::Alt(ref sub) => sub.node.script_size() + 2,
943            Terminal::Swap(ref sub) => sub.node.script_size() + 1,
944            Terminal::Check(ref sub) => sub.node.script_size() + 1,
945            Terminal::DupIf(ref sub) => sub.node.script_size() + 3,
946            Terminal::Verify(ref sub) => {
947                sub.node.script_size() + usize::from(!sub.ext.has_free_verify)
948            }
949            Terminal::NonZero(ref sub) => sub.node.script_size() + 4,
950            Terminal::ZeroNotEqual(ref sub) => sub.node.script_size() + 1,
951            Terminal::AndV(ref l, ref r) => l.node.script_size() + r.node.script_size(),
952            Terminal::AndB(ref l, ref r) => l.node.script_size() + r.node.script_size() + 1,
953            Terminal::AndOr(ref a, ref b, ref c) => {
954                a.node.script_size() + b.node.script_size() + c.node.script_size() + 3
955            }
956            Terminal::OrB(ref l, ref r) => l.node.script_size() + r.node.script_size() + 1,
957            Terminal::OrD(ref l, ref r) => l.node.script_size() + r.node.script_size() + 3,
958            Terminal::OrC(ref l, ref r) => l.node.script_size() + r.node.script_size() + 2,
959            Terminal::OrI(ref l, ref r) => l.node.script_size() + r.node.script_size() + 3,
960            Terminal::Thresh(k, ref subs) => {
961                assert!(!subs.is_empty(), "threshold must be nonempty");
962                script_num_size(k) // k
963                    + 1 // EQUAL
964                    + subs.iter().map(|s| s.node.script_size()).sum::<usize>()
965                    + subs.len() // ADD
966                    - 1 // no ADD on first element
967            }
968            Terminal::Multi(k, ref pks) => {
969                script_num_size(k)
970                    + 1
971                    + script_num_size(pks.len())
972                    + pks.iter().map(|pk| Ctx::pk_len(pk)).sum::<usize>()
973            }
974            Terminal::MultiA(k, ref pks) => {
975                script_num_size(k)
976                    + 1 // NUMEQUAL
977                    + pks.iter().map(|pk| Ctx::pk_len(pk)).sum::<usize>() // n keys
978                    + pks.len() // n times CHECKSIGADD
979            }
980            Terminal::Ext(ref e) => e.script_size(),
981        }
982    }
983}
elements_miniscript/miniscript/astelem.rs

elements_miniscript/miniscript/
astelem.rs
