miniscript_debug/descriptor/
sortedmulti.rs

1// Miniscript
2// Written in 2020 by rust-miniscript developers
3//
4// To the extent possible under law, the author(s) have dedicated all
5// copyright and related and neighboring rights to this software to
6// the public domain worldwide. This software is distributed without
7// any warranty.
8//
9// You should have received a copy of the CC0 Public Domain Dedication
10// along with this software.
11// If not, see <http://creativecommons.org/publicdomain/zero/1.0/>.
12//
13
14//! # Sorted Multi
15//!
16//! Implementation of sorted multi primitive for descriptors
17//!
18
19use core::fmt;
20use core::marker::PhantomData;
21use core::str::FromStr;
22
23use bitcoin::blockdata::script;
24
25use crate::miniscript::context::ScriptContext;
26use crate::miniscript::decode::Terminal;
27use crate::miniscript::limits::MAX_PUBKEYS_PER_MULTISIG;
28use crate::prelude::*;
29use crate::{
30    errstr, expression, miniscript, policy, script_num_size, Error, ForEachKey, Miniscript,
31    MiniscriptKey, Satisfier, ToPublicKey, Translator,
32};
33
34/// Contents of a "sortedmulti" descriptor
35#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
36pub struct SortedMultiVec<Pk: MiniscriptKey, Ctx: ScriptContext> {
37    /// signatures required
38    pub k: usize,
39    /// public keys inside sorted Multi
40    pub pks: Vec<Pk>,
41    /// The current ScriptContext for sortedmulti
42    pub(crate) phantom: PhantomData<Ctx>,
43}
44
45impl<Pk: MiniscriptKey, Ctx: ScriptContext> SortedMultiVec<Pk, Ctx> {
46    /// Create a new instance of `SortedMultiVec` given a list of keys and the threshold
47    ///
48    /// Internally checks all the applicable size limits and pubkey types limitations according to the current `Ctx`.
49    pub fn new(k: usize, pks: Vec<Pk>) -> Result<Self, Error> {
50        // A sortedmulti() is only defined for <= 20 keys (it maps to CHECKMULTISIG)
51        if pks.len() > MAX_PUBKEYS_PER_MULTISIG {
52            return Err(Error::BadDescriptor("Too many public keys".to_string()));
53        }
54
55        // Check the limits before creating a new SortedMultiVec
56        // For example, under p2sh context the scriptlen can only be
57        // upto 520 bytes.
58        let term: miniscript::decode::Terminal<Pk, Ctx> = Terminal::Multi(k, pks.clone());
59        let ms = Miniscript::from_ast(term)?;
60
61        // This would check all the consensus rules for p2sh/p2wsh and
62        // even tapscript in future
63        Ctx::check_local_validity(&ms)?;
64
65        Ok(Self {
66            k,
67            pks,
68            phantom: PhantomData,
69        })
70    }
71    /// Parse an expression tree into a SortedMultiVec
72    pub fn from_tree(tree: &expression::Tree) -> Result<Self, Error>
73    where
74        Pk: FromStr,
75        <Pk as FromStr>::Err: ToString,
76    {
77        if tree.args.is_empty() {
78            return Err(errstr("no arguments given for sortedmulti"));
79        }
80        let k = expression::parse_num(tree.args[0].name)?;
81        if k > (tree.args.len() - 1) as u32 {
82            return Err(errstr(
83                "higher threshold than there were keys in sortedmulti",
84            ));
85        }
86        let pks: Result<Vec<Pk>, _> = tree.args[1..]
87            .iter()
88            .map(|sub| expression::terminal(sub, Pk::from_str))
89            .collect();
90
91        pks.map(|pks| SortedMultiVec::new(k as usize, pks))?
92    }
93
94    /// This will panic if fpk returns an uncompressed key when
95    /// converting to a Segwit descriptor. To prevent this panic, ensure
96    /// fpk returns an error in this case instead.
97    pub fn translate_pk<T, Q, FuncError>(
98        &self,
99        t: &mut T,
100    ) -> Result<SortedMultiVec<Q, Ctx>, FuncError>
101    where
102        T: Translator<Pk, Q, FuncError>,
103        Q: MiniscriptKey,
104    {
105        let pks: Result<Vec<Q>, _> = self.pks.iter().map(|pk| t.pk(pk)).collect();
106        Ok(SortedMultiVec {
107            k: self.k,
108            pks: pks?,
109            phantom: PhantomData,
110        })
111    }
112}
113
114impl<Pk: MiniscriptKey, Ctx: ScriptContext> ForEachKey<Pk> for SortedMultiVec<Pk, Ctx> {
115    fn for_each_key<'a, F: FnMut(&'a Pk) -> bool>(&'a self, mut pred: F) -> bool
116    where
117        Pk: 'a,
118    {
119        self.pks.iter().all(|key| pred(key))
120    }
121}
122
123impl<Pk: MiniscriptKey, Ctx: ScriptContext> SortedMultiVec<Pk, Ctx> {
124    /// utility function to sanity a sorted multi vec
125    pub fn sanity_check(&self) -> Result<(), Error> {
126        let ms: Miniscript<Pk, Ctx> =
127            Miniscript::from_ast(Terminal::Multi(self.k, self.pks.clone()))
128                .expect("Must typecheck");
129        // '?' for doing From conversion
130        ms.sanity_check()?;
131        Ok(())
132    }
133}
134
135impl<Pk: MiniscriptKey, Ctx: ScriptContext> SortedMultiVec<Pk, Ctx> {
136    /// Create Terminal::Multi containing sorted pubkeys
137    pub fn sorted_node(&self) -> Terminal<Pk, Ctx>
138    where
139        Pk: ToPublicKey,
140    {
141        let mut pks = self.pks.clone();
142        // Sort pubkeys lexicographically according to BIP 67
143        pks.sort_by(|a, b| {
144            a.to_public_key()
145                .inner
146                .serialize()
147                .partial_cmp(&b.to_public_key().inner.serialize())
148                .unwrap()
149        });
150        Terminal::Multi(self.k, pks)
151    }
152
153    /// Encode as a Bitcoin script
154    pub fn encode(&self) -> script::Script
155    where
156        Pk: ToPublicKey,
157    {
158        self.sorted_node()
159            .encode(script::Builder::new())
160            .into_script()
161    }
162
163    /// Attempt to produce a satisfying witness for the
164    /// witness script represented by the parse tree
165    pub fn satisfy<S>(&self, satisfier: S) -> Result<Vec<Vec<u8>>, Error>
166    where
167        Pk: ToPublicKey,
168        S: Satisfier<Pk>,
169    {
170        let ms = Miniscript::from_ast(self.sorted_node()).expect("Multi node typecheck");
171        ms.satisfy(satisfier)
172    }
173
174    /// Size, in bytes of the script-pubkey. If this Miniscript is used outside
175    /// of segwit (e.g. in a bare or P2SH descriptor), this quantity should be
176    /// multiplied by 4 to compute the weight.
177    ///
178    /// In general, it is not recommended to use this function directly, but
179    /// to instead call the corresponding function on a `Descriptor`, which
180    /// will handle the segwit/non-segwit technicalities for you.
181    pub fn script_size(&self) -> usize {
182        script_num_size(self.k)
183            + 1
184            + script_num_size(self.pks.len())
185            + self.pks.iter().map(|pk| Ctx::pk_len(pk)).sum::<usize>()
186    }
187
188    /// Maximum number of witness elements used to satisfy the Miniscript
189    /// fragment, including the witness script itself. Used to estimate
190    /// the weight of the `VarInt` that specifies this number in a serialized
191    /// transaction.
192    ///
193    /// This function may panic on malformed `Miniscript` objects which do
194    /// not correspond to semantically sane Scripts. (Such scripts should be
195    /// rejected at parse time. Any exceptions are bugs.)
196    pub fn max_satisfaction_witness_elements(&self) -> usize {
197        2 + self.k
198    }
199
200    /// Maximum size, in bytes, of a satisfying witness.
201    /// In general, it is not recommended to use this function directly, but
202    /// to instead call the corresponding function on a `Descriptor`, which
203    /// will handle the segwit/non-segwit technicalities for you.
204    ///
205    /// All signatures are assumed to be 73 bytes in size, including the
206    /// length prefix (segwit) or push opcode (pre-segwit) and sighash
207    /// postfix.
208    pub fn max_satisfaction_size(&self) -> usize {
209        1 + 73 * self.k
210    }
211}
212
213impl<Pk: MiniscriptKey, Ctx: ScriptContext> policy::Liftable<Pk> for SortedMultiVec<Pk, Ctx> {
214    fn lift(&self) -> Result<policy::semantic::Policy<Pk>, Error> {
215        let ret = policy::semantic::Policy::Threshold(
216            self.k,
217            self.pks
218                .iter()
219                .map(|k| policy::semantic::Policy::Key(k.clone()))
220                .collect(),
221        );
222        Ok(ret)
223    }
224}
225
226impl<Pk: MiniscriptKey, Ctx: ScriptContext> fmt::Debug for SortedMultiVec<Pk, Ctx> {
227    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
228        fmt::Display::fmt(self, f)
229    }
230}
231
232impl<Pk: MiniscriptKey, Ctx: ScriptContext> fmt::Display for SortedMultiVec<Pk, Ctx> {
233    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
234        write!(f, "sortedmulti({}", self.k)?;
235        for k in &self.pks {
236            write!(f, ",{}", k)?;
237        }
238        f.write_str(")")
239    }
240}
241
242#[cfg(test)]
243mod tests {
244    use bitcoin::secp256k1::PublicKey;
245    use miniscript::context::Legacy;
246
247    use super::*;
248
249    #[test]
250    fn too_many_pubkeys() {
251        // Arbitrary pubic key.
252        let pk = PublicKey::from_str(
253            "02e6642fd69bd211f93f7f1f36ca51a26a5290eb2dd1b0d8279a87bb0d480c8443",
254        )
255        .unwrap();
256
257        let over = 1 + MAX_PUBKEYS_PER_MULTISIG;
258
259        let mut pks = Vec::new();
260        for _ in 0..over {
261            pks.push(pk.clone());
262        }
263
264        let res: Result<SortedMultiVec<PublicKey, Legacy>, Error> = SortedMultiVec::new(0, pks);
265        let error = res.err().expect("constructor should err");
266
267        match error {
268            Error::BadDescriptor(_) => {} // ok
269            other => panic!("unexpected error: {:?}", other),
270        }
271    }
272}
miniscript_debug/descriptor/sortedmulti.rs

miniscript_debug/descriptor/
sortedmulti.rs
