snarkvm_algorithms/traits/
algebraic_sponge.rs

1// Copyright 2024 Aleo Network Foundation
2// This file is part of the snarkVM library.
3
4// Licensed under the Apache License, Version 2.0 (the "License");
5// you may not use this file except in compliance with the License.
6// You may obtain a copy of the License at:
7
8// http://www.apache.org/licenses/LICENSE-2.0
9
10// Unless required by applicable law or agreed to in writing, software
11// distributed under the License is distributed on an "AS IS" BASIS,
12// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13// See the License for the specific language governing permissions and
14// limitations under the License.
15
16use smallvec::SmallVec;
17use snarkvm_fields::{PrimeField, ToConstraintField};
18use snarkvm_utilities::FromBits;
19
20use core::fmt::Debug;
21
22/// The interface for a cryptographic sponge.
23/// A sponge can `absorb` or take in inputs and later `squeeze` or output bytes
24/// or field elements. The outputs are dependent on previous `absorb` and
25/// `squeeze` calls.
26pub trait AlgebraicSponge<F: PrimeField, const RATE: usize>: Clone + Debug {
27    /// Parameters used by the sponge.
28    type Parameters;
29
30    fn sample_parameters() -> Self::Parameters;
31
32    /// Initialize a new instance of the sponge.
33    fn new_with_parameters(params: &Self::Parameters) -> Self;
34
35    /// Initialize a new instance of the sponge.
36    fn new() -> Self {
37        let parameters = Self::sample_parameters();
38        Self::new_with_parameters(&parameters)
39    }
40
41    /// Takes in field elements.
42    fn absorb_native_field_elements<T: ToConstraintField<F>>(&mut self, elements: &[T]);
43
44    /// Takes in field elements.
45    fn absorb_nonnative_field_elements<Target: PrimeField>(&mut self, elements: impl IntoIterator<Item = Target>);
46
47    /// Takes in bytes.
48    fn absorb_bytes(&mut self, elements: &[u8]) {
49        let capacity = F::size_in_bits() - 1;
50        let mut bits = Vec::<bool>::with_capacity(elements.len() * 8);
51        for elem in elements {
52            bits.extend_from_slice(&[
53                elem & 128 != 0,
54                elem & 64 != 0,
55                elem & 32 != 0,
56                elem & 16 != 0,
57                elem & 8 != 0,
58                elem & 4 != 0,
59                elem & 2 != 0,
60                elem & 1 != 0,
61            ]);
62        }
63        let elements = bits
64            .chunks(capacity)
65            .map(|bits| F::from_bigint(F::BigInteger::from_bits_be(bits).unwrap()).unwrap())
66            .collect::<SmallVec<[F; 10]>>();
67
68        self.absorb_native_field_elements(&elements);
69    }
70
71    /// Takes in field elements.
72    fn squeeze_native_field_elements(&mut self, num: usize) -> SmallVec<[F; 10]>;
73
74    /// Takes out field elements.
75    fn squeeze_nonnative_field_elements<Target: PrimeField>(&mut self, num: usize) -> SmallVec<[Target; 10]>;
76
77    /// Takes out field elements of 168 bits.
78    fn squeeze_short_nonnative_field_elements<Target: PrimeField>(&mut self, num: usize) -> SmallVec<[Target; 10]>;
79
80    /// Takes out a field element of 168 bits.
81    fn squeeze_short_nonnative_field_element<Target: PrimeField>(&mut self) -> Target {
82        self.squeeze_short_nonnative_field_elements(1)[0]
83    }
84}
85
86/// The mode structure for duplex sponges
87#[derive(PartialEq, Eq, Clone, Debug)]
88pub enum DuplexSpongeMode {
89    /// The sponge is currently absorbing data.
90    Absorbing {
91        /// next position of the state to be XOR-ed when absorbing.
92        next_absorb_index: usize,
93    },
94    /// The sponge is currently squeezing data out.
95    Squeezing {
96        /// next position of the state to be outputted when squeezing.
97        next_squeeze_index: usize,
98    },
99}
100
101pub(crate) mod nonnative_params {
102    /// A macro for computing ceil(log2(x))+1 for a field element x. The
103    /// num_bits param is expected to be a vector to which the BE bits can
104    /// be written; it is not created here, as reusing it allows us to avoid
105    /// a lot of allocations.
106    #[macro_export]
107    macro_rules! overhead {
108        ($x:expr, $num_bits:expr) => {{
109            use snarkvm_utilities::ToBits;
110            let num = $x;
111            let num_bits = $num_bits;
112            num.to_bigint().write_bits_be(num_bits);
113            let mut skipped_bits = 0;
114            for b in num_bits.iter() {
115                if *b == false {
116                    skipped_bits += 1;
117                } else {
118                    break;
119                }
120            }
121
122            let mut is_power_of_2 = true;
123            for b in num_bits.iter().skip(skipped_bits + 1) {
124                if *b == true {
125                    is_power_of_2 = false;
126                }
127            }
128
129            let result = if is_power_of_2 { num_bits.len() - skipped_bits } else { num_bits.len() - skipped_bits + 1 };
130
131            // Clear the reusable vector for bits.
132            num_bits.clear();
133
134            result
135        }};
136    }
137
138    /// Parameters for a specific `NonNativeFieldVar` instantiation
139    #[derive(Clone, Debug)]
140    pub struct NonNativeFieldParams {
141        /// The number of limbs (`BaseField` elements) used to represent a
142        /// `TargetField` element. Highest limb first.
143        pub num_limbs: usize,
144
145        /// The number of bits of the limb
146        pub bits_per_limb: usize,
147    }
148
149    /// Obtain the parameters from a `ConstraintSystem`'s cache or generate a
150    /// new one
151    #[must_use]
152    pub const fn get_params(
153        target_field_size: usize,
154        base_field_size: usize,
155        optimization_type: OptimizationType,
156    ) -> NonNativeFieldParams {
157        let (num_of_limbs, limb_size) = find_parameters(base_field_size, target_field_size, optimization_type);
158        NonNativeFieldParams { num_limbs: num_of_limbs, bits_per_limb: limb_size }
159    }
160
161    #[derive(Clone, Copy, Debug, PartialEq, Eq)]
162    /// The type of optimization target for the parameters searching
163    pub enum OptimizationType {
164        /// Optimized for constraints
165        Constraints,
166        /// Optimized for weight
167        Weight,
168    }
169
170    /// A function to search for parameters for nonnative field gadgets
171    pub const fn find_parameters(
172        base_field_prime_length: usize,
173        target_field_prime_bit_length: usize,
174        optimization_type: OptimizationType,
175    ) -> (usize, usize) {
176        let mut found = false;
177        let mut min_cost = 0usize;
178        let mut min_cost_limb_size = 0usize;
179        let mut min_cost_num_of_limbs = 0usize;
180
181        let surfeit = 10;
182        let mut max_limb_size = (base_field_prime_length - 1 - surfeit - 1) / 2 - 1;
183        if max_limb_size > target_field_prime_bit_length {
184            max_limb_size = target_field_prime_bit_length;
185        }
186        let mut limb_size = 1;
187
188        while limb_size <= max_limb_size {
189            let num_of_limbs = target_field_prime_bit_length.div_ceil(limb_size);
190
191            let group_size = (base_field_prime_length - 1 - surfeit - 1 - 1 - limb_size).div_ceil(limb_size);
192            let num_of_groups = (2 * num_of_limbs - 1).div_ceil(group_size);
193
194            let mut this_cost = 0;
195
196            match optimization_type {
197                OptimizationType::Constraints => {
198                    this_cost += 2 * num_of_limbs - 1;
199                }
200                OptimizationType::Weight => {
201                    this_cost += 6 * num_of_limbs * num_of_limbs;
202                }
203            };
204
205            match optimization_type {
206                OptimizationType::Constraints => {
207                    this_cost += target_field_prime_bit_length; // allocation of k
208                    this_cost += target_field_prime_bit_length + num_of_limbs; // allocation of r
209                    //this_cost += 2 * num_of_limbs - 1; // compute kp
210                    this_cost += num_of_groups + (num_of_groups - 1) * (limb_size * 2 + surfeit) + 1;
211                    // equality check
212                }
213                OptimizationType::Weight => {
214                    this_cost += target_field_prime_bit_length * 3 + target_field_prime_bit_length; // allocation of k
215                    this_cost += target_field_prime_bit_length * 3 + target_field_prime_bit_length + num_of_limbs; // allocation of r
216                    this_cost += num_of_limbs * num_of_limbs + 2 * (2 * num_of_limbs - 1); // compute kp
217                    this_cost += num_of_limbs
218                        + num_of_groups
219                        + 6 * num_of_groups
220                        + (num_of_groups - 1) * (2 * limb_size + surfeit) * 4
221                        + 2; // equality check
222                }
223            };
224
225            if !found || this_cost < min_cost {
226                found = true;
227                min_cost = this_cost;
228                min_cost_limb_size = limb_size;
229                min_cost_num_of_limbs = num_of_limbs;
230            }
231
232            limb_size += 1;
233        }
234
235        (min_cost_num_of_limbs, min_cost_limb_size)
236    }
237}
snarkvm_algorithms/traits/algebraic_sponge.rs

snarkvm_algorithms/traits/
algebraic_sponge.rs
