elements_miniscript/descriptor/
sortedmulti.rs

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

elements_miniscript/descriptor/
sortedmulti.rs
