p3_goldilocks/
poseidon2.rs

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::{Algebra, InjectiveMonomial};
13use p3_poseidon2::{
14    ExternalLayer, ExternalLayerConstants, ExternalLayerConstructor, HLMDSMat4, InternalLayer,
15    InternalLayerConstructor, MDSMat4, Poseidon2, add_rc_and_sbox_generic,
16    external_initial_permute_state, external_terminal_permute_state, internal_permute_state,
17    matmul_internal,
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,
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,
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 InternalLayerConstructor<Goldilocks> for Poseidon2InternalLayerGoldilocks {
129    fn new_from_constants(internal_constants: Vec<Goldilocks>) -> Self {
130        Self { internal_constants }
131    }
132}
133
134impl<A: Algebra<Goldilocks> + InjectiveMonomial<GOLDILOCKS_S_BOX_DEGREE>>
135    InternalLayer<A, 8, GOLDILOCKS_S_BOX_DEGREE> for Poseidon2InternalLayerGoldilocks
136{
137    /// Perform the internal layers of the Poseidon2 permutation on the given state.
138    fn permute_state(&self, state: &mut [A; 8]) {
139        internal_permute_state(
140            state,
141            |x| matmul_internal(x, MATRIX_DIAG_8_GOLDILOCKS),
142            &self.internal_constants,
143        );
144    }
145}
146
147impl<A: Algebra<Goldilocks> + InjectiveMonomial<GOLDILOCKS_S_BOX_DEGREE>>
148    InternalLayer<A, 12, GOLDILOCKS_S_BOX_DEGREE> for Poseidon2InternalLayerGoldilocks
149{
150    /// Perform the internal layers of the Poseidon2 permutation on the given state.
151    fn permute_state(&self, state: &mut [A; 12]) {
152        internal_permute_state(
153            state,
154            |x| matmul_internal(x, MATRIX_DIAG_12_GOLDILOCKS),
155            &self.internal_constants,
156        );
157    }
158}
159
160impl<A: Algebra<Goldilocks> + InjectiveMonomial<GOLDILOCKS_S_BOX_DEGREE>>
161    InternalLayer<A, 16, GOLDILOCKS_S_BOX_DEGREE> for Poseidon2InternalLayerGoldilocks
162{
163    /// Perform the internal layers of the Poseidon2 permutation on the given state.
164    fn permute_state(&self, state: &mut [A; 16]) {
165        internal_permute_state(
166            state,
167            |x| matmul_internal(x, MATRIX_DIAG_16_GOLDILOCKS),
168            &self.internal_constants,
169        );
170    }
171}
172
173impl<A: Algebra<Goldilocks> + InjectiveMonomial<GOLDILOCKS_S_BOX_DEGREE>>
174    InternalLayer<A, 20, GOLDILOCKS_S_BOX_DEGREE> for Poseidon2InternalLayerGoldilocks
175{
176    /// Perform the internal layers of the Poseidon2 permutation on the given state.
177    fn permute_state(&self, state: &mut [A; 20]) {
178        internal_permute_state(
179            state,
180            |x| matmul_internal(x, MATRIX_DIAG_20_GOLDILOCKS),
181            &self.internal_constants,
182        );
183    }
184}
185
186/// The external layers of the Poseidon2 permutation.
187#[derive(Clone)]
188pub struct Poseidon2ExternalLayerGoldilocks<const WIDTH: usize> {
189    pub(crate) external_constants: ExternalLayerConstants<Goldilocks, WIDTH>,
190}
191
192impl<const WIDTH: usize> ExternalLayerConstructor<Goldilocks, WIDTH>
193    for Poseidon2ExternalLayerGoldilocks<WIDTH>
194{
195    fn new_from_constants(external_constants: ExternalLayerConstants<Goldilocks, WIDTH>) -> Self {
196        Self { external_constants }
197    }
198}
199
200impl<A: Algebra<Goldilocks> + InjectiveMonomial<GOLDILOCKS_S_BOX_DEGREE>, const WIDTH: usize>
201    ExternalLayer<A, WIDTH, GOLDILOCKS_S_BOX_DEGREE> for Poseidon2ExternalLayerGoldilocks<WIDTH>
202{
203    /// Perform the initial external layers of the Poseidon2 permutation on the given state.
204    fn permute_state_initial(&self, state: &mut [A; WIDTH]) {
205        external_initial_permute_state(
206            state,
207            self.external_constants.get_initial_constants(),
208            add_rc_and_sbox_generic,
209            &MDSMat4,
210        );
211    }
212
213    /// Perform the terminal external layers of the Poseidon2 permutation on the given state.
214    fn permute_state_terminal(&self, state: &mut [A; WIDTH]) {
215        external_terminal_permute_state(
216            state,
217            self.external_constants.get_terminal_constants(),
218            add_rc_and_sbox_generic,
219            &MDSMat4,
220        );
221    }
222}
223
224/// The external layers of the Poseidon2 permutation used by Horizen Labs.
225#[derive(Clone)]
226pub struct Poseidon2ExternalLayerGoldilocksHL<const WIDTH: usize> {
227    pub(crate) external_constants: ExternalLayerConstants<Goldilocks, WIDTH>,
228}
229
230impl<const WIDTH: usize> ExternalLayerConstructor<Goldilocks, WIDTH>
231    for Poseidon2ExternalLayerGoldilocksHL<WIDTH>
232{
233    fn new_from_constants(external_constants: ExternalLayerConstants<Goldilocks, WIDTH>) -> Self {
234        Self { external_constants }
235    }
236}
237
238impl<A: Algebra<Goldilocks> + InjectiveMonomial<GOLDILOCKS_S_BOX_DEGREE>, const WIDTH: usize>
239    ExternalLayer<A, WIDTH, GOLDILOCKS_S_BOX_DEGREE> for Poseidon2ExternalLayerGoldilocksHL<WIDTH>
240{
241    /// Perform the initial external layers of the Poseidon2 permutation on the given state.
242    fn permute_state_initial(&self, state: &mut [A; WIDTH]) {
243        external_initial_permute_state(
244            state,
245            self.external_constants.get_initial_constants(),
246            add_rc_and_sbox_generic,
247            &HLMDSMat4,
248        );
249    }
250
251    /// Perform the terminal external layers of the Poseidon2 permutation on the given state.
252    fn permute_state_terminal(&self, state: &mut [A; WIDTH]) {
253        external_terminal_permute_state(
254            state,
255            self.external_constants.get_terminal_constants(),
256            add_rc_and_sbox_generic,
257            &HLMDSMat4,
258        );
259    }
260}
261
262pub const HL_GOLDILOCKS_8_EXTERNAL_ROUND_CONSTANTS: [[[u64; 8]; 4]; 2] = [
263    [
264        [
265            0xdd5743e7f2a5a5d9,
266            0xcb3a864e58ada44b,
267            0xffa2449ed32f8cdc,
268            0x42025f65d6bd13ee,
269            0x7889175e25506323,
270            0x34b98bb03d24b737,
271            0xbdcc535ecc4faa2a,
272            0x5b20ad869fc0d033,
273        ],
274        [
275            0xf1dda5b9259dfcb4,
276            0x27515210be112d59,
277            0x4227d1718c766c3f,
278            0x26d333161a5bd794,
279            0x49b938957bf4b026,
280            0x4a56b5938b213669,
281            0x1120426b48c8353d,
282            0x6b323c3f10a56cad,
283        ],
284        [
285            0xce57d6245ddca6b2,
286            0xb1fc8d402bba1eb1,
287            0xb5c5096ca959bd04,
288            0x6db55cd306d31f7f,
289            0xc49d293a81cb9641,
290            0x1ce55a4fe979719f,
291            0xa92e60a9d178a4d1,
292            0x002cc64973bcfd8c,
293        ],
294        [
295            0xcea721cce82fb11b,
296            0xe5b55eb8098ece81,
297            0x4e30525c6f1ddd66,
298            0x43c6702827070987,
299            0xaca68430a7b5762a,
300            0x3674238634df9c93,
301            0x88cee1c825e33433,
302            0xde99ae8d74b57176,
303        ],
304    ],
305    [
306        [
307            0x014ef1197d341346,
308            0x9725e20825d07394,
309            0xfdb25aef2c5bae3b,
310            0xbe5402dc598c971e,
311            0x93a5711f04cdca3d,
312            0xc45a9a5b2f8fb97b,
313            0xfe8946a924933545,
314            0x2af997a27369091c,
315        ],
316        [
317            0xaa62c88e0b294011,
318            0x058eb9d810ce9f74,
319            0xb3cb23eced349ae4,
320            0xa3648177a77b4a84,
321            0x43153d905992d95d,
322            0xf4e2a97cda44aa4b,
323            0x5baa2702b908682f,
324            0x082923bdf4f750d1,
325        ],
326        [
327            0x98ae09a325893803,
328            0xf8a6475077968838,
329            0xceb0735bf00b2c5f,
330            0x0a1a5d953888e072,
331            0x2fcb190489f94475,
332            0xb5be06270dec69fc,
333            0x739cb934b09acf8b,
334            0x537750b75ec7f25b,
335        ],
336        [
337            0xe9dd318bae1f3961,
338            0xf7462137299efe1a,
339            0xb1f6b8eee9adb940,
340            0xbdebcc8a809dfe6b,
341            0x40fc1f791b178113,
342            0x3ac1c3362d014864,
343            0x9a016184bdb8aeba,
344            0x95f2394459fbc25e,
345        ],
346    ],
347];
348pub const HL_GOLDILOCKS_8_INTERNAL_ROUND_CONSTANTS: [u64; 22] = [
349    0x488897d85ff51f56,
350    0x1140737ccb162218,
351    0xa7eeb9215866ed35,
352    0x9bd2976fee49fcc9,
353    0xc0c8f0de580a3fcc,
354    0x4fb2dae6ee8fc793,
355    0x343a89f35f37395b,
356    0x223b525a77ca72c8,
357    0x56ccb62574aaa918,
358    0xc4d507d8027af9ed,
359    0xa080673cf0b7e95c,
360    0xf0184884eb70dcf8,
361    0x044f10b0cb3d5c69,
362    0xe9e3f7993938f186,
363    0x1b761c80e772f459,
364    0x606cec607a1b5fac,
365    0x14a0c2e1d45f03cd,
366    0x4eace8855398574f,
367    0xf905ca7103eff3e6,
368    0xf8c8f8d20862c059,
369    0xb524fe8bdd678e5a,
370    0xfbb7865901a1ec41,
371];
372
373#[cfg(test)]
374mod tests {
375    use core::array;
376
377    use p3_field::PrimeCharacteristicRing;
378    use p3_poseidon2::Poseidon2;
379    use p3_symmetric::Permutation;
380
381    use super::*;
382
383    type F = Goldilocks;
384
385    // A function which recreates the poseidon2 implementation in
386    // https://github.com/HorizenLabs/poseidon2
387    fn hl_poseidon2_goldilocks_width_8(input: &mut [F; 8]) {
388        const WIDTH: usize = 8;
389
390        // Our Poseidon2 implementation.
391        let poseidon2: Poseidon2GoldilocksHL<WIDTH> = Poseidon2::new(
392            ExternalLayerConstants::<Goldilocks, WIDTH>::new_from_saved_array(
393                HL_GOLDILOCKS_8_EXTERNAL_ROUND_CONSTANTS,
394                Goldilocks::new_array,
395            ),
396            Goldilocks::new_array(HL_GOLDILOCKS_8_INTERNAL_ROUND_CONSTANTS).to_vec(),
397        );
398
399        poseidon2.permute_mut(input);
400    }
401
402    /// Test on the constant 0 input.
403    #[test]
404    fn test_poseidon2_width_8_zeros() {
405        let mut input: [F; 8] = [Goldilocks::ZERO; 8];
406
407        let expected: [F; 8] = Goldilocks::new_array([
408            4214787979728720400,
409            12324939279576102560,
410            10353596058419792404,
411            15456793487362310586,
412            10065219879212154722,
413            16227496357546636742,
414            2959271128466640042,
415            14285409611125725709,
416        ]);
417        hl_poseidon2_goldilocks_width_8(&mut input);
418        assert_eq!(input, expected);
419    }
420
421    /// Test on the input 0..16.
422    #[test]
423    fn test_poseidon2_width_8_range() {
424        let mut input: [F; 8] = array::from_fn(|i| F::from_u64(i as u64));
425
426        let expected: [F; 8] = Goldilocks::new_array([
427            14266028122062624699,
428            5353147180106052723,
429            15203350112844181434,
430            17630919042639565165,
431            16601551015858213987,
432            10184091939013874068,
433            16774100645754596496,
434            12047415603622314780,
435        ]);
436        hl_poseidon2_goldilocks_width_8(&mut input);
437        assert_eq!(input, expected);
438    }
439
440    /// Test on a roughly random input.
441    /// This random input is generated by the following sage code:
442    /// set_random_seed(2468)
443    /// vector([ZZ.random_element(2**31) for t in range(16)])
444    #[test]
445    fn test_poseidon2_width_8_random() {
446        let mut input: [F; 8] = Goldilocks::new_array([
447            5116996373749832116,
448            8931548647907683339,
449            17132360229780760684,
450            11280040044015983889,
451            11957737519043010992,
452            15695650327991256125,
453            17604752143022812942,
454            543194415197607509,
455        ]);
456
457        let expected: [F; 8] = Goldilocks::new_array([
458            1831346684315917658,
459            13497752062035433374,
460            12149460647271516589,
461            15656333994315312197,
462            4671534937670455565,
463            3140092508031220630,
464            4251208148861706881,
465            6973971209430822232,
466        ]);
467
468        hl_poseidon2_goldilocks_width_8(&mut input);
469        assert_eq!(input, expected);
470    }
471}
p3_goldilocks/poseidon2.rs

p3_goldilocks/
poseidon2.rs
