Line data Source code
1 : #ifndef HEADER_fd_src_disco_shred_fd_rnonce_ss_h
2 : #define HEADER_fd_src_disco_shred_fd_rnonce_ss_h
3 : #include "../../util/fd_util.h"
4 :
5 : /* fd_rnonce_ss_t is a strongly typed version of the 64 byte shared
6 : secret used to generate and verify nonces for repair requests and
7 : responses. */
8 : union fd_rnonce_ss {
9 : uchar bytes[64];
10 : struct {
11 : ulong ss0[3];
12 : ulong slot;
13 : ulong ss1[1];
14 : uint shred_idx;
15 : uint ss2[2];
16 : uint time;
17 : ulong ss3[1];
18 : } private;
19 : };
20 : typedef union fd_rnonce_ss fd_rnonce_ss_t;
21 : FD_STATIC_ASSERT( sizeof(fd_rnonce_ss_t)==64, rnonce_ss );
22 :
23 : /* FD_RNONCE_SS_DELTA_MAX is how many 2^24 ns ticks after it is computed
24 : a nonce still verifies, about 1 s. */
25 :
26 0 : #define FD_RNONCE_SS_DELTA_MAX ((uint)((1000000000UL + (1UL<<24) - 1UL)/(1UL<<24))) /* == 60 */
27 :
28 : FD_PROTOTYPES_BEGIN
29 :
30 : FD_FN_CONST static inline int
31 0 : fd_rnonce_ss_normal_repair( uint nonce ) { return (int)(nonce>>31); }
32 :
33 : /* fd_rnonce_ss_{compute,verify} compute and verify, respectively, the
34 : nonce for the specified repair request issued or received at time_ns.
35 : slot and shred_idx specify the slot and shred index of the
36 : requested/received shred. slot_complete must be non-zero if the
37 : received shred is the last in the slot. normal_repair must be
38 : non-zero if the request is a "normal" repair request, i.e., one for a
39 : specific shred index. If normal_repair is zero, shred_idx is
40 : ignored, slot is adjusted (see below), and slot_complete must be
41 : non-zero in the verify function. ss is a pointer to the shared secret
42 : value. ss_compute returns the value of the nonce. ss_verify takes
43 : the supposed value of the nonce in the nonce parameter. ss_verify
44 : returns 1 if the nonce is correct and 0 otherwise.
45 :
46 : These satisfy:
47 : 1==ss_verify( ss_v, ss_compute( ss_c, 1, slot_c, shred_idx_c, rq_time ), slot_v, shred_idx_v, slot_complete, rs_time )
48 : when
49 : ss_v == ss_c,
50 : slot_v == slot_c,
51 : shred_idx_v == shred_idx_c, AND
52 : rq_time <= rs_time < rq_time + 1.02 seconds.
53 : When any of these of these conditions is false, it should return 0
54 : with high probability, approx (1 - 2^25).
55 :
56 : And
57 : 1==ss_verify( ss_v, ss_compute( ss_c, 0, slot_c, shred_idx_c, rq_time ), slot_v, shred_idx_v, slot_complete, rs_time )
58 : when
59 : ss_v == ss_c,
60 : slot_complete != 0,
61 : -1 <= floor(slot_v/128) - floor(slot_c/128) <= 0, which is looser than slot_c - 128 <= slot_v <= slot_c, AND
62 : rq_time <= rs_time < rq_time + 1.02 seconds.
63 : When any of these of these conditions is false, it should return 0
64 : with high probability, approx (1 - 2^25).
65 : */
66 : static inline uint
67 : fd_rnonce_ss_compute( fd_rnonce_ss_t const * ss,
68 : int normal_repair,
69 : ulong slot,
70 : uint shred_idx,
71 0 : long time_ns ) {
72 0 : fd_rnonce_ss_t temp[1] = { *ss };
73 : /* truncate time down to intervals of 2^32 ns, which is ~4 seconds. */
74 0 : temp->private.time = (uint)(time_ns>>32);
75 0 : temp->private.slot = fd_ulong_if( normal_repair, slot, slot/128UL );
76 0 : temp->private.shred_idx = fd_uint_if ( normal_repair, shred_idx, 0U );
77 : /* seed is fractional part of sqrt(17) */
78 : /* Then we add back in time_ns>>24 (truncated to 16ms intervals).
79 : This is kind of surprising, but it means that we can generate a new
80 : nonce when we re-request a specific shred, but we don't need to
81 : compute a ton of hashes. */
82 0 : return (uint)(
83 0 : fd_ulong_if( normal_repair, 0x80000000UL, 0UL ) |
84 0 : (0x7FFFFFFFUL & (fd_hash( 2270897969802886507UL, temp, sizeof(temp) ) + (((ulong)time_ns)>>24) ) ) );
85 0 : }
86 :
87 : static inline int
88 : fd_rnonce_ss_verify( fd_rnonce_ss_t const * ss,
89 : uint nonce,
90 : ulong slot,
91 : uint shred_idx,
92 : int slot_complete,
93 0 : long time_ns ) {
94 0 : fd_rnonce_ss_t temp[1] = { *ss };
95 0 : int normal_repair = fd_rnonce_ss_normal_repair( nonce );
96 :
97 : /* If it's not "normal" repair, then the shred must have slot
98 : complete. Technically this is not required by the repair protocol,
99 : so we may occasionally reject an honest response here when the
100 : responder doesn't have the last shred in the slot, but this is good
101 : defense in depth. If none of the repair peers have the last shred
102 : in the slot, then it's unlikely the cluster has confirmed it. */
103 0 : if( FD_UNLIKELY( (!normal_repair) & (!slot_complete) ) ) return 0;
104 :
105 0 : temp->private.time = (uint)(time_ns>>32);
106 0 : temp->private.slot = fd_ulong_if( normal_repair, slot, slot/128UL );
107 0 : temp->private.shred_idx = fd_uint_if ( normal_repair, shred_idx, 0U );
108 0 : #define ALLOWED_TIME_DELTA FD_RNONCE_SS_DELTA_MAX
109 :
110 0 : #define CHECKN( temp ) do{ if( FD_LIKELY( \
111 0 : ( (fd_hash( 2270897969802886507UL, temp, sizeof(temp) ) + (((ulong)time_ns)>>24) - (ulong)nonce) & \
112 0 : 0x7FFFFFFFUL ) <= ALLOWED_TIME_DELTA ) ) \
113 0 : return 1; \
114 0 : } while( 0 )
115 :
116 :
117 0 : CHECKN( temp );
118 :
119 0 : int try_prev_time = ((time_ns-1000000000L)>>32) != (time_ns>>32);
120 0 : if( try_prev_time ) {
121 : /* If that doesn't match, check the previous time bucket. */
122 0 : temp->private.time--;
123 0 : CHECKN( temp );
124 0 : temp->private.time++;
125 0 : }
126 :
127 0 : if( FD_UNLIKELY( !normal_repair ) ) {
128 : /* Check the next slot bucket */
129 0 : temp->private.slot++;
130 0 : CHECKN( temp );
131 0 : if( try_prev_time ) {
132 : /* And check it with the prev time bucket */
133 0 : temp->private.time--;
134 0 : CHECKN( temp );
135 0 : }
136 0 : }
137 0 : #undef CHECKN
138 0 : #undef ALLOWED_TIME_DELTA
139 0 : return 0;
140 0 : }
141 :
142 : FD_PROTOTYPES_END
143 :
144 : #endif /* HEADER_fd_src_disco_shred_fd_rnonce_ss_h */
|
