elements_miniscript/policy/
mod.rs

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

elements_miniscript/policy/
mod.rs
