miniscript_debug/miniscript/types/
malleability.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//! Malleability-related Type properties
16
17use super::{ErrorKind, Property};
18use crate::ScriptContext;
19
20/// Whether the fragment has a dissatisfaction, and if so, whether
21/// it is unique. Affects both correctness and malleability-freeness,
22/// since we assume 3rd parties are able to produce dissatisfactions
23/// for all fragments.
24#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash)]
25pub enum Dissat {
26    /// Fragment has no dissatisfactions and will abort given non-satisfying
27    /// input.
28    None,
29    /// Fragment has a unique dissatisfaction, which is always available,
30    /// and will push 0 given this dissatisfaction as input. The combination
31    /// of `Dissat::Unique` and `Input::Zero` implies that a fragment is
32    /// impossible to satisfy (is a `0` or equivalent).
33    Unique,
34    /// No assumptions may be made about dissatisfying this fragment. This
35    /// does not necessarily mean that there are multiple dissatisfactions;
36    /// there may be none, or none that are always available (e.g. for a
37    /// `pk_h` the key preimage may not be available).
38    Unknown,
39}
40
41impl Dissat {
42    /// Check whether given `Dissat` is a subtype of `other`. That is,
43    /// if some Dissat is `Unique` then it must be `Unknown`.
44    fn is_subtype(&self, other: Self) -> bool {
45        match (*self, other) {
46            (x, y) if x == y => true,
47            (_, Dissat::Unknown) => true,
48            _ => false,
49        }
50    }
51}
52
53/// Structure representing the type properties of a fragment which have
54/// relevance to malleability analysis
55#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash)]
56pub struct Malleability {
57    /// Properties of dissatisfying inputs
58    pub dissat: Dissat,
59    /// `true` if satisfactions cannot be created by any 3rd party
60    /// who has not yet seen a satisfaction. (Hash preimages and
61    /// signature checks are safe; timelocks are not.) Affects
62    /// malleability.
63    pub safe: bool,
64    /// Whether a non-malleable satisfaction is guaranteed to exist for
65    /// the fragment
66    pub non_malleable: bool,
67}
68
69impl Malleability {
70    /// Check whether the `self` is a subtype of `other` argument .
71    /// This checks whether the argument `other` has attributes which are present
72    /// in the given `Type`. This returns `true` on same arguments
73    /// `a.is_subtype(a)` is `true`.
74    pub fn is_subtype(&self, other: Self) -> bool {
75        self.dissat.is_subtype(other.dissat)
76            && self.safe >= other.safe
77            && self.non_malleable >= other.non_malleable
78    }
79}
80
81impl Property for Malleability {
82    fn from_true() -> Self {
83        Malleability {
84            dissat: Dissat::None,
85            safe: false,
86            non_malleable: true,
87        }
88    }
89
90    fn from_false() -> Self {
91        Malleability {
92            dissat: Dissat::Unique,
93            safe: true,
94            non_malleable: true,
95        }
96    }
97
98    fn from_pk_k<Ctx: ScriptContext>() -> Self {
99        Malleability {
100            dissat: Dissat::Unique,
101            safe: true,
102            non_malleable: true,
103        }
104    }
105
106    fn from_pk_h<Ctx: ScriptContext>() -> Self {
107        Malleability {
108            dissat: Dissat::Unique,
109            safe: true,
110            non_malleable: true,
111        }
112    }
113
114    fn from_multi(_: usize, _: usize) -> Self {
115        Malleability {
116            dissat: Dissat::Unique,
117            safe: true,
118            non_malleable: true,
119        }
120    }
121
122    fn from_multi_a(_: usize, _: usize) -> Self {
123        Malleability {
124            dissat: Dissat::Unique,
125            safe: true,
126            non_malleable: true,
127        }
128    }
129
130    fn from_hash() -> Self {
131        Malleability {
132            dissat: Dissat::Unknown,
133            safe: false,
134            non_malleable: true,
135        }
136    }
137
138    fn from_time(_: u32) -> Self {
139        Malleability {
140            dissat: Dissat::None,
141            safe: false,
142            non_malleable: true,
143        }
144    }
145
146    fn cast_alt(self) -> Result<Self, ErrorKind> {
147        Ok(self)
148    }
149
150    fn cast_swap(self) -> Result<Self, ErrorKind> {
151        Ok(self)
152    }
153
154    fn cast_check(self) -> Result<Self, ErrorKind> {
155        Ok(self)
156    }
157
158    fn cast_dupif(self) -> Result<Self, ErrorKind> {
159        Ok(Malleability {
160            dissat: if self.dissat == Dissat::None {
161                Dissat::Unique
162            } else {
163                Dissat::Unknown
164            },
165            safe: self.safe,
166            non_malleable: self.non_malleable,
167        })
168    }
169
170    fn cast_verify(self) -> Result<Self, ErrorKind> {
171        Ok(Malleability {
172            dissat: Dissat::None,
173            safe: self.safe,
174            non_malleable: self.non_malleable,
175        })
176    }
177
178    fn cast_nonzero(self) -> Result<Self, ErrorKind> {
179        Ok(Malleability {
180            dissat: if self.dissat == Dissat::None {
181                Dissat::Unique
182            } else {
183                Dissat::Unknown
184            },
185            safe: self.safe,
186            non_malleable: self.non_malleable,
187        })
188    }
189
190    fn cast_zeronotequal(self) -> Result<Self, ErrorKind> {
191        Ok(self)
192    }
193
194    fn cast_true(self) -> Result<Self, ErrorKind> {
195        Ok(Malleability {
196            dissat: Dissat::None,
197            safe: self.safe,
198            non_malleable: self.non_malleable,
199        })
200    }
201
202    fn cast_or_i_false(self) -> Result<Self, ErrorKind> {
203        Ok(Malleability {
204            dissat: if self.dissat == Dissat::None {
205                Dissat::Unique
206            } else {
207                Dissat::Unknown
208            },
209            safe: self.safe,
210            non_malleable: self.non_malleable,
211        })
212    }
213
214    fn and_b(left: Self, right: Self) -> Result<Self, ErrorKind> {
215        Ok(Malleability {
216            dissat: match (left.dissat, right.dissat) {
217                (Dissat::None, Dissat::None) => Dissat::None,
218                (Dissat::None, _) if left.safe => Dissat::None,
219                (_, Dissat::None) if right.safe => Dissat::None,
220                (Dissat::Unique, Dissat::Unique) => {
221                    if left.safe && right.safe {
222                        Dissat::Unique
223                    } else {
224                        Dissat::Unknown
225                    }
226                }
227                _ => Dissat::Unknown,
228            },
229            safe: left.safe || right.safe,
230            non_malleable: left.non_malleable && right.non_malleable,
231        })
232    }
233
234    fn and_v(left: Self, right: Self) -> Result<Self, ErrorKind> {
235        Ok(Malleability {
236            dissat: match (left.safe, right.dissat) {
237                (_, Dissat::None) => Dissat::None, // fy
238                (true, _) => Dissat::None,         // sx
239                _ => Dissat::Unknown,
240            },
241            safe: left.safe || right.safe,
242            non_malleable: left.non_malleable && right.non_malleable,
243        })
244    }
245
246    fn or_b(left: Self, right: Self) -> Result<Self, ErrorKind> {
247        Ok(Malleability {
248            dissat: Dissat::Unique,
249            safe: left.safe && right.safe,
250            non_malleable: left.non_malleable
251                && left.dissat == Dissat::Unique
252                && right.non_malleable
253                && right.dissat == Dissat::Unique
254                && (left.safe || right.safe),
255        })
256    }
257
258    fn or_d(left: Self, right: Self) -> Result<Self, ErrorKind> {
259        Ok(Malleability {
260            dissat: right.dissat,
261            safe: left.safe && right.safe,
262            non_malleable: left.non_malleable
263                && left.dissat == Dissat::Unique
264                && right.non_malleable
265                && (left.safe || right.safe),
266        })
267    }
268
269    fn or_c(left: Self, right: Self) -> Result<Self, ErrorKind> {
270        Ok(Malleability {
271            dissat: Dissat::None,
272            safe: left.safe && right.safe,
273            non_malleable: left.non_malleable
274                && left.dissat == Dissat::Unique
275                && right.non_malleable
276                && (left.safe || right.safe),
277        })
278    }
279
280    fn or_i(left: Self, right: Self) -> Result<Self, ErrorKind> {
281        Ok(Malleability {
282            dissat: match (left.dissat, right.dissat) {
283                (Dissat::None, Dissat::None) => Dissat::None,
284                (Dissat::Unique, Dissat::None) => Dissat::Unique,
285                (Dissat::None, Dissat::Unique) => Dissat::Unique,
286                _ => Dissat::Unknown,
287            },
288            safe: left.safe && right.safe,
289            non_malleable: left.non_malleable && right.non_malleable && (left.safe || right.safe),
290        })
291    }
292
293    fn and_or(a: Self, b: Self, c: Self) -> Result<Self, ErrorKind> {
294        Ok(Malleability {
295            dissat: match (a.safe, b.dissat, c.dissat) {
296                (_, Dissat::None, Dissat::Unique) => Dissat::Unique, //E: ez fy
297                (true, _, Dissat::Unique) => Dissat::Unique,         // E: ez sx
298                (_, Dissat::None, Dissat::None) => Dissat::None,     // F: fy && fz
299                (true, _, Dissat::None) => Dissat::None,             // F: sx && fz
300                _ => Dissat::Unknown,
301            },
302            safe: (a.safe || b.safe) && c.safe,
303            non_malleable: a.non_malleable
304                && c.non_malleable
305                && a.dissat == Dissat::Unique
306                && b.non_malleable
307                && (a.safe || b.safe || c.safe),
308        })
309    }
310
311    fn threshold<S>(k: usize, n: usize, mut sub_ck: S) -> Result<Self, ErrorKind>
312    where
313        S: FnMut(usize) -> Result<Self, ErrorKind>,
314    {
315        let mut safe_count = 0;
316        let mut all_are_dissat_unique = true;
317        let mut all_are_non_malleable = true;
318        for i in 0..n {
319            let subtype = sub_ck(i)?;
320            safe_count += if subtype.safe { 1 } else { 0 };
321            all_are_dissat_unique &= subtype.dissat == Dissat::Unique;
322            all_are_non_malleable &= subtype.non_malleable;
323        }
324        Ok(Malleability {
325            dissat: if all_are_dissat_unique && safe_count == n {
326                Dissat::Unique
327            } else {
328                Dissat::Unknown
329            },
330            safe: safe_count > n - k,
331            non_malleable: all_are_non_malleable && safe_count >= n - k && all_are_dissat_unique,
332        })
333    }
334}
miniscript_debug/miniscript/types/malleability.rs

miniscript_debug/miniscript/types/
malleability.rs
