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
121#[derive(Copy, Clone, Debug)]
122pub enum RpoDigestError {
123 InvalidInteger,
124}
125
126impl TryFrom<&RpoDigest> for [bool; DIGEST_SIZE] {
127 type Error = RpoDigestError;
128
129 fn try_from(value: &RpoDigest) -> Result<Self, Self::Error> {
130 (*value).try_into()
131 }
132}
133
134impl TryFrom<RpoDigest> for [bool; DIGEST_SIZE] {
135 type Error = RpoDigestError;
136
137 fn try_from(value: RpoDigest) -> Result<Self, Self::Error> {
138 fn to_bool(v: u64) -> Option<bool> {
139 if v <= 1 {
140 Some(v == 1)
141 } else {
142 None
143 }
144 }
145
146 Ok([
147 to_bool(value.0[0].as_int()).ok_or(RpoDigestError::InvalidInteger)?,
148 to_bool(value.0[1].as_int()).ok_or(RpoDigestError::InvalidInteger)?,
149 to_bool(value.0[2].as_int()).ok_or(RpoDigestError::InvalidInteger)?,
150 to_bool(value.0[3].as_int()).ok_or(RpoDigestError::InvalidInteger)?,
151 ])
152 }
153}
154
155impl TryFrom<&RpoDigest> for [u8; DIGEST_SIZE] {
156 type Error = RpoDigestError;
157
158 fn try_from(value: &RpoDigest) -> Result<Self, Self::Error> {
159 (*value).try_into()
160 }
161}
162
163impl TryFrom<RpoDigest> for [u8; DIGEST_SIZE] {
164 type Error = RpoDigestError;
165
166 fn try_from(value: RpoDigest) -> Result<Self, Self::Error> {
167 Ok([
168 value.0[0].as_int().try_into().map_err(|_| RpoDigestError::InvalidInteger)?,
169 value.0[1].as_int().try_into().map_err(|_| RpoDigestError::InvalidInteger)?,
170 value.0[2].as_int().try_into().map_err(|_| RpoDigestError::InvalidInteger)?,
171 value.0[3].as_int().try_into().map_err(|_| RpoDigestError::InvalidInteger)?,
172 ])
173 }
174}
175
176impl TryFrom<&RpoDigest> for [u16; DIGEST_SIZE] {
177 type Error = RpoDigestError;
178
179 fn try_from(value: &RpoDigest) -> Result<Self, Self::Error> {
180 (*value).try_into()
181 }
182}
183
184impl TryFrom<RpoDigest> for [u16; DIGEST_SIZE] {
185 type Error = RpoDigestError;
186
187 fn try_from(value: RpoDigest) -> Result<Self, Self::Error> {
188 Ok([
189 value.0[0].as_int().try_into().map_err(|_| RpoDigestError::InvalidInteger)?,
190 value.0[1].as_int().try_into().map_err(|_| RpoDigestError::InvalidInteger)?,
191 value.0[2].as_int().try_into().map_err(|_| RpoDigestError::InvalidInteger)?,
192 value.0[3].as_int().try_into().map_err(|_| RpoDigestError::InvalidInteger)?,
193 ])
194 }
195}
196
197impl TryFrom<&RpoDigest> for [u32; DIGEST_SIZE] {
198 type Error = RpoDigestError;
199
200 fn try_from(value: &RpoDigest) -> Result<Self, Self::Error> {
201 (*value).try_into()
202 }
203}
204
205impl TryFrom<RpoDigest> for [u32; DIGEST_SIZE] {
206 type Error = RpoDigestError;
207
208 fn try_from(value: RpoDigest) -> Result<Self, Self::Error> {
209 Ok([
210 value.0[0].as_int().try_into().map_err(|_| RpoDigestError::InvalidInteger)?,
211 value.0[1].as_int().try_into().map_err(|_| RpoDigestError::InvalidInteger)?,
212 value.0[2].as_int().try_into().map_err(|_| RpoDigestError::InvalidInteger)?,
213 value.0[3].as_int().try_into().map_err(|_| RpoDigestError::InvalidInteger)?,
214 ])
215 }
216}
217
218impl From<&RpoDigest> for [u64; DIGEST_SIZE] {
219 fn from(value: &RpoDigest) -> Self {
220 (*value).into()
221 }
222}
223
224impl From<RpoDigest> for [u64; DIGEST_SIZE] {
225 fn from(value: RpoDigest) -> Self {
226 [
227 value.0[0].as_int(),
228 value.0[1].as_int(),
229 value.0[2].as_int(),
230 value.0[3].as_int(),
231 ]
232 }
233}
234
235impl From<&RpoDigest> for [Felt; DIGEST_SIZE] {
236 fn from(value: &RpoDigest) -> Self {
237 (*value).into()
238 }
239}
240
241impl From<RpoDigest> for [Felt; DIGEST_SIZE] {
242 fn from(value: RpoDigest) -> Self {
243 value.0
244 }
245}
246
247impl From<&RpoDigest> for [u8; DIGEST_BYTES] {
248 fn from(value: &RpoDigest) -> Self {
249 (*value).into()
250 }
251}
252
253impl From<RpoDigest> for [u8; DIGEST_BYTES] {
254 fn from(value: RpoDigest) -> Self {
255 value.as_bytes()
256 }
257}
258
259impl From<&RpoDigest> for String {
260 /// The returned string starts with `0x`.
261 fn from(value: &RpoDigest) -> Self {
262 (*value).into()
263 }
264}
265
266impl From<RpoDigest> for String {
267 /// The returned string starts with `0x`.
268 fn from(value: RpoDigest) -> Self {
269 value.to_hex()
270 }
271}
272
273// CONVERSIONS: TO RPO DIGEST
274// ================================================================================================
275
276impl From<&[bool; DIGEST_SIZE]> for RpoDigest {
277 fn from(value: &[bool; DIGEST_SIZE]) -> Self {
278 (*value).into()
279 }
280}
281
282impl From<[bool; DIGEST_SIZE]> for RpoDigest {
283 fn from(value: [bool; DIGEST_SIZE]) -> Self {
284 [value[0] as u32, value[1] as u32, value[2] as u32, value[3] as u32].into()
285 }
286}
287
288impl From<&[u8; DIGEST_SIZE]> for RpoDigest {
289 fn from(value: &[u8; DIGEST_SIZE]) -> Self {
290 (*value).into()
291 }
292}
293
294impl From<[u8; DIGEST_SIZE]> for RpoDigest {
295 fn from(value: [u8; DIGEST_SIZE]) -> Self {
296 Self([value[0].into(), value[1].into(), value[2].into(), value[3].into()])
297 }
298}
299
300impl From<&[u16; DIGEST_SIZE]> for RpoDigest {
301 fn from(value: &[u16; DIGEST_SIZE]) -> Self {
302 (*value).into()
303 }
304}
305
306impl From<[u16; DIGEST_SIZE]> for RpoDigest {
307 fn from(value: [u16; DIGEST_SIZE]) -> Self {
308 Self([value[0].into(), value[1].into(), value[2].into(), value[3].into()])
309 }
310}
311
312impl From<&[u32; DIGEST_SIZE]> for RpoDigest {
313 fn from(value: &[u32; DIGEST_SIZE]) -> Self {
314 (*value).into()
315 }
316}
317
318impl From<[u32; DIGEST_SIZE]> for RpoDigest {
319 fn from(value: [u32; DIGEST_SIZE]) -> Self {
320 Self([value[0].into(), value[1].into(), value[2].into(), value[3].into()])
321 }
322}
323
324impl TryFrom<&[u64; DIGEST_SIZE]> for RpoDigest {
325 type Error = RpoDigestError;
326
327 fn try_from(value: &[u64; DIGEST_SIZE]) -> Result<Self, RpoDigestError> {
328 (*value).try_into()
329 }
330}
331
332impl TryFrom<[u64; DIGEST_SIZE]> for RpoDigest {
333 type Error = RpoDigestError;
334
335 fn try_from(value: [u64; DIGEST_SIZE]) -> Result<Self, RpoDigestError> {
336 Ok(Self([
337 value[0].try_into().map_err(|_| RpoDigestError::InvalidInteger)?,
338 value[1].try_into().map_err(|_| RpoDigestError::InvalidInteger)?,
339 value[2].try_into().map_err(|_| RpoDigestError::InvalidInteger)?,
340 value[3].try_into().map_err(|_| RpoDigestError::InvalidInteger)?,
341 ]))
342 }
343}
344
345impl From<&[Felt; DIGEST_SIZE]> for RpoDigest {
346 fn from(value: &[Felt; DIGEST_SIZE]) -> Self {
347 Self(*value)
348 }
349}
350
351impl From<[Felt; DIGEST_SIZE]> for RpoDigest {
352 fn from(value: [Felt; DIGEST_SIZE]) -> Self {
353 Self(value)
354 }
355}
356
357impl TryFrom<&[u8; DIGEST_BYTES]> for RpoDigest {
358 type Error = HexParseError;
359
360 fn try_from(value: &[u8; DIGEST_BYTES]) -> Result<Self, Self::Error> {
361 (*value).try_into()
362 }
363}
364
365impl TryFrom<[u8; DIGEST_BYTES]> for RpoDigest {
366 type Error = HexParseError;
367
368 fn try_from(value: [u8; DIGEST_BYTES]) -> Result<Self, Self::Error> {
369 // Note: the input length is known, the conversion from slice to array must succeed so the
370 // `unwrap`s below are safe
371 let a = u64::from_le_bytes(value[0..8].try_into().unwrap());
372 let b = u64::from_le_bytes(value[8..16].try_into().unwrap());
373 let c = u64::from_le_bytes(value[16..24].try_into().unwrap());
374 let d = u64::from_le_bytes(value[24..32].try_into().unwrap());
375
376 if [a, b, c, d].iter().any(|v| *v >= Felt::MODULUS) {
377 return Err(HexParseError::OutOfRange);
378 }
379
380 Ok(RpoDigest([Felt::new(a), Felt::new(b), Felt::new(c), Felt::new(d)]))
381 }
382}
383
384impl TryFrom<&[u8]> for RpoDigest {
385 type Error = HexParseError;
386
387 fn try_from(value: &[u8]) -> Result<Self, Self::Error> {
388 (*value).try_into()
389 }
390}
391
392impl TryFrom<&str> for RpoDigest {
393 type Error = HexParseError;
394
395 /// Expects the string to start with `0x`.
396 fn try_from(value: &str) -> Result<Self, Self::Error> {
397 hex_to_bytes::<DIGEST_BYTES>(value).and_then(RpoDigest::try_from)
398 }
399}
400
401impl TryFrom<String> for RpoDigest {
402 type Error = HexParseError;
403
404 /// Expects the string to start with `0x`.
405 fn try_from(value: String) -> Result<Self, Self::Error> {
406 value.as_str().try_into()
407 }
408}
409
410impl TryFrom<&String> for RpoDigest {
411 type Error = HexParseError;
412
413 /// Expects the string to start with `0x`.
414 fn try_from(value: &String) -> Result<Self, Self::Error> {
415 value.as_str().try_into()
416 }
417}
418
419// SERIALIZATION / DESERIALIZATION
420// ================================================================================================
421
422impl Serializable for RpoDigest {
423 fn write_into<W: ByteWriter>(&self, target: &mut W) {
424 target.write_bytes(&self.as_bytes());
425 }
426}
427
428impl Deserializable for RpoDigest {
429 fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
430 let mut inner: [Felt; DIGEST_SIZE] = [ZERO; DIGEST_SIZE];
431 for inner in inner.iter_mut() {
432 let e = source.read_u64()?;
433 if e >= Felt::MODULUS {
434 return Err(DeserializationError::InvalidValue(String::from(
435 "Value not in the appropriate range",
436 )));
437 }
438 *inner = Felt::new(e);
439 }
440
441 Ok(Self(inner))
442 }
443}
444
445// ITERATORS
446// ================================================================================================
447impl IntoIterator for RpoDigest {
448 type Item = Felt;
449 type IntoIter = <[Felt; 4] as IntoIterator>::IntoIter;
450
451 fn into_iter(self) -> Self::IntoIter {
452 self.0.into_iter()
453 }
454}
455
456// TESTS
457// ================================================================================================
458
459#[cfg(test)]
460mod tests {
461 use alloc::string::String;
462 use rand_utils::rand_value;
463
464 use super::{Deserializable, Felt, RpoDigest, Serializable, DIGEST_BYTES, DIGEST_SIZE};
465 use crate::utils::SliceReader;
466
467 #[test]
468 fn digest_serialization() {
469 let e1 = Felt::new(rand_value());
470 let e2 = Felt::new(rand_value());
471 let e3 = Felt::new(rand_value());
472 let e4 = Felt::new(rand_value());
473
474 let d1 = RpoDigest([e1, e2, e3, e4]);
475
476 let mut bytes = vec![];
477 d1.write_into(&mut bytes);
478 assert_eq!(DIGEST_BYTES, bytes.len());
479
480 let mut reader = SliceReader::new(&bytes);
481 let d2 = RpoDigest::read_from(&mut reader).unwrap();
482
483 assert_eq!(d1, d2);
484 }
485
486 #[test]
487 fn digest_encoding() {
488 let digest = RpoDigest([
489 Felt::new(rand_value()),
490 Felt::new(rand_value()),
491 Felt::new(rand_value()),
492 Felt::new(rand_value()),
493 ]);
494
495 let string: String = digest.into();
496 let round_trip: RpoDigest = string.try_into().expect("decoding failed");
497
498 assert_eq!(digest, round_trip);
499 }
500
501 #[test]
502 fn test_conversions() {
503 let digest = RpoDigest([
504 Felt::new(rand_value()),
505 Felt::new(rand_value()),
506 Felt::new(rand_value()),
507 Felt::new(rand_value()),
508 ]);
509
510 // BY VALUE
511 // ----------------------------------------------------------------------------------------
512 let v: [bool; DIGEST_SIZE] = [true, false, true, true];
513 let v2: RpoDigest = v.into();
514 assert_eq!(v, <[bool; DIGEST_SIZE]>::try_from(v2).unwrap());
515
516 let v: [u8; DIGEST_SIZE] = [0_u8, 1_u8, 2_u8, 3_u8];
517 let v2: RpoDigest = v.into();
518 assert_eq!(v, <[u8; DIGEST_SIZE]>::try_from(v2).unwrap());
519
520 let v: [u16; DIGEST_SIZE] = [0_u16, 1_u16, 2_u16, 3_u16];
521 let v2: RpoDigest = v.into();
522 assert_eq!(v, <[u16; DIGEST_SIZE]>::try_from(v2).unwrap());
523
524 let v: [u32; DIGEST_SIZE] = [0_u32, 1_u32, 2_u32, 3_u32];
525 let v2: RpoDigest = v.into();
526 assert_eq!(v, <[u32; DIGEST_SIZE]>::try_from(v2).unwrap());
527
528 let v: [u64; DIGEST_SIZE] = digest.into();
529 let v2: RpoDigest = v.try_into().unwrap();
530 assert_eq!(digest, v2);
531
532 let v: [Felt; DIGEST_SIZE] = digest.into();
533 let v2: RpoDigest = v.into();
534 assert_eq!(digest, v2);
535
536 let v: [u8; DIGEST_BYTES] = digest.into();
537 let v2: RpoDigest = v.try_into().unwrap();
538 assert_eq!(digest, v2);
539
540 let v: String = digest.into();
541 let v2: RpoDigest = v.try_into().unwrap();
542 assert_eq!(digest, v2);
543
544 // BY REF
545 // ----------------------------------------------------------------------------------------
546 let v: [bool; DIGEST_SIZE] = [true, false, true, true];
547 let v2: RpoDigest = (&v).into();
548 assert_eq!(v, <[bool; DIGEST_SIZE]>::try_from(&v2).unwrap());
549
550 let v: [u8; DIGEST_SIZE] = [0_u8, 1_u8, 2_u8, 3_u8];
551 let v2: RpoDigest = (&v).into();
552 assert_eq!(v, <[u8; DIGEST_SIZE]>::try_from(&v2).unwrap());
553
554 let v: [u16; DIGEST_SIZE] = [0_u16, 1_u16, 2_u16, 3_u16];
555 let v2: RpoDigest = (&v).into();
556 assert_eq!(v, <[u16; DIGEST_SIZE]>::try_from(&v2).unwrap());
557
558 let v: [u32; DIGEST_SIZE] = [0_u32, 1_u32, 2_u32, 3_u32];
559 let v2: RpoDigest = (&v).into();
560 assert_eq!(v, <[u32; DIGEST_SIZE]>::try_from(&v2).unwrap());
561
562 let v: [u64; DIGEST_SIZE] = (&digest).into();
563 let v2: RpoDigest = (&v).try_into().unwrap();
564 assert_eq!(digest, v2);
565
566 let v: [Felt; DIGEST_SIZE] = (&digest).into();
567 let v2: RpoDigest = (&v).into();
568 assert_eq!(digest, v2);
569
570 let v: [u8; DIGEST_BYTES] = (&digest).into();
571 let v2: RpoDigest = (&v).try_into().unwrap();
572 assert_eq!(digest, v2);
573
574 let v: String = (&digest).into();
575 let v2: RpoDigest = (&v).try_into().unwrap();
576 assert_eq!(digest, v2);
577 }
578}