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            .chunks_exact(8)
326            .map(|chunk| {
327                let mut buf = [0u8; 8];
328                buf.copy_from_slice(chunk);
329                Fp::try_from_le_bytes(buf).expect("non-canonical Fp limb")
330            })
331            .collect()
332    }
333
334    fn encode_fps(fs: &[Fp]) -> String {
335        let mut bytes = Vec::with_capacity(fs.len() * 8);
336        for f in fs {
337            bytes.extend_from_slice(&f.to_le_bytes());
338        }
339        bytes_to_hex(&bytes)
340    }
341
342    #[rstest]
343    fn permute_matches_go_reference_vectors() {
344        let suite: VectorsFile = serde_json::from_str(VECTORS_JSON).expect("parse vectors");
345        assert!(!suite.vectors.permute.is_empty(), "permute vectors empty");
346
347        for (i, v) in suite.vectors.permute.iter().enumerate() {
348            let input = decode_fps(&v.input);
349            assert_eq!(input.len(), WIDTH, "vector {i}: input width");
350
351            let mut state = [Fp::ZERO; WIDTH];
352            state.copy_from_slice(&input);
353            permute(&mut state);
354
355            assert_eq!(encode_fps(&state), v.output, "vector {i}: permute output");
356        }
357    }
358
359    #[rstest]
360    fn sponge_matches_go_reference_vectors() {
361        let suite: VectorsFile = serde_json::from_str(VECTORS_JSON).expect("parse vectors");
362        assert!(!suite.vectors.sponge.is_empty(), "sponge vectors empty");
363
364        for (i, v) in suite.vectors.sponge.iter().enumerate() {
365            let input = decode_fps(&v.input);
366            let out = hash_n_to_m_no_pad(&input, v.num_outputs);
367
368            assert_eq!(out.len(), v.num_outputs, "vector {i}: sponge output length");
369            assert_eq!(encode_fps(&out), v.output, "vector {i}: sponge output");
370        }
371    }
372
373    #[rstest]
374    fn hash_to_quintic_matches_go_reference_vectors() {
375        let suite: VectorsFile = serde_json::from_str(VECTORS_JSON).expect("parse vectors");
376        assert!(
377            !suite.vectors.hash_to_quintic.is_empty(),
378            "hash_to_quintic vectors empty",
379        );
380
381        for (i, v) in suite.vectors.hash_to_quintic.iter().enumerate() {
382            let input = decode_fps(&v.input);
383            let out = hash_to_quintic_extension(&input);
384
385            assert_eq!(
386                bytes_to_hex(&out.to_le_bytes()),
387                v.output,
388                "vector {i}: hash_to_quintic output",
389            );
390        }
391    }
392
393    #[rstest]
394    fn hash_two_to_one_matches_concatenation() {
395        let a = [
396            Fp::from_u64_reduce(1),
397            Fp::from_u64_reduce(2),
398            Fp::from_u64_reduce(3),
399            Fp::from_u64_reduce(4),
400        ];
401        let b = [
402            Fp::from_u64_reduce(5),
403            Fp::from_u64_reduce(6),
404            Fp::from_u64_reduce(7),
405            Fp::from_u64_reduce(8),
406        ];
407        let buf = [a[0], a[1], a[2], a[3], b[0], b[1], b[2], b[3]];
408        assert_eq!(hash_two_to_one(a, b), hash_n_to_hash_no_pad(&buf));
409    }
410
411    #[rstest]
412    fn hash_n_to_one_single_input_is_identity() {
413        let a = [
414            Fp::from_u64_reduce(11),
415            Fp::from_u64_reduce(22),
416            Fp::from_u64_reduce(33),
417            Fp::from_u64_reduce(44),
418        ];
419        assert_eq!(hash_n_to_one(&[a]), a);
420    }
421
422    #[rstest]
423    fn hash_n_to_one_matches_go_reference_vectors() {
424        let suite: VectorsFile = serde_json::from_str(VECTORS_JSON).expect("parse vectors");
425        assert!(
426            !suite.vectors.hash_n_to_one.is_empty(),
427            "hash_n_to_one vectors empty",
428        );
429
430        for (i, v) in suite.vectors.hash_n_to_one.iter().enumerate() {
431            let inputs: Vec<[Fp; HASH_OUT]> = v
432                .inputs
433                .iter()
434                .map(|hex| {
435                    let limbs = decode_fps(hex);
436                    assert_eq!(
437                        limbs.len(),
438                        HASH_OUT,
439                        "vector {i}: each input must encode {HASH_OUT} limbs, was {}",
440                        limbs.len(),
441                    );
442                    [limbs[0], limbs[1], limbs[2], limbs[3]]
443                })
444                .collect();
445
446            let out = hash_n_to_one(&inputs);
447
448            assert_eq!(
449                encode_fps(&out),
450                v.output,
451                "vector {i}: hash_n_to_one output (n={})",
452                inputs.len(),
453            );
454        }
455    }
456
457    #[rstest]
458    #[should_panic(expected = "hash_n_to_one requires at least one input")]
459    fn hash_n_to_one_empty_panics() {
460        let _ = hash_n_to_one(&[]);
461    }
462
463    /// Empty input reads zeros from the uninitialised state for the first
464    /// `RATE` squeeze outputs (no permute happens before the first wrap of
465    /// the squeeze loop). Once `num_outputs > RATE`, the sponge permutes
466    /// the all-zero state and subsequent outputs are no longer zero.
467    #[rstest]
468    #[case(0)]
469    #[case(1)]
470    #[case(RATE - 1)]
471    #[case(RATE)]
472    fn empty_input_squeezes_zeros_up_to_rate(#[case] num_outputs: usize) {
473        let out = hash_n_to_m_no_pad(&[], num_outputs);
474        assert_eq!(out.len(), num_outputs, "output length mismatch");
475        for (i, fp) in out.iter().enumerate() {
476            assert!(fp.is_zero(), "slot {i} must be zero, was {fp:?}");
477        }
478    }
479
480    /// Sponge runs cleanly across every absorb-loop boundary width.
481    /// Verifies no panics, correct output length, and determinism on the
482    /// boundary inputs.
483    #[rstest]
484    #[case(1)]
485    #[case(RATE - 1)]
486    #[case(RATE)]
487    #[case(RATE + 1)]
488    #[case(2 * RATE - 1)]
489    #[case(2 * RATE)]
490    #[case(2 * RATE + 1)]
491    #[case(3 * RATE)]
492    fn sponge_handles_input_length_at_rate_boundaries(#[case] input_len: usize) {
493        let input: Vec<Fp> = (0..input_len)
494            .map(|i| Fp::from_u64_reduce(i as u64 + 1))
495            .collect();
496        let out_a = hash_n_to_m_no_pad(&input, HASH_OUT);
497        let out_b = hash_n_to_m_no_pad(&input, HASH_OUT);
498        assert_eq!(out_a.len(), HASH_OUT, "input_len {input_len}: length");
499        assert_eq!(out_a, out_b, "input_len {input_len}: not deterministic");
500    }
501
502    proptest! {
503        /// `permute` is deterministic.
504        #[rstest]
505        fn prop_permute_deterministic(s in any::<[u64; WIDTH]>()) {
506            let state: [Fp; WIDTH] = core::array::from_fn(|i| Fp::from_u64_reduce(s[i]));
507            let mut s1 = state;
508            let mut s2 = state;
509            permute(&mut s1);
510            permute(&mut s2);
511            prop_assert_eq!(s1, s2);
512        }
513
514        /// `permute` is injective on distinct states (probabilistic — over
515        /// any pair of distinct inputs, outputs almost surely differ).
516        #[rstest]
517        fn prop_permute_injective_on_pairs(
518            s1 in any::<[u64; WIDTH]>(),
519            s2 in any::<[u64; WIDTH]>(),
520        ) {
521            let mut state1: [Fp; WIDTH] = core::array::from_fn(|i| Fp::from_u64_reduce(s1[i]));
522            let mut state2: [Fp; WIDTH] = core::array::from_fn(|i| Fp::from_u64_reduce(s2[i]));
523            prop_assume!(state1 != state2);
524            permute(&mut state1);
525            permute(&mut state2);
526            prop_assert_ne!(state1, state2);
527        }
528
529        /// `hash_no_pad` is deterministic over arbitrary input vectors.
530        #[rstest]
531        fn prop_hash_no_pad_deterministic(
532            input in proptest::collection::vec(arb_fp(), 0..32),
533        ) {
534            prop_assert_eq!(hash_no_pad(&input), hash_no_pad(&input));
535        }
536
537        /// `hash_two_to_one(a, b) == hash_no_pad(a || b)`.
538        #[rstest]
539        fn prop_hash_two_to_one_equals_concat(
540            a in any::<[u64; HASH_OUT]>(),
541            b in any::<[u64; HASH_OUT]>(),
542        ) {
543            let a_fp: [Fp; HASH_OUT] = core::array::from_fn(|i| Fp::from_u64_reduce(a[i]));
544            let b_fp: [Fp; HASH_OUT] = core::array::from_fn(|i| Fp::from_u64_reduce(b[i]));
545            let concat = [
546                a_fp[0], a_fp[1], a_fp[2], a_fp[3],
547                b_fp[0], b_fp[1], b_fp[2], b_fp[3],
548            ];
549            prop_assert_eq!(hash_two_to_one(a_fp, b_fp), hash_no_pad(&concat));
550        }
551
552        /// `hash_n_to_one` is the left fold of `hash_two_to_one` for any
553        /// non-empty input list.
554        #[rstest]
555        fn prop_hash_n_to_one_left_fold(
556            inputs in proptest::collection::vec(any::<[u64; HASH_OUT]>(), 1..6),
557        ) {
558            let inputs_fp: Vec<[Fp; HASH_OUT]> = inputs
559                .iter()
560                .map(|raw| core::array::from_fn(|j| Fp::from_u64_reduce(raw[j])))
561                .collect();
562            let mut expected = inputs_fp[0];
563            for next in &inputs_fp[1..] {
564                expected = hash_two_to_one(expected, *next);
565            }
566            prop_assert_eq!(hash_n_to_one(&inputs_fp), expected);
567        }
568
569        /// `hash_to_quintic_extension(input)` packs into Fp5 deterministically.
570        #[rstest]
571        fn prop_hash_to_quintic_extension_deterministic(
572            input in proptest::collection::vec(arb_fp(), 0..32),
573        ) {
574            prop_assert_eq!(
575                hash_to_quintic_extension(&input),
576                hash_to_quintic_extension(&input),
577            );
578        }
579
580        /// `hash_two_to_quintic` matches the explicit 10-element preimage
581        /// hash through `hash_to_quintic_extension`.
582        #[rstest]
583        fn prop_hash_two_to_quintic_matches_concat(
584            a in any::<[u64; 5]>(),
585            b in any::<[u64; 5]>(),
586        ) {
587            let a_fp5 = Fp5::from_u64s_reduce(a);
588            let b_fp5 = Fp5::from_u64s_reduce(b);
589            let mut concat = [Fp::ZERO; 10];
590            concat[..5].copy_from_slice(&a_fp5.0);
591            concat[5..].copy_from_slice(&b_fp5.0);
592            prop_assert_eq!(
593                hash_two_to_quintic(a_fp5, b_fp5),
594                hash_to_quintic_extension(&concat),
595            );
596        }
597    }
598}
nautilus_lighter/signing/hash/poseidon2.rs

nautilus_lighter/signing/hash/
poseidon2.rs
