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