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

simplicity/policy/
ast.rs
