miniscript_debug/policy/
mod.rs

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

miniscript_debug/policy/
mod.rs
