Line data Source code
1 : #ifndef HEADER_fd_src_choreo_votes_fd_votes_h 2 : #define HEADER_fd_src_choreo_votes_fd_votes_h 3 : 4 : /* fd_votes handles votes, specifically vote transactions, from all 5 : sources including gossip, TPU and replay. 6 : 7 : Solana has two notions of a vote: vote _transactions_ and vote 8 : _accounts_. Vote transactions are updates to vote accounts. Vote 9 : transactions are "across forks": a vote transaction observed via 10 : gossip or TPU is not tied to any particular fork and can be counted 11 : globally. Vote transactions are also sourced from replay: when a 12 : vote txn packed in a block is successfully executed, votes processes 13 : it. In this case, the vote txn is sourced from the specific fork the 14 : block is on, but this is not inherently significant to vote txns 15 : generally or fd_votes. Vote accounts, on the other hand, are "per 16 : fork": each fork has its own copy of the vote account state, which is 17 : the last successfully executed vote transaction on that fork (in 18 : addition to other metadata). 19 : 20 : Solana reaches consensus via replay, but can "forward confirm" slots 21 : ahead of the replay tip by listening to vote txns from gossip or TPU. 22 : The larger max_live_slots (specified in configuration toml), the 23 : further ahead slots can be cluster confirmed before they are 24 : replayed. 25 : 26 : What's the difference between fd_ghost and fd_votes? 27 : 28 : The reason both fd_ghost and fd_votes exist even though they appear 29 : to do the same thing ie. counting votes is because of the 30 : aforementioned distinction between the two kinds of votes (vote txns 31 : vs. vote accs). 32 : 33 : At a high-level, fd_ghost "counts" vote accounts vs. fd_votes 34 : "counts" vote transactions. Everything in fd_ghost is dependent on 35 : the vote account's state after vote transactions have been 36 : successfully executed. So ghost can only count a vote for a block 37 : after a _descendant_ of that block has been replayed (meaning the 38 : vote txns packed into that block have been executed). 39 : 40 : On the other hand, fd_votes counts vote transactions even if the 41 : block they are packed in has not been replayed yet. Specifically, 42 : txns that come from gossip and TPU do not have the same requirement 43 : that the block has been replayed. This is important, because block 44 : transmission is unreliable, and votes provides a fallback mechanism 45 : for detecting votes for blocks we don't have. fd_votes still ingests 46 : replay votes as well, so it is guaranteed to be a superset of the 47 : votes tracked by fd_ghost, though note this assumption is contingent 48 : on feature "Deprecate legacy vote instructions" because votes only 49 : counts TowerSync ixs and ignores any other deprecated vote 50 : instructions. 51 : 52 : There are also differences in how votes are counted between the two. 53 : In fd_ghost, we use the GHOST rule to recursively sum the stake of 54 : the subtree (a slot and all its descendants). The LMD rule counts a 55 : validator's stake to at most one fork. When the validator switches 56 : forks, their stake is subtracted from the old fork and added to the 57 : new fork. The tree is then traversed as part of fork choice to find 58 : the best leaf ("head"). ghost bases fork choice purely on replay 59 : votes, but marks forks valid or invalid with gossip votes. 60 : 61 : In fd_votes, we count votes towards only the block itself, and not 62 : its ancestors. Also a validator's stake can be counted towards 63 : multiple forks at the same time if they vote on a fork then switch to 64 : a different one, unlike ghost. votes uses both replay and gossip 65 : votes when counting stake. 66 : 67 : What's the difference between fd_hfork and fd_votes? 68 : 69 : Both operate on vote transactions (not vote accounts), but have very 70 : different purposes and accounting methods. 71 : 72 : fd_hfork detects hard forks that result from runtime execution 73 : differences. These manifest as different bank hashes for a given 74 : block id, meaning validators agreed on which block to process but 75 : arrived at different ledger states after executing it. This 76 : indicates a consensus bug (e.g. Firedancer and Agave disagree on the 77 : result of executing transactions in a block). 78 : 79 : fd_votes detects different block ids for a given slot, which 80 : indicates equivocation by a leader: the leader produced multiple 81 : different blocks for the same slot. This is a different problem 82 : entirely- it is about leader misbehavior rather than execution 83 : divergence. 84 : 85 : A note on slots and block ids: vote transactions only contain the 86 : block_id of the last vote slot (and do not specify what block_ids 87 : previous vote slots correspond to. Agave assumes if the hash of the 88 : last vote slot matches, all the previous slots in the tower match as 89 : well. Agave uses bank hashes instead of block_ids (the relevant code 90 : predates block_ids) and maps slots to bank hashes during replay. 91 : 92 : As a result, there can be multiple block ids for a given slot. votes 93 : tracks the block_id for each slot using fd_tower_block, and also 94 : "duplicate confirmation". If votes observes a duplicate confirmation 95 : for a different block_id than the one it has for a given slot, it 96 : updates the block_id for that slot to the duplicate confirmed one. */ 97 : 98 : /* FD_VOTES_PARANOID: Define this to non-zero at compile time to turn 99 : on additional runtime integrity checks. */ 100 : 101 : #include "../fd_choreo_base.h" 102 : 103 : #ifndef FD_VOTES_PARANOID 104 : #define FD_VOTES_PARANOID 1 105 : #endif 106 : 107 : struct fd_votes_blk_key { 108 : ulong slot; 109 : fd_hash_t block_id; 110 : }; 111 : typedef struct fd_votes_blk_key fd_votes_blk_key_t; 112 : 113 : struct fd_votes_blk { 114 : fd_votes_blk_key_t key; /* blk_map key: (slot, block_id) */ 115 : ulong stake; 116 : uint next; /* pool next */ 117 : struct { 118 : uint prev; 119 : uint next; 120 : } map; 121 : struct { 122 : uint prev; 123 : uint next; 124 : } dlist; 125 : uchar flags; /* first 4 bits: confirmation levels, last 4 bits: forward confirmation levels */ 126 : }; 127 : typedef struct fd_votes_blk fd_votes_blk_t; 128 : 129 : FD_STATIC_ASSERT( sizeof(fd_votes_blk_t)==72UL, fd_votes_blk ); 130 : 131 : struct fd_votes; 132 : typedef struct fd_votes fd_votes_t; 133 : 134 : FD_PROTOTYPES_BEGIN 135 : 136 : /* fd_votes_{align,footprint} return the required alignment and 137 : footprint of a memory region suitable for use as a votes. align 138 : returns fd_votes_ALIGN. footprint returns fd_votes_FOOTPRINT. */ 139 : 140 : FD_FN_CONST ulong 141 : fd_votes_align( void ); 142 : 143 : ulong 144 : fd_votes_footprint( ulong slot_max, 145 : ulong vtr_max ); 146 : 147 : /* fd_votes_new formats an unused memory region for use as a votes. mem 148 : is a non-NULL pointer to this region in the local address space with 149 : the required footprint and alignment. */ 150 : 151 : void * 152 : fd_votes_new( void * shmem, 153 : ulong slot_max, 154 : ulong vtr_max, 155 : ulong seed ); 156 : 157 : /* fd_votes_join joins the caller to the votes. votes points to the 158 : first byte of the memory region backing the votes in the caller's 159 : address space. 160 : 161 : Returns a pointer in the local address space to votes on success. */ 162 : 163 : fd_votes_t * 164 : fd_votes_join( void * votes ); 165 : 166 : /* fd_votes_leave leaves a current local join. Returns a pointer to the 167 : underlying shared memory region on success and NULL on failure (logs 168 : details). Reasons for failure include votes is NULL. */ 169 : 170 : void * 171 : fd_votes_leave( fd_votes_t const * votes ); 172 : 173 : /* fd_votes_delete unformats a memory region used as a votes. Assumes 174 : only the local process is joined to the region. Returns a pointer to 175 : the underlying shared memory region or NULL if used obviously in 176 : error (e.g. votes is obviously not a votes ... logs details). The 177 : ownership of the memory region is transferred to the caller. */ 178 : 179 : void * 180 : fd_votes_delete( void * votes ); 181 : 182 : /* fd_votes_query returns a pointer to the votes block entry for the 183 : given (slot, block_id), or NULL if not found. 184 : 185 : If block_id is NULL, searches all block_ids for the slot and returns 186 : the one with the highest forward confirmation level (upper nibble of 187 : flags), or NULL if no forward-confirmed entry exists. */ 188 : 189 : fd_votes_blk_t * 190 : fd_votes_query( fd_votes_t * votes, 191 : ulong slot, 192 : fd_hash_t const * block_id ); 193 : 194 : /* fd_votes_count_vote return codes. */ 195 : 196 258 : #define FD_VOTES_SUCCESS ( 0) /* vote counted successfully */ 197 27 : #define FD_VOTES_ERR_VOTE_TOO_NEW (-1) /* vote_slot >= root + slot_max */ 198 6 : #define FD_VOTES_ERR_UNKNOWN_VTR (-2) /* voter not in vtr_map */ 199 99 : #define FD_VOTES_ERR_ALREADY_VOTED (-3) /* voter already voted for this slot */ 200 : 201 : /* fd_votes_count_vote counts stake towards the voted (slot, block_id) 202 : for vote_acc. The caller passes stake explicitly because it depends 203 : on the vote's epoch, which votes does not track. Assumes the votes 204 : root has already been initialized via fd_votes_publish. Returns 205 : FD_VOTES_SUCCESS on success, or a negative FD_VOTES_ERR_* code if 206 : the vote was not counted. */ 207 : 208 : int 209 : fd_votes_count_vote( fd_votes_t * votes, 210 : fd_pubkey_t const * vote_acc, 211 : ulong stake, 212 : ulong slot, 213 : fd_hash_t const * block_id ); 214 : 215 : /* fd_votes_update_voters updates the set of voters tracked by votes. 216 : Should be called on each epoch boundary when the stake-weighted voter 217 : set changes. Voters not in vote_accs[0..cnt) are removed. New 218 : voters are added and assigned bit positions in the per-slot vtrs 219 : bitset. Existing voters keep their old bit positions. All existing 220 : slot vtrs are intersected with the kept set to clear removed voters' 221 : bits. vote_accs is an array of length cnt, where vote_accs[i] is the 222 : vote account address. */ 223 : 224 : void 225 : fd_votes_update_voters( fd_votes_t * votes, 226 : fd_pubkey_t const * vote_accs, 227 : ulong cnt ); 228 : 229 : /* fd_votes_publish publishes root as the new votes root slot, removing 230 : all blocks with slot numbers < the new votes root slot. Some slots 231 : on minority forks that were pruned but >= the new root may remain but 232 : they will eventually be pruned as well as the root advances. */ 233 : 234 : void 235 : fd_votes_publish( fd_votes_t * votes, 236 : ulong root ); 237 : 238 : FD_PROTOTYPES_END 239 : 240 : #endif /* HEADER_fd_src_choreo_votes_fd_votes_h */
