Line data Source code
1 : #ifndef HEADER_fd_src_disco_shred_fd_fec_samp_h
2 : #define HEADER_fd_src_disco_shred_fd_fec_samp_h
3 :
4 :
5 : /* This header defines a few methods for digesting a FEC set into a
6 : small hash and then probabilistically answering if a given shred
7 : might have been part of that FEC set using the hash. These are
8 : designed for use by the FEC resolver only, but are factored out into
9 : this file to make them easier to iterate and test.
10 :
11 : Doing this probabilistically might seem excessive, but when Turbine
12 : is working perfectly, we expect 32 shreds to arrive after the FEC set
13 : is in the done_map, which means we expect to answer "was shred X
14 : probably part of FEC set Y?" 32 times per FEC set. If we derive the
15 : Merkle root for shred X, which is the way to answer the question
16 : deterministically, that's about 40us of wasted computation per FEC
17 : set, which is a sizable fraction of the total computation per FEC
18 : set. Plus, the answer to the question is almost always "yes" unless
19 : the leader is malicious and equivocating. */
20 :
21 : FD_PROTOTYPES_BEGIN
22 :
23 : /* fd_fec_samp_t is an opaque small type that contains the digest of a
24 : FEC set. It's only 4 bytes right now and it is statically sized, so
25 : it can be declared on the stack or included in a struct. */
26 : union fd_fec_samp;
27 : typedef union fd_fec_samp fd_fec_samp_t;
28 :
29 : /* fd_fec_samp_derive creates a digest of a FEC set and populates s with
30 : it. s must point to a valid fd_fec_samp_t. seed is an arbitrary
31 : value, intended to be different per-validator. slot, fec_set_idx,
32 : signature, and root all describe the FEC set that is being digested.
33 : bmtree must be a valid tree initialized with all the shreds in the
34 : FEC set as leaves. */
35 : static inline void
36 : fd_fec_samp_derive( fd_fec_samp_t * s,
37 : ulong seed,
38 : ulong slot,
39 : uint fec_set_idx,
40 : void const * signature,
41 : fd_bmtree_node_t const * root,
42 : fd_bmtree_commit_t const * bmtree );
43 :
44 : /* fd_fec_samp_set_force_match modifies the digest s to match any and
45 : all shreds. This is useful for cases where you have already detected
46 : equivocation and do not want to spend any more computation on the FEC
47 : set. */
48 : static inline void fd_fec_samp_set_force_match( fd_fec_samp_t * s );
49 :
50 :
51 : /* fd_fec_samp_matches answers queries of "is it likely that the shred
52 : pointed to by shred comes from the same FEC set (identified by Merkle
53 : root) whose digest is stored in s?" Returns 1 if so, and 0 if it is
54 : certain the shred did not come from the digest in s. seed must be the
55 : same value provided to fd_fec_samp_derive. It's expected that s has
56 : the same slot and fec_set_idx as the FEC set whose digest is stored
57 : in s, but that is not checked. IMPORTANT: This function is
58 : probabilistic. It may return 1 for shreds that did not come from the
59 : FEC set whose digest is stored in s. However, it will never make a
60 : mistake in the other direction (returning 0 for a shred that actually
61 : did come from the FEC set digested into s). If
62 : fd_fec_samp_set_force_match was called on s, always returns 1.
63 : This function is designed to be extremely fast in the common case.
64 : About 6% of the time, it will do a sha256 operation, but the rest of
65 : the time, it is just O(1) cheap operations.
66 :
67 : In general, if s does not come from the FEC set digested into s, and
68 : it comes from a replayable FEC set, it will return 0 (the correct
69 : answer) approximately 99.99% of the time (1-2^-14).
70 : There are certainly maliciously constructed FEC sets that are not
71 : actually valid that it can detect with much lower probability, only
72 : about 3%.
73 : Furthermore, extremely rarely (2^-32 of the time), a FEC set will
74 : return a degenerate digest, resulting in all shreds returning 1.
75 : See below for much more commentary on the probabilities. */
76 : static inline int
77 : fd_fec_samp_matches( fd_fec_samp_t const * s,
78 : ulong seed,
79 : fd_shred_t const * shred );
80 :
81 : FD_PROTOTYPES_END
82 :
83 : /* Suppose we derive a sample from FEC set F containing shreds S_0, S_1,
84 : ... S_63, where S_i for i in [0, 32) are data shreds. Let proof(S_i)
85 : be the operation that extracts the Merkle proof from shred S_i and
86 : contanates the elements into one long bitstring. If F' is a
87 : different FEC set produced honetly, then we expect proof(S_i) and
88 : proof(S'_i) to be uncorrelated. That is, for any set of n bit
89 : positions that we extract from both, the probability they will match
90 : at all n positions is 2^-n.
91 :
92 : However, that is not necessarily true when F' is constructed
93 : maliciously. The easiest example of this is to suppose S_0==S'_0,
94 : ... S_30=S'_30 but S_31 != S'_31, then proof(S_i) and proof(S'_i)
95 : *will* be correlated for i<32. However, the Reed-Solomon parity
96 : shreds will be different, which means proof(S_i) and proof(S'_i) will
97 : not be correlated for i>=32.
98 :
99 : More generally, since Reed-Solomon works on polynomials of degree<32,
100 : and modifying a shred can be seen as adding a non-zero polynomial,
101 : which then has no more than 31 zeros, if F!=F', then they differ in
102 : at least 33 shreds, assuming the erasure coding is computed correctly
103 : (otherwise it would be invalid).
104 :
105 : There is one other attack worth mentioning: the attacker could send
106 : shred S'_i but with a Merkle proof cloned from S_i. Every shred in
107 : this sort of attack makes its own FEC set, so this attack can't
108 : really be used for real equivocation, but it's a bit lame if we're
109 : totally blind to that type of attack because we only consider Merkle
110 : proofs. That means we do sometimes need to hash some shreds.
111 :
112 : If we didn't have Merkle proofs, we might try an approach like this:
113 : using the seed and the (slot, FEC index), choose 32 of the 64 shreds,
114 : and a bit position for each. When you receive a shred, if it's one
115 : of the ones in the sample, compute the hash and test if the bit
116 : matches. If it doesn't you know there's equivocation. Because of
117 : our pigeon hole principle/fundamental theorem of algebra argument, we
118 : know that if the attacker modified any shred, he modified at least 33
119 : of them, which means our sample includes at least one of the modified
120 : shreds, so we can detect this equivocation at least with probability
121 : 0.5. We'll measure the cost of this as 0.5, since we expect to have
122 : to hash half of the shreds. Since this approach is only shred-based,
123 : it's unaffected by the attacker playing games with the Merkle proof.
124 :
125 : On the other extreme, we could sample 16 bits from each of the
126 : highest nodes in the Merkle proof. Again, assuming the erasure
127 : coding is legitimate, F and F' differ in at least 33 shreds, which
128 : means both halves of the Merkle tree have at least one differing
129 : leaf, so both children of the root will differ. Since each shred
130 : must contain one of the immediate children of the root, the
131 : probability we miss an equivocation is 2^-16 (0.0015%). In this
132 : approach, we never have to hash, so we'll say its cost is 0.
133 : However, obviously this approach doesn't catch equivocation when the
134 : attacker is playing the games with the Merkle proof we considered
135 : above or not generating the erasure coding legitimately (recall again
136 : that those games prevent this equivocating proof from ever being
137 : COMPLETE-able, and thus replayable).
138 :
139 : Does it ever make sense to take bits from another node? I think it
140 : doesn't. First of all, as in the case we considered earlier where
141 : S_i==S'_i for i<31, it's possible for other nodes in the Merkle tree
142 : for F and F' to be equal as long as they have fewer than 32 leaves
143 : under them. Secondly, those bits are only useful for the fraction of
144 : shreds that include the node we sampled from. Thirdly, those bits
145 : don't give any additional discriminating power beyond what they would
146 : if they were in the root.
147 :
148 : Then the only question becomes how many bits to allocate to direct
149 : hashes, and there's not a mathematical answer, since it's just about
150 : our desired sensitivity to the proof-cloning game. If we store b
151 : bits from each hash of h shreds, and we expect to receive each of the
152 : 64 shreds (which have all been modified but retain their orignal
153 : Merkle proofs) with equal probability then we'll detect this as
154 : equivocation with probability h/64*(1-2^-b), and this consumes h*b
155 : bits total. This shows for a constant bit-budget, it's better to
156 : make h as large as possible and keep b as small as possible.
157 : Maximizing h also increases the hashing cost of the approach, so we
158 : don't want it too large.
159 :
160 : All put together, we'll use 14 bits for the left child of the root,
161 : 14 bits for the right child of the root, and 4 bits for leaf hashes,
162 : one bit per hash for each of four shreds. */
163 :
164 : union fd_fec_samp {
165 : uint val;
166 : struct {
167 : ushort data;
168 : ushort parity;
169 : };
170 : };
171 : typedef union fd_fec_samp fd_fec_samp_t;
172 :
173 :
174 : /* The following are private helper functions/types */
175 : typedef struct {
176 : ulong mask; /* in [0, 0xFF_FFFF_FFFF] */
177 : ulong offset; /* in [0, 15] */
178 : ulong shred0; /* in [0, 31] */
179 : ulong shred1; /* in [0, 31] */
180 : ulong shred_bit; /* in [0, 31], indicating which bit of the selected uint to compare */
181 : ulong shred0_off; /* in [0, 4] */
182 : ulong shred1_off; /* in [0, 4] */
183 : } fd_fec_samp_dec_t;
184 :
185 :
186 : FD_PROTOTYPES_BEGIN
187 :
188 : static inline void
189 : fd_fec_samp_decompose( ulong entropy,
190 0 : fd_fec_samp_dec_t * out ) {
191 0 : ulong final_bits = entropy>>59; /* 5 bits left */
192 :
193 0 : *out = (fd_fec_samp_dec_t) {
194 0 : .mask = (entropy >> 0) & 0xFFFFFFFFFFUL,
195 0 : .offset = (entropy >> 40) & 0xFUL,
196 0 : .shred0 = (entropy >> 44) & 0x1FUL,
197 0 : .shred1 = (entropy >> 49) & 0x1FUL,
198 0 : .shred_bit = (entropy >> 54) & 0x1FUL,
199 : /* We don't have enough entropy left to choose one of 160 bits for
200 : each of the two shreds, so we'll just have them use the same
201 : bit within a uint and different uint. */
202 0 : .shred0_off = final_bits%5UL,
203 0 : .shred1_off = (final_bits/5UL)%5UL,
204 0 : };
205 :
206 : /* Fixup to make sure the two shreds are different */
207 0 : out->shred1 = fd_ulong_if( out->shred0==out->shred1, (out->shred1)^1UL, out->shred1 );
208 0 : }
209 :
210 : /* Selects up to 14 bits of 40 bits from input corresponding to 1 bits
211 : in mask. */
212 : static inline ulong
213 : fd_fec_samp_extract_cor_bits( ulong input,
214 0 : ulong mask ) {
215 : #if FD_HAS_AVX2 /* Actually BMI2, but the same CPUs support AVX2 as BMI2 */
216 : /* It's actually easier to take the first 14 bits with this AND than
217 : to make sure the mask only has 14 bits set to 1. */
218 : return 0x3FFFUL & _pext_u64( input, mask );
219 : #else
220 0 : ulong cor_bits = 0UL;
221 0 : ulong j = 1UL;
222 0 : for( ulong i=0UL; i<40UL; i++ ) if( 1UL & (mask>>i) ) { cor_bits |= fd_ulong_if( 1UL & (input>>i), j, 0UL ); j<<=1; }
223 0 : return cor_bits & 0x3FFFUL;
224 0 : #endif
225 0 : }
226 :
227 : static inline ushort
228 : fd_fec_samp_extract( fd_bmtree_commit_t const * bmtree,
229 : fd_fec_samp_dec_t const * entropy,
230 0 : ulong leaf_off ) {
231 0 : union {
232 0 : uchar p[6][20];
233 0 : uchar raw[120 + 8]; /* allow tail reading */
234 0 : uint uints[6][5];
235 0 : } proof;
236 :
237 : /* We can get the hash of shred n by getting the proof of shred n^1 */
238 0 : FD_TEST( -1!=fd_bmtree_get_proof( bmtree, proof.raw, leaf_off + (entropy->shred0 ^ 1UL) ) );
239 :
240 : /* Extract ~14 bits from the child of the root */
241 0 : ulong cor_bits = fd_fec_samp_extract_cor_bits( fd_ulong_load_5_fast( proof.p[5] + entropy->offset ), entropy->mask );
242 :
243 : /* Extract 1 bit from the randomly selected leaf, then 1 bit from the
244 : other randomly selected leaf. */
245 0 : ulong shred0_bit = 1UL & (proof.uints[0][entropy->shred0_off]>>entropy->shred_bit);
246 :
247 0 : FD_TEST( -1!=fd_bmtree_get_proof( bmtree, proof.raw, leaf_off + (entropy->shred1 ^ 1UL) ) );
248 0 : ulong shred1_bit = 1UL & (proof.uints[0][entropy->shred1_off]>>entropy->shred_bit);
249 :
250 0 : return (ushort)( (shred0_bit<<15) | (shred1_bit<<14) | cor_bits );
251 0 : }
252 :
253 : /* end of private helpers */
254 :
255 : static inline void
256 : fd_fec_samp_derive( fd_fec_samp_t * s,
257 : ulong seed,
258 : ulong slot,
259 : uint fec_set_idx,
260 : void const * signature,
261 : fd_bmtree_node_t const * root,
262 0 : fd_bmtree_commit_t const * bmtree ) {
263 : /* We don't use either the signature (since it's not a trustworthy
264 : key) or the root (since it's not available in the shred) */
265 0 : (void)signature;
266 0 : (void)root;
267 :
268 : /* For the probabilities to be right above, it doesn't matter what
269 : bits we choose. However, an adversary could grind hashes to make
270 : it collide if we were using well-known bits, and if all validators
271 : were using the same bits, we'd lose the advantage of
272 : per-validator statistical independence. Ideally, we'd choose 14 of
273 : the 160 bits uniformly randomly without replacement, probably with
274 : something like reservoir sampling. However, that's a lot of work,
275 : and we don't need that level of precision. Instead we'll generate
276 : random 40 bits, and take the first 14 one bits it has (98% chance
277 : it will have at least 14 bits set to one), then use that as a mask
278 : with 5 contiguous bytes in the 20 byte proof element. This is not
279 : exactly uniform (the last bit has only 0.08% chance of being
280 : selected, the first bit has a 3.1% chance of being selected,
281 : compared to 8.75% for each bit if we did things perfectly) but it's
282 : pretty close; entropy-wise, this is something like picking from 140
283 : bits instead of 160 bits. */
284 0 : fd_rng_t rng[1];
285 0 : fd_rng_join( fd_rng_new( rng, (uint)slot ^ (uint)(fec_set_idx<<20), seed ) );
286 0 : fd_fec_samp_dec_t data[1], parity[1];
287 0 : fd_fec_samp_decompose( fd_rng_ulong( rng ), data );
288 0 : fd_fec_samp_decompose( fd_rng_ulong( rng ), parity );
289 :
290 : /* The data shreds are the first 32 shreds in the FEC set/Merkle tree,
291 : and the parity shreds are the last 32. */
292 0 : s->data = fd_fec_samp_extract( bmtree, data, 0UL );
293 0 : s->parity = fd_fec_samp_extract( bmtree, parity, 32UL );
294 :
295 : /* It's possible, but extremely unlikely that s->val could be UINT_MAX
296 : at this point. However, an attacker could bias the probabilities
297 : in that direction by grinding for hashes with a lot of 1 bits. We
298 : can eliminate that attack vector with another xor */
299 0 : s->val ^= (uint)seed;
300 :
301 0 : fd_rng_delete( fd_rng_leave( rng ) );
302 0 : }
303 :
304 : static inline int
305 : fd_fec_samp_matches( fd_fec_samp_t const * s_raw,
306 : ulong seed,
307 0 : fd_shred_t const * shred ) {
308 0 : if( FD_UNLIKELY( s_raw->val==UINT_MAX ) ) return 1;
309 :
310 0 : fd_rng_t rng[1];
311 0 : fd_rng_join( fd_rng_new( rng, (uint)shred->slot ^ (uint)(shred->fec_set_idx<<20), seed ) );
312 0 : fd_fec_samp_dec_t entropy[1];
313 : /* undo the final xor from derive */
314 0 : fd_fec_samp_t s[1] = {{ .val = s_raw->val ^ (uint)seed }};
315 :
316 0 : int is_data_shred = fd_shred_is_data( fd_shred_type( shred->variant ) );
317 0 : ushort compare = fd_ushort_if( is_data_shred, s->data, s->parity );
318 :
319 0 : if( !is_data_shred ) fd_rng_ulong( rng ); /* advance rng */
320 0 : fd_fec_samp_decompose( fd_rng_ulong( rng ), entropy );
321 0 : fd_rng_delete( fd_rng_leave( rng ) );
322 :
323 0 : fd_shred_merkle_t const * nodes = fd_shred_merkle_nodes( shred );
324 :
325 0 : ulong cor_bits = fd_fec_samp_extract_cor_bits( fd_ulong_load_5( nodes[5] + entropy->offset ), entropy->mask );
326 0 : if( FD_UNLIKELY( cor_bits!=(compare&0x3FFFUL) ) ) return 0;
327 :
328 0 : ulong in_type_idx = fd_ulong_if( is_data_shred, shred->idx - shred->fec_set_idx, shred->code.idx );
329 0 : if( FD_UNLIKELY( (in_type_idx==entropy->shred0) | (in_type_idx==entropy->shred1) ) ) {
330 : /* This is one of the shreds we need to hash. */
331 0 : ulong merkle_protected_sz = fd_ulong_if( is_data_shred, FD_SHRED_MIN_SZ, FD_SHRED_MAX_SZ )
332 0 : - FD_SHRED_SIGNATURE_SZ * (1UL+fd_shred_is_resigned( fd_shred_type( shred->variant ) ))
333 0 : - FD_SHRED_MERKLE_NODE_SZ*(FD_SHRED_MERKLE_LAYER_CNT-1UL);
334 :
335 0 : union {
336 0 : fd_bmtree_node_t leaf[1];
337 0 : uint u[5];
338 0 : } l;
339 :
340 0 : fd_bmtree_hash_leaf( l.leaf, (uchar const *)shred + sizeof(fd_ed25519_sig_t), merkle_protected_sz, FD_BMTREE_LONG_PREFIX_SZ );
341 0 : ulong bit = 1UL & (l.u[ fd_ulong_if( in_type_idx==entropy->shred0, entropy->shred0_off, entropy->shred1_off ) ]>>entropy->shred_bit);
342 0 : if( FD_UNLIKELY( bit!=(1UL & fd_ulong_if( in_type_idx==entropy->shred0, compare>>15, compare>>14 ) ) ) ) return 0;
343 0 : }
344 :
345 0 : return 1;
346 0 : }
347 :
348 4572 : static inline void fd_fec_samp_set_force_match( fd_fec_samp_t * s ) { s->val = UINT_MAX; }
349 :
350 : FD_PROTOTYPES_END
351 :
352 : #endif /* HEADER_fd_src_disco_shred_fd_fec_samp_h */
|
