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