p3_symmetric/
sponge.rs

1use alloc::string::String;
2use core::marker::PhantomData;
3
4use itertools::Itertools;
5use p3_field::{Field, PrimeField, PrimeField32, reduce_32};
6
7use crate::hasher::CryptographicHasher;
8use crate::permutation::CryptographicPermutation;
9
10/// A padding-free, overwrite-mode sponge function.
11///
12/// `WIDTH` is the sponge's rate plus the sponge's capacity.
13#[derive(Copy, Clone, Debug)]
14pub struct PaddingFreeSponge<P, const WIDTH: usize, const RATE: usize, const OUT: usize> {
15    permutation: P,
16}
17
18impl<P, const WIDTH: usize, const RATE: usize, const OUT: usize>
19    PaddingFreeSponge<P, WIDTH, RATE, OUT>
20{
21    pub const fn new(permutation: P) -> Self {
22        Self { permutation }
23    }
24}
25
26impl<T, P, const WIDTH: usize, const RATE: usize, const OUT: usize> CryptographicHasher<T, [T; OUT]>
27    for PaddingFreeSponge<P, WIDTH, RATE, OUT>
28where
29    T: Default + Copy,
30    P: CryptographicPermutation<[T; WIDTH]>,
31{
32    fn hash_iter<I>(&self, input: I) -> [T; OUT]
33    where
34        I: IntoIterator<Item = T>,
35    {
36        // static_assert(RATE < WIDTH)
37        let mut state = [T::default(); WIDTH];
38        let mut input = input.into_iter();
39
40        // Itertools' chunks() is more convenient, but seems to add more overhead,
41        // hence the more manual loop.
42        'outer: loop {
43            for i in 0..RATE {
44                if let Some(x) = input.next() {
45                    state[i] = x;
46                } else {
47                    if i != 0 {
48                        self.permutation.permute_mut(&mut state);
49                    }
50                    break 'outer;
51                }
52            }
53            self.permutation.permute_mut(&mut state);
54        }
55
56        state[..OUT].try_into().unwrap()
57    }
58}
59
60/// A padding-free, overwrite-mode sponge function that operates natively over PF but accepts elements
61/// of F: PrimeField32.
62///
63/// `WIDTH` is the sponge's rate plus the sponge's capacity.
64#[derive(Clone, Debug)]
65pub struct MultiField32PaddingFreeSponge<
66    F,
67    PF,
68    P,
69    const WIDTH: usize,
70    const RATE: usize,
71    const OUT: usize,
72> {
73    permutation: P,
74    num_f_elms: usize,
75    _phantom: PhantomData<(F, PF)>,
76}
77
78impl<F, PF, P, const WIDTH: usize, const RATE: usize, const OUT: usize>
79    MultiField32PaddingFreeSponge<F, PF, P, WIDTH, RATE, OUT>
80where
81    F: PrimeField32,
82    PF: Field,
83{
84    pub fn new(permutation: P) -> Result<Self, String> {
85        if F::order() >= PF::order() {
86            return Err(String::from("F::order() must be less than PF::order()"));
87        }
88
89        let num_f_elms = PF::bits() / F::bits();
90        Ok(Self {
91            permutation,
92            num_f_elms,
93            _phantom: PhantomData,
94        })
95    }
96}
97
98impl<F, PF, P, const WIDTH: usize, const RATE: usize, const OUT: usize>
99    CryptographicHasher<F, [PF; OUT]> for MultiField32PaddingFreeSponge<F, PF, P, WIDTH, RATE, OUT>
100where
101    F: PrimeField32,
102    PF: PrimeField + Default + Copy,
103    P: CryptographicPermutation<[PF; WIDTH]>,
104{
105    fn hash_iter<I>(&self, input: I) -> [PF; OUT]
106    where
107        I: IntoIterator<Item = F>,
108    {
109        let mut state = [PF::default(); WIDTH];
110        for block_chunk in &input.into_iter().chunks(RATE) {
111            for (chunk_id, chunk) in (&block_chunk.chunks(self.num_f_elms))
112                .into_iter()
113                .enumerate()
114            {
115                state[chunk_id] = reduce_32(&chunk.collect_vec());
116            }
117            state = self.permutation.permute(state);
118        }
119
120        state[..OUT].try_into().unwrap()
121    }
122}
123
124#[cfg(test)]
125mod tests {
126    use super::*;
127    use crate::Permutation;
128
129    #[derive(Clone)]
130    struct MockPermutation;
131
132    impl<T, const WIDTH: usize> Permutation<[T; WIDTH]> for MockPermutation
133    where
134        T: Copy + core::ops::Add<Output = T> + Default,
135    {
136        fn permute_mut(&self, input: &mut [T; WIDTH]) {
137            let sum: T = input.iter().copied().fold(T::default(), |acc, x| acc + x);
138            // Set every element to the sum
139            *input = [sum; WIDTH];
140        }
141    }
142
143    impl<T, const WIDTH: usize> CryptographicPermutation<[T; WIDTH]> for MockPermutation where
144        T: Copy + core::ops::Add<Output = T> + Default
145    {
146    }
147
148    #[test]
149    fn test_padding_free_sponge_basic() {
150        const WIDTH: usize = 4;
151        const RATE: usize = 2;
152        const OUT: usize = 2;
153
154        let permutation = MockPermutation;
155        let sponge = PaddingFreeSponge::<MockPermutation, WIDTH, RATE, OUT>::new(permutation);
156
157        let input = [1, 2, 3, 4, 5];
158        let output = sponge.hash_iter(input);
159
160        // Explanation of why the final state results in [44, 44, 44, 44]:
161        // Initial state: [0, 0, 0, 0]
162        // First input chunk [1, 2] overwrites first two positions: [1, 2, 0, 0]
163        // Apply permutation (sum all elements and overwrite): [3, 3, 3, 3]
164        // Second input chunk [3, 4] overwrites first two positions: [3, 4, 3, 3]
165        // Apply permutation: [13, 13, 13, 13] (3 + 4 + 3 + 3 = 13)
166        // Third input chunk [5] overwrites first position: [5, 13, 13, 13]
167        // Apply permutation: [44, 44, 44, 44] (5 + 13 + 13 + 13 = 44)
168
169        assert_eq!(output, [44; OUT]);
170    }
171
172    #[test]
173    fn test_padding_free_sponge_empty_input() {
174        const WIDTH: usize = 4;
175        const RATE: usize = 2;
176        const OUT: usize = 2;
177
178        let permutation = MockPermutation;
179        let sponge = PaddingFreeSponge::<MockPermutation, WIDTH, RATE, OUT>::new(permutation);
180
181        let input: [u64; 0] = [];
182        let output = sponge.hash_iter(input);
183
184        assert_eq!(
185            output, [0; OUT],
186            "Should return default values when input is empty."
187        );
188    }
189
190    #[test]
191    fn test_padding_free_sponge_exact_block_size() {
192        const WIDTH: usize = 6;
193        const RATE: usize = 3;
194        const OUT: usize = 2;
195
196        let permutation = MockPermutation;
197        let sponge = PaddingFreeSponge::<MockPermutation, WIDTH, RATE, OUT>::new(permutation);
198
199        let input = [10, 20, 30];
200        let output = sponge.hash_iter(input);
201
202        let expected_sum = 10 + 20 + 30;
203        assert_eq!(output, [expected_sum; OUT]);
204    }
205}
p3_symmetric/sponge.rs

p3_symmetric/
sponge.rs
