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