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

sapio_miniscript/miniscript/types/
malleability.rs
