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

simplicity/policy/
satisfy.rs
