Line data    Source code

       1             : #ifndef HEADER_fd_src_choreo_notar_fd_notar_h
       2             : #define HEADER_fd_src_choreo_notar_fd_notar_h
       3             : 
       4             : /* fd_notar ("notarized") processes vote transactions from both TPU and
       5             :    gossip and tracks when blocks become confirmed.  There are three key
       6             :    confirmation thresholds in Solana:
       7             : 
       8             :    - propagation confirmed: a block is propagated if it has received
       9             :      votes from at least 1/3 of stake in the cluster.  This threshold is
      10             :      important in two contexts:
      11             : 
      12             :      1. When becoming leader, we need to check that our "previous"
      13             :         leader block _as of_ the parent slot we're building on, has
      14             :         propagated.  If it's not propagated, we need to instead
      15             :         retransmit our last block that failed to propagate.  "Previous"
      16             :         is quoted, because there is a grace period of one leader
      17             :         rotation for leader blocks to propagate.
      18             : 
      19             :      2. When voting, we need to check our previous leader block _as of_
      20             :         the slot we're voting for has propagated (unless we're voting
      21             :         for one of our own leader blocks).  We cannot vote for slots in
      22             :         which our last leader block failed to propagate.
      23             : 
      24             :    - duplicate confirmed: a block is duplicate confirmed if it has
      25             :      received votes from at least 52% of stake in the cluster.  The
      26             :      "duplicate" adjective is a bit of a misnomer, and a more accurate
      27             :      technical term is equivocation: two (or more) different blocks for
      28             :      the same slot.  This threshold is important for consensus safety,
      29             :      because it ensures Solana eventually converges to the same block
      30             :      per slot.  Specifically fork choice allows choosing a fork if it is
      31             :      duplicate confirmed, even if there is equivocation.
      32             : 
      33             :    - optimistically confirmed: a block is optimistically confirmed if it
      34             :      has received votes from at least 2/3 of stake in the cluster.  This
      35             :      threshold is important for end-users, who rely on the "confirmed"
      36             :      commitment status of blocks (queryable via RPC) to determine that
      37             :      their transaction has landed on a block that will not rollback.
      38             :      This is unimplemented in Firedancer and only relevant for RPC.
      39             :      (TODO verify this?)
      40             : 
      41             :    Unlike duplicate and optimistic confirmation, propagation is at the
      42             :    slot-level rather than block-level.  So two votes for different block
      43             :    ids would count towards the same slot.  This mirrors Agave behavior.
      44             : 
      45             :    On the similarities and differences between fd_ghost vs fd_notar:
      46             : 
      47             :    The reason both fd_ghost and fd_notar exist even though they do
      48             :    seemingly similar things (tracking vote stake on blocks) is because
      49             :    Solana implements the rules quite differently.
      50             : 
      51             :    In fd_ghost, we use the GHOST rule to recursively sum the stake of
      52             :    the subtree (a slot and all its descendants).  The LMD rule counts a
      53             :    validator's stake to at most one fork.  When the validator switches
      54             :    forks, their stake is subtracted from the old fork and added to the
      55             :    new fork.  The tree is then traversed as part of fork choice to find
      56             :    the best leaf ("head").  ghost bases fork choice purely on replay
      57             :    votes, but marks forks valid or invalid with gossip votes.
      58             : 
      59             :    In fd_notar, we count votes towards only the block itself, and not
      60             :    its ancestors.  Also a validator's stake can be counted towards
      61             :    multiple forks at the same time if they vote on a fork then switch to
      62             :    a different one, unlike ghost.  notar uses both replay and gossip
      63             :    votes when counting stake.
      64             : 
      65             :    A note on slots and block ids: vote transactions only contain the
      66             :    block_id of the last vote slot (and do not specify what block_ids
      67             :    previous vote slots correspond to.  Agave assumes if the hash of the
      68             :    last vote slot matches, all the previous slots in the tower match as
      69             :    well.  Agave uses bank hashes instead of block_ids (the relevant code
      70             :    predates block_ids) and maps slots to bank hashes during replay.
      71             : 
      72             :    As a result, there can be multiple block ids for a given slot.  notar
      73             :    tracks the block_id for each slot using fd_tower_forks, and also
      74             :    "duplicate confirmation".  If notar observes a duplicate confirmation
      75             :    for a different block_id than the one it has for a given slot, it
      76             :    updates the block_id for that slot to the duplicate confirmed one. */
      77             : 
      78             : /* FD_NOTAR_PARANOID:  Define this to non-zero at compile time to turn
      79             :    on additional runtime integrity checks. */
      80             : 
      81             : #include "../fd_choreo_base.h"
      82             : #include "../tower/fd_tower_accts.h"
      83             : 
      84             : #ifndef FD_NOTAR_PARANOID
      85             : #define FD_NOTAR_PARANOID 1
      86             : #endif
      87             : 
      88             : #define FD_NOTAR_FLAG_CONFIRMED_PROPAGATED (0)
      89             : #define FD_NOTAR_FLAG_CONFIRMED_DUPLICATE  (1)
      90             : #define FD_NOTAR_FLAG_CONFIRMED_OPTIMISTIC (2)
      91             : 
      92             : #define SET_NAME fd_notar_slot_vtrs
      93             : #define SET_MAX  FD_VOTER_MAX
      94             : #include "../../util/tmpl/fd_set.c"
      95             : 
      96             : struct fd_notar_slot {
      97             :   ulong slot;             /* map key, vote slot */
      98             :   ulong parent_slot;      /* parent slot */
      99             :   ulong prev_leader_slot; /* previous slot in which we were leader */
     100             :   ulong stake;            /* amount of stake that has voted for this slot */
     101             :   int   is_leader;        /* whether this slot was our own leader slot */
     102             :   int   is_propagated;    /* whether this slot has reached 1/3 of stake */
     103             : 
     104             :   fd_hash_t block_ids[FD_VOTER_MAX]; /* one block id per voter per slot */
     105             :   ulong     block_ids_cnt;           /* count of block ids */
     106             : 
     107             :   fd_notar_slot_vtrs_t prev_vtrs[fd_notar_slot_vtrs_word_cnt]; /* who has voted for this slot, prev epoch */
     108             :   fd_notar_slot_vtrs_t vtrs     [fd_notar_slot_vtrs_word_cnt]; /* who has voted for this slot, curr epoch */
     109             : };
     110             : typedef struct fd_notar_slot fd_notar_slot_t;
     111             : 
     112             : struct fd_notar_blk {
     113             :   fd_hash_t block_id;  /* map key */
     114             :   uint      hash;      /* reserved for fd_map_dynamic */
     115             :   ulong     slot;      /* slot associated with this block */
     116             :   ulong     stake;     /* sum of stake that has voted for this block_id */
     117             :   int       dup_conf;  /* whether this block has reached 52% of stake */
     118             :   int       opt_conf;  /* whether this block has reached 2/3 of stake */
     119             :   int       dup_notif; /* set by caller, whether we've notified consumers this is duplicate confirmed */
     120             :   int       opt_notif; /* set by caller, whether we've notified consumers this is optimistically confirmed */
     121             : };
     122             : typedef struct fd_notar_blk fd_notar_blk_t;
     123             : 
     124             : #define MAP_NAME              fd_notar_blk
     125          12 : #define MAP_T                 fd_notar_blk_t
     126      196614 : #define MAP_KEY               block_id
     127           6 : #define MAP_KEY_T             fd_hash_t
     128      196608 : #define MAP_KEY_NULL          hash_null
     129             : #define MAP_KEY_EQUAL_IS_SLOW 1
     130           6 : #define MAP_KEY_INVAL(k)      MAP_KEY_EQUAL((k),MAP_KEY_NULL)
     131           9 : #define MAP_KEY_EQUAL(k0,k1)  (!memcmp( (k0).key, (k1).key, 32UL ))
     132           6 : #define MAP_KEY_HASH(key,s)   ((MAP_HASH_T)( (key).ul[1] ))
     133             : #include "../../util/tmpl/fd_map_dynamic.c"
     134             : 
     135             : /* TODO map key DOS */
     136             : 
     137             : #define MAP_NAME    fd_notar_slot
     138          18 : #define MAP_T       fd_notar_slot_t
     139          60 : #define MAP_KEY     slot
     140             : #define MAP_MEMOIZE 0
     141             : #include "../../util/tmpl/fd_map_dynamic.c"
     142             : 
     143             : struct fd_notar_vtr {
     144             :   fd_pubkey_t vote_acc;     /* map key, vote account address */
     145             :   uint        hash;         /* reserved for fd_map_dynamic */
     146             :   ulong       prev_stake;   /* amount of stake this voter has in epoch - 1 */
     147             :   ulong       stake;        /* amount of stake this voter has in epoch */
     148             :   ulong       prev_bit;     /* bit position in fd_notar_slot_vtrs in epoch - 1 (ULONG_MAX if not set) */
     149             :   ulong       bit;          /* bit position in fd_notar_slot_vtrs in epoch (ULONG_MAX if not set) */
     150             : };
     151             : typedef struct fd_notar_vtr fd_notar_vtr_t;
     152             : 
     153             : #define MAP_NAME              fd_notar_vtr
     154          21 : #define MAP_T                 fd_notar_vtr_t
     155       24591 : #define MAP_KEY               vote_acc
     156          15 : #define MAP_KEY_T             fd_pubkey_t
     157       24576 : #define MAP_KEY_NULL          pubkey_null
     158             : #define MAP_KEY_EQUAL_IS_SLOW 1
     159       49161 : #define MAP_KEY_INVAL(k)      MAP_KEY_EQUAL((k),MAP_KEY_NULL)
     160       49173 : #define MAP_KEY_EQUAL(k0,k1)  (!memcmp( (k0).key, (k1).key, 32UL ))
     161          15 : #define MAP_KEY_HASH(key,s)   ((MAP_HASH_T)( (key).ul[1] ))
     162             : #include "../../util/tmpl/fd_map_dynamic.c"
     163             : 
     164             : struct __attribute__((aligned(128UL))) fd_notar {
     165             :   ulong epoch;    /* highest replayed epoch */
     166             :   ulong lo_wmark; /* notar ignores votes < lo_wmark */
     167             :   ulong hi_wmark; /* notar ignores votes > hi_wmark */
     168             :   ulong slot_max; /* maximum number of slots notar can track */
     169             : 
     170             :   fd_notar_slot_t * slot_map; /* tracks who has voted for a given slot */
     171             :   fd_notar_blk_t *  blk_map;  /* tracks amount of stake for a given block (keyed by block id) */
     172             :   fd_notar_vtr_t *  vtr_map;  /* tracks each voter's stake and prev vote */
     173             : };
     174             : typedef struct fd_notar fd_notar_t;
     175             : 
     176             : /* fd_notar_{align,footprint} return the required alignment and
     177             :    footprint of a memory region suitable for use as a notar.  align
     178             :    returns fd_notar_ALIGN.  footprint returns fd_notar_FOOTPRINT. */
     179             : 
     180             : FD_FN_CONST static inline ulong
     181          33 : fd_notar_align( void ) {
     182          33 :   return alignof(fd_notar_t);
     183          33 : }
     184             : 
     185             : FD_FN_CONST static inline ulong
     186           6 : fd_notar_footprint( ulong slot_max ) {
     187           6 :   int lg_slot_max = fd_ulong_find_msb( fd_ulong_pow2_up( slot_max ) ) + 1;
     188           6 :   int lg_blk_max  = fd_ulong_find_msb( fd_ulong_pow2_up( slot_max * FD_VOTER_MAX ) ) + 1;
     189           6 :   int lg_vtr_max  = fd_ulong_find_msb( fd_ulong_pow2_up( FD_VOTER_MAX ) ) + 1;
     190           6 :   return FD_LAYOUT_FINI(
     191           6 :     FD_LAYOUT_APPEND(
     192           6 :     FD_LAYOUT_APPEND(
     193           6 :     FD_LAYOUT_APPEND(
     194           6 :     FD_LAYOUT_APPEND(
     195           6 :     FD_LAYOUT_INIT,
     196           6 :       alignof(fd_notar_t),   sizeof(fd_notar_t)                     ),
     197           6 :       fd_notar_slot_align(), fd_notar_slot_footprint( lg_slot_max ) ),
     198           6 :       fd_notar_blk_align(),  fd_notar_blk_footprint( lg_blk_max )   ),
     199           6 :       fd_notar_vtr_align(),  fd_notar_vtr_footprint( lg_vtr_max )   ),
     200           6 :     fd_notar_align() );
     201           6 : }
     202             : 
     203             : /* fd_notar_new formats an unused memory region for use as a notar.  mem
     204             :    is a non-NULL pointer to this region in the local address space with
     205             :    the required footprint and alignment. */
     206             : 
     207             : void *
     208             : fd_notar_new( void * shmem,
     209             :               ulong  slot_max );
     210             : 
     211             : /* fd_notar_join joins the caller to the notar.  notar points to the
     212             :    first byte of the memory region backing the notar in the caller's
     213             :    address space.
     214             : 
     215             :    Returns a pointer in the local address space to notar on success. */
     216             : 
     217             : fd_notar_t *
     218             : fd_notar_join( void * notar );
     219             : 
     220             : /* fd_notar_leave leaves a current local join.  Returns a pointer to the
     221             :    underlying shared memory region on success and NULL on failure (logs
     222             :    details).  Reasons for failure include notar is NULL. */
     223             : 
     224             : void *
     225             : fd_notar_leave( fd_notar_t const * notar );
     226             : 
     227             : /* fd_notar_delete unformats a memory region used as a notar.  Assumes
     228             :    only the local process is joined to the region.  Returns a pointer to
     229             :    the underlying shared memory region or NULL if used obviously in
     230             :    error (e.g. notar is obviously not a notar ...  logs details).  The
     231             :    ownership of the memory region is transferred to the caller. */
     232             : 
     233             : void *
     234             : fd_notar_delete( void * notar );
     235             : 
     236             : /* fd_notar_count_vote counts addr's stake towards the voted slots in
     237             :    their tower.  Returns 1 if block_id is duplicate confirmed by this
     238             :    vote, otherwise 0 (useful for the downstream tower tile to implement
     239             :    duplicate confirmation notifications).  addr is the vote account
     240             :    address, stake is the amount of stake associated with the vote
     241             :    account in the current epoch, slot is slot being voted for, block_id
     242             :    is the voter's proposed block id for this vote slot. */
     243             : 
     244             : fd_notar_blk_t *
     245             : fd_notar_count_vote( fd_notar_t *        notar,
     246             :                      ulong               total_stake,
     247             :                      fd_pubkey_t const * addr,
     248             :                      ulong               slot,
     249             :                      fd_hash_t const *   block_id );
     250             : 
     251             : void
     252             : fd_notar_advance_epoch( fd_notar_t *       notar,
     253             :                         fd_tower_accts_t * accts,
     254             :                         ulong              epoch );
     255             : 
     256             : /* fd_notar_publish publishes root as the new notar root slot, removing
     257             :    all blocks with slot numbers < the old notar root slot.  Some slots
     258             :    on minority forks that were pruned but > than the new root may remain
     259             :    but they will eventually be pruned as well as the root advances. */
     260             : 
     261             : void
     262             : fd_notar_advance_wmark( fd_notar_t * notar,
     263             :                         ulong        root );
     264             : 
     265             : #endif /* HEADER_fd_src_choreo_notar_fd_notar_h */