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