miden-crypto/src/merkle/empty_roots.rs
src/merkle/empty_roots.rsRaw
1use super::{Felt, RpoDigest, WORD_SIZE, ZERO};
2use core::slice;
3
4// EMPTY NODES SUBTREES
5// ================================================================================================
6
7/// Contains precomputed roots of empty subtrees in a Merkle rtee of depth 64.
8pub struct EmptySubtreeRoots;
9
10impl EmptySubtreeRoots {
11 /// Returns a static slice with roots of empty subtrees of a Merkle tree starting at the
12 /// specified depth.
13 ///
14 /// # Panics
15 ///
16 /// This function will panic if the provided `depth` is greater than `64`.
17 pub const fn empty_hashes(depth: u8) -> &'static [RpoDigest] {
18 assert!(depth < 65);
19 let ptr = &EMPTY_SUBTREES_64[64 - depth as usize] as *const RpoDigest;
20 // Safety: this is a static/constant array, so it will never be outlived. If we attempt to
21 // use regular slices, this wouldn't be a `const` function, meaning we won't be able to use
22 // the returned value for static/constant definitions.
23 unsafe { slice::from_raw_parts(ptr, depth as usize + 1) }
24 }
25}
26
27const EMPTY_SUBTREES_64: [RpoDigest; 65] = [
28 RpoDigest::new([
29 Felt::new(15321474589252129342),
30 Felt::new(17373224439259377994),
31 Felt::new(15071539326562317628),
32 Felt::new(3312677166725950353),
33 ]),
34 RpoDigest::new([
35 Felt::new(12146678323567200178),
36 Felt::new(14288630174929498478),
37 Felt::new(13374892366980833045),
38 Felt::new(11840636859983936891),
39 ]),
40 RpoDigest::new([
41 Felt::new(15220380953028059006),
42 Felt::new(2981707349961006045),
43 Felt::new(7409523958661360004),
44 Felt::new(2816116826688969892),
45 ]),
46 RpoDigest::new([
47 Felt::new(7829641133220670678),
48 Felt::new(6170216088031698405),
49 Felt::new(11814483661801576435),
50 Felt::new(1762887097744793975),
51 ]),
52 RpoDigest::new([
53 Felt::new(1299421782687082884),
54 Felt::new(9938699043036414489),
55 Felt::new(10193025806762503939),
56 Felt::new(12073246492422971113),
57 ]),
58 RpoDigest::new([
59 Felt::new(3774016405860870757),
60 Felt::new(2584714598467121158),
61 Felt::new(7418645462301488344),
62 Felt::new(1016804897028793820),
63 ]),
64 RpoDigest::new([
65 Felt::new(13238072489118494737),
66 Felt::new(6917129315345826393),
67 Felt::new(13736362398490889690),
68 Felt::new(4929049375601714136),
69 ]),
70 RpoDigest::new([
71 Felt::new(2433738165854950976),
72 Felt::new(6710644905925382197),
73 Felt::new(10571480102433401045),
74 Felt::new(16853295309134271298),
75 ]),
76 RpoDigest::new([
77 Felt::new(3162775558610426184),
78 Felt::new(11944004899624546116),
79 Felt::new(55767976185223284),
80 Felt::new(5892480272697245897),
81 ]),
82 RpoDigest::new([
83 Felt::new(12582634330812132159),
84 Felt::new(6886254574119140332),
85 Felt::new(4407453795368410417),
86 Felt::new(6959805977831121004),
87 ]),
88 RpoDigest::new([
89 Felt::new(16001070406220863863),
90 Felt::new(4426773743735082930),
91 Felt::new(6860108527212616559),
92 Felt::new(3994703491288516722),
93 ]),
94 RpoDigest::new([
95 Felt::new(9755907048710665826),
96 Felt::new(13697078808748604851),
97 Felt::new(17210321635283113095),
98 Felt::new(1203394006092675979),
99 ]),
100 RpoDigest::new([
101 Felt::new(3332855817731547893),
102 Felt::new(1068928372599561798),
103 Felt::new(17119375903210334455),
104 Felt::new(8148601736624954416),
105 ]),
106 RpoDigest::new([
107 Felt::new(17265634841675424144),
108 Felt::new(18322832739735580203),
109 Felt::new(17896992777163902308),
110 Felt::new(6189383326950297131),
111 ]),
112 RpoDigest::new([
113 Felt::new(9329637674239983584),
114 Felt::new(2512861030579248721),
115 Felt::new(10833150484884266896),
116 Felt::new(7470498642428983444),
117 ]),
118 RpoDigest::new([
119 Felt::new(3611140194800558886),
120 Felt::new(17185933650781587767),
121 Felt::new(7835232399818923215),
122 Felt::new(7974155618002781326),
123 ]),
124 RpoDigest::new([
125 Felt::new(17483286922353768131),
126 Felt::new(353378057542380712),
127 Felt::new(1935183237414585408),
128 Felt::new(4820339620987989650),
129 ]),
130 RpoDigest::new([
131 Felt::new(16172462385444809646),
132 Felt::new(3268597753131435459),
133 Felt::new(3481491333654579291),
134 Felt::new(16487779176137683725),
135 ]),
136 RpoDigest::new([
137 Felt::new(16595012576192613315),
138 Felt::new(16028552537812484518),
139 Felt::new(13016887826405546773),
140 Felt::new(14649690775021494057),
141 ]),
142 RpoDigest::new([
143 Felt::new(11300236651178143890),
144 Felt::new(15307634289168527196),
145 Felt::new(2834866419963148279),
146 Felt::new(7512874625395280090),
147 ]),
148 RpoDigest::new([
149 Felt::new(1148273481270068529),
150 Felt::new(7411276436636897120),
151 Felt::new(14325955409748352141),
152 Felt::new(15577038614919538356),
153 ]),
154 RpoDigest::new([
155 Felt::new(13911627859049081064),
156 Felt::new(13298542751859672529),
157 Felt::new(18341014824837028242),
158 Felt::new(5587966507704160144),
159 ]),
160 RpoDigest::new([
161 Felt::new(10957185917743597702),
162 Felt::new(15815185767119166433),
163 Felt::new(17883994521792846784),
164 Felt::new(15958104556930886663),
165 ]),
166 RpoDigest::new([
167 Felt::new(13148367538964199489),
168 Felt::new(7372139436485928380),
169 Felt::new(13408383191801051600),
170 Felt::new(2114382634401123096),
171 ]),
172 RpoDigest::new([
173 Felt::new(14448157482521530067),
174 Felt::new(17865161921504959156),
175 Felt::new(10319385198642448897),
176 Felt::new(364163501511998552),
177 ]),
178 RpoDigest::new([
179 Felt::new(9722640569118951143),
180 Felt::new(16371655672847089887),
181 Felt::new(12379452272155069993),
182 Felt::new(11605969747977185617),
183 ]),
184 RpoDigest::new([
185 Felt::new(2782512273606877924),
186 Felt::new(3656296563981095117),
187 Felt::new(5947388149010135441),
188 Felt::new(1678144343036748885),
189 ]),
190 RpoDigest::new([
191 Felt::new(10347491038074052866),
192 Felt::new(11061756013655443653),
193 Felt::new(8901792852813329415),
194 Felt::new(10002477867799577447),
195 ]),
196 RpoDigest::new([
197 Felt::new(16688151588649906570),
198 Felt::new(12937054427339650762),
199 Felt::new(2125115528195796454),
200 Felt::new(4796610823085621719),
201 ]),
202 RpoDigest::new([
203 Felt::new(3032620037225059051),
204 Felt::new(13522881885116127385),
205 Felt::new(6010511038055304264),
206 Felt::new(8199256447383686121),
207 ]),
208 RpoDigest::new([
209 Felt::new(11250302734399433639),
210 Felt::new(4970037623163209776),
211 Felt::new(15776613712371118341),
212 Felt::new(5554382612311754837),
213 ]),
214 RpoDigest::new([
215 Felt::new(5116523511540088640),
216 Felt::new(12381059245485642368),
217 Felt::new(2176361879916914688),
218 Felt::new(11209293198464735683),
219 ]),
220 RpoDigest::new([
221 Felt::new(11677748883385181208),
222 Felt::new(15891398395707500576),
223 Felt::new(3790704659934033620),
224 Felt::new(2126099371106695189),
225 ]),
226 RpoDigest::new([
227 Felt::new(13948603355603496603),
228 Felt::new(15902438544472945077),
229 Felt::new(1969361494026622497),
230 Felt::new(17326911676634210553),
231 ]),
232 RpoDigest::new([
233 Felt::new(16081431322775411514),
234 Felt::new(13201312030265587002),
235 Felt::new(18283434127959076535),
236 Felt::new(9889802180847551599),
237 ]),
238 RpoDigest::new([
239 Felt::new(8490051641633132830),
240 Felt::new(11985660456681176415),
241 Felt::new(12193381039977027251),
242 Felt::new(17563185381678568385),
243 ]),
244 RpoDigest::new([
245 Felt::new(3870617340693651786),
246 Felt::new(2748490321246408799),
247 Felt::new(8501743976565218963),
248 Felt::new(1660720190266083389),
249 ]),
250 RpoDigest::new([
251 Felt::new(2121119282758520982),
252 Felt::new(9042267662074029772),
253 Felt::new(15431993929052434204),
254 Felt::new(10659345458998811701),
255 ]),
256 RpoDigest::new([
257 Felt::new(15206763021853065070),
258 Felt::new(15268692497656424421),
259 Felt::new(13335448435922172445),
260 Felt::new(3421340628484408379),
261 ]),
262 RpoDigest::new([
263 Felt::new(5175159910654039438),
264 Felt::new(10258564296733764665),
265 Felt::new(235961379704359454),
266 Felt::new(18007006485615491006),
267 ]),
268 RpoDigest::new([
269 Felt::new(9455184082727641653),
270 Felt::new(6634498452861935579),
271 Felt::new(18189776179964984407),
272 Felt::new(3546641211720870472),
273 ]),
274 RpoDigest::new([
275 Felt::new(2566088177506289568),
276 Felt::new(7785941571143323572),
277 Felt::new(13948908169667863201),
278 Felt::new(8557252288425473395),
279 ]),
280 RpoDigest::new([
281 Felt::new(8801845050152766755),
282 Felt::new(514652983374395586),
283 Felt::new(13975919271481418443),
284 Felt::new(17480955484347349170),
285 ]),
286 RpoDigest::new([
287 Felt::new(7078477424334594989),
288 Felt::new(9975053207879493059),
289 Felt::new(5220656123503260168),
290 Felt::new(13795787984352794188),
291 ]),
292 RpoDigest::new([
293 Felt::new(1478357986561897612),
294 Felt::new(3963701567400985039),
295 Felt::new(10269836564499521403),
296 Felt::new(11874873630603798755),
297 ]),
298 RpoDigest::new([
299 Felt::new(936391814816943993),
300 Felt::new(6085855616346025677),
301 Felt::new(5782721339195502211),
302 Felt::new(10409491632083436908),
303 ]),
304 RpoDigest::new([
305 Felt::new(11138475264090866271),
306 Felt::new(17799626597540451271),
307 Felt::new(17968790388406362807),
308 Felt::new(9539434947296310791),
309 ]),
310 RpoDigest::new([
311 Felt::new(13051724588530357940),
312 Felt::new(8058102530250142518),
313 Felt::new(1861782711432586670),
314 Felt::new(2928050228215055187),
315 ]),
316 RpoDigest::new([
317 Felt::new(10650694022550988030),
318 Felt::new(5634734408638476525),
319 Felt::new(9233115969432897632),
320 Felt::new(1437907447409278328),
321 ]),
322 RpoDigest::new([
323 Felt::new(9720135276484706819),
324 Felt::new(9350120041401976641),
325 Felt::new(1348777594376050933),
326 Felt::new(13138246165242825648),
327 ]),
328 RpoDigest::new([
329 Felt::new(10866643979409126085),
330 Felt::new(13790633638103642042),
331 Felt::new(6374461622011119670),
332 Felt::new(5702679962735491362),
333 ]),
334 RpoDigest::new([
335 Felt::new(5257277882444261955),
336 Felt::new(8511211402794551302),
337 Felt::new(3294838877645533839),
338 Felt::new(4084864647832858048),
339 ]),
340 RpoDigest::new([
341 Felt::new(7948776578097466250),
342 Felt::new(8630046431048474853),
343 Felt::new(11549811661672434609),
344 Felt::new(14329713552208961509),
345 ]),
346 RpoDigest::new([
347 Felt::new(734617692582477804),
348 Felt::new(11871516935077749937),
349 Felt::new(12085935336918533812),
350 Felt::new(11028098016323141988),
351 ]),
352 RpoDigest::new([
353 Felt::new(10937083382606895486),
354 Felt::new(12203867463821771187),
355 Felt::new(13369919265612777227),
356 Felt::new(2521482611471096233),
357 ]),
358 RpoDigest::new([
359 Felt::new(1242037330294600071),
360 Felt::new(8643213198640797337),
361 Felt::new(14112360612081236212),
362 Felt::new(11296904697431650998),
363 ]),
364 RpoDigest::new([
365 Felt::new(11958494925108187724),
366 Felt::new(6059642826232274823),
367 Felt::new(1563918267677757605),
368 Felt::new(266509853282035592),
369 ]),
370 RpoDigest::new([
371 Felt::new(17288335252189973373),
372 Felt::new(3243363076395469373),
373 Felt::new(8880515798614590986),
374 Felt::new(10260780639137628077),
375 ]),
376 RpoDigest::new([
377 Felt::new(1839714959437284152),
378 Felt::new(12088193186987715006),
379 Felt::new(10200898335013164008),
380 Felt::new(12768529781145127245),
381 ]),
382 RpoDigest::new([
383 Felt::new(1537615626967151439),
384 Felt::new(11731506816677487155),
385 Felt::new(4748463589169553420),
386 Felt::new(17495851576537541106),
387 ]),
388 RpoDigest::new([
389 Felt::new(957733314860117562),
390 Felt::new(15623410588944187169),
391 Felt::new(4321611031548662227),
392 Felt::new(12856104259650439278),
393 ]),
394 RpoDigest::new([
395 Felt::new(14827447693720375746),
396 Felt::new(17296925942589213350),
397 Felt::new(13524332314559504765),
398 Felt::new(15663886706087995199),
399 ]),
400 RpoDigest::new([
401 Felt::new(18185978518863914335),
402 Felt::new(936586966360019113),
403 Felt::new(497299419609993926),
404 Felt::new(1977881506773614749),
405 ]),
406 RpoDigest::new([
407 Felt::new(8635338869442206704),
408 Felt::new(11671305615285950885),
409 Felt::new(15253023094703789604),
410 Felt::new(7398108415970215319),
411 ]),
412 RpoDigest::new([ZERO; WORD_SIZE]),
413];
414
415#[test]
416fn all_depths_opens_to_zero() {
417 use super::Rpo256;
418
419 for depth in 1..=64 {
420 // fetch the subtrees and reverse it so the path is leaf -> root
421 let mut subtree = EmptySubtreeRoots::empty_hashes(depth).to_vec();
422 subtree.reverse();
423
424 // the length of the subtrees set must be equal to depth + 1 as we also
425 // include the root
426 assert_eq!(depth as usize + 1, subtree.len());
427
428 // assert the opening is zero
429 let initial = RpoDigest::new([ZERO; WORD_SIZE]);
430 assert_eq!(initial, subtree.remove(0));
431
432 // compute every node of the path manually and compare with the output
433 subtree
434 .into_iter()
435 .scan(initial, |state, x| {
436 *state = Rpo256::merge(&[*state; 2]);
437 Some((x, *state))
438 })
439 .for_each(|(x, computed)| assert_eq!(x, computed));
440 }
441}
442
443#[test]
444fn arbitrary_inputs_will_generate_sound_slices() {
445 let min = &EMPTY_SUBTREES_64[0] as *const RpoDigest;
446 let max = unsafe { min.add(64) };
447 for depth in 0..=64 {
448 let subtree = EmptySubtreeRoots::empty_hashes(depth);
449 let first = &subtree[0] as *const RpoDigest;
450 let last = &subtree[depth as usize] as *const RpoDigest;
451 assert!(min <= first && first <= max);
452 assert!(min <= last && last <= max);
453 }
454}