elements_miniscript/miniscript/types/
malleability.rs

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

elements_miniscript/miniscript/types/
malleability.rs
