miniscript_debug/policy/
semantic.rs

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

miniscript_debug/policy/
semantic.rs
