miden-crypto/src/hash/rescue/rpo/digest.rs
src/hash/rescue/rpo/digest.rsRaw
1use alloc::string::String;
2use core::{cmp::Ordering, fmt::Display, ops::Deref};
3
4use super::{Digest, Felt, StarkField, DIGEST_BYTES, DIGEST_SIZE, ZERO};
5use crate::{
6 rand::Randomizable,
7 utils::{
8 bytes_to_hex_string, hex_to_bytes, ByteReader, ByteWriter, Deserializable,
9 DeserializationError, HexParseError, Serializable,
10 },
11};
12
13// DIGEST TRAIT IMPLEMENTATIONS
14// ================================================================================================
15
16#[derive(Debug, Default, Copy, Clone, Eq, PartialEq)]
17#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
18#[cfg_attr(feature = "serde", serde(into = "String", try_from = "&str"))]
19pub struct RpoDigest([Felt; DIGEST_SIZE]);
20
21impl RpoDigest {
22 pub const fn new(value: [Felt; DIGEST_SIZE]) -> Self {
23 Self(value)
24 }
25
26 pub fn as_elements(&self) -> &[Felt] {
27 self.as_ref()
28 }
29
30 pub fn as_bytes(&self) -> [u8; DIGEST_BYTES] {
31 <Self as Digest>::as_bytes(self)
32 }
33
34 pub fn digests_as_elements<'a, I>(digests: I) -> impl Iterator<Item = &'a Felt>
35 where
36 I: Iterator<Item = &'a Self>,
37 {
38 digests.flat_map(|d| d.0.iter())
39 }
40
41 /// Returns hexadecimal representation of this digest prefixed with `0x`.
42 pub fn to_hex(&self) -> String {
43 bytes_to_hex_string(self.as_bytes())
44 }
45}
46
47impl Digest for RpoDigest {
48 fn as_bytes(&self) -> [u8; DIGEST_BYTES] {
49 let mut result = [0; DIGEST_BYTES];
50
51 result[..8].copy_from_slice(&self.0[0].as_int().to_le_bytes());
52 result[8..16].copy_from_slice(&self.0[1].as_int().to_le_bytes());
53 result[16..24].copy_from_slice(&self.0[2].as_int().to_le_bytes());
54 result[24..].copy_from_slice(&self.0[3].as_int().to_le_bytes());
55
56 result
57 }
58}
59
60impl Deref for RpoDigest {
61 type Target = [Felt; DIGEST_SIZE];
62
63 fn deref(&self) -> &Self::Target {
64 &self.0
65 }
66}
67
68impl Ord for RpoDigest {
69 fn cmp(&self, other: &Self) -> Ordering {
70 // compare the inner u64 of both elements.
71 //
72 // it will iterate the elements and will return the first computation different than
73 // `Equal`. Otherwise, the ordering is equal.
74 //
75 // the endianness is irrelevant here because since, this being a cryptographically secure
76 // hash computation, the digest shouldn't have any ordered property of its input.
77 //
78 // finally, we use `Felt::inner` instead of `Felt::as_int` so we avoid performing a
79 // montgomery reduction for every limb. that is safe because every inner element of the
80 // digest is guaranteed to be in its canonical form (that is, `x in [0,p)`).
81 self.0.iter().map(Felt::inner).zip(other.0.iter().map(Felt::inner)).fold(
82 Ordering::Equal,
83 |ord, (a, b)| match ord {
84 Ordering::Equal => a.cmp(&b),
85 _ => ord,
86 },
87 )
88 }
89}
90
91impl PartialOrd for RpoDigest {
92 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
93 Some(self.cmp(other))
94 }
95}
96
97impl Display for RpoDigest {
98 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
99 let encoded: String = self.into();
100 write!(f, "{}", encoded)?;
101 Ok(())
102 }
103}
104
105impl Randomizable for RpoDigest {
106 const VALUE_SIZE: usize = DIGEST_BYTES;
107
108 fn from_random_bytes(bytes: &[u8]) -> Option<Self> {
109 let bytes_array: Option<[u8; 32]> = bytes.try_into().ok();
110 if let Some(bytes_array) = bytes_array {
111 Self::try_from(bytes_array).ok()
112 } else {
113 None
114 }
115 }
116}
117
118// CONVERSIONS: FROM RPO DIGEST
119// ================================================================================================
120
121impl From<&RpoDigest> for [Felt; DIGEST_SIZE] {
122 fn from(value: &RpoDigest) -> Self {
123 value.0
124 }
125}
126
127impl From<RpoDigest> for [Felt; DIGEST_SIZE] {
128 fn from(value: RpoDigest) -> Self {
129 value.0
130 }
131}
132
133impl From<&RpoDigest> for [u64; DIGEST_SIZE] {
134 fn from(value: &RpoDigest) -> Self {
135 [
136 value.0[0].as_int(),
137 value.0[1].as_int(),
138 value.0[2].as_int(),
139 value.0[3].as_int(),
140 ]
141 }
142}
143
144impl From<RpoDigest> for [u64; DIGEST_SIZE] {
145 fn from(value: RpoDigest) -> Self {
146 [
147 value.0[0].as_int(),
148 value.0[1].as_int(),
149 value.0[2].as_int(),
150 value.0[3].as_int(),
151 ]
152 }
153}
154
155impl From<&RpoDigest> for [u8; DIGEST_BYTES] {
156 fn from(value: &RpoDigest) -> Self {
157 value.as_bytes()
158 }
159}
160
161impl From<RpoDigest> for [u8; DIGEST_BYTES] {
162 fn from(value: RpoDigest) -> Self {
163 value.as_bytes()
164 }
165}
166
167impl From<RpoDigest> for String {
168 /// The returned string starts with `0x`.
169 fn from(value: RpoDigest) -> Self {
170 value.to_hex()
171 }
172}
173
174impl From<&RpoDigest> for String {
175 /// The returned string starts with `0x`.
176 fn from(value: &RpoDigest) -> Self {
177 (*value).into()
178 }
179}
180
181// CONVERSIONS: TO RPO DIGEST
182// ================================================================================================
183
184#[derive(Copy, Clone, Debug)]
185pub enum RpoDigestError {
186 /// The provided u64 integer does not fit in the field's moduli.
187 InvalidInteger,
188}
189
190impl From<&[Felt; DIGEST_SIZE]> for RpoDigest {
191 fn from(value: &[Felt; DIGEST_SIZE]) -> Self {
192 Self(*value)
193 }
194}
195
196impl From<[Felt; DIGEST_SIZE]> for RpoDigest {
197 fn from(value: [Felt; DIGEST_SIZE]) -> Self {
198 Self(value)
199 }
200}
201
202impl TryFrom<[u8; DIGEST_BYTES]> for RpoDigest {
203 type Error = HexParseError;
204
205 fn try_from(value: [u8; DIGEST_BYTES]) -> Result<Self, Self::Error> {
206 // Note: the input length is known, the conversion from slice to array must succeed so the
207 // `unwrap`s below are safe
208 let a = u64::from_le_bytes(value[0..8].try_into().unwrap());
209 let b = u64::from_le_bytes(value[8..16].try_into().unwrap());
210 let c = u64::from_le_bytes(value[16..24].try_into().unwrap());
211 let d = u64::from_le_bytes(value[24..32].try_into().unwrap());
212
213 if [a, b, c, d].iter().any(|v| *v >= Felt::MODULUS) {
214 return Err(HexParseError::OutOfRange);
215 }
216
217 Ok(RpoDigest([Felt::new(a), Felt::new(b), Felt::new(c), Felt::new(d)]))
218 }
219}
220
221impl TryFrom<&[u8; DIGEST_BYTES]> for RpoDigest {
222 type Error = HexParseError;
223
224 fn try_from(value: &[u8; DIGEST_BYTES]) -> Result<Self, Self::Error> {
225 (*value).try_into()
226 }
227}
228
229impl TryFrom<&[u8]> for RpoDigest {
230 type Error = HexParseError;
231
232 fn try_from(value: &[u8]) -> Result<Self, Self::Error> {
233 (*value).try_into()
234 }
235}
236
237impl TryFrom<[u64; DIGEST_SIZE]> for RpoDigest {
238 type Error = RpoDigestError;
239
240 fn try_from(value: [u64; DIGEST_SIZE]) -> Result<Self, RpoDigestError> {
241 Ok(Self([
242 value[0].try_into().map_err(|_| RpoDigestError::InvalidInteger)?,
243 value[1].try_into().map_err(|_| RpoDigestError::InvalidInteger)?,
244 value[2].try_into().map_err(|_| RpoDigestError::InvalidInteger)?,
245 value[3].try_into().map_err(|_| RpoDigestError::InvalidInteger)?,
246 ]))
247 }
248}
249
250impl TryFrom<&[u64; DIGEST_SIZE]> for RpoDigest {
251 type Error = RpoDigestError;
252
253 fn try_from(value: &[u64; DIGEST_SIZE]) -> Result<Self, RpoDigestError> {
254 (*value).try_into()
255 }
256}
257
258impl TryFrom<&str> for RpoDigest {
259 type Error = HexParseError;
260
261 /// Expects the string to start with `0x`.
262 fn try_from(value: &str) -> Result<Self, Self::Error> {
263 hex_to_bytes(value).and_then(|v| v.try_into())
264 }
265}
266
267impl TryFrom<String> for RpoDigest {
268 type Error = HexParseError;
269
270 /// Expects the string to start with `0x`.
271 fn try_from(value: String) -> Result<Self, Self::Error> {
272 value.as_str().try_into()
273 }
274}
275
276impl TryFrom<&String> for RpoDigest {
277 type Error = HexParseError;
278
279 /// Expects the string to start with `0x`.
280 fn try_from(value: &String) -> Result<Self, Self::Error> {
281 value.as_str().try_into()
282 }
283}
284
285// SERIALIZATION / DESERIALIZATION
286// ================================================================================================
287
288impl Serializable for RpoDigest {
289 fn write_into<W: ByteWriter>(&self, target: &mut W) {
290 target.write_bytes(&self.as_bytes());
291 }
292}
293
294impl Deserializable for RpoDigest {
295 fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
296 let mut inner: [Felt; DIGEST_SIZE] = [ZERO; DIGEST_SIZE];
297 for inner in inner.iter_mut() {
298 let e = source.read_u64()?;
299 if e >= Felt::MODULUS {
300 return Err(DeserializationError::InvalidValue(String::from(
301 "Value not in the appropriate range",
302 )));
303 }
304 *inner = Felt::new(e);
305 }
306
307 Ok(Self(inner))
308 }
309}
310
311// ITERATORS
312// ================================================================================================
313impl IntoIterator for RpoDigest {
314 type Item = Felt;
315 type IntoIter = <[Felt; 4] as IntoIterator>::IntoIter;
316
317 fn into_iter(self) -> Self::IntoIter {
318 self.0.into_iter()
319 }
320}
321
322// TESTS
323// ================================================================================================
324
325#[cfg(test)]
326mod tests {
327 use alloc::string::String;
328 use rand_utils::rand_value;
329
330 use super::{Deserializable, Felt, RpoDigest, Serializable, DIGEST_BYTES, DIGEST_SIZE};
331 use crate::utils::SliceReader;
332
333 #[test]
334 fn digest_serialization() {
335 let e1 = Felt::new(rand_value());
336 let e2 = Felt::new(rand_value());
337 let e3 = Felt::new(rand_value());
338 let e4 = Felt::new(rand_value());
339
340 let d1 = RpoDigest([e1, e2, e3, e4]);
341
342 let mut bytes = vec![];
343 d1.write_into(&mut bytes);
344 assert_eq!(DIGEST_BYTES, bytes.len());
345
346 let mut reader = SliceReader::new(&bytes);
347 let d2 = RpoDigest::read_from(&mut reader).unwrap();
348
349 assert_eq!(d1, d2);
350 }
351
352 #[test]
353 fn digest_encoding() {
354 let digest = RpoDigest([
355 Felt::new(rand_value()),
356 Felt::new(rand_value()),
357 Felt::new(rand_value()),
358 Felt::new(rand_value()),
359 ]);
360
361 let string: String = digest.into();
362 let round_trip: RpoDigest = string.try_into().expect("decoding failed");
363
364 assert_eq!(digest, round_trip);
365 }
366
367 #[test]
368 fn test_conversions() {
369 let digest = RpoDigest([
370 Felt::new(rand_value()),
371 Felt::new(rand_value()),
372 Felt::new(rand_value()),
373 Felt::new(rand_value()),
374 ]);
375
376 let v: [Felt; DIGEST_SIZE] = digest.into();
377 let v2: RpoDigest = v.into();
378 assert_eq!(digest, v2);
379
380 let v: [Felt; DIGEST_SIZE] = (&digest).into();
381 let v2: RpoDigest = v.into();
382 assert_eq!(digest, v2);
383
384 let v: [u64; DIGEST_SIZE] = digest.into();
385 let v2: RpoDigest = v.try_into().unwrap();
386 assert_eq!(digest, v2);
387
388 let v: [u64; DIGEST_SIZE] = (&digest).into();
389 let v2: RpoDigest = v.try_into().unwrap();
390 assert_eq!(digest, v2);
391
392 let v: [u8; DIGEST_BYTES] = digest.into();
393 let v2: RpoDigest = v.try_into().unwrap();
394 assert_eq!(digest, v2);
395
396 let v: [u8; DIGEST_BYTES] = (&digest).into();
397 let v2: RpoDigest = v.try_into().unwrap();
398 assert_eq!(digest, v2);
399
400 let v: String = digest.into();
401 let v2: RpoDigest = v.try_into().unwrap();
402 assert_eq!(digest, v2);
403
404 let v: String = (&digest).into();
405 let v2: RpoDigest = v.try_into().unwrap();
406 assert_eq!(digest, v2);
407
408 let v: [u8; DIGEST_BYTES] = digest.into();
409 let v2: RpoDigest = (&v).try_into().unwrap();
410 assert_eq!(digest, v2);
411
412 let v: [u8; DIGEST_BYTES] = (&digest).into();
413 let v2: RpoDigest = (&v).try_into().unwrap();
414 assert_eq!(digest, v2);
415 }
416}