Line data Source code
1 : #include "fd_rangeproofs.h"
2 :
3 : /* https://github.com/solana-program/zk-elgamal-proof/blob/zk-sdk%40v5.0.1/zk-sdk/src/range_proof/mod.rs#L509 */
4 : void
5 : fd_rangeproofs_delta(
6 : uchar delta[ 32 ],
7 : ulong const nm,
8 : uchar const y[ 32 ],
9 : uchar const z[ 32 ],
10 : uchar const zz[ 32 ],
11 : uchar const bit_lengths[ 1 ],
12 : uchar const batch_len
13 30 : ) {
14 30 : uchar exp_y[ 32 ];
15 30 : uchar sum_of_powers_y[ 32 ];
16 30 : fd_memcpy( exp_y, y, 32 );
17 30 : fd_curve25519_scalar_add( sum_of_powers_y, y, fd_curve25519_scalar_one );
18 210 : for( ulong i=nm; i>2; i/=2 ) {
19 180 : fd_curve25519_scalar_mul ( exp_y, exp_y, exp_y );
20 180 : fd_curve25519_scalar_muladd( sum_of_powers_y, exp_y, sum_of_powers_y, sum_of_powers_y );
21 180 : }
22 30 : fd_curve25519_scalar_sub( delta, z, zz );
23 30 : fd_curve25519_scalar_mul( delta, delta, sum_of_powers_y );
24 :
25 30 : uchar neg_exp_z[ 32 ];
26 30 : uchar sum_2[ 32 ];
27 30 : fd_curve25519_scalar_neg( neg_exp_z, zz );
28 270 : for( ulong i=0; i<batch_len; i++ ) {
29 240 : fd_memset( sum_2, 0, 32 );
30 : //TODO currently assuming that bit_length[i] is multiple of 8 - need to fix cases: 1, 2, 4
31 240 : fd_memset( sum_2, 0xFF, bit_lengths[i] / 8 );
32 240 : fd_curve25519_scalar_mul ( neg_exp_z, neg_exp_z, z );
33 240 : fd_curve25519_scalar_muladd( delta, neg_exp_z, sum_2, delta );
34 240 : }
35 30 : }
36 :
37 : /* https://github.com/solana-program/zk-elgamal-proof/blob/zk-sdk%40v5.0.1/zk-sdk/src/range_proof/mod.rs#L324 */
38 : int
39 : fd_rangeproofs_verify(
40 : fd_rangeproofs_range_proof_t const * range_proof,
41 : fd_rangeproofs_ipp_proof_t const * ipp_proof,
42 : uchar const commitments [ 32 ],
43 : uchar const bit_lengths [ 1 ],
44 : uchar const batch_len,
45 36 : fd_merlin_transcript_t * transcript ) {
46 :
47 : /*
48 : We need to verify a range proof, by computing a large MSM.
49 :
50 : We store points in the following array.
51 : Indexes are the common example of u128 batch range proof with batch_len==4,
52 : used in SPL confidential transfers.
53 :
54 : points
55 : 0 G
56 : 1 H
57 : 2 S
58 : 3 T_1
59 : 4 T_2
60 : 5 commitments[ 0 ]
61 : ...
62 : 8 commitments[ 3 ] // 4 == batch_len (example)
63 : 9 L_vec[ 0 ]
64 : ...
65 : 15 L_vec[ 6 ] // 7 == log2( 128 )
66 : 16 R_vec[ 0 ]
67 : ...
68 : 22 R_vec[ 6 ] // 7 == log2( 128 )
69 : 23 generators_H[ 0 ]
70 : ...
71 : 150 generators_H[ 127 ] // 128 generators
72 : 151 generators_G[ 0 ]
73 : ...
74 : 278 generators_G[ 127 ] // 128 generators
75 : ------------------------------------------------------ MSM
76 : A
77 :
78 : As final check we test that the result of the MSM == -A.
79 : We could negate all scalars, but that'd make it more complex to debug
80 : against Rust rangeproofs / Solana, in case of issues, and the marginal
81 : cost of negating A is negligible.
82 :
83 : This implementation has a few differences compared to the Rust implementation.
84 :
85 : - We need to support batched range proofs for u64, u128 and u256.
86 : Rust does dynamic allocations. This implementation statically allocates
87 : for u256 (a total of <64kB) and dynamically handles u64 and u128.
88 :
89 : - This implementation limits memory copies.
90 : Input data arrives from the Solana tx in a certain order and essentially
91 : includes compressed points and scalars.
92 : We allocate enough scalars and (uncompressed) points for the MSM.
93 : As we parse input data, we compute scalars and decompress points
94 : directly into the memory region used by MSM (layout shown above).
95 :
96 : - Points and scalars are in a different order compared to Rust,
97 : but their value is the same. The order has no particular meaning,
98 : it just seemed more convenient.
99 :
100 : - Range proof depends interally on innerproduct proof (ipp).
101 : ipp needs to invert logn elements (called u_i).
102 : range proof, in addition, needs to invert y.
103 : Rust uses batch inversion to invert all u_i more efficiently.
104 : We also include y in the batch, to save 1 inversion (~300 mul).
105 :
106 : - ipp generates n scalars s_i, from which range proof derives 2n scalars
107 : for generators_G and generators_H.
108 : The scalars for generators_G are just a rescaling of s_i,
109 : while the scalars for generators_H are a bit more complex.
110 : We store s_i in the same memory region of generators_G scalars,
111 : then use them to compute generators_H scalars, and finally we do
112 : the rescaling. This saves 8kB of stack.
113 : */
114 :
115 : /* Capital LOGN, N are used to allocate memory.
116 : Lowercase logn, n are used at runtime.
117 : This implementation allocates memory to support u256, and
118 : at runtime can verify u64, u128 and u256 range proofs. */
119 36 : #define LOGN 8
120 36 : #define N (1 << LOGN)
121 36 : #define MAX (2*N + 2*LOGN + 5 + FD_RANGEPROOFS_MAX_COMMITMENTS)
122 :
123 36 : const ulong logn = ipp_proof->logn;
124 36 : const ulong n = 1UL << logn;
125 :
126 : /* https://github.com/solana-program/zk-elgamal-proof/blob/zk-sdk%40v5.0.1/zk-sdk/src/range_proof/mod.rs#L330-L338
127 : These checks are already done in batched_range_proof_context_try_into() */
128 :
129 : /* https://github.com/solana-program/zk-elgamal-proof/blob/zk-sdk%40v5.0.1/zk-sdk/src/range_proof/mod.rs#L340-L344
130 : total bit length (nm) should be a power of 2, and equal to the sz of the range proof.
131 : since n by definition is a power of 2, we can just check nm == n. */
132 36 : ulong nm = 0;
133 324 : for( uchar i=0; i<batch_len; i++ ) {
134 288 : nm += bit_lengths[i];
135 288 : }
136 36 : if( FD_UNLIKELY( nm != n ) ) {
137 0 : return FD_RANGEPROOFS_ERROR;
138 0 : }
139 :
140 : /* Validate all inputs */
141 36 : uchar scalars[ MAX*32 ];
142 36 : fd_ristretto255_point_t points[ MAX ];
143 36 : fd_ristretto255_point_t a_res[ 1 ];
144 36 : fd_ristretto255_point_t res[ 1 ];
145 :
146 36 : if( FD_UNLIKELY( fd_curve25519_scalar_validate( range_proof->tx )==NULL ) ) {
147 0 : return FD_RANGEPROOFS_ERROR;
148 0 : }
149 36 : if( FD_UNLIKELY( fd_curve25519_scalar_validate( range_proof->tx_blinding )==NULL ) ) {
150 0 : return FD_RANGEPROOFS_ERROR;
151 0 : }
152 36 : if( FD_UNLIKELY( fd_curve25519_scalar_validate( range_proof->e_blinding )==NULL ) ) {
153 0 : return FD_RANGEPROOFS_ERROR;
154 0 : }
155 36 : if( FD_UNLIKELY( fd_curve25519_scalar_validate( ipp_proof->a )==NULL ) ) {
156 0 : return FD_RANGEPROOFS_ERROR;
157 0 : }
158 36 : if( FD_UNLIKELY( fd_curve25519_scalar_validate( ipp_proof->b )==NULL ) ) {
159 0 : return FD_RANGEPROOFS_ERROR;
160 0 : }
161 :
162 36 : fd_ristretto255_point_set( &points[0], fd_rangeproofs_basepoint_G );
163 36 : fd_ristretto255_point_set( &points[1], fd_rangeproofs_basepoint_H );
164 36 : if( FD_UNLIKELY( fd_ristretto255_point_decompress( a_res, range_proof->a )==NULL ) ) {
165 0 : return FD_RANGEPROOFS_ERROR;
166 0 : }
167 36 : if( FD_UNLIKELY( fd_ristretto255_point_decompress( &points[2], range_proof->s )==NULL ) ) {
168 0 : return FD_RANGEPROOFS_ERROR;
169 0 : }
170 36 : if( FD_UNLIKELY( fd_ristretto255_point_decompress( &points[3], range_proof->t1 )==NULL ) ) {
171 0 : return FD_RANGEPROOFS_ERROR;
172 0 : }
173 36 : if( FD_UNLIKELY( fd_ristretto255_point_decompress( &points[4], range_proof->t2 )==NULL ) ) {
174 0 : return FD_RANGEPROOFS_ERROR;
175 0 : }
176 36 : ulong idx = 5;
177 276 : for( ulong i=0; i<batch_len; i++, idx++ ) {
178 246 : if( FD_UNLIKELY( fd_ristretto255_point_decompress( &points[ idx ], &commitments[ i*32 ] )==NULL ) ) {
179 6 : return FD_RANGEPROOFS_ERROR;
180 6 : }
181 246 : }
182 240 : for( ulong i=0; i<logn; i++, idx++ ) {
183 210 : if( FD_UNLIKELY( fd_ristretto255_point_decompress( &points[ idx ], ipp_proof->vecs[ i ].l )==NULL ) ) {
184 0 : return FD_RANGEPROOFS_ERROR;
185 0 : }
186 210 : }
187 240 : for( ulong i=0; i<logn; i++, idx++ ) {
188 210 : if( FD_UNLIKELY( fd_ristretto255_point_decompress( &points[ idx ], ipp_proof->vecs[ i ].r )==NULL ) ) {
189 0 : return FD_RANGEPROOFS_ERROR;
190 0 : }
191 210 : }
192 30 : fd_memcpy( &points[ idx ], fd_rangeproofs_generators_H, n*sizeof(fd_ristretto255_point_t) );
193 30 : fd_memcpy( &points[ idx+n ], fd_rangeproofs_generators_G, n*sizeof(fd_ristretto255_point_t) );
194 :
195 : /* Finalize transcript and extract challenges */
196 :
197 : /* https://github.com/solana-program/zk-elgamal-proof/blob/zk-sdk%40v5.0.1/zk-sdk/src/range_proof/mod.rs#L349 */
198 30 : fd_rangeproofs_transcript_domsep_range_proof( transcript, nm );
199 :
200 : /* https://github.com/solana-program/zk-elgamal-proof/blob/zk-sdk%40v5.0.1/zk-sdk/src/range_proof/mod.rs#L351-L387 */
201 30 : int val = FD_TRANSCRIPT_SUCCESS;
202 30 : val |= fd_rangeproofs_transcript_validate_and_append_point( transcript, FD_TRANSCRIPT_LITERAL("A"), range_proof->a);
203 30 : val |= fd_rangeproofs_transcript_validate_and_append_point( transcript, FD_TRANSCRIPT_LITERAL("S"), range_proof->s);
204 :
205 : /* We need to invert a bunch of values, we collect them all in a single buffer to use batch inversion. */
206 30 : uchar batchinv_in [ 32*(1+LOGN) ];
207 30 : uchar batchinv_out[ 32*(1+LOGN) ];
208 30 : uchar allinv[ 32 ];
209 :
210 30 : uchar *y_inv = batchinv_out;
211 30 : uchar *y = batchinv_in;
212 30 : uchar z[ 32 ];
213 30 : fd_rangeproofs_transcript_challenge_scalar( y, transcript, FD_TRANSCRIPT_LITERAL("y") );
214 30 : fd_rangeproofs_transcript_challenge_scalar( z, transcript, FD_TRANSCRIPT_LITERAL("z") );
215 :
216 30 : val |= fd_rangeproofs_transcript_validate_and_append_point( transcript, FD_TRANSCRIPT_LITERAL("T_1"), range_proof->t1);
217 30 : val |= fd_rangeproofs_transcript_validate_and_append_point( transcript, FD_TRANSCRIPT_LITERAL("T_2"), range_proof->t2);
218 30 : if( FD_UNLIKELY( val != FD_TRANSCRIPT_SUCCESS ) ) {
219 0 : return FD_RANGEPROOFS_ERROR;
220 0 : }
221 :
222 30 : uchar x[ 32 ];
223 30 : fd_rangeproofs_transcript_challenge_scalar( x, transcript, FD_TRANSCRIPT_LITERAL("x") );
224 :
225 30 : fd_rangeproofs_transcript_append_scalar( transcript, FD_TRANSCRIPT_LITERAL("t_x"), range_proof->tx);
226 30 : fd_rangeproofs_transcript_append_scalar( transcript, FD_TRANSCRIPT_LITERAL("t_x_blinding"), range_proof->tx_blinding);
227 30 : fd_rangeproofs_transcript_append_scalar( transcript, FD_TRANSCRIPT_LITERAL("e_blinding"), range_proof->e_blinding);
228 :
229 30 : uchar w[ 32 ];
230 30 : uchar _c[ 32 ];
231 30 : uchar d[ 32 ];
232 30 : fd_rangeproofs_transcript_challenge_scalar( w, transcript, FD_TRANSCRIPT_LITERAL("w") );
233 : /* The challenge `c` is a legacy component from an older implementation.
234 : It is now unused, but is kept here for backward compatibility. */
235 30 : fd_rangeproofs_transcript_challenge_scalar( _c, transcript, FD_TRANSCRIPT_LITERAL("c") );
236 :
237 : /* Inner Product (sub)Proof */
238 30 : uchar *u = &batchinv_in [ 32 ]; // skip y
239 30 : uchar *u_inv = &batchinv_out[ 32 ]; // skip y_inv
240 : /* https://github.com/solana-program/zk-elgamal-proof/blob/zk-sdk%40v5.0.1/zk-sdk/src/range_proof/mod.rs#L377 */
241 30 : {
242 : /* https://github.com/solana-program/zk-elgamal-proof/blob/main/zk-sdk/src/range_proof/inner_product.rs#L246 */
243 30 : fd_rangeproofs_transcript_domsep_inner_product( transcript, nm );
244 :
245 240 : for( ulong i=0; i<logn; i++ ) {
246 210 : val |= fd_rangeproofs_transcript_validate_and_append_point( transcript, FD_TRANSCRIPT_LITERAL("L"), ipp_proof->vecs[ i ].l);
247 210 : val |= fd_rangeproofs_transcript_validate_and_append_point( transcript, FD_TRANSCRIPT_LITERAL("R"), ipp_proof->vecs[ i ].r);
248 210 : if( FD_UNLIKELY( val != FD_TRANSCRIPT_SUCCESS ) ) {
249 0 : return FD_RANGEPROOFS_ERROR;
250 0 : }
251 210 : fd_rangeproofs_transcript_challenge_scalar( &u[ i*32 ], transcript, FD_TRANSCRIPT_LITERAL("u") );
252 210 : }
253 30 : fd_curve25519_scalar_batch_inv( batchinv_out, allinv, batchinv_in, logn+1 );
254 30 : }
255 :
256 30 : fd_rangeproofs_transcript_append_scalar( transcript, FD_TRANSCRIPT_LITERAL("ipp_a"), ipp_proof->a );
257 30 : fd_rangeproofs_transcript_append_scalar( transcript, FD_TRANSCRIPT_LITERAL("ipp_b"), ipp_proof->b );
258 :
259 : /* https://github.com/solana-program/zk-elgamal-proof/blob/zk-sdk%40v5.0.1/zk-sdk/src/range_proof/mod.rs#L387 */
260 30 : fd_rangeproofs_transcript_challenge_scalar( d, transcript, FD_TRANSCRIPT_LITERAL("d") );
261 :
262 : /* Compute scalars */
263 :
264 : /* https://github.com/solana-program/zk-elgamal-proof/blob/zk-sdk%40v5.0.1/zk-sdk/src/range_proof/mod.rs#L391-L411 */
265 :
266 : // H: - ( eb + c t_xb )
267 30 : uchar const *eb = range_proof->e_blinding;
268 30 : uchar const *txb = range_proof->tx_blinding;
269 30 : fd_curve25519_scalar_muladd( &scalars[ 1*32 ], d, txb, eb );
270 30 : fd_curve25519_scalar_neg( &scalars[ 1*32 ], &scalars[ 1*32 ] );
271 :
272 : // S: x
273 : // T_1: c x
274 : // T_2: c x^2
275 30 : fd_curve25519_scalar_set( &scalars[ 2*32 ], x );
276 30 : fd_curve25519_scalar_mul( &scalars[ 3*32 ], d, x );
277 30 : fd_curve25519_scalar_mul( &scalars[ 4*32 ], &scalars[ 3*32 ], x );
278 :
279 : // commitments: c z^2, c z^3 ...
280 30 : uchar zz[ 32 ];
281 30 : fd_curve25519_scalar_mul( zz, z, z );
282 30 : fd_curve25519_scalar_mul( &scalars[ 5*32 ], zz, d );
283 30 : idx = 6;
284 240 : for( ulong i=1; i<batch_len; i++, idx++ ) {
285 210 : fd_curve25519_scalar_mul( &scalars[ idx*32 ], &scalars[ (idx-1)*32 ], z );
286 210 : }
287 :
288 : // L_vec: u0^2, u1^2...
289 : // R_vec: 1/u0^2, 1/u1^2...
290 30 : uchar *u_sq = &scalars[ idx*32 ];
291 240 : for( ulong i=0; i<logn; i++, idx++ ) {
292 210 : fd_curve25519_scalar_mul( &scalars[ idx*32 ], &u[ i*32 ], &u[ i*32 ] );
293 210 : }
294 240 : for( ulong i=0; i<logn; i++, idx++ ) {
295 210 : fd_curve25519_scalar_mul( &scalars[ idx*32 ], &u_inv[ i*32 ], &u_inv[ i*32 ] );
296 210 : }
297 :
298 : // s_i for generators_G, generators_H
299 30 : uchar *s = &scalars[ (idx+n)*32 ];
300 30 : fd_curve25519_scalar_mul( &s[ 0*32 ], allinv, y ); // allinv also contains 1/y
301 : // s[i] = s[ i-k ] * u[ k+1 ]^2 (k the "next power of 2" wrt i)
302 239 : for( ulong k=0; k<logn; k++ ) {
303 209 : ulong powk = (1UL << k);
304 4657 : for( ulong j=0; j<powk; j++ ) {
305 4448 : ulong i = powk + j;
306 4448 : fd_curve25519_scalar_mul( &s[ i*32 ], &s[ j*32 ], &u_sq[ (logn-1-k)*32 ] );
307 4448 : }
308 209 : }
309 :
310 : // generators_H: (-a * s_i) + (-z)
311 30 : uchar const *a = ipp_proof->a;
312 30 : uchar const *b = ipp_proof->b;
313 30 : uchar minus_b[ 32 ];
314 30 : uchar exp_z[ 32 ];
315 30 : uchar exp_y_inv[ 32 ];
316 30 : uchar z_and_2[ 32 ];
317 30 : fd_curve25519_scalar_neg( minus_b, b );
318 30 : fd_memcpy( exp_z, zz, 32 );
319 30 : fd_memcpy( z_and_2, exp_z, 32 );
320 30 : fd_memcpy( exp_y_inv, y, 32 ); //TODO: remove 2 unnecessary muls
321 4508 : for( ulong i=0, j=0, m=0; i<n; i++, j++, idx++ ) {
322 4478 : if( j == bit_lengths[m] ) {
323 210 : j = 0;
324 210 : m++;
325 210 : fd_curve25519_scalar_mul ( exp_z, exp_z, z );
326 210 : fd_memcpy( z_and_2, exp_z, 32 );
327 210 : }
328 4478 : if( j != 0 ) {
329 4238 : fd_curve25519_scalar_add ( z_and_2, z_and_2, z_and_2 );
330 4238 : }
331 4478 : fd_curve25519_scalar_mul ( exp_y_inv, exp_y_inv, y_inv );
332 4478 : fd_curve25519_scalar_muladd( &scalars[ idx*32 ], &s[ (n-1-i)*32 ], minus_b, z_and_2 );
333 4478 : fd_curve25519_scalar_muladd( &scalars[ idx*32 ], &scalars[ idx*32 ], exp_y_inv, z );
334 4478 : }
335 :
336 : // generators_G: (-a * s_i) + (-z)
337 30 : uchar minus_z[ 32 ];
338 30 : uchar minus_a[ 32 ];
339 30 : fd_curve25519_scalar_neg( minus_z, z );
340 30 : fd_curve25519_scalar_neg( minus_a, a );
341 4509 : for( ulong i=0; i<n; i++, idx++ ) {
342 4479 : fd_curve25519_scalar_muladd( &scalars[ idx*32 ], &s[ i*32 ], minus_a, minus_z );
343 4479 : }
344 :
345 : // G
346 : // w * (self.t_x - a * b) + c * (delta(&bit_lengths, &y, &z) - self.t_x)
347 30 : uchar delta[ 32 ];
348 30 : fd_rangeproofs_delta( delta, nm, y, z, zz, bit_lengths, batch_len );
349 30 : fd_curve25519_scalar_muladd( &scalars[ 0 ], minus_a, b, range_proof->tx );
350 30 : fd_curve25519_scalar_sub( delta, delta, range_proof->tx );
351 30 : fd_curve25519_scalar_mul( delta, delta, d );
352 30 : fd_curve25519_scalar_muladd( &scalars[ 0 ], &scalars[ 0 ], w, delta );
353 :
354 : /* Compute the final MSM */
355 :
356 : /* https://github.com/solana-program/zk-elgamal-proof/blob/zk-sdk%40v5.0.1/zk-sdk/src/range_proof/mod.rs#L415-L439 */
357 30 : fd_ristretto255_multi_scalar_mul( res, scalars, points, idx );
358 :
359 : /* https://github.com/solana-program/zk-elgamal-proof/blob/zk-sdk%40v5.0.1/zk-sdk/src/range_proof/mod.rs#L441-L445 */
360 30 : if( FD_LIKELY( fd_ristretto255_point_eq_neg( res, a_res ) ) ) {
361 12 : return FD_RANGEPROOFS_SUCCESS;
362 12 : }
363 18 : return FD_RANGEPROOFS_ERROR;
364 30 : #undef LOGN
365 30 : #undef N
366 30 : #undef MAX
367 30 : }
|
