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