use std::str::FromStr;
use std::{fmt, str};
use bitcoin::hashes::hex::FromHex;
use bitcoin::hashes::{hash160, ripemd160, sha256, sha256d};
use super::concrete::PolicyError;
use errstr;
use Error;
use {expression, ForEach, ForEachKey, MiniscriptKey};
use super::ENTAILMENT_MAX_TERMINALS;
#[derive(Clone, PartialEq, Eq, PartialOrd, Ord)]
pub enum Policy<Pk: MiniscriptKey> {
Unsatisfiable,
Trivial,
KeyHash(Pk::Hash),
After(u32),
Older(u32),
Sha256(sha256::Hash),
Hash256(sha256d::Hash),
Ripemd160(ripemd160::Hash),
Hash160(hash160::Hash),
Threshold(usize, Vec<Policy<Pk>>),
TxTemplate(sha256::Hash),
}
impl<Pk: MiniscriptKey> ForEachKey<Pk> for Policy<Pk> {
fn for_each_key<'a, F: FnMut(ForEach<'a, Pk>) -> bool>(&'a self, mut pred: F) -> bool
where
Pk: 'a,
Pk::Hash: 'a,
{
match *self {
Policy::Unsatisfiable | Policy::Trivial => true,
Policy::KeyHash(ref pkh) => pred(ForEach::Hash(pkh)),
Policy::Sha256(..)
| Policy::Hash256(..)
| Policy::Ripemd160(..)
| Policy::Hash160(..)
| Policy::After(..)
| Policy::Older(..)
| Policy::TxTemplate(..) => true,
Policy::Threshold(_, ref subs) => subs.iter().all(|sub| sub.for_each_key(&mut pred)),
}
}
}
impl<Pk: MiniscriptKey> Policy<Pk> {
pub fn translate_pkh<Fpkh, Q, E>(&self, mut translatefpkh: Fpkh) -> Result<Policy<Q>, E>
where
Fpkh: FnMut(&Pk::Hash) -> Result<Q::Hash, E>,
Q: MiniscriptKey,
{
match *self {
Policy::Unsatisfiable => Ok(Policy::Unsatisfiable),
Policy::Trivial => Ok(Policy::Trivial),
Policy::KeyHash(ref pkh) => translatefpkh(pkh).map(Policy::KeyHash),
Policy::Sha256(ref h) => Ok(Policy::Sha256(h.clone())),
Policy::Hash256(ref h) => Ok(Policy::Hash256(h.clone())),
Policy::Ripemd160(ref h) => Ok(Policy::Ripemd160(h.clone())),
Policy::Hash160(ref h) => Ok(Policy::Hash160(h.clone())),
Policy::After(n) => Ok(Policy::After(n)),
Policy::Older(n) => Ok(Policy::Older(n)),
Policy::Threshold(k, ref subs) => {
let new_subs: Result<Vec<Policy<Q>>, _> = subs
.iter()
.map(|sub| sub.translate_pkh(&mut translatefpkh))
.collect();
new_subs.map(|ok| Policy::Threshold(k, ok))
}
Policy::TxTemplate(ref h) => Ok(Policy::TxTemplate(h.clone()))
}
}
pub fn entails(self, other: Policy<Pk>) -> Result<bool, PolicyError> {
if self.n_terminals() > ENTAILMENT_MAX_TERMINALS {
return Err(PolicyError::EntailmentMaxTerminals);
}
match (self, other) {
(Policy::Unsatisfiable, _) => Ok(true),
(Policy::Trivial, Policy::Trivial) => Ok(true),
(Policy::Trivial, _) => Ok(false),
(_, Policy::Unsatisfiable) => Ok(false),
(a, b) => {
let (a_norm, b_norm) = (a.normalized(), b.normalized());
let first_constraint = a_norm.first_constraint();
let (a1, b1) = (
a_norm.clone().satisfy_constraint(&first_constraint, true),
b_norm.clone().satisfy_constraint(&first_constraint, true),
);
let (a2, b2) = (
a_norm.satisfy_constraint(&first_constraint, false),
b_norm.satisfy_constraint(&first_constraint, false),
);
Ok(Policy::entails(a1, b1)? && Policy::entails(a2, b2)?)
}
}
}
fn n_terminals(&self) -> usize {
match self {
&Policy::Threshold(_k, ref subs) => subs.iter().map(|sub| sub.n_terminals()).sum(),
&Policy::Trivial | &Policy::Unsatisfiable => 0,
_leaf => 1,
}
}
fn first_constraint(&self) -> Policy<Pk> {
debug_assert!(self.clone().normalized() == self.clone());
match self {
&Policy::Threshold(_k, ref subs) => subs[0].first_constraint(),
first => first.clone(),
}
}
fn satisfy_constraint(self, witness: &Policy<Pk>, available: bool) -> Policy<Pk> {
debug_assert!(self.clone().normalized() == self.clone());
match *witness {
Policy::Threshold(..) => unreachable!(),
_ => {}
};
let ret = match self {
Policy::Threshold(k, subs) => {
let mut ret_subs = vec![];
for sub in subs {
ret_subs.push(sub.satisfy_constraint(witness, available));
}
Policy::Threshold(k, ret_subs)
}
ref leaf if leaf == witness => {
if available {
Policy::Trivial
} else {
Policy::Unsatisfiable
}
}
x => x,
};
ret.normalized()
}
}
impl<Pk: MiniscriptKey> fmt::Debug for Policy<Pk> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
match *self {
Policy::Unsatisfiable => f.write_str("UNSATISFIABLE()"),
Policy::Trivial => f.write_str("TRIVIAL()"),
Policy::KeyHash(ref pkh) => write!(f, "pkh({:?})", pkh),
Policy::After(n) => write!(f, "after({})", n),
Policy::Older(n) => write!(f, "older({})", n),
Policy::Sha256(h) => write!(f, "sha256({})", h),
Policy::Hash256(h) => write!(f, "hash256({})", h),
Policy::Ripemd160(h) => write!(f, "ripemd160({})", h),
Policy::Hash160(h) => write!(f, "hash160({})", h),
Policy::Threshold(k, ref subs) => {
if k == subs.len() {
write!(f, "and(")?;
} else if k == 1 {
write!(f, "or(")?;
} else {
write!(f, "thresh({}", k)?;
}
for (i, sub) in subs.into_iter().enumerate() {
if i == 0 {
write!(f, "{}", sub)?;
} else {
write!(f, ",{}", sub)?;
}
}
f.write_str(")")
}
Policy::TxTemplate(h) => write!(f, "txtmpl({})", h),
}
}
}
impl<Pk: MiniscriptKey> fmt::Display for Policy<Pk> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
match *self {
Policy::Unsatisfiable => f.write_str("UNSATISFIABLE"),
Policy::Trivial => f.write_str("TRIVIAL"),
Policy::KeyHash(ref pkh) => write!(f, "pkh({})", pkh),
Policy::After(n) => write!(f, "after({})", n),
Policy::Older(n) => write!(f, "older({})", n),
Policy::Sha256(h) => write!(f, "sha256({})", h),
Policy::Hash256(h) => write!(f, "hash256({})", h),
Policy::Ripemd160(h) => write!(f, "ripemd160({})", h),
Policy::Hash160(h) => write!(f, "hash160({})", h),
Policy::Threshold(k, ref subs) => {
if k == subs.len() {
write!(f, "and(")?;
} else if k == 1 {
write!(f, "or(")?;
} else {
write!(f, "thresh({},", k)?;
}
for (i, sub) in subs.into_iter().enumerate() {
if i == 0 {
write!(f, "{}", sub)?;
} else {
write!(f, ",{}", sub)?;
}
}
f.write_str(")")
}
Policy::TxTemplate(h) => write!(f, "txtmpl({})", h),
}
}
}
impl<Pk> str::FromStr for Policy<Pk>
where
Pk: MiniscriptKey + str::FromStr,
Pk::Hash: str::FromStr,
<Pk as str::FromStr>::Err: ToString,
<<Pk as MiniscriptKey>::Hash as str::FromStr>::Err: ToString,
{
type Err = Error;
fn from_str(s: &str) -> Result<Policy<Pk>, Error> {
for ch in s.as_bytes() {
if *ch < 20 || *ch > 127 {
return Err(Error::Unprintable(*ch));
}
}
let tree = expression::Tree::from_str(s)?;
expression::FromTree::from_tree(&tree)
}
}
serde_string_impl_pk!(Policy, "a miniscript semantic policy");
impl<Pk> expression::FromTree for Policy<Pk>
where
Pk: MiniscriptKey + str::FromStr,
Pk::Hash: str::FromStr,
<Pk as str::FromStr>::Err: ToString,
<<Pk as MiniscriptKey>::Hash as str::FromStr>::Err: ToString,
{
fn from_tree(top: &expression::Tree) -> Result<Policy<Pk>, Error> {
match (top.name, top.args.len()) {
("UNSATISFIABLE", 0) => Ok(Policy::Unsatisfiable),
("TRIVIAL", 0) => Ok(Policy::Trivial),
("pkh", 1) => expression::terminal(&top.args[0], |pk| {
Pk::Hash::from_str(pk).map(Policy::KeyHash)
}),
("after", 1) => expression::terminal(&top.args[0], |x| {
expression::parse_num(x).map(Policy::After)
}),
("older", 1) => expression::terminal(&top.args[0], |x| {
expression::parse_num(x).map(Policy::Older)
}),
("sha256", 1) => expression::terminal(&top.args[0], |x| {
sha256::Hash::from_hex(x).map(Policy::Sha256)
}),
("hash256", 1) => expression::terminal(&top.args[0], |x| {
sha256d::Hash::from_hex(x).map(Policy::Hash256)
}),
("ripemd160", 1) => expression::terminal(&top.args[0], |x| {
ripemd160::Hash::from_hex(x).map(Policy::Ripemd160)
}),
("hash160", 1) => expression::terminal(&top.args[0], |x| {
hash160::Hash::from_hex(x).map(Policy::Hash160)
}),
("and", nsubs) => {
if nsubs < 2 {
return Err(Error::PolicyError(PolicyError::InsufficientArgsforAnd));
}
let mut subs = Vec::with_capacity(nsubs);
for arg in &top.args {
subs.push(Policy::from_tree(arg)?);
}
Ok(Policy::Threshold(nsubs, subs))
}
("or", nsubs) => {
if nsubs < 2 {
return Err(Error::PolicyError(PolicyError::InsufficientArgsforOr));
}
let mut subs = Vec::with_capacity(nsubs);
for arg in &top.args {
subs.push(Policy::from_tree(arg)?);
}
Ok(Policy::Threshold(1, subs))
}
("thresh", nsubs) => {
if nsubs == 0 || nsubs == 1 {
return Err(errstr("thresh without args"));
}
if !top.args[0].args.is_empty() {
return Err(errstr(top.args[0].args[0].name));
}
let thresh = expression::parse_num(top.args[0].name)?;
if thresh <= 1 || thresh >= (nsubs as u32 - 1) {
return Err(errstr(
"Semantic Policy thresh cannot have k = 1 or k =n, use `and`/`or` instead",
));
}
if thresh >= (nsubs as u32) {
return Err(errstr(top.args[0].name));
}
let mut subs = Vec::with_capacity(top.args.len() - 1);
for arg in &top.args[1..] {
subs.push(Policy::from_tree(arg)?);
}
Ok(Policy::Threshold(thresh as usize, subs))
}
("txtmpl", 1) => expression::terminal(&top.args[0], |x| {
sha256::Hash::from_hex(x).map(Policy::TxTemplate)
}),
_ => Err(errstr(top.name)),
}
}
}
impl<Pk: MiniscriptKey> Policy<Pk> {
pub fn normalized(self) -> Policy<Pk> {
match self {
Policy::Threshold(k, subs) => {
let mut ret_subs = Vec::with_capacity(subs.len());
let subs: Vec<_> = subs.into_iter().map(|sub| sub.normalized()).collect();
let trivial_count = subs.iter().filter(|&pol| *pol == Policy::Trivial).count();
let unsatisfied_count = subs
.iter()
.filter(|&pol| *pol == Policy::Unsatisfiable)
.count();
let n = subs.len() - unsatisfied_count - trivial_count;
let m = k.checked_sub(trivial_count).map_or(0, |x| x);
let is_and = m == n;
let is_or = m == 1;
for sub in subs {
match sub {
Policy::Trivial | Policy::Unsatisfiable => {}
Policy::Threshold(1, or_subs) => {
if is_or {
ret_subs.extend(or_subs);
} else {
ret_subs.push(Policy::Threshold(1, or_subs));
}
}
Policy::Threshold(k, and_subs) => {
if k == and_subs.len() && is_and {
ret_subs.extend(and_subs)
} else {
ret_subs.push(Policy::Threshold(k, and_subs));
}
}
x => ret_subs.push(x),
}
}
if m == 0 {
Policy::Trivial
} else if m > ret_subs.len() {
Policy::Unsatisfiable
} else if ret_subs.len() == 1 {
ret_subs.pop().unwrap()
} else if is_and {
Policy::Threshold(ret_subs.len(), ret_subs)
} else if is_or {
Policy::Threshold(1, ret_subs)
} else {
Policy::Threshold(m, ret_subs)
}
}
x => x,
}
}
pub fn is_trivial(&self) -> bool {
match *self {
Policy::Trivial => true,
_ => false,
}
}
pub fn is_unsatisfiable(&self) -> bool {
match *self {
Policy::Unsatisfiable => true,
_ => false,
}
}
fn real_relative_timelocks(&self) -> Vec<u32> {
match *self {
Policy::Unsatisfiable
| Policy::Trivial
| Policy::KeyHash(..)
| Policy::Sha256(..)
| Policy::Hash256(..)
| Policy::Ripemd160(..)
| Policy::Hash160(..)
| Policy::TxTemplate(..) => vec![],
Policy::After(..) => vec![],
Policy::Older(t) => vec![t],
Policy::Threshold(_, ref subs) => subs.iter().fold(vec![], |mut acc, x| {
acc.extend(x.real_relative_timelocks());
acc
}),
}
}
pub fn relative_timelocks(&self) -> Vec<u32> {
let mut ret = self.real_relative_timelocks();
ret.sort();
ret.dedup();
ret
}
pub fn at_age(mut self, time: u32) -> Policy<Pk> {
self = match self {
Policy::Older(t) => {
if t > time {
Policy::Unsatisfiable
} else {
Policy::Older(t)
}
}
Policy::Threshold(k, subs) => {
Policy::Threshold(k, subs.into_iter().map(|sub| sub.at_age(time)).collect())
}
x => x,
};
self.normalized()
}
pub fn n_keys(&self) -> usize {
match *self {
Policy::Unsatisfiable | Policy::Trivial => 0,
Policy::KeyHash(..) => 1,
Policy::After(..)
| Policy::Older(..)
| Policy::Sha256(..)
| Policy::Hash256(..)
| Policy::Ripemd160(..)
| Policy::Hash160(..)
| Policy::TxTemplate(..) => 0,
Policy::Threshold(_, ref subs) => subs.iter().map(|sub| sub.n_keys()).sum::<usize>(),
}
}
pub fn minimum_n_keys(&self) -> usize {
match *self {
Policy::Unsatisfiable | Policy::Trivial => 0,
Policy::KeyHash(..) => 1,
Policy::After(..)
| Policy::Older(..)
| Policy::Sha256(..)
| Policy::Hash256(..)
| Policy::Ripemd160(..)
| Policy::Hash160(..)
| Policy::TxTemplate(..) => 0,
Policy::Threshold(k, ref subs) => {
let mut sublens: Vec<usize> = subs.iter().map(Policy::minimum_n_keys).collect();
sublens.sort();
sublens[0..k].iter().cloned().sum::<usize>()
}
}
}
}
impl<Pk: MiniscriptKey> Policy<Pk> {
pub fn sorted(self) -> Policy<Pk> {
match self {
Policy::Threshold(k, subs) => {
let mut new_subs: Vec<_> = subs.into_iter().map(Policy::sorted).collect();
new_subs.sort();
Policy::Threshold(k, new_subs)
}
x => x,
}
}
}
#[cfg(test)]
mod tests {
use bitcoin::PublicKey;
use std::str::FromStr;
use super::*;
type StringPolicy = Policy<String>;
#[test]
fn parse_policy_err() {
assert!(StringPolicy::from_str("(").is_err());
assert!(StringPolicy::from_str("(x()").is_err());
assert!(StringPolicy::from_str("(\u{7f}()3").is_err());
assert!(StringPolicy::from_str("pkh()").is_ok());
assert!(StringPolicy::from_str("or(or)").is_err());
assert!(Policy::<PublicKey>::from_str("pkh()").is_err());
assert!(Policy::<PublicKey>::from_str(
"pkh(\
0200000000000000000000000000000000000002\
)"
)
.is_ok());
}
#[test]
fn semantic_analysis() {
let policy = StringPolicy::from_str("pkh()").unwrap();
assert_eq!(policy, Policy::KeyHash("".to_owned()));
assert_eq!(policy.relative_timelocks(), vec![]);
assert_eq!(policy.clone().at_age(0), policy.clone());
assert_eq!(policy.clone().at_age(10000), policy.clone());
assert_eq!(policy.n_keys(), 1);
assert_eq!(policy.minimum_n_keys(), 1);
let policy = StringPolicy::from_str("older(1000)").unwrap();
assert_eq!(policy, Policy::Older(1000));
assert_eq!(policy.relative_timelocks(), vec![1000]);
assert_eq!(policy.clone().at_age(0), Policy::Unsatisfiable);
assert_eq!(policy.clone().at_age(999), Policy::Unsatisfiable);
assert_eq!(policy.clone().at_age(1000), policy.clone());
assert_eq!(policy.clone().at_age(10000), policy.clone());
assert_eq!(policy.n_keys(), 0);
assert_eq!(policy.minimum_n_keys(), 0);
let policy = StringPolicy::from_str("or(pkh(),older(1000))").unwrap();
assert_eq!(
policy,
Policy::Threshold(
1,
vec![Policy::KeyHash("".to_owned()), Policy::Older(1000),]
)
);
assert_eq!(policy.relative_timelocks(), vec![1000]);
assert_eq!(policy.clone().at_age(0), Policy::KeyHash("".to_owned()));
assert_eq!(policy.clone().at_age(999), Policy::KeyHash("".to_owned()));
assert_eq!(policy.clone().at_age(1000), policy.clone().normalized());
assert_eq!(policy.clone().at_age(10000), policy.clone().normalized());
assert_eq!(policy.n_keys(), 1);
assert_eq!(policy.minimum_n_keys(), 0);
let policy = StringPolicy::from_str(
"thresh(\
2,older(1000),older(10000),older(1000),older(2000),older(2000)\
)",
)
.unwrap();
assert_eq!(
policy,
Policy::Threshold(
2,
vec![
Policy::Older(1000),
Policy::Older(10000),
Policy::Older(1000),
Policy::Older(2000),
Policy::Older(2000),
]
)
);
assert_eq!(
policy.relative_timelocks(),
vec![1000, 2000, 10000]
);
}
#[test]
fn entailment_liquid_test() {
let liquid_pol = StringPolicy::from_str(
"or(and(older(4096),thresh(2,pkh(A),pkh(B),pkh(C))),thresh(11,pkh(F1),pkh(F2),pkh(F3),pkh(F4),pkh(F5),pkh(F6),pkh(F7),pkh(F8),pkh(F9),pkh(F10),pkh(F11),pkh(F12),pkh(F13),pkh(F14)))").unwrap();
let master_key = StringPolicy::from_str("and(older(50000000),pkh(master))").unwrap();
let new_liquid_pol = Policy::Threshold(1, vec![liquid_pol.clone(), master_key]);
assert!(liquid_pol.clone().entails(new_liquid_pol.clone()).unwrap());
assert!(!new_liquid_pol.entails(liquid_pol.clone()).unwrap());
let backup_policy = StringPolicy::from_str("thresh(2,pkh(A),pkh(B),pkh(C))").unwrap();
assert!(!backup_policy
.clone()
.entails(liquid_pol.clone().at_age(4095))
.unwrap());
let fed_pol = StringPolicy::from_str("thresh(11,pkh(F1),pkh(F2),pkh(F3),pkh(F4),pkh(F5),pkh(F6),pkh(F7),pkh(F8),pkh(F9),pkh(F10),pkh(F11),pkh(F12),pkh(F13),pkh(F14))").unwrap();
let backup_policy_after_expiry =
StringPolicy::from_str("and(older(4096),thresh(2,pkh(A),pkh(B),pkh(C)))").unwrap();
assert!(fed_pol.entails(liquid_pol.clone()).unwrap());
assert!(backup_policy_after_expiry
.entails(liquid_pol.clone())
.unwrap());
}
#[test]
fn entailment_escrow() {
let escrow_pol =
StringPolicy::from_str("thresh(2,pkh(Alice),pkh(Bob),pkh(Judge))").unwrap();
let auth_alice = StringPolicy::from_str("and(pkh(Alice),pkh(Judge))").unwrap();
let control_alice =
StringPolicy::from_str("or(pkh(Alice),and(pkh(Judge),pkh(Bob)))").unwrap();
assert!(auth_alice.entails(escrow_pol.clone()).unwrap());
assert!(escrow_pol.entails(control_alice).unwrap());
let h = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
let htlc_pol = StringPolicy::from_str(&format!(
"or(and(pkh(Alice),older(100)),and(pkh(Bob),sha256({})))",
h
))
.unwrap();
let auth_alice = StringPolicy::from_str("and(pkh(Alice),older(100))").unwrap();
let control_alice =
StringPolicy::from_str(&format!("or(pkh(Alice),sha256({}))", h)).unwrap();
assert!(auth_alice.entails(htlc_pol.clone()).unwrap());
assert!(htlc_pol.entails(control_alice).unwrap());
}
}