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

snarkvm_algorithms/traits/
algebraic_sponge.rs
