miniscript_debug/
lib.rs

1#![recursion_limit = "32768"]
2// Miniscript
3// Written in 2019 by
4//     Andrew Poelstra <apoelstra@wpsoftware.net>
5//
6// To the extent possible under law, the author(s) have dedicated all
7// copyright and related and neighboring rights to this software to
8// the public domain worldwide. This software is distributed without
9// any warranty.
10//
11// You should have received a copy of the CC0 Public Domain Dedication
12// along with this software.
13// If not, see <http://creativecommons.org/publicdomain/zero/1.0/>.
14//
15
16//! Miniscript and Output Descriptors
17//!
18//! # Introduction
19//! ## Bitcoin Script
20//!
21//! In Bitcoin, spending policies are defined and enforced by means of a
22//! stack-based programming language known as Bitcoin Script. While this
23//! language appears to be designed with tractable analysis in mind (e.g.
24//! there are no looping or jumping constructions), in practice this is
25//! extremely difficult. As a result, typical wallet software supports only
26//! a small set of script templates, cannot interoperate with other similar
27//! software, and each wallet contains independently written ad-hoc manually
28//! verified code to handle these templates. Users who require more complex
29//! spending policies, or who want to combine signing infrastructure which
30//! was not explicitly designed to work together, are simply out of luck.
31//!
32//! ## Miniscript
33//!
34//! Miniscript is an alternative to Bitcoin Script which eliminates these
35//! problems. It can be efficiently and simply encoded as Script to ensure
36//! that it works on the Bitcoin blockchain, but its design is very different.
37//! Essentially, a Miniscript is a monotone function (tree of ANDs, ORs and
38//! thresholds) of signature requirements, hash preimage requirements, and
39//! timelocks.
40//!
41//! A [full description of Miniscript is available here](http://bitcoin.sipa.be/miniscript/miniscript.html).
42//!
43//! Miniscript also admits a more human-readable encoding.
44//!
45//! ## Output Descriptors
46//!
47//! While spending policies in Bitcoin are entirely defined by Script; there
48//! are multiple ways of embedding these Scripts in transaction outputs; for
49//! example, P2SH or Segwit v0. These different embeddings are expressed by
50//! *Output Descriptors*, [which are described here](https://github.com/bitcoin/bitcoin/blob/master/doc/descriptors.md)
51//!
52//! # Examples
53//!
54//! ## Deriving an address from a descriptor
55//!
56//! ```rust
57//! use std::str::FromStr;
58//!
59//! let desc = miniscript::Descriptor::<bitcoin::PublicKey>::from_str("\
60//!     sh(wsh(or_d(\
61//!     c:pk_k(020e0338c96a8870479f2396c373cc7696ba124e8635d41b0ea581112b67817261),\
62//!     c:pk_k(0250863ad64a87ae8a2fe83c1af1a8403cb53f53e486d8511dad8a04887e5b2352)\
63//!     )))\
64//!     ").unwrap();
65//!
66//! // Derive the P2SH address
67//! assert_eq!(
68//!     desc.address(bitcoin::Network::Bitcoin).unwrap().to_string(),
69//!     "3CJxbQBfWAe1ZkKiGQNEYrioV73ZwvBWns"
70//! );
71//!
72//! // Check whether the descriptor is safe. This checks whether all spend paths are accessible in
73//! // the Bitcoin network. It may be possible that some of the spend paths require more than 100
74//! // elements in Wsh scripts or they contain a combination of timelock and heightlock.
75//! assert!(desc.sanity_check().is_ok());
76//!
77//! // Estimate the satisfaction cost
78//! assert_eq!(desc.max_satisfaction_weight().unwrap(), 293);
79//! ```
80//!
81
82#![cfg_attr(all(not(feature = "std"), not(test)), no_std)]
83#![cfg_attr(all(test, feature = "unstable"), feature(test))]
84// Coding conventions
85#![deny(unsafe_code)]
86#![deny(non_upper_case_globals)]
87#![deny(non_camel_case_types)]
88#![deny(non_snake_case)]
89#![deny(unused_mut)]
90#![deny(dead_code)]
91#![deny(unused_imports)]
92#![deny(missing_docs)]
93
94#[cfg(target_pointer_width = "16")]
95compile_error!(
96    "rust-miniscript currently only supports architectures with pointers wider than 16 bits"
97);
98
99pub use bitcoin;
100
101#[cfg(not(feature = "std"))]
102#[macro_use]
103extern crate alloc;
104
105#[cfg(not(feature = "std"))]
106extern crate hashbrown;
107
108#[cfg(any(feature = "std", test))]
109extern crate core;
110
111#[cfg(feature = "serde")]
112pub use actual_serde as serde;
113#[cfg(all(test, feature = "unstable"))]
114extern crate test;
115
116#[macro_use]
117mod macros;
118
119#[macro_use]
120mod pub_macros;
121
122pub use pub_macros::*;
123
124pub mod descriptor;
125pub mod expression;
126pub mod interpreter;
127pub mod miniscript;
128pub mod policy;
129pub mod psbt;
130
131#[cfg(test)]
132mod test_utils;
133mod util;
134
135use core::str::FromStr;
136use core::{fmt, hash, str};
137#[cfg(feature = "std")]
138use std::error;
139
140use bitcoin::blockdata::{opcodes, script};
141use bitcoin::hashes::{hash160, ripemd160, sha256, Hash};
142
143pub use crate::descriptor::{DefiniteDescriptorKey, Descriptor, DescriptorPublicKey};
144pub use crate::interpreter::Interpreter;
145pub use crate::miniscript::analyzable::{AnalysisError, ExtParams};
146pub use crate::miniscript::context::{BareCtx, Legacy, ScriptContext, Segwitv0, SigType, Tap};
147pub use crate::miniscript::decode::Terminal;
148pub use crate::miniscript::satisfy::{Preimage32, Satisfier};
149pub use crate::miniscript::{hash256, Miniscript};
150use crate::prelude::*;
151
152///Public key trait which can be converted to Hash type
153pub trait MiniscriptKey: Clone + Eq + Ord + fmt::Debug + fmt::Display + hash::Hash {
154    /// Returns true if the pubkey is uncompressed. Defaults to `false`.
155    fn is_uncompressed(&self) -> bool {
156        false
157    }
158
159    /// Returns true if the pubkey is an x-only pubkey. Defaults to `false`.
160    // This is required to know what in DescriptorPublicKey to know whether the inner
161    // key in allowed in descriptor context
162    fn is_x_only_key(&self) -> bool {
163        false
164    }
165
166    /// The associated [`sha256::Hash`] for this [`MiniscriptKey`],
167    /// used in the hash256 fragment.
168    type Sha256: Clone + Eq + Ord + fmt::Display + fmt::Debug + hash::Hash;
169
170    /// The associated [`hash256::Hash`] for this [`MiniscriptKey`],
171    /// used in the hash256 fragment.
172    type Hash256: Clone + Eq + Ord + fmt::Display + fmt::Debug + hash::Hash;
173    /// The associated [`ripedmd160::Hash`] for this [`MiniscriptKey`] type.
174    /// used in the ripemd160 fragment
175    type Ripemd160: Clone + Eq + Ord + fmt::Display + fmt::Debug + hash::Hash;
176
177    /// The associated [`hash160::Hash`] for this [`MiniscriptKey`] type.
178    /// used in the hash160 fragment
179    type Hash160: Clone + Eq + Ord + fmt::Display + fmt::Debug + hash::Hash;
180}
181
182impl MiniscriptKey for bitcoin::secp256k1::PublicKey {
183    type Sha256 = sha256::Hash;
184    type Hash256 = hash256::Hash;
185    type Ripemd160 = ripemd160::Hash;
186    type Hash160 = hash160::Hash;
187}
188
189impl MiniscriptKey for bitcoin::PublicKey {
190    /// Returns the compressed-ness of the underlying secp256k1 key.
191    fn is_uncompressed(&self) -> bool {
192        !self.compressed
193    }
194
195    type Sha256 = sha256::Hash;
196    type Hash256 = hash256::Hash;
197    type Ripemd160 = ripemd160::Hash;
198    type Hash160 = hash160::Hash;
199}
200
201impl MiniscriptKey for bitcoin::secp256k1::XOnlyPublicKey {
202    type Sha256 = sha256::Hash;
203    type Hash256 = hash256::Hash;
204    type Ripemd160 = ripemd160::Hash;
205    type Hash160 = hash160::Hash;
206
207    fn is_x_only_key(&self) -> bool {
208        true
209    }
210}
211
212impl MiniscriptKey for String {
213    type Sha256 = String; // specify hashes as string
214    type Hash256 = String;
215    type Ripemd160 = String;
216    type Hash160 = String;
217}
218
219/// Trait describing public key types which can be converted to bitcoin pubkeys
220pub trait ToPublicKey: MiniscriptKey {
221    /// Converts an object to a public key
222    fn to_public_key(&self) -> bitcoin::PublicKey;
223
224    /// Convert an object to x-only pubkey
225    fn to_x_only_pubkey(&self) -> bitcoin::secp256k1::XOnlyPublicKey {
226        let pk = self.to_public_key();
227        bitcoin::secp256k1::XOnlyPublicKey::from(pk.inner)
228    }
229
230    /// Obtain the public key hash for this MiniscriptKey
231    /// Expects an argument to specify the signature type.
232    /// This would determine whether to serialize the key as 32 byte x-only pubkey
233    /// or regular public key when computing the hash160
234    fn to_pubkeyhash(&self, sig_type: SigType) -> hash160::Hash {
235        match sig_type {
236            SigType::Ecdsa => hash160::Hash::hash(&self.to_public_key().to_bytes()),
237            SigType::Schnorr => hash160::Hash::hash(&self.to_x_only_pubkey().serialize()),
238        }
239    }
240
241    /// Converts the generic associated [`MiniscriptKey::Sha256`] to [`sha256::Hash`]
242    fn to_sha256(hash: &<Self as MiniscriptKey>::Sha256) -> sha256::Hash;
243
244    /// Converts the generic associated [`MiniscriptKey::Hash256`] to [`hash256::Hash`]
245    fn to_hash256(hash: &<Self as MiniscriptKey>::Hash256) -> hash256::Hash;
246
247    /// Converts the generic associated [`MiniscriptKey::Ripemd160`] to [`ripemd160::Hash`]
248    fn to_ripemd160(hash: &<Self as MiniscriptKey>::Ripemd160) -> ripemd160::Hash;
249
250    /// Converts the generic associated [`MiniscriptKey::Hash160`] to [`hash160::Hash`]
251    fn to_hash160(hash: &<Self as MiniscriptKey>::Hash160) -> hash160::Hash;
252}
253
254impl ToPublicKey for bitcoin::PublicKey {
255    fn to_public_key(&self) -> bitcoin::PublicKey {
256        *self
257    }
258
259    fn to_sha256(hash: &sha256::Hash) -> sha256::Hash {
260        *hash
261    }
262
263    fn to_hash256(hash: &hash256::Hash) -> hash256::Hash {
264        *hash
265    }
266
267    fn to_ripemd160(hash: &ripemd160::Hash) -> ripemd160::Hash {
268        *hash
269    }
270
271    fn to_hash160(hash: &hash160::Hash) -> hash160::Hash {
272        *hash
273    }
274}
275
276impl ToPublicKey for bitcoin::secp256k1::PublicKey {
277    fn to_public_key(&self) -> bitcoin::PublicKey {
278        bitcoin::PublicKey::new(*self)
279    }
280
281    fn to_sha256(hash: &sha256::Hash) -> sha256::Hash {
282        *hash
283    }
284
285    fn to_hash256(hash: &hash256::Hash) -> hash256::Hash {
286        *hash
287    }
288
289    fn to_ripemd160(hash: &ripemd160::Hash) -> ripemd160::Hash {
290        *hash
291    }
292
293    fn to_hash160(hash: &hash160::Hash) -> hash160::Hash {
294        *hash
295    }
296}
297
298impl ToPublicKey for bitcoin::secp256k1::XOnlyPublicKey {
299    fn to_public_key(&self) -> bitcoin::PublicKey {
300        // This code should never be used.
301        // But is implemented for completeness
302        let mut data: Vec<u8> = vec![0x02];
303        data.extend(self.serialize().iter());
304        bitcoin::PublicKey::from_slice(&data)
305            .expect("Failed to construct 33 Publickey from 0x02 appended x-only key")
306    }
307
308    fn to_x_only_pubkey(&self) -> bitcoin::secp256k1::XOnlyPublicKey {
309        *self
310    }
311
312    fn to_sha256(hash: &sha256::Hash) -> sha256::Hash {
313        *hash
314    }
315
316    fn to_hash256(hash: &hash256::Hash) -> hash256::Hash {
317        *hash
318    }
319
320    fn to_ripemd160(hash: &ripemd160::Hash) -> ripemd160::Hash {
321        *hash
322    }
323
324    fn to_hash160(hash: &hash160::Hash) -> hash160::Hash {
325        *hash
326    }
327}
328
329/// Dummy key which de/serializes to the empty string; useful sometimes for testing
330#[derive(Copy, Clone, PartialOrd, Ord, PartialEq, Eq, Debug, Default)]
331pub struct DummyKey;
332
333impl str::FromStr for DummyKey {
334    type Err = &'static str;
335    fn from_str(x: &str) -> Result<DummyKey, &'static str> {
336        if x.is_empty() {
337            Ok(DummyKey)
338        } else {
339            Err("non empty dummy key")
340        }
341    }
342}
343
344impl MiniscriptKey for DummyKey {
345    type Sha256 = DummySha256Hash;
346    type Hash256 = DummyHash256Hash;
347    type Ripemd160 = DummyRipemd160Hash;
348    type Hash160 = DummyHash160Hash;
349}
350
351impl hash::Hash for DummyKey {
352    fn hash<H: hash::Hasher>(&self, state: &mut H) {
353        "DummyKey".hash(state);
354    }
355}
356
357impl fmt::Display for DummyKey {
358    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
359        f.write_str("")
360    }
361}
362
363impl ToPublicKey for DummyKey {
364    fn to_public_key(&self) -> bitcoin::PublicKey {
365        bitcoin::PublicKey::from_str(
366            "0250863ad64a87ae8a2fe83c1af1a8403cb53f53e486d8511dad8a04887e5b2352",
367        )
368        .unwrap()
369    }
370
371    fn to_sha256(_hash: &DummySha256Hash) -> sha256::Hash {
372        sha256::Hash::from_str("50863ad64a87ae8a2fe83c1af1a8403cb53f53e486d8511dad8a04887e5b2352")
373            .unwrap()
374    }
375
376    fn to_hash256(_hash: &DummyHash256Hash) -> hash256::Hash {
377        hash256::Hash::from_str("50863ad64a87ae8a2fe83c1af1a8403cb53f53e486d8511dad8a04887e5b2352")
378            .unwrap()
379    }
380
381    fn to_ripemd160(_: &DummyRipemd160Hash) -> ripemd160::Hash {
382        ripemd160::Hash::from_str("f54a5851e9372b87810a8e60cdd2e7cfd80b6e31").unwrap()
383    }
384
385    fn to_hash160(_: &DummyHash160Hash) -> hash160::Hash {
386        hash160::Hash::from_str("f54a5851e9372b87810a8e60cdd2e7cfd80b6e31").unwrap()
387    }
388}
389
390/// Dummy keyhash which de/serializes to the empty string; useful sometimes for testing
391#[derive(Copy, Clone, PartialOrd, Ord, PartialEq, Eq, Debug, Default)]
392pub struct DummyKeyHash;
393
394impl str::FromStr for DummyKeyHash {
395    type Err = &'static str;
396    fn from_str(x: &str) -> Result<DummyKeyHash, &'static str> {
397        if x.is_empty() {
398            Ok(DummyKeyHash)
399        } else {
400            Err("non empty dummy key")
401        }
402    }
403}
404
405impl fmt::Display for DummyKeyHash {
406    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
407        f.write_str("")
408    }
409}
410
411impl hash::Hash for DummyKeyHash {
412    fn hash<H: hash::Hasher>(&self, state: &mut H) {
413        "DummyKeyHash".hash(state);
414    }
415}
416
417/// Dummy keyhash which de/serializes to the empty string; useful for testing
418#[derive(Copy, Clone, PartialOrd, Ord, PartialEq, Eq, Debug, Default)]
419pub struct DummySha256Hash;
420
421impl str::FromStr for DummySha256Hash {
422    type Err = &'static str;
423    fn from_str(x: &str) -> Result<DummySha256Hash, &'static str> {
424        if x.is_empty() {
425            Ok(DummySha256Hash)
426        } else {
427            Err("non empty dummy hash")
428        }
429    }
430}
431
432impl fmt::Display for DummySha256Hash {
433    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
434        f.write_str("")
435    }
436}
437
438impl hash::Hash for DummySha256Hash {
439    fn hash<H: hash::Hasher>(&self, state: &mut H) {
440        "DummySha256Hash".hash(state);
441    }
442}
443
444/// Dummy keyhash which de/serializes to the empty string; useful for testing
445#[derive(Copy, Clone, PartialOrd, Ord, PartialEq, Eq, Debug, Default)]
446pub struct DummyHash256Hash;
447
448impl str::FromStr for DummyHash256Hash {
449    type Err = &'static str;
450    fn from_str(x: &str) -> Result<DummyHash256Hash, &'static str> {
451        if x.is_empty() {
452            Ok(DummyHash256Hash)
453        } else {
454            Err("non empty dummy hash")
455        }
456    }
457}
458
459/// Dummy keyhash which de/serializes to the empty string; useful for testing
460#[derive(Copy, Clone, PartialOrd, Ord, PartialEq, Eq, Debug, Default)]
461pub struct DummyRipemd160Hash;
462
463impl str::FromStr for DummyRipemd160Hash {
464    type Err = &'static str;
465    fn from_str(x: &str) -> Result<DummyRipemd160Hash, &'static str> {
466        if x.is_empty() {
467            Ok(DummyRipemd160Hash)
468        } else {
469            Err("non empty dummy hash")
470        }
471    }
472}
473
474impl fmt::Display for DummyHash256Hash {
475    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
476        f.write_str("")
477    }
478}
479impl fmt::Display for DummyRipemd160Hash {
480    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
481        f.write_str("")
482    }
483}
484
485impl hash::Hash for DummyHash256Hash {
486    fn hash<H: hash::Hasher>(&self, state: &mut H) {
487        "DummySha256Hash".hash(state);
488    }
489}
490
491impl hash::Hash for DummyRipemd160Hash {
492    fn hash<H: hash::Hasher>(&self, state: &mut H) {
493        "DummyRipemd160Hash".hash(state);
494    }
495}
496
497/// Dummy keyhash which de/serializes to the empty string; useful for testing
498#[derive(Copy, Clone, PartialOrd, Ord, PartialEq, Eq, Debug, Default)]
499pub struct DummyHash160Hash;
500
501impl str::FromStr for DummyHash160Hash {
502    type Err = &'static str;
503    fn from_str(x: &str) -> Result<DummyHash160Hash, &'static str> {
504        if x.is_empty() {
505            Ok(DummyHash160Hash)
506        } else {
507            Err("non empty dummy hash")
508        }
509    }
510}
511
512impl fmt::Display for DummyHash160Hash {
513    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
514        f.write_str("")
515    }
516}
517
518impl hash::Hash for DummyHash160Hash {
519    fn hash<H: hash::Hasher>(&self, state: &mut H) {
520        "DummyHash160Hash".hash(state);
521    }
522}
523/// Describes an object that can translate various keys and hashes from one key to the type
524/// associated with the other key. Used by the [`TranslatePk`] trait to do the actual translations.
525pub trait Translator<P, Q, E>
526where
527    P: MiniscriptKey,
528    Q: MiniscriptKey,
529{
530    /// Translates public keys P -> Q.
531    fn pk(&mut self, pk: &P) -> Result<Q, E>;
532
533    /// Provides the translation from P::Sha256 -> Q::Sha256
534    fn sha256(&mut self, sha256: &P::Sha256) -> Result<Q::Sha256, E>;
535
536    /// Provides the translation from P::Hash256 -> Q::Hash256
537    fn hash256(&mut self, hash256: &P::Hash256) -> Result<Q::Hash256, E>;
538
539    /// Translates ripemd160 hashes from P::Ripemd160 -> Q::Ripemd160
540    fn ripemd160(&mut self, ripemd160: &P::Ripemd160) -> Result<Q::Ripemd160, E>;
541
542    /// Translates hash160 hashes from P::Hash160 -> Q::Hash160
543    fn hash160(&mut self, hash160: &P::Hash160) -> Result<Q::Hash160, E>;
544}
545
546/// Converts a descriptor using abstract keys to one using specific keys. Uses translator `t` to do
547/// the actual translation function calls.
548pub trait TranslatePk<P, Q>
549where
550    P: MiniscriptKey,
551    Q: MiniscriptKey,
552{
553    /// The associated output type. This must be `Self<Q>`.
554    type Output;
555
556    /// Translates a struct from one generic to another where the translations
557    /// for Pk are provided by the given [`Translator`].
558    fn translate_pk<T, E>(&self, translator: &mut T) -> Result<Self::Output, E>
559    where
560        T: Translator<P, Q, E>;
561}
562
563/// Either a key or keyhash, but both contain Pk
564// pub struct ForEach<'a, Pk: MiniscriptKey>(&'a Pk);
565
566// impl<'a, Pk: MiniscriptKey<Hash = Pk>> ForEach<'a, Pk> {
567//     /// Convenience method to avoid distinguishing between keys and hashes when these are the same type
568//     pub fn as_key(&self) -> &'a Pk {
569//         self.0
570//     }
571// }
572
573/// Trait describing the ability to iterate over every key
574pub trait ForEachKey<Pk: MiniscriptKey> {
575    /// Run a predicate on every key in the descriptor, returning whether
576    /// the predicate returned true for every key
577    fn for_each_key<'a, F: FnMut(&'a Pk) -> bool>(&'a self, pred: F) -> bool
578    where
579        Pk: 'a;
580
581    /// Run a predicate on every key in the descriptor, returning whether
582    /// the predicate returned true for any key
583    fn for_any_key<'a, F: FnMut(&'a Pk) -> bool>(&'a self, mut pred: F) -> bool
584    where
585        Pk: 'a,
586    {
587        !self.for_each_key(|key| !pred(key))
588    }
589}
590
591/// Miniscript
592
593#[derive(Debug, PartialEq)]
594pub enum Error {
595    /// Opcode appeared which is not part of the script subset
596    InvalidOpcode(opcodes::All),
597    /// Some opcode occurred followed by `OP_VERIFY` when it had
598    /// a `VERIFY` version that should have been used instead
599    NonMinimalVerify(String),
600    /// Push was illegal in some context
601    InvalidPush(Vec<u8>),
602    /// rust-bitcoin script error
603    Script(script::Error),
604    /// rust-bitcoin address error
605    AddrError(bitcoin::util::address::Error),
606    /// A `CHECKMULTISIG` opcode was preceded by a number > 20
607    CmsTooManyKeys(u32),
608    /// A tapscript multi_a cannot support more than MAX_BLOCK_WEIGHT/32 keys
609    MultiATooManyKeys(u32),
610    /// Encountered unprintable character in descriptor
611    Unprintable(u8),
612    /// expected character while parsing descriptor; didn't find one
613    ExpectedChar(char),
614    /// While parsing backward, hit beginning of script
615    UnexpectedStart,
616    /// Got something we were not expecting
617    Unexpected(String),
618    /// Name of a fragment contained `:` multiple times
619    MultiColon(String),
620    /// Name of a fragment contained `@` multiple times
621    MultiAt(String),
622    /// Name of a fragment contained `@` but we were not parsing an OR
623    AtOutsideOr(String),
624    /// Encountered a `l:0` which is syntactically equal to `u:0` except stupid
625    LikelyFalse,
626    /// Encountered a wrapping character that we don't recognize
627    UnknownWrapper(char),
628    /// Parsed a miniscript and the result was not of type T
629    NonTopLevel(String),
630    /// Parsed a miniscript but there were more script opcodes after it
631    Trailing(String),
632    /// Failed to parse a push as a public key
633    BadPubkey(bitcoin::util::key::Error),
634    /// Could not satisfy a script (fragment) because of a missing hash preimage
635    MissingHash(sha256::Hash),
636    /// Could not satisfy a script (fragment) because of a missing signature
637    MissingSig(bitcoin::PublicKey),
638    /// Could not satisfy, relative locktime not met
639    RelativeLocktimeNotMet(u32),
640    /// Could not satisfy, absolute locktime not met
641    AbsoluteLocktimeNotMet(u32),
642    /// General failure to satisfy
643    CouldNotSatisfy,
644    /// Typechecking failed
645    TypeCheck(String),
646    /// General error in creating descriptor
647    BadDescriptor(String),
648    /// Forward-secp related errors
649    Secp(bitcoin::secp256k1::Error),
650    #[cfg(feature = "compiler")]
651    /// Compiler related errors
652    CompilerError(crate::policy::compiler::CompilerError),
653    /// Errors related to policy
654    PolicyError(policy::concrete::PolicyError),
655    /// Errors related to lifting
656    LiftError(policy::LiftError),
657    /// Forward script context related errors
658    ContextError(miniscript::context::ScriptContextError),
659    /// Recursion depth exceeded when parsing policy/miniscript from string
660    MaxRecursiveDepthExceeded,
661    /// Script size too large
662    ScriptSizeTooLarge,
663    /// Anything but c:pk(key) (P2PK), c:pk_h(key) (P2PKH), and thresh_m(k,...)
664    /// up to n=3 is invalid by standardness (bare)
665    NonStandardBareScript,
666    /// Analysis Error
667    AnalysisError(miniscript::analyzable::AnalysisError),
668    /// Miniscript is equivalent to false. No possible satisfaction
669    ImpossibleSatisfaction,
670    /// Bare descriptors don't have any addresses
671    BareDescriptorAddr,
672    /// PubKey invalid under current context
673    PubKeyCtxError(miniscript::decode::KeyParseError, &'static str),
674    /// Attempted to call function that requires PreComputed taproot info
675    TaprootSpendInfoUnavialable,
676    /// No script code for Tr descriptors
677    TrNoScriptCode,
678    /// No explicit script for Tr descriptors
679    TrNoExplicitScript,
680}
681
682// https://github.com/sipa/miniscript/pull/5 for discussion on this number
683const MAX_RECURSION_DEPTH: u32 = 402;
684// https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki
685const MAX_SCRIPT_SIZE: u32 = 10000;
686
687impl fmt::Display for Error {
688    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
689        match *self {
690            Error::InvalidOpcode(op) => write!(f, "invalid opcode {}", op),
691            Error::NonMinimalVerify(ref tok) => write!(f, "{} VERIFY", tok),
692            Error::InvalidPush(ref push) => write!(f, "invalid push {:?}", push), // TODO hexify this
693            Error::Script(ref e) => fmt::Display::fmt(e, f),
694            Error::AddrError(ref e) => fmt::Display::fmt(e, f),
695            Error::CmsTooManyKeys(n) => write!(f, "checkmultisig with {} keys", n),
696            Error::Unprintable(x) => write!(f, "unprintable character 0x{:02x}", x),
697            Error::ExpectedChar(c) => write!(f, "expected {}", c),
698            Error::UnexpectedStart => f.write_str("unexpected start of script"),
699            Error::Unexpected(ref s) => write!(f, "unexpected «{}»", s),
700            Error::MultiColon(ref s) => write!(f, "«{}» has multiple instances of «:»", s),
701            Error::MultiAt(ref s) => write!(f, "«{}» has multiple instances of «@»", s),
702            Error::AtOutsideOr(ref s) => write!(f, "«{}» contains «@» in non-or() context", s),
703            Error::LikelyFalse => write!(f, "0 is not very likely (use «u:0»)"),
704            Error::UnknownWrapper(ch) => write!(f, "unknown wrapper «{}:»", ch),
705            Error::NonTopLevel(ref s) => write!(f, "non-T miniscript: {}", s),
706            Error::Trailing(ref s) => write!(f, "trailing tokens: {}", s),
707            Error::MissingHash(ref h) => write!(f, "missing preimage of hash {}", h),
708            Error::MissingSig(ref pk) => write!(f, "missing signature for key {:?}", pk),
709            Error::RelativeLocktimeNotMet(n) => {
710                write!(f, "required relative locktime CSV of {} blocks, not met", n)
711            }
712            Error::AbsoluteLocktimeNotMet(n) => write!(
713                f,
714                "required absolute locktime CLTV of {} blocks, not met",
715                n
716            ),
717            Error::CouldNotSatisfy => f.write_str("could not satisfy"),
718            Error::BadPubkey(ref e) => fmt::Display::fmt(e, f),
719            Error::TypeCheck(ref e) => write!(f, "typecheck: {}", e),
720            Error::BadDescriptor(ref e) => write!(f, "Invalid descriptor: {}", e),
721            Error::Secp(ref e) => fmt::Display::fmt(e, f),
722            Error::ContextError(ref e) => fmt::Display::fmt(e, f),
723            #[cfg(feature = "compiler")]
724            Error::CompilerError(ref e) => fmt::Display::fmt(e, f),
725            Error::PolicyError(ref e) => fmt::Display::fmt(e, f),
726            Error::LiftError(ref e) => fmt::Display::fmt(e, f),
727            Error::MaxRecursiveDepthExceeded => write!(
728                f,
729                "Recursive depth over {} not permitted",
730                MAX_RECURSION_DEPTH
731            ),
732            Error::ScriptSizeTooLarge => write!(
733                f,
734                "Standardness rules imply bitcoin than {} bytes",
735                MAX_SCRIPT_SIZE
736            ),
737            Error::NonStandardBareScript => write!(
738                f,
739                "Anything but c:pk(key) (P2PK), c:pk_h(key) (P2PKH), and thresh_m(k,...) \
740                up to n=3 is invalid by standardness (bare).
741                "
742            ),
743            Error::AnalysisError(ref e) => e.fmt(f),
744            Error::ImpossibleSatisfaction => write!(f, "Impossible to satisfy Miniscript"),
745            Error::BareDescriptorAddr => write!(f, "Bare descriptors don't have address"),
746            Error::PubKeyCtxError(ref pk, ref ctx) => {
747                write!(f, "Pubkey error: {} under {} scriptcontext", pk, ctx)
748            }
749            Error::MultiATooManyKeys(k) => write!(f, "MultiA too many keys {}", k),
750            Error::TaprootSpendInfoUnavialable => write!(f, "Taproot Spend Info not computed."),
751            Error::TrNoScriptCode => write!(f, "No script code for Tr descriptors"),
752            Error::TrNoExplicitScript => write!(f, "No script code for Tr descriptors"),
753        }
754    }
755}
756
757#[cfg(feature = "std")]
758impl error::Error for Error {
759    fn cause(&self) -> Option<&dyn error::Error> {
760        use self::Error::*;
761
762        match self {
763            InvalidOpcode(_)
764            | NonMinimalVerify(_)
765            | InvalidPush(_)
766            | CmsTooManyKeys(_)
767            | MultiATooManyKeys(_)
768            | Unprintable(_)
769            | ExpectedChar(_)
770            | UnexpectedStart
771            | Unexpected(_)
772            | MultiColon(_)
773            | MultiAt(_)
774            | AtOutsideOr(_)
775            | LikelyFalse
776            | UnknownWrapper(_)
777            | NonTopLevel(_)
778            | Trailing(_)
779            | MissingHash(_)
780            | MissingSig(_)
781            | RelativeLocktimeNotMet(_)
782            | AbsoluteLocktimeNotMet(_)
783            | CouldNotSatisfy
784            | TypeCheck(_)
785            | BadDescriptor(_)
786            | MaxRecursiveDepthExceeded
787            | ScriptSizeTooLarge
788            | NonStandardBareScript
789            | ImpossibleSatisfaction
790            | BareDescriptorAddr
791            | TaprootSpendInfoUnavialable
792            | TrNoScriptCode
793            | TrNoExplicitScript => None,
794            Script(e) => Some(e),
795            AddrError(e) => Some(e),
796            BadPubkey(e) => Some(e),
797            Secp(e) => Some(e),
798            #[cfg(feature = "compiler")]
799            CompilerError(e) => Some(e),
800            PolicyError(e) => Some(e),
801            LiftError(e) => Some(e),
802            ContextError(e) => Some(e),
803            AnalysisError(e) => Some(e),
804            PubKeyCtxError(e, _) => Some(e),
805        }
806    }
807}
808
809#[doc(hidden)]
810impl<Pk, Ctx> From<miniscript::types::Error<Pk, Ctx>> for Error
811where
812    Pk: MiniscriptKey,
813    Ctx: ScriptContext,
814{
815    fn from(e: miniscript::types::Error<Pk, Ctx>) -> Error {
816        Error::TypeCheck(e.to_string())
817    }
818}
819
820#[doc(hidden)]
821impl From<policy::LiftError> for Error {
822    fn from(e: policy::LiftError) -> Error {
823        Error::LiftError(e)
824    }
825}
826
827#[doc(hidden)]
828impl From<miniscript::context::ScriptContextError> for Error {
829    fn from(e: miniscript::context::ScriptContextError) -> Error {
830        Error::ContextError(e)
831    }
832}
833
834#[doc(hidden)]
835impl From<miniscript::analyzable::AnalysisError> for Error {
836    fn from(e: miniscript::analyzable::AnalysisError) -> Error {
837        Error::AnalysisError(e)
838    }
839}
840
841#[doc(hidden)]
842impl From<bitcoin::secp256k1::Error> for Error {
843    fn from(e: bitcoin::secp256k1::Error) -> Error {
844        Error::Secp(e)
845    }
846}
847
848#[doc(hidden)]
849impl From<bitcoin::util::address::Error> for Error {
850    fn from(e: bitcoin::util::address::Error) -> Error {
851        Error::AddrError(e)
852    }
853}
854
855#[doc(hidden)]
856#[cfg(feature = "compiler")]
857impl From<crate::policy::compiler::CompilerError> for Error {
858    fn from(e: crate::policy::compiler::CompilerError) -> Error {
859        Error::CompilerError(e)
860    }
861}
862
863#[doc(hidden)]
864impl From<policy::concrete::PolicyError> for Error {
865    fn from(e: policy::concrete::PolicyError) -> Error {
866        Error::PolicyError(e)
867    }
868}
869
870fn errstr(s: &str) -> Error {
871    Error::Unexpected(s.to_owned())
872}
873
874/// The size of an encoding of a number in Script
875pub fn script_num_size(n: usize) -> usize {
876    match n {
877        n if n <= 0x10 => 1,      // OP_n
878        n if n < 0x80 => 2,       // OP_PUSH1 <n>
879        n if n < 0x8000 => 3,     // OP_PUSH2 <n>
880        n if n < 0x800000 => 4,   // OP_PUSH3 <n>
881        n if n < 0x80000000 => 5, // OP_PUSH4 <n>
882        _ => 6,                   // OP_PUSH5 <n>
883    }
884}
885
886/// Returns the size of the smallest push opcode used to push a given number of bytes onto the stack
887///
888/// For sizes ≤ 75, there are dedicated single-byte opcodes, so the push size is one. Otherwise,
889/// if the size can fit into 1, 2 or 4 bytes, we use the `PUSHDATA{1,2,4}` opcode respectively,
890/// followed by the actual size encoded in that many bytes.
891fn push_opcode_size(script_size: usize) -> usize {
892    if script_size < 76 {
893        1
894    } else if script_size < 0x100 {
895        2
896    } else if script_size < 0x10000 {
897        3
898    } else {
899        5
900    }
901}
902
903/// Helper function used by tests
904#[cfg(test)]
905fn hex_script(s: &str) -> bitcoin::Script {
906    let v: Vec<u8> = bitcoin::hashes::hex::FromHex::from_hex(s).unwrap();
907    bitcoin::Script::from(v)
908}
909
910#[cfg(test)]
911mod tests {
912    use super::*;
913
914    #[test]
915    fn regression_bitcoin_key_hash() {
916        use bitcoin::PublicKey;
917
918        // Uncompressed key.
919        let pk = PublicKey::from_str(
920            "042e58afe51f9ed8ad3cc7897f634d881fdbe49a81564629ded8156bebd2ffd1af191923a2964c177f5b5923ae500fca49e99492d534aa3759d6b25a8bc971b133"
921        ).unwrap();
922
923        let want = hash160::Hash::from_str("ac2e7daf42d2c97418fd9f78af2de552bb9c6a7a").unwrap();
924        let got = pk.to_pubkeyhash(SigType::Ecdsa);
925        assert_eq!(got, want)
926    }
927
928    #[test]
929    fn regression_secp256k1_key_hash() {
930        use bitcoin::secp256k1::PublicKey;
931
932        // Compressed key.
933        let pk = PublicKey::from_str(
934            "032e58afe51f9ed8ad3cc7897f634d881fdbe49a81564629ded8156bebd2ffd1af",
935        )
936        .unwrap();
937
938        let want = hash160::Hash::from_str("9511aa27ef39bbfa4e4f3dd15f4d66ea57f475b4").unwrap();
939        let got = pk.to_pubkeyhash(SigType::Ecdsa);
940        assert_eq!(got, want)
941    }
942
943    #[test]
944    fn regression_xonly_key_hash() {
945        use bitcoin::secp256k1::XOnlyPublicKey;
946
947        let pk = XOnlyPublicKey::from_str(
948            "cc8a4bc64d897bddc5fbc2f670f7a8ba0b386779106cf1223c6fc5d7cd6fc115",
949        )
950        .unwrap();
951
952        let want = hash160::Hash::from_str("eb8ac65f971ae688a94aeabf223506865e7e08f2").unwrap();
953        let got = pk.to_pubkeyhash(SigType::Schnorr);
954        assert_eq!(got, want)
955    }
956}
957
958mod prelude {
959    // Mutex implementation from LDK
960    // https://github.com/lightningdevkit/rust-lightning/blob/9bdce47f0e0516e37c89c09f1975dfc06b5870b1/lightning-invoice/src/sync.rs
961    #[cfg(all(not(feature = "std"), not(test)))]
962    mod mutex {
963        use core::cell::{RefCell, RefMut};
964        use core::ops::{Deref, DerefMut};
965
966        pub type LockResult<Guard> = Result<Guard, ()>;
967
968        /// `Mutex` is not a real mutex as it cannot be used in a multi-threaded
969        /// context. `Mutex` is a dummy implementation of [`std::sync::Mutex`]
970        /// for `no_std` environments.
971        pub struct Mutex<T: ?Sized> {
972            inner: RefCell<T>,
973        }
974
975        #[must_use = "if unused the Mutex will immediately unlock"]
976        pub struct MutexGuard<'a, T: ?Sized + 'a> {
977            lock: RefMut<'a, T>,
978        }
979
980        impl<T: ?Sized> Deref for MutexGuard<'_, T> {
981            type Target = T;
982
983            fn deref(&self) -> &T {
984                &self.lock.deref()
985            }
986        }
987
988        impl<T: ?Sized> DerefMut for MutexGuard<'_, T> {
989            fn deref_mut(&mut self) -> &mut T {
990                self.lock.deref_mut()
991            }
992        }
993
994        impl<T> Mutex<T> {
995            pub fn new(inner: T) -> Mutex<T> {
996                Mutex {
997                    inner: RefCell::new(inner),
998                }
999            }
1000
1001            pub fn lock<'a>(&'a self) -> LockResult<MutexGuard<'a, T>> {
1002                Ok(MutexGuard {
1003                    lock: self.inner.borrow_mut(),
1004                })
1005            }
1006        }
1007    }
1008
1009    #[cfg(all(not(feature = "std"), not(test)))]
1010    pub use alloc::{
1011        borrow::{Borrow, Cow, ToOwned},
1012        boxed::Box,
1013        collections::{vec_deque::VecDeque, BTreeMap, BTreeSet, BinaryHeap},
1014        rc, slice,
1015        string::{String, ToString},
1016        sync,
1017        vec::Vec,
1018    };
1019    #[cfg(any(feature = "std", test))]
1020    pub use std::{
1021        borrow::{Borrow, Cow, ToOwned},
1022        boxed::Box,
1023        collections::{vec_deque::VecDeque, BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet},
1024        rc, slice,
1025        string::{String, ToString},
1026        sync,
1027        sync::Mutex,
1028        vec::Vec,
1029    };
1030
1031    #[cfg(all(not(feature = "std"), not(test)))]
1032    pub use hashbrown::{HashMap, HashSet};
1033
1034    #[cfg(all(not(feature = "std"), not(test)))]
1035    pub use self::mutex::Mutex;
1036}