simplicity/merkle/
tmr.rs

1// SPDX-License-Identifier: CC0-1.0
2
3use crate::impl_midstate_wrapper;
4use hashes::sha256::Midstate;
5
6/// Type Merkle root
7///
8/// A Merkle root that commits to a type's primitive (unit, sum, product)
9/// and recursively its sub-types.
10///
11/// Uniquely identifies a type.
12#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
13pub struct Tmr(pub(crate) Midstate);
14
15impl_midstate_wrapper!(Tmr);
16
17impl Tmr {
18    #[rustfmt::skip]
19    const UNIT_IV: Tmr = Tmr(Midstate([
20        0x50, 0xb3, 0x8c, 0xd7, 0x64, 0x75, 0xff, 0x89,
21        0x29, 0x28, 0x8b, 0xfc, 0xd0, 0xd9, 0xdf, 0x0e,
22        0x4a, 0x24, 0x1c, 0x0a, 0x57, 0x08, 0x57, 0x2a,
23        0xd2, 0x64, 0x19, 0x2a, 0x4f, 0xe6, 0x7b, 0xee,
24    ]));
25
26    #[rustfmt::skip]
27    const SUM_IV: Tmr = Tmr(Midstate([
28        0x92, 0x0c, 0xfd, 0x83, 0xcf, 0x96, 0xbb, 0x32,
29        0x73, 0x17, 0x36, 0x0f, 0x6d, 0x3a, 0xd7, 0x60,
30        0x1e, 0xef, 0x0a, 0x16, 0xdd, 0x53, 0x14, 0x6c,
31        0x2e, 0x5d, 0xe3, 0x5f, 0x51, 0xef, 0x8d, 0xa4,
32    ]));
33
34    #[rustfmt::skip]
35    const PROD_IV: Tmr = Tmr(Midstate([
36        0xae, 0x99, 0x2a, 0x3e, 0xe0, 0x71, 0x3b, 0xf6,
37        0x19, 0x5d, 0x3b, 0xac, 0x1a, 0xf5, 0x05, 0xa7,
38        0x29, 0xc1, 0x4d, 0x47, 0x95, 0x58, 0xf0, 0xd6,
39        0x29, 0x96, 0x30, 0xf7, 0xfa, 0x97, 0x2e, 0xf8,
40    ]));
41
42    /// The TMRs of the types TWO^(2^n) for small values of n
43    #[rustfmt::skip]
44    pub const TWO_TWO_N: [Tmr; 32] = [
45        Tmr(Midstate([
46            0x88, 0x5a, 0x22, 0xde, 0x3e, 0xdb, 0x3f, 0x40,
47            0xdb, 0x06, 0x09, 0xc2, 0x40, 0x23, 0x30, 0x3f,
48            0xec, 0x67, 0x87, 0xbe, 0x4d, 0x49, 0x21, 0xe4,
49            0x5e, 0xe9, 0xd9, 0x83, 0xac, 0xb5, 0xd8, 0x9d,
50        ])),
51        Tmr(Midstate([
52            0x55, 0x22, 0xba, 0x1c, 0x92, 0x89, 0x4d, 0xf2,
53            0x57, 0x23, 0xcf, 0xeb, 0x5a, 0xf2, 0x59, 0xf4,
54            0xc5, 0x5a, 0x5c, 0xfc, 0x82, 0x00, 0xd5, 0x9b,
55            0xad, 0x09, 0x64, 0x99, 0x7f, 0x9b, 0x2b, 0x04,
56        ])),
57        Tmr(Midstate([
58            0xfa, 0x28, 0xba, 0x9f, 0x0f, 0x07, 0xb4, 0xfa,
59            0xe4, 0xdd, 0x86, 0x23, 0x61, 0x41, 0x12, 0xff,
60            0x3b, 0xaf, 0xab, 0xe2, 0x9c, 0x41, 0x5d, 0x2e,
61            0x0c, 0x1e, 0xd3, 0xc4, 0x13, 0x51, 0x28, 0xe0,
62        ])),
63        Tmr(Midstate([
64            0xd3, 0x43, 0xe4, 0xd5, 0xfa, 0xa4, 0xce, 0xa4,
65            0x4b, 0xb7, 0x11, 0xef, 0x4b, 0x1b, 0x96, 0xb7,
66            0xe0, 0xfb, 0x26, 0xcf, 0xa8, 0x5a, 0x96, 0x04,
67            0x39, 0xba, 0x84, 0x58, 0xc0, 0xb6, 0xc5, 0xc3,
68        ])),
69        Tmr(Midstate([
70            0x62, 0x8c, 0x36, 0x1f, 0x09, 0xcb, 0x2e, 0x5b,
71            0xaa, 0xd9, 0xc6, 0xb7, 0x26, 0xa9, 0xfa, 0x95,
72            0xd1, 0xda, 0x67, 0x79, 0x7e, 0xe2, 0x4c, 0xcf,
73            0x01, 0x41, 0x0c, 0x97, 0x93, 0x39, 0x95, 0x00,
74        ])),
75        Tmr(Midstate([
76            0xb1, 0xa9, 0xf9, 0x68, 0x78, 0x33, 0xdc, 0x44,
77            0xbc, 0x8f, 0x17, 0xd3, 0xcb, 0xc2, 0x55, 0xb7,
78            0xaa, 0x49, 0x9a, 0x78, 0xfe, 0xc8, 0x5c, 0xc9,
79            0x8a, 0x0c, 0x33, 0x5c, 0x86, 0xed, 0x26, 0xe9,
80        ])),
81        Tmr(Midstate([
82            0xfd, 0x75, 0xbc, 0xd8, 0xcb, 0x55, 0xa5, 0xe4,
83            0x24, 0xe0, 0x92, 0x88, 0xac, 0x8e, 0xb4, 0x29,
84            0x42, 0x53, 0x4e, 0xc1, 0x09, 0x9b, 0x72, 0xbe,
85            0xce, 0x0e, 0xa2, 0xc5, 0x47, 0x9b, 0xf3, 0xe7,
86        ])),
87        Tmr(Midstate([
88            0xe3, 0x94, 0xd2, 0xa0, 0x51, 0x6d, 0x73, 0x8d,
89            0x6e, 0x04, 0x59, 0xb9, 0x1b, 0xb0, 0xdd, 0x47,
90            0x1d, 0x0d, 0xaa, 0x77, 0x96, 0x71, 0xa5, 0x31,
91            0x3b, 0x62, 0x14, 0x0e, 0xc7, 0x0a, 0x22, 0x6e,
92        ])),
93        Tmr(Midstate([
94            0xe4, 0xc4, 0x72, 0x8d, 0x87, 0x67, 0x49, 0xbe,
95            0xbe, 0x4d, 0x62, 0x97, 0xdf, 0xad, 0xd4, 0x2c,
96            0xe2, 0x68, 0x44, 0x50, 0x0d, 0x96, 0xc5, 0xe9,
97            0x14, 0x61, 0x57, 0x50, 0x8e, 0xb9, 0x09, 0x8f,
98        ])),
99        Tmr(Midstate([
100            0x1a, 0xe5, 0x45, 0xb7, 0xc3, 0xfd, 0x85, 0xfe,
101            0x81, 0x6c, 0x70, 0xea, 0x4c, 0x78, 0xb7, 0x41,
102            0x9d, 0x8b, 0xe3, 0xc1, 0xfb, 0x3f, 0x72, 0x23,
103            0xfa, 0x7d, 0x8d, 0x50, 0x36, 0x75, 0x51, 0x8f,
104        ])),
105        Tmr(Midstate([
106            0x6a, 0x9c, 0x72, 0x40, 0xe5, 0xd7, 0x1d, 0x5a,
107            0x83, 0x30, 0xb3, 0xb3, 0xb6, 0x65, 0x0b, 0xc3,
108            0x66, 0x6c, 0x3f, 0xef, 0x2e, 0x80, 0x3e, 0xd8,
109            0x64, 0xf1, 0x2f, 0xcd, 0x8f, 0xea, 0xc1, 0xca,
110        ])),
111        Tmr(Midstate([
112            0x0a, 0x2a, 0x58, 0x7a, 0xeb, 0xc9, 0x6b, 0x0e,
113            0x3e, 0x26, 0x01, 0x38, 0x2e, 0xb3, 0x2a, 0x9f,
114            0x1e, 0x29, 0xc8, 0x50, 0x1c, 0xbd, 0xd8, 0x0e,
115            0x87, 0x05, 0xc0, 0xe7, 0xd3, 0xf5, 0xb3, 0x4f,
116        ])),
117        Tmr(Midstate([
118            0xb3, 0xed, 0xb6, 0xfd, 0x83, 0x8e, 0xc4, 0x05,
119            0x7b, 0x76, 0x8c, 0x86, 0xb0, 0xe8, 0xa9, 0x6d,
120            0x1c, 0xe3, 0xf1, 0x69, 0x54, 0x31, 0x4d, 0xcd,
121            0x3d, 0xbf, 0x72, 0x85, 0xeb, 0xa5, 0x63, 0xa9,
122        ])),
123        Tmr(Midstate([
124            0xd0, 0x47, 0x4c, 0x0c, 0x1e, 0x2c, 0x09, 0xd9,
125            0xc5, 0xf0, 0x50, 0x98, 0x93, 0x57, 0xce, 0x71,
126            0xab, 0x5d, 0x90, 0x4e, 0x8e, 0x2e, 0x82, 0x87,
127            0x42, 0x86, 0xc0, 0xc2, 0x12, 0xde, 0x3e, 0x71,
128        ])),
129        Tmr(Midstate([
130            0x37, 0x92, 0x46, 0xdc, 0x86, 0x6d, 0x37, 0x0d,
131            0xbf, 0xc9, 0x70, 0x4f, 0xbc, 0x57, 0xcd, 0x7a,
132            0x6e, 0xb5, 0xed, 0xe7, 0x97, 0xa0, 0x0c, 0x4a,
133            0x72, 0xb3, 0xb4, 0xa5, 0xd9, 0xf0, 0x9f, 0xe1,
134        ])),
135        Tmr(Midstate([
136            0x8a, 0x59, 0xe8, 0x3f, 0x43, 0xe2, 0xa1, 0xf9,
137            0x07, 0xd3, 0xa2, 0x96, 0x67, 0x53, 0x33, 0x6a,
138            0x1d, 0xa2, 0x0d, 0x23, 0xfe, 0x63, 0x63, 0x28,
139            0x58, 0xf9, 0x4e, 0xc0, 0x7d, 0x19, 0x13, 0xd2,
140        ])),
141        Tmr(Midstate([
142            0x0f, 0x51, 0x95, 0x68, 0x9f, 0x55, 0x6d, 0x00,
143            0xbe, 0x92, 0xfc, 0x2d, 0xc5, 0x7b, 0xcb, 0xb1,
144            0x25, 0x62, 0x0f, 0xfc, 0x00, 0x96, 0x3c, 0x09,
145            0x14, 0xb1, 0x96, 0x15, 0x1a, 0x77, 0x84, 0x1c,
146        ])),
147        Tmr(Midstate([
148            0x6d, 0x2a, 0x47, 0x99, 0xa1, 0x6e, 0xb6, 0x78,
149            0x4e, 0x49, 0x66, 0xb8, 0x1d, 0xa6, 0x27, 0xd3,
150            0x5a, 0xa7, 0x08, 0xfd, 0x97, 0x25, 0xd6, 0x04,
151            0x77, 0x7b, 0x14, 0x3e, 0x28, 0xd4, 0xac, 0xf0,
152        ])),
153        Tmr(Midstate([
154            0x2a, 0x07, 0x5c, 0x50, 0xca, 0x10, 0xe5, 0x00,
155            0x92, 0x77, 0x86, 0xca, 0x86, 0xa5, 0x2b, 0xb7,
156            0xe5, 0x2d, 0xdb, 0x16, 0x42, 0xe3, 0x77, 0x45,
157            0xfb, 0x44, 0x14, 0x91, 0x39, 0xb3, 0x2d, 0x67,
158        ])),
159        Tmr(Midstate([
160            0xf5, 0x67, 0xc8, 0x1b, 0x82, 0x5d, 0xc9, 0x00,
161            0xe0, 0xbc, 0x0c, 0x59, 0xce, 0xa6, 0xaa, 0x1f,
162            0x1f, 0x34, 0x28, 0x3f, 0xcb, 0xee, 0xff, 0x73,
163            0x2d, 0xb8, 0xe2, 0x17, 0x57, 0x6c, 0x22, 0x55,
164        ])),
165        Tmr(Midstate([
166            0x0a, 0xee, 0x10, 0x39, 0xd3, 0xc8, 0xaf, 0x91,
167            0x41, 0xbc, 0xb9, 0xfd, 0xf3, 0xf8, 0x24, 0x1e,
168            0xf9, 0xfd, 0x4b, 0x85, 0x85, 0x3a, 0x79, 0xba,
169            0xbc, 0xfb, 0x2a, 0xb4, 0xdb, 0x8e, 0xf3, 0x8c,
170        ])),
171        Tmr(Midstate([
172            0x30, 0xaa, 0xe9, 0xb8, 0xf2, 0xc6, 0xfa, 0xf0,
173            0x7a, 0x62, 0x07, 0x2f, 0x55, 0xb2, 0x96, 0x98,
174            0x5d, 0xd7, 0x3b, 0xc1, 0x04, 0x42, 0xc8, 0x02,
175            0x79, 0x32, 0xff, 0xf4, 0x1f, 0x2a, 0x2d, 0x72,
176        ])),
177        Tmr(Midstate([
178            0xbc, 0x14, 0x6c, 0xb5, 0xae, 0x67, 0xe0, 0x0a,
179            0x6d, 0x8e, 0x3f, 0xd0, 0x56, 0xfb, 0x7a, 0x72,
180            0x82, 0x04, 0x84, 0xc6, 0x1a, 0xcf, 0x17, 0xfe,
181            0xcc, 0xf1, 0x30, 0xcb, 0xa6, 0x22, 0xd2, 0x7f,
182        ])),
183        Tmr(Midstate([
184            0xa8, 0x67, 0xba, 0xcf, 0xf8, 0xd1, 0xc2, 0x5c,
185            0x9e, 0x82, 0x4f, 0x1b, 0x63, 0xa4, 0x9c, 0x17,
186            0x67, 0x9b, 0xba, 0x8a, 0xd8, 0x76, 0x99, 0xa0,
187            0xcd, 0xf7, 0x7d, 0xef, 0x0a, 0x1b, 0x75, 0x11,
188        ])),
189        Tmr(Midstate([
190            0xc1, 0x28, 0xdc, 0x7e, 0x8d, 0x79, 0x4a, 0x7a,
191            0x48, 0x08, 0x14, 0x95, 0xa6, 0xeb, 0x2b, 0x2d,
192            0x3c, 0xb6, 0x6b, 0xc0, 0xe0, 0x33, 0x27, 0x3b,
193            0xf9, 0xdd, 0xbc, 0x98, 0x6c, 0x22, 0x68, 0x92,
194        ])),
195        Tmr(Midstate([
196            0x19, 0x9f, 0xfd, 0xe4, 0x7d, 0x27, 0x91, 0xa3,
197            0x58, 0xf2, 0x3a, 0xe5, 0x08, 0x25, 0x16, 0xc6,
198            0x5e, 0x57, 0xf5, 0x5a, 0xe6, 0x6d, 0xdf, 0x44,
199            0x65, 0xba, 0xab, 0x4b, 0xfa, 0x3c, 0x3a, 0x5f,
200        ])),
201        Tmr(Midstate([
202            0x40, 0x38, 0x09, 0x5d, 0xbb, 0x32, 0xe2, 0x7e,
203            0x6e, 0x31, 0x66, 0x52, 0x7b, 0xce, 0xdd, 0xa8,
204            0x4e, 0x8b, 0x21, 0xf6, 0xd4, 0x2f, 0x7e, 0x56,
205            0xea, 0xff, 0x21, 0x85, 0x6a, 0xd2, 0x04, 0xa2,
206        ])),
207        Tmr(Midstate([
208            0xc3, 0xa0, 0xa6, 0xf8, 0x7e, 0x6c, 0x3f, 0x02,
209            0xbf, 0x98, 0x05, 0x1c, 0xe4, 0x5d, 0x6d, 0x69,
210            0x55, 0x38, 0x24, 0x78, 0xf1, 0x0f, 0xa0, 0x6a,
211            0xdd, 0x51, 0x30, 0xe5, 0x99, 0x17, 0xf8, 0xc7,
212        ])),
213        Tmr(Midstate([
214            0x7c, 0x25, 0xbf, 0x44, 0x7a, 0x45, 0xba, 0x13,
215            0x23, 0xe8, 0xdb, 0x8b, 0x81, 0x78, 0x87, 0xa8,
216            0x85, 0x8b, 0xee, 0x25, 0x6e, 0x5c, 0xa3, 0x52,
217            0x8e, 0x79, 0xcf, 0xbc, 0x2d, 0x41, 0x9c, 0xe3,
218        ])),
219        Tmr(Midstate([
220            0x75, 0xa7, 0x7a, 0x6c, 0x7b, 0x6d, 0xe9, 0x1d,
221            0x23, 0xc1, 0x00, 0x4d, 0x8e, 0xb0, 0xb3, 0x5d,
222            0x9c, 0xdf, 0x6f, 0xa1, 0xdf, 0xc7, 0xca, 0xbd,
223            0x04, 0x66, 0x92, 0xf1, 0xa2, 0x43, 0x14, 0x17,
224        ])),
225        Tmr(Midstate([
226            0x9f, 0xc2, 0x4a, 0xb6, 0x99, 0x70, 0xf8, 0x66,
227            0x6d, 0x7b, 0x1e, 0x52, 0x5a, 0x3a, 0x8e, 0x79,
228            0x43, 0x99, 0x76, 0xe7, 0x79, 0x2b, 0xfe, 0x1a,
229            0x1b, 0x0d, 0x0d, 0x84, 0xff, 0x03, 0x84, 0x34,
230        ])),
231        Tmr(Midstate([
232            0x64, 0x25, 0x1a, 0xb9, 0x70, 0x77, 0x17, 0x0e,
233            0x19, 0x91, 0x15, 0x76, 0x5e, 0x93, 0x43, 0xe7,
234            0x1b, 0x59, 0x0e, 0x41, 0x78, 0x88, 0xf2, 0xa8,
235            0x36, 0x43, 0x11, 0xd8, 0x65, 0x40, 0xed, 0xfa,
236        ])),
237    ];
238
239    /// The TMR for the unit type
240    pub const fn unit() -> Tmr {
241        Self::UNIT_IV
242    }
243
244    /// The TMR for the sum of two types, whose TMRs are given
245    pub fn sum(tmr1: Tmr, tmr2: Tmr) -> Tmr {
246        Self::SUM_IV.update(tmr1, tmr2)
247    }
248
249    /// The TMR for the product of two types, whose TMRs are given
250    pub fn product(tmr1: Tmr, tmr2: Tmr) -> Tmr {
251        Self::PROD_IV.update(tmr1, tmr2)
252    }
253}
254
255#[cfg(test)]
256mod tests {
257    use super::*;
258
259    use crate::merkle::bip340_iv;
260    use crate::types;
261
262    #[test]
263    fn ivs() {
264        fn check_iv(target: Tmr, s: &'static str) {
265            let name = s.trim_start_matches("Simplicity\x1fType\x1f");
266            // Uncomment this if the IVs ever change
267            /*
268            let target = Tmr(bip340_iv(s.as_bytes()));
269            println!("    #[rustfmt::skip]");
270            println!("    const {}_IV: Tmr = Tmr(Midstate([", name.to_ascii_uppercase());
271            print!("       "); for ch in &target.0[0..8] { print!(" 0x{:02x},", ch); }; println!();
272            print!("       "); for ch in &target.0[8..16] { print!(" 0x{:02x},", ch); }; println!();
273            print!("       "); for ch in &target.0[16..24] { print!(" 0x{:02x},", ch); }; println!();
274            print!("       "); for ch in &target.0[24..32] { print!(" 0x{:02x},", ch); }; println!();
275            println!("    ]));");
276            println!();
277            */
278            assert_eq!(
279                target,
280                Tmr(bip340_iv(s.as_bytes())),
281                "mismatch on IV for {}",
282                name
283            );
284        }
285
286        check_iv(Tmr::UNIT_IV, "Simplicity\x1fType\x1funit");
287        check_iv(Tmr::SUM_IV, "Simplicity\x1fType\x1fsum");
288        check_iv(Tmr::PROD_IV, "Simplicity\x1fType\x1fprod");
289    }
290
291    #[test]
292    #[allow(clippy::needless_range_loop)]
293    fn const_powers_of_2() {
294        fn check_pow(target: Tmr, i: usize, expected_tmrs: &[Tmr]) {
295            // Uncomment this if the IVs ever change
296            /*
297            let target = tmrs[i];
298            println!("    Tmr(Midstate([");
299            print!("       "); for ch in &target.0[0..8] { print!(" 0x{:02x},", ch); }; println!();
300            print!("       "); for ch in &target.0[8..16] { print!(" 0x{:02x},", ch); }; println!();
301            print!("       "); for ch in &target.0[16..24] { print!(" 0x{:02x},", ch); }; println!();
302            print!("       "); for ch in &target.0[24..32] { print!(" 0x{:02x},", ch); }; println!();
303            println!("    ])),");
304            */
305            assert_eq!(target, expected_tmrs[i], "mismatch on TMR for TWO^(2^{i})");
306        }
307
308        let n = Tmr::TWO_TWO_N.len();
309        types::Context::with_context(|ctx| {
310            let tmrs = types::Type::powers_of_two(&ctx, n)
311                .iter()
312                .filter_map(types::Type::tmr)
313                .collect::<Vec<Tmr>>();
314            debug_assert_eq!(tmrs.len(), n);
315            for i in 0..n {
316                check_pow(Tmr::TWO_TWO_N[i], i, &tmrs);
317            }
318        });
319    }
320}
simplicity/merkle/tmr.rs

simplicity/merkle/
tmr.rs
