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