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