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

elements_miniscript/policy/
semantic.rs
