miden-crypto/src/hash/rescue/rpo/mod.rs
src/hash/rescue/rpo/mod.rsRaw
1use core::ops::Range;
2
3use super::{
4 add_constants, add_constants_and_apply_inv_sbox, add_constants_and_apply_sbox, apply_inv_sbox,
5 apply_mds, apply_sbox, Digest, ElementHasher, Felt, FieldElement, Hasher, StarkField, ARK1,
6 ARK2, BINARY_CHUNK_SIZE, CAPACITY_RANGE, DIGEST_BYTES, DIGEST_RANGE, DIGEST_SIZE, INPUT1_RANGE,
7 INPUT2_RANGE, MDS, NUM_ROUNDS, RATE_RANGE, RATE_WIDTH, STATE_WIDTH, ZERO,
8};
9
10mod digest;
11pub use digest::{RpoDigest, RpoDigestError};
12
13#[cfg(test)]
14mod tests;
15
16// HASHER IMPLEMENTATION
17// ================================================================================================
18
19/// Implementation of the Rescue Prime Optimized hash function with 256-bit output.
20///
21/// The hash function is implemented according to the Rescue Prime Optimized
22/// [specifications](https://eprint.iacr.org/2022/1577) while the padding rule follows the one
23/// described [here](https://eprint.iacr.org/2023/1045).
24///
25/// The parameters used to instantiate the function are:
26/// * Field: 64-bit prime field with modulus p = 2^64 - 2^32 + 1.
27/// * State width: 12 field elements.
28/// * Rate size: r = 8 field elements.
29/// * Capacity size: c = 4 field elements.
30/// * Number of founds: 7.
31/// * S-Box degree: 7.
32///
33/// The above parameters target a 128-bit security level. The digest consists of four field elements
34/// and it can be serialized into 32 bytes (256 bits).
35///
36/// ## Hash output consistency
37/// Functions [hash_elements()](Rpo256::hash_elements), [merge()](Rpo256::merge), and
38/// [merge_with_int()](Rpo256::merge_with_int) are internally consistent. That is, computing
39/// a hash for the same set of elements using these functions will always produce the same
40/// result. For example, merging two digests using [merge()](Rpo256::merge) will produce the
41/// same result as hashing 8 elements which make up these digests using
42/// [hash_elements()](Rpo256::hash_elements) function.
43///
44/// However, [hash()](Rpo256::hash) function is not consistent with functions mentioned above.
45/// For example, if we take two field elements, serialize them to bytes and hash them using
46/// [hash()](Rpo256::hash), the result will differ from the result obtained by hashing these
47/// elements directly using [hash_elements()](Rpo256::hash_elements) function. The reason for
48/// this difference is that [hash()](Rpo256::hash) function needs to be able to handle
49/// arbitrary binary strings, which may or may not encode valid field elements - and thus,
50/// deserialization procedure used by this function is different from the procedure used to
51/// deserialize valid field elements.
52///
53/// Thus, if the underlying data consists of valid field elements, it might make more sense
54/// to deserialize them into field elements and then hash them using
55/// [hash_elements()](Rpo256::hash_elements) function rather than hashing the serialized bytes
56/// using [hash()](Rpo256::hash) function.
57///
58/// ## Domain separation
59/// [merge_in_domain()](Rpo256::merge_in_domain) hashes two digests into one digest with some domain
60/// identifier and the current implementation sets the second capacity element to the value of
61/// this domain identifier. Using a similar argument to the one formulated for domain separation of
62/// the RPX hash function in Appendix C of its [specification](https://eprint.iacr.org/2023/1045),
63/// one sees that doing so degrades only pre-image resistance, from its initial bound of c.log_2(p),
64/// by as much as the log_2 of the size of the domain identifier space. Since pre-image resistance
65/// becomes the bottleneck for the security bound of the sponge in overwrite-mode only when it is
66/// lower than 2^128, we see that the target 128-bit security level is maintained as long as
67/// the size of the domain identifier space, including for padding, is less than 2^128.
68///
69/// ## Hashing of empty input
70/// The current implementation hashes empty input to the zero digest [0, 0, 0, 0]. This has
71/// the benefit of requiring no calls to the RPO permutation when hashing empty input.
72#[derive(Debug, Copy, Clone, Eq, PartialEq)]
73pub struct Rpo256();
74
75impl Hasher for Rpo256 {
76 /// Rpo256 collision resistance is 128-bits.
77 const COLLISION_RESISTANCE: u32 = 128;
78
79 type Digest = RpoDigest;
80
81 fn hash(bytes: &[u8]) -> Self::Digest {
82 // initialize the state with zeroes
83 let mut state = [ZERO; STATE_WIDTH];
84
85 // determine the number of field elements needed to encode `bytes` when each field element
86 // represents at most 7 bytes.
87 let num_field_elem = bytes.len().div_ceil(BINARY_CHUNK_SIZE);
88
89 // set the first capacity element to `RATE_WIDTH + (num_field_elem % RATE_WIDTH)`. We do
90 // this to achieve:
91 // 1. Domain separating hashing of `[u8]` from hashing of `[Felt]`.
92 // 2. Avoiding collisions at the `[Felt]` representation of the encoded bytes.
93 state[CAPACITY_RANGE.start] =
94 Felt::from((RATE_WIDTH + (num_field_elem % RATE_WIDTH)) as u8);
95
96 // initialize a buffer to receive the little-endian elements.
97 let mut buf = [0_u8; 8];
98
99 // iterate the chunks of bytes, creating a field element from each chunk and copying it
100 // into the state.
101 //
102 // every time the rate range is filled, a permutation is performed. if the final value of
103 // `rate_pos` is not zero, then the chunks count wasn't enough to fill the state range,
104 // and an additional permutation must be performed.
105 let mut current_chunk_idx = 0_usize;
106 // handle the case of an empty `bytes`
107 let last_chunk_idx = if num_field_elem == 0 {
108 current_chunk_idx
109 } else {
110 num_field_elem - 1
111 };
112 let rate_pos = bytes.chunks(BINARY_CHUNK_SIZE).fold(0, |rate_pos, chunk| {
113 // copy the chunk into the buffer
114 if current_chunk_idx != last_chunk_idx {
115 buf[..BINARY_CHUNK_SIZE].copy_from_slice(chunk);
116 } else {
117 // on the last iteration, we pad `buf` with a 1 followed by as many 0's as are
118 // needed to fill it
119 buf.fill(0);
120 buf[..chunk.len()].copy_from_slice(chunk);
121 buf[chunk.len()] = 1;
122 }
123 current_chunk_idx += 1;
124
125 // set the current rate element to the input. since we take at most 7 bytes, we are
126 // guaranteed that the inputs data will fit into a single field element.
127 state[RATE_RANGE.start + rate_pos] = Felt::new(u64::from_le_bytes(buf));
128
129 // proceed filling the range. if it's full, then we apply a permutation and reset the
130 // counter to the beginning of the range.
131 if rate_pos == RATE_WIDTH - 1 {
132 Self::apply_permutation(&mut state);
133 0
134 } else {
135 rate_pos + 1
136 }
137 });
138
139 // if we absorbed some elements but didn't apply a permutation to them (would happen when
140 // the number of elements is not a multiple of RATE_WIDTH), apply the RPO permutation. we
141 // don't need to apply any extra padding because the first capacity element contains a
142 // flag indicating the number of field elements constituting the last block when the latter
143 // is not divisible by `RATE_WIDTH`.
144 if rate_pos != 0 {
145 state[RATE_RANGE.start + rate_pos..RATE_RANGE.end].fill(ZERO);
146 Self::apply_permutation(&mut state);
147 }
148
149 // return the first 4 elements of the rate as hash result.
150 RpoDigest::new(state[DIGEST_RANGE].try_into().unwrap())
151 }
152
153 fn merge(values: &[Self::Digest; 2]) -> Self::Digest {
154 // initialize the state by copying the digest elements into the rate portion of the state
155 // (8 total elements), and set the capacity elements to 0.
156 let mut state = [ZERO; STATE_WIDTH];
157 let it = Self::Digest::digests_as_elements_iter(values.iter());
158 for (i, v) in it.enumerate() {
159 state[RATE_RANGE.start + i] = *v;
160 }
161
162 // apply the RPO permutation and return the first four elements of the state
163 Self::apply_permutation(&mut state);
164 RpoDigest::new(state[DIGEST_RANGE].try_into().unwrap())
165 }
166
167 fn merge_many(values: &[Self::Digest]) -> Self::Digest {
168 Self::hash_elements(Self::Digest::digests_as_elements(values))
169 }
170
171 fn merge_with_int(seed: Self::Digest, value: u64) -> Self::Digest {
172 // initialize the state as follows:
173 // - seed is copied into the first 4 elements of the rate portion of the state.
174 // - if the value fits into a single field element, copy it into the fifth rate element and
175 // set the first capacity element to 5.
176 // - if the value doesn't fit into a single field element, split it into two field elements,
177 // copy them into rate elements 5 and 6 and set the first capacity element to 6.
178 let mut state = [ZERO; STATE_WIDTH];
179 state[INPUT1_RANGE].copy_from_slice(seed.as_elements());
180 state[INPUT2_RANGE.start] = Felt::new(value);
181 if value < Felt::MODULUS {
182 state[CAPACITY_RANGE.start] = Felt::from(5_u8);
183 } else {
184 state[INPUT2_RANGE.start + 1] = Felt::new(value / Felt::MODULUS);
185 state[CAPACITY_RANGE.start] = Felt::from(6_u8);
186 }
187
188 // apply the RPO permutation and return the first four elements of the rate
189 Self::apply_permutation(&mut state);
190 RpoDigest::new(state[DIGEST_RANGE].try_into().unwrap())
191 }
192}
193
194impl ElementHasher for Rpo256 {
195 type BaseField = Felt;
196
197 fn hash_elements<E: FieldElement<BaseField = Self::BaseField>>(elements: &[E]) -> Self::Digest {
198 // convert the elements into a list of base field elements
199 let elements = E::slice_as_base_elements(elements);
200
201 // initialize state to all zeros, except for the first element of the capacity part, which
202 // is set to `elements.len() % RATE_WIDTH`.
203 let mut state = [ZERO; STATE_WIDTH];
204 state[CAPACITY_RANGE.start] = Self::BaseField::from((elements.len() % RATE_WIDTH) as u8);
205
206 // absorb elements into the state one by one until the rate portion of the state is filled
207 // up; then apply the Rescue permutation and start absorbing again; repeat until all
208 // elements have been absorbed
209 let mut i = 0;
210 for &element in elements.iter() {
211 state[RATE_RANGE.start + i] = element;
212 i += 1;
213 if i % RATE_WIDTH == 0 {
214 Self::apply_permutation(&mut state);
215 i = 0;
216 }
217 }
218
219 // if we absorbed some elements but didn't apply a permutation to them (would happen when
220 // the number of elements is not a multiple of RATE_WIDTH), apply the RPO permutation after
221 // padding by as many 0 as necessary to make the input length a multiple of the RATE_WIDTH.
222 if i > 0 {
223 while i != RATE_WIDTH {
224 state[RATE_RANGE.start + i] = ZERO;
225 i += 1;
226 }
227 Self::apply_permutation(&mut state);
228 }
229
230 // return the first 4 elements of the state as hash result
231 RpoDigest::new(state[DIGEST_RANGE].try_into().unwrap())
232 }
233}
234
235// HASH FUNCTION IMPLEMENTATION
236// ================================================================================================
237
238impl Rpo256 {
239 // CONSTANTS
240 // --------------------------------------------------------------------------------------------
241
242 /// The number of rounds is set to 7 to target 128-bit security level.
243 pub const NUM_ROUNDS: usize = NUM_ROUNDS;
244
245 /// Sponge state is set to 12 field elements or 768 bytes; 8 elements are reserved for rate and
246 /// the remaining 4 elements are reserved for capacity.
247 pub const STATE_WIDTH: usize = STATE_WIDTH;
248
249 /// The rate portion of the state is located in elements 4 through 11 (inclusive).
250 pub const RATE_RANGE: Range<usize> = RATE_RANGE;
251
252 /// The capacity portion of the state is located in elements 0, 1, 2, and 3.
253 pub const CAPACITY_RANGE: Range<usize> = CAPACITY_RANGE;
254
255 /// The output of the hash function can be read from state elements 4, 5, 6, and 7.
256 pub const DIGEST_RANGE: Range<usize> = DIGEST_RANGE;
257
258 /// MDS matrix used for computing the linear layer in a RPO round.
259 pub const MDS: [[Felt; STATE_WIDTH]; STATE_WIDTH] = MDS;
260
261 /// Round constants added to the hasher state in the first half of the RPO round.
262 pub const ARK1: [[Felt; STATE_WIDTH]; NUM_ROUNDS] = ARK1;
263
264 /// Round constants added to the hasher state in the second half of the RPO round.
265 pub const ARK2: [[Felt; STATE_WIDTH]; NUM_ROUNDS] = ARK2;
266
267 // TRAIT PASS-THROUGH FUNCTIONS
268 // --------------------------------------------------------------------------------------------
269
270 /// Returns a hash of the provided sequence of bytes.
271 #[inline(always)]
272 pub fn hash(bytes: &[u8]) -> RpoDigest {
273 <Self as Hasher>::hash(bytes)
274 }
275
276 /// Returns a hash of two digests. This method is intended for use in construction of
277 /// Merkle trees and verification of Merkle paths.
278 #[inline(always)]
279 pub fn merge(values: &[RpoDigest; 2]) -> RpoDigest {
280 <Self as Hasher>::merge(values)
281 }
282
283 /// Returns a hash of the provided field elements.
284 #[inline(always)]
285 pub fn hash_elements<E: FieldElement<BaseField = Felt>>(elements: &[E]) -> RpoDigest {
286 <Self as ElementHasher>::hash_elements(elements)
287 }
288
289 // DOMAIN IDENTIFIER
290 // --------------------------------------------------------------------------------------------
291
292 /// Returns a hash of two digests and a domain identifier.
293 pub fn merge_in_domain(values: &[RpoDigest; 2], domain: Felt) -> RpoDigest {
294 // initialize the state by copying the digest elements into the rate portion of the state
295 // (8 total elements), and set the capacity elements to 0.
296 let mut state = [ZERO; STATE_WIDTH];
297 let it = RpoDigest::digests_as_elements_iter(values.iter());
298 for (i, v) in it.enumerate() {
299 state[RATE_RANGE.start + i] = *v;
300 }
301
302 // set the second capacity element to the domain value. The first capacity element is used
303 // for padding purposes.
304 state[CAPACITY_RANGE.start + 1] = domain;
305
306 // apply the RPO permutation and return the first four elements of the state
307 Self::apply_permutation(&mut state);
308 RpoDigest::new(state[DIGEST_RANGE].try_into().unwrap())
309 }
310
311 // RESCUE PERMUTATION
312 // --------------------------------------------------------------------------------------------
313
314 /// Applies RPO permutation to the provided state.
315 #[inline(always)]
316 pub fn apply_permutation(state: &mut [Felt; STATE_WIDTH]) {
317 for i in 0..NUM_ROUNDS {
318 Self::apply_round(state, i);
319 }
320 }
321
322 /// RPO round function.
323 #[inline(always)]
324 pub fn apply_round(state: &mut [Felt; STATE_WIDTH], round: usize) {
325 // apply first half of RPO round
326 apply_mds(state);
327 if !add_constants_and_apply_sbox(state, &ARK1[round]) {
328 add_constants(state, &ARK1[round]);
329 apply_sbox(state);
330 }
331
332 // apply second half of RPO round
333 apply_mds(state);
334 if !add_constants_and_apply_inv_sbox(state, &ARK2[round]) {
335 add_constants(state, &ARK2[round]);
336 apply_inv_sbox(state);
337 }
338 }
339}