Line data Source code
1 : #ifndef HEADER_fd_src_choreo_eqvoc_fd_eqvoc_h
2 : #define HEADER_fd_src_choreo_eqvoc_fd_eqvoc_h
3 :
4 : #include "../../ballet/shred/fd_shred.h"
5 : #include "../../flamenco/leaders/fd_leaders.h"
6 : #include "../fd_choreo_base.h"
7 :
8 : /* fd_eqvoc presents an API for detecting and sending / receiving
9 : "proofs" of equivocation.
10 :
11 : Equivocation is when the shred producer produces two or more versions
12 : of a shred for the same (slot, idx). An equivocation proof comprises
13 : a sample of two shreds that conflict in a way that imply the shreds'
14 : producer equivocated.
15 :
16 : The proof can be both direct and indirect (implied). A direct proof
17 : is simpler: the proof is generated when you observe two versions of
18 : the same shred, ie. two shreds that have the same slot and shred_idx
19 : but a different data payload. Indirect
20 :
21 : The following lists the equivocation cases:
22 :
23 : 1. Two shreds with the same slot and idx but different data payloads.
24 : 2. Two shreds in the same FEC set have different merkle roots.
25 : 3. Two shreds in the same FEC set with different metadata ie.
26 : code_cnt, data_cnt, last_idx.
27 : 4. Two shreds in the same FEC set that are both data shreds, where
28 : one is marked as the last data shred in the slot, but the other
29 : shred has a higher data shred index than that.
30 : 3. Two shreds in different FEC sets and the FEC sets are overlapping
31 : ie. the same shred idx appears in both FEC sets.
32 :
33 : Every FEC set must have the same signature for every shred in the
34 : set, so a different signature would indicate equivocation. Note in
35 : the case of merkle shreds, the shred signature is signed on the FEC
36 : set's merkle root, so every shred in the same FEC set must have the
37 : same signature. */
38 :
39 : /* FD_EQVOC_USE_HANDHOLDING: Define this to non-zero at compile time
40 : to turn on additional runtime checks and logging. */
41 :
42 : #ifndef FD_EQVOC_USE_HANDHOLDING
43 : #define FD_EQVOC_USE_HANDHOLDING 1
44 : #endif
45 :
46 : #define FD_EQVOC_MAX ( 1UL << 10 )
47 0 : #define FD_EQVOC_FEC_MAX ( 67UL )
48 :
49 : /* This is the standard IPv6 MTU - IP / UDP headers - DuplicateShred application headers
50 : https://github.com/anza-xyz/agave/blob/v2.0.3/gossip/src/cluster_info.rs#L113 */
51 : #define FD_EQVOC_CHUNK_MAX ( 1232UL - 115UL )
52 :
53 : /* The chunk_cnt is encoded in a UCHAR_MAX, so you can have at most UCHAR_MAX chunkskj */
54 : #define FD_EQVOC_CHUNK_MIN ( FD_SHRED_MAX_SZ * 2 / UCHAR_MAX + 1 )
55 :
56 : struct fd_eqvoc_chunk {
57 : fd_slot_pubkey_t key;
58 : ulong next;
59 : fd_gossip_duplicate_shred_t duplicate_shred;
60 : };
61 : typedef struct fd_eqvoc_chunk fd_eqvoc_chunk_t;
62 :
63 : #define POOL_NAME fd_eqvoc_chunk_pool
64 : #define POOL_T fd_eqvoc_chunk_t
65 : #include "../../util/tmpl/fd_pool.c"
66 :
67 : /* clang-format off */
68 : #define MAP_NAME fd_eqvoc_chunk_map
69 : #define MAP_ELE_T fd_eqvoc_chunk_t
70 : #define MAP_KEY_T fd_slot_pubkey_t
71 : #define MAP_KEY_EQ(k0,k1) (FD_SLOT_PUBKEY_EQ(k0,k1))
72 : #define MAP_KEY_HASH(key,seed) (FD_SLOT_PUBKEY_HASH(key,seed))
73 : #include "../../util/tmpl/fd_map_chain.c"
74 :
75 :
76 : struct fd_eqvoc_key {
77 : ulong slot;
78 : uint fec_set_idx;
79 : };
80 : typedef struct fd_eqvoc_key fd_eqvoc_key_t;
81 :
82 : /* clang-format off */
83 : static const fd_eqvoc_key_t fd_eqvoc_key_null = { 0 };
84 : #define FD_EQVOC_KEY_NULL fd_eqvoc_key_null
85 : #define FD_EQVOC_KEY_INVAL(key) (!((key).slot) & !((key).fec_set_idx))
86 0 : #define FD_EQVOC_KEY_EQ(k0,k1) (!(((k0).slot) ^ ((k1).slot))) & !(((k0).fec_set_idx) ^ (((k1).fec_set_idx)))
87 0 : #define FD_EQVOC_KEY_HASH(key) ((uint)(((key).slot)<<15UL) | (((key).fec_set_idx)))
88 : /* clang-format on */
89 :
90 : struct fd_eqvoc_entry {
91 : fd_eqvoc_key_t key;
92 : ulong next;
93 : ulong code_cnt;
94 : ulong data_cnt;
95 : uint last_idx;
96 : fd_ed25519_sig_t sig;
97 : };
98 : typedef struct fd_eqvoc_entry fd_eqvoc_entry_t;
99 :
100 : #define POOL_NAME fd_eqvoc_pool
101 0 : #define POOL_T fd_eqvoc_entry_t
102 : #include "../../util/tmpl/fd_pool.c"
103 :
104 : /* clang-format off */
105 : #define MAP_NAME fd_eqvoc_map
106 : #define MAP_ELE_T fd_eqvoc_entry_t
107 : #define MAP_KEY_T fd_eqvoc_key_t
108 0 : #define MAP_KEY_EQ(k0,k1) (FD_EQVOC_KEY_EQ(*k0,*k1))
109 0 : #define MAP_KEY_HASH(key,seed) (FD_EQVOC_KEY_HASH(*key)^seed)
110 : #include "../../util/tmpl/fd_map_chain.c"
111 : /* clang-format on */
112 :
113 : typedef int (*fd_eqvoc_sig_verify_fn)( void * arg, fd_shred_t * shred );
114 :
115 : struct fd_eqvoc {
116 :
117 : /* primitives */
118 :
119 : ulong min_slot; /* min slot we're currently indexing. */
120 : ulong key_max; /* max # of FEC sets we can index. */
121 : ulong shred_version; /* shred version we expect in all shreds in eqvoc-related msgs. */
122 :
123 : /* owned */
124 :
125 : fd_eqvoc_map_t * map;
126 : fd_eqvoc_entry_t * pool;
127 : fd_sha512_t * sha512;
128 : void * bmtree_mem;
129 :
130 : /* borrowed */
131 : fd_epoch_leaders_t const * leaders;
132 :
133 : fd_eqvoc_sig_verify_fn sig_verify_fn;
134 : };
135 : typedef struct fd_eqvoc fd_eqvoc_t;
136 :
137 : /* clang-format off */
138 :
139 : /* fd_eqvoc_{align,footprint} return the required alignment and
140 : footprint of a memory region suitable for use as eqvoc with up to
141 : node_max nodes and vote_max votes. */
142 :
143 : FD_FN_CONST static inline ulong
144 0 : fd_eqvoc_align( void ) {
145 0 : return alignof(fd_eqvoc_t);
146 0 : }
147 :
148 : FD_FN_CONST static inline ulong
149 0 : fd_eqvoc_footprint( ulong key_max ) {
150 0 : return FD_LAYOUT_FINI(
151 0 : FD_LAYOUT_APPEND(
152 0 : FD_LAYOUT_APPEND(
153 0 : FD_LAYOUT_APPEND(
154 0 : FD_LAYOUT_APPEND(
155 0 : FD_LAYOUT_APPEND(
156 0 : FD_LAYOUT_APPEND(
157 0 : FD_LAYOUT_INIT,
158 0 : alignof(fd_eqvoc_t), sizeof(fd_eqvoc_t) ),
159 0 : fd_eqvoc_pool_align(), fd_eqvoc_pool_footprint( key_max ) ),
160 0 : fd_eqvoc_map_align(), fd_eqvoc_map_footprint( FD_EQVOC_MAX ) ),
161 0 : fd_sha512_align(), fd_sha512_footprint() ),
162 0 : fd_bmtree_commit_align(), fd_bmtree_commit_footprint( FD_SHRED_MERKLE_LAYER_CNT ) ),
163 0 : fd_eqvoc_map_align(), fd_eqvoc_map_footprint( FD_EQVOC_MAX ) ),
164 0 : fd_eqvoc_align() );
165 0 : }
166 : /* clang-format on */
167 :
168 : /* fd_eqvoc_new formats an unused memory region for use as a eqvoc.
169 : mem is a non-NULL pointer to this region in the local address space
170 : with the required footprint and alignment. */
171 :
172 : void *
173 : fd_eqvoc_new( void * shmem, ulong key_max, ulong seed );
174 :
175 : /* fd_eqvoc_join joins the caller to the eqvoc. eqvoc points to the
176 : first byte of the memory region backing the eqvoc in the caller's
177 : address space.
178 :
179 : Returns a pointer in the local address space to eqvoc on success. */
180 :
181 : fd_eqvoc_t *
182 : fd_eqvoc_join( void * sheqvoc );
183 :
184 : /* fd_eqvoc_leave leaves a current local join. Returns a pointer to the
185 : underlying shared memory region on success and NULL on failure (logs
186 : details). Reasons for failure include eqvoc is NULL. */
187 :
188 : void *
189 : fd_eqvoc_leave( fd_eqvoc_t const * eqvoc );
190 :
191 : /* fd_eqvoc_delete unformats a memory region used as a eqvoc.
192 : Assumes only the nobody is joined to the region. Returns a
193 : pointer to the underlying shared memory region or NULL if used
194 : obviously in error (e.g. eqvoc is obviously not a eqvoc ... logs
195 : details). The ownership of the memory region is transferred to the
196 : caller. */
197 :
198 : void *
199 : fd_eqvoc_delete( void * sheqvoc );
200 :
201 : /* fd_eqvoc_insert inserts `shred` into eqvoc, indexing it by (slot,
202 : fec_set_idx). If `shred` is a coding shred, it populates entry's
203 : metadata fields. */
204 :
205 : void
206 : fd_eqvoc_insert( fd_eqvoc_t * eqvoc, fd_shred_t const * shred );
207 :
208 : /* fd_eqvoc_query queries for FEC set metadata on (slot, fec_set_idx).
209 : At least one coding shred most be inserted to populate code_cnt,
210 : data_cnt, and the last data shred in the slot to populate last_idx.
211 : Otherwise fields are defaulted to 0, 0, FD_SHRED_IDX_NULL
212 : respectively. Callers should check whether fields are the default
213 : values before using them. */
214 :
215 : FD_FN_CONST static inline fd_eqvoc_entry_t const *
216 0 : fd_eqvoc_query( fd_eqvoc_t const * eqvoc, ulong slot, uint fec_set_idx ) {
217 0 : fd_eqvoc_key_t key = { slot, fec_set_idx };
218 0 : return fd_eqvoc_map_ele_query_const( eqvoc->map, &key, NULL, eqvoc->pool );
219 0 : }
220 :
221 : /* fd_eqvoc_search searches for whether `shred` implies equivocation by
222 : checking for a conflict in the currently indexed FEC sets. Returns
223 : the conflicting entry if there is one, NULL otherwise.
224 :
225 : A FEC set "overlaps" with another if they both contain a data shred
226 : at the samed idx. For example, say we have a FEC set containing data
227 : shreds in the idx interval [13, 15] and another containing idxs [15,
228 : 20]. The first FEC set has fec_set_idx 13 and data_cnt 3. The second
229 : FEC set has fec_set_idx 15 and data_cnt 6. They overlap because they
230 : both contain a data shred at idx 15. Therefore, these two FEC sets
231 : imply equivocation.
232 :
233 : This overlap can be detected arithmetically by adding the data_cnt to
234 : the fec_set_idx that starts earlier. If the result is greater than
235 : the fec_set_idx that starts later, we know at least one data shred
236 : idx must overlap. In this example, 13 + 3 > 15, which indicates
237 : equivocation.
238 :
239 : We can check for this overlap both backwards and forwards. We know
240 : the max number of data shred idxs in a valid FEC set is 67. So we
241 : need to look back at most 67 FEC set idxs to find the previous FEC
242 : set. Similarly, we look forward at most data_cnt idxs to find the
243 : next FEC set. */
244 :
245 : fd_eqvoc_entry_t const *
246 : fd_eqvoc_search( fd_eqvoc_t const * eqvoc, fd_shred_t const * shred );
247 :
248 : /* fd_eqvoc_test tests whether shred1 and shred2 present a valid
249 : equivocation proof. See the header at the top of the file for an
250 : explanation and enumeration of the equivocation cases.
251 :
252 : To prevent false positives, this function checks equivocation proofs
253 : contain the following:
254 :
255 : 1. shred1 and shred2 are for the same slot
256 : 2. shred1 and shred2 are the expected shred_version
257 : 3. shred1 and shred2 contain valid signatures by the current leader
258 : 4. shred1 and shred2 are the same shred type
259 : */
260 :
261 : int
262 : fd_eqvoc_test( fd_eqvoc_t const * eqvoc, fd_shred_t * shred1, fd_shred_t * shred2 );
263 :
264 : /* fd_eqvoc_from_chunks reconstructs shred1_out and shred2_out from
265 : `chunks` which is an array of "duplicate shred" gossip msgs. Shred1
266 : and shred2 comprise a "duplicate shred proof", ie. proof of two
267 : shreds that conflict and therefore demonstrate the shreds' producer
268 : has equivocated.
269 :
270 : Assumes `chunks` is non-NULL and contains at least one valid array
271 : member chunks[0] to extract header information. Caller's
272 : responsibility to guarantee this. Also assumes the `chunk` field in
273 : `fd_gossip_duplicate_shred_t` is a pointer to valid memory and
274 : consistent with the metadata presented in the header of the first
275 : array member, eg. if the header says there are 4 chunks then this
276 : implementation assumes this is true. These assumptions should be
277 : already upheld by caller if using deserializers in `fd_types.h`.
278 : Behavior is undefined otherwise.
279 :
280 : Does additional sanity-check validation eg. checking chunk_len <=
281 : FD_EQVOC_CHUNK_MAX. */
282 :
283 : void
284 : fd_eqvoc_from_chunks( fd_eqvoc_t const * eqvoc,
285 : fd_gossip_duplicate_shred_t * chunks,
286 : fd_shred_t * shred1_out,
287 : fd_shred_t * shred2_out );
288 :
289 : /* fd_eqvoc_to_chunks constructs an array of DuplicateShred gossip msgs
290 : (`chunks_out`) from shred1 and shred2.
291 :
292 : Shred1 and shred2 are concatenated (this concatenation is virtual in
293 : the implementation) and then spliced into chunks of `chunk_len` size.
294 : These chunks are embedded in the body of each DuplicateShred msg,
295 : along with a common header across all msgs.
296 :
297 : Caller supplies `chunks_out`, which is an array that MUST contain
298 : `ceil(shred1_payload_sz + shred2_payload_sz / chunk_len)` elements.
299 : Each chunk in `chunks_out` MUST have a buffer of at least `chunk_len`
300 : size available in its `chunk` pointer field. Behavior is undefined
301 : otherwise.
302 :
303 : IMPORTANT SAFETY TIP! The lifetime of each chunk in `chunks_out`
304 : must be at least as long as the lifetime of the array of
305 : duplicate_shreds. Caller is responsible for ensuring this memory
306 : safety guarantee. */
307 :
308 : void
309 : fd_eqvoc_to_chunks( fd_eqvoc_t const * eqvoc,
310 : fd_shred_t const * shred1,
311 : fd_shred_t const * shred2,
312 : ulong chunk_len,
313 : fd_gossip_duplicate_shred_t * chunks_out );
314 :
315 : #endif /* HEADER_fd_src_choreo_eqvoc_fd_eqvoc_h */
|
