Line data Source code
1 : /* This file declares a family of functions for different widths of
2 : binary Merkle trees based on the SHA-256 hash function. It can be
3 : included multiple times to get different widths. Example:
4 :
5 : #define BMTREE_NAME bmt
6 : #define BMTREE_HASH_SZ 20
7 : #include "fd_bmtree_tmpl.c"
8 :
9 : will declare in the current compile unit a header only library
10 : with the following APIs:
11 :
12 : // Public node API
13 :
14 : struct __attribute__((aligned(32))) bmt_node {
15 : uchar hash[ 32 ]; // Only first 20 bytes are meaningful
16 : };
17 :
18 : typedef struct bmt_node bmt_node_t;
19 :
20 : bmt_node_t * bmtree_hash_leaf( bmt_node_t * node, void const * data, ulong data_sz );
21 :
22 : // Public commit API
23 :
24 : struct bmt_commit;
25 : typedef struct bmt_commit bmt_commit_t;
26 :
27 : ulong bmt_commit_align ( void );
28 : ulong bmt_commit_footprint( void );
29 : bmt_commit_t * bmt_commit_init ( void * mem );
30 : ulong bmt_commit_leaf_cnt ( bmt_commit_t const * bmt );
31 : bmt_commit_t * bmt_commit_append ( bmt_commit_t * bmt, bmt_node_t const * leaf, ulong leaf_cnt );
32 : uchar * bmt_commit_fini ( bmt_commit_t * bmt );
33 :
34 : See comments below for more details.
35 :
36 : Widths 20 and 32 are used in the Solana protocol. Specification:
37 :
38 : https://github.com/solana-foundation/specs/blob/main/core/merkle-tree.md */
39 : #include "fd_bmtree.h"
40 : #include "../sha256/fd_sha256.h"
41 :
42 : #define SET_NAME ipfset
43 : #include "../../util/tmpl/fd_smallset.c"
44 :
45 : #if FD_HAS_AVX
46 : #include <x86intrin.h>
47 : #endif
48 :
49 :
50 :
51 : fd_bmtree_node_t *
52 : fd_bmtree_hash_leaf( fd_bmtree_node_t * node,
53 : void const * data,
54 : ulong data_sz,
55 20760 : ulong prefix_sz ) {
56 :
57 : /* FIXME: Ideally we'd use the streamlined SHA-256 variant here but it
58 : is pretty wonky from a usability perspective to require users to
59 : allow us this API prepend a zero to their data region. See note
60 : below for other nasty performance drags here in the implementation
61 : details (the algorithm conceptually is very clever and sound but
62 : the implementation requirements did not take into any consideration
63 : how real world computers and hardware actually work). */
64 :
65 20760 : fd_sha256_t sha[1];
66 20760 : fd_sha256_fini( fd_sha256_append( fd_sha256_append( fd_sha256_init( sha ), fd_bmtree_leaf_prefix, prefix_sz ), data, data_sz ), node->hash );
67 20760 : return node;
68 20760 : }
69 :
70 : /* bmtree_merge computes `SHA-256(prefix|a->hash|b->hash)` and writes
71 : the full hash into node->hash (which can then be truncated as
72 : necessary). prefix is the first prefix_sz bytes of
73 : fd_bmtree_node_prefix and is typically FD_BMTREE_LONG_PREFIX_SZ or
74 : FD_BMTREE_SHORT_PREFIX_SZ. In-place operation fine. Returns node.
75 : */
76 :
77 : static inline fd_bmtree_node_t *
78 : fd_bmtree_private_merge( fd_bmtree_node_t * node,
79 : fd_bmtree_node_t const * a,
80 : fd_bmtree_node_t const * b,
81 : ulong hash_sz,
82 12303996 : ulong prefix_sz ) {
83 :
84 : /* FIXME: As can be seen from the below, if we actually wanted to be
85 : fast, we'd not bother with 20 byte variant as we actually have to
86 : do more work for this given the SHA algorithm and the hardware work
87 : at a much coarser granularity (and it doesn't save any space in
88 : packets because you could just compute the 32 byte variant and then
89 : truncate the result to 20 bytes ... it'd be both faster and more
90 : secure).
91 :
92 : Further, we'd use a sane prefix (or maybe a suffix) length instead
93 : of a single byte (fine grained memory accesses are the death knell
94 : of real world performance ... it's actually more work for the CPU
95 : and hardware).
96 :
97 : And then, if we really cared, we'd probably replace the stock
98 : SHA256 implementation with a block level parallel SHA256 variant
99 : here and above. This would have equivalent strength but be
100 : dramatically higher performance on real world software and
101 : hardware.
102 :
103 : And then, we could bake into the leaf / branch prefixes into the
104 : parallel block calcs to further reduce comp load and alignment
105 : swizzling. This would make the calculation faster still in
106 : software and less area in hardware while preserving security.
107 :
108 : The net result would be a dramatically faster and significant more
109 : secure and less code in software and a lot easier to accelerate in
110 : hardware.
111 :
112 : In the meantime, we write abominations like the below to get some
113 : extra mileage out of commodity CPUs. Practically helps speed this
114 : up tree construction low tens of percent in the large number of
115 : small leaves limit). */
116 :
117 12303996 : # if FD_HAS_AVX
118 :
119 12303996 : __m256i avx_pre = _mm256_load_si256 ( (__m256i const *)fd_bmtree_node_prefix );
120 12303996 : __m256i avx_a = _mm256_loadu_si256( (__m256i const *)a );
121 12303996 : __m256i avx_b = _mm256_loadu_si256( (__m256i const *)b );
122 :
123 12303996 : uchar mem[96] __attribute__((aligned(32)));
124 :
125 12303996 : _mm256_store_si256( (__m256i *)(mem), avx_pre );
126 12303996 : _mm256_storeu_si256( (__m256i *)(mem+prefix_sz), avx_a );
127 12303996 : _mm256_storeu_si256( (__m256i *)(mem+prefix_sz+hash_sz), avx_b );
128 :
129 12303996 : fd_sha256_hash( mem, prefix_sz+2UL*hash_sz, node );
130 :
131 : /* Consider FD_HAS_SSE only variant? */
132 :
133 : # else
134 :
135 : fd_sha256_t sha[1];
136 : fd_sha256_fini( fd_sha256_append( fd_sha256_append( fd_sha256_append( fd_sha256_init( sha ),
137 : fd_bmtree_node_prefix, prefix_sz ), a->hash, hash_sz ), b->hash, hash_sz ), node->hash );
138 :
139 : # endif
140 :
141 12303996 : return node;
142 12303996 : }
143 :
144 : /* bmtree_depth returns the number of layers in a binary Merkle tree. */
145 :
146 : FD_FN_CONST ulong
147 30774954 : fd_bmtree_depth( ulong leaf_cnt ) {
148 30774954 : return fd_ulong_if(
149 30774954 : /* if */ leaf_cnt<=1UL,
150 30774954 : /* then */ leaf_cnt,
151 30774954 : /* else */ (ulong)fd_ulong_find_msb_w_default( leaf_cnt-1UL, -1 /*irrelevant*/ ) + 2UL
152 30774954 : );
153 30774954 : }
154 :
155 : FD_FN_CONST ulong
156 30000000 : fd_bmtree_node_cnt( ulong leaf_cnt ) {
157 : /* Compute the number of nodes in a tree with inclusion_proof_leaf_cnt
158 : leaves. Based on the proposition that layer l having N_l nodes
159 : implies the above layer has floor((N_l+1)/2) nodes, we know that
160 : the kth layer above has floor(((N_l+2^(k-1)+2^(k-2)+...+1)/2^k)
161 : nodes, which is floor((N_l+2^k - 1)/2^k) = 1+floor((N_l-1)/2^k)
162 : nodes. We stop when we get to 1 node though. It seems like there
163 : should be a bit-twiddling way to calculate this faster, especially
164 : given that you can go all the way to 64 and correct with a value
165 : that comes from the MSB, but I couldn't find it. */
166 30000000 : if( FD_UNLIKELY( leaf_cnt==0UL ) ) return 0UL;
167 29999997 : ulong cnt = 0UL;
168 29999997 : leaf_cnt--;
169 1949999805 : for( int i=0; i<64; i++ ) {
170 1919999808 : ulong term = leaf_cnt>>i;
171 1919999808 : cnt += term;
172 1919999808 : }
173 29999997 : cnt += (ulong)(2+fd_ulong_find_msb_w_default(leaf_cnt, -1));
174 29999997 : return cnt;
175 30000000 : }
176 :
177 : /* bmtree_commit_{footprint,align} return the alignment and footprint
178 : required for a memory region to be used as a bmtree_commit_t. */
179 957 : FD_FN_CONST ulong fd_bmtree_commit_align ( void ) { return FD_BMTREE_COMMIT_ALIGN; }
180 :
181 : FD_FN_CONST ulong
182 954 : fd_bmtree_commit_footprint( ulong inclusion_proof_layer_cnt ) {
183 : /* A complete binary tree with n layers has (2^n)-1 nodes. We keep 1
184 : extra bmtree_node_t (included in sizeof(fd_bmtree_commit_t)) to
185 : avoid branches when appending commits. */
186 954 : return fd_ulong_align_up( sizeof(fd_bmtree_commit_t) +
187 954 : ( (1UL<<inclusion_proof_layer_cnt)-1UL )*sizeof(fd_bmtree_node_t) +
188 954 : (((1UL<<inclusion_proof_layer_cnt)+63UL)/64UL)*sizeof(ulong),
189 954 : fd_bmtree_commit_align() );
190 954 : }
191 :
192 :
193 : /* bmtree_commit_init starts a vector commitment calculation */
194 :
195 : fd_bmtree_commit_t * /* Returns mem as a bmtree_commit_t *, commit will be in a calc */
196 : fd_bmtree_commit_init( void * mem, /* Assumed unused with required alignment and footprint */
197 : ulong hash_sz,
198 : ulong prefix_sz,
199 196668 : ulong inclusion_proof_layer_cnt ) {
200 196668 : fd_bmtree_commit_t * state = (fd_bmtree_commit_t *) mem;
201 196668 : ulong inclusion_proof_sz = (1UL<<inclusion_proof_layer_cnt) - 1UL;
202 196668 : state->leaf_cnt = 0UL;
203 196668 : state->hash_sz = hash_sz;
204 196668 : state->prefix_sz = prefix_sz;
205 196668 : state->inclusion_proof_sz = inclusion_proof_sz;
206 196668 : state->inclusion_proofs_valid = (ulong*)(state->inclusion_proofs + inclusion_proof_sz);
207 196668 : fd_memset( state->inclusion_proofs_valid, 0, sizeof(ulong)*(1UL + inclusion_proof_sz/ipfset_MAX) );
208 196668 : return state;
209 196668 : }
210 :
211 :
212 : /* Builds the tree of an empty commit from leaf_cnt leaves at once,
213 : layer by layer, hashing each layer's merges as one SHA-256 batch.
214 : Leaves the exact state the leaf-at-a-time loop below would: node i of
215 : layer L at inclusion_proofs[ (i<<(L+1)) + (1<<L) - 1 ] and node_buf[L]
216 : the last even-indexed node of layer L. An odd node at a layer stays
217 : unmerged, as in the loop; fini handles it. */
218 :
219 : #define FD_BMTREE_PRIVATE_BATCH_LEAF_MAX (64UL)
220 :
221 : static void
222 : fd_bmtree_private_commit_batch( fd_bmtree_commit_t * state,
223 : fd_bmtree_node_t const * FD_RESTRICT leaf,
224 187956 : ulong leaf_cnt ) {
225 187956 : ulong hash_sz = state->hash_sz;
226 187956 : ulong prefix_sz = state->prefix_sz;
227 187956 : ulong ip_sz = state->inclusion_proof_sz;
228 187956 : ulong msg_sz = prefix_sz + 2UL*hash_sz;
229 :
230 187956 : fd_bmtree_node_t * FD_RESTRICT ip = state->inclusion_proofs;
231 187956 : fd_bmtree_node_t * FD_RESTRICT node_buf = state->node_buf;
232 :
233 12202458 : for( ulong i=0UL; i<leaf_cnt; i++ ) ip[ fd_ulong_min( 2UL*i, ip_sz ) ] = leaf[ i ];
234 187956 : node_buf[ 0 ] = leaf[ (leaf_cnt-1UL) & ~1UL ];
235 :
236 187956 : fd_bmtree_node_t lvl[ 2 ][ FD_BMTREE_PRIVATE_BATCH_LEAF_MAX/2UL ];
237 187956 : uchar msg[ FD_SHA256_BATCH_MAX ][ 96 ] __attribute__((aligned(32)));
238 187956 : uchar batch_mem[ FD_SHA256_BATCH_FOOTPRINT ] __attribute__((aligned(FD_SHA256_BATCH_ALIGN)));
239 :
240 187956 : fd_bmtree_node_t const * cur = leaf;
241 187956 : ulong cnt = leaf_cnt;
242 1314882 : for( ulong layer=1UL; cnt>=2UL; layer++ ) {
243 1126926 : fd_bmtree_node_t * next = lvl[ layer & 1UL ];
244 1126926 : ulong merge_cnt = cnt>>1;
245 2816988 : for( ulong p0=0UL; p0<merge_cnt; p0+=FD_SHA256_BATCH_MAX ) {
246 1690062 : ulong p1 = fd_ulong_min( p0+FD_SHA256_BATCH_MAX, merge_cnt );
247 1690062 : fd_sha256_batch_t * batch = fd_sha256_batch_init( batch_mem );
248 13515480 : for( ulong p=p0; p<p1; p++ ) {
249 11825418 : uchar * m = msg[ p-p0 ];
250 11825418 : # if FD_HAS_AVX
251 11825418 : _mm256_store_si256 ( (__m256i *)(m), _mm256_load_si256 ( (__m256i const *)fd_bmtree_node_prefix ) );
252 11825418 : _mm256_storeu_si256( (__m256i *)(m+prefix_sz), _mm256_loadu_si256( (__m256i const *)(cur+2UL*p ) ) );
253 11825418 : _mm256_storeu_si256( (__m256i *)(m+prefix_sz+hash_sz), _mm256_loadu_si256( (__m256i const *)(cur+2UL*p+1UL) ) );
254 : # else
255 : fd_memcpy( m, fd_bmtree_node_prefix, prefix_sz );
256 : fd_memcpy( m+prefix_sz, cur[ 2UL*p ].hash, hash_sz );
257 : fd_memcpy( m+prefix_sz+hash_sz, cur[ 2UL*p+1UL ].hash, hash_sz );
258 : # endif
259 11825418 : fd_sha256_batch_add( batch, m, msg_sz, next[ p ].hash );
260 11825418 : }
261 1690062 : fd_sha256_batch_fini( batch );
262 1690062 : }
263 12952344 : for( ulong p=0UL; p<merge_cnt; p++ ) ip[ fd_ulong_min( (p<<(layer+1UL)) + (1UL<<layer) - 1UL, ip_sz ) ] = next[ p ];
264 1126926 : node_buf[ layer ] = next[ (merge_cnt-1UL) & ~1UL ];
265 1126926 : cur = next;
266 1126926 : cnt = merge_cnt;
267 1126926 : }
268 :
269 187956 : state->leaf_cnt = leaf_cnt;
270 187956 : }
271 :
272 : /* bmtree_commit_append appends a range of leaf nodes. Assumes that
273 : leaf_cnt + new_leaf_cnt << 2^63 (which, unless planning on running
274 : for millennia, is always true). */
275 :
276 : fd_bmtree_commit_t * /* Returns state */
277 : fd_bmtree_commit_append( fd_bmtree_commit_t * state, /* Assumed valid and in a calc */
278 : fd_bmtree_node_t const * FD_RESTRICT new_leaf, /* Indexed [0,new_leaf_cnt) */
279 6306243 : ulong new_leaf_cnt ) {
280 6306243 : ulong leaf_cnt = state->leaf_cnt;
281 6306243 : fd_bmtree_node_t * FD_RESTRICT node_buf = state->node_buf;
282 :
283 6306243 : if( FD_UNLIKELY( (!leaf_cnt) & (new_leaf_cnt>=8UL) & (new_leaf_cnt<=FD_BMTREE_PRIVATE_BATCH_LEAF_MAX) ) ) {
284 187956 : fd_bmtree_private_commit_batch( state, new_leaf, new_leaf_cnt );
285 187956 : return state;
286 187956 : }
287 :
288 12236763 : for( ulong new_leaf_idx=0UL; new_leaf_idx<new_leaf_cnt; new_leaf_idx++ ) {
289 :
290 : /* Accumulates a single leaf node into the tree.
291 :
292 : Maintains the invariant that the left node of the last node pair
293 : for each layer is copied to `state->node_buf`.
294 :
295 : This serves to allow the algorithm to derive a new parent branch
296 : node for any pair of children, once the (previously missing)
297 : right node becomes available. */
298 :
299 6118476 : fd_bmtree_node_t tmp[1];
300 6118476 : *tmp = new_leaf[ new_leaf_idx ];
301 :
302 : /* Walk the tree upwards from the bottom layer.
303 :
304 : `tmp` contains a previously missing right node which is used to
305 : derive a branch node, together with the previously buffered value
306 : in `node_buf`.
307 :
308 : Each iteration, merges that pair of nodes into a new branch node.
309 : Terminates if the new branch node is the left node of a pair. */
310 :
311 6118476 : ulong layer = 0UL; /* `layer` starts at 0 (leaf nodes) and increments each iteration. */
312 6118476 : ulong inc_idx = 2UL*leaf_cnt; /* `inc_idx` is the index of the current node in the inclusion proof array */
313 6118476 : ulong cursor = ++leaf_cnt; /* `cursor` is the number of known nodes in the current layer. */
314 12231669 : while( !(cursor & 1UL) ) { /* Continue while the right node in the last pair is available. */
315 6113193 : state->inclusion_proofs[ fd_ulong_min( inc_idx, state->inclusion_proof_sz ) ] = *tmp;
316 6113193 : fd_bmtree_private_merge( tmp, node_buf + layer, tmp, state->hash_sz, state->prefix_sz );
317 6113193 : inc_idx -= 1UL<<layer; layer++; cursor>>=1; /* Move up one layer. */
318 6113193 : }
319 :
320 : /* Note on correctness of the above loop: The termination condition
321 : is that bit zero (LSB) of `cursor` is 1. Because `cursor` shifts
322 : right every iteration, the loop terminates as long as any bit in
323 : `cursor` is set to 1. (i.e. `cursor!=0UL`) */
324 :
325 : /* Emplace left node (could be root node) into buffer. FIXME:
326 : Consider computing this location upfront and doing this inplace
327 : instead of copying at end? (Probably a wash.) */
328 :
329 6118476 : node_buf[ layer ] = *tmp;
330 6118476 : state->inclusion_proofs[ fd_ulong_min( inc_idx, state->inclusion_proof_sz ) ] = *tmp;
331 6118476 : }
332 :
333 6118287 : state->leaf_cnt = leaf_cnt;
334 6118287 : return state;
335 6306243 : }
336 :
337 : /* bmtree_commit_fini seals the commitment calculation by deriving the
338 : root node. Assumes state is valid, in calc on entry with at least
339 : one leaf in the tree. The state will be valid but no longer in a
340 : calc on return. Returns a pointer in the caller's address space to
341 : the first byte of a memory region of BMTREE_HASH_SZ with to the root
342 : hash on success. The lifetime of the returned pointer is that of the
343 : state or until the memory used for state gets initialized for a new
344 : calc. */
345 :
346 : uchar *
347 189582 : fd_bmtree_commit_fini( fd_bmtree_commit_t * state ) {
348 189582 : ulong leaf_cnt = state->leaf_cnt;
349 189582 : fd_bmtree_node_t * node_buf = state->node_buf;
350 :
351 : /* Pointer to root node. */
352 189582 : fd_bmtree_node_t * root = node_buf + (fd_bmtree_depth( leaf_cnt ) - 1UL);
353 :
354 : /* Further hashing required if leaf count is not a power of two. */
355 189582 : if( FD_LIKELY( !fd_ulong_is_pow2( leaf_cnt ) ) ) {
356 :
357 : /* Start at the first layer where number of nodes is odd. */
358 1884 : ulong layer = (ulong)fd_ulong_find_lsb( leaf_cnt );
359 1884 : ulong layer_cnt = leaf_cnt >> layer; /* number of nodes in this layer */
360 1884 : ulong inc_idx = (layer_cnt<<(layer+1UL)) - (1UL<<layer) - 1UL;
361 :
362 : /* Allocate temporary node. */
363 1884 : fd_bmtree_node_t tmp[1];
364 1884 : *tmp = node_buf[layer];
365 :
366 : /* Ascend until we reach the root node. Calculate branch nodes
367 : along the way. We use the fd_ulong_if to encourage inlining of
368 : merge and unnecessary branch elimination by cmov. */
369 11481 : while( layer_cnt>1UL ) {
370 9597 : fd_bmtree_node_t const * tmp2 = fd_ptr_if( layer_cnt & 1UL, &tmp[0] /* 1 child */, node_buf+layer /* 2 children */ ); /* cmov */
371 9597 : fd_bmtree_private_merge( tmp, tmp2, tmp, state->hash_sz, state->prefix_sz );
372 :
373 9597 : layer++; layer_cnt = (layer_cnt+1UL) >> 1;
374 :
375 9597 : inc_idx = (layer_cnt<<(layer+1UL)) - (1UL<<layer) - 1UL;
376 9597 : state->inclusion_proofs[ fd_ulong_min( inc_idx, state->inclusion_proof_sz ) ] = *tmp;
377 9597 : }
378 :
379 : /* Fix up root node. */
380 1884 : *root = *tmp;
381 1884 : }
382 :
383 189582 : return root->hash;
384 189582 : }
385 :
386 : int
387 : fd_bmtree_get_proof( fd_bmtree_commit_t * state,
388 : uchar * dest,
389 12139428 : ulong leaf_idx ) {
390 :
391 12139428 : ulong leaf_cnt = state->leaf_cnt;
392 12139428 : ulong hash_sz = state->hash_sz;
393 :
394 12139428 : if( FD_UNLIKELY( leaf_idx >= leaf_cnt ) ) return 0UL;
395 :
396 12139428 : ulong inc_idx = leaf_idx * 2UL;
397 12139428 : ulong layer = 0UL;
398 12139428 : ulong layer_cnt = state->leaf_cnt;
399 4046476 : # if FD_HAS_AVX512
400 4046476 : __mmask32 hash_mask = (__mmask32)fd_ulong_mask_lsb( (int)hash_sz );
401 4046476 : # endif
402 :
403 85126092 : while( layer_cnt>1UL ) {
404 72986664 : ulong sibling_idx = inc_idx ^ (1UL<<(layer+1UL));
405 72986664 : ulong max_idx_for_layer = fd_ulong_insert_lsb( (leaf_cnt - 1UL)<<1, 1+(int)layer, (1UL<<layer)-1UL );
406 72986664 : sibling_idx = fd_ulong_if( sibling_idx>max_idx_for_layer, inc_idx /* Double link */, sibling_idx );
407 :
408 72986664 : if( FD_UNLIKELY( sibling_idx>=state->inclusion_proof_sz ) ) return -1;
409 24328888 : # if FD_HAS_AVX512
410 24328888 : _mm256_mask_storeu_epi8( dest + layer*hash_sz, hash_mask, _mm256_loadu_si256( (__m256i const *)(state->inclusion_proofs + sibling_idx) ) );
411 : # else
412 48657776 : fd_memcpy( dest + layer*hash_sz, state->inclusion_proofs + sibling_idx, hash_sz );
413 48657776 : # endif
414 :
415 72986664 : layer++; layer_cnt = (layer_cnt+1UL)>>1;
416 72986664 : inc_idx = fd_ulong_insert_lsb( inc_idx, (int)layer+1, (1UL<<layer)-1UL );
417 72986664 : }
418 :
419 12139428 : return (int)layer;
420 12139428 : }
421 :
422 : fd_bmtree_node_t *
423 : fd_bmtree_from_proof( fd_bmtree_node_t const * leaf,
424 : ulong leaf_idx,
425 : fd_bmtree_node_t * root,
426 : uchar const * proof,
427 : ulong proof_depth,
428 : ulong hash_sz,
429 395652 : ulong prefix_sz ) {
430 395652 : fd_bmtree_node_t tmp[2]; /* 0 stores the generated node, 1 stores the node from the proof */
431 395652 : fd_bmtree_node_t * tmp_l;
432 395652 : fd_bmtree_node_t * tmp_r;
433 :
434 395652 : tmp[0] = *leaf;
435 :
436 395652 : if( FD_UNLIKELY( proof_depth < fd_bmtree_depth( leaf_idx+1UL )-1UL ) ) return NULL;
437 :
438 394884 : ulong inc_idx = leaf_idx * 2UL;
439 3420570 : for( ulong layer=0UL; layer<proof_depth; layer++ ) {
440 3025686 : fd_memcpy( tmp+1, proof + layer*hash_sz, hash_sz );
441 :
442 3025686 : tmp_l = fd_ptr_if( 0UL==(inc_idx & (1UL<<(layer+1UL))), tmp+0, tmp+1 );
443 3025686 : tmp_r = fd_ptr_if( 0UL==(inc_idx & (1UL<<(layer+1UL))), tmp+1, tmp+0 );
444 :
445 3025686 : fd_bmtree_private_merge( tmp, tmp_l, tmp_r, hash_sz, prefix_sz );
446 :
447 3025686 : inc_idx = fd_ulong_insert_lsb( inc_idx, (int)layer+2, (2UL<<layer)-1UL );
448 3025686 : }
449 394884 : return fd_memcpy( root, tmp, 32UL );
450 395652 : }
451 :
452 :
453 : /* TODO: Make robust */
454 13750506 : #define HAS(inc_idx) (ipfset_test( state->inclusion_proofs_valid[(inc_idx)/64UL], (inc_idx)%64UL ) )
455 :
456 : int
457 : fd_bmtree_commitp_insert_with_proof( fd_bmtree_commit_t * state,
458 : ulong idx,
459 : fd_bmtree_node_t const * new_leaf,
460 : uchar const * proof,
461 : ulong proof_depth,
462 3316824 : fd_bmtree_node_t * opt_root ) {
463 3316824 : ulong inc_idx = 2UL * idx;
464 3316824 : ulong inclusion_proof_sz = state->inclusion_proof_sz;
465 3316824 : ulong hash_sz = state->hash_sz;
466 :
467 3316824 : if( FD_UNLIKELY( inc_idx >= inclusion_proof_sz ) ) return 0;
468 : /* We want to bail if proof_depth>=inclusion_proof_layer_cnt, but we
469 : only have inclusion_proof_size, which is
470 : (1<<inclusion_proof_layer_cnt)-1. This is a monotonic increasing
471 : function for inclusion_proof_layer_cnt in [0, 63], so we just apply
472 : it to both sides of the inequality. */
473 3316824 : if( FD_UNLIKELY( (proof_depth>63UL) || (((1UL<<proof_depth)-1UL)>=inclusion_proof_sz) ) ) return 0;
474 :
475 3316824 : state->node_buf[ 0 ] = *new_leaf;
476 :
477 3316824 : ulong layer=0UL;
478 4155366 : for( ; layer<proof_depth; layer++ ) {
479 1035921 : ulong sibling_idx = inc_idx ^ (2UL<<layer);
480 1035921 : if( FD_UNLIKELY( HAS(sibling_idx) && !fd_memeq( proof+hash_sz*layer, state->inclusion_proofs[sibling_idx].hash, hash_sz ) ) )
481 98685 : return 0;
482 937236 : if( FD_UNLIKELY( HAS(inc_idx) && !fd_memeq( state->node_buf[layer].hash, state->inclusion_proofs[ inc_idx ].hash, hash_sz ) ) )
483 98694 : return 0;
484 :
485 838542 : ulong parent_idx = fd_ulong_insert_lsb( inc_idx, (int)layer+2, (2UL<<layer)-1UL );
486 :
487 838542 : if( HAS(sibling_idx) & HAS(inc_idx) ) state->node_buf[ layer+1UL ] = state->inclusion_proofs[ parent_idx ];
488 146625 : else {
489 146625 : fd_bmtree_node_t sibling;
490 146625 : fd_memcpy( sibling.hash, proof+hash_sz*layer, hash_sz );
491 :
492 146625 : fd_bmtree_node_t * tmp_l = fd_ptr_if( 0UL==(inc_idx & (2UL<<layer)), state->node_buf+layer, &sibling );
493 146625 : fd_bmtree_node_t * tmp_r = fd_ptr_if( 0UL==(inc_idx & (2UL<<layer)), &sibling, state->node_buf+layer );
494 :
495 146625 : fd_bmtree_private_merge( state->node_buf+layer+1UL, tmp_l, tmp_r, state->hash_sz, state->prefix_sz );
496 146625 : }
497 :
498 838542 : inc_idx = parent_idx;
499 838542 : }
500 :
501 6123669 : for( ; layer<63UL; layer++ ) {
502 6123669 : if( (inc_idx|(2UL<<layer)) >= inclusion_proof_sz ) break; /* Sibling out of bounds => At root */
503 6036210 : if( HAS( inc_idx ) | !HAS( inc_idx ^ (2UL<<layer) ) ) break; /* Not able to derive any more */
504 :
505 3004224 : fd_bmtree_node_t * sibling = state->inclusion_proofs + (inc_idx ^ (2UL<<layer));
506 3004224 : fd_bmtree_node_t * tmp_l = fd_ptr_if( 0UL==(inc_idx & (2UL<<layer)), state->node_buf+layer, sibling );
507 3004224 : fd_bmtree_node_t * tmp_r = fd_ptr_if( 0UL==(inc_idx & (2UL<<layer)), sibling, state->node_buf+layer );
508 3004224 : fd_bmtree_private_merge( state->node_buf+layer+1UL, tmp_l, tmp_r, state->hash_sz, state->prefix_sz );
509 :
510 3004224 : inc_idx = fd_ulong_insert_lsb( inc_idx, (int)layer+2, (2UL<<layer)-1UL );
511 3004224 : }
512 : /* TODO: Prove inc_idx < inclusion_proof_sz at this point */
513 3119445 : if( FD_UNLIKELY( HAS(inc_idx) &&
514 3119445 : !fd_memeq( state->node_buf[layer].hash, state->inclusion_proofs[ inc_idx ].hash, state->hash_sz ) ) )
515 3 : return 0;
516 :
517 : /* Cache the nodes from the main branch */
518 3119442 : inc_idx = 2UL * idx;
519 10081650 : for( ulong i=0UL; i<=layer; i++ ) {
520 6962208 : state->inclusion_proofs[ inc_idx ] = state->node_buf[ i ];
521 6962208 : state->inclusion_proofs_valid[inc_idx/64UL] |= ipfset_ele( inc_idx%64UL );
522 6962208 : inc_idx = fd_ulong_insert_lsb( inc_idx, (int)i+2, (2UL<<i)-1UL );
523 6962208 : }
524 :
525 : /* Cache the inclusion proof */
526 3119442 : inc_idx = 2UL * idx;
527 3957984 : for( ulong i=0UL; i<proof_depth; i++ ) {
528 838542 : ulong sibling_idx = inc_idx ^ (2UL<<i);
529 838542 : fd_memcpy( state->inclusion_proofs[ sibling_idx ].hash, proof+hash_sz*i, hash_sz );
530 838542 : state->inclusion_proofs_valid[sibling_idx/64UL] |= ipfset_ele( sibling_idx%64UL );
531 838542 : inc_idx = fd_ulong_insert_lsb( inc_idx, (int)i+2, (2UL<<i)-1UL );
532 838542 : }
533 :
534 3119442 : if( FD_UNLIKELY( opt_root != NULL ) ) *opt_root = state->node_buf[ layer ];
535 :
536 3119442 : return 1;
537 3119445 : }
538 :
539 : uchar *
540 1002 : fd_bmtree_commitp_fini( fd_bmtree_commit_t * state, ulong leaf_cnt ) {
541 1002 : ulong inclusion_proof_sz = state->inclusion_proof_sz;
542 1002 : ulong hash_sz = state->hash_sz;
543 1002 : fd_bmtree_node_t * node_buf = state->node_buf;
544 :
545 1002 : if( FD_UNLIKELY( leaf_cnt==0UL ) ) return NULL;
546 :
547 : /* Further hashing required if leaf count is not a power of two. */
548 1002 : if( FD_LIKELY( !fd_ulong_is_pow2( leaf_cnt ) ) ) {
549 :
550 : /* Start at the first layer where number of nodes is odd. */
551 750 : ulong layer = (ulong)fd_ulong_find_lsb( leaf_cnt );
552 750 : ulong layer_cnt = leaf_cnt >> layer; /* number of nodes in this layer */
553 750 : ulong inc_idx = (layer_cnt<<(layer+1UL)) - (1UL<<layer) - 1UL;
554 :
555 : /* When you go up and left in the tree, the index decreases. If you
556 : are the left child of the parent (the only way you can go up and
557 : right), then bit 1<<(l+1) is unset, and going up and right will
558 : not change that. This means that if you start at a leaf node in
559 : the right half of the tree (which is always the case for the last
560 : leaf node), then going up will never go past the next power of 2
561 : beyond the current one. Since inclusion_proof_sz is a power of
562 : 2, that means it suffices to check this once and not every time
563 : we go up the tree. */
564 : /* TODO: Make this argument more formal */
565 750 : if( FD_UNLIKELY( inc_idx >= inclusion_proof_sz ) ) return NULL;
566 :
567 750 : if( FD_UNLIKELY( !HAS(inc_idx) ) ) return NULL;
568 750 : node_buf[layer] = state->inclusion_proofs[inc_idx];
569 :
570 : /* Ascend until we reach the root node. Calculate branch nodes
571 : along the way. We use the fd_ulong_if to encourage inlining of
572 : merge and unnecessary branch elimination by cmov. */
573 5421 : while( layer_cnt>1UL ) {
574 : /* If this is a 2-child parent, make sure we have the sibling. */
575 4671 : if( FD_UNLIKELY( !(layer_cnt&1UL) & !HAS(inc_idx^(2UL<<layer)) ) ) return NULL;
576 :
577 4671 : fd_bmtree_node_t const * tmp_l = fd_ptr_if( layer_cnt & 1UL, node_buf+layer /* 1 child */, state->inclusion_proofs + (inc_idx^(2UL<<layer))/* 2 children */ ); /* cmov */
578 :
579 4671 : fd_bmtree_private_merge( node_buf+layer+1UL, tmp_l, node_buf+layer, hash_sz, state->prefix_sz );
580 :
581 4671 : layer++; layer_cnt = (layer_cnt+1UL) >> 1;
582 :
583 4671 : inc_idx = (layer_cnt<<(layer+1UL)) - (1UL<<layer) - 1UL;
584 :
585 4671 : if( FD_UNLIKELY( HAS( inc_idx ) && !fd_memeq( node_buf[layer].hash, state->inclusion_proofs[inc_idx].hash, hash_sz ) ) )
586 0 : return NULL;
587 4671 : }
588 :
589 : /* Cache that path */
590 750 : layer = (ulong)fd_ulong_find_lsb( leaf_cnt );
591 750 : layer_cnt = leaf_cnt >> layer; /* number of nodes in this layer */
592 750 : inc_idx = (layer_cnt<<(layer+1UL)) - (1UL<<layer) - 1UL;
593 5421 : while( layer_cnt>1UL ) {
594 4671 : layer++; layer_cnt = (layer_cnt+1UL) >> 1;
595 4671 : inc_idx = (layer_cnt<<(layer+1UL)) - (1UL<<layer) - 1UL;
596 :
597 4671 : state->inclusion_proofs[inc_idx] = node_buf[layer];
598 4671 : state->inclusion_proofs_valid[inc_idx/64UL] |= ipfset_ele( inc_idx%64UL );
599 4671 : }
600 750 : }
601 :
602 : /* Now check to make sure we have all the nodes we should */
603 1002 : ulong root_idx = fd_ulong_pow2_up( leaf_cnt ) - 1UL;
604 : /* We should definitely have all nodes <= root_idx */
605 1002 : ulong i=0UL;
606 52389 : for( ; i<(root_idx+1UL)/64UL; i++ ) if( FD_UNLIKELY( !ipfset_is_full( state->inclusion_proofs_valid[i] ) ) ) return NULL;
607 :
608 7776 : for( ulong layer=0UL; (1UL<<layer)-1UL < root_idx; layer++ ) {
609 : /* Loop over indices s.t. 64*( (root_idx+1)/64 ) <= index <= that match the bit
610 : pattern 01..1 with `layer` 1s */
611 6774 : ulong min_idx_for_layer = fd_ulong_insert_lsb( 64UL*((root_idx+1UL)/64UL), 1+(int)layer, (1UL<<layer)-1UL );
612 6774 : ulong max_idx_for_layer = fd_ulong_insert_lsb( (leaf_cnt - 1UL)<<1, 1+(int)layer, (1UL<<layer)-1UL );
613 2944740 : for( ulong inc_idx=min_idx_for_layer; inc_idx<=max_idx_for_layer; inc_idx += 2UL<<layer ) {
614 2937966 : if( FD_UNLIKELY( !HAS(inc_idx) ) ) return NULL;
615 2937966 : }
616 6774 : }
617 : /* If the root idx is less than 63, the previous loop doesn't check
618 : it. */
619 1002 : if( !HAS( root_idx ) ) return NULL;
620 :
621 1002 : state->leaf_cnt = leaf_cnt;
622 1002 : return state->inclusion_proofs[root_idx].hash;
623 1002 : }
|
