miden-crypto/src/hash/blake/mod.rs
src/hash/blake/mod.rsRaw
1use super::{Digest, ElementHasher, Felt, FieldElement, Hasher, StarkField};
2use crate::utils::{ByteReader, ByteWriter, Deserializable, DeserializationError, Serializable};
3use core::{
4 mem::{size_of, transmute, transmute_copy},
5 ops::Deref,
6 slice::from_raw_parts,
7};
8
9#[cfg(test)]
10mod tests;
11
12// CONSTANTS
13// ================================================================================================
14
15const DIGEST32_BYTES: usize = 32;
16const DIGEST24_BYTES: usize = 24;
17const DIGEST20_BYTES: usize = 20;
18
19// BLAKE3 N-BIT OUTPUT
20// ================================================================================================
21
22/// N-bytes output of a blake3 function.
23///
24/// Note: `N` can't be greater than `32` because [`Digest::as_bytes`] currently supports only 32
25/// bytes.
26#[derive(Debug, Copy, Clone, Eq, PartialEq)]
27pub struct Blake3Digest<const N: usize>([u8; N]);
28
29impl<const N: usize> Default for Blake3Digest<N> {
30 fn default() -> Self {
31 Self([0; N])
32 }
33}
34
35impl<const N: usize> Deref for Blake3Digest<N> {
36 type Target = [u8];
37
38 fn deref(&self) -> &Self::Target {
39 &self.0
40 }
41}
42
43impl<const N: usize> From<Blake3Digest<N>> for [u8; N] {
44 fn from(value: Blake3Digest<N>) -> Self {
45 value.0
46 }
47}
48
49impl<const N: usize> From<[u8; N]> for Blake3Digest<N> {
50 fn from(value: [u8; N]) -> Self {
51 Self(value)
52 }
53}
54
55impl<const N: usize> Serializable for Blake3Digest<N> {
56 fn write_into<W: ByteWriter>(&self, target: &mut W) {
57 target.write_u8_slice(&self.0);
58 }
59}
60
61impl<const N: usize> Deserializable for Blake3Digest<N> {
62 fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
63 source.read_u8_array().map(Self)
64 }
65}
66
67impl<const N: usize> Digest for Blake3Digest<N> {
68 fn as_bytes(&self) -> [u8; 32] {
69 // compile-time assertion
70 assert!(N <= 32, "digest currently supports only 32 bytes!");
71 expand_bytes(&self.0)
72 }
73}
74
75// BLAKE3 256-BIT OUTPUT
76// ================================================================================================
77
78/// 256-bit output blake3 hasher.
79pub struct Blake3_256;
80
81impl Hasher for Blake3_256 {
82 type Digest = Blake3Digest<32>;
83
84 fn hash(bytes: &[u8]) -> Self::Digest {
85 Blake3Digest(blake3::hash(bytes).into())
86 }
87
88 fn merge(values: &[Self::Digest; 2]) -> Self::Digest {
89 Self::hash(prepare_merge(values))
90 }
91
92 fn merge_with_int(seed: Self::Digest, value: u64) -> Self::Digest {
93 let mut hasher = blake3::Hasher::new();
94 hasher.update(&seed.0);
95 hasher.update(&value.to_le_bytes());
96 Blake3Digest(hasher.finalize().into())
97 }
98}
99
100impl ElementHasher for Blake3_256 {
101 type BaseField = Felt;
102
103 fn hash_elements<E>(elements: &[E]) -> Self::Digest
104 where
105 E: FieldElement<BaseField = Self::BaseField>,
106 {
107 Blake3Digest(hash_elements(elements))
108 }
109}
110
111impl Blake3_256 {
112 /// Returns a hash of the provided sequence of bytes.
113 #[inline(always)]
114 pub fn hash(bytes: &[u8]) -> Blake3Digest<DIGEST32_BYTES> {
115 <Self as Hasher>::hash(bytes)
116 }
117
118 /// Returns a hash of two digests. This method is intended for use in construction of
119 /// Merkle trees and verification of Merkle paths.
120 #[inline(always)]
121 pub fn merge(values: &[Blake3Digest<DIGEST32_BYTES>; 2]) -> Blake3Digest<DIGEST32_BYTES> {
122 <Self as Hasher>::merge(values)
123 }
124
125 /// Returns a hash of the provided field elements.
126 #[inline(always)]
127 pub fn hash_elements<E>(elements: &[E]) -> Blake3Digest<DIGEST32_BYTES>
128 where
129 E: FieldElement<BaseField = Felt>,
130 {
131 <Self as ElementHasher>::hash_elements(elements)
132 }
133}
134
135// BLAKE3 192-BIT OUTPUT
136// ================================================================================================
137
138/// 192-bit output blake3 hasher.
139pub struct Blake3_192;
140
141impl Hasher for Blake3_192 {
142 type Digest = Blake3Digest<24>;
143
144 fn hash(bytes: &[u8]) -> Self::Digest {
145 Blake3Digest(*shrink_bytes(&blake3::hash(bytes).into()))
146 }
147
148 fn merge(values: &[Self::Digest; 2]) -> Self::Digest {
149 Self::hash(prepare_merge(values))
150 }
151
152 fn merge_with_int(seed: Self::Digest, value: u64) -> Self::Digest {
153 let mut hasher = blake3::Hasher::new();
154 hasher.update(&seed.0);
155 hasher.update(&value.to_le_bytes());
156 Blake3Digest(*shrink_bytes(&hasher.finalize().into()))
157 }
158}
159
160impl ElementHasher for Blake3_192 {
161 type BaseField = Felt;
162
163 fn hash_elements<E>(elements: &[E]) -> Self::Digest
164 where
165 E: FieldElement<BaseField = Self::BaseField>,
166 {
167 Blake3Digest(hash_elements(elements))
168 }
169}
170
171impl Blake3_192 {
172 /// Returns a hash of the provided sequence of bytes.
173 #[inline(always)]
174 pub fn hash(bytes: &[u8]) -> Blake3Digest<DIGEST24_BYTES> {
175 <Self as Hasher>::hash(bytes)
176 }
177
178 /// Returns a hash of two digests. This method is intended for use in construction of
179 /// Merkle trees and verification of Merkle paths.
180 #[inline(always)]
181 pub fn merge(values: &[Blake3Digest<DIGEST24_BYTES>; 2]) -> Blake3Digest<DIGEST24_BYTES> {
182 <Self as Hasher>::merge(values)
183 }
184
185 /// Returns a hash of the provided field elements.
186 #[inline(always)]
187 pub fn hash_elements<E>(elements: &[E]) -> Blake3Digest<DIGEST24_BYTES>
188 where
189 E: FieldElement<BaseField = Felt>,
190 {
191 <Self as ElementHasher>::hash_elements(elements)
192 }
193}
194
195// BLAKE3 160-BIT OUTPUT
196// ================================================================================================
197
198/// 160-bit output blake3 hasher.
199pub struct Blake3_160;
200
201impl Hasher for Blake3_160 {
202 type Digest = Blake3Digest<20>;
203
204 fn hash(bytes: &[u8]) -> Self::Digest {
205 Blake3Digest(*shrink_bytes(&blake3::hash(bytes).into()))
206 }
207
208 fn merge(values: &[Self::Digest; 2]) -> Self::Digest {
209 Self::hash(prepare_merge(values))
210 }
211
212 fn merge_with_int(seed: Self::Digest, value: u64) -> Self::Digest {
213 let mut hasher = blake3::Hasher::new();
214 hasher.update(&seed.0);
215 hasher.update(&value.to_le_bytes());
216 Blake3Digest(*shrink_bytes(&hasher.finalize().into()))
217 }
218}
219
220impl ElementHasher for Blake3_160 {
221 type BaseField = Felt;
222
223 fn hash_elements<E>(elements: &[E]) -> Self::Digest
224 where
225 E: FieldElement<BaseField = Self::BaseField>,
226 {
227 Blake3Digest(hash_elements(elements))
228 }
229}
230
231impl Blake3_160 {
232 /// Returns a hash of the provided sequence of bytes.
233 #[inline(always)]
234 pub fn hash(bytes: &[u8]) -> Blake3Digest<DIGEST20_BYTES> {
235 <Self as Hasher>::hash(bytes)
236 }
237
238 /// Returns a hash of two digests. This method is intended for use in construction of
239 /// Merkle trees and verification of Merkle paths.
240 #[inline(always)]
241 pub fn merge(values: &[Blake3Digest<DIGEST20_BYTES>; 2]) -> Blake3Digest<DIGEST20_BYTES> {
242 <Self as Hasher>::merge(values)
243 }
244
245 /// Returns a hash of the provided field elements.
246 #[inline(always)]
247 pub fn hash_elements<E>(elements: &[E]) -> Blake3Digest<DIGEST20_BYTES>
248 where
249 E: FieldElement<BaseField = Felt>,
250 {
251 <Self as ElementHasher>::hash_elements(elements)
252 }
253}
254
255// HELPER FUNCTIONS
256// ================================================================================================
257
258/// Zero-copy ref shrink to array.
259fn shrink_bytes<const M: usize, const N: usize>(bytes: &[u8; M]) -> &[u8; N] {
260 // compile-time assertion
261 assert!(
262 M >= N,
263 "N should fit in M so it can be safely transmuted into a smaller slice!"
264 );
265 // safety: bytes len is asserted
266 unsafe { transmute(bytes) }
267}
268
269/// Hash the elements into bytes and shrink the output.
270fn hash_elements<const N: usize, E>(elements: &[E]) -> [u8; N]
271where
272 E: FieldElement<BaseField = Felt>,
273{
274 // don't leak assumptions from felt and check its actual implementation.
275 // this is a compile-time branch so it is for free
276 let digest = if Felt::IS_CANONICAL {
277 blake3::hash(E::elements_as_bytes(elements))
278 } else {
279 let blen = elements.len() << 3;
280 let mut bytes = vec![0u8; blen];
281
282 for (idx, element) in E::as_base_elements(elements).iter().enumerate() {
283 bytes[idx * 8..(idx + 1) * 8].copy_from_slice(&element.as_int().to_le_bytes());
284 }
285
286 let mut hasher = blake3::Hasher::new();
287 hasher.update(&bytes);
288 hasher.finalize()
289 };
290 *shrink_bytes(&digest.into())
291}
292
293/// Owned bytes expansion.
294fn expand_bytes<const M: usize, const N: usize>(bytes: &[u8; M]) -> [u8; N] {
295 // compile-time assertion
296 assert!(M <= N, "M should fit in N so M can be expanded!");
297 // this branch is constant so it will be optimized to be either one of the variants in release
298 // mode
299 if M == N {
300 // safety: the sizes are checked to be the same
301 unsafe { transmute_copy(bytes) }
302 } else {
303 let mut expanded = [0u8; N];
304 expanded[..M].copy_from_slice(bytes);
305 expanded
306 }
307}
308
309// Cast the slice into contiguous bytes.
310fn prepare_merge<const N: usize, D>(args: &[D; N]) -> &[u8]
311where
312 D: Deref<Target = [u8]>,
313{
314 // compile-time assertion
315 assert!(N > 0, "N shouldn't represent an empty slice!");
316 let values = args.as_ptr() as *const u8;
317 let len = size_of::<D>() * N;
318 // safety: the values are tested to be contiguous
319 let bytes = unsafe { from_raw_parts(values, len) };
320 debug_assert_eq!(args[0].deref(), &bytes[..len / N]);
321 bytes
322}