Line data    Source code

       1             : #include "fd_shred.h"
       2             : 
       3             : fd_shred_t const *
       4             : fd_shred_parse( uchar const * const buf,
       5             :                 ulong         const sz,
       6       26562 :                 ulong         const max_shred_idx ) {
       7       26562 :   ulong total_shred_sz = sz;
       8             :   /* Initial bounds check */
       9       26562 :   if( FD_UNLIKELY( total_shred_sz<fd_ulong_min( FD_SHRED_DATA_HEADER_SZ, FD_SHRED_CODE_HEADER_SZ ) ) ) return NULL;
      10             : 
      11       26553 :   fd_shred_t const * shred = (fd_shred_t *)buf;
      12             : 
      13             :   /* Validate shred type.
      14             :      Safe to access because `variant` ends at 0x41, which is <= 0x58 */
      15       26553 :   uchar variant = shred->variant;
      16       26553 :   uchar type = fd_shred_type( variant );
      17       26553 :   if( FD_UNLIKELY( (type!=FD_SHRED_TYPE_MERKLE_DATA) &
      18       26553 :                    (type!=FD_SHRED_TYPE_MERKLE_CODE) &
      19       26553 :                    (type!=FD_SHRED_TYPE_MERKLE_DATA_CHAINED) &
      20       26553 :                    (type!=FD_SHRED_TYPE_MERKLE_CODE_CHAINED) &
      21       26553 :                    (type!=FD_SHRED_TYPE_MERKLE_DATA_CHAINED_RESIGNED) &
      22       26553 :                    (type!=FD_SHRED_TYPE_MERKLE_CODE_CHAINED_RESIGNED) &
      23       26553 :                    (variant!=0xa5 /*FD_SHRED_TYPE_LEGACY_DATA*/ ) &
      24       26553 :                    (variant!=0x5a /*FD_SHRED_TYPE_LEGACY_CODE*/ ) ) )
      25         474 :     return NULL;
      26             : 
      27             :   /* There are six sections of a shred that can contribute to the size:
      28             :      header, payload, zero-padding, Merkle root of previous erasure
      29             :      batch, Merkle proof, and retransmitter signature.
      30             :      Some of these may have 0 size in certain cases.  sz is the sum of
      31             :      all 5, while for data shreds, shred->data.size == header+payload.
      32             :      We'll call the last three section the trailer. */
      33       26079 :   ulong header_sz       = fd_shred_header_sz( variant ); /* between 88 and 89 bytes */
      34       26079 :   ulong trailer_sz      = fd_shred_merkle_sz( shred->variant )   /* between 0 and 300 bytes */
      35       26079 :                            + fd_ulong_if( fd_shred_is_resigned( type ), FD_SHRED_SIGNATURE_SZ, 0UL ) /* 0 or 64 */
      36       26079 :                            + fd_ulong_if( fd_shred_is_chained( type ),  FD_SHRED_MERKLE_ROOT_SZ, 0UL ); /* 0 or 32 */
      37       26079 :   ulong zero_padding_sz;
      38       26079 :   ulong payload_sz;
      39             : 
      40       26079 :   if( FD_LIKELY( type & FD_SHRED_TYPEMASK_DATA ) ) {
      41       12738 :     if( FD_UNLIKELY( shred->data.size<header_sz ) ) return NULL;
      42       12738 :     payload_sz = (ulong)shred->data.size - header_sz; /* between 0 and USHORT_MAX */
      43       12738 :     if( FD_UNLIKELY( (type!=FD_SHRED_TYPE_LEGACY_DATA) & (sz<FD_SHRED_MIN_SZ) ) ) return NULL;
      44             : 
      45             :     /* legacy data shreds might be shorter than the normal
      46             :        FD_SHRED_MIN_SZ, but they don't have Merkle proofs, so everything
      47             :        after the payload is zero-padding/ignored.  On the other hand,
      48             :        Merkle data shreds might have some zero-padding, but anything
      49             :        between [FD_SHRED_MIN_SZ, sz) is extra bytes after the shred
      50             :        (which we don't care about the contents of but also tolerate).
      51             :        The Merkle proof is not in bytes [sz-merkle_proof_sz, sz) but in
      52             :        [FD_SHRED_MIN_SZ-merkle_proof_sz, FD_SHRED_MIN_SZ).  From above,
      53             :        we know sz >= FD_SHRED_MIN_SZ in this case. */
      54       12738 :     uchar is_legacy_data_shred = type==FD_SHRED_TYPE_LEGACY_DATA;
      55       12738 :     ulong effective_sz = fd_ulong_if( is_legacy_data_shred, sz, FD_SHRED_MIN_SZ );
      56       12738 :     if( FD_UNLIKELY( effective_sz < header_sz+payload_sz+trailer_sz ) ) return NULL;
      57       12738 :     zero_padding_sz = effective_sz - header_sz - payload_sz - trailer_sz;
      58       12738 :   }
      59       13341 :   else if( FD_LIKELY( type & FD_SHRED_TYPEMASK_CODE ) ) {
      60       13341 :     zero_padding_sz = 0UL;
      61             :     /* Payload size is not specified directly, but the whole shred must
      62             :        be FD_SHRED_MAX_SZ. */
      63       13341 :     if( FD_UNLIKELY( header_sz+zero_padding_sz+trailer_sz > FD_SHRED_MAX_SZ ) ) return NULL;
      64       13341 :     payload_sz      = FD_SHRED_MAX_SZ - header_sz - zero_padding_sz - trailer_sz;
      65       13341 :   }
      66           0 :   else return NULL;
      67             : 
      68       26079 :   if( FD_UNLIKELY( sz < header_sz + payload_sz + zero_padding_sz + trailer_sz ) ) return NULL;
      69             : 
      70             :   /* At this point we know all the fields exist, but we need to sanity
      71             :      check a few fields that would make a shred illegal. */
      72       26079 :   if( FD_LIKELY( type & FD_SHRED_TYPEMASK_DATA ) ) {
      73       12738 :     ulong parent_off = (ulong)shred->data.parent_off;
      74       12738 :     ulong slot       = shred->slot;
      75       12738 :     if( FD_UNLIKELY( (shred->data.flags&0xC0)==0x80                              ) ) return NULL;
      76       12735 :     if( FD_UNLIKELY( parent_off>slot                                             ) ) return NULL;
      77             : 
      78             :     /* There are 3 cases we want to allow:
      79             :         slot==0, parent_off==0
      80             :         slot==1, parent_off==1
      81             :         slot>1,  0<parent_off<slot
      82             :       We've already ensured parent_off<=slot, so the cases we need to reject are:
      83             :         slot==1, parent_off==0
      84             :         slot>1,  parent_off==0
      85             :         slot>1,  parent_off==slot
      86             : 
      87             :       That gives
      88             :       (slot==1 & parent_off==0) | (slot>1 & parent_off==0) | (slot>1 & parent_off==slot)
      89             :       Simplifying a bit,
      90             :       ((slot==1 | slot>1) & parent_off==0) | (slot>1 & parent_off==slot)
      91             :       (slot!=0 & parent_off==0) | (slot>1 & parent_off==slot)
      92             : 
      93             :       https://github.com/anza-xyz/agave/blob/dda8b79162d9aa1191c7813ca7f024ab5a5b0b9f/ledger/src/blockstore.rs#L5035
      94             :     */
      95             : 
      96       12729 :     if( FD_UNLIKELY( ((slot!=0UL) & (parent_off==0UL)) | ((slot>1UL) & (parent_off==slot)) ) ) return NULL;
      97       12723 :     if( FD_UNLIKELY( shred->idx<shred->fec_set_idx                               ) ) return NULL;
      98             : 
      99             :     /* https://github.com/anza-xyz/agave/blob/v4.0.2/ledger/src/shred/shred_data.rs#L19 */
     100       12717 :     if( FD_UNLIKELY( shred->idx>=max_shred_idx                                   ) ) return NULL;
     101       13341 :   } else {
     102       13341 :     if( FD_UNLIKELY( shred->code.idx>=shred->code.code_cnt                       ) ) return NULL;
     103       13335 :     if( FD_UNLIKELY( shred->code.idx> shred->idx                                 ) ) return NULL;
     104       13335 :     if( FD_UNLIKELY( (shred->code.data_cnt==0)|(shred->code.code_cnt==0)         ) ) return NULL;
     105       13332 :     if( FD_UNLIKELY( shred->code.code_cnt>256                                    ) ) return NULL;
     106       13332 :     if( FD_UNLIKELY( (ulong)shred->code.data_cnt+(ulong)shred->code.code_cnt>256 ) ) return NULL; /* I don't see this check in Agave, but it seems necessary */
     107             : 
     108             :     /* https://github.com/anza-xyz/agave/blob/v4.0.2/ledger/src/shred/shred_code.rs#L40 */
     109       13326 :     if( FD_UNLIKELY( shred->idx>=max_shred_idx                                                          ) ) return NULL;
     110             :     /* https://github.com/anza-xyz/agave/blob/v4.0.2/ledger/src/shred/shred_code.rs#L12-L25
     111             :        Subtractions are safe here due to the checks above. */
     112       13320 :     if( FD_UNLIKELY( (ulong)shred->fec_set_idx+(ulong)shred->code.data_cnt-1UL>=max_shred_idx           ) ) return NULL;
     113       13317 :     if( FD_UNLIKELY( (ulong)(shred->idx-shred->code.idx)+(ulong)shred->code.code_cnt-1UL>=max_shred_idx ) ) return NULL;
     114       13317 :   }
     115             : 
     116       26028 :   return shred;
     117       26079 : }
     118             : 
     119             : int
     120        5871 : fd_shred_merkle_root( fd_shred_t const * shred, void * bmtree_mem, fd_bmtree_node_t * root_out ) {
     121        5871 :   fd_bmtree_commit_t * tree = fd_bmtree_commit_init( bmtree_mem,
     122        5871 :                                                      FD_SHRED_MERKLE_NODE_SZ,
     123        5871 :                                                      FD_BMTREE_LONG_PREFIX_SZ,
     124        5871 :                                                      FD_SHRED_MERKLE_LAYER_CNT );
     125             : 
     126        5871 :   uchar shred_type  = fd_shred_type( shred->variant );
     127        5871 :   int is_data_shred = fd_shred_is_data( shred_type );
     128        5871 :   ulong in_type_idx = fd_ulong_if( is_data_shred, shred->idx - shred->fec_set_idx, shred->code.idx );
     129        5871 :   ulong shred_idx   = fd_ulong_if( is_data_shred, in_type_idx, in_type_idx + shred->code.data_cnt  );
     130             : 
     131        5871 :   ulong tree_depth           = fd_shred_merkle_cnt( shred->variant ); /* In [0, 15] */
     132        5871 :   if( FD_UNLIKELY( tree_depth!=FD_SHRED_MERKLE_LAYER_CNT-1UL ) ) return 0;
     133        5871 :   ulong reedsol_protected_sz = 1115UL + FD_SHRED_DATA_HEADER_SZ - FD_SHRED_SIGNATURE_SZ - FD_SHRED_MERKLE_NODE_SZ*tree_depth
     134        5871 :                                       - FD_SHRED_MERKLE_ROOT_SZ*fd_shred_is_chained ( shred_type )
     135        5871 :                                       - FD_SHRED_SIGNATURE_SZ  *fd_shred_is_resigned( shred_type); /* In [743, 1139] conservatively*/
     136        5871 :   ulong data_merkle_protected_sz   = reedsol_protected_sz + FD_SHRED_MERKLE_ROOT_SZ*fd_shred_is_chained ( shred_type );
     137        5871 :   ulong parity_merkle_protected_sz = reedsol_protected_sz + FD_SHRED_MERKLE_ROOT_SZ*fd_shred_is_chained ( shred_type )+FD_SHRED_CODE_HEADER_SZ-FD_ED25519_SIG_SZ;
     138        5871 :   ulong merkle_protected_sz  = fd_ulong_if( is_data_shred, data_merkle_protected_sz, parity_merkle_protected_sz );
     139        5871 :   fd_bmtree_node_t leaf;
     140        5871 :   fd_bmtree_hash_leaf( &leaf, (uchar const *)shred + sizeof(fd_ed25519_sig_t), merkle_protected_sz, FD_BMTREE_LONG_PREFIX_SZ );
     141             : 
     142        5871 :   return fd_bmtree_commitp_insert_with_proof( tree, shred_idx, &leaf, (uchar const *)fd_shred_merkle_nodes( shred ), fd_shred_merkle_cnt( shred->variant ), root_out );
     143        5871 : }