Line data Source code
1 : #include "fd_ed25519.h"
2 : #include "fd_curve25519.h"
3 :
4 99 : #define FD_ED25519_CACHE_MAGIC (0xfd3d25519cac4e00UL) /* fd ed25519 cache ver 0 */
5 :
6 : /* A set holds the keys of its WAY_CNT ways in 2 cache lines. use[w]
7 : is the tick of the last use of way w (0 if way w is invalid). */
8 :
9 1354774 : #define WAY_CNT (4UL)
10 :
11 : struct __attribute__((aligned(128))) fd_ed25519_cache_set {
12 : uchar key[ WAY_CNT ][ 32 ];
13 : ulong use[ WAY_CNT ];
14 : };
15 : typedef struct fd_ed25519_cache_set fd_ed25519_cache_set_t;
16 :
17 : struct __attribute__((aligned(FD_ED25519_CACHE_ALIGN))) fd_ed25519_cache {
18 : ulong magic;
19 : ulong set_cnt; /* power of 2 */
20 : ulong filter_cnt; /* power of 2 */
21 : ulong seed;
22 :
23 : ulong credit; /* table builds are paid for with credits, see cache_admit */
24 : ulong tick; /* incremented on every lookup */
25 :
26 : ulong hit_cnt;
27 : ulong miss_cnt;
28 : ulong insert_cnt;
29 :
30 : fd_ed25519_cache_set_t * set; /* indexed [0,set_cnt) */
31 : ulong * filter; /* indexed [0,filter_cnt), hashes of recent successful misses */
32 : fd_ed25519_point_t * tbl; /* indexed [0,WAY_CNT*set_cnt*FD_ED25519_SPLIT_A_TBL_CNT), split tables of -A */
33 :
34 : fd_ed25519_point_t b_tbl[ FD_ED25519_SPLIT_B_TBL_CNT ];
35 : };
36 :
37 : /* The admission filter has 4 slots per entry */
38 :
39 99 : #define FILTER_RATIO (4UL)
40 :
41 : /* Each evaluated group equation earns a credit and a table build
42 : (~0.7 verify) costs BUILD_COST credits, bounding the build overhead
43 : to <10% even when every key is new. Up to CREDIT_MAX credits bank
44 : up for bursts of new keys. */
45 :
46 261976 : #define BUILD_COST (8UL)
47 249632 : #define CREDIT_MAX (64UL*BUILD_COST)
48 :
49 : FD_FN_CONST ulong
50 1227 : fd_ed25519_cache_align( void ) {
51 1227 : return FD_ED25519_CACHE_ALIGN;
52 1227 : }
53 :
54 : FD_FN_CONST ulong
55 321 : fd_ed25519_cache_footprint( ulong ent_cnt ) {
56 321 : if( FD_UNLIKELY( !fd_ulong_is_pow2( ent_cnt ) || ent_cnt<WAY_CNT || ent_cnt>(1UL<<20) ) ) return 0UL;
57 321 : ulong set_cnt = ent_cnt/WAY_CNT;
58 321 : ulong l = FD_LAYOUT_INIT;
59 321 : l = FD_LAYOUT_APPEND( l, alignof(fd_ed25519_cache_t), sizeof(fd_ed25519_cache_t) );
60 321 : l = FD_LAYOUT_APPEND( l, alignof(fd_ed25519_cache_set_t), set_cnt*sizeof(fd_ed25519_cache_set_t) );
61 321 : l = FD_LAYOUT_APPEND( l, alignof(ulong), FILTER_RATIO*ent_cnt*sizeof(ulong) );
62 321 : l = FD_LAYOUT_APPEND( l, alignof(fd_ed25519_point_t), ent_cnt*FD_ED25519_SPLIT_A_TBL_CNT*sizeof(fd_ed25519_point_t) );
63 321 : return FD_LAYOUT_FINI( l, fd_ed25519_cache_align() );
64 321 : }
65 :
66 : void *
67 : fd_ed25519_cache_new( void * mem,
68 : ulong ent_cnt,
69 99 : ulong seed ) {
70 99 : if( FD_UNLIKELY( !mem ) ) {
71 0 : FD_LOG_WARNING(( "NULL mem" ));
72 0 : return NULL;
73 0 : }
74 99 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)mem, fd_ed25519_cache_align() ) ) ) {
75 0 : FD_LOG_WARNING(( "misaligned mem" ));
76 0 : return NULL;
77 0 : }
78 99 : if( FD_UNLIKELY( !fd_ed25519_cache_footprint( ent_cnt ) ) ) {
79 0 : FD_LOG_WARNING(( "bad ent_cnt" ));
80 0 : return NULL;
81 0 : }
82 :
83 99 : ulong set_cnt = ent_cnt/WAY_CNT;
84 99 : ulong filter_cnt = FILTER_RATIO*ent_cnt;
85 :
86 99 : FD_SCRATCH_ALLOC_INIT( l, mem );
87 99 : fd_ed25519_cache_t * cache = FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_ed25519_cache_t), sizeof(fd_ed25519_cache_t) );
88 99 : void * set = FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_ed25519_cache_set_t), set_cnt*sizeof(fd_ed25519_cache_set_t) );
89 99 : ulong * filt = FD_SCRATCH_ALLOC_APPEND( l, alignof(ulong), filter_cnt*sizeof(ulong) );
90 99 : void * tbl = FD_SCRATCH_ALLOC_APPEND( l, alignof(fd_ed25519_point_t), ent_cnt*FD_ED25519_SPLIT_A_TBL_CNT*sizeof(fd_ed25519_point_t) );
91 99 : FD_SCRATCH_ALLOC_FINI( l, fd_ed25519_cache_align() );
92 :
93 99 : cache->set_cnt = set_cnt;
94 99 : cache->filter_cnt = filter_cnt;
95 99 : cache->seed = seed;
96 99 : cache->credit = CREDIT_MAX;
97 99 : cache->tick = 0UL;
98 99 : cache->hit_cnt = 0UL;
99 99 : cache->miss_cnt = 0UL;
100 99 : cache->insert_cnt = 0UL;
101 99 : cache->set = set;
102 99 : cache->filter = filt;
103 99 : cache->tbl = tbl;
104 :
105 99 : memset( set, 0, set_cnt*sizeof(fd_ed25519_cache_set_t) );
106 99 : memset( filt, 0, filter_cnt*sizeof(ulong) );
107 :
108 99 : fd_ed25519_split_table_b( cache->b_tbl );
109 :
110 99 : FD_COMPILER_MFENCE();
111 99 : cache->magic = FD_ED25519_CACHE_MAGIC;
112 99 : FD_COMPILER_MFENCE();
113 :
114 99 : return mem;
115 99 : }
116 :
117 : fd_ed25519_cache_t *
118 99 : fd_ed25519_cache_join( void * shcache ) {
119 99 : fd_ed25519_cache_t * cache = (fd_ed25519_cache_t *)shcache;
120 99 : if( FD_UNLIKELY( !cache ) ) {
121 0 : FD_LOG_WARNING(( "NULL shcache" ));
122 0 : return NULL;
123 0 : }
124 99 : if( FD_UNLIKELY( cache->magic!=FD_ED25519_CACHE_MAGIC ) ) {
125 0 : FD_LOG_WARNING(( "bad magic" ));
126 0 : return NULL;
127 0 : }
128 99 : return cache;
129 99 : }
130 :
131 : void *
132 54 : fd_ed25519_cache_leave( fd_ed25519_cache_t * cache ) {
133 54 : return (void *)cache;
134 54 : }
135 :
136 : void *
137 54 : fd_ed25519_cache_delete( void * shcache ) {
138 54 : fd_ed25519_cache_t * cache = (fd_ed25519_cache_t *)shcache;
139 54 : if( FD_UNLIKELY( !cache ) ) {
140 0 : FD_LOG_WARNING(( "NULL shcache" ));
141 0 : return NULL;
142 0 : }
143 54 : if( FD_UNLIKELY( cache->magic!=FD_ED25519_CACHE_MAGIC ) ) {
144 0 : FD_LOG_WARNING(( "bad magic" ));
145 0 : return NULL;
146 0 : }
147 54 : FD_COMPILER_MFENCE();
148 54 : cache->magic = 0UL;
149 54 : FD_COMPILER_MFENCE();
150 54 : return shcache;
151 54 : }
152 :
153 12027 : ulong fd_ed25519_cache_hit_cnt ( fd_ed25519_cache_t const * cache ) { return cache->hit_cnt; }
154 15 : ulong fd_ed25519_cache_miss_cnt ( fd_ed25519_cache_t const * cache ) { return cache->miss_cnt; }
155 36 : ulong fd_ed25519_cache_insert_cnt( fd_ed25519_cache_t const * cache ) { return cache->insert_cnt; }
156 :
157 : /* cache_query returns the split table of -A for public_key, or NULL if
158 : public_key is not cached. *_h is set to the hash of public_key. */
159 :
160 : static fd_ed25519_point_t const *
161 : cache_query( fd_ed25519_cache_t * cache,
162 : uchar const public_key[ 32 ],
163 353080 : ulong * _h ) {
164 353080 : ulong h = fd_hash( cache->seed, public_key, 32UL );
165 353080 : ulong idx = h & (cache->set_cnt-1UL);
166 353080 : *_h = h;
167 :
168 353080 : fd_ed25519_cache_set_t * set = cache->set + idx;
169 353080 : ulong tick = ++cache->tick;
170 :
171 1085808 : for( ulong w=0UL; w<WAY_CNT; w++ ) {
172 939554 : if( FD_LIKELY( set->use[ w ] && fd_memeq( set->key[ w ], public_key, 32UL ) ) ) {
173 206826 : set->use[ w ] = tick;
174 206826 : cache->hit_cnt++;
175 206826 : fd_ed25519_point_t const * tbl = cache->tbl + (WAY_CNT*idx+w)*FD_ED25519_SPLIT_A_TBL_CNT;
176 17861290 : for( ulong off=0UL; off<FD_ED25519_SPLIT_A_TBL_CNT*sizeof(fd_ed25519_point_t); off+=64UL ) {
177 17654464 : __builtin_prefetch( (uchar const *)tbl + off, 0, 3 );
178 17654464 : }
179 206826 : return tbl;
180 206826 : }
181 939554 : }
182 146254 : cache->miss_cnt++;
183 146254 : return NULL;
184 353080 : }
185 :
186 : /* cache_admit is called after a signature by public_key (hash h, not
187 : cached) verified successfully, with neg_a the decoded point -A. The
188 : key is inserted if it also verified successfully recently. Only
189 : keys that decode to a valid, not small order point can verify
190 : successfully, and building a table requires a valid signature, so
191 : junk traffic can't force table builds. */
192 :
193 : static void
194 : cache_admit( fd_ed25519_cache_t * cache,
195 : uchar const public_key[ 32 ],
196 : ulong h,
197 44127 : fd_ed25519_point_t const * neg_a ) {
198 :
199 44127 : ulong * slot = cache->filter + (fd_ulong_hash( h ) & (cache->filter_cnt-1UL));
200 44127 : if( FD_LIKELY( *slot!=h ) ) {
201 21505 : *slot = h;
202 21505 : return;
203 21505 : }
204 22622 : if( FD_UNLIKELY( cache->credit<BUILD_COST ) ) return;
205 12344 : cache->credit -= BUILD_COST;
206 12344 : *slot = 0UL;
207 :
208 : /* Replace the least recently used way (invalid ways have use 0) */
209 :
210 12344 : ulong idx = h & (cache->set_cnt-1UL);
211 12344 : fd_ed25519_cache_set_t * set = cache->set + idx;
212 12344 : ulong w = 0UL;
213 49376 : for( ulong v=1UL; v<WAY_CNT; v++ ) w = fd_ulong_if( set->use[ v ]<set->use[ w ], v, w );
214 :
215 12344 : fd_ed25519_split_table_a( cache->tbl + (WAY_CNT*idx+w)*FD_ED25519_SPLIT_A_TBL_CNT, neg_a );
216 12344 : memcpy( set->key[ w ], public_key, 32UL );
217 12344 : set->use[ w ] = ++cache->tick;
218 12344 : cache->insert_cnt++;
219 12344 : }
220 :
221 : /* verify_one does the checks of fd_ed25519_verify on one signature, in
222 : the same order and with the same error codes, and returns the first
223 : failing check's error code. If all checks pass, it returns
224 : FD_ED25519_SUCCESS and, if *_ok is non-zero on entry, sets *_ok to
225 : whether the group equation holds (if *_ok is zero on entry, the
226 : group equation is not evaluated). */
227 :
228 : static int
229 : verify_one( uchar const msg[],
230 : ulong msg_sz,
231 : uchar const sig[ 64 ],
232 : uchar const public_key[ 32 ],
233 : fd_sha512_t * sha,
234 : fd_ed25519_cache_t * cache,
235 369499 : int * _ok ) {
236 :
237 369499 : uchar const * r = sig;
238 369499 : uchar const * S = sig + 32;
239 :
240 369499 : if( FD_UNLIKELY( !fd_curve25519_scalar_validate( S ) ) ) return FD_ED25519_ERR_SIG;
241 :
242 353080 : ulong h;
243 353080 : fd_ed25519_point_t const * a_tbl = cache_query( cache, public_key, &h );
244 :
245 353080 : fd_ed25519_point_t Aprime[1], R[1];
246 353080 : if( FD_LIKELY( a_tbl ) ) {
247 :
248 : /* A is cached, so it decodes and is not small order: the checks of
249 : the uncached path reduce to the ones on R. frombytes_1x gives
250 : the same point as frombytes_2x, so the small order checks
251 : agree. When the equation is evaluated, R's decode is
252 : interleaved with the scalar mul and its checks run afterwards,
253 : in the same order. */
254 :
255 206826 : if( FD_UNLIKELY( !*_ok ) ) {
256 29514 : if( FD_UNLIKELY( fd_ed25519_point_frombytes_1x( R, r ) ) ) return FD_ED25519_ERR_SIG;
257 28930 : if( FD_UNLIKELY( fd_ed25519_affine_is_small_order( R ) ) ) return FD_ED25519_ERR_SIG;
258 28927 : return FD_ED25519_SUCCESS;
259 28930 : }
260 :
261 177312 : fd_ed25519_point_decode_t dec[1];
262 177312 : fd_ed25519_point_decode_init( dec, r );
263 :
264 177312 : uchar k[ 64 ];
265 177312 : fd_sha512_fini( fd_sha512_append( fd_sha512_append( fd_sha512_append( fd_sha512_init( sha ),
266 177312 : r, 32UL ), public_key, 32UL ), msg, msg_sz ), k );
267 177312 : fd_curve25519_scalar_reduce( k, k );
268 :
269 : /* Rcmp = [k](-A') + [S]B */
270 :
271 177312 : fd_ed25519_point_t Rcmp[1];
272 177312 : fd_ed25519_double_scalar_mul_base_split_decode( Rcmp, k, a_tbl, S, cache->b_tbl, dec );
273 :
274 177312 : if( FD_UNLIKELY( fd_ed25519_point_decode_fini( R, dec ) ) ) return FD_ED25519_ERR_SIG;
275 163482 : if( FD_UNLIKELY( fd_ed25519_affine_is_small_order( R ) ) ) return FD_ED25519_ERR_SIG;
276 :
277 155124 : cache->credit = fd_ulong_min( cache->credit+1UL, CREDIT_MAX );
278 155124 : *_ok = fd_ed25519_point_eq_z1( Rcmp, R );
279 155124 : return FD_ED25519_SUCCESS;
280 163482 : }
281 :
282 146254 : int res = fd_ed25519_point_frombytes_2x( Aprime, public_key, R, r );
283 146254 : if( FD_UNLIKELY( res ) ) return res == -1 ? FD_ED25519_ERR_PUBKEY : FD_ED25519_ERR_SIG;
284 122452 : if( FD_UNLIKELY( fd_ed25519_affine_is_small_order( Aprime ) ) ) return FD_ED25519_ERR_PUBKEY;
285 110473 : if( FD_UNLIKELY( fd_ed25519_affine_is_small_order( R ) ) ) return FD_ED25519_ERR_SIG;
286 :
287 108562 : if( FD_UNLIKELY( !*_ok ) ) return FD_ED25519_SUCCESS;
288 :
289 94409 : cache->credit = fd_ulong_min( cache->credit+1UL, CREDIT_MAX );
290 :
291 94409 : uchar k[ 64 ];
292 94409 : fd_sha512_fini( fd_sha512_append( fd_sha512_append( fd_sha512_append( fd_sha512_init( sha ),
293 94409 : r, 32UL ), public_key, 32UL ), msg, msg_sz ), k );
294 94409 : fd_curve25519_scalar_reduce( k, k );
295 :
296 : /* Rcmp = [k](-A') + [S]B */
297 :
298 94409 : fd_ed25519_point_t Rcmp[1];
299 94409 : fd_ed25519_point_neg( Aprime, Aprime );
300 94409 : fd_ed25519_double_scalar_mul_base( Rcmp, k, Aprime, S );
301 94409 : *_ok = fd_ed25519_point_eq_z1( Rcmp, R );
302 94409 : if( FD_LIKELY( *_ok ) ) cache_admit( cache, public_key, h, Aprime );
303 94409 : return FD_ED25519_SUCCESS;
304 108562 : }
305 :
306 : int
307 : fd_ed25519_verify_cached( uchar const msg[], /* msg_sz */
308 : ulong msg_sz,
309 : uchar const sig[ 64 ],
310 : uchar const public_key[ 32 ],
311 : fd_sha512_t * sha,
312 155158 : fd_ed25519_cache_t * cache ) {
313 155158 : int ok = 1;
314 155158 : int err = verify_one( msg, msg_sz, sig, public_key, sha, cache, &ok );
315 155158 : if( FD_UNLIKELY( err ) ) return err;
316 91337 : return FD_LIKELY( ok ) ? FD_ED25519_SUCCESS : FD_ED25519_ERR_MSG;
317 155158 : }
318 :
319 : int
320 : fd_ed25519_verify_batch_single_msg_cached( uchar const msg[], /* msg_sz */
321 : ulong const msg_sz,
322 : uchar const signatures[ 64 ], /* 64 * batch_sz */
323 : uchar const pubkeys[ 32 ], /* 32 * batch_sz */
324 : fd_sha512_t * shas[ 1 ], /* batch_sz */
325 : uchar const batch_sz,
326 41478 : fd_ed25519_cache_t * cache ) {
327 41478 : if( FD_UNLIKELY( batch_sz == 0 || batch_sz > 16 ) ) return FD_ED25519_ERR_SIG;
328 :
329 : /* The uncached version runs all checks first and then the group
330 : equations. A check failure on any signature takes precedence over
331 : a group equation failure on an earlier one, so group equation
332 : failures are only reported after all checks pass. Once a group
333 : equation fails, the remaining ones are skipped. */
334 :
335 41073 : int ok = 1;
336 242349 : for( ulong j=0UL; j<batch_sz; j++ ) {
337 214341 : int err = verify_one( msg, msg_sz, signatures+64UL*j, pubkeys+32UL*j, shas[j], cache, &ok );
338 214341 : if( FD_UNLIKELY( err ) ) return err;
339 214341 : }
340 28008 : return FD_LIKELY( ok ) ? FD_ED25519_SUCCESS : FD_ED25519_ERR_MSG;
341 41073 : }
|
