p3_goldilocks/
poseidon2.rs

Help
1//! Implementation of Poseidon2, see: https://eprint.iacr.org/2023/323
2
3//! For now we recreate the implementation given in:
4//! https://github.com/HorizenLabs/poseidon2/blob/main/plain_implementations/src/poseidon2/poseidon2_instance_goldilocks.rs
5//! This uses the constants below along with using the 4x4 matrix:
6//! [[5, 7, 1, 3], [4, 6, 1, 1], [1, 3, 5, 7], [1, 1, 4, 6]]
7//! to build the 4t x 4t matrix used for the external (full) rounds).
8
9//! Long term we will use more optimised internal and external linear layers.
10use alloc::vec::Vec;
11
12use p3_field::{Field, FieldAlgebra};
13use p3_poseidon2::{
14    add_rc_and_sbox_generic, external_initial_permute_state, external_terminal_permute_state,
15    internal_permute_state, matmul_internal, ExternalLayer, ExternalLayerConstants,
16    ExternalLayerConstructor, HLMDSMat4, InternalLayer, InternalLayerConstructor, MDSMat4,
17    Poseidon2,
18};
19
20use crate::Goldilocks;
21
22/// Degree of the chosen permutation polynomial for Goldilocks, used as the Poseidon2 S-Box.
23///
24/// As p - 1 = 2^32 * 3 * 5 * 17 * ... the smallest choice for a degree D satisfying gcd(p - 1, D) = 1 is 7.
25const GOLDILOCKS_S_BOX_DEGREE: u64 = 7;
26
27/// An implementation of the Poseidon2 hash function for the Goldilocks field.
28///
29/// It acts on arrays of the form `[Goldilocks; WIDTH]`.
30/// Currently the internal layers are unoptimized. These could be sped up in a similar way to
31/// how it was done for Monty31 fields.
32pub type Poseidon2Goldilocks<const WIDTH: usize> = Poseidon2<
33    <Goldilocks as Field>::Packing,
34    Poseidon2ExternalLayerGoldilocks<WIDTH>,
35    Poseidon2InternalLayerGoldilocks,
36    WIDTH,
37    GOLDILOCKS_S_BOX_DEGREE,
38>;
39
40/// A recreating of the Poseidon2 implementation by Horizen Labs for the Goldilocks field.
41///
42/// It acts on arrays of the form `[Goldilocks; WIDTH]`
43/// The original implementation can be found here: https://github.com/HorizenLabs/poseidon2.
44/// This implementation is slightly slower than `Poseidon2Goldilocks` as is uses a slower matrix
45/// for the external rounds.
46pub type Poseidon2GoldilocksHL<const WIDTH: usize> = Poseidon2<
47    <Goldilocks as Field>::Packing,
48    Poseidon2ExternalLayerGoldilocksHL<WIDTH>,
49    Poseidon2InternalLayerGoldilocks,
50    WIDTH,
51    GOLDILOCKS_S_BOX_DEGREE,
52>;
53
54pub const MATRIX_DIAG_8_GOLDILOCKS: [Goldilocks; 8] = Goldilocks::new_array([
55    0xa98811a1fed4e3a5,
56    0x1cc48b54f377e2a0,
57    0xe40cd4f6c5609a26,
58    0x11de79ebca97a4a3,
59    0x9177c73d8b7e929c,
60    0x2a6fe8085797e791,
61    0x3de6e93329f8d5ad,
62    0x3f7af9125da962fe,
63]);
64
65pub const MATRIX_DIAG_12_GOLDILOCKS: [Goldilocks; 12] = Goldilocks::new_array([
66    0xc3b6c08e23ba9300,
67    0xd84b5de94a324fb6,
68    0x0d0c371c5b35b84f,
69    0x7964f570e7188037,
70    0x5daf18bbd996604b,
71    0x6743bc47b9595257,
72    0x5528b9362c59bb70,
73    0xac45e25b7127b68b,
74    0xa2077d7dfbb606b5,
75    0xf3faac6faee378ae,
76    0x0c6388b51545e883,
77    0xd27dbb6944917b60,
78]);
79
80pub const MATRIX_DIAG_16_GOLDILOCKS: [Goldilocks; 16] = Goldilocks::new_array([
81    0xde9b91a467d6afc0,
82    0xc5f16b9c76a9be17,
83    0x0ab0fef2d540ac55,
84    0x3001d27009d05773,
85    0xed23b1f906d3d9eb,
86    0x5ce73743cba97054,
87    0x1c3bab944af4ba24,
88    0x2faa105854dbafae,
89    0x53ffb3ae6d421a10,
90    0xbcda9df8884ba396,
91    0xfc1273e4a31807bb,
92    0xc77952573d5142c0,
93    0x56683339a819b85e,
94    0x328fcbd8f0ddc8eb,
95    0xb5101e303fce9cb7,
96    0x774487b8c40089bb,
97]);
98
99pub const MATRIX_DIAG_20_GOLDILOCKS: [Goldilocks; 20] = Goldilocks::new_array([
100    0x95c381fda3b1fa57,
101    0xf36fe9eb1288f42c,
102    0x89f5dcdfef277944,
103    0x106f22eadeb3e2d2,
104    0x684e31a2530e5111,
105    0x27435c5d89fd148e,
106    0x3ebed31c414dbf17,
107    0xfd45b0b2d294e3cc,
108    0x48c904473a7f6dbf,
109    0xe0d1b67809295b4d,
110    0xddd1941e9d199dcb,
111    0x8cfe534eeb742219,
112    0xa6e5261d9e3b8524,
113    0x6897ee5ed0f82c1b,
114    0x0e7dcd0739ee5f78,
115    0x493253f3d0d32363,
116    0xbb2737f5845f05c0,
117    0xa187e810b06ad903,
118    0xb635b995936c4918,
119    0x0b3694a940bd2394,
120]);
121
122/// The internal layers of the Poseidon2 permutation.
123#[derive(Debug, Clone, Default)]
124pub struct Poseidon2InternalLayerGoldilocks {
125    internal_constants: Vec<Goldilocks>,
126}
127
128impl<FA: FieldAlgebra<F = Goldilocks>> InternalLayerConstructor<FA>
129    for Poseidon2InternalLayerGoldilocks
130{
131    fn new_from_constants(internal_constants: Vec<Goldilocks>) -> Self {
132        Self { internal_constants }
133    }
134}
135
136impl<FA: FieldAlgebra<F = Goldilocks>> InternalLayer<FA, 8, GOLDILOCKS_S_BOX_DEGREE>
137    for Poseidon2InternalLayerGoldilocks
138{
139    /// Perform the internal layers of the Poseidon2 permutation on the given state.
140    fn permute_state(&self, state: &mut [FA; 8]) {
141        internal_permute_state::<FA, 8, GOLDILOCKS_S_BOX_DEGREE>(
142            state,
143            |x| matmul_internal(x, MATRIX_DIAG_8_GOLDILOCKS),
144            &self.internal_constants,
145        )
146    }
147}
148
149impl<FA: FieldAlgebra<F = Goldilocks>> InternalLayer<FA, 12, GOLDILOCKS_S_BOX_DEGREE>
150    for Poseidon2InternalLayerGoldilocks
151{
152    /// Perform the internal layers of the Poseidon2 permutation on the given state.
153    fn permute_state(&self, state: &mut [FA; 12]) {
154        internal_permute_state::<FA, 12, GOLDILOCKS_S_BOX_DEGREE>(
155            state,
156            |x| matmul_internal(x, MATRIX_DIAG_12_GOLDILOCKS),
157            &self.internal_constants,
158        )
159    }
160}
161
162impl<FA: FieldAlgebra<F = Goldilocks>> InternalLayer<FA, 16, GOLDILOCKS_S_BOX_DEGREE>
163    for Poseidon2InternalLayerGoldilocks
164{
165    /// Perform the internal layers of the Poseidon2 permutation on the given state.
166    fn permute_state(&self, state: &mut [FA; 16]) {
167        internal_permute_state::<FA, 16, GOLDILOCKS_S_BOX_DEGREE>(
168            state,
169            |x| matmul_internal(x, MATRIX_DIAG_16_GOLDILOCKS),
170            &self.internal_constants,
171        )
172    }
173}
174
175impl<FA: FieldAlgebra<F = Goldilocks>> InternalLayer<FA, 20, GOLDILOCKS_S_BOX_DEGREE>
176    for Poseidon2InternalLayerGoldilocks
177{
178    /// Perform the internal layers of the Poseidon2 permutation on the given state.
179    fn permute_state(&self, state: &mut [FA; 20]) {
180        internal_permute_state::<FA, 20, GOLDILOCKS_S_BOX_DEGREE>(
181            state,
182            |x| matmul_internal(x, MATRIX_DIAG_20_GOLDILOCKS),
183            &self.internal_constants,
184        )
185    }
186}
187
188/// The external layers of the Poseidon2 permutation.
189#[derive(Clone)]
190pub struct Poseidon2ExternalLayerGoldilocks<const WIDTH: usize> {
191    pub(crate) external_constants: ExternalLayerConstants<Goldilocks, WIDTH>,
192}
193
194impl<FA: FieldAlgebra<F = Goldilocks>, const WIDTH: usize> ExternalLayerConstructor<FA, WIDTH>
195    for Poseidon2ExternalLayerGoldilocks<WIDTH>
196{
197    fn new_from_constants(external_constants: ExternalLayerConstants<Goldilocks, WIDTH>) -> Self {
198        Self { external_constants }
199    }
200}
201
202impl<FA: FieldAlgebra<F = Goldilocks>, const WIDTH: usize>
203    ExternalLayer<FA, WIDTH, GOLDILOCKS_S_BOX_DEGREE> for Poseidon2ExternalLayerGoldilocks<WIDTH>
204{
205    /// Perform the initial external layers of the Poseidon2 permutation on the given state.
206    fn permute_state_initial(&self, state: &mut [FA; WIDTH]) {
207        external_initial_permute_state(
208            state,
209            self.external_constants.get_initial_constants(),
210            add_rc_and_sbox_generic::<_, GOLDILOCKS_S_BOX_DEGREE>,
211            &MDSMat4,
212        );
213    }
214
215    /// Perform the terminal external layers of the Poseidon2 permutation on the given state.
216    fn permute_state_terminal(&self, state: &mut [FA; WIDTH]) {
217        external_terminal_permute_state(
218            state,
219            self.external_constants.get_terminal_constants(),
220            add_rc_and_sbox_generic::<_, GOLDILOCKS_S_BOX_DEGREE>,
221            &MDSMat4,
222        );
223    }
224}
225
226/// The external layers of the Poseidon2 permutation used by Horizen Labs.
227#[derive(Clone)]
228pub struct Poseidon2ExternalLayerGoldilocksHL<const WIDTH: usize> {
229    pub(crate) external_constants: ExternalLayerConstants<Goldilocks, WIDTH>,
230}
231
232impl<FA: FieldAlgebra<F = Goldilocks>, const WIDTH: usize> ExternalLayerConstructor<FA, WIDTH>
233    for Poseidon2ExternalLayerGoldilocksHL<WIDTH>
234{
235    fn new_from_constants(external_constants: ExternalLayerConstants<Goldilocks, WIDTH>) -> Self {
236        Self { external_constants }
237    }
238}
239
240impl<FA: FieldAlgebra<F = Goldilocks>, const WIDTH: usize>
241    ExternalLayer<FA, WIDTH, GOLDILOCKS_S_BOX_DEGREE>
242    for Poseidon2ExternalLayerGoldilocksHL<WIDTH>
243{
244    /// Perform the initial external layers of the Poseidon2 permutation on the given state.
245    fn permute_state_initial(&self, state: &mut [FA; WIDTH]) {
246        external_initial_permute_state(
247            state,
248            self.external_constants.get_initial_constants(),
249            add_rc_and_sbox_generic::<_, GOLDILOCKS_S_BOX_DEGREE>,
250            &HLMDSMat4,
251        );
252    }
253
254    /// Perform the terminal external layers of the Poseidon2 permutation on the given state.
255    fn permute_state_terminal(&self, state: &mut [FA; WIDTH]) {
256        external_terminal_permute_state(
257            state,
258            self.external_constants.get_terminal_constants(),
259            add_rc_and_sbox_generic::<_, GOLDILOCKS_S_BOX_DEGREE>,
260            &HLMDSMat4,
261        );
262    }
263}
264
265pub const HL_GOLDILOCKS_8_EXTERNAL_ROUND_CONSTANTS: [[[u64; 8]; 4]; 2] = [
266    [
267        [
268            0xdd5743e7f2a5a5d9,
269            0xcb3a864e58ada44b,
270            0xffa2449ed32f8cdc,
271            0x42025f65d6bd13ee,
272            0x7889175e25506323,
273            0x34b98bb03d24b737,
274            0xbdcc535ecc4faa2a,
275            0x5b20ad869fc0d033,
276        ],
277        [
278            0xf1dda5b9259dfcb4,
279            0x27515210be112d59,
280            0x4227d1718c766c3f,
281            0x26d333161a5bd794,
282            0x49b938957bf4b026,
283            0x4a56b5938b213669,
284            0x1120426b48c8353d,
285            0x6b323c3f10a56cad,
286        ],
287        [
288            0xce57d6245ddca6b2,
289            0xb1fc8d402bba1eb1,
290            0xb5c5096ca959bd04,
291            0x6db55cd306d31f7f,
292            0xc49d293a81cb9641,
293            0x1ce55a4fe979719f,
294            0xa92e60a9d178a4d1,
295            0x002cc64973bcfd8c,
296        ],
297        [
298            0xcea721cce82fb11b,
299            0xe5b55eb8098ece81,
300            0x4e30525c6f1ddd66,
301            0x43c6702827070987,
302            0xaca68430a7b5762a,
303            0x3674238634df9c93,
304            0x88cee1c825e33433,
305            0xde99ae8d74b57176,
306        ],
307    ],
308    [
309        [
310            0x014ef1197d341346,
311            0x9725e20825d07394,
312            0xfdb25aef2c5bae3b,
313            0xbe5402dc598c971e,
314            0x93a5711f04cdca3d,
315            0xc45a9a5b2f8fb97b,
316            0xfe8946a924933545,
317            0x2af997a27369091c,
318        ],
319        [
320            0xaa62c88e0b294011,
321            0x058eb9d810ce9f74,
322            0xb3cb23eced349ae4,
323            0xa3648177a77b4a84,
324            0x43153d905992d95d,
325            0xf4e2a97cda44aa4b,
326            0x5baa2702b908682f,
327            0x082923bdf4f750d1,
328        ],
329        [
330            0x98ae09a325893803,
331            0xf8a6475077968838,
332            0xceb0735bf00b2c5f,
333            0x0a1a5d953888e072,
334            0x2fcb190489f94475,
335            0xb5be06270dec69fc,
336            0x739cb934b09acf8b,
337            0x537750b75ec7f25b,
338        ],
339        [
340            0xe9dd318bae1f3961,
341            0xf7462137299efe1a,
342            0xb1f6b8eee9adb940,
343            0xbdebcc8a809dfe6b,
344            0x40fc1f791b178113,
345            0x3ac1c3362d014864,
346            0x9a016184bdb8aeba,
347            0x95f2394459fbc25e,
348        ],
349    ],
350];
351pub const HL_GOLDILOCKS_8_INTERNAL_ROUND_CONSTANTS: [u64; 22] = [
352    0x488897d85ff51f56,
353    0x1140737ccb162218,
354    0xa7eeb9215866ed35,
355    0x9bd2976fee49fcc9,
356    0xc0c8f0de580a3fcc,
357    0x4fb2dae6ee8fc793,
358    0x343a89f35f37395b,
359    0x223b525a77ca72c8,
360    0x56ccb62574aaa918,
361    0xc4d507d8027af9ed,
362    0xa080673cf0b7e95c,
363    0xf0184884eb70dcf8,
364    0x044f10b0cb3d5c69,
365    0xe9e3f7993938f186,
366    0x1b761c80e772f459,
367    0x606cec607a1b5fac,
368    0x14a0c2e1d45f03cd,
369    0x4eace8855398574f,
370    0xf905ca7103eff3e6,
371    0xf8c8f8d20862c059,
372    0xb524fe8bdd678e5a,
373    0xfbb7865901a1ec41,
374];
375
376#[cfg(test)]
377mod tests {
378    use core::array;
379
380    use p3_field::FieldAlgebra;
381    use p3_poseidon2::Poseidon2;
382    use p3_symmetric::Permutation;
383
384    use super::*;
385
386    type F = Goldilocks;
387
388    // A function which recreates the poseidon2 implementation in
389    // https://github.com/HorizenLabs/poseidon2
390    fn hl_poseidon2_goldilocks_width_8(input: &mut [F; 8]) {
391        const WIDTH: usize = 8;
392
393        // Our Poseidon2 implementation.
394        let poseidon2: Poseidon2GoldilocksHL<WIDTH> = Poseidon2::new(
395            ExternalLayerConstants::<Goldilocks, WIDTH>::new_from_saved_array(
396                HL_GOLDILOCKS_8_EXTERNAL_ROUND_CONSTANTS,
397                Goldilocks::new_array,
398            ),
399            Goldilocks::new_array(HL_GOLDILOCKS_8_INTERNAL_ROUND_CONSTANTS).to_vec(),
400        );
401
402        poseidon2.permute_mut(input);
403    }
404
405    /// Test on the constant 0 input.
406    #[test]
407    fn test_poseidon2_width_8_zeroes() {
408        let mut input: [F; 8] = [Goldilocks::ZERO; 8];
409
410        let expected: [F; 8] = Goldilocks::new_array([
411            4214787979728720400,
412            12324939279576102560,
413            10353596058419792404,
414            15456793487362310586,
415            10065219879212154722,
416            16227496357546636742,
417            2959271128466640042,
418            14285409611125725709,
419        ]);
420        hl_poseidon2_goldilocks_width_8(&mut input);
421        assert_eq!(input, expected);
422    }
423
424    /// Test on the input 0..16.
425    #[test]
426    fn test_poseidon2_width_8_range() {
427        let mut input: [F; 8] = array::from_fn(F::from_canonical_usize);
428
429        let expected: [F; 8] = Goldilocks::new_array([
430            14266028122062624699,
431            5353147180106052723,
432            15203350112844181434,
433            17630919042639565165,
434            16601551015858213987,
435            10184091939013874068,
436            16774100645754596496,
437            12047415603622314780,
438        ]);
439        hl_poseidon2_goldilocks_width_8(&mut input);
440        assert_eq!(input, expected);
441    }
442
443    /// Test on a roughly random input.
444    /// This random input is generated by the following sage code:
445    /// set_random_seed(2468)
446    /// vector([ZZ.random_element(2**31) for t in range(16)])
447    #[test]
448    fn test_poseidon2_width_8_random() {
449        let mut input: [F; 8] = Goldilocks::new_array([
450            5116996373749832116,
451            8931548647907683339,
452            17132360229780760684,
453            11280040044015983889,
454            11957737519043010992,
455            15695650327991256125,
456            17604752143022812942,
457            543194415197607509,
458        ]);
459
460        let expected: [F; 8] = Goldilocks::new_array([
461            1831346684315917658,
462            13497752062035433374,
463            12149460647271516589,
464            15656333994315312197,
465            4671534937670455565,
466            3140092508031220630,
467            4251208148861706881,
468            6973971209430822232,
469        ]);
470
471        hl_poseidon2_goldilocks_width_8(&mut input);
472        assert_eq!(input, expected);
473    }
474}
p3_goldilocks/poseidon2.rs

p3_goldilocks/
poseidon2.rs
