miden_crypto/hash/rescue/rpx/
digest.rs

1use alloc::string::String;
2use core::{cmp::Ordering, fmt::Display, ops::Deref, slice};
3
4use thiserror::Error;
5
6use super::{DIGEST_BYTES, DIGEST_SIZE, Digest, Felt, StarkField, ZERO};
7use crate::{
8    rand::Randomizable,
9    utils::{
10        ByteReader, ByteWriter, Deserializable, DeserializationError, HexParseError, Serializable,
11        bytes_to_hex_string, hex_to_bytes,
12    },
13};
14
15// DIGEST TRAIT IMPLEMENTATIONS
16// ================================================================================================
17
18#[derive(Debug, Default, Copy, Clone, Eq, PartialEq)]
19#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
20#[cfg_attr(feature = "serde", serde(into = "String", try_from = "&str"))]
21pub struct RpxDigest([Felt; DIGEST_SIZE]);
22
23impl RpxDigest {
24    /// The serialized size of the digest in bytes.
25    pub const SERIALIZED_SIZE: usize = DIGEST_BYTES;
26
27    pub const fn new(value: [Felt; DIGEST_SIZE]) -> Self {
28        Self(value)
29    }
30
31    pub fn as_elements(&self) -> &[Felt] {
32        self.as_ref()
33    }
34
35    pub fn as_bytes(&self) -> [u8; DIGEST_BYTES] {
36        <Self as Digest>::as_bytes(self)
37    }
38
39    pub fn digests_as_elements_iter<'a, I>(digests: I) -> impl Iterator<Item = &'a Felt>
40    where
41        I: Iterator<Item = &'a Self>,
42    {
43        digests.flat_map(|d| d.0.iter())
44    }
45
46    pub fn digests_as_elements(digests: &[Self]) -> &[Felt] {
47        let p = digests.as_ptr();
48        let len = digests.len() * DIGEST_SIZE;
49        unsafe { slice::from_raw_parts(p as *const Felt, len) }
50    }
51
52    /// Returns hexadecimal representation of this digest prefixed with `0x`.
53    pub fn to_hex(&self) -> String {
54        bytes_to_hex_string(self.as_bytes())
55    }
56}
57
58impl Digest for RpxDigest {
59    fn as_bytes(&self) -> [u8; DIGEST_BYTES] {
60        let mut result = [0; DIGEST_BYTES];
61
62        result[..8].copy_from_slice(&self.0[0].as_int().to_le_bytes());
63        result[8..16].copy_from_slice(&self.0[1].as_int().to_le_bytes());
64        result[16..24].copy_from_slice(&self.0[2].as_int().to_le_bytes());
65        result[24..].copy_from_slice(&self.0[3].as_int().to_le_bytes());
66
67        result
68    }
69}
70
71impl Deref for RpxDigest {
72    type Target = [Felt; DIGEST_SIZE];
73
74    fn deref(&self) -> &Self::Target {
75        &self.0
76    }
77}
78
79impl Ord for RpxDigest {
80    fn cmp(&self, other: &Self) -> Ordering {
81        // compare the inner u64 of both elements.
82        //
83        // it will iterate the elements and will return the first computation different than
84        // `Equal`. Otherwise, the ordering is equal.
85        //
86        // the endianness is irrelevant here because since, this being a cryptographically secure
87        // hash computation, the digest shouldn't have any ordered property of its input.
88        //
89        // finally, we use `Felt::inner` instead of `Felt::as_int` so we avoid performing a
90        // montgomery reduction for every limb. that is safe because every inner element of the
91        // digest is guaranteed to be in its canonical form (that is, `x in [0,p)`).
92        self.0.iter().map(Felt::inner).zip(other.0.iter().map(Felt::inner)).fold(
93            Ordering::Equal,
94            |ord, (a, b)| match ord {
95                Ordering::Equal => a.cmp(&b),
96                _ => ord,
97            },
98        )
99    }
100}
101
102impl PartialOrd for RpxDigest {
103    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
104        Some(self.cmp(other))
105    }
106}
107
108impl Display for RpxDigest {
109    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
110        let encoded: String = self.into();
111        write!(f, "{}", encoded)?;
112        Ok(())
113    }
114}
115
116impl Randomizable for RpxDigest {
117    const VALUE_SIZE: usize = DIGEST_BYTES;
118
119    fn from_random_bytes(bytes: &[u8]) -> Option<Self> {
120        let bytes_array: Option<[u8; 32]> = bytes.try_into().ok();
121        if let Some(bytes_array) = bytes_array {
122            Self::try_from(bytes_array).ok()
123        } else {
124            None
125        }
126    }
127}
128
129// CONVERSIONS: FROM RPX DIGEST
130// ================================================================================================
131
132#[derive(Debug, Error)]
133pub enum RpxDigestError {
134    #[error("failed to convert digest field element to {0}")]
135    TypeConversion(&'static str),
136    #[error("failed to convert to field element: {0}")]
137    InvalidFieldElement(String),
138}
139
140impl TryFrom<&RpxDigest> for [bool; DIGEST_SIZE] {
141    type Error = RpxDigestError;
142
143    fn try_from(value: &RpxDigest) -> Result<Self, Self::Error> {
144        (*value).try_into()
145    }
146}
147
148impl TryFrom<RpxDigest> for [bool; DIGEST_SIZE] {
149    type Error = RpxDigestError;
150
151    fn try_from(value: RpxDigest) -> Result<Self, Self::Error> {
152        fn to_bool(v: u64) -> Option<bool> {
153            if v <= 1 { Some(v == 1) } else { None }
154        }
155
156        Ok([
157            to_bool(value.0[0].as_int()).ok_or(RpxDigestError::TypeConversion("bool"))?,
158            to_bool(value.0[1].as_int()).ok_or(RpxDigestError::TypeConversion("bool"))?,
159            to_bool(value.0[2].as_int()).ok_or(RpxDigestError::TypeConversion("bool"))?,
160            to_bool(value.0[3].as_int()).ok_or(RpxDigestError::TypeConversion("bool"))?,
161        ])
162    }
163}
164
165impl TryFrom<&RpxDigest> for [u8; DIGEST_SIZE] {
166    type Error = RpxDigestError;
167
168    fn try_from(value: &RpxDigest) -> Result<Self, Self::Error> {
169        (*value).try_into()
170    }
171}
172
173impl TryFrom<RpxDigest> for [u8; DIGEST_SIZE] {
174    type Error = RpxDigestError;
175
176    fn try_from(value: RpxDigest) -> Result<Self, Self::Error> {
177        Ok([
178            value.0[0]
179                .as_int()
180                .try_into()
181                .map_err(|_| RpxDigestError::TypeConversion("u8"))?,
182            value.0[1]
183                .as_int()
184                .try_into()
185                .map_err(|_| RpxDigestError::TypeConversion("u8"))?,
186            value.0[2]
187                .as_int()
188                .try_into()
189                .map_err(|_| RpxDigestError::TypeConversion("u8"))?,
190            value.0[3]
191                .as_int()
192                .try_into()
193                .map_err(|_| RpxDigestError::TypeConversion("u8"))?,
194        ])
195    }
196}
197
198impl TryFrom<&RpxDigest> for [u16; DIGEST_SIZE] {
199    type Error = RpxDigestError;
200
201    fn try_from(value: &RpxDigest) -> Result<Self, Self::Error> {
202        (*value).try_into()
203    }
204}
205
206impl TryFrom<RpxDigest> for [u16; DIGEST_SIZE] {
207    type Error = RpxDigestError;
208
209    fn try_from(value: RpxDigest) -> Result<Self, Self::Error> {
210        Ok([
211            value.0[0]
212                .as_int()
213                .try_into()
214                .map_err(|_| RpxDigestError::TypeConversion("u16"))?,
215            value.0[1]
216                .as_int()
217                .try_into()
218                .map_err(|_| RpxDigestError::TypeConversion("u16"))?,
219            value.0[2]
220                .as_int()
221                .try_into()
222                .map_err(|_| RpxDigestError::TypeConversion("u16"))?,
223            value.0[3]
224                .as_int()
225                .try_into()
226                .map_err(|_| RpxDigestError::TypeConversion("u16"))?,
227        ])
228    }
229}
230
231impl TryFrom<&RpxDigest> for [u32; DIGEST_SIZE] {
232    type Error = RpxDigestError;
233
234    fn try_from(value: &RpxDigest) -> Result<Self, Self::Error> {
235        (*value).try_into()
236    }
237}
238
239impl TryFrom<RpxDigest> for [u32; DIGEST_SIZE] {
240    type Error = RpxDigestError;
241
242    fn try_from(value: RpxDigest) -> Result<Self, Self::Error> {
243        Ok([
244            value.0[0]
245                .as_int()
246                .try_into()
247                .map_err(|_| RpxDigestError::TypeConversion("u32"))?,
248            value.0[1]
249                .as_int()
250                .try_into()
251                .map_err(|_| RpxDigestError::TypeConversion("u32"))?,
252            value.0[2]
253                .as_int()
254                .try_into()
255                .map_err(|_| RpxDigestError::TypeConversion("u32"))?,
256            value.0[3]
257                .as_int()
258                .try_into()
259                .map_err(|_| RpxDigestError::TypeConversion("u32"))?,
260        ])
261    }
262}
263
264impl From<&RpxDigest> for [u64; DIGEST_SIZE] {
265    fn from(value: &RpxDigest) -> Self {
266        (*value).into()
267    }
268}
269
270impl From<RpxDigest> for [u64; DIGEST_SIZE] {
271    fn from(value: RpxDigest) -> Self {
272        [
273            value.0[0].as_int(),
274            value.0[1].as_int(),
275            value.0[2].as_int(),
276            value.0[3].as_int(),
277        ]
278    }
279}
280
281impl From<&RpxDigest> for [Felt; DIGEST_SIZE] {
282    fn from(value: &RpxDigest) -> Self {
283        value.0
284    }
285}
286
287impl From<RpxDigest> for [Felt; DIGEST_SIZE] {
288    fn from(value: RpxDigest) -> Self {
289        value.0
290    }
291}
292
293impl From<&RpxDigest> for [u8; DIGEST_BYTES] {
294    fn from(value: &RpxDigest) -> Self {
295        value.as_bytes()
296    }
297}
298
299impl From<RpxDigest> for [u8; DIGEST_BYTES] {
300    fn from(value: RpxDigest) -> Self {
301        value.as_bytes()
302    }
303}
304
305impl From<&RpxDigest> for String {
306    /// The returned string starts with `0x`.
307    fn from(value: &RpxDigest) -> Self {
308        (*value).into()
309    }
310}
311
312impl From<RpxDigest> for String {
313    /// The returned string starts with `0x`.
314    fn from(value: RpxDigest) -> Self {
315        value.to_hex()
316    }
317}
318
319// CONVERSIONS: TO RPX DIGEST
320// ================================================================================================
321
322impl From<&[bool; DIGEST_SIZE]> for RpxDigest {
323    fn from(value: &[bool; DIGEST_SIZE]) -> Self {
324        (*value).into()
325    }
326}
327
328impl From<[bool; DIGEST_SIZE]> for RpxDigest {
329    fn from(value: [bool; DIGEST_SIZE]) -> Self {
330        [value[0] as u32, value[1] as u32, value[2] as u32, value[3] as u32].into()
331    }
332}
333
334impl From<&[u8; DIGEST_SIZE]> for RpxDigest {
335    fn from(value: &[u8; DIGEST_SIZE]) -> Self {
336        (*value).into()
337    }
338}
339
340impl From<[u8; DIGEST_SIZE]> for RpxDigest {
341    fn from(value: [u8; DIGEST_SIZE]) -> Self {
342        Self([value[0].into(), value[1].into(), value[2].into(), value[3].into()])
343    }
344}
345
346impl From<&[u16; DIGEST_SIZE]> for RpxDigest {
347    fn from(value: &[u16; DIGEST_SIZE]) -> Self {
348        (*value).into()
349    }
350}
351
352impl From<[u16; DIGEST_SIZE]> for RpxDigest {
353    fn from(value: [u16; DIGEST_SIZE]) -> Self {
354        Self([value[0].into(), value[1].into(), value[2].into(), value[3].into()])
355    }
356}
357
358impl From<&[u32; DIGEST_SIZE]> for RpxDigest {
359    fn from(value: &[u32; DIGEST_SIZE]) -> Self {
360        (*value).into()
361    }
362}
363
364impl From<[u32; DIGEST_SIZE]> for RpxDigest {
365    fn from(value: [u32; DIGEST_SIZE]) -> Self {
366        Self([value[0].into(), value[1].into(), value[2].into(), value[3].into()])
367    }
368}
369
370impl TryFrom<&[u64; DIGEST_SIZE]> for RpxDigest {
371    type Error = RpxDigestError;
372
373    fn try_from(value: &[u64; DIGEST_SIZE]) -> Result<Self, RpxDigestError> {
374        (*value).try_into()
375    }
376}
377
378impl TryFrom<[u64; DIGEST_SIZE]> for RpxDigest {
379    type Error = RpxDigestError;
380
381    fn try_from(value: [u64; DIGEST_SIZE]) -> Result<Self, RpxDigestError> {
382        Ok(Self([
383            value[0].try_into().map_err(RpxDigestError::InvalidFieldElement)?,
384            value[1].try_into().map_err(RpxDigestError::InvalidFieldElement)?,
385            value[2].try_into().map_err(RpxDigestError::InvalidFieldElement)?,
386            value[3].try_into().map_err(RpxDigestError::InvalidFieldElement)?,
387        ]))
388    }
389}
390
391impl From<&[Felt; DIGEST_SIZE]> for RpxDigest {
392    fn from(value: &[Felt; DIGEST_SIZE]) -> Self {
393        Self(*value)
394    }
395}
396
397impl From<[Felt; DIGEST_SIZE]> for RpxDigest {
398    fn from(value: [Felt; DIGEST_SIZE]) -> Self {
399        Self(value)
400    }
401}
402
403impl TryFrom<&[u8; DIGEST_BYTES]> for RpxDigest {
404    type Error = HexParseError;
405
406    fn try_from(value: &[u8; DIGEST_BYTES]) -> Result<Self, Self::Error> {
407        (*value).try_into()
408    }
409}
410
411impl TryFrom<[u8; DIGEST_BYTES]> for RpxDigest {
412    type Error = HexParseError;
413
414    fn try_from(value: [u8; DIGEST_BYTES]) -> Result<Self, Self::Error> {
415        // Note: the input length is known, the conversion from slice to array must succeed so the
416        // `unwrap`s below are safe
417        let a = u64::from_le_bytes(value[0..8].try_into().unwrap());
418        let b = u64::from_le_bytes(value[8..16].try_into().unwrap());
419        let c = u64::from_le_bytes(value[16..24].try_into().unwrap());
420        let d = u64::from_le_bytes(value[24..32].try_into().unwrap());
421
422        if [a, b, c, d].iter().any(|v| *v >= Felt::MODULUS) {
423            return Err(HexParseError::OutOfRange);
424        }
425
426        Ok(RpxDigest([Felt::new(a), Felt::new(b), Felt::new(c), Felt::new(d)]))
427    }
428}
429
430impl TryFrom<&[u8]> for RpxDigest {
431    type Error = HexParseError;
432
433    fn try_from(value: &[u8]) -> Result<Self, Self::Error> {
434        (*value).try_into()
435    }
436}
437
438impl TryFrom<&str> for RpxDigest {
439    type Error = HexParseError;
440
441    /// Expects the string to start with `0x`.
442    fn try_from(value: &str) -> Result<Self, Self::Error> {
443        hex_to_bytes::<DIGEST_BYTES>(value).and_then(RpxDigest::try_from)
444    }
445}
446
447impl TryFrom<&String> for RpxDigest {
448    type Error = HexParseError;
449
450    /// Expects the string to start with `0x`.
451    fn try_from(value: &String) -> Result<Self, Self::Error> {
452        value.as_str().try_into()
453    }
454}
455
456impl TryFrom<String> for RpxDigest {
457    type Error = HexParseError;
458
459    /// Expects the string to start with `0x`.
460    fn try_from(value: String) -> Result<Self, Self::Error> {
461        value.as_str().try_into()
462    }
463}
464
465// SERIALIZATION / DESERIALIZATION
466// ================================================================================================
467
468impl Serializable for RpxDigest {
469    fn write_into<W: ByteWriter>(&self, target: &mut W) {
470        target.write_bytes(&self.as_bytes());
471    }
472
473    fn get_size_hint(&self) -> usize {
474        Self::SERIALIZED_SIZE
475    }
476}
477
478impl Deserializable for RpxDigest {
479    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
480        let mut inner: [Felt; DIGEST_SIZE] = [ZERO; DIGEST_SIZE];
481        for inner in inner.iter_mut() {
482            let e = source.read_u64()?;
483            if e >= Felt::MODULUS {
484                return Err(DeserializationError::InvalidValue(String::from(
485                    "Value not in the appropriate range",
486                )));
487            }
488            *inner = Felt::new(e);
489        }
490
491        Ok(Self(inner))
492    }
493}
494
495// ITERATORS
496// ================================================================================================
497impl IntoIterator for RpxDigest {
498    type Item = Felt;
499    type IntoIter = <[Felt; 4] as IntoIterator>::IntoIter;
500
501    fn into_iter(self) -> Self::IntoIter {
502        self.0.into_iter()
503    }
504}
505
506// TESTS
507// ================================================================================================
508
509#[cfg(test)]
510mod tests {
511    use alloc::string::String;
512
513    use rand_utils::rand_value;
514
515    use super::{DIGEST_BYTES, DIGEST_SIZE, Deserializable, Felt, RpxDigest, Serializable};
516    use crate::utils::SliceReader;
517
518    #[test]
519    fn digest_serialization() {
520        let e1 = Felt::new(rand_value());
521        let e2 = Felt::new(rand_value());
522        let e3 = Felt::new(rand_value());
523        let e4 = Felt::new(rand_value());
524
525        let d1 = RpxDigest([e1, e2, e3, e4]);
526
527        let mut bytes = vec![];
528        d1.write_into(&mut bytes);
529        assert_eq!(DIGEST_BYTES, bytes.len());
530        assert_eq!(bytes.len(), d1.get_size_hint());
531
532        let mut reader = SliceReader::new(&bytes);
533        let d2 = RpxDigest::read_from(&mut reader).unwrap();
534
535        assert_eq!(d1, d2);
536    }
537
538    #[test]
539    fn digest_encoding() {
540        let digest = RpxDigest([
541            Felt::new(rand_value()),
542            Felt::new(rand_value()),
543            Felt::new(rand_value()),
544            Felt::new(rand_value()),
545        ]);
546
547        let string: String = digest.into();
548        let round_trip: RpxDigest = string.try_into().expect("decoding failed");
549
550        assert_eq!(digest, round_trip);
551    }
552
553    #[test]
554    fn test_conversions() {
555        let digest = RpxDigest([
556            Felt::new(rand_value()),
557            Felt::new(rand_value()),
558            Felt::new(rand_value()),
559            Felt::new(rand_value()),
560        ]);
561
562        // BY VALUE
563        // ----------------------------------------------------------------------------------------
564        let v: [bool; DIGEST_SIZE] = [true, false, true, true];
565        let v2: RpxDigest = v.into();
566        assert_eq!(v, <[bool; DIGEST_SIZE]>::try_from(v2).unwrap());
567
568        let v: [u8; DIGEST_SIZE] = [0_u8, 1_u8, 2_u8, 3_u8];
569        let v2: RpxDigest = v.into();
570        assert_eq!(v, <[u8; DIGEST_SIZE]>::try_from(v2).unwrap());
571
572        let v: [u16; DIGEST_SIZE] = [0_u16, 1_u16, 2_u16, 3_u16];
573        let v2: RpxDigest = v.into();
574        assert_eq!(v, <[u16; DIGEST_SIZE]>::try_from(v2).unwrap());
575
576        let v: [u32; DIGEST_SIZE] = [0_u32, 1_u32, 2_u32, 3_u32];
577        let v2: RpxDigest = v.into();
578        assert_eq!(v, <[u32; DIGEST_SIZE]>::try_from(v2).unwrap());
579
580        let v: [u64; DIGEST_SIZE] = digest.into();
581        let v2: RpxDigest = v.try_into().unwrap();
582        assert_eq!(digest, v2);
583
584        let v: [Felt; DIGEST_SIZE] = digest.into();
585        let v2: RpxDigest = v.into();
586        assert_eq!(digest, v2);
587
588        let v: [u8; DIGEST_BYTES] = digest.into();
589        let v2: RpxDigest = v.try_into().unwrap();
590        assert_eq!(digest, v2);
591
592        let v: String = digest.into();
593        let v2: RpxDigest = v.try_into().unwrap();
594        assert_eq!(digest, v2);
595
596        // BY REF
597        // ----------------------------------------------------------------------------------------
598        let v: [bool; DIGEST_SIZE] = [true, false, true, true];
599        let v2: RpxDigest = (&v).into();
600        assert_eq!(v, <[bool; DIGEST_SIZE]>::try_from(&v2).unwrap());
601
602        let v: [u8; DIGEST_SIZE] = [0_u8, 1_u8, 2_u8, 3_u8];
603        let v2: RpxDigest = (&v).into();
604        assert_eq!(v, <[u8; DIGEST_SIZE]>::try_from(&v2).unwrap());
605
606        let v: [u16; DIGEST_SIZE] = [0_u16, 1_u16, 2_u16, 3_u16];
607        let v2: RpxDigest = (&v).into();
608        assert_eq!(v, <[u16; DIGEST_SIZE]>::try_from(&v2).unwrap());
609
610        let v: [u32; DIGEST_SIZE] = [0_u32, 1_u32, 2_u32, 3_u32];
611        let v2: RpxDigest = (&v).into();
612        assert_eq!(v, <[u32; DIGEST_SIZE]>::try_from(&v2).unwrap());
613
614        let v: [u64; DIGEST_SIZE] = (&digest).into();
615        let v2: RpxDigest = (&v).try_into().unwrap();
616        assert_eq!(digest, v2);
617
618        let v: [Felt; DIGEST_SIZE] = (&digest).into();
619        let v2: RpxDigest = (&v).into();
620        assert_eq!(digest, v2);
621
622        let v: [u8; DIGEST_BYTES] = (&digest).into();
623        let v2: RpxDigest = (&v).try_into().unwrap();
624        assert_eq!(digest, v2);
625
626        let v: String = (&digest).into();
627        let v2: RpxDigest = (&v).try_into().unwrap();
628        assert_eq!(digest, v2);
629    }
630}
miden_crypto/hash/rescue/rpx/digest.rs

miden_crypto/hash/rescue/rpx/
digest.rs
