simplicity/policy/
ast.rs

1// SPDX-License-Identifier: CC0-1.0
2
3//! # Abstract Policies
4//!
5//! These policies represent spending conditions in the most simplest form
6//! Policies are combination of `and`, `or` and `thresh` fragments. For example,
7//! or(pk(A),pk(B)) represents a policy that can be spend with either pk(A) or pk(B).
8//! These policies can be compiled to Simplicity and also be lifted back up from
9//! Simplicity expressions to policy.
10
11use std::convert::TryFrom;
12use std::sync::Arc;
13use std::{fmt, iter, mem};
14
15use crate::node::{ConstructNode, CoreConstructible, WitnessConstructible};
16use crate::policy::serialize;
17use crate::{types, Value};
18use crate::{Cmr, CommitNode, FailEntropy};
19use crate::{SimplicityKey, ToXOnlyPubkey, Translator};
20
21/// Policy that expresses spending conditions for Simplicity.
22///
23/// The policy can be compiled into a Simplicity program and executed on the Bit Machine,
24/// given a witness.
25///
26/// Furthermore, the policy can be normalized and is amenable to semantic analysis.
27#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
28pub enum Policy<Pk: SimplicityKey> {
29    /// Unsatisfiable
30    Unsatisfiable(FailEntropy),
31    /// Trivially satisfiable
32    Trivial,
33    /// Provide a signature that matches the given public key and some given message hash
34    Key(Pk),
35    /// Absolute timelock
36    After(u32),
37    /// Relative timelock
38    Older(u16),
39    /// Provide the preimage of the given SHA256 hash image
40    Sha256(Pk::Sha256),
41    /// Satisfy both of the given sub-policies
42    And {
43        left: Arc<Policy<Pk>>,
44        right: Arc<Policy<Pk>>,
45    },
46    /// Satisfy exactly one of the given sub-policies
47    Or {
48        left: Arc<Policy<Pk>>,
49        right: Arc<Policy<Pk>>,
50    },
51    /// Satisfy exactly `k` of the given sub-policies
52    Threshold(usize, Vec<Policy<Pk>>),
53}
54
55impl<Pk: ToXOnlyPubkey> Policy<Pk> {
56    /// Serializes the policy as a Simplicity fragment, with all witness nodes unpopulated.
57    fn serialize_no_witness<'brand, N>(&self, inference_context: &types::Context<'brand>) -> N
58    where
59        N: CoreConstructible<'brand> + WitnessConstructible<'brand, Option<Value>>,
60    {
61        match *self {
62            Policy::Unsatisfiable(entropy) => serialize::unsatisfiable(inference_context, entropy),
63            Policy::Trivial => serialize::trivial(inference_context),
64            Policy::After(n) => serialize::after(inference_context, n),
65            Policy::Older(n) => serialize::older(inference_context, n),
66            Policy::Key(ref key) => serialize::key(inference_context, key, None),
67            Policy::Sha256(ref hash) => {
68                serialize::sha256::<Pk, _, _>(inference_context, hash, None)
69            }
70            Policy::And {
71                ref left,
72                ref right,
73            } => {
74                let left = left.serialize_no_witness(inference_context);
75                let right = right.serialize_no_witness(inference_context);
76                serialize::and(&left, &right)
77            }
78            Policy::Or {
79                ref left,
80                ref right,
81            } => {
82                let left = left.serialize_no_witness(inference_context);
83                let right = right.serialize_no_witness(inference_context);
84                serialize::or(&left, &right, None)
85            }
86            Policy::Threshold(k, ref subs) => {
87                let k = u32::try_from(k).expect("can have k at most 2^32 in a threshold");
88                let subs = subs
89                    .iter()
90                    .map(|sub| sub.serialize_no_witness(inference_context))
91                    .collect::<Vec<N>>();
92                let wits = iter::repeat(None).take(subs.len()).collect::<Vec<_>>();
93                serialize::threshold(k, &subs, &wits)
94            }
95        }
96    }
97
98    /// Return the program commitment of the policy.
99    pub fn commit(&self) -> Arc<CommitNode> {
100        types::Context::with_context(|ctx| {
101            let construct: Arc<ConstructNode> = self.serialize_no_witness(&ctx);
102            construct.finalize_types().expect("policy has sound types")
103        })
104    }
105
106    /// Return the CMR of the policy.
107    pub fn cmr(&self) -> Cmr {
108        types::Context::with_context(|ctx| {
109            self.serialize_no_witness::<crate::merkle::cmr::ConstructibleCmr>(&ctx)
110                .cmr
111        })
112    }
113}
114
115impl<Pk: SimplicityKey> Policy<Pk> {
116    /// Convert a policy using one kind of public key to another
117    /// type of public key
118    pub fn translate<T, Q, E>(&self, translator: &mut T) -> Result<Policy<Q>, E>
119    where
120        T: Translator<Pk, Q, E>,
121        Q: SimplicityKey,
122    {
123        match *self {
124            Policy::Unsatisfiable(entropy) => Ok(Policy::Unsatisfiable(entropy)),
125            Policy::Trivial => Ok(Policy::Trivial),
126            Policy::Key(ref pk) => translator.pk(pk).map(Policy::Key),
127            Policy::Sha256(ref h) => translator.sha256(h).map(Policy::Sha256),
128            Policy::After(n) => Ok(Policy::After(n)),
129            Policy::Older(n) => Ok(Policy::Older(n)),
130            Policy::Threshold(k, ref subs) => {
131                let new_subs: Result<Vec<Policy<Q>>, _> =
132                    subs.iter().map(|sub| sub.translate(translator)).collect();
133                new_subs.map(|ok| Policy::Threshold(k, ok))
134            }
135            Policy::And {
136                ref left,
137                ref right,
138            } => Ok(Policy::And {
139                left: Arc::new(left.translate(translator)?),
140                right: Arc::new(right.translate(translator)?),
141            }),
142            Policy::Or {
143                ref left,
144                ref right,
145            } => Ok(Policy::Or {
146                left: Arc::new(left.translate(translator)?),
147                right: Arc::new(right.translate(translator)?),
148            }),
149        }
150    }
151
152    /// Flatten out trees of `And`s and `Or`s; eliminate `Trivial` and
153    /// `Unsatisfiable`s. Does not reorder any branches; use `.sort`.
154    pub fn normalized(self) -> Policy<Pk> {
155        match self {
156            Policy::And { left, right } => {
157                if let Policy::Unsatisfiable(entropy) = *left {
158                    Policy::Unsatisfiable(entropy)
159                } else if let Policy::Unsatisfiable(entropy) = *right {
160                    Policy::Unsatisfiable(entropy)
161                } else if *left == Policy::Trivial {
162                    right.as_ref().clone().normalized()
163                } else if *right == Policy::Trivial {
164                    left.as_ref().clone().normalized()
165                } else {
166                    Policy::And {
167                        left: Arc::new(left.as_ref().clone().normalized()),
168                        right: Arc::new(right.as_ref().clone().normalized()),
169                    }
170                }
171            }
172            Policy::Or { left, right } => {
173                if *left == Policy::Trivial || *right == Policy::Trivial {
174                    Policy::Trivial
175                } else if let Policy::Unsatisfiable(..) = *left {
176                    right.as_ref().clone().normalized()
177                } else if let Policy::Unsatisfiable(..) = *right {
178                    left.as_ref().clone().normalized()
179                } else {
180                    Policy::Or {
181                        left: Arc::new(left.as_ref().clone().normalized()),
182                        right: Arc::new(right.as_ref().clone().normalized()),
183                    }
184                }
185            }
186            x => x,
187        }
188    }
189
190    /// "Sort" a policy to bring it into a canonical form to allow comparisons.
191    /// Does **not** allow policies to be compared for functional equivalence;
192    /// in general this appears to require Gröbner basis techniques that are not
193    /// implemented.
194    pub fn sorted(mut self) -> Policy<Pk> {
195        self.sort();
196        self
197    }
198
199    fn sort(&mut self) {
200        match self {
201            Policy::And {
202                ref mut left,
203                ref mut right,
204            }
205            | Policy::Or {
206                ref mut left,
207                ref mut right,
208            } => {
209                left.as_ref().clone().sort();
210                right.as_ref().clone().sort();
211                if right > left {
212                    mem::swap(left, right);
213                }
214            }
215            Policy::Threshold(_, ref mut subs) => {
216                for sub in &mut *subs {
217                    sub.sort();
218                }
219                subs.sort();
220            }
221            _ => {}
222        }
223    }
224
225    /// Return an iterator over the fragments of the policy.
226    pub fn iter(&self) -> PolicyIter<'_, Pk> {
227        PolicyIter::new(self)
228    }
229
230    /// Return an iterator over the public keys of the policy.
231    pub fn iter_pk(&self) -> impl Iterator<Item = Pk> + '_ {
232        self.iter().filter_map(|fragment| match fragment {
233            Policy::Key(key) => Some(key.clone()),
234            _ => None,
235        })
236    }
237}
238
239impl<Pk: SimplicityKey> fmt::Debug for Policy<Pk> {
240    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
241        match self {
242            Policy::Unsatisfiable(..) => f.write_str("UNSATISFIABLE"),
243            Policy::Trivial => f.write_str("TRIVIAL"),
244            Policy::Key(pk) => write!(f, "pk({})", pk),
245            Policy::After(n) => write!(f, "after({})", n),
246            Policy::Older(n) => write!(f, "older({})", n),
247            Policy::Sha256(h) => write!(f, "sha256({})", h),
248            Policy::And { left, right } => write!(f, "and({},{})", left, right),
249            Policy::Or { left, right } => write!(f, "or({},{})", left, right),
250            Policy::Threshold(k, sub_policies) => {
251                write!(f, "thresh({}", k)?;
252                for sub in sub_policies {
253                    write!(f, ",{:?}", sub)?;
254                }
255                f.write_str(")")
256            }
257        }
258    }
259}
260
261impl<Pk: SimplicityKey> fmt::Display for Policy<Pk> {
262    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
263        fmt::Debug::fmt(self, f)
264    }
265}
266
267/// Iterator over the fragments of a Simplicity policy.
268///
269/// The fragments are visited in preorder:
270/// We first visit the parent, then the left subtree, then the right subtree.
271pub struct PolicyIter<'a, Pk: SimplicityKey> {
272    stack: Vec<&'a Policy<Pk>>,
273}
274
275impl<'a, Pk: SimplicityKey> PolicyIter<'a, Pk> {
276    /// Create an iterator for the given policy.
277    pub fn new(policy: &'a Policy<Pk>) -> Self {
278        Self {
279            stack: vec![policy],
280        }
281    }
282}
283
284impl<'a, Pk: SimplicityKey> Iterator for PolicyIter<'a, Pk> {
285    type Item = &'a Policy<Pk>;
286
287    fn next(&mut self) -> Option<Self::Item> {
288        let top = self.stack.pop()?;
289        match top {
290            Policy::And { left, right } | Policy::Or { left, right } => {
291                self.stack.push(right);
292                self.stack.push(left);
293            }
294            Policy::Threshold(_, children) => {
295                self.stack.extend(children.iter().rev());
296            }
297            _ => {}
298        }
299        Some(top)
300    }
301}
simplicity/policy/ast.rs

simplicity/policy/
ast.rs
