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

miniscript/policy/
semantic.rs
