simplicity/policy/
satisfy.rs

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

simplicity/policy/
satisfy.rs
