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