ark_sponge/
lib.rs

1#![cfg_attr(not(feature = "std"), no_std)]
2//! A crate for the cryptographic sponge trait.
3#![deny(
4    const_err,
5    future_incompatible,
6    missing_docs,
7    non_shorthand_field_patterns,
8    renamed_and_removed_lints,
9    rust_2018_idioms,
10    stable_features,
11    trivial_casts,
12    trivial_numeric_casts,
13    unused,
14    variant_size_differences,
15    warnings
16)]
17#![forbid(unsafe_code)]
18
19use ark_ff::{FpParameters, PrimeField};
20use ark_std::vec;
21use ark_std::vec::Vec;
22
23/// Infrastructure for the constraints counterparts.
24#[cfg(feature = "r1cs")]
25pub mod constraints;
26
27mod absorb;
28pub use absorb::*;
29
30/// The sponge for Poseidon
31///
32/// This implementation of Poseidon is entirely from Fractal's implementation in [COS20][cos]
33/// with small syntax changes.
34///
35/// [cos]: https://eprint.iacr.org/2019/1076
36pub mod poseidon;
37
38/// An enum for specifying the output field element size.
39#[derive(Clone, Copy, Eq, PartialEq)]
40pub enum FieldElementSize {
41    /// Sample field elements from the entire field.
42    Full,
43
44    /// Sample field elements from a subset of the field, specified by the maximum number of bits.
45    Truncated(usize),
46}
47
48impl FieldElementSize {
49    pub(crate) fn num_bits<F: PrimeField>(&self) -> usize {
50        if let FieldElementSize::Truncated(num_bits) = self {
51            if *num_bits > (F::Params::MODULUS_BITS as usize) {
52                panic!("num_bits is greater than the capacity of the field.")
53            }
54        };
55        F::Params::CAPACITY as usize
56    }
57
58    /// Calculate the sum of field element sizes in `elements`.
59    pub fn sum<F: PrimeField>(elements: &[Self]) -> usize {
60        elements.iter().map(|item| item.num_bits::<F>()).sum()
61    }
62}
63
64/// Default implementation of `CryptographicSponge::squeeze_field_elements_with_sizes`
65pub(crate) fn squeeze_field_elements_with_sizes_default_impl<F: PrimeField>(
66    sponge: &mut impl CryptographicSponge,
67    sizes: &[FieldElementSize],
68) -> Vec<F> {
69    if sizes.len() == 0 {
70        return Vec::new();
71    }
72
73    let mut total_bits = 0usize;
74    for size in sizes {
75        total_bits += size.num_bits::<F>();
76    }
77
78    let bits = sponge.squeeze_bits(total_bits);
79    let mut bits_window = bits.as_slice();
80
81    let mut output = Vec::with_capacity(sizes.len());
82    for size in sizes {
83        let num_bits = size.num_bits::<F>();
84        let nonnative_bits_le: Vec<bool> = bits_window[..num_bits].to_vec();
85        bits_window = &bits_window[num_bits..];
86
87        let nonnative_bytes = nonnative_bits_le
88            .chunks(8)
89            .map(|bits| {
90                let mut byte = 0u8;
91                for (i, &bit) in bits.into_iter().enumerate() {
92                    if bit {
93                        byte += 1 << i;
94                    }
95                }
96                byte
97            })
98            .collect::<Vec<_>>();
99
100        output.push(F::from_le_bytes_mod_order(nonnative_bytes.as_slice()));
101    }
102
103    output
104}
105
106/// The interface for a cryptographic sponge.
107/// A sponge can `absorb` or take in inputs and later `squeeze` or output bytes or field elements.
108/// The outputs are dependent on previous `absorb` and `squeeze` calls.
109pub trait CryptographicSponge: Clone {
110    /// Parameters used by the sponge.
111    type Parameters;
112
113    /// Initialize a new instance of the sponge.
114    fn new(params: &Self::Parameters) -> Self;
115
116    /// Absorb an input into the sponge.
117    fn absorb(&mut self, input: &impl Absorb);
118
119    /// Squeeze `num_bytes` bytes from the sponge.
120    fn squeeze_bytes(&mut self, num_bytes: usize) -> Vec<u8>;
121
122    /// Squeeze `num_bits` bits from the sponge.
123    fn squeeze_bits(&mut self, num_bits: usize) -> Vec<bool>;
124
125    /// Squeeze `sizes.len()` field elements from the sponge, where the `i`-th element of
126    /// the output has size `sizes[i]`.
127    ///
128    /// If the implementation is field-based, to squeeze native field elements,
129    /// call `self.squeeze_native_field_elements` instead.
130    ///
131    /// TODO: Support general Field.
132    ///
133    /// Note that when `FieldElementSize` is `FULL`, the output is not strictly uniform. Output
134    /// space is uniform in \[0, 2^{F::MODULUS_BITS - 1}\]
135    fn squeeze_field_elements_with_sizes<F: PrimeField>(
136        &mut self,
137        sizes: &[FieldElementSize],
138    ) -> Vec<F> {
139        squeeze_field_elements_with_sizes_default_impl(self, sizes)
140    }
141
142    /// Squeeze `num_elements` nonnative field elements from the sponge.
143    ///
144    /// Because of rust limitation, for field-based implementation, using this method to squeeze
145    /// native field elements will have runtime casting cost. For better efficiency, use `squeeze_native_field_elements`.
146    fn squeeze_field_elements<F: PrimeField>(&mut self, num_elements: usize) -> Vec<F> {
147        self.squeeze_field_elements_with_sizes::<F>(
148            vec![FieldElementSize::Full; num_elements].as_slice(),
149        )
150    }
151
152    /// Creates a new sponge with applied domain separation.
153    fn fork(&self, domain: &[u8]) -> Self {
154        let mut new_sponge = self.clone();
155
156        let mut input = Absorb::to_sponge_bytes_as_vec(&domain.len());
157        input.extend_from_slice(domain);
158        new_sponge.absorb(&input);
159
160        new_sponge
161    }
162}
163
164/// The interface for field-based cryptographic sponge.
165/// `CF` is the native field used by the cryptographic sponge implementation.
166pub trait FieldBasedCryptographicSponge<CF: PrimeField>: CryptographicSponge {
167    /// Squeeze `num_elements` field elements from the sponge.
168    fn squeeze_native_field_elements(&mut self, num_elements: usize) -> Vec<CF>;
169
170    /// Squeeze `sizes.len()` field elements from the sponge, where the `i`-th element of
171    /// the output has size `sizes[i]`.
172    fn squeeze_native_field_elements_with_sizes(&mut self, sizes: &[FieldElementSize]) -> Vec<CF> {
173        let mut all_full_sizes = true;
174        for size in sizes {
175            if *size != FieldElementSize::Full {
176                all_full_sizes = false;
177                break;
178            }
179        }
180
181        if all_full_sizes {
182            self.squeeze_native_field_elements(sizes.len())
183        } else {
184            squeeze_field_elements_with_sizes_default_impl(self, sizes)
185        }
186    }
187}
188
189/// An extension for the interface of a cryptographic sponge.
190/// In addition to operations defined in `CryptographicSponge`, `SpongeExt` can convert itself to
191/// a state, and instantiate itself from state.
192pub trait SpongeExt: CryptographicSponge {
193    /// The full state of the cryptographic sponge.
194    type State: Clone;
195    /// Returns a sponge that uses `state`.
196    fn from_state(state: Self::State, params: &Self::Parameters) -> Self;
197    /// Consumes `self` and returns the state.
198    fn into_state(self) -> Self::State;
199}
ark_sponge/lib.rs

ark_sponge/
lib.rs
