twenty_first/tip5/
mod.rs

1//! The arithmetization-oriented, cryptographic hash function Tip5.
2//!
3//! This module contains the reference implementation of [“The Tip5 Hash
4//! Function for Recursive STARKs”](https://eprint.iacr.org/2023/107.pdf), as
5//! well as an [AVX-512](https://en.wikipedia.org/wiki/AVX-512)-accelerated
6//! implementation, which subject to conditional compilation and compatible
7//! hardware.
8
9use std::hash::Hasher;
10
11use arbitrary::Arbitrary;
12pub use digest::Digest;
13use get_size2::GetSize;
14use itertools::Itertools;
15use num_traits::ConstOne;
16use num_traits::ConstZero;
17use serde::Deserialize;
18use serde::Serialize;
19
20use crate::math::x_field_element::EXTENSION_DEGREE;
21use crate::prelude::BFieldCodec;
22use crate::prelude::BFieldElement;
23use crate::prelude::XFieldElement;
24use crate::util_types::sponge::Domain;
25use crate::util_types::sponge::Sponge;
26
27pub const STATE_SIZE: usize = 16;
28pub const NUM_SPLIT_AND_LOOKUP: usize = 4;
29pub const LOG2_STATE_SIZE: usize = 4;
30pub const CAPACITY: usize = 6;
31pub const RATE: usize = 10;
32pub const NUM_ROUNDS: usize = 5;
33
34pub mod digest;
35
36#[cfg(all(
37    target_feature = "avx512ifma",
38    target_feature = "avx512f",
39    target_feature = "avx512bw",
40    target_feature = "avx512vbmi"
41))]
42mod avx512;
43#[cfg(test)]
44mod naive;
45
46/// The lookup table with a high algebraic degree used in the TIP-5 permutation. To verify its
47/// correctness, see the test “lookup_table_is_correct.”
48pub const LOOKUP_TABLE: [u8; 256] = [
49    0, 7, 26, 63, 124, 215, 85, 254, 214, 228, 45, 185, 140, 173, 33, 240, 29, 177, 176, 32, 8,
50    110, 87, 202, 204, 99, 150, 106, 230, 14, 235, 128, 213, 239, 212, 138, 23, 130, 208, 6, 44,
51    71, 93, 116, 146, 189, 251, 81, 199, 97, 38, 28, 73, 179, 95, 84, 152, 48, 35, 119, 49, 88,
52    242, 3, 148, 169, 72, 120, 62, 161, 166, 83, 175, 191, 137, 19, 100, 129, 112, 55, 221, 102,
53    218, 61, 151, 237, 68, 164, 17, 147, 46, 234, 203, 216, 22, 141, 65, 57, 123, 12, 244, 54, 219,
54    231, 96, 77, 180, 154, 5, 253, 133, 165, 98, 195, 205, 134, 245, 30, 9, 188, 59, 142, 186, 197,
55    181, 144, 92, 31, 224, 163, 111, 74, 58, 69, 113, 196, 67, 246, 225, 10, 121, 50, 60, 157, 90,
56    122, 2, 250, 101, 75, 178, 159, 24, 36, 201, 11, 243, 132, 198, 190, 114, 233, 39, 52, 21, 209,
57    108, 238, 91, 187, 18, 104, 194, 37, 153, 34, 200, 143, 126, 155, 236, 118, 64, 80, 172, 89,
58    94, 193, 135, 183, 86, 107, 252, 13, 167, 206, 136, 220, 207, 103, 171, 160, 76, 182, 227, 217,
59    158, 56, 174, 4, 66, 109, 139, 162, 184, 211, 249, 47, 125, 232, 117, 43, 16, 42, 127, 20, 241,
60    25, 149, 105, 156, 51, 53, 168, 145, 247, 223, 79, 78, 226, 15, 222, 82, 115, 70, 210, 27, 41,
61    1, 170, 40, 131, 192, 229, 248, 255,
62];
63
64/// The round constants used in the Tip5 permutation. To verify their correctness, see the test
65/// “round_constants_are_correct.”
66pub const ROUND_CONSTANTS: [BFieldElement; NUM_ROUNDS * STATE_SIZE] = [
67    BFieldElement::new(13630775303355457758),
68    BFieldElement::new(16896927574093233874),
69    BFieldElement::new(10379449653650130495),
70    BFieldElement::new(1965408364413093495),
71    BFieldElement::new(15232538947090185111),
72    BFieldElement::new(15892634398091747074),
73    BFieldElement::new(3989134140024871768),
74    BFieldElement::new(2851411912127730865),
75    BFieldElement::new(8709136439293758776),
76    BFieldElement::new(3694858669662939734),
77    BFieldElement::new(12692440244315327141),
78    BFieldElement::new(10722316166358076749),
79    BFieldElement::new(12745429320441639448),
80    BFieldElement::new(17932424223723990421),
81    BFieldElement::new(7558102534867937463),
82    BFieldElement::new(15551047435855531404),
83    BFieldElement::new(17532528648579384106),
84    BFieldElement::new(5216785850422679555),
85    BFieldElement::new(15418071332095031847),
86    BFieldElement::new(11921929762955146258),
87    BFieldElement::new(9738718993677019874),
88    BFieldElement::new(3464580399432997147),
89    BFieldElement::new(13408434769117164050),
90    BFieldElement::new(264428218649616431),
91    BFieldElement::new(4436247869008081381),
92    BFieldElement::new(4063129435850804221),
93    BFieldElement::new(2865073155741120117),
94    BFieldElement::new(5749834437609765994),
95    BFieldElement::new(6804196764189408435),
96    BFieldElement::new(17060469201292988508),
97    BFieldElement::new(9475383556737206708),
98    BFieldElement::new(12876344085611465020),
99    BFieldElement::new(13835756199368269249),
100    BFieldElement::new(1648753455944344172),
101    BFieldElement::new(9836124473569258483),
102    BFieldElement::new(12867641597107932229),
103    BFieldElement::new(11254152636692960595),
104    BFieldElement::new(16550832737139861108),
105    BFieldElement::new(11861573970480733262),
106    BFieldElement::new(1256660473588673495),
107    BFieldElement::new(13879506000676455136),
108    BFieldElement::new(10564103842682358721),
109    BFieldElement::new(16142842524796397521),
110    BFieldElement::new(3287098591948630584),
111    BFieldElement::new(685911471061284805),
112    BFieldElement::new(5285298776918878023),
113    BFieldElement::new(18310953571768047354),
114    BFieldElement::new(3142266350630002035),
115    BFieldElement::new(549990724933663297),
116    BFieldElement::new(4901984846118077401),
117    BFieldElement::new(11458643033696775769),
118    BFieldElement::new(8706785264119212710),
119    BFieldElement::new(12521758138015724072),
120    BFieldElement::new(11877914062416978196),
121    BFieldElement::new(11333318251134523752),
122    BFieldElement::new(3933899631278608623),
123    BFieldElement::new(16635128972021157924),
124    BFieldElement::new(10291337173108950450),
125    BFieldElement::new(4142107155024199350),
126    BFieldElement::new(16973934533787743537),
127    BFieldElement::new(11068111539125175221),
128    BFieldElement::new(17546769694830203606),
129    BFieldElement::new(5315217744825068993),
130    BFieldElement::new(4609594252909613081),
131    BFieldElement::new(3350107164315270407),
132    BFieldElement::new(17715942834299349177),
133    BFieldElement::new(9600609149219873996),
134    BFieldElement::new(12894357635820003949),
135    BFieldElement::new(4597649658040514631),
136    BFieldElement::new(7735563950920491847),
137    BFieldElement::new(1663379455870887181),
138    BFieldElement::new(13889298103638829706),
139    BFieldElement::new(7375530351220884434),
140    BFieldElement::new(3502022433285269151),
141    BFieldElement::new(9231805330431056952),
142    BFieldElement::new(9252272755288523725),
143    BFieldElement::new(10014268662326746219),
144    BFieldElement::new(15565031632950843234),
145    BFieldElement::new(1209725273521819323),
146    BFieldElement::new(6024642864597845108),
147];
148
149/// The defining, first column of the (circulant) MDS matrix.
150/// Derived from the SHA-256 hash of the ASCII string “Tip5” by dividing the digest into 16-bit
151/// chunks.
152pub const MDS_MATRIX_FIRST_COLUMN: [i64; STATE_SIZE] = [
153    61402, 1108, 28750, 33823, 7454, 43244, 53865, 12034, 56951, 27521, 41351, 40901, 12021, 59689,
154    26798, 17845,
155];
156
157#[derive(
158    Debug, Clone, Serialize, Deserialize, Default, PartialEq, Eq, GetSize, BFieldCodec, Arbitrary,
159)]
160#[repr(align(64))] // for SIMD, align along BFieldElement
161pub struct Tip5 {
162    pub state: [BFieldElement; STATE_SIZE],
163}
164
165#[cfg(not(all(
166    target_feature = "avx512ifma",
167    target_feature = "avx512f",
168    target_feature = "avx512bw",
169    target_feature = "avx512vbmi"
170)))]
171impl Tip5 {
172    #[inline(always)]
173    fn round(&mut self, round_index: usize) {
174        self.sbox_layer();
175        self.mds_generated();
176        for i in 0..STATE_SIZE {
177            self.state[i] += ROUND_CONSTANTS[round_index * STATE_SIZE + i];
178        }
179    }
180
181    #[inline(always)]
182    fn sbox_layer(&mut self) {
183        for i in 0..NUM_SPLIT_AND_LOOKUP {
184            Self::split_and_lookup(&mut self.state[i]);
185        }
186
187        for i in NUM_SPLIT_AND_LOOKUP..STATE_SIZE {
188            let sq = self.state[i] * self.state[i];
189            let qu = sq * sq;
190            self.state[i] *= sq * qu;
191        }
192    }
193
194    #[inline]
195    fn split_and_lookup(element: &mut BFieldElement) {
196        // let value = element.value();
197        let mut bytes = element.raw_bytes();
198
199        for i in 0..8 {
200            // bytes[i] = Self::offset_fermat_cube_map(bytes[i].into()) as u8;
201            bytes[i] = LOOKUP_TABLE[bytes[i] as usize];
202        }
203
204        *element = BFieldElement::from_raw_bytes(&bytes);
205    }
206
207    #[inline(always)]
208    fn mds_generated(&mut self) {
209        let mut lo: [u64; STATE_SIZE] = [0; STATE_SIZE];
210        let mut hi: [u64; STATE_SIZE] = [0; STATE_SIZE];
211        for i in 0..STATE_SIZE {
212            let b = self.state[i].raw_u64();
213            hi[i] = b >> 32;
214            lo[i] = b & 0xffffffffu64;
215        }
216
217        lo = Self::generated_function(lo);
218        hi = Self::generated_function(hi);
219
220        for r in 0..STATE_SIZE {
221            let s = (lo[r] >> 4) as u128 + ((hi[r] as u128) << 28);
222
223            let s_hi = (s >> 64) as u64;
224            let s_lo = s as u64;
225
226            let (res, over) = s_lo.overflowing_add(s_hi * 0xffffffffu64);
227
228            self.state[r] =
229                BFieldElement::from_raw_u64(if over { res + 0xffffffffu64 } else { res });
230        }
231    }
232
233    #[inline(always)]
234    fn generated_function(input: [u64; STATE_SIZE]) -> [u64; STATE_SIZE] {
235        let node_34 = input[0].wrapping_add(input[8]);
236        let node_38 = input[4].wrapping_add(input[12]);
237        let node_36 = input[2].wrapping_add(input[10]);
238        let node_40 = input[6].wrapping_add(input[14]);
239        let node_35 = input[1].wrapping_add(input[9]);
240        let node_39 = input[5].wrapping_add(input[13]);
241        let node_37 = input[3].wrapping_add(input[11]);
242        let node_41 = input[7].wrapping_add(input[15]);
243        let node_50 = node_34.wrapping_add(node_38);
244        let node_52 = node_36.wrapping_add(node_40);
245        let node_51 = node_35.wrapping_add(node_39);
246        let node_53 = node_37.wrapping_add(node_41);
247        let node_160 = input[0].wrapping_sub(input[8]);
248        let node_161 = input[1].wrapping_sub(input[9]);
249        let node_165 = input[5].wrapping_sub(input[13]);
250        let node_163 = input[3].wrapping_sub(input[11]);
251        let node_167 = input[7].wrapping_sub(input[15]);
252        let node_162 = input[2].wrapping_sub(input[10]);
253        let node_166 = input[6].wrapping_sub(input[14]);
254        let node_164 = input[4].wrapping_sub(input[12]);
255        let node_58 = node_50.wrapping_add(node_52);
256        let node_59 = node_51.wrapping_add(node_53);
257        let node_90 = node_34.wrapping_sub(node_38);
258        let node_91 = node_35.wrapping_sub(node_39);
259        let node_93 = node_37.wrapping_sub(node_41);
260        let node_92 = node_36.wrapping_sub(node_40);
261        let node_64 = node_58.wrapping_add(node_59).wrapping_mul(524757);
262        let node_67 = node_58.wrapping_sub(node_59).wrapping_mul(52427);
263        let node_71 = node_50.wrapping_sub(node_52);
264        let node_72 = node_51.wrapping_sub(node_53);
265        let node_177 = node_161.wrapping_add(node_165);
266        let node_179 = node_163.wrapping_add(node_167);
267        let node_178 = node_162.wrapping_add(node_166);
268        let node_176 = node_160.wrapping_add(node_164);
269        let node_69 = node_64.wrapping_add(node_67);
270        let node_397 = node_71
271            .wrapping_mul(18446744073709525744)
272            .wrapping_sub(node_72.wrapping_mul(53918));
273        let node_1857 = node_90.wrapping_mul(395512);
274        let node_99 = node_91.wrapping_add(node_93);
275        let node_1865 = node_91.wrapping_mul(18446744073709254400);
276        let node_1869 = node_93.wrapping_mul(179380);
277        let node_1873 = node_92.wrapping_mul(18446744073709509368);
278        let node_1879 = node_160.wrapping_mul(35608);
279        let node_185 = node_161.wrapping_add(node_163);
280        let node_1915 = node_161.wrapping_mul(18446744073709340312);
281        let node_1921 = node_163.wrapping_mul(18446744073709494992);
282        let node_1927 = node_162.wrapping_mul(18446744073709450808);
283        let node_228 = node_165.wrapping_add(node_167);
284        let node_1939 = node_165.wrapping_mul(18446744073709420056);
285        let node_1945 = node_167.wrapping_mul(18446744073709505128);
286        let node_1951 = node_166.wrapping_mul(216536);
287        let node_1957 = node_164.wrapping_mul(18446744073709515080);
288        let node_70 = node_64.wrapping_sub(node_67);
289        let node_702 = node_71
290            .wrapping_mul(53918)
291            .wrapping_add(node_72.wrapping_mul(18446744073709525744));
292        let node_1961 = node_90.wrapping_mul(18446744073709254400);
293        let node_1963 = node_91.wrapping_mul(395512);
294        let node_1965 = node_92.wrapping_mul(179380);
295        let node_1967 = node_93.wrapping_mul(18446744073709509368);
296        let node_1970 = node_160.wrapping_mul(18446744073709340312);
297        let node_1973 = node_161.wrapping_mul(35608);
298        let node_1982 = node_162.wrapping_mul(18446744073709494992);
299        let node_1985 = node_163.wrapping_mul(18446744073709450808);
300        let node_1988 = node_166.wrapping_mul(18446744073709505128);
301        let node_1991 = node_167.wrapping_mul(216536);
302        let node_1994 = node_164.wrapping_mul(18446744073709420056);
303        let node_1997 = node_165.wrapping_mul(18446744073709515080);
304        let node_98 = node_90.wrapping_add(node_92);
305        let node_184 = node_160.wrapping_add(node_162);
306        let node_227 = node_164.wrapping_add(node_166);
307        let node_86 = node_69.wrapping_add(node_397);
308        let node_403 = node_1857.wrapping_sub(
309            node_99
310                .wrapping_mul(18446744073709433780)
311                .wrapping_sub(node_1865)
312                .wrapping_sub(node_1869)
313                .wrapping_add(node_1873),
314        );
315        let node_271 = node_177.wrapping_add(node_179);
316        let node_1891 = node_177.wrapping_mul(18446744073709208752);
317        let node_1897 = node_179.wrapping_mul(18446744073709448504);
318        let node_1903 = node_178.wrapping_mul(115728);
319        let node_1909 = node_185.wrapping_mul(18446744073709283688);
320        let node_1933 = node_228.wrapping_mul(18446744073709373568);
321        let node_88 = node_70.wrapping_add(node_702);
322        let node_708 = node_1961
323            .wrapping_add(node_1963)
324            .wrapping_sub(node_1965.wrapping_add(node_1967));
325        let node_1976 = node_178.wrapping_mul(18446744073709448504);
326        let node_1979 = node_179.wrapping_mul(115728);
327        let node_87 = node_69.wrapping_sub(node_397);
328        let node_897 = node_1865
329            .wrapping_add(node_98.wrapping_mul(353264))
330            .wrapping_sub(node_1857)
331            .wrapping_sub(node_1873)
332            .wrapping_sub(node_1869);
333        let node_2007 = node_184.wrapping_mul(18446744073709486416);
334        let node_2013 = node_227.wrapping_mul(180000);
335        let node_89 = node_70.wrapping_sub(node_702);
336        let node_1077 = node_98
337            .wrapping_mul(18446744073709433780)
338            .wrapping_add(node_99.wrapping_mul(353264))
339            .wrapping_sub(node_1961.wrapping_add(node_1963))
340            .wrapping_sub(node_1965.wrapping_add(node_1967));
341        let node_2020 = node_184.wrapping_mul(18446744073709283688);
342        let node_2023 = node_185.wrapping_mul(18446744073709486416);
343        let node_2026 = node_227.wrapping_mul(18446744073709373568);
344        let node_2029 = node_228.wrapping_mul(180000);
345        let node_2035 = node_176.wrapping_mul(18446744073709550688);
346        let node_2038 = node_176.wrapping_mul(18446744073709208752);
347        let node_2041 = node_177.wrapping_mul(18446744073709550688);
348        let node_270 = node_176.wrapping_add(node_178);
349        let node_152 = node_86.wrapping_add(node_403);
350        let node_412 = node_1879.wrapping_sub(
351            node_271
352                .wrapping_mul(18446744073709105640)
353                .wrapping_sub(node_1891)
354                .wrapping_sub(node_1897)
355                .wrapping_add(node_1903)
356                .wrapping_sub(
357                    node_1909
358                        .wrapping_sub(node_1915)
359                        .wrapping_sub(node_1921)
360                        .wrapping_add(node_1927),
361                )
362                .wrapping_sub(
363                    node_1933
364                        .wrapping_sub(node_1939)
365                        .wrapping_sub(node_1945)
366                        .wrapping_add(node_1951),
367                )
368                .wrapping_add(node_1957),
369        );
370        let node_154 = node_88.wrapping_add(node_708);
371        let node_717 = node_1970.wrapping_add(node_1973).wrapping_sub(
372            node_1976
373                .wrapping_add(node_1979)
374                .wrapping_sub(node_1982.wrapping_add(node_1985))
375                .wrapping_sub(node_1988.wrapping_add(node_1991))
376                .wrapping_add(node_1994.wrapping_add(node_1997)),
377        );
378        let node_156 = node_87.wrapping_add(node_897);
379        let node_906 = node_1915
380            .wrapping_add(node_2007)
381            .wrapping_sub(node_1879)
382            .wrapping_sub(node_1927)
383            .wrapping_sub(
384                node_1897
385                    .wrapping_sub(node_1921)
386                    .wrapping_sub(node_1945)
387                    .wrapping_add(
388                        node_1939
389                            .wrapping_add(node_2013)
390                            .wrapping_sub(node_1957)
391                            .wrapping_sub(node_1951),
392                    ),
393            );
394        let node_158 = node_89.wrapping_add(node_1077);
395        let node_1086 = node_2020
396            .wrapping_add(node_2023)
397            .wrapping_sub(node_1970.wrapping_add(node_1973))
398            .wrapping_sub(node_1982.wrapping_add(node_1985))
399            .wrapping_sub(
400                node_2026
401                    .wrapping_add(node_2029)
402                    .wrapping_sub(node_1994.wrapping_add(node_1997))
403                    .wrapping_sub(node_1988.wrapping_add(node_1991)),
404            );
405        let node_153 = node_86.wrapping_sub(node_403);
406        let node_1237 = node_1909
407            .wrapping_sub(node_1915)
408            .wrapping_sub(node_1921)
409            .wrapping_add(node_1927)
410            .wrapping_add(node_2035)
411            .wrapping_sub(node_1879)
412            .wrapping_sub(node_1957)
413            .wrapping_sub(
414                node_1933
415                    .wrapping_sub(node_1939)
416                    .wrapping_sub(node_1945)
417                    .wrapping_add(node_1951),
418            );
419        let node_155 = node_88.wrapping_sub(node_708);
420        let node_1375 = node_1982
421            .wrapping_add(node_1985)
422            .wrapping_add(node_2038.wrapping_add(node_2041))
423            .wrapping_sub(node_1970.wrapping_add(node_1973))
424            .wrapping_sub(node_1994.wrapping_add(node_1997))
425            .wrapping_sub(node_1988.wrapping_add(node_1991));
426        let node_157 = node_87.wrapping_sub(node_897);
427        let node_1492 = node_1921
428            .wrapping_add(
429                node_1891
430                    .wrapping_add(node_270.wrapping_mul(114800))
431                    .wrapping_sub(node_2035)
432                    .wrapping_sub(node_1903),
433            )
434            .wrapping_sub(
435                node_1915
436                    .wrapping_add(node_2007)
437                    .wrapping_sub(node_1879)
438                    .wrapping_sub(node_1927),
439            )
440            .wrapping_sub(
441                node_1939
442                    .wrapping_add(node_2013)
443                    .wrapping_sub(node_1957)
444                    .wrapping_sub(node_1951),
445            )
446            .wrapping_sub(node_1945);
447        let node_159 = node_89.wrapping_sub(node_1077);
448        let node_1657 = node_270
449            .wrapping_mul(18446744073709105640)
450            .wrapping_add(node_271.wrapping_mul(114800))
451            .wrapping_sub(node_2038.wrapping_add(node_2041))
452            .wrapping_sub(node_1976.wrapping_add(node_1979))
453            .wrapping_sub(
454                node_2020
455                    .wrapping_add(node_2023)
456                    .wrapping_sub(node_1970.wrapping_add(node_1973))
457                    .wrapping_sub(node_1982.wrapping_add(node_1985)),
458            )
459            .wrapping_sub(
460                node_2026
461                    .wrapping_add(node_2029)
462                    .wrapping_sub(node_1994.wrapping_add(node_1997))
463                    .wrapping_sub(node_1988.wrapping_add(node_1991)),
464            );
465
466        [
467            node_152.wrapping_add(node_412),
468            node_154.wrapping_add(node_717),
469            node_156.wrapping_add(node_906),
470            node_158.wrapping_add(node_1086),
471            node_153.wrapping_add(node_1237),
472            node_155.wrapping_add(node_1375),
473            node_157.wrapping_add(node_1492),
474            node_159.wrapping_add(node_1657),
475            node_152.wrapping_sub(node_412),
476            node_154.wrapping_sub(node_717),
477            node_156.wrapping_sub(node_906),
478            node_158.wrapping_sub(node_1086),
479            node_153.wrapping_sub(node_1237),
480            node_155.wrapping_sub(node_1375),
481            node_157.wrapping_sub(node_1492),
482            node_159.wrapping_sub(node_1657),
483        ]
484    }
485}
486
487impl Tip5 {
488    #[inline]
489    pub const fn new(domain: Domain) -> Self {
490        let mut state = const { [BFieldElement::ZERO; STATE_SIZE] };
491
492        match domain {
493            Domain::VariableLength => (),
494            Domain::FixedLength => {
495                let mut i = RATE;
496                while i < STATE_SIZE {
497                    state[i] = BFieldElement::ONE;
498                    i += 1;
499                }
500            }
501        }
502
503        Self { state }
504    }
505
506    #[inline(always)]
507    pub fn permutation(&mut self) {
508        for i in 0..NUM_ROUNDS {
509            self.round(i);
510        }
511    }
512
513    /// Functionally equivalent to [`permutation`](Self::permutation). Returns the trace of
514    /// applying the permutation; that is, the initial state of the sponge as well as its state
515    /// after each round.
516    pub fn trace(&mut self) -> [[BFieldElement; STATE_SIZE]; 1 + NUM_ROUNDS] {
517        let mut trace = [[BFieldElement::ZERO; STATE_SIZE]; 1 + NUM_ROUNDS];
518
519        trace[0] = self.state;
520        for i in 0..NUM_ROUNDS {
521            self.round(i);
522            trace[1 + i] = self.state;
523        }
524
525        trace
526    }
527
528    /// Hash 10 [`BFieldElement`]s.
529    ///
530    /// There is no input-padding because the input length is fixed.
531    ///
532    /// When you want to hash together two [`Digest`]s, use [`Self::hash_pair`]
533    /// instead. In some rare cases you do want to hash a fixed-length string
534    /// of individual [`BFieldElement`]s, which is why this function is exposed.
535    ///
536    /// See also: [`Self::hash_pair`], [`Self::hash`], [`Self::hash_varlen`].
537    pub fn hash_10(input: &[BFieldElement; RATE]) -> [BFieldElement; Digest::LEN] {
538        let mut sponge = Self::new(Domain::FixedLength);
539
540        // absorb once
541        sponge.state[..RATE].copy_from_slice(input);
542
543        sponge.permutation();
544
545        // squeeze once
546        sponge.state[..Digest::LEN].try_into().unwrap()
547    }
548
549    /// Hash two [`Digest`]s together.
550    ///
551    /// This function is syntax sugar for calling [`Self::hash_10`] on the
552    /// concatenation of the digests' values.
553    ///
554    /// See also: [`Self::hash_10`], [`Self::hash`], [`Self::hash_varlen`].
555    pub fn hash_pair(left: Digest, right: Digest) -> Digest {
556        let mut sponge = Self::new(Domain::FixedLength);
557        sponge.state[..Digest::LEN].copy_from_slice(&left.values());
558        sponge.state[Digest::LEN..2 * Digest::LEN].copy_from_slice(&right.values());
559
560        sponge.permutation();
561
562        let digest_values = sponge.state[..Digest::LEN].try_into().unwrap();
563        Digest::new(digest_values)
564    }
565
566    /// Hash an object based on its [`BFieldCodec`]-encoding.
567    ///
568    /// Thin wrapper around [`hash_varlen`](Self::hash_varlen).
569    ///
570    /// See also: [`Self::hash_10`], [`Self::hash_pair`], [`Self::hash_varlen`].
571    pub fn hash<T: BFieldCodec>(value: &T) -> Digest {
572        Self::hash_varlen(&value.encode())
573    }
574
575    /// Hash a variable-length sequence of [`BFieldElement`].
576    ///
577    /// This function pads the input as its length is variable.
578    ///
579    /// Note that [`Self::hash_varlen`] and [`Self::hash_10`] are different
580    /// functions, even when the input to the former, after padding, agrees with
581    /// the input to the latter. The difference comes from the initial value of
582    /// the capacity-part of the state, which in the case of variable-length
583    /// hashing is all-ones but in the case of fixed-length hashing is
584    /// all-zeroes.
585    ///
586    /// Prefer [`Self::hash`] whenever an object is being hashed whose type
587    /// implements [`BFieldCodec`]. However, such an object is not always
588    /// available, which is why this function is exposed.
589    ///
590    /// See also: [`Self::hash_10`], [`Self::hash_pair`], [`Self::hash`].
591    //
592    // - Apply the correct padding
593    // - [Sponge::pad_and_absorb_all()]
594    // - Read the digest from the resulting state.
595    pub fn hash_varlen(input: &[BFieldElement]) -> Digest {
596        let mut sponge = Self::init();
597        sponge.pad_and_absorb_all(input);
598        let produce = (&sponge.state[..Digest::LEN]).try_into().unwrap();
599
600        Digest::new(produce)
601    }
602
603    /// Produce `num_indices` random integer values in the range `[0, upper_bound)`. The
604    /// `upper_bound` must be a power of 2.
605    ///
606    /// This method uses von Neumann rejection sampling.
607    /// Specifically, if the top 32 bits of a BFieldElement are all ones, then the bottom 32 bits
608    /// are not uniformly distributed, and so they are dropped. This method invokes squeeze until
609    /// enough uniform u32s have been sampled.
610    pub fn sample_indices(&mut self, upper_bound: u32, num_indices: usize) -> Vec<u32> {
611        debug_assert!(upper_bound.is_power_of_two());
612        let mut indices = vec![];
613        let mut squeezed_elements = vec![];
614        while indices.len() != num_indices {
615            if squeezed_elements.is_empty() {
616                squeezed_elements = self.squeeze().into_iter().rev().collect_vec();
617            }
618            let element = squeezed_elements.pop().unwrap();
619            if element != BFieldElement::new(BFieldElement::MAX) {
620                indices.push(element.value() as u32 % upper_bound);
621            }
622        }
623        indices
624    }
625
626    /// Produce `num_elements` random [`XFieldElement`] values.
627    ///
628    /// If `num_elements` is not divisible by [`RATE`][rate], spill the remaining elements of the
629    /// last [`squeeze`][Sponge::squeeze].
630    ///
631    /// [rate]: Sponge::RATE
632    pub fn sample_scalars(&mut self, num_elements: usize) -> Vec<XFieldElement> {
633        let num_squeezes = (num_elements * EXTENSION_DEGREE).div_ceil(Self::RATE);
634        debug_assert!(
635            num_elements * EXTENSION_DEGREE <= num_squeezes * Self::RATE,
636            "need {} elements but getting {}",
637            num_elements * EXTENSION_DEGREE,
638            num_squeezes * Self::RATE
639        );
640        (0..num_squeezes)
641            .flat_map(|_| self.squeeze())
642            .collect_vec()
643            .chunks(3)
644            .take(num_elements)
645            .map(|elem| XFieldElement::new([elem[0], elem[1], elem[2]]))
646            .collect()
647    }
648}
649
650impl Sponge for Tip5 {
651    const RATE: usize = RATE;
652
653    fn init() -> Self {
654        Self::new(Domain::VariableLength)
655    }
656
657    fn absorb(&mut self, input: [BFieldElement; RATE]) {
658        self.state[..RATE]
659            .iter_mut()
660            .zip_eq(&input)
661            .for_each(|(a, &b)| *a = b);
662
663        self.permutation();
664    }
665
666    fn squeeze(&mut self) -> [BFieldElement; RATE] {
667        let produce: [BFieldElement; RATE] = (&self.state[..RATE]).try_into().unwrap();
668        self.permutation();
669
670        produce
671    }
672}
673
674impl Hasher for Tip5 {
675    fn finish(&self) -> u64 {
676        self.state[0].value()
677    }
678
679    fn write(&mut self, bytes: &[u8]) {
680        let bfield_elements = bytes.chunks(BFieldElement::BYTES).map(|chunk| {
681            let mut buffer = [0u8; BFieldElement::BYTES];
682            buffer[..chunk.len()].copy_from_slice(chunk);
683            BFieldElement::new(u64::from_le_bytes(buffer))
684        });
685
686        for chunk in bfield_elements.chunks(Tip5::RATE).into_iter() {
687            let mut buffer = [BFieldElement::ZERO; Tip5::RATE];
688            for (buffer_elem, chunk_elem) in buffer.iter_mut().zip(chunk) {
689                *buffer_elem = chunk_elem;
690            }
691            self.absorb(buffer)
692        }
693    }
694}
695
696#[cfg(test)]
697#[cfg_attr(coverage_nightly, coverage(off))]
698pub(crate) mod tests {
699    use std::hash::Hash;
700    use std::ops::Mul;
701
702    use prop::sample::size_range;
703    use proptest::prelude::*;
704    use proptest_arbitrary_interop::arb;
705    use rand::RngCore;
706    use rayon::prelude::IntoParallelIterator;
707    use rayon::prelude::ParallelIterator;
708    use test_strategy::proptest;
709
710    use super::*;
711    use crate::math::other::random_elements;
712    use crate::math::x_field_element::XFieldElement;
713
714    impl proptest::arbitrary::Arbitrary for Tip5 {
715        type Parameters = ();
716
717        fn arbitrary_with(_: Self::Parameters) -> Self::Strategy {
718            arb().boxed()
719        }
720
721        type Strategy = BoxedStrategy<Self>;
722    }
723
724    impl Tip5 {
725        fn mds_cyclomul(&mut self) {
726            let mut result = [BFieldElement::ZERO; STATE_SIZE];
727
728            let mut lo: [i64; STATE_SIZE] = [0; STATE_SIZE];
729            let mut hi: [i64; STATE_SIZE] = [0; STATE_SIZE];
730            for (i, b) in self.state.iter().enumerate() {
731                hi[i] = (b.raw_u64() >> 32) as i64;
732                lo[i] = (b.raw_u64() as u32) as i64;
733            }
734
735            lo = Self::fast_cyclomul16(lo, MDS_MATRIX_FIRST_COLUMN);
736            hi = Self::fast_cyclomul16(hi, MDS_MATRIX_FIRST_COLUMN);
737
738            for r in 0..STATE_SIZE {
739                let s = lo[r] as u128 + ((hi[r] as u128) << 32);
740                let s_hi = (s >> 64) as u64;
741                let s_lo = s as u64;
742                let z = (s_hi << 32) - s_hi;
743                let (res, over) = s_lo.overflowing_add(z);
744
745                result[r] = BFieldElement::from_raw_u64(
746                    res.wrapping_add(0u32.wrapping_sub(over as u32) as u64),
747                );
748            }
749            self.state = result;
750        }
751
752        fn fast_cyclomul16(f: [i64; 16], g: [i64; 16]) -> [i64; 16] {
753            const N: usize = 8;
754            let mut ff_lo = [0i64; N];
755            let mut gg_lo = [0i64; N];
756            let mut ff_hi = [0i64; N];
757            let mut gg_hi = [0i64; N];
758            for i in 0..N {
759                ff_lo[i] = f[i] + f[i + N];
760                ff_hi[i] = f[i] - f[i + N];
761                gg_lo[i] = g[i] + g[i + N];
762                gg_hi[i] = g[i] - g[i + N];
763            }
764
765            let hh_lo = Self::fast_cyclomul8(ff_lo, gg_lo);
766            let hh_hi = Self::complex_negacyclomul8(ff_hi, gg_hi);
767
768            let mut hh = [0i64; 2 * N];
769            for i in 0..N {
770                hh[i] = (hh_lo[i] + hh_hi[i]) >> 1;
771                hh[i + N] = (hh_lo[i] - hh_hi[i]) >> 1;
772            }
773
774            hh
775        }
776
777        fn fast_cyclomul8(f: [i64; 8], g: [i64; 8]) -> [i64; 8] {
778            const N: usize = 4;
779            let mut ff_lo = [0i64; N];
780            let mut gg_lo = [0i64; N];
781            let mut ff_hi = [0i64; N];
782            let mut gg_hi = [0i64; N];
783            for i in 0..N {
784                ff_lo[i] = f[i] + f[i + N];
785                ff_hi[i] = f[i] - f[i + N];
786                gg_lo[i] = g[i] + g[i + N];
787                gg_hi[i] = g[i] - g[i + N];
788            }
789
790            let hh_lo = Self::fast_cyclomul4(ff_lo, gg_lo);
791            let hh_hi = Self::complex_negacyclomul4(ff_hi, gg_hi);
792
793            let mut hh = [0i64; 2 * N];
794            for i in 0..N {
795                hh[i] = (hh_lo[i] + hh_hi[i]) >> 1;
796                hh[i + N] = (hh_lo[i] - hh_hi[i]) >> 1;
797            }
798
799            hh
800        }
801
802        fn fast_cyclomul4(f: [i64; 4], g: [i64; 4]) -> [i64; 4] {
803            const N: usize = 2;
804            let mut ff_lo = [0i64; N];
805            let mut gg_lo = [0i64; N];
806            let mut ff_hi = [0i64; N];
807            let mut gg_hi = [0i64; N];
808            for i in 0..N {
809                ff_lo[i] = f[i] + f[i + N];
810                ff_hi[i] = f[i] - f[i + N];
811                gg_lo[i] = g[i] + g[i + N];
812                gg_hi[i] = g[i] - g[i + N];
813            }
814
815            let hh_lo = Self::fast_cyclomul2(ff_lo, gg_lo);
816            let hh_hi = Self::complex_negacyclomul2(ff_hi, gg_hi);
817
818            let mut hh = [0i64; 2 * N];
819            for i in 0..N {
820                hh[i] = (hh_lo[i] + hh_hi[i]) >> 1;
821                hh[i + N] = (hh_lo[i] - hh_hi[i]) >> 1;
822            }
823
824            hh
825        }
826
827        fn fast_cyclomul2(f: [i64; 2], g: [i64; 2]) -> [i64; 2] {
828            let ff_lo = f[0] + f[1];
829            let ff_hi = f[0] - f[1];
830            let gg_lo = g[0] + g[1];
831            let gg_hi = g[0] - g[1];
832
833            let hh_lo = ff_lo * gg_lo;
834            let hh_hi = ff_hi * gg_hi;
835
836            let mut hh = [0i64; 2];
837            hh[0] = (hh_lo + hh_hi) >> 1;
838            hh[1] = (hh_lo - hh_hi) >> 1;
839
840            hh
841        }
842
843        fn complex_negacyclomul8(f: [i64; 8], g: [i64; 8]) -> [i64; 8] {
844            const N: usize = 4;
845
846            let mut f0 = [(0i64, 0i64); N];
847            let mut g0 = [(0i64, 0i64); N];
848
849            for i in 0..N {
850                f0[i] = (f[i], -f[N + i]);
851                g0[i] = (g[i], -g[N + i]);
852            }
853
854            let h0 = Self::complex_karatsuba4(f0, g0);
855
856            let mut h = [0i64; 3 * N - 1];
857            for i in 0..(2 * N - 1) {
858                h[i] += h0[i].0;
859                h[i + N] -= h0[i].1;
860            }
861
862            let mut hh = [0i64; 2 * N];
863            for i in 0..(2 * N) {
864                hh[i] += h[i];
865            }
866            for i in (2 * N)..(3 * N - 1) {
867                hh[i - 2 * N] -= h[i];
868            }
869
870            hh
871        }
872
873        fn complex_negacyclomul4(f: [i64; 4], g: [i64; 4]) -> [i64; 4] {
874            const N: usize = 2;
875
876            let mut f0 = [(0i64, 0i64); N];
877            let mut g0 = [(0i64, 0i64); N];
878
879            for i in 0..N {
880                f0[i] = (f[i], -f[N + i]);
881                g0[i] = (g[i], -g[N + i]);
882            }
883
884            let h0 = Self::complex_karatsuba2(f0, g0);
885
886            let mut h = [0i64; 4 * N - 1];
887            for i in 0..(2 * N - 1) {
888                h[i] += h0[i].0;
889                h[i + N] -= h0[i].1;
890            }
891
892            let mut hh = [0i64; 2 * N];
893            for i in 0..(2 * N) {
894                hh[i] += h[i];
895            }
896            for i in (2 * N)..(4 * N - 1) {
897                hh[i - 2 * N] -= h[i];
898            }
899
900            hh
901        }
902
903        fn complex_negacyclomul2(f: [i64; 2], g: [i64; 2]) -> [i64; 2] {
904            let f0 = (f[0], -f[1]);
905            let g0 = (g[0], -g[1]);
906
907            let h0 = Self::complex_product(f0, g0);
908
909            [h0.0, -h0.1]
910        }
911
912        #[inline(always)]
913        fn complex_karatsuba4(f: [(i64, i64); 4], g: [(i64, i64); 4]) -> [(i64, i64); 7] {
914            const N: usize = 2;
915
916            let ff = Self::complex_sum::<2>(f[..N].try_into().unwrap(), f[N..].try_into().unwrap());
917            let gg = Self::complex_sum::<2>(g[..N].try_into().unwrap(), g[N..].try_into().unwrap());
918
919            let lo =
920                Self::complex_karatsuba2(f[..N].try_into().unwrap(), g[..N].try_into().unwrap());
921            let hi =
922                Self::complex_karatsuba2(f[N..].try_into().unwrap(), g[N..].try_into().unwrap());
923
924            let li = Self::complex_diff::<3>(
925                Self::complex_karatsuba2(ff, gg),
926                Self::complex_sum::<3>(lo, hi),
927            );
928
929            let mut result = [(0i64, 0i64); 4 * N - 1];
930            for i in 0..(2 * N - 1) {
931                result[i].0 = lo[i].0;
932                result[i].1 = lo[i].1;
933            }
934            for i in 0..(2 * N - 1) {
935                result[N + i].0 += li[i].0;
936                result[N + i].1 += li[i].1;
937            }
938            for i in 0..(2 * N - 1) {
939                result[2 * N + i].0 += hi[i].0;
940                result[2 * N + i].1 += hi[i].1;
941            }
942
943            result
944        }
945
946        fn complex_karatsuba2(f: [(i64, i64); 2], g: [(i64, i64); 2]) -> [(i64, i64); 3] {
947            const N: usize = 1;
948
949            let ff = (f[0].0 + f[1].0, f[0].1 + f[1].1);
950            let gg = (g[0].0 + g[1].0, g[0].1 + g[1].1);
951
952            let lo = Self::complex_product(f[0], g[0]);
953            let hi = Self::complex_product(f[1], g[1]);
954
955            let ff_times_gg = Self::complex_product(ff, gg);
956            let lo_plus_hi = (lo.0 + hi.0, lo.1 + hi.1);
957
958            let li = (ff_times_gg.0 - lo_plus_hi.0, ff_times_gg.1 - lo_plus_hi.1);
959
960            let mut result = [(0i64, 0i64); 4 * N - 1];
961            result[0].0 += lo.0;
962            result[0].1 += lo.1;
963            result[N].0 += li.0;
964            result[N].1 += li.1;
965            result[2 * N].0 += hi.0;
966            result[2 * N].1 += hi.1;
967
968            result
969        }
970
971        fn complex_product(f: (i64, i64), g: (i64, i64)) -> (i64, i64) {
972            // don't karatsuba; this is faster
973            (f.0 * g.0 - f.1 * g.1, f.0 * g.1 + f.1 * g.0)
974        }
975
976        fn complex_sum<const N: usize>(f: [(i64, i64); N], g: [(i64, i64); N]) -> [(i64, i64); N] {
977            let mut h = [(0i64, 0i64); N];
978            for i in 0..N {
979                h[i].0 = f[i].0 + g[i].0;
980                h[i].1 = f[i].1 + g[i].1;
981            }
982            h
983        }
984
985        fn complex_diff<const N: usize>(f: [(i64, i64); N], g: [(i64, i64); N]) -> [(i64, i64); N] {
986            let mut h = [(0i64, 0i64); N];
987            for i in 0..N {
988                h[i].0 = f[i].0 - g[i].0;
989                h[i].1 = f[i].1 - g[i].1;
990            }
991            h
992        }
993
994        fn offset_fermat_cube_map(x: u16) -> u16 {
995            let xx = (x + 1) as u64;
996            let xxx = xx * xx * xx;
997            ((xxx + 256) % 257) as u16
998        }
999    }
1000
1001    #[proptest(cases = 10)]
1002    fn get_size(tip5: Tip5) {
1003        assert_eq!(STATE_SIZE * BFieldElement::ZERO.get_size(), tip5.get_size());
1004    }
1005
1006    #[test]
1007    fn lookup_table_is_correct() {
1008        let table: [u8; 256] = (0..256)
1009            .map(|t| Tip5::offset_fermat_cube_map(t as u16) as u8)
1010            .collect_vec()
1011            .try_into()
1012            .unwrap();
1013
1014        println!(
1015            "Entire lookup table:\n{}",
1016            table.iter().map(|t| format!("{t:02x}")).join(", ")
1017        );
1018
1019        (0_usize..256).for_each(|i| {
1020            assert_eq!(
1021                LOOKUP_TABLE[i], table[i],
1022                "Lookup tables must agree at every index, including index {i}."
1023            )
1024        });
1025    }
1026
1027    #[test]
1028    fn round_constants_are_correct() {
1029        let to_int = |bytes: &[u8]| {
1030            bytes
1031                .iter()
1032                .take(16)
1033                .enumerate()
1034                .map(|(i, b)| (*b as u128) << (8 * i))
1035                .sum::<u128>()
1036        };
1037        let round_constants = (0..NUM_ROUNDS * STATE_SIZE)
1038            .map(|i| ["Tip5".to_string().as_bytes(), &[i as u8]].concat())
1039            .map(|bytes| blake3::hash(&bytes))
1040            .map(|hash| *hash.as_bytes())
1041            .map(|bytes| to_int(&bytes))
1042            .map(|i| (i % BFieldElement::P as u128) as u64)
1043            .map(BFieldElement::from_raw_u64)
1044            .collect_vec();
1045
1046        println!(
1047            "In case you changed something, here are all round constants:\n{}",
1048            round_constants.iter().map(|c| format!("{c}")).join(", ")
1049        );
1050
1051        (0_usize..NUM_ROUNDS * STATE_SIZE).for_each(|i| {
1052            assert_eq!(
1053                ROUND_CONSTANTS[i], round_constants[i],
1054                "Round constants must agree at every index, including index {i}."
1055            )
1056        });
1057    }
1058
1059    #[test]
1060    fn test_fermat_cube_map_is_permutation() {
1061        let mut touched = [false; 256];
1062        for i in 0..256 {
1063            touched[Tip5::offset_fermat_cube_map(i) as usize] = true;
1064        }
1065        assert!(touched.iter().all(|t| *t));
1066        assert_eq!(Tip5::offset_fermat_cube_map(0), 0);
1067        assert_eq!(Tip5::offset_fermat_cube_map(255), 255);
1068    }
1069
1070    #[test]
1071    fn calculate_differential_uniformity() {
1072        // cargo test calculate_differential_uniformity -- --include-ignored --nocapture
1073        // addition-differential
1074        let count_satisfiers_fermat = |a, b| {
1075            (0..(1 << 8))
1076                .map(|x| {
1077                    u16::from(
1078                        (256 + Tip5::offset_fermat_cube_map((x + a) & 0xff)
1079                            - Tip5::offset_fermat_cube_map(x))
1080                            & 0xff
1081                            == b,
1082                    )
1083                })
1084                .sum()
1085        };
1086        let du_fermat: u16 = (1..256)
1087            .into_par_iter()
1088            .map(|a| {
1089                (1..256)
1090                    .map(|b| count_satisfiers_fermat(a, b))
1091                    .max()
1092                    .unwrap()
1093            })
1094            .max()
1095            .unwrap();
1096        println!("additive differential uniformity for fermat cube map: {du_fermat}");
1097
1098        // bitwise-differential
1099        let count_satisfiers_fermat_bitwise = |a: u16, b: u16| {
1100            (0..(1 << 8))
1101                .map(|x| {
1102                    u16::from(
1103                        (Tip5::offset_fermat_cube_map(x ^ a) ^ Tip5::offset_fermat_cube_map(x))
1104                            == b,
1105                    )
1106                })
1107                .sum::<u16>()
1108        };
1109        for a in 1..256 {
1110            for b in 1..256 {
1111                let num_satisfiers = count_satisfiers_fermat_bitwise(a, b);
1112                if num_satisfiers == 256 {
1113                    println!("a: {a}, b: {b} -> 256 satisfiers");
1114                }
1115            }
1116        }
1117        let du_fermat_bitwise: u16 = (1..256)
1118            .into_par_iter()
1119            .map(|a| {
1120                (1..256)
1121                    .map(|b| count_satisfiers_fermat_bitwise(a, b))
1122                    .max()
1123                    .unwrap()
1124            })
1125            .max()
1126            .unwrap();
1127        println!("bitwise differential uniformity for fermat cube map: {du_fermat_bitwise}");
1128    }
1129
1130    #[test]
1131    fn calculate_approximation_quality() {
1132        let mut fermat_cubed = [0u16; 65536];
1133        let mut bfield_cubed = [0u16; 65536];
1134        for i in 0..65536 {
1135            let cubed = (i as u64) * (i as u64) * (i as u64);
1136            fermat_cubed[i] = (cubed % 65537) as u16;
1137            bfield_cubed[i] = (cubed & 0xffff) as u16;
1138        }
1139        let equal_count = fermat_cubed
1140            .iter()
1141            .zip(bfield_cubed.iter())
1142            .filter(|(a, b)| a == b)
1143            .count();
1144        println!("agreement with low-degree function: {equal_count}");
1145    }
1146
1147    /// A snapshot of a [`Digest`], in hexadecimal form. The exact procedure to
1148    /// arrive at the `Digest` in question is involved and best read from the
1149    /// code below.
1150    ///
1151    /// It is paramount that Tip5 has at least some snapshot tests. The reason
1152    /// is that (with the current implementation), conditional compilation
1153    /// changes the concrete instructions that make up Tip5. Testing different
1154    /// binaries for equivalent behavior is easiest when that behavior is pinned
1155    /// through snapshots.
1156    const MAGIC_SNAPSHOT_HEX: &str =
1157        "109cc2fe453bd9962f754b96d8f5b919b60af030940a275f5540da195fef65ee651c1b6fa19b2c6a";
1158
1159    #[test]
1160    fn hash10_test_vectors_snapshot() {
1161        let mut preimage = [BFieldElement::ZERO; RATE];
1162        for i in 0..6 {
1163            let digest = Tip5::hash_10(&preimage);
1164            preimage[i..i + Digest::LEN].copy_from_slice(&digest);
1165        }
1166        let final_digest = Digest::new(Tip5::hash_10(&preimage)).to_hex();
1167        assert_eq!(MAGIC_SNAPSHOT_HEX, final_digest);
1168    }
1169
1170    #[test]
1171    fn hash_varlen_test_vectors() {
1172        let mut digest_sum = [BFieldElement::ZERO; Digest::LEN];
1173        for i in 0..20 {
1174            let preimage = (0..i).map(BFieldElement::new).collect_vec();
1175            let digest = Tip5::hash_varlen(&preimage);
1176            digest_sum
1177                .iter_mut()
1178                .zip(digest.values().iter())
1179                .for_each(|(s, d)| *s += *d);
1180        }
1181
1182        let final_digest = Digest::new(digest_sum).to_hex();
1183        assert_eq!(
1184            "efbafa86622a9c69652f8a1c4ffd734f021ad23a0a8085412a877de0f9170b18ea4ff69b6fff9a03",
1185            final_digest,
1186        );
1187    }
1188
1189    #[test]
1190    fn snapshot() {
1191        let state = [
1192            0x0000_000f_ffff_fff0,
1193            0x0000_0000_ffff_ffff,
1194            0x0000_0000_ffff_ffff,
1195            0x0000_0028_ffff_ffd7,
1196            0x0000_0006_ffff_fff9,
1197            0x0000_0002_ffff_fffd,
1198            0x0000_0000_ffff_ffff,
1199            0x0000_0030_ffff_ffcf,
1200            0x0000_0397_ffff_fc68,
1201            0x0000_000f_ffff_fff0,
1202            0x316b_fb72_3638_2123,
1203            0x216f_521b_66ef_83f5,
1204            0x5689_d7b3_63f5_2df0,
1205            0xeb2f_59e3_aeae_25fc,
1206            0xb082_99d2_77cb_b4dc,
1207            0xcbe3_d9fd_c534_9140,
1208        ]
1209        .map(BFieldElement::from_raw_u64);
1210
1211        let mut tip5 = Tip5 { state };
1212        tip5.permutation();
1213
1214        let expected = [
1215            0x15d3_8ea9_29f6_632a,
1216            0xf988_e509_ff73_8bb4,
1217            0x48bc_dfae_88a2_e9f3,
1218            0x8733_9e83_2daa_c02a,
1219            0x511e_4126_8150_fdac,
1220        ]
1221        .map(BFieldElement::from_raw_u64);
1222
1223        assert_eq!(&expected, &tip5.state[0..5]);
1224    }
1225
1226    fn manual_hash_varlen(preimage: &[BFieldElement]) -> Digest {
1227        let mut sponge = Tip5::init();
1228        sponge.pad_and_absorb_all(preimage);
1229        let squeeze_result = sponge.squeeze();
1230
1231        Digest::new((&squeeze_result[..Digest::LEN]).try_into().unwrap())
1232    }
1233
1234    #[test]
1235    fn hash_var_len_equivalence_edge_cases() {
1236        for preimage_length in 0..=11 {
1237            let preimage = vec![BFieldElement::new(42); preimage_length];
1238            let hash_varlen_digest = Tip5::hash_varlen(&preimage);
1239
1240            let digest_through_pad_squeeze_absorb = manual_hash_varlen(&preimage);
1241            assert_eq!(digest_through_pad_squeeze_absorb, hash_varlen_digest);
1242        }
1243    }
1244
1245    #[proptest]
1246    fn hash_var_len_equivalence(#[strategy(arb())] preimage: Vec<BFieldElement>) {
1247        let hash_varlen_digest = Tip5::hash_varlen(&preimage);
1248        let digest_through_pad_squeeze_absorb = manual_hash_varlen(&preimage);
1249        prop_assert_eq!(digest_through_pad_squeeze_absorb, hash_varlen_digest);
1250    }
1251
1252    #[test]
1253    fn test_linearity_of_mds() {
1254        type SpongeState = [BFieldElement; STATE_SIZE];
1255
1256        let mds_procedure = |state| {
1257            let mut sponge = Tip5 { state };
1258            sponge.mds_cyclomul();
1259            sponge.state
1260        };
1261
1262        let a: BFieldElement = random_elements(1)[0];
1263        let b: BFieldElement = random_elements(1)[0];
1264
1265        let mul_procedure = |u: SpongeState, v: SpongeState| -> SpongeState {
1266            let mul_result = u.iter().zip(&v).map(|(&uu, &vv)| a * uu + b * vv);
1267            mul_result.collect_vec().try_into().unwrap()
1268        };
1269
1270        let u: SpongeState = random_elements(STATE_SIZE).try_into().unwrap();
1271        let v: SpongeState = random_elements(STATE_SIZE).try_into().unwrap();
1272        let w = mul_procedure(u, v);
1273
1274        let u = mds_procedure(u);
1275        let v = mds_procedure(v);
1276        let w = mds_procedure(w);
1277
1278        let w_ = mul_procedure(u, v);
1279
1280        assert_eq!(w, w_);
1281    }
1282
1283    #[test]
1284    fn test_mds_circulancy() {
1285        let mut sponge = Tip5::init();
1286        sponge.state = [BFieldElement::ZERO; STATE_SIZE];
1287        sponge.state[0] = BFieldElement::ONE;
1288
1289        sponge.mds_cyclomul();
1290
1291        let mut mat_first_row = [BFieldElement::ZERO; STATE_SIZE];
1292        mat_first_row[0] = sponge.state[0];
1293        for (i, first_row_elem) in mat_first_row.iter_mut().enumerate().skip(1) {
1294            *first_row_elem = sponge.state[STATE_SIZE - i];
1295        }
1296
1297        println!(
1298            "mds matrix first row: {:?}",
1299            mat_first_row.map(|b| b.value())
1300        );
1301
1302        let initial_state: [BFieldElement; STATE_SIZE] =
1303            random_elements(STATE_SIZE).try_into().unwrap();
1304
1305        let mut mv = [BFieldElement::ZERO; STATE_SIZE];
1306        for i in 0..STATE_SIZE {
1307            for j in 0..STATE_SIZE {
1308                mv[i] += mat_first_row[(STATE_SIZE - i + j) % STATE_SIZE] * initial_state[j];
1309            }
1310        }
1311
1312        let mut sponge_2 = Tip5::init();
1313        sponge_2.state = initial_state;
1314        sponge_2.mds_cyclomul();
1315
1316        assert_eq!(sponge_2.state, mv);
1317    }
1318
1319    #[test]
1320    fn test_complex_karatsuba() {
1321        const N: usize = 4;
1322        let mut f = [(0i64, 0i64); N];
1323        let mut g = [(0i64, 0i64); N];
1324        for i in 0..N {
1325            f[i].0 = i as i64;
1326            g[i].0 = 1;
1327            f[i].1 = 1;
1328            g[i].1 = i as i64;
1329        }
1330
1331        let h0 = Tip5::complex_karatsuba4(f, g);
1332        let h1 = [(0, 1), (0, 2), (0, 4), (0, 8), (0, 13), (0, 14), (0, 10)];
1333
1334        assert_eq!(h0, h1);
1335    }
1336
1337    #[test]
1338    fn test_complex_product() {
1339        let mut rng = rand::rng();
1340        let mut random_small_i64 = || (rng.next_u32() % (1 << 16)) as i64;
1341        for _ in 0..1000 {
1342            let f = (random_small_i64(), random_small_i64());
1343            let g = (random_small_i64(), random_small_i64());
1344            let h0 = Tip5::complex_product(f, g);
1345            let h1 = (f.0 * g.0 - f.1 * g.1, f.0 * g.1 + f.1 * g.0);
1346            assert_eq!(h1, h0);
1347        }
1348    }
1349
1350    #[proptest]
1351    fn sample_scalars(mut tip5: Tip5, #[strategy(0_usize..=100)] num_scalars: usize) {
1352        tip5.permutation(); // remove any 0s that exist due to shrinking
1353
1354        let scalars = tip5.sample_scalars(num_scalars);
1355        prop_assert_eq!(num_scalars, scalars.len());
1356
1357        let product = scalars
1358            .into_iter()
1359            .fold(XFieldElement::ONE, XFieldElement::mul);
1360        prop_assert_ne!(product, XFieldElement::ZERO);
1361    }
1362
1363    // Function `mds_generated` is not available if the AVX-512 functions are.
1364    #[cfg(not(all(
1365        target_feature = "avx512ifma",
1366        target_feature = "avx512f",
1367        target_feature = "avx512bw",
1368        target_feature = "avx512vbmi"
1369    )))]
1370    #[proptest]
1371    fn test_mds_matrix_mul_methods_agree(state: [BFieldElement; STATE_SIZE]) {
1372        let mut sponge_cyclomut = Tip5 { state };
1373        let mut sponge_generated = Tip5 { state };
1374
1375        sponge_cyclomut.mds_cyclomul();
1376        sponge_generated.mds_generated();
1377
1378        prop_assert_eq!(
1379            &sponge_cyclomut,
1380            &sponge_generated,
1381            "cyclomul =/= generated\n{}\n{}",
1382            sponge_cyclomut.state.into_iter().join(","),
1383            sponge_generated.state.into_iter().join(",")
1384        );
1385    }
1386
1387    #[test]
1388    fn tip5_hasher_trait_snapshot_test() {
1389        let mut hasher = Tip5::init();
1390        let data = b"hello world";
1391        hasher.write(data);
1392        assert_eq!(hasher.finish(), 2267905471610932299);
1393    }
1394
1395    #[proptest]
1396    fn tip5_hasher_consumes_small_data(#[filter(!#bytes.is_empty())] bytes: Vec<u8>) {
1397        let mut hasher = Tip5::init();
1398        bytes.hash(&mut hasher);
1399
1400        prop_assert_ne!(Tip5::init().finish(), hasher.finish());
1401    }
1402
1403    #[proptest]
1404    fn appending_small_data_to_big_data_changes_tip5_hash(
1405        #[any(size_range(2_000..8_000).lift())] big_data: Vec<u8>,
1406        #[filter(!#small_data.is_empty())] small_data: Vec<u8>,
1407    ) {
1408        let mut hasher = Tip5::init();
1409        big_data.hash(&mut hasher);
1410        let big_data_hash = hasher.finish();
1411
1412        // finish doesn't terminate the hasher; see it's documentation
1413        small_data.hash(&mut hasher);
1414        let all_data_hash = hasher.finish();
1415
1416        prop_assert_ne!(big_data_hash, all_data_hash);
1417    }
1418
1419    #[proptest]
1420    fn tip5_trace_starts_with_initial_state_and_is_equivalent_to_permutation(mut tip5: Tip5) {
1421        let [first, .., last] = tip5.clone().trace();
1422        prop_assert_eq!(first, tip5.state);
1423
1424        tip5.permutation();
1425        prop_assert_eq!(last, tip5.state);
1426    }
1427}
twenty_first/tip5/mod.rs

twenty_first/tip5/
mod.rs
