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 : struct fd_votes_vtr;
135 : typedef struct fd_votes_vtr fd_votes_vtr_t;
136 :
137 : FD_PROTOTYPES_BEGIN
138 :
139 : /* fd_votes_{align,footprint} return the required alignment and
140 : footprint of a memory region suitable for use as a votes. align
141 : returns fd_votes_ALIGN. footprint returns fd_votes_FOOTPRINT. */
142 :
143 : FD_FN_CONST ulong
144 : fd_votes_align( void );
145 :
146 : ulong
147 : fd_votes_footprint( ulong slot_max,
148 : ulong vtr_max );
149 :
150 : /* fd_votes_new formats an unused memory region for use as a votes. mem
151 : is a non-NULL pointer to this region in the local address space with
152 : the required footprint and alignment. */
153 :
154 : void *
155 : fd_votes_new( void * shmem,
156 : ulong slot_max,
157 : ulong vtr_max,
158 : ulong seed );
159 :
160 : /* fd_votes_join joins the caller to the votes. votes points to the
161 : first byte of the memory region backing the votes in the caller's
162 : address space.
163 :
164 : Returns a pointer in the local address space to votes on success. */
165 :
166 : fd_votes_t *
167 : fd_votes_join( void * votes );
168 :
169 : /* fd_votes_leave leaves a current local join. Returns a pointer to the
170 : underlying shared memory region on success and NULL on failure (logs
171 : details). Reasons for failure include votes is NULL. */
172 :
173 : void *
174 : fd_votes_leave( fd_votes_t const * votes );
175 :
176 : /* fd_votes_delete unformats a memory region used as a votes. Assumes
177 : only the local process is joined to the region. Returns a pointer to
178 : the underlying shared memory region or NULL if used obviously in
179 : error (e.g. votes is obviously not a votes ... logs details). The
180 : ownership of the memory region is transferred to the caller. */
181 :
182 : void *
183 : fd_votes_delete( void * votes );
184 :
185 : /* fd_votes_query returns a pointer to the votes block entry for the
186 : given (slot, block_id), or NULL if not found.
187 :
188 : If block_id is NULL, searches all block_ids for the slot and returns
189 : the one with the highest forward confirmation level (upper nibble of
190 : flags), or NULL if no forward-confirmed entry exists. */
191 :
192 : fd_votes_blk_t *
193 : fd_votes_query( fd_votes_t * votes,
194 : ulong slot,
195 : fd_hash_t const * block_id );
196 :
197 : /* fd_votes_count_vote return codes. */
198 :
199 0 : #define FD_VOTES_SUCCESS ( 0) /* vote counted successfully */
200 0 : #define FD_VOTES_ERR_VOTE_TOO_NEW (-1) /* vote_slot >= root + slot_max */
201 0 : #define FD_VOTES_ERR_UNKNOWN_VTR (-2) /* voter not in vtr_map */
202 0 : #define FD_VOTES_ERR_ALREADY_VOTED (-3) /* voter already voted for this slot */
203 :
204 : /* fd_votes_count_vote counts stake towards the voted (slot, block_id)
205 : for vote_acc. The caller passes stake explicitly because it depends
206 : on the vote's epoch, which votes does not track. Assumes the votes
207 : root has already been initialized via fd_votes_publish. Returns
208 : FD_VOTES_SUCCESS on success, or a negative FD_VOTES_ERR_* code if
209 : the vote was not counted. */
210 :
211 : int
212 : fd_votes_count_vote( fd_votes_t * votes,
213 : fd_pubkey_t const * vote_acc,
214 : ulong stake,
215 : ulong slot,
216 : fd_hash_t const * block_id );
217 :
218 : /* fd_votes_vtr_query returns the voter tracked for vote_acc, or NULL
219 : if there is none. The handle stays valid until the next
220 : fd_votes_update_voters. fd_votes_count_vote_vtr is
221 : fd_votes_count_vote with the voter looked up by the caller (NULL for
222 : an unknown voter): a caller counting several slots of one vote txn
223 : looks the voter up once. For every (votes, vote_acc, stake, slot,
224 : block_id), fd_votes_count_vote_vtr( votes, fd_votes_vtr_query( votes,
225 : vote_acc ), stake, slot, block_id ) returns what fd_votes_count_vote
226 : does and leaves votes in the same state, VOTE_TOO_NEW before
227 : UNKNOWN_VTR included. */
228 :
229 : fd_votes_vtr_t *
230 : fd_votes_vtr_query( fd_votes_t * votes,
231 : fd_pubkey_t const * vote_acc );
232 :
233 : int
234 : fd_votes_count_vote_vtr( fd_votes_t * votes,
235 : fd_votes_vtr_t * vtr,
236 : ulong stake,
237 : ulong slot,
238 : fd_hash_t const * block_id );
239 :
240 : /* fd_votes_update_voters updates the set of voters tracked by votes.
241 : Should be called on each epoch boundary when the stake-weighted voter
242 : set changes. Voters not in vote_accs[0..cnt) are removed. New
243 : voters are added and assigned bit positions in the per-slot vtrs
244 : bitset. Existing voters keep their old bit positions. All existing
245 : slot vtrs are intersected with the kept set to clear removed voters'
246 : bits. vote_accs is an array of length cnt, where vote_accs[i] is the
247 : vote account address. */
248 :
249 : void
250 : fd_votes_update_voters( fd_votes_t * votes,
251 : fd_pubkey_t const * vote_accs,
252 : ulong cnt );
253 :
254 : /* fd_votes_publish publishes root as the new votes root slot, removing
255 : all blocks with slot numbers < the new votes root slot. Some slots
256 : on minority forks that were pruned but >= the new root may remain but
257 : they will eventually be pruned as well as the root advances. */
258 :
259 : void
260 : fd_votes_publish( fd_votes_t * votes,
261 : ulong root );
262 :
263 : FD_PROTOTYPES_END
264 :
265 : #endif /* HEADER_fd_src_choreo_votes_fd_votes_h */
|
