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

simplicity/policy/
ast.rs
