sonobe/folding-schemes-solidity/templates/kzg10_verifier.askama.sol
folding-schemes-solidity/templates/kzg10_verifier.askama.solRaw
1{{ sdpx }}
2
3{{ pragma_version }}
4
5/**
6 * @author Privacy and Scaling Explorations team - pse.dev
7 * @dev Contains utility functions for ops in BN254; in G_1 mostly.
8 * @notice Forked from https://github.com/weijiekoh/libkzg/tree/master.
9 * Among others, a few of the changes we did on this fork were:
10 * - Templating the pragma version
11 * - Removing type wrappers and use uints instead
12 * - Performing changes on arg types
13 * - Update some of the `require` statements
14 * - Use the bn254 scalar field instead of checking for overflow on the babyjub prime
15 * - In batch checking, we compute auxiliary polynomials and their commitments at the same time.
16 */
17contract KZG10Verifier {
18
19 // prime of field F_p over which y^2 = x^3 + 3 is defined
20 uint256 public constant BN254_PRIME_FIELD =
21 21888242871839275222246405745257275088696311157297823662689037894645226208583;
22 uint256 public constant BN254_SCALAR_FIELD =
23 21888242871839275222246405745257275088548364400416034343698204186575808495617;
24
25 /**
26 * @notice Performs scalar multiplication in G_1.
27 * @param p G_1 point to multiply
28 * @param s Scalar to multiply by
29 * @return r G_1 point p multiplied by scalar s
30 */
31 function mulScalar(uint256[2] memory p, uint256 s) internal view returns (uint256[2] memory r) {
32 uint256[3] memory input;
33 input[0] = p[0];
34 input[1] = p[1];
35 input[2] = s;
36 bool success;
37 assembly {
38 success := staticcall(sub(gas(), 2000), 7, input, 0x60, r, 0x40)
39 switch success
40 case 0 { invalid() }
41 }
42 require(success, "bn254: scalar mul failed");
43 }
44
45 /**
46 * @notice Negates a point in G_1.
47 * @param p G_1 point to negate
48 * @return uint256[2] G_1 point -p
49 */
50 function negate(uint256[2] memory p) internal pure returns (uint256[2] memory) {
51 if (p[0] == 0 && p[1] == 0) {
52 return p;
53 }
54 return [p[0], BN254_PRIME_FIELD - (p[1] % BN254_PRIME_FIELD)];
55 }
56
57 /**
58 * @notice Adds two points in G_1.
59 * @param p1 G_1 point 1
60 * @param p2 G_1 point 2
61 * @return r G_1 point p1 + p2
62 */
63 function add(uint256[2] memory p1, uint256[2] memory p2) internal view returns (uint256[2] memory r) {
64 bool success;
65 uint256[4] memory input = [p1[0], p1[1], p2[0], p2[1]];
66 assembly {
67 success := staticcall(sub(gas(), 2000), 6, input, 0x80, r, 0x40)
68 switch success
69 case 0 { invalid() }
70 }
71
72 require(success, "bn254: point add failed");
73 }
74
75 /**
76 * @notice Computes the pairing check e(p1, p2) * e(p3, p4) == 1
77 * @dev Note that G_2 points a*i + b are encoded as two elements of F_p, (a, b)
78 * @param a_1 G_1 point 1
79 * @param a_2 G_2 point 1
80 * @param b_1 G_1 point 2
81 * @param b_2 G_2 point 2
82 * @return result true if pairing check is successful
83 */
84 function pairing(uint256[2] memory a_1, uint256[2][2] memory a_2, uint256[2] memory b_1, uint256[2][2] memory b_2)
85 internal
86 view
87 returns (bool result)
88 {
89 uint256[12] memory input = [
90 a_1[0],
91 a_1[1],
92 a_2[0][1], // imaginary part first
93 a_2[0][0],
94 a_2[1][1], // imaginary part first
95 a_2[1][0],
96 b_1[0],
97 b_1[1],
98 b_2[0][1], // imaginary part first
99 b_2[0][0],
100 b_2[1][1], // imaginary part first
101 b_2[1][0]
102 ];
103
104 uint256[1] memory out;
105 bool success;
106
107 assembly {
108 success := staticcall(sub(gas(), 2000), 8, input, 0x180, out, 0x20)
109 switch success
110 case 0 { invalid() }
111 }
112
113 require(success, "bn254: pairing failed");
114
115 return out[0] == 1;
116 }
117
118 uint256[2] G_1 = [
119 {{ g1.0[0] }},
120 {{ g1.0[1] }}
121 ];
122 uint256[2][2] G_2 = [
123 [
124 {{ g2.0[0][0] }},
125 {{ g2.0[0][1] }}
126 ],
127 [
128 {{ g2.0[1][0] }},
129 {{ g2.0[1][1] }}
130 ]
131 ];
132 uint256[2][2] VK = [
133 [
134 {{ vk.0[0][0] }},
135 {{ vk.0[0][1] }}
136 ],
137 [
138 {{ vk.0[1][0] }},
139 {{ vk.0[1][1] }}
140 ]
141 ];
142
143 uint256[2][{{ g1_crs_len }}] G1_CRS = [
144 {%- for (i, point) in g1_crs.iter().enumerate() %}
145 [
146 {{ point.0[0] }},
147 {{ point.0[1] }}
148 {% if loop.last -%}
149 ]
150 {%- else -%}
151 ],
152 {%- endif -%}
153 {% endfor -%}
154 ];
155
156 /**
157 * @notice Verifies a single point evaluation proof. Function name follows `ark-poly`.
158 * @dev To avoid ops in G_2, we slightly tweak how the verification is done.
159 * @param c G_1 point commitment to polynomial.
160 * @param pi G_1 point proof.
161 * @param x Value to prove evaluation of polynomial at.
162 * @param y Evaluation poly(x).
163 * @return result Indicates if KZG proof is correct.
164 */
165 function check(uint256[2] calldata c, uint256[2] calldata pi, uint256 x, uint256 y)
166 public
167 view
168 returns (bool result)
169 {
170 //
171 // we want to:
172 // 1. avoid gas intensive ops in G2
173 // 2. format the pairing check in line with what the evm opcode expects.
174 //
175 // we can do this by tweaking the KZG check to be:
176 //
177 // e(pi, vk - x * g2) = e(c - y * g1, g2) [initial check]
178 // e(pi, vk - x * g2) * e(c - y * g1, g2)^{-1} = 1
179 // e(pi, vk - x * g2) * e(-c + y * g1, g2) = 1 [bilinearity of pairing for all subsequent steps]
180 // e(pi, vk) * e(pi, -x * g2) * e(-c + y * g1, g2) = 1
181 // e(pi, vk) * e(-x * pi, g2) * e(-c + y * g1, g2) = 1
182 // e(pi, vk) * e(x * -pi - c + y * g1, g2) = 1 [done]
183 // |_ rhs_pairing _|
184 //
185 uint256[2] memory rhs_pairing =
186 add(mulScalar(negate(pi), x), add(negate(c), mulScalar(G_1, y)));
187 return pairing(pi, VK, rhs_pairing, G_2);
188 }
189
190 function evalPolyAt(uint256[] memory _coefficients, uint256 _index) public pure returns (uint256) {
191 uint256 m = BN254_SCALAR_FIELD;
192 uint256 result = 0;
193 uint256 powerOfX = 1;
194
195 for (uint256 i = 0; i < _coefficients.length; i++) {
196 uint256 coeff = _coefficients[i];
197 assembly {
198 result := addmod(result, mulmod(powerOfX, coeff, m), m)
199 powerOfX := mulmod(powerOfX, _index, m)
200 }
201 }
202 return result;
203 }
204
205 /**
206 * @notice Ensures that z(x) == 0 and l(x) == y for all x in x_vals and y in y_vals. It returns the commitment to z(x) and l(x).
207 * @param z_coeffs coefficients of the zero polynomial z(x) = (x - x_1)(x - x_2)...(x - x_n).
208 * @param l_coeffs coefficients of the lagrange polynomial l(x).
209 * @param x_vals x values to evaluate the polynomials at.
210 * @param y_vals y values to which l(x) should evaluate to.
211 * @return uint256[2] commitment to z(x).
212 * @return uint256[2] commitment to l(x).
213 */
214 function checkAndCommitAuxPolys(
215 uint256[] memory z_coeffs,
216 uint256[] memory l_coeffs,
217 uint256[] memory x_vals,
218 uint256[] memory y_vals
219 ) public view returns (uint256[2] memory, uint256[2] memory) {
220 // z(x) is of degree len(x_vals), it is a product of linear polynomials (x - x_i)
221 // l(x) is of degree len(x_vals) - 1
222 uint256[2] memory z_commit;
223 uint256[2] memory l_commit;
224 for (uint256 i = 0; i < x_vals.length; i++) {
225 z_commit = add(z_commit, mulScalar(G1_CRS[i], z_coeffs[i])); // update commitment to z(x)
226 l_commit = add(l_commit, mulScalar(G1_CRS[i], l_coeffs[i])); // update commitment to l(x)
227
228 uint256 eval_z = evalPolyAt(z_coeffs, x_vals[i]);
229 uint256 eval_l = evalPolyAt(l_coeffs, x_vals[i]);
230
231 require(eval_z == 0, "checkAndCommitAuxPolys: wrong zero poly");
232 require(eval_l == y_vals[i], "checkAndCommitAuxPolys: wrong lagrange poly");
233 }
234 // z(x) has len(x_vals) + 1 coeffs, we add to the commitment the last coeff of z(x)
235 z_commit = add(z_commit, mulScalar(G1_CRS[z_coeffs.length - 1], z_coeffs[z_coeffs.length - 1]));
236
237 return (z_commit, l_commit);
238 }
239
240 /**
241 * @notice Verifies a batch of point evaluation proofs. Function name follows `ark-poly`.
242 * @dev To avoid ops in G_2, we slightly tweak how the verification is done.
243 * @param c G1 point commitment to polynomial.
244 * @param pi G2 point proof.
245 * @param x_vals Values to prove evaluation of polynomial at.
246 * @param y_vals Evaluation poly(x).
247 * @param l_coeffs Coefficients of the lagrange polynomial.
248 * @param z_coeffs Coefficients of the zero polynomial z(x) = (x - x_1)(x - x_2)...(x - x_n).
249 * @return result Indicates if KZG proof is correct.
250 */
251 function batchCheck(
252 uint256[2] calldata c,
253 uint256[2][2] calldata pi,
254 uint256[] calldata x_vals,
255 uint256[] calldata y_vals,
256 uint256[] calldata l_coeffs,
257 uint256[] calldata z_coeffs
258 ) public view returns (bool result) {
259 //
260 // we want to:
261 // 1. avoid gas intensive ops in G2
262 // 2. format the pairing check in line with what the evm opcode expects.
263 //
264 // we can do this by tweaking the KZG check to be:
265 //
266 // e(z(r) * g1, pi) * e(g1, l(r) * g2) = e(c, g2) [initial check]
267 // e(z(r) * g1, pi) * e(l(r) * g1, g2) * e(c, g2)^{-1} = 1 [bilinearity of pairing]
268 // e(z(r) * g1, pi) * e(l(r) * g1 - c, g2) = 1 [done]
269 //
270 (uint256[2] memory z_commit, uint256[2] memory l_commit) =
271 checkAndCommitAuxPolys(z_coeffs, l_coeffs, x_vals, y_vals);
272 uint256[2] memory neg_commit = negate(c);
273 return pairing(z_commit, pi, add(l_commit, neg_commit), G_2);
274 }
275}