nautilus_lighter/signing/hash/
poseidon2.rs

1// -------------------------------------------------------------------------------------------------
2//  Copyright (C) 2015-2026 Nautech Systems Pty Ltd. All rights reserved.
3//  https://nautechsystems.io
4//
5//  Licensed under the GNU Lesser General Public License Version 3.0 (the "License");
6//  You may not use this file except in compliance with the License.
7//  You may obtain a copy of the License at https://www.gnu.org/licenses/lgpl-3.0.en.html
8//
9//  Unless required by applicable law or agreed to in writing, software
10//  distributed under the License is distributed on an "AS IS" BASIS,
11//  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12//  See the License for the specific language governing permissions and
13//  limitations under the License.
14// -------------------------------------------------------------------------------------------------
15
16//! Poseidon2 permutation and sponge over the Goldilocks field `Fp`.
17//!
18//! The permutation operates on a fixed-width state of [`WIDTH`] field elements
19//! and is composed of [`ROUNDS_F_HALF`] external rounds, then `ROUNDS_P`
20//! internal rounds with the S-box restricted to position 0, then a final
21//! [`ROUNDS_F_HALF`] external rounds. An initial external linear layer is
22//! applied before any round constants are added (the Poseidon2 specification's
23//! "pre-mix"). All round constants and the diagonal of the internal MDS matrix
24//! live in [`super::params`].
25//!
26//! The sponge is the "overwrite" variant the Lighter reference uses: each
27//! absorption block writes the input block into the leading [`RATE`] state
28//! positions (without XORing into prior state) and then permutes; the capacity
29//! `WIDTH - RATE` positions are never touched by absorption. Squeezing reads
30//! [`RATE`] elements at a time and re-permutes on demand. No length padding is
31//! applied; callers are responsible for domain separation.
32//!
33//! All arithmetic is performed through the public [`Fp`] API, so the
34//! constant-time guarantees of the field carry over without exception. The
35//! permutation contains no data-dependent branches; the sponge has only the
36//! public-information branches on input length and requested output length.
37
38use super::params::{
39    EXTERNAL_CONSTANTS, INTERNAL_CONSTANTS, MATRIX_DIAG_12, RATE, ROUNDS_F_HALF, WIDTH,
40};
41use crate::signing::field::{Fp, Fp5};
42
43/// Output digest of the standard Poseidon2 hash, holding [`HASH_OUT`] field elements.
44pub const HASH_OUT: usize = 4;
45
46/// In-place Poseidon2 permutation over a [`WIDTH`]-element state.
47pub fn permute(state: &mut [Fp; WIDTH]) {
48    external_linear_layer(state);
49    full_rounds(state, 0);
50    partial_rounds(state);
51    full_rounds(state, ROUNDS_F_HALF);
52}
53
54/// Run the absorption phase of the "overwrite, no-pad" sponge over `input`
55/// and return the resulting state. Callers squeeze by reading the leading
56/// state positions directly (`num_outputs <= RATE` paths) or by iterating
57/// `permute` between reads ([`hash_n_to_m_no_pad`]).
58///
59/// With an empty `input`, the state stays at zero and no permute is run.
60#[inline]
61fn absorb(input: &[Fp]) -> [Fp; WIDTH] {
62    let mut state = [Fp::ZERO; WIDTH];
63
64    let mut i = 0;
65    while i < input.len() {
66        let chunk_end = core::cmp::min(i + RATE, input.len());
67        for (j, &val) in input[i..chunk_end].iter().enumerate() {
68            state[j] = val;
69        }
70        permute(&mut state);
71        i += RATE;
72    }
73
74    state
75}
76
77/// Variable-length absorb / variable-length squeeze sponge built on [`permute`].
78///
79/// Returns `num_outputs` field elements derived from `input` under the Lighter
80/// "overwrite, no-pad" sponge convention. With an empty `input`, the state
81/// stays at zero and the squeeze reads zeros directly without permuting.
82///
83/// Fixed-size callers ([`hash_n_to_hash_no_pad`], [`hash_to_quintic_extension`])
84/// bypass the [`Vec`] allocation; this entry point exists for callers that
85/// need a variable `num_outputs`.
86#[must_use]
87pub fn hash_n_to_m_no_pad(input: &[Fp], num_outputs: usize) -> Vec<Fp> {
88    let mut state = absorb(input);
89
90    let mut out = Vec::with_capacity(num_outputs);
91    while out.len() < num_outputs {
92        for slot in &state[..RATE] {
93            out.push(*slot);
94            if out.len() == num_outputs {
95                return out;
96            }
97        }
98        permute(&mut state);
99    }
100    out
101}
102
103/// Compress an arbitrary-length input to a fixed [`HASH_OUT`]-element digest.
104///
105/// `HASH_OUT <= RATE`, so the squeeze never re-permutes and there is no
106/// reason to allocate a [`Vec`].
107#[must_use]
108pub fn hash_n_to_hash_no_pad(input: &[Fp]) -> [Fp; HASH_OUT] {
109    let state = absorb(input);
110    [state[0], state[1], state[2], state[3]]
111}
112
113/// Convenience alias for [`hash_n_to_hash_no_pad`] matching the Lighter Go API.
114#[must_use]
115pub fn hash_no_pad(input: &[Fp]) -> [Fp; HASH_OUT] {
116    hash_n_to_hash_no_pad(input)
117}
118
119/// Two-to-one compression of two [`HASH_OUT`]-element digests.
120#[must_use]
121pub fn hash_two_to_one(a: [Fp; HASH_OUT], b: [Fp; HASH_OUT]) -> [Fp; HASH_OUT] {
122    let buf = [a[0], a[1], a[2], a[3], b[0], b[1], b[2], b[3]];
123    hash_n_to_hash_no_pad(&buf)
124}
125
126/// Iteratively compress `inputs` left-to-right via [`hash_two_to_one`].
127///
128/// Returns `inputs[0]` when the slice has a single element, mirroring the Go
129/// reference's `HashNToOne`.
130///
131/// # Panics
132///
133/// Panics if `inputs` is empty.
134#[must_use]
135pub fn hash_n_to_one(inputs: &[[Fp; HASH_OUT]]) -> [Fp; HASH_OUT] {
136    assert!(
137        !inputs.is_empty(),
138        "hash_n_to_one requires at least one input"
139    );
140
141    if inputs.len() == 1 {
142        return inputs[0];
143    }
144
145    let mut acc = hash_two_to_one(inputs[0], inputs[1]);
146    for next in &inputs[2..] {
147        acc = hash_two_to_one(acc, *next);
148    }
149    acc
150}
151
152/// Hash an arbitrary-length input into the quintic extension `Fp5`.
153///
154/// Squeezes 5 field elements and packs them into an [`Fp5`] limb-wise. Used by
155/// the Lighter Schnorr binding to derive a curve scalar from a message digest.
156///
157/// `5 <= RATE`, so the squeeze never re-permutes and there is no reason to
158/// allocate a [`Vec`].
159#[must_use]
160pub fn hash_to_quintic_extension(input: &[Fp]) -> Fp5 {
161    let state = absorb(input);
162    Fp5([state[0], state[1], state[2], state[3], state[4]])
163}
164
165/// Hash a `(Fp5, Fp5)` pair as a 10-element preimage into a single `Fp5`.
166///
167/// Concatenates `a.0 || b.0` and feeds the result through
168/// [`hash_to_quintic_extension`]. Used by Schnorr signing/verification (where
169/// the pair is `(r, hashed_msg)`) and by the L2 tx aggregation step (where the
170/// pair is `(body_digest, attribute_digest)`).
171#[must_use]
172pub fn hash_two_to_quintic(a: Fp5, b: Fp5) -> Fp5 {
173    let mut preimage = [Fp::ZERO; 10];
174    preimage[..5].copy_from_slice(&a.0);
175    preimage[5..].copy_from_slice(&b.0);
176    hash_to_quintic_extension(&preimage)
177}
178
179/// One full (external) S-box layer: `state[i] <- state[i]^7` for all `i`.
180fn sbox_full(state: &mut [Fp; WIDTH]) {
181    for slot in state.iter_mut() {
182        *slot = sbox(*slot);
183    }
184}
185
186/// S-box on a single element: `x -> x^7`.
187#[inline]
188fn sbox(x: Fp) -> Fp {
189    let x2 = x.square();
190    let x6 = (x2 * x).square();
191    x6 * x
192}
193
194/// External linear layer: composition of a 4x4 MDS on each disjoint block of 4
195/// state positions with the all-ones lift across the three blocks. Matches the
196/// Plonky3 / Lighter circulant `circ(2, 3, 1, 1)` formulation.
197fn external_linear_layer(state: &mut [Fp; WIDTH]) {
198    for block in 0..3 {
199        let base = block * 4;
200        let s0 = state[base];
201        let s1 = state[base + 1];
202        let s2 = state[base + 2];
203        let s3 = state[base + 3];
204        let t0 = s0 + s1;
205        let t1 = s2 + s3;
206        let t2 = t0 + t1;
207        let t3 = t2 + s1;
208        let t4 = t2 + s3;
209        let t5 = s0 + s0;
210        let t6 = s2 + s2;
211        state[base] = t3 + t0;
212        state[base + 1] = t6 + t3;
213        state[base + 2] = t1 + t4;
214        state[base + 3] = t5 + t4;
215    }
216
217    let mut sums = [Fp::ZERO; 4];
218
219    for k in 0..4 {
220        let mut j = 0;
221
222        while j < WIDTH {
223            sums[k] += state[j + k];
224            j += 4;
225        }
226    }
227
228    for i in 0..WIDTH {
229        state[i] += sums[i % 4];
230    }
231}
232
233/// Internal linear layer: `state <- (diag(MATRIX_DIAG_12) + J) * state`,
234/// where `J` is the all-ones matrix.
235fn internal_linear_layer(state: &mut [Fp; WIDTH]) {
236    let mut sum = state[0];
237
238    for slot in &state[1..] {
239        sum += *slot;
240    }
241
242    for i in 0..WIDTH {
243        state[i] = state[i] * MATRIX_DIAG_12[i] + sum;
244    }
245}
246
247fn full_rounds(state: &mut [Fp; WIDTH], start: usize) {
248    for round_consts in &EXTERNAL_CONSTANTS[start..start + ROUNDS_F_HALF] {
249        for (slot, rc) in state.iter_mut().zip(round_consts.iter()) {
250            *slot += *rc;
251        }
252        sbox_full(state);
253        external_linear_layer(state);
254    }
255}
256
257fn partial_rounds(state: &mut [Fp; WIDTH]) {
258    for rc in &INTERNAL_CONSTANTS {
259        state[0] += *rc;
260        state[0] = sbox(state[0]);
261        internal_linear_layer(state);
262    }
263}
264
265#[cfg(test)]
266mod tests {
267    use proptest::prelude::*;
268    use rstest::rstest;
269    use serde::Deserialize;
270
271    use super::*;
272    use crate::signing::fixtures::{arb_fp, bytes_to_hex, hex_to_bytes};
273
274    const VECTORS_JSON: &str = include_str!(concat!(
275        env!("CARGO_MANIFEST_DIR"),
276        "/test_data/signing_hash_poseidon2_vectors.json",
277    ));
278
279    #[derive(Debug, Deserialize)]
280    struct VectorsFile {
281        vectors: Vectors,
282    }
283
284    #[derive(Debug, Deserialize)]
285    struct Vectors {
286        permute: Vec<PermuteVector>,
287        sponge: Vec<SpongeVector>,
288        hash_to_quintic: Vec<QuinticVector>,
289        hash_n_to_one: Vec<HashNToOneVector>,
290    }
291
292    #[derive(Debug, Deserialize)]
293    struct PermuteVector {
294        input: String,
295        output: String,
296    }
297
298    #[derive(Debug, Deserialize)]
299    struct SpongeVector {
300        input: String,
301        num_outputs: usize,
302        output: String,
303    }
304
305    #[derive(Debug, Deserialize)]
306    struct QuinticVector {
307        input: String,
308        output: String,
309    }
310
311    #[derive(Debug, Deserialize)]
312    struct HashNToOneVector {
313        inputs: Vec<String>,
314        output: String,
315    }
316
317    fn decode_fps(hex: &str) -> Vec<Fp> {
318        let bytes = hex_to_bytes(hex);
319        assert!(
320            bytes.len().is_multiple_of(8),
321            "fp encoding must be 8-byte multiples, was {} bytes",
322            bytes.len(),
323        );
324        bytes
325            .as_chunks::<8>()
326            .0
327            .iter()
328            .map(|chunk| {
329                let mut buf = [0u8; 8];
330                buf.copy_from_slice(chunk);
331                Fp::try_from_le_bytes(buf).expect("non-canonical Fp limb")
332            })
333            .collect()
334    }
335
336    fn encode_fps(fs: &[Fp]) -> String {
337        let mut bytes = Vec::with_capacity(fs.len() * 8);
338        for f in fs {
339            bytes.extend_from_slice(&f.to_le_bytes());
340        }
341        bytes_to_hex(&bytes)
342    }
343
344    #[rstest]
345    fn permute_matches_go_reference_vectors() {
346        let suite: VectorsFile = serde_json::from_str(VECTORS_JSON).expect("parse vectors");
347        assert!(!suite.vectors.permute.is_empty(), "permute vectors empty");
348
349        for (i, v) in suite.vectors.permute.iter().enumerate() {
350            let input = decode_fps(&v.input);
351            assert_eq!(input.len(), WIDTH, "vector {i}: input width");
352
353            let mut state = [Fp::ZERO; WIDTH];
354            state.copy_from_slice(&input);
355            permute(&mut state);
356
357            assert_eq!(encode_fps(&state), v.output, "vector {i}: permute output");
358        }
359    }
360
361    #[rstest]
362    fn sponge_matches_go_reference_vectors() {
363        let suite: VectorsFile = serde_json::from_str(VECTORS_JSON).expect("parse vectors");
364        assert!(!suite.vectors.sponge.is_empty(), "sponge vectors empty");
365
366        for (i, v) in suite.vectors.sponge.iter().enumerate() {
367            let input = decode_fps(&v.input);
368            let out = hash_n_to_m_no_pad(&input, v.num_outputs);
369
370            assert_eq!(out.len(), v.num_outputs, "vector {i}: sponge output length");
371            assert_eq!(encode_fps(&out), v.output, "vector {i}: sponge output");
372        }
373    }
374
375    #[rstest]
376    fn hash_to_quintic_matches_go_reference_vectors() {
377        let suite: VectorsFile = serde_json::from_str(VECTORS_JSON).expect("parse vectors");
378        assert!(
379            !suite.vectors.hash_to_quintic.is_empty(),
380            "hash_to_quintic vectors empty",
381        );
382
383        for (i, v) in suite.vectors.hash_to_quintic.iter().enumerate() {
384            let input = decode_fps(&v.input);
385            let out = hash_to_quintic_extension(&input);
386
387            assert_eq!(
388                bytes_to_hex(&out.to_le_bytes()),
389                v.output,
390                "vector {i}: hash_to_quintic output",
391            );
392        }
393    }
394
395    #[rstest]
396    fn hash_two_to_one_matches_concatenation() {
397        let a = [
398            Fp::from_u64_reduce(1),
399            Fp::from_u64_reduce(2),
400            Fp::from_u64_reduce(3),
401            Fp::from_u64_reduce(4),
402        ];
403        let b = [
404            Fp::from_u64_reduce(5),
405            Fp::from_u64_reduce(6),
406            Fp::from_u64_reduce(7),
407            Fp::from_u64_reduce(8),
408        ];
409        let buf = [a[0], a[1], a[2], a[3], b[0], b[1], b[2], b[3]];
410        assert_eq!(hash_two_to_one(a, b), hash_n_to_hash_no_pad(&buf));
411    }
412
413    #[rstest]
414    fn hash_n_to_one_single_input_is_identity() {
415        let a = [
416            Fp::from_u64_reduce(11),
417            Fp::from_u64_reduce(22),
418            Fp::from_u64_reduce(33),
419            Fp::from_u64_reduce(44),
420        ];
421        assert_eq!(hash_n_to_one(&[a]), a);
422    }
423
424    #[rstest]
425    fn hash_n_to_one_matches_go_reference_vectors() {
426        let suite: VectorsFile = serde_json::from_str(VECTORS_JSON).expect("parse vectors");
427        assert!(
428            !suite.vectors.hash_n_to_one.is_empty(),
429            "hash_n_to_one vectors empty",
430        );
431
432        for (i, v) in suite.vectors.hash_n_to_one.iter().enumerate() {
433            let inputs: Vec<[Fp; HASH_OUT]> = v
434                .inputs
435                .iter()
436                .map(|hex| {
437                    let limbs = decode_fps(hex);
438                    assert_eq!(
439                        limbs.len(),
440                        HASH_OUT,
441                        "vector {i}: each input must encode {HASH_OUT} limbs, was {}",
442                        limbs.len(),
443                    );
444                    [limbs[0], limbs[1], limbs[2], limbs[3]]
445                })
446                .collect();
447
448            let out = hash_n_to_one(&inputs);
449
450            assert_eq!(
451                encode_fps(&out),
452                v.output,
453                "vector {i}: hash_n_to_one output (n={})",
454                inputs.len(),
455            );
456        }
457    }
458
459    #[rstest]
460    #[should_panic(expected = "hash_n_to_one requires at least one input")]
461    fn hash_n_to_one_empty_panics() {
462        let _ = hash_n_to_one(&[]);
463    }
464
465    /// Empty input reads zeros from the uninitialised state for the first
466    /// `RATE` squeeze outputs (no permute happens before the first wrap of
467    /// the squeeze loop). Once `num_outputs > RATE`, the sponge permutes
468    /// the all-zero state and subsequent outputs are no longer zero.
469    #[rstest]
470    #[case(0)]
471    #[case(1)]
472    #[case(RATE - 1)]
473    #[case(RATE)]
474    fn empty_input_squeezes_zeros_up_to_rate(#[case] num_outputs: usize) {
475        let out = hash_n_to_m_no_pad(&[], num_outputs);
476        assert_eq!(out.len(), num_outputs, "output length mismatch");
477        for (i, fp) in out.iter().enumerate() {
478            assert!(fp.is_zero(), "slot {i} must be zero, was {fp:?}");
479        }
480    }
481
482    /// Sponge runs cleanly across every absorb-loop boundary width.
483    /// Verifies no panics, correct output length, and determinism on the
484    /// boundary inputs.
485    #[rstest]
486    #[case(1)]
487    #[case(RATE - 1)]
488    #[case(RATE)]
489    #[case(RATE + 1)]
490    #[case(2 * RATE - 1)]
491    #[case(2 * RATE)]
492    #[case(2 * RATE + 1)]
493    #[case(3 * RATE)]
494    fn sponge_handles_input_length_at_rate_boundaries(#[case] input_len: usize) {
495        let input: Vec<Fp> = (0..input_len)
496            .map(|i| Fp::from_u64_reduce(i as u64 + 1))
497            .collect();
498        let out_a = hash_n_to_m_no_pad(&input, HASH_OUT);
499        let out_b = hash_n_to_m_no_pad(&input, HASH_OUT);
500        assert_eq!(out_a.len(), HASH_OUT, "input_len {input_len}: length");
501        assert_eq!(out_a, out_b, "input_len {input_len}: not deterministic");
502    }
503
504    proptest! {
505        /// `permute` is deterministic.
506        #[rstest]
507        fn prop_permute_deterministic(s in any::<[u64; WIDTH]>()) {
508            let state: [Fp; WIDTH] = core::array::from_fn(|i| Fp::from_u64_reduce(s[i]));
509            let mut s1 = state;
510            let mut s2 = state;
511            permute(&mut s1);
512            permute(&mut s2);
513            prop_assert_eq!(s1, s2);
514        }
515
516        /// `permute` is injective on distinct states (probabilistic - over
517        /// any pair of distinct inputs, outputs almost surely differ).
518        #[rstest]
519        fn prop_permute_injective_on_pairs(
520            s1 in any::<[u64; WIDTH]>(),
521            s2 in any::<[u64; WIDTH]>(),
522        ) {
523            let mut state1: [Fp; WIDTH] = core::array::from_fn(|i| Fp::from_u64_reduce(s1[i]));
524            let mut state2: [Fp; WIDTH] = core::array::from_fn(|i| Fp::from_u64_reduce(s2[i]));
525            prop_assume!(state1 != state2);
526            permute(&mut state1);
527            permute(&mut state2);
528            prop_assert_ne!(state1, state2);
529        }
530
531        /// `hash_no_pad` is deterministic over arbitrary input vectors.
532        #[rstest]
533        fn prop_hash_no_pad_deterministic(
534            input in proptest::collection::vec(arb_fp(), 0..32),
535        ) {
536            prop_assert_eq!(hash_no_pad(&input), hash_no_pad(&input));
537        }
538
539        /// `hash_two_to_one(a, b) == hash_no_pad(a || b)`.
540        #[rstest]
541        fn prop_hash_two_to_one_equals_concat(
542            a in any::<[u64; HASH_OUT]>(),
543            b in any::<[u64; HASH_OUT]>(),
544        ) {
545            let a_fp: [Fp; HASH_OUT] = core::array::from_fn(|i| Fp::from_u64_reduce(a[i]));
546            let b_fp: [Fp; HASH_OUT] = core::array::from_fn(|i| Fp::from_u64_reduce(b[i]));
547            let concat = [
548                a_fp[0], a_fp[1], a_fp[2], a_fp[3],
549                b_fp[0], b_fp[1], b_fp[2], b_fp[3],
550            ];
551            prop_assert_eq!(hash_two_to_one(a_fp, b_fp), hash_no_pad(&concat));
552        }
553
554        /// `hash_n_to_one` is the left fold of `hash_two_to_one` for any
555        /// non-empty input list.
556        #[rstest]
557        fn prop_hash_n_to_one_left_fold(
558            inputs in proptest::collection::vec(any::<[u64; HASH_OUT]>(), 1..6),
559        ) {
560            let inputs_fp: Vec<[Fp; HASH_OUT]> = inputs
561                .iter()
562                .map(|raw| core::array::from_fn(|j| Fp::from_u64_reduce(raw[j])))
563                .collect();
564            let mut expected = inputs_fp[0];
565            for next in &inputs_fp[1..] {
566                expected = hash_two_to_one(expected, *next);
567            }
568            prop_assert_eq!(hash_n_to_one(&inputs_fp), expected);
569        }
570
571        /// `hash_to_quintic_extension(input)` packs into Fp5 deterministically.
572        #[rstest]
573        fn prop_hash_to_quintic_extension_deterministic(
574            input in proptest::collection::vec(arb_fp(), 0..32),
575        ) {
576            prop_assert_eq!(
577                hash_to_quintic_extension(&input),
578                hash_to_quintic_extension(&input),
579            );
580        }
581
582        /// `hash_two_to_quintic` matches the explicit 10-element preimage
583        /// hash through `hash_to_quintic_extension`.
584        #[rstest]
585        fn prop_hash_two_to_quintic_matches_concat(
586            a in any::<[u64; 5]>(),
587            b in any::<[u64; 5]>(),
588        ) {
589            let a_fp5 = Fp5::from_u64s_reduce(a);
590            let b_fp5 = Fp5::from_u64s_reduce(b);
591            let mut concat = [Fp::ZERO; 10];
592            concat[..5].copy_from_slice(&a_fp5.0);
593            concat[5..].copy_from_slice(&b_fp5.0);
594            prop_assert_eq!(
595                hash_two_to_quintic(a_fp5, b_fp5),
596                hash_to_quintic_extension(&concat),
597            );
598        }
599    }
600}
nautilus_lighter/signing/hash/poseidon2.rs

nautilus_lighter/signing/hash/
poseidon2.rs
