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