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/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 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, ushort shred_version );
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 :
91 : /* fd_shredder_count_{data_shreds, parity_shreds, fec_sets}: returns the
92 : number of data shreds, parity shreds, or FEC sets (respectively)
93 : required to send an entry batch of size `sz_bytes` bytes, with shreds
94 : of type `type`. `type` must be one of FD_SHRED_TYPE_MERKLE_{DATA,
95 : DATA_CHAINED, DATA_CHAINED_RESIGNED}. For data and parity shred counts,
96 : this is the total count across all FEC sets.
97 :
98 : We use the same policy for shredding that the Agave validator uses,
99 : even though it's a bit strange. If the entry batch size is an exact
100 : multiple of the default FEC set total data size of 31840, then we
101 : make sz_byte/31840 FEC sets, where each FEC set has 32 data shreds,
102 : and each data shred contains 995 bytes of payload. Otherwise, we
103 : make 31840 B FEC sets until we have less than 63680 bytes left, and
104 : we make one oddly sized FEC set for the remaining payload.
105 :
106 : (Note: while this is true for the logic of the shredder, the way our
107 : shred tile works with watermark implies that this never happens, and
108 : the only case that happens in practice is the "oddly sized" FEC set
109 : described below.)
110 :
111 : Computing this "oddly sized" FEC set is a bit strange because the
112 : number of shreds in the set depends on the amount of payload in each
113 : shred, which depends on the depth of the Merkle tree required to
114 : store all the shreds in the set, which depends on the number of
115 : shreds in the set. The spec gives the formula:
116 : payload_bytes_per_shred = 1115 - 20*ceiling( log2( num_shreds ) )
117 : where num_shreds = num_data_shreds + num_parity_shreds, and
118 : num_data_shreds = payload_sz_remaining/payload_bytes_per_shred and
119 : num_parity_shreds is a non-decreasing function of num_data_shreds.
120 :
121 : The Agave validator solves this formula by brute force.
122 : Instead, we'll do the computation ahead of time to build a nice
123 : table:
124 : Case payload_bytes_per_shred
125 : 1 <= D <= 9135 1015
126 : 8956 <= D <= 31840 995
127 : 31201 <= D <= 62400 975
128 : 61121 <= D <= 63984 955
129 :
130 : Where D is the remaining payload size in bytes. You may notice the
131 : cases overlap. That's the gross outcome of using a gross formula.
132 : There are two legitimate ways to send certain payload sizes. We
133 : always pick the larger value of payload_bytes_per_shred.
134 :
135 : In short, the relationship between the constants that appear in the
136 : code below is as follow:
137 :
138 : Unchained Merkle Shreds.
139 : - data_sz: 9135 == payload_sz: 1015 * 9 shreds (merkle tree height: 5)
140 : - data_sz: 31840 == payload_sz: 995 * 32 shreds (merkle tree height: 6)
141 : - data_sz: 62400 == payload_sz: 975 * 64 shreds (merkle tree height: 7)
142 : - payload_sz: 955 (merkle tree height: 8)
143 : note: payload_sz decreases by 20 bytes as the merkle tree height increases.
144 : note 2: in the first entry, 9 data shreds + 23 corresponding parity shreds
145 : total to 32 shreds, hence a merkle tree of height 5.
146 :
147 : Chained Merkle Shreds.
148 : - data_sz: 8847 == payload_sz: 983 * 9 shreds (merkle tree height: 5)
149 : - data_sz: 30816 == payload_sz: 963 * 32 shreds (merkle tree height: 6)
150 : - data_sz: 60352 == payload_sz: 943 * 64 shreds (merkle tree height: 7)
151 : - payload_sz: 923 (merkle tree height: 8)
152 : note: payload_sz is the unchained payload_sz - 32 bytes (for chained merkle root).
153 :
154 : Resigned Chained Merkle Shreds.
155 : - data_sz: 8271 == payload_sz: 919 * 9 shreds (merkle tree height: 5)
156 : - data_sz: 28768 == payload_sz: 899 * 32 shreds (merkle tree height: 6)
157 : - data_sz: 56256 == payload_sz: 879 * 64 shreds (merkle tree height: 7)
158 : - payload_sz: 859 (merkle tree height: 8)
159 : note: payload_sz is the chained payload_sz - 64 bytes (for signature). */
160 :
161 32505840 : #define FD_SHREDDER_NORMAL_FEC_SET_PAYLOAD_SZ (31840UL)
162 31937286 : #define FD_SHREDDER_CHAINED_FEC_SET_PAYLOAD_SZ (30816UL) /* -32 bytes * 32 shreds */
163 32022390 : #define FD_SHREDDER_RESIGNED_FEC_SET_PAYLOAD_SZ (28768UL) /* -64 bytes * 32 shreds */
164 :
165 : #define FD_SHREDDER_NORMAL_FEC_SET_RAW_BUF_SZ (63679UL) /* 2 * ...PAYLOAD_SZ - 1 */
166 : #define FD_SHREDDER_CHAINED_FEC_SET_RAW_BUF_SZ (61631UL) /* 2 * ...PAYLOAD_SZ - 1 */
167 : #define FD_SHREDDER_RESIGNED_FEC_SET_RAW_BUF_SZ (57535UL) /* 2 * ...PAYLOAD_SZ - 1 */
168 :
169 : FD_FN_CONST static inline ulong
170 34207599 : fd_shredder_count_fec_sets( ulong sz_bytes, ulong type ) {
171 : /* In the case of normal fec_sets, if sz_bytes < 2*31840, we make 1 FEC set.
172 : If sz_bytes is a multiple of 31840, we make exactly sz_bytes/31840 sets.
173 : Otherwise, we make floor(sz_bytes/31840)-1 normal set + one odd-sized set.
174 : In the case of chained and (chained+)resigned fec_sets, the thresholds are
175 : adjusted accordingly. */
176 34207599 : if( FD_UNLIKELY( fd_shred_is_resigned( type ) ) ) {
177 11354808 : return fd_ulong_max( sz_bytes, 2UL*FD_SHREDDER_RESIGNED_FEC_SET_PAYLOAD_SZ - 1UL ) / FD_SHREDDER_RESIGNED_FEC_SET_PAYLOAD_SZ;
178 22852791 : } else if( FD_LIKELY( fd_shred_is_chained( type ) ) ) {
179 11330538 : return fd_ulong_max( sz_bytes, 2UL*FD_SHREDDER_CHAINED_FEC_SET_PAYLOAD_SZ - 1UL ) / FD_SHREDDER_CHAINED_FEC_SET_PAYLOAD_SZ;
180 11330538 : }
181 11522253 : return fd_ulong_max( sz_bytes, 2UL*FD_SHREDDER_NORMAL_FEC_SET_PAYLOAD_SZ - 1UL ) / FD_SHREDDER_NORMAL_FEC_SET_PAYLOAD_SZ;
182 34207599 : }
183 : FD_FN_CONST static inline ulong
184 11879298 : fd_shredder_count_data_shreds( ulong sz_bytes, ulong type ) {
185 11879298 : ulong normal_sets = fd_shredder_count_fec_sets( sz_bytes, type ) - 1UL;
186 11879298 : ulong shreds = normal_sets * 32UL;
187 11879298 : if( FD_UNLIKELY( fd_shred_is_resigned( type ) ) ) {
188 3941100 : ulong remaining_bytes = sz_bytes - normal_sets * FD_SHREDDER_RESIGNED_FEC_SET_PAYLOAD_SZ;
189 3941100 : if( FD_UNLIKELY( remaining_bytes <= 8271UL ) ) shreds += fd_ulong_max( 1UL, (remaining_bytes + 918UL)/ 919UL );
190 3841842 : else if( FD_LIKELY( remaining_bytes <= 28768UL ) ) shreds += (remaining_bytes + 898UL)/ 899UL;
191 3427287 : else if( FD_LIKELY( remaining_bytes <= 56256UL ) ) shreds += (remaining_bytes + 878UL)/ 879UL;
192 145806 : else shreds += (remaining_bytes + 858UL)/ 859UL;
193 7938198 : } else if( FD_LIKELY( fd_shred_is_chained( type ) ) ) {
194 3922818 : ulong remaining_bytes = sz_bytes - normal_sets * FD_SHREDDER_CHAINED_FEC_SET_PAYLOAD_SZ;
195 3922818 : if( FD_UNLIKELY( remaining_bytes <= 8847UL ) ) shreds += fd_ulong_max( 1UL, (remaining_bytes + 982UL)/ 983UL );
196 3816648 : else if( FD_LIKELY( remaining_bytes <= 30816UL ) ) shreds += (remaining_bytes + 962UL)/ 963UL;
197 3414987 : else if( FD_LIKELY( remaining_bytes <= 60352UL ) ) shreds += (remaining_bytes + 942UL)/ 943UL;
198 138132 : else shreds += (remaining_bytes + 922UL)/ 923UL;
199 4015380 : } else {
200 4015380 : ulong remaining_bytes = sz_bytes - normal_sets * FD_SHREDDER_NORMAL_FEC_SET_PAYLOAD_SZ;
201 4015380 : if( FD_UNLIKELY( remaining_bytes <= 9135UL ) ) shreds += fd_ulong_max( 1UL, (remaining_bytes + 1014UL)/1015UL );
202 3905754 : else if( FD_LIKELY( remaining_bytes <= 31840UL ) ) shreds += (remaining_bytes + 994UL)/ 995UL;
203 3409440 : else if( FD_LIKELY( remaining_bytes <= 62400UL ) ) shreds += (remaining_bytes + 974UL)/ 975UL;
204 134295 : else shreds += (remaining_bytes + 954UL)/ 955UL;
205 4015380 : }
206 11879298 : return shreds;
207 11879298 : }
208 : FD_FN_CONST static inline ulong
209 11879298 : fd_shredder_count_parity_shreds( ulong sz_bytes, ulong type ) {
210 11879298 : ulong normal_sets = fd_shredder_count_fec_sets( sz_bytes, type ) - 1UL;
211 11879298 : ulong shreds = normal_sets * 32UL;
212 11879298 : if( FD_UNLIKELY( fd_shred_is_resigned( type ) ) ) {
213 3941100 : ulong remaining_bytes = sz_bytes - normal_sets * FD_SHREDDER_RESIGNED_FEC_SET_PAYLOAD_SZ;
214 3941100 : if( FD_UNLIKELY( remaining_bytes <= 8271UL ) ) shreds += fd_shredder_data_to_parity_cnt[ fd_ulong_max( 1UL, (remaining_bytes + 918UL)/ 919UL ) ];
215 3841842 : else if( FD_LIKELY( remaining_bytes <= 28768UL ) ) shreds += fd_shredder_data_to_parity_cnt[ (remaining_bytes + 898UL)/ 899UL ];
216 3427287 : else if( FD_LIKELY( remaining_bytes <= 56256UL ) ) shreds += (remaining_bytes + 878UL)/ 879UL;
217 145806 : else shreds += (remaining_bytes + 858UL)/ 859UL;
218 7938198 : } else if( FD_LIKELY( fd_shred_is_chained( type ) ) ) {
219 3922818 : ulong remaining_bytes = sz_bytes - normal_sets * FD_SHREDDER_CHAINED_FEC_SET_PAYLOAD_SZ;
220 3922818 : if( FD_UNLIKELY( remaining_bytes <= 8847UL ) ) shreds += fd_shredder_data_to_parity_cnt[ fd_ulong_max( 1UL, (remaining_bytes + 982UL)/ 983UL ) ];
221 3816648 : else if( FD_LIKELY( remaining_bytes <= 30816UL ) ) shreds += fd_shredder_data_to_parity_cnt[ (remaining_bytes + 962UL)/ 963UL ];
222 3414987 : else if( FD_LIKELY( remaining_bytes <= 60352UL ) ) shreds += (remaining_bytes + 942UL)/ 943UL;
223 138132 : else shreds += (remaining_bytes + 922UL)/ 923UL;
224 4015380 : } else {
225 4015380 : ulong remaining_bytes = sz_bytes - normal_sets * FD_SHREDDER_NORMAL_FEC_SET_PAYLOAD_SZ;
226 4015380 : if( FD_UNLIKELY( remaining_bytes <= 9135UL ) ) shreds += fd_shredder_data_to_parity_cnt[ fd_ulong_max( 1UL, (remaining_bytes + 1014UL)/1015UL ) ];
227 3905754 : else if( FD_LIKELY( remaining_bytes <= 31840UL ) ) shreds += fd_shredder_data_to_parity_cnt[ (remaining_bytes + 994UL)/ 995UL ];
228 3409440 : else if( FD_LIKELY( remaining_bytes <= 62400UL ) ) shreds += (remaining_bytes + 974UL)/ 975UL;
229 134295 : else shreds += (remaining_bytes + 954UL)/ 955UL;
230 4015380 : }
231 11879298 : return shreds;
232 11879298 : }
233 :
234 : /* fd_shredder_init_batch begins the computation of shreds for an entry
235 : batch. shredder must be a valid local join. entry_batch points to
236 : the first byte of a region of memory entry_batch_sz bytes long.
237 : entry_batch_sz must be strictly positive. The shredder object
238 : retains a read interest in the region of memory [entry_batch,
239 : entry_batch+entry_batch_sz) that lasts until fd_shredder_fini_batch
240 : is called. This region of memory should not be modified while in use
241 : by the shredder. meta contains the metadata for the batch that is
242 : necessary for shred production. The shredder object does not retain
243 : a read interest in the memory pointed to by meta.
244 :
245 : Returns shredder, which will be in a new batch when the function
246 : returns. */
247 : fd_shredder_t * fd_shredder_init_batch( fd_shredder_t * shredder,
248 : void const * entry_batch,
249 : ulong entry_batch_sz,
250 : ulong slot,
251 : fd_entry_batch_meta_t const * meta );
252 :
253 : /* fd_shredder_skip_batch updates the shredder state as necessary
254 : to skip processing this current batch. shredder must be a valid
255 : local join. entry_batch_sz must be strictly positive.
256 :
257 : Returns shredder, which will have data and parity shred indices
258 : updated as if the caller had called fd_shredder_init_batch with
259 : a batch of the specified size, followed by fd_shredder_next_fec_set
260 : exactly fd_shredder_count_fec_sets( entry_batch_sz ) times. */
261 : fd_shredder_t * fd_shredder_skip_batch( fd_shredder_t * shredder,
262 : ulong entry_batch_sz,
263 : ulong slot,
264 : ulong shred_type );
265 :
266 : /* fd_shredder_next_fec_set extracts the next FEC set from the in
267 : progress batch. Computes the entirety of both data and parity
268 : shreds, including the parity information, Merkle proofs, and
269 : signatures. Additionally computes the destination index for each
270 : shred. Stores the generated FEC set in result, which is clobbered.
271 : Populates all fields of result except for {data,parity}_shred_present
272 : (which is only used for reconstruction).
273 :
274 : shredder must be a valid local join, and signing_private_key must
275 : point to the first byte of an Ed25519 private key that will be used
276 : to sign the shreds. It must correspond to the public key passed in
277 : the shredder constructor.
278 :
279 : chained_merkle_root is either NULL or a pointer to a 32-byte buffer
280 : containing the chained merkle root (the merkle root of the previous
281 : FEC set). If not NULL, chained_merkle_root is updated with the new
282 : root. This determines the variant of shreds created.
283 :
284 : Returns result on success and NULL if all of the entry batch's data
285 : has been consumed already by previous calls to this function. On
286 : success, advances the position of the shredder within the batch
287 : without finishing the batch. */
288 : fd_fec_set_t *
289 : fd_shredder_next_fec_set( fd_shredder_t * shredder,
290 : fd_fec_set_t * result,
291 : uchar * chained_merkle_root );
292 :
293 : /* fd_shredder_fini_batch finishes the in process batch. shredder must
294 : be a valid local join that is currently in a batch. Upon return,
295 : shredder will no longer be in a batch and will be ready to begin a
296 : new batch with init_batch. Returns shredder. */
297 : fd_shredder_t * fd_shredder_fini_batch( fd_shredder_t * shredder );
298 :
299 : #endif /* HEADER_fd_src_disco_shred_fd_shredder_h */
|
