Line data    Source code

       1             : #ifndef HEADER_fd_src_flamenco_leaders_fd_leaders_base_h
       2             : #define HEADER_fd_src_flamenco_leaders_fd_leaders_base_h
       3             : 
       4             : #include "../types/fd_types_custom.h"
       5             : #include "../features/fd_features.h"
       6             : 
       7      242361 : #define MAX_SHRED_DESTS              40200UL /* 200 * 201 - 1 (exclude self) */
       8           0 : #define MAX_SLOTS_PER_EPOCH          432000UL
       9          57 : #define MAX_STAKED_LEADERS           108000UL
      10          36 : #define MAX_COMPRESSED_STAKE_WEIGHTS (MAX_STAKED_LEADERS*2UL+1UL)
      11             : 
      12             : /* Follows message structure in fd_stake_ci_stake_msg_init.
      13             :    Frankendancer only */
      14             : struct fd_stake_weight_msg_t {
      15             :   ulong             epoch;             /* Epoch for which the stake weights are valid */
      16             :   ulong             staked_vote_cnt;   /* Number of staked nodes */
      17             :   ulong             staked_id_cnt;     /* Number of staked nodes */
      18             :   ulong             start_slot;        /* Start slot of the epoch */
      19             :   ulong             slot_cnt;          /* Number of slots in the epoch */
      20             :   ulong             excluded_id_stake; /* Total stake that is excluded for shred dests */
      21             :   ulong             vote_keyed_lsched; /* 1=use vote-keyed leader schedule, 0=use old leader schedule */
      22             : };
      23             : typedef struct fd_stake_weight_msg_t fd_stake_weight_msg_t;
      24             : 
      25         684 : #define FD_STAKE_CI_STAKE_MSG_HEADER_SZ (sizeof(fd_stake_weight_msg_t))
      26         306 : #define FD_STAKE_CI_STAKE_MSG_RECORD_SZ (sizeof(fd_vote_stake_weight_t))
      27           0 : #define FD_STAKE_CI_ID_WEIGHT_RECORD_SZ (sizeof(fd_stake_weight_t))
      28           0 : #define FD_STAKE_CI_STAKE_MSG_SZ (FD_STAKE_CI_STAKE_MSG_HEADER_SZ + MAX_COMPRESSED_STAKE_WEIGHTS * FD_STAKE_CI_STAKE_MSG_RECORD_SZ + MAX_SHRED_DESTS * FD_STAKE_CI_ID_WEIGHT_RECORD_SZ)
      29             : 
      30           0 : #define FD_STAKE_OUT_MTU FD_STAKE_CI_STAKE_MSG_SZ
      31             : 
      32             : static inline ulong fd_stake_weight_msg_sz( ulong staked_vote_cnt,
      33           0 :                                             ulong staked_id_cnt ) {
      34           0 :   return FD_STAKE_CI_STAKE_MSG_HEADER_SZ + staked_vote_cnt * FD_STAKE_CI_STAKE_MSG_RECORD_SZ + staked_id_cnt * FD_STAKE_CI_ID_WEIGHT_RECORD_SZ;
      35           0 : }
      36             : 
      37             : static inline fd_vote_stake_weight_t *
      38         378 : fd_stake_weight_msg_stake_weights( fd_stake_weight_msg_t const * stake_weight_msg ) {
      39         378 :   return (fd_vote_stake_weight_t *)fd_type_pun( (uchar *)stake_weight_msg + FD_STAKE_CI_STAKE_MSG_HEADER_SZ );
      40         378 : }
      41             : 
      42             : static inline fd_stake_weight_t *
      43         306 : fd_stake_weight_msg_id_weights( fd_stake_weight_msg_t const * stake_weight_msg ) {
      44         306 :   return (fd_stake_weight_t *)fd_type_pun( (uchar *)stake_weight_msg + FD_STAKE_CI_STAKE_MSG_HEADER_SZ + stake_weight_msg->staked_vote_cnt * FD_STAKE_CI_STAKE_MSG_RECORD_SZ );
      45         306 : }
      46             : 
      47             : /* Firedancer only */
      48             : struct fd_epoch_info_msg_t {
      49             :   ulong                  epoch;             /* Epoch for which the info is valid */
      50             :   ulong                  staked_vote_cnt;   /* Number of staked nodes */
      51             :   ulong                  staked_id_cnt;     /* Number of staked nodes */
      52             :   ulong                  start_slot;        /* Start slot of the epoch */
      53             :   ulong                  slot_cnt;          /* Number of slots in the epoch */
      54             :   ulong                  excluded_id_stake; /* Total stake that is excluded for shred dests */
      55             :   ulong                  vote_keyed_lsched; /* Whether vote account keyed leader schedule is active */
      56             :   fd_epoch_schedule_t    epoch_schedule;    /* Epoch schedule */
      57             :   fd_features_t          features;          /* Feature activation slots */
      58             : };
      59             : typedef struct fd_epoch_info_msg_t fd_epoch_info_msg_t;
      60             : 
      61             : /* Leader schedule calculation is done based on a weighted sample of
      62             :    a sorted list of stake weights (see fd_leaders and fd_wsample).
      63             :    Because there are many consumers of the stake weights from the Replay
      64             :    tile, a naive approach will make the link size very large:
      65             :    (72 bytes per weight * 40M vote accounts) = ~2.9GB.
      66             : 
      67             :    In order to do something more clever consider some protocol/message
      68             :    invariants:
      69             :    1. the set of stake weights that is passed around is sorted based on
      70             :       stake and then tiebroken on lexicographic order of the vote key.
      71             :    2. There are 108,000 leaders per epoch in the worst case (432000
      72             :       slots per epoch / 4 leaders per slot).
      73             :    3. Stake weighted sample is done to select leaders.
      74             : 
      75             :    From this we know that there can be up to 108k leaders from a much
      76             :    larger set of stake weights.  All other pubkeys can be ignored since
      77             :    we know that they won't be selected.  In the worst case there are
      78             :    40M - 108,000 vote accounts that won't be selected.  In the weighted
      79             :    sample, two adjacent, non-selected pubkeys can be combined into one
      80             :    aggregated stake weight.  If we take this idea to its limit we can
      81             :    combine all adjacent non-selected pubkeys into aggregated weights.
      82             :    The worst case number of these non-selected pubkeys is 108001 (if
      83             :    the non-selected keys are perfectly interleaved with the selected
      84             :    keys with the first and last key also being non-selected).  In
      85             :    practice, this bound is probably tighter because the higher staked
      86             :    nodes are almost guaranteed to be selected.
      87             : 
      88             :    Regardless, this allows us to compress the set of stake weights into
      89             :    a much smaller, bounded set.  The worst case number of compressed
      90             :    stake weights is 108000 + 108001 = 216001 keys.  The aggregated
      91             :    weights will be stored as FD_DUMMY_ACCOUNT.  The consumer is
      92             :    responsible for post-processing the aggregated weights to make sure
      93             :    they aren't inserted into any downstream data structures. */
      94             : 
      95         360 : #define FD_EPOCH_INFO_MSG_HEADER_SZ (sizeof(fd_epoch_info_msg_t))
      96           0 : #define FD_EPOCH_INFO_MAX_MSG_SZ    (FD_EPOCH_INFO_MSG_HEADER_SZ + MAX_COMPRESSED_STAKE_WEIGHTS * sizeof(fd_vote_stake_weight_t) + MAX_SHRED_DESTS * sizeof(fd_stake_weight_t))
      97           0 : #define FD_EPOCH_OUT_MTU            FD_EPOCH_INFO_MAX_MSG_SZ
      98             : 
      99             : static inline ulong fd_epoch_info_msg_sz( ulong vote_cnt,
     100           0 :                                           ulong id_weight_cnt ) {
     101           0 :   return FD_EPOCH_INFO_MSG_HEADER_SZ +
     102           0 :          (vote_cnt * sizeof(fd_vote_stake_weight_t)) +
     103           0 :          (id_weight_cnt * sizeof(fd_stake_weight_t));
     104           0 : }
     105             : 
     106             : static inline fd_vote_stake_weight_t *
     107         180 : fd_epoch_info_msg_stake_weights( fd_epoch_info_msg_t const * epoch_info_msg ) {
     108         180 :   return (fd_vote_stake_weight_t *)fd_type_pun( (uchar *)epoch_info_msg + FD_EPOCH_INFO_MSG_HEADER_SZ );
     109         180 : }
     110             : 
     111             : static inline fd_stake_weight_t *
     112         180 : fd_epoch_info_msg_id_weights( fd_epoch_info_msg_t const * epoch_info_msg ) {
     113         180 :   return (fd_stake_weight_t *)fd_type_pun( (uchar *)epoch_info_msg + FD_EPOCH_INFO_MSG_HEADER_SZ + epoch_info_msg->staked_vote_cnt * sizeof(fd_vote_stake_weight_t) );
     114         180 : }
     115             : 
     116             : /* compute_id_weights_from_vote_weights() translates vote-based
     117             :    stake weights into (older) identity-based stake weights.
     118             : 
     119             :    Before SIMD-0180, the leader schedule was generated starting from
     120             :    a list [(id, stake)] where `id` is the validator identity and
     121             :    `stake` its aggregated stake, and the same list was used to build
     122             :    the Turbine tree.
     123             : 
     124             :    After SIMD-0180, the leader schedule is generated by vote
     125             :    accounts, i.e. starting from a list [(vote, id, stake)] instead.
     126             :    This makes it easier to send rewards to the expected vote account.
     127             :    Notably, turbine tree doesn't change with SIMD-0180, so the old
     128             :    list [(id, stake)] is still necessary.
     129             : 
     130             :    Realistically, there should be a 1:1 relationship between id and
     131             :    vote, but unfortunately the on chain state allows for a 1:N
     132             :    relationship (1 id could be associated to N vote accounts).
     133             :    At the time of writing, testnet has one such example.
     134             :    id: DtSguGSHVrXdqZU1mKWKocsAjrXMhaC7YJic5xxN1Uom
     135             :    votes:
     136             :    - https://solscan.io/account/BbtyLT1ntMFbbXtsJRCZnYjpe7d7TUtyZeGKzod3eNsN?cluster=testnet
     137             :    - https://solscan.io/account/FFr8Gyjy3Wjeqv6oD4RjbwqD1mVfKycAFxQdASYAfR75?cluster=testnet
     138             : 
     139             :    Even when there is a 1:1 relationship, the order of the 2 lists
     140             :    can be different because validators with the same stake could
     141             :    be ordered differently by vote vs id.
     142             : 
     143             :    Last consideration, this operation is done only once per epoch, twice
     144             :    at startup.
     145             : 
     146             :    The current implementation uses sort in place to avoid extra memory
     147             :    for a map or tree. */
     148             :    ulong
     149             :    compute_id_weights_from_vote_weights( fd_stake_weight_t *            stake_weight,
     150             :                                          fd_vote_stake_weight_t const * vote_stake_weight,
     151             :                                          ulong                          staked_cnt );
     152             : 
     153             : #endif /* HEADER_fd_src_flamenco_leaders_fd_leaders_base_h */