miden-crypto/src/hash/rescue/rpx/digest.rs
src/hash/rescue/rpx/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 RpxDigest([Felt; DIGEST_SIZE]);
20
21impl RpxDigest {
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 RpxDigest {
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 RpxDigest {
61 type Target = [Felt; DIGEST_SIZE];
62
63 fn deref(&self) -> &Self::Target {
64 &self.0
65 }
66}
67
68impl Ord for RpxDigest {
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 RpxDigest {
92 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
93 Some(self.cmp(other))
94 }
95}
96
97impl Display for RpxDigest {
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 RpxDigest {
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 RPX DIGEST
119// ================================================================================================
120
121#[derive(Copy, Clone, Debug)]
122pub enum RpxDigestError {
123 InvalidInteger,
124}
125
126impl TryFrom<&RpxDigest> for [bool; DIGEST_SIZE] {
127 type Error = RpxDigestError;
128
129 fn try_from(value: &RpxDigest) -> Result<Self, Self::Error> {
130 (*value).try_into()
131 }
132}
133
134impl TryFrom<RpxDigest> for [bool; DIGEST_SIZE] {
135 type Error = RpxDigestError;
136
137 fn try_from(value: RpxDigest) -> 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(RpxDigestError::InvalidInteger)?,
148 to_bool(value.0[1].as_int()).ok_or(RpxDigestError::InvalidInteger)?,
149 to_bool(value.0[2].as_int()).ok_or(RpxDigestError::InvalidInteger)?,
150 to_bool(value.0[3].as_int()).ok_or(RpxDigestError::InvalidInteger)?,
151 ])
152 }
153}
154
155impl TryFrom<&RpxDigest> for [u8; DIGEST_SIZE] {
156 type Error = RpxDigestError;
157
158 fn try_from(value: &RpxDigest) -> Result<Self, Self::Error> {
159 (*value).try_into()
160 }
161}
162
163impl TryFrom<RpxDigest> for [u8; DIGEST_SIZE] {
164 type Error = RpxDigestError;
165
166 fn try_from(value: RpxDigest) -> Result<Self, Self::Error> {
167 Ok([
168 value.0[0].as_int().try_into().map_err(|_| RpxDigestError::InvalidInteger)?,
169 value.0[1].as_int().try_into().map_err(|_| RpxDigestError::InvalidInteger)?,
170 value.0[2].as_int().try_into().map_err(|_| RpxDigestError::InvalidInteger)?,
171 value.0[3].as_int().try_into().map_err(|_| RpxDigestError::InvalidInteger)?,
172 ])
173 }
174}
175
176impl TryFrom<&RpxDigest> for [u16; DIGEST_SIZE] {
177 type Error = RpxDigestError;
178
179 fn try_from(value: &RpxDigest) -> Result<Self, Self::Error> {
180 (*value).try_into()
181 }
182}
183
184impl TryFrom<RpxDigest> for [u16; DIGEST_SIZE] {
185 type Error = RpxDigestError;
186
187 fn try_from(value: RpxDigest) -> Result<Self, Self::Error> {
188 Ok([
189 value.0[0].as_int().try_into().map_err(|_| RpxDigestError::InvalidInteger)?,
190 value.0[1].as_int().try_into().map_err(|_| RpxDigestError::InvalidInteger)?,
191 value.0[2].as_int().try_into().map_err(|_| RpxDigestError::InvalidInteger)?,
192 value.0[3].as_int().try_into().map_err(|_| RpxDigestError::InvalidInteger)?,
193 ])
194 }
195}
196
197impl TryFrom<&RpxDigest> for [u32; DIGEST_SIZE] {
198 type Error = RpxDigestError;
199
200 fn try_from(value: &RpxDigest) -> Result<Self, Self::Error> {
201 (*value).try_into()
202 }
203}
204
205impl TryFrom<RpxDigest> for [u32; DIGEST_SIZE] {
206 type Error = RpxDigestError;
207
208 fn try_from(value: RpxDigest) -> Result<Self, Self::Error> {
209 Ok([
210 value.0[0].as_int().try_into().map_err(|_| RpxDigestError::InvalidInteger)?,
211 value.0[1].as_int().try_into().map_err(|_| RpxDigestError::InvalidInteger)?,
212 value.0[2].as_int().try_into().map_err(|_| RpxDigestError::InvalidInteger)?,
213 value.0[3].as_int().try_into().map_err(|_| RpxDigestError::InvalidInteger)?,
214 ])
215 }
216}
217
218impl From<&RpxDigest> for [u64; DIGEST_SIZE] {
219 fn from(value: &RpxDigest) -> Self {
220 (*value).into()
221 }
222}
223
224impl From<RpxDigest> for [u64; DIGEST_SIZE] {
225 fn from(value: RpxDigest) -> 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<&RpxDigest> for [Felt; DIGEST_SIZE] {
236 fn from(value: &RpxDigest) -> Self {
237 value.0
238 }
239}
240
241impl From<RpxDigest> for [Felt; DIGEST_SIZE] {
242 fn from(value: RpxDigest) -> Self {
243 value.0
244 }
245}
246
247impl From<&RpxDigest> for [u8; DIGEST_BYTES] {
248 fn from(value: &RpxDigest) -> Self {
249 value.as_bytes()
250 }
251}
252
253impl From<RpxDigest> for [u8; DIGEST_BYTES] {
254 fn from(value: RpxDigest) -> Self {
255 value.as_bytes()
256 }
257}
258
259impl From<&RpxDigest> for String {
260 /// The returned string starts with `0x`.
261 fn from(value: &RpxDigest) -> Self {
262 (*value).into()
263 }
264}
265
266impl From<RpxDigest> for String {
267 /// The returned string starts with `0x`.
268 fn from(value: RpxDigest) -> Self {
269 value.to_hex()
270 }
271}
272
273// CONVERSIONS: TO RPX DIGEST
274// ================================================================================================
275
276impl From<&[bool; DIGEST_SIZE]> for RpxDigest {
277 fn from(value: &[bool; DIGEST_SIZE]) -> Self {
278 (*value).into()
279 }
280}
281
282impl From<[bool; DIGEST_SIZE]> for RpxDigest {
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 RpxDigest {
289 fn from(value: &[u8; DIGEST_SIZE]) -> Self {
290 (*value).into()
291 }
292}
293
294impl From<[u8; DIGEST_SIZE]> for RpxDigest {
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 RpxDigest {
301 fn from(value: &[u16; DIGEST_SIZE]) -> Self {
302 (*value).into()
303 }
304}
305
306impl From<[u16; DIGEST_SIZE]> for RpxDigest {
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 RpxDigest {
313 fn from(value: &[u32; DIGEST_SIZE]) -> Self {
314 (*value).into()
315 }
316}
317
318impl From<[u32; DIGEST_SIZE]> for RpxDigest {
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 RpxDigest {
325 type Error = RpxDigestError;
326
327 fn try_from(value: &[u64; DIGEST_SIZE]) -> Result<Self, RpxDigestError> {
328 (*value).try_into()
329 }
330}
331
332impl TryFrom<[u64; DIGEST_SIZE]> for RpxDigest {
333 type Error = RpxDigestError;
334
335 fn try_from(value: [u64; DIGEST_SIZE]) -> Result<Self, RpxDigestError> {
336 Ok(Self([
337 value[0].try_into().map_err(|_| RpxDigestError::InvalidInteger)?,
338 value[1].try_into().map_err(|_| RpxDigestError::InvalidInteger)?,
339 value[2].try_into().map_err(|_| RpxDigestError::InvalidInteger)?,
340 value[3].try_into().map_err(|_| RpxDigestError::InvalidInteger)?,
341 ]))
342 }
343}
344
345impl From<&[Felt; DIGEST_SIZE]> for RpxDigest {
346 fn from(value: &[Felt; DIGEST_SIZE]) -> Self {
347 Self(*value)
348 }
349}
350
351impl From<[Felt; DIGEST_SIZE]> for RpxDigest {
352 fn from(value: [Felt; DIGEST_SIZE]) -> Self {
353 Self(value)
354 }
355}
356
357impl TryFrom<&[u8; DIGEST_BYTES]> for RpxDigest {
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 RpxDigest {
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(RpxDigest([Felt::new(a), Felt::new(b), Felt::new(c), Felt::new(d)]))
381 }
382}
383
384impl TryFrom<&[u8]> for RpxDigest {
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 RpxDigest {
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(RpxDigest::try_from)
398 }
399}
400
401impl TryFrom<&String> for RpxDigest {
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 RpxDigest {
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 RpxDigest {
423 fn write_into<W: ByteWriter>(&self, target: &mut W) {
424 target.write_bytes(&self.as_bytes());
425 }
426}
427
428impl Deserializable for RpxDigest {
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 RpxDigest {
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
463 use rand_utils::rand_value;
464
465 use super::{Deserializable, Felt, RpxDigest, Serializable, DIGEST_BYTES, DIGEST_SIZE};
466 use crate::utils::SliceReader;
467
468 #[test]
469 fn digest_serialization() {
470 let e1 = Felt::new(rand_value());
471 let e2 = Felt::new(rand_value());
472 let e3 = Felt::new(rand_value());
473 let e4 = Felt::new(rand_value());
474
475 let d1 = RpxDigest([e1, e2, e3, e4]);
476
477 let mut bytes = vec![];
478 d1.write_into(&mut bytes);
479 assert_eq!(DIGEST_BYTES, bytes.len());
480
481 let mut reader = SliceReader::new(&bytes);
482 let d2 = RpxDigest::read_from(&mut reader).unwrap();
483
484 assert_eq!(d1, d2);
485 }
486
487 #[test]
488 fn digest_encoding() {
489 let digest = RpxDigest([
490 Felt::new(rand_value()),
491 Felt::new(rand_value()),
492 Felt::new(rand_value()),
493 Felt::new(rand_value()),
494 ]);
495
496 let string: String = digest.into();
497 let round_trip: RpxDigest = string.try_into().expect("decoding failed");
498
499 assert_eq!(digest, round_trip);
500 }
501
502 #[test]
503 fn test_conversions() {
504 let digest = RpxDigest([
505 Felt::new(rand_value()),
506 Felt::new(rand_value()),
507 Felt::new(rand_value()),
508 Felt::new(rand_value()),
509 ]);
510
511 // BY VALUE
512 // ----------------------------------------------------------------------------------------
513 let v: [bool; DIGEST_SIZE] = [true, false, true, true];
514 let v2: RpxDigest = v.into();
515 assert_eq!(v, <[bool; DIGEST_SIZE]>::try_from(v2).unwrap());
516
517 let v: [u8; DIGEST_SIZE] = [0_u8, 1_u8, 2_u8, 3_u8];
518 let v2: RpxDigest = v.into();
519 assert_eq!(v, <[u8; DIGEST_SIZE]>::try_from(v2).unwrap());
520
521 let v: [u16; DIGEST_SIZE] = [0_u16, 1_u16, 2_u16, 3_u16];
522 let v2: RpxDigest = v.into();
523 assert_eq!(v, <[u16; DIGEST_SIZE]>::try_from(v2).unwrap());
524
525 let v: [u32; DIGEST_SIZE] = [0_u32, 1_u32, 2_u32, 3_u32];
526 let v2: RpxDigest = v.into();
527 assert_eq!(v, <[u32; DIGEST_SIZE]>::try_from(v2).unwrap());
528
529 let v: [u64; DIGEST_SIZE] = digest.into();
530 let v2: RpxDigest = v.try_into().unwrap();
531 assert_eq!(digest, v2);
532
533 let v: [Felt; DIGEST_SIZE] = digest.into();
534 let v2: RpxDigest = v.into();
535 assert_eq!(digest, v2);
536
537 let v: [u8; DIGEST_BYTES] = digest.into();
538 let v2: RpxDigest = v.try_into().unwrap();
539 assert_eq!(digest, v2);
540
541 let v: String = digest.into();
542 let v2: RpxDigest = v.try_into().unwrap();
543 assert_eq!(digest, v2);
544
545 // BY REF
546 // ----------------------------------------------------------------------------------------
547 let v: [bool; DIGEST_SIZE] = [true, false, true, true];
548 let v2: RpxDigest = (&v).into();
549 assert_eq!(v, <[bool; DIGEST_SIZE]>::try_from(&v2).unwrap());
550
551 let v: [u8; DIGEST_SIZE] = [0_u8, 1_u8, 2_u8, 3_u8];
552 let v2: RpxDigest = (&v).into();
553 assert_eq!(v, <[u8; DIGEST_SIZE]>::try_from(&v2).unwrap());
554
555 let v: [u16; DIGEST_SIZE] = [0_u16, 1_u16, 2_u16, 3_u16];
556 let v2: RpxDigest = (&v).into();
557 assert_eq!(v, <[u16; DIGEST_SIZE]>::try_from(&v2).unwrap());
558
559 let v: [u32; DIGEST_SIZE] = [0_u32, 1_u32, 2_u32, 3_u32];
560 let v2: RpxDigest = (&v).into();
561 assert_eq!(v, <[u32; DIGEST_SIZE]>::try_from(&v2).unwrap());
562
563 let v: [u64; DIGEST_SIZE] = (&digest).into();
564 let v2: RpxDigest = (&v).try_into().unwrap();
565 assert_eq!(digest, v2);
566
567 let v: [Felt; DIGEST_SIZE] = (&digest).into();
568 let v2: RpxDigest = (&v).into();
569 assert_eq!(digest, v2);
570
571 let v: [u8; DIGEST_BYTES] = (&digest).into();
572 let v2: RpxDigest = (&v).try_into().unwrap();
573 assert_eq!(digest, v2);
574
575 let v: String = (&digest).into();
576 let v2: RpxDigest = (&v).try_into().unwrap();
577 assert_eq!(digest, v2);
578 }
579}