1use core::fmt;
21use core::marker::PhantomData;
22#[cfg(feature = "std")]
23use std::error;
24
25use bitcoin::blockdata::constants::MAX_BLOCK_WEIGHT;
26use bitcoin::hashes::{hash160, ripemd160, sha256, Hash};
27use sync::Arc;
28
29use crate::bitcoin::{LockTime, PackedLockTime, Sequence};
30use crate::miniscript::lex::{Token as Tk, TokenIter};
31use crate::miniscript::limits::MAX_PUBKEYS_PER_MULTISIG;
32use crate::miniscript::types::extra_props::ExtData;
33use crate::miniscript::types::{Property, Type};
34use crate::miniscript::ScriptContext;
35use crate::prelude::*;
36use crate::{bitcoin, hash256, Error, Miniscript, MiniscriptKey, ToPublicKey};
37
38fn return_none<T>(_: usize) -> Option<T> {
39 None
40}
41
42pub trait ParseableKey: Sized + ToPublicKey + private::Sealed {
44 fn from_slice(sl: &[u8]) -> Result<Self, KeyParseError>;
46}
47
48impl ParseableKey for bitcoin::PublicKey {
49 fn from_slice(sl: &[u8]) -> Result<Self, KeyParseError> {
50 bitcoin::PublicKey::from_slice(sl).map_err(KeyParseError::FullKeyParseError)
51 }
52}
53
54impl ParseableKey for bitcoin::secp256k1::XOnlyPublicKey {
55 fn from_slice(sl: &[u8]) -> Result<Self, KeyParseError> {
56 bitcoin::secp256k1::XOnlyPublicKey::from_slice(sl)
57 .map_err(KeyParseError::XonlyKeyParseError)
58 }
59}
60
61#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
63pub enum KeyParseError {
64 FullKeyParseError(bitcoin::util::key::Error),
66 XonlyKeyParseError(bitcoin::secp256k1::Error),
68}
69
70impl fmt::Display for KeyParseError {
71 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
72 match self {
73 KeyParseError::FullKeyParseError(_e) => write!(f, "FullKey Parse Error"),
74 KeyParseError::XonlyKeyParseError(_e) => write!(f, "XonlyKey Parse Error"),
75 }
76 }
77}
78
79#[cfg(feature = "std")]
80impl error::Error for KeyParseError {
81 fn cause(&self) -> Option<&(dyn error::Error + 'static)> {
82 match self {
83 KeyParseError::FullKeyParseError(e) => Some(e),
84 KeyParseError::XonlyKeyParseError(e) => Some(e),
85 }
86 }
87}
88
89mod private {
91
92 pub trait Sealed {}
93
94 impl Sealed for super::bitcoin::PublicKey {}
96 impl Sealed for super::bitcoin::secp256k1::XOnlyPublicKey {}
97}
98
99#[derive(Copy, Clone, Debug)]
100enum NonTerm {
101 Expression,
102 WExpression,
103 Swap,
104 MaybeAndV,
105 Alt,
106 Check,
107 DupIf,
108 Verify,
109 NonZero,
110 ZeroNotEqual,
111 AndV,
112 AndB,
113 Tern,
114 OrB,
115 OrD,
116 OrC,
117 ThreshW { k: usize, n: usize },
118 ThreshE { k: usize, n: usize },
119 EndIf,
121 EndIfNotIf,
123 EndIfElse,
125}
126#[allow(broken_intra_doc_links)]
134#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
135pub enum Terminal<Pk: MiniscriptKey, Ctx: ScriptContext> {
136 True,
138 False,
140 PkK(Pk),
143 PkH(Pk),
145 RawPkH(hash160::Hash),
151 After(PackedLockTime),
154 Older(Sequence),
156 Sha256(Pk::Sha256),
159 Hash256(Pk::Hash256),
161 Ripemd160(Pk::Ripemd160),
163 Hash160(Pk::Hash160),
165 Alt(Arc<Miniscript<Pk, Ctx>>),
168 Swap(Arc<Miniscript<Pk, Ctx>>),
170 Check(Arc<Miniscript<Pk, Ctx>>),
172 DupIf(Arc<Miniscript<Pk, Ctx>>),
174 Verify(Arc<Miniscript<Pk, Ctx>>),
176 NonZero(Arc<Miniscript<Pk, Ctx>>),
178 ZeroNotEqual(Arc<Miniscript<Pk, Ctx>>),
180 AndV(Arc<Miniscript<Pk, Ctx>>, Arc<Miniscript<Pk, Ctx>>),
183 AndB(Arc<Miniscript<Pk, Ctx>>, Arc<Miniscript<Pk, Ctx>>),
185 AndOr(
187 Arc<Miniscript<Pk, Ctx>>,
188 Arc<Miniscript<Pk, Ctx>>,
189 Arc<Miniscript<Pk, Ctx>>,
190 ),
191 OrB(Arc<Miniscript<Pk, Ctx>>, Arc<Miniscript<Pk, Ctx>>),
194 OrD(Arc<Miniscript<Pk, Ctx>>, Arc<Miniscript<Pk, Ctx>>),
196 OrC(Arc<Miniscript<Pk, Ctx>>, Arc<Miniscript<Pk, Ctx>>),
198 OrI(Arc<Miniscript<Pk, Ctx>>, Arc<Miniscript<Pk, Ctx>>),
200 Thresh(usize, Vec<Arc<Miniscript<Pk, Ctx>>>),
203 Multi(usize, Vec<Pk>),
205 MultiA(usize, Vec<Pk>),
207}
208
209macro_rules! match_token {
210 ($tokens:expr => $sub:expr,) => { $sub };
212 ($tokens:expr, $($first:pat $(,$rest:pat)* => $sub:expr,)*) => {
214 match $tokens.next() {
215 $(
216 Some($first) => match_token!($tokens $(,$rest)* => $sub,),
217 )*
218 Some(other) => return Err(Error::Unexpected(other.to_string())),
219 None => return Err(Error::UnexpectedStart),
220 }
221 };
222}
223
224#[derive(Debug)]
226struct TerminalStack<Pk: MiniscriptKey, Ctx: ScriptContext>(Vec<Miniscript<Pk, Ctx>>);
227
228impl<Pk: MiniscriptKey, Ctx: ScriptContext> TerminalStack<Pk, Ctx> {
229 fn pop(&mut self) -> Option<Miniscript<Pk, Ctx>> {
231 self.0.pop()
232 }
233
234 fn reduce0(&mut self, ms: Terminal<Pk, Ctx>) -> Result<(), Error> {
236 let ty = Type::type_check(&ms, return_none)?;
237 let ext = ExtData::type_check(&ms, return_none)?;
238 let ms = Miniscript {
239 node: ms,
240 ty,
241 ext,
242 phantom: PhantomData,
243 };
244 Ctx::check_global_validity(&ms)?;
245 self.0.push(ms);
246 Ok(())
247 }
248
249 fn reduce1<F>(&mut self, wrap: F) -> Result<(), Error>
251 where
252 F: FnOnce(Arc<Miniscript<Pk, Ctx>>) -> Terminal<Pk, Ctx>,
253 {
254 let top = self.pop().unwrap();
255 let wrapped_ms = wrap(Arc::new(top));
256
257 let ty = Type::type_check(&wrapped_ms, return_none)?;
258 let ext = ExtData::type_check(&wrapped_ms, return_none)?;
259 let ms = Miniscript {
260 node: wrapped_ms,
261 ty,
262 ext,
263 phantom: PhantomData,
264 };
265 Ctx::check_global_validity(&ms)?;
266 self.0.push(ms);
267 Ok(())
268 }
269
270 fn reduce2<F>(&mut self, wrap: F) -> Result<(), Error>
272 where
273 F: FnOnce(Arc<Miniscript<Pk, Ctx>>, Arc<Miniscript<Pk, Ctx>>) -> Terminal<Pk, Ctx>,
274 {
275 let left = self.pop().unwrap();
276 let right = self.pop().unwrap();
277
278 let wrapped_ms = wrap(Arc::new(left), Arc::new(right));
279
280 let ty = Type::type_check(&wrapped_ms, return_none)?;
281 let ext = ExtData::type_check(&wrapped_ms, return_none)?;
282 let ms = Miniscript {
283 node: wrapped_ms,
284 ty,
285 ext,
286 phantom: PhantomData,
287 };
288 Ctx::check_global_validity(&ms)?;
289 self.0.push(ms);
290 Ok(())
291 }
292}
293
294#[allow(unreachable_patterns)]
296pub fn parse<Ctx: ScriptContext>(
297 tokens: &mut TokenIter,
298) -> Result<Miniscript<Ctx::Key, Ctx>, Error> {
299 let mut non_term = Vec::with_capacity(tokens.len());
300 let mut term = TerminalStack(Vec::with_capacity(tokens.len()));
301
302 non_term.push(NonTerm::MaybeAndV);
304 non_term.push(NonTerm::Expression);
305 loop {
306 match non_term.pop() {
307 Some(NonTerm::Expression) => {
308 match_token!(
309 tokens,
310 Tk::Bytes33(pk) => {
312 let ret = Ctx::Key::from_slice(pk)
313 .map_err(|e| Error::PubKeyCtxError(e, Ctx::name_str()))?;
314 term.reduce0(Terminal::PkK(ret))?
315 },
316 Tk::Bytes65(pk) => {
317 let ret = Ctx::Key::from_slice(pk)
318 .map_err(|e| Error::PubKeyCtxError(e, Ctx::name_str()))?;
319 term.reduce0(Terminal::PkK(ret))?
320 },
321 Tk::Bytes32(pk) => {
334 let ret = Ctx::Key::from_slice(pk).map_err(|e| Error::PubKeyCtxError(e, Ctx::name_str()))?;
335 term.reduce0(Terminal::PkK(ret))?
336 },
337 Tk::CheckSig => {
339 non_term.push(NonTerm::Check);
340 non_term.push(NonTerm::Expression);
341 },
342 Tk::Verify => match_token!(
344 tokens,
345 Tk::Equal => match_token!(
346 tokens,
347 Tk::Hash20(hash) => match_token!(
348 tokens,
349 Tk::Hash160 => match_token!(
350 tokens,
351 Tk::Dup => {
352 term.reduce0(Terminal::RawPkH(
353 hash160::Hash::from_slice(hash).expect("valid size")
354 ))?
355 },
356 Tk::Verify, Tk::Equal, Tk::Num(32), Tk::Size => {
357 non_term.push(NonTerm::Verify);
358 term.reduce0(Terminal::Hash160(
359 hash160::Hash::from_slice(hash).expect("valid size")
360 ))?
361 },
362 ),
363 Tk::Ripemd160, Tk::Verify, Tk::Equal, Tk::Num(32), Tk::Size => {
364 non_term.push(NonTerm::Verify);
365 term.reduce0(Terminal::Ripemd160(
366 ripemd160::Hash::from_slice(hash).expect("valid size")
367 ))?
368 },
369 ),
370 Tk::Bytes32(hash) => match_token!(
372 tokens,
373 Tk::Sha256, Tk::Verify, Tk::Equal, Tk::Num(32), Tk::Size => {
374 non_term.push(NonTerm::Verify);
375 term.reduce0(Terminal::Sha256(
376 sha256::Hash::from_slice(hash).expect("valid size")
377 ))?
378 },
379 Tk::Hash256, Tk::Verify, Tk::Equal, Tk::Num(32), Tk::Size => {
380 non_term.push(NonTerm::Verify);
381 term.reduce0(Terminal::Hash256(
382 hash256::Hash::from_slice(hash).expect("valid size")
383 ))?
384 },
385 ),
386 Tk::Num(k) => {
387 non_term.push(NonTerm::Verify);
388 non_term.push(NonTerm::ThreshW {
389 k: k as usize,
390 n: 0
391 });
392 },
393 ),
394 x => {
395 tokens.un_next(x);
396 non_term.push(NonTerm::Verify);
397 non_term.push(NonTerm::Expression);
398 },
399 ),
400 Tk::ZeroNotEqual => {
401 non_term.push(NonTerm::ZeroNotEqual);
402 non_term.push(NonTerm::Expression);
403 },
404 Tk::CheckSequenceVerify, Tk::Num(n)
406 => term.reduce0(Terminal::Older(Sequence::from_consensus(n)))?,
407 Tk::CheckLockTimeVerify, Tk::Num(n)
408 => term.reduce0(Terminal::After(LockTime::from_consensus(n).into()))?,
409 Tk::Equal => match_token!(
411 tokens,
412 Tk::Bytes32(hash) => match_token!(
413 tokens,
414 Tk::Sha256,
415 Tk::Verify,
416 Tk::Equal,
417 Tk::Num(32),
418 Tk::Size => term.reduce0(Terminal::Sha256(
419 sha256::Hash::from_slice(hash).expect("valid size")
420 ))?,
421 Tk::Hash256,
422 Tk::Verify,
423 Tk::Equal,
424 Tk::Num(32),
425 Tk::Size => term.reduce0(Terminal::Hash256(
426 hash256::Hash::from_slice(hash).expect("valid size")
427 ))?,
428 ),
429 Tk::Hash20(hash) => match_token!(
430 tokens,
431 Tk::Ripemd160,
432 Tk::Verify,
433 Tk::Equal,
434 Tk::Num(32),
435 Tk::Size => term.reduce0(Terminal::Ripemd160(
436 ripemd160::Hash::from_slice(hash).expect("valid size")
437 ))?,
438 Tk::Hash160,
439 Tk::Verify,
440 Tk::Equal,
441 Tk::Num(32),
442 Tk::Size => term.reduce0(Terminal::Hash160(
443 hash160::Hash::from_slice(hash).expect("valid size")
444 ))?,
445 ),
446 Tk::Num(k) => {
448 non_term.push(NonTerm::ThreshW {
449 k: k as usize,
450 n: 0
451 });
452 },
456 ),
457 Tk::Num(0) => term.reduce0(Terminal::False)?,
459 Tk::Num(1) => term.reduce0(Terminal::True)?,
460 Tk::EndIf => {
461 non_term.push(NonTerm::EndIf);
462 non_term.push(NonTerm::MaybeAndV);
463 non_term.push(NonTerm::Expression);
464 },
465 Tk::BoolAnd => {
467 non_term.push(NonTerm::AndB);
468 non_term.push(NonTerm::Expression);
469 non_term.push(NonTerm::WExpression);
470 },
471 Tk::BoolOr => {
472 non_term.push(NonTerm::OrB);
473 non_term.push(NonTerm::Expression);
474 non_term.push(NonTerm::WExpression);
475 },
476 Tk::CheckMultiSig, Tk::Num(n) => {
478 if n as usize > MAX_PUBKEYS_PER_MULTISIG {
479 return Err(Error::CmsTooManyKeys(n));
480 }
481 let mut keys = Vec::with_capacity(n as usize);
482 for _ in 0..n {
483 match_token!(
484 tokens,
485 Tk::Bytes33(pk) => keys.push(<Ctx::Key>::from_slice(pk)
486 .map_err(|e| Error::PubKeyCtxError(e, Ctx::name_str()))?),
487 Tk::Bytes65(pk) => keys.push(<Ctx::Key>::from_slice(pk)
488 .map_err(|e| Error::PubKeyCtxError(e, Ctx::name_str()))?),
489 );
490 }
491 let k = match_token!(
492 tokens,
493 Tk::Num(k) => k,
494 );
495 keys.reverse();
496 term.reduce0(Terminal::Multi(k as usize, keys))?;
497 },
498 Tk::NumEqual, Tk::Num(k) => {
500 if k > MAX_BLOCK_WEIGHT/32 {
502 return Err(Error::MultiATooManyKeys(MAX_BLOCK_WEIGHT/32))
503 }
504 let mut keys = Vec::with_capacity(k as usize); while tokens.peek() == Some(&Tk::CheckSigAdd) {
506 match_token!(
507 tokens,
508 Tk::CheckSigAdd, Tk::Bytes32(pk) => keys.push(<Ctx::Key>::from_slice(pk)
509 .map_err(|e| Error::PubKeyCtxError(e, Ctx::name_str()))?),
510 );
511 }
512 match_token!(
514 tokens,
515 Tk::CheckSig, Tk::Bytes32(pk) => keys.push(<Ctx::Key>::from_slice(pk)
516 .map_err(|e| Error::PubKeyCtxError(e, Ctx::name_str()))?),
517 );
518 keys.reverse();
519 term.reduce0(Terminal::MultiA(k as usize, keys))?;
520 },
521 );
522 }
523 Some(NonTerm::MaybeAndV) => {
524 if is_and_v(tokens) {
526 non_term.push(NonTerm::AndV);
527 non_term.push(NonTerm::Expression);
528 }
529 }
530 Some(NonTerm::Swap) => {
531 match_token!(
533 tokens,
534 Tk::Swap => {},
535 );
536 term.reduce1(Terminal::Swap)?;
537 }
539 Some(NonTerm::Alt) => {
540 match_token!(
541 tokens,
542 Tk::ToAltStack => {},
543 );
544 term.reduce1(Terminal::Alt)?;
545 }
546 Some(NonTerm::Check) => term.reduce1(Terminal::Check)?,
547 Some(NonTerm::DupIf) => term.reduce1(Terminal::DupIf)?,
548 Some(NonTerm::Verify) => term.reduce1(Terminal::Verify)?,
549 Some(NonTerm::NonZero) => term.reduce1(Terminal::NonZero)?,
550 Some(NonTerm::ZeroNotEqual) => term.reduce1(Terminal::ZeroNotEqual)?,
551 Some(NonTerm::AndV) => {
552 if is_and_v(tokens) {
553 non_term.push(NonTerm::AndV);
554 non_term.push(NonTerm::MaybeAndV);
555 } else {
556 term.reduce2(Terminal::AndV)?
557 }
558 }
559 Some(NonTerm::AndB) => term.reduce2(Terminal::AndB)?,
560 Some(NonTerm::OrB) => term.reduce2(Terminal::OrB)?,
561 Some(NonTerm::OrC) => term.reduce2(Terminal::OrC)?,
562 Some(NonTerm::OrD) => term.reduce2(Terminal::OrD)?,
563 Some(NonTerm::Tern) => {
564 let a = term.pop().unwrap();
565 let b = term.pop().unwrap();
566 let c = term.pop().unwrap();
567 let wrapped_ms = Terminal::AndOr(Arc::new(a), Arc::new(c), Arc::new(b));
568
569 let ty = Type::type_check(&wrapped_ms, return_none)?;
570 let ext = ExtData::type_check(&wrapped_ms, return_none)?;
571
572 term.0.push(Miniscript {
573 node: wrapped_ms,
574 ty,
575 ext,
576 phantom: PhantomData,
577 });
578 }
579 Some(NonTerm::ThreshW { n, k }) => {
580 match_token!(
581 tokens,
582 Tk::Add => {
583 non_term.push(NonTerm::ThreshW { n: n + 1, k });
584 non_term.push(NonTerm::WExpression);
585 },
586 x => {
587 tokens.un_next(x);
588 non_term.push(NonTerm::ThreshE { n: n + 1, k });
589 non_term.push(NonTerm::Expression);
590 },
591 );
592 }
593 Some(NonTerm::ThreshE { n, k }) => {
594 let mut subs = Vec::with_capacity(n);
595 for _ in 0..n {
596 subs.push(Arc::new(term.pop().unwrap()));
597 }
598 term.reduce0(Terminal::Thresh(k, subs))?;
599 }
600 Some(NonTerm::EndIf) => {
601 match_token!(
602 tokens,
603 Tk::Else => {
604 non_term.push(NonTerm::EndIfElse);
605 non_term.push(NonTerm::MaybeAndV);
606 non_term.push(NonTerm::Expression);
607 },
608 Tk::If => match_token!(
609 tokens,
610 Tk::Dup => non_term.push(NonTerm::DupIf),
611 Tk::ZeroNotEqual, Tk::Size
612 => non_term.push(NonTerm::NonZero),
613 ),
614 Tk::NotIf => {
615 non_term.push(NonTerm::EndIfNotIf);
616 },
617 );
618 }
619 Some(NonTerm::EndIfNotIf) => {
620 match_token!(
621 tokens,
622 Tk::IfDup => non_term.push(NonTerm::OrD),
623 x => {
624 tokens.un_next(x);
625 non_term.push(NonTerm::OrC);
626 },
627 );
628 non_term.push(NonTerm::Expression);
629 }
630 Some(NonTerm::EndIfElse) => {
631 match_token!(
632 tokens,
633 Tk::If => {
634 term.reduce2(Terminal::OrI)?;
635 },
636 Tk::NotIf => {
637 non_term.push(NonTerm::Tern);
638 non_term.push(NonTerm::Expression);
639 },
640 );
641 }
642 Some(NonTerm::WExpression) => {
643 match_token!(tokens,
645 Tk::FromAltStack => { non_term.push(NonTerm::Alt);},
646 tok => { tokens.un_next(tok); non_term.push(NonTerm::Swap);},);
647 non_term.push(NonTerm::MaybeAndV);
648 non_term.push(NonTerm::Expression);
649 }
650 None => {
651 break;
653 }
654 }
655 }
656
657 assert_eq!(non_term.len(), 0);
658 assert_eq!(term.0.len(), 1);
659 Ok(term.pop().unwrap())
660}
661
662fn is_and_v(tokens: &mut TokenIter) -> bool {
663 match tokens.peek() {
664 None
665 | Some(&Tk::If)
666 | Some(&Tk::NotIf)
667 | Some(&Tk::Else)
668 | Some(&Tk::ToAltStack)
669 | Some(&Tk::Swap) => false,
670 _ => true,
671 }
672}