miden_crypto/merkle/
empty_roots.rs

1use core::slice;
2
3use super::{Felt, Word, smt::InnerNode};
4
5// EMPTY NODES SUBTREES
6// ================================================================================================
7
8/// Contains precomputed roots of empty subtrees in a Merkle tree.
9pub struct EmptySubtreeRoots;
10
11impl EmptySubtreeRoots {
12    /// Returns a static slice with roots of empty subtrees of a Merkle tree starting at the
13    /// specified depth.
14    pub const fn empty_hashes(tree_depth: u8) -> &'static [Word] {
15        let ptr = &EMPTY_SUBTREES[255 - tree_depth as usize] as *const Word;
16        // Safety: this is a static/constant array, so it will never be outlived. If we attempt to
17        // use regular slices, this wouldn't be a `const` function, meaning we won't be able to use
18        // the returned value for static/constant definitions.
19        unsafe { slice::from_raw_parts(ptr, tree_depth as usize + 1) }
20    }
21
22    /// Returns the node's digest for a sub-tree with all its leaves set to the empty word.
23    pub const fn entry(tree_depth: u8, node_depth: u8) -> &'static Word {
24        assert!(node_depth <= tree_depth);
25        let pos = 255 - tree_depth + node_depth;
26        &EMPTY_SUBTREES[pos as usize]
27    }
28
29    /// Returns a sparse Merkle tree [`InnerNode`] with two empty children.
30    ///
31    /// # Note
32    /// `node_depth` is the depth of the **parent** to have empty children. That is, `node_depth`
33    /// and the depth of the returned [`InnerNode`] are the same, and thus the empty hashes are for
34    /// subtrees of depth `node_depth + 1`.
35    pub(crate) const fn get_inner_node(tree_depth: u8, node_depth: u8) -> InnerNode {
36        let &child = Self::entry(tree_depth, node_depth + 1);
37        InnerNode { left: child, right: child }
38    }
39}
40
41// Poseidon2 empty subtree hashes for depths 0..255 (root at index 0). Generated by repeatedly
42// merging the empty word upward.
43const EMPTY_SUBTREES: [Word; 256] = [
44    Word::new([
45        Felt::new(0xb70f49c4aabc102d),
46        Felt::new(0xf38a6b6579150a60),
47        Felt::new(0xd5fb29ed3d3cf828),
48        Felt::new(0x0a2415d68965735f),
49    ]),
50    Word::new([
51        Felt::new(0x60f370624956f997),
52        Felt::new(0x096971f3e695318a),
53        Felt::new(0x4905cc3882a2334a),
54        Felt::new(0x34e362786e6759f0),
55    ]),
56    Word::new([
57        Felt::new(0x3824d067838b15d6),
58        Felt::new(0x30417bf4696bd6be),
59        Felt::new(0x57625234b7b657ba),
60        Felt::new(0x40c6d1b249951cda),
61    ]),
62    Word::new([
63        Felt::new(0xd9d317c3bad907d7),
64        Felt::new(0x8cd99ba6cf203a57),
65        Felt::new(0x47c499cb3d999340),
66        Felt::new(0x60b28fab42847875),
67    ]),
68    Word::new([
69        Felt::new(0xb8dcfdb6a66dacc9),
70        Felt::new(0x4859b0ed69894461),
71        Felt::new(0x5cf0768579ca2f98),
72        Felt::new(0x3358b0e52b7b1d34),
73    ]),
74    Word::new([
75        Felt::new(0x13820bce6b9e9734),
76        Felt::new(0xc278575ef6c0ba33),
77        Felt::new(0x909216fec7fa7515),
78        Felt::new(0x277b09c7728bb7f5),
79    ]),
80    Word::new([
81        Felt::new(0x57730f57b34fc978),
82        Felt::new(0xb6e64648ef9b842b),
83        Felt::new(0x02e4f56085c37b5f),
84        Felt::new(0xff5f1f2291d26346),
85    ]),
86    Word::new([
87        Felt::new(0xf40f1334ccbd3d5b),
88        Felt::new(0x6fabce118d0a5997),
89        Felt::new(0x77a68b875eb4fb6b),
90        Felt::new(0x85107a3ee95c821f),
91    ]),
92    Word::new([
93        Felt::new(0xc6262d4107930d53),
94        Felt::new(0x7a8c642a0af3c172),
95        Felt::new(0x3af26e9e442a707d),
96        Felt::new(0xac62031f2abab944),
97    ]),
98    Word::new([
99        Felt::new(0x44605e433fd3c167),
100        Felt::new(0xc3e3b8b0f3236e69),
101        Felt::new(0xd736df3ce2d7b28b),
102        Felt::new(0xd42a7bb1513c6d3d),
103    ]),
104    Word::new([
105        Felt::new(0x53c291792b3b77dc),
106        Felt::new(0x4c3fed368e306473),
107        Felt::new(0x45c6e6bcaea9eff7),
108        Felt::new(0x93c68160468a305e),
109    ]),
110    Word::new([
111        Felt::new(0xbc6925f5b3017050),
112        Felt::new(0xde86e82ab374379e),
113        Felt::new(0x6623a8fb49a26e8b),
114        Felt::new(0x3f299face348f881),
115    ]),
116    Word::new([
117        Felt::new(0x74af619f24f20403),
118        Felt::new(0x24f25d56523eab6f),
119        Felt::new(0x3aa725c3a2235b82),
120        Felt::new(0x14420f697109064c),
121    ]),
122    Word::new([
123        Felt::new(0xcbffe33be12e5fae),
124        Felt::new(0x41deb98f3e7b69aa),
125        Felt::new(0x0b4adfb7b431bd72),
126        Felt::new(0x0b408fdb684a306a),
127    ]),
128    Word::new([
129        Felt::new(0xef8d84d2a98b503c),
130        Felt::new(0xe069f292e333e21a),
131        Felt::new(0x66ac70af5d095046),
132        Felt::new(0x9c3f4a827756042b),
133    ]),
134    Word::new([
135        Felt::new(0xb6621ea4d868959c),
136        Felt::new(0x6654f0371c7ab628),
137        Felt::new(0xa86f684ace4b22a3),
138        Felt::new(0xd3e15afa79689c3e),
139    ]),
140    Word::new([
141        Felt::new(0x8998bdb1d4483bf9),
142        Felt::new(0x22fbe7289a50d070),
143        Felt::new(0x2a5382ef2162a65c),
144        Felt::new(0x5a3960393b8e7c61),
145    ]),
146    Word::new([
147        Felt::new(0x715e9a73a0f50f0b),
148        Felt::new(0x7265725a0d6b733b),
149        Felt::new(0x794591556f58d6cd),
150        Felt::new(0x77073707f8dd3c13),
151    ]),
152    Word::new([
153        Felt::new(0xead47b65b8cf7e93),
154        Felt::new(0x3db24824b44f2f8a),
155        Felt::new(0xd032f4c8141623a2),
156        Felt::new(0x7ffd33ca934df915),
157    ]),
158    Word::new([
159        Felt::new(0x86e0f5f5c4ea97cb),
160        Felt::new(0x2ce565c6fcd84a5c),
161        Felt::new(0x8ce0883224280104),
162        Felt::new(0x3475d1d7f8124f22),
163    ]),
164    Word::new([
165        Felt::new(0x31ecf12b05f93adf),
166        Felt::new(0x17242240909b8925),
167        Felt::new(0xf021614f85a0fd8e),
168        Felt::new(0x0681e976da2da221),
169    ]),
170    Word::new([
171        Felt::new(0x94b1324ed4e3d2c3),
172        Felt::new(0xb2f7e944db9b7fc3),
173        Felt::new(0xcb3b4289822ed449),
174        Felt::new(0x7add148186f57183),
175    ]),
176    Word::new([
177        Felt::new(0xf599fba7930f1fb8),
178        Felt::new(0x52a8dbeb5a7f2277),
179        Felt::new(0xeb3e832df10049e2),
180        Felt::new(0x65a509471c608e4d),
181    ]),
182    Word::new([
183        Felt::new(0xe82a672f9d3d1939),
184        Felt::new(0x7e50791921de7cad),
185        Felt::new(0xfcf6af2550d444a6),
186        Felt::new(0xf59d4bd29be522c2),
187    ]),
188    Word::new([
189        Felt::new(0xc4fba9ae23020044),
190        Felt::new(0xdbe23428e91cf970),
191        Felt::new(0x8f4d9b4974bd6748),
192        Felt::new(0x010fb7ab752d50d4),
193    ]),
194    Word::new([
195        Felt::new(0x870999a63cf57309),
196        Felt::new(0xf295b3cecc17c7fa),
197        Felt::new(0x55daca97a971c755),
198        Felt::new(0xf3a11d1147e9bee5),
199    ]),
200    Word::new([
201        Felt::new(0x154b008d1baa72b7),
202        Felt::new(0x0ecf570359fc91e1),
203        Felt::new(0xf1b7f9e2692e0b25),
204        Felt::new(0x8f6bbf0ad9867a77),
205    ]),
206    Word::new([
207        Felt::new(0x022cb18c0a5a203e),
208        Felt::new(0x24491dbefe48ef4d),
209        Felt::new(0xae9e8c66c44eec84),
210        Felt::new(0x1c53ce2fa81a8417),
211    ]),
212    Word::new([
213        Felt::new(0xe1df227725b70010),
214        Felt::new(0x28fb719d8e33d565),
215        Felt::new(0x3742a4a680e5881a),
216        Felt::new(0xd07e4304605673d4),
217    ]),
218    Word::new([
219        Felt::new(0xdbd7f9c2b149bf22),
220        Felt::new(0xb61f1889e20354a8),
221        Felt::new(0x4bb9e22ab3e4d65a),
222        Felt::new(0x9cd1da3ff563f651),
223    ]),
224    Word::new([
225        Felt::new(0x8e1d357154c2634a),
226        Felt::new(0xa644c12376fa5cae),
227        Felt::new(0xdb83acd5f00c27ab),
228        Felt::new(0xb3e2376e846bd50e),
229    ]),
230    Word::new([
231        Felt::new(0xd85519b0e2c2f289),
232        Felt::new(0x29d5604abe1203e7),
233        Felt::new(0xeb92a378922a359e),
234        Felt::new(0xde6cf31064c0eb69),
235    ]),
236    Word::new([
237        Felt::new(0x682db793679dd5f4),
238        Felt::new(0x96ef3fe1870faff2),
239        Felt::new(0x73013ec444a4d7a5),
240        Felt::new(0xcaf9d122c3e38336),
241    ]),
242    Word::new([
243        Felt::new(0x2a50e766ac3244b0),
244        Felt::new(0x53a6802d0c699901),
245        Felt::new(0xc288971f330762c3),
246        Felt::new(0x8b6c0635d1773d45),
247    ]),
248    Word::new([
249        Felt::new(0x51c847dac636a5f1),
250        Felt::new(0x698969fca5682a41),
251        Felt::new(0xa2c7cb7e23da3352),
252        Felt::new(0x5fb4b42ad093656c),
253    ]),
254    Word::new([
255        Felt::new(0xa008d253cd64a28d),
256        Felt::new(0x0724d0d35701b523),
257        Felt::new(0xaf366ea4c2d99dc7),
258        Felt::new(0xd3fac30a27fd1502),
259    ]),
260    Word::new([
261        Felt::new(0x7fd83af788bb10bd),
262        Felt::new(0x98742683f67b7f27),
263        Felt::new(0xa117a29cd88e34d0),
264        Felt::new(0xc6ae5e698c779003),
265    ]),
266    Word::new([
267        Felt::new(0x4bbfd2b901b9dfef),
268        Felt::new(0xa9080fe3b22a0325),
269        Felt::new(0xc86530265f007301),
270        Felt::new(0x8e01ae5e6c8f615d),
271    ]),
272    Word::new([
273        Felt::new(0x43f162b5392273ed),
274        Felt::new(0xd6c79ba623643952),
275        Felt::new(0xf961ca425dce47a9),
276        Felt::new(0x6887d784400afb26),
277    ]),
278    Word::new([
279        Felt::new(0x354c512d4ea52b8e),
280        Felt::new(0x5d91bebd21c6249a),
281        Felt::new(0xb0a276cfb81d599f),
282        Felt::new(0x1a7acd4a354baa3b),
283    ]),
284    Word::new([
285        Felt::new(0x788a621898e13694),
286        Felt::new(0x004e2b5b0bb7fa90),
287        Felt::new(0x59cb4c714f14cbc8),
288        Felt::new(0x02402688fee3e69b),
289    ]),
290    Word::new([
291        Felt::new(0xa9a4a6cc9e8ad4b3),
292        Felt::new(0x9eeb3b4ec6076c2b),
293        Felt::new(0x815b1ab01fef23a3),
294        Felt::new(0xf91e9d41209c1781),
295    ]),
296    Word::new([
297        Felt::new(0xdbdf8c531cddc05b),
298        Felt::new(0x9c217c8ffc968205),
299        Felt::new(0xf23b50f1647c080b),
300        Felt::new(0x0fc6963460c88ce5),
301    ]),
302    Word::new([
303        Felt::new(0x75fae0bbb7de0f22),
304        Felt::new(0xc490fee21d5a4ae7),
305        Felt::new(0xae08a07e4a727dee),
306        Felt::new(0xb814ac6a66e63c73),
307    ]),
308    Word::new([
309        Felt::new(0x5f9f6699b6ecc804),
310        Felt::new(0xe4808414b962660c),
311        Felt::new(0x15a5ba5ec4cd4f06),
312        Felt::new(0x3012b4afba294f4f),
313    ]),
314    Word::new([
315        Felt::new(0xd9f051c926775485),
316        Felt::new(0x86a4e6a7c2f3c239),
317        Felt::new(0xed7a0e2c5f58ceb9),
318        Felt::new(0x3f1b26a4da43cd0d),
319    ]),
320    Word::new([
321        Felt::new(0x2165cd0f28f3599c),
322        Felt::new(0xb50ee14aba3e7170),
323        Felt::new(0x407eaf93756a857f),
324        Felt::new(0xff39c5c2ee52a4f9),
325    ]),
326    Word::new([
327        Felt::new(0x335459b2e67f0067),
328        Felt::new(0x279b7c011b14108b),
329        Felt::new(0x86b22da12e45da48),
330        Felt::new(0xa42bccc7717df4ce),
331    ]),
332    Word::new([
333        Felt::new(0x694548f769f4895f),
334        Felt::new(0x2a4a24618314b209),
335        Felt::new(0xba6794f78b5c5b4d),
336        Felt::new(0x39ecedb9a601d9c6),
337    ]),
338    Word::new([
339        Felt::new(0x5441c2d7a579649a),
340        Felt::new(0xb4f6e2babb6e22f4),
341        Felt::new(0x4e2e474a92b8b51c),
342        Felt::new(0x0ee364795d881cc1),
343    ]),
344    Word::new([
345        Felt::new(0x875901844acc837e),
346        Felt::new(0x337fdc8fe4306ec6),
347        Felt::new(0xfd3d7e42b2ef10cd),
348        Felt::new(0x79e8ff324da10dab),
349    ]),
350    Word::new([
351        Felt::new(0x12ebb44ba4a44d5b),
352        Felt::new(0x4a2061b3541ef52f),
353        Felt::new(0x8e789cb40e742e0d),
354        Felt::new(0x171a423883764c09),
355    ]),
356    Word::new([
357        Felt::new(0x67d23a623f20da69),
358        Felt::new(0xd9e625c05be6f041),
359        Felt::new(0x93068ae492586907),
360        Felt::new(0x11a5eb7ff2417b7c),
361    ]),
362    Word::new([
363        Felt::new(0x9c3d6e2e97125ee3),
364        Felt::new(0x550479ac4d9b702c),
365        Felt::new(0xe059e7a2fa114053),
366        Felt::new(0x5abd975d30928636),
367    ]),
368    Word::new([
369        Felt::new(0x91859ed75bc15763),
370        Felt::new(0xba8b03049e91bee7),
371        Felt::new(0x545c6fd0d574bb1c),
372        Felt::new(0xf7eb3257db1f03e6),
373    ]),
374    Word::new([
375        Felt::new(0x0546e4e18a472e57),
376        Felt::new(0xecb125d13bc5068e),
377        Felt::new(0xd20ef3e739a69fdd),
378        Felt::new(0x54da5ceb579efb00),
379    ]),
380    Word::new([
381        Felt::new(0x9e6d46b0ad9e1c3f),
382        Felt::new(0x3fc49f1d3b987ec3),
383        Felt::new(0xa89dba5622cbd29d),
384        Felt::new(0x7c2d052aa927f1a6),
385    ]),
386    Word::new([
387        Felt::new(0xc987595852b3000c),
388        Felt::new(0xf4d145064450dca0),
389        Felt::new(0x3e489e33eb7a316d),
390        Felt::new(0x3d17bca9d577410e),
391    ]),
392    Word::new([
393        Felt::new(0x32666c6229bfa4ab),
394        Felt::new(0x14891937dca422fb),
395        Felt::new(0x57a753c70b0ac3d9),
396        Felt::new(0xb32446493d5464ce),
397    ]),
398    Word::new([
399        Felt::new(0xbb2c31ac5a1a3719),
400        Felt::new(0x6d6a26ba7f3cc71b),
401        Felt::new(0x6c58ba151bf46fa1),
402        Felt::new(0x8a9ee566cb189e35),
403    ]),
404    Word::new([
405        Felt::new(0xe2223d554d0c5af4),
406        Felt::new(0x1e6fcd33a2bd8055),
407        Felt::new(0x118b06a85a99be06),
408        Felt::new(0x07497b70207a9a50),
409    ]),
410    Word::new([
411        Felt::new(0x8b703d584eb67496),
412        Felt::new(0x3edfc05cfabfe2e8),
413        Felt::new(0x4743b9b2b46f9544),
414        Felt::new(0x47489dffb5959b15),
415    ]),
416    Word::new([
417        Felt::new(0x666cc8c5f556b230),
418        Felt::new(0x5c662624781d1eda),
419        Felt::new(0x162e768abdbe8770),
420        Felt::new(0xd7ba85dd1e72d4a1),
421    ]),
422    Word::new([
423        Felt::new(0x86aebabad91fedae),
424        Felt::new(0x0c56212bfc3e07f2),
425        Felt::new(0x05fdaed4545675ea),
426        Felt::new(0xfbf1e5af0f29d30f),
427    ]),
428    Word::new([
429        Felt::new(0x07ead4607e3284b1),
430        Felt::new(0x19f892ec975e1aa0),
431        Felt::new(0xe31cb5d20d65b858),
432        Felt::new(0x0156637a0ba0630d),
433    ]),
434    Word::new([
435        Felt::new(0xee94681b12771edc),
436        Felt::new(0xaeb787acd51af0a5),
437        Felt::new(0x97ea46f0e59979ac),
438        Felt::new(0x0aedd1a12ef5a3da),
439    ]),
440    Word::new([
441        Felt::new(0xcc4dde18f244c0a3),
442        Felt::new(0x75593abedbca1f75),
443        Felt::new(0x0745f7e503834bb5),
444        Felt::new(0xd1aa72f11080e143),
445    ]),
446    Word::new([
447        Felt::new(0x2b03d6780b868555),
448        Felt::new(0xca3486641ed48f15),
449        Felt::new(0xeed3ea4297d7c4ff),
450        Felt::new(0x4e374623b5f5d940),
451    ]),
452    Word::new([
453        Felt::new(0x86a0f718a27d9508),
454        Felt::new(0x5fe00cf82985a4bf),
455        Felt::new(0xe70dab7244c1d756),
456        Felt::new(0xfe84713dc37216a7),
457    ]),
458    Word::new([
459        Felt::new(0xab9b7d9d92dc8e92),
460        Felt::new(0xd367e47cb409abb9),
461        Felt::new(0xb0815c449b50d320),
462        Felt::new(0x8bf91e2671a502cc),
463    ]),
464    Word::new([
465        Felt::new(0x37e21999cca2af2a),
466        Felt::new(0x5d4c3fdae52fd6e3),
467        Felt::new(0x7c2a63f243083424),
468        Felt::new(0x85bc46e3253ced12),
469    ]),
470    Word::new([
471        Felt::new(0x359397ff99b106dc),
472        Felt::new(0x5af7da08fbd5ed37),
473        Felt::new(0xbf4bcfc7f30cddc9),
474        Felt::new(0xdf5e505deea050ae),
475    ]),
476    Word::new([
477        Felt::new(0x567e60727d9e8a69),
478        Felt::new(0xaddb2e33493bb678),
479        Felt::new(0x63e8f4fd813a8717),
480        Felt::new(0x7e6f327033191fa1),
481    ]),
482    Word::new([
483        Felt::new(0xc493169726e44d47),
484        Felt::new(0xb0d73f7dec4405e2),
485        Felt::new(0x12ce496206bd1144),
486        Felt::new(0x0489ebc41b5ff277),
487    ]),
488    Word::new([
489        Felt::new(0x12eac3132c52f64c),
490        Felt::new(0xe9c1587c49a823b5),
491        Felt::new(0x9bc86b1fb88516e7),
492        Felt::new(0xa7e5a3ce7c7374b9),
493    ]),
494    Word::new([
495        Felt::new(0xdab4168ab42c968d),
496        Felt::new(0x780f9ddf4a4e3571),
497        Felt::new(0x0dfbd49cc0ff60a9),
498        Felt::new(0x463559b7c08224e6),
499    ]),
500    Word::new([
501        Felt::new(0xc6a2d68bc98659d8),
502        Felt::new(0x923f6036bde4a662),
503        Felt::new(0xf5ec79864915ff3e),
504        Felt::new(0xef3a9bdfd5fdde4a),
505    ]),
506    Word::new([
507        Felt::new(0x4d7b39df2a6682ab),
508        Felt::new(0xce7139c699c438a7),
509        Felt::new(0x1837e393fef489e9),
510        Felt::new(0x812d088b2b983f55),
511    ]),
512    Word::new([
513        Felt::new(0x5720a4c993c56a60),
514        Felt::new(0xe25fcbb6156c7dba),
515        Felt::new(0x35c12e8b8141b466),
516        Felt::new(0x8eda168f7eff7b35),
517    ]),
518    Word::new([
519        Felt::new(0xcf01f59c2e72b382),
520        Felt::new(0xe94386684f8ed2bf),
521        Felt::new(0xb6d7ba96cafc9994),
522        Felt::new(0xa8d5bbe975e059f0),
523    ]),
524    Word::new([
525        Felt::new(0x35f676b56b532441),
526        Felt::new(0xebe05922a3cc819c),
527        Felt::new(0x6284a94f8f871e5f),
528        Felt::new(0xf24d26cf4d21afb9),
529    ]),
530    Word::new([
531        Felt::new(0x27a4b6e402d091bf),
532        Felt::new(0xb14dbda6f732a9e4),
533        Felt::new(0xda4f85b0e8f66e2b),
534        Felt::new(0xf817d6f9d274e1ba),
535    ]),
536    Word::new([
537        Felt::new(0xce4b5c3f48025345),
538        Felt::new(0x5d73b65785aab19f),
539        Felt::new(0x53b3ec2fbcb30503),
540        Felt::new(0xc4a5badd310cd88e),
541    ]),
542    Word::new([
543        Felt::new(0x88cc10e54f12c5ed),
544        Felt::new(0x411a746abc87ed3b),
545        Felt::new(0x2f1b94e4462119bc),
546        Felt::new(0x4b7e537ad6e5104b),
547    ]),
548    Word::new([
549        Felt::new(0x8260499fb2360775),
550        Felt::new(0xca531419eaab87d0),
551        Felt::new(0x2c8f6ffffbc730e3),
552        Felt::new(0x2a542eeb199e0188),
553    ]),
554    Word::new([
555        Felt::new(0xa3055a3f70793f26),
556        Felt::new(0x0a3b2cc605ef4732),
557        Felt::new(0xba8d01a69068b828),
558        Felt::new(0x810cefa092abdbbf),
559    ]),
560    Word::new([
561        Felt::new(0x78c362cc4aaa4dd4),
562        Felt::new(0x7b4757319188651d),
563        Felt::new(0x181e324be417bd15),
564        Felt::new(0x155c8ed6282f7e86),
565    ]),
566    Word::new([
567        Felt::new(0x95dcdd0def238a6f),
568        Felt::new(0x559999f6fa5f08a4),
569        Felt::new(0x66d1e52cd3c59b7b),
570        Felt::new(0xec49070012294ee9),
571    ]),
572    Word::new([
573        Felt::new(0x870ba5b4c7120439),
574        Felt::new(0x22b26a1f6dedb83c),
575        Felt::new(0x388be0894aab204a),
576        Felt::new(0xd352c8ac653b3add),
577    ]),
578    Word::new([
579        Felt::new(0x3b3b01bf43cb6ea2),
580        Felt::new(0xc95149e67675dc57),
581        Felt::new(0xbdb065f63b34a784),
582        Felt::new(0xb05d7b591c39496c),
583    ]),
584    Word::new([
585        Felt::new(0x700765b29ce6a984),
586        Felt::new(0x487f2aad500ea0d8),
587        Felt::new(0xb19b89448f839bf4),
588        Felt::new(0xf087f0f19f7212cd),
589    ]),
590    Word::new([
591        Felt::new(0xf6d142dcfc2dbdfd),
592        Felt::new(0xa90dc638201ba6ee),
593        Felt::new(0xcbf567a319c880b4),
594        Felt::new(0x7d9ff5233020a341),
595    ]),
596    Word::new([
597        Felt::new(0xa36d9cc70b13c4cf),
598        Felt::new(0xe6d9208c49661fe2),
599        Felt::new(0xa335db806dcc1072),
600        Felt::new(0x3f701c87e5664389),
601    ]),
602    Word::new([
603        Felt::new(0x9b572bf042261f9b),
604        Felt::new(0x410dc7708306726e),
605        Felt::new(0x7e8fa17f0dad1f9b),
606        Felt::new(0xddd5d4cbdf070f10),
607    ]),
608    Word::new([
609        Felt::new(0xd5295c577641c9b2),
610        Felt::new(0xfe37beaaf966a996),
611        Felt::new(0x25324add6afc9701),
612        Felt::new(0x370c1b4b32e05189),
613    ]),
614    Word::new([
615        Felt::new(0x7052a5fcfb4b5f20),
616        Felt::new(0x5cc07e64180dba47),
617        Felt::new(0xe62a8d19ad29af7d),
618        Felt::new(0xcbfff28ef21ed355),
619    ]),
620    Word::new([
621        Felt::new(0xec08e75dd21ccba5),
622        Felt::new(0x0e453d4fbc8f33e4),
623        Felt::new(0xaf65358edc0dde3d),
624        Felt::new(0xedf1f85ea9557ffc),
625    ]),
626    Word::new([
627        Felt::new(0xbf0742d96d410028),
628        Felt::new(0x8cc49e4edb48965e),
629        Felt::new(0xf36263ffc2dd1b71),
630        Felt::new(0x7c8e5a64d9815b3b),
631    ]),
632    Word::new([
633        Felt::new(0x7175b516eb9d97af),
634        Felt::new(0xd0f6f208f300a47c),
635        Felt::new(0x2d2ff1c7e93b28f4),
636        Felt::new(0xe5aa10f76b3d71f5),
637    ]),
638    Word::new([
639        Felt::new(0x47af3319e908137e),
640        Felt::new(0x77a6e80674004b8b),
641        Felt::new(0x9023839df1c9e1f9),
642        Felt::new(0x9b6ce63cc65d2757),
643    ]),
644    Word::new([
645        Felt::new(0x30742f2e5602e399),
646        Felt::new(0xfcdf70bba95b7358),
647        Felt::new(0xe2fd987d05ecdb8a),
648        Felt::new(0x155ac789fb89403d),
649    ]),
650    Word::new([
651        Felt::new(0x5dffc0444bd3688b),
652        Felt::new(0x4b68b14225fd3604),
653        Felt::new(0xb967634b410b1a73),
654        Felt::new(0x6c0f6783006aaa4d),
655    ]),
656    Word::new([
657        Felt::new(0xbec989eda65bfd98),
658        Felt::new(0x10450a3aca653113),
659        Felt::new(0x09823d415301e260),
660        Felt::new(0x83c459041b044921),
661    ]),
662    Word::new([
663        Felt::new(0x704ea1315a3c372b),
664        Felt::new(0xfe3ebe5b02b66532),
665        Felt::new(0xfe8e37e2c2a996cd),
666        Felt::new(0xc7e23f42d146aab8),
667    ]),
668    Word::new([
669        Felt::new(0x34518952a9c13963),
670        Felt::new(0x67a7efc16364b020),
671        Felt::new(0x05429574811e470c),
672        Felt::new(0x9f25ec1ebbebec78),
673    ]),
674    Word::new([
675        Felt::new(0xfd70b8e960ddb2cb),
676        Felt::new(0x235e94f4d0068cad),
677        Felt::new(0x57ba64f6fd33a07d),
678        Felt::new(0xf5e9be1498c2e243),
679    ]),
680    Word::new([
681        Felt::new(0x2d3d473a4c0f4022),
682        Felt::new(0x1b244b25a3ecadf1),
683        Felt::new(0xe855d144de4bd14d),
684        Felt::new(0x56282deb6a0ec7fe),
685    ]),
686    Word::new([
687        Felt::new(0x5848e8580c68aa7c),
688        Felt::new(0xa3dcc518c329f378),
689        Felt::new(0x6ee02b80fdd99213),
690        Felt::new(0x2575ab55891f15ff),
691    ]),
692    Word::new([
693        Felt::new(0xebada5cb5bb83bb3),
694        Felt::new(0xc9c76a48b826d274),
695        Felt::new(0x8412fd732379fb33),
696        Felt::new(0x07e2664d33d36fa4),
697    ]),
698    Word::new([
699        Felt::new(0x988fd5a250b1b40a),
700        Felt::new(0x542d30d05090539e),
701        Felt::new(0x6e3504d6a03607cf),
702        Felt::new(0xf2246eee8300984f),
703    ]),
704    Word::new([
705        Felt::new(0x109b3acdc552fae8),
706        Felt::new(0xdd68d5a7226e4631),
707        Felt::new(0x5b88ec90433c1e7c),
708        Felt::new(0xf11315763e01912b),
709    ]),
710    Word::new([
711        Felt::new(0xb6701421be588640),
712        Felt::new(0xc14dd230ceb161a2),
713        Felt::new(0x6893c74a74f31403),
714        Felt::new(0xea01a82649f6dcdc),
715    ]),
716    Word::new([
717        Felt::new(0x10283c7df5f217a9),
718        Felt::new(0x6c3dca0ab6897e83),
719        Felt::new(0x9e7eec19b4184699),
720        Felt::new(0xd9727b457ccbc2b8),
721    ]),
722    Word::new([
723        Felt::new(0x5a5909a772bbb426),
724        Felt::new(0xc93992bc91b011c4),
725        Felt::new(0xd5eea93f55e1afca),
726        Felt::new(0xd0740d01853554f6),
727    ]),
728    Word::new([
729        Felt::new(0xe4b9fb13511684df),
730        Felt::new(0xb3e3778dd9ce82e7),
731        Felt::new(0x054e6fba0c8b873b),
732        Felt::new(0xc7db268ebb31f73a),
733    ]),
734    Word::new([
735        Felt::new(0x94ad755f91cfc69c),
736        Felt::new(0x364ad9b084460a84),
737        Felt::new(0x4225747075ff8e77),
738        Felt::new(0x71251602ae91069b),
739    ]),
740    Word::new([
741        Felt::new(0xd460369d74b2a756),
742        Felt::new(0xe68b74a4ce55495a),
743        Felt::new(0x5970fc0497d83b7e),
744        Felt::new(0x7febce94338a1449),
745    ]),
746    Word::new([
747        Felt::new(0xd43b3d1f844a1ead),
748        Felt::new(0xf0d5da85ce1c1861),
749        Felt::new(0xfd10bda41bfda3f4),
750        Felt::new(0xe503116a9c37c678),
751    ]),
752    Word::new([
753        Felt::new(0x2ba7ff5da227f5b1),
754        Felt::new(0x6d99d0ca2d6e2f20),
755        Felt::new(0x55f2fab50778d043),
756        Felt::new(0xebd80de8ffea5e79),
757    ]),
758    Word::new([
759        Felt::new(0x5ce5419daa27376e),
760        Felt::new(0x8a6c000961dbafca),
761        Felt::new(0xe94aab9d599d63e4),
762        Felt::new(0x83a2202191a77859),
763    ]),
764    Word::new([
765        Felt::new(0x6e96352e7ad6d211),
766        Felt::new(0x17a0fd498269729c),
767        Felt::new(0xca3ee252b136307a),
768        Felt::new(0x95e3db23c78412cd),
769    ]),
770    Word::new([
771        Felt::new(0x9b074ce0916bb459),
772        Felt::new(0x47733a8262d8618a),
773        Felt::new(0xdc426c3f66253547),
774        Felt::new(0x5a003cdd6aefeaa4),
775    ]),
776    Word::new([
777        Felt::new(0x6501daa92c53d863),
778        Felt::new(0x5d9c61a7bc7c12f6),
779        Felt::new(0x0e064127315e13df),
780        Felt::new(0x766824f9adabd9a9),
781    ]),
782    Word::new([
783        Felt::new(0x4bbcc1f9bfc36037),
784        Felt::new(0x94592e04aef2047b),
785        Felt::new(0x1230ad895858c112),
786        Felt::new(0xd2a07c006c94050c),
787    ]),
788    Word::new([
789        Felt::new(0x38ee2f4837c28d2c),
790        Felt::new(0xe284a8c09189604c),
791        Felt::new(0xebd72086dca0ac2a),
792        Felt::new(0xc6dd43e307c6560f),
793    ]),
794    Word::new([
795        Felt::new(0x5d80a21551fdb81c),
796        Felt::new(0xf47eb3d8bfce0fe2),
797        Felt::new(0x936aec656d34aca1),
798        Felt::new(0x3a9fa674bab063d0),
799    ]),
800    Word::new([
801        Felt::new(0x4584177925505f0c),
802        Felt::new(0x2c06394dc3c8b525),
803        Felt::new(0xb418bb11fc87f664),
804        Felt::new(0x2f2dd03d9035808a),
805    ]),
806    Word::new([
807        Felt::new(0xadd647fa0d07420e),
808        Felt::new(0x172f967db343e4ac),
809        Felt::new(0xfec7a4b2cd2ce36a),
810        Felt::new(0x11359b39c2c12eae),
811    ]),
812    Word::new([
813        Felt::new(0xa53bf8e872ab17cf),
814        Felt::new(0x3e646eb81992887b),
815        Felt::new(0x8df625a197135d6c),
816        Felt::new(0xc9eb62cbf73b8afb),
817    ]),
818    Word::new([
819        Felt::new(0xb2fa941b228d6f3a),
820        Felt::new(0xc56418d9e7de11d0),
821        Felt::new(0x4898d1fce23143d4),
822        Felt::new(0xe2eb8742ddce4cdd),
823    ]),
824    Word::new([
825        Felt::new(0x67e8ad66c18c6335),
826        Felt::new(0x1b25e193d55e3a3f),
827        Felt::new(0x01b5285d164fd026),
828        Felt::new(0xf32b4a5ebee92d50),
829    ]),
830    Word::new([
831        Felt::new(0x87e613a4c555ab74),
832        Felt::new(0x4a09621b5c561c96),
833        Felt::new(0x2b64ab15aab3666b),
834        Felt::new(0xfd04e14a8a0b6c09),
835    ]),
836    Word::new([
837        Felt::new(0x3f970c2db33f5242),
838        Felt::new(0x80a3fcb6661723a2),
839        Felt::new(0xa82ec8a677866efd),
840        Felt::new(0x5a82e39fdb2313f6),
841    ]),
842    Word::new([
843        Felt::new(0x2797ceaaa67c8131),
844        Felt::new(0x26f3c1c666d3c505),
845        Felt::new(0xb7c0b86783c25696),
846        Felt::new(0x2280f9f50af34b3a),
847    ]),
848    Word::new([
849        Felt::new(0x4bc36a52bdf92a1a),
850        Felt::new(0x25af7d67f1426927),
851        Felt::new(0x78d32e715406b40d),
852        Felt::new(0xf5bd9122df7f8678),
853    ]),
854    Word::new([
855        Felt::new(0xf688c0c29f9437fa),
856        Felt::new(0x1f81eebf8878f6d4),
857        Felt::new(0x186a6d4490941249),
858        Felt::new(0xf63cda0d6f269065),
859    ]),
860    Word::new([
861        Felt::new(0x84f3d1ebcfaa1562),
862        Felt::new(0x9cce9d6adbb76865),
863        Felt::new(0x94fa01600dd11898),
864        Felt::new(0xd5458829b4130256),
865    ]),
866    Word::new([
867        Felt::new(0x16a747be6063b1b5),
868        Felt::new(0xb9996c5b744aedbf),
869        Felt::new(0x8e8e4acaea70053c),
870        Felt::new(0xa7282c670831d43b),
871    ]),
872    Word::new([
873        Felt::new(0x483ee342c011f7f9),
874        Felt::new(0x5c0c9fe86bc86b67),
875        Felt::new(0x4cddd40605793509),
876        Felt::new(0x381429922edcb020),
877    ]),
878    Word::new([
879        Felt::new(0xa59ed90c1ca60698),
880        Felt::new(0x09981a7f81544b7b),
881        Felt::new(0xf953c75c139fdc85),
882        Felt::new(0x260fb0632f3efab2),
883    ]),
884    Word::new([
885        Felt::new(0x4afefea9330f4c0e),
886        Felt::new(0x466621aa41ab021a),
887        Felt::new(0x1bdc06a9a25d619d),
888        Felt::new(0xd6e857e49b7cbfd4),
889    ]),
890    Word::new([
891        Felt::new(0x25b3e8478af5493e),
892        Felt::new(0x0508193caa22a375),
893        Felt::new(0xc6261bed917be14b),
894        Felt::new(0xe03bea63fb71cbf5),
895    ]),
896    Word::new([
897        Felt::new(0x8ebca1d27c35d685),
898        Felt::new(0x8fbf4f9ab6b18930),
899        Felt::new(0x21c8ff832ef2b4b6),
900        Felt::new(0x53a3363026b09a01),
901    ]),
902    Word::new([
903        Felt::new(0x57253100597ad1ec),
904        Felt::new(0x9e3ad735bac054aa),
905        Felt::new(0x84bea83f5aff0950),
906        Felt::new(0x6cad0be6ccd7cf55),
907    ]),
908    Word::new([
909        Felt::new(0x8abc91c5bfc02ecc),
910        Felt::new(0xaa0126e4c41988c1),
911        Felt::new(0xc9c83cfb8f4e08f2),
912        Felt::new(0x7d25ae8c2a18f4f2),
913    ]),
914    Word::new([
915        Felt::new(0x5a9ccf2cb7b0993a),
916        Felt::new(0x20e0cc8e09a5584d),
917        Felt::new(0xccb156feb1d4b9b5),
918        Felt::new(0x0f3f16b2d1be0575),
919    ]),
920    Word::new([
921        Felt::new(0xde12ff9ef674c614),
922        Felt::new(0x74c16547bbf8260c),
923        Felt::new(0xacc3eae06a9aef55),
924        Felt::new(0x2a2d94e77b6189c2),
925    ]),
926    Word::new([
927        Felt::new(0x2fa228aeb96f2623),
928        Felt::new(0xf8a57adfcdccf641),
929        Felt::new(0xbf552b92065ac157),
930        Felt::new(0x5130f01fc96b62e2),
931    ]),
932    Word::new([
933        Felt::new(0x1bdc44006adb1698),
934        Felt::new(0x5151ca32eddac5d1),
935        Felt::new(0xfd72f666343f784c),
936        Felt::new(0xfd132ba4bb738826),
937    ]),
938    Word::new([
939        Felt::new(0xdd45068ab899fa71),
940        Felt::new(0x1367ac815e888410),
941        Felt::new(0x1a800820d67e7e55),
942        Felt::new(0x9960bb8fd886e2ae),
943    ]),
944    Word::new([
945        Felt::new(0x802517284c772d85),
946        Felt::new(0x5c962d1d0a4e1c25),
947        Felt::new(0x08f61eebbe4fbe76),
948        Felt::new(0x85228c63c7a49efd),
949    ]),
950    Word::new([
951        Felt::new(0x9cb407455c288be8),
952        Felt::new(0x2e1043b2cc13875c),
953        Felt::new(0x8f3872b43eb40cb9),
954        Felt::new(0x2f5298b8d703c092),
955    ]),
956    Word::new([
957        Felt::new(0xf9b409b5dfa20237),
958        Felt::new(0x509cdf91d771c4c0),
959        Felt::new(0xa03399ef00003e9a),
960        Felt::new(0x137fee82f099bfdc),
961    ]),
962    Word::new([
963        Felt::new(0x6200c7bc52786a84),
964        Felt::new(0x07e208e9a6d8297b),
965        Felt::new(0x6d88fc6e7017c6ad),
966        Felt::new(0xb5c8fdacfa860fde),
967    ]),
968    Word::new([
969        Felt::new(0x3fa86b8fc6371912),
970        Felt::new(0x4babf426ae37d40f),
971        Felt::new(0xd8ce6543bd8b9bbb),
972        Felt::new(0x47a7cb0b6b6a242d),
973    ]),
974    Word::new([
975        Felt::new(0x8bdb240e415d744a),
976        Felt::new(0x35aaf2b9ecae3ebc),
977        Felt::new(0xcfdc0a1b426abeb3),
978        Felt::new(0x592fee4621dcc2bf),
979    ]),
980    Word::new([
981        Felt::new(0x71f086dc9626aa9d),
982        Felt::new(0xab58f57b141c9806),
983        Felt::new(0x7f47c3feea78e6a1),
984        Felt::new(0xf8ade27ff44ef11c),
985    ]),
986    Word::new([
987        Felt::new(0x50ee5035b0d85667),
988        Felt::new(0x1bdcf2544d9cb2a7),
989        Felt::new(0x3ee4c339793a054b),
990        Felt::new(0x9e788acc61d1b6e8),
991    ]),
992    Word::new([
993        Felt::new(0x37650cb60969e966),
994        Felt::new(0xfe9247256673163a),
995        Felt::new(0x240611a46d8024a7),
996        Felt::new(0x50496ee909404115),
997    ]),
998    Word::new([
999        Felt::new(0x95f0de9ec639c51a),
1000        Felt::new(0xc900fb33ff6c757b),
1001        Felt::new(0x2ec20d0eaa39a048),
1002        Felt::new(0x14362711cd47de96),
1003    ]),
1004    Word::new([
1005        Felt::new(0x6d7ce36fe1803e4b),
1006        Felt::new(0xca4b3ee42416ba15),
1007        Felt::new(0xaa8f0737e9fc1f07),
1008        Felt::new(0x5b726c41400665ca),
1009    ]),
1010    Word::new([
1011        Felt::new(0x7be99fbb68e1bc97),
1012        Felt::new(0x2bb479bb52c6426e),
1013        Felt::new(0x454d3aea7c6d06a7),
1014        Felt::new(0xcd613f3f9841a48f),
1015    ]),
1016    Word::new([
1017        Felt::new(0x4b4832c38acc0b61),
1018        Felt::new(0x1ff6eba8026046a5),
1019        Felt::new(0xab74b76254ac5c8c),
1020        Felt::new(0x29cac392e4f3cc7f),
1021    ]),
1022    Word::new([
1023        Felt::new(0x01fdbfd0b87f2e09),
1024        Felt::new(0x4e074d6a472fd5b6),
1025        Felt::new(0x628d930e44c871c8),
1026        Felt::new(0x5a3e619eaed03283),
1027    ]),
1028    Word::new([
1029        Felt::new(0x8c19096097e3df12),
1030        Felt::new(0xe8857578a1bdbb8c),
1031        Felt::new(0x50689e0cb310f595),
1032        Felt::new(0xbe1742c30b7e11a2),
1033    ]),
1034    Word::new([
1035        Felt::new(0x9fd9929dfd838547),
1036        Felt::new(0x59ad7ecd6f8561e9),
1037        Felt::new(0x9be7ed4a7d558164),
1038        Felt::new(0x3cc5e790310cf87e),
1039    ]),
1040    Word::new([
1041        Felt::new(0x5988ffa09e5dc662),
1042        Felt::new(0xdf77e0b8bed90f25),
1043        Felt::new(0x96f3e807bf0af8ee),
1044        Felt::new(0x9efc143168113a8d),
1045    ]),
1046    Word::new([
1047        Felt::new(0xf03f6198aa069685),
1048        Felt::new(0x862768943cc33dfe),
1049        Felt::new(0x79fd7dce8353cc21),
1050        Felt::new(0xa70883055a67410b),
1051    ]),
1052    Word::new([
1053        Felt::new(0x958be73cd7b9b636),
1054        Felt::new(0xda82710cf709d664),
1055        Felt::new(0xfcc735123f454965),
1056        Felt::new(0x1db6d0ca80ef235b),
1057    ]),
1058    Word::new([
1059        Felt::new(0xd986e1c34a8e7e0a),
1060        Felt::new(0xc8bc3f0f6d634738),
1061        Felt::new(0x59c01743c8c45a1e),
1062        Felt::new(0x30f70c57c98be4e1),
1063    ]),
1064    Word::new([
1065        Felt::new(0xfa731977e87b88cb),
1066        Felt::new(0x0211fc99064cf66d),
1067        Felt::new(0x62f91f0452839651),
1068        Felt::new(0xfd0459b3324291eb),
1069    ]),
1070    Word::new([
1071        Felt::new(0xdf34097258613c7f),
1072        Felt::new(0x92777ff51538e1c1),
1073        Felt::new(0x5d38328f0ab20b20),
1074        Felt::new(0xea5bad665b2bdb69),
1075    ]),
1076    Word::new([
1077        Felt::new(0xce9415c1103d41c8),
1078        Felt::new(0x33e56c7b98737652),
1079        Felt::new(0x98cf8572aadbb142),
1080        Felt::new(0x8cdd8dd5f33db9be),
1081    ]),
1082    Word::new([
1083        Felt::new(0xbad69843fd27a859),
1084        Felt::new(0x1f01e096692c3c59),
1085        Felt::new(0x5bfccc8353013d54),
1086        Felt::new(0x273d211cdce77fb8),
1087    ]),
1088    Word::new([
1089        Felt::new(0x0ae0e050c52d9381),
1090        Felt::new(0xec0d7b0182f942c9),
1091        Felt::new(0x167d0024d0e180c2),
1092        Felt::new(0xc3a4758a8e8ff5cb),
1093    ]),
1094    Word::new([
1095        Felt::new(0xb6c9793eaadcbc77),
1096        Felt::new(0x44f0017595bfe256),
1097        Felt::new(0xec78adf967a3214a),
1098        Felt::new(0x4e3aa60340d68e65),
1099    ]),
1100    Word::new([
1101        Felt::new(0x3faa82b5fbd1f467),
1102        Felt::new(0xbce0c8978c146e9c),
1103        Felt::new(0x7f47470c22e93fd4),
1104        Felt::new(0x3fb93441b389d389),
1105    ]),
1106    Word::new([
1107        Felt::new(0x7193f11b620b1a0d),
1108        Felt::new(0x49b062199d57ebe6),
1109        Felt::new(0x0a31c04000656106),
1110        Felt::new(0xaf7d7a07a6eb73e7),
1111    ]),
1112    Word::new([
1113        Felt::new(0xbfc8f3debeaaccb9),
1114        Felt::new(0x027bb07371639273),
1115        Felt::new(0xf8cd94ccd8829c21),
1116        Felt::new(0x0d698f9d65d14061),
1117    ]),
1118    Word::new([
1119        Felt::new(0x9bacc29ba7a25d59),
1120        Felt::new(0x1168877e510ed38d),
1121        Felt::new(0xa37e780648f00d11),
1122        Felt::new(0xdd1419b32e808e01),
1123    ]),
1124    Word::new([
1125        Felt::new(0x686e16bf96e0dffa),
1126        Felt::new(0x2a66ea7ed019ac55),
1127        Felt::new(0x4a13653de99f10ae),
1128        Felt::new(0x90891fb044c67756),
1129    ]),
1130    Word::new([
1131        Felt::new(0xf7f4c880706aec96),
1132        Felt::new(0xb962efabc033df77),
1133        Felt::new(0x14f21eb75e04e815),
1134        Felt::new(0xf6079d7fb6ee39f8),
1135    ]),
1136    Word::new([
1137        Felt::new(0xae3145790a30ba67),
1138        Felt::new(0x6b7115acd8d16e1e),
1139        Felt::new(0xec9651fea505b477),
1140        Felt::new(0x341ebac3f7cd1a77),
1141    ]),
1142    Word::new([
1143        Felt::new(0xa7a693e65d7b485a),
1144        Felt::new(0x07ecc806fb91d03b),
1145        Felt::new(0x9925566ced31f668),
1146        Felt::new(0x3d6cf66a05ad36d1),
1147    ]),
1148    Word::new([
1149        Felt::new(0x310efab3f050e9cc),
1150        Felt::new(0x6907608ddc657b5b),
1151        Felt::new(0x31ee000b84e51290),
1152        Felt::new(0x06ce4e8ef44a412a),
1153    ]),
1154    Word::new([
1155        Felt::new(0x5cffd24924aca24d),
1156        Felt::new(0xe0f4f6bc74efc000),
1157        Felt::new(0x81ffffb283f2091b),
1158        Felt::new(0xad216176fa87fd9f),
1159    ]),
1160    Word::new([
1161        Felt::new(0xdf7d4f7042a35716),
1162        Felt::new(0x2efb3ba83af345b4),
1163        Felt::new(0x382b6f6943ae6efd),
1164        Felt::new(0x4953f27954478314),
1165    ]),
1166    Word::new([
1167        Felt::new(0x87d503581afe38a7),
1168        Felt::new(0x5cc6c0d05007c364),
1169        Felt::new(0xf7142e232a4ebe1c),
1170        Felt::new(0x5cb6382efbaa7b04),
1171    ]),
1172    Word::new([
1173        Felt::new(0x1b694df14813c23d),
1174        Felt::new(0x018501129fd167ae),
1175        Felt::new(0x16836cb666963beb),
1176        Felt::new(0x9ccefcb3c111d2c1),
1177    ]),
1178    Word::new([
1179        Felt::new(0xc9aa885f6b1eebca),
1180        Felt::new(0xc8ed5b8d25810804),
1181        Felt::new(0xd8219dbbcc7da1e7),
1182        Felt::new(0x337431a1eda8563f),
1183    ]),
1184    Word::new([
1185        Felt::new(0x31eba37c60bd1682),
1186        Felt::new(0x6eca92986b0d2b8c),
1187        Felt::new(0xbbf6f1248083a544),
1188        Felt::new(0x384c22650b3be05a),
1189    ]),
1190    Word::new([
1191        Felt::new(0xa08dba24fe1fc506),
1192        Felt::new(0x63bf0cea699af3b1),
1193        Felt::new(0x738d154ea773b70f),
1194        Felt::new(0x1f15fbc12a759dc1),
1195    ]),
1196    Word::new([
1197        Felt::new(0x6ecb8966d3e3a1d2),
1198        Felt::new(0x4ffe6eef4bde94c9),
1199        Felt::new(0x4154d42d2951e5e1),
1200        Felt::new(0x716b1d675b13f7c9),
1201    ]),
1202    Word::new([
1203        Felt::new(0x6b0b5916ff352bf4),
1204        Felt::new(0xc7c47cffcf547b8a),
1205        Felt::new(0x69ef74458e4f6d09),
1206        Felt::new(0x94a5991fb68d83a6),
1207    ]),
1208    Word::new([
1209        Felt::new(0x6cdcb02959571505),
1210        Felt::new(0x207b77cfbe672a42),
1211        Felt::new(0xbdd76d575b1bf415),
1212        Felt::new(0xfd2829a667bc6610),
1213    ]),
1214    Word::new([
1215        Felt::new(0x27e655c213ab7557),
1216        Felt::new(0xc498abff9684e414),
1217        Felt::new(0xabd9b1f29e46169e),
1218        Felt::new(0x2c3334a6d114ad33),
1219    ]),
1220    Word::new([
1221        Felt::new(0x2c4d010b6cdb496b),
1222        Felt::new(0xa2c41e518763d815),
1223        Felt::new(0x06d40f064444d6e6),
1224        Felt::new(0x3ae548cb8d057afd),
1225    ]),
1226    Word::new([
1227        Felt::new(0x737e01ec9910cfda),
1228        Felt::new(0xa2c941998d808f61),
1229        Felt::new(0xdd6b4a8029796504),
1230        Felt::new(0x2f68cfed183ccc34),
1231    ]),
1232    Word::new([
1233        Felt::new(0x23f669d9ce07f077),
1234        Felt::new(0x6f3dc43dc02c6f1d),
1235        Felt::new(0xf3f1e3541c6117c7),
1236        Felt::new(0x28a571e36abbaace),
1237    ]),
1238    Word::new([
1239        Felt::new(0x6da85ec3f33ba133),
1240        Felt::new(0x252355a98a6cd911),
1241        Felt::new(0x63b15077f053f4bc),
1242        Felt::new(0x1ae62ec16fd7fdbc),
1243    ]),
1244    Word::new([
1245        Felt::new(0xf70f5db5aff03727),
1246        Felt::new(0xc65b599e71d7caaa),
1247        Felt::new(0x6044114442d565d2),
1248        Felt::new(0x62ea7655d3d0c330),
1249    ]),
1250    Word::new([
1251        Felt::new(0x0866c3e684c9e35f),
1252        Felt::new(0x0f33c50c313e5bfa),
1253        Felt::new(0x6dcf72e37d2dcca3),
1254        Felt::new(0x3704807cd3c6de92),
1255    ]),
1256    Word::new([
1257        Felt::new(0x2c417271018b4372),
1258        Felt::new(0xf4d10ace12df9588),
1259        Felt::new(0xcbdf0a4fb229b7c1),
1260        Felt::new(0xcf5a4c3002e65541),
1261    ]),
1262    Word::new([
1263        Felt::new(0xcfaac25cac74c895),
1264        Felt::new(0xc9af6f14973154e6),
1265        Felt::new(0x8b6041d1a7fbb3c0),
1266        Felt::new(0x2fd4d6b578efee90),
1267    ]),
1268    Word::new([
1269        Felt::new(0x7ecbfb9c2c47516a),
1270        Felt::new(0x53aee5487ab0c680),
1271        Felt::new(0xac92711629c37a75),
1272        Felt::new(0x2945f4166fd590c7),
1273    ]),
1274    Word::new([
1275        Felt::new(0xc67642914b052720),
1276        Felt::new(0x91d323ce00bf1118),
1277        Felt::new(0xdcb6c341847197f9),
1278        Felt::new(0x3715874d9a4157ff),
1279    ]),
1280    Word::new([
1281        Felt::new(0x018dc9a4b47d35a4),
1282        Felt::new(0x84578f992a4b57ae),
1283        Felt::new(0x53dba2deb351f882),
1284        Felt::new(0xeeb3a4e41e19d3ac),
1285    ]),
1286    Word::new([
1287        Felt::new(0x19f3ddef203b4eaa),
1288        Felt::new(0xc330bc99572590b7),
1289        Felt::new(0xc40ce83bfbf50a51),
1290        Felt::new(0x88ae15846aa8c47e),
1291    ]),
1292    Word::new([
1293        Felt::new(0xea95b07de74db84c),
1294        Felt::new(0x25f24c92bca74eec),
1295        Felt::new(0x6adbf8918405066e),
1296        Felt::new(0x3598a521e9dbc12f),
1297    ]),
1298    Word::new([
1299        Felt::new(0xd2b485237dc87035),
1300        Felt::new(0x9b94fcefe9761871),
1301        Felt::new(0x86b1fc36fb33059f),
1302        Felt::new(0xd9a01c3d524a1f64),
1303    ]),
1304    Word::new([
1305        Felt::new(0x6bb88e64acf6e6d3),
1306        Felt::new(0xd6218cb38e359a29),
1307        Felt::new(0xa90945f8948f466e),
1308        Felt::new(0xb5f232e3e5b6638d),
1309    ]),
1310    Word::new([
1311        Felt::new(0x18f9825adc30d124),
1312        Felt::new(0x7badbe0ccb1bdf7c),
1313        Felt::new(0x26734fb973862f42),
1314        Felt::new(0x48cb3aa280a1b610),
1315    ]),
1316    Word::new([
1317        Felt::new(0x5a242e66851f3ce1),
1318        Felt::new(0x46723ee9a9637f99),
1319        Felt::new(0xaca5e19be991e988),
1320        Felt::new(0xe6be5ec090670666),
1321    ]),
1322    Word::new([
1323        Felt::new(0xd3cac74e1c73ae96),
1324        Felt::new(0x571f9c148f6c3a29),
1325        Felt::new(0x3aab030fa1c17103),
1326        Felt::new(0x12c01509ded56d2e),
1327    ]),
1328    Word::new([
1329        Felt::new(0xfa0211fb143cffac),
1330        Felt::new(0xc4bc02a6e706d164),
1331        Felt::new(0xcd4d2f875acf7384),
1332        Felt::new(0xe1a028540085477e),
1333    ]),
1334    Word::new([
1335        Felt::new(0x5bee74efb6935aeb),
1336        Felt::new(0xc238b7ef9daf0b79),
1337        Felt::new(0x7a07d0ecad1f8e18),
1338        Felt::new(0x84298e03581c3c73),
1339    ]),
1340    Word::new([
1341        Felt::new(0xe8eba3dab0f4aaea),
1342        Felt::new(0xe7884a653a1ec6f5),
1343        Felt::new(0x1c46ca905461cef0),
1344        Felt::new(0x8f6511bd67d1d26a),
1345    ]),
1346    Word::new([
1347        Felt::new(0x9ce806ee666f4c7a),
1348        Felt::new(0xc7756864a0c480f5),
1349        Felt::new(0x8e5a941d0c8bb591),
1350        Felt::new(0x65f92bc3c31cee43),
1351    ]),
1352    Word::new([
1353        Felt::new(0xf765992519ace8ec),
1354        Felt::new(0x47f3875ee1e33e14),
1355        Felt::new(0xc693a0f0c39d1f8b),
1356        Felt::new(0x827d37c4becc7c23),
1357    ]),
1358    Word::new([
1359        Felt::new(0xe7841cba02153301),
1360        Felt::new(0xae360d71d1f3f9bf),
1361        Felt::new(0x0f9dc12dedc0b53e),
1362        Felt::new(0x948e2e0f2d0feab9),
1363    ]),
1364    Word::new([
1365        Felt::new(0x15074c84d1e8e716),
1366        Felt::new(0xbf8ba357416abc48),
1367        Felt::new(0xc4719d062d5b2bba),
1368        Felt::new(0x64bb509cb47edeb5),
1369    ]),
1370    Word::new([
1371        Felt::new(0xe318dd6e3b65042a),
1372        Felt::new(0x78787e1d76bef52e),
1373        Felt::new(0x7a81debdfcc7bae7),
1374        Felt::new(0xb345047c9e557153),
1375    ]),
1376    Word::new([
1377        Felt::new(0x8d382bf7623c09d2),
1378        Felt::new(0xd26a688e52452b02),
1379        Felt::new(0x1092db1d52000435),
1380        Felt::new(0x08dc1b4e50d6d51a),
1381    ]),
1382    Word::new([
1383        Felt::new(0x16dc8cda8f04358d),
1384        Felt::new(0x838de5cc2f70282c),
1385        Felt::new(0x148f06fdae8ba71e),
1386        Felt::new(0xd9dd7ae619acfdbc),
1387    ]),
1388    Word::new([
1389        Felt::new(0x58b322ddbfbba1af),
1390        Felt::new(0x9398f83ba548e30c),
1391        Felt::new(0xf744167b9d6e6688),
1392        Felt::new(0x14341ceab42a5b83),
1393    ]),
1394    Word::new([
1395        Felt::new(0xe5ef74f758cc8000),
1396        Felt::new(0xb83f6a02d87211ba),
1397        Felt::new(0x58ae77415137763d),
1398        Felt::new(0x3acb2e367a17ac83),
1399    ]),
1400    Word::new([
1401        Felt::new(0x153f8bffd4816e8e),
1402        Felt::new(0x904700f5e763ef37),
1403        Felt::new(0x9e31bb0556795cdb),
1404        Felt::new(0x225dbcb0580f60fa),
1405    ]),
1406    Word::new([
1407        Felt::new(0x4d3f9f5807ab5065),
1408        Felt::new(0x286b1b5f4ac6bc49),
1409        Felt::new(0xbae4d712df7c5291),
1410        Felt::new(0x69073ff9e5c35fb3),
1411    ]),
1412    Word::new([
1413        Felt::new(0x9d77fcce5377e5f3),
1414        Felt::new(0x0bec32771ab1ba8d),
1415        Felt::new(0x2eda25b78c8b300a),
1416        Felt::new(0x1d158b86263b5ab6),
1417    ]),
1418    Word::new([
1419        Felt::new(0x228fe2fa2e3f5ed1),
1420        Felt::new(0xe8495a53a74f093a),
1421        Felt::new(0x257a753ba2e43af2),
1422        Felt::new(0xfd538fa9da4e0f27),
1423    ]),
1424    Word::new([
1425        Felt::new(0x54d06c74a0a7db7f),
1426        Felt::new(0x6ae8f49e798dc860),
1427        Felt::new(0xdbc80936878e3a79),
1428        Felt::new(0xc50fd000599bc191),
1429    ]),
1430    Word::new([
1431        Felt::new(0xd868fa65ec044777),
1432        Felt::new(0x5ecc61c057d8f828),
1433        Felt::new(0xb5ffa6a30770c2e7),
1434        Felt::new(0x2a603c07498f29c4),
1435    ]),
1436    Word::new([
1437        Felt::new(0x1eaddbff84d97639),
1438        Felt::new(0x1b5a2ff8d2d97cc1),
1439        Felt::new(0x869825924edef25f),
1440        Felt::new(0xc5461a47f89eb46c),
1441    ]),
1442    Word::new([
1443        Felt::new(0x5d322dbb2f762f46),
1444        Felt::new(0xf48ef8dc6daa8c2c),
1445        Felt::new(0x27d4b670c82074c4),
1446        Felt::new(0x4bd090499ff2587d),
1447    ]),
1448    Word::new([
1449        Felt::new(0x354e814aaae16fff),
1450        Felt::new(0x308049c1a9cdb07d),
1451        Felt::new(0x2ca3bd1ace6e7348),
1452        Felt::new(0x6782667ba99b5d18),
1453    ]),
1454    Word::new([
1455        Felt::new(0x0aaec950fc0eb154),
1456        Felt::new(0xc20bfdf465c8010e),
1457        Felt::new(0x7f8e848bcac5abe2),
1458        Felt::new(0xbb08ae9eede5b9be),
1459    ]),
1460    Word::new([
1461        Felt::new(0x40af30f55c36ba02),
1462        Felt::new(0x6c3078ec8eeb5923),
1463        Felt::new(0x6a2e537061eaed81),
1464        Felt::new(0x002ad72bd2b6ec7b),
1465    ]),
1466    Word::new([
1467        Felt::new(0xeeb3faff2d77b8ba),
1468        Felt::new(0x638ef01f4b91eb98),
1469        Felt::new(0x4444b42687a47eaf),
1470        Felt::new(0x5330c4248c5a8c66),
1471    ]),
1472    Word::new([
1473        Felt::new(0x6690920a6bcc72a7),
1474        Felt::new(0x6010c282ae56eea0),
1475        Felt::new(0x2fed049030b97533),
1476        Felt::new(0x138b76e4f2bc47cb),
1477    ]),
1478    Word::new([
1479        Felt::new(0xaf5278ff99a628df),
1480        Felt::new(0x595f052fecc9ab19),
1481        Felt::new(0x6061913440182875),
1482        Felt::new(0x53eab420a61b2bf8),
1483    ]),
1484    Word::new([
1485        Felt::new(0x88209ac769d94dab),
1486        Felt::new(0xa12d55043a6c48c1),
1487        Felt::new(0x13e16385eb2b52b8),
1488        Felt::new(0x85042f91b4193103),
1489    ]),
1490    Word::new([
1491        Felt::new(0x13b0825a2f949def),
1492        Felt::new(0x0f133761b751a266),
1493        Felt::new(0xb90bd5bccb8122a7),
1494        Felt::new(0xaf2b1414a5909241),
1495    ]),
1496    Word::new([
1497        Felt::new(0xca9b15725ee26e84),
1498        Felt::new(0x4c0654b5622b7d28),
1499        Felt::new(0x50cf58c8b1ab4d01),
1500        Felt::new(0x5252f94dcd689e7f),
1501    ]),
1502    Word::new([
1503        Felt::new(0x966b1ccc512c9110),
1504        Felt::new(0xf06e95f61e5b0b9a),
1505        Felt::new(0x21827fe65b538b7f),
1506        Felt::new(0xfbc190d74e45917d),
1507    ]),
1508    Word::new([
1509        Felt::new(0x6d5753cc036c18f9),
1510        Felt::new(0xdaf6f79da89c0461),
1511        Felt::new(0x42de26ac092a4e0b),
1512        Felt::new(0x6c213c0062b64dba),
1513    ]),
1514    Word::new([
1515        Felt::new(0x91b3c707ed17f648),
1516        Felt::new(0x6e90170e9052b9a7),
1517        Felt::new(0xb45972fdfd4c51dd),
1518        Felt::new(0x27701793ecfc50b1),
1519    ]),
1520    Word::new([
1521        Felt::new(0x1c0637c214e8ebac),
1522        Felt::new(0x43bf3c2506e8dbae),
1523        Felt::new(0x4420bee16606142f),
1524        Felt::new(0xf27e1e3054b67fab),
1525    ]),
1526    Word::new([
1527        Felt::new(0x883e08713a0c0afd),
1528        Felt::new(0xf9cdb6c6fcff5e43),
1529        Felt::new(0x791a72cd6f40d832),
1530        Felt::new(0xa7f3e71ca960f613),
1531    ]),
1532    Word::new([
1533        Felt::new(0x39ac62e8a61aa45f),
1534        Felt::new(0xbf109a4a60f5cbd0),
1535        Felt::new(0x1d8b66b47b281470),
1536        Felt::new(0xc62ecd5c4b3e2239),
1537    ]),
1538    Word::new([
1539        Felt::new(0xf9047dd2b5b38650),
1540        Felt::new(0x234c754760a7c97a),
1541        Felt::new(0xa6ef6dcea7f0e615),
1542        Felt::new(0x466e0ea54307045d),
1543    ]),
1544    Word::new([
1545        Felt::new(0xf7b010a7b4775867),
1546        Felt::new(0x60e66f53c5cbec31),
1547        Felt::new(0x4a323fc08a401a16),
1548        Felt::new(0x9030956e04fcb4c2),
1549    ]),
1550    Word::new([
1551        Felt::new(0x589bfdc28df24262),
1552        Felt::new(0x9fe7efa3e57efc69),
1553        Felt::new(0x0d7bf81f3877a1a5),
1554        Felt::new(0xb8c1e6d103328f81),
1555    ]),
1556    Word::new([
1557        Felt::new(0x0bd4df64ebeb2195),
1558        Felt::new(0xd718c22709eca79d),
1559        Felt::new(0x12a11a5383359344),
1560        Felt::new(0xcd399effd24a2e6d),
1561    ]),
1562    Word::new([
1563        Felt::new(0xa95c68ebff06feb0),
1564        Felt::new(0x631cfec23d027097),
1565        Felt::new(0x06f4ef2a64b127db),
1566        Felt::new(0x07d396ac3d7625b0),
1567    ]),
1568    Word::new([
1569        Felt::new(0xef311849263abcb4),
1570        Felt::new(0x8bf04d36f9a01799),
1571        Felt::new(0x9e570c4df0f2699f),
1572        Felt::new(0x6927c3a96db0b2ad),
1573    ]),
1574    Word::new([
1575        Felt::new(0x0000000000000000),
1576        Felt::new(0x0000000000000000),
1577        Felt::new(0x0000000000000000),
1578        Felt::new(0x0000000000000000),
1579    ]),
1580];
1581
1582// TESTS
1583// ================================================================================================
1584
1585#[cfg(test)]
1586mod tests {
1587    use super::{
1588        super::{EMPTY_WORD, Poseidon2},
1589        EMPTY_SUBTREES, EmptySubtreeRoots,
1590    };
1591
1592    #[test]
1593    fn all_depths_opens_to_zero() {
1594        // assert the length of the static constants is correct and will cover every possible depth
1595        assert!(EMPTY_SUBTREES.len() > u8::MAX as usize);
1596
1597        for depth in 0..=u8::MAX {
1598            // fetch the subtrees and reverse it so the path is leaf -> root
1599            let mut subtree = EmptySubtreeRoots::empty_hashes(depth).to_vec();
1600            subtree.reverse();
1601
1602            // the length of the subtrees set must be equal to depth + 1 as we also
1603            // include the root
1604            assert_eq!(depth as usize + 1, subtree.len());
1605
1606            // assert the opening is zero
1607            let initial = EMPTY_WORD;
1608            assert_eq!(initial, subtree.remove(0));
1609
1610            // compute every node of the path manually and compare with the output
1611            subtree
1612                .into_iter()
1613                .scan(initial, |state, x| {
1614                    *state = Poseidon2::merge(&[*state; 2]);
1615                    Some((x, *state))
1616                })
1617                .for_each(|(x, computed)| assert_eq!(x, computed));
1618        }
1619    }
1620
1621    #[test]
1622    fn test_entry() {
1623        // check the leaf is always the empty work
1624        for depth in 0..255 {
1625            assert_eq!(EmptySubtreeRoots::entry(depth, depth), &EMPTY_WORD);
1626        }
1627
1628        // check the root matches the first element of empty_hashes
1629        for depth in 0..255 {
1630            assert_eq!(
1631                EmptySubtreeRoots::entry(depth, 0),
1632                &EmptySubtreeRoots::empty_hashes(depth)[0]
1633            );
1634        }
1635    }
1636}
miden_crypto/merkle/empty_roots.rs

miden_crypto/merkle/
empty_roots.rs
