miniscript/descriptor/
sortedmulti.rs

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

miniscript/descriptor/
sortedmulti.rs
