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

miniscript/policy/
mod.rs
