Line data Source code
1 : #include "fd_bls.h"
2 :
3 : #include "../../third_party/blst/bindings/blst.h"
4 :
5 : void
6 : fd_bls_sec_to_pub( fd_bls_sec_t const * sk,
7 0 : fd_bls_pub_t * pk ) {
8 0 : blst_p1 p[1];
9 0 : blst_sk_to_pk_in_g1( p, sk );
10 0 : blst_p1_to_affine( pk, p );
11 0 : }
12 :
13 : void
14 : fd_bls_sec_sign( fd_bls_sec_t const * sk,
15 : uchar const * msg,
16 : ulong msg_sz,
17 0 : fd_bls_sig_t * sig ) {
18 0 : blst_p2 hash[1];
19 0 : blst_p2 p[1];
20 0 : blst_hash_to_g2( hash, msg, msg_sz, (uchar const *)FD_BLS_DST, FD_BLS_DST_SZ, NULL, 0UL );
21 0 : blst_sign_pk_in_g1( p, hash, sk );
22 0 : blst_p2_to_affine( sig, p );
23 0 : }
24 :
25 : void
26 : fd_bls_sec_derive( fd_bls_sec_t * sk,
27 : uchar const * ikm,
28 0 : ulong ikm_sz ) {
29 0 : FD_TEST( ikm_sz>=32UL );
30 0 : blst_keygen( sk, ikm, ikm_sz, NULL, 0UL );
31 0 : }
32 :
33 : void
34 : fd_bls_sig_ser( fd_bls_sig_t const * sig,
35 0 : uchar buf[ static FD_BLS_SIG_SZ ] ) {
36 0 : blst_p2_affine_serialize( buf, sig );
37 0 : }
38 :
39 : int
40 : fd_bls_sig_de( fd_bls_sig_t * sig,
41 0 : uchar const buf[ static FD_BLS_SIG_SZ ] ) {
42 0 : if( FD_UNLIKELY( blst_p2_deserialize( sig, buf )!=BLST_SUCCESS ) ) return -1;
43 0 : if( FD_UNLIKELY( !blst_p2_affine_in_g2( sig ) ) ) return -1;
44 0 : return 0;
45 0 : }
46 :
47 : static int
48 : pub_from_bytes( blst_p1_affine * out,
49 : uchar const * in,
50 0 : ulong in_sz ) {
51 0 : BLST_ERROR err;
52 0 : switch( in_sz ) {
53 0 : case FD_BLS_PUB_COMPRESSED_SZ: err = blst_p1_uncompress ( out, in ); break;
54 0 : case FD_BLS_PUB_SZ:
55 0 : if( FD_UNLIKELY( in[0]&0xA0U ) ) return 0;
56 0 : err = blst_p1_deserialize( out, in );
57 0 : break;
58 0 : default: return 0;
59 0 : }
60 0 : return err==BLST_SUCCESS &&
61 0 : !blst_p1_affine_is_inf( out ) &&
62 0 : blst_p1_affine_in_g1( out );
63 0 : }
64 :
65 : int
66 : fd_bls_pub_de( fd_bls_pub_t * pub,
67 : uchar const * buf,
68 0 : ulong buf_sz ) {
69 0 : return pub_from_bytes( pub, buf, buf_sz ) ? 0 : -1;
70 0 : }
71 :
72 : fd_bls_agg_t *
73 0 : fd_bls_agg_null( fd_bls_agg_t * agg ) {
74 0 : fd_memset( &agg->pub, 0, sizeof(blst_p1) );
75 0 : fd_memset( &agg->sig, 0, sizeof(blst_p2) );
76 0 : fd_bls_set_null( agg->set );
77 0 : return agg;
78 0 : }
79 :
80 : fd_bls_agg_t *
81 : fd_bls_agg_construct( fd_bls_agg_t * agg,
82 : fd_bls_pub_t const * pub,
83 : fd_bls_sig_t const * sig,
84 0 : fd_bls_set_t const * set ) {
85 0 : fd_bls_set_copy( agg->set, set );
86 :
87 : /* one batched addition per curve: a field inversion per batch in
88 : place of one per signer */
89 0 : fd_bls_pub_t const * pub_ptr[ FD_BLS_SET_MAX ];
90 0 : fd_bls_sig_t const * sig_ptr[ FD_BLS_SET_MAX ];
91 0 : ulong cnt = 0UL;
92 0 : for( ulong rank = fd_bls_set_const_iter_init( set );
93 0 : !fd_bls_set_const_iter_done( rank );
94 0 : rank = fd_bls_set_const_iter_next( set, rank ) ) {
95 0 : pub_ptr[ cnt ] = pub+rank;
96 0 : sig_ptr[ cnt ] = sig+rank;
97 0 : cnt++;
98 0 : }
99 0 : blst_p1s_add( &agg->pub, pub_ptr, cnt );
100 0 : blst_p2s_add( &agg->sig, sig_ptr, cnt );
101 0 : return agg;
102 0 : }
103 :
104 : blst_p1 *
105 : fd_bls_pub_sum( blst_p1 * pub,
106 : fd_bls_pub_t const * key,
107 : ulong key_cnt,
108 : fd_bls_set_t const * set,
109 0 : blst_p1 const * full ) {
110 0 : fd_memset( pub, 0, sizeof(blst_p1) ); /* point at infinity */
111 :
112 0 : if( FD_LIKELY( !full || 2UL*fd_bls_set_cnt( set )<=key_cnt ) ) {
113 0 : for( ulong rank=0UL; rank<key_cnt; rank++ ) {
114 0 : if( fd_bls_set_test( set, rank ) ) blst_p1_add_or_double_affine( pub, pub, key+rank );
115 0 : }
116 0 : return pub;
117 0 : }
118 :
119 : /* full minus the keys not in set */
120 0 : for( ulong rank=0UL; rank<key_cnt; rank++ ) {
121 0 : if( !fd_bls_set_test( set, rank ) ) blst_p1_add_or_double_affine( pub, pub, key+rank );
122 0 : }
123 0 : blst_p1_cneg( pub, 1 );
124 0 : blst_p1_add_or_double( pub, full, pub );
125 0 : return pub;
126 0 : }
127 :
128 :
129 : void
130 : fd_bls_hash_msg( uchar const * msg,
131 : ulong msg_sz,
132 0 : blst_p2_affine * h ) {
133 0 : blst_p2 p[1];
134 0 : blst_hash_to_g2( p, msg, msg_sz, (uchar const *)FD_BLS_DST, FD_BLS_DST_SZ, NULL, 0UL );
135 0 : blst_p2_to_affine( h, p );
136 0 : }
137 :
138 : /* agg_pairing computes gt = e(pub,h) / e(G1,sig), which is the identity iff
139 : sig is a valid signature on h under pub. */
140 :
141 : static blst_fp12 *
142 : agg_pairing( blst_fp12 * gt,
143 : blst_p2_affine const * h,
144 : blst_p1 const * pub,
145 0 : blst_p2 const * sig ) {
146 0 : blst_p1_affine a[2];
147 0 : blst_p2_affine b[2];
148 0 : blst_p1_affine const * aptr[2];
149 0 : blst_p2_affine const * bptr[2];
150 0 : ulong n = 0UL;
151 0 : if( FD_LIKELY( !blst_p1_is_inf( pub ) && !blst_p2_affine_is_inf( h ) ) ) { blst_p1_to_affine( a+n, pub ); b[n] = *h; aptr[n] = a+n; bptr[n] = b+n; n++; }
152 0 : if( FD_LIKELY( !blst_p2_is_inf( sig ) ) ) { a[n] = BLS12_381_NEG_G1; blst_p2_to_affine( b+n, sig ); aptr[n] = a+n; bptr[n] = b+n; n++; }
153 0 : if( FD_UNLIKELY( !n ) ) { *gt = *blst_fp12_one(); return gt; }
154 0 : blst_miller_loop_n( gt, bptr, aptr, n );
155 0 : blst_final_exp( gt, gt );
156 0 : return gt;
157 0 : }
158 :
159 : int
160 : fd_bls_agg_verify_hashed( blst_p2_affine const * h,
161 : blst_p1 const * pub,
162 0 : blst_p2 const * sig ) {
163 0 : if( FD_UNLIKELY( blst_p2_affine_is_inf( h ) || blst_p1_is_inf( pub ) || blst_p2_is_inf( sig ) ) ) return 0;
164 0 : blst_fp12 gt[1];
165 0 : return !!blst_fp12_is_one( agg_pairing( gt, h, pub, sig ) );
166 0 : }
167 :
168 : int
169 : fd_bls_agg_verify( uchar const * msg,
170 : ulong msg_sz,
171 : blst_p1 const * pub,
172 0 : blst_p2 const * sig ) {
173 0 : if( FD_UNLIKELY( blst_p1_is_inf( pub ) || blst_p2_is_inf( sig ) ) ) return 0;
174 0 : blst_p2_affine h[1];
175 0 : fd_bls_hash_msg( msg, msg_sz, h );
176 0 : return fd_bls_agg_verify_hashed( h, pub, sig );
177 0 : }
178 :
179 : static fd_bls_set_t *
180 : verify_linear_hashed( fd_bls_agg_t const * agg,
181 : blst_p2_affine const * h,
182 : fd_bls_pub_t const * pub,
183 : fd_bls_sig_t const * sig,
184 0 : fd_bls_set_t * bad ) {
185 0 : fd_bls_set_null( bad );
186 0 : for( ulong rank = fd_bls_set_const_iter_init( agg->set );
187 0 : !fd_bls_set_const_iter_done( rank );
188 0 : rank = fd_bls_set_const_iter_next( agg->set, rank ) ) {
189 0 : blst_p1 p; blst_p1_from_affine( &p, pub+rank );
190 0 : blst_p2 s; blst_p2_from_affine( &s, sig+rank );
191 0 : if( FD_UNLIKELY( !fd_bls_agg_verify_hashed( h, &p, &s ) ) ) fd_bls_set_insert( bad, rank );
192 0 : }
193 0 : return bad;
194 0 : }
195 :
196 : /* verify_bisect_rec descends the contiguous run ranks[ lo, hi ) of
197 : the signer list. pub and sig are the signers' keys and signatures
198 : gathered into signer-list (not rank) order. The caller
199 : guarantees gt!=1, i.e. the run contains a bad signer. p, s and gt
200 : are consumed by the descent, which lets both halves be derived
201 : without copying the parent: the hi run's sums are p-lp and its gt
202 : is conj( lgt*conj(gt) ) = conj(lgt)*gt. */
203 :
204 : #define BISECT_DEPTH_MAX (11UL)
205 : FD_STATIC_ASSERT( FD_BLS_SET_MAX<=(1UL<<BISECT_DEPTH_MAX), bisect_depth );
206 :
207 : static void
208 : verify_bisect_rec( blst_p2_affine const * h,
209 : fd_bls_pub_t const * pub,
210 : fd_bls_sig_t const * sig,
211 : ushort const * ranks,
212 : ushort lo,
213 : ushort hi,
214 : blst_p1 * p,
215 : blst_p2 * s,
216 : blst_fp12 * gt,
217 0 : fd_bls_set_t * bad ) {
218 0 : if( hi-lo==1 ) { fd_bls_set_insert( bad, ranks[ lo ] ); return; }
219 :
220 0 : ushort mid = (ushort)( lo + ( (ulong)hi-(ulong)lo )/2UL );
221 :
222 : /* Sum the lo half's pub and sig points in one batch each. */
223 0 : fd_bls_pub_t const * pub_sum[2] = { pub+lo, NULL };
224 0 : fd_bls_sig_t const * sig_sum[2] = { sig+lo, NULL };
225 0 : blst_p1 lp[1]; blst_p2 ls[1];
226 0 : blst_p1s_add( lp, pub_sum, (size_t)( (ulong)mid-(ulong)lo ) );
227 0 : blst_p2s_add( ls, sig_sum, (size_t)( (ulong)mid-(ulong)lo ) );
228 :
229 0 : blst_p1_cneg( p, 1 );
230 0 : blst_p2_cneg( s, 1 );
231 0 : blst_p1 hp[1]; blst_p2 hs[1];
232 0 : blst_p1_add_or_double( hp, lp, p ); blst_p1_cneg( hp, 1 ); /* hp = p-lp */
233 0 : blst_p2_add_or_double( hs, ls, s ); blst_p2_cneg( hs, 1 ); /* hs = s-ls */
234 :
235 0 : blst_fp12 lgt[1];
236 0 : agg_pairing( lgt, h, lp, ls );
237 0 : blst_fp12_conjugate( gt );
238 0 : blst_fp12 hgt[1];
239 0 : blst_fp12_mul( hgt, lgt, gt );
240 0 : blst_fp12_conjugate( hgt ); /* hgt = conj(lgt)*gt */
241 :
242 0 : if( FD_LIKELY( !blst_fp12_is_one( lgt ) ) ) verify_bisect_rec( h, pub, sig, ranks, lo, mid, lp, ls, lgt, bad );
243 0 : if( FD_LIKELY( !blst_fp12_is_one( hgt ) ) ) verify_bisect_rec( h, pub, sig, ranks, mid, hi, hp, hs, hgt, bad );
244 0 : }
245 :
246 : static fd_bls_set_t *
247 : verify_bisect_hashed( fd_bls_agg_t const * agg,
248 : blst_p2_affine const * h,
249 : fd_bls_pub_t const * pub,
250 : fd_bls_sig_t const * sig,
251 0 : fd_bls_set_t * bad ) {
252 0 : fd_bls_set_null( bad );
253 0 : if( FD_UNLIKELY( fd_bls_set_is_null( agg->set ) ) ) return bad;
254 :
255 : /* a valid aggregate, the common case */
256 0 : blst_p1 p[1]; p[ 0 ] = agg->pub; /* consumed by the descent */
257 0 : blst_p2 s[1]; s[ 0 ] = agg->sig;
258 0 : blst_fp12 gt[1];
259 0 : agg_pairing( gt, h, &agg->pub, &agg->sig );
260 0 : if( FD_LIKELY( blst_fp12_is_one( gt ) ) ) return bad;
261 :
262 : /* gather the signers into a contiguous run so each half of the
263 : descent is a linear range */
264 0 : ushort ranks [ FD_BLS_SET_MAX ];
265 0 : fd_bls_pub_t pub_run[ FD_BLS_SET_MAX ];
266 0 : fd_bls_sig_t sig_run[ FD_BLS_SET_MAX ];
267 0 : ulong cnt = 0UL;
268 0 : for( ulong rank = fd_bls_set_const_iter_init( agg->set );
269 0 : !fd_bls_set_const_iter_done( rank );
270 0 : rank = fd_bls_set_const_iter_next( agg->set, rank ) ) {
271 0 : ranks [ cnt ] = (ushort)rank;
272 0 : pub_run[ cnt ] = pub[ rank ];
273 0 : sig_run[ cnt ] = sig[ rank ];
274 0 : cnt++;
275 0 : }
276 0 : verify_bisect_rec( h, pub_run, sig_run, ranks, 0, (ushort)cnt, p, s, gt, bad );
277 0 : return bad;
278 0 : }
279 :
280 : fd_bls_set_t *
281 : fd_bls_agg_verify_linear( fd_bls_agg_t const * agg,
282 : uchar const * msg,
283 : ulong msg_sz,
284 : fd_bls_pub_t const * pub,
285 : fd_bls_sig_t const * sig,
286 0 : fd_bls_set_t * bad ) {
287 0 : blst_p2_affine h[1];
288 0 : fd_bls_hash_msg( msg, msg_sz, h );
289 0 : return verify_linear_hashed( agg, h, pub, sig, bad );
290 0 : }
291 :
292 : fd_bls_set_t *
293 : fd_bls_agg_verify_bisect( fd_bls_agg_t const * agg,
294 : uchar const * msg,
295 : ulong msg_sz,
296 : fd_bls_pub_t const * pub,
297 : fd_bls_sig_t const * sig,
298 0 : fd_bls_set_t * bad ) {
299 0 : blst_p2_affine h[1];
300 0 : fd_bls_hash_msg( msg, msg_sz, h );
301 0 : return verify_bisect_hashed( agg, h, pub, sig, bad );
302 0 : }
303 :
304 : int
305 : fd_bls_agg_verify_subtract( fd_bls_agg_t * agg,
306 : uchar const * msg,
307 : ulong msg_sz,
308 : fd_bls_pub_t const * pub,
309 : fd_bls_sig_t const * sig,
310 0 : fd_bls_set_t * bad ) {
311 0 : blst_p2_affine h[1];
312 0 : fd_bls_hash_msg( msg, msg_sz, h );
313 0 : verify_bisect_hashed( agg, h, pub, sig, bad );
314 0 : if( FD_UNLIKELY( !fd_bls_set_is_null( bad ) ) ) {
315 0 : fd_bls_agg_t sub = { 0 };
316 0 : fd_bls_agg_construct( &sub, pub, sig, bad );
317 0 : blst_p1_cneg( &sub.pub, 1 ); blst_p1_add_or_double( &agg->pub, &agg->pub, &sub.pub );
318 0 : blst_p2_cneg( &sub.sig, 1 ); blst_p2_add_or_double( &agg->sig, &agg->sig, &sub.sig );
319 0 : fd_bls_set_subtract( agg->set, agg->set, bad );
320 0 : }
321 : /* an aggregate whose keys cancel to infinity carries no stake even
322 : when every signer is individually valid */
323 0 : if( FD_UNLIKELY( blst_p1_is_inf( &agg->pub ) ) ) return -1;
324 0 : return 0;
325 0 : }
|
