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 "../../disco/pack/fd_microblock.h"
7 : #include "../../ballet/wsample/fd_wsample.h"
8 : #include "../../ballet/ed25519/fd_ed25519.h"
9 : #include "../../ballet/reedsol/fd_reedsol.h"
10 : #include "../../ballet/bmtree/fd_bmtree.h"
11 : #include "../../ballet/shred/fd_fec_set.h"
12 : #include "../../ballet/shred/fd_shred.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 114 : #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 57 : #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 0 : #define FD_SHRED_FEATURES_ACTIVATION_SLOT_CNT (4UL)
29 : #define FD_SHRED_FEATURES_ACTIVATION_SLOT_SZ (8UL)
30 0 : #define FD_SHRED_FEATURES_ACTIVATION_SLOT_DISABLED (ULONG_MAX)
31 :
32 : union fd_shred_features_activation_private {
33 : /* slots for features of interest - update cnt as needed in the future. */
34 : ulong slots[ FD_SHRED_FEATURES_ACTIVATION_SLOT_CNT ];
35 : struct {
36 : /* 0 */ ulong disable_turbine_fanout_experiments;
37 : /* 1 */ ulong enable_turbine_extended_fanout_experiments;
38 : /* 2 */ ulong enable_chained_merkle_shreds;
39 : /* 3 */ ulong drop_unchained_merkle_shreds;
40 : };
41 : };
42 : typedef union fd_shred_features_activation_private fd_shred_features_activation_t;
43 :
44 : static ulong const fd_shredder_data_to_parity_cnt[ 33UL ] = {
45 : 0UL, 17UL, 18UL, 19UL, 19UL, 20UL, 21UL, 21UL,
46 : 22UL, 23UL, 23UL, 24UL, 24UL, 25UL, 25UL, 26UL,
47 : 26UL, 26UL, 27UL, 27UL, 28UL, 28UL, 29UL, 29UL,
48 : 29UL, 30UL, 30UL, 31UL, 31UL, 31UL, 32UL, 32UL, 32UL };
49 :
50 : struct __attribute__((aligned(FD_SHREDDER_ALIGN))) fd_shredder_private {
51 : ulong magic;
52 : ushort shred_version;
53 :
54 : fd_sha256_batch_t sha256 [ 1 ];
55 : fd_reedsol_t reedsol[ 1 ];
56 : union __attribute__((aligned(FD_BMTREE_COMMIT_ALIGN))) {
57 : fd_bmtree_commit_t bmtree;
58 : uchar _bmtree_footprint[ FD_BMTREE_COMMIT_FOOTPRINT( FD_FEC_SET_MAX_BMTREE_DEPTH ) ];
59 : };
60 : fd_bmtree_node_t bmtree_leaves[ FD_REEDSOL_DATA_SHREDS_MAX + FD_REEDSOL_PARITY_SHREDS_MAX ];
61 :
62 : void const * entry_batch;
63 : ulong sz;
64 : ulong offset;
65 :
66 : void * signer_ctx;
67 : fd_shredder_sign_fn * signer;
68 :
69 : fd_entry_batch_meta_t meta;
70 : ulong slot;
71 : ulong data_idx_offset;
72 : ulong parity_idx_offset;
73 : };
74 :
75 : typedef struct fd_shredder_private fd_shredder_t;
76 :
77 114 : FD_FN_CONST static inline ulong fd_shredder_align ( void ) { return FD_SHREDDER_ALIGN; }
78 6 : FD_FN_CONST static inline ulong fd_shredder_footprint( void ) { return sizeof(fd_shredder_t); }
79 :
80 : /* fd_shredder_new formats a region of memory as a shredder object.
81 : pubkey must point to the first byte of 32 bytes containing the public
82 : key of the validator that will sign the shreds this shredder
83 : produces. The value provided for shred_version will be stored in the
84 : shred_version field of each shred that this shredder produces. */
85 : void * fd_shredder_new( void * mem, fd_shredder_sign_fn * signer, void * signer_ctx );
86 : fd_shredder_t * fd_shredder_join( void * mem );
87 : void * fd_shredder_leave( fd_shredder_t * shredder );
88 : void * fd_shredder_delete( void * mem );
89 :
90 27 : static inline void fd_shredder_set_shred_version( fd_shredder_t * shredder, ushort shred_version ) { shredder->shred_version = shred_version; }
91 :
92 :
93 : /* fd_shredder_count_{data_shreds, parity_shreds, fec_sets}: returns the
94 : number of data shreds, parity shreds, or FEC sets (respectively)
95 : required to send an entry batch of size `sz_bytes` bytes, with shreds
96 : of type `type`. `type` must be one of FD_SHRED_TYPE_MERKLE_{DATA,
97 : DATA_CHAINED, DATA_CHAINED_RESIGNED}. For data and parity shred counts,
98 : this is the total count across all FEC sets.
99 :
100 : We use the same policy for shredding that the Agave validator uses,
101 : even though it's a bit strange. If the entry batch size is an exact
102 : multiple of the default FEC set total data size of 31840, then we
103 : make sz_byte/31840 FEC sets, where each FEC set has 32 data shreds,
104 : and each data shred contains 995 bytes of payload. Otherwise, we
105 : make 31840 B FEC sets until we have less than 63680 bytes left, and
106 : we make one oddly sized FEC set for the remaining payload.
107 :
108 : (Note: while this is true for the logic of the shredder, the way our
109 : shred tile works with watermark implies that this never happens, and
110 : the only case that happens in practice is the "oddly sized" FEC set
111 : described below.)
112 :
113 : Computing this "oddly sized" FEC set is a bit strange because the
114 : number of shreds in the set depends on the amount of payload in each
115 : shred, which depends on the depth of the Merkle tree required to
116 : store all the shreds in the set, which depends on the number of
117 : shreds in the set. The spec gives the formula:
118 : payload_bytes_per_shred = 1115 - 20*ceiling( log2( num_shreds ) )
119 : where num_shreds = num_data_shreds + num_parity_shreds, and
120 : num_data_shreds = payload_sz_remaining/payload_bytes_per_shred and
121 : num_parity_shreds is a non-decreasing function of num_data_shreds.
122 :
123 : The Agave validator solves this formula by brute force.
124 : Instead, we'll do the computation ahead of time to build a nice
125 : table:
126 : Case payload_bytes_per_shred
127 : 1 <= D <= 9135 1015
128 : 8956 <= D <= 31840 995
129 : 31201 <= D <= 62400 975
130 : 61121 <= D <= 63984 955
131 :
132 : Where D is the remaining payload size in bytes. You may notice the
133 : cases overlap. That's the gross outcome of using a gross formula.
134 : There are two legitimate ways to send certain payload sizes. We
135 : always pick the larger value of payload_bytes_per_shred.
136 :
137 : In short, the relationship between the constants that appear in the
138 : code below is as follow:
139 :
140 : Unchained Merkle Shreds.
141 : - data_sz: 9135 == payload_sz: 1015 * 9 shreds (merkle tree height: 5)
142 : - data_sz: 31840 == payload_sz: 995 * 32 shreds (merkle tree height: 6)
143 : - data_sz: 62400 == payload_sz: 975 * 64 shreds (merkle tree height: 7)
144 : - payload_sz: 955 (merkle tree height: 8)
145 : note: payload_sz decreases by 20 bytes as the merkle tree height increases.
146 : note 2: in the first entry, 9 data shreds + 23 corresponding parity shreds
147 : total to 32 shreds, hence a merkle tree of height 5.
148 :
149 : Chained Merkle Shreds.
150 : - data_sz: 8847 == payload_sz: 983 * 9 shreds (merkle tree height: 5)
151 : - data_sz: 30816 == payload_sz: 963 * 32 shreds (merkle tree height: 6)
152 : - data_sz: 60352 == payload_sz: 943 * 64 shreds (merkle tree height: 7)
153 : - payload_sz: 923 (merkle tree height: 8)
154 : note: payload_sz is the unchained payload_sz - 32 bytes (for chained merkle root).
155 :
156 : Resigned Chained Merkle Shreds.
157 : - data_sz: 8271 == payload_sz: 919 * 9 shreds (merkle tree height: 5)
158 : - data_sz: 28768 == payload_sz: 899 * 32 shreds (merkle tree height: 6)
159 : - data_sz: 56256 == payload_sz: 879 * 64 shreds (merkle tree height: 7)
160 : - payload_sz: 859 (merkle tree height: 8)
161 : note: payload_sz is the chained payload_sz - 64 bytes (for signature). */
162 :
163 32505840 : #define FD_SHREDDER_NORMAL_FEC_SET_PAYLOAD_SZ (31840UL)
164 31937550 : #define FD_SHREDDER_CHAINED_FEC_SET_PAYLOAD_SZ (30816UL) /* -32 bytes * 32 shreds */
165 32022390 : #define FD_SHREDDER_RESIGNED_FEC_SET_PAYLOAD_SZ (28768UL) /* -64 bytes * 32 shreds */
166 :
167 : #define FD_SHREDDER_NORMAL_FEC_SET_RAW_BUF_SZ (63679UL) /* 2 * ...PAYLOAD_SZ - 1 */
168 : #define FD_SHREDDER_CHAINED_FEC_SET_RAW_BUF_SZ (61631UL) /* 2 * ...PAYLOAD_SZ - 1 */
169 : #define FD_SHREDDER_RESIGNED_FEC_SET_RAW_BUF_SZ (57535UL) /* 2 * ...PAYLOAD_SZ - 1 */
170 :
171 : FD_FN_CONST static inline ulong
172 34207599 : fd_shredder_count_fec_sets( ulong sz_bytes, ulong type ) {
173 : /* In the case of normal fec_sets, if sz_bytes < 2*31840, we make 1 FEC set.
174 : If sz_bytes is a multiple of 31840, we make exactly sz_bytes/31840 sets.
175 : Otherwise, we make floor(sz_bytes/31840)-1 normal set + one odd-sized set.
176 : In the case of chained and (chained+)resigned fec_sets, the thresholds are
177 : adjusted accordingly. */
178 34207599 : if( FD_UNLIKELY( fd_shred_is_resigned( type ) ) ) {
179 11354808 : return fd_ulong_max( sz_bytes, 2UL*FD_SHREDDER_RESIGNED_FEC_SET_PAYLOAD_SZ - 1UL ) / FD_SHREDDER_RESIGNED_FEC_SET_PAYLOAD_SZ;
180 22852791 : } else if( FD_LIKELY( fd_shred_is_chained( type ) ) ) {
181 11330538 : return fd_ulong_max( sz_bytes, 2UL*FD_SHREDDER_CHAINED_FEC_SET_PAYLOAD_SZ - 1UL ) / FD_SHREDDER_CHAINED_FEC_SET_PAYLOAD_SZ;
182 11330538 : }
183 11522253 : return fd_ulong_max( sz_bytes, 2UL*FD_SHREDDER_NORMAL_FEC_SET_PAYLOAD_SZ - 1UL ) / FD_SHREDDER_NORMAL_FEC_SET_PAYLOAD_SZ;
184 34207599 : }
185 : FD_FN_CONST static inline ulong
186 11879298 : fd_shredder_count_data_shreds( ulong sz_bytes, ulong type ) {
187 11879298 : ulong normal_sets = fd_shredder_count_fec_sets( sz_bytes, type ) - 1UL;
188 11879298 : ulong shreds = normal_sets * 32UL;
189 11879298 : if( FD_UNLIKELY( fd_shred_is_resigned( type ) ) ) {
190 3941100 : ulong remaining_bytes = sz_bytes - normal_sets * FD_SHREDDER_RESIGNED_FEC_SET_PAYLOAD_SZ;
191 3941100 : if( FD_UNLIKELY( remaining_bytes <= 8271UL ) ) shreds += fd_ulong_max( 1UL, (remaining_bytes + 918UL)/ 919UL );
192 3841842 : else if( FD_LIKELY( remaining_bytes <= 28768UL ) ) shreds += (remaining_bytes + 898UL)/ 899UL;
193 3427287 : else if( FD_LIKELY( remaining_bytes <= 56256UL ) ) shreds += (remaining_bytes + 878UL)/ 879UL;
194 145806 : else shreds += (remaining_bytes + 858UL)/ 859UL;
195 7938198 : } else if( FD_LIKELY( fd_shred_is_chained( type ) ) ) {
196 3922818 : ulong remaining_bytes = sz_bytes - normal_sets * FD_SHREDDER_CHAINED_FEC_SET_PAYLOAD_SZ;
197 3922818 : if( FD_UNLIKELY( remaining_bytes <= 8847UL ) ) shreds += fd_ulong_max( 1UL, (remaining_bytes + 982UL)/ 983UL );
198 3816648 : else if( FD_LIKELY( remaining_bytes <= 30816UL ) ) shreds += (remaining_bytes + 962UL)/ 963UL;
199 3414987 : else if( FD_LIKELY( remaining_bytes <= 60352UL ) ) shreds += (remaining_bytes + 942UL)/ 943UL;
200 138132 : else shreds += (remaining_bytes + 922UL)/ 923UL;
201 4015380 : } else {
202 4015380 : ulong remaining_bytes = sz_bytes - normal_sets * FD_SHREDDER_NORMAL_FEC_SET_PAYLOAD_SZ;
203 4015380 : if( FD_UNLIKELY( remaining_bytes <= 9135UL ) ) shreds += fd_ulong_max( 1UL, (remaining_bytes + 1014UL)/1015UL );
204 3905754 : else if( FD_LIKELY( remaining_bytes <= 31840UL ) ) shreds += (remaining_bytes + 994UL)/ 995UL;
205 3409440 : else if( FD_LIKELY( remaining_bytes <= 62400UL ) ) shreds += (remaining_bytes + 974UL)/ 975UL;
206 134295 : else shreds += (remaining_bytes + 954UL)/ 955UL;
207 4015380 : }
208 11879298 : return shreds;
209 11879298 : }
210 : FD_FN_CONST static inline ulong
211 11879298 : fd_shredder_count_parity_shreds( ulong sz_bytes, ulong type ) {
212 11879298 : ulong normal_sets = fd_shredder_count_fec_sets( sz_bytes, type ) - 1UL;
213 11879298 : ulong shreds = normal_sets * 32UL;
214 11879298 : if( FD_UNLIKELY( fd_shred_is_resigned( type ) ) ) {
215 3941100 : ulong remaining_bytes = sz_bytes - normal_sets * FD_SHREDDER_RESIGNED_FEC_SET_PAYLOAD_SZ;
216 3941100 : if( FD_UNLIKELY( remaining_bytes <= 8271UL ) ) shreds += fd_shredder_data_to_parity_cnt[ fd_ulong_max( 1UL, (remaining_bytes + 918UL)/ 919UL ) ];
217 3841842 : else if( FD_LIKELY( remaining_bytes <= 28768UL ) ) shreds += fd_shredder_data_to_parity_cnt[ (remaining_bytes + 898UL)/ 899UL ];
218 3427287 : else if( FD_LIKELY( remaining_bytes <= 56256UL ) ) shreds += (remaining_bytes + 878UL)/ 879UL;
219 145806 : else shreds += (remaining_bytes + 858UL)/ 859UL;
220 7938198 : } else if( FD_LIKELY( fd_shred_is_chained( type ) ) ) {
221 3922818 : ulong remaining_bytes = sz_bytes - normal_sets * FD_SHREDDER_CHAINED_FEC_SET_PAYLOAD_SZ;
222 3922818 : if( FD_UNLIKELY( remaining_bytes <= 8847UL ) ) shreds += fd_shredder_data_to_parity_cnt[ fd_ulong_max( 1UL, (remaining_bytes + 982UL)/ 983UL ) ];
223 3816648 : else if( FD_LIKELY( remaining_bytes <= 30816UL ) ) shreds += fd_shredder_data_to_parity_cnt[ (remaining_bytes + 962UL)/ 963UL ];
224 3414987 : else if( FD_LIKELY( remaining_bytes <= 60352UL ) ) shreds += (remaining_bytes + 942UL)/ 943UL;
225 138132 : else shreds += (remaining_bytes + 922UL)/ 923UL;
226 4015380 : } else {
227 4015380 : ulong remaining_bytes = sz_bytes - normal_sets * FD_SHREDDER_NORMAL_FEC_SET_PAYLOAD_SZ;
228 4015380 : if( FD_UNLIKELY( remaining_bytes <= 9135UL ) ) shreds += fd_shredder_data_to_parity_cnt[ fd_ulong_max( 1UL, (remaining_bytes + 1014UL)/1015UL ) ];
229 3905754 : else if( FD_LIKELY( remaining_bytes <= 31840UL ) ) shreds += fd_shredder_data_to_parity_cnt[ (remaining_bytes + 994UL)/ 995UL ];
230 3409440 : else if( FD_LIKELY( remaining_bytes <= 62400UL ) ) shreds += (remaining_bytes + 974UL)/ 975UL;
231 134295 : else shreds += (remaining_bytes + 954UL)/ 955UL;
232 4015380 : }
233 11879298 : return shreds;
234 11879298 : }
235 :
236 : /* fd_shredder_init_batch begins the computation of shreds for an entry
237 : batch. shredder must be a valid local join. entry_batch points to
238 : the first byte of a region of memory entry_batch_sz bytes long.
239 : entry_batch_sz must be strictly positive. The shredder object
240 : retains a read interest in the region of memory [entry_batch,
241 : entry_batch+entry_batch_sz) that lasts until fd_shredder_fini_batch
242 : is called. This region of memory should not be modified while in use
243 : by the shredder. meta contains the metadata for the batch that is
244 : necessary for shred production. The shredder object does not retain
245 : a read interest in the memory pointed to by meta.
246 :
247 : Returns shredder, which will be in a new batch when the function
248 : returns. */
249 : fd_shredder_t * fd_shredder_init_batch( fd_shredder_t * shredder,
250 : void const * entry_batch,
251 : ulong entry_batch_sz,
252 : ulong slot,
253 : fd_entry_batch_meta_t const * meta );
254 :
255 : /* fd_shredder_skip_batch updates the shredder state as necessary
256 : to skip processing this current batch. shredder must be a valid
257 : local join. entry_batch_sz must be strictly positive.
258 :
259 : Returns shredder, which will have data and parity shred indices
260 : updated as if the caller had called fd_shredder_init_batch with
261 : a batch of the specified size, followed by fd_shredder_next_fec_set
262 : exactly fd_shredder_count_fec_sets( entry_batch_sz ) times. */
263 : fd_shredder_t * fd_shredder_skip_batch( fd_shredder_t * shredder,
264 : ulong entry_batch_sz,
265 : ulong slot,
266 : ulong shred_type );
267 :
268 : /* fd_shredder_next_fec_set extracts the next FEC set from the in
269 : progress batch. Computes the entirety of both data and parity
270 : shreds, including the parity information, Merkle proofs, and
271 : signatures. Additionally computes the destination index for each
272 : shred. Stores the generated FEC set in result, which is clobbered.
273 : Populates all fields of result except for {data,parity}_shred_present
274 : (which is only used for reconstruction).
275 :
276 : shredder must be a valid local join, and signing_private_key must
277 : point to the first byte of an Ed25519 private key that will be used
278 : to sign the shreds. It must correspond to the public key passed in
279 : the shredder constructor.
280 :
281 : chained_merkle_root is either NULL or a pointer to a 32-byte buffer
282 : containing the chained merkle root (the merkle root of the previous
283 : FEC set). If not NULL, chained_merkle_root is updated with the new
284 : root. This determines the variant of shreds created.
285 :
286 : out_merkle_root is an optional parameter: if non-NULL the merkle root
287 : of the extracted FEC set will be copied into out_merkle_root on
288 : success. Assumes out_merkle_root pointers to a buffer of at least 32
289 : bytes (FD_SHRED_MERKLE_ROOT_SZ).
290 :
291 : Returns result on success and NULL if all of the entry batch's data
292 : has been consumed already by previous calls to this function. On
293 : success, advances the position of the shredder within the batch
294 : without finishing the batch. */
295 : fd_fec_set_t *
296 : fd_shredder_next_fec_set( fd_shredder_t * shredder,
297 : fd_fec_set_t * result,
298 : uchar * chained_merkle_root,
299 : uchar * out_merkle_root );
300 :
301 : /* fd_shredder_fini_batch finishes the in process batch. shredder must
302 : be a valid local join that is currently in a batch. Upon return,
303 : shredder will no longer be in a batch and will be ready to begin a
304 : new batch with init_batch. Returns shredder. */
305 : fd_shredder_t * fd_shredder_fini_batch( fd_shredder_t * shredder );
306 :
307 : #endif /* HEADER_fd_src_disco_shred_fd_shredder_h */
|
