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