miniscript/descriptor/
tr.rs

1// SPDX-License-Identifier: CC0-1.0
2
3use core::str::FromStr;
4use core::{cmp, fmt, hash};
5
6#[cfg(not(test))] // https://github.com/rust-lang/rust/issues/121684
7use bitcoin::secp256k1;
8use bitcoin::taproot::{
9    LeafVersion, TaprootBuilder, TaprootSpendInfo, TAPROOT_CONTROL_BASE_SIZE,
10    TAPROOT_CONTROL_MAX_NODE_COUNT, TAPROOT_CONTROL_NODE_SIZE,
11};
12use bitcoin::{opcodes, Address, Network, ScriptBuf, Weight};
13use sync::Arc;
14
15use super::checksum::{self, verify_checksum};
16use crate::descriptor::DefiniteDescriptorKey;
17use crate::expression::{self, FromTree};
18use crate::miniscript::satisfy::{Placeholder, Satisfaction, SchnorrSigType, Witness};
19use crate::miniscript::Miniscript;
20use crate::plan::AssetProvider;
21use crate::policy::semantic::Policy;
22use crate::policy::Liftable;
23use crate::prelude::*;
24use crate::util::{varint_len, witness_size};
25use crate::{
26    errstr, Error, ForEachKey, FromStrKey, MiniscriptKey, Satisfier, ScriptContext, Tap, Threshold,
27    ToPublicKey, TranslateErr, TranslatePk, Translator,
28};
29
30/// A Taproot Tree representation.
31// Hidden leaves are not yet supported in descriptor spec. Conceptually, it should
32// be simple to integrate those here, but it is best to wait on core for the exact syntax.
33#[derive(Clone, Ord, PartialOrd, Eq, PartialEq, Hash)]
34pub enum TapTree<Pk: MiniscriptKey> {
35    /// A taproot tree structure
36    Tree {
37        /// Left tree branch.
38        left: Arc<TapTree<Pk>>,
39        /// Right tree branch.
40        right: Arc<TapTree<Pk>>,
41        /// Tree height, defined as `1 + max(left_height, right_height)`.
42        height: usize,
43    },
44    /// A taproot leaf denoting a spending condition
45    // A new leaf version would require a new Context, therefore there is no point
46    // in adding a LeafVersion with Leaf type here. All Miniscripts right now
47    // are of Leafversion::default
48    Leaf(Arc<Miniscript<Pk, Tap>>),
49}
50
51/// A taproot descriptor
52pub struct Tr<Pk: MiniscriptKey> {
53    /// A taproot internal key
54    internal_key: Pk,
55    /// Optional Taproot Tree with spending conditions
56    tree: Option<TapTree<Pk>>,
57    /// Optional spending information associated with the descriptor
58    /// This will be [`None`] when the descriptor is not derived.
59    /// This information will be cached automatically when it is required
60    //
61    // The inner `Arc` here is because Rust does not allow us to return a reference
62    // to the contents of the `Option` from inside a `MutexGuard`. There is no outer
63    // `Arc` because when this structure is cloned, we create a whole new mutex.
64    spend_info: Mutex<Option<Arc<TaprootSpendInfo>>>,
65}
66
67impl<Pk: MiniscriptKey> Clone for Tr<Pk> {
68    fn clone(&self) -> Self {
69        // When cloning, construct a new Mutex so that distinct clones don't
70        // cause blocking between each other. We clone only the internal `Arc`,
71        // so the clone is always cheap (in both time and space)
72        Self {
73            internal_key: self.internal_key.clone(),
74            tree: self.tree.clone(),
75            spend_info: Mutex::new(
76                self.spend_info
77                    .lock()
78                    .expect("Lock poisoned")
79                    .as_ref()
80                    .map(Arc::clone),
81            ),
82        }
83    }
84}
85
86impl<Pk: MiniscriptKey> PartialEq for Tr<Pk> {
87    fn eq(&self, other: &Self) -> bool {
88        self.internal_key == other.internal_key && self.tree == other.tree
89    }
90}
91
92impl<Pk: MiniscriptKey> Eq for Tr<Pk> {}
93
94impl<Pk: MiniscriptKey> PartialOrd for Tr<Pk> {
95    fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> { Some(self.cmp(other)) }
96}
97
98impl<Pk: MiniscriptKey> Ord for Tr<Pk> {
99    fn cmp(&self, other: &Self) -> cmp::Ordering {
100        match self.internal_key.cmp(&other.internal_key) {
101            cmp::Ordering::Equal => {}
102            ord => return ord,
103        }
104        self.tree.cmp(&other.tree)
105    }
106}
107
108impl<Pk: MiniscriptKey> hash::Hash for Tr<Pk> {
109    fn hash<H: hash::Hasher>(&self, state: &mut H) {
110        self.internal_key.hash(state);
111        self.tree.hash(state);
112    }
113}
114
115impl<Pk: MiniscriptKey> TapTree<Pk> {
116    /// Creates a `TapTree` by combining `left` and `right` tree nodes.
117    pub fn combine(left: TapTree<Pk>, right: TapTree<Pk>) -> Self {
118        let height = 1 + cmp::max(left.height(), right.height());
119        TapTree::Tree { left: Arc::new(left), right: Arc::new(right), height }
120    }
121
122    /// Returns the height of this tree.
123    pub fn height(&self) -> usize {
124        match *self {
125            TapTree::Tree { left: _, right: _, height } => height,
126            TapTree::Leaf(..) => 0,
127        }
128    }
129
130    /// Iterates over all miniscripts in DFS walk order compatible with the
131    /// PSBT requirements (BIP 371).
132    pub fn iter(&self) -> TapTreeIter<'_, Pk> { TapTreeIter { stack: vec![(0, self)] } }
133
134    // Helper function to translate keys
135    fn translate_helper<T, Q, E>(&self, t: &mut T) -> Result<TapTree<Q>, TranslateErr<E>>
136    where
137        T: Translator<Pk, Q, E>,
138        Q: MiniscriptKey,
139    {
140        let frag = match *self {
141            TapTree::Tree { ref left, ref right, ref height } => TapTree::Tree {
142                left: Arc::new(left.translate_helper(t)?),
143                right: Arc::new(right.translate_helper(t)?),
144                height: *height,
145            },
146            TapTree::Leaf(ref ms) => TapTree::Leaf(Arc::new(ms.translate_pk(t)?)),
147        };
148        Ok(frag)
149    }
150}
151
152impl<Pk: MiniscriptKey> fmt::Display for TapTree<Pk> {
153    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
154        match self {
155            TapTree::Tree { ref left, ref right, height: _ } => {
156                write!(f, "{{{},{}}}", *left, *right)
157            }
158            TapTree::Leaf(ref script) => write!(f, "{}", *script),
159        }
160    }
161}
162
163impl<Pk: MiniscriptKey> fmt::Debug for TapTree<Pk> {
164    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
165        match self {
166            TapTree::Tree { ref left, ref right, height: _ } => {
167                write!(f, "{{{:?},{:?}}}", *left, *right)
168            }
169            TapTree::Leaf(ref script) => write!(f, "{:?}", *script),
170        }
171    }
172}
173
174impl<Pk: MiniscriptKey> Tr<Pk> {
175    /// Create a new [`Tr`] descriptor from internal key and [`TapTree`]
176    pub fn new(internal_key: Pk, tree: Option<TapTree<Pk>>) -> Result<Self, Error> {
177        Tap::check_pk(&internal_key)?;
178        let nodes = tree.as_ref().map(|t| t.height()).unwrap_or(0);
179
180        if nodes <= TAPROOT_CONTROL_MAX_NODE_COUNT {
181            Ok(Self { internal_key, tree, spend_info: Mutex::new(None) })
182        } else {
183            Err(Error::MaxRecursiveDepthExceeded)
184        }
185    }
186
187    /// Obtain the internal key of [`Tr`] descriptor
188    pub fn internal_key(&self) -> &Pk { &self.internal_key }
189
190    /// Obtain the [`TapTree`] of the [`Tr`] descriptor
191    pub fn tap_tree(&self) -> &Option<TapTree<Pk>> { &self.tree }
192
193    /// Obtain the [`TapTree`] of the [`Tr`] descriptor
194    #[deprecated(since = "11.0.0", note = "use tap_tree instead")]
195    pub fn taptree(&self) -> &Option<TapTree<Pk>> { self.tap_tree() }
196
197    /// Iterate over all scripts in merkle tree. If there is no script path, the iterator
198    /// yields [`None`]
199    pub fn iter_scripts(&self) -> TapTreeIter<'_, Pk> {
200        match self.tree {
201            Some(ref t) => t.iter(),
202            None => TapTreeIter { stack: vec![] },
203        }
204    }
205
206    /// Compute the [`TaprootSpendInfo`] associated with this descriptor if spend data is `None`.
207    ///
208    /// If spend data is already computed (i.e it is not `None`), this does not recompute it.
209    ///
210    /// [`TaprootSpendInfo`] is only required for spending via the script paths.
211    pub fn spend_info(&self) -> Arc<TaprootSpendInfo>
212    where
213        Pk: ToPublicKey,
214    {
215        // If the value is already cache, read it
216        // read only panics if the lock is poisoned (meaning other thread having a lock panicked)
217        let read_lock = self.spend_info.lock().expect("Lock poisoned");
218        if let Some(ref spend_info) = *read_lock {
219            return Arc::clone(spend_info);
220        }
221        drop(read_lock);
222
223        // Get a new secp context
224        // This would be cheap operation after static context support from upstream
225        let secp = secp256k1::Secp256k1::verification_only();
226        // Key spend path with no merkle root
227        let data = if self.tree.is_none() {
228            TaprootSpendInfo::new_key_spend(&secp, self.internal_key.to_x_only_pubkey(), None)
229        } else {
230            let mut builder = TaprootBuilder::new();
231            for (depth, ms) in self.iter_scripts() {
232                let script = ms.encode();
233                builder = builder
234                    .add_leaf(depth, script)
235                    .expect("Computing spend data on a valid Tree should always succeed");
236            }
237            // Assert builder cannot error here because we have a well formed descriptor
238            match builder.finalize(&secp, self.internal_key.to_x_only_pubkey()) {
239                Ok(data) => data,
240                Err(_) => unreachable!("We know the builder can be finalized"),
241            }
242        };
243        let spend_info = Arc::new(data);
244        *self.spend_info.lock().expect("Lock poisoned") = Some(Arc::clone(&spend_info));
245        spend_info
246    }
247
248    /// Checks whether the descriptor is safe.
249    pub fn sanity_check(&self) -> Result<(), Error> {
250        for (_depth, ms) in self.iter_scripts() {
251            ms.sanity_check()?;
252        }
253        Ok(())
254    }
255
256    /// Computes an upper bound on the difference between a non-satisfied
257    /// `TxIn`'s `segwit_weight` and a satisfied `TxIn`'s `segwit_weight`
258    ///
259    /// Assumes all Schnorr signatures are 66 bytes, including push opcode and
260    /// sighash suffix.
261    ///
262    /// # Errors
263    /// When the descriptor is impossible to safisfy (ex: sh(OP_FALSE)).
264    pub fn max_weight_to_satisfy(&self) -> Result<Weight, Error> {
265        let tree = match self.tap_tree() {
266            None => {
267                // key spend path
268                // item: varint(sig+sigHash) + <sig(64)+sigHash(1)>
269                let item_sig_size = 1 + 65;
270                // 1 stack item
271                let stack_varint_diff = varint_len(1) - varint_len(0);
272
273                return Ok(Weight::from_wu((stack_varint_diff + item_sig_size) as u64));
274            }
275            // script path spend..
276            Some(tree) => tree,
277        };
278
279        let wu = tree
280            .iter()
281            .filter_map(|(depth, ms)| {
282                let script_size = ms.script_size();
283                let max_sat_elems = ms.max_satisfaction_witness_elements().ok()?;
284                let max_sat_size = ms.max_satisfaction_size().ok()?;
285                let control_block_size = control_block_len(depth);
286
287                // stack varint difference (+1 for ctrl block, witness script already included)
288                let stack_varint_diff = varint_len(max_sat_elems + 1) - varint_len(0);
289
290                Some(
291                    stack_varint_diff +
292                    // size of elements to satisfy script
293                    max_sat_size +
294                    // second to last element: script
295                    varint_len(script_size) +
296                    script_size +
297                    // last element: control block
298                    varint_len(control_block_size) +
299                    control_block_size,
300                )
301            })
302            .max()
303            .ok_or(Error::ImpossibleSatisfaction)?;
304
305        Ok(Weight::from_wu(wu as u64))
306    }
307
308    /// Computes an upper bound on the weight of a satisfying witness to the
309    /// transaction.
310    ///
311    /// Assumes all ec-signatures are 73 bytes, including push opcode and
312    /// sighash suffix. Includes the weight of the VarInts encoding the
313    /// scriptSig and witness stack length.
314    ///
315    /// # Errors
316    /// When the descriptor is impossible to safisfy (ex: sh(OP_FALSE)).
317    #[deprecated(
318        since = "10.0.0",
319        note = "Use max_weight_to_satisfy instead. The method to count bytes was redesigned and the results will differ from max_weight_to_satisfy. For more details check rust-bitcoin/rust-miniscript#476."
320    )]
321    pub fn max_satisfaction_weight(&self) -> Result<usize, Error> {
322        let tree = match self.tap_tree() {
323            // key spend path:
324            // scriptSigLen(4) + stackLen(1) + stack[Sig]Len(1) + stack[Sig](65)
325            None => return Ok(4 + 1 + 1 + 65),
326            // script path spend..
327            Some(tree) => tree,
328        };
329
330        tree.iter()
331            .filter_map(|(depth, ms)| {
332                let script_size = ms.script_size();
333                let max_sat_elems = ms.max_satisfaction_witness_elements().ok()?;
334                let max_sat_size = ms.max_satisfaction_size().ok()?;
335                let control_block_size = control_block_len(depth);
336                Some(
337                    // scriptSig len byte
338                    4 +
339                    // witness field stack len (+2 for control block & script)
340                    varint_len(max_sat_elems + 2) +
341                    // size of elements to satisfy script
342                    max_sat_size +
343                    // second to last element: script
344                    varint_len(script_size) +
345                    script_size +
346                    // last element: control block
347                    varint_len(control_block_size) +
348                    control_block_size,
349                )
350            })
351            .max()
352            .ok_or(Error::ImpossibleSatisfaction)
353    }
354}
355
356impl<Pk: MiniscriptKey + ToPublicKey> Tr<Pk> {
357    /// Obtains the corresponding script pubkey for this descriptor.
358    pub fn script_pubkey(&self) -> ScriptBuf {
359        let output_key = self.spend_info().output_key();
360        let builder = bitcoin::blockdata::script::Builder::new();
361        builder
362            .push_opcode(opcodes::all::OP_PUSHNUM_1)
363            .push_slice(output_key.serialize())
364            .into_script()
365    }
366
367    /// Obtains the corresponding address for this descriptor.
368    pub fn address(&self, network: Network) -> Address {
369        let spend_info = self.spend_info();
370        Address::p2tr_tweaked(spend_info.output_key(), network)
371    }
372
373    /// Returns satisfying non-malleable witness and scriptSig with minimum
374    /// weight to spend an output controlled by the given descriptor if it is
375    /// possible to construct one using the `satisfier`.
376    pub fn get_satisfaction<S>(&self, satisfier: &S) -> Result<(Vec<Vec<u8>>, ScriptBuf), Error>
377    where
378        S: Satisfier<Pk>,
379    {
380        let satisfaction = best_tap_spend(self, satisfier, false /* allow_mall */)
381            .try_completing(satisfier)
382            .expect("the same satisfier should manage to complete the template");
383        if let Witness::Stack(stack) = satisfaction.stack {
384            Ok((stack, ScriptBuf::new()))
385        } else {
386            Err(Error::CouldNotSatisfy)
387        }
388    }
389
390    /// Returns satisfying, possibly malleable, witness and scriptSig with
391    /// minimum weight to spend an output controlled by the given descriptor if
392    /// it is possible to construct one using the `satisfier`.
393    pub fn get_satisfaction_mall<S>(
394        &self,
395        satisfier: &S,
396    ) -> Result<(Vec<Vec<u8>>, ScriptBuf), Error>
397    where
398        S: Satisfier<Pk>,
399    {
400        let satisfaction = best_tap_spend(self, satisfier, true /* allow_mall */)
401            .try_completing(satisfier)
402            .expect("the same satisfier should manage to complete the template");
403        if let Witness::Stack(stack) = satisfaction.stack {
404            Ok((stack, ScriptBuf::new()))
405        } else {
406            Err(Error::CouldNotSatisfy)
407        }
408    }
409}
410
411impl Tr<DefiniteDescriptorKey> {
412    /// Returns a plan if the provided assets are sufficient to produce a non-malleable satisfaction
413    pub fn plan_satisfaction<P>(
414        &self,
415        provider: &P,
416    ) -> Satisfaction<Placeholder<DefiniteDescriptorKey>>
417    where
418        P: AssetProvider<DefiniteDescriptorKey>,
419    {
420        best_tap_spend(self, provider, false /* allow_mall */)
421    }
422
423    /// Returns a plan if the provided assets are sufficient to produce a malleable satisfaction
424    pub fn plan_satisfaction_mall<P>(
425        &self,
426        provider: &P,
427    ) -> Satisfaction<Placeholder<DefiniteDescriptorKey>>
428    where
429        P: AssetProvider<DefiniteDescriptorKey>,
430    {
431        best_tap_spend(self, provider, true /* allow_mall */)
432    }
433}
434
435/// Iterator for Taproot structures
436/// Yields a pair of (depth, miniscript) in a depth first walk
437/// For example, this tree:
438///                                     - N0 -
439///                                    /     \\
440///                                   N1      N2
441///                                  /  \    /  \\
442///                                 A    B  C   N3
443///                                            /  \\
444///                                           D    E
445/// would yield (2, A), (2, B), (2,C), (3, D), (3, E).
446///
447#[derive(Debug, Clone)]
448pub struct TapTreeIter<'a, Pk: MiniscriptKey> {
449    stack: Vec<(u8, &'a TapTree<Pk>)>,
450}
451
452impl<'a, Pk> Iterator for TapTreeIter<'a, Pk>
453where
454    Pk: MiniscriptKey + 'a,
455{
456    type Item = (u8, &'a Miniscript<Pk, Tap>);
457
458    fn next(&mut self) -> Option<Self::Item> {
459        while let Some((depth, last)) = self.stack.pop() {
460            match *last {
461                TapTree::Tree { ref left, ref right, height: _ } => {
462                    self.stack.push((depth + 1, right));
463                    self.stack.push((depth + 1, left));
464                }
465                TapTree::Leaf(ref ms) => return Some((depth, ms)),
466            }
467        }
468        None
469    }
470}
471
472#[rustfmt::skip]
473impl<Pk: FromStrKey> Tr<Pk> {
474    // Helper function to parse taproot script path
475    fn parse_tr_script_spend(tree: &expression::Tree,) -> Result<TapTree<Pk>, Error> {
476        match tree {
477            expression::Tree { name, args } if !name.is_empty() && args.is_empty() => {
478                let script = Miniscript::<Pk, Tap>::from_str(name)?;
479                Ok(TapTree::Leaf(Arc::new(script)))
480            }
481            expression::Tree { name, args } if name.is_empty() && args.len() == 2 => {
482                let left = Self::parse_tr_script_spend(&args[0])?;
483                let right = Self::parse_tr_script_spend(&args[1])?;
484                Ok(TapTree::combine(left, right))
485            }
486            _ => Err(Error::Unexpected(
487                "unknown format for script spending paths while parsing taproot descriptor"
488                    .to_string(),
489            )),
490        }
491    }
492}
493
494impl<Pk: FromStrKey> crate::expression::FromTree for Tr<Pk> {
495    fn from_tree(top: &expression::Tree) -> Result<Self, Error> {
496        if top.name == "tr" {
497            match top.args.len() {
498                1 => {
499                    let key = &top.args[0];
500                    if !key.args.is_empty() {
501                        return Err(Error::Unexpected(format!(
502                            "#{} script associated with `key-path` while parsing taproot descriptor",
503                            key.args.len()
504                        )));
505                    }
506                    Tr::new(expression::terminal(key, Pk::from_str)?, None)
507                }
508                2 => {
509                    let key = &top.args[0];
510                    if !key.args.is_empty() {
511                        return Err(Error::Unexpected(format!(
512                            "#{} script associated with `key-path` while parsing taproot descriptor",
513                            key.args.len()
514                        )));
515                    }
516                    let tree = &top.args[1];
517                    let ret = Self::parse_tr_script_spend(tree)?;
518                    Tr::new(expression::terminal(key, Pk::from_str)?, Some(ret))
519                }
520                _ => Err(Error::Unexpected(format!(
521                    "{}[#{} args] while parsing taproot descriptor",
522                    top.name,
523                    top.args.len()
524                ))),
525            }
526        } else {
527            Err(Error::Unexpected(format!(
528                "{}[#{} args] while parsing taproot descriptor",
529                top.name,
530                top.args.len()
531            )))
532        }
533    }
534}
535
536impl<Pk: FromStrKey> core::str::FromStr for Tr<Pk> {
537    type Err = Error;
538    fn from_str(s: &str) -> Result<Self, Self::Err> {
539        let desc_str = verify_checksum(s)?;
540        let top = parse_tr_tree(desc_str)?;
541        Self::from_tree(&top)
542    }
543}
544
545impl<Pk: MiniscriptKey> fmt::Debug for Tr<Pk> {
546    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
547        match self.tree {
548            Some(ref s) => write!(f, "tr({:?},{:?})", self.internal_key, s),
549            None => write!(f, "tr({:?})", self.internal_key),
550        }
551    }
552}
553
554impl<Pk: MiniscriptKey> fmt::Display for Tr<Pk> {
555    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
556        use fmt::Write;
557        let mut wrapped_f = checksum::Formatter::new(f);
558        let key = &self.internal_key;
559        match self.tree {
560            Some(ref s) => write!(wrapped_f, "tr({},{})", key, s)?,
561            None => write!(wrapped_f, "tr({})", key)?,
562        }
563        wrapped_f.write_checksum_if_not_alt()
564    }
565}
566
567// Helper function to parse string into miniscript tree form
568fn parse_tr_tree(s: &str) -> Result<expression::Tree<'_>, Error> {
569    expression::check_valid_chars(s)?;
570
571    if s.len() > 3 && &s[..3] == "tr(" && s.as_bytes()[s.len() - 1] == b')' {
572        let rest = &s[3..s.len() - 1];
573        if !rest.contains(',') {
574            let key = expression::Tree::from_str(rest)?;
575            if !key.args.is_empty() {
576                return Err(Error::Unexpected("invalid taproot internal key".to_string()));
577            }
578            let internal_key = expression::Tree { name: key.name, args: vec![] };
579            return Ok(expression::Tree { name: "tr", args: vec![internal_key] });
580        }
581        // use str::split_once() method to refactor this when compiler version bumps up
582        let (key, script) = split_once(rest, ',')
583            .ok_or_else(|| Error::BadDescriptor("invalid taproot descriptor".to_string()))?;
584
585        let key = expression::Tree::from_str(key)?;
586        if !key.args.is_empty() {
587            return Err(Error::Unexpected("invalid taproot internal key".to_string()));
588        }
589        let internal_key = expression::Tree { name: key.name, args: vec![] };
590        let (tree, rest) = expression::Tree::from_slice_delim(script, 1, '{')?;
591        if rest.is_empty() {
592            Ok(expression::Tree { name: "tr", args: vec![internal_key, tree] })
593        } else {
594            Err(errstr(rest))
595        }
596    } else {
597        Err(Error::Unexpected("invalid taproot descriptor".to_string()))
598    }
599}
600
601fn split_once(inp: &str, delim: char) -> Option<(&str, &str)> {
602    if inp.is_empty() {
603        None
604    } else {
605        // find the first character that matches delim
606        let res = inp
607            .chars()
608            .position(|ch| ch == delim)
609            .map(|idx| (&inp[..idx], &inp[idx + 1..]))
610            .unwrap_or((inp, ""));
611        Some(res)
612    }
613}
614
615impl<Pk: MiniscriptKey> Liftable<Pk> for TapTree<Pk> {
616    fn lift(&self) -> Result<Policy<Pk>, Error> {
617        fn lift_helper<Pk: MiniscriptKey>(s: &TapTree<Pk>) -> Result<Policy<Pk>, Error> {
618            match *s {
619                TapTree::Tree { ref left, ref right, height: _ } => Ok(Policy::Thresh(
620                    Threshold::or(Arc::new(lift_helper(left)?), Arc::new(lift_helper(right)?)),
621                )),
622                TapTree::Leaf(ref leaf) => leaf.lift(),
623            }
624        }
625
626        let pol = lift_helper(self)?;
627        Ok(pol.normalized())
628    }
629}
630
631impl<Pk: MiniscriptKey> Liftable<Pk> for Tr<Pk> {
632    fn lift(&self) -> Result<Policy<Pk>, Error> {
633        match &self.tree {
634            Some(root) => Ok(Policy::Thresh(Threshold::or(
635                Arc::new(Policy::Key(self.internal_key.clone())),
636                Arc::new(root.lift()?),
637            ))),
638            None => Ok(Policy::Key(self.internal_key.clone())),
639        }
640    }
641}
642
643impl<Pk: MiniscriptKey> ForEachKey<Pk> for Tr<Pk> {
644    fn for_each_key<'a, F: FnMut(&'a Pk) -> bool>(&'a self, mut pred: F) -> bool {
645        let script_keys_res = self
646            .iter_scripts()
647            .all(|(_d, ms)| ms.for_each_key(&mut pred));
648        script_keys_res && pred(&self.internal_key)
649    }
650}
651
652impl<P, Q> TranslatePk<P, Q> for Tr<P>
653where
654    P: MiniscriptKey,
655    Q: MiniscriptKey,
656{
657    type Output = Tr<Q>;
658
659    fn translate_pk<T, E>(&self, translate: &mut T) -> Result<Self::Output, TranslateErr<E>>
660    where
661        T: Translator<P, Q, E>,
662    {
663        let tree = match &self.tree {
664            Some(tree) => Some(tree.translate_helper(translate)?),
665            None => None,
666        };
667        let translate_desc = Tr::new(translate.pk(&self.internal_key)?, tree)
668            .map_err(|e| TranslateErr::OuterError(e))?;
669        Ok(translate_desc)
670    }
671}
672
673// Helper function to compute the len of control block at a given depth
674fn control_block_len(depth: u8) -> usize {
675    TAPROOT_CONTROL_BASE_SIZE + (depth as usize) * TAPROOT_CONTROL_NODE_SIZE
676}
677
678// Helper function to get a script spend satisfaction
679// try script spend
680fn best_tap_spend<Pk, P>(
681    desc: &Tr<Pk>,
682    provider: &P,
683    allow_mall: bool,
684) -> Satisfaction<Placeholder<Pk>>
685where
686    Pk: ToPublicKey,
687    P: AssetProvider<Pk>,
688{
689    let spend_info = desc.spend_info();
690    // First try the key spend path
691    if let Some(size) = provider.provider_lookup_tap_key_spend_sig(&desc.internal_key) {
692        Satisfaction {
693            stack: Witness::Stack(vec![Placeholder::SchnorrSigPk(
694                desc.internal_key.clone(),
695                SchnorrSigType::KeySpend { merkle_root: spend_info.merkle_root() },
696                size,
697            )]),
698            has_sig: true,
699            absolute_timelock: None,
700            relative_timelock: None,
701        }
702    } else {
703        // Since we have the complete descriptor we can ignore the satisfier. We don't use the control block
704        // map (lookup_control_block) from the satisfier here.
705        let mut min_satisfaction = Satisfaction {
706            stack: Witness::Unavailable,
707            has_sig: false,
708            relative_timelock: None,
709            absolute_timelock: None,
710        };
711        let mut min_wit_len = None;
712        for (_depth, ms) in desc.iter_scripts() {
713            let mut satisfaction = if allow_mall {
714                match ms.build_template(provider) {
715                    s @ Satisfaction { stack: Witness::Stack(_), .. } => s,
716                    _ => continue, // No witness for this script in tr descriptor, look for next one
717                }
718            } else {
719                match ms.build_template_mall(provider) {
720                    s @ Satisfaction { stack: Witness::Stack(_), .. } => s,
721                    _ => continue, // No witness for this script in tr descriptor, look for next one
722                }
723            };
724            let wit = match satisfaction {
725                Satisfaction { stack: Witness::Stack(ref mut wit), .. } => wit,
726                _ => unreachable!(),
727            };
728
729            let leaf_script = (ms.encode(), LeafVersion::TapScript);
730            let control_block = spend_info
731                .control_block(&leaf_script)
732                .expect("Control block must exist in script map for every known leaf");
733
734            wit.push(Placeholder::TapScript(leaf_script.0));
735            wit.push(Placeholder::TapControlBlock(control_block));
736
737            let wit_size = witness_size(wit);
738            if min_wit_len.is_some() && Some(wit_size) > min_wit_len {
739                continue;
740            } else {
741                min_satisfaction = satisfaction;
742                min_wit_len = Some(wit_size);
743            }
744        }
745
746        min_satisfaction
747    }
748}
749
750#[cfg(test)]
751mod tests {
752    use super::*;
753
754    fn descriptor() -> String {
755        let desc = "tr(acc0, {
756            multi_a(3, acc10, acc11, acc12), {
757              and_v(
758                v:multi_a(2, acc10, acc11, acc12),
759                after(10)
760              ),
761              and_v(
762                v:multi_a(1, acc10, acc11, ac12),
763                after(100)
764              )
765            }
766         })";
767        desc.replace(&[' ', '\n'][..], "")
768    }
769
770    #[test]
771    fn regression_736() {
772        crate::Descriptor::<crate::DescriptorPublicKey>::from_str(
773            "tr(0000000000000000000000000000000000000000000000000000000000000002,)",
774        )
775        .unwrap_err();
776    }
777
778    #[test]
779    fn for_each() {
780        let desc = descriptor();
781        let tr = Tr::<String>::from_str(&desc).unwrap();
782        // Note the last ac12 only has ac and fails the predicate
783        assert!(!tr.for_each_key(|k| k.starts_with("acc")));
784    }
785
786    #[test]
787    fn height() {
788        let desc = descriptor();
789        let tr = Tr::<String>::from_str(&desc).unwrap();
790        assert_eq!(tr.tap_tree().as_ref().unwrap().height(), 2);
791    }
792}
miniscript/descriptor/tr.rs

miniscript/descriptor/
tr.rs
