Line data Source code
1 : #ifndef HEADER_fd_src_choreo_ghost_fd_ghost_h
2 : #define HEADER_fd_src_choreo_ghost_fd_ghost_h
3 :
4 : /* fd_ghost implements Solana's LMD-GHOST ("latest message-driven greedy
5 : heaviest-observed subtree") fork choice rule.
6 :
7 : Protocol details:
8 :
9 : - LMD is an acronym for "latest message-driven". It denotes the
10 : specific flavor of GHOST implementation, ie. only a
11 : validator's latest vote counts.
12 :
13 : - GHOST is an acronym for "greedy heaviest-observed subtree":
14 : - greedy: pick the locally optimal subtree / fork based on our
15 : current view (which may not be globally optimal).
16 : - heaviest: pick based on the highest stake weight.
17 : - observed: this is the validator's local view, and other
18 : validators may have differing views.
19 : - subtree: pick a subtree, not an individual node.
20 :
21 : In-memory representation:
22 :
23 : - Each tree node is keyed by slot number.
24 :
25 : - Each tree node tracks the amount of stake (`stake`) that has voted
26 : for its slot, as well as the recursive sum of stake for the subtree
27 : rooted at that node (`weight`).
28 :
29 : Link to original GHOST paper: https://eprint.iacr.org/2013/881.pdf.
30 : This is simply a reference for those curious about the etymology, and
31 : not prerequisite reading for understanding this implementation. */
32 :
33 : #include "../fd_choreo_base.h"
34 :
35 : /* FD_GHOST_USE_HANDHOLDING: Define this to non-zero at compile time
36 : to turn on additional runtime checks and logging. */
37 :
38 : #ifndef FD_GHOST_USE_HANDHOLDING
39 : #define FD_GHOST_USE_HANDHOLDING 1
40 : #endif
41 :
42 : /* clang-format off */
43 :
44 : /* fd_ghost_node_t implements a left-child, right-sibling n-ary tree.
45 : Each node maintains pointers to its left-most child, its
46 : immediate-right sibling, and its parent. */
47 :
48 : typedef struct fd_ghost_node fd_ghost_node_t;
49 : struct __attribute__((aligned(128UL))) fd_ghost_node {
50 : ulong slot; /* slot this node is tracking, also the map key */
51 : ulong next; /* reserved for internal use by fd_pool and fd_map_chain */
52 : ulong weight; /* amount of stake (in lamports) that has voted for this slot or any of its descendants */
53 : ulong stake; /* amount of stake (in lamports) that has voted for this slot */
54 : ulong gossip_stake; /* amount of stake (in lamports) that has voted for this slot via gossip (sans replay overlap) */
55 : ulong rooted_stake; /* amount of stake (in lamports) that has rooted this slot */
56 : int eqv; /* flag for equivocation (multiple blocks) in this slot */
57 : fd_ghost_node_t * parent; /* pointer to the parent */
58 : fd_ghost_node_t * child; /* pointer to the left-most child */
59 : fd_ghost_node_t * sibling; /* pointer to next sibling */
60 : };
61 :
62 : #define FD_GHOST_EQV_SAFE ( 0.52 )
63 : #define FD_GHOST_OPT_CONF ( 2.0 / 3.0 )
64 :
65 : #define POOL_NAME fd_ghost_node_pool
66 0 : #define POOL_T fd_ghost_node_t
67 : #include "../../util/tmpl/fd_pool.c"
68 :
69 : #define MAP_NAME fd_ghost_node_map
70 : #define MAP_ELE_T fd_ghost_node_t
71 0 : #define MAP_KEY slot
72 : #include "../../util/tmpl/fd_map_chain.c"
73 :
74 : /* fd_ghost_vote_t represents a validator's vote. This includes the
75 : slot being voted for, the validator's pubkey identity, and the
76 : validator's stake. */
77 :
78 : struct fd_ghost_vote {
79 : fd_pubkey_t pubkey; /* validator identity, also the map key */
80 : ulong next; /* reserved for internal use by fd_pool and fd_map_chain */
81 : ulong slot; /* latest vote slot */
82 : ulong root; /* latest root slot */
83 : ulong stake; /* validator's stake */
84 : };
85 : typedef struct fd_ghost_vote fd_ghost_vote_t;
86 :
87 : #define POOL_NAME fd_ghost_vote_pool
88 0 : #define POOL_T fd_ghost_vote_t
89 : #include "../../util/tmpl/fd_pool.c"
90 :
91 : #define MAP_NAME fd_ghost_vote_map
92 : #define MAP_ELE_T fd_ghost_vote_t
93 0 : #define MAP_KEY pubkey
94 : #define MAP_KEY_T fd_pubkey_t
95 0 : #define MAP_KEY_EQ(k0,k1) (!(memcmp((k0)->hash,(k1)->hash,sizeof(fd_hash_t))))
96 0 : #define MAP_KEY_HASH(key,seed) (key->ui[0]^seed)
97 : #include "../../util/tmpl/fd_map_chain.c"
98 :
99 : /* fd_ghost_t is the top-level structure that holds the root of the
100 : tree, as well as the memory pools and map structures for tracking
101 : ghost nodes and votes.
102 :
103 : These structures are bump-allocated and laid out contiguously in
104 : memory from the fd_ghost_t * pointer which points to the beginning of
105 : the memory region.
106 :
107 : ---------------------- <--- fd_ghost_t *
108 : | root | total_stake |
109 : ----------------------
110 : | node_pool |
111 : ----------------------
112 : | node_map |
113 : ----------------------
114 : | vote_map |
115 : ----------------------
116 : */
117 :
118 : struct __attribute__((aligned(128UL))) fd_ghost {
119 :
120 : /* Metadata */
121 :
122 : fd_ghost_node_t * root;
123 : ulong total_stake;
124 :
125 : /* Inline data structures */
126 :
127 : fd_ghost_node_t * node_pool; /* memory pool of ghost nodes */
128 : fd_ghost_node_map_t * node_map; /* map of slot_hash->fd_ghost_node_t */
129 : fd_ghost_vote_t * vote_pool; /* memory pool of ghost votes */
130 : fd_ghost_vote_map_t * vote_map; /* each node's latest vote. map of pubkey->fd_ghost_vote_t */
131 : };
132 : typedef struct fd_ghost fd_ghost_t;
133 :
134 : FD_PROTOTYPES_BEGIN
135 :
136 : /* Constructors */
137 :
138 : /* fd_ghost_{align,footprint} return the required alignment and
139 : footprint of a memory region suitable for use as ghost with up to
140 : node_max nodes and vote_max votes. */
141 :
142 : FD_FN_CONST static inline ulong
143 0 : fd_ghost_align( void ) {
144 0 : return alignof(fd_ghost_t);
145 0 : }
146 :
147 : FD_FN_CONST static inline ulong
148 0 : fd_ghost_footprint( ulong node_max, ulong vote_max ) {
149 0 : return FD_LAYOUT_FINI(
150 0 : FD_LAYOUT_APPEND(
151 0 : FD_LAYOUT_APPEND(
152 0 : FD_LAYOUT_APPEND(
153 0 : FD_LAYOUT_APPEND(
154 0 : FD_LAYOUT_APPEND(
155 0 : FD_LAYOUT_INIT,
156 0 : alignof(fd_ghost_t), sizeof(fd_ghost_t) ),
157 0 : fd_ghost_node_pool_align(), fd_ghost_node_pool_footprint( node_max ) ),
158 0 : fd_ghost_node_map_align(), fd_ghost_node_map_footprint( node_max ) ),
159 0 : fd_ghost_vote_pool_align(), fd_ghost_vote_pool_footprint( vote_max ) ),
160 0 : fd_ghost_vote_map_align(), fd_ghost_vote_map_footprint( vote_max ) ),
161 0 : fd_ghost_align() );
162 0 : }
163 : /* clang-format on */
164 :
165 : /* fd_ghost_new formats an unused memory region for use as a ghost.
166 : mem is a non-NULL pointer to this region in the local address space
167 : with the required footprint and alignment. */
168 :
169 : void *
170 : fd_ghost_new( void * mem, ulong node_max, ulong vote_max, ulong seed );
171 :
172 : /* fd_ghost_join joins the caller to the ghost. ghost points to the
173 : first byte of the memory region backing the ghost in the caller's
174 : address space.
175 :
176 : Returns a pointer in the local address space to ghost on success. */
177 :
178 : fd_ghost_t *
179 : fd_ghost_join( void * ghost );
180 :
181 : /* fd_ghost_leave leaves a current local join. Returns a pointer to the
182 : underlying shared memory region on success and NULL on failure (logs
183 : details). Reasons for failure include ghost is NULL. */
184 :
185 : void *
186 : fd_ghost_leave( fd_ghost_t const * ghost );
187 :
188 : /* fd_ghost_delete unformats a memory region used as a ghost.
189 : Assumes only the nobody is joined to the region. Returns a
190 : pointer to the underlying shared memory region or NULL if used
191 : obviously in error (e.g. ghost is obviously not a ghost ... logs
192 : details). The ownership of the memory region is transferred to the
193 : caller. */
194 :
195 : void *
196 : fd_ghost_delete( void * ghost );
197 :
198 : /* fd_ghost_init initializes a ghost. Assumes ghost is a valid local
199 : join and no one else is joined. root is the initial root ghost will
200 : use. This is the snapshot slot if booting from a snapshot, 0 if the
201 : genesis slot.
202 :
203 : In general, this should be called by the same process that formatted
204 : ghost's memory, ie. the caller of fd_ghost_new. */
205 :
206 : void
207 : fd_ghost_init( fd_ghost_t * ghost, ulong root, ulong total_stake );
208 :
209 : /* Accessors */
210 :
211 : FD_FN_PURE static inline fd_ghost_node_t const *
212 0 : fd_ghost_query( fd_ghost_t const * ghost, ulong slot ) {
213 0 : return fd_ghost_node_map_ele_query_const( ghost->node_map, &slot, NULL, ghost->node_pool );
214 0 : }
215 :
216 : /* Operations */
217 :
218 : /* fd_ghost_node_insert inserts a new node with slot as the key into the
219 : ghost. Assumes slot >= ghost->smr, slot is not already in ghost,
220 : parent_slot is already in ghost, and the node pool has a free element
221 : (if handholding is enabled, explicitly checks and errors). Returns
222 : the inserted ghost node. */
223 :
224 : fd_ghost_node_t *
225 : fd_ghost_insert( fd_ghost_t * ghost, ulong slot, ulong parent_slot );
226 :
227 : /* fd_ghost_replay_vote votes for slot, adding pubkey's stake to the
228 : `replay_stake` field for slot and to the `weight` field for both slot
229 : and slot's ancestors. If pubkey has previously voted, pubkey's stake
230 : is also subtracted from `weight` for its previous vote slot and its
231 : ancestors.
232 :
233 : Assumes slot is present in ghost (if handholding is enabled,
234 : explicitly checks and errors). Returns the ghost node keyed by slot.
235 :
236 : TODO the implementation can be made more efficient by
237 : short-circuiting and doing fewer traversals. Currently this is
238 : bounded to O(h), where h is the height of ghost. */
239 :
240 : fd_ghost_node_t const *
241 : fd_ghost_replay_vote( fd_ghost_t * ghost, ulong slot, fd_pubkey_t const * pubkey, ulong stake );
242 :
243 : /* fd_ghost_gossip_vote adds stake amount to the gossip_stake field of
244 : slot.
245 :
246 : Assumes slot is present in ghost (if handholding is enabled,
247 : explicitly checks and errors). Returns the ghost node keyed by slot.
248 :
249 : Unlike fd_ghost_replay_vote, this stake is not propagated to
250 : the weight field for slot and slot's ancestors. It is only counted
251 : towards slot itself, as gossip votes are only used for optimistic
252 : confirmation and not fork choice. */
253 :
254 : fd_ghost_node_t const *
255 : fd_ghost_gossip_vote( fd_ghost_t * ghost, ulong slot, fd_pubkey_t const * pubkey, ulong stake );
256 :
257 : /* fd_ghost_rooted_vote adds stake amount to the rooted_stake field of
258 : slot.
259 :
260 : Assumes slot is present in ghost (if handholding is enabled,
261 : explicitly checks and errors). Returns the ghost node keyed by slot.
262 :
263 : Note rooting a slot implies rooting its ancestor, but ghost does not
264 : explicitly track this. */
265 :
266 : fd_ghost_node_t const *
267 : fd_ghost_rooted_vote( fd_ghost_t * ghost, ulong slot, fd_pubkey_t const * pubkey, ulong stake );
268 :
269 : /* fd_ghost_publish publishes slot as the new ghost root, setting the
270 : subtree beginning from slot as the new ghost tree (ie. slot and all
271 : its descendants). Prunes all nodes not in slot's ancestry. Assumes
272 : slot is present in ghost. Returns the new root. */
273 :
274 : fd_ghost_node_t const *
275 : fd_ghost_publish( fd_ghost_t * ghost, ulong slot );
276 :
277 : /* Traversals */
278 :
279 : /* fd_ghost_gca returns the greatest common ancestor of slot1, slot2 in
280 : ghost. Assumes slot1 or slot2 are present in ghost (warns and
281 : returns NULL with handholding enabled). This is guaranteed to be
282 : non-NULL if slot1 and slot2 are both present. */
283 :
284 : FD_FN_PURE fd_ghost_node_t const *
285 : fd_ghost_gca( fd_ghost_t const * ghost, ulong slot1, ulong slot2 );
286 :
287 : /* fd_ghost_head returns ghost's head. Assumes caller has called
288 : fd_ghost_init and that the ghost is non-empty, ie. has a root. */
289 :
290 : FD_FN_PURE fd_ghost_node_t const *
291 : fd_ghost_head( fd_ghost_t const * ghost );
292 :
293 : /* fd_ghost_is_descendant returns 1 if slot descends from ancestor_slot,
294 : 0 otherwise. Assumes slot is present in ghost (warns and returns 0
295 : early if handholding is on). Does not assume the same of
296 : ancestor_slot. */
297 :
298 : FD_FN_PURE int
299 : fd_ghost_is_descendant( fd_ghost_t const * ghost, ulong slot, ulong ancestor_slot );
300 :
301 : /* Misc */
302 :
303 : /* fd_ghost_slot_print pretty-prints a formatted ghost tree. slot
304 : controls which slot to begin printing from (will appear as the root
305 : in the print output). depth allows caller to specify additional
306 : ancestors to walk back from slot to set as the root.
307 :
308 : ghost->root->slot and 0 are valid defaults for the above,
309 : respectively. In that case, this would print ghost beginning from
310 : the root. See fd_ghost_print.
311 :
312 : Typical usage is to pass in the most recently executed slot, in which
313 : that slot in a leaf in ghost, and pick an appropriate depth for
314 : visualization (20 is a reasonable default). */
315 :
316 : void
317 : fd_ghost_slot_print( fd_ghost_t * ghost, ulong slot, ulong depth );
318 :
319 : /* fd_ghost_print pretty-prints a formatted ghost tree starting from the
320 : root using fd_ghost_slot_print. */
321 :
322 : static inline void
323 0 : fd_ghost_print( fd_ghost_t * ghost ) {
324 0 : fd_ghost_slot_print( ghost, ghost->root->slot, 0 );
325 0 : }
326 :
327 : FD_PROTOTYPES_END
328 :
329 : #endif /* HEADER_fd_src_choreo_ghost_fd_ghost_h */
|
