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

simplicity/policy/
ast.rs
