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};
7
8/// The number of bytes needed to encoded a digest
9pub const DIGEST_BYTES: usize = 32;
10
11// DIGEST TRAIT IMPLEMENTATIONS
12// ================================================================================================
13
14#[derive(Debug, Default, Copy, Clone, Eq, PartialEq)]
15#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
16#[cfg_attr(feature = "serde", serde(into = "String", try_from = "&str"))]
17pub struct RpoDigest([Felt; DIGEST_SIZE]);
18
19impl RpoDigest {
20 pub const fn new(value: [Felt; DIGEST_SIZE]) -> Self {
21 Self(value)
22 }
23
24 pub fn as_elements(&self) -> &[Felt] {
25 self.as_ref()
26 }
27
28 pub fn as_bytes(&self) -> [u8; DIGEST_BYTES] {
29 <Self as Digest>::as_bytes(self)
30 }
31
32 pub fn digests_as_elements<'a, I>(digests: I) -> impl Iterator<Item = &'a Felt>
33 where
34 I: Iterator<Item = &'a Self>,
35 {
36 digests.flat_map(|d| d.0.iter())
37 }
38}
39
40impl Digest for RpoDigest {
41 fn as_bytes(&self) -> [u8; DIGEST_BYTES] {
42 let mut result = [0; DIGEST_BYTES];
43
44 result[..8].copy_from_slice(&self.0[0].as_int().to_le_bytes());
45 result[8..16].copy_from_slice(&self.0[1].as_int().to_le_bytes());
46 result[16..24].copy_from_slice(&self.0[2].as_int().to_le_bytes());
47 result[24..].copy_from_slice(&self.0[3].as_int().to_le_bytes());
48
49 result
50 }
51}
52
53impl Deref for RpoDigest {
54 type Target = [Felt; DIGEST_SIZE];
55
56 fn deref(&self) -> &Self::Target {
57 &self.0
58 }
59}
60
61impl Ord for RpoDigest {
62 fn cmp(&self, other: &Self) -> Ordering {
63 // compare the inner u64 of both elements.
64 //
65 // it will iterate the elements and will return the first computation different than
66 // `Equal`. Otherwise, the ordering is equal.
67 //
68 // the endianness is irrelevant here because since, this being a cryptographically secure
69 // hash computation, the digest shouldn't have any ordered property of its input.
70 //
71 // finally, we use `Felt::inner` instead of `Felt::as_int` so we avoid performing a
72 // montgomery reduction for every limb. that is safe because every inner element of the
73 // digest is guaranteed to be in its canonical form (that is, `x in [0,p)`).
74 self.0.iter().map(Felt::inner).zip(other.0.iter().map(Felt::inner)).fold(
75 Ordering::Equal,
76 |ord, (a, b)| match ord {
77 Ordering::Equal => a.cmp(&b),
78 _ => ord,
79 },
80 )
81 }
82}
83
84impl PartialOrd for RpoDigest {
85 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
86 Some(self.cmp(other))
87 }
88}
89
90impl Display for RpoDigest {
91 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
92 let encoded: String = self.into();
93 write!(f, "{}", encoded)?;
94 Ok(())
95 }
96}
97
98// CONVERSIONS: FROM RPO DIGEST
99// ================================================================================================
100
101impl From<&RpoDigest> for [Felt; DIGEST_SIZE] {
102 fn from(value: &RpoDigest) -> Self {
103 value.0
104 }
105}
106
107impl From<RpoDigest> for [Felt; DIGEST_SIZE] {
108 fn from(value: RpoDigest) -> Self {
109 value.0
110 }
111}
112
113impl From<&RpoDigest> for [u64; DIGEST_SIZE] {
114 fn from(value: &RpoDigest) -> Self {
115 [
116 value.0[0].as_int(),
117 value.0[1].as_int(),
118 value.0[2].as_int(),
119 value.0[3].as_int(),
120 ]
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 [u8; DIGEST_BYTES] {
136 fn from(value: &RpoDigest) -> Self {
137 value.as_bytes()
138 }
139}
140
141impl From<RpoDigest> for [u8; DIGEST_BYTES] {
142 fn from(value: RpoDigest) -> Self {
143 value.as_bytes()
144 }
145}
146
147impl From<RpoDigest> for String {
148 /// The returned string starts with `0x`.
149 fn from(value: RpoDigest) -> Self {
150 bytes_to_hex_string(value.as_bytes())
151 }
152}
153
154impl From<&RpoDigest> for String {
155 /// The returned string starts with `0x`.
156 fn from(value: &RpoDigest) -> Self {
157 (*value).into()
158 }
159}
160
161// CONVERSIONS: TO DIGEST
162// ================================================================================================
163
164impl From<[Felt; DIGEST_SIZE]> for RpoDigest {
165 fn from(value: [Felt; DIGEST_SIZE]) -> Self {
166 Self(value)
167 }
168}
169
170impl TryFrom<[u8; DIGEST_BYTES]> for RpoDigest {
171 type Error = HexParseError;
172
173 fn try_from(value: [u8; DIGEST_BYTES]) -> Result<Self, Self::Error> {
174 // Note: the input length is known, the conversion from slice to array must succeed so the
175 // `unwrap`s below are safe
176 let a = u64::from_le_bytes(value[0..8].try_into().unwrap());
177 let b = u64::from_le_bytes(value[8..16].try_into().unwrap());
178 let c = u64::from_le_bytes(value[16..24].try_into().unwrap());
179 let d = u64::from_le_bytes(value[24..32].try_into().unwrap());
180
181 if [a, b, c, d].iter().any(|v| *v >= Felt::MODULUS) {
182 return Err(HexParseError::OutOfRange);
183 }
184
185 Ok(RpoDigest([Felt::new(a), Felt::new(b), Felt::new(c), Felt::new(d)]))
186 }
187}
188
189impl TryFrom<&str> for RpoDigest {
190 type Error = HexParseError;
191
192 /// Expects the string to start with `0x`.
193 fn try_from(value: &str) -> Result<Self, Self::Error> {
194 hex_to_bytes(value).and_then(|v| v.try_into())
195 }
196}
197
198impl TryFrom<String> for RpoDigest {
199 type Error = HexParseError;
200
201 /// Expects the string to start with `0x`.
202 fn try_from(value: String) -> Result<Self, Self::Error> {
203 value.as_str().try_into()
204 }
205}
206
207impl TryFrom<&String> for RpoDigest {
208 type Error = HexParseError;
209
210 /// Expects the string to start with `0x`.
211 fn try_from(value: &String) -> Result<Self, Self::Error> {
212 value.as_str().try_into()
213 }
214}
215
216// SERIALIZATION / DESERIALIZATION
217// ================================================================================================
218
219impl Serializable for RpoDigest {
220 fn write_into<W: ByteWriter>(&self, target: &mut W) {
221 target.write_bytes(&self.as_bytes());
222 }
223}
224
225impl Deserializable for RpoDigest {
226 fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
227 let mut inner: [Felt; DIGEST_SIZE] = [ZERO; DIGEST_SIZE];
228 for inner in inner.iter_mut() {
229 let e = source.read_u64()?;
230 if e >= Felt::MODULUS {
231 return Err(DeserializationError::InvalidValue(String::from(
232 "Value not in the appropriate range",
233 )));
234 }
235 *inner = Felt::new(e);
236 }
237
238 Ok(Self(inner))
239 }
240}
241
242// TESTS
243// ================================================================================================
244
245#[cfg(test)]
246mod tests {
247 use super::{Deserializable, Felt, RpoDigest, Serializable, DIGEST_BYTES};
248 use crate::utils::SliceReader;
249 use rand_utils::rand_value;
250
251 #[test]
252 fn digest_serialization() {
253 let e1 = Felt::new(rand_value());
254 let e2 = Felt::new(rand_value());
255 let e3 = Felt::new(rand_value());
256 let e4 = Felt::new(rand_value());
257
258 let d1 = RpoDigest([e1, e2, e3, e4]);
259
260 let mut bytes = vec![];
261 d1.write_into(&mut bytes);
262 assert_eq!(DIGEST_BYTES, bytes.len());
263
264 let mut reader = SliceReader::new(&bytes);
265 let d2 = RpoDigest::read_from(&mut reader).unwrap();
266
267 assert_eq!(d1, d2);
268 }
269
270 #[cfg(feature = "std")]
271 #[test]
272 fn digest_encoding() {
273 let digest = RpoDigest([
274 Felt::new(rand_value()),
275 Felt::new(rand_value()),
276 Felt::new(rand_value()),
277 Felt::new(rand_value()),
278 ]);
279
280 let string: String = digest.into();
281 let round_trip: RpoDigest = string.try_into().expect("decoding failed");
282
283 assert_eq!(digest, round_trip);
284 }
285}