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 0 : ) {
14 0 : uchar exp_y[ 32 ];
15 0 : uchar sum_of_powers_y[ 32 ];
16 0 : fd_memcpy( exp_y, y, 32 );
17 0 : fd_curve25519_scalar_add( sum_of_powers_y, y, fd_curve25519_scalar_one );
18 0 : for( ulong i=nm; i>2; i/=2 ) {
19 0 : fd_curve25519_scalar_mul ( exp_y, exp_y, exp_y );
20 0 : fd_curve25519_scalar_muladd( sum_of_powers_y, exp_y, sum_of_powers_y, sum_of_powers_y );
21 0 : }
22 0 : fd_curve25519_scalar_sub( delta, z, zz );
23 0 : fd_curve25519_scalar_mul( delta, delta, sum_of_powers_y );
24 :
25 0 : uchar neg_exp_z[ 32 ];
26 0 : uchar sum_2[ 32 ];
27 0 : fd_curve25519_scalar_neg( neg_exp_z, zz );
28 0 : 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 0 : fd_memset( sum_2, 0, 32 );
32 0 : fd_memset( sum_2, 0xFF, bit_lengths[i] / 8 );
33 0 : if( bit_lengths[i] % 8 ) {
34 0 : sum_2[ bit_lengths[i] / 8 ] = (uchar)( ( 1U << ( bit_lengths[i] % 8 ) ) - 1U );
35 0 : }
36 0 : fd_curve25519_scalar_mul ( neg_exp_z, neg_exp_z, z );
37 0 : fd_curve25519_scalar_muladd( delta, neg_exp_z, sum_2, delta );
38 0 : }
39 0 : }
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 [ 32 ],
47 : uchar const bit_lengths [ 1 ],
48 : uchar const batch_len,
49 0 : 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 interally 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 0 : #define LOGN 8
124 0 : #define N (1 << LOGN)
125 0 : #define MAX (2*N + 2*LOGN + 5 + FD_RANGEPROOFS_MAX_COMMITMENTS)
126 :
127 0 : const ulong logn = ipp_proof->logn;
128 0 : 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 0 : ulong nm = 0;
137 0 : for( uchar i=0; i<batch_len; i++ ) {
138 0 : nm += bit_lengths[i];
139 0 : }
140 0 : if( FD_UNLIKELY( nm != n ) ) {
141 0 : return FD_RANGEPROOFS_ERROR;
142 0 : }
143 :
144 : /* Validate all inputs */
145 0 : uchar scalars[ MAX*32 ];
146 0 : fd_ristretto255_point_t points[ MAX ];
147 0 : fd_ristretto255_point_t a_res[ 1 ];
148 0 : fd_ristretto255_point_t res[ 1 ];
149 :
150 0 : if( FD_UNLIKELY( fd_curve25519_scalar_validate( range_proof->tx )==NULL ) ) {
151 0 : return FD_RANGEPROOFS_ERROR;
152 0 : }
153 0 : if( FD_UNLIKELY( fd_curve25519_scalar_validate( range_proof->tx_blinding )==NULL ) ) {
154 0 : return FD_RANGEPROOFS_ERROR;
155 0 : }
156 0 : if( FD_UNLIKELY( fd_curve25519_scalar_validate( range_proof->e_blinding )==NULL ) ) {
157 0 : return FD_RANGEPROOFS_ERROR;
158 0 : }
159 0 : if( FD_UNLIKELY( fd_curve25519_scalar_validate( ipp_proof->a )==NULL ) ) {
160 0 : return FD_RANGEPROOFS_ERROR;
161 0 : }
162 0 : if( FD_UNLIKELY( fd_curve25519_scalar_validate( ipp_proof->b )==NULL ) ) {
163 0 : return FD_RANGEPROOFS_ERROR;
164 0 : }
165 :
166 0 : fd_ristretto255_point_set( &points[0], fd_rangeproofs_basepoint_G );
167 0 : fd_ristretto255_point_set( &points[1], fd_rangeproofs_basepoint_H );
168 0 : if( FD_UNLIKELY( fd_ristretto255_point_decompress( a_res, range_proof->a )==NULL ) ) {
169 0 : return FD_RANGEPROOFS_ERROR;
170 0 : }
171 0 : if( FD_UNLIKELY( fd_ristretto255_point_decompress( &points[2], range_proof->s )==NULL ) ) {
172 0 : return FD_RANGEPROOFS_ERROR;
173 0 : }
174 0 : if( FD_UNLIKELY( fd_ristretto255_point_decompress( &points[3], range_proof->t1 )==NULL ) ) {
175 0 : return FD_RANGEPROOFS_ERROR;
176 0 : }
177 0 : if( FD_UNLIKELY( fd_ristretto255_point_decompress( &points[4], range_proof->t2 )==NULL ) ) {
178 0 : return FD_RANGEPROOFS_ERROR;
179 0 : }
180 0 : ulong idx = 5;
181 0 : for( ulong i=0; i<batch_len; i++, idx++ ) {
182 0 : if( FD_UNLIKELY( fd_ristretto255_point_decompress( &points[ idx ], &commitments[ i*32 ] )==NULL ) ) {
183 0 : return FD_RANGEPROOFS_ERROR;
184 0 : }
185 0 : }
186 0 : for( ulong i=0; i<logn; i++, idx++ ) {
187 0 : if( FD_UNLIKELY( fd_ristretto255_point_decompress( &points[ idx ], ipp_proof->vecs[ i ].l )==NULL ) ) {
188 0 : return FD_RANGEPROOFS_ERROR;
189 0 : }
190 0 : }
191 0 : for( ulong i=0; i<logn; i++, idx++ ) {
192 0 : if( FD_UNLIKELY( fd_ristretto255_point_decompress( &points[ idx ], ipp_proof->vecs[ i ].r )==NULL ) ) {
193 0 : return FD_RANGEPROOFS_ERROR;
194 0 : }
195 0 : }
196 0 : fd_memcpy( &points[ idx ], fd_rangeproofs_generators_H, n*sizeof(fd_ristretto255_point_t) );
197 0 : 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 0 : 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 0 : int val = FD_TRANSCRIPT_SUCCESS;
206 0 : val |= fd_rangeproofs_transcript_validate_and_append_point( transcript, FD_TRANSCRIPT_LITERAL("A"), range_proof->a);
207 0 : 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 0 : uchar batchinv_in [ 32*(1+LOGN) ];
211 0 : uchar batchinv_out[ 32*(1+LOGN) ];
212 0 : uchar allinv[ 32 ];
213 :
214 0 : uchar *y_inv = batchinv_out;
215 0 : uchar *y = batchinv_in;
216 0 : uchar z[ 32 ];
217 0 : fd_rangeproofs_transcript_challenge_scalar( y, transcript, FD_TRANSCRIPT_LITERAL("y") );
218 0 : fd_rangeproofs_transcript_challenge_scalar( z, transcript, FD_TRANSCRIPT_LITERAL("z") );
219 :
220 0 : val |= fd_rangeproofs_transcript_validate_and_append_point( transcript, FD_TRANSCRIPT_LITERAL("T_1"), range_proof->t1);
221 0 : val |= fd_rangeproofs_transcript_validate_and_append_point( transcript, FD_TRANSCRIPT_LITERAL("T_2"), range_proof->t2);
222 0 : if( FD_UNLIKELY( val != FD_TRANSCRIPT_SUCCESS ) ) {
223 0 : return FD_RANGEPROOFS_ERROR;
224 0 : }
225 :
226 0 : uchar x[ 32 ];
227 0 : fd_rangeproofs_transcript_challenge_scalar( x, transcript, FD_TRANSCRIPT_LITERAL("x") );
228 :
229 0 : fd_rangeproofs_transcript_append_scalar( transcript, FD_TRANSCRIPT_LITERAL("t_x"), range_proof->tx);
230 0 : fd_rangeproofs_transcript_append_scalar( transcript, FD_TRANSCRIPT_LITERAL("t_x_blinding"), range_proof->tx_blinding);
231 0 : fd_rangeproofs_transcript_append_scalar( transcript, FD_TRANSCRIPT_LITERAL("e_blinding"), range_proof->e_blinding);
232 :
233 0 : uchar w[ 32 ];
234 0 : uchar _c[ 32 ];
235 0 : uchar d[ 32 ];
236 0 : 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 0 : fd_rangeproofs_transcript_challenge_scalar( _c, transcript, FD_TRANSCRIPT_LITERAL("c") );
240 :
241 : /* Inner Product (sub)Proof */
242 0 : uchar *u = &batchinv_in [ 32 ]; // skip y
243 0 : 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 0 : {
246 : /* https://github.com/solana-program/zk-elgamal-proof/blob/main/zk-sdk/src/range_proof/inner_product.rs#L246 */
247 0 : fd_rangeproofs_transcript_domsep_inner_product( transcript, nm );
248 :
249 0 : for( ulong i=0; i<logn; i++ ) {
250 0 : val |= fd_rangeproofs_transcript_validate_and_append_point( transcript, FD_TRANSCRIPT_LITERAL("L"), ipp_proof->vecs[ i ].l);
251 0 : val |= fd_rangeproofs_transcript_validate_and_append_point( transcript, FD_TRANSCRIPT_LITERAL("R"), ipp_proof->vecs[ i ].r);
252 0 : if( FD_UNLIKELY( val != FD_TRANSCRIPT_SUCCESS ) ) {
253 0 : return FD_RANGEPROOFS_ERROR;
254 0 : }
255 0 : fd_rangeproofs_transcript_challenge_scalar( &u[ i*32 ], transcript, FD_TRANSCRIPT_LITERAL("u") );
256 0 : }
257 0 : fd_curve25519_scalar_batch_inv( batchinv_out, allinv, batchinv_in, logn+1 );
258 0 : }
259 :
260 0 : fd_rangeproofs_transcript_append_scalar( transcript, FD_TRANSCRIPT_LITERAL("ipp_a"), ipp_proof->a );
261 0 : 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 0 : 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 0 : uchar const *eb = range_proof->e_blinding;
272 0 : uchar const *txb = range_proof->tx_blinding;
273 0 : fd_curve25519_scalar_muladd( &scalars[ 1*32 ], d, txb, eb );
274 0 : fd_curve25519_scalar_neg( &scalars[ 1*32 ], &scalars[ 1*32 ] );
275 :
276 : // S: x
277 : // T_1: c x
278 : // T_2: c x^2
279 0 : fd_curve25519_scalar_set( &scalars[ 2*32 ], x );
280 0 : fd_curve25519_scalar_mul( &scalars[ 3*32 ], d, x );
281 0 : fd_curve25519_scalar_mul( &scalars[ 4*32 ], &scalars[ 3*32 ], x );
282 :
283 : // commitments: c z^2, c z^3 ...
284 0 : uchar zz[ 32 ];
285 0 : fd_curve25519_scalar_mul( zz, z, z );
286 0 : fd_curve25519_scalar_mul( &scalars[ 5*32 ], zz, d );
287 0 : idx = 6;
288 0 : for( ulong i=1; i<batch_len; i++, idx++ ) {
289 0 : fd_curve25519_scalar_mul( &scalars[ idx*32 ], &scalars[ (idx-1)*32 ], z );
290 0 : }
291 :
292 : // L_vec: u0^2, u1^2...
293 : // R_vec: 1/u0^2, 1/u1^2...
294 0 : uchar *u_sq = &scalars[ idx*32 ];
295 0 : for( ulong i=0; i<logn; i++, idx++ ) {
296 0 : fd_curve25519_scalar_mul( &scalars[ idx*32 ], &u[ i*32 ], &u[ i*32 ] );
297 0 : }
298 0 : for( ulong i=0; i<logn; i++, idx++ ) {
299 0 : fd_curve25519_scalar_mul( &scalars[ idx*32 ], &u_inv[ i*32 ], &u_inv[ i*32 ] );
300 0 : }
301 :
302 : // s_i for generators_G, generators_H
303 0 : uchar *s = &scalars[ (idx+n)*32 ];
304 0 : 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 0 : for( ulong k=0; k<logn; k++ ) {
307 0 : ulong powk = (1UL << k);
308 0 : for( ulong j=0; j<powk; j++ ) {
309 0 : ulong i = powk + j;
310 0 : fd_curve25519_scalar_mul( &s[ i*32 ], &s[ j*32 ], &u_sq[ (logn-1-k)*32 ] );
311 0 : }
312 0 : }
313 :
314 : // generators_H: (-a * s_i) + (-z)
315 0 : uchar const *a = ipp_proof->a;
316 0 : uchar const *b = ipp_proof->b;
317 0 : uchar minus_b[ 32 ];
318 0 : uchar exp_z[ 32 ];
319 0 : uchar exp_y_inv[ 32 ];
320 0 : uchar z_and_2[ 32 ];
321 0 : fd_curve25519_scalar_neg( minus_b, b );
322 0 : fd_memcpy( exp_z, zz, 32 );
323 0 : fd_memcpy( z_and_2, exp_z, 32 );
324 0 : fd_memcpy( exp_y_inv, y, 32 ); //TODO: remove 2 unnecessary muls
325 0 : for( ulong i=0, j=0, m=0; i<n; i++, j++, idx++ ) {
326 0 : if( j == bit_lengths[m] ) {
327 0 : j = 0;
328 0 : m++;
329 0 : fd_curve25519_scalar_mul ( exp_z, exp_z, z );
330 0 : fd_memcpy( z_and_2, exp_z, 32 );
331 0 : }
332 0 : if( j != 0 ) {
333 0 : fd_curve25519_scalar_add ( z_and_2, z_and_2, z_and_2 );
334 0 : }
335 0 : fd_curve25519_scalar_mul ( exp_y_inv, exp_y_inv, y_inv );
336 0 : fd_curve25519_scalar_muladd( &scalars[ idx*32 ], &s[ (n-1-i)*32 ], minus_b, z_and_2 );
337 0 : fd_curve25519_scalar_muladd( &scalars[ idx*32 ], &scalars[ idx*32 ], exp_y_inv, z );
338 0 : }
339 :
340 : // generators_G: (-a * s_i) + (-z)
341 0 : uchar minus_z[ 32 ];
342 0 : uchar minus_a[ 32 ];
343 0 : fd_curve25519_scalar_neg( minus_z, z );
344 0 : fd_curve25519_scalar_neg( minus_a, a );
345 0 : for( ulong i=0; i<n; i++, idx++ ) {
346 0 : fd_curve25519_scalar_muladd( &scalars[ idx*32 ], &s[ i*32 ], minus_a, minus_z );
347 0 : }
348 :
349 : // G
350 : // w * (self.t_x - a * b) + c * (delta(&bit_lengths, &y, &z) - self.t_x)
351 0 : uchar delta[ 32 ];
352 0 : fd_rangeproofs_delta( delta, nm, y, z, zz, bit_lengths, batch_len );
353 0 : fd_curve25519_scalar_muladd( &scalars[ 0 ], minus_a, b, range_proof->tx );
354 0 : fd_curve25519_scalar_sub( delta, delta, range_proof->tx );
355 0 : fd_curve25519_scalar_mul( delta, delta, d );
356 0 : 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 0 : 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 0 : if( FD_LIKELY( fd_ristretto255_point_eq_neg( res, a_res ) ) ) {
365 0 : return FD_RANGEPROOFS_SUCCESS;
366 0 : }
367 0 : return FD_RANGEPROOFS_ERROR;
368 0 : #undef LOGN
369 0 : #undef N
370 0 : #undef MAX
371 0 : }
|
