use core::{cmp, fmt, i64, mem};
use bitcoin::hashes::hash160;
use bitcoin::key::XOnlyPublicKey;
use bitcoin::taproot::{ControlBlock, LeafVersion, TapLeafHash, TapNodeHash};
use bitcoin::{absolute, ScriptBuf, Sequence};
use sync::Arc;
use super::context::SigType;
use crate::plan::AssetProvider;
use crate::prelude::*;
use crate::util::witness_size;
use crate::{AbsLockTime, Miniscript, MiniscriptKey, ScriptContext, Terminal, ToPublicKey};
pub type Preimage32 = [u8; 32];
pub trait Satisfier<Pk: MiniscriptKey + ToPublicKey> {
fn lookup_ecdsa_sig(&self, _: &Pk) -> Option<bitcoin::ecdsa::Signature> { None }
fn lookup_tap_key_spend_sig(&self) -> Option<bitcoin::taproot::Signature> { None }
fn lookup_tap_leaf_script_sig(
&self,
_: &Pk,
_: &TapLeafHash,
) -> Option<bitcoin::taproot::Signature> {
None
}
fn lookup_tap_control_block_map(
&self,
) -> Option<&BTreeMap<ControlBlock, (bitcoin::ScriptBuf, LeafVersion)>> {
None
}
fn lookup_raw_pkh_pk(&self, _: &hash160::Hash) -> Option<bitcoin::PublicKey> { None }
fn lookup_raw_pkh_x_only_pk(&self, _: &hash160::Hash) -> Option<XOnlyPublicKey> { None }
fn lookup_raw_pkh_ecdsa_sig(
&self,
_: &hash160::Hash,
) -> Option<(bitcoin::PublicKey, bitcoin::ecdsa::Signature)> {
None
}
fn lookup_raw_pkh_tap_leaf_script_sig(
&self,
_: &(hash160::Hash, TapLeafHash),
) -> Option<(XOnlyPublicKey, bitcoin::taproot::Signature)> {
None
}
fn lookup_sha256(&self, _: &Pk::Sha256) -> Option<Preimage32> { None }
fn lookup_hash256(&self, _: &Pk::Hash256) -> Option<Preimage32> { None }
fn lookup_ripemd160(&self, _: &Pk::Ripemd160) -> Option<Preimage32> { None }
fn lookup_hash160(&self, _: &Pk::Hash160) -> Option<Preimage32> { None }
fn check_older(&self, _: Sequence) -> bool { false }
fn check_after(&self, _: absolute::LockTime) -> bool { false }
}
impl<Pk: MiniscriptKey + ToPublicKey> Satisfier<Pk> for () {}
impl<Pk: MiniscriptKey + ToPublicKey> Satisfier<Pk> for Sequence {
fn check_older(&self, n: Sequence) -> bool {
if !self.is_relative_lock_time() {
return false;
}
const SEQUENCE_LOCKTIME_MASK: u32 = 0x0000ffff;
const SEQUENCE_LOCKTIME_TYPE_FLAG: u32 = 0x00400000;
let mask = SEQUENCE_LOCKTIME_MASK | SEQUENCE_LOCKTIME_TYPE_FLAG;
let masked_n = n.to_consensus_u32() & mask;
let masked_seq = self.to_consensus_u32() & mask;
if masked_n < SEQUENCE_LOCKTIME_TYPE_FLAG && masked_seq >= SEQUENCE_LOCKTIME_TYPE_FLAG {
false
} else {
masked_n <= masked_seq
}
}
}
impl<Pk: MiniscriptKey + ToPublicKey> Satisfier<Pk> for absolute::LockTime {
fn check_after(&self, n: absolute::LockTime) -> bool {
use absolute::LockTime::*;
match (n, *self) {
(Blocks(n), Blocks(lock_time)) => n <= lock_time,
(Seconds(n), Seconds(lock_time)) => n <= lock_time,
_ => false, }
}
}
macro_rules! impl_satisfier_for_map_key_to_ecdsa_sig {
($(#[$($attr:meta)*])* impl Satisfier<Pk> for $map:ident<$key:ty, $val:ty>) => {
$(#[$($attr)*])*
impl<Pk: MiniscriptKey + ToPublicKey> Satisfier<Pk>
for $map<Pk, bitcoin::ecdsa::Signature>
{
fn lookup_ecdsa_sig(&self, key: &Pk) -> Option<bitcoin::ecdsa::Signature> {
self.get(key).copied()
}
}
};
}
impl_satisfier_for_map_key_to_ecdsa_sig! {
impl Satisfier<Pk> for BTreeMap<Pk, bitcoin::ecdsa::Signature>
}
impl_satisfier_for_map_key_to_ecdsa_sig! {
#[cfg(feature = "std")]
impl Satisfier<Pk> for HashMap<Pk, bitcoin::ecdsa::Signature>
}
macro_rules! impl_satisfier_for_map_key_hash_to_taproot_sig {
($(#[$($attr:meta)*])* impl Satisfier<Pk> for $map:ident<$key:ty, $val:ty>) => {
$(#[$($attr)*])*
impl<Pk: MiniscriptKey + ToPublicKey> Satisfier<Pk>
for $map<(Pk, TapLeafHash), bitcoin::taproot::Signature>
{
fn lookup_tap_leaf_script_sig(
&self,
key: &Pk,
h: &TapLeafHash,
) -> Option<bitcoin::taproot::Signature> {
self.get(&(key.clone(), *h)).copied()
}
}
};
}
impl_satisfier_for_map_key_hash_to_taproot_sig! {
impl Satisfier<Pk> for BTreeMap<(Pk, TapLeafHash), bitcoin::taproot::Signature>
}
impl_satisfier_for_map_key_hash_to_taproot_sig! {
#[cfg(feature = "std")]
impl Satisfier<Pk> for HashMap<(Pk, TapLeafHash), bitcoin::taproot::Signature>
}
macro_rules! impl_satisfier_for_map_hash_to_key_ecdsa_sig {
($(#[$($attr:meta)*])* impl Satisfier<Pk> for $map:ident<$key:ty, $val:ty>) => {
$(#[$($attr)*])*
impl<Pk: MiniscriptKey + ToPublicKey> Satisfier<Pk>
for $map<hash160::Hash, (Pk, bitcoin::ecdsa::Signature)>
where
Pk: MiniscriptKey + ToPublicKey,
{
fn lookup_ecdsa_sig(&self, key: &Pk) -> Option<bitcoin::ecdsa::Signature> {
self.get(&key.to_pubkeyhash(SigType::Ecdsa)).map(|x| x.1)
}
fn lookup_raw_pkh_pk(&self, pk_hash: &hash160::Hash) -> Option<bitcoin::PublicKey> {
self.get(pk_hash).map(|x| x.0.to_public_key())
}
fn lookup_raw_pkh_ecdsa_sig(
&self,
pk_hash: &hash160::Hash,
) -> Option<(bitcoin::PublicKey, bitcoin::ecdsa::Signature)> {
self.get(pk_hash)
.map(|&(ref pk, sig)| (pk.to_public_key(), sig))
}
}
};
}
impl_satisfier_for_map_hash_to_key_ecdsa_sig! {
impl Satisfier<Pk> for BTreeMap<hash160::Hash, (Pk, bitcoin::ecdsa::Signature)>
}
impl_satisfier_for_map_hash_to_key_ecdsa_sig! {
#[cfg(feature = "std")]
impl Satisfier<Pk> for HashMap<hash160::Hash, (Pk, bitcoin::ecdsa::Signature)>
}
macro_rules! impl_satisfier_for_map_hash_tapleafhash_to_key_taproot_sig {
($(#[$($attr:meta)*])* impl Satisfier<Pk> for $map:ident<$key:ty, $val:ty>) => {
$(#[$($attr)*])*
impl<Pk: MiniscriptKey + ToPublicKey> Satisfier<Pk>
for $map<(hash160::Hash, TapLeafHash), (Pk, bitcoin::taproot::Signature)>
where
Pk: MiniscriptKey + ToPublicKey,
{
fn lookup_tap_leaf_script_sig(
&self,
key: &Pk,
h: &TapLeafHash,
) -> Option<bitcoin::taproot::Signature> {
self.get(&(key.to_pubkeyhash(SigType::Schnorr), *h))
.map(|x| x.1)
}
fn lookup_raw_pkh_tap_leaf_script_sig(
&self,
pk_hash: &(hash160::Hash, TapLeafHash),
) -> Option<(XOnlyPublicKey, bitcoin::taproot::Signature)> {
self.get(pk_hash)
.map(|&(ref pk, sig)| (pk.to_x_only_pubkey(), sig))
}
}
};
}
impl_satisfier_for_map_hash_tapleafhash_to_key_taproot_sig! {
impl Satisfier<Pk> for BTreeMap<(hash160::Hash, TapLeafHash), (Pk, bitcoin::taproot::Signature)>
}
impl_satisfier_for_map_hash_tapleafhash_to_key_taproot_sig! {
#[cfg(feature = "std")]
impl Satisfier<Pk> for HashMap<(hash160::Hash, TapLeafHash), (Pk, bitcoin::taproot::Signature)>
}
impl<'a, Pk: MiniscriptKey + ToPublicKey, S: Satisfier<Pk>> Satisfier<Pk> for &'a S {
fn lookup_ecdsa_sig(&self, p: &Pk) -> Option<bitcoin::ecdsa::Signature> {
(**self).lookup_ecdsa_sig(p)
}
fn lookup_tap_leaf_script_sig(
&self,
p: &Pk,
h: &TapLeafHash,
) -> Option<bitcoin::taproot::Signature> {
(**self).lookup_tap_leaf_script_sig(p, h)
}
fn lookup_raw_pkh_pk(&self, pkh: &hash160::Hash) -> Option<bitcoin::PublicKey> {
(**self).lookup_raw_pkh_pk(pkh)
}
fn lookup_raw_pkh_x_only_pk(&self, pkh: &hash160::Hash) -> Option<XOnlyPublicKey> {
(**self).lookup_raw_pkh_x_only_pk(pkh)
}
fn lookup_raw_pkh_ecdsa_sig(
&self,
pkh: &hash160::Hash,
) -> Option<(bitcoin::PublicKey, bitcoin::ecdsa::Signature)> {
(**self).lookup_raw_pkh_ecdsa_sig(pkh)
}
fn lookup_tap_key_spend_sig(&self) -> Option<bitcoin::taproot::Signature> {
(**self).lookup_tap_key_spend_sig()
}
fn lookup_raw_pkh_tap_leaf_script_sig(
&self,
pkh: &(hash160::Hash, TapLeafHash),
) -> Option<(XOnlyPublicKey, bitcoin::taproot::Signature)> {
(**self).lookup_raw_pkh_tap_leaf_script_sig(pkh)
}
fn lookup_tap_control_block_map(
&self,
) -> Option<&BTreeMap<ControlBlock, (bitcoin::ScriptBuf, LeafVersion)>> {
(**self).lookup_tap_control_block_map()
}
fn lookup_sha256(&self, h: &Pk::Sha256) -> Option<Preimage32> { (**self).lookup_sha256(h) }
fn lookup_hash256(&self, h: &Pk::Hash256) -> Option<Preimage32> { (**self).lookup_hash256(h) }
fn lookup_ripemd160(&self, h: &Pk::Ripemd160) -> Option<Preimage32> {
(**self).lookup_ripemd160(h)
}
fn lookup_hash160(&self, h: &Pk::Hash160) -> Option<Preimage32> { (**self).lookup_hash160(h) }
fn check_older(&self, t: Sequence) -> bool { (**self).check_older(t) }
fn check_after(&self, n: absolute::LockTime) -> bool { (**self).check_after(n) }
}
impl<'a, Pk: MiniscriptKey + ToPublicKey, S: Satisfier<Pk>> Satisfier<Pk> for &'a mut S {
fn lookup_ecdsa_sig(&self, p: &Pk) -> Option<bitcoin::ecdsa::Signature> {
(**self).lookup_ecdsa_sig(p)
}
fn lookup_tap_leaf_script_sig(
&self,
p: &Pk,
h: &TapLeafHash,
) -> Option<bitcoin::taproot::Signature> {
(**self).lookup_tap_leaf_script_sig(p, h)
}
fn lookup_tap_key_spend_sig(&self) -> Option<bitcoin::taproot::Signature> {
(**self).lookup_tap_key_spend_sig()
}
fn lookup_raw_pkh_pk(&self, pkh: &hash160::Hash) -> Option<bitcoin::PublicKey> {
(**self).lookup_raw_pkh_pk(pkh)
}
fn lookup_raw_pkh_x_only_pk(&self, pkh: &hash160::Hash) -> Option<XOnlyPublicKey> {
(**self).lookup_raw_pkh_x_only_pk(pkh)
}
fn lookup_raw_pkh_ecdsa_sig(
&self,
pkh: &hash160::Hash,
) -> Option<(bitcoin::PublicKey, bitcoin::ecdsa::Signature)> {
(**self).lookup_raw_pkh_ecdsa_sig(pkh)
}
fn lookup_raw_pkh_tap_leaf_script_sig(
&self,
pkh: &(hash160::Hash, TapLeafHash),
) -> Option<(XOnlyPublicKey, bitcoin::taproot::Signature)> {
(**self).lookup_raw_pkh_tap_leaf_script_sig(pkh)
}
fn lookup_tap_control_block_map(
&self,
) -> Option<&BTreeMap<ControlBlock, (bitcoin::ScriptBuf, LeafVersion)>> {
(**self).lookup_tap_control_block_map()
}
fn lookup_sha256(&self, h: &Pk::Sha256) -> Option<Preimage32> { (**self).lookup_sha256(h) }
fn lookup_hash256(&self, h: &Pk::Hash256) -> Option<Preimage32> { (**self).lookup_hash256(h) }
fn lookup_ripemd160(&self, h: &Pk::Ripemd160) -> Option<Preimage32> {
(**self).lookup_ripemd160(h)
}
fn lookup_hash160(&self, h: &Pk::Hash160) -> Option<Preimage32> { (**self).lookup_hash160(h) }
fn check_older(&self, t: Sequence) -> bool { (**self).check_older(t) }
fn check_after(&self, n: absolute::LockTime) -> bool { (**self).check_after(n) }
}
macro_rules! impl_tuple_satisfier {
($($ty:ident),*) => {
#[allow(non_snake_case)]
impl<$($ty,)* Pk> Satisfier<Pk> for ($($ty,)*)
where
Pk: MiniscriptKey + ToPublicKey,
$($ty: Satisfier< Pk>,)*
{
fn lookup_ecdsa_sig(&self, key: &Pk) -> Option<bitcoin::ecdsa::Signature> {
let &($(ref $ty,)*) = self;
$(
if let Some(result) = $ty.lookup_ecdsa_sig(key) {
return Some(result);
}
)*
None
}
fn lookup_tap_key_spend_sig(&self) -> Option<bitcoin::taproot::Signature> {
let &($(ref $ty,)*) = self;
$(
if let Some(result) = $ty.lookup_tap_key_spend_sig() {
return Some(result);
}
)*
None
}
fn lookup_tap_leaf_script_sig(&self, key: &Pk, h: &TapLeafHash) -> Option<bitcoin::taproot::Signature> {
let &($(ref $ty,)*) = self;
$(
if let Some(result) = $ty.lookup_tap_leaf_script_sig(key, h) {
return Some(result);
}
)*
None
}
fn lookup_raw_pkh_ecdsa_sig(
&self,
key_hash: &hash160::Hash,
) -> Option<(bitcoin::PublicKey, bitcoin::ecdsa::Signature)> {
let &($(ref $ty,)*) = self;
$(
if let Some(result) = $ty.lookup_raw_pkh_ecdsa_sig(key_hash) {
return Some(result);
}
)*
None
}
fn lookup_raw_pkh_tap_leaf_script_sig(
&self,
key_hash: &(hash160::Hash, TapLeafHash),
) -> Option<(XOnlyPublicKey, bitcoin::taproot::Signature)> {
let &($(ref $ty,)*) = self;
$(
if let Some(result) = $ty.lookup_raw_pkh_tap_leaf_script_sig(key_hash) {
return Some(result);
}
)*
None
}
fn lookup_raw_pkh_pk(
&self,
key_hash: &hash160::Hash,
) -> Option<bitcoin::PublicKey> {
let &($(ref $ty,)*) = self;
$(
if let Some(result) = $ty.lookup_raw_pkh_pk(key_hash) {
return Some(result);
}
)*
None
}
fn lookup_raw_pkh_x_only_pk(
&self,
key_hash: &hash160::Hash,
) -> Option<XOnlyPublicKey> {
let &($(ref $ty,)*) = self;
$(
if let Some(result) = $ty.lookup_raw_pkh_x_only_pk(key_hash) {
return Some(result);
}
)*
None
}
fn lookup_tap_control_block_map(
&self,
) -> Option<&BTreeMap<ControlBlock, (bitcoin::ScriptBuf, LeafVersion)>> {
let &($(ref $ty,)*) = self;
$(
if let Some(result) = $ty.lookup_tap_control_block_map() {
return Some(result);
}
)*
None
}
fn lookup_sha256(&self, h: &Pk::Sha256) -> Option<Preimage32> {
let &($(ref $ty,)*) = self;
$(
if let Some(result) = $ty.lookup_sha256(h) {
return Some(result);
}
)*
None
}
fn lookup_hash256(&self, h: &Pk::Hash256) -> Option<Preimage32> {
let &($(ref $ty,)*) = self;
$(
if let Some(result) = $ty.lookup_hash256(h) {
return Some(result);
}
)*
None
}
fn lookup_ripemd160(&self, h: &Pk::Ripemd160) -> Option<Preimage32> {
let &($(ref $ty,)*) = self;
$(
if let Some(result) = $ty.lookup_ripemd160(h) {
return Some(result);
}
)*
None
}
fn lookup_hash160(&self, h: &Pk::Hash160) -> Option<Preimage32> {
let &($(ref $ty,)*) = self;
$(
if let Some(result) = $ty.lookup_hash160(h) {
return Some(result);
}
)*
None
}
fn check_older(&self, n: Sequence) -> bool {
let &($(ref $ty,)*) = self;
$(
if $ty.check_older(n) {
return true;
}
)*
false
}
fn check_after(&self, n: absolute::LockTime) -> bool {
let &($(ref $ty,)*) = self;
$(
if $ty.check_after(n) {
return true;
}
)*
false
}
}
}
}
impl_tuple_satisfier!(A);
impl_tuple_satisfier!(A, B);
impl_tuple_satisfier!(A, B, C);
impl_tuple_satisfier!(A, B, C, D);
impl_tuple_satisfier!(A, B, C, D, E);
impl_tuple_satisfier!(A, B, C, D, E, F);
impl_tuple_satisfier!(A, B, C, D, E, F, G);
impl_tuple_satisfier!(A, B, C, D, E, F, G, H);
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum SchnorrSigType {
KeySpend {
merkle_root: Option<TapNodeHash>,
},
ScriptSpend {
leaf_hash: TapLeafHash,
},
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Placeholder<Pk: MiniscriptKey> {
Pubkey(Pk, usize),
PubkeyHash(hash160::Hash, usize),
EcdsaSigPk(Pk),
EcdsaSigPkHash(hash160::Hash),
SchnorrSigPk(Pk, SchnorrSigType, usize),
SchnorrSigPkHash(hash160::Hash, TapLeafHash, usize),
Sha256Preimage(Pk::Sha256),
Hash256Preimage(Pk::Hash256),
Ripemd160Preimage(Pk::Ripemd160),
Hash160Preimage(Pk::Hash160),
HashDissatisfaction,
PushOne,
PushZero,
TapScript(ScriptBuf),
TapControlBlock(ControlBlock),
}
impl<Pk: MiniscriptKey> fmt::Display for Placeholder<Pk> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
use Placeholder::*;
match self {
Pubkey(pk, size) => write!(f, "Pubkey(pk: {}, size: {})", pk, size),
PubkeyHash(hash, size) => write!(f, "PubkeyHash(hash: {}, size: {})", hash, size),
EcdsaSigPk(pk) => write!(f, "EcdsaSigPk(pk: {})", pk),
EcdsaSigPkHash(hash) => write!(f, "EcdsaSigPkHash(pkh: {})", hash),
SchnorrSigPk(pk, tap_leaf_hash, size) => write!(
f,
"SchnorrSig(pk: {}, tap_leaf_hash: {:?}, size: {})",
pk, tap_leaf_hash, size
),
SchnorrSigPkHash(pkh, tap_leaf_hash, size) => write!(
f,
"SchnorrSigPkHash(pkh: {}, tap_leaf_hash: {:?}, size: {})",
pkh, tap_leaf_hash, size
),
Sha256Preimage(hash) => write!(f, "Sha256Preimage(hash: {})", hash),
Hash256Preimage(hash) => write!(f, "Hash256Preimage(hash: {})", hash),
Ripemd160Preimage(hash) => write!(f, "Ripemd160Preimage(hash: {})", hash),
Hash160Preimage(hash) => write!(f, "Hash160Preimage(hash: {})", hash),
HashDissatisfaction => write!(f, "HashDissatisfaction"),
PushOne => write!(f, "PushOne"),
PushZero => write!(f, "PushZero"),
TapScript(script) => write!(f, "TapScript(script: {})", script),
TapControlBlock(control_block) => write!(
f,
"TapControlBlock(control_block: {})",
bitcoin::consensus::encode::serialize_hex(&control_block.serialize())
),
}
}
}
impl<Pk: MiniscriptKey + ToPublicKey> Placeholder<Pk> {
pub fn satisfy_self<Sat: Satisfier<Pk>>(&self, sat: &Sat) -> Option<Vec<u8>> {
match self {
Placeholder::Pubkey(pk, size) => {
if *size == 33 {
Some(pk.to_x_only_pubkey().serialize().to_vec())
} else {
Some(pk.to_public_key().to_bytes())
}
}
Placeholder::PubkeyHash(pkh, size) => sat
.lookup_raw_pkh_pk(pkh)
.map(|p| p.to_public_key())
.or(sat.lookup_raw_pkh_ecdsa_sig(pkh).map(|(p, _)| p))
.map(|pk| {
let pk = pk.to_bytes();
debug_assert!(1 + pk.len() == *size);
pk
}),
Placeholder::Hash256Preimage(h) => sat.lookup_hash256(h).map(|p| p.to_vec()),
Placeholder::Sha256Preimage(h) => sat.lookup_sha256(h).map(|p| p.to_vec()),
Placeholder::Hash160Preimage(h) => sat.lookup_hash160(h).map(|p| p.to_vec()),
Placeholder::Ripemd160Preimage(h) => sat.lookup_ripemd160(h).map(|p| p.to_vec()),
Placeholder::EcdsaSigPk(pk) => sat.lookup_ecdsa_sig(pk).map(|s| s.to_vec()),
Placeholder::EcdsaSigPkHash(pkh) => {
sat.lookup_raw_pkh_ecdsa_sig(pkh).map(|(_, s)| s.to_vec())
}
Placeholder::SchnorrSigPk(pk, SchnorrSigType::ScriptSpend { leaf_hash }, size) => sat
.lookup_tap_leaf_script_sig(pk, leaf_hash)
.map(|s| s.to_vec())
.map(|s| {
debug_assert!(s.len() == *size);
s
}),
Placeholder::SchnorrSigPk(_, _, size) => {
sat.lookup_tap_key_spend_sig().map(|s| s.to_vec()).map(|s| {
debug_assert!(s.len() == *size);
s
})
}
Placeholder::SchnorrSigPkHash(pkh, tap_leaf_hash, size) => sat
.lookup_raw_pkh_tap_leaf_script_sig(&(*pkh, *tap_leaf_hash))
.map(|(_, s)| {
let sig = s.to_vec();
debug_assert!(sig.len() == *size);
sig
}),
Placeholder::HashDissatisfaction => Some(vec![0; 32]),
Placeholder::PushZero => Some(vec![]),
Placeholder::PushOne => Some(vec![1]),
Placeholder::TapScript(s) => Some(s.to_bytes()),
Placeholder::TapControlBlock(cb) => Some(cb.serialize()),
}
}
}
#[derive(Clone, PartialEq, Eq, Debug)]
pub enum Witness<T> {
Stack(Vec<T>),
Unavailable,
Impossible,
}
impl<Pk: MiniscriptKey> PartialOrd for Witness<Placeholder<Pk>> {
fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> { Some(self.cmp(other)) }
}
impl<Pk: MiniscriptKey> Ord for Witness<Placeholder<Pk>> {
fn cmp(&self, other: &Self) -> cmp::Ordering {
match (self, other) {
(Witness::Stack(v1), Witness::Stack(v2)) => {
let w1 = witness_size(v1);
let w2 = witness_size(v2);
w1.cmp(&w2)
}
(Witness::Stack(_), _) => cmp::Ordering::Less,
(_, Witness::Stack(_)) => cmp::Ordering::Greater,
(Witness::Impossible, Witness::Unavailable) => cmp::Ordering::Less,
(Witness::Unavailable, Witness::Impossible) => cmp::Ordering::Greater,
(Witness::Impossible, Witness::Impossible) => cmp::Ordering::Equal,
(Witness::Unavailable, Witness::Unavailable) => cmp::Ordering::Equal,
}
}
}
impl<Pk: MiniscriptKey + ToPublicKey> Witness<Placeholder<Pk>> {
fn signature<S: AssetProvider<Pk>, Ctx: ScriptContext>(
sat: &S,
pk: &Pk,
leaf_hash: &TapLeafHash,
) -> Self {
match Ctx::sig_type() {
super::context::SigType::Ecdsa => {
if sat.provider_lookup_ecdsa_sig(pk) {
Witness::Stack(vec![Placeholder::EcdsaSigPk(pk.clone())])
} else {
Witness::Impossible
}
}
super::context::SigType::Schnorr => {
match sat.provider_lookup_tap_leaf_script_sig(pk, leaf_hash) {
Some(size) => Witness::Stack(vec![Placeholder::SchnorrSigPk(
pk.clone(),
SchnorrSigType::ScriptSpend { leaf_hash: *leaf_hash },
size,
)]),
None => Witness::Impossible,
}
}
}
}
fn pkh_public_key<S: AssetProvider<Pk>, Ctx: ScriptContext>(
sat: &S,
pkh: &hash160::Hash,
) -> Self {
match Ctx::sig_type() {
SigType::Ecdsa => match sat.provider_lookup_raw_pkh_pk(pkh) {
Some(pk) => Witness::Stack(vec![Placeholder::PubkeyHash(*pkh, Ctx::pk_len(&pk))]),
None => Witness::Unavailable,
},
SigType::Schnorr => match sat.provider_lookup_raw_pkh_x_only_pk(pkh) {
Some(pk) => Witness::Stack(vec![Placeholder::PubkeyHash(*pkh, Ctx::pk_len(&pk))]),
None => Witness::Unavailable,
},
}
}
fn pkh_signature<S: AssetProvider<Pk>, Ctx: ScriptContext>(
sat: &S,
pkh: &hash160::Hash,
leaf_hash: &TapLeafHash,
) -> Self {
match Ctx::sig_type() {
SigType::Ecdsa => match sat.provider_lookup_raw_pkh_ecdsa_sig(pkh) {
Some(pk) => Witness::Stack(vec![
Placeholder::EcdsaSigPkHash(*pkh),
Placeholder::PubkeyHash(*pkh, Ctx::pk_len(&pk)),
]),
None => Witness::Impossible,
},
SigType::Schnorr => {
match sat.provider_lookup_raw_pkh_tap_leaf_script_sig(&(*pkh, *leaf_hash)) {
Some((pk, size)) => Witness::Stack(vec![
Placeholder::SchnorrSigPkHash(*pkh, *leaf_hash, size),
Placeholder::PubkeyHash(*pkh, Ctx::pk_len(&pk)),
]),
None => Witness::Impossible,
}
}
}
}
fn ripemd160_preimage<S: AssetProvider<Pk>>(sat: &S, h: &Pk::Ripemd160) -> Self {
if sat.provider_lookup_ripemd160(h) {
Witness::Stack(vec![Placeholder::Ripemd160Preimage(h.clone())])
} else {
Witness::Unavailable
}
}
fn hash160_preimage<S: AssetProvider<Pk>>(sat: &S, h: &Pk::Hash160) -> Self {
if sat.provider_lookup_hash160(h) {
Witness::Stack(vec![Placeholder::Hash160Preimage(h.clone())])
} else {
Witness::Unavailable
}
}
fn sha256_preimage<S: AssetProvider<Pk>>(sat: &S, h: &Pk::Sha256) -> Self {
if sat.provider_lookup_sha256(h) {
Witness::Stack(vec![Placeholder::Sha256Preimage(h.clone())])
} else {
Witness::Unavailable
}
}
fn hash256_preimage<S: AssetProvider<Pk>>(sat: &S, h: &Pk::Hash256) -> Self {
if sat.provider_lookup_hash256(h) {
Witness::Stack(vec![Placeholder::Hash256Preimage(h.clone())])
} else {
Witness::Unavailable
}
}
}
impl<Pk: MiniscriptKey> Witness<Placeholder<Pk>> {
fn hash_dissatisfaction() -> Self { Witness::Stack(vec![Placeholder::HashDissatisfaction]) }
fn empty() -> Self { Witness::Stack(vec![]) }
fn push_1() -> Self { Witness::Stack(vec![Placeholder::PushOne]) }
fn push_0() -> Self { Witness::Stack(vec![Placeholder::PushZero]) }
fn combine(one: Self, two: Self) -> Self {
match (one, two) {
(Witness::Impossible, _) | (_, Witness::Impossible) => Witness::Impossible,
(Witness::Unavailable, _) | (_, Witness::Unavailable) => Witness::Unavailable,
(Witness::Stack(mut a), Witness::Stack(b)) => {
a.extend(b);
Witness::Stack(a)
}
}
}
}
#[derive(Clone, PartialEq, Eq, Debug)]
pub struct Satisfaction<T> {
pub stack: Witness<T>,
pub has_sig: bool,
pub absolute_timelock: Option<AbsLockTime>,
pub relative_timelock: Option<Sequence>,
}
impl<Pk: MiniscriptKey + ToPublicKey> Satisfaction<Placeholder<Pk>> {
pub(crate) fn build_template<P, Ctx>(
term: &Terminal<Pk, Ctx>,
provider: &P,
root_has_sig: bool,
leaf_hash: &TapLeafHash,
) -> Self
where
Ctx: ScriptContext,
P: AssetProvider<Pk>,
{
Self::satisfy_helper(
term,
provider,
root_has_sig,
leaf_hash,
&mut Satisfaction::minimum,
&mut Satisfaction::thresh,
)
}
pub(crate) fn build_template_mall<P, Ctx>(
term: &Terminal<Pk, Ctx>,
provider: &P,
root_has_sig: bool,
leaf_hash: &TapLeafHash,
) -> Self
where
Ctx: ScriptContext,
P: AssetProvider<Pk>,
{
Self::satisfy_helper(
term,
provider,
root_has_sig,
leaf_hash,
&mut Satisfaction::minimum_mall,
&mut Satisfaction::thresh_mall,
)
}
fn thresh<Ctx, Sat, F>(
k: usize,
subs: &[Arc<Miniscript<Pk, Ctx>>],
stfr: &Sat,
root_has_sig: bool,
leaf_hash: &TapLeafHash,
min_fn: &mut F,
) -> Self
where
Ctx: ScriptContext,
Sat: AssetProvider<Pk>,
F: FnMut(
Satisfaction<Placeholder<Pk>>,
Satisfaction<Placeholder<Pk>>,
) -> Satisfaction<Placeholder<Pk>>,
{
let mut sats = subs
.iter()
.map(|s| {
Self::satisfy_helper(
&s.node,
stfr,
root_has_sig,
leaf_hash,
min_fn,
&mut Self::thresh,
)
})
.collect::<Vec<_>>();
let mut ret_stack = subs
.iter()
.map(|s| {
Self::dissatisfy_helper(
&s.node,
stfr,
root_has_sig,
leaf_hash,
min_fn,
&mut Self::thresh,
)
})
.collect::<Vec<_>>();
let mut sat_indices = (0..subs.len()).collect::<Vec<_>>();
sat_indices.sort_by_key(|&i| {
let stack_weight = match (&sats[i].stack, &ret_stack[i].stack) {
(&Witness::Unavailable, _) | (&Witness::Impossible, _) => i64::MAX,
(_, &Witness::Unavailable) | (_, &Witness::Impossible) => i64::MIN,
(Witness::Stack(s), Witness::Stack(d)) => {
witness_size(s) as i64 - witness_size(d) as i64
}
};
let is_impossible = sats[i].stack == Witness::Impossible;
(is_impossible, sats[i].has_sig, stack_weight)
});
for i in 0..k {
mem::swap(&mut ret_stack[sat_indices[i]], &mut sats[sat_indices[i]]);
}
assert!(k > 0);
if sats[sat_indices[k - 1]].stack == Witness::Impossible {
Satisfaction {
stack: Witness::Impossible,
has_sig: false,
relative_timelock: None,
absolute_timelock: None,
}
}
else if k < sat_indices.len()
&& !sats[sat_indices[k]].has_sig
&& sats[sat_indices[k]].stack != Witness::Impossible
{
for sat in &ret_stack {
assert!(!sat.has_sig);
}
Satisfaction {
stack: Witness::Unavailable,
has_sig: false,
relative_timelock: None,
absolute_timelock: None,
}
} else {
Satisfaction {
has_sig: ret_stack.iter().any(|sat| sat.has_sig),
relative_timelock: ret_stack
.iter()
.filter_map(|sat| sat.relative_timelock)
.max(),
absolute_timelock: ret_stack
.iter()
.filter_map(|sat| sat.absolute_timelock)
.max(),
stack: ret_stack
.into_iter()
.fold(Witness::empty(), |acc, next| Witness::combine(next.stack, acc)),
}
}
}
fn thresh_mall<Ctx, Sat, F>(
k: usize,
subs: &[Arc<Miniscript<Pk, Ctx>>],
stfr: &Sat,
root_has_sig: bool,
leaf_hash: &TapLeafHash,
min_fn: &mut F,
) -> Self
where
Ctx: ScriptContext,
Sat: AssetProvider<Pk>,
F: FnMut(
Satisfaction<Placeholder<Pk>>,
Satisfaction<Placeholder<Pk>>,
) -> Satisfaction<Placeholder<Pk>>,
{
let mut sats = subs
.iter()
.map(|s| {
Self::satisfy_helper(
&s.node,
stfr,
root_has_sig,
leaf_hash,
min_fn,
&mut Self::thresh_mall,
)
})
.collect::<Vec<_>>();
let mut ret_stack = subs
.iter()
.map(|s| {
Self::dissatisfy_helper(
&s.node,
stfr,
root_has_sig,
leaf_hash,
min_fn,
&mut Self::thresh_mall,
)
})
.collect::<Vec<_>>();
let mut sat_indices = (0..subs.len()).collect::<Vec<_>>();
sat_indices.sort_by_key(|&i| {
match (&sats[i].stack, &ret_stack[i].stack) {
(&Witness::Unavailable, _) | (&Witness::Impossible, _) => i64::MAX,
(_, &Witness::Unavailable) | (_, &Witness::Impossible) => i64::MIN,
(Witness::Stack(s), Witness::Stack(d)) => {
witness_size(s) as i64 - witness_size(d) as i64
}
}
});
for i in 0..k {
mem::swap(&mut ret_stack[sat_indices[i]], &mut sats[sat_indices[i]]);
}
Satisfaction {
has_sig: ret_stack.iter().any(|sat| sat.has_sig),
relative_timelock: ret_stack
.iter()
.filter_map(|sat| sat.relative_timelock)
.max(),
absolute_timelock: ret_stack
.iter()
.filter_map(|sat| sat.absolute_timelock)
.max(),
stack: ret_stack
.into_iter()
.fold(Witness::empty(), |acc, next| Witness::combine(next.stack, acc)),
}
}
fn minimum(sat1: Self, sat2: Self) -> Self {
match (&sat1.stack, &sat2.stack) {
(&Witness::Impossible, _) => return sat2,
(_, &Witness::Impossible) => return sat1,
_ => {}
}
match (sat1.has_sig, sat2.has_sig) {
(false, false) => Satisfaction {
stack: Witness::Unavailable,
has_sig: false,
relative_timelock: None,
absolute_timelock: None,
},
(false, true) => Satisfaction {
stack: sat1.stack,
has_sig: false,
relative_timelock: sat1.relative_timelock,
absolute_timelock: sat1.absolute_timelock,
},
(true, false) => Satisfaction {
stack: sat2.stack,
has_sig: false,
relative_timelock: sat2.relative_timelock,
absolute_timelock: sat2.absolute_timelock,
},
(true, true) if sat1.stack < sat2.stack => Satisfaction {
stack: sat1.stack,
has_sig: true,
relative_timelock: sat1.relative_timelock,
absolute_timelock: sat1.absolute_timelock,
},
(true, true) => Satisfaction {
stack: sat2.stack,
has_sig: true,
relative_timelock: sat2.relative_timelock,
absolute_timelock: sat2.absolute_timelock,
},
}
}
fn minimum_mall(sat1: Self, sat2: Self) -> Self {
match (&sat1.stack, &sat2.stack) {
(&Witness::Impossible, _) | (&Witness::Unavailable, _) => return sat2,
(_, &Witness::Impossible) | (_, &Witness::Unavailable) => return sat1,
_ => {}
}
let (stack, absolute_timelock, relative_timelock) = if sat1.stack < sat2.stack {
(sat1.stack, sat1.absolute_timelock, sat1.relative_timelock)
} else {
(sat2.stack, sat2.absolute_timelock, sat2.relative_timelock)
};
Satisfaction {
stack,
has_sig: sat1.has_sig && sat2.has_sig,
relative_timelock,
absolute_timelock,
}
}
fn satisfy_helper<Ctx, Sat, F, G>(
term: &Terminal<Pk, Ctx>,
stfr: &Sat,
root_has_sig: bool,
leaf_hash: &TapLeafHash,
min_fn: &mut F,
thresh_fn: &mut G,
) -> Self
where
Ctx: ScriptContext,
Sat: AssetProvider<Pk>,
F: FnMut(
Satisfaction<Placeholder<Pk>>,
Satisfaction<Placeholder<Pk>>,
) -> Satisfaction<Placeholder<Pk>>,
G: FnMut(
usize,
&[Arc<Miniscript<Pk, Ctx>>],
&Sat,
bool,
&TapLeafHash,
&mut F,
) -> Satisfaction<Placeholder<Pk>>,
{
match *term {
Terminal::PkK(ref pk) => Satisfaction {
stack: Witness::signature::<_, Ctx>(stfr, pk, leaf_hash),
has_sig: true,
relative_timelock: None,
absolute_timelock: None,
},
Terminal::PkH(ref pk) => {
let wit = Witness::signature::<_, Ctx>(stfr, pk, leaf_hash);
Satisfaction {
stack: Witness::combine(
wit,
Witness::Stack(vec![Placeholder::Pubkey(pk.clone(), Ctx::pk_len(pk))]),
),
has_sig: true,
relative_timelock: None,
absolute_timelock: None,
}
}
Terminal::RawPkH(ref pkh) => Satisfaction {
stack: Witness::pkh_signature::<_, Ctx>(stfr, pkh, leaf_hash),
has_sig: true,
relative_timelock: None,
absolute_timelock: None,
},
Terminal::After(t) => {
let (stack, absolute_timelock) = if stfr.check_after(t.into()) {
(Witness::empty(), Some(t))
} else if root_has_sig {
(Witness::Impossible, None)
} else {
(Witness::Unavailable, None)
};
Satisfaction { stack, has_sig: false, relative_timelock: None, absolute_timelock }
}
Terminal::Older(t) => {
let (stack, relative_timelock) = if stfr.check_older(t) {
(Witness::empty(), Some(t))
} else if root_has_sig {
(Witness::Impossible, None)
} else {
(Witness::Unavailable, None)
};
Satisfaction { stack, has_sig: false, relative_timelock, absolute_timelock: None }
}
Terminal::Ripemd160(ref h) => Satisfaction {
stack: Witness::ripemd160_preimage(stfr, h),
has_sig: false,
relative_timelock: None,
absolute_timelock: None,
},
Terminal::Hash160(ref h) => Satisfaction {
stack: Witness::hash160_preimage(stfr, h),
has_sig: false,
relative_timelock: None,
absolute_timelock: None,
},
Terminal::Sha256(ref h) => Satisfaction {
stack: Witness::sha256_preimage(stfr, h),
has_sig: false,
relative_timelock: None,
absolute_timelock: None,
},
Terminal::Hash256(ref h) => Satisfaction {
stack: Witness::hash256_preimage(stfr, h),
has_sig: false,
relative_timelock: None,
absolute_timelock: None,
},
Terminal::True => Satisfaction {
stack: Witness::empty(),
has_sig: false,
relative_timelock: None,
absolute_timelock: None,
},
Terminal::False => Satisfaction {
stack: Witness::Impossible,
has_sig: false,
relative_timelock: None,
absolute_timelock: None,
},
Terminal::Alt(ref sub)
| Terminal::Swap(ref sub)
| Terminal::Check(ref sub)
| Terminal::Verify(ref sub)
| Terminal::NonZero(ref sub)
| Terminal::ZeroNotEqual(ref sub) => {
Self::satisfy_helper(&sub.node, stfr, root_has_sig, leaf_hash, min_fn, thresh_fn)
}
Terminal::DupIf(ref sub) => {
let sat = Self::satisfy_helper(
&sub.node,
stfr,
root_has_sig,
leaf_hash,
min_fn,
thresh_fn,
);
Satisfaction {
stack: Witness::combine(sat.stack, Witness::push_1()),
has_sig: sat.has_sig,
relative_timelock: sat.relative_timelock,
absolute_timelock: sat.absolute_timelock,
}
}
Terminal::AndV(ref l, ref r) | Terminal::AndB(ref l, ref r) => {
let l_sat =
Self::satisfy_helper(&l.node, stfr, root_has_sig, leaf_hash, min_fn, thresh_fn);
let r_sat =
Self::satisfy_helper(&r.node, stfr, root_has_sig, leaf_hash, min_fn, thresh_fn);
Satisfaction {
stack: Witness::combine(r_sat.stack, l_sat.stack),
has_sig: l_sat.has_sig || r_sat.has_sig,
relative_timelock: cmp::max(l_sat.relative_timelock, r_sat.relative_timelock),
absolute_timelock: cmp::max(l_sat.absolute_timelock, r_sat.absolute_timelock),
}
}
Terminal::AndOr(ref a, ref b, ref c) => {
let a_sat =
Self::satisfy_helper(&a.node, stfr, root_has_sig, leaf_hash, min_fn, thresh_fn);
let a_nsat = Self::dissatisfy_helper(
&a.node,
stfr,
root_has_sig,
leaf_hash,
min_fn,
thresh_fn,
);
let b_sat =
Self::satisfy_helper(&b.node, stfr, root_has_sig, leaf_hash, min_fn, thresh_fn);
let c_sat =
Self::satisfy_helper(&c.node, stfr, root_has_sig, leaf_hash, min_fn, thresh_fn);
min_fn(
Satisfaction {
stack: Witness::combine(b_sat.stack, a_sat.stack),
has_sig: a_sat.has_sig || b_sat.has_sig,
relative_timelock: cmp::max(
a_sat.relative_timelock,
b_sat.relative_timelock,
),
absolute_timelock: cmp::max(
a_sat.absolute_timelock,
b_sat.absolute_timelock,
),
},
Satisfaction {
stack: Witness::combine(c_sat.stack, a_nsat.stack),
has_sig: a_nsat.has_sig || c_sat.has_sig,
relative_timelock: c_sat.relative_timelock,
absolute_timelock: c_sat.absolute_timelock,
},
)
}
Terminal::OrB(ref l, ref r) => {
let l_sat =
Self::satisfy_helper(&l.node, stfr, root_has_sig, leaf_hash, min_fn, thresh_fn);
let r_sat =
Self::satisfy_helper(&r.node, stfr, root_has_sig, leaf_hash, min_fn, thresh_fn);
let l_nsat = Self::dissatisfy_helper(
&l.node,
stfr,
root_has_sig,
leaf_hash,
min_fn,
thresh_fn,
);
let r_nsat = Self::dissatisfy_helper(
&r.node,
stfr,
root_has_sig,
leaf_hash,
min_fn,
thresh_fn,
);
assert!(!l_nsat.has_sig);
assert!(!r_nsat.has_sig);
min_fn(
Satisfaction {
stack: Witness::combine(r_sat.stack, l_nsat.stack),
has_sig: r_sat.has_sig,
relative_timelock: r_sat.relative_timelock,
absolute_timelock: r_sat.absolute_timelock,
},
Satisfaction {
stack: Witness::combine(r_nsat.stack, l_sat.stack),
has_sig: l_sat.has_sig,
relative_timelock: l_sat.relative_timelock,
absolute_timelock: l_sat.absolute_timelock,
},
)
}
Terminal::OrD(ref l, ref r) | Terminal::OrC(ref l, ref r) => {
let l_sat =
Self::satisfy_helper(&l.node, stfr, root_has_sig, leaf_hash, min_fn, thresh_fn);
let r_sat =
Self::satisfy_helper(&r.node, stfr, root_has_sig, leaf_hash, min_fn, thresh_fn);
let l_nsat = Self::dissatisfy_helper(
&l.node,
stfr,
root_has_sig,
leaf_hash,
min_fn,
thresh_fn,
);
assert!(!l_nsat.has_sig);
min_fn(
l_sat,
Satisfaction {
stack: Witness::combine(r_sat.stack, l_nsat.stack),
has_sig: r_sat.has_sig,
relative_timelock: r_sat.relative_timelock,
absolute_timelock: r_sat.absolute_timelock,
},
)
}
Terminal::OrI(ref l, ref r) => {
let l_sat =
Self::satisfy_helper(&l.node, stfr, root_has_sig, leaf_hash, min_fn, thresh_fn);
let r_sat =
Self::satisfy_helper(&r.node, stfr, root_has_sig, leaf_hash, min_fn, thresh_fn);
min_fn(
Satisfaction {
stack: Witness::combine(l_sat.stack, Witness::push_1()),
has_sig: l_sat.has_sig,
relative_timelock: l_sat.relative_timelock,
absolute_timelock: l_sat.absolute_timelock,
},
Satisfaction {
stack: Witness::combine(r_sat.stack, Witness::push_0()),
has_sig: r_sat.has_sig,
relative_timelock: r_sat.relative_timelock,
absolute_timelock: r_sat.absolute_timelock,
},
)
}
Terminal::Thresh(k, ref subs) => {
thresh_fn(k, subs, stfr, root_has_sig, leaf_hash, min_fn)
}
Terminal::Multi(k, ref keys) => {
let mut sig_count = 0;
let mut sigs = Vec::with_capacity(k);
for pk in keys {
match Witness::signature::<_, Ctx>(stfr, pk, leaf_hash) {
Witness::Stack(sig) => {
sigs.push(sig);
sig_count += 1;
}
Witness::Impossible => {}
Witness::Unavailable => unreachable!(
"Signature satisfaction without witness must be impossible"
),
}
}
if sig_count < k {
Satisfaction {
stack: Witness::Impossible,
has_sig: false,
relative_timelock: None,
absolute_timelock: None,
}
} else {
for _ in 0..sig_count - k {
let max_idx = sigs
.iter()
.enumerate()
.max_by_key(|&(_, v)| v.len())
.unwrap()
.0;
sigs[max_idx] = vec![];
}
Satisfaction {
stack: sigs.into_iter().fold(Witness::push_0(), |acc, sig| {
Witness::combine(acc, Witness::Stack(sig))
}),
has_sig: true,
relative_timelock: None,
absolute_timelock: None,
}
}
}
Terminal::MultiA(k, ref keys) => {
let mut sig_count = 0;
let mut sigs = vec![vec![Placeholder::PushZero]; keys.len()];
for (i, pk) in keys.iter().rev().enumerate() {
match Witness::signature::<_, Ctx>(stfr, pk, leaf_hash) {
Witness::Stack(sig) => {
sigs[i] = sig;
sig_count += 1;
if sig_count == k {
break;
}
}
Witness::Impossible => {}
Witness::Unavailable => unreachable!(
"Signature satisfaction without witness must be impossible"
),
}
}
if sig_count < k {
Satisfaction {
stack: Witness::Impossible,
has_sig: false,
relative_timelock: None,
absolute_timelock: None,
}
} else {
Satisfaction {
stack: sigs.into_iter().fold(Witness::empty(), |acc, sig| {
Witness::combine(acc, Witness::Stack(sig))
}),
has_sig: true,
relative_timelock: None,
absolute_timelock: None,
}
}
}
}
}
fn dissatisfy_helper<Ctx, Sat, F, G>(
term: &Terminal<Pk, Ctx>,
stfr: &Sat,
root_has_sig: bool,
leaf_hash: &TapLeafHash,
min_fn: &mut F,
thresh_fn: &mut G,
) -> Self
where
Ctx: ScriptContext,
Sat: AssetProvider<Pk>,
F: FnMut(
Satisfaction<Placeholder<Pk>>,
Satisfaction<Placeholder<Pk>>,
) -> Satisfaction<Placeholder<Pk>>,
G: FnMut(
usize,
&[Arc<Miniscript<Pk, Ctx>>],
&Sat,
bool,
&TapLeafHash,
&mut F,
) -> Satisfaction<Placeholder<Pk>>,
{
match *term {
Terminal::PkK(..) => Satisfaction {
stack: Witness::push_0(),
has_sig: false,
relative_timelock: None,
absolute_timelock: None,
},
Terminal::PkH(ref pk) => Satisfaction {
stack: Witness::combine(
Witness::push_0(),
Witness::Stack(vec![Placeholder::Pubkey(pk.clone(), Ctx::pk_len(pk))]),
),
has_sig: false,
relative_timelock: None,
absolute_timelock: None,
},
Terminal::RawPkH(ref pkh) => Satisfaction {
stack: Witness::combine(
Witness::push_0(),
Witness::pkh_public_key::<_, Ctx>(stfr, pkh),
),
has_sig: false,
relative_timelock: None,
absolute_timelock: None,
},
Terminal::False => Satisfaction {
stack: Witness::empty(),
has_sig: false,
relative_timelock: None,
absolute_timelock: None,
},
Terminal::True
| Terminal::Older(_)
| Terminal::After(_)
| Terminal::Verify(_)
| Terminal::OrC(..) => Satisfaction {
stack: Witness::Impossible,
has_sig: false,
relative_timelock: None,
absolute_timelock: None,
},
Terminal::Sha256(_)
| Terminal::Hash256(_)
| Terminal::Ripemd160(_)
| Terminal::Hash160(_) => Satisfaction {
stack: Witness::hash_dissatisfaction(),
has_sig: false,
relative_timelock: None,
absolute_timelock: None,
},
Terminal::Alt(ref sub)
| Terminal::Swap(ref sub)
| Terminal::Check(ref sub)
| Terminal::ZeroNotEqual(ref sub) => {
Self::dissatisfy_helper(&sub.node, stfr, root_has_sig, leaf_hash, min_fn, thresh_fn)
}
Terminal::DupIf(_) | Terminal::NonZero(_) => Satisfaction {
stack: Witness::push_0(),
has_sig: false,
relative_timelock: None,
absolute_timelock: None,
},
Terminal::AndV(ref v, ref other) => {
let vsat =
Self::satisfy_helper(&v.node, stfr, root_has_sig, leaf_hash, min_fn, thresh_fn);
let odissat = Self::dissatisfy_helper(
&other.node,
stfr,
root_has_sig,
leaf_hash,
min_fn,
thresh_fn,
);
Satisfaction {
stack: Witness::combine(odissat.stack, vsat.stack),
has_sig: vsat.has_sig || odissat.has_sig,
relative_timelock: None,
absolute_timelock: None,
}
}
Terminal::AndB(ref l, ref r)
| Terminal::OrB(ref l, ref r)
| Terminal::OrD(ref l, ref r)
| Terminal::AndOr(ref l, _, ref r) => {
let lnsat = Self::dissatisfy_helper(
&l.node,
stfr,
root_has_sig,
leaf_hash,
min_fn,
thresh_fn,
);
let rnsat = Self::dissatisfy_helper(
&r.node,
stfr,
root_has_sig,
leaf_hash,
min_fn,
thresh_fn,
);
Satisfaction {
stack: Witness::combine(rnsat.stack, lnsat.stack),
has_sig: rnsat.has_sig || lnsat.has_sig,
relative_timelock: None,
absolute_timelock: None,
}
}
Terminal::OrI(ref l, ref r) => {
let lnsat = Self::dissatisfy_helper(
&l.node,
stfr,
root_has_sig,
leaf_hash,
min_fn,
thresh_fn,
);
let dissat_1 = Satisfaction {
stack: Witness::combine(lnsat.stack, Witness::push_1()),
has_sig: lnsat.has_sig,
relative_timelock: None,
absolute_timelock: None,
};
let rnsat = Self::dissatisfy_helper(
&r.node,
stfr,
root_has_sig,
leaf_hash,
min_fn,
thresh_fn,
);
let dissat_2 = Satisfaction {
stack: Witness::combine(rnsat.stack, Witness::push_0()),
has_sig: rnsat.has_sig,
relative_timelock: None,
absolute_timelock: None,
};
Satisfaction::minimum_mall(dissat_1, dissat_2)
}
Terminal::Thresh(_, ref subs) => Satisfaction {
stack: subs.iter().fold(Witness::empty(), |acc, sub| {
let nsat = Self::dissatisfy_helper(
&sub.node,
stfr,
root_has_sig,
leaf_hash,
min_fn,
thresh_fn,
);
assert!(!nsat.has_sig);
Witness::combine(nsat.stack, acc)
}),
has_sig: false,
relative_timelock: None,
absolute_timelock: None,
},
Terminal::Multi(k, _) => Satisfaction {
stack: Witness::Stack(vec![Placeholder::PushZero; k + 1]),
has_sig: false,
relative_timelock: None,
absolute_timelock: None,
},
Terminal::MultiA(_, ref pks) => Satisfaction {
stack: Witness::Stack(vec![Placeholder::PushZero; pks.len()]),
has_sig: false,
relative_timelock: None,
absolute_timelock: None,
},
}
}
pub fn try_completing<Sat: Satisfier<Pk>>(&self, stfr: &Sat) -> Option<Satisfaction<Vec<u8>>> {
let Satisfaction { stack, has_sig, relative_timelock, absolute_timelock } = self;
let stack = match stack {
Witness::Stack(stack) => Witness::Stack(
stack
.iter()
.map(|placeholder| placeholder.satisfy_self(stfr))
.collect::<Option<_>>()?,
),
Witness::Unavailable => Witness::Unavailable,
Witness::Impossible => Witness::Impossible,
};
Some(Satisfaction {
stack,
has_sig: *has_sig,
relative_timelock: *relative_timelock,
absolute_timelock: *absolute_timelock,
})
}
}
impl Satisfaction<Vec<u8>> {
pub(super) fn satisfy<Ctx, Pk, Sat>(
term: &Terminal<Pk, Ctx>,
stfr: &Sat,
root_has_sig: bool,
leaf_hash: &TapLeafHash,
) -> Self
where
Ctx: ScriptContext,
Pk: MiniscriptKey + ToPublicKey,
Sat: Satisfier<Pk>,
{
Satisfaction::<Placeholder<Pk>>::build_template(term, &stfr, root_has_sig, leaf_hash)
.try_completing(stfr)
.expect("the same satisfier should manage to complete the template")
}
pub(super) fn satisfy_mall<Ctx, Pk, Sat>(
term: &Terminal<Pk, Ctx>,
stfr: &Sat,
root_has_sig: bool,
leaf_hash: &TapLeafHash,
) -> Self
where
Ctx: ScriptContext,
Pk: MiniscriptKey + ToPublicKey,
Sat: Satisfier<Pk>,
{
Satisfaction::<Placeholder<Pk>>::build_template_mall(term, &stfr, root_has_sig, leaf_hash)
.try_completing(stfr)
.expect("the same satisfier should manage to complete the template")
}
}