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 0 : 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 0 : fd_sha256_t sha[1];
66 0 : 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 0 : return node;
68 0 : }
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 0 : 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 0 : # if FD_HAS_AVX
118 :
119 0 : __m256i avx_pre = _mm256_load_si256 ( (__m256i const *)fd_bmtree_node_prefix );
120 0 : __m256i avx_a = _mm256_loadu_si256( (__m256i const *)a );
121 0 : __m256i avx_b = _mm256_loadu_si256( (__m256i const *)b );
122 :
123 0 : uchar mem[96] __attribute__((aligned(32)));
124 :
125 0 : _mm256_store_si256( (__m256i *)(mem), avx_pre );
126 0 : _mm256_storeu_si256( (__m256i *)(mem+prefix_sz), avx_a );
127 0 : _mm256_storeu_si256( (__m256i *)(mem+prefix_sz+hash_sz), avx_b );
128 :
129 0 : 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 0 : return node;
142 0 : }
143 :
144 : /* bmtree_depth returns the number of layers in a binary Merkle tree. */
145 :
146 : FD_FN_CONST ulong
147 0 : fd_bmtree_depth( ulong leaf_cnt ) {
148 0 : return fd_ulong_if(
149 0 : /* if */ leaf_cnt<=1UL,
150 0 : /* then */ leaf_cnt,
151 0 : /* else */ (ulong)fd_ulong_find_msb_w_default( leaf_cnt-1UL, -1 /*irrelevant*/ ) + 2UL
152 0 : );
153 0 : }
154 :
155 : FD_FN_CONST ulong
156 0 : 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 0 : if( FD_UNLIKELY( leaf_cnt==0UL ) ) return 0UL;
167 0 : ulong cnt = 0UL;
168 0 : leaf_cnt--;
169 0 : for( int i=0; i<64; i++ ) {
170 0 : ulong term = leaf_cnt>>i;
171 0 : cnt += term;
172 0 : }
173 0 : cnt += (ulong)(2+fd_ulong_find_msb_w_default(leaf_cnt, -1));
174 0 : return cnt;
175 0 : }
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 0 : FD_FN_CONST ulong fd_bmtree_commit_align ( void ) { return FD_BMTREE_COMMIT_ALIGN; }
180 :
181 : FD_FN_CONST ulong
182 0 : 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 0 : return fd_ulong_align_up( sizeof(fd_bmtree_commit_t) +
187 0 : ( (1UL<<inclusion_proof_layer_cnt)-1UL )*sizeof(fd_bmtree_node_t) +
188 0 : (((1UL<<inclusion_proof_layer_cnt)+63UL)/64UL)*sizeof(ulong),
189 0 : fd_bmtree_commit_align() );
190 0 : }
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 0 : ulong inclusion_proof_layer_cnt ) {
200 0 : fd_bmtree_commit_t * state = (fd_bmtree_commit_t *) mem;
201 0 : ulong inclusion_proof_sz = (1UL<<inclusion_proof_layer_cnt) - 1UL;
202 0 : state->leaf_cnt = 0UL;
203 0 : state->hash_sz = hash_sz;
204 0 : state->prefix_sz = prefix_sz;
205 0 : state->inclusion_proof_sz = inclusion_proof_sz;
206 0 : state->inclusion_proofs_valid = (ulong*)(state->inclusion_proofs + inclusion_proof_sz);
207 0 : fd_memset( state->inclusion_proofs_valid, 0, sizeof(ulong)*(1UL + inclusion_proof_sz/ipfset_MAX) );
208 0 : return state;
209 0 : }
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 0 : ulong leaf_cnt ) {
225 0 : ulong hash_sz = state->hash_sz;
226 0 : ulong prefix_sz = state->prefix_sz;
227 0 : ulong ip_sz = state->inclusion_proof_sz;
228 0 : ulong msg_sz = prefix_sz + 2UL*hash_sz;
229 :
230 0 : fd_bmtree_node_t * FD_RESTRICT ip = state->inclusion_proofs;
231 0 : fd_bmtree_node_t * FD_RESTRICT node_buf = state->node_buf;
232 :
233 0 : for( ulong i=0UL; i<leaf_cnt; i++ ) ip[ fd_ulong_min( 2UL*i, ip_sz ) ] = leaf[ i ];
234 0 : node_buf[ 0 ] = leaf[ (leaf_cnt-1UL) & ~1UL ];
235 :
236 0 : fd_bmtree_node_t lvl[ 2 ][ FD_BMTREE_PRIVATE_BATCH_LEAF_MAX/2UL ];
237 0 : uchar msg[ FD_SHA256_BATCH_MAX ][ 96 ] __attribute__((aligned(32)));
238 0 : uchar batch_mem[ FD_SHA256_BATCH_FOOTPRINT ] __attribute__((aligned(FD_SHA256_BATCH_ALIGN)));
239 :
240 0 : fd_bmtree_node_t const * cur = leaf;
241 0 : ulong cnt = leaf_cnt;
242 0 : for( ulong layer=1UL; cnt>=2UL; layer++ ) {
243 0 : fd_bmtree_node_t * next = lvl[ layer & 1UL ];
244 0 : ulong merge_cnt = cnt>>1;
245 0 : for( ulong p0=0UL; p0<merge_cnt; p0+=FD_SHA256_BATCH_MAX ) {
246 0 : ulong p1 = fd_ulong_min( p0+FD_SHA256_BATCH_MAX, merge_cnt );
247 0 : fd_sha256_batch_t * batch = fd_sha256_batch_init( batch_mem );
248 0 : for( ulong p=p0; p<p1; p++ ) {
249 0 : uchar * m = msg[ p-p0 ];
250 0 : # if FD_HAS_AVX
251 0 : _mm256_store_si256 ( (__m256i *)(m), _mm256_load_si256 ( (__m256i const *)fd_bmtree_node_prefix ) );
252 0 : _mm256_storeu_si256( (__m256i *)(m+prefix_sz), _mm256_loadu_si256( (__m256i const *)(cur+2UL*p ) ) );
253 0 : _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 0 : fd_sha256_batch_add( batch, m, msg_sz, next[ p ].hash );
260 0 : }
261 0 : fd_sha256_batch_fini( batch );
262 0 : }
263 0 : for( ulong p=0UL; p<merge_cnt; p++ ) ip[ fd_ulong_min( (p<<(layer+1UL)) + (1UL<<layer) - 1UL, ip_sz ) ] = next[ p ];
264 0 : node_buf[ layer ] = next[ (merge_cnt-1UL) & ~1UL ];
265 0 : cur = next;
266 0 : cnt = merge_cnt;
267 0 : }
268 :
269 0 : state->leaf_cnt = leaf_cnt;
270 0 : }
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 0 : ulong new_leaf_cnt ) {
280 0 : ulong leaf_cnt = state->leaf_cnt;
281 0 : fd_bmtree_node_t * FD_RESTRICT node_buf = state->node_buf;
282 :
283 0 : if( FD_UNLIKELY( (!leaf_cnt) & (new_leaf_cnt>=8UL) & (new_leaf_cnt<=FD_BMTREE_PRIVATE_BATCH_LEAF_MAX) ) ) {
284 0 : fd_bmtree_private_commit_batch( state, new_leaf, new_leaf_cnt );
285 0 : return state;
286 0 : }
287 :
288 0 : 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 0 : fd_bmtree_node_t tmp[1];
300 0 : *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 0 : ulong layer = 0UL; /* `layer` starts at 0 (leaf nodes) and increments each iteration. */
312 0 : ulong inc_idx = 2UL*leaf_cnt; /* `inc_idx` is the index of the current node in the inclusion proof array */
313 0 : ulong cursor = ++leaf_cnt; /* `cursor` is the number of known nodes in the current layer. */
314 0 : while( !(cursor & 1UL) ) { /* Continue while the right node in the last pair is available. */
315 0 : state->inclusion_proofs[ fd_ulong_min( inc_idx, state->inclusion_proof_sz ) ] = *tmp;
316 0 : fd_bmtree_private_merge( tmp, node_buf + layer, tmp, state->hash_sz, state->prefix_sz );
317 0 : inc_idx -= 1UL<<layer; layer++; cursor>>=1; /* Move up one layer. */
318 0 : }
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 0 : node_buf[ layer ] = *tmp;
330 0 : state->inclusion_proofs[ fd_ulong_min( inc_idx, state->inclusion_proof_sz ) ] = *tmp;
331 0 : }
332 :
333 0 : state->leaf_cnt = leaf_cnt;
334 0 : return state;
335 0 : }
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 0 : fd_bmtree_commit_fini( fd_bmtree_commit_t * state ) {
348 0 : ulong leaf_cnt = state->leaf_cnt;
349 0 : fd_bmtree_node_t * node_buf = state->node_buf;
350 :
351 : /* Pointer to root node. */
352 0 : 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 0 : if( FD_LIKELY( !fd_ulong_is_pow2( leaf_cnt ) ) ) {
356 :
357 : /* Start at the first layer where number of nodes is odd. */
358 0 : ulong layer = (ulong)fd_ulong_find_lsb( leaf_cnt );
359 0 : ulong layer_cnt = leaf_cnt >> layer; /* number of nodes in this layer */
360 0 : ulong inc_idx = (layer_cnt<<(layer+1UL)) - (1UL<<layer) - 1UL;
361 :
362 : /* Allocate temporary node. */
363 0 : fd_bmtree_node_t tmp[1];
364 0 : *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 0 : while( layer_cnt>1UL ) {
370 0 : fd_bmtree_node_t const * tmp2 = fd_ptr_if( layer_cnt & 1UL, &tmp[0] /* 1 child */, node_buf+layer /* 2 children */ ); /* cmov */
371 0 : fd_bmtree_private_merge( tmp, tmp2, tmp, state->hash_sz, state->prefix_sz );
372 :
373 0 : layer++; layer_cnt = (layer_cnt+1UL) >> 1;
374 :
375 0 : inc_idx = (layer_cnt<<(layer+1UL)) - (1UL<<layer) - 1UL;
376 0 : state->inclusion_proofs[ fd_ulong_min( inc_idx, state->inclusion_proof_sz ) ] = *tmp;
377 0 : }
378 :
379 : /* Fix up root node. */
380 0 : *root = *tmp;
381 0 : }
382 :
383 0 : return root->hash;
384 0 : }
385 :
386 : int
387 : fd_bmtree_get_proof( fd_bmtree_commit_t * state,
388 : uchar * dest,
389 0 : ulong leaf_idx ) {
390 :
391 0 : ulong leaf_cnt = state->leaf_cnt;
392 0 : ulong hash_sz = state->hash_sz;
393 :
394 0 : if( FD_UNLIKELY( leaf_idx >= leaf_cnt ) ) return 0UL;
395 :
396 0 : ulong inc_idx = leaf_idx * 2UL;
397 0 : ulong layer = 0UL;
398 0 : ulong layer_cnt = state->leaf_cnt;
399 0 : # if FD_HAS_AVX512
400 0 : __mmask32 hash_mask = (__mmask32)fd_ulong_mask_lsb( (int)hash_sz );
401 0 : # endif
402 :
403 0 : while( layer_cnt>1UL ) {
404 0 : ulong sibling_idx = inc_idx ^ (1UL<<(layer+1UL));
405 0 : ulong max_idx_for_layer = fd_ulong_insert_lsb( (leaf_cnt - 1UL)<<1, 1+(int)layer, (1UL<<layer)-1UL );
406 0 : sibling_idx = fd_ulong_if( sibling_idx>max_idx_for_layer, inc_idx /* Double link */, sibling_idx );
407 :
408 0 : if( FD_UNLIKELY( sibling_idx>=state->inclusion_proof_sz ) ) return -1;
409 0 : # if FD_HAS_AVX512
410 0 : _mm256_mask_storeu_epi8( dest + layer*hash_sz, hash_mask, _mm256_loadu_si256( (__m256i const *)(state->inclusion_proofs + sibling_idx) ) );
411 : # else
412 : fd_memcpy( dest + layer*hash_sz, state->inclusion_proofs + sibling_idx, hash_sz );
413 : # endif
414 :
415 0 : layer++; layer_cnt = (layer_cnt+1UL)>>1;
416 0 : inc_idx = fd_ulong_insert_lsb( inc_idx, (int)layer+1, (1UL<<layer)-1UL );
417 0 : }
418 :
419 0 : return (int)layer;
420 0 : }
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 0 : ulong prefix_sz ) {
430 0 : fd_bmtree_node_t tmp[2]; /* 0 stores the generated node, 1 stores the node from the proof */
431 0 : fd_bmtree_node_t * tmp_l;
432 0 : fd_bmtree_node_t * tmp_r;
433 :
434 0 : tmp[0] = *leaf;
435 :
436 0 : if( FD_UNLIKELY( proof_depth < fd_bmtree_depth( leaf_idx+1UL )-1UL ) ) return NULL;
437 :
438 0 : ulong inc_idx = leaf_idx * 2UL;
439 0 : for( ulong layer=0UL; layer<proof_depth; layer++ ) {
440 0 : fd_memcpy( tmp+1, proof + layer*hash_sz, hash_sz );
441 :
442 0 : tmp_l = fd_ptr_if( 0UL==(inc_idx & (1UL<<(layer+1UL))), tmp+0, tmp+1 );
443 0 : tmp_r = fd_ptr_if( 0UL==(inc_idx & (1UL<<(layer+1UL))), tmp+1, tmp+0 );
444 :
445 0 : fd_bmtree_private_merge( tmp, tmp_l, tmp_r, hash_sz, prefix_sz );
446 :
447 0 : inc_idx = fd_ulong_insert_lsb( inc_idx, (int)layer+2, (2UL<<layer)-1UL );
448 0 : }
449 0 : return fd_memcpy( root, tmp, 32UL );
450 0 : }
451 :
452 :
453 : /* TODO: Make robust */
454 0 : #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 0 : fd_bmtree_node_t * opt_root ) {
463 0 : ulong inc_idx = 2UL * idx;
464 0 : ulong inclusion_proof_sz = state->inclusion_proof_sz;
465 0 : ulong hash_sz = state->hash_sz;
466 :
467 0 : 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 0 : if( FD_UNLIKELY( (proof_depth>63UL) || (((1UL<<proof_depth)-1UL)>=inclusion_proof_sz) ) ) return 0;
474 :
475 0 : state->node_buf[ 0 ] = *new_leaf;
476 :
477 0 : ulong layer=0UL;
478 0 : for( ; layer<proof_depth; layer++ ) {
479 0 : ulong sibling_idx = inc_idx ^ (2UL<<layer);
480 0 : if( FD_UNLIKELY( HAS(sibling_idx) && !fd_memeq( proof+hash_sz*layer, state->inclusion_proofs[sibling_idx].hash, hash_sz ) ) )
481 0 : return 0;
482 0 : if( FD_UNLIKELY( HAS(inc_idx) && !fd_memeq( state->node_buf[layer].hash, state->inclusion_proofs[ inc_idx ].hash, hash_sz ) ) )
483 0 : return 0;
484 :
485 0 : ulong parent_idx = fd_ulong_insert_lsb( inc_idx, (int)layer+2, (2UL<<layer)-1UL );
486 :
487 0 : if( HAS(sibling_idx) & HAS(inc_idx) ) state->node_buf[ layer+1UL ] = state->inclusion_proofs[ parent_idx ];
488 0 : else {
489 0 : fd_bmtree_node_t sibling;
490 0 : fd_memcpy( sibling.hash, proof+hash_sz*layer, hash_sz );
491 :
492 0 : fd_bmtree_node_t * tmp_l = fd_ptr_if( 0UL==(inc_idx & (2UL<<layer)), state->node_buf+layer, &sibling );
493 0 : fd_bmtree_node_t * tmp_r = fd_ptr_if( 0UL==(inc_idx & (2UL<<layer)), &sibling, state->node_buf+layer );
494 :
495 0 : fd_bmtree_private_merge( state->node_buf+layer+1UL, tmp_l, tmp_r, state->hash_sz, state->prefix_sz );
496 0 : }
497 :
498 0 : inc_idx = parent_idx;
499 0 : }
500 :
501 0 : for( ; layer<63UL; layer++ ) {
502 0 : if( (inc_idx|(2UL<<layer)) >= inclusion_proof_sz ) break; /* Sibling out of bounds => At root */
503 0 : if( HAS( inc_idx ) | !HAS( inc_idx ^ (2UL<<layer) ) ) break; /* Not able to derive any more */
504 :
505 0 : fd_bmtree_node_t * sibling = state->inclusion_proofs + (inc_idx ^ (2UL<<layer));
506 0 : fd_bmtree_node_t * tmp_l = fd_ptr_if( 0UL==(inc_idx & (2UL<<layer)), state->node_buf+layer, sibling );
507 0 : fd_bmtree_node_t * tmp_r = fd_ptr_if( 0UL==(inc_idx & (2UL<<layer)), sibling, state->node_buf+layer );
508 0 : fd_bmtree_private_merge( state->node_buf+layer+1UL, tmp_l, tmp_r, state->hash_sz, state->prefix_sz );
509 :
510 0 : inc_idx = fd_ulong_insert_lsb( inc_idx, (int)layer+2, (2UL<<layer)-1UL );
511 0 : }
512 : /* TODO: Prove inc_idx < inclusion_proof_sz at this point */
513 0 : if( FD_UNLIKELY( HAS(inc_idx) &&
514 0 : !fd_memeq( state->node_buf[layer].hash, state->inclusion_proofs[ inc_idx ].hash, state->hash_sz ) ) )
515 0 : return 0;
516 :
517 : /* Cache the nodes from the main branch */
518 0 : inc_idx = 2UL * idx;
519 0 : for( ulong i=0UL; i<=layer; i++ ) {
520 0 : state->inclusion_proofs[ inc_idx ] = state->node_buf[ i ];
521 0 : state->inclusion_proofs_valid[inc_idx/64UL] |= ipfset_ele( inc_idx%64UL );
522 0 : inc_idx = fd_ulong_insert_lsb( inc_idx, (int)i+2, (2UL<<i)-1UL );
523 0 : }
524 :
525 : /* Cache the inclusion proof */
526 0 : inc_idx = 2UL * idx;
527 0 : for( ulong i=0UL; i<proof_depth; i++ ) {
528 0 : ulong sibling_idx = inc_idx ^ (2UL<<i);
529 0 : fd_memcpy( state->inclusion_proofs[ sibling_idx ].hash, proof+hash_sz*i, hash_sz );
530 0 : state->inclusion_proofs_valid[sibling_idx/64UL] |= ipfset_ele( sibling_idx%64UL );
531 0 : inc_idx = fd_ulong_insert_lsb( inc_idx, (int)i+2, (2UL<<i)-1UL );
532 0 : }
533 :
534 0 : if( FD_UNLIKELY( opt_root != NULL ) ) *opt_root = state->node_buf[ layer ];
535 :
536 0 : return 1;
537 0 : }
538 :
539 : uchar *
540 0 : fd_bmtree_commitp_fini( fd_bmtree_commit_t * state, ulong leaf_cnt ) {
541 0 : ulong inclusion_proof_sz = state->inclusion_proof_sz;
542 0 : ulong hash_sz = state->hash_sz;
543 0 : fd_bmtree_node_t * node_buf = state->node_buf;
544 :
545 0 : if( FD_UNLIKELY( leaf_cnt==0UL ) ) return NULL;
546 :
547 : /* Further hashing required if leaf count is not a power of two. */
548 0 : if( FD_LIKELY( !fd_ulong_is_pow2( leaf_cnt ) ) ) {
549 :
550 : /* Start at the first layer where number of nodes is odd. */
551 0 : ulong layer = (ulong)fd_ulong_find_lsb( leaf_cnt );
552 0 : ulong layer_cnt = leaf_cnt >> layer; /* number of nodes in this layer */
553 0 : 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 0 : if( FD_UNLIKELY( inc_idx >= inclusion_proof_sz ) ) return NULL;
566 :
567 0 : if( FD_UNLIKELY( !HAS(inc_idx) ) ) return NULL;
568 0 : 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 0 : while( layer_cnt>1UL ) {
574 : /* If this is a 2-child parent, make sure we have the sibling. */
575 0 : if( FD_UNLIKELY( !(layer_cnt&1UL) & !HAS(inc_idx^(2UL<<layer)) ) ) return NULL;
576 :
577 0 : 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 0 : fd_bmtree_private_merge( node_buf+layer+1UL, tmp_l, node_buf+layer, hash_sz, state->prefix_sz );
580 :
581 0 : layer++; layer_cnt = (layer_cnt+1UL) >> 1;
582 :
583 0 : inc_idx = (layer_cnt<<(layer+1UL)) - (1UL<<layer) - 1UL;
584 :
585 0 : 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 0 : }
588 :
589 : /* Cache that path */
590 0 : layer = (ulong)fd_ulong_find_lsb( leaf_cnt );
591 0 : layer_cnt = leaf_cnt >> layer; /* number of nodes in this layer */
592 0 : inc_idx = (layer_cnt<<(layer+1UL)) - (1UL<<layer) - 1UL;
593 0 : while( layer_cnt>1UL ) {
594 0 : layer++; layer_cnt = (layer_cnt+1UL) >> 1;
595 0 : inc_idx = (layer_cnt<<(layer+1UL)) - (1UL<<layer) - 1UL;
596 :
597 0 : state->inclusion_proofs[inc_idx] = node_buf[layer];
598 0 : state->inclusion_proofs_valid[inc_idx/64UL] |= ipfset_ele( inc_idx%64UL );
599 0 : }
600 0 : }
601 :
602 : /* Now check to make sure we have all the nodes we should */
603 0 : ulong root_idx = fd_ulong_pow2_up( leaf_cnt ) - 1UL;
604 : /* We should definitely have all nodes <= root_idx */
605 0 : ulong i=0UL;
606 0 : for( ; i<(root_idx+1UL)/64UL; i++ ) if( FD_UNLIKELY( !ipfset_is_full( state->inclusion_proofs_valid[i] ) ) ) return NULL;
607 :
608 0 : 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 0 : ulong min_idx_for_layer = fd_ulong_insert_lsb( 64UL*((root_idx+1UL)/64UL), 1+(int)layer, (1UL<<layer)-1UL );
612 0 : ulong max_idx_for_layer = fd_ulong_insert_lsb( (leaf_cnt - 1UL)<<1, 1+(int)layer, (1UL<<layer)-1UL );
613 0 : for( ulong inc_idx=min_idx_for_layer; inc_idx<=max_idx_for_layer; inc_idx += 2UL<<layer ) {
614 0 : if( FD_UNLIKELY( !HAS(inc_idx) ) ) return NULL;
615 0 : }
616 0 : }
617 : /* If the root idx is less than 63, the previous loop doesn't check
618 : it. */
619 0 : if( !HAS( root_idx ) ) return NULL;
620 :
621 0 : state->leaf_cnt = leaf_cnt;
622 0 : return state->inclusion_proofs[root_idx].hash;
623 0 : }
|
