simplicity/policy/
satisfy.rs

1// SPDX-License-Identifier: CC0-1.0
2
3use crate::analysis::Cost;
4use crate::jet::Elements;
5use crate::node::{ConstructNode, Hiding, RedeemNode};
6use crate::policy::ToXOnlyPubkey;
7use crate::types;
8use crate::{Cmr, Policy, Value};
9
10use elements::bitcoin;
11use elements::locktime::Height;
12use elements::taproot::TapLeafHash;
13use hashes::Hash;
14
15use crate::jet::elements::ElementsEnv;
16use std::convert::TryFrom;
17use std::sync::Arc;
18
19/// Type alias for 32-byte preimage.
20pub type Preimage32 = [u8; 32];
21
22/// Lookup table for signatures, hash preimages, etc.
23///
24/// Every method has a default implementation that simply returns `None`
25/// on every query. Users are expected to override the methods that they
26/// have data for.
27pub trait Satisfier<'brand, Pk: ToXOnlyPubkey> {
28    /// Given a public key, look up a Schnorr signature with that key.
29    fn lookup_tap_leaf_script_sig(&self, _: &Pk, _: &TapLeafHash) -> Option<elements::SchnorrSig> {
30        None
31    }
32
33    /// Given a SHA256 hash, look up its preimage.
34    fn lookup_sha256(&self, _: &Pk::Sha256) -> Option<Preimage32> {
35        None
36    }
37
38    /// Assert that a relative lock time is satisfied.
39    fn check_older(&self, _: elements::Sequence) -> bool {
40        false
41    }
42
43    /// Assert that an absolute lock time is satisfied.
44    fn check_after(&self, _: elements::LockTime) -> bool {
45        false
46    }
47
48    /// Returns at type inference context to be used when constructing programs.
49    ///
50    /// Unlike in Miniscript, satisfactions can't exist independently of the programs
51    /// they satisfy. Instead, they are represented by programs whose 'witness' nodes
52    /// are populated with the witness data. Therefore, during satisfaction, we must
53    /// construct a program, doing type inference along the way.
54    ///
55    /// In order to support the [`Self::lookup_asm_program`] method, which needs to
56    /// return a [`ConstructNode`] with the same type inference context as the other
57    /// parts of the constructed program, this context must be part of the satisfier
58    /// and made available through this method.
59    ///
60    /// Because of Rust's lack of specialization, this is true even for satisfiers
61    /// that do not implement [`Self::lookup_asm_program`].
62    fn inference_context(&self) -> &types::Context<'brand>;
63
64    /// Given a CMR, look up a matching assembly program.
65    ///
66    /// ## Successful execution
67    ///
68    /// It is the **responsibility of the implementor** to ensure that the returned assembly
69    /// program has sufficient witness data to successfully run on the Bit Machine.
70    ///
71    /// The execution of a program depends on the transaction environment,
72    /// so implementations should compute witness data based on that.
73    ///
74    /// If the assembly program fails to run for the current transaction environment,
75    /// then implementations should return `None`.
76    fn lookup_asm_program(&self, _: Cmr) -> Option<Arc<ConstructNode<'brand, Elements>>> {
77        None
78    }
79}
80
81impl<'brand, Pk: ToXOnlyPubkey> Satisfier<'brand, Pk>
82    for (&types::Context<'brand>, elements::Sequence)
83{
84    fn inference_context(&self) -> &types::Context<'brand> {
85        self.0
86    }
87
88    fn check_older(&self, n: elements::Sequence) -> bool {
89        use elements::bitcoin::locktime::relative::LockTime::*;
90
91        let this = match bitcoin::Sequence(self.1 .0).to_relative_lock_time() {
92            Some(x) => x,
93            None => return false,
94        };
95        let n = match bitcoin::Sequence(n.0).to_relative_lock_time() {
96            Some(x) => x,
97            None => return false,
98        };
99
100        match (n, this) {
101            (Blocks(n), Blocks(lock_time)) => n <= lock_time,
102            (Time(n), Time(lock_time)) => n <= lock_time,
103            _ => false, // Not the same units
104        }
105    }
106}
107
108impl<'brand, Pk: ToXOnlyPubkey> Satisfier<'brand, Pk>
109    for (&types::Context<'brand>, elements::LockTime)
110{
111    fn inference_context(&self) -> &types::Context<'brand> {
112        self.0
113    }
114
115    fn check_after(&self, n: elements::LockTime) -> bool {
116        use elements::LockTime::*;
117
118        match (n, self.1) {
119            (Blocks(n), Blocks(lock_time)) => n <= lock_time,
120            (Seconds(n), Seconds(lock_time)) => n <= lock_time,
121            _ => false, // Not the same units.
122        }
123    }
124}
125
126#[derive(Debug)]
127pub enum SatisfierError {
128    /// A satisfying witness for the policy could not be produced.
129    Unsatisfiable,
130    /// An assembly program failed to run on the Bit Machine.
131    ///
132    /// This can happen when the [`Satisfier::lookup_asm_program`] method is incorrectly implemented.
133    AssemblyFailed(crate::bit_machine::ExecutionError),
134}
135
136type SatResult<'brand> = Hiding<'brand, Arc<ConstructNode<'brand, Elements>>>;
137
138fn ok_if(condition: bool, expr: SatResult) -> SatResult {
139    match condition {
140        true => expr,
141        false => expr.hide(),
142    }
143}
144
145impl<Pk: ToXOnlyPubkey> Policy<Pk> {
146    fn satisfy_internal<'brand, S: Satisfier<'brand, Pk>>(
147        &self,
148        satisfier: &S,
149    ) -> Result<SatResult<'brand>, SatisfierError> {
150        let inference_context = satisfier.inference_context();
151        let node: SatResult = match *self {
152            Policy::Unsatisfiable(entropy) => {
153                super::serialize::unsatisfiable::<SatResult>(inference_context, entropy).hide()
154            }
155            Policy::Trivial => super::serialize::trivial(inference_context),
156            Policy::Key(ref key) => {
157                let signature = satisfier
158                    .lookup_tap_leaf_script_sig(key, &TapLeafHash::all_zeros())
159                    .map(|sig| sig.sig.serialize())
160                    .map(Value::u512);
161                ok_if(
162                    signature.is_some(),
163                    super::serialize::key(inference_context, key, signature),
164                )
165            }
166            Policy::After(n) => {
167                let height = Height::from_consensus(n).expect("timelock is valid");
168                ok_if(
169                    satisfier.check_after(elements::LockTime::Blocks(height)),
170                    super::serialize::after(inference_context, n),
171                )
172            }
173            Policy::Older(n) => ok_if(
174                satisfier.check_older(elements::Sequence(n.into())),
175                super::serialize::older(inference_context, n),
176            ),
177            Policy::Sha256(ref hash) => {
178                let preimage = satisfier.lookup_sha256(hash).map(Value::u256);
179                ok_if(
180                    preimage.is_some(),
181                    super::serialize::sha256::<Pk, _, _>(inference_context, hash, preimage),
182                )
183            }
184            Policy::And {
185                ref left,
186                ref right,
187            } => {
188                let left_res = left.satisfy_internal(satisfier)?;
189                let right_res = right.satisfy_internal(satisfier)?;
190                super::serialize::and(&left_res, &right_res)
191            }
192            Policy::Or {
193                ref left,
194                ref right,
195            } => {
196                let left_res = left.satisfy_internal(satisfier)?;
197                let right_res = right.satisfy_internal(satisfier)?;
198                let take_right = match (left_res.as_node(), right_res.as_node()) {
199                    (Some(left), Some(right)) => {
200                        let left_cost = left
201                            .finalize_unpruned()
202                            .expect("serialization should be sound")
203                            .bounds()
204                            .cost;
205                        let right_cost = right
206                            .finalize_unpruned()
207                            .expect("serialization should be sound")
208                            .bounds()
209                            .cost;
210                        right_cost < left_cost
211                    }
212                    (None, Some(..)) => true,
213                    (Some(..), None) => false,
214                    // If both children are unsatisfiable, then the choice doesn't matter.
215                    // The entire expression will be pruned out.
216                    (None, None) => false,
217                };
218
219                let ret = if take_right {
220                    super::serialize::or(&left_res, &right_res, Some(Value::u1(1)))
221                } else {
222                    super::serialize::or(&left_res, &right_res, Some(Value::u1(0)))
223                };
224                ok_if(
225                    left_res.as_node().is_some() || right_res.as_node().is_some(),
226                    ret,
227                )
228            }
229            Policy::Threshold(k, ref subs) => {
230                let subs_res: Vec<SatResult> = subs
231                    .iter()
232                    .map(|sub| sub.satisfy_internal(satisfier))
233                    .collect::<Result<_, SatisfierError>>()?;
234                let costs: Vec<Cost> = subs_res
235                    .iter()
236                    .map(|result| match result.as_node() {
237                        Some(node) => node
238                            .finalize_unpruned()
239                            .map(|redeem| redeem.bounds().cost)
240                            .unwrap_or(Cost::CONSENSUS_MAX),
241                        None => Cost::CONSENSUS_MAX,
242                    })
243                    .collect();
244                let selected_node_indices = {
245                    let mut indices: Vec<usize> = (0..costs.len()).collect();
246                    indices.sort_by_key(|&i| costs[i]);
247                    indices.truncate(k);
248                    indices
249                };
250                let all_selected_ok = selected_node_indices
251                    .iter()
252                    .all(|&i| subs_res[i].as_node().is_some());
253                let witness_bits: Vec<Option<Value>> = (0..subs_res.len())
254                    .map(|i| Some(Value::u1(u8::from(selected_node_indices.contains(&i)))))
255                    .collect();
256                let k = u32::try_from(k).expect("k should be less than 2^32");
257                ok_if(
258                    all_selected_ok,
259                    super::serialize::threshold(k, &subs_res, &witness_bits),
260                )
261            }
262            Policy::Assembly(cmr) => match satisfier.lookup_asm_program(cmr) {
263                Some(program) => Hiding::from(program),
264                None => Hiding::hidden(cmr, inference_context.shallow_clone()),
265            },
266        };
267        Ok(node)
268    }
269
270    /// Return the policy program with satisfying witness data.
271    ///
272    /// The program is run on the Bit Machine for pruning,
273    /// so the transaction environment needs to be provided.
274    pub fn satisfy<'brand, S: Satisfier<'brand, Pk>>(
275        &self,
276        satisfier: &S,
277        env: &ElementsEnv<Arc<elements::Transaction>>,
278    ) -> Result<Arc<RedeemNode<Elements>>, SatisfierError> {
279        let result = self.satisfy_internal(satisfier)?;
280        match result.get_node() {
281            Some(program) => program
282                .finalize_unpruned()
283                .expect("serialization should be sound")
284                .prune(env)
285                .map_err(SatisfierError::AssemblyFailed), // execution fails iff assembly fragment fails
286            None => Err(SatisfierError::Unsatisfiable),
287        }
288    }
289}
290
291#[cfg(test)]
292mod tests {
293    use super::*;
294    use crate::bit_encoding::BitCollector;
295    use crate::dag::{DagLike, NoSharing};
296    use crate::jet::elements::ElementsEnv;
297    use crate::node::{CoreConstructible, JetConstructible, SimpleFinalizer, WitnessConstructible};
298    use crate::policy::serialize;
299    use crate::{BitMachine, FailEntropy, SimplicityKey};
300    use elements::bitcoin::key::{Keypair, XOnlyPublicKey};
301    use elements::secp256k1_zkp;
302    use hashes::{sha256, Hash};
303    use std::collections::HashMap;
304    use std::sync::Arc;
305
306    pub struct PolicySatisfier<'a, 'brand, Pk: SimplicityKey> {
307        pub context: types::Context<'brand>,
308        pub preimages: HashMap<Pk::Sha256, Preimage32>,
309        pub signatures: HashMap<Pk, elements::SchnorrSig>,
310        pub assembly: HashMap<Cmr, Arc<ConstructNode<'brand, Elements>>>,
311        pub tx: &'a elements::Transaction,
312        pub index: usize,
313    }
314
315    impl<'brand, Pk: ToXOnlyPubkey> Satisfier<'brand, Pk> for PolicySatisfier<'_, 'brand, Pk> {
316        fn inference_context(&self) -> &types::Context<'brand> {
317            &self.context
318        }
319
320        fn lookup_tap_leaf_script_sig(
321            &self,
322            pk: &Pk,
323            _: &TapLeafHash,
324        ) -> Option<elements::SchnorrSig> {
325            self.signatures.get(pk).copied()
326        }
327
328        fn lookup_sha256(&self, hash: &Pk::Sha256) -> Option<Preimage32> {
329            self.preimages.get(hash).copied()
330        }
331
332        fn check_older(&self, sequence: elements::Sequence) -> bool {
333            let self_sequence = self.tx.input[self.index].sequence;
334            Satisfier::<Pk>::check_older(&(&self.context, self_sequence), sequence)
335        }
336
337        fn check_after(&self, locktime: elements::LockTime) -> bool {
338            Satisfier::<Pk>::check_after(&(&self.context, self.tx.lock_time), locktime)
339        }
340
341        fn lookup_asm_program(&self, cmr: Cmr) -> Option<Arc<ConstructNode<'brand, Elements>>> {
342            self.assembly.get(&cmr).cloned()
343        }
344    }
345
346    fn get_satisfier<'tx, 'brand>(
347        context: types::Context<'brand>,
348
349        env: &'tx ElementsEnv<Arc<elements::Transaction>>,
350    ) -> PolicySatisfier<'tx, 'brand, XOnlyPublicKey> {
351        let mut preimages = HashMap::new();
352
353        for i in 0..3 {
354            let preimage = [i; 32];
355            preimages.insert(sha256::Hash::hash(&preimage), preimage);
356        }
357
358        let secp = secp256k1_zkp::Secp256k1::new();
359        let mut rng = secp256k1_zkp::rand::rngs::ThreadRng::default();
360        let mut signatures = HashMap::new();
361
362        for _ in 0..3 {
363            let keypair = Keypair::new(&secp, &mut rng);
364            let xonly = keypair.x_only_public_key().0;
365
366            let sighash = env.c_tx_env().sighash_all();
367            let msg = secp256k1_zkp::Message::from_digest(sighash.to_byte_array());
368            let sig = elements::SchnorrSig {
369                sig: keypair.sign_schnorr(msg),
370                hash_ty: elements::SchnorrSighashType::All,
371            };
372
373            signatures.insert(xonly, sig);
374        }
375
376        PolicySatisfier {
377            context,
378            preimages,
379            signatures,
380            assembly: HashMap::new(),
381            tx: env.tx(),
382            index: env.ix() as usize,
383        }
384    }
385
386    fn execute_successful(
387        program: Arc<RedeemNode<Elements>>,
388        env: &ElementsEnv<Arc<elements::Transaction>>,
389    ) {
390        let mut mac = BitMachine::for_program(&program).unwrap();
391        assert!(mac.exec(&program, env).is_ok());
392    }
393
394    fn execute_unsuccessful(
395        program: Arc<RedeemNode<Elements>>,
396        env: &ElementsEnv<Arc<elements::Transaction>>,
397    ) {
398        let mut mac = BitMachine::for_program(&program).unwrap();
399        assert!(mac.exec(&program, env).is_err());
400    }
401
402    fn to_witness(program: &RedeemNode<Elements>) -> Vec<&Value> {
403        program
404            .post_order_iter::<NoSharing>()
405            .into_witnesses()
406            .collect()
407    }
408
409    #[test]
410    fn satisfy_unsatisfiable() {
411        types::Context::with_context(|ctx| {
412            let env = ElementsEnv::dummy();
413            let satisfier = get_satisfier(ctx, &env);
414            let policy = Policy::Unsatisfiable(FailEntropy::ZERO);
415
416            assert!(policy.satisfy(&satisfier, &env).is_err());
417
418            let commit = policy.commit().expect("no asm");
419            let program = commit
420                .finalize(&mut SimpleFinalizer::new(std::iter::empty()))
421                .expect("finalize");
422
423            execute_unsuccessful(program, &env);
424        });
425    }
426
427    #[test]
428    fn satisfy_trivial() {
429        types::Context::with_context(|ctx| {
430            let env = ElementsEnv::dummy();
431            let satisfier = get_satisfier(ctx, &env);
432            let policy = Policy::Trivial;
433
434            let program = policy.satisfy(&satisfier, &env).expect("satisfiable");
435            let witness = to_witness(&program);
436            assert!(witness.is_empty());
437
438            execute_successful(program, &env);
439        });
440    }
441
442    #[test]
443    fn satisfy_pk() {
444        types::Context::with_context(|ctx| {
445            let env = ElementsEnv::dummy();
446            let satisfier = get_satisfier(ctx, &env);
447            let mut it = satisfier.signatures.keys();
448            let xonly = it.next().unwrap();
449            let policy = Policy::Key(*xonly);
450
451            let program = policy.satisfy(&satisfier, &env).expect("satisfiable");
452            let witness = to_witness(&program);
453            assert_eq!(1, witness.len());
454
455            let sighash = env.c_tx_env().sighash_all();
456            let message = secp256k1_zkp::Message::from_digest(sighash.to_byte_array());
457            let signature_bytes = witness[0]
458                .iter_padded()
459                .try_collect_bytes()
460                .expect("to bytes");
461            let signature = secp256k1_zkp::schnorr::Signature::from_slice(&signature_bytes)
462                .expect("to signature");
463            assert!(signature.verify(&message, xonly).is_ok());
464
465            execute_successful(program, &env);
466        });
467    }
468
469    #[test]
470    fn satisfy_sha256() {
471        types::Context::with_context(|ctx| {
472            let env = ElementsEnv::dummy();
473            let satisfier = get_satisfier(ctx, &env);
474            let mut it = satisfier.preimages.keys();
475            let image = *it.next().unwrap();
476            let policy = Policy::Sha256(image);
477
478            let program = policy.satisfy(&satisfier, &env).expect("satisfiable");
479            let witness = to_witness(&program);
480            assert_eq!(1, witness.len());
481
482            let witness_bytes = witness[0]
483                .iter_padded()
484                .try_collect_bytes()
485                .expect("to bytes");
486            let witness_preimage =
487                Preimage32::try_from(witness_bytes.as_slice()).expect("to array");
488            let preimage = *satisfier.preimages.get(&image).unwrap();
489            assert_eq!(preimage, witness_preimage);
490
491            execute_successful(program, &env);
492        });
493    }
494
495    #[test]
496    fn satisfy_after() {
497        types::Context::with_context(|ctx| {
498            let height = Height::from_consensus(42).unwrap();
499            let env = ElementsEnv::dummy_with(
500                elements::LockTime::Blocks(height),
501                elements::Sequence::ZERO,
502            );
503            let satisfier = get_satisfier(ctx, &env);
504
505            let policy0 = Policy::After(41);
506            let program = policy0.satisfy(&satisfier, &env).expect("satisfiable");
507            let witness = to_witness(&program);
508            assert!(witness.is_empty());
509            execute_successful(program, &env);
510
511            let policy1 = Policy::After(42);
512            let program = policy1.satisfy(&satisfier, &env).expect("satisfiable");
513            let witness = to_witness(&program);
514            assert!(witness.is_empty());
515            execute_successful(program, &env);
516
517            let policy2 = Policy::After(43);
518            assert!(policy2.satisfy(&satisfier, &env).is_err(), "unsatisfiable");
519        });
520    }
521
522    #[test]
523    fn satisfy_older() {
524        types::Context::with_context(|ctx| {
525            let env = ElementsEnv::dummy_with(
526                elements::LockTime::ZERO,
527                elements::Sequence::from_consensus(42),
528            );
529            let satisfier = get_satisfier(ctx, &env);
530
531            let policy0 = Policy::Older(41);
532            let program = policy0.satisfy(&satisfier, &env).expect("satisfiable");
533            let witness = to_witness(&program);
534            assert!(witness.is_empty());
535            execute_successful(program, &env);
536
537            let policy1 = Policy::Older(42);
538            let program = policy1.satisfy(&satisfier, &env).expect("satisfiable");
539            let witness = to_witness(&program);
540            assert!(witness.is_empty());
541            execute_successful(program, &env);
542
543            let policy2 = Policy::Older(43);
544            assert!(policy2.satisfy(&satisfier, &env).is_err(), "unsatisfiable");
545        });
546    }
547
548    #[test]
549    fn satisfy_and() {
550        types::Context::with_context(|ctx| {
551            let env = ElementsEnv::dummy();
552            let satisfier = get_satisfier(ctx, &env);
553            let images: Vec<_> = satisfier.preimages.keys().copied().collect();
554            let preimages: Vec<_> = images
555                .iter()
556                .map(|x| satisfier.preimages.get(x).unwrap())
557                .collect();
558
559            // Policy 0
560
561            let policy0 = Policy::And {
562                left: Arc::new(Policy::Sha256(images[0])),
563                right: Arc::new(Policy::Sha256(images[1])),
564            };
565            let program = policy0.satisfy(&satisfier, &env).expect("satisfiable");
566            let witness = to_witness(&program);
567            assert_eq!(2, witness.len());
568
569            for i in 0..2 {
570                let preimage_bytes = witness[i]
571                    .iter_padded()
572                    .try_collect_bytes()
573                    .expect("to bytes");
574                let witness_preimage =
575                    Preimage32::try_from(preimage_bytes.as_slice()).expect("to array");
576                assert_eq!(preimages[i], &witness_preimage);
577            }
578
579            execute_successful(program, &env);
580
581            // Policy 1
582
583            let policy1 = Policy::And {
584                left: Arc::new(Policy::Sha256(sha256::Hash::from_byte_array([0; 32]))),
585                right: Arc::new(Policy::Sha256(images[1])),
586            };
587            assert!(policy1.satisfy(&satisfier, &env).is_err());
588
589            // Policy 2
590
591            let policy2 = Policy::And {
592                left: Arc::new(Policy::Sha256(images[0])),
593                right: Arc::new(Policy::Sha256(sha256::Hash::from_byte_array([0; 32]))),
594            };
595            assert!(policy2.satisfy(&satisfier, &env).is_err());
596        });
597    }
598
599    #[test]
600    fn satisfy_or() {
601        types::Context::with_context(|ctx| {
602            let env = ElementsEnv::dummy();
603            let satisfier = get_satisfier(ctx, &env);
604            let images: Vec<_> = satisfier.preimages.keys().copied().collect();
605            let preimages: Vec<_> = images.iter().map(|x| satisfier.preimages[x]).collect();
606
607            let assert_branch = |policy: &Policy<XOnlyPublicKey>, bit: bool| {
608                let program = policy.satisfy(&satisfier, &env).expect("satisfiable");
609                let witness = to_witness(&program);
610                assert_eq!(2, witness.len());
611
612                assert_eq!(Value::u1(u8::from(bit)), *witness[0]);
613                let preimage_bytes = witness[1]
614                    .iter_padded()
615                    .try_collect_bytes()
616                    .expect("to bytes");
617                let witness_preimage =
618                    Preimage32::try_from(preimage_bytes.as_slice()).expect("to array");
619                assert_eq!(preimages[usize::from(bit)], witness_preimage);
620
621                execute_successful(program, &env);
622            };
623
624            // Policy 0
625
626            let policy0 = Policy::Or {
627                left: Arc::new(Policy::Sha256(images[0])),
628                right: Arc::new(Policy::Sha256(images[1])),
629            };
630            assert_branch(&policy0, false);
631
632            // Policy 1
633
634            let policy1 = Policy::Or {
635                left: Arc::new(Policy::Sha256(images[0])),
636                right: Arc::new(Policy::Sha256(sha256::Hash::from_byte_array([1; 32]))),
637            };
638            assert_branch(&policy1, false);
639
640            // Policy 2
641
642            let policy2 = Policy::Or {
643                left: Arc::new(Policy::Sha256(sha256::Hash::from_byte_array([0; 32]))),
644                right: Arc::new(Policy::Sha256(images[1])),
645            };
646            assert_branch(&policy2, true);
647
648            // Policy 3
649
650            let policy3 = Policy::Or {
651                left: Arc::new(Policy::Sha256(sha256::Hash::from_byte_array([0; 32]))),
652                right: Arc::new(Policy::Sha256(sha256::Hash::from_byte_array([1; 32]))),
653            };
654            assert!(policy3.satisfy(&satisfier, &env).is_err());
655        });
656    }
657
658    #[test]
659    fn satisfy_thresh() {
660        types::Context::with_context(|ctx| {
661            let env = ElementsEnv::dummy();
662            let satisfier = get_satisfier(ctx, &env);
663            let images: Vec<_> = satisfier.preimages.keys().copied().collect();
664            let preimages: Vec<_> = images
665                .iter()
666                .map(|x| satisfier.preimages.get(x).unwrap())
667                .collect();
668
669            let assert_branches = |policy: &Policy<XOnlyPublicKey>, bits: &[bool]| {
670                let program = policy.satisfy(&satisfier, &env).expect("satisfiable");
671                let witness = to_witness(&program);
672                assert_eq!(
673                    witness.len(),
674                    bits.len() + bits.iter().filter(|b| **b).count(),
675                );
676
677                let mut witidx = 0;
678                for (bit_n, bit) in bits.iter().copied().enumerate() {
679                    assert_eq!(*witness[witidx], Value::u1(bit.into()));
680                    witidx += 1;
681                    if bit {
682                        let preimage_bytes = witness[witidx]
683                            .iter_padded()
684                            .try_collect_bytes()
685                            .expect("to bytes");
686                        let witness_preimage =
687                            Preimage32::try_from(preimage_bytes.as_slice()).expect("to array");
688                        assert_eq!(preimages[bit_n], &witness_preimage);
689                        witidx += 1;
690                    }
691                }
692
693                execute_successful(program, &env);
694            };
695
696            let image_from_bit = |bit: bool, j: u8| {
697                if bit {
698                    images[j as usize]
699                } else {
700                    sha256::Hash::from_byte_array([j; 32])
701                }
702            };
703
704            for &bit0 in &[true, false] {
705                let image0 = image_from_bit(bit0, 0);
706
707                for &bit1 in &[true, false] {
708                    let image1 = image_from_bit(bit1, 1);
709
710                    for &bit2 in &[true, false] {
711                        let image2 = image_from_bit(bit2, 2);
712
713                        let policy = Policy::Threshold(
714                            2,
715                            vec![
716                                Policy::Sha256(image0),
717                                Policy::Sha256(image1),
718                                Policy::Sha256(image2),
719                            ],
720                        );
721
722                        match u8::from(bit0) + u8::from(bit1) + u8::from(bit2) {
723                            3 => assert_branches(&policy, &[bit0, bit1, false]),
724                            2 => assert_branches(&policy, &[bit0, bit1, bit2]),
725                            _ => assert!(policy.satisfy(&satisfier, &env).is_err()),
726                        }
727                    }
728                }
729            }
730        });
731    }
732
733    #[test]
734    fn satisfy_asm() {
735        types::Context::with_context(|ctx| {
736            let env = ElementsEnv::dummy();
737            let mut satisfier = get_satisfier(ctx, &env);
738
739            let mut assert_branch = |witness0: Value, witness1: Value| {
740                let ctx = &satisfier.context;
741                let asm_program = serialize::verify_bexp(
742                    &Arc::<ConstructNode<Elements>>::pair(
743                        &Arc::<ConstructNode<Elements>>::witness(ctx, Some(witness0.clone())),
744                        &Arc::<ConstructNode<Elements>>::witness(ctx, Some(witness1.clone())),
745                    )
746                    .expect("sound types"),
747                    &Arc::<ConstructNode<Elements>>::jet(ctx, Elements::Eq8),
748                );
749                let cmr = asm_program.cmr();
750                satisfier.assembly.insert(cmr, asm_program);
751
752                let policy = Policy::Assembly(cmr);
753                let result = policy.satisfy(&satisfier, &env);
754
755                if witness0 == witness1 {
756                    let program = result.expect("policy should be satisfiable");
757                    let witness = to_witness(&program);
758
759                    assert_eq!(2, witness.len());
760                    assert_eq!(&witness0, witness[0]);
761                    assert_eq!(&witness1, witness[1]);
762
763                    execute_successful(program, &env);
764                } else {
765                    assert!(matches!(result, Err(SatisfierError::AssemblyFailed(..))));
766                }
767            };
768
769            for a in 0..2 {
770                for b in 0..2 {
771                    assert_branch(Value::u8(a), Value::u8(b))
772                }
773            }
774        });
775    }
776
777    #[test]
778    #[ignore]
779    fn satisfy_asm_and_older() {
780        types::Context::with_context(|ctx| {
781            let env = ElementsEnv::dummy_with(
782                elements::LockTime::ZERO,
783                elements::Sequence::from_consensus(42),
784            );
785            let mut satisfier = get_satisfier(ctx, &env);
786
787            let mut assert_branch = |witness0: Value, witness1: Value| {
788                let ctx = &satisfier.context;
789                let asm_program = serialize::verify_bexp(
790                    &Arc::<ConstructNode<Elements>>::pair(
791                        &Arc::<ConstructNode<Elements>>::witness(ctx, Some(witness0.clone())),
792                        &Arc::<ConstructNode<Elements>>::witness(ctx, Some(witness1.clone())),
793                    )
794                    .expect("sound types"),
795                    &Arc::<ConstructNode<Elements>>::jet(ctx, Elements::Eq8),
796                );
797                let cmr = asm_program.cmr();
798                satisfier.assembly.insert(cmr, asm_program);
799
800                let policy = Policy::And {
801                    left: Arc::new(Policy::Assembly(cmr)),
802                    right: Arc::new(Policy::Older(41)),
803                };
804                let result = policy.satisfy(&satisfier, &env);
805
806                if witness0 == witness1 {
807                    let program = result.expect("policy should be satisfiable");
808                    let witness = to_witness(&program);
809
810                    assert_eq!(2, witness.len());
811                    assert_eq!(&witness0, witness[0]);
812                    assert_eq!(&witness1, witness[1]);
813
814                    execute_successful(program, &env);
815                } else {
816                    assert!(matches!(result, Err(SatisfierError::AssemblyFailed(..))));
817                }
818            };
819
820            for a in 0..2 {
821                for b in 0..2 {
822                    assert_branch(Value::u8(a), Value::u8(b))
823                }
824            }
825        });
826    }
827}
simplicity/policy/satisfy.rs

simplicity/policy/
satisfy.rs
