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