Line data Source code
1 : #ifndef HEADER_fd_src_ballet_shred_fd_shred_h 2 : #define HEADER_fd_src_ballet_shred_fd_shred_h 3 : 4 : #include <stdio.h> 5 : /* Shreds form the on-wire representation of Solana block data 6 : optimized for transmission over unreliable links/WAN. 7 : 8 : ### Layout 9 : 10 : Each shred is 1228 bytes long. 11 : 12 : +------------------------+ 13 : | Common Shred Header | 83 bytes 14 : +------------------------+ 15 : | Data Header | 5 bytes 16 : | or Coding Header | or 6 bytes 17 : +------------------------+ 18 : | | variable 19 : | Payload | length 20 : | | 21 : +------------------------+ 22 : 23 : for Merkle shreds, followed by: 24 : 25 : +------------------------+ 26 : | (Chained merkle root) | 32 bytes 27 : +------------------------+ 28 : +------------------------+ 29 : | Merkle node #0 (root) | 20 bytes 30 : +------------------------+ 31 : | Merkle node #1 | 20 bytes 32 : .......................... 33 : 34 : for resigned shreds shreds, followed by: 35 : 36 : +------------------------+ 37 : | signature | 64 bytes 38 : .......................... 39 : 40 : ### Shredding 41 : 42 : For a given input data blob (usually an entry batch), 43 : data shreds are derived by simply splitting up the blob into subslices. 44 : 45 : Each shred is sized such that it fits into a single UDP packet, 46 : i.e. currently bound by the generally accepted IPv6 MTU of 1280 bytes. 47 : 48 : ### Forward Error Correction 49 : 50 : Coding shreds implement Reed-Solomon error correction to provide tolerance against packet loss. 51 : 52 : Each data shred is first assigned an FEC set. 53 : For the vector of data shreds in each set, a corresponding vector of coding shreds contains parity data. 54 : 55 : FEC sets and entry batches do not necessarily align. 56 : 57 : ### Merkle Inclusion Proofs 58 : 59 : Data and coding shreds come in two variants respectively: legacy and merkle. 60 : Merkle shreds extend legacy shreds by adding FEC set inclusion proofs. 61 : 62 : It allows the block producer to commit to the vector of shreds that make up an FEC set. 63 : The inclusion proof is used to verify whether a shred is part of the FEC set commitment. 64 : 65 : The length of the inclusion proof is indicated by the variant field. 66 : 67 : ### resigned shreds 68 : 69 : Resigned shreds allow for an additional signature to be added on to lock down 70 : the retransmitter for turbine propagation 71 : 72 : ### Authentication 73 : 74 : Shreds are signed by the block producer. 75 : Consequentially, only the block producer is able to create valid shreds for any given block. */ 76 : 77 : #include "../fd_ballet.h" 78 : 79 : /* FD_SHRED_MAX_SZ: The max byte size of a shred. 80 : This limit derives from the IPv6 MTU of 1280 bytes, minus 48 bytes 81 : for the UDP/IPv6 headers and another 4 bytes for good measure. Most 82 : shreds are this size, but Merkle data shreds may be smaller. */ 83 102428826 : #define FD_SHRED_MAX_SZ (1228UL) 84 : /* FD_SHRED_MIN_SZ: The minimum byte size of a shred. 85 : A code shred of the max size covers a data shred of the minimum size 86 : with no padding. */ 87 102427233 : #define FD_SHRED_MIN_SZ (1203UL) 88 : /* FD_SHRED_DATA_HEADER_SZ: size of all headers for data type shreds. */ 89 100564068 : #define FD_SHRED_DATA_HEADER_SZ (0x58UL) 90 : /* FD_SHRED_CODE_HEADER_SZ: size of all headers for coding type shreds. */ 91 51177402 : #define FD_SHRED_CODE_HEADER_SZ (0x59UL) 92 : 93 : /* FD_SHRED_TYPE_* identifies the type of a shred. 94 : It is located at the four high bits of byte 0x40 (64) of the shred header 95 : and can be extracted using the fd_shred_type() function. */ 96 : /* FD_SHRED_TYPE_LEGACY_DATA: A shred carrying raw binary data. */ 97 105967074 : #define FD_SHRED_TYPE_LEGACY_DATA ((uchar)0xA0) 98 : /* FD_SHRED_TYPE_LEGACY_CODE: A shred carrying Reed-Solomon ECC. */ 99 : #define FD_SHRED_TYPE_LEGACY_CODE ((uchar)0x50) 100 : /* FD_SHRED_TYPE_MERKLE_DATA: A shred carrying raw binary data and a merkle inclusion proof. */ 101 54984906 : #define FD_SHRED_TYPE_MERKLE_DATA ((uchar)0x80) 102 : /* FD_SHRED_TYPE_MERKLE_CODE: A shred carrying Reed-Solomon ECC and a merkle inclusion proof. */ 103 153215931 : #define FD_SHRED_TYPE_MERKLE_CODE ((uchar)0x40) 104 : /* FD_SHRED_TYPE_MERKLE_DATA_CHAINED: A shred carrying raw binary data and a chained merkle inclusion proof. */ 105 23292 : #define FD_SHRED_TYPE_MERKLE_DATA_CHAINED ((uchar)0x90) 106 : /* FD_SHRED_TYPE_MERKLE_CODE_CHAINED: A shred carrying Reed-Solomon ECC and a chained merkle inclusion proof. */ 107 22428 : #define FD_SHRED_TYPE_MERKLE_CODE_CHAINED ((uchar)0x60) 108 : 109 : /* FD_SHRED_TYPE_MERKLE_DATA_CHAINED_RESIGNED: A shred carrying raw binary data and a chained merkle inclusion proof and resigned. */ 110 101486664 : #define FD_SHRED_TYPE_MERKLE_DATA_CHAINED_RESIGNED ((uchar)0xB0) 111 : /* FD_SHRED_TYPE_MERKLE_CODE_CHAINED_RESIGNED: A shred carrying Reed-Solomon ECC and a chained merkle inclusion proof and resigned. */ 112 101485032 : #define FD_SHRED_TYPE_MERKLE_CODE_CHAINED_RESIGNED ((uchar)0x70) 113 : 114 : /* FD_SHRED_TYPEMASK_DATA: bitwise AND with type matches data shred */ 115 : #define FD_SHRED_TYPEMASK_DATA FD_SHRED_TYPE_MERKLE_DATA 116 : /* FD_SHRED_TYPEMASK_CODE: bitwise AND with type matches code shred */ 117 101457426 : #define FD_SHRED_TYPEMASK_CODE FD_SHRED_TYPE_MERKLE_CODE 118 : 119 : /* FD_SHRED_MERKLE_ROOT_SZ: the size of a merkle tree root in bytes. */ 120 21945 : #define FD_SHRED_MERKLE_ROOT_SZ (32UL) 121 : /* FD_SHRED_MERKLE_NODE_SZ: the size of a merkle inclusion proof node in bytes. */ 122 102946059 : #define FD_SHRED_MERKLE_NODE_SZ (20UL) 123 : /* FD_SHRED_MERKLE_LAYER_CNT: the count of inclusion proof layers in the binary merkle tree. */ 124 159 : #define FD_SHRED_MERKLE_LAYER_CNT (10UL) 125 : /* FD_SHRED_SIGNATURE_SZ: the size of a signature in a shred. */ 126 101467497 : #define FD_SHRED_SIGNATURE_SZ (64UL) 127 : /* A merkle inclusion proof node. */ 128 : typedef uchar fd_shred_merkle_t[FD_SHRED_MERKLE_NODE_SZ]; 129 : 130 : /* Constants relating to the data shred "flags" field. */ 131 : 132 : /* Mask of the "reference tick" field in shred.data.flags */ 133 0 : #define FD_SHRED_DATA_REF_TICK_MASK ((uchar)0x3f) 134 : /* Mask of the "slot complete" bit in shred.data.flags 135 : Indicates the last shred in a slot. */ 136 0 : #define FD_SHRED_DATA_FLAG_SLOT_COMPLETE ((uchar)0x80) 137 : /* Mask of the "data batch complete" bit in shred.data.flags */ 138 : #define FD_SHRED_DATA_FLAG_DATA_COMPLETE ((uchar)0x40) 139 : 140 : /* Maximum number of data shreds in a slot, also maximum number of parity shreds in a slot */ 141 0 : #define FD_SHRED_MAX_PER_SLOT (1 << 15UL) /* 32,768 shreds */ 142 : 143 : /* Offset of the shred variant. Used for parsing. */ 144 : #define FD_SHRED_VARIANT_OFF 0x40 145 : 146 : /* Firedancer-specific internal error codes. 147 : 148 : These are not part of the Solana protocol. */ 149 : 150 0 : #define FD_SHRED_EBATCH 0x4000 /* End of batch reached (success) 151 : no more shreds and found FD_SHRED_DATA_FLAG_DATA_COMPLETE */ 152 0 : #define FD_SHRED_ESLOT 0x8000 /* End of slot reached (success) 153 : no more shreds and found FD_SHRED_DATA_FLAG_SLOT_COMPLETE */ 154 0 : #define FD_SHRED_ENOMEM 12 /* Error: Target buffer too small */ 155 0 : #define FD_SHRED_EINVAL 22 /* Error: Invalid shred data */ 156 0 : #define FD_SHRED_EPIPE 32 /* Error: Expected data in source buffer, got EOF */ 157 : 158 : /* Primary shred data structure. 159 : Relies heavily on packed fields and unaligned memory accesses. */ 160 : struct __attribute__((packed)) fd_shred { 161 : /* Ed25519 signature over the shred 162 : 163 : For legacy type shreds, signs over content of the shred structure past this signature field. 164 : For merkle type shreds, signs over the first node of the inclusion proof (merkle root). */ 165 : /* 0x00 */ fd_ed25519_sig_t signature; 166 : 167 : /* Shred variant specifier 168 : Consists of two four bit fields. (Deliberately not using bit fields here) 169 : 170 : The high four bits indicate the shred type: 171 : - 0101: legacy code 172 : - 1010: legacy data 173 : - 0100: merkle code 174 : - 0110: merkle code (chained) 175 : - 0111: merkle code (chained resigned) 176 : - 1000: merkle data 177 : - 1001: merkle data (chained) 178 : - 1011: merkle data (chained resigned) 179 : 180 : For legacy type shreds, the low four bits are set to static patterns. 181 : For merkle type shreds, the low four bits are set to the number of non-root nodes in the inclusion proof. 182 : For merkle code type shreds, the 3rd highest bit represents if the merkle tree is chained. 183 : For merkle data type shreds, the 4th highest bit represents if the merkle tree is chained. 184 : For merkle code type shreds, the 4th highest bit represents if the shred is resigned. 185 : For merkle data type shreds, the 3th highest bit represents if the shred is resigned. 186 : */ 187 : /* 0x40 */ uchar variant; 188 : 189 : /* Slot number that this shred is part of */ 190 : /* 0x41 */ ulong slot; 191 : 192 : /* Index of this shred within the slot */ 193 : /* 0x49 */ uint idx; 194 : 195 : /* Hash of the genesis version and historical hard forks of the current chain */ 196 : /* 0x4d */ ushort version; 197 : 198 : /* Index into the vector of FEC sets for this slot. For data shreds, fec_set_idx<=idx. */ 199 : /* 0x4f */ uint fec_set_idx; 200 : 201 : union { 202 : /* Common data shred header */ 203 : struct __attribute__((packed)) { 204 : /* Slot number difference between this block and the parent block. 205 : parent_off <= slot. 206 : Always greater than zero, except for slot 0, in which case the 207 : previous invariant forces this to be 0. */ 208 : /* 0x53 */ ushort parent_off; 209 : 210 : /* Bit field (MSB first) 211 : See FD_SHRED_DATA_FLAG_* 212 : 213 : [XX.. ....] Block complete? 0b00=no 0b01=no 0b11=yes (implies Entry batch complete) 214 : [.X.. ....] Entry batch complete? 0b0=no 0b1=yes 215 : [..XX XXXX] Reference tick number */ 216 : /* 0x55 */ uchar flags; 217 : 218 : /* Shred size: size of data shred headers (88 bytes) + payload length */ 219 : /* 0x56 */ ushort size; 220 : } data; 221 : 222 : /* Common coding shred header */ 223 : struct __attribute__((packed)) { 224 : /* Total number of data shreds in slot. Must be positive. */ 225 : /* 0x53 */ ushort data_cnt; 226 : 227 : /* Total number of coding shreds in slot. Must be positive. */ 228 : /* 0x55 */ ushort code_cnt; 229 : 230 : /* Index within the vector of coding shreds in slot. In [0, 231 : code_cnt). Also, shred.code.idx <= shred.idx. */ 232 : /* 0x57 */ ushort idx; 233 : } code; 234 : }; 235 : }; 236 : typedef struct fd_shred fd_shred_t; 237 : 238 : FD_PROTOTYPES_BEGIN 239 : 240 : /* fd_shred_parse: Parses and validates an untrusted shred stored in 241 : bytes buf[i] for i in [0, sz). sz must be at least FD_SHRED_MIN_SZ 242 : bytes. Allows trailing data. 243 : 244 : The returned pointer either equals the input pointer or is NULL if 245 : the given shred is malformed or violates any invariants described 246 : above. */ 247 : FD_FN_PURE fd_shred_t const * 248 : fd_shred_parse( uchar const * buf, 249 : ulong sz ); 250 : 251 : /* fd_shred_type: Returns the value of the shred's type field. (FD_SHRED_TYPE_*) */ 252 : FD_FN_CONST static inline uchar 253 308909103 : fd_shred_type( uchar variant ) { 254 308909103 : return variant & 0xf0; 255 308909103 : } 256 : 257 : /* fd_shred_variant: Returns the encoded variant field 258 : given the shred type and merkle proof length. */ 259 : FD_FN_CONST static inline uchar 260 : fd_shred_variant( uchar type, 261 101837526 : uchar merkle_cnt ) { 262 101837526 : if( FD_LIKELY( type==FD_SHRED_TYPE_LEGACY_DATA ) ) 263 3 : merkle_cnt = 0x05; 264 101837526 : if( FD_LIKELY( type==FD_SHRED_TYPE_LEGACY_CODE ) ) 265 3 : merkle_cnt = 0x0a; 266 101837526 : return (uchar)(type | merkle_cnt); 267 101837526 : } 268 : 269 : FD_FN_PURE static inline ulong 270 101455980 : fd_shred_sz( fd_shred_t const * shred ) { 271 101455980 : uchar type = fd_shred_type( shred->variant ); 272 101455980 : return fd_ulong_if( 273 101455980 : type & FD_SHRED_TYPEMASK_CODE, 274 101455980 : FD_SHRED_MAX_SZ, 275 101455980 : fd_ulong_if( type==FD_SHRED_TYPE_LEGACY_DATA, shred->data.size, FD_SHRED_MIN_SZ) 276 101455980 : ); /* Legacy data */ 277 101455980 : } 278 : 279 : /* fd_shred_header_sz: Returns the header size of a shred. 280 : Returns zero if the shred has an invalid variant. 281 : 282 : Accesses offsets up to FD_SHRED_HEADER_MIN_SZ. */ 283 : FD_FN_CONST static inline ulong 284 9909 : fd_shred_header_sz( uchar variant ) { 285 9909 : uchar type = fd_shred_type( variant ); 286 9909 : if( FD_LIKELY( type & FD_SHRED_TYPEMASK_DATA ) ) 287 4524 : return FD_SHRED_DATA_HEADER_SZ; 288 5385 : if( FD_LIKELY( type & FD_SHRED_TYPEMASK_CODE ) ) 289 5385 : return FD_SHRED_CODE_HEADER_SZ; 290 0 : return 0; 291 5385 : } 292 : 293 : /* fd_shred_merkle_cnt: Returns number of nodes in the merkle inclusion 294 : proof. Note that this excludes the root. Returns zero if the given 295 : shred is not a merkle variant. */ 296 : FD_FN_CONST static inline uint 297 101470254 : fd_shred_merkle_cnt( uchar variant ) { 298 101470254 : uchar type = fd_shred_type( variant ); 299 101470254 : if( FD_UNLIKELY( ( type == FD_SHRED_TYPE_LEGACY_DATA ) | ( type == FD_SHRED_TYPE_LEGACY_CODE ) ) ) 300 45 : return 0; 301 101470209 : return (variant&0xfU); 302 101470254 : } 303 : 304 : /* fd_shred_merkle_sz: Returns the size in bytes of the merkle inclusion proof. 305 : Returns zero if the given shred is not a merkle variant. */ 306 : FD_FN_CONST static inline ulong 307 101461065 : fd_shred_merkle_sz( uchar variant ) { 308 101461065 : return fd_shred_merkle_cnt( variant ) * FD_SHRED_MERKLE_NODE_SZ; 309 101461065 : } 310 : 311 : 312 : /* fd_shred_is_chained: Returns true if the shred is a chained merkle data or code shred. */ 313 : FD_FN_CONST static inline uchar 314 18831 : fd_shred_is_chained( ulong type ) { 315 18831 : return (uchar)( 316 18831 : ( type == FD_SHRED_TYPE_MERKLE_DATA_CHAINED ) 317 18831 : | ( type == FD_SHRED_TYPE_MERKLE_CODE_CHAINED ) 318 18831 : | ( type == FD_SHRED_TYPE_MERKLE_DATA_CHAINED_RESIGNED ) 319 18831 : | ( type == FD_SHRED_TYPE_MERKLE_CODE_CHAINED_RESIGNED ) ); 320 18831 : } 321 : 322 : /* fd_shred_is_resigned: Returns true if the shred is resigned by the retransmitter */ 323 : FD_FN_CONST static inline uchar 324 101464284 : fd_shred_is_resigned( ulong type ) { 325 101464284 : return ( type == FD_SHRED_TYPE_MERKLE_DATA_CHAINED_RESIGNED ) 326 101464284 : | ( type == FD_SHRED_TYPE_MERKLE_CODE_CHAINED_RESIGNED ); 327 101464284 : } 328 : 329 : /* fd_shred_is_{data,code} return 1 if the provided shred type is one of 330 : the data (or code, respectively) types, and 0 if not. The value 331 : provided for type must be a valid shred type (one of the 332 : FD_SHRED_TYPE_* values). For the purposes of these functions, 333 : properties beyond data/code are ignored; e.g. a chained resigned 334 : Merkle data shred is considered a data shred. */ 335 3522 : FD_FN_CONST static inline uchar fd_shred_is_data( ulong type ) { return (type & 0xC0UL)==0x80UL; } 336 294 : FD_FN_CONST static inline uchar fd_shred_is_code( ulong type ) { return (type & 0xC0UL)==0x40UL; } 337 : 338 : /* fd_shred_swap_type: changes data into code or vice versa without 339 : affecting leagacy, merkle, chained, or resigned status. For example, 340 : fd_shred_swap_type( chained resigned data ) == chained resigned code. 341 : fd_shred_swap_type( merkle code ) == merkle data. */ 342 : FD_FN_CONST static inline uchar 343 3057 : fd_shred_swap_type( ulong type ) { 344 : /* Swap bits 4 and 5. Swap bits 6 and 7. */ 345 3057 : return (uchar)(((type & 0x50UL)<<1) | ((type&0xA0UL)>>1)); 346 3057 : } 347 : 348 : /* fd_shred_payload_sz: Returns the payload size of a shred. 349 : Undefined behavior if the shred has not passed `fd_shred_parse`. */ 350 : FD_FN_PURE static inline ulong 351 294 : fd_shred_payload_sz( fd_shred_t const * shred ) { 352 294 : ulong type = fd_shred_type( shred->variant ); 353 294 : if( FD_LIKELY( type & FD_SHRED_TYPEMASK_DATA ) ) { 354 147 : return shred->data.size - FD_SHRED_DATA_HEADER_SZ; 355 147 : } else { 356 147 : return fd_shred_sz( shred ) - FD_SHRED_CODE_HEADER_SZ 357 147 : - fd_shred_merkle_sz( shred->variant ) 358 147 : - fd_ulong_if( fd_shred_is_chained( type ), FD_SHRED_MERKLE_ROOT_SZ, 0 ) 359 147 : - fd_ulong_if( fd_shred_is_resigned( type ), FD_SHRED_SIGNATURE_SZ, 0 ); 360 147 : } 361 294 : } 362 : 363 : /* fd_shred_merkle_off: Returns the byte offset of the merkle inclusion proof of a shred. 364 : 365 : The provided shred must have passed validation in fd_shred_parse(). */ 366 : FD_FN_PURE static inline ulong 367 101449563 : fd_shred_merkle_off( fd_shred_t const * shred ) { 368 101449563 : ulong type = fd_shred_type( shred->variant ); 369 101449563 : return fd_shred_sz( shred ) 370 101449563 : - fd_shred_merkle_sz( shred->variant ) 371 101449563 : - fd_ulong_if( fd_shred_is_resigned( type ), FD_SHRED_SIGNATURE_SZ, 0 ); 372 101449563 : } 373 : 374 : /* fd_shred_merkle_nodes: Returns a pointer to the shred's merkle proof data. 375 : 376 : The provided shred must have passed validation in fd_shred_parse(). */ 377 : FD_FN_PURE static inline fd_shred_merkle_t const * 378 3009 : fd_shred_merkle_nodes( fd_shred_t const * shred ) { 379 3009 : uchar const * ptr = (uchar const *)shred; 380 3009 : ptr += fd_shred_merkle_off( shred ); 381 3009 : return (fd_shred_merkle_t const *)ptr; 382 3009 : } 383 : 384 : /* fd_shred_data_payload: Returns a pointer to a data shred payload. 385 : 386 : The provided shred must have passed validation in fd_shred_parse(), 387 : and must satisfy `type&FD_SHRED_TYPEMASK_DATA` 388 : where `uchar type = fd_shred_type( shred->variant )`. */ 389 : FD_FN_CONST static inline uchar const * 390 3 : fd_shred_data_payload( fd_shred_t const * shred ) { 391 3 : return (uchar const *)shred + FD_SHRED_DATA_HEADER_SZ; 392 3 : } 393 : 394 : /* fd_shred_code_payload: Returns a pointer to a coding shred payload. 395 : 396 : The provided shred must have passed validation in fd_shred_parse(), 397 : and must satisfy `type&FD_SHRED_TYPEMASK_CODE` 398 : where `uchar type = fd_shred_type( shred->variant )`. */ 399 : FD_FN_CONST static inline uchar const * 400 0 : fd_shred_code_payload( fd_shred_t const * shred ) { 401 0 : return (uchar const *)shred + FD_SHRED_CODE_HEADER_SZ; 402 0 : } 403 : 404 : /* fd_shred_chain_offset: Assuming that `shred` is a chained Merkle 405 : variant, compute the offset from the start of the shred to the start 406 : of the chained Merkle root. U.B. if the shred is not a chained 407 : variant. */ 408 : FD_FN_CONST static inline ulong 409 1446 : fd_shred_chain_offset( uchar variant ) { 410 1446 : ulong type = fd_shred_type( variant ); 411 1446 : return fd_ulong_if( type & FD_SHRED_TYPEMASK_CODE, FD_SHRED_MAX_SZ, FD_SHRED_MIN_SZ ) 412 1446 : - FD_SHRED_MERKLE_ROOT_SZ 413 1446 : - fd_shred_merkle_sz( variant ) 414 1446 : - fd_ulong_if( fd_shred_is_resigned( type ), FD_SHRED_SIGNATURE_SZ, 0 ); 415 1446 : } 416 : 417 : /* fd_shred_retrasmitter_sig_off: Assuming that `shred` is a resigned 418 : variant, compute the offset from the start of the shred to the start 419 : of the retransmitter signature. U.B if the shred is not a resigned 420 : chained type. */ 421 : FD_FN_PURE static inline ulong 422 192 : fd_shred_retransmitter_sig_off( fd_shred_t const * shred ) { 423 192 : return fd_shred_sz( shred )-FD_SHRED_SIGNATURE_SZ; 424 192 : } 425 : 426 : FD_PROTOTYPES_END 427 : 428 : #endif /* HEADER_fd_src_ballet_shred_fd_shred_h */