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       sup_conf;  /* whether this block has reached 4/5 of stake */
     120             :   int       dup_notif; /* set by caller, whether we've notified consumers this is duplicate confirmed */
     121             :   int       opt_notif; /* set by caller, whether we've notified consumers this is optimistically confirmed */
     122             : };
     123             : typedef struct fd_notar_blk fd_notar_blk_t;
     124             : 
     125             : #define MAP_NAME              fd_notar_blk
     126          12 : #define MAP_T                 fd_notar_blk_t
     127      196614 : #define MAP_KEY               block_id
     128           6 : #define MAP_KEY_T             fd_hash_t
     129      196608 : #define MAP_KEY_NULL          hash_null
     130             : #define MAP_KEY_EQUAL_IS_SLOW 1
     131           6 : #define MAP_KEY_INVAL(k)      MAP_KEY_EQUAL((k),MAP_KEY_NULL)
     132           9 : #define MAP_KEY_EQUAL(k0,k1)  (!memcmp( (k0).key, (k1).key, 32UL ))
     133           6 : #define MAP_KEY_HASH(key,s)   ((MAP_HASH_T)( (key).ul[1] ))
     134             : #include "../../util/tmpl/fd_map_dynamic.c"
     135             : 
     136             : /* TODO map key DOS */
     137             : 
     138             : #define MAP_NAME           fd_notar_slot
     139          18 : #define MAP_T              fd_notar_slot_t
     140          60 : #define MAP_KEY            slot
     141          48 : #define MAP_KEY_NULL       ULONG_MAX
     142          12 : #define MAP_KEY_INVAL(key) ((key)==ULONG_MAX)
     143             : #define MAP_MEMOIZE        0
     144             : #include "../../util/tmpl/fd_map_dynamic.c"
     145             : 
     146             : struct fd_notar_vtr {
     147             :   fd_pubkey_t vote_acc;     /* map key, vote account address */
     148             :   uint        hash;         /* reserved for fd_map_dynamic */
     149             :   ulong       prev_stake;   /* amount of stake this voter has in epoch - 1 */
     150             :   ulong       stake;        /* amount of stake this voter has in epoch */
     151             :   ulong       prev_bit;     /* bit position in fd_notar_slot_vtrs in epoch - 1 (ULONG_MAX if not set) */
     152             :   ulong       bit;          /* bit position in fd_notar_slot_vtrs in epoch (ULONG_MAX if not set) */
     153             : };
     154             : typedef struct fd_notar_vtr fd_notar_vtr_t;
     155             : 
     156             : #define MAP_NAME              fd_notar_vtr
     157          21 : #define MAP_T                 fd_notar_vtr_t
     158       24591 : #define MAP_KEY               vote_acc
     159          15 : #define MAP_KEY_T             fd_pubkey_t
     160       24576 : #define MAP_KEY_NULL          pubkey_null
     161             : #define MAP_KEY_EQUAL_IS_SLOW 1
     162       49161 : #define MAP_KEY_INVAL(k)      MAP_KEY_EQUAL((k),MAP_KEY_NULL)
     163       49173 : #define MAP_KEY_EQUAL(k0,k1)  (!memcmp( (k0).key, (k1).key, 32UL ))
     164          15 : #define MAP_KEY_HASH(key,s)   ((MAP_HASH_T)( (key).ul[1] ))
     165             : #include "../../util/tmpl/fd_map_dynamic.c"
     166             : 
     167             : struct __attribute__((aligned(128UL))) fd_notar {
     168             :   ulong epoch;    /* highest replayed epoch */
     169             :   ulong lo_wmark; /* notar ignores votes < lo_wmark */
     170             :   ulong hi_wmark; /* notar ignores votes > hi_wmark */
     171             :   ulong slot_max; /* maximum number of slots notar can track */
     172             : 
     173             :   fd_notar_slot_t * slot_map; /* tracks who has voted for a given slot */
     174             :   fd_notar_blk_t *  blk_map;  /* tracks amount of stake for a given block (keyed by block id) */
     175             :   fd_notar_vtr_t *  vtr_map;  /* tracks each voter's stake and prev vote */
     176             : };
     177             : typedef struct fd_notar fd_notar_t;
     178             : 
     179             : /* fd_notar_{align,footprint} return the required alignment and
     180             :    footprint of a memory region suitable for use as a notar.  align
     181             :    returns fd_notar_ALIGN.  footprint returns fd_notar_FOOTPRINT. */
     182             : 
     183             : FD_FN_CONST static inline ulong
     184          33 : fd_notar_align( void ) {
     185          33 :   return alignof(fd_notar_t);
     186          33 : }
     187             : 
     188             : FD_FN_CONST static inline ulong
     189           6 : fd_notar_footprint( ulong slot_max ) {
     190           6 :   int lg_slot_max = fd_ulong_find_msb( fd_ulong_pow2_up( slot_max ) ) + 1;
     191           6 :   int lg_blk_max  = fd_ulong_find_msb( fd_ulong_pow2_up( slot_max * FD_VOTER_MAX ) ) + 1;
     192           6 :   int lg_vtr_max  = fd_ulong_find_msb( fd_ulong_pow2_up( FD_VOTER_MAX ) ) + 1;
     193           6 :   return FD_LAYOUT_FINI(
     194           6 :     FD_LAYOUT_APPEND(
     195           6 :     FD_LAYOUT_APPEND(
     196           6 :     FD_LAYOUT_APPEND(
     197           6 :     FD_LAYOUT_APPEND(
     198           6 :     FD_LAYOUT_INIT,
     199           6 :       alignof(fd_notar_t),   sizeof(fd_notar_t)                     ),
     200           6 :       fd_notar_slot_align(), fd_notar_slot_footprint( lg_slot_max ) ),
     201           6 :       fd_notar_blk_align(),  fd_notar_blk_footprint( lg_blk_max )   ),
     202           6 :       fd_notar_vtr_align(),  fd_notar_vtr_footprint( lg_vtr_max )   ),
     203           6 :     fd_notar_align() );
     204           6 : }
     205             : 
     206             : /* fd_notar_new formats an unused memory region for use as a notar.  mem
     207             :    is a non-NULL pointer to this region in the local address space with
     208             :    the required footprint and alignment. */
     209             : 
     210             : void *
     211             : fd_notar_new( void * shmem,
     212             :               ulong  slot_max );
     213             : 
     214             : /* fd_notar_join joins the caller to the notar.  notar points to the
     215             :    first byte of the memory region backing the notar in the caller's
     216             :    address space.
     217             : 
     218             :    Returns a pointer in the local address space to notar on success. */
     219             : 
     220             : fd_notar_t *
     221             : fd_notar_join( void * notar );
     222             : 
     223             : /* fd_notar_leave leaves a current local join.  Returns a pointer to the
     224             :    underlying shared memory region on success and NULL on failure (logs
     225             :    details).  Reasons for failure include notar is NULL. */
     226             : 
     227             : void *
     228             : fd_notar_leave( fd_notar_t const * notar );
     229             : 
     230             : /* fd_notar_delete unformats a memory region used as a notar.  Assumes
     231             :    only the local process is joined to the region.  Returns a pointer to
     232             :    the underlying shared memory region or NULL if used obviously in
     233             :    error (e.g. notar is obviously not a notar ...  logs details).  The
     234             :    ownership of the memory region is transferred to the caller. */
     235             : 
     236             : void *
     237             : fd_notar_delete( void * notar );
     238             : 
     239             : /* fd_notar_count_vote counts addr's stake towards the voted slots in
     240             :    their tower.  Returns 1 if block_id is duplicate confirmed by this
     241             :    vote, otherwise 0 (useful for the downstream tower tile to implement
     242             :    duplicate confirmation notifications).  addr is the vote account
     243             :    address, stake is the amount of stake associated with the vote
     244             :    account in the current epoch, slot is slot being voted for, block_id
     245             :    is the voter's proposed block id for this vote slot. */
     246             : 
     247             : fd_notar_blk_t *
     248             : fd_notar_count_vote( fd_notar_t *        notar,
     249             :                      ulong               total_stake,
     250             :                      fd_pubkey_t const * addr,
     251             :                      ulong               slot,
     252             :                      fd_hash_t const *   block_id );
     253             : 
     254             : void
     255             : fd_notar_advance_epoch( fd_notar_t *       notar,
     256             :                         fd_tower_accts_t * accts,
     257             :                         ulong              epoch );
     258             : 
     259             : /* fd_notar_publish publishes root as the new notar root slot, removing
     260             :    all blocks with slot numbers < the old notar root slot.  Some slots
     261             :    on minority forks that were pruned but > than the new root may remain
     262             :    but they will eventually be pruned as well as the root advances. */
     263             : 
     264             : void
     265             : fd_notar_advance_wmark( fd_notar_t * notar,
     266             :                         ulong        root );
     267             : 
     268             : #endif /* HEADER_fd_src_choreo_notar_fd_notar_h */