elements_miniscript/policy/
semantic.rs

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

elements_miniscript/policy/
semantic.rs
