simplicity/node/
construct.rs

1// SPDX-License-Identifier: CC0-1.0
2
3use crate::dag::{InternalSharing, PostOrderIterItem};
4use crate::jet::{Jet, JetEnvironment};
5use crate::types::{self, arrow::Arrow};
6use crate::{encode, BitIter, BitWriter, Cmr, FailEntropy, FinalizeError, RedeemNode, Value, Word};
7
8use std::io;
9use std::marker::PhantomData;
10use std::sync::Arc;
11
12use super::{
13    Commit, CommitData, CommitNode, Converter, Inner, Marker, NoDisconnect, NoWitness, Node,
14    Redeem, RedeemData,
15};
16use super::{CoreConstructible, DisconnectConstructible, JetConstructible, WitnessConstructible};
17
18/// ID used to share [`ConstructNode`]s.
19///
20/// This is impossible to construct, which is a promise that it is impossible
21/// to share [`ConstructNode`]s.
22#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash)]
23pub enum ConstructId {}
24
25#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash)]
26pub struct Construct<'brand> {
27    /// Makes the type non-constructible.
28    never: std::convert::Infallible,
29    /// Required by Rust.
30    phantom: std::marker::PhantomData<&'brand ()>,
31}
32
33impl<'brand> Marker for Construct<'brand> {
34    type CachedData = ConstructData<'brand>;
35    type Witness = Option<Value>;
36    type Disconnect = Option<Arc<ConstructNode<'brand>>>;
37    type SharingId = ConstructId;
38
39    fn compute_sharing_id(_: Cmr, _: &ConstructData<'brand>) -> Option<ConstructId> {
40        None
41    }
42}
43
44pub type ConstructNode<'brand> = Node<Construct<'brand>>;
45
46impl<'brand> ConstructNode<'brand> {
47    /// Accessor for the node's arrow
48    pub fn arrow(&self) -> &Arrow<'brand> {
49        self.data.arrow()
50    }
51
52    /// Sets the source and target type of the node to unit
53    pub fn set_arrow_to_program(&self) -> Result<(), types::Error> {
54        let ctx = self.data.inference_context();
55        let unit_ty = types::Type::unit(ctx);
56        ctx.unify(
57            &self.arrow().source,
58            &unit_ty,
59            "setting root source to unit",
60        )?;
61        ctx.unify(
62            &self.arrow().target,
63            &unit_ty,
64            "setting root target to unit",
65        )?;
66        Ok(())
67    }
68
69    /// Convert a [`ConstructNode`] to a [`CommitNode`] by finalizing all of the types.
70    ///
71    /// Also sets the source and target type of this node to unit. This is almost
72    /// certainly what you want, since the resulting `CommitNode` cannot be further
73    /// composed, and needs to be 1->1 to go on-chain. But if you don't, call
74    /// [`Self::finalize_types_non_program`] instead.
75    pub fn finalize_types(&self) -> Result<Arc<CommitNode>, types::Error> {
76        self.set_arrow_to_program()?;
77        self.finalize_types_non_program()
78    }
79
80    /// Convert a [`ConstructNode`] to a [`CommitNode`] by finalizing all of the types.
81    ///
82    /// Does *not* sets the source and target type of this node to unit.
83    pub fn finalize_types_non_program(&self) -> Result<Arc<CommitNode>, types::Error> {
84        struct FinalizeTypes;
85
86        impl<'brand> Converter<Construct<'brand>, Commit> for FinalizeTypes {
87            type Error = types::Error;
88
89            fn convert_witness(
90                &mut self,
91                _: &PostOrderIterItem<&ConstructNode>,
92                _: &Option<Value>,
93            ) -> Result<NoWitness, Self::Error> {
94                Ok(NoWitness)
95            }
96
97            fn convert_disconnect(
98                &mut self,
99                _: &PostOrderIterItem<&ConstructNode>,
100                _: Option<&Arc<CommitNode>>,
101                _: &Option<Arc<ConstructNode>>,
102            ) -> Result<NoDisconnect, Self::Error> {
103                Ok(NoDisconnect)
104            }
105
106            fn convert_data(
107                &mut self,
108                data: &PostOrderIterItem<&ConstructNode>,
109                inner: Inner<&Arc<CommitNode>, &NoDisconnect, &NoWitness>,
110            ) -> Result<Arc<CommitData>, Self::Error> {
111                let converted_data = inner.map(|node| node.cached_data());
112                CommitData::new(&data.node.data.arrow, converted_data).map(Arc::new)
113            }
114        }
115
116        self.convert::<InternalSharing, _, _>(&mut FinalizeTypes)
117    }
118
119    /// Finalize the witness program as an unpruned redeem program.
120    ///
121    /// Witness nodes must be populated with sufficient data,
122    /// to ensure that the resulting redeem program successfully runs on the Bit Machine.
123    /// Furthermore, **all** disconnected branches must be populated,
124    /// even those that are not executed.
125    ///
126    /// The resulting redeem program is **not pruned**.
127    ///
128    /// ## See
129    ///
130    /// [`RedeemNode::prune`]
131    pub fn finalize_unpruned(&self) -> Result<Arc<RedeemNode>, FinalizeError> {
132        struct Finalizer(PhantomData<()>);
133
134        impl<'brand> Converter<Construct<'brand>, Redeem> for Finalizer {
135            type Error = FinalizeError;
136
137            fn convert_witness(
138                &mut self,
139                data: &PostOrderIterItem<&ConstructNode>,
140                wit: &Option<Value>,
141            ) -> Result<Value, Self::Error> {
142                if let Some(ref wit) = wit {
143                    Ok(wit.shallow_clone())
144                } else {
145                    // We insert a zero value into unpopulated witness nodes,
146                    // assuming that this node will later be pruned out of the program.
147                    //
148                    // Pruning requires running a program on the Bit Machine,
149                    // which in turn requires a program with fully populated witness nodes.
150                    // It would be horrible UX to force the caller to provide witness data
151                    // even for unexecuted branches, so we insert zero values here.
152                    //
153                    // If this node is executed after all, then the caller can fix the witness
154                    // data based on the returned execution error.
155                    //
156                    // Zero values may "accidentally" satisfy a program even if the caller
157                    // didn't provide any witness data. However, this is only the case for the
158                    // most trivial programs. The only place where we must be careful is our
159                    // unit tests, which tend to include these kinds of trivial programs.
160                    let ty = data
161                        .node
162                        .arrow()
163                        .target
164                        .finalize()
165                        .map_err(FinalizeError::Type)?;
166                    Ok(Value::zero(&ty))
167                }
168            }
169
170            fn convert_disconnect(
171                &mut self,
172                _: &PostOrderIterItem<&ConstructNode>,
173                maybe_converted: Option<&Arc<RedeemNode>>,
174                _: &Option<Arc<ConstructNode>>,
175            ) -> Result<Arc<RedeemNode>, Self::Error> {
176                if let Some(child) = maybe_converted {
177                    Ok(Arc::clone(child))
178                } else {
179                    Err(FinalizeError::DisconnectRedeemTime)
180                }
181            }
182
183            fn convert_data(
184                &mut self,
185                data: &PostOrderIterItem<&ConstructNode>,
186                inner: Inner<&Arc<RedeemNode>, &Arc<RedeemNode>, &Value>,
187            ) -> Result<Arc<RedeemData>, Self::Error> {
188                let converted_data = inner
189                    .map(|node| node.cached_data())
190                    .map_disconnect(|node| node.cached_data())
191                    .map_witness(Value::shallow_clone);
192                Ok(Arc::new(RedeemData::new(
193                    data.node.arrow().finalize().map_err(FinalizeError::Type)?,
194                    converted_data,
195                )))
196            }
197        }
198
199        self.convert::<InternalSharing, _, _>(&mut Finalizer(PhantomData))
200    }
201
202    /// Finalize the witness program as a pruned redeem program.
203    ///
204    /// Witness nodes must be populated with sufficient data,
205    /// to ensure that the resulting redeem program successfully runs on the Bit Machine.
206    /// Furthermore, **all** disconnected branches must be populated,
207    /// even those that are not executed.
208    ///
209    /// The resulting redeem program is **pruned** based on the given transaction environment.
210    ///
211    /// ## See
212    ///
213    /// [`RedeemNode::prune`]
214    pub fn finalize_pruned<JE: JetEnvironment>(
215        &self,
216        env: &JE,
217    ) -> Result<Arc<RedeemNode>, FinalizeError> {
218        let unpruned = self.finalize_unpruned()?;
219        unpruned.prune(env).map_err(FinalizeError::Execution)
220    }
221
222    /// Decode a Simplicity expression from bits, without witness data.
223    ///
224    /// # Usage
225    ///
226    /// Use this method only if the serialization **does not** include the witness data.
227    /// This means, the program simply has no witness during commitment,
228    /// or the witness is provided by other means.
229    ///
230    /// If the serialization contains the witness data, then use [`crate::RedeemNode::decode()`].
231    pub fn decode<I: Iterator<Item = u8>, J: Jet>(
232        context: &types::Context<'brand>,
233        mut bits: BitIter<I>,
234    ) -> Result<Arc<Self>, crate::decode::Error> {
235        let res = crate::decode::decode_expression::<I, J>(context, &mut bits)?;
236        bits.close()?;
237        Ok(res)
238    }
239
240    #[cfg(feature = "base64")]
241    #[allow(clippy::should_implement_trait)] // returns Arc<Self>, needs tyctx
242    pub fn from_str<J: Jet>(
243        context: &types::Context<'brand>,
244        s: &str,
245    ) -> Result<Arc<Self>, crate::ParseError> {
246        use crate::base64::engine::general_purpose;
247        use crate::base64::Engine as _;
248
249        let v = general_purpose::STANDARD
250            .decode(s)
251            .map_err(crate::ParseError::Base64)?;
252        let iter = crate::BitIter::new(v.into_iter());
253        Self::decode::<_, J>(context, iter)
254            .map_err(crate::DecodeError::Decode)
255            .map_err(crate::ParseError::Decode)
256    }
257
258    /// Encode a Simplicity expression to bits, with no witness data
259    #[deprecated(since = "0.5.0", note = "use Self::encode_without_witness instead")]
260    pub fn encode(&self, w: &mut BitWriter<&mut dyn io::Write>) -> io::Result<usize> {
261        let program_bits = encode::encode_program(self, w)?;
262        w.flush_all()?;
263        Ok(program_bits)
264    }
265}
266
267#[derive(Clone, Debug)]
268pub struct ConstructData<'brand> {
269    arrow: Arrow<'brand>,
270}
271
272impl<'brand> ConstructData<'brand> {
273    /// Constructs a new [`ConstructData`] from an (unfinalized) type arrow
274    pub fn new(arrow: Arrow<'brand>) -> Self {
275        ConstructData { arrow }
276    }
277
278    /// Accessor for the node's arrow
279    pub fn arrow(&self) -> &Arrow<'brand> {
280        &self.arrow
281    }
282}
283
284impl<'brand> CoreConstructible<'brand> for ConstructData<'brand> {
285    fn iden(inference_context: &types::Context<'brand>) -> Self {
286        ConstructData {
287            arrow: Arrow::iden(inference_context),
288        }
289    }
290
291    fn unit(inference_context: &types::Context<'brand>) -> Self {
292        ConstructData {
293            arrow: Arrow::unit(inference_context),
294        }
295    }
296
297    fn injl(child: &Self) -> Self {
298        ConstructData {
299            arrow: Arrow::injl(&child.arrow),
300        }
301    }
302
303    fn injr(child: &Self) -> Self {
304        ConstructData {
305            arrow: Arrow::injr(&child.arrow),
306        }
307    }
308
309    fn take(child: &Self) -> Self {
310        ConstructData {
311            arrow: Arrow::take(&child.arrow),
312        }
313    }
314
315    fn drop_(child: &Self) -> Self {
316        ConstructData {
317            arrow: Arrow::drop_(&child.arrow),
318        }
319    }
320
321    fn comp(left: &Self, right: &Self) -> Result<Self, types::Error> {
322        Ok(ConstructData {
323            arrow: Arrow::comp(&left.arrow, &right.arrow)?,
324        })
325    }
326
327    fn case(left: &Self, right: &Self) -> Result<Self, types::Error> {
328        Ok(ConstructData {
329            arrow: Arrow::case(&left.arrow, &right.arrow)?,
330        })
331    }
332
333    fn assertl(left: &Self, right: Cmr) -> Result<Self, types::Error> {
334        Ok(ConstructData {
335            arrow: Arrow::assertl(&left.arrow, right)?,
336        })
337    }
338
339    fn assertr(left: Cmr, right: &Self) -> Result<Self, types::Error> {
340        Ok(ConstructData {
341            arrow: Arrow::assertr(left, &right.arrow)?,
342        })
343    }
344
345    fn pair(left: &Self, right: &Self) -> Result<Self, types::Error> {
346        Ok(ConstructData {
347            arrow: Arrow::pair(&left.arrow, &right.arrow)?,
348        })
349    }
350
351    fn fail(inference_context: &types::Context<'brand>, entropy: FailEntropy) -> Self {
352        ConstructData {
353            arrow: Arrow::fail(inference_context, entropy),
354        }
355    }
356
357    fn const_word(inference_context: &types::Context<'brand>, word: Word) -> Self {
358        ConstructData {
359            arrow: Arrow::const_word(inference_context, word),
360        }
361    }
362
363    fn inference_context(&self) -> &types::Context<'brand> {
364        self.arrow.inference_context()
365    }
366}
367
368impl<'brand> DisconnectConstructible<'brand, Option<Arc<ConstructNode<'brand>>>>
369    for ConstructData<'brand>
370{
371    fn disconnect(
372        left: &Self,
373        right: &Option<Arc<ConstructNode<'brand>>>,
374    ) -> Result<Self, types::Error> {
375        let right = right.as_ref();
376        Ok(ConstructData {
377            arrow: Arrow::disconnect(&left.arrow, &right.map(|n| n.arrow()))?,
378        })
379    }
380}
381
382impl<'brand> WitnessConstructible<'brand, Option<Value>> for ConstructData<'brand> {
383    fn witness(inference_context: &types::Context<'brand>, _witness: Option<Value>) -> Self {
384        ConstructData {
385            arrow: Arrow::witness(inference_context, NoWitness),
386        }
387    }
388}
389
390impl<'brand> JetConstructible<'brand> for ConstructData<'brand> {
391    fn jet(inference_context: &types::Context<'brand>, jet: &dyn Jet) -> Self {
392        ConstructData {
393            arrow: Arrow::jet(inference_context, jet),
394        }
395    }
396}
397
398#[cfg(test)]
399mod tests {
400    use super::*;
401    use crate::types::Final;
402    use crate::Value;
403
404    #[test]
405    fn occurs_check_error() {
406        types::Context::with_context(|ctx| {
407            let iden = Arc::<ConstructNode>::iden(&ctx);
408            let node = Arc::<ConstructNode>::disconnect(&iden, &Some(Arc::clone(&iden))).unwrap();
409
410            assert!(matches!(
411                node.finalize_types_non_program(),
412                Err(types::Error::OccursCheck { .. }),
413            ));
414        });
415    }
416
417    #[test]
418    fn occurs_check_2() {
419        types::Context::with_context(|ctx| {
420            // A more complicated occurs-check test that caused a deadlock in the past.
421            let iden = Arc::<ConstructNode>::iden(&ctx);
422            let injr = Arc::<ConstructNode>::injr(&iden);
423            let pair = Arc::<ConstructNode>::pair(&injr, &iden).unwrap();
424            let drop = Arc::<ConstructNode>::drop_(&pair);
425
426            let case1 = Arc::<ConstructNode>::case(&drop, &drop).unwrap();
427            let case2 = Arc::<ConstructNode>::case(&case1, &case1).unwrap();
428
429            let comp1 = Arc::<ConstructNode>::comp(&case2, &case2).unwrap();
430            let comp2 = Arc::<ConstructNode>::comp(&comp1, &case1).unwrap();
431
432            assert!(matches!(
433                comp2.finalize_types_non_program(),
434                Err(types::Error::OccursCheck { .. }),
435            ));
436        });
437    }
438
439    #[test]
440    fn occurs_check_3() {
441        types::Context::with_context(|ctx| {
442            // A similar example that caused a slightly different deadlock in the past.
443            let wit = Arc::<ConstructNode>::witness(&ctx, None);
444            let drop = Arc::<ConstructNode>::drop_(&wit);
445
446            let comp1 = Arc::<ConstructNode>::comp(&drop, &drop).unwrap();
447            let comp2 = Arc::<ConstructNode>::comp(&comp1, &comp1).unwrap();
448            let comp3 = Arc::<ConstructNode>::comp(&comp2, &comp2).unwrap();
449            let comp4 = Arc::<ConstructNode>::comp(&comp3, &comp3).unwrap();
450            let comp5 = Arc::<ConstructNode>::comp(&comp4, &comp4).unwrap();
451
452            let case = Arc::<ConstructNode>::case(&comp5, &comp4).unwrap();
453            let drop2 = Arc::<ConstructNode>::drop_(&case);
454            let case2 = Arc::<ConstructNode>::case(&drop2, &case).unwrap();
455            let comp6 = Arc::<ConstructNode>::comp(&case2, &case2).unwrap();
456            let case3 = Arc::<ConstructNode>::case(&comp6, &comp6).unwrap();
457
458            let comp7 = Arc::<ConstructNode>::comp(&case3, &case3).unwrap();
459            let comp8 = Arc::<ConstructNode>::comp(&comp7, &comp7).unwrap();
460
461            assert!(matches!(
462                comp8.finalize_types_non_program(),
463                Err(types::Error::OccursCheck { .. }),
464            ));
465        });
466    }
467
468    #[test]
469    fn type_check_error() {
470        types::Context::with_context(|ctx| {
471            let unit = Arc::<ConstructNode>::unit(&ctx);
472            let case = Arc::<ConstructNode>::case(&unit, &unit).unwrap();
473
474            assert!(matches!(
475                Arc::<ConstructNode>::disconnect(&case, &Some(unit)),
476                Err(types::Error::Bind { .. }),
477            ));
478        });
479    }
480
481    #[test]
482    fn scribe() {
483        // Ok to use same type inference context for all the below tests,
484        // since everything has concrete types and anyway we only care
485        // about CMRs, for which type inference is irrelevant.
486        types::Context::with_context(|ctx| {
487            let unit = Arc::<ConstructNode>::unit(&ctx);
488            let bit0 = Arc::<ConstructNode>::const_word(&ctx, Word::u1(0));
489            let bit1 = Arc::<ConstructNode>::const_word(&ctx, Word::u1(1));
490
491            assert_eq!(
492                unit.cmr(),
493                Arc::<ConstructNode>::scribe(&ctx, &Value::unit()).cmr()
494            );
495            assert_eq!(
496                bit0.cmr(),
497                Arc::<ConstructNode>::scribe(&ctx, &Value::u1(0)).cmr()
498            );
499            assert_eq!(
500                bit1.cmr(),
501                Arc::<ConstructNode>::scribe(&ctx, &Value::u1(1)).cmr()
502            );
503            assert_eq!(
504                Arc::<ConstructNode>::const_word(&ctx, Word::u2(1)).cmr(),
505                Arc::<ConstructNode>::scribe(&ctx, &Value::u2(1)).cmr()
506            );
507            assert_eq!(
508                Arc::<ConstructNode>::injl(&bit0).cmr(),
509                Arc::<ConstructNode>::scribe(&ctx, &Value::left(Value::u1(0), Final::unit())).cmr()
510            );
511            assert_eq!(
512                Arc::<ConstructNode>::injr(&bit1).cmr(),
513                Arc::<ConstructNode>::scribe(&ctx, &Value::right(Final::unit(), Value::u1(1)))
514                    .cmr()
515            );
516            assert_eq!(
517                Arc::<ConstructNode>::pair(&unit, &unit).unwrap().cmr(),
518                Arc::<ConstructNode>::scribe(&ctx, &Value::product(Value::unit(), Value::unit()))
519                    .cmr()
520            );
521        });
522    }
523
524    #[test]
525    fn regression_286_1() {
526        // This is the smallest pure Simplicity program I was able to find that exhibits the bad
527        // behavior seen in https://github.com/BlockstreamResearch/rust-simplicity/issues/286
528        types::Context::with_context(|ctx| {
529            let cmr = Cmr::from_byte_array([0xde; 32]);
530
531            let u0 = Arc::<ConstructNode>::unit(&ctx);
532            let i1 = Arc::<ConstructNode>::injl(&u0);
533            let i2 = Arc::<ConstructNode>::injr(&i1);
534            let i3 = Arc::<ConstructNode>::injr(&i2);
535            let i4 = Arc::<ConstructNode>::injl(&i3);
536            let u5 = Arc::<ConstructNode>::unit(&ctx);
537            let i6 = Arc::<ConstructNode>::injl(&u5);
538            let i7 = Arc::<ConstructNode>::injr(&i6);
539            let p8 = Arc::<ConstructNode>::pair(&i4, &i7).unwrap();
540            let u9 = Arc::<ConstructNode>::unit(&ctx);
541            let a10 = Arc::<ConstructNode>::assertr(cmr, &u9).unwrap();
542            let u11 = Arc::<ConstructNode>::unit(&ctx);
543            let a12 = Arc::<ConstructNode>::assertr(cmr, &u11).unwrap();
544            let a13 = Arc::<ConstructNode>::assertl(&a12, cmr).unwrap();
545            let c14 = Arc::<ConstructNode>::case(&a10, &a13).unwrap();
546            let c15 = Arc::<ConstructNode>::comp(&p8, &c14).unwrap();
547
548            let finalized: Arc<CommitNode> = c15.finalize_types().unwrap();
549            let prog = finalized.to_vec_without_witness();
550            // In #286 we are encoding correctly...
551            assert_eq!(
552                hex::DisplayHex::as_hex(&prog).to_string(),
553                "dc920a28812b6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f243090e00b10e00680",
554            );
555
556            let prog = BitIter::from(prog);
557            let decode = CommitNode::decode::<_, crate::jet::Core>(prog).unwrap();
558
559            // ...but then during decoding we read the program incorrectly and this assertion fails.
560            assert_eq!(finalized, decode);
561        });
562    }
563
564    #[test]
565    fn regression_286_2() {
566        // This one is smaller because it starts with a witness node which has a large type.
567        // This is a bit easier to grok but can't be serialized as a complete/valid program
568        // without providing the witness data, which limits its ability to share with the
569        // other libraries.
570        //
571        // It also exhibits the bug earlier than the other one -- it *should* just fail to
572        // typecheck and not be constructible. So we can't get an encoding of it.
573        types::Context::with_context(|ctx| {
574            let w0 = Arc::<ConstructNode>::witness(&ctx, None);
575            let i1 = Arc::<ConstructNode>::iden(&ctx);
576            let d2 = Arc::<ConstructNode>::drop_(&i1);
577            let i3 = Arc::<ConstructNode>::iden(&ctx);
578            let i4 = Arc::<ConstructNode>::iden(&ctx);
579            let t5 = Arc::<ConstructNode>::take(&i4);
580            let ca6 = Arc::<ConstructNode>::case(&i3, &t5).unwrap();
581            let ca7 = Arc::<ConstructNode>::case(&d2, &ca6).unwrap();
582            let c8 = Arc::<ConstructNode>::comp(&w0, &ca7).unwrap();
583            let u9 = Arc::<ConstructNode>::unit(&ctx);
584            let c10 = Arc::<ConstructNode>::comp(&c8, &u9).unwrap();
585
586            // In #286 we incorrectly succeed finalizing the types, and then encode a bad program.
587            let err = c10.finalize_types().unwrap_err();
588            assert!(matches!(err, types::Error::OccursCheck { .. }));
589        });
590    }
591}
simplicity/node/construct.rs

simplicity/node/
construct.rs
