miniscript/policy/
semantic.rs

1// SPDX-License-Identifier: CC0-1.0
2
3//! Abstract Policies
4//!
5//! We use the terms "semantic" and "abstract" interchangeably because
6//! "abstract" is a reserved keyword in Rust.
7
8use core::{fmt, str};
9
10use bitcoin::{absolute, relative};
11
12use super::ENTAILMENT_MAX_TERMINALS;
13use crate::iter::{Tree, TreeLike};
14use crate::prelude::*;
15use crate::sync::Arc;
16use crate::{
17    expression, AbsLockTime, Error, ForEachKey, FromStrKey, MiniscriptKey, RelLockTime, Threshold,
18    Translator,
19};
20
21/// Abstract policy which corresponds to the semantics of a miniscript and
22/// which allows complex forms of analysis, e.g. filtering and normalization.
23///
24/// Semantic policies store only hashes of keys to ensure that objects
25/// representing the same policy are lifted to the same abstract `Policy`,
26/// regardless of their choice of `pk` or `pk_h` nodes.
27#[derive(Clone, PartialEq, Eq, PartialOrd, Ord)]
28pub enum Policy<Pk: MiniscriptKey> {
29    /// Unsatisfiable.
30    Unsatisfiable,
31    /// Trivially satisfiable.
32    Trivial,
33    /// Signature and public key matching a given hash is required.
34    Key(Pk),
35    /// An absolute locktime restriction.
36    After(AbsLockTime),
37    /// A relative locktime restriction.
38    Older(RelLockTime),
39    /// A SHA256 whose preimage must be provided to satisfy the descriptor.
40    Sha256(Pk::Sha256),
41    /// A SHA256d whose preimage must be provided to satisfy the descriptor.
42    Hash256(Pk::Hash256),
43    /// A RIPEMD160 whose preimage must be provided to satisfy the descriptor.
44    Ripemd160(Pk::Ripemd160),
45    /// A HASH160 whose preimage must be provided to satisfy the descriptor.
46    Hash160(Pk::Hash160),
47    /// A set of descriptors, satisfactions must be provided for `k` of them.
48    Thresh(Threshold<Arc<Policy<Pk>>, 0>),
49}
50
51impl<Pk: MiniscriptKey> ForEachKey<Pk> for Policy<Pk> {
52    fn for_each_key<'a, F: FnMut(&'a Pk) -> bool>(&'a self, mut pred: F) -> bool {
53        self.pre_order_iter().all(|policy| match policy {
54            Policy::Key(ref pk) => pred(pk),
55            _ => true,
56        })
57    }
58}
59
60impl<Pk: MiniscriptKey> Policy<Pk> {
61    /// Converts a policy using one kind of public key to another type of public key.
62    ///
63    /// # Examples
64    ///
65    /// ```
66    /// use std::collections::HashMap;
67    /// use std::str::FromStr;
68    /// use miniscript::bitcoin::{hashes::hash160, PublicKey};
69    /// use miniscript::{translate_hash_fail, policy::semantic::Policy, Translator};
70    /// let alice_pk = "02c79ef3ede6d14f72a00d0e49b4becfb152197b64c0707425c4f231df29500ee7";
71    /// let bob_pk = "03d008a849fbf474bd17e9d2c1a827077a468150e58221582ec3410ab309f5afe4";
72    /// let placeholder_policy = Policy::<String>::from_str("and(pk(alice_pk),pk(bob_pk))").unwrap();
73    ///
74    /// // Information to translate abstract string type keys to concrete `bitcoin::PublicKey`s.
75    /// // In practice, wallets would map from string key names to BIP32 keys.
76    /// struct StrPkTranslator {
77    ///     pk_map: HashMap<String, bitcoin::PublicKey>
78    /// }
79    ///
80    /// // If we also wanted to provide mapping of other associated types (sha256, older etc),
81    /// // we would use the general [`Translator`] trait.
82    /// impl Translator<String> for StrPkTranslator {
83    ///     type TargetPk = bitcoin::PublicKey;
84    ///     type Error = ();
85    ///
86    ///     fn pk(&mut self, pk: &String) -> Result<bitcoin::PublicKey, Self::Error> {
87    ///         self.pk_map.get(pk).copied().ok_or(()) // Dummy Err
88    ///     }
89    ///
90    ///     // Handy macro for failing if we encounter any other fragment.
91    ///     // See also [`translate_hash_clone!`] for cloning instead of failing.
92    ///     translate_hash_fail!(String);
93    /// }
94    ///
95    /// let mut pk_map = HashMap::new();
96    /// pk_map.insert(String::from("alice_pk"), bitcoin::PublicKey::from_str(alice_pk).unwrap());
97    /// pk_map.insert(String::from("bob_pk"), bitcoin::PublicKey::from_str(bob_pk).unwrap());
98    /// let mut t = StrPkTranslator { pk_map };
99    ///
100    /// let real_policy = placeholder_policy.translate_pk(&mut t).unwrap();
101    ///
102    /// let expected_policy = Policy::from_str(&format!("and(pk({}),pk({}))", alice_pk, bob_pk)).unwrap();
103    /// assert_eq!(real_policy, expected_policy);
104    /// ```
105    pub fn translate_pk<T>(&self, t: &mut T) -> Result<Policy<T::TargetPk>, T::Error>
106    where
107        T: Translator<Pk>,
108    {
109        use Policy::*;
110
111        let mut translated = vec![];
112        for data in self.rtl_post_order_iter() {
113            let new_policy = match data.node {
114                Unsatisfiable => Unsatisfiable,
115                Trivial => Trivial,
116                Key(ref pk) => t.pk(pk).map(Key)?,
117                Sha256(ref h) => t.sha256(h).map(Sha256)?,
118                Hash256(ref h) => t.hash256(h).map(Hash256)?,
119                Ripemd160(ref h) => t.ripemd160(h).map(Ripemd160)?,
120                Hash160(ref h) => t.hash160(h).map(Hash160)?,
121                Older(ref n) => Older(*n),
122                After(ref n) => After(*n),
123                Thresh(ref thresh) => Thresh(thresh.map_ref(|_| translated.pop().unwrap())),
124            };
125            translated.push(Arc::new(new_policy));
126        }
127        // Unwrap is ok because we know we processed at least one node.
128        let root_node = translated.pop().unwrap();
129        // Unwrap is ok because we know `root_node` is the only strong reference.
130        Ok(Arc::try_unwrap(root_node).unwrap())
131    }
132
133    /// Computes whether the current policy entails the second one.
134    ///
135    /// A |- B means every satisfaction of A is also a satisfaction of B.
136    ///
137    /// This implementation will run slowly for larger policies but should be
138    /// sufficient for most practical policies.
139    ///
140    /// Returns None for very large policies for which entailment cannot
141    /// be practically computed.
142    // This algorithm has a naive implementation. It is possible to optimize this
143    // by memoizing and maintaining a hashmap.
144    pub fn entails(self, other: Policy<Pk>) -> Option<bool> {
145        if self.n_terminals() > ENTAILMENT_MAX_TERMINALS {
146            return None;
147        }
148        match (self, other) {
149            (Policy::Unsatisfiable, _) => Some(true),
150            (Policy::Trivial, Policy::Trivial) => Some(true),
151            (Policy::Trivial, _) => Some(false),
152            (_, Policy::Unsatisfiable) => Some(false),
153            (a, b) => {
154                let (a_norm, b_norm) = (a.normalized(), b.normalized());
155                let first_constraint = a_norm.first_constraint();
156                let (a1, b1) = (
157                    a_norm.clone().satisfy_constraint(&first_constraint, true),
158                    b_norm.clone().satisfy_constraint(&first_constraint, true),
159                );
160                let (a2, b2) = (
161                    a_norm.satisfy_constraint(&first_constraint, false),
162                    b_norm.satisfy_constraint(&first_constraint, false),
163                );
164                Some(Policy::entails(a1, b1)? && Policy::entails(a2, b2)?)
165            }
166        }
167    }
168
169    // Helper function to compute the number of constraints in policy.
170    fn n_terminals(&self) -> usize {
171        use Policy::*;
172
173        let mut n_terminals = vec![];
174        for data in self.rtl_post_order_iter() {
175            let num = match data.node {
176                Thresh(thresh) => (0..thresh.n()).map(|_| n_terminals.pop().unwrap()).sum(),
177                Trivial | Unsatisfiable => 0,
178                _leaf => 1,
179            };
180            n_terminals.push(num);
181        }
182        // Ok to unwrap because we know we processed at least one node.
183        n_terminals.pop().unwrap()
184    }
185
186    // Helper function to get the first constraint in the policy.
187    // Returns the first leaf policy. Used in policy entailment.
188    // Assumes that the current policy is normalized.
189    fn first_constraint(&self) -> Policy<Pk> {
190        debug_assert!(self.clone().normalized() == self.clone());
191        match self {
192            Policy::Thresh(ref thresh) => thresh.data()[0].first_constraint(),
193            first => first.clone(),
194        }
195    }
196
197    // Helper function that takes in witness and its availability, changing it
198    // to true or false and returning the resultant normalized policy. Witness
199    // is currently encoded as policy. Only accepts leaf fragment and a
200    // normalized policy
201    pub(crate) fn satisfy_constraint(self, witness: &Policy<Pk>, available: bool) -> Policy<Pk> {
202        debug_assert!(self.clone().normalized() == self);
203        if let Policy::Thresh { .. } = *witness {
204            // We can't debug_assert on Policy::Thresh.
205            panic!("should be unreachable")
206        }
207
208        let ret =
209            match self {
210                Policy::Thresh(thresh) => Policy::Thresh(thresh.map(|sub| {
211                    Arc::new(sub.as_ref().clone().satisfy_constraint(witness, available))
212                })),
213                ref leaf if leaf == witness => {
214                    if available {
215                        Policy::Trivial
216                    } else {
217                        Policy::Unsatisfiable
218                    }
219                }
220                x => x,
221            };
222        ret.normalized()
223    }
224}
225
226impl<Pk: MiniscriptKey> fmt::Debug for Policy<Pk> {
227    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
228        match *self {
229            Policy::Unsatisfiable => f.write_str("UNSATISFIABLE()"),
230            Policy::Trivial => f.write_str("TRIVIAL()"),
231            Policy::Key(ref pkh) => write!(f, "pk({:?})", pkh),
232            Policy::After(n) => write!(f, "after({})", n),
233            Policy::Older(n) => write!(f, "older({})", n),
234            Policy::Sha256(ref h) => write!(f, "sha256({})", h),
235            Policy::Hash256(ref h) => write!(f, "hash256({})", h),
236            Policy::Ripemd160(ref h) => write!(f, "ripemd160({})", h),
237            Policy::Hash160(ref h) => write!(f, "hash160({})", h),
238            Policy::Thresh(ref thresh) => {
239                if thresh.k() == thresh.n() {
240                    thresh.debug("and", false).fmt(f)
241                } else if thresh.k() == 1 {
242                    thresh.debug("or", false).fmt(f)
243                } else {
244                    thresh.debug("thresh", true).fmt(f)
245                }
246            }
247        }
248    }
249}
250
251impl<Pk: MiniscriptKey> fmt::Display for Policy<Pk> {
252    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
253        match *self {
254            Policy::Unsatisfiable => f.write_str("UNSATISFIABLE"),
255            Policy::Trivial => f.write_str("TRIVIAL"),
256            Policy::Key(ref pkh) => write!(f, "pk({})", pkh),
257            Policy::After(n) => write!(f, "after({})", n),
258            Policy::Older(n) => write!(f, "older({})", n),
259            Policy::Sha256(ref h) => write!(f, "sha256({})", h),
260            Policy::Hash256(ref h) => write!(f, "hash256({})", h),
261            Policy::Ripemd160(ref h) => write!(f, "ripemd160({})", h),
262            Policy::Hash160(ref h) => write!(f, "hash160({})", h),
263            Policy::Thresh(ref thresh) => {
264                if thresh.k() == thresh.n() {
265                    thresh.display("and", false).fmt(f)
266                } else if thresh.k() == 1 {
267                    thresh.display("or", false).fmt(f)
268                } else {
269                    thresh.display("thresh", true).fmt(f)
270                }
271            }
272        }
273    }
274}
275
276impl<Pk: FromStrKey> str::FromStr for Policy<Pk> {
277    type Err = Error;
278    fn from_str(s: &str) -> Result<Policy<Pk>, Error> {
279        let tree = expression::Tree::from_str(s)?;
280        expression::FromTree::from_tree(tree.root())
281    }
282}
283
284serde_string_impl_pk!(Policy, "a miniscript semantic policy");
285
286impl<Pk: FromStrKey> expression::FromTree for Policy<Pk> {
287    fn from_tree(root: expression::TreeIterItem) -> Result<Policy<Pk>, Error> {
288        root.verify_no_curly_braces()
289            .map_err(From::from)
290            .map_err(Error::Parse)?;
291
292        let mut stack = Vec::with_capacity(128);
293        for node in root.pre_order_iter().rev() {
294            // Before doing anything else, check if this is the inner value of a terminal.
295            // In that case, just skip the node. Conveniently, there are no combinators
296            // in policy that have a single child that these might be confused with (we
297            // require and, or and thresholds to all have >1 child).
298            if let Some(parent) = node.parent() {
299                if parent.n_children() == 1 {
300                    continue;
301                }
302                if node.is_first_child() && parent.name() == "thresh" {
303                    continue;
304                }
305            }
306
307            let new = match node.name() {
308                "UNSATISFIABLE" => {
309                    node.verify_n_children("UNSATISFIABLE", 0..=0)
310                        .map_err(From::from)
311                        .map_err(Error::Parse)?;
312                    Ok(Policy::Unsatisfiable)
313                }
314                "TRIVIAL" => {
315                    node.verify_n_children("TRIVIAL", 0..=0)
316                        .map_err(From::from)
317                        .map_err(Error::Parse)?;
318                    Ok(Policy::Trivial)
319                }
320                "pk" => node
321                    .verify_terminal_parent("pk", "public key")
322                    .map(Policy::Key)
323                    .map_err(Error::Parse),
324                "after" => node.verify_after().map_err(Error::Parse).map(Policy::After),
325                "older" => node.verify_older().map_err(Error::Parse).map(Policy::Older),
326                "sha256" => node
327                    .verify_terminal_parent("sha256", "hash")
328                    .map(Policy::Sha256)
329                    .map_err(Error::Parse),
330                "hash256" => node
331                    .verify_terminal_parent("hash256", "hash")
332                    .map(Policy::Hash256)
333                    .map_err(Error::Parse),
334                "ripemd160" => node
335                    .verify_terminal_parent("ripemd160", "hash")
336                    .map(Policy::Ripemd160)
337                    .map_err(Error::Parse),
338                "hash160" => node
339                    .verify_terminal_parent("hash160", "hash")
340                    .map(Policy::Hash160)
341                    .map_err(Error::Parse),
342                "and" => {
343                    node.verify_n_children("and", 2..)
344                        .map_err(From::from)
345                        .map_err(Error::Parse)?;
346
347                    let child_iter = (0..node.n_children()).map(|_| stack.pop().unwrap());
348                    let thresh = Threshold::from_iter(node.n_children(), child_iter)
349                        .map_err(Error::Threshold)?;
350                    Ok(Policy::Thresh(thresh))
351                }
352                "or" => {
353                    node.verify_n_children("or", 2..)
354                        .map_err(From::from)
355                        .map_err(Error::Parse)?;
356                    let child_iter = (0..node.n_children()).map(|_| stack.pop().unwrap());
357                    let thresh = Threshold::from_iter(1, child_iter).map_err(Error::Threshold)?;
358                    Ok(Policy::Thresh(thresh))
359                }
360                "thresh" => {
361                    let thresh = node.verify_threshold(|_| Ok::<_, Error>(stack.pop().unwrap()))?;
362
363                    // thresh(1) and thresh(n) are disallowed in semantic policies
364                    if thresh.is_or() {
365                        return Err(Error::ParseThreshold(crate::ParseThresholdError::IllegalOr));
366                    }
367                    if thresh.is_and() {
368                        return Err(Error::ParseThreshold(crate::ParseThresholdError::IllegalAnd));
369                    }
370
371                    Ok(Policy::Thresh(thresh))
372                }
373                x => {
374                    Err(Error::Parse(crate::ParseError::Tree(crate::ParseTreeError::UnknownName {
375                        name: x.to_owned(),
376                    })))
377                }
378            }?;
379
380            stack.push(Arc::new(new));
381        }
382
383        assert_eq!(stack.len(), 1);
384        Ok(Arc::try_unwrap(stack.pop().unwrap()).unwrap())
385    }
386}
387
388impl<Pk: MiniscriptKey> Policy<Pk> {
389    /// Flattens out trees of `And`s and `Or`s; eliminate `Trivial` and
390    /// `Unsatisfiable`s. Does not reorder any branches; use `.sort`.
391    pub fn normalized(self) -> Policy<Pk> {
392        match self {
393            Policy::Thresh(thresh) => {
394                let mut ret_subs = Vec::with_capacity(thresh.n());
395
396                let subs: Vec<_> = thresh
397                    .iter()
398                    .map(|sub| Arc::new(sub.as_ref().clone().normalized()))
399                    .collect();
400                let trivial_count = subs
401                    .iter()
402                    .filter(|&pol| *pol.as_ref() == Policy::Trivial)
403                    .count();
404                let unsatisfied_count = subs
405                    .iter()
406                    .filter(|&pol| *pol.as_ref() == Policy::Unsatisfiable)
407                    .count();
408
409                let n = subs.len() - unsatisfied_count - trivial_count; // remove all true/false
410                let m = thresh.k().saturating_sub(trivial_count); // satisfy all trivial
411
412                let is_and = m == n;
413                let is_or = m == 1;
414
415                for sub in subs {
416                    match sub.as_ref() {
417                        Policy::Trivial | Policy::Unsatisfiable => {}
418                        Policy::Thresh(ref subthresh) => {
419                            match (is_and, is_or) {
420                                (true, true) => {
421                                    // means m = n = 1, thresh(1,X) type thing.
422                                    ret_subs.push(Arc::new(Policy::Thresh(subthresh.clone())));
423                                }
424                                (true, false) if subthresh.k() == subthresh.n() => {
425                                    ret_subs.extend(subthresh.iter().cloned())
426                                } // and case
427                                (false, true) if subthresh.k() == 1 => {
428                                    ret_subs.extend(subthresh.iter().cloned())
429                                } // or case
430                                _ => ret_subs.push(Arc::new(Policy::Thresh(subthresh.clone()))),
431                            }
432                        }
433                        x => ret_subs.push(Arc::new(x.clone())),
434                    }
435                }
436                // Now reason about m of n threshold
437                if m == 0 {
438                    Policy::Trivial
439                } else if m > ret_subs.len() {
440                    Policy::Unsatisfiable
441                } else if ret_subs.len() == 1 {
442                    let policy = ret_subs.pop().unwrap();
443                    // Only one strong reference because we created the Arc when pushing to ret_subs.
444                    Arc::try_unwrap(policy).unwrap()
445                } else if is_and {
446                    // unwrap ok since ret_subs is nonempty
447                    Policy::Thresh(Threshold::new(ret_subs.len(), ret_subs).unwrap())
448                } else if is_or {
449                    // unwrap ok since ret_subs is nonempty
450                    Policy::Thresh(Threshold::new(1, ret_subs).unwrap())
451                } else {
452                    // unwrap ok since ret_subs is nonempty and we made sure m <= ret_subs.len
453                    Policy::Thresh(Threshold::new(m, ret_subs).unwrap())
454                }
455            }
456            x => x,
457        }
458    }
459
460    /// Detects a true/trivial policy.
461    ///
462    /// Only checks whether the policy is `Policy::Trivial`, to check if the
463    /// normalized form is trivial, the caller is expected to normalize the
464    /// policy first.
465    pub fn is_trivial(&self) -> bool { matches!(*self, Policy::Trivial) }
466
467    /// Detects a false/unsatisfiable policy.
468    ///
469    /// Only checks whether the policy is `Policy::Unsatisfiable`, to check if
470    /// the normalized form is unsatisfiable, the caller is expected to
471    /// normalize the policy first.
472    pub fn is_unsatisfiable(&self) -> bool { matches!(*self, Policy::Unsatisfiable) }
473
474    /// Helper function to do the recursion in `timelocks`.
475    fn real_relative_timelocks(&self) -> Vec<u32> {
476        self.pre_order_iter()
477            .filter_map(|policy| match policy {
478                Policy::Older(t) => Some(t.to_consensus_u32()),
479                _ => None,
480            })
481            .collect()
482    }
483
484    /// Returns a list of all relative timelocks, not including 0, which appear
485    /// in the policy.
486    pub fn relative_timelocks(&self) -> Vec<u32> {
487        let mut ret = self.real_relative_timelocks();
488        ret.sort_unstable();
489        ret.dedup();
490        ret
491    }
492
493    /// Helper function for recursion in `absolute timelocks`
494    fn real_absolute_timelocks(&self) -> Vec<u32> {
495        self.pre_order_iter()
496            .filter_map(|policy| match policy {
497                Policy::After(t) => Some(t.to_consensus_u32()),
498                _ => None,
499            })
500            .collect()
501    }
502
503    /// Returns a list of all absolute timelocks, not including 0, which appear
504    /// in the policy.
505    pub fn absolute_timelocks(&self) -> Vec<u32> {
506        let mut ret = self.real_absolute_timelocks();
507        ret.sort_unstable();
508        ret.dedup();
509        ret
510    }
511
512    /// Filters a policy by eliminating relative timelock constraints
513    /// that are not satisfied at the given `age`.
514    pub fn at_age(self, age: relative::LockTime) -> Policy<Pk> {
515        use Policy::*;
516
517        let mut at_age = vec![];
518        for data in Arc::new(self).rtl_post_order_iter() {
519            let new_policy = match data.node.as_ref() {
520                Older(ref t) => {
521                    if relative::LockTime::from(*t).is_implied_by(age) {
522                        Some(Older(*t))
523                    } else {
524                        Some(Unsatisfiable)
525                    }
526                }
527                Thresh(ref thresh) => Some(Thresh(thresh.map_ref(|_| at_age.pop().unwrap()))),
528                _ => None,
529            };
530            match new_policy {
531                Some(new_policy) => at_age.push(Arc::new(new_policy)),
532                None => at_age.push(Arc::clone(data.node)),
533            }
534        }
535        // Unwrap is ok because we know we processed at least one node.
536        let root_node = at_age.pop().unwrap();
537        // Unwrap is ok because we know `root_node` is the only strong reference.
538        let policy = Arc::try_unwrap(root_node).unwrap();
539        policy.normalized()
540    }
541
542    /// Filters a policy by eliminating absolute timelock constraints
543    /// that are not satisfied at the given `n` (`n OP_CHECKLOCKTIMEVERIFY`).
544    pub fn at_lock_time(self, n: absolute::LockTime) -> Policy<Pk> {
545        use Policy::*;
546
547        let mut at_age = vec![];
548        for data in Arc::new(self).rtl_post_order_iter() {
549            let new_policy = match data.node.as_ref() {
550                After(t) => {
551                    if absolute::LockTime::from(*t).is_implied_by(n) {
552                        Some(After(*t))
553                    } else {
554                        Some(Unsatisfiable)
555                    }
556                }
557                Thresh(ref thresh) => Some(Thresh(thresh.map_ref(|_| at_age.pop().unwrap()))),
558                _ => None,
559            };
560            match new_policy {
561                Some(new_policy) => at_age.push(Arc::new(new_policy)),
562                None => at_age.push(Arc::clone(data.node)),
563            }
564        }
565        // Unwrap is ok because we know we processed at least one node.
566        let root_node = at_age.pop().unwrap();
567        // Unwrap is ok because we know `root_node` is the only strong reference.
568        let policy = Arc::try_unwrap(root_node).unwrap();
569        policy.normalized()
570    }
571
572    /// Counts the number of public keys and keyhashes referenced in a policy.
573    /// Duplicate keys will be double-counted.
574    pub fn n_keys(&self) -> usize {
575        self.pre_order_iter()
576            .filter(|policy| matches!(policy, Policy::Key(..)))
577            .count()
578    }
579
580    /// Counts the minimum number of public keys for which signatures could be
581    /// used to satisfy the policy.
582    ///
583    /// # Returns
584    ///
585    /// Returns `None` if the policy is not satisfiable.
586    pub fn minimum_n_keys(&self) -> Option<usize> {
587        use Policy::*;
588
589        let mut minimum_n_keys = vec![];
590        for data in self.rtl_post_order_iter() {
591            let minimum_n_key = match data.node {
592                Unsatisfiable => None,
593                Trivial | After(..) | Older(..) | Sha256(..) | Hash256(..) | Ripemd160(..)
594                | Hash160(..) => Some(0),
595                Key(..) => Some(1),
596                Thresh(ref thresh) => {
597                    let mut sublens = (0..thresh.n())
598                        .filter_map(|_| minimum_n_keys.pop().unwrap())
599                        .collect::<Vec<usize>>();
600                    if sublens.len() < thresh.k() {
601                        // Not enough branches are satisfiable
602                        None
603                    } else {
604                        sublens.sort_unstable();
605                        Some(sublens[0..thresh.k()].iter().cloned().sum::<usize>())
606                    }
607                }
608            };
609            minimum_n_keys.push(minimum_n_key);
610        }
611        // Ok to unwrap because we know we processed at least one node.
612        minimum_n_keys.pop().unwrap()
613    }
614}
615
616impl<Pk: MiniscriptKey> Policy<Pk> {
617    /// "Sorts" a policy to bring it into a canonical form to allow comparisons.
618    ///
619    /// Does **not** allow policies to be compared for functional equivalence;
620    /// in general this appears to require Gröbner basis techniques that are not
621    /// implemented.
622    pub fn sorted(self) -> Policy<Pk> {
623        use Policy::*;
624
625        let mut sorted = vec![];
626        for data in Arc::new(self).rtl_post_order_iter() {
627            let new_policy = match data.node.as_ref() {
628                Thresh(ref thresh) => {
629                    let mut new_thresh = thresh.map_ref(|_| sorted.pop().unwrap());
630                    new_thresh.data_mut().sort();
631                    Some(Thresh(new_thresh))
632                }
633                _ => None,
634            };
635            match new_policy {
636                Some(new_policy) => sorted.push(Arc::new(new_policy)),
637                None => sorted.push(Arc::clone(data.node)),
638            }
639        }
640        // Unwrap is ok because we know we processed at least one node.
641        let root_node = sorted.pop().unwrap();
642        // Unwrap is ok because we know `root_node` is the only strong reference.
643        Arc::try_unwrap(root_node).unwrap()
644    }
645}
646
647impl<'a, Pk: MiniscriptKey> TreeLike for &'a Policy<Pk> {
648    type NaryChildren = &'a [Arc<Policy<Pk>>];
649
650    fn nary_len(tc: &Self::NaryChildren) -> usize { tc.len() }
651    fn nary_index(tc: Self::NaryChildren, idx: usize) -> Self { &tc[idx] }
652
653    fn as_node(&self) -> Tree<Self, Self::NaryChildren> {
654        use Policy::*;
655
656        match *self {
657            Unsatisfiable | Trivial | Key(_) | After(_) | Older(_) | Sha256(_) | Hash256(_)
658            | Ripemd160(_) | Hash160(_) => Tree::Nullary,
659            Thresh(ref thresh) => Tree::Nary(thresh.data()),
660        }
661    }
662}
663
664impl<'a, Pk: MiniscriptKey> TreeLike for &'a Arc<Policy<Pk>> {
665    type NaryChildren = &'a [Arc<Policy<Pk>>];
666
667    fn nary_len(tc: &Self::NaryChildren) -> usize { tc.len() }
668    fn nary_index(tc: Self::NaryChildren, idx: usize) -> Self { &tc[idx] }
669
670    fn as_node(&self) -> Tree<Self, Self::NaryChildren> {
671        use Policy::*;
672
673        match ***self {
674            Unsatisfiable | Trivial | Key(_) | After(_) | Older(_) | Sha256(_) | Hash256(_)
675            | Ripemd160(_) | Hash160(_) => Tree::Nullary,
676            Thresh(ref thresh) => Tree::Nary(thresh.data()),
677        }
678    }
679}
680
681#[cfg(test)]
682mod tests {
683    use core::str::FromStr as _;
684
685    use bitcoin::PublicKey;
686
687    use super::*;
688
689    type StringPolicy = Policy<String>;
690
691    #[test]
692    fn parse_policy_err() {
693        assert!(StringPolicy::from_str("(").is_err());
694        assert!(StringPolicy::from_str("(x()").is_err());
695        assert!(StringPolicy::from_str("(\u{7f}()3").is_err());
696        assert!(StringPolicy::from_str("pk()").is_ok());
697
698        assert!(StringPolicy::from_str("or(or)").is_err());
699
700        assert!(Policy::<PublicKey>::from_str("pk()").is_err());
701        assert!(Policy::<PublicKey>::from_str(
702            "pk(\
703             0200000000000000000000000000000000000002\
704             )"
705        )
706        .is_err());
707        assert!(Policy::<PublicKey>::from_str(
708            "pk(\
709                02c79ef3ede6d14f72a00d0e49b4becfb152197b64c0707425c4f231df29500ee7\
710             )"
711        )
712        .is_ok());
713    }
714
715    #[test]
716    fn semantic_analysis() {
717        let policy = StringPolicy::from_str("pk()").unwrap();
718        assert_eq!(policy, Policy::Key("".to_owned()));
719        assert_eq!(policy.relative_timelocks(), vec![]);
720        assert_eq!(policy.absolute_timelocks(), vec![]);
721        assert_eq!(policy.clone().at_age(RelLockTime::ZERO.into()), policy);
722        assert_eq!(
723            policy
724                .clone()
725                .at_age(RelLockTime::from_height(10000).into()),
726            policy
727        );
728        assert_eq!(policy.n_keys(), 1);
729        assert_eq!(policy.minimum_n_keys(), Some(1));
730
731        let policy = StringPolicy::from_str("older(1000)").unwrap();
732        assert_eq!(policy, Policy::Older(RelLockTime::from_height(1000)));
733        assert_eq!(policy.absolute_timelocks(), vec![]);
734        assert_eq!(policy.relative_timelocks(), vec![1000]);
735        assert_eq!(policy.clone().at_age(RelLockTime::ZERO.into()), Policy::Unsatisfiable);
736        assert_eq!(
737            policy.clone().at_age(RelLockTime::from_height(999).into()),
738            Policy::Unsatisfiable
739        );
740        assert_eq!(policy.clone().at_age(RelLockTime::from_height(1000).into()), policy);
741        assert_eq!(
742            policy
743                .clone()
744                .at_age(RelLockTime::from_height(10000).into()),
745            policy
746        );
747        assert_eq!(policy.n_keys(), 0);
748        assert_eq!(policy.minimum_n_keys(), Some(0));
749
750        let policy = StringPolicy::from_str("or(pk(),older(1000))").unwrap();
751        assert_eq!(
752            policy,
753            Policy::Thresh(Threshold::or(
754                Policy::Key("".to_owned()).into(),
755                Policy::Older(RelLockTime::from_height(1000)).into(),
756            ))
757        );
758        assert_eq!(policy.relative_timelocks(), vec![1000]);
759        assert_eq!(policy.absolute_timelocks(), vec![]);
760        assert_eq!(policy.clone().at_age(RelLockTime::ZERO.into()), Policy::Key("".to_owned()));
761        assert_eq!(
762            policy.clone().at_age(RelLockTime::from_height(999).into()),
763            Policy::Key("".to_owned())
764        );
765        assert_eq!(
766            policy.clone().at_age(RelLockTime::from_height(1000).into()),
767            policy.clone().normalized()
768        );
769        assert_eq!(
770            policy
771                .clone()
772                .at_age(RelLockTime::from_height(10000).into()),
773            policy.clone().normalized()
774        );
775        assert_eq!(policy.n_keys(), 1);
776        assert_eq!(policy.minimum_n_keys(), Some(0));
777
778        let policy = StringPolicy::from_str("or(pk(),UNSATISFIABLE)").unwrap();
779        assert_eq!(
780            policy,
781            Policy::Thresh(Threshold::or(
782                Policy::Key("".to_owned()).into(),
783                Policy::Unsatisfiable.into()
784            ))
785        );
786        assert_eq!(policy.relative_timelocks(), vec![]);
787        assert_eq!(policy.absolute_timelocks(), vec![]);
788        assert_eq!(policy.n_keys(), 1);
789        assert_eq!(policy.minimum_n_keys(), Some(1));
790
791        let policy = StringPolicy::from_str("and(pk(),UNSATISFIABLE)").unwrap();
792        assert_eq!(
793            policy,
794            Policy::Thresh(Threshold::and(
795                Policy::Key("".to_owned()).into(),
796                Policy::Unsatisfiable.into()
797            ))
798        );
799        assert_eq!(policy.relative_timelocks(), vec![]);
800        assert_eq!(policy.absolute_timelocks(), vec![]);
801        assert_eq!(policy.n_keys(), 1);
802        assert_eq!(policy.minimum_n_keys(), None);
803
804        let policy = StringPolicy::from_str(
805            "thresh(\
806             2,older(1000),older(10000),older(1000),older(2000),older(2000)\
807             )",
808        )
809        .unwrap();
810        assert_eq!(
811            policy,
812            Policy::Thresh(
813                Threshold::new(
814                    2,
815                    vec![
816                        Policy::Older(RelLockTime::from_height(1000)).into(),
817                        Policy::Older(RelLockTime::from_height(10000)).into(),
818                        Policy::Older(RelLockTime::from_height(1000)).into(),
819                        Policy::Older(RelLockTime::from_height(2000)).into(),
820                        Policy::Older(RelLockTime::from_height(2000)).into(),
821                    ]
822                )
823                .unwrap()
824            )
825        );
826        assert_eq!(
827            policy.relative_timelocks(),
828            vec![1000, 2000, 10000] //sorted and dedup'd
829        );
830
831        let policy = StringPolicy::from_str(
832            "thresh(\
833             2,older(1000),older(10000),older(1000),UNSATISFIABLE,UNSATISFIABLE\
834             )",
835        )
836        .unwrap();
837        assert_eq!(
838            policy,
839            Policy::Thresh(
840                Threshold::new(
841                    2,
842                    vec![
843                        Policy::Older(RelLockTime::from_height(1000)).into(),
844                        Policy::Older(RelLockTime::from_height(10000)).into(),
845                        Policy::Older(RelLockTime::from_height(1000)).into(),
846                        Policy::Unsatisfiable.into(),
847                        Policy::Unsatisfiable.into(),
848                    ]
849                )
850                .unwrap()
851            )
852        );
853        assert_eq!(
854            policy.relative_timelocks(),
855            vec![1000, 10000] //sorted and dedup'd
856        );
857        assert_eq!(policy.n_keys(), 0);
858        assert_eq!(policy.minimum_n_keys(), Some(0));
859
860        // Block height 1000.
861        let policy = StringPolicy::from_str("after(1000)").unwrap();
862        assert_eq!(policy, Policy::After(AbsLockTime::from_consensus(1000).unwrap()));
863        assert_eq!(policy.absolute_timelocks(), vec![1000]);
864        assert_eq!(policy.relative_timelocks(), vec![]);
865        assert_eq!(policy.clone().at_lock_time(absolute::LockTime::ZERO), Policy::Unsatisfiable);
866        assert_eq!(
867            policy
868                .clone()
869                .at_lock_time(absolute::LockTime::from_height(999).expect("valid block height")),
870            Policy::Unsatisfiable
871        );
872        assert_eq!(
873            policy
874                .clone()
875                .at_lock_time(absolute::LockTime::from_height(1000).expect("valid block height")),
876            policy
877        );
878        assert_eq!(
879            policy
880                .clone()
881                .at_lock_time(absolute::LockTime::from_height(10000).expect("valid block height")),
882            policy
883        );
884        // Pass a UNIX timestamp to at_lock_time while policy uses a block height.
885        assert_eq!(
886            policy
887                .clone()
888                .at_lock_time(absolute::LockTime::from_time(500_000_001).expect("valid timestamp")),
889            Policy::Unsatisfiable
890        );
891        assert_eq!(policy.n_keys(), 0);
892        assert_eq!(policy.minimum_n_keys(), Some(0));
893
894        // UNIX timestamp of 10 seconds after the epoch.
895        let policy = StringPolicy::from_str("after(500000010)").unwrap();
896        assert_eq!(policy, Policy::After(AbsLockTime::from_consensus(500_000_010).unwrap()));
897        assert_eq!(policy.absolute_timelocks(), vec![500_000_010]);
898        assert_eq!(policy.relative_timelocks(), vec![]);
899        // Pass a block height to at_lock_time while policy uses a UNIX timestapm.
900        assert_eq!(policy.clone().at_lock_time(absolute::LockTime::ZERO), Policy::Unsatisfiable);
901        assert_eq!(
902            policy
903                .clone()
904                .at_lock_time(absolute::LockTime::from_height(999).expect("valid block height")),
905            Policy::Unsatisfiable
906        );
907        assert_eq!(
908            policy
909                .clone()
910                .at_lock_time(absolute::LockTime::from_height(1000).expect("valid block height")),
911            Policy::Unsatisfiable
912        );
913        assert_eq!(
914            policy
915                .clone()
916                .at_lock_time(absolute::LockTime::from_height(10000).expect("valid block height")),
917            Policy::Unsatisfiable
918        );
919        // And now pass a UNIX timestamp to at_lock_time while policy also uses a timestamp.
920        assert_eq!(
921            policy
922                .clone()
923                .at_lock_time(absolute::LockTime::from_time(500_000_000).expect("valid timestamp")),
924            Policy::Unsatisfiable
925        );
926        assert_eq!(
927            policy
928                .clone()
929                .at_lock_time(absolute::LockTime::from_time(500_000_001).expect("valid timestamp")),
930            Policy::Unsatisfiable
931        );
932        assert_eq!(
933            policy
934                .clone()
935                .at_lock_time(absolute::LockTime::from_time(500_000_010).expect("valid timestamp")),
936            policy
937        );
938        assert_eq!(
939            policy
940                .clone()
941                .at_lock_time(absolute::LockTime::from_time(500_000_012).expect("valid timestamp")),
942            policy
943        );
944        assert_eq!(policy.n_keys(), 0);
945        assert_eq!(policy.minimum_n_keys(), Some(0));
946    }
947
948    #[test]
949    fn entailment_liquid_test() {
950        //liquid policy
951        let liquid_pol = StringPolicy::from_str(
952            "or(and(older(4096),thresh(2,pk(A),pk(B),pk(C))),thresh(11,pk(F1),pk(F2),pk(F3),pk(F4),pk(F5),pk(F6),pk(F7),pk(F8),pk(F9),pk(F10),pk(F11),pk(F12),pk(F13),pk(F14)))").unwrap();
953        // Very bad idea to add master key,pk but let's have it have 50M blocks
954        let master_key = StringPolicy::from_str("and(older(50000000),pk(master))").unwrap();
955        let new_liquid_pol =
956            Policy::Thresh(Threshold::or(liquid_pol.clone().into(), master_key.into()));
957
958        assert!(liquid_pol.clone().entails(new_liquid_pol.clone()).unwrap());
959        assert!(!new_liquid_pol.entails(liquid_pol.clone()).unwrap());
960
961        // test liquid backup policy before the emergency timeout
962        let backup_policy = StringPolicy::from_str("thresh(2,pk(A),pk(B),pk(C))").unwrap();
963        assert!(!backup_policy
964            .entails(
965                liquid_pol
966                    .clone()
967                    .at_age(RelLockTime::from_height(4095).into())
968            )
969            .unwrap());
970
971        // Finally test both spending paths
972        let fed_pol = StringPolicy::from_str("thresh(11,pk(F1),pk(F2),pk(F3),pk(F4),pk(F5),pk(F6),pk(F7),pk(F8),pk(F9),pk(F10),pk(F11),pk(F12),pk(F13),pk(F14))").unwrap();
973        let backup_policy_after_expiry =
974            StringPolicy::from_str("and(older(4096),thresh(2,pk(A),pk(B),pk(C)))").unwrap();
975        assert!(fed_pol.entails(liquid_pol.clone()).unwrap());
976        assert!(backup_policy_after_expiry.entails(liquid_pol).unwrap());
977    }
978
979    #[test]
980    fn entailment_escrow() {
981        // Escrow contract
982        let escrow_pol = StringPolicy::from_str("thresh(2,pk(Alice),pk(Bob),pk(Judge))").unwrap();
983        // Alice's authorization constraint
984        // Authorization is a constraint that states the conditions under which one party must
985        // be able to redeem the funds.
986        let auth_alice = StringPolicy::from_str("and(pk(Alice),pk(Judge))").unwrap();
987
988        //Alice's Control constraint
989        // The control constraint states the conditions that one party requires
990        // must be met if the funds are spent by anyone
991        // Either Alice must authorize the funds or both Judge and Bob must control it
992        let control_alice = StringPolicy::from_str("or(pk(Alice),and(pk(Judge),pk(Bob)))").unwrap();
993
994        // Entailment rules
995        // Authorization entails |- policy |- control constraints
996        assert!(auth_alice.entails(escrow_pol.clone()).unwrap());
997        assert!(escrow_pol.entails(control_alice).unwrap());
998
999        // Entailment HTLC's
1000        // Escrow contract
1001        let h = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
1002        let htlc_pol = StringPolicy::from_str(&format!(
1003            "or(and(pk(Alice),older(100)),and(pk(Bob),sha256({})))",
1004            h
1005        ))
1006        .unwrap();
1007        // Alice's authorization constraint
1008        // Authorization is a constraint that states the conditions under which one party must
1009        // be able to redeem the funds. In HLTC, alice only cares that she can
1010        // authorize her funds with Pk and CSV 100.
1011        let auth_alice = StringPolicy::from_str("and(pk(Alice),older(100))").unwrap();
1012
1013        //Alice's Control constraint
1014        // The control constraint states the conditions that one party requires
1015        // must be met if the funds are spent by anyone
1016        // Either Alice must authorize the funds or sha2 preimage must be revealed.
1017        let control_alice =
1018            StringPolicy::from_str(&format!("or(pk(Alice),sha256({}))", h)).unwrap();
1019
1020        // Entailment rules
1021        // Authorization entails |- policy |- control constraints
1022        assert!(auth_alice.entails(htlc_pol.clone()).unwrap());
1023        assert!(htlc_pol.entails(control_alice).unwrap());
1024    }
1025
1026    #[test]
1027    fn for_each_key() {
1028        let liquid_pol = StringPolicy::from_str(
1029            "or(and(older(4096),thresh(2,pk(A),pk(B),pk(C))),thresh(11,pk(F1),pk(F2),pk(F3),pk(F4),pk(F5),pk(F6),pk(F7),pk(F8),pk(F9),pk(F10),pk(F11),pk(F12),pk(F13),pk(F14)))").unwrap();
1030        let mut count = 0;
1031        assert!(liquid_pol.for_each_key(|_| {
1032            count += 1;
1033            true
1034        }));
1035        assert_eq!(count, 17);
1036    }
1037}
miniscript/policy/semantic.rs

miniscript/policy/
semantic.rs
