Line data Source code
1 : #ifndef HEADER_fd_src_ballet_blake3_fd_blake3_h
2 : #define HEADER_fd_src_ballet_blake3_fd_blake3_h
3 :
4 : #include "../fd_ballet_base.h"
5 :
6 : /* fd_blake3 provides APIs for BLAKE3 hashing of messages.
7 :
8 : The BLAKE3 specification is available here:
9 : https://github.com/BLAKE3-team/BLAKE3-specs/blob/master/blake3.pdf
10 :
11 : ### High-level overview
12 :
13 : fd_blake3 provides the "hash" mode of BLAKE3 with variable size
14 : output. Keyed hashing and key derivation are not supported. For
15 : hashes with more than 1024 bytes of input data, uses SIMD parallelism
16 : depending on hardware capabilities. For smaller message sizes, use
17 : the batch API to process multiple independent inputs in parallel.
18 :
19 : ### Usage (simple)
20 :
21 : fd_blake3_t hasher[1];
22 : fd_blake3_init( hasher );
23 : fd_blake3_append( hasher, data, sz );
24 : uchar hash[ 32 ];
25 : fd_blake3_fini( hasher, hash );
26 :
27 : ### Usage (batched)
28 :
29 : ... TODO ...
30 :
31 : ### Hash Construction
32 :
33 : The "core" of BLAKE3 is an add-rotate-xor compression function with
34 : a 512-bit state size. This state is created from the following
35 : 896-bit input:
36 :
37 : - 256-bit chaining value (optionally used to create a hash chain)
38 : - 512-bit input data
39 : - 64-bit counter
40 : - 32-bit input data size
41 : - 32-bit flags
42 :
43 : The BLAKE3 hash is constructed purely by repeated invocation of the
44 : compression function while mixing in input data and metadata.
45 :
46 : At a high-level, there exist two phases: Compress, and expand.
47 : The data dependencies of the compression phase form a hash tree,
48 : ending in a 896-bit root input. In the expand phase, the compression
49 : function is repeatedly applied on the root input with increasing
50 : counter values (each call producing 512-bit of final output data).
51 :
52 : The compress phase is further divided into the chunk phase and the
53 : tree phase. In the chunk phase, each 8192-bit input is hashed to
54 : a 256-bit output via serial calls to the compression function.
55 : (Note that each chunk can be computed independently)
56 :
57 : In the tree phase, the chunks are joined pairwise into a hash tree.
58 :
59 : Figure 1 illustrates a BLAKE3 hash tree with a 2170 byte input
60 : (34 chunks in{X}), one branch nodes (b{Y}), the root state (RS), and
61 : a 192 byte hash output (h{Z}). */
62 :
63 : /*** Figure 1: BLAKE3 Hash Tree ******************************
64 : * *
65 : * ┌────┐ ┌────┐ ┌────┐ ─┐ *
66 : * │ h0 │ │ h1 │ │ h2 │ │ *
67 : * └──▲─┘ └─▲──┘ └─▲──┘ ├─ Expand *
68 : * │ │ │ │ *
69 : * └───────┐│┌────────┘ ─┘ *
70 : * │││ *
71 : * ┌┴┴┴─┐ ─┐ *
72 : * ┌──────►│ RS ├───────┐ │ *
73 : * │ └────┘ │ │ *
74 : * │ │ ├─ Compress Tree *
75 : * ┌─┴──┐ │ │ *
76 : * ┌──►│ b0 │◄──┐ │ │ *
77 : * │ └────┘ │ │ ─┘ *
78 : * │ │ │ *
79 : * ┌──┴───┐ ┌──┴───┐ ┌──┴───┐ ─┐ *
80 : * │ in15 │ │ in31 │ │ in33 │ │ *
81 : * └──▲───┘ └──▲───┘ └──▲───┘ │ *
82 : * │ │ │ │ *
83 : * ... ... ┌──┴───┐ │ *
84 : * ▲ ▲ │ in32 │ │ *
85 : * │ │ └──────┘ ├─ Compress Chunk *
86 : * ┌──┴───┐ ┌──┴───┐ │ *
87 : * │ in1 │ │ in17 │ │ *
88 : * └──▲───┘ └──▲───┘ │ *
89 : * │ │ │ *
90 : * ┌──┴───┐ ┌──┴───┐ │ *
91 : * │ in0 │ │ in16 │ │ *
92 : * └──────┘ └──────┘ ─┘ *
93 : * *
94 : **************************************************************/
95 :
96 : /* ### Implementation
97 :
98 : fd_blake3 consists of three major parts:
99 :
100 : (1) Hash state machines, which track the progress of hash
101 : calculations and prepare operations to advance them;
102 : (2) Schedulers, which accumulate batches of operations from state
103 : machines, then send them to hash backends;
104 : (3) Hash backends (SSE, AVX2, AVX512, SVE2) which work off a static
105 : size vector of independent hash operations.
106 :
107 : The goal is to maximize throughput. The fastest backend usually is
108 : the widest, creating a scheduling problem. The scheduler should be
109 : able to flexibly schedule operations in parallel without taking up
110 : valuable time that could be used for hashing.
111 :
112 : The simplest opportunity to parallelize is during chunk compression.
113 : The bulk of the work is done in the chunk phase, independently for
114 : each 1024 bytes of input data. This is effective for inputs of size
115 : (width*FD_CHUNK_SZ), i.e. >=8192 bytes of input for AVX2.
116 :
117 : To accelerate processing of smaller inputs, a batch API is offered.
118 : Batching allows the scheduler to process operations over multiple
119 : independent messages at once. This has a significantly higher
120 : scheduling overhead though.
121 :
122 : It is worth noting that compression operations require a variable
123 : amount of compression function calls. (Recall that each call
124 : processes 64 bytes of input data, but a chunk can have up to 1024
125 : bytes of data) fd_blake3 therefore has an internal clock that ticks
126 : each time a hash backend processes a vector of blocks. When a state
127 : machine schedules an op with a 1024 byte input, it knows that the op
128 : completes 16 ticks into the future. */
129 :
130 :
131 : /* Protocol constants *************************************************/
132 :
133 : /* FD_BLAKE3_BLOCK_SZ is the byte size of the inputs to the internal
134 : compression function. This is a protocol constant. */
135 :
136 : #define FD_BLAKE3_BLOCK_LG_SZ (6)
137 912025897 : #define FD_BLAKE3_BLOCK_SZ (64UL)
138 :
139 : /* FD_BLAKE3_OUTCHAIN_SZ is the byte size of an "output chaining
140 : value". This is a protocol constant. */
141 :
142 96792459 : #define FD_BLAKE3_OUTCHAIN_LG_SZ (5)
143 10653695 : #define FD_BLAKE3_OUTCHAIN_SZ (32UL)
144 :
145 : /* FD_BLAKE3_CHUNK_SZ is the max number of input bytes of a leaf node.
146 : This is a protocol constant.
147 : (1<<FD_BLAKE3_CHUNK_LG_SZ)==FD_BLAKE3_CHUNK_SZ */
148 :
149 122544085 : #define FD_BLAKE3_CHUNK_LG_SZ (10)
150 38978791 : #define FD_BLAKE3_CHUNK_SZ (1024UL)
151 :
152 : /* FD_BLAKE3_KEY_SZ is the byte size of the optional key in expanded
153 : form. This is a protocol constant. */
154 :
155 : #define FD_BLAKE3_KEY_SZ (32UL)
156 :
157 : /* Implementation constants *******************************************/
158 :
159 : /* FD_BLAKE3_ROW_CNT is the max supported tree height of fd_blake3. */
160 :
161 : #define FD_BLAKE3_ROW_CNT (32UL)
162 :
163 : /* FD_BLAKE3_INPUT_MAX_SZ is the max supported message size of
164 : fd_blake3, derived by FD_BLAKE3_ROW_CNT. (About 4.40 terabytes) */
165 :
166 : #define FD_BLAKE3_INPUT_MAX_SZ ((1UL<<FD_BLAKE3_ROW_CNT)<<FD_BLAKE3_CHUNK_LG_SZ)
167 :
168 : /* FD_BLAKE3_COL_CNT is the max number of adjacent tree nodes to be
169 : buffered per hash state. Used for parallel processing.
170 : (1<<FD_BLAKE3_COL_LG_CNT) == FD_BLAKE3_COL_CNT */
171 :
172 : #if FD_HAS_AVX512
173 : #define FD_BLAKE3_COL_LG_CNT ( 5UL)
174 4196267 : #define FD_BLAKE3_COL_CNT (32UL)
175 : #elif FD_HAS_SVE2
176 : #define FD_BLAKE3_COL_LG_CNT ( 3UL)
177 : #define FD_BLAKE3_COL_CNT ( 8UL)
178 : #else
179 : #define FD_BLAKE3_COL_LG_CNT ( 4UL)
180 12969682 : #define FD_BLAKE3_COL_CNT (16UL)
181 : #endif
182 :
183 : /* FD_BLAKE3_{ALIGN,FOOTPRINT} describe the alignment and footprint needed
184 : for a memory region to hold a fd_blake3_t. ALIGN is a positive
185 : integer power of 2. FOOTPRINT is a multiple of align. ALIGN is
186 : recommended to be at least double cache line to mitigate various
187 : kinds of false sharing. These are provided to facilitate compile
188 : time declarations. */
189 :
190 354 : #define FD_BLAKE3_ALIGN (128UL)
191 :
192 : /* A fd_blake3_t should be treated as an opaque handle of a blake3
193 : calculation state. (It technically isn't here facilitate compile
194 : time declarations of fd_blake3_t memory.) */
195 :
196 10979564 : #define FD_BLAKE3_MAGIC (0xF17EDA2CEB1A4E30) /* FIREDANCE BLAKE3 V0 */
197 :
198 : /* Hash state machine *************************************************/
199 :
200 : /* fd_blake3_pos_t is a hash state machine. The user should consider
201 : this struct implementation-defined. It prepares inputs to all
202 : compression function calls. It also tracks dependencies between
203 : those calls. For every fd_blake3_pos_t, there is a fd_blake3_buf_t.
204 : Depending on input size, it may be able to prepare multiple ops that
205 : can be worked on in parallel. */
206 :
207 : struct __attribute__((aligned(FD_BLAKE3_ALIGN))) fd_blake3_pos {
208 :
209 : /* The tail and head arrays track the hash progress of each tree
210 : layer. head.uc[n] is the number of nodes buffered for that layer.
211 : tail.uc[n] is the number of nodes already hashed into the next
212 : layer. The 32-byte "output chaining value" for that node is stored
213 : in fd_blake3_buf_t. */
214 :
215 : /* This point is 128-byte aligned */
216 :
217 : /* 32-byte aligned so the implementation can use vector accesses */
218 : union { uchar uc[ 32 ] __attribute__((aligned(32))); } tail;
219 : union { uchar uc[ 32 ] __attribute__((aligned(32))); } head;
220 :
221 : /* leaf_idx is the number of leaf chunks processed so far. All but
222 : the last leaf chunk are of size FD_CHUNK_SZs. live_cnt is the
223 : number of nodes for which an output chaining value is buffered and
224 : awaiting further processing. next_tick keeps track of relative
225 : time to inform scheduling when a batch of operations will complete.
226 : layer is the tree layer that the scheduler will work on next. */
227 :
228 : /* This point is 64-byte aligned */
229 :
230 : ulong leaf_idx;
231 : ulong live_cnt;
232 : ulong next_tick;
233 : uint layer;
234 : uchar _pad[4];
235 :
236 : /* [input,input+input_sz) is the user-provided memory region
237 : containing the hash input. May be unaligned. */
238 :
239 : /* This point is 32-byte aligned */
240 :
241 : uchar const * input;
242 : ulong input_sz;
243 :
244 : /* magic==FD_BLAKE3_MAGIC (useful for debugging and detecting memory
245 : corruption) */
246 :
247 : ulong magic;
248 :
249 : };
250 :
251 : typedef struct fd_blake3_pos fd_blake3_pos_t;
252 :
253 : /* fd_blake3_buf_t contains intermediate results of hash tree
254 : construction. Internally, it is a table of output chaining values.
255 : Each row contains a contiguous window of output chaining values for
256 : the nodes at a specific tree layer. Row 0 is the leaf layer. */
257 :
258 : union __attribute__((aligned(FD_BLAKE3_ALIGN))) fd_blake3_buf {
259 :
260 : uchar slots[ FD_BLAKE3_ROW_CNT ][ FD_BLAKE3_COL_CNT ][ FD_BLAKE3_OUTCHAIN_SZ ];
261 : uchar rows [ FD_BLAKE3_ROW_CNT ][ FD_BLAKE3_COL_CNT * FD_BLAKE3_OUTCHAIN_SZ ];
262 :
263 : };
264 :
265 : typedef union fd_blake3_buf fd_blake3_buf_t;
266 :
267 : /* Simple API *********************************************************/
268 :
269 : #if FD_HAS_AVX512
270 41415501 : #define FD_BLAKE3_PARA_LG_MAX (4UL)
271 : #elif FD_HAS_AVX
272 82598244 : #define FD_BLAKE3_PARA_LG_MAX (3UL)
273 : #elif FD_HAS_SVE2
274 : #define FD_BLAKE3_PARA_LG_MAX (2UL)
275 : #else
276 : #define FD_BLAKE3_PARA_LG_MAX (0UL)
277 : #endif
278 90806250 : #define FD_BLAKE3_PARA_MAX (1<<FD_BLAKE3_PARA_LG_MAX)
279 :
280 33207495 : #define FD_BLAKE3_PRIVATE_LG_BUF_MAX (FD_BLAKE3_PARA_LG_MAX+FD_BLAKE3_CHUNK_LG_SZ)
281 11183254 : #define FD_BLAKE3_PRIVATE_BUF_MAX (1UL<<FD_BLAKE3_PRIVATE_LG_BUF_MAX)
282 :
283 : struct fd_blake3 {
284 : fd_blake3_buf_t buf;
285 : uchar block[ FD_BLAKE3_PRIVATE_BUF_MAX ];
286 : fd_blake3_pos_t pos;
287 : ulong block_sz;
288 : };
289 :
290 : typedef struct fd_blake3 fd_blake3_t;
291 :
292 117 : #define FD_BLAKE3_FOOTPRINT (sizeof(fd_blake3_t))
293 :
294 : FD_PROTOTYPES_BEGIN
295 :
296 : /* fd_blake3_{align,footprint,new,join,leave,delete} usage is identical to
297 : that of their fd_sha512 counterparts. See ../sha512/fd_sha512.h */
298 :
299 : FD_FN_CONST ulong
300 : fd_blake3_align( void );
301 :
302 : FD_FN_CONST ulong
303 : fd_blake3_footprint( void );
304 :
305 : void *
306 : fd_blake3_new( void * shmem );
307 :
308 : fd_blake3_t *
309 : fd_blake3_join( void * shsha );
310 :
311 : void *
312 : fd_blake3_leave( fd_blake3_t * sha );
313 :
314 : void *
315 : fd_blake3_delete( void * shsha );
316 :
317 : /* fd_blake3_init starts a blake3 calculation. sha is assumed to be a
318 : current local join to a blake3 calculation state with no other
319 : concurrent operation that would modify the state while this is
320 : executing. Any preexisting state for an in-progress or recently
321 : completed calculation will be discarded. Returns sha (on return, sha
322 : will have the state of a new in-progress calculation). */
323 :
324 : fd_blake3_t *
325 : fd_blake3_init( fd_blake3_t * sha );
326 :
327 : /* fd_blake3_append adds sz bytes locally pointed to by data an
328 : in-progress blake3 calculation. sha, data and sz are assumed to be
329 : valid (i.e. sha is a current local join to a blake3 calculation state
330 : with no other concurrent operations that would modify the state while
331 : this is executing, data points to the first of the sz bytes and will
332 : be unmodified while this is running with no interest retained after
333 : return ... data==NULL is fine if sz==0). Returns sha (on return, sha
334 : will have the updated state of the in-progress calculation).
335 :
336 : It does not matter how the user group data bytes for a blake3
337 : calculation; the final hash will be identical. It is preferable for
338 : performance to try to append as many bytes as possible as a time
339 : though. It is also preferable for performance if sz is a multiple of
340 : 64 for all but the last append (it is also preferable if sz is less
341 : than 56 for the last append). */
342 :
343 : fd_blake3_t *
344 : fd_blake3_append( fd_blake3_t * sha,
345 : void const * data,
346 : ulong sz );
347 :
348 : /* fd_blake3_fini finishes a a blake3 calculation. sha and hash are
349 : assumed to be valid (i.e. sha is a local join to a blake3 calculation
350 : state that has an in-progress calculation with no other concurrent
351 : operations that would modify the state while this is executing and
352 : hash points to the first byte of a 32-byte memory region where the
353 : result of the calculation should be stored). Returns hash (on
354 : return, there will be no calculation in-progress on sha and 32-byte
355 : buffer pointed to by hash will be populated with the calculation
356 : result). */
357 :
358 : void *
359 : fd_blake3_fini( fd_blake3_t * sha,
360 : void * hash );
361 :
362 : void *
363 : fd_blake3_fini_2048( fd_blake3_t * sha,
364 : void * hash );
365 :
366 : void *
367 : fd_blake3_hash( void const * data,
368 : ulong sz,
369 : void * hash );
370 :
371 : /* fd_blake3_lthash_batch{n} calculate a batch of n independent BLAKE3
372 : hash operations with 2048 byte XOF output, and up to 1024 byte input.
373 : The outputs are reduced down to a single value using 'LtHash'
374 : group-add arithmetic.
375 :
376 : batch_data[i] gives a pointer to the input message and does not have
377 : to be aligned. batch_sz[i] gives the input size (in [0,1024]). On
378 : return, 2048 bytes of output are written to out_lthash. batch_data,
379 : batch_sz, and out_lthash are assumed to be 32-byte aligned for batch8
380 : and 64-byte aligned for batch16.
381 :
382 : Execution time is bound by the largest batch_sz[i] input. */
383 :
384 : #if FD_HAS_AVX
385 :
386 : void
387 : fd_blake3_lthash_batch8(
388 : void const * batch_data[8], /* align=32 ele_align=1 */
389 : uint const batch_sz [8], /* align=32 */
390 : void * out_lthash /* align=32 */
391 : );
392 :
393 : #endif
394 :
395 : #if FD_HAS_AVX512
396 :
397 : void
398 : fd_blake3_lthash_batch16(
399 : void const * batch_data[16], /* align=64 ele_align=1 */
400 : uint const batch_sz [16], /* align=64 */
401 : void * out_lthash /* align=64 */
402 : );
403 :
404 : #endif
405 :
406 : FD_PROTOTYPES_END
407 :
408 : #endif /* HEADER_fd_src_ballet_blake3_fd_blake3_h */
|
