Line data Source code
1 : #ifndef HEADER_fd_src_choreo_tower_fd_tower_h
2 : #define HEADER_fd_src_choreo_tower_fd_tower_h
3 :
4 : /* fd_tower presents an API for Solana's TowerBFT algorithm.
5 :
6 : What is TowerBFT? TowerBFT is an algorithm for converging a
7 : supermajority of stake in the validator cluster on the same fork.
8 :
9 : /-- 3-- 4 (A)
10 : 1-- 2
11 : \-- 5 (B)
12 :
13 : Above is a diagram of a fork. The leader for slot 5 decided to build
14 : off slot 2, rather than slot 4. This can happen for various reasons,
15 : for example network propagation delay. We now have two possible forks
16 : labeled A and B. The consensus algorithm has to pick one of them.
17 :
18 : So, how does the consensus algorithm pick? As detailed in
19 : fd_ghost.h, we pick the fork based on the most stake from votes,
20 : called the "heaviest". Validators vote for blocks during replay, and
21 : simultaneously use other validator’s votes to determine which block
22 : to vote for. This encourages convergence, because as one fork gathers
23 : more votes, more and more votes pile-on, solidifying its position as
24 : the heaviest fork.
25 :
26 : /-- 3-- 4 (10%)
27 : 1-- 2
28 : \-- 5 (9%)
29 :
30 : However, network propagation delay of votes can lead us to think one
31 : fork is heaviest, before observing new votes that indicate another
32 : fork is heavier. So our consensus algorithm also needs to support
33 : switching.
34 :
35 : /-- 3-- 4 (10%)
36 : 1-- 2
37 : \-- 5 (15%)
38 :
39 : At the same time we don’t want excessive switching. The more often
40 : validators switch, the more difficult it will be to achieve that
41 : pile-on effect I just described.
42 :
43 : Note that to switch forks, you need to rollback a given slot and its
44 : descendants on that fork. In the example above, to switch to 1, 2, 5,
45 : we need to rollback 3 and 4. The consensus algorithm makes it more
46 : costly the further you want to rollback a fork. Here, I’ve added a
47 : column lockout, which doubles for every additional slot you want to
48 : rollback.
49 :
50 : Eventually you have traversed far enough down a fork, that the
51 : lockout is so great it is infeasible to imagine it ever rolling back
52 : in practice. So you can make that fork permanent or “commit” it.
53 : Once all validators do this, the blockchain now just has a single
54 : fork.
55 :
56 : Armed with some intuition, let’s now begin defining some terminology.
57 : Here is a diagram of a validator's "vote tower":
58 :
59 : slot | confirmation count (conf)
60 : --------------------------------
61 : 4 | 1
62 : 3 | 2
63 : 2 | 3
64 : 1 | 4
65 :
66 : It is a stack structure in which each element is a vote. The vote
67 : slot column indicates which slots the validator has voted for,
68 : ordered from most to least recent.
69 :
70 : The confirmation count column indicates how many consecutive votes on
71 : the same fork have been pushed on top of that vote. You are
72 : confirming your own votes for a fork every time you vote on top of
73 : the same fork.
74 :
75 : Two related concepts to confirmation count are lockout and expiration
76 : slot. Lockout equals 2 to the power of confirmation count. Every
77 : time we “confirm” a vote by voting on top of it, we double the
78 : lockout. The expiration slot is the sum of vote slot and lockout, so
79 : it also increases when lockouts double. It represents which slot the
80 : vote will expire. When a vote expires, it is popped from the top of
81 : the tower. An important Tower rule is that a validator cannot vote
82 : for a different fork from a given vote slot, until reaching the
83 : expiration slot for that vote slot. To summarize, the further a
84 : validator wants to rollback their fork (or vote slots) the longer the
85 : validator needs to wait without voting (in slot time).
86 :
87 : Here is the same tower, fully-expanded to include all the fields:
88 :
89 : slot | conf | lockout | expiration
90 : ----------------------------------
91 : 4 | 1 | 2 | 6
92 : 3 | 2 | 4 | 7
93 : 2 | 3 | 8 | 10
94 : 1 | 4 | 16 | 17
95 :
96 : Based on this tower, the validator is locked out from voting for any
97 : slot <= 6 that is on a different fork than slot 4. I’d like to
98 : emphasize that the expiration is with respect to the vote slot, and
99 : is _not_ related to the Proof-of-History slot or what the "current
100 : slot" is. So even if the current slot is now 7, the validator can’t
101 : go back and vote for slot 5, if slot 5 were on a different fork than
102 : 4. The earliest valid vote slot this validator could submit for a
103 : different fork from 4 would be slot 7 or later.
104 :
105 : Next let’s look at how the tower makes state transitions. Here we
106 : have the previous example tower, with a before-and-after view with
107 : respect to a vote for slot 9:
108 :
109 : (before) slot | conf
110 : -----------
111 : 4 | 1
112 : 3 | 2
113 : 2 | 3
114 : 1 | 4
115 :
116 : (after) slot | conf
117 : -----------
118 : 9 | 1
119 : 2 | 3
120 : 1 | 4
121 :
122 : As you can see, we added a vote for slot 9 to the top of the tower.
123 : But we also removed the votes for slot 4 and slot 3. What happened?
124 : This is an example of vote expiry in action. When we voted for slot
125 : 9, this exceeded the expirations of vote slots 4 and 3, which were 6
126 : and 7 respectively. This action of voting triggered the popping of
127 : the expired votes from the top of the tower.
128 :
129 : Next, we add a vote for slot 10:
130 :
131 : (before) slot | conf
132 : -----------
133 : 9 | 1
134 : 2 | 3
135 : 1 | 4
136 :
137 : (after) slot | conf
138 : -----------
139 : 10 | 1
140 : 9 | 2
141 : 2 | 3
142 : 1 | 4
143 :
144 : The next vote for slot 10 doesn’t involve expirations, so we just add
145 : it to the top of the tower. Also, here is an important property of
146 : lockouts. Note that the lockout for vote slot 9 doubled (ie. the
147 : confirmation count increased by 1) but the lockouts of vote slots 2
148 : and 1 remained unchanged.
149 :
150 : The reason for this is confirmation counts only increase when they
151 : are consecutive in the vote tower. Because 4 and 3 were expired
152 : previously by the vote for 9, that consecutive property was broken.
153 : In this case, the vote for slot 10 is only consecutive with slot 9,
154 : but not 2 and 1. Specifically, there is a gap in the before-tower at
155 : confirmation count 2.
156 :
157 : In the after-tower, all the votes are again consecutive (confirmation
158 : counts 1, 2, 3, 4 are all accounted for), so the next vote will
159 : result in all lockouts doubling as long as it doesn’t result in more
160 : expirations.
161 :
162 : One other thing I’d like to point out about this vote for slot 10.
163 : Even though 10 >= the expiration slot of vote slot 2, which is 10,
164 : voting for 11 did not expire the vote for 2. This is because
165 : expiration happens top-down and contiguously. Because vote slot 9
166 : was not expired, we do not proceed with expiring 2.
167 :
168 : In the Tower rules, once a vote reaches a conf count of 32, it is
169 : considered rooted and it is popped from the bottom of the tower.
170 : Here is an example where 1 got rooted and popped from the bottom:
171 :
172 : (before) slot | conf
173 : -----------
174 : 50 | 1
175 : ... | ... (29 votes elided)
176 : 1 | 31
177 :
178 : (after) slot | conf
179 : -----------
180 : 53 | 1
181 : ... | ... (29 votes elided)
182 : 2 | 31
183 :
184 : So the tower is really a double-ended queue rather than a stack.
185 :
186 : Rooting has implications beyond the Tower. It's what we use to prune
187 : our state. Every time tower makes a new root slot, we prune any old
188 : state that does not originate from that new root slot. Our
189 : blockstore will discard blocks below that root, our forks structure
190 : will discard stale banks, our accounts database will discard stale
191 : transactions (which in turn track modifications to accounts), and
192 : ghost (which is our fork select tree) will discard stale nodes
193 : tracking stake percentages. We call this operation advancing the
194 : root.
195 :
196 : Note that the vote slots are not necessarily consecutive. Here I
197 : elided the votes sandwiched between the newest and oldest votes for
198 : brevity.
199 :
200 : Next, let’s go over three additional tower checks. These three
201 : checks further reinforce the consensus algorithm we established with
202 : intuition, in this case getting a supermajority (ie. 2/3) of stake to
203 : converge on a fork.
204 :
205 : The first is the threshold check. The threshold check makes sure at
206 : least 2/3 of stake has voted for the same fork as the vote at depth 8
207 : in our tower. Essentially, this guards our tower from getting too
208 : out of sync with the rest of the cluster. If we get too out of sync
209 : we can’t vote for a long time, because we had to rollback a vote we
210 : had already confirmed many times and had a large lockout. This might
211 : otherwise happen as the result of a network partition where we can
212 : only communicate with a subset of stake.
213 :
214 : Next is the lockout check. We went in detail on this earlier when
215 : going through the lockout and expiration slot, and as before, the
216 : rule is we can only vote on a slot for a different fork from a
217 : previous vote, after that vote’s expiration slot.
218 :
219 : Given this fork and tower from earlier:
220 :
221 : /-- 3-- 4
222 : 1-- 2
223 : \-- 5
224 :
225 : slot | conf
226 : -----------
227 : 4 | 1
228 : 3 | 2
229 : 2 | 3
230 : 1 | 4
231 :
232 : You’re locked out from voting for 5 because it’s on a different fork
233 : from 4 and the expiration slot of your previous vote for 4 is 6.
234 :
235 : However, if we introduce a new slot 9:
236 :
237 : /-- 3-- 4
238 : 1-- 2
239 : \-- 5-- 9
240 :
241 : slot | conf
242 : -----------
243 : 9 | 1
244 : 2 | 3
245 : 1 | 4
246 :
247 : Here the new Slot 9 descends from 5 and exceeds vote slot 4’s
248 : expiration slot of 6 unlike 5.
249 :
250 : After your lockout expires, the tower rules allow you to vote for
251 : descendants of the fork slot you wanted to switch to in the first
252 : place (here, 9 descending from 5). So we eventually switch to the
253 : fork we wanted, by voting for 9 and expiring 3 and 4.
254 :
255 : Importantly, notice that the fork slots and vote slots are not exactly
256 : 1-to-1. While conceptually our tower is voting for the fork 1, 2, 5,
257 : 9, the vote for 5 is only implied. Our tower votes themselves still
258 : can’t include 5 due to lockout.
259 :
260 : Finally, the switch check. The switch check is used to safeguard
261 : optimistic confirmation. Optimistic confirmation is when a slot gets
262 : 2/3 of stake-weighted votes. This is then treated as a signal that the
263 : slot will eventually get rooted. However, to actually guarantee this
264 : we need a rule that prevents validators from arbitrarily switching
265 : forks (even when their vote lockout has expired). This rule is the
266 : switch check.
267 :
268 : The switch check is additional to the lockout check. Before switching
269 : forks, we need to make sure at least 38% of stake has voted for a
270 : different fork than our own. Different fork is defined by finding the
271 : greatest common ancestor of our last voted fork slot and the slot we
272 : want to switch to. Any forks descending from the greatest common
273 : ancestor (which I will subsequently call the GCA) that are not our
274 : own fork are counted towards the switch check stake.
275 :
276 : Here we visualize the switch check:
277 :
278 : /-- 7
279 : /-- 3-- 4
280 : 1-- 2 -- 6
281 : \-- 5-- 9
282 :
283 : First, we find the GCA of 4 and 9 which is 2. Then we look at all the
284 : descendants of the GCA that do not share a fork with us, and make sure
285 : their stake sums to more than 38%.
286 :
287 : I’d like to highlight that 7 here is not counted towards the switch
288 : proof, even though it is on a different fork from 4. This is because
289 : it’s on the same fork relative to the GCA.
290 :
291 : So that covers the checks. Next, there are two additional important
292 : concepts: "reset slot" and "vote slot". The reset slot is the slot you
293 : reset PoH to when it's your turn to be leader. Because you are
294 : responsible for producing a block, you need to decide which fork to
295 : build your block on. For example, if there are two competing slots 3
296 : and 4, you would decide whether to build 3 <- 5 or 4 <- 5. In general
297 : the reset slot is the same fork as the vote slot, but not always.
298 : There is an important reason for this. Recall this fork graph from
299 : earlier:
300 :
301 : /-- 3-- 4 (10%)
302 : 1-- 2
303 : \-- 5-- 6 (9%)
304 :
305 : In this diagram, 4 is the winner of fork choice. All future leaders
306 : now want to reset to slot 4. Naively, this makes sense because you
307 : maximize the chance of your block finalizing (and earning the rewards)
308 : if you greedily (in the algorithmic, and perhaps also literal sense)
309 : pick what's currently the heaviest.
310 :
311 : However, say most validators actually voted fork 5, even though we
312 : currently observe 3 as the heavier. For whatever reason, those votes
313 : for 5 just didn't land (the leader for 6 missed the votes, network
314 : blip, etc.)
315 :
316 : All these validators that voted for 5 are now constrained by the
317 : switch check (38% of stake), and none of them can actually switch
318 : their vote to 4 (which only has 10%). But they're all continuing to
319 : build blocks on top of fork 4, which importantly implies that votes
320 : for 5 will not be able to propagate. This is because the validators
321 : that can't switch continue to refresh their votes for 5, but those
322 : votes never "land" because no one is building blocks on top of fork
323 : 5 anymore (everyone is building on 4 because that's currently the
324 : heaviest).
325 :
326 : Therefore, it is important to reset to the same fork as your last vote
327 : slot, which is usually also the heaviest fork, but not always.
328 :
329 : Now let’s switch gears from theory back to practice. How does the
330 : literal mechanism of voting actually work?
331 :
332 : Validators don't send individual votes. Rather, they send their
333 : entire updated tower to the cluster every time. Essentially, the
334 : validator is continuously syncing their local tower with the cluster.
335 : That tower state is then stored inside a vote account, like any other
336 : state on Solana.
337 :
338 : On the flip side, validators also must stay in sync the other way from
339 : cluster to local. If a validator has previously voted, then they have
340 : an on-chain vote account containing the cluster's latest view of the
341 : tower (as of a given replay slot). If this on-chain tower is
342 : incompatible with the local one, they must be reconciled
343 : (fd_tower_reconcile - also note the etymology for the "TowerSync" vote
344 : instruction).
345 :
346 : Finally, a note on the difference between the Vote Program and
347 : TowerBFT. The Vote Program runs during transaction (block) execution.
348 : It checks that certain invariants about the tower inside a vote
349 : transaction are upheld (recall a validator sends their entire tower as
350 : part of a "vote"): otherwise, it fails the transaction. For example,
351 : it checks that every vote contains a tower in which the vote slots are
352 : strictly monotonically increasing. As a consequence, only valid
353 : towers are committed to the ledger. Another important detail of the
354 : Vote Program is that it only has a view of the current fork on which
355 : it is executing. Specifically, it can't observe what state is on
356 : other forks, like what a validator's tower looks like on fork A vs.
357 : fork B.
358 :
359 : The TowerBFT rules, on the other hand, run after transaction
360 : execution. Also unlike the Vote Program, the TowerBFT rules do not
361 : take the vote transactions as inputs: rather the inputs are the towers
362 : that have already been written to the ledger by the Vote Program. As
363 : described above, the Vote Program validates every tower, and in this
364 : way, the TowerBFT rules leverage the validation already done by the
365 : Vote Program to (mostly) assume each tower is valid. Every validator
366 : runs TowerBFT to update their own tower with votes based on the
367 : algorithm documented above. Importantly, TowerBFT has a view of all
368 : forks, and the validator makes a voting decision based on all forks.
369 : */
370 :
371 : #include "../fd_choreo_base.h"
372 : #include "fd_tower_serdes.h"
373 :
374 : #include "fd_tower_stakes.h"
375 : #include "../ghost/fd_ghost.h"
376 : #include "../votes/fd_votes.h"
377 : #include "../../disco/pack/fd_microblock.h"
378 :
379 5901 : #define FD_TOWER_LOCKOS_MAX 31UL
380 5748 : #define FD_TOWER_VOTE_MAX (FD_TOWER_LOCKOS_MAX)
381 :
382 : /* fd_tower is a representation of a validator's "vote tower" (described
383 : in detail in the preamble at the top of this file). The votes in the
384 : tower are stored in an fd_deque.c ordered from lowest to highest vote
385 : slot (highest to lowest confirmation count) relative to the head and
386 : tail. There can be at most FD_TOWER_VOTE_MAX votes in the tower. */
387 :
388 : struct fd_tower_vote {
389 : ulong slot; /* vote slot */
390 : ulong conf; /* confirmation count */
391 : };
392 : typedef struct fd_tower_vote fd_tower_vote_t;
393 :
394 : #define DEQUE_NAME fd_tower_vote
395 12 : #define DEQUE_T fd_tower_vote_t
396 5589 : #define DEQUE_MAX FD_TOWER_VOTE_MAX
397 : #include "../../util/tmpl/fd_deque.c"
398 :
399 : /* FD_TOWER_VOTE_{ALIGN,FOOTPRINT} provided for static declarations. */
400 :
401 : #define FD_TOWER_VOTE_ALIGN (alignof(fd_tower_vote_private_t))
402 : #define FD_TOWER_VOTE_FOOTPRINT (sizeof (fd_tower_vote_private_t))
403 : FD_STATIC_ASSERT( alignof(fd_tower_vote_private_t)==8UL, FD_TOWER_VOTE_ALIGN );
404 : FD_STATIC_ASSERT( sizeof (fd_tower_vote_private_t)==512UL, FD_TOWER_VOTE_FOOTPRINT );
405 :
406 : /* fd_tower_blk_t maintains tower-specific metadata about every block,
407 : such as what block_id we last replayed, what block_id we voted for,
408 : and what block_id was ultimately "duplicate confirmed".
409 :
410 : This is used by tower to make voting decisions, such as whether or
411 : not we can switch "forks". In this context, a fork is a branch of a
412 : tree that extends from the root to a leaf. For example:
413 :
414 : /-- 3-- 4 (A)
415 : 1-- 2
416 : \-- 5 (B)
417 :
418 : Here, A and B are two different forks. A is [1, 2, 3, 4] and B is
419 : [1, 2, 5], two branches that each extend from the root to a leaf.
420 :
421 : Note that even though fd_tower_blk_t is block_id-aware, it does not
422 : use them for determining parentage. Instead, parentage is based on
423 : slot numbers, so in cases of equivocation (duplicate blocks), tower
424 : will consider something an ancestor or descendant even if the block
425 : ids do not chain.
426 :
427 : This behavior intentionally mirrors the Agave logic implemented in
428 : `make_check_switch_threshold_decision`. Essentially, tower is unable
429 : to distinguish duplicates because the vote account format (in which
430 : towers are stored) only stores slot numbers and not block_ids. */
431 :
432 : struct fd_tower_blk {
433 : ulong slot; /* pool next / map key */
434 : ulong next; /* pool next / map next */
435 : ulong prev; /* map prev */
436 : ulong parent_slot; /* parent slot */
437 : ulong epoch; /* epoch of this slot */
438 : fd_hash_t bank_hash; /* our bank hash for this slot */
439 : fd_hash_t block_hash; /* last microblock header hash for this slot */
440 : int replayed; /* whether we've replayed this slot yet */
441 : fd_hash_t replayed_block_id; /* the block_id we _last_ replayed for this slot */
442 : int voted; /* whether we voted for this slot yet */
443 : fd_hash_t voted_block_id; /* the block_id we voted on for this slot */
444 : int confirmed; /* whether this slot has been duplicate confirmed */
445 : fd_hash_t confirmed_block_id; /* the block_id that was duplicate confirmed */
446 : int leader; /* whether this slot was our own leader slot */
447 : int propagated; /* whether this slot has been propagation confirmed (1/3 stake) */
448 : ulong prev_leader_slot; /* previous slot in which we were leader as of this slot (inclusive) */
449 : };
450 : typedef struct fd_tower_blk fd_tower_blk_t;
451 :
452 : /* fd_tower_vtr_t describes a single vote account that feeds into
453 : TowerBFT rules: vote account address, stake, and deserialized tower
454 : votes + root. The votes pointer points into pre-allocated storage
455 : managed by the tower and is joined once during init. */
456 :
457 : struct fd_tower_vtr {
458 : fd_pubkey_t vote_acc; /* vote account address */
459 : ulong stake; /* vote account stake */
460 : fd_tower_vote_t * votes; /* deserialized vote deque (pre-allocated, owned by tower) */
461 : ulong root; /* tower root slot (ULONG_MAX if none) */
462 : };
463 : typedef struct fd_tower_vtr fd_tower_vtr_t;
464 :
465 : #define DEQUE_NAME fd_tower_vtr
466 9 : #define DEQUE_T fd_tower_vtr_t
467 : #include "../../util/tmpl/fd_deque_dynamic.c"
468 :
469 : /* fd_tower_t wraps the vote deque, root slot, block metadata, and
470 : voter entries. Sub-structures are allocated inline after the struct.
471 : Use fd_tower_{new,join,leave,delete,align,footprint} to manage. */
472 :
473 : struct fd_tower {
474 : fd_tower_vote_t * votes; /* our local tower's vote deque */
475 : ulong root; /* our local tower's root slot (ULONG_MAX if none) */
476 :
477 : ulong blk_max; /* max number of blocks */
478 : ulong vtr_max; /* max number of voters */
479 : fd_tower_blk_t * blk_pool; /* pool of blk_t elements (NULL if blk_max==0) */
480 : void * blk_map; /* map chain of blk_t elements (NULL if blk_max==0) */
481 : fd_tower_vtr_t * vtrs; /* deque of voter entries (NULL if vtr_max==0) */
482 :
483 : void * lck_pool; /* lockout interval pool */
484 : void * lck_map; /* lockout interval map chain */
485 :
486 : fd_tower_stakes_vtr_map_t * stk_vtr_map;
487 : fd_tower_stakes_vtr_t * stk_vtr_pool;
488 : fd_tower_stakes_slot_t * stk_slot_map;
489 : fd_used_acc_scratch_t * stk_used_acc;
490 : };
491 : typedef struct fd_tower fd_tower_t;
492 :
493 : /* fd_tower_{align,footprint} return the required alignment and
494 : footprint of a memory region suitable for use as a tower.
495 : blk_max==0 creates a votes-only tower (for voter towers). */
496 :
497 : FD_FN_CONST ulong
498 : fd_tower_align( void );
499 :
500 : ulong
501 : fd_tower_footprint( ulong blk_max,
502 : ulong vtr_max );
503 :
504 : /* fd_tower_new formats an unused memory region for use as a tower. mem
505 : is a non-NULL pointer to this region in the local address space with
506 : the required footprint and alignment. seed is for the block map
507 : hash. */
508 :
509 : void *
510 : fd_tower_new( void * mem,
511 : ulong blk_max,
512 : ulong vtr_max,
513 : ulong seed );
514 :
515 : /* fd_tower_join joins the caller to the tower. tower points to the
516 : first byte of the memory region backing the tower in the caller's
517 : address space.
518 :
519 : Returns a pointer in the local address space to tower on success. */
520 :
521 : fd_tower_t *
522 : fd_tower_join( void * tower );
523 :
524 : /* fd_tower_leave leaves a current local join. Returns a pointer to the
525 : underlying shared memory region on success and NULL on failure (logs
526 : details). Reasons for failure include tower is NULL. */
527 :
528 : void *
529 : fd_tower_leave( fd_tower_t const * tower );
530 :
531 : /* fd_tower_delete unformats a memory region used as a tower. Assumes
532 : only the local process is joined to the region. Returns a pointer to
533 : the underlying shared memory region or NULL if used obviously in
534 : error (e.g. tower is obviously not a tower ... logs details). The
535 : ownership of the memory region is transferred to the caller. */
536 :
537 : void *
538 : fd_tower_delete( void * tower );
539 :
540 0 : #define FD_TOWER_FLAG_ANCESTOR_ROLLBACK 0 /* rollback to an ancestor of our prev vote */
541 0 : #define FD_TOWER_FLAG_SIBLING_CONFIRMED 1 /* our prev vote was a duplicate and its sibling got confirmed */
542 0 : #define FD_TOWER_FLAG_SAME_FORK 2 /* prev vote is on the same fork */
543 3 : #define FD_TOWER_FLAG_SWITCH_PASS 3 /* successfully switched to a different fork */
544 3 : #define FD_TOWER_FLAG_SWITCH_FAIL 4 /* failed to switch to a different fork */
545 3 : #define FD_TOWER_FLAG_LOCKOUT_FAIL 5 /* failed lockout check */
546 0 : #define FD_TOWER_FLAG_THRESHOLD_FAIL 6 /* failed threshold check */
547 0 : #define FD_TOWER_FLAG_PROPAGATED_FAIL 7 /* failed propagated check */
548 :
549 : struct fd_tower_out {
550 : uchar flags; /* one of FD_TOWER_{EMPTY,...} */
551 : ulong reset_slot; /* slot to reset PoH to */
552 : fd_hash_t reset_block_id; /* block ID to reset PoH to */
553 : ulong vote_slot; /* slot to vote for (ULONG_MAX if no vote) */
554 : fd_hash_t vote_block_id; /* block ID to vote for */
555 : fd_hash_t vote_bank_hash; /* bank hash to vote for */
556 : fd_hash_t vote_block_hash; /* block hash (recent blockhash) to vote for */
557 : ulong root_slot; /* new tower root slot (ULONG_MAX if no new root) */
558 : fd_hash_t root_block_id; /* new tower root block ID */
559 : };
560 : typedef struct fd_tower_out fd_tower_out_t;
561 :
562 0 : #define FD_TOWER_CSTR_MIN (917UL) /* worst-case tower with 31 entries and 20-digit (the max width of a `ulong`) slots */
563 :
564 : void
565 : fd_tower_count_vote( fd_tower_t * tower,
566 : fd_pubkey_t const * vote_acc,
567 : ulong stake,
568 : uchar const * data,
569 : ulong data_sz );
570 :
571 : /* fd_tower_vote_and_reset selects both a block to vote for and block to
572 : reset to. Returns flags (FD_TOWER_FLAG_{...}) and writes results to
573 : out-pointers for {reset,vote,root}_{slot,block_id}.
574 :
575 : We can't always vote, so vote_slot may be ULONG_MAX which indicates
576 : no vote should be cast and caller should ignore vote_block_id. New
577 : roots result from votes, so the same applies for root_slot (there is
578 : not always a new root). However there is always a reset block, so
579 : reset_slot and reset_block_id will always be populated on return. The
580 : implementation contains detailed documentation of the tower rules. */
581 :
582 : uchar
583 : fd_tower_vote_and_reset( fd_tower_t * tower,
584 : fd_ghost_t * ghost,
585 : fd_votes_t * votes,
586 : ulong * reset_slot,
587 : fd_hash_t * reset_block_id,
588 : ulong * vote_slot,
589 : fd_hash_t * vote_block_id,
590 : fd_hash_t * vote_bank_hash,
591 : fd_hash_t * vote_block_hash,
592 : ulong * root_slot,
593 : fd_hash_t * root_block_id );
594 :
595 : /* Misc */
596 :
597 : /* fd_tower_reconcile reconciles our local tower with the on-chain tower
598 : inside our vote account. Mirrors what Agave does. Also updates
599 : block vote metadata to match the updated tower. */
600 :
601 : void
602 : fd_tower_reconcile( fd_tower_t * tower,
603 : fd_tower_vote_t * onchain_votes,
604 : ulong onchain_root );
605 :
606 : /* fd_tower_blocks_{query,insert,remove} provide convenient wrappers for
607 : {querying,inserting,removing} blocks into the tower's block map. */
608 :
609 : fd_tower_blk_t *
610 : fd_tower_blocks_query( fd_tower_t * tower,
611 : ulong slot );
612 :
613 : fd_tower_blk_t *
614 : fd_tower_blocks_insert( fd_tower_t * tower,
615 : ulong slot,
616 : ulong parent_slot );
617 :
618 : void
619 : fd_tower_blocks_remove( fd_tower_t * tower,
620 : ulong slot );
621 :
622 : int
623 : fd_tower_blocks_is_slot_ancestor( fd_tower_t * tower,
624 : ulong descendant_slot,
625 : ulong ancestor_slot );
626 :
627 : int
628 : fd_tower_blocks_is_slot_descendant( fd_tower_t * tower,
629 : ulong ancestor_slot,
630 : ulong descendant_slot );
631 :
632 : ulong
633 : fd_tower_blocks_lowest_common_ancestor( fd_tower_t * tower,
634 : ulong slot1,
635 : ulong slot2 );
636 :
637 : fd_hash_t const *
638 : fd_tower_blocks_canonical_block_id( fd_tower_t * tower,
639 : ulong slot );
640 :
641 : /* fd_tower_from_vote_acc deserializes the vote account into a votes
642 : deque and extracts the root. Assumes votes is a valid joined deque
643 : and currently empty. On return *root is the tower root slot, or
644 : ULONG_MAX if the vote account has no root. */
645 :
646 : void
647 : fd_tower_from_vote_acc( fd_tower_vote_t * votes,
648 : ulong * root,
649 : uchar const * data,
650 : ulong data_sz );
651 :
652 : /* fd_tower_with_lat_from_vote_acc deserializes the vote account into
653 : tower, including slot latency (when available) for tower votes.
654 : Assumes tower points to a static array of length FD_TOWER_VOTE_MAX.
655 :
656 : Returns the number of copied elements. */
657 :
658 : ulong
659 : fd_tower_with_lat_from_vote_acc( fd_vote_acc_vote_t tower[ static FD_TOWER_VOTE_MAX ],
660 : uchar const * data,
661 : ulong data_sz );
662 :
663 : /* fd_tower_to_vote_txn writes tower into a fd_tower_sync_t vote
664 : instruction and serializes it into a Solana transaction. Assumes
665 : tower is a valid local join. */
666 :
667 : void
668 : fd_tower_to_vote_txn( fd_tower_t const * tower,
669 : fd_hash_t const * bank_hash,
670 : fd_hash_t const * block_id,
671 : fd_hash_t const * recent_blockhash,
672 : fd_pubkey_t const * validator_identity,
673 : fd_pubkey_t const * vote_authority,
674 : fd_pubkey_t const * vote_account,
675 : fd_txn_p_t * vote_txn );
676 :
677 : /* fd_tower_verify checks tower is in a valid state. Valid iff:
678 : - cnt < FD_TOWER_VOTE_MAX
679 : - vote slots and confirmation counts in the tower are monotonically
680 : increasing */
681 :
682 : int
683 : fd_tower_verify( fd_tower_t const * tower );
684 :
685 : /* fd_tower_to_cstr pretty-prints tower as a formatted table to the
686 : buffer cstr. Assumes cstr is a buffer of at least FD_TOWER_CSTR_MIN
687 : capacity.
688 :
689 : Sample output:
690 :
691 : slot | confirmation count
692 : --------- | ------------------
693 : 279803931 | 1
694 : 279803930 | 2
695 : ...
696 : 279803901 | 31
697 : 279803900 | root
698 : */
699 :
700 : char *
701 : fd_tower_to_cstr( fd_tower_t const * tower,
702 : char * cstr );
703 :
704 : /* fd_tower_lockos API. Lockout intervals are stored inline in the
705 : tower (lck_pool and lck_map). */
706 :
707 : void
708 : fd_tower_lockos_insert( fd_tower_t * tower,
709 : ulong slot,
710 : fd_hash_t const * vote_acc,
711 : fd_tower_vote_t * votes );
712 :
713 : void
714 : fd_tower_lockos_remove( fd_tower_t * tower,
715 : ulong slot );
716 :
717 : #endif /* HEADER_fd_src_choreo_tower_fd_tower_h */
|
