Line data Source code
1 : #ifndef HEADER_fd_src_discof_repair_fd_repair_h
2 : #define HEADER_fd_src_discof_repair_fd_repair_h
3 :
4 : /* fd_repair implements the Solana Repair protocol. In a nutshell,
5 : Repair is a protocol for recovering shreds that the validator is
6 : expecting but has not received from Turbine. Neither the logic for
7 : how the validator determines it should be expecting a shred nor the
8 : logic for determining which peer validator to request the shred from
9 : is implemented in this file (see fd_policy.h instead); rather, this
10 : is an implementation of the protocol itself for requesting shreds
11 : from other validators.
12 :
13 : The repair protocol supports seven different message types on the
14 : client side:
15 :
16 : - Pong( ping_token )
17 :
18 : This is a response message to address validation via a Ping-Pong
19 : protocol. When a validator receives a repair request from another
20 : validator it does not recognize, it will ignore the request and
21 : instead respond with its own Ping message to the requesting
22 : validator. The Ping contains a 32-byte token that the requesting
23 : validator needs to hash and sign as part of a Pong response. The
24 : scheme is as follows: the Ping token is concatenated with the
25 : prefix "SOLANA_PING_PONG", which is then piped in as the preimage
26 : into SHA-256. The resulting hash is then signed and the signature
27 : along with the actual hash is packed into a Pong.
28 :
29 : - Shred( slot, shred_idx )
30 :
31 : This is a request for a specific shred in the provided slot. The
32 : (slot, shred index) generally uniquely identifies a shred except in
33 : certain exceptional conditions (equivocation). The responding
34 : validator will return the shred if it has it.
35 :
36 : - HighestShred( slot, shred_idx )
37 :
38 : This is a request for the highest shred in the provided slot that
39 : is greater than or equal to shred_idx, or a lower shred marked as
40 : the last shred in the slot. Note this is not necessarily the last
41 : shred in the slot, as it depends on what the responding validator
42 : has available. The responding validator will return the highest
43 : shred it has that meets the condition.
44 :
45 : - Orphan( slot )
46 :
47 : This is a request for up to 11 shreds, where each shred is the
48 : prior one's ancestor, beginning from and including slot. For
49 : example, an orphan request for slot 10 will return the highest
50 : shred for slots 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 and 0 (assuming
51 : no skips).
52 :
53 : The below are repair request types introduced by Alpenglow.
54 :
55 : - ParentAndFecSetCount( slot, block_id )
56 :
57 : This is a request for the parent slot and FEC set count for the
58 : provided block_id. The responding validator will return the
59 : parent slot and FEC set count it has for the provided block_id.
60 :
61 : - FecSetRoot( slot, block_id, fec_set_idx )
62 :
63 : This is a request for the FEC set root for the provided block_id
64 : and FEC set index. The responding validator will return the FEC
65 : set root it has for the provided block_id and FEC set index.
66 :
67 : - ShredForBlockId( slot, shred_idx, block_id )
68 :
69 : This is a request for the shred at the provided slot, shred index
70 : and block_id. The responding validator will return the shred it
71 : has for the provided slot, shred index and block_id.
72 :
73 : All 7 repair request types are prefixed with a common header of from
74 : pubkey, to pubkey, ulong timestamp and uint nonce. The timestamp is
75 : a standard UNIX epoch (milliseconds since 1970-01-01T00:00:00Z) and
76 : the nonce is echoed back by the responding validator in the repair
77 : response. Unlike a typical cryptographic nonce that prevents replay
78 : attacks, the repair server implementation ignores the nonce and this
79 : implementation leaves it up to the calling application to manage the
80 : nonce. Note the 4 nonce bytes are appended after the end of a shred
81 : in a repair response.
82 :
83 : All communication across the wire is done with bincode serialization
84 : encoding. */
85 :
86 : #include "../../ballet/ed25519/fd_ed25519.h"
87 : #include "../../flamenco/fd_flamenco_base.h"
88 : #include "../../ballet/shred/fd_shred.h"
89 : #include "../../disco/shred/fd_fec_set.h"
90 :
91 : /* FD_REPAIR_KIND_{PONG,SHRED,HIGHEST_SHRED,ORPHAN,ANCESTOR_HASHES} specify
92 : discriminant values the protocol uses to distinguish message types. */
93 :
94 0 : #define FD_REPAIR_KIND_PING (0U)
95 : #define AG_REPAIR_KIND_PING (2U)
96 :
97 33 : #define FD_REPAIR_KIND_PONG (7U)
98 23772 : #define FD_REPAIR_KIND_SHRED (8U)
99 6519 : #define FD_REPAIR_KIND_HIGHEST_SHRED (9U)
100 6336 : #define FD_REPAIR_KIND_ORPHAN (10U)
101 0 : #define FD_REPAIR_KIND_ANCESTOR_HASHES (11U)
102 6951 : #define AG_REPAIR_KIND_PARENT_FEC_COUNT (12U)
103 7014 : #define AG_REPAIR_KIND_FEC_ROOT (13U)
104 16725 : #define AG_REPAIR_KIND_SHRED_FOR_BLOCK_ID (14U)
105 :
106 : /* fd_repair_pong describes the schema of a Pong. */
107 :
108 : struct __attribute__((packed)) fd_repair_pong {
109 : fd_pubkey_t from; /* pubkey of the validator responding with the pong */
110 : fd_hash_t hash; /* sha-256 hash generated from a ping hash */
111 : fd_ed25519_sig_t sig; /* from's signature over the preceding hash field */
112 : };
113 : typedef struct fd_repair_pong fd_repair_pong_t;
114 :
115 : /* REQ_HDR defines the common header of Repair request types. */
116 :
117 : #define REQ_HDR \
118 : fd_ed25519_sig_t sig; /* ed25519 signature over all the subsequent fields */ \
119 : fd_pubkey_t from; /* pubkey of the validator that sent the request */ \
120 : fd_pubkey_t to; /* pubkey of the validator that is being requested */ \
121 : ulong ts; /* timestamp in milliseconds since unix epoch */ \
122 : uint nonce; /* nonce to be echoed back by the responding validator */ \
123 :
124 : /* fd_repair_shred requests the specific shred at slot and shred_idx
125 : from a peer validator. */
126 :
127 : /* TODO: remove _req suffix from below */
128 : struct __attribute__((packed)) fd_repair_shred_req {
129 : REQ_HDR
130 : ulong slot;
131 : ulong shred_idx;
132 : };
133 : typedef struct fd_repair_shred_req fd_repair_shred_req_t;
134 :
135 : /* fd_repair_highest_shred requests the highest shred in slot greater
136 : than shred_idx that a peer validator has. Note this is not
137 : necessarily the last shred in the slot, as it depends on what the
138 : peer has available. */
139 :
140 : struct __attribute__((packed)) fd_repair_highest_shred_req {
141 : REQ_HDR
142 : ulong slot;
143 : ulong shred_idx;
144 : };
145 : typedef struct fd_repair_highest_shred_req fd_repair_highest_shred_req_t;
146 :
147 : /* fd_repair_orphan requests the ancestors of slot (an "orphaned" slot)
148 : from a peer validator. The peer can respond with shreds for up to 11
149 : slots (including the requested slot itself), where every shred is
150 : the highest shred for that slot. */
151 :
152 : struct __attribute__((packed)) fd_repair_orphan_req {
153 : REQ_HDR
154 : ulong slot;
155 : };
156 : typedef struct fd_repair_orphan_req fd_repair_orphan_req_t;
157 :
158 : struct __attribute__((packed)) ag_repair_parent_fec_count_req {
159 : REQ_HDR
160 : ulong slot;
161 : fd_hash_t block_id;
162 : };
163 : typedef struct ag_repair_parent_fec_count_req ag_repair_parent_fec_count_req_t;
164 :
165 : struct __attribute__((packed)) ag_repair_fec_root_req {
166 : REQ_HDR
167 : ulong slot;
168 : fd_hash_t block_id;
169 : uint fec_set_idx;
170 : };
171 : typedef struct ag_repair_fec_root_req ag_repair_fec_root_req_t;
172 :
173 : struct __attribute__((packed)) ag_repair_shred_block_id_req {
174 : REQ_HDR
175 : ulong slot;
176 : uint shred_idx;
177 : fd_hash_t block_id;
178 : };
179 : typedef struct ag_repair_shred_block_id_req ag_repair_shred_block_id_req_t;
180 :
181 : /* fd_repair_req_header gives a view into the header of the SHRED,
182 : HIGHEST_SHRED, and ORPHAN request types. */
183 : struct __attribute__((packed)) fd_repair_req_header {
184 : REQ_HDR
185 : };
186 : typedef struct fd_repair_req_header fd_repair_req_header_t;
187 :
188 : /* fd_repair_msg_t defines the schema of all Repair message types. */
189 :
190 : struct __attribute__((packed)) fd_repair_msg {
191 : uint kind; /* FD_REPAIR_KIND_{...} */
192 : union {
193 : fd_repair_pong_t pong;
194 : fd_repair_shred_req_t shred;
195 : fd_repair_highest_shred_req_t highest_shred;
196 : fd_repair_orphan_req_t orphan;
197 : fd_repair_req_header_t header;
198 :
199 : ag_repair_parent_fec_count_req_t parent_fec_set_count;
200 : ag_repair_fec_root_req_t fec_set_root;
201 : ag_repair_shred_block_id_req_t shred_block_id;
202 : };
203 : };
204 : typedef struct fd_repair_msg fd_repair_msg_t;
205 :
206 : struct __attribute__((packed)) fd_repair_ping {
207 : uint kind;
208 : fd_repair_pong_t ping;
209 : };
210 : typedef struct fd_repair_ping fd_repair_ping_t;
211 :
212 : /* alpenglow blockid repair response types */
213 :
214 : typedef uchar ag_proof_node_t[FD_SHRED_MERKLE_NODE_SZ];
215 : #define AG_MAX_FEC_PROOF_NODE_CNT (1U + (63 - __builtin_clzl( FD_SHRED_BLK_MAX_RAISED/FD_FEC_SHRED_CNT ))) /* 24 = 1 node for parent block_id + 23 for log2 of the most FEC sets any configuration allows */
216 :
217 : struct ag_parent_fec_count_res {
218 : uint fec_set_count;
219 : ulong parent_slot;
220 : fd_hash_t parent_block_id;
221 : ulong proof_len; /* number of proof nodes in parent_proof */
222 : ag_proof_node_t parent_proof[ AG_MAX_FEC_PROOF_NODE_CNT ]; /* variable-length */
223 : };
224 : typedef struct ag_parent_fec_count_res ag_parent_fec_count_res_t;
225 : struct ag_fec_root_res {
226 : ag_proof_node_t root; /* 20-byte FEC-set merkle root prefix */
227 : ulong proof_len; /* number of proof nodes in fec_proof */
228 : ag_proof_node_t fec_proof[ AG_MAX_FEC_PROOF_NODE_CNT ]; /* variable-length */
229 : };
230 : typedef struct ag_fec_root_res ag_fec_root_res_t;
231 :
232 90 : #define AG_REPAIR_RESPONSE_PARENT_FEC_SET_COUNT (0U)
233 186 : #define AG_REPAIR_RESPONSE_FEC_SET_ROOT (1U)
234 : struct ag_repair_response {
235 : uint kind;
236 : union {
237 : ag_parent_fec_count_res_t parent_fec_set_res;
238 : ag_fec_root_res_t fec_set_root;
239 : };
240 : uint nonce;
241 : };
242 : typedef struct ag_repair_response ag_repair_response_t;
243 :
244 : /* Max payload size of a blockid repair response */
245 : #define AG_REPAIR_RESPONSE_MAX_SZ (sizeof(ag_repair_response_t))
246 :
247 : /* FD_REPAIR_PONG_PREIMAGE_PREFIX is used by Repair's Ping-Pong protocol.
248 : Both a Ping and Pong contain a hash token, that is generated from a
249 : preimage prefixed with the below. */
250 :
251 0 : #define FD_REPAIR_PONG_PREIMAGE_PREFIX "SOLANA_PING_PONG"
252 0 : #define FD_REPAIR_PONG_PREIMAGE_SZ (48UL)
253 :
254 : /* FD_REPAIR_MAX_PREIMAGE_SZ is the maximum size of a preimage for a
255 : repair request. This is the size of the largest repair request
256 : (highest_shred or shred) without the signature. */
257 :
258 0 : #define FD_REPAIR_MAX_PREIMAGE_SZ (sizeof(fd_repair_msg_t) - sizeof(fd_ed25519_sig_t))
259 :
260 : static const fd_pubkey_t null_pubkey = {{ 0 }};
261 :
262 : /* fd_repair_sign_fn defines the function signature for a user-provided
263 : signing callback. */
264 :
265 : typedef void (fd_repair_sign_fn)( void * ctx, fd_repair_msg_t * msg, uchar * sig );
266 :
267 : struct fd_repair {
268 : fd_pubkey_t identity_key; /* validator identity key */
269 : fd_repair_sign_fn * sign_fn; /* user-provided signing callback */
270 : void * sign_ctx; /* user-provided context for signing callback */
271 : fd_repair_msg_t msg; /* buffer for outgoing repair requests */
272 : };
273 : typedef struct fd_repair fd_repair_t;
274 :
275 : /* Constructors */
276 :
277 : /* fd_repair_{align,footprint} return the required alignment and
278 : footprint of a memory region suitable for use as repair. Declaration
279 : friendly (e.g. a memory region declared as "fd_repair_t repair[1];"
280 : will automatically have the needed alignment and footprint). */
281 :
282 : FD_FN_CONST static inline ulong
283 135 : fd_repair_align( void ) {
284 135 : return alignof(fd_repair_t);
285 135 : }
286 :
287 : FD_FN_CONST static inline ulong
288 90 : fd_repair_footprint( void ) {
289 90 : return sizeof(fd_repair_t);
290 90 : }
291 :
292 : /* fd_repair_new formats an unused memory region for use as a repair.
293 : mem is a non-NULL pointer to this region in the local address space
294 : with the required footprint and alignment.
295 : Initializes repair with the public identity key. */
296 :
297 : void *
298 : fd_repair_new( void * shmem, fd_pubkey_t * identity_key );
299 :
300 : /* fd_repair_join joins the caller to the repair. repair points to the
301 : first byte of the memory region backing the repair in the caller's
302 : address space. Returns a pointer in the local address space to
303 : repair on success. */
304 :
305 : fd_repair_t *
306 : fd_repair_join( void * repair );
307 :
308 : /* fd_repair_leave leaves a current local join. Returns a pointer to
309 : the underlying shared memory region on success and NULL on failure
310 : (logs details). Reasons for failure include repair is NULL. */
311 :
312 : void *
313 : fd_repair_leave( fd_repair_t const * repair );
314 :
315 : /* fd_repair_delete unformats a memory region used as a repair. Assumes
316 : only the nobody is joined to the region. Returns a pointer to the
317 : underlying shared memory region or NULL if used obviously in error
318 : (e.g. repair is obviously not a repair ... logs details). The
319 : ownership of the memory region is transferred to the caller. */
320 :
321 : void *
322 : fd_repair_delete( void * repair );
323 :
324 : /* fd_repair_ping_de and fd_repair_ping_ser deserialize and serialize a
325 : ping message. */
326 : int
327 : fd_repair_ping_de( fd_repair_ping_t * ping,
328 : uchar const * buf,
329 : ulong buf_sz );
330 :
331 : int
332 : fd_repair_ping_ser( fd_repair_ping_t const * ping,
333 : uchar buf[static sizeof(fd_repair_ping_t)],
334 : ulong buf_sz );
335 :
336 : /* fd_repair_{pong,shred,highest_shred,orphan} creates and returns a
337 : pointer to a serialized {Pong,Shred,HighestShred,Orphan} message.
338 : Does not require the caller to provide memory, as Repair itself
339 : maintains a dedicated memory region (repair->msg) for buffering
340 : requests. Assumes repair->msg is not already buffering an existing
341 : request and can be overwritten. Returns a pointer to repair->msg,
342 : cannot fail. */
343 :
344 : fd_repair_msg_t * fd_repair_pong ( fd_repair_t * repair, fd_hash_t * ping_token );
345 : fd_repair_msg_t * fd_repair_shred ( fd_repair_t * repair, fd_pubkey_t const * to, ulong ts, uint nonce, ulong slot, ulong shred_idx );
346 : fd_repair_msg_t * fd_repair_highest_shred( fd_repair_t * repair, fd_pubkey_t const * to, ulong ts, uint nonce, ulong slot, ulong shred_idx );
347 : fd_repair_msg_t * fd_repair_orphan ( fd_repair_t * repair, fd_pubkey_t const * to, ulong ts, uint nonce, ulong slot );
348 :
349 : fd_repair_msg_t *
350 : ag_repair_parent_and_fec_set_count( fd_repair_t * repair, fd_pubkey_t const * to, ulong ts, uint nonce, ulong slot, fd_hash_t const * block_id );
351 :
352 : fd_repair_msg_t *
353 : ag_repair_fec_set_root( fd_repair_t * repair, fd_pubkey_t const * to, ulong ts, uint nonce, ulong slot, fd_hash_t const * block_id, uint fec_set_idx );
354 :
355 : fd_repair_msg_t *
356 : ag_repair_shred_block_id( fd_repair_t * repair, fd_pubkey_t const * to, ulong ts, uint nonce, ulong slot, fd_hash_t const * block_id, uint shred_idx );
357 :
358 : /* ag_repair_response_de deserializes a general Alpenglow repair metadata
359 : response from buf into response.
360 :
361 : u32 tag: 0=ParentFecSetCount, 1=FecSetRoot
362 : tag 0: u32 fec_set_count, u64 parent_slot, u8[32] parent_block_id,
363 : u64 proof_sz, u8[proof_sz] proof
364 : tag 1: u8[32] fec_set_root, u64 proof_sz, u8[proof_sz] proof
365 : u32 nonce
366 :
367 : Proofs are a concatenation of 20-byte merkle nodes (proof_sz must be
368 : a multiple of FD_SHRED_MERKLE_NODE_SZ). Ping responses (tag 2) are
369 : not handled here; they are the same sz as legacy repair pings and
370 : should be routed to the ping path. fec_set_max bounds the FEC sets
371 : a block may hold (max_shreds_per_block/FD_FEC_SHRED_CNT). Returns 0
372 : on success and -1 if the response is malformed.
373 : Does NOT verify the merkle proofs. */
374 : int
375 : ag_repair_response_de( ag_repair_response_t * response,
376 : uchar const * buf,
377 : ulong buf_sz,
378 : ulong fec_set_max );
379 :
380 : /* ag_repair_parent_fec_count_verify / ag_repair_fec_set_root_verify
381 : verifies a deserialized Alpenglow repair metadata response against
382 : the block id (double-merkle root) the request was made for. Both
383 : return 0 if the response's merkle proof is valid for block_id, -1
384 : otherwise. */
385 : int
386 : ag_repair_parent_fec_count_verify( ag_parent_fec_count_res_t const * res,
387 : fd_hash_t const * block_id );
388 : int
389 : ag_repair_fec_set_root_verify( ag_fec_root_res_t const * res,
390 : fd_hash_t const * block_id,
391 : uint fec_set_idx );
392 :
393 : /* fd_repair_sz returns the bincode-serialized sz of msg. */
394 :
395 : static inline ulong
396 4302 : fd_repair_sz( fd_repair_msg_t const * msg ) {
397 4302 : switch( msg->kind ) {
398 0 : case FD_REPAIR_KIND_PONG: return sizeof(uint) + sizeof(fd_repair_pong_t);
399 72 : case FD_REPAIR_KIND_SHRED: return sizeof(uint) + sizeof(fd_repair_shred_req_t);
400 54 : case FD_REPAIR_KIND_HIGHEST_SHRED: return sizeof(uint) + sizeof(fd_repair_highest_shred_req_t);
401 0 : case FD_REPAIR_KIND_ORPHAN: return sizeof(uint) + sizeof(fd_repair_orphan_req_t);
402 120 : case AG_REPAIR_KIND_PARENT_FEC_COUNT: return sizeof(uint) + sizeof(ag_repair_parent_fec_count_req_t);
403 210 : case AG_REPAIR_KIND_FEC_ROOT: return sizeof(uint) + sizeof(ag_repair_fec_root_req_t);
404 3846 : case AG_REPAIR_KIND_SHRED_FOR_BLOCK_ID: return sizeof(uint) + sizeof(ag_repair_shred_block_id_req_t);
405 0 : default: FD_LOG_ERR(( "Unhandled repair kind %u", msg->kind ));
406 4302 : }
407 4302 : }
408 :
409 : /* preimage_pong creates the signing payload for a pong message. */
410 :
411 : static inline uchar *
412 : preimage_pong( fd_hash_t const * ping_token,
413 0 : uchar preimage_buf[ static FD_REPAIR_PONG_PREIMAGE_SZ ] ) {
414 0 : ulong prefix_sz = sizeof(FD_REPAIR_PONG_PREIMAGE_PREFIX) - 1 /* subtract NUL */;
415 0 : memcpy( preimage_buf, FD_REPAIR_PONG_PREIMAGE_PREFIX, prefix_sz );
416 0 : memcpy( preimage_buf + prefix_sz, ping_token, sizeof(fd_hash_t) );
417 0 : return preimage_buf;
418 0 : }
419 :
420 : /* preimage_req takes a repair request populated with all fields except
421 : for the signature, and returns a pointer to a preimage that can be
422 : signed. Modifies the msg in place.
423 :
424 : At the start of this function, the repair_msg_t should contain
425 :
426 : [ discriminant ] [ empty sig ] [ repair request fields ]
427 : ^ ^ ^
428 : 0 4 68
429 :
430 : https://github.com/solana-labs/solana/blob/master/core/src/repair/serve_repair.rs#L1258
431 :
432 : We want to sign over
433 : [ discriminant ] [ payload ]
434 : ^ ^
435 : buffer buffer+4
436 :
437 : We can do this without using any extra memory copying the discriminant
438 : to the last 4 bytes of the sig field, and returning a pointer to
439 : that copied location. The sig field should be overwritten with the
440 : actual signature value later, else the fd_repair_msg_t will be
441 : incorrect. */
442 :
443 : static inline uchar *
444 2151 : preimage_req( fd_repair_msg_t * msg, ulong * preimage_sz ) {
445 2151 : uchar * preimage = (uchar *)fd_type_pun(msg);
446 2151 : preimage += sizeof(fd_ed25519_sig_t);
447 2151 : FD_STORE( uint, preimage, msg->kind ); /* copy discriminant over */
448 2151 : *preimage_sz = fd_repair_sz( msg ) - sizeof(fd_ed25519_sig_t);
449 2151 : return preimage;
450 2151 : }
451 : #endif /* HEADER_fd_src_discof_repair_fd_repair_h */
|
