Line data Source code
1 : #ifndef HEADER_fd_src_disco_shred_fd_shredder_h
2 : #define HEADER_fd_src_disco_shred_fd_shredder_h
3 :
4 : #include "../keyguard/fd_keyguard_client.h"
5 : #include "../../ballet/sha256/fd_sha256.h"
6 : #include "../../ballet/pack/fd_microblock.h"
7 : #include "../../ballet/chacha20/fd_chacha20rng.h"
8 : #include "../../ballet/wsample/fd_wsample.h"
9 : #include "../../ballet/ed25519/fd_ed25519.h"
10 : #include "../../ballet/reedsol/fd_reedsol.h"
11 : #include "../../ballet/bmtree/fd_bmtree.h"
12 : #include "../../ballet/shred/fd_fec_set.h"
13 :
14 : #define FD_SHREDDER_MAX_STAKE_WEIGHTS (1UL<<20)
15 :
16 :
17 : #define FD_FEC_SET_MAX_BMTREE_DEPTH (9UL) /* ceil(log2(DATA_SHREDS_MAX + PARITY_SHREDS_MAX)) */
18 :
19 0 : #define FD_SHREDDER_ALIGN ( 128UL)
20 : /* FD_SHREDDER_FOOTPRINT is not provided because it depends on the footprint
21 : of fd_sha256_batch_t, which is not invariant (the latter depends on the
22 : underlying implementation). Instead, a static inline function is provided. */
23 :
24 39 : #define FD_SHREDDER_MAGIC (0xF17EDA2547EDDE70UL) /* FIREDAN SHREDDER V0 */
25 :
26 : typedef void (fd_shredder_sign_fn)( void * ctx, uchar * sig, uchar const * merkle_root );
27 :
28 :
29 :
30 : static ulong const fd_shredder_data_to_parity_cnt[ 33UL ] = {
31 : 0UL, 17UL, 18UL, 19UL, 19UL, 20UL, 21UL, 21UL,
32 : 22UL, 23UL, 23UL, 24UL, 24UL, 25UL, 25UL, 26UL,
33 : 26UL, 26UL, 27UL, 27UL, 28UL, 28UL, 29UL, 29UL,
34 : 29UL, 30UL, 30UL, 31UL, 31UL, 31UL, 32UL, 32UL, 32UL };
35 :
36 : struct __attribute__((aligned(FD_SHREDDER_ALIGN))) fd_shredder_private {
37 : ulong magic;
38 : ushort shred_version;
39 :
40 : fd_sha256_batch_t sha256 [ 1 ];
41 : fd_reedsol_t reedsol[ 1 ];
42 : union __attribute__((aligned(FD_BMTREE_COMMIT_ALIGN))) {
43 : fd_bmtree_commit_t bmtree;
44 : uchar _bmtree_footprint[ FD_BMTREE_COMMIT_FOOTPRINT( FD_FEC_SET_MAX_BMTREE_DEPTH ) ];
45 : };
46 : fd_bmtree_node_t bmtree_leaves[ FD_REEDSOL_DATA_SHREDS_MAX + FD_REEDSOL_PARITY_SHREDS_MAX ];
47 :
48 : void const * entry_batch;
49 : ulong sz;
50 : ulong offset;
51 :
52 : void * signer_ctx;
53 : fd_shredder_sign_fn * signer;
54 :
55 : fd_entry_batch_meta_t meta;
56 : ulong slot;
57 : ulong data_idx_offset;
58 : ulong parity_idx_offset;
59 : };
60 :
61 : typedef struct fd_shredder_private fd_shredder_t;
62 :
63 0 : FD_FN_CONST static inline ulong fd_shredder_align ( void ) { return FD_SHREDDER_ALIGN; }
64 0 : FD_FN_CONST static inline ulong fd_shredder_footprint( void ) { return sizeof(fd_shredder_t); }
65 :
66 : /* fd_shredder_new formats a region of memory as a shredder object.
67 : pubkey must point to the first byte of 32 bytes containing the public
68 : key of the validator that will sign the shreds this shredder
69 : produces. The value provided for shred_version will be stored in the
70 : shred_version field of each shred that this shredder produces. */
71 : void * fd_shredder_new( void * mem, fd_shredder_sign_fn * signer, void * signer_ctx, ushort shred_version );
72 : fd_shredder_t * fd_shredder_join( void * mem );
73 : void * fd_shredder_leave( fd_shredder_t * shredder );
74 : void * fd_shredder_delete( void * mem );
75 :
76 :
77 : /* fd_shredder_count_{data_shreds, parity_shreds, fec_sets}: returns the
78 : number of data shreds, parity shreds, or FEC sets (respectively)
79 : required to send an entry batch of size sz_bytes bytes. For data and
80 : parity shred counts, this is the total count across all FEC sets.
81 :
82 : We use the same policy for shredding that the Agave validator uses,
83 : even though it's a bit strange. If the entry batch size is an exact
84 : multiple of the default FEC set total data size of 31840, then we
85 : make sz_byte/31840 FEC sets, where each FEC set has 32 data shreds,
86 : and each data shred contains 995 bytes of payload. Otherwise, we
87 : make 31840 B FEC sets until we have less than 63680 bytes left, and
88 : we make one oddly sized FEC set for the remaining payload.
89 :
90 : Computing this "oddly sized" FEC set is a bit strange because the
91 : number of shreds in the set depends on the amount of payload in each
92 : shred, which depends on the depth of the Merkle tree required to
93 : store all the shreds in the set, which depends on the number of
94 : shreds in the set. The spec gives the formula:
95 : payload_bytes_per_shred = 1115 - 20*ceiling( log2( num_shreds ) )
96 : where num_shreds = num_data_shreds + num_parity_shreds, and
97 : num_data_shreds = payload_sz_remaining/payload_bytes_per_shred and
98 : num_parity_shreds is a non-decreasing function of num_data_shreds.
99 :
100 : The Agave validator solves this formula by brute force.
101 : Instead, we'll do the computation ahead of time to build a nice
102 : table:
103 : Case payload_bytes_per_shred
104 : 1 <= D <= 9135 1015
105 : 8956 <= D <= 31840 995
106 : 31201 <= D <= 62400 975
107 : 61121 <= D <= 63984 955
108 :
109 : Where D is the remaining payload size in bytes. You may notice the
110 : cases overlap. That's the gross outcome of using a gross formula.
111 : There are two legitimate ways to send certain payload sizes. We
112 : always pick the larger value of payload_bytes_per_shred. */
113 :
114 38311992 : #define FD_SHREDDER_NORMAL_FEC_SET_PAYLOAD_SZ (31840UL)
115 :
116 : FD_FN_CONST static inline ulong
117 12893268 : fd_shredder_count_fec_sets( ulong sz_bytes ) {
118 : /* if sz_bytes < 2*31840, we make 1 FEC set. If sz_bytes is a
119 : multiple of 31840, we make exactly sz_bytes/31840 sets. Otherwise,
120 : we make floor(sz_bytes/31840)-1 normal set + one odd-sized set.
121 : These cases can be simplified to make it branchless: */
122 12893268 : return fd_ulong_max( sz_bytes, 2UL*FD_SHREDDER_NORMAL_FEC_SET_PAYLOAD_SZ - 1UL ) / FD_SHREDDER_NORMAL_FEC_SET_PAYLOAD_SZ;
123 12893268 : }
124 : FD_FN_CONST static inline ulong
125 4781454 : fd_shredder_count_data_shreds( ulong sz_bytes ) {
126 4781454 : ulong normal_sets = fd_shredder_count_fec_sets( sz_bytes ) - 1UL;
127 4781454 : ulong remaining_bytes = sz_bytes - normal_sets * FD_SHREDDER_NORMAL_FEC_SET_PAYLOAD_SZ;
128 4781454 : ulong shreds = normal_sets * 32UL;
129 4781454 : if( FD_UNLIKELY( remaining_bytes <= 9135UL ) ) shreds += fd_ulong_max( 1UL, (remaining_bytes + 1014UL)/1015UL );
130 4699236 : else if( FD_LIKELY( remaining_bytes <= 31840UL ) ) shreds += (remaining_bytes + 994UL)/ 995UL;
131 3343833 : else if( FD_LIKELY( remaining_bytes <= 62400UL ) ) shreds += (remaining_bytes + 974UL)/ 975UL;
132 130458 : else shreds += (remaining_bytes + 954UL)/ 955UL;
133 4781454 : return shreds;
134 4781454 : }
135 : FD_FN_CONST static inline ulong
136 4781454 : fd_shredder_count_parity_shreds( ulong sz_bytes ) {
137 4781454 : ulong normal_sets = fd_shredder_count_fec_sets( sz_bytes ) - 1UL;
138 4781454 : ulong remaining_bytes = sz_bytes - normal_sets * FD_SHREDDER_NORMAL_FEC_SET_PAYLOAD_SZ;
139 4781454 : ulong shreds = normal_sets * 32UL;
140 4781454 : if( FD_UNLIKELY( remaining_bytes <= 9135UL ) ) shreds += fd_shredder_data_to_parity_cnt[ fd_ulong_max( 1UL, (remaining_bytes + 1014UL)/1015UL ) ];
141 4699236 : else if( FD_LIKELY( remaining_bytes <= 31840UL ) ) shreds += fd_shredder_data_to_parity_cnt[ (remaining_bytes + 994UL)/ 995UL ];
142 3343833 : else if( FD_LIKELY( remaining_bytes <= 62400UL ) ) shreds += (remaining_bytes + 974UL)/ 975UL;
143 130458 : else shreds += (remaining_bytes + 954UL)/ 955UL;
144 4781454 : return shreds;
145 4781454 : }
146 :
147 : /* fd_shredder_init_batch begins the computation of shreds for an entry
148 : batch. shredder must be a valid local join. entry_batch points to
149 : the first byte of a region of memory entry_batch_sz bytes long.
150 : entry_batch_sz must be strictly positive. The shredder object
151 : retains a read interest in the region of memory [entry_batch,
152 : entry_batch+entry_batch_sz) that lasts until fd_shredder_fini_batch
153 : is called. This region of memory should not be modified while in use
154 : by the shredder. meta contains the metadata for the batch that is
155 : necessary for shred production. The shredder object does not retain
156 : a read interest in the memory pointed to by meta.
157 :
158 : Returns shredder, which will be in a new batch when the function
159 : returns. */
160 : fd_shredder_t * fd_shredder_init_batch( fd_shredder_t * shredder,
161 : void const * entry_batch,
162 : ulong entry_batch_sz,
163 : ulong slot,
164 : fd_entry_batch_meta_t const * meta );
165 :
166 : /* fd_shredder_skip_batch updates the shredder state as necessary
167 : to skip processing this current batch. shredder must be a valid
168 : local join. entry_batch_sz must be strictly positive.
169 :
170 : Returns shredder, which will have data and parity shred indices
171 : updated as if the caller had called fd_shredder_init_batch with
172 : a batch of the specified size, followed by fd_shredder_next_fec_set
173 : exactly fd_shredder_count_fec_sets( entry_batch_sz ) times. */
174 : fd_shredder_t * fd_shredder_skip_batch( fd_shredder_t * shredder,
175 : ulong entry_batch_sz,
176 : ulong slot );
177 :
178 : /* fd_shredder_next_fec_set extracts the next FEC set from the in
179 : progress batch. Computes the entirety of both data and parity
180 : shreds, including the parity information, Merkle proofs, and
181 : signatures. Additionally computes the destination index for each
182 : shred. Stores the generated FEC set in result, which is clobbered.
183 : Populates all fields of result except for {data,parity}_shred_present
184 : (which is only used for reconstruction).
185 :
186 : shredder must be a valid local join, and signing_private_key must
187 : point to the first byte of an Ed25519 private key that will be used
188 : to sign the shreds. It must correspond to the public key passed in
189 : the shredder constructor.
190 :
191 : Returns result on success and NULL if all of the entry batch's data
192 : has been consumed already by previous calls to this function. On
193 : success, advances the position of the shredder within the batch
194 : without finishing the batch. */
195 : fd_fec_set_t * fd_shredder_next_fec_set( fd_shredder_t * shredder, fd_fec_set_t * result );
196 :
197 : /* fd_shredder_fini_batch finishes the in process batch. shredder must
198 : be a valid local join that is currently in a batch. Upon return,
199 : shredder will no longer be in a batch and will be ready to begin a
200 : new batch with init_batch. Returns shredder. */
201 : fd_shredder_t * fd_shredder_fini_batch( fd_shredder_t * shredder );
202 :
203 : #endif /* HEADER_fd_src_disco_shred_fd_shredder_h */
|
