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 {% if g1_crs_len>0 %} // only enabled if g1_crs_len>0, for batch_check
140 uint256[2][{{ g1_crs_len }}] G1_CRS = [
141 {%- for (i, point) in g1_crs.iter().enumerate() %}
142 [
143 {{ point.0[0] }},
144 {{ point.0[1] }}
145 {% if loop.last -%}
146 ]
147 {%- else -%}
148 ],
149 {%- endif -%}
150 {% endfor -%}
151 ];
152 {%~ endif %}
153
154 /**
155 * @notice Verifies a single point evaluation proof. Function name follows `ark-poly`.
156 * @dev To avoid ops in G_2, we slightly tweak how the verification is done.
157 * @param c G_1 point commitment to polynomial.
158 * @param pi G_1 point proof.
159 * @param x Value to prove evaluation of polynomial at.
160 * @param y Evaluation poly(x).
161 * @return result Indicates if KZG proof is correct.
162 */
163 function check(uint256[2] calldata c, uint256[2] calldata pi, uint256 x, uint256 y)
164 public
165 view
166 returns (bool result)
167 {
168 //
169 // we want to:
170 // 1. avoid gas intensive ops in G2
171 // 2. format the pairing check in line with what the evm opcode expects.
172 //
173 // we can do this by tweaking the KZG check to be:
174 //
175 // e(pi, vk - x * g2) = e(c - y * g1, g2) [initial check]
176 // e(pi, vk - x * g2) * e(c - y * g1, g2)^{-1} = 1
177 // e(pi, vk - x * g2) * e(-c + y * g1, g2) = 1 [bilinearity of pairing for all subsequent steps]
178 // e(pi, vk) * e(pi, -x * g2) * e(-c + y * g1, g2) = 1
179 // e(pi, vk) * e(-x * pi, g2) * e(-c + y * g1, g2) = 1
180 // e(pi, vk) * e(x * -pi - c + y * g1, g2) = 1 [done]
181 // |_ rhs_pairing _|
182 //
183 uint256[2] memory rhs_pairing =
184 add(mulScalar(negate(pi), x), add(negate(c), mulScalar(G_1, y)));
185 return pairing(pi, VK, rhs_pairing, G_2);
186 }
187
188 function evalPolyAt(uint256[] memory _coefficients, uint256 _index) public pure returns (uint256) {
189 uint256 m = BN254_SCALAR_FIELD;
190 uint256 result = 0;
191 uint256 powerOfX = 1;
192
193 for (uint256 i = 0; i < _coefficients.length; i++) {
194 uint256 coeff = _coefficients[i];
195 assembly {
196 result := addmod(result, mulmod(powerOfX, coeff, m), m)
197 powerOfX := mulmod(powerOfX, _index, m)
198 }
199 }
200 return result;
201 }
202
203 {% if g1_crs_len>0 %} // only enabled if g1_crs_len>0, for batch_check
204 /**
205 * @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).
206 * @param z_coeffs coefficients of the zero polynomial z(x) = (x - x_1)(x - x_2)...(x - x_n).
207 * @param l_coeffs coefficients of the lagrange polynomial l(x).
208 * @param x_vals x values to evaluate the polynomials at.
209 * @param y_vals y values to which l(x) should evaluate to.
210 * @return uint256[2] commitment to z(x).
211 * @return uint256[2] commitment to l(x).
212 */
213 function checkAndCommitAuxPolys(
214 uint256[] memory z_coeffs,
215 uint256[] memory l_coeffs,
216 uint256[] memory x_vals,
217 uint256[] memory y_vals
218 ) public view returns (uint256[2] memory, uint256[2] memory) {
219 // z(x) is of degree len(x_vals), it is a product of linear polynomials (x - x_i)
220 // l(x) is of degree len(x_vals) - 1
221 uint256[2] memory z_commit;
222 uint256[2] memory l_commit;
223 for (uint256 i = 0; i < x_vals.length; i++) {
224 z_commit = add(z_commit, mulScalar(G1_CRS[i], z_coeffs[i])); // update commitment to z(x)
225 l_commit = add(l_commit, mulScalar(G1_CRS[i], l_coeffs[i])); // update commitment to l(x)
226
227 uint256 eval_z = evalPolyAt(z_coeffs, x_vals[i]);
228 uint256 eval_l = evalPolyAt(l_coeffs, x_vals[i]);
229
230 require(eval_z == 0, "checkAndCommitAuxPolys: wrong zero poly");
231 require(eval_l == y_vals[i], "checkAndCommitAuxPolys: wrong lagrange poly");
232 }
233 // z(x) has len(x_vals) + 1 coeffs, we add to the commitment the last coeff of z(x)
234 z_commit = add(z_commit, mulScalar(G1_CRS[z_coeffs.length - 1], z_coeffs[z_coeffs.length - 1]));
235
236 return (z_commit, l_commit);
237 }
238
239 /**
240 * @notice Verifies a batch of point evaluation proofs. Function name follows `ark-poly`.
241 * @dev To avoid ops in G_2, we slightly tweak how the verification is done.
242 * @param c G1 point commitment to polynomial.
243 * @param pi G2 point proof.
244 * @param x_vals Values to prove evaluation of polynomial at.
245 * @param y_vals Evaluation poly(x).
246 * @param l_coeffs Coefficients of the lagrange polynomial.
247 * @param z_coeffs Coefficients of the zero polynomial z(x) = (x - x_1)(x - x_2)...(x - x_n).
248 * @return result Indicates if KZG proof is correct.
249 */
250 function batchCheck(
251 uint256[2] calldata c,
252 uint256[2][2] calldata pi,
253 uint256[] calldata x_vals,
254 uint256[] calldata y_vals,
255 uint256[] calldata l_coeffs,
256 uint256[] calldata z_coeffs
257 ) public view returns (bool result) {
258 //
259 // we want to:
260 // 1. avoid gas intensive ops in G2
261 // 2. format the pairing check in line with what the evm opcode expects.
262 //
263 // we can do this by tweaking the KZG check to be:
264 //
265 // e(z(r) * g1, pi) * e(g1, l(r) * g2) = e(c, g2) [initial check]
266 // e(z(r) * g1, pi) * e(l(r) * g1, g2) * e(c, g2)^{-1} = 1 [bilinearity of pairing]
267 // e(z(r) * g1, pi) * e(l(r) * g1 - c, g2) = 1 [done]
268 //
269 (uint256[2] memory z_commit, uint256[2] memory l_commit) =
270 checkAndCommitAuxPolys(z_coeffs, l_coeffs, x_vals, y_vals);
271 uint256[2] memory neg_commit = negate(c);
272 return pairing(z_commit, pi, add(l_commit, neg_commit), G_2);
273 }
274 {%~ endif %}
275}