simplicity/merkle/
amr.rs

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

simplicity/merkle/
amr.rs
