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