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