p3_mersenne_31/
poseidon2.rs

1//! Implementation of Poseidon2, see: `<https://eprint.iacr.org/2023/323>`
2//!
3//! For the diffusion matrix, 1 + Diag(V), we perform a search to find an optimized
4//! vector V composed of elements with efficient multiplication algorithms in AVX2/AVX512/NEON.
5//!
6//! This leads to using small values (e.g. 1, 2) where multiplication is implemented using addition
7//! and powers of 2 where multiplication is implemented using shifts.
8//! Additionally, for technical reasons, having the first entry be -2 is useful.
9//!
10//! Optimized Diagonal for Mersenne31 width 16:
11//! [-2, 2^0, 2, 4, 8, 16, 32, 64, 2^7, 2^8, 2^10, 2^12, 2^13, 2^14, 2^15, 2^16]
12//! Optimized Diagonal for Mersenne31 width 24:
13//! [-2, 2^0, 2, 4, 8, 16, 32, 64, 2^7, 2^8, 2^9, 2^10, 2^11, 2^12, 2^13, 2^14, 2^15, 2^16, 2^17, 2^18, 2^19, 2^20, 2^21, 2^22]
14//! See poseidon2\src\diffusion.rs for information on how to double check these matrices in Sage.
15
16use p3_field::PrimeCharacteristicRing;
17use p3_poseidon2::{
18    ExternalLayer, ExternalLayerConstants, GenericPoseidon2LinearLayers, InternalLayer, MDSMat4,
19    Poseidon2, add_rc_and_sbox_generic, external_initial_permute_state,
20    external_terminal_permute_state, internal_permute_state,
21};
22
23use crate::{
24    Mersenne31, Poseidon2ExternalLayerMersenne31, Poseidon2InternalLayerMersenne31, from_u62,
25};
26
27/// S-box degree for Mersenne31 Poseidon2.
28///
29/// Since `p - 1 = 2 × 3^2 × 7 × 11 × 31 × 151 × 331`, both 3 and 4 share factors
30/// with `p - 1`. The smallest valid exponent satisfying `gcd(α, p - 1) = 1` is 5.
31pub const MERSENNE31_S_BOX_DEGREE: u64 = 5;
32
33/// Number of full rounds per half for Mersenne31 Poseidon2 (`RF / 2`).
34///
35/// The total number of full rounds is `RF = 8` (4 beginning + 4 ending).
36/// Follows the Poseidon2 paper's security analysis with a +2 RF margin.
37pub const MERSENNE31_POSEIDON2_HALF_FULL_ROUNDS: usize = 4;
38
39/// Number of partial rounds for Mersenne31 Poseidon2 (width 16).
40///
41/// Derived from the Gröbner basis bound in the Poseidon2 paper (Eq. 1, R_GB term 3):
42///
43///   R_GB ≥ t − 7 + log_α(2) · min{κ/(t+1), log_2(p)/2}
44///        = 9 + 0.4307 · min{7.53, 15.5} = 12.243
45///
46/// With the +7.5% security margin: ⌈1.075 × 12.243⌉ = 14.
47pub const MERSENNE31_POSEIDON2_PARTIAL_ROUNDS_16: usize = 14;
48
49/// Number of partial rounds for Mersenne31 Poseidon2 (width 24).
50///
51/// Same Gröbner basis bound as width 16:
52///
53///   R_GB ≥ 17 + 0.4307 · min{5.12, 15.5} = 19.205
54///
55/// With the +7.5% security margin: ⌈1.075 × 19.205⌉ = 21.
56///
57/// The official round number script yields R_P = 22 for this configuration
58/// (matching the Grain LFSR parameters used to generate the round constants).
59pub const MERSENNE31_POSEIDON2_PARTIAL_ROUNDS_24: usize = 22;
60
61/// Number of partial rounds for Mersenne31 Poseidon2 (width 32).
62///
63/// The official round number script yields R_P = 30 for this configuration
64/// (matching the Grain LFSR parameters used to generate the round constants below).
65pub const MERSENNE31_POSEIDON2_PARTIAL_ROUNDS_32: usize = 30;
66
67/// An implementation of the Poseidon2 hash function specialised to run on the current architecture.
68///
69/// It acts on arrays of the form either `[Mersenne31::Packing; WIDTH]` or `[Mersenne31; WIDTH]`. For speed purposes,
70/// wherever possible, input arrays should of the form `[Mersenne31::Packing; WIDTH]`.
71pub type Poseidon2Mersenne31<const WIDTH: usize> = Poseidon2<
72    Mersenne31,
73    Poseidon2ExternalLayerMersenne31<WIDTH>,
74    Poseidon2InternalLayerMersenne31,
75    WIDTH,
76    MERSENNE31_S_BOX_DEGREE,
77>;
78
79/// Round constants for width-16 Poseidon2 on Mersenne31.
80///
81/// Generated by the Grain LFSR with parameters:
82///     field_type=1, alpha=5 (exp_flag=0), n=31, t=16, R_F=8, R_P=14
83///
84/// Generated by `poseidon2/generate_constants.py --field mersenne31 --width 16`.
85///
86/// Layout: external_initial (4 rounds × 16 elements).
87pub const MERSENNE31_POSEIDON2_RC_16_EXTERNAL_INITIAL: [[Mersenne31; 16]; 4] = [
88    Mersenne31::new_array([
89        0x768bab52, 0x70e0ab7d, 0x3d266c8a, 0x6da42045, 0x600fef22, 0x41dace6b, 0x64f9bdd4,
90        0x5d42d4fe, 0x76b1516d, 0x6fc9a717, 0x70ac4fb6, 0x00194ef6, 0x22b644e2, 0x1f7916d5,
91        0x47581be2, 0x2710a123,
92    ]),
93    Mersenne31::new_array([
94        0x6284e867, 0x018d3afe, 0x5df99ef3, 0x4c1e467b, 0x566f6abc, 0x2994e427, 0x538a6d42,
95        0x5d7bf2cf, 0x7fda2dab, 0x0fd854c4, 0x46922fca, 0x3d7763a1, 0x19fd05ca, 0x0a4bbb43,
96        0x15075851, 0x3d903d76,
97    ]),
98    Mersenne31::new_array([
99        0x2d290ff7, 0x40809fa0, 0x59dac6ec, 0x127927a2, 0x6bbf0ea0, 0x0294140f, 0x24742976,
100        0x6e84c081, 0x22484f4a, 0x354cae59, 0x0453ffe1, 0x3f47a3cc, 0x0088204e, 0x6066e109,
101        0x3b7c4b80, 0x6b55665d,
102    ]),
103    Mersenne31::new_array([
104        0x3bc4b897, 0x735bf378, 0x508daf42, 0x1884fc2b, 0x7214f24c, 0x7498be0a, 0x1a60e640,
105        0x3303f928, 0x29b46376, 0x5c96bb68, 0x65d097a5, 0x1d358e9f, 0x4a9a9017, 0x4724cf76,
106        0x347af70f, 0x1e77e59a,
107    ]),
108];
109
110/// Round constants for width-16 Poseidon2 on Mersenne31.
111///
112/// Generated by the Grain LFSR with parameters:
113///     field_type=1, alpha=5 (exp_flag=0), n=31, t=16, R_F=8, R_P=14
114///
115/// Generated by `poseidon2/generate_constants.py --field mersenne31 --width 16`.
116///
117/// Layout: external_final (4 rounds × 16 elements).
118pub const MERSENNE31_POSEIDON2_RC_16_EXTERNAL_FINAL: [[Mersenne31; 16]; 4] = [
119    Mersenne31::new_array([
120        0x57090613, 0x1fa42108, 0x17bbef50, 0x1ff7e11c, 0x047b24ca, 0x4e140275, 0x4fa086f5,
121        0x079b309c, 0x1159bd47, 0x6d37e4e5, 0x075d8dce, 0x12121ca0, 0x7f6a7c40, 0x68e182ba,
122        0x5493201b, 0x0444a80e,
123    ]),
124    Mersenne31::new_array([
125        0x0064f4c6, 0x6467abe6, 0x66975762, 0x2af68f9b, 0x345b33be, 0x1b70d47f, 0x053db717,
126        0x381189cb, 0x43b915f8, 0x20df3694, 0x0f459d26, 0x77a0e97b, 0x2f73e739, 0x1876c2f9,
127        0x65a0e29a, 0x4cabefbe,
128    ]),
129    Mersenne31::new_array([
130        0x5abd1268, 0x4d34a760, 0x12771799, 0x69a0c9ac, 0x39091e55, 0x7f611cd0, 0x3af055da,
131        0x7ac0bbdf, 0x6e0f3a24, 0x41e3b6f7, 0x49b3756d, 0x568bc538, 0x20c079d8, 0x1701c72c,
132        0x7670dc6c, 0x5a439035,
133    ]),
134    Mersenne31::new_array([
135        0x7c93e00e, 0x561fbb4d, 0x1178907b, 0x02737406, 0x32fb24f1, 0x6323b60a, 0x6ab12418,
136        0x42c99cea, 0x155a0b97, 0x53d1c6aa, 0x2bd20347, 0x279b3d73, 0x4f5f3c70, 0x0245af6c,
137        0x238359d3, 0x49966a59,
138    ]),
139];
140
141/// Round constants for width-16 Poseidon2 on Mersenne31.
142///
143/// Generated by the Grain LFSR with parameters:
144///     field_type=1, alpha=5 (exp_flag=0), n=31, t=16, R_F=8, R_P=14
145///
146/// Generated by `poseidon2/generate_constants.py --field mersenne31 --width 16`.
147///
148/// Layout: internal (14 scalar constants).
149pub const MERSENNE31_POSEIDON2_RC_16_INTERNAL: [Mersenne31; 14] = Mersenne31::new_array([
150    0x7f7ec4bf, 0x0421926f, 0x5198e669, 0x34db3148, 0x4368bafd, 0x66685c7f, 0x78d3249a, 0x60187881,
151    0x76dad67a, 0x0690b437, 0x1ea95311, 0x40e5369a, 0x38f103fc, 0x1d226a21,
152]);
153
154/// Round constants for width-24 Poseidon2 on Mersenne31.
155///
156/// Generated by the Grain LFSR with parameters:
157///     field_type=1, alpha=5 (exp_flag=0), n=31, t=24, R_F=8, R_P=22
158///
159/// Generated by `poseidon2/generate_constants.py --field mersenne31 --width 24`.
160///
161/// Layout: external_initial (4 rounds × 24 elements).
162pub const MERSENNE31_POSEIDON2_RC_24_EXTERNAL_INITIAL: [[Mersenne31; 24]; 4] = [
163    Mersenne31::new_array([
164        0x1feaba61, 0x53224454, 0x6bceb9e2, 0x5019f9b4, 0x48726592, 0x2b22d0a8, 0x6151bbf9,
165        0x2f474b21, 0x2eb5f337, 0x3b645d87, 0x0942cef0, 0x65228c52, 0x78ffb30f, 0x4d2837c8,
166        0x0e17ac4f, 0x05546686, 0x046c06cc, 0x0b51c3b6, 0x568db763, 0x38b334e4, 0x57f5acf0,
167        0x19d32611, 0x77d02f4b, 0x6c82e9b8,
168    ]),
169    Mersenne31::new_array([
170        0x7148c1b6, 0x08067c75, 0x46d1e8c9, 0x30973b07, 0x20614f3b, 0x5c3ff851, 0x30503329,
171        0x4972e7cc, 0x02d1d8bc, 0x09d5bfa6, 0x097104c0, 0x7ba49a34, 0x4a07c2fc, 0x24c1ee69,
172        0x28a6ab41, 0x5d9108a0, 0x3a7851c7, 0x1dd495f9, 0x12b49ff4, 0x7bad5760, 0x5fed64c2,
173        0x66f5c96c, 0x7eafbd02, 0x39b3593b,
174    ]),
175    Mersenne31::new_array([
176        0x4a653b49, 0x75091dc1, 0x56e488e0, 0x1704a355, 0x745e4ff3, 0x392ef16e, 0x31e33fdf,
177        0x02c28c66, 0x36c3083a, 0x3104d1fa, 0x5b03cda3, 0x6641e1af, 0x37754b56, 0x396f5af9,
178        0x1a1a461a, 0x688e26f2, 0x6f829784, 0x1bb91d69, 0x5b788016, 0x704aa5c5, 0x0181869c,
179        0x41211e56, 0x0ce803a0, 0x23bff3a0,
180    ]),
181    Mersenne31::new_array([
182        0x17fb7064, 0x47317220, 0x76914b53, 0x219c1905, 0x16655528, 0x4df35544, 0x60808465,
183        0x3350f833, 0x03bccdc7, 0x0a87180a, 0x017a99f5, 0x6e945726, 0x15445504, 0x780533b1,
184        0x3b91bf38, 0x3fc77eb1, 0x4b4d960e, 0x3cd93d2e, 0x0ea4e976, 0x1d5306cc, 0x3a7ac284,
185        0x0ec22934, 0x4d979713, 0x51a41c65,
186    ]),
187];
188
189/// Round constants for width-24 Poseidon2 on Mersenne31.
190///
191/// Generated by the Grain LFSR with parameters:
192///     field_type=1, alpha=5 (exp_flag=0), n=31, t=24, R_F=8, R_P=22
193///
194/// Generated by `poseidon2/generate_constants.py --field mersenne31 --width 24`.
195///
196/// Layout: external_final (4 rounds × 24 elements).
197pub const MERSENNE31_POSEIDON2_RC_24_EXTERNAL_FINAL: [[Mersenne31; 24]; 4] = [
198    Mersenne31::new_array([
199        0x1c662299, 0x057c955a, 0x7ab6c0f2, 0x25a6ad0a, 0x75850b58, 0x48fd3793, 0x0b4366b1,
200        0x0fdd0d49, 0x7db419f9, 0x49b9cc0f, 0x48949716, 0x29c35890, 0x76445485, 0x1c27d30c,
201        0x10aa7a3b, 0x30f34fb6, 0x6fe06435, 0x02135ecd, 0x6caaba96, 0x3eb290d0, 0x22fd8d3b,
202        0x768b1525, 0x5be95814, 0x523d7fe9,
203    ]),
204    Mersenne31::new_array([
205        0x55e94cec, 0x47c42e1f, 0x1aa53b5e, 0x2fd1fe7e, 0x59230e91, 0x7472da66, 0x6443f2df,
206        0x2d9de19d, 0x6f7f6a84, 0x77800430, 0x0f014bc8, 0x7bf3d095, 0x26afd318, 0x582561f7,
207        0x5ee3198c, 0x6acc0000, 0x2f315e26, 0x27cac040, 0x2595081e, 0x5963b7da, 0x7e073565,
208        0x6cf3f5f1, 0x09f8a3a4, 0x0da8ccfe,
209    ]),
210    Mersenne31::new_array([
211        0x60be2365, 0x7ed742f5, 0x668b8031, 0x4bb03494, 0x59019333, 0x700e2878, 0x1cc45856,
212        0x1d1617f7, 0x7b988da6, 0x4eb4936c, 0x78c9f87e, 0x63ce3e94, 0x7178341b, 0x45bc2f86,
213        0x05b775bc, 0x704b0244, 0x29eed278, 0x47f43032, 0x2127b2e5, 0x1997903f, 0x24b3ce03,
214        0x0c32298c, 0x7d2b6f3a, 0x17fcaa81,
215    ]),
216    Mersenne31::new_array([
217        0x72f37fef, 0x3028e7a9, 0x5edd4d96, 0x1f96583b, 0x4cd6918a, 0x14880f0e, 0x69170359,
218        0x173cbd33, 0x0969e7f4, 0x6e7f23ab, 0x6182ea87, 0x4dcb1f5c, 0x585fa113, 0x729cb3b6,
219        0x01b3a27a, 0x1ba173e7, 0x4b33bcea, 0x63d93bbb, 0x6b3fbf99, 0x6f17e9d1, 0x0c3dd8ba,
220        0x0bc1f9a8, 0x64d3f370, 0x465a6a18,
221    ]),
222];
223
224/// Round constants for width-24 Poseidon2 on Mersenne31.
225///
226/// Generated by the Grain LFSR with parameters:
227///     field_type=1, alpha=5 (exp_flag=0), n=31, t=24, R_F=8, R_P=22
228///
229/// Generated by `poseidon2/generate_constants.py --field mersenne31 --width 24`.
230///
231/// Layout: internal (22 scalar constants).
232pub const MERSENNE31_POSEIDON2_RC_24_INTERNAL: [Mersenne31; 22] = Mersenne31::new_array([
233    0x22776a11, 0x5fa34268, 0x1415528d, 0x563fbd14, 0x34f45244, 0x120ea1b6, 0x261368a5, 0x27665ec1,
234    0x36be2805, 0x345c4784, 0x17efdcc1, 0x393e6530, 0x6da0b4b8, 0x31e5ded3, 0x675b27ac, 0x0ae88c30,
235    0x577841cc, 0x5fe06dec, 0x56b0691a, 0x7242de1f, 0x3c377529, 0x339b7523,
236]);
237
238/// Create a default width-16 Poseidon2 permutation for Mersenne31.
239pub fn default_mersenne31_poseidon2_16() -> Poseidon2Mersenne31<16> {
240    Poseidon2::new(
241        ExternalLayerConstants::new(
242            MERSENNE31_POSEIDON2_RC_16_EXTERNAL_INITIAL.to_vec(),
243            MERSENNE31_POSEIDON2_RC_16_EXTERNAL_FINAL.to_vec(),
244        ),
245        MERSENNE31_POSEIDON2_RC_16_INTERNAL.to_vec(),
246    )
247}
248
249/// Create a default width-24 Poseidon2 permutation for Mersenne31.
250pub fn default_mersenne31_poseidon2_24() -> Poseidon2Mersenne31<24> {
251    Poseidon2::new(
252        ExternalLayerConstants::new(
253            MERSENNE31_POSEIDON2_RC_24_EXTERNAL_INITIAL.to_vec(),
254            MERSENNE31_POSEIDON2_RC_24_EXTERNAL_FINAL.to_vec(),
255        ),
256        MERSENNE31_POSEIDON2_RC_24_INTERNAL.to_vec(),
257    )
258}
259
260/// Round constants for width-32 Poseidon2 on Mersenne31.
261///
262/// Generated by the Grain LFSR with parameters:
263///     field_type=1, alpha=5 (exp_flag=0), n=31, t=32, R_F=8, R_P=30
264///
265/// Generated by `poseidon2/generate_constants.py --field mersenne31 --width 32`.
266///
267/// Layout: external_initial (4 rounds × 32 elements).
268pub const MERSENNE31_POSEIDON2_RC_32_EXTERNAL_INITIAL: [[Mersenne31; 32]; 4] = [
269    Mersenne31::new_array([
270        0x6710e381, 0x01ab3dad, 0x49bdc51f, 0x41c98c65, 0x23885d8a, 0x24ea7d7c, 0x6b65fc6d,
271        0x6106615a, 0x084957f3, 0x157c3634, 0x4dada10f, 0x6cdfa46d, 0x1bf208be, 0x5bd22fac,
272        0x79da8fdb, 0x78ebc8ed, 0x4c8bcbdf, 0x27f79490, 0x70495412, 0x2a41844e, 0x51bb69f1,
273        0x3215dc21, 0x67114819, 0x27aa6a09, 0x5f4d3cad, 0x5fd6c724, 0x1b4c108d, 0x7ebd949d,
274        0x5799d04d, 0x568c212f, 0x680821db, 0x62073729,
275    ]),
276    Mersenne31::new_array([
277        0x229ee780, 0x3b4f94c3, 0x17a3ac54, 0x6c388279, 0x4876fe55, 0x3170f20a, 0x33703e4e,
278        0x03980ab1, 0x012fb0fa, 0x145ee8db, 0x49815b30, 0x46ad879c, 0x52bc503d, 0x586530d7,
279        0x5c36f9e5, 0x028e6503, 0x08310368, 0x75546646, 0x732516f1, 0x33483e5a, 0x04a0842c,
280        0x1a3135d9, 0x537b2eb1, 0x5baf4f77, 0x4b78cd6d, 0x5aed2c4a, 0x66c893e1, 0x3c5493a6,
281        0x46c62bfc, 0x564e591a, 0x52ded7a7, 0x00d1032d,
282    ]),
283    Mersenne31::new_array([
284        0x2b30d801, 0x101dabf7, 0x2efb21cd, 0x4a361c39, 0x49eff572, 0x2e13caf4, 0x016e6799,
285        0x1b5cdb44, 0x17ca2dc6, 0x0e500ee0, 0x0141ca9b, 0x279b2376, 0x6647c40b, 0x0dcaee3c,
286        0x16e7fcf9, 0x59e6d65c, 0x1eb730c9, 0x7ebf0417, 0x28607848, 0x45727f9c, 0x4e543ffb,
287        0x03ee2550, 0x010cd54b, 0x7b1a1050, 0x02dc4b76, 0x2b3a9a3c, 0x2eabb2d9, 0x06928553,
288        0x2d23b3f5, 0x6da322b1, 0x1527ec07, 0x0e450b7a,
289    ]),
290    Mersenne31::new_array([
291        0x53961612, 0x20f16b10, 0x16f00c60, 0x4c39d50f, 0x41d59d76, 0x5253f822, 0x3b53d381,
292        0x1b7f470a, 0x5e3d895c, 0x52658125, 0x012190d3, 0x65563b80, 0x1d0faa47, 0x3575b3c9,
293        0x4c0d9d20, 0x18cff09f, 0x64a7da5c, 0x2f140b25, 0x139f9e31, 0x66e36bd5, 0x6442c811,
294        0x58879bce, 0x5fcc87c6, 0x6807ae0c, 0x4111c657, 0x633c8929, 0x74962971, 0x3fc18eb8,
295        0x456cf288, 0x31f6c8d2, 0x6c3a31a8, 0x6d82df50,
296    ]),
297];
298
299/// Round constants for width-32 Poseidon2 on Mersenne31.
300///
301/// Generated by the Grain LFSR with parameters:
302///     field_type=1, alpha=5 (exp_flag=0), n=31, t=32, R_F=8, R_P=30
303///
304/// Generated by `poseidon2/generate_constants.py --field mersenne31 --width 32`.
305///
306/// Layout: external_final (4 rounds × 32 elements).
307pub const MERSENNE31_POSEIDON2_RC_32_EXTERNAL_FINAL: [[Mersenne31; 32]; 4] = [
308    Mersenne31::new_array([
309        0x7818a8d3, 0x1a58e115, 0x29113198, 0x776b289f, 0x1e922ee2, 0x2165fbf0, 0x28ccaf78,
310        0x1983287d, 0x492b22e0, 0x77cc4657, 0x39005c27, 0x48cd8089, 0x267cfcbb, 0x1c41ca85,
311        0x41b3943f, 0x20e7727a, 0x64ad78f3, 0x13dd4413, 0x1042e3dc, 0x74adeb2c, 0x2dcdd3c7,
312        0x06006fbc, 0x35a609e9, 0x0daf273c, 0x3a4f694f, 0x7a992693, 0x59fd101d, 0x27d2112b,
313        0x1937b69f, 0x2e8880bc, 0x40c12429, 0x067965a6,
314    ]),
315    Mersenne31::new_array([
316        0x6ea1b36d, 0x6e01476e, 0x29cd718a, 0x5406c693, 0x51de2e9a, 0x6ddc388a, 0x53763473,
317        0x7fbd6bda, 0x17a25cbf, 0x1f2982cd, 0x7af8156c, 0x19ca5afd, 0x2d703c93, 0x0c2840e4,
318        0x2cda82cd, 0x5c7f51e0, 0x1db58806, 0x3cb62bd1, 0x2b45461b, 0x6204ba50, 0x7bcdbe79,
319        0x6857f0bc, 0x4af2a368, 0x32c146f4, 0x1acfdd93, 0x2dc39570, 0x0dbdeb4e, 0x50bef84d,
320        0x6f83a22c, 0x434c3741, 0x2060e160, 0x68f58f0b,
321    ]),
322    Mersenne31::new_array([
323        0x2529b2bd, 0x112c4768, 0x70409ce2, 0x1b57460e, 0x21dc818c, 0x5f6b5330, 0x443f8fba,
324        0x211a90de, 0x591d4a30, 0x5b5a3e75, 0x635c333a, 0x1efd6a70, 0x5d35445f, 0x5637cf22,
325        0x6e9ba8b1, 0x10b54e2c, 0x04291eb8, 0x2d4ea543, 0x720a5c61, 0x1a5b6323, 0x68e176e7,
326        0x26149775, 0x58f30beb, 0x450402ab, 0x24928255, 0x32c59955, 0x2b5b7261, 0x6279779f,
327        0x599b6a8e, 0x70d145d3, 0x3786c4d1, 0x11363460,
328    ]),
329    Mersenne31::new_array([
330        0x22ff2181, 0x4d06fc50, 0x27a8a3df, 0x647df984, 0x3a748cc3, 0x4aa91ea2, 0x21ead2a1,
331        0x50cd5d8d, 0x06d6ffc6, 0x5bc51117, 0x45f848bc, 0x12c3d5f1, 0x487f9065, 0x1617243c,
332        0x5c8774e4, 0x76bcd3ec, 0x783819d0, 0x349c8a4b, 0x265d6a36, 0x39fc652e, 0x246831a8,
333        0x488058fc, 0x0a5c75d6, 0x760d4eed, 0x7acd5d5f, 0x2d2957ad, 0x6188b6fe, 0x2084c575,
334        0x67c5ff60, 0x3d6d899b, 0x2759464a, 0x1e4319d2,
335    ]),
336];
337
338/// Round constants for width-32 Poseidon2 on Mersenne31.
339///
340/// Generated by the Grain LFSR with parameters:
341///     field_type=1, alpha=5 (exp_flag=0), n=31, t=32, R_F=8, R_P=30
342///
343/// Generated by `poseidon2/generate_constants.py --field mersenne31 --width 32`.
344///
345/// Layout: internal (30 scalar constants).
346pub const MERSENNE31_POSEIDON2_RC_32_INTERNAL: [Mersenne31; 30] = Mersenne31::new_array([
347    0x3d432793, 0x4195a297, 0x7fcf576b, 0x6bce9b95, 0x3c822af0, 0x7629e5b3, 0x3dddd04e, 0x5a3d0558,
348    0x763e6c75, 0x676f1d88, 0x77b82255, 0x25df8a51, 0x697c3b10, 0x03cf6edf, 0x12b54f78, 0x6633d534,
349    0x426fbcb7, 0x554665dc, 0x5689bdb2, 0x12e747de, 0x60c28745, 0x11ca4ba5, 0x7c7c7b7a, 0x3f0f9583,
350    0x7a3c8210, 0x56c7d993, 0x20f6875f, 0x69e597c8, 0x3c911573, 0x29c7f702,
351]);
352
353/// Create a default width-32 Poseidon2 permutation for Mersenne31.
354pub fn default_mersenne31_poseidon2_32() -> Poseidon2Mersenne31<32> {
355    Poseidon2::new(
356        ExternalLayerConstants::new(
357            MERSENNE31_POSEIDON2_RC_32_EXTERNAL_INITIAL.to_vec(),
358            MERSENNE31_POSEIDON2_RC_32_EXTERNAL_FINAL.to_vec(),
359        ),
360        MERSENNE31_POSEIDON2_RC_32_INTERNAL.to_vec(),
361    )
362}
363
364/// An implementation of the matrix multiplications in the internal and external layers of Poseidon2.
365///
366/// This can act on `[A; WIDTH]` for any ring implementing `Algebra<Mersenne31>`.
367/// If you have either `[Mersenne31::Packing; WIDTH]` or `[Mersenne31; WIDTH]` it will be much faster
368/// to use `Poseidon2Mersenne31<WIDTH>` instead of building a Poseidon2 permutation using this.
369pub struct GenericPoseidon2LinearLayersMersenne31 {}
370
371const POSEIDON2_INTERNAL_MATRIX_DIAG_16_SHIFTS: [u8; 15] =
372    [0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 13, 14, 15, 16];
373
374const POSEIDON2_INTERNAL_MATRIX_DIAG_24_SHIFTS: [u8; 23] = [
375    0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22,
376];
377
378const POSEIDON2_INTERNAL_MATRIX_DIAG_32_SHIFTS: [u8; 31] = [
379    0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25,
380    26, 27, 28, 29, 30,
381];
382
383/// Multiply state by the matrix (1 + Diag(V))
384///
385/// Here V is the vector [-2] + 1 << shifts. This used delayed reduction to be slightly faster.
386fn permute_mut<const N: usize>(state: &mut [Mersenne31; N], shifts: &[u8]) {
387    debug_assert_eq!(shifts.len() + 1, N);
388    let part_sum: u64 = state[1..].iter().map(|x| x.value as u64).sum();
389    let full_sum = part_sum + (state[0].value as u64);
390    let s0 = part_sum + (-state[0]).value as u64;
391    state[0] = from_u62(s0);
392    for i in 1..N {
393        let si = full_sum + ((state[i].value as u64) << shifts[i - 1]);
394        state[i] = from_u62(si);
395    }
396}
397
398impl InternalLayer<Mersenne31, 16, MERSENNE31_S_BOX_DEGREE> for Poseidon2InternalLayerMersenne31 {
399    /// Perform the internal layers of the Poseidon2 permutation on the given state.
400    fn permute_state(&self, state: &mut [Mersenne31; 16]) {
401        internal_permute_state(
402            state,
403            |x| permute_mut(x, &POSEIDON2_INTERNAL_MATRIX_DIAG_16_SHIFTS),
404            &self.internal_constants,
405        );
406    }
407}
408
409impl InternalLayer<Mersenne31, 24, MERSENNE31_S_BOX_DEGREE> for Poseidon2InternalLayerMersenne31 {
410    /// Perform the internal layers of the Poseidon2 permutation on the given state.
411    fn permute_state(&self, state: &mut [Mersenne31; 24]) {
412        internal_permute_state(
413            state,
414            |x| permute_mut(x, &POSEIDON2_INTERNAL_MATRIX_DIAG_24_SHIFTS),
415            &self.internal_constants,
416        );
417    }
418}
419
420impl InternalLayer<Mersenne31, 32, MERSENNE31_S_BOX_DEGREE> for Poseidon2InternalLayerMersenne31 {
421    /// Perform the internal layers of the Poseidon2 permutation on the given state.
422    fn permute_state(&self, state: &mut [Mersenne31; 32]) {
423        internal_permute_state(
424            state,
425            |x| permute_mut(x, &POSEIDON2_INTERNAL_MATRIX_DIAG_32_SHIFTS),
426            &self.internal_constants,
427        );
428    }
429}
430
431impl<const WIDTH: usize> ExternalLayer<Mersenne31, WIDTH, MERSENNE31_S_BOX_DEGREE>
432    for Poseidon2ExternalLayerMersenne31<WIDTH>
433{
434    /// Perform the initial external layers of the Poseidon2 permutation on the given state.
435    fn permute_state_initial(&self, state: &mut [Mersenne31; WIDTH]) {
436        external_initial_permute_state(
437            state,
438            self.external_constants.get_initial_constants(),
439            add_rc_and_sbox_generic,
440            &MDSMat4,
441        );
442    }
443
444    /// Perform the terminal external layers of the Poseidon2 permutation on the given state.
445    fn permute_state_terminal(&self, state: &mut [Mersenne31; WIDTH]) {
446        external_terminal_permute_state(
447            state,
448            self.external_constants.get_terminal_constants(),
449            add_rc_and_sbox_generic,
450            &MDSMat4,
451        );
452    }
453}
454
455impl GenericPoseidon2LinearLayers<16> for GenericPoseidon2LinearLayersMersenne31 {
456    fn internal_linear_layer<R: PrimeCharacteristicRing>(state: &mut [R; 16]) {
457        let part_sum: R = state[1..].iter().map(|r| r.dup()).sum();
458        let full_sum = part_sum.dup() + state[0].dup();
459
460        // The first three diagonal elements are -2, 1, 2 so we do something custom.
461        state[0] = part_sum - state[0].dup();
462        state[1] = full_sum.dup() + state[1].dup();
463        state[2] = full_sum.dup() + state[2].double();
464
465        // For the remaining elements we use the mul_2exp_u64 method.
466        // We need state[1..] as POSEIDON2_INTERNAL_MATRIX_DIAG_16_SHIFTS
467        // doesn't include the shift for the 0'th element as it is -2.
468        state[1..]
469            .iter_mut()
470            .zip(POSEIDON2_INTERNAL_MATRIX_DIAG_16_SHIFTS)
471            .skip(2)
472            .for_each(|(val, diag_shift)| {
473                *val = full_sum.dup() + val.dup().mul_2exp_u64(diag_shift as u64);
474            });
475    }
476}
477
478impl GenericPoseidon2LinearLayers<24> for GenericPoseidon2LinearLayersMersenne31 {
479    fn internal_linear_layer<R: PrimeCharacteristicRing>(state: &mut [R; 24]) {
480        let part_sum: R = state[1..].iter().map(|r| r.dup()).sum();
481        let full_sum = part_sum.dup() + state[0].dup();
482
483        // The first three diagonal elements are -2, 1, 2 so we do something custom.
484        state[0] = part_sum - state[0].dup();
485        state[1] = full_sum.dup() + state[1].dup();
486        state[2] = full_sum.dup() + state[2].double();
487
488        // For the remaining elements we use the mul_2exp_u64 method.
489        // We need state[1..] as POSEIDON2_INTERNAL_MATRIX_DIAG_24_SHIFTS
490        // doesn't include the shift for the 0'th element as it is -2.
491        state[1..]
492            .iter_mut()
493            .zip(POSEIDON2_INTERNAL_MATRIX_DIAG_24_SHIFTS)
494            .skip(2)
495            .for_each(|(val, diag_shift)| {
496                *val = full_sum.dup() + val.dup().mul_2exp_u64(diag_shift as u64);
497            });
498    }
499}
500
501impl GenericPoseidon2LinearLayers<32> for GenericPoseidon2LinearLayersMersenne31 {
502    fn internal_linear_layer<R: PrimeCharacteristicRing>(state: &mut [R; 32]) {
503        let part_sum: R = state[1..].iter().map(|r| r.dup()).sum();
504        let full_sum = part_sum.dup() + state[0].dup();
505
506        // The first three diagonal elements are -2, 1, 2 so we do something custom.
507        state[0] = part_sum - state[0].dup();
508        state[1] = full_sum.dup() + state[1].dup();
509        state[2] = full_sum.dup() + state[2].double();
510
511        // For the remaining elements we use the mul_2exp_u64 method.
512        state[1..]
513            .iter_mut()
514            .zip(POSEIDON2_INTERNAL_MATRIX_DIAG_32_SHIFTS)
515            .skip(2)
516            .for_each(|(val, diag_shift)| {
517                *val = full_sum.dup() + val.dup().mul_2exp_u64(diag_shift as u64);
518            });
519    }
520}
521
522#[cfg(test)]
523mod tests {
524    use p3_symmetric::Permutation;
525    use rand::SeedableRng;
526    use rand_xoshiro::Xoroshiro128Plus;
527
528    use super::*;
529
530    type F = Mersenne31;
531
532    // We need to make some round constants. We use Xoroshiro128Plus for this as we can easily match this PRNG in sage.
533    // See: https://github.com/0xPolygonZero/hash-constants for the sage code used to create all these tests.
534
535    /// Test on a roughly random input.
536    /// This random input is generated by the following sage code:
537    /// set_random_seed(16)
538    /// vector([M31.random_element() for t in range(16)]).
539    #[test]
540    fn test_poseidon2_width_16_random() {
541        let mut input: [F; 16] = Mersenne31::new_array([
542            894848333, 1437655012, 1200606629, 1690012884, 71131202, 1749206695, 1717947831,
543            120589055, 19776022, 42382981, 1831865506, 724844064, 171220207, 1299207443, 227047920,
544            1783754913,
545        ]);
546
547        let expected: [F; 16] = Mersenne31::new_array([
548            1124552602, 2127602268, 1834113265, 1207687593, 1891161485, 245915620, 981277919,
549            627265710, 1534924153, 1580826924, 887997842, 1526280482, 547791593, 1028672510,
550            1803086471, 323071277,
551        ]);
552
553        let mut rng = Xoroshiro128Plus::seed_from_u64(1);
554        let perm = Poseidon2Mersenne31::new_from_rng_128(&mut rng);
555
556        perm.permute_mut(&mut input);
557        assert_eq!(input, expected);
558    }
559
560    /// Test on a roughly random input.
561    /// This random input is generated by the following sage code:
562    /// set_random_seed(24)
563    /// vector([M31.random_element() for t in range(24)]).
564    #[test]
565    fn test_poseidon2_width_24_random() {
566        let mut input: [F; 24] = Mersenne31::new_array([
567            886409618, 1327899896, 1902407911, 591953491, 648428576, 1844789031, 1198336108,
568            355597330, 1799586834, 59617783, 790334801, 1968791836, 559272107, 31054313,
569            1042221543, 474748436, 135686258, 263665994, 1962340735, 1741539604, 2026927696,
570            449439011, 1131357108, 50869465,
571        ]);
572
573        let expected: [F; 24] = Mersenne31::new_array([
574            87189408, 212775836, 954807335, 1424761838, 1222521810, 1264950009, 1891204592,
575            710452896, 957091834, 1776630156, 1091081383, 786687731, 1101902149, 1281649821,
576            436070674, 313565599, 1961711763, 2002894460, 2040173120, 854107426, 25198245,
577            1967213543, 604802266, 2086190331,
578        ]);
579
580        let mut rng = Xoroshiro128Plus::seed_from_u64(1);
581        let perm = Poseidon2Mersenne31::new_from_rng_128(&mut rng);
582
583        perm.permute_mut(&mut input);
584        assert_eq!(input, expected);
585    }
586
587    #[test]
588    fn test_default_mersenne31_poseidon2_width_16() {
589        let mut input: [F; 16] =
590            Mersenne31::new_array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]);
591
592        let expected: [F; 16] = Mersenne31::new_array([
593            0x0b2c803a, 0x5b1ee4d1, 0x49c6b1e3, 0x2cdc280c, 0x310a60c8, 0x530a729e, 0x4e61bcb4,
594            0x2e84d3c3, 0x58709c08, 0x7e82ac42, 0x2162bcef, 0x6d153ab6, 0x742cf0e3, 0x2f21632d,
595            0x61adce1e, 0x1973d6f1,
596        ]);
597
598        let perm = default_mersenne31_poseidon2_16();
599        perm.permute_mut(&mut input);
600
601        assert_eq!(input, expected);
602    }
603
604    #[test]
605    fn test_default_mersenne31_poseidon2_width_24() {
606        let mut input: [F; 24] = Mersenne31::new_array([
607            0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23,
608        ]);
609
610        let expected: [F; 24] = Mersenne31::new_array([
611            0x2040f051, 0x7261dbfa, 0x4fbd519e, 0x2320ecaf, 0x039ef27c, 0x48d60ad5, 0x73ca17ff,
612            0x6023111a, 0x6c5e31e7, 0x373cd90d, 0x75a3ae11, 0x00ecc878, 0x33a7c097, 0x244c2171,
613            0x7552a38e, 0x58d20817, 0x00feecb7, 0x47c43c88, 0x30d3001c, 0x24d09ba6, 0x71f241d9,
614            0x1c72ab2e, 0x4749f79d, 0x61ff7579,
615        ]);
616
617        let perm = default_mersenne31_poseidon2_24();
618        perm.permute_mut(&mut input);
619
620        assert_eq!(input, expected);
621    }
622
623    #[test]
624    fn test_default_mersenne31_poseidon2_width_32() {
625        let mut input: [F; 32] = Mersenne31::new_array([
626            886409618, 1327899896, 1902407911, 591953491, 648428576, 1844789031, 1198336108,
627            355597330, 1799586834, 59617783, 790334801, 1968791836, 559272107, 31054313,
628            1042221543, 474748436, 135686258, 263665994, 1962340735, 1741539604, 2026927696,
629            449439011, 1131357108, 50869465, 894848333, 1437655012, 1200606629, 1690012884,
630            71131202, 1749206695, 1717947831, 120589055,
631        ]);
632
633        let expected: [F; 32] = Mersenne31::new_array([
634            1856060025, 1254059276, 2099136415, 1891507371, 202832695, 754761125, 1546769253,
635            2039240755, 969633288, 117763588, 624654727, 1034887750, 898944818, 1818019588,
636            1662865566, 1426397765, 102254187, 1541093348, 280956251, 1038202157, 1207554722,
637            1615928492, 2099241528, 997904479, 621678012, 724483212, 1292553224, 1107946119,
638            1584500975, 1889218820, 432786428, 1331980049,
639        ]);
640
641        let perm = default_mersenne31_poseidon2_32();
642        perm.permute_mut(&mut input);
643
644        assert_eq!(input, expected);
645    }
646}
p3_mersenne_31/poseidon2.rs

p3_mersenne_31/
poseidon2.rs
