simplicity/merkle/
amr.rs

1// SPDX-License-Identifier: CC0-1.0
2
3use crate::impl_midstate_wrapper;
4use crate::jet::Jet;
5use crate::merkle::compact_value;
6use crate::types::arrow::FinalArrow;
7use crate::value::Word;
8use crate::{Cmr, Tmr, Value};
9use hashes::sha256::Midstate;
10
11use super::FailEntropy;
12
13/// Annotated Merkle root
14///
15/// A Merkle root that commits to a node's combinator, its source and target type,
16/// its witness data (if present), and recursively its children.
17///
18/// Uniquely identifies a program's structure in terms of types at redemption time.
19#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
20pub struct Amr(Midstate);
21
22impl_midstate_wrapper!(Amr);
23
24impl From<Cmr> for Amr {
25    fn from(cmr: Cmr) -> Self {
26        Amr::from_byte_array(cmr.to_byte_array())
27    }
28}
29
30impl From<Tmr> for Amr {
31    fn from(tmr: Tmr) -> Self {
32        Amr::from_byte_array(tmr.to_byte_array())
33    }
34}
35
36impl Amr {
37    /// Produce a CMR for an iden combinator
38    pub fn iden(ty: &FinalArrow) -> Self {
39        let a = &ty.source;
40        Self::IDEN_IV.update_1(a.tmr().into())
41    }
42
43    /// Produce a CMR for a unit combinator
44    pub fn unit(ty: &FinalArrow) -> Self {
45        let a = &ty.source;
46        Self::UNIT_IV.update_1(a.tmr().into())
47    }
48
49    /// Produce a CMR for an injl combinator
50    pub fn injl(ty: &FinalArrow, child: Amr) -> Self {
51        let a = &ty.source;
52        let (b, c) = ty.target.as_sum().unwrap();
53        Self::INJL_IV
54            .update(a.tmr().into(), b.tmr().into())
55            .update(c.tmr().into(), child)
56    }
57
58    /// Produce a CMR for an injr combinator
59    pub fn injr(ty: &FinalArrow, child: Amr) -> Self {
60        let a = &ty.source;
61        let (b, c) = ty.target.as_sum().unwrap();
62        Self::INJR_IV
63            .update(a.tmr().into(), b.tmr().into())
64            .update(c.tmr().into(), child)
65    }
66
67    /// Produce a CMR for a take combinator
68    pub fn take(ty: &FinalArrow, child: Amr) -> Self {
69        let (a, b) = ty.source.as_product().unwrap();
70        let c = &ty.target;
71        Self::TAKE_IV
72            .update(a.tmr().into(), b.tmr().into())
73            .update(c.tmr().into(), child)
74    }
75
76    /// Produce a CMR for a drop combinator
77    pub fn drop(ty: &FinalArrow, child: Amr) -> Self {
78        let (a, b) = ty.source.as_product().unwrap();
79        let c = &ty.target;
80        Self::DROP_IV
81            .update(a.tmr().into(), b.tmr().into())
82            .update(c.tmr().into(), child)
83    }
84
85    /// Produce a CMR for a comp combinator
86    pub fn comp(ty: &FinalArrow, left_arrow: &FinalArrow, left: Amr, right: Amr) -> Self {
87        let a = &ty.source;
88        let b = &left_arrow.target;
89        let c = &ty.target;
90        Self::COMP_IV
91            .update_1(a.tmr().into())
92            .update(b.tmr().into(), c.tmr().into())
93            .update(left, right)
94    }
95
96    fn case_helper(iv: Amr, ty: &FinalArrow, left: Amr, right: Amr) -> Self {
97        let (sum_a_b, c) = ty.source.as_product().unwrap();
98        let (a, b) = sum_a_b.as_sum().unwrap();
99        let d = &ty.target;
100        iv.update(a.tmr().into(), b.tmr().into())
101            .update(c.tmr().into(), d.tmr().into())
102            .update(left, right)
103    }
104
105    /// Produce a CMR for a case combinator
106    pub fn case(ty: &FinalArrow, left: Amr, right: Amr) -> Self {
107        Self::case_helper(Self::CASE_IV, ty, left, right)
108    }
109
110    /// Produce a CMR for an assertl combinator
111    pub fn assertl(ty: &FinalArrow, left: Amr, right: Amr) -> Self {
112        Self::case_helper(Self::ASSERTL_IV, ty, left, right)
113    }
114
115    /// Produce a CMR for an assertr combinator
116    pub fn assertr(ty: &FinalArrow, left: Amr, right: Amr) -> Self {
117        Self::case_helper(Self::ASSERTR_IV, ty, left, right)
118    }
119
120    /// Produce a CMR for a pair combinator
121    pub fn pair(
122        ty: &FinalArrow,
123        left_arrow: &FinalArrow,
124        right_arrow: &FinalArrow,
125        left: Amr,
126        right: Amr,
127    ) -> Self {
128        let a = &ty.source;
129        let b = &left_arrow.target;
130        let c = &right_arrow.target;
131        Self::PAIR_IV
132            .update_1(a.tmr().into())
133            .update(b.tmr().into(), c.tmr().into())
134            .update(left, right)
135    }
136
137    /// Produce a CMR for a disconnect combinator
138    pub fn disconnect(ty: &FinalArrow, right_arrow: &FinalArrow, left: Amr, right: Amr) -> Self {
139        let a = &ty.source;
140        let (b, d) = ty.target.as_product().unwrap();
141        let c = &right_arrow.source;
142        Self::DISCONNECT_IV
143            .update(a.tmr().into(), b.tmr().into())
144            .update(c.tmr().into(), d.tmr().into())
145            .update(left, right)
146    }
147
148    /// Produce a CMR for a witness combinator
149    pub fn witness(ty: &FinalArrow, value: &Value) -> Self {
150        let a = &ty.source;
151        let b = &ty.target;
152        Self::WITNESS_IV
153            .update_1(a.tmr().into())
154            .update(b.tmr().into(), Amr::from_byte_array(compact_value(value)))
155    }
156
157    /// Produce an AMR for a fail combinator
158    pub fn fail(entropy: FailEntropy) -> Self {
159        Self::FAIL_IV.update_fail_entropy(entropy)
160    }
161
162    /// Produce a CMR for a jet
163    pub fn jet<J: Jet>(jet: J) -> Self {
164        Cmr::jet(jet).into()
165    }
166
167    /// Compute the CMR of a constant word jet
168    ///
169    /// This is equal to the IHR of the equivalent scribe, converted to a CMR in
170    /// the usual way for jets.
171    pub fn const_word(word: &Word) -> Self {
172        Cmr::const_word(word).into()
173    }
174
175    #[rustfmt::skip]
176    const IDEN_IV: Amr = Amr(Midstate([
177        0x45, 0x1f, 0x68, 0x8c, 0x41, 0x50, 0x99, 0x68,
178        0x3a, 0x8d, 0x36, 0xa7, 0x09, 0xba, 0x42, 0x49,
179        0xe6, 0xde, 0xf7, 0x1b, 0x35, 0x29, 0xb4, 0xc1,
180        0xf2, 0xe4, 0xd5, 0x63, 0x85, 0x54, 0x91, 0xaf,
181    ]));
182
183    #[rustfmt::skip]
184    const UNIT_IV: Amr = Amr(Midstate([
185        0xdb, 0xfe, 0xe7, 0x84, 0x3b, 0x59, 0x1e, 0x8f,
186        0x7c, 0xe4, 0x85, 0xdc, 0xb5, 0xd6, 0x6b, 0xcc,
187        0x23, 0x98, 0x48, 0x10, 0xbd, 0x6b, 0xe5, 0x2a,
188        0xa7, 0x6e, 0xaf, 0x2b, 0x25, 0xcb, 0x44, 0x23,
189    ]));
190
191    #[rustfmt::skip]
192    const INJL_IV: Amr = Amr(Midstate([
193        0xba, 0xcb, 0x63, 0x56, 0x69, 0x80, 0xdc, 0xac,
194        0x45, 0x59, 0x1f, 0x5a, 0xef, 0x0d, 0x91, 0xd4,
195        0x9e, 0xa4, 0xc1, 0xe0, 0x07, 0x2b, 0x1c, 0xe3,
196        0xdd, 0x20, 0x75, 0x21, 0xc9, 0xea, 0xd8, 0x08,
197    ]));
198
199    #[rustfmt::skip]
200    const INJR_IV: Amr = Amr(Midstate([
201        0x7b, 0x11, 0x6e, 0xbc, 0x3f, 0x90, 0x9e, 0xef,
202        0x13, 0x87, 0x98, 0x71, 0x99, 0x84, 0x4b, 0x91,
203        0xbc, 0xc7, 0x40, 0x2c, 0x24, 0x30, 0xc4, 0x85,
204        0x29, 0x75, 0xd4, 0x8f, 0x49, 0x0c, 0x54, 0x7a,
205    ]));
206
207    #[rustfmt::skip]
208    const TAKE_IV: Amr = Amr(Midstate([
209        0x41, 0x75, 0xa1, 0x34, 0xe6, 0xb4, 0xd1, 0x5b,
210        0xb4, 0x8a, 0xc5, 0x82, 0xd9, 0xbc, 0x83, 0xa2,
211        0x94, 0x84, 0xc7, 0xec, 0x27, 0x00, 0x4d, 0xff,
212        0x94, 0xaa, 0xe4, 0xcb, 0x5d, 0x87, 0x6f, 0xb6,
213    ]));
214
215    #[rustfmt::skip]
216    const DROP_IV: Amr = Amr(Midstate([
217        0x3b, 0x32, 0x93, 0xab, 0xbc, 0xc9, 0xb9, 0xdb,
218        0xe1, 0xbd, 0x70, 0xa3, 0x31, 0x5f, 0x38, 0xff,
219        0x26, 0x05, 0xfb, 0x30, 0xe3, 0x1f, 0x3c, 0xee,
220        0x7b, 0x25, 0x1a, 0x88, 0x31, 0xc1, 0x56, 0x89,
221    ]));
222
223    #[rustfmt::skip]
224    const COMP_IV: Amr = Amr(Midstate([
225        0x73, 0x7f, 0xd0, 0x53, 0x08, 0xd6, 0x05, 0x00,
226        0x3b, 0xde, 0x8e, 0xb2, 0x0a, 0x3b, 0x93, 0x97,
227        0xc1, 0xda, 0xaa, 0xe5, 0x43, 0xd8, 0xa4, 0xe4,
228        0xfe, 0xef, 0x48, 0x38, 0x76, 0x85, 0x93, 0x84,
229    ]));
230
231    #[rustfmt::skip]
232    const CASE_IV: Amr = Amr(Midstate([
233        0x59, 0x58, 0x14, 0xf9, 0xe0, 0xc8, 0x89, 0xb4,
234        0x84, 0x7a, 0xba, 0x1d, 0x51, 0xe1, 0x4e, 0x04,
235        0x8f, 0x95, 0x34, 0x4b, 0x2a, 0x43, 0x20, 0x91,
236        0xf8, 0x1b, 0xd3, 0xb8, 0x36, 0xec, 0x35, 0x04,
237    ]));
238
239    #[rustfmt::skip]
240    const ASSERTL_IV: Amr = Amr(Midstate([
241        0xd5, 0xdd, 0xd7, 0x41, 0xd7, 0x27, 0xe2, 0x20,
242        0x35, 0x56, 0xb0, 0xf8, 0xba, 0x4f, 0x7f, 0xd0,
243        0xb4, 0x8f, 0x8d, 0xbf, 0x7a, 0x85, 0x84, 0x87,
244        0x9b, 0xab, 0xa8, 0xd6, 0xec, 0xaa, 0x43, 0xef,
245    ]));
246
247    #[rustfmt::skip]
248    const ASSERTR_IV: Amr = Amr(Midstate([
249        0xc5, 0xfe, 0xcd, 0x9c, 0xad, 0xc1, 0x6a, 0x7a,
250        0x08, 0xcf, 0x21, 0x5a, 0xe7, 0x58, 0x40, 0xf6,
251        0xd2, 0x05, 0xe7, 0xaa, 0x27, 0xf6, 0xff, 0xf2,
252        0x6b, 0xfa, 0x1e, 0x6b, 0x3a, 0x0f, 0x76, 0xfa,
253    ]));
254
255    #[rustfmt::skip]
256    const PAIR_IV: Amr = Amr(Midstate([
257        0x79, 0x96, 0xb3, 0xbf, 0xa6, 0x03, 0x36, 0x73,
258        0x25, 0x15, 0xa1, 0x24, 0x3f, 0x6b, 0x3c, 0x23,
259        0x6b, 0xff, 0x0e, 0xb0, 0x66, 0x2f, 0x8a, 0xdd,
260        0x54, 0xaf, 0x0c, 0x98, 0xd1, 0xfd, 0xdd, 0xa7,
261    ]));
262
263    #[rustfmt::skip]
264    const DISCONNECT_IV: Amr = Amr(Midstate([
265        0x27, 0xeb, 0xbc, 0xaa, 0x5a, 0x53, 0x7c, 0x25,
266        0xd8, 0xbb, 0x43, 0x40, 0x37, 0xbb, 0x2f, 0xff,
267        0x6b, 0x88, 0x15, 0x35, 0x43, 0x5e, 0x6d, 0x60,
268        0xa5, 0xf8, 0x5c, 0xd0, 0xf0, 0x5a, 0x61, 0x47,
269    ]));
270
271    #[rustfmt::skip]
272    const WITNESS_IV: Amr = Amr(Midstate([
273        0x6b, 0xc6, 0x20, 0xcb, 0x52, 0xf9, 0x0c, 0x63,
274        0x0e, 0xf8, 0xc8, 0x0d, 0x5f, 0x69, 0x0d, 0xb4,
275        0xe9, 0x93, 0x0a, 0xd0, 0xfa, 0x70, 0x71, 0x36,
276        0x5b, 0x5c, 0x93, 0xe0, 0x39, 0x1b, 0xd7, 0x96,
277    ]));
278
279    #[rustfmt::skip]
280    const FAIL_IV: Amr = Amr(Midstate([
281        0x36, 0x9c, 0xdd, 0x29, 0x3f, 0xd5, 0x8a, 0x85,
282        0xa5, 0x90, 0x38, 0x0f, 0x12, 0x20, 0x7e, 0x18,
283        0x10, 0x02, 0x0d, 0x39, 0x1c, 0x46, 0xd1, 0xab,
284        0xbe, 0xb2, 0x12, 0x2e, 0xa2, 0xfd, 0x55, 0xec,
285    ]));
286}
287
288#[cfg(test)]
289mod tests {
290    use super::super::bip340_iv;
291    use super::*;
292
293    use crate::jet::Core;
294    use crate::node::{ConstructNode, JetConstructible};
295    use crate::types;
296    use std::sync::Arc;
297
298    #[test]
299    fn fixed_amr() {
300        types::Context::with_context(|ctx| {
301            let node = Arc::<ConstructNode<_>>::jet(&ctx, Core::Verify)
302                .finalize_types_non_program()
303                .unwrap();
304            // Checked against C implementation
305            #[rustfmt::skip]
306            assert_eq!(
307                &node.amr().unwrap().to_string(),
308                "343e6dc16b3f52e83e3b4ccc99b8c6f96a074fe399327af364bc285e299745a2"
309            );
310        });
311    }
312
313    #[test]
314    fn ivs() {
315        fn check_iv(target: Amr, s: &'static str) {
316            let name = s.trim_start_matches("Simplicity\x1fAnnotated\x1f");
317            // Uncomment this if the IVs ever change
318            /*
319            let target = Amr(bip340_iv(s.as_bytes()));
320            println!("    #[rustfmt::skip]");
321            println!("    const {}_IV: Amr = Amr(Midstate([", name.to_ascii_uppercase());
322            print!("       "); for ch in &target.0[0..8] { print!(" 0x{:02x},", ch); }; println!();
323            print!("       "); for ch in &target.0[8..16] { print!(" 0x{:02x},", ch); }; println!();
324            print!("       "); for ch in &target.0[16..24] { print!(" 0x{:02x},", ch); }; println!();
325            print!("       "); for ch in &target.0[24..32] { print!(" 0x{:02x},", ch); }; println!();
326            println!("    ]));");
327            println!();
328            */
329            assert_eq!(
330                target,
331                Amr(bip340_iv(s.as_bytes())),
332                "mismatch on IV for {}",
333                name
334            );
335        }
336
337        check_iv(Amr::IDEN_IV, "Simplicity\x1fAnnotated\x1fiden");
338        check_iv(Amr::UNIT_IV, "Simplicity\x1fAnnotated\x1funit");
339        check_iv(Amr::INJL_IV, "Simplicity\x1fAnnotated\x1finjl");
340        check_iv(Amr::INJR_IV, "Simplicity\x1fAnnotated\x1finjr");
341        check_iv(Amr::TAKE_IV, "Simplicity\x1fAnnotated\x1ftake");
342        check_iv(Amr::DROP_IV, "Simplicity\x1fAnnotated\x1fdrop");
343        check_iv(Amr::COMP_IV, "Simplicity\x1fAnnotated\x1fcomp");
344        check_iv(Amr::CASE_IV, "Simplicity\x1fAnnotated\x1fcase");
345        check_iv(Amr::ASSERTL_IV, "Simplicity\x1fAnnotated\x1fassertl");
346        check_iv(Amr::ASSERTR_IV, "Simplicity\x1fAnnotated\x1fassertr");
347        check_iv(Amr::PAIR_IV, "Simplicity\x1fAnnotated\x1fpair");
348        check_iv(Amr::DISCONNECT_IV, "Simplicity\x1fAnnotated\x1fdisconnect");
349        check_iv(Amr::WITNESS_IV, "Simplicity\x1fAnnotated\x1fwitness");
350        check_iv(Amr::FAIL_IV, "Simplicity\x1fAnnotated\x1ffail");
351    }
352}
simplicity/merkle/amr.rs

simplicity/merkle/
amr.rs
