miniscript/policy/
mod.rs

1// SPDX-License-Identifier: CC0-1.0
2
3//!  Script Policies
4//!
5//! Tools for representing Bitcoin scriptpubkeys as abstract spending policies.
6//! These may be compiled to Miniscript, which contains extra information to
7//! describe the exact representation as Bitcoin script.
8//!
9//! The format represents EC public keys abstractly to allow wallets to replace
10//! these with BIP32 paths, pay-to-contract instructions, etc.
11//!
12use core::fmt;
13#[cfg(feature = "std")]
14use std::error;
15
16#[cfg(feature = "compiler")]
17pub mod compiler;
18pub mod concrete;
19pub mod semantic;
20
21pub use self::concrete::Policy as Concrete;
22pub use self::semantic::Policy as Semantic;
23use crate::descriptor::Descriptor;
24use crate::iter::TreeLike as _;
25use crate::miniscript::{Miniscript, ScriptContext};
26use crate::sync::Arc;
27#[cfg(all(not(feature = "std"), not(test)))]
28use crate::Vec;
29use crate::{Error, MiniscriptKey, Terminal, Threshold};
30
31/// Policy entailment algorithm maximum number of terminals allowed.
32const ENTAILMENT_MAX_TERMINALS: usize = 20;
33
34/// Trait describing script representations which can be lifted into
35/// an abstract policy, by discarding information.
36///
37/// After Lifting all policies are converted into `KeyHash(Pk::HasH)` to
38/// maintain the following invariant(modulo resource limits):
39/// `Lift(Concrete) == Concrete -> Miniscript -> Script -> Miniscript -> Semantic`
40///
41/// Lifting from [`Miniscript`] or [`Descriptor`] can fail if the miniscript
42/// contains a timelock combination or if it contains a branch that exceeds
43/// resource limits.
44///
45/// Lifting from concrete policies can fail if the policy contains a timelock
46/// combination. It is possible that a concrete policy has some branches that
47/// exceed resource limits for any compilation but cannot detect such policies
48/// while lifting. Note that our compiler would not succeed for any such
49/// policies.
50pub trait Liftable<Pk: MiniscriptKey> {
51    /// Converts this object into an abstract policy.
52    fn lift(&self) -> Result<Semantic<Pk>, Error>;
53}
54
55/// Error occurring during lifting.
56#[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
57pub enum LiftError {
58    /// Cannot lift policies that have a combination of height and timelocks.
59    HeightTimelockCombination,
60    /// Duplicate public keys.
61    BranchExceedResourceLimits,
62    /// Cannot lift raw descriptors.
63    RawDescriptorLift,
64}
65
66impl fmt::Display for LiftError {
67    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
68        match *self {
69            LiftError::HeightTimelockCombination => {
70                f.write_str("Cannot lift policies that have a heightlock and timelock combination")
71            }
72            LiftError::BranchExceedResourceLimits => f.write_str(
73                "Cannot lift policies containing one branch that exceeds resource limits",
74            ),
75            LiftError::RawDescriptorLift => f.write_str("Cannot lift raw descriptors"),
76        }
77    }
78}
79
80#[cfg(feature = "std")]
81impl error::Error for LiftError {
82    fn cause(&self) -> Option<&dyn error::Error> {
83        use self::LiftError::*;
84
85        match self {
86            HeightTimelockCombination | BranchExceedResourceLimits | RawDescriptorLift => None,
87        }
88    }
89}
90
91impl<Pk: MiniscriptKey, Ctx: ScriptContext> Miniscript<Pk, Ctx> {
92    /// Lifting corresponds to conversion of a miniscript into a [`Semantic`]
93    /// policy for human readable or machine analysis. However, naively lifting
94    /// miniscripts can result in incorrect interpretations that don't
95    /// correspond to the underlying semantics when we try to spend them on
96    /// bitcoin network. This can occur if the miniscript contains:
97    /// 1. A combination of timelocks
98    /// 2. A spend that exceeds resource limits
99    pub fn lift_check(&self) -> Result<(), LiftError> {
100        if !self.within_resource_limits() {
101            Err(LiftError::BranchExceedResourceLimits)
102        } else if self.has_mixed_timelocks() {
103            Err(LiftError::HeightTimelockCombination)
104        } else {
105            Ok(())
106        }
107    }
108}
109
110impl<Pk: MiniscriptKey, Ctx: ScriptContext> Liftable<Pk> for Miniscript<Pk, Ctx> {
111    fn lift(&self) -> Result<Semantic<Pk>, Error> {
112        // check whether the root miniscript can have a spending path that is
113        // a combination of heightlock and timelock
114        self.lift_check()?;
115
116        let mut stack = vec![];
117        for item in self.rtl_post_order_iter() {
118            let new_term = match item.node.node {
119                Terminal::PkK(ref pk) | Terminal::PkH(ref pk) => {
120                    Arc::new(Semantic::Key(pk.clone()))
121                }
122                Terminal::RawPkH(ref _pkh) => {
123                    return Err(Error::LiftError(LiftError::RawDescriptorLift))
124                }
125                Terminal::After(t) => Arc::new(Semantic::After(t)),
126                Terminal::Older(t) => Arc::new(Semantic::Older(t)),
127                Terminal::Sha256(ref h) => Arc::new(Semantic::Sha256(h.clone())),
128                Terminal::Hash256(ref h) => Arc::new(Semantic::Hash256(h.clone())),
129                Terminal::Ripemd160(ref h) => Arc::new(Semantic::Ripemd160(h.clone())),
130                Terminal::Hash160(ref h) => Arc::new(Semantic::Hash160(h.clone())),
131                Terminal::False => Arc::new(Semantic::Unsatisfiable),
132                Terminal::True => Arc::new(Semantic::Trivial),
133                Terminal::Alt(..)
134                | Terminal::Swap(..)
135                | Terminal::Check(..)
136                | Terminal::DupIf(..)
137                | Terminal::Verify(..)
138                | Terminal::NonZero(..)
139                | Terminal::ZeroNotEqual(..) => stack.pop().unwrap(),
140                Terminal::AndV(..) | Terminal::AndB(..) => Arc::new(Semantic::Thresh(
141                    Threshold::and(stack.pop().unwrap(), stack.pop().unwrap()),
142                )),
143                Terminal::AndOr(..) => Arc::new(Semantic::Thresh(Threshold::or(
144                    Arc::new(Semantic::Thresh(Threshold::and(
145                        stack.pop().unwrap(),
146                        stack.pop().unwrap(),
147                    ))),
148                    stack.pop().unwrap(),
149                ))),
150                Terminal::OrB(..) | Terminal::OrD(..) | Terminal::OrC(..) | Terminal::OrI(..) => {
151                    Arc::new(Semantic::Thresh(Threshold::or(
152                        stack.pop().unwrap(),
153                        stack.pop().unwrap(),
154                    )))
155                }
156                Terminal::Thresh(ref thresh) => {
157                    Arc::new(Semantic::Thresh(thresh.map_ref(|_| stack.pop().unwrap())))
158                }
159                Terminal::Multi(ref thresh) => Arc::new(Semantic::Thresh(
160                    thresh
161                        .map_ref(|key| Arc::new(Semantic::Key(key.clone())))
162                        .forget_maximum(),
163                )),
164                Terminal::MultiA(ref thresh) => Arc::new(Semantic::Thresh(
165                    thresh
166                        .map_ref(|key| Arc::new(Semantic::Key(key.clone())))
167                        .forget_maximum(),
168                )),
169            };
170            stack.push(new_term)
171        }
172        Ok(Arc::try_unwrap(stack.pop().unwrap()).unwrap().normalized())
173    }
174}
175
176impl<Pk: MiniscriptKey> Liftable<Pk> for Descriptor<Pk> {
177    fn lift(&self) -> Result<Semantic<Pk>, Error> {
178        match *self {
179            Descriptor::Bare(ref bare) => bare.lift(),
180            Descriptor::Pkh(ref pkh) => pkh.lift(),
181            Descriptor::Wpkh(ref wpkh) => wpkh.lift(),
182            Descriptor::Wsh(ref wsh) => wsh.lift(),
183            Descriptor::Sh(ref sh) => sh.lift(),
184            Descriptor::Tr(ref tr) => tr.lift(),
185        }
186    }
187}
188
189impl<Pk: MiniscriptKey> Liftable<Pk> for Semantic<Pk> {
190    fn lift(&self) -> Result<Semantic<Pk>, Error> { Ok(self.clone()) }
191}
192
193impl<Pk: MiniscriptKey> Liftable<Pk> for Concrete<Pk> {
194    fn lift(&self) -> Result<Semantic<Pk>, Error> {
195        // do not lift if there is a possible satisfaction
196        // involving combination of timelocks and heightlocks
197        self.check_timelocks().map_err(Error::ConcretePolicy)?;
198        let ret = match *self {
199            Concrete::Unsatisfiable => Semantic::Unsatisfiable,
200            Concrete::Trivial => Semantic::Trivial,
201            Concrete::Key(ref pk) => Semantic::Key(pk.clone()),
202            Concrete::After(t) => Semantic::After(t),
203            Concrete::Older(t) => Semantic::Older(t),
204            Concrete::Sha256(ref h) => Semantic::Sha256(h.clone()),
205            Concrete::Hash256(ref h) => Semantic::Hash256(h.clone()),
206            Concrete::Ripemd160(ref h) => Semantic::Ripemd160(h.clone()),
207            Concrete::Hash160(ref h) => Semantic::Hash160(h.clone()),
208            Concrete::And(ref subs) => {
209                let semantic_subs: Result<Vec<Semantic<Pk>>, Error> =
210                    subs.iter().map(Liftable::lift).collect();
211                let semantic_subs = semantic_subs?.into_iter().map(Arc::new).collect();
212                Semantic::Thresh(Threshold::new(2, semantic_subs).unwrap())
213            }
214            Concrete::Or(ref subs) => {
215                let semantic_subs: Result<Vec<Semantic<Pk>>, Error> =
216                    subs.iter().map(|(_p, sub)| sub.lift()).collect();
217                let semantic_subs = semantic_subs?.into_iter().map(Arc::new).collect();
218                Semantic::Thresh(Threshold::new(1, semantic_subs).unwrap())
219            }
220            Concrete::Thresh(ref thresh) => {
221                Semantic::Thresh(thresh.translate_ref(|sub| Liftable::lift(sub).map(Arc::new))?)
222            }
223        }
224        .normalized();
225        Ok(ret)
226    }
227}
228impl<Pk: MiniscriptKey> Liftable<Pk> for Arc<Concrete<Pk>> {
229    fn lift(&self) -> Result<Semantic<Pk>, Error> { self.as_ref().lift() }
230}
231
232#[cfg(test)]
233mod tests {
234    use core::str::FromStr;
235
236    use super::*;
237    #[cfg(feature = "compiler")]
238    use crate::descriptor::Tr;
239    use crate::miniscript::context::Segwitv0;
240    use crate::prelude::*;
241    use crate::RelLockTime;
242    #[cfg(feature = "compiler")]
243    use crate::{descriptor::TapTree, Tap};
244
245    type ConcretePol = Concrete<String>;
246    type SemanticPol = Semantic<String>;
247
248    fn concrete_policy_rtt(s: &str) {
249        let conc = ConcretePol::from_str(s).unwrap();
250        let output = conc.to_string();
251        assert_eq!(s.to_lowercase(), output.to_lowercase());
252    }
253
254    fn semantic_policy_rtt(s: &str) {
255        let sem = SemanticPol::from_str(s).unwrap();
256        let output = sem.normalized().to_string();
257        assert_eq!(s.to_lowercase(), output.to_lowercase());
258    }
259
260    #[test]
261    fn test_timelock_validity() {
262        // only height
263        assert!(ConcretePol::from_str("after(100)").is_ok());
264        // only time
265        assert!(ConcretePol::from_str("after(1000000000)").is_ok());
266        // disjunction
267        assert!(ConcretePol::from_str("or(after(1000000000),after(100))").is_ok());
268        // conjunction
269        assert!(ConcretePol::from_str("and(after(1000000000),after(100))").is_err());
270        // thresh with k = 1
271        assert!(ConcretePol::from_str("thresh(1,pk(),after(1000000000),after(100))").is_ok());
272        // thresh with k = 2
273        assert!(ConcretePol::from_str("thresh(2,after(1000000000),after(100),pk())").is_err());
274    }
275    #[test]
276    fn policy_rtt_tests() {
277        concrete_policy_rtt("pk()");
278        concrete_policy_rtt("or(1@pk(X),1@pk(Y))");
279        concrete_policy_rtt("or(99@pk(X),1@pk(Y))");
280        concrete_policy_rtt("and(pk(X),or(99@pk(Y),1@older(12960)))");
281
282        semantic_policy_rtt("pk()");
283        semantic_policy_rtt("or(pk(X),pk(Y))");
284        semantic_policy_rtt("and(pk(X),pk(Y))");
285
286        //fuzzer crashes
287        assert!(ConcretePol::from_str("thresh()").is_err());
288        assert!(SemanticPol::from_str("thresh(0)").is_err());
289        assert!(SemanticPol::from_str("thresh()").is_err());
290        concrete_policy_rtt("ripemd160()");
291    }
292
293    #[test]
294    fn compile_invalid() {
295        // Since the root Error does not support Eq type, we have to
296        // compare the string representations of the error
297        assert_eq!(
298            ConcretePol::from_str("thresh(2,pk(),thresh(0))")
299                .unwrap_err()
300                .to_string(),
301            "thresholds in Miniscript must be nonempty",
302        );
303        assert_eq!(
304            ConcretePol::from_str("thresh(2,pk(),thresh(0,pk()))")
305                .unwrap_err()
306                .to_string(),
307            "thresholds in Miniscript must have k > 0",
308        );
309        assert_eq!(
310            ConcretePol::from_str("and(pk())").unwrap_err().to_string(),
311            "and must have 2 children, but found 1"
312        );
313        assert_eq!(
314            ConcretePol::from_str("or(pk())").unwrap_err().to_string(),
315            "or must have 2 children, but found 1"
316        );
317        // these weird "unexpected" wrapping of errors will go away in a later PR
318        // which rewrites the expression parser
319        assert_eq!(
320            ConcretePol::from_str("thresh(3,after(0),pk(),pk())")
321                .unwrap_err()
322                .to_string(),
323            "absolute locktimes in Miniscript have a minimum value of 1",
324        );
325
326        assert_eq!(
327            ConcretePol::from_str("thresh(2,older(2147483650),pk(),pk())")
328                .unwrap_err()
329                .to_string(),
330            "locktime value 2147483650 is not a valid BIP68 relative locktime"
331        );
332    }
333
334    //https://github.com/apoelstra/rust-miniscript/issues/41
335    #[test]
336    fn heavy_nest() {
337        let policy_string = "thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk(),thresh(1,pk(),pk(),pk()))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))";
338        ConcretePol::from_str(policy_string).unwrap_err();
339    }
340
341    #[test]
342    fn lift_andor() {
343        let key_a: bitcoin::PublicKey =
344            "02d7924d4f7d43ea965a465ae3095ff41131e5946f3c85f79e44adbcf8e27e080e"
345                .parse()
346                .unwrap();
347        let key_b: bitcoin::PublicKey =
348            "03b506a1dbe57b4bf48c95e0c7d417b87dd3b4349d290d2e7e9ba72c912652d80a"
349                .parse()
350                .unwrap();
351
352        let ms_str: Miniscript<bitcoin::PublicKey, Segwitv0> =
353            format!("andor(multi(1,{}),older(42),c:pk_k({}))", key_a.inner, key_b.inner)
354                .parse()
355                .unwrap();
356        assert_eq!(
357            Semantic::Thresh(Threshold::or(
358                Arc::new(Semantic::Thresh(Threshold::and(
359                    Arc::new(Semantic::Key(key_a)),
360                    Arc::new(Semantic::Older(RelLockTime::from_height(42)))
361                ))),
362                Arc::new(Semantic::Key(key_b))
363            )),
364            ms_str.lift().unwrap()
365        );
366    }
367
368    #[test]
369    #[cfg(feature = "compiler")]
370    fn taproot_compile() {
371        // Trivial single-node compilation
372        let unspendable_key: String = "UNSPENDABLE".to_string();
373        {
374            let policy: Concrete<String> = policy_str!("thresh(2,pk(A),pk(B),pk(C),pk(D))");
375            let descriptor = policy.compile_tr(Some(unspendable_key.clone())).unwrap();
376
377            let ms_compilation: Miniscript<String, Tap> = ms_str!("multi_a(2,A,B,C,D)");
378            let tree: TapTree<String> = TapTree::leaf(ms_compilation);
379            let expected_descriptor =
380                Descriptor::new_tr(unspendable_key.clone(), Some(tree)).unwrap();
381            assert_eq!(descriptor, expected_descriptor);
382        }
383
384        // Trivial multi-node compilation
385        {
386            let policy: Concrete<String> = policy_str!("or(and(pk(A),pk(B)),and(pk(C),pk(D)))");
387            let descriptor = policy.compile_tr(Some(unspendable_key.clone())).unwrap();
388
389            let left_ms_compilation: Miniscript<String, Tap> = ms_str!("and_v(v:pk(C),pk(D))");
390            let right_ms_compilation: Miniscript<String, Tap> = ms_str!("and_v(v:pk(A),pk(B))");
391
392            let left = TapTree::leaf(left_ms_compilation);
393            let right = TapTree::leaf(right_ms_compilation);
394            let tree = TapTree::combine(left, right).unwrap();
395
396            let expected_descriptor =
397                Descriptor::new_tr(unspendable_key.clone(), Some(tree)).unwrap();
398            assert_eq!(descriptor, expected_descriptor);
399        }
400
401        {
402            // Invalid policy compilation (Duplicate PubKeys)
403            let policy: Concrete<String> = policy_str!("or(and(pk(A),pk(B)),and(pk(A),pk(D)))");
404            let descriptor = policy.compile_tr(Some(unspendable_key.clone()));
405
406            assert_eq!(descriptor.unwrap_err().to_string(), "Policy contains duplicate keys");
407        }
408
409        // Non-trivial multi-node compilation
410        {
411            let node_policies = [
412                "and(pk(A),pk(B))",
413                "and(pk(C),older(12960))",
414                "pk(D)",
415                "pk(E)",
416                "thresh(3,pk(F),pk(G),pk(H))",
417                "and(and(or(2@pk(I),1@pk(J)),or(1@pk(K),20@pk(L))),pk(M))",
418                "pk(N)",
419            ];
420
421            // Floating-point precision errors cause the minor errors
422            let node_probabilities: [f64; 7] =
423                [0.12000002, 0.28, 0.08, 0.12, 0.19, 0.18999998, 0.02];
424
425            let policy: Concrete<String> = policy_str!(
426                "{}",
427                &format!(
428                    "or(4@or(3@{},7@{}),6@thresh(1,or(4@{},6@{}),{},or(9@{},1@{})))",
429                    node_policies[0],
430                    node_policies[1],
431                    node_policies[2],
432                    node_policies[3],
433                    node_policies[4],
434                    node_policies[5],
435                    node_policies[6]
436                )
437            );
438            let descriptor = policy.compile_tr(Some(unspendable_key.clone())).unwrap();
439
440            let mut sorted_policy_prob = node_policies
441                .iter()
442                .zip(node_probabilities.iter())
443                .collect::<Vec<_>>();
444            sorted_policy_prob.sort_by(|a, b| (a.1).partial_cmp(b.1).unwrap());
445            let sorted_policies = sorted_policy_prob
446                .into_iter()
447                .map(|(x, _prob)| x)
448                .collect::<Vec<_>>();
449
450            // Generate TapTree leaves compilations from the given sub-policies
451            let node_compilations = sorted_policies
452                .into_iter()
453                .map(|x| {
454                    let leaf_policy: Concrete<String> = policy_str!("{}", x);
455                    TapTree::leaf(leaf_policy.compile::<Tap>().unwrap())
456                })
457                .collect::<Vec<_>>();
458
459            // Arrange leaf compilations (acc. to probabilities) using huffman encoding into a TapTree
460            let tree = TapTree::combine(
461                TapTree::combine(node_compilations[4].clone(), node_compilations[5].clone())
462                    .unwrap(),
463                TapTree::combine(
464                    TapTree::combine(
465                        TapTree::combine(
466                            node_compilations[0].clone(),
467                            node_compilations[1].clone(),
468                        )
469                        .unwrap(),
470                        node_compilations[3].clone(),
471                    )
472                    .unwrap(),
473                    node_compilations[6].clone(),
474                )
475                .unwrap(),
476            )
477            .unwrap();
478
479            let expected_descriptor = Descriptor::new_tr("E".to_string(), Some(tree)).unwrap();
480            assert_eq!(descriptor, expected_descriptor);
481        }
482    }
483
484    #[test]
485    #[cfg(feature = "compiler")]
486    fn experimental_taproot_compile() {
487        let unspendable_key = "UNSPEND".to_string();
488
489        {
490            let pol = Concrete::<String>::from_str(
491                "thresh(7,pk(A),pk(B),pk(C),pk(D),pk(E),pk(F),pk(G),pk(H))",
492            )
493            .unwrap();
494            let desc = pol
495                .compile_tr_private_experimental(Some(unspendable_key.clone()))
496                .unwrap();
497            let expected_desc = Descriptor::Tr(
498                Tr::<String>::from_str(
499                    "tr(UNSPEND ,{
500                {
501                    {and_v(v:and_v(v:and_v(v:and_v(v:and_v(v:and_v(v:pk(B),pk(C)),pk(D)),pk(E)),pk(F)),pk(G)),pk(H)),and_v(v:and_v(v:and_v(v:and_v(v:and_v(v:and_v(v:pk(A),pk(C)),pk(D)),pk(E)),pk(F)),pk(G)),pk(H))},
502                    {and_v(v:and_v(v:and_v(v:and_v(v:and_v(v:and_v(v:pk(A),pk(B)),pk(D)),pk(E)),pk(F)),pk(G)),pk(H)),and_v(v:and_v(v:and_v(v:and_v(v:and_v(v:and_v(v:pk(A),pk(B)),pk(C)),pk(E)),pk(F)),pk(G)),pk(H))}
503                },
504                {
505                    {and_v(v:and_v(v:and_v(v:and_v(v:and_v(v:and_v(v:pk(A),pk(B)),pk(C)),pk(D)),pk(F)),pk(G)),pk(H)),and_v(v:and_v(v:and_v(v:and_v(v:and_v(v:and_v(v:pk(A),pk(B)),pk(C)),pk(D)),pk(E)),pk(G)),pk(H))},
506                    {and_v(v:and_v(v:and_v(v:and_v(v:and_v(v:and_v(v:pk(A),pk(B)),pk(C)),pk(D)),pk(E)),pk(F)),pk(H)),and_v(v:and_v(v:and_v(v:and_v(v:and_v(v:and_v(v:pk(A),pk(B)),pk(C)),pk(D)),pk(E)),pk(F)),pk(G))}
507                }})"
508                    .replace(&['\t', ' ', '\n'][..], "")
509                    .as_str(),
510                )
511                .unwrap(),
512            );
513            assert_eq!(desc, expected_desc);
514        }
515
516        {
517            let pol =
518                Concrete::<String>::from_str("thresh(3,pk(A),pk(B),pk(C),pk(D),pk(E))").unwrap();
519            let desc = pol
520                .compile_tr_private_experimental(Some(unspendable_key.clone()))
521                .unwrap();
522            println!("{}", desc);
523            let expected_desc = Descriptor::Tr(
524                Tr::<String>::from_str(
525                    "tr(UNSPEND,
526                    {{
527                        {and_v(v:and_v(v:pk(A),pk(D)),pk(E)),and_v(v:and_v(v:pk(A),pk(C)),pk(E))},
528                        {and_v(v:and_v(v:pk(A),pk(C)),pk(D)),and_v(v:and_v(v:pk(A),pk(B)),pk(E))}
529                    },
530                    {
531                        {and_v(v:and_v(v:pk(A),pk(B)),pk(D)),and_v(v:and_v(v:pk(A),pk(B)),pk(C))},
532                        {
533                            {and_v(v:and_v(v:pk(C),pk(D)),pk(E)),and_v(v:and_v(v:pk(B),pk(D)),pk(E))},
534                            {and_v(v:and_v(v:pk(B),pk(C)),pk(E)),and_v(v:and_v(v:pk(B),pk(C)),pk(D))}
535                    }}})"
536                        .replace(&['\t', ' ', '\n'][..], "")
537                        .as_str(),
538                )
539                .unwrap(),
540            );
541            assert_eq!(desc, expected_desc);
542        }
543    }
544}
miniscript/policy/mod.rs

miniscript/policy/
mod.rs
