grove
grove/src/blake3.rs
at @3
1//! BLAKE3, the hash behind every object id.
2//!
3//! A direct implementation of the BLAKE3 specification (portable, single-threaded), checked
4//! against the official test vectors below. Only the default hash mode is needed.
5
6const OUT_LEN: usize = 32;
7const BLOCK_LEN: usize = 64;
8const CHUNK_LEN: usize = 1024;
9
10const CHUNK_START: u32 = 1 << 0;
11const CHUNK_END: u32 = 1 << 1;
12const PARENT: u32 = 1 << 2;
13const ROOT: u32 = 1 << 3;
14
15const IV: [u32; 8] = [
16 0x6A09E667, 0xBB67AE85, 0x3C6EF372, 0xA54FF53A, 0x510E527F, 0x9B05688C, 0x1F83D9AB, 0x5BE0CD19,
17];
18
19const MSG_PERMUTATION: [usize; 16] = [2, 6, 3, 10, 7, 0, 4, 13, 1, 11, 12, 5, 9, 14, 15, 8];
20
21#[inline(always)]
22fn g(state: &mut [u32; 16], a: usize, b: usize, c: usize, d: usize, mx: u32, my: u32) {
23 state[a] = state[a].wrapping_add(state[b]).wrapping_add(mx);
24 state[d] = (state[d] ^ state[a]).rotate_right(16);
25 state[c] = state[c].wrapping_add(state[d]);
26 state[b] = (state[b] ^ state[c]).rotate_right(12);
27 state[a] = state[a].wrapping_add(state[b]).wrapping_add(my);
28 state[d] = (state[d] ^ state[a]).rotate_right(8);
29 state[c] = state[c].wrapping_add(state[d]);
30 state[b] = (state[b] ^ state[c]).rotate_right(7);
31}
32
33#[inline(always)]
34fn round(state: &mut [u32; 16], m: &[u32; 16]) {
35 // Columns.
36 g(state, 0, 4, 8, 12, m[0], m[1]);
37 g(state, 1, 5, 9, 13, m[2], m[3]);
38 g(state, 2, 6, 10, 14, m[4], m[5]);
39 g(state, 3, 7, 11, 15, m[6], m[7]);
40 // Diagonals.
41 g(state, 0, 5, 10, 15, m[8], m[9]);
42 g(state, 1, 6, 11, 12, m[10], m[11]);
43 g(state, 2, 7, 8, 13, m[12], m[13]);
44 g(state, 3, 4, 9, 14, m[14], m[15]);
45}
46
47fn permute(m: &mut [u32; 16]) {
48 let mut permuted = [0; 16];
49 for i in 0..16 {
50 permuted[i] = m[MSG_PERMUTATION[i]];
51 }
52 *m = permuted;
53}
54
55fn compress(cv: &[u32; 8], block_words: &[u32; 16], counter: u64, block_len: u32, flags: u32) -> [u32; 16] {
56 let mut state = [
57 cv[0], cv[1], cv[2], cv[3], cv[4], cv[5], cv[6], cv[7],
58 IV[0], IV[1], IV[2], IV[3],
59 counter as u32, (counter >> 32) as u32, block_len, flags,
60 ];
61 let mut block = *block_words;
62 for r in 0..7 {
63 round(&mut state, &block);
64 if r < 6 {
65 permute(&mut block);
66 }
67 }
68 for i in 0..8 {
69 state[i] ^= state[i + 8];
70 state[i + 8] ^= cv[i];
71 }
72 state
73}
74
75fn first_8_words(w: [u32; 16]) -> [u32; 8] {
76 let mut out = [0; 8];
77 out.copy_from_slice(&w[..8]);
78 out
79}
80
81fn words_from_le_bytes(bytes: &[u8; BLOCK_LEN]) -> [u32; 16] {
82 let mut words = [0; 16];
83 for (word, chunk) in words.iter_mut().zip(bytes.chunks_exact(4)) {
84 *word = u32::from_le_bytes([chunk[0], chunk[1], chunk[2], chunk[3]]);
85 }
86 words
87}
88
89struct Output {
90 input_cv: [u32; 8],
91 block_words: [u32; 16],
92 counter: u64,
93 block_len: u32,
94 flags: u32,
95}
96
97impl Output {
98 fn chaining_value(&self) -> [u32; 8] {
99 first_8_words(compress(&self.input_cv, &self.block_words, self.counter, self.block_len, self.flags))
100 }
101
102 fn root_hash(&self) -> [u8; OUT_LEN] {
103 let words = compress(&self.input_cv, &self.block_words, 0, self.block_len, self.flags | ROOT);
104 let mut out = [0u8; OUT_LEN];
105 for (i, word) in words[..8].iter().enumerate() {
106 out[i * 4..i * 4 + 4].copy_from_slice(&word.to_le_bytes());
107 }
108 out
109 }
110}
111
112struct ChunkState {
113 cv: [u32; 8],
114 chunk_counter: u64,
115 block: [u8; BLOCK_LEN],
116 block_len: usize,
117 blocks_compressed: usize,
118}
119
120impl ChunkState {
121 fn new(chunk_counter: u64) -> Self {
122 ChunkState { cv: IV, chunk_counter, block: [0; BLOCK_LEN], block_len: 0, blocks_compressed: 0 }
123 }
124
125 fn len(&self) -> usize {
126 BLOCK_LEN * self.blocks_compressed + self.block_len
127 }
128
129 fn start_flag(&self) -> u32 {
130 if self.blocks_compressed == 0 { CHUNK_START } else { 0 }
131 }
132
133 fn update(&mut self, mut input: &[u8]) {
134 while !input.is_empty() {
135 // A full block is only compressed once more input arrives, so the last block of the
136 // chunk is still here when output() needs it.
137 if self.block_len == BLOCK_LEN {
138 let words = words_from_le_bytes(&self.block);
139 self.cv = first_8_words(compress(&self.cv, &words, self.chunk_counter, BLOCK_LEN as u32, self.start_flag()));
140 self.blocks_compressed += 1;
141 self.block = [0; BLOCK_LEN];
142 self.block_len = 0;
143 }
144 let take = (BLOCK_LEN - self.block_len).min(input.len());
145 self.block[self.block_len..self.block_len + take].copy_from_slice(&input[..take]);
146 self.block_len += take;
147 input = &input[take..];
148 }
149 }
150
151 fn output(&self) -> Output {
152 Output {
153 input_cv: self.cv,
154 block_words: words_from_le_bytes(&self.block),
155 counter: self.chunk_counter,
156 block_len: self.block_len as u32,
157 flags: self.start_flag() | CHUNK_END,
158 }
159 }
160}
161
162fn parent_output(left: [u32; 8], right: [u32; 8]) -> Output {
163 let mut block_words = [0; 16];
164 block_words[..8].copy_from_slice(&left);
165 block_words[8..].copy_from_slice(&right);
166 Output { input_cv: IV, block_words, counter: 0, block_len: BLOCK_LEN as u32, flags: PARENT }
167}
168
169/// Incremental BLAKE3 hasher.
170pub struct Hasher {
171 chunk: ChunkState,
172 cv_stack: [[u32; 8]; 54], // enough for 2^54 chunks
173 cv_stack_len: usize,
174}
175
176impl Default for Hasher {
177 fn default() -> Self {
178 Self::new()
179 }
180}
181
182impl Hasher {
183 pub fn new() -> Self {
184 Hasher { chunk: ChunkState::new(0), cv_stack: [[0; 8]; 54], cv_stack_len: 0 }
185 }
186
187 fn push(&mut self, cv: [u32; 8]) {
188 self.cv_stack[self.cv_stack_len] = cv;
189 self.cv_stack_len += 1;
190 }
191
192 fn pop(&mut self) -> [u32; 8] {
193 self.cv_stack_len -= 1;
194 self.cv_stack[self.cv_stack_len]
195 }
196
197 // Merge completed subtrees: one merge per trailing zero bit of the chunk count.
198 fn add_chunk_cv(&mut self, mut cv: [u32; 8], mut total_chunks: u64) {
199 while total_chunks & 1 == 0 {
200 cv = parent_output(self.pop(), cv).chaining_value();
201 total_chunks >>= 1;
202 }
203 self.push(cv);
204 }
205
206 pub fn update(&mut self, mut input: &[u8]) -> &mut Self {
207 while !input.is_empty() {
208 if self.chunk.len() == CHUNK_LEN {
209 let cv = self.chunk.output().chaining_value();
210 let total = self.chunk.chunk_counter + 1;
211 self.add_chunk_cv(cv, total);
212 self.chunk = ChunkState::new(total);
213 }
214 let take = (CHUNK_LEN - self.chunk.len()).min(input.len());
215 self.chunk.update(&input[..take]);
216 input = &input[take..];
217 }
218 self
219 }
220
221 pub fn finalize(&self) -> [u8; OUT_LEN] {
222 let mut output = self.chunk.output();
223 let mut i = self.cv_stack_len;
224 while i > 0 {
225 i -= 1;
226 output = parent_output(self.cv_stack[i], output.chaining_value());
227 }
228 output.root_hash()
229 }
230}
231
232/// The BLAKE3 hash of `input`.
233pub fn hash(input: &[u8]) -> [u8; OUT_LEN] {
234 let mut h = Hasher::new();
235 h.update(input);
236 h.finalize()
237}
238
239#[cfg(test)]
240mod tests {
241 use super::*;
242 use crate::hex;
243
244 // From the official test_vectors.json: input is bytes 0, 1, 2, … 250, 0, 1, … of each length.
245 const VECTORS: &[(usize, &str)] = &[
246 (0, "af1349b9f5f9a1a6a0404dea36dcc9499bcb25c9adc112b7cc9a93cae41f3262"),
247 (1, "2d3adedff11b61f14c886e35afa036736dcd87a74d27b5c1510225d0f592e213"),
248 (63, "e9bc37a594daad83be9470df7f7b3798297c3d834ce80ba85d6e207627b7db7b"),
249 (64, "4eed7141ea4a5cd4b788606bd23f46e212af9cacebacdc7d1f4c6dc7f2511b98"),
250 (65, "de1e5fa0be70df6d2be8fffd0e99ceaa8eb6e8c93a63f2d8d1c30ecb6b263dee"),
251 (1023, "10108970eeda3eb932baac1428c7a2163b0e924c9a9e25b35bba72b28f70bd11"),
252 (1024, "42214739f095a406f3fc83deb889744ac00df831c10daa55189b5d121c855af7"),
253 (1025, "d00278ae47eb27b34faecf67b4fe263f82d5412916c1ffd97c8cb7fb814b8444"),
254 (2048, "e776b6028c7cd22a4d0ba182a8bf62205d2ef576467e838ed6f2529b85fba24a"),
255 (2049, "5f4d72f40d7a5f82b15ca2b2e44b1de3c2ef86c426c95c1af0b6879522563030"),
256 (3072, "b98cb0ff3623be03326b373de6b9095218513e64f1ee2edd2525c7ad1e5cffd2"),
257 (3073, "7124b49501012f81cc7f11ca069ec9226cecb8a2c850cfe644e327d22d3e1cd3"),
258 (4096, "015094013f57a5277b59d8475c0501042c0b642e531b0a1c8f58d2163229e969"),
259 (4097, "9b4052b38f1c5fc8b1f9ff7ac7b27cd242487b3d890d15c96a1c25b8aa0fb995"),
260 (8192, "aae792484c8efe4f19e2ca7d371d8c467ffb10748d8a5a1ae579948f718a2a63"),
261 (8193, "bab6c09cb8ce8cf459261398d2e7aef35700bf488116ceb94a36d0f5f1b7bc3b"),
262 (16384, "f875d6646de28985646f34ee13be9a576fd515f76b5b0a26bb324735041ddde4"),
263 (31744, "62b6960e1a44bcc1eb1a611a8d6235b6b4b78f32e7abc4fb4c6cdcce94895c47"),
264 (102400, "bc3e3d41a1146b069abffad3c0d44860cf664390afce4d9661f7902e7943e085"),
265 ];
266
267 fn input(len: usize) -> Vec<u8> {
268 (0..len).map(|i| (i % 251) as u8).collect()
269 }
270
271 #[test]
272 fn official_vectors() {
273 for &(len, expected) in VECTORS {
274 assert_eq!(hex::encode(&hash(&input(len))), expected, "length {len}");
275 }
276 }
277
278 #[test]
279 fn incremental_matches_one_shot() {
280 let data = input(102400);
281 for split in [1, 63, 64, 65, 1023, 1024, 1025, 4097, 50000] {
282 let mut h = Hasher::new();
283 for piece in data.chunks(split) {
284 h.update(piece);
285 }
286 assert_eq!(h.finalize(), hash(&data), "pieces of {split}");
287 }
288 }
289}