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. 6 : 7 : Unlike duplicate and optimistic confirmation, propagation is counted 8 : at the slot-level rather than block id-level. So two votes for 9 : different block ids would count towards the same slot. This is 10 : intentionally done to mirror Agave behavior. 11 : 12 : Solana reaches consensus via replay, but can "forward confirm" slots 13 : ahead of the replay tip by listening to vote txns from gossip or TPU. 14 : The larger max_live_slots (specified in configuration toml), the 15 : further ahead slots can be cluster confirmed before they are 16 : replayed. 17 : 18 : On the similarities and differences between fd_ghost / fd_tower vs. 19 : fd_notar: 20 : 21 : The reason both fd_ghost / fd_tower and fd_notar exist even though 22 : they do seemingly similar things (tracking vote stake on blocks) is 23 : because Solana implements the rules quite differently. 24 : 25 : At a high-level, fd_ghost / fd_tower is based on vote accounts vs. 26 : fd_notar which is based on vote _transactions_. Everything in 27 : fd_ghost / fd_tower is dependent on the vote account's state after 28 : the vote txns have been replayed. So we only have stake information 29 : in fd_ghost / fd_tower for a block, if that block has been replayed. 30 : 31 : On the other hand, fd_notar processes vote transactions as they come 32 : in from gossip and TPU, so it does not have this same requirement 33 : that the block has been replayed. This is important, because block 34 : transmission is unreliable, and notar provides a fallback mechanism 35 : for detecting votes for blocks we don't have. fd_notar still ingests 36 : replay votes as well, so it is guaranteed to be a superset of the 37 : votes tracked by fd_ghost / fd_tower, though note this assumption is 38 : contingent on feature "Deprecate legacy vote instructions" because 39 : notar only counts TowerSync ixs and ignores any other deprecated vote 40 : instructions. 41 : 42 : There are also differences in how votes are counted between the two. 43 : In fd_ghost, we use the GHOST rule to recursively sum the stake of 44 : the subtree (a slot and all its descendants). The LMD rule counts a 45 : validator's stake to at most one fork. When the validator switches 46 : forks, their stake is subtracted from the old fork and added to the 47 : new fork. The tree is then traversed as part of fork choice to find 48 : the best leaf ("head"). ghost bases fork choice purely on replay 49 : votes, but marks forks valid or invalid with gossip votes. 50 : 51 : In fd_notar, we count votes towards only the block itself, and not 52 : its ancestors. Also a validator's stake can be counted towards 53 : multiple forks at the same time if they vote on a fork then switch to 54 : a different one, unlike ghost. notar uses both replay and gossip 55 : votes when counting stake. 56 : 57 : A note on slots and block ids: vote transactions only contain the 58 : block_id of the last vote slot (and do not specify what block_ids 59 : previous vote slots correspond to. Agave assumes if the hash of the 60 : last vote slot matches, all the previous slots in the tower match as 61 : well. Agave uses bank hashes instead of block_ids (the relevant code 62 : predates block_ids) and maps slots to bank hashes during replay. 63 : 64 : As a result, there can be multiple block ids for a given slot. notar 65 : tracks the block_id for each slot using fd_tower_block, and also 66 : "duplicate confirmation". If notar observes a duplicate confirmation 67 : for a different block_id than the one it has for a given slot, it 68 : updates the block_id for that slot to the duplicate confirmed one. */ 69 : 70 : /* FD_NOTAR_PARANOID: Define this to non-zero at compile time to turn 71 : on additional runtime integrity checks. */ 72 : 73 : #include "../fd_choreo_base.h" 74 : #include "../tower/fd_tower_voters.h" 75 : 76 : #ifndef FD_NOTAR_PARANOID 77 : #define FD_NOTAR_PARANOID 1 78 : #endif 79 : 80 : #define FD_NOTAR_FLAG_CONFIRMED_PROPAGATED (0) 81 : #define FD_NOTAR_FLAG_CONFIRMED_DUPLICATE (1) 82 : #define FD_NOTAR_FLAG_CONFIRMED_OPTIMISTIC (2) 83 : 84 : #define SET_NAME fd_notar_slot_vtrs 85 0 : #define SET_MAX FD_VOTER_MAX 86 : #include "../../util/tmpl/fd_set.c" 87 : 88 : struct fd_notar_slot { 89 : ulong slot; /* map key, vote slot */ 90 : ulong parent_slot; /* parent slot */ 91 : ulong prev_leader_slot; /* previous slot in which we were leader */ 92 : ulong stake; /* amount of stake that has voted for this slot */ 93 : int is_leader; /* whether this slot was our own leader slot */ 94 : int is_propagated; /* whether this slot has reached 1/3 of stake */ 95 : 96 : fd_hash_t block_ids[FD_VOTER_MAX]; /* one block id per voter per slot */ 97 : ulong block_ids_cnt; /* count of block ids */ 98 : 99 : fd_notar_slot_vtrs_t vtrs[fd_notar_slot_vtrs_word_cnt]; /* who has voted for this slot, curr epoch */ 100 : }; 101 : typedef struct fd_notar_slot fd_notar_slot_t; 102 : 103 : struct fd_notar_blk { 104 : fd_hash_t block_id; /* map key */ 105 : uint hash; /* reserved for fd_map_dynamic */ 106 : ulong slot; /* slot associated with this block */ 107 : ulong stake; /* sum of stake that has voted for this block_id */ 108 : int level; /* confirmation level, set by caller */ 109 : int fwd_level; /* forward confirmation level, set by caller */ 110 : }; 111 : typedef struct fd_notar_blk fd_notar_blk_t; 112 : 113 : #define MAP_NAME fd_notar_blk 114 0 : #define MAP_T fd_notar_blk_t 115 0 : #define MAP_KEY block_id 116 0 : #define MAP_KEY_T fd_hash_t 117 0 : #define MAP_KEY_NULL hash_null 118 : #define MAP_KEY_EQUAL_IS_SLOW 1 119 0 : #define MAP_KEY_INVAL(k) MAP_KEY_EQUAL((k),MAP_KEY_NULL) 120 0 : #define MAP_KEY_EQUAL(k0,k1) (!memcmp( (k0).key, (k1).key, 32UL )) 121 0 : #define MAP_KEY_HASH(key,s) ((MAP_HASH_T)( (key).ul[1] )) 122 : #include "../../util/tmpl/fd_map_dynamic.c" 123 : 124 : /* TODO map key DOS */ 125 : 126 : #define MAP_NAME fd_notar_slot 127 0 : #define MAP_T fd_notar_slot_t 128 0 : #define MAP_KEY slot 129 0 : #define MAP_KEY_NULL ULONG_MAX 130 0 : #define MAP_KEY_INVAL(key) ((key)==ULONG_MAX) 131 : #define MAP_MEMOIZE 0 132 : #include "../../util/tmpl/fd_map_dynamic.c" 133 : 134 : struct fd_notar_vtr { 135 : fd_pubkey_t addr; /* map key, vote account address */ 136 : uint hash; /* reserved for fd_map_dynamic */ 137 : ulong bit; /* bit position in fd_notar_slot_vtrs in epoch (ULONG_MAX if not set) */ 138 : ulong stake; /* amount of stake this voter has in epoch */ 139 : }; 140 : typedef struct fd_notar_vtr fd_notar_vtr_t; 141 : 142 : #define MAP_NAME fd_notar_vtr 143 0 : #define MAP_T fd_notar_vtr_t 144 0 : #define MAP_KEY addr 145 0 : #define MAP_KEY_T fd_pubkey_t 146 0 : #define MAP_KEY_NULL pubkey_null 147 : #define MAP_KEY_EQUAL_IS_SLOW 1 148 0 : #define MAP_KEY_INVAL(k) MAP_KEY_EQUAL((k),MAP_KEY_NULL) 149 0 : #define MAP_KEY_EQUAL(k0,k1) (!memcmp( (k0).key, (k1).key, 32UL )) 150 0 : #define MAP_KEY_HASH(key,s) ((MAP_HASH_T)( (key).ul[1] )) 151 : #include "../../util/tmpl/fd_map_dynamic.c" 152 : 153 : struct __attribute__((aligned(128UL))) fd_notar { 154 : ulong root; /* current root slot */ 155 : ulong slot_max; /* maximum number of slots notar can track */ 156 : fd_notar_slot_t * slot_map; /* tracks who has voted for a given slot */ 157 : fd_notar_blk_t * blk_map; /* tracks amount of stake for a given block (keyed by block id) */ 158 : fd_notar_vtr_t * vtr_map; /* tracks each voter's stake and prev vote */ 159 : }; 160 : typedef struct fd_notar fd_notar_t; 161 : 162 : /* fd_notar_{align,footprint} return the required alignment and 163 : footprint of a memory region suitable for use as a notar. align 164 : returns fd_notar_ALIGN. footprint returns fd_notar_FOOTPRINT. */ 165 : 166 : FD_FN_CONST static inline ulong 167 0 : fd_notar_align( void ) { 168 0 : return alignof(fd_notar_t); 169 0 : } 170 : 171 : FD_FN_CONST static inline ulong 172 0 : fd_notar_footprint( ulong slot_max ) { 173 0 : int lg_slot_max = fd_ulong_find_msb( fd_ulong_pow2_up( slot_max ) ) + 1; 174 0 : int lg_blk_max = fd_ulong_find_msb( fd_ulong_pow2_up( slot_max * FD_VOTER_MAX ) ) + 1; 175 0 : int lg_vtr_max = fd_ulong_find_msb( fd_ulong_pow2_up( FD_VOTER_MAX ) ) + 1; 176 0 : return FD_LAYOUT_FINI( 177 0 : FD_LAYOUT_APPEND( 178 0 : FD_LAYOUT_APPEND( 179 0 : FD_LAYOUT_APPEND( 180 0 : FD_LAYOUT_APPEND( 181 0 : FD_LAYOUT_INIT, 182 0 : alignof(fd_notar_t), sizeof(fd_notar_t) ), 183 0 : fd_notar_slot_align(), fd_notar_slot_footprint( lg_slot_max ) ), 184 0 : fd_notar_blk_align(), fd_notar_blk_footprint( lg_blk_max ) ), 185 0 : fd_notar_vtr_align(), fd_notar_vtr_footprint( lg_vtr_max ) ), 186 0 : fd_notar_align() ); 187 0 : } 188 : 189 : /* fd_notar_new formats an unused memory region for use as a notar. mem 190 : is a non-NULL pointer to this region in the local address space with 191 : the required footprint and alignment. */ 192 : 193 : void * 194 : fd_notar_new( void * shmem, 195 : ulong slot_max ); 196 : 197 : /* fd_notar_join joins the caller to the notar. notar points to the 198 : first byte of the memory region backing the notar in the caller's 199 : address space. 200 : 201 : Returns a pointer in the local address space to notar on success. */ 202 : 203 : fd_notar_t * 204 : fd_notar_join( void * notar ); 205 : 206 : /* fd_notar_leave leaves a current local join. Returns a pointer to the 207 : underlying shared memory region on success and NULL on failure (logs 208 : details). Reasons for failure include notar is NULL. */ 209 : 210 : void * 211 : fd_notar_leave( fd_notar_t const * notar ); 212 : 213 : /* fd_notar_delete unformats a memory region used as a notar. Assumes 214 : only the local process is joined to the region. Returns a pointer to 215 : the underlying shared memory region or NULL if used obviously in 216 : error (e.g. notar is obviously not a notar ... logs details). The 217 : ownership of the memory region is transferred to the caller. */ 218 : 219 : void * 220 : fd_notar_delete( void * notar ); 221 : 222 : /* fd_notar_count_vote counts addr's stake towards the voted slots in 223 : their tower. Returns 1 if block_id is duplicate confirmed by this 224 : vote, otherwise 0 (useful for the downstream tower tile to implement 225 : duplicate confirmation notifications). addr is the vote account 226 : address, stake is the amount of stake associated with the vote 227 : account in the current epoch, slot is slot being voted for, block_id 228 : is the voter's proposed block id for this vote slot. */ 229 : 230 : fd_notar_blk_t * 231 : fd_notar_count_vote( fd_notar_t * notar, 232 : fd_pubkey_t const * addr, 233 : ulong slot, 234 : fd_hash_t const * block_id ); 235 : 236 : /* fd_notar_publish publishes root as the new notar root slot, removing 237 : all blocks with slot numbers < the old notar root slot. Some slots 238 : on minority forks that were pruned but > than the new root may remain 239 : but they will eventually be pruned as well as the root advances. */ 240 : 241 : void 242 : fd_notar_publish( fd_notar_t * notar, 243 : ulong root ); 244 : 245 : #endif /* HEADER_fd_src_choreo_notar_fd_notar_h */
