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_bytes(&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_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.
79#[derive(Debug, Copy, Clone, Eq, PartialEq)]
80pub struct Blake3_256;
81
82impl Hasher for Blake3_256 {
83 /// Blake3 collision resistance is 128-bits for 32-bytes output.
84 const COLLISION_RESISTANCE: u32 = 128;
85
86 type Digest = Blake3Digest<32>;
87
88 fn hash(bytes: &[u8]) -> Self::Digest {
89 Blake3Digest(blake3::hash(bytes).into())
90 }
91
92 fn merge(values: &[Self::Digest; 2]) -> Self::Digest {
93 Self::hash(prepare_merge(values))
94 }
95
96 fn merge_with_int(seed: Self::Digest, value: u64) -> Self::Digest {
97 let mut hasher = blake3::Hasher::new();
98 hasher.update(&seed.0);
99 hasher.update(&value.to_le_bytes());
100 Blake3Digest(hasher.finalize().into())
101 }
102}
103
104impl ElementHasher for Blake3_256 {
105 type BaseField = Felt;
106
107 fn hash_elements<E>(elements: &[E]) -> Self::Digest
108 where
109 E: FieldElement<BaseField = Self::BaseField>,
110 {
111 Blake3Digest(hash_elements(elements))
112 }
113}
114
115impl Blake3_256 {
116 /// Returns a hash of the provided sequence of bytes.
117 #[inline(always)]
118 pub fn hash(bytes: &[u8]) -> Blake3Digest<DIGEST32_BYTES> {
119 <Self as Hasher>::hash(bytes)
120 }
121
122 /// Returns a hash of two digests. This method is intended for use in construction of
123 /// Merkle trees and verification of Merkle paths.
124 #[inline(always)]
125 pub fn merge(values: &[Blake3Digest<DIGEST32_BYTES>; 2]) -> Blake3Digest<DIGEST32_BYTES> {
126 <Self as Hasher>::merge(values)
127 }
128
129 /// Returns a hash of the provided field elements.
130 #[inline(always)]
131 pub fn hash_elements<E>(elements: &[E]) -> Blake3Digest<DIGEST32_BYTES>
132 where
133 E: FieldElement<BaseField = Felt>,
134 {
135 <Self as ElementHasher>::hash_elements(elements)
136 }
137}
138
139// BLAKE3 192-BIT OUTPUT
140// ================================================================================================
141
142/// 192-bit output blake3 hasher.
143#[derive(Debug, Copy, Clone, Eq, PartialEq)]
144pub struct Blake3_192;
145
146impl Hasher for Blake3_192 {
147 /// Blake3 collision resistance is 96-bits for 24-bytes output.
148 const COLLISION_RESISTANCE: u32 = 96;
149
150 type Digest = Blake3Digest<24>;
151
152 fn hash(bytes: &[u8]) -> Self::Digest {
153 Blake3Digest(*shrink_bytes(&blake3::hash(bytes).into()))
154 }
155
156 fn merge(values: &[Self::Digest; 2]) -> Self::Digest {
157 Self::hash(prepare_merge(values))
158 }
159
160 fn merge_with_int(seed: Self::Digest, value: u64) -> Self::Digest {
161 let mut hasher = blake3::Hasher::new();
162 hasher.update(&seed.0);
163 hasher.update(&value.to_le_bytes());
164 Blake3Digest(*shrink_bytes(&hasher.finalize().into()))
165 }
166}
167
168impl ElementHasher for Blake3_192 {
169 type BaseField = Felt;
170
171 fn hash_elements<E>(elements: &[E]) -> Self::Digest
172 where
173 E: FieldElement<BaseField = Self::BaseField>,
174 {
175 Blake3Digest(hash_elements(elements))
176 }
177}
178
179impl Blake3_192 {
180 /// Returns a hash of the provided sequence of bytes.
181 #[inline(always)]
182 pub fn hash(bytes: &[u8]) -> Blake3Digest<DIGEST24_BYTES> {
183 <Self as Hasher>::hash(bytes)
184 }
185
186 /// Returns a hash of two digests. This method is intended for use in construction of
187 /// Merkle trees and verification of Merkle paths.
188 #[inline(always)]
189 pub fn merge(values: &[Blake3Digest<DIGEST24_BYTES>; 2]) -> Blake3Digest<DIGEST24_BYTES> {
190 <Self as Hasher>::merge(values)
191 }
192
193 /// Returns a hash of the provided field elements.
194 #[inline(always)]
195 pub fn hash_elements<E>(elements: &[E]) -> Blake3Digest<DIGEST24_BYTES>
196 where
197 E: FieldElement<BaseField = Felt>,
198 {
199 <Self as ElementHasher>::hash_elements(elements)
200 }
201}
202
203// BLAKE3 160-BIT OUTPUT
204// ================================================================================================
205
206/// 160-bit output blake3 hasher.
207#[derive(Debug, Copy, Clone, Eq, PartialEq)]
208pub struct Blake3_160;
209
210impl Hasher for Blake3_160 {
211 /// Blake3 collision resistance is 80-bits for 20-bytes output.
212 const COLLISION_RESISTANCE: u32 = 80;
213
214 type Digest = Blake3Digest<20>;
215
216 fn hash(bytes: &[u8]) -> Self::Digest {
217 Blake3Digest(*shrink_bytes(&blake3::hash(bytes).into()))
218 }
219
220 fn merge(values: &[Self::Digest; 2]) -> Self::Digest {
221 Self::hash(prepare_merge(values))
222 }
223
224 fn merge_with_int(seed: Self::Digest, value: u64) -> Self::Digest {
225 let mut hasher = blake3::Hasher::new();
226 hasher.update(&seed.0);
227 hasher.update(&value.to_le_bytes());
228 Blake3Digest(*shrink_bytes(&hasher.finalize().into()))
229 }
230}
231
232impl ElementHasher for Blake3_160 {
233 type BaseField = Felt;
234
235 fn hash_elements<E>(elements: &[E]) -> Self::Digest
236 where
237 E: FieldElement<BaseField = Self::BaseField>,
238 {
239 Blake3Digest(hash_elements(elements))
240 }
241}
242
243impl Blake3_160 {
244 /// Returns a hash of the provided sequence of bytes.
245 #[inline(always)]
246 pub fn hash(bytes: &[u8]) -> Blake3Digest<DIGEST20_BYTES> {
247 <Self as Hasher>::hash(bytes)
248 }
249
250 /// Returns a hash of two digests. This method is intended for use in construction of
251 /// Merkle trees and verification of Merkle paths.
252 #[inline(always)]
253 pub fn merge(values: &[Blake3Digest<DIGEST20_BYTES>; 2]) -> Blake3Digest<DIGEST20_BYTES> {
254 <Self as Hasher>::merge(values)
255 }
256
257 /// Returns a hash of the provided field elements.
258 #[inline(always)]
259 pub fn hash_elements<E>(elements: &[E]) -> Blake3Digest<DIGEST20_BYTES>
260 where
261 E: FieldElement<BaseField = Felt>,
262 {
263 <Self as ElementHasher>::hash_elements(elements)
264 }
265}
266
267// HELPER FUNCTIONS
268// ================================================================================================
269
270/// Zero-copy ref shrink to array.
271fn shrink_bytes<const M: usize, const N: usize>(bytes: &[u8; M]) -> &[u8; N] {
272 // compile-time assertion
273 assert!(M >= N, "N should fit in M so it can be safely transmuted into a smaller slice!");
274 // safety: bytes len is asserted
275 unsafe { transmute(bytes) }
276}
277
278/// Hash the elements into bytes and shrink the output.
279fn hash_elements<const N: usize, E>(elements: &[E]) -> [u8; N]
280where
281 E: FieldElement<BaseField = Felt>,
282{
283 // don't leak assumptions from felt and check its actual implementation.
284 // this is a compile-time branch so it is for free
285 let digest = if Felt::IS_CANONICAL {
286 blake3::hash(E::elements_as_bytes(elements))
287 } else {
288 let mut hasher = blake3::Hasher::new();
289
290 // BLAKE3 state is 64 bytes - so, we can absorb 64 bytes into the state in a single
291 // permutation. we move the elements into the hasher via the buffer to give the CPU
292 // a chance to process multiple element-to-byte conversions in parallel
293 let mut buf = [0_u8; 64];
294 let mut chunk_iter = E::slice_as_base_elements(elements).chunks_exact(8);
295 for chunk in chunk_iter.by_ref() {
296 for i in 0..8 {
297 buf[i * 8..(i + 1) * 8].copy_from_slice(&chunk[i].as_int().to_le_bytes());
298 }
299 hasher.update(&buf);
300 }
301
302 for element in chunk_iter.remainder() {
303 hasher.update(&element.as_int().to_le_bytes());
304 }
305
306 hasher.finalize()
307 };
308 *shrink_bytes(&digest.into())
309}
310
311/// Owned bytes expansion.
312fn expand_bytes<const M: usize, const N: usize>(bytes: &[u8; M]) -> [u8; N] {
313 // compile-time assertion
314 assert!(M <= N, "M should fit in N so M can be expanded!");
315 // this branch is constant so it will be optimized to be either one of the variants in release
316 // mode
317 if M == N {
318 // safety: the sizes are checked to be the same
319 unsafe { transmute_copy(bytes) }
320 } else {
321 let mut expanded = [0u8; N];
322 expanded[..M].copy_from_slice(bytes);
323 expanded
324 }
325}
326
327// Cast the slice into contiguous bytes.
328fn prepare_merge<const N: usize, D>(args: &[D; N]) -> &[u8]
329where
330 D: Deref<Target = [u8]>,
331{
332 // compile-time assertion
333 assert!(N > 0, "N shouldn't represent an empty slice!");
334 let values = args.as_ptr() as *const u8;
335 let len = size_of::<D>() * N;
336 // safety: the values are tested to be contiguous
337 let bytes = unsafe { from_raw_parts(values, len) };
338 debug_assert_eq!(args[0].deref(), &bytes[..len / N]);
339 bytes
340}