Barretenberg
The ZK-SNARK library at the core of Aztec
Loading...
Searching...
No Matches
honk_optimized_contract.hpp
Go to the documentation of this file.
1// === AUDIT STATUS ===
2// internal: { status: Planned, auditors: [], commit: }
3// external_1: { status: not started, auditors: [], commit: }
4// external_2: { status: not started, auditors: [], commit: }
5// =====================
6
7#pragma once
8#include <filesystem>
9#include <fstream>
10#include <iostream>
11#include <sstream>
12#include <vector>
13
14// Complete implementation of generate_offsets.py converted to C++
15inline std::string generate_memory_offsets(int log_n)
16{
17 const int BATCHED_RELATION_PARTIAL_LENGTH = 8;
18 const int NUMBER_OF_SUBRELATIONS = 28;
19 const int NUMBER_OF_ALPHAS = NUMBER_OF_SUBRELATIONS - 1;
20 const int START_POINTER = 0x1000;
21 const int SCRATCH_SPACE_POINTER = 0x100;
22 const int BARYCENTRIC_DOMAIN_SIZE = 8;
23
24 std::ostringstream out;
25
26 // Helper lambdas
27 auto print_header_centered = [&](const std::string& text) {
28 const std::string top = "/*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/";
29 const std::string bottom = "/*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/";
30 size_t width = static_cast<size_t>(top.length()) - 4; // exclude /* and */
31 std::string centered =
32 "/*" + std::string(static_cast<size_t>((width - text.length()) / 2), ' ') + text +
33 std::string(static_cast<size_t>(width - text.length() - (width - text.length()) / 2), ' ') + "*/";
34 out << "\n" << top << "\n" << centered << "\n" << bottom << "\n";
35 };
36
37 auto print_loc = [&](int pointer, const std::string& name) {
38 out << "uint256 internal constant " << name << " = " << std::showbase << std::hex << pointer << ";\n";
39 };
40
41 auto print_fr = print_loc;
42
43 auto print_g1 = [&](int pointer, const std::string& name) {
44 print_loc(pointer, name + "_X_LOC");
45 print_loc(pointer + 32, name + "_Y_LOC");
46 };
47
48 // Data arrays from Python script
49 const std::vector<std::string> vk_fr = { "VK_CIRCUIT_SIZE_LOC",
50 "VK_NUM_PUBLIC_INPUTS_LOC",
51 "VK_PUB_INPUTS_OFFSET_LOC" };
52
53 const std::vector<std::string> vk_g1 = { "Q_M",
54 "Q_C",
55 "Q_L",
56 "Q_R",
57 "Q_O",
58 "Q_4",
59 "Q_LOOKUP",
60 "Q_ARITH",
61 "Q_DELTA_RANGE",
62 "Q_ELLIPTIC",
63 "Q_MEMORY",
64 "Q_NNF",
65 "Q_POSEIDON_2_EXTERNAL",
66 "Q_POSEIDON_2_INTERNAL",
67 "SIGMA_1",
68 "SIGMA_2",
69 "SIGMA_3",
70 "SIGMA_4",
71 "ID_1",
72 "ID_2",
73 "ID_3",
74 "ID_4",
75 "TABLE_1",
76 "TABLE_2",
77 "TABLE_3",
78 "TABLE_4",
79 "LAGRANGE_FIRST",
80 "LAGRANGE_LAST" };
81
82 const std::vector<std::string> proof_fr = { "PROOF_CIRCUIT_SIZE",
83 "PROOF_NUM_PUBLIC_INPUTS",
84 "PROOF_PUB_INPUTS_OFFSET" };
85
86 const std::vector<std::string> pairing_points = { "PAIRING_POINT_0_X_0_LOC", "PAIRING_POINT_0_X_1_LOC",
87 "PAIRING_POINT_0_Y_0_LOC", "PAIRING_POINT_0_Y_1_LOC",
88 "PAIRING_POINT_1_X_0_LOC", "PAIRING_POINT_1_X_1_LOC",
89 "PAIRING_POINT_1_Y_0_LOC", "PAIRING_POINT_1_Y_1_LOC" };
90
91 const std::vector<std::string> proof_g1 = {
92 "W_L", "W_R", "W_O", "LOOKUP_READ_COUNTS", "LOOKUP_READ_TAGS", "W_4", "LOOKUP_INVERSES", "Z_PERM"
93 };
94
95 const std::vector<std::string> entities = { "QM",
96 "QC",
97 "QL",
98 "QR",
99 "QO",
100 "Q4",
101 "QLOOKUP",
102 "QARITH",
103 "QRANGE",
104 "QELLIPTIC",
105 "QMEMORY",
106 "QNNF",
107 "QPOSEIDON2_EXTERNAL",
108 "QPOSEIDON2_INTERNAL",
109 "SIGMA1",
110 "SIGMA2",
111 "SIGMA3",
112 "SIGMA4",
113 "ID1",
114 "ID2",
115 "ID3",
116 "ID4",
117 "TABLE1",
118 "TABLE2",
119 "TABLE3",
120 "TABLE4",
121 "LAGRANGE_FIRST",
122 "LAGRANGE_LAST",
123 "W1",
124 "W2",
125 "W3",
126 "W4",
127 "Z_PERM",
128 "LOOKUP_INVERSES",
129 "LOOKUP_READ_COUNTS",
130 "LOOKUP_READ_TAGS",
131 "W1_SHIFT",
132 "W2_SHIFT",
133 "W3_SHIFT",
134 "W4_SHIFT",
135 "Z_PERM_SHIFT" };
136
137 const std::vector<std::string> challenges = { "ETA",
138 "ETA_TWO",
139 "ETA_THREE",
140 "BETA",
141 "GAMMA",
142 "RHO",
143 "GEMINI_R",
144 "SHPLONK_NU",
145 "SHPLONK_Z",
146 "PUBLIC_INPUTS_DELTA_NUMERATOR",
147 "PUBLIC_INPUTS_DELTA_DENOMINATOR" };
148
149 const std::vector<std::string> subrelation_intermediates = { "AUX_NON_NATIVE_FIELD_IDENTITY",
150 "AUX_LIMB_ACCUMULATOR_IDENTITY",
151 "AUX_RAM_CONSISTENCY_CHECK_IDENTITY",
152 "AUX_ROM_CONSISTENCY_CHECK_IDENTITY",
153 "AUX_MEMORY_CHECK_IDENTITY" };
154
155 const std::vector<std::string> general_intermediates = { "FINAL_ROUND_TARGET_LOC", "POW_PARTIAL_EVALUATION_LOC" };
156
157 int pointer = START_POINTER;
158
159 // VK INDICIES
160 print_header_centered("VK INDICIES");
161 for (const auto& item : vk_fr) {
162 print_fr(pointer, item);
163 pointer += 32;
164 }
165 for (const auto& item : vk_g1) {
166 print_g1(pointer, item);
167 pointer += 64;
168 }
169
170 // PROOF INDICIES
171 print_header_centered("PROOF INDICIES");
172 for (const auto& item : pairing_points) {
173 print_fr(pointer, item);
174 pointer += 32;
175 }
176 for (const auto& item : proof_g1) {
177 print_g1(pointer, item);
178 pointer += 64;
179 }
180
181 // SUMCHECK UNIVARIATES
182 print_header_centered("PROOF INDICIES - SUMCHECK UNIVARIATES");
183 for (int size = 0; size < log_n; ++size) {
184 for (int relation_len = 0; relation_len < BATCHED_RELATION_PARTIAL_LENGTH; ++relation_len) {
185 std::string name =
186 "SUMCHECK_UNIVARIATE_" + std::to_string(size) + "_" + std::to_string(relation_len) + "_LOC";
187 print_fr(pointer, name);
188 pointer += 32;
189 }
190 }
191
192 // SUMCHECK EVALUATIONS
193 print_header_centered("PROOF INDICIES - SUMCHECK EVALUATIONS");
194 for (const auto& entity : entities) {
195 print_fr(pointer, entity + "_EVAL_LOC");
196 pointer += 32;
197 }
198
199 // SHPLEMINI - GEMINI FOLDING COMMS
200 print_header_centered("PROOF INDICIES - GEMINI FOLDING COMMS");
201 for (int size = 0; size < log_n - 1; ++size) {
202 print_g1(pointer, "GEMINI_FOLD_UNIVARIATE_" + std::to_string(size));
203 pointer += 64;
204 }
205
206 // GEMINI FOLDING EVALUATIONS
207 print_header_centered("PROOF INDICIES - GEMINI FOLDING EVALUATIONS");
208 for (int size = 0; size < log_n; ++size) {
209 print_fr(pointer, "GEMINI_A_EVAL_" + std::to_string(size));
210 pointer += 32;
211 }
212 print_g1(pointer, "SHPLONK_Q");
213 pointer += 64;
214 print_g1(pointer, "KZG_QUOTIENT");
215 pointer += 64;
216
217 print_header_centered("PROOF INDICIES - COMPLETE");
218
219 // CHALLENGES
220 print_header_centered("CHALLENGES");
221 for (const auto& chall : challenges) {
222 print_fr(pointer, chall + "_CHALLENGE");
223 pointer += 32;
224 }
225 for (int alpha = 0; alpha < NUMBER_OF_ALPHAS; ++alpha) {
226 print_fr(pointer, "ALPHA_CHALLENGE_" + std::to_string(alpha));
227 pointer += 32;
228 }
229 for (int gate = 0; gate < log_n; ++gate) {
230 print_fr(pointer, "GATE_CHALLENGE_" + std::to_string(gate));
231 pointer += 32;
232 }
233 for (int sum_u = 0; sum_u < log_n; ++sum_u) {
234 print_fr(pointer, "SUM_U_CHALLENGE_" + std::to_string(sum_u));
235 pointer += 32;
236 }
237 print_header_centered("CHALLENGES - COMPLETE");
238
239 // RUNTIME MEMORY
240 print_header_centered("SUMCHECK - RUNTIME MEMORY");
241 print_header_centered("SUMCHECK - RUNTIME MEMORY - BARYCENTRIC");
242
243 // Barycentric domain (uses scratch space)
244 int bary_pointer = SCRATCH_SPACE_POINTER;
245 for (int i = 0; i < BARYCENTRIC_DOMAIN_SIZE; ++i) {
246 print_fr(bary_pointer, "BARYCENTRIC_LAGRANGE_DENOMINATOR_" + std::to_string(i) + "_LOC");
247 bary_pointer += 32;
248 }
249 for (int i = 0; i < log_n; ++i) {
250 for (int j = 0; j < BARYCENTRIC_DOMAIN_SIZE; ++j) {
251 print_fr(pointer,
252 "BARYCENTRIC_DENOMINATOR_INVERSES_" + std::to_string(i) + "_" + std::to_string(j) + "_LOC");
253 pointer += 32;
254 }
255 }
256 print_header_centered("SUMCHECK - RUNTIME MEMORY - BARYCENTRIC COMPLETE");
257
258 // SUBRELATION EVALUATIONS
259 print_header_centered("SUMCHECK - RUNTIME MEMORY - SUBRELATION EVALUATIONS");
260 for (int i = 0; i < NUMBER_OF_SUBRELATIONS; ++i) {
261 print_fr(pointer, "SUBRELATION_EVAL_" + std::to_string(i) + "_LOC");
262 pointer += 32;
263 }
264 print_header_centered("SUMCHECK - RUNTIME MEMORY - SUBRELATION EVALUATIONS COMPLETE");
265
266 // SUBRELATION INTERMEDIATES
267 print_header_centered("SUMCHECK - RUNTIME MEMORY - SUBRELATION INTERMEDIATES");
268 for (const auto& item : general_intermediates) {
269 print_fr(pointer, item);
270 pointer += 32;
271 }
272 for (const auto& item : subrelation_intermediates) {
273 print_fr(pointer, item);
274 pointer += 32;
275 }
276 print_header_centered("SUMCHECK - RUNTIME MEMORY - COMPLETE");
277
278 // SHPLEMINI RUNTIME MEMORY
279 print_header_centered("SHPLEMINI - RUNTIME MEMORY");
280 print_header_centered("SHPLEMINI - POWERS OF EVALUATION CHALLENGE");
281 out << "/// {{ UNROLL_SECTION_START POWERS_OF_EVALUATION_CHALLENGE }}\n";
282 for (int i = 0; i < log_n; ++i) {
283 print_fr(pointer, "POWERS_OF_EVALUATION_CHALLENGE_" + std::to_string(i) + "_LOC");
284 pointer += 32;
285 }
286 out << "/// {{ UNROLL_SECTION_END POWERS_OF_EVALUATION_CHALLENGE }}\n";
287 print_header_centered("SHPLEMINI - POWERS OF EVALUATION CHALLENGE COMPLETE");
288
289 // BATCH SCALARS
290 print_header_centered("SHPLEMINI - RUNTIME MEMORY - BATCH SCALARS");
291 const int BATCH_SIZE = 69;
292 for (int i = 0; i < BATCH_SIZE; ++i) {
293 print_fr(pointer, "BATCH_SCALAR_" + std::to_string(i) + "_LOC");
294 pointer += 32;
295 }
296 print_header_centered("SHPLEMINI - RUNTIME MEMORY - BATCH SCALARS COMPLETE");
297
298 // INVERSIONS
299 print_header_centered("SHPLEMINI - RUNTIME MEMORY - INVERSIONS");
300
301 // Inverted gemini denominators
302 for (int i = 0; i < log_n + 1; ++i) {
303 print_fr(pointer, "INVERTED_GEMINI_DENOMINATOR_" + std::to_string(i) + "_LOC");
304 pointer += 32;
305 }
306
307 // Batched evaluation accumulator inversions
308 for (int i = 0; i < log_n; ++i) {
309 print_fr(pointer, "BATCH_EVALUATION_ACCUMULATOR_INVERSION_" + std::to_string(i) + "_LOC");
310 pointer += 32;
311 }
312
313 out << "\n";
314 print_fr(pointer, "BATCHED_EVALUATION_LOC");
315 pointer += 32;
316 print_fr(pointer, "CONSTANT_TERM_ACCUMULATOR_LOC");
317 pointer += 32;
318
319 out << "\n";
320 print_fr(pointer, "POS_INVERTED_DENOMINATOR");
321 pointer += 32;
322 print_fr(pointer, "NEG_INVERTED_DENOMINATOR");
323 pointer += 32;
324
325 out << "\n";
326 out << "// LOG_N challenge pow minus u\n";
327 for (int i = 0; i < log_n; ++i) {
328 print_fr(pointer, "INVERTED_CHALLENEGE_POW_MINUS_U_" + std::to_string(i) + "_LOC");
329 pointer += 32;
330 }
331
332 out << "\n";
333 out << "// LOG_N pos_inverted_off\n";
334 for (int i = 0; i < log_n; ++i) {
335 print_fr(pointer, "POS_INVERTED_DENOM_" + std::to_string(i) + "_LOC");
336 pointer += 32;
337 }
338
339 out << "\n";
340 out << "// LOG_N neg_inverted_off\n";
341 for (int i = 0; i < log_n; ++i) {
342 print_fr(pointer, "NEG_INVERTED_DENOM_" + std::to_string(i) + "_LOC");
343 pointer += 32;
344 }
345
346 out << "\n";
347 for (int i = 0; i < log_n; ++i) {
348 print_fr(pointer, "FOLD_POS_EVALUATIONS_" + std::to_string(i) + "_LOC");
349 pointer += 32;
350 }
351
352 print_header_centered("SHPLEMINI RUNTIME MEMORY - INVERSIONS - COMPLETE");
353 print_header_centered("SHPLEMINI RUNTIME MEMORY - COMPLETE");
354
355 out << "\n";
356 print_fr(pointer, "LATER_SCRATCH_SPACE");
357 pointer += 32;
358
359 // Temporary space
360 print_header_centered("Temporary space");
361 for (int i = 0; i < 3 * log_n; ++i) {
362 print_fr(pointer, "TEMP_" + std::to_string(i) + "_LOC");
363 pointer += 32;
364 }
365 print_header_centered("Temporary space - COMPLETE");
366
367 // Scratch space aliases
368 out << "\n";
369 out << "// Aliases for scratch space\n";
370 print_fr(0x00, "CHALL_POW_LOC");
371 print_fr(0x20, "SUMCHECK_U_LOC");
372 print_fr(0x40, "GEMINI_A_LOC");
373 out << "\n";
374 print_fr(0x00, "SS_POS_INV_DENOM_LOC");
375 print_fr(0x20, "SS_NEG_INV_DENOM_LOC");
376 print_fr(0x40, "SS_GEMINI_EVALS_LOC");
377
378 // EC aliases
379 out << "\n\n";
380 out << "// Aliases\n";
381 out << "// Aliases for wire values (Elliptic curve gadget)\n";
382 print_header_centered("SUMCHECK - MEMORY ALIASES");
383
384 return out.str();
385}
386
387// Source code for the Ultrahonk Solidity verifier.
388// It's expected that the AcirComposer will inject a library which will load the verification key into memory.
389// NOLINTNEXTLINE(cppcoreguidelines-avoid-c-arrays)
390static const char HONK_CONTRACT_OPT_SOURCE[] = R"(
391// SPDX-License-Identifier: Apache-2.0
392// Copyright 2022 Aztec
393pragma solidity ^0.8.27;
394
395interface IVerifier {
396 function verify(bytes calldata _proof, bytes32[] calldata _publicInputs) external view returns (bool);
397}
398
399
400
401uint256 constant NUMBER_OF_SUBRELATIONS = 28;
402uint256 constant BATCHED_RELATION_PARTIAL_LENGTH = 8;
403uint256 constant ZK_BATCHED_RELATION_PARTIAL_LENGTH = 9;
404uint256 constant NUMBER_OF_ENTITIES = 41;
405uint256 constant NUMBER_UNSHIFTED = 36;
406uint256 constant NUMBER_TO_BE_SHIFTED = 5;
407uint256 constant PAIRING_POINTS_SIZE = 8;
408
409uint256 constant VK_HASH = {{ VK_HASH }};
410uint256 constant CIRCUIT_SIZE = {{ CIRCUIT_SIZE }};
411uint256 constant LOG_N = {{ LOG_CIRCUIT_SIZE }};
412uint256 constant NUMBER_PUBLIC_INPUTS = {{ NUM_PUBLIC_INPUTS }};
413uint256 constant REAL_NUMBER_PUBLIC_INPUTS = {{ REAL_NUM_PUBLIC_INPUTS }};
414uint256 constant PUBLIC_INPUTS_OFFSET = 1;
415// LOG_N * 8
416uint256 constant NUMBER_OF_BARYCENTRIC_INVERSES = {{ NUMBER_OF_BARYCENTRIC_INVERSES }};
417
418contract HonkVerifier is IVerifier {
419 /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
420 /* SLAB ALLOCATION */
421 /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/
430 // {{ SECTION_START MEMORY_LAYOUT }}
431 // {{ SECTION_END MEMORY_LAYOUT }}
432
433 /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
434 /* SUMCHECK - MEMORY ALIASES */
435 /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/
436 uint256 internal constant EC_X_1 = W2_EVAL_LOC;
437 uint256 internal constant EC_Y_1 = W3_EVAL_LOC;
438 uint256 internal constant EC_X_2 = W1_SHIFT_EVAL_LOC;
439 uint256 internal constant EC_Y_2 = W4_SHIFT_EVAL_LOC;
440 uint256 internal constant EC_Y_3 = W3_SHIFT_EVAL_LOC;
441 uint256 internal constant EC_X_3 = W2_SHIFT_EVAL_LOC;
442
443 // Aliases for selectors (Elliptic curve gadget)
444 uint256 internal constant EC_Q_SIGN = QL_EVAL_LOC;
445 uint256 internal constant EC_Q_IS_DOUBLE = QM_EVAL_LOC;
446
447 /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
448 /* CONSTANTS */
449 /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/
450 uint256 internal constant GRUMPKIN_CURVE_B_PARAMETER_NEGATED = 17; // -(-17)
451
452 // Auxiliary relation constants
453 // In the Non Native Field Arithmetic Relation, large field elements are broken up into 4 LIMBs of 68 `LIMB_SIZE` bits each.
454 uint256 internal constant LIMB_SIZE = 0x100000000000000000; // 2<<68
455
456 // In the Delta Range Check Relation, there is a range checking relation that can validate 14-bit range checks with only 1
457 // extra relation in the execution trace.
458 // For large range checks, we decompose them into a collection of 14-bit range checks.
459 uint256 internal constant SUBLIMB_SHIFT = 0x4000; // 2<<14
460
461 // Poseidon2 internal constants
462 // https://github.com/HorizenLabs/poseidon2/blob/main/poseidon2_rust_params.sage - derivation code
463 uint256 internal constant POS_INTERNAL_MATRIX_D_0 =
464 0x10dc6e9c006ea38b04b1e03b4bd9490c0d03f98929ca1d7fb56821fd19d3b6e7;
465 uint256 internal constant POS_INTERNAL_MATRIX_D_1 =
466 0x0c28145b6a44df3e0149b3d0a30b3bb599df9756d4dd9b84a86b38cfb45a740b;
467 uint256 internal constant POS_INTERNAL_MATRIX_D_2 =
468 0x00544b8338791518b2c7645a50392798b21f75bb60e3596170067d00141cac15;
469 uint256 internal constant POS_INTERNAL_MATRIX_D_3 =
470 0x222c01175718386f2e2e82eb122789e352e105a3b8fa852613bc534433ee428b;
471
472 // Constants inspecting proof components
473 uint256 internal constant NUMBER_OF_UNSHIFTED_ENTITIES = 36;
474 // Shifted columns are columes that are duplicates of existing columns but right-shifted by 1
475 uint256 internal constant NUMBER_OF_SHIFTED_ENTITIES = 5;
476 uint256 internal constant TOTAL_NUMBER_OF_ENTITIES = 41;
477
478 // Constants for performing batch multiplication
479 uint256 internal constant ACCUMULATOR = 0x00;
480 uint256 internal constant ACCUMULATOR_2 = 0x40;
481 uint256 internal constant G1_LOCATION = 0x60;
482 uint256 internal constant G1_Y_LOCATION = 0x80;
483 uint256 internal constant SCALAR_LOCATION = 0xa0;
484
485 uint256 internal constant LOWER_127_MASK = 0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF;
486
487 // Group order
488 uint256 internal constant Q = 21888242871839275222246405745257275088696311157297823662689037894645226208583; // EC group order
489
490 // Field order constants
491 // -1/2 mod p
492 uint256 internal constant NEG_HALF_MODULO_P = 0x183227397098d014dc2822db40c0ac2e9419f4243cdcb848a1f0fac9f8000000;
493 uint256 internal constant P = 21888242871839275222246405745257275088548364400416034343698204186575808495617;
494 uint256 internal constant P_SUB_1 = 21888242871839275222246405745257275088548364400416034343698204186575808495616;
495 uint256 internal constant P_SUB_2 = 21888242871839275222246405745257275088548364400416034343698204186575808495615;
496 uint256 internal constant P_SUB_3 = 21888242871839275222246405745257275088548364400416034343698204186575808495614;
497 uint256 internal constant P_SUB_4 = 21888242871839275222246405745257275088548364400416034343698204186575808495613;
498 uint256 internal constant P_SUB_5 = 21888242871839275222246405745257275088548364400416034343698204186575808495612;
499 uint256 internal constant P_SUB_6 = 21888242871839275222246405745257275088548364400416034343698204186575808495611;
500 uint256 internal constant P_SUB_7 = 21888242871839275222246405745257275088548364400416034343698204186575808495610;
501
502 // Barycentric evaluation constants
503 uint256 internal constant BARYCENTRIC_LAGRANGE_DENOMINATOR_0 =
504 0x30644e72e131a029b85045b68181585d2833e84879b9709143e1f593efffec51;
505 uint256 internal constant BARYCENTRIC_LAGRANGE_DENOMINATOR_1 =
506 0x00000000000000000000000000000000000000000000000000000000000002d0;
507 uint256 internal constant BARYCENTRIC_LAGRANGE_DENOMINATOR_2 =
508 0x30644e72e131a029b85045b68181585d2833e84879b9709143e1f593efffff11;
509 uint256 internal constant BARYCENTRIC_LAGRANGE_DENOMINATOR_3 =
510 0x0000000000000000000000000000000000000000000000000000000000000090;
511 uint256 internal constant BARYCENTRIC_LAGRANGE_DENOMINATOR_4 =
512 0x30644e72e131a029b85045b68181585d2833e84879b9709143e1f593efffff71;
513 uint256 internal constant BARYCENTRIC_LAGRANGE_DENOMINATOR_5 =
514 0x00000000000000000000000000000000000000000000000000000000000000f0;
515 uint256 internal constant BARYCENTRIC_LAGRANGE_DENOMINATOR_6 =
516 0x30644e72e131a029b85045b68181585d2833e84879b9709143e1f593effffd31;
517 uint256 internal constant BARYCENTRIC_LAGRANGE_DENOMINATOR_7 =
518 0x00000000000000000000000000000000000000000000000000000000000013b0;
519
520 // Constants for computing public input delta
521 uint256 internal constant PERMUTATION_ARGUMENT_VALUE_SEPARATOR = 1 << 28;
522
523 /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
524 /* ERRORS */
525 /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/
526 // The errors match Errors.sol
527
528 bytes4 internal constant VALUE_GE_LIMB_MAX_SELECTOR = 0xeb73e0bd;
529 bytes4 internal constant VALUE_GE_GROUP_ORDER_SELECTOR = 0x607be13e;
530 bytes4 internal constant VALUE_GE_FIELD_ORDER_SELECTOR = 0x20a33589;
531 bytes4 internal constant SUMCHECK_FAILED_SELECTOR = 0x9fc3a218;
532 bytes4 internal constant SHPLEMINI_FAILED_SELECTOR = 0xa5d82e8a;
533 bytes4 internal constant POINT_AT_INFINITY_SELECTOR = 0x4ddaa5e5;
534
535 bytes4 internal constant PROOF_LENGTH_WRONG_WITH_LOG_N_SELECTOR = 0x59895a53;
536 bytes4 internal constant PUBLIC_INPUTS_LENGTH_WRONG_SELECTOR = 0xfa066593;
537
538 bytes4 internal constant MODEXP_FAILED_SELECTOR = 0xf442f163;
539
540 constructor() {}
541
542 function verify(
543 bytes calldata,
544 /*proof*/
545 bytes32[] calldata /*public_inputs*/
546 )
547 public
548 view
549 override
550 returns (bool)
551 {
552 // Load the proof from calldata in one large chunk
553 assembly {
554 /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
555 /* LOAD VERIFCATION KEY */
556 /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/
557 // Write the verification key into memory
558 //
559 // Although defined at the top of the file, it is used towards the end of the algorithm when batching in the commitment scheme.
560 function loadVk() {
561 mstore(Q_L_X_LOC, {{ Q_L_X_LOC }})
562 mstore(Q_L_Y_LOC, {{ Q_L_Y_LOC }})
563 mstore(Q_R_X_LOC, {{ Q_R_X_LOC }})
564 mstore(Q_R_Y_LOC, {{ Q_R_Y_LOC }})
565 mstore(Q_O_X_LOC, {{ Q_O_X_LOC }})
566 mstore(Q_O_Y_LOC, {{ Q_O_Y_LOC }})
567 mstore(Q_4_X_LOC, {{ Q_4_X_LOC }})
568 mstore(Q_4_Y_LOC, {{ Q_4_Y_LOC }})
569 mstore(Q_M_X_LOC, {{ Q_M_X_LOC }})
570 mstore(Q_M_Y_LOC, {{ Q_M_Y_LOC }})
571 mstore(Q_C_X_LOC, {{ Q_C_X_LOC }})
572 mstore(Q_C_Y_LOC, {{ Q_C_Y_LOC }})
573 mstore(Q_LOOKUP_X_LOC, {{ Q_LOOKUP_X_LOC }})
574 mstore(Q_LOOKUP_Y_LOC, {{ Q_LOOKUP_Y_LOC }})
575 mstore(Q_ARITH_X_LOC, {{ Q_ARITH_X_LOC }})
576 mstore(Q_ARITH_Y_LOC, {{ Q_ARITH_Y_LOC }})
577 mstore(Q_DELTA_RANGE_X_LOC, {{ Q_DELTA_RANGE_X_LOC }})
578 mstore(Q_DELTA_RANGE_Y_LOC, {{ Q_DELTA_RANGE_Y_LOC }})
579 mstore(Q_ELLIPTIC_X_LOC, {{ Q_ELLIPTIC_X_LOC }})
580 mstore(Q_ELLIPTIC_Y_LOC, {{ Q_ELLIPTIC_Y_LOC }})
581 mstore(Q_MEMORY_X_LOC, {{ Q_MEMORY_X_LOC }})
582 mstore(Q_MEMORY_Y_LOC, {{ Q_MEMORY_Y_LOC }})
583 mstore(Q_NNF_X_LOC, {{ Q_NNF_X_LOC }})
584 mstore(Q_NNF_Y_LOC, {{ Q_NNF_Y_LOC }})
585 mstore(Q_POSEIDON_2_EXTERNAL_X_LOC, {{ Q_POSEIDON_2_EXTERNAL_X_LOC }})
586 mstore(Q_POSEIDON_2_EXTERNAL_Y_LOC, {{ Q_POSEIDON_2_EXTERNAL_Y_LOC }})
587 mstore(Q_POSEIDON_2_INTERNAL_X_LOC, {{ Q_POSEIDON_2_INTERNAL_X_LOC }})
588 mstore(Q_POSEIDON_2_INTERNAL_Y_LOC, {{ Q_POSEIDON_2_INTERNAL_Y_LOC }})
589 mstore(SIGMA_1_X_LOC, {{ SIGMA_1_X_LOC }})
590 mstore(SIGMA_1_Y_LOC, {{ SIGMA_1_Y_LOC }})
591 mstore(SIGMA_2_X_LOC, {{ SIGMA_2_X_LOC }})
592 mstore(SIGMA_2_Y_LOC, {{ SIGMA_2_Y_LOC }})
593 mstore(SIGMA_3_X_LOC, {{ SIGMA_3_X_LOC }})
594 mstore(SIGMA_3_Y_LOC, {{ SIGMA_3_Y_LOC }})
595 mstore(SIGMA_4_X_LOC, {{ SIGMA_4_X_LOC }})
596 mstore(SIGMA_4_Y_LOC, {{ SIGMA_4_Y_LOC }})
597 mstore(TABLE_1_X_LOC, {{ TABLE_1_X_LOC }})
598 mstore(TABLE_1_Y_LOC, {{ TABLE_1_Y_LOC }})
599 mstore(TABLE_2_X_LOC, {{ TABLE_2_X_LOC }})
600 mstore(TABLE_2_Y_LOC, {{ TABLE_2_Y_LOC }})
601 mstore(TABLE_3_X_LOC, {{ TABLE_3_X_LOC }})
602 mstore(TABLE_3_Y_LOC, {{ TABLE_3_Y_LOC }})
603 mstore(TABLE_4_X_LOC, {{ TABLE_4_X_LOC }})
604 mstore(TABLE_4_Y_LOC, {{ TABLE_4_Y_LOC }})
605 mstore(ID_1_X_LOC, {{ ID_1_X_LOC }})
606 mstore(ID_1_Y_LOC, {{ ID_1_Y_LOC }})
607 mstore(ID_2_X_LOC, {{ ID_2_X_LOC }})
608 mstore(ID_2_Y_LOC, {{ ID_2_Y_LOC }})
609 mstore(ID_3_X_LOC, {{ ID_3_X_LOC }})
610 mstore(ID_3_Y_LOC, {{ ID_3_Y_LOC }})
611 mstore(ID_4_X_LOC, {{ ID_4_X_LOC }})
612 mstore(ID_4_Y_LOC, {{ ID_4_Y_LOC }})
613 mstore(LAGRANGE_FIRST_X_LOC, {{ LAGRANGE_FIRST_X_LOC }})
614 mstore(LAGRANGE_FIRST_Y_LOC, {{ LAGRANGE_FIRST_Y_LOC }})
615 mstore(LAGRANGE_LAST_X_LOC, {{ LAGRANGE_LAST_X_LOC }})
616 mstore(LAGRANGE_LAST_Y_LOC, {{ LAGRANGE_LAST_Y_LOC }})
617 }
618
619 // Prime field order - placing on the stack
620 let p := P
621
622 {
623 let proof_ptr := add(calldataload(0x04), 0x24)
624
625 /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
626 /* VALIDATE INPUT LENGTHS */
627 /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/
628 // Validate proof byte length matches expected size for this circuit's LOG_N.
629 // Expected = (8*2 + LOG_N*BATCHED_RELATION_PARTIAL_LENGTH + NUMBER_OF_ENTITIES
630 // + (LOG_N-1)*2 + LOG_N + 2*2 + PAIRING_POINTS_SIZE) * 32
631 {
632 let expected_proof_size := mul(
633 add(
634 add(
635 add(16, mul(LOG_N, BATCHED_RELATION_PARTIAL_LENGTH)),
636 add(NUMBER_OF_ENTITIES, mul(sub(LOG_N, 1), 2))
637 ),
638 add(add(LOG_N, 4), PAIRING_POINTS_SIZE)
639 ),
640 32
641 )
642 let proof_length := calldataload(add(calldataload(0x04), 0x04))
643 if iszero(eq(proof_length, expected_proof_size)) {
644 mstore(0x00, PROOF_LENGTH_WRONG_WITH_LOG_N_SELECTOR)
645 mstore(0x04, LOG_N)
646 mstore(0x24, proof_length)
647 mstore(0x44, expected_proof_size)
648 revert(0x00, 0x64)
649 }
650 }
651 // Validate public inputs array length matches expected count.
652 {
653 let pi_count := calldataload(add(calldataload(0x24), 0x04))
654 if iszero(eq(pi_count, REAL_NUMBER_PUBLIC_INPUTS)) {
655 mstore(0x00, PUBLIC_INPUTS_LENGTH_WRONG_SELECTOR)
656 revert(0x00, 0x04)
657 }
658 }
659
660 /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
661 /* GENERATE CHALLENGES */
662 /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/
663 /*
664 * Proof points (affine coordinates) in the proof are in the following format, where offset is
665 * the offset in the entire proof until the first bit of the x coordinate
666 * offset + 0x00: x
667 * offset + 0x20: y
668 */
669
670 /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
671 /* GENERATE ETA CHALLENGE */
672 /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/
673 /* Eta challenge participants
674 * - circuit size
675 * - number of public inputs
676 * - public inputs offset
677 * - w1
678 * - w2
679 * - w3
680 *
681 * Where circuit size, number of public inputs and public inputs offset are all 32 byte values
682 * and w1,w2,w3 are all proof points values
683 */
684
685 mstore(0x00, VK_HASH)
686
687 let public_inputs_start := add(calldataload(0x24), 0x24)
688 let public_inputs_size := mul(REAL_NUMBER_PUBLIC_INPUTS, 0x20)
689
690 // Copy the public inputs into the eta buffer
691 calldatacopy(0x20, public_inputs_start, public_inputs_size)
692
693 // Copy Pairing points into eta buffer
694 let public_inputs_end := add(0x20, public_inputs_size)
695
696 calldatacopy(public_inputs_end, proof_ptr, 0x100)
697
698 // 0x20 * 8 = 0x100 (8 pairing point limbs)
699 // End of public inputs + pairing points
700 calldatacopy(add(0x120, public_inputs_size), add(proof_ptr, 0x100), 0x100)
701
702 // 0x1e0 = 1 * 32 bytes + 3 * 64 bytes for (w1,w2,w3) + 0x100 for pairing points
703 let eta_input_length := add(0x1e0, public_inputs_size)
704
705 // Get single eta challenge and compute powers (eta, eta², eta³)
706 let prev_challenge := mod(keccak256(0x00, eta_input_length), p)
707 mstore(0x00, prev_challenge)
708
709 let eta := and(prev_challenge, LOWER_127_MASK)
710 let eta_two := mulmod(eta, eta, p)
711 let eta_three := mulmod(eta_two, eta, p)
712
713 mstore(ETA_CHALLENGE, eta)
714 mstore(ETA_TWO_CHALLENGE, eta_two)
715 mstore(ETA_THREE_CHALLENGE, eta_three)
716
717 /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
718 /* LOAD PROOF INTO MEMORY */
719 /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/
720 // As all of our proof points are written in contiguous parts of memory, we call use a single
721 // calldatacopy to place all of our proof into the correct memory regions
722 // We copy the entire proof into memory as we must hash each proof section for challenge
723 // evaluation
724 // The last item in the proof, and the first item in the proof (pairing point 0)
725 let proof_size := sub(ETA_CHALLENGE, PAIRING_POINT_0_X_0_LOC)
726
727 calldatacopy(PAIRING_POINT_0_X_0_LOC, proof_ptr, proof_size)
728
729 /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
730 /* VALIDATE PROOF INPUTS */
731 /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/
732 // Validate all proof elements are within their expected ranges.
733 // Pairing limbs: lo < 2^136, hi < 2^120. G1 coordinates < Q. Fr elements < P.
734 {
735 let valid := true
736 let lo_limb_max := shl(136, 1)
737 let hi_limb_max := shl(120, 1)
738 let q_mod := Q
739
740 // 1. Pairing limbs: lo < 2^136, hi < 2^120 (4 pairs, stride 0x40)
741 let ptr := PAIRING_POINT_0_X_0_LOC
742 for {} lt(ptr, W_L_X_LOC) { ptr := add(ptr, 0x40) } {
743 valid := and(valid, lt(mload(ptr), lo_limb_max))
744 valid := and(valid, lt(mload(add(ptr, 0x20)), hi_limb_max))
745 }
746 if iszero(valid) {
747 mstore(0x00, VALUE_GE_LIMB_MAX_SELECTOR)
748 revert(0x00, 0x04)
749 }
750
751 // 2. G1 coordinates: each < Q
752 // - Witness commitments: W_L through Z_PERM (16 slots)
753 for { ptr := W_L_X_LOC } lt(ptr, SUMCHECK_UNIVARIATE_0_0_LOC) { ptr := add(ptr, 0x20) } {
754 valid := and(valid, lt(mload(ptr), q_mod))
755 }
756 // - Gemini fold commitments (28 slots)
757 for { ptr := GEMINI_FOLD_UNIVARIATE_0_X_LOC } lt(ptr, GEMINI_A_EVAL_0) { ptr := add(ptr, 0x20) } {
758 valid := and(valid, lt(mload(ptr), q_mod))
759 }
760 // - Shplonk Q + KZG quotient (4 slots)
761 for { ptr := SHPLONK_Q_X_LOC } lt(ptr, ETA_CHALLENGE) { ptr := add(ptr, 0x20) } {
762 valid := and(valid, lt(mload(ptr), q_mod))
763 }
764 if iszero(valid) {
765 mstore(0x00, VALUE_GE_GROUP_ORDER_SELECTOR)
766 revert(0x00, 0x04)
767 }
768
769 // 2b. G1 points: reject point at infinity (0,0).
770 // EVM precompiles silently treat (0,0) as the identity element,
771 // which could zero out commitments. On-curve validation (y² = x³ + 3)
772 // is handled by the ecAdd/ecMul precompiles per EIP-196.
773 // - Witness commitments (8 points, stride 0x40)
774 for { ptr := W_L_X_LOC } lt(ptr, SUMCHECK_UNIVARIATE_0_0_LOC) { ptr := add(ptr, 0x40) } {
775 valid := and(valid, iszero(iszero(or(mload(ptr), mload(add(ptr, 0x20))))))
776 }
777 // - Gemini fold commitments (14 points, stride 0x40)
778 for { ptr := GEMINI_FOLD_UNIVARIATE_0_X_LOC } lt(ptr, GEMINI_A_EVAL_0) { ptr := add(ptr, 0x40) } {
779 valid := and(valid, iszero(iszero(or(mload(ptr), mload(add(ptr, 0x20))))))
780 }
781 // - Shplonk Q + KZG quotient (2 points, stride 0x40)
782 for { ptr := SHPLONK_Q_X_LOC } lt(ptr, ETA_CHALLENGE) { ptr := add(ptr, 0x40) } {
783 valid := and(valid, iszero(iszero(or(mload(ptr), mload(add(ptr, 0x20))))))
784 }
785 if iszero(valid) {
786 mstore(0x00, POINT_AT_INFINITY_SELECTOR)
787 revert(0x00, 0x04)
788 }
789
790 // 3. Fr elements: each < P
791 // - Sumcheck univariates + evaluations (161 slots)
792 for { ptr := SUMCHECK_UNIVARIATE_0_0_LOC } lt(ptr, GEMINI_FOLD_UNIVARIATE_0_X_LOC) {
793 ptr := add(ptr, 0x20)
794 } {
795 valid := and(valid, lt(mload(ptr), p))
796 }
797 // - Gemini evaluations (15 slots)
798 for { ptr := GEMINI_A_EVAL_0 } lt(ptr, SHPLONK_Q_X_LOC) { ptr := add(ptr, 0x20) } {
799 valid := and(valid, lt(mload(ptr), p))
800 }
801 if iszero(valid) {
802 mstore(0x00, VALUE_GE_FIELD_ORDER_SELECTOR)
803 revert(0x00, 0x04)
804 }
805 }
806
807 /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
808 /* GENERATE BETA and GAMMAA CHALLENGE */
809 /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/
810
811 // Generate Beta and Gamma Chalenges
812 // - prevChallenge
813 // - LOOKUP_READ_COUNTS
814 // - LOOKUP_READ_TAGS
815 // - W4
816 mcopy(0x20, LOOKUP_READ_COUNTS_X_LOC, 0xc0)
817
818 prev_challenge := mod(keccak256(0x00, 0xe0), p)
819 mstore(0x00, prev_challenge)
820 let beta := and(prev_challenge, LOWER_127_MASK)
821 let gamma := shr(127, prev_challenge)
822
823 mstore(BETA_CHALLENGE, beta)
824 mstore(GAMMA_CHALLENGE, gamma)
825
826 /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
827 /* ALPHA CHALLENGES */
828 /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/
829 // Generate Alpha challenges - non-linearise the gate contributions
830 //
831 // There are 26 total subrelations in this honk relation, we do not need to non linearise the first sub relation.
832 // There are 25 total gate contributions, a gate contribution is analogous to
833 // a custom gate, it is an expression which must evaluate to zero for each
834 // row in the constraint matrix
835 //
836 // If we do not non-linearise sub relations, then sub relations which rely
837 // on the same wire will interact with each other's sums.
838
839 mcopy(0x20, LOOKUP_INVERSES_X_LOC, 0x80)
840
841 prev_challenge := mod(keccak256(0x00, 0xa0), p)
842 mstore(0x00, prev_challenge)
843 let alpha := and(prev_challenge, LOWER_127_MASK)
844 mstore(ALPHA_CHALLENGE_0, alpha)
845
846 // Compute powers of alpha: alpha^2, alpha^3, ..., alpha^26
847 let alpha_off_set := ALPHA_CHALLENGE_1
848 for {} lt(alpha_off_set, add(ALPHA_CHALLENGE_26, 0x20)) {} {
849 let prev_alpha := mload(sub(alpha_off_set, 0x20))
850 mstore(alpha_off_set, mulmod(prev_alpha, alpha, p))
851 alpha_off_set := add(alpha_off_set, 0x20)
852 }
853
854 /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
855 /* GATE CHALLENGES */
856 /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/
857
858 // Store the first gate challenge
859 prev_challenge := mod(keccak256(0x00, 0x20), p)
860 mstore(0x00, prev_challenge)
861 let gate_challenge := and(prev_challenge, LOWER_127_MASK)
862 mstore(GATE_CHALLENGE_0, gate_challenge)
863
864 let gate_off := GATE_CHALLENGE_1
865 for {} lt(gate_off, SUM_U_CHALLENGE_0) {} {
866 let prev := mload(sub(gate_off, 0x20))
867
868 mstore(gate_off, mulmod(prev, prev, p))
869 gate_off := add(gate_off, 0x20)
870 }
871
872 // Sumcheck Univariate challenges
873 // The algebraic relations of the Honk protocol are max degree-7.
874 // To prove satifiability, we multiply the relation by a random (POW) polynomial. We do this as we want all of our relations
875 // to be zero on every row - not for the sum of the relations to be zero. (Which is all sumcheck can do without this modification)
876 //
877 // As a result, in every round of sumcheck, the prover sends an degree-8 univariate polynomial.
878 // The sumcheck univariate challenge produces a challenge for each round of sumcheck, hashing the prev_challenge with
879 // a hash of the degree 8 univariate polynomial provided by the prover.
880 //
881 // 8 points are sent as it is enough to uniquely identify the polynomial
882 let read_off := SUMCHECK_UNIVARIATE_0_0_LOC
883 let write_off := SUM_U_CHALLENGE_0
884 for {} lt(read_off, QM_EVAL_LOC) {} {
885 // Increase by 20 * batched relation length (8)
886 // 0x20 * 0x8 = 0x100
887 mcopy(0x20, read_off, 0x100)
888
889 // Hash 0x100 + 0x20 (prev hash) = 0x120
890 prev_challenge := mod(keccak256(0x00, 0x120), p)
891 mstore(0x00, prev_challenge)
892
893 let sumcheck_u_challenge := and(prev_challenge, LOWER_127_MASK)
894 mstore(write_off, sumcheck_u_challenge)
895
896 // Progress read / write pointers
897 read_off := add(read_off, 0x100)
898 write_off := add(write_off, 0x20)
899 }
900
901 /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
902 /* RHO CHALLENGES */
903 /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/
904 // The RHO challenge is the hash of the evaluations of all of the wire values
905 // As per usual, it includes the previous challenge
906 // Evaluations of the following wires and their shifts (for relevant wires):
907 // - QM
908 // - QC
909 // - Q1 (QL)
910 // - Q2 (QR)
911 // - Q3 (QO)
912 // - Q4
913 // - QLOOKUP
914 // - QARITH
915 // - QRANGE
916 // - QELLIPTIC
917 // - QMEMORY
918 // - QNNF (NNF = Non Native Field)
919 // - QPOSEIDON2_EXTERNAL
920 // - QPOSEIDON2_INTERNAL
921 // - SIGMA1
922 // - SIGMA2
923 // - SIGMA3
924 // - SIGMA4
925 // - ID1
926 // - ID2
927 // - ID3
928 // - ID4
929 // - TABLE1
930 // - TABLE2
931 // - TABLE3
932 // - TABLE4
933 // - W1 (WL)
934 // - W2 (WR)
935 // - W3 (WO)
936 // - W4
937 // - Z_PERM
938 // - LOOKUP_INVERSES
939 // - LOOKUP_READ_COUNTS
940 // - LOOKUP_READ_TAGS
941 // - W1_SHIFT
942 // - W2_SHIFT
943 // - W3_SHIFT
944 // - W4_SHIFT
945 // - Z_PERM_SHIFT
946 //
947 // Hash of all of the above evaluations
948 // Number of bytes to copy = 0x20 * NUMBER_OF_ENTITIES (41) = 0x520
949 mcopy(0x20, QM_EVAL_LOC, 0x520)
950 prev_challenge := mod(keccak256(0x00, 0x540), p)
951 mstore(0x00, prev_challenge)
952
953 let rho := and(prev_challenge, LOWER_127_MASK)
954
955 mstore(RHO_CHALLENGE, rho)
956
957 /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
958 /* GEMINI R CHALLENGE */
959 /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/
960 // The Gemini R challenge contains a of all of commitments to all of the univariates
961 // evaluated in the Gemini Protocol
962 // So for multivariate polynomials in l variables, we will hash l - 1 commitments.
963 // For this implementation, we have logN number of of rounds and thus logN - 1 committments
964 // The format of these commitments are proof points, which are explained above
965 // 0x40 * (logN - 1)
966
967 mcopy(0x20, GEMINI_FOLD_UNIVARIATE_0_X_LOC, {{ GEMINI_FOLD_UNIVARIATE_LENGTH }})
968
969 prev_challenge := mod(keccak256(0x00, {{ GEMINI_FOLD_UNIVARIATE_HASH_LENGTH }}), p)
970 mstore(0x00, prev_challenge)
971
972 let geminiR := and(prev_challenge, LOWER_127_MASK)
973
974 mstore(GEMINI_R_CHALLENGE, geminiR)
975
976 /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
977 /* SHPLONK NU CHALLENGE */
978 /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/
979 // The shplonk nu challenge hashes the evaluations of the above gemini univariates
980 // 0x20 * logN = 0x20 * 15 = 0x1e0
981
982 mcopy(0x20, GEMINI_A_EVAL_0, {{ GEMINI_EVALS_LENGTH }})
983 prev_challenge := mod(keccak256(0x00, {{ GEMINI_EVALS_HASH_LENGTH }}), p)
984 mstore(0x00, prev_challenge)
985
986 let shplonkNu := and(prev_challenge, LOWER_127_MASK)
987 mstore(SHPLONK_NU_CHALLENGE, shplonkNu)
988
989 /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
990 /* SHPLONK Z CHALLENGE */
991 /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/
992 // Generate Shplonk Z
993 // Hash of the single shplonk Q commitment
994 mcopy(0x20, SHPLONK_Q_X_LOC, 0x40)
995 prev_challenge := mod(keccak256(0x00, 0x60), p)
996
997 let shplonkZ := and(prev_challenge, LOWER_127_MASK)
998 mstore(SHPLONK_Z_CHALLENGE, shplonkZ)
999
1000 /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
1001 /* CHALLENGES COMPLETE */
1002 /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/
1003 }
1004
1005 /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
1006 /* PUBLIC INPUT DELTA */
1007 /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/
1036 {
1037 let beta := mload(BETA_CHALLENGE)
1038 let gamma := mload(GAMMA_CHALLENGE)
1039 let pub_off := PUBLIC_INPUTS_OFFSET
1040
1041 let numerator_value := 1
1042 let denominator_value := 1
1043
1044 let p_clone := p // move p to the front of the stack
1045
1046 // Assume offset is less than p
1047 // numerator_acc = gamma + (beta * (PERMUTATION_ARGUMENT_VALUE_SEPARATOR + offset))
1048 let numerator_acc :=
1049 addmod(gamma, mulmod(beta, add(PERMUTATION_ARGUMENT_VALUE_SEPARATOR, pub_off), p_clone), p_clone)
1050 // demonimator_acc = gamma - (beta * (offset + 1))
1051 let beta_x_off := mulmod(beta, add(pub_off, 1), p_clone)
1052 let denominator_acc := addmod(gamma, sub(p_clone, beta_x_off), p_clone)
1053
1054 let valid_inputs := true
1055 // Load the starting point of the public inputs (jump over the selector and the length of public inputs [0x24])
1056 let public_inputs_ptr := add(calldataload(0x24), 0x24)
1057
1058 // endpoint_ptr = public_inputs_ptr + num_inputs * 0x20. // every public input is 0x20 bytes
1059 let endpoint_ptr := add(public_inputs_ptr, mul(REAL_NUMBER_PUBLIC_INPUTS, 0x20))
1060
1061 for {} lt(public_inputs_ptr, endpoint_ptr) { public_inputs_ptr := add(public_inputs_ptr, 0x20) } {
1062 // Get public inputs from calldata
1063 let input := calldataload(public_inputs_ptr)
1064
1065 valid_inputs := and(valid_inputs, lt(input, p_clone))
1066
1067 numerator_value := mulmod(numerator_value, addmod(numerator_acc, input, p_clone), p_clone)
1068 denominator_value := mulmod(denominator_value, addmod(denominator_acc, input, p_clone), p_clone)
1069
1070 numerator_acc := addmod(numerator_acc, beta, p_clone)
1071 denominator_acc := addmod(denominator_acc, sub(p_clone, beta), p_clone)
1072 }
1073
1074 // Revert if not all public inputs are field elements (i.e. < p)
1075 if iszero(valid_inputs) {
1076 mstore(0x00, VALUE_GE_FIELD_ORDER_SELECTOR)
1077 revert(0x00, 0x04)
1078 }
1079
1080 /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
1081 /* PUBLIC INPUT DELTA - Pairing points accum */
1082 /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/
1083 // Pairing points contribution to public inputs delta
1084 let pairing_points_ptr := PAIRING_POINT_0_X_0_LOC
1085 for {} lt(pairing_points_ptr, W_L_X_LOC) { pairing_points_ptr := add(pairing_points_ptr, 0x20) } {
1086 let input := mload(pairing_points_ptr)
1087
1088 numerator_value := mulmod(numerator_value, addmod(numerator_acc, input, p_clone), p_clone)
1089 denominator_value := mulmod(denominator_value, addmod(denominator_acc, input, p_clone), p_clone)
1090
1091 numerator_acc := addmod(numerator_acc, beta, p_clone)
1092 denominator_acc := addmod(denominator_acc, sub(p_clone, beta), p_clone)
1093 }
1094
1095 mstore(PUBLIC_INPUTS_DELTA_NUMERATOR_CHALLENGE, numerator_value)
1096 mstore(PUBLIC_INPUTS_DELTA_DENOMINATOR_CHALLENGE, denominator_value)
1097
1098 // TODO: batch with barycentric inverses
1099 let dom_inverse := 0
1100 {
1101 mstore(0, 0x20)
1102 mstore(0x20, 0x20)
1103 mstore(0x40, 0x20)
1104 mstore(0x60, denominator_value)
1105 mstore(0x80, P_SUB_2)
1106 mstore(0xa0, p)
1107 if iszero(staticcall(gas(), 0x05, 0x00, 0xc0, 0x00, 0x20)) {
1108 mstore(0x00, MODEXP_FAILED_SELECTOR)
1109 revert(0x00, 0x04)
1110 }
1111 // 1 / (0 . 1 . 2 . 3 . 4 . 5 . 6 . 7)
1112 dom_inverse := mload(0x00)
1113 }
1114 // Calculate the public inputs delta
1115 mstore(PUBLIC_INPUTS_DELTA_NUMERATOR_CHALLENGE, mulmod(numerator_value, dom_inverse, p))
1116 }
1117 /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
1118 /* PUBLIC INPUT DELTA - complete */
1119 /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/
1120
1121 /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
1122 /* SUMCHECK */
1123 /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/
1124 //
1125 // Sumcheck is used to prove that every relation 0 on each row of the witness.
1126 //
1127 // Given each of the columns of our trace is a multilinear polynomial 𝑃1,…,𝑃𝑁∈𝔽[𝑋0,…,𝑋𝑑−1]. We run sumcheck over the polynomial
1128 //
1129 // 𝐹̃ (𝑋0,…,𝑋𝑑−1)=𝑝𝑜𝑤𝛽(𝑋0,…,𝑋𝑑−1)⋅𝐹(𝑃1(𝑋0,…,𝑋𝑑−1),…,𝑃𝑁(𝑋0,…,𝑋𝑑−1))
1130 //
1131 // The Pow polynomial is a random polynomial that allows us to ceritify that the relations sum to 0 on each row of the witness,
1132 // rather than the entire sum just targeting 0.
1133 //
1134 // Each polynomial P in our implementation are the polys in the proof and the verification key. (W_1, W_2, W_3, W_4, Z_PERM, etc....)
1135 //
1136 // We start with a LOG_N variate multilinear polynomial, each round fixes a variable to a challenge value.
1137 // Each round the prover sends a round univariate poly, since the degree of our honk relations is 7 + the pow polynomial the prover
1138 // sends a degree-8 univariate on each round.
1139 // This is sent efficiently by sending 8 values, enough to represent a unique polynomial.
1140 // Barycentric evaluation is used to evaluate the polynomial at any point on the domain, given these 8 unique points.
1141 //
1142 // In the sumcheck protocol, the target sum for each round is the sum of the round univariate evaluated on 0 and 1.
1143 // 𝜎𝑖=?𝑆̃ 𝑖(0)+𝑆̃ 𝑖(1)
1144 // This is efficiently checked as S(0) and S(1) are sent by the prover as values of the round univariate.
1145 //
1146 // We compute the next challenge by evaluating the round univariate at a random challenge value.
1147 // 𝜎𝑖+1←𝑆̃ 𝑖(𝑢𝑖)
1148 // This evaluation is performed via barycentric evaluation.
1149 //
1150 // Once we have reduced the multilinear polynomials into single dimensional polys, we check the entire sumcheck relation matches the target sum.
1151 //
1152 // Below this is composed of 8 relations:
1153 // 1. Arithmetic relation - constrains arithmetic
1154 // 2. Permutaiton Relation - efficiently encodes copy constraints
1155 // 3. Log Derivative Lookup Relation - used for lookup operations
1156 // 4. Delta Range Relation - used for efficient range checks
1157 // 5. Memory Relation - used for efficient memory operations
1158 // 6. NNF Relation - used for efficient Non Native Field operations
1159 // 7. Poseidon2 External Relation - used for efficient in-circuit hashing
1160 // 8. Poseidon2 Internal Relation - used for efficient in-circuit hashing
1161 //
1162 // These are batched together and evaluated at the same time using the alpha challenges.
1163 //
1164 {
1165 // We write the barycentric domain values into memory
1166 // These are written once per program execution, and reused across all
1167 // sumcheck rounds
1168 mstore(BARYCENTRIC_LAGRANGE_DENOMINATOR_0_LOC, BARYCENTRIC_LAGRANGE_DENOMINATOR_0)
1169 mstore(BARYCENTRIC_LAGRANGE_DENOMINATOR_1_LOC, BARYCENTRIC_LAGRANGE_DENOMINATOR_1)
1170 mstore(BARYCENTRIC_LAGRANGE_DENOMINATOR_2_LOC, BARYCENTRIC_LAGRANGE_DENOMINATOR_2)
1171 mstore(BARYCENTRIC_LAGRANGE_DENOMINATOR_3_LOC, BARYCENTRIC_LAGRANGE_DENOMINATOR_3)
1172 mstore(BARYCENTRIC_LAGRANGE_DENOMINATOR_4_LOC, BARYCENTRIC_LAGRANGE_DENOMINATOR_4)
1173 mstore(BARYCENTRIC_LAGRANGE_DENOMINATOR_5_LOC, BARYCENTRIC_LAGRANGE_DENOMINATOR_5)
1174 mstore(BARYCENTRIC_LAGRANGE_DENOMINATOR_6_LOC, BARYCENTRIC_LAGRANGE_DENOMINATOR_6)
1175 mstore(BARYCENTRIC_LAGRANGE_DENOMINATOR_7_LOC, BARYCENTRIC_LAGRANGE_DENOMINATOR_7)
1176
1177 // Compute the target sums for each round of sumcheck
1178 {
1179 // This requires the barycentric inverses to be computed for each round
1180 // Write all of the non inverted barycentric denominators into memory
1181 let accumulator := 1
1182 let temp := LATER_SCRATCH_SPACE
1183 let bary_centric_inverses_off := BARYCENTRIC_DENOMINATOR_INVERSES_0_0_LOC
1184 {
1185 let round_challenge_off := SUM_U_CHALLENGE_0
1186 for { let round := 0 } lt(round, LOG_N) { round := add(round, 1) } {
1187 let round_challenge := mload(round_challenge_off)
1188 let bary_lagrange_denominator_off := BARYCENTRIC_LAGRANGE_DENOMINATOR_0_LOC
1189
1190 // Unrolled as this loop as it only has 8 iterations
1191 {
1192 let bary_lagrange_denominator := mload(bary_lagrange_denominator_off)
1193 let pre_inv :=
1194 mulmod(
1195 bary_lagrange_denominator,
1196 addmod(round_challenge, p, p), // sub(p, 0) = p
1197 p
1198 )
1199 mstore(bary_centric_inverses_off, pre_inv)
1200 temp := add(temp, 0x20)
1201 mstore(temp, accumulator)
1202 accumulator := mulmod(accumulator, pre_inv, p)
1203
1204 // increase offsets
1205 bary_lagrange_denominator_off := add(bary_lagrange_denominator_off, 0x20)
1206 bary_centric_inverses_off := add(bary_centric_inverses_off, 0x20)
1207
1208 // barycentric_index = 1
1209 bary_lagrange_denominator := mload(bary_lagrange_denominator_off)
1210 pre_inv := mulmod(bary_lagrange_denominator, addmod(round_challenge, P_SUB_1, p), p)
1211 mstore(bary_centric_inverses_off, pre_inv)
1212 temp := add(temp, 0x20)
1213 mstore(temp, accumulator)
1214 accumulator := mulmod(accumulator, pre_inv, p)
1215
1216 // increase offsets
1217 bary_lagrange_denominator_off := add(bary_lagrange_denominator_off, 0x20)
1218 bary_centric_inverses_off := add(bary_centric_inverses_off, 0x20)
1219
1220 // barycentric_index = 2
1221 bary_lagrange_denominator := mload(bary_lagrange_denominator_off)
1222 pre_inv := mulmod(bary_lagrange_denominator, addmod(round_challenge, P_SUB_2, p), p)
1223 mstore(bary_centric_inverses_off, pre_inv)
1224 temp := add(temp, 0x20)
1225 mstore(temp, accumulator)
1226 accumulator := mulmod(accumulator, pre_inv, p)
1227
1228 // increase offsets
1229 bary_lagrange_denominator_off := add(bary_lagrange_denominator_off, 0x20)
1230 bary_centric_inverses_off := add(bary_centric_inverses_off, 0x20)
1231
1232 // barycentric_index = 3
1233 bary_lagrange_denominator := mload(bary_lagrange_denominator_off)
1234 pre_inv := mulmod(bary_lagrange_denominator, addmod(round_challenge, P_SUB_3, p), p)
1235 mstore(bary_centric_inverses_off, pre_inv)
1236 temp := add(temp, 0x20)
1237 mstore(temp, accumulator)
1238 accumulator := mulmod(accumulator, pre_inv, p)
1239
1240 // increase offsets
1241 bary_lagrange_denominator_off := add(bary_lagrange_denominator_off, 0x20)
1242 bary_centric_inverses_off := add(bary_centric_inverses_off, 0x20)
1243
1244 // barycentric_index = 4
1245 bary_lagrange_denominator := mload(bary_lagrange_denominator_off)
1246 pre_inv := mulmod(bary_lagrange_denominator, addmod(round_challenge, P_SUB_4, p), p)
1247 mstore(bary_centric_inverses_off, pre_inv)
1248 temp := add(temp, 0x20)
1249 mstore(temp, accumulator)
1250 accumulator := mulmod(accumulator, pre_inv, p)
1251
1252 // increase offsets
1253 bary_lagrange_denominator_off := add(bary_lagrange_denominator_off, 0x20)
1254 bary_centric_inverses_off := add(bary_centric_inverses_off, 0x20)
1255
1256 // barycentric_index = 5
1257 bary_lagrange_denominator := mload(bary_lagrange_denominator_off)
1258 pre_inv := mulmod(bary_lagrange_denominator, addmod(round_challenge, P_SUB_5, p), p)
1259 mstore(bary_centric_inverses_off, pre_inv)
1260 temp := add(temp, 0x20)
1261 mstore(temp, accumulator)
1262 accumulator := mulmod(accumulator, pre_inv, p)
1263
1264 // increase offsets
1265 bary_lagrange_denominator_off := add(bary_lagrange_denominator_off, 0x20)
1266 bary_centric_inverses_off := add(bary_centric_inverses_off, 0x20)
1267
1268 // barycentric_index = 6
1269 bary_lagrange_denominator := mload(bary_lagrange_denominator_off)
1270 pre_inv := mulmod(bary_lagrange_denominator, addmod(round_challenge, P_SUB_6, p), p)
1271 mstore(bary_centric_inverses_off, pre_inv)
1272 temp := add(temp, 0x20)
1273 mstore(temp, accumulator)
1274 accumulator := mulmod(accumulator, pre_inv, p)
1275
1276 // increase offsets
1277 bary_lagrange_denominator_off := add(bary_lagrange_denominator_off, 0x20)
1278 bary_centric_inverses_off := add(bary_centric_inverses_off, 0x20)
1279
1280 // barycentric_index = 7
1281 bary_lagrange_denominator := mload(bary_lagrange_denominator_off)
1282 pre_inv := mulmod(bary_lagrange_denominator, addmod(round_challenge, P_SUB_7, p), p)
1283 mstore(bary_centric_inverses_off, pre_inv)
1284 temp := add(temp, 0x20)
1285 mstore(temp, accumulator)
1286 accumulator := mulmod(accumulator, pre_inv, p)
1287
1288 // increase offsets
1289 bary_lagrange_denominator_off := add(bary_lagrange_denominator_off, 0x20)
1290 bary_centric_inverses_off := add(bary_centric_inverses_off, 0x20)
1291 }
1292 round_challenge_off := add(round_challenge_off, 0x20)
1293 }
1294 }
1295
1296 // Invert all of the barycentric denominators as a single batch
1297 {
1298 {
1299 mstore(0, 0x20)
1300 mstore(0x20, 0x20)
1301 mstore(0x40, 0x20)
1302 mstore(0x60, accumulator)
1303 mstore(0x80, P_SUB_2)
1304 mstore(0xa0, p)
1305 if iszero(staticcall(gas(), 0x05, 0x00, 0xc0, 0x00, 0x20)) {
1306 mstore(0x00, MODEXP_FAILED_SELECTOR)
1307 revert(0x00, 0x04)
1308 }
1309
1310 accumulator := mload(0x00)
1311 }
1312
1313 // Normalise as last loop will have incremented the offset
1314 bary_centric_inverses_off := sub(bary_centric_inverses_off, 0x20)
1315 for {} gt(bary_centric_inverses_off, SUM_U_CHALLENGE_{{ LOG_N_MINUS_ONE }}) {
1316 bary_centric_inverses_off := sub(bary_centric_inverses_off, 0x20)
1317 } {
1318 let tmp := mulmod(accumulator, mload(temp), p)
1319 accumulator := mulmod(accumulator, mload(bary_centric_inverses_off), p)
1320 mstore(bary_centric_inverses_off, tmp)
1321
1322 temp := sub(temp, 0x20)
1323 }
1324 }
1325 }
1326
1327 let valid := true
1328 let round_target := 0
1329 let pow_partial_evaluation := 1
1330 let gate_challenge_off := GATE_CHALLENGE_0
1331 let round_univariates_off := SUMCHECK_UNIVARIATE_0_0_LOC
1332
1333 let challenge_off := SUM_U_CHALLENGE_0
1334 let bary_inverses_off := BARYCENTRIC_DENOMINATOR_INVERSES_0_0_LOC
1335
1336 for { let round := 0 } lt(round, LOG_N) { round := add(round, 1) } {
1337 let round_challenge := mload(challenge_off)
1338
1339 // Total sum = u[0] + u[1]
1340 let total_sum := addmod(mload(round_univariates_off), mload(add(round_univariates_off, 0x20)), p)
1341 valid := and(valid, eq(total_sum, round_target))
1342
1343 // Compute next target sum
1344 let numerator_value := round_challenge
1345 numerator_value := mulmod(numerator_value, addmod(round_challenge, P_SUB_1, p), p)
1346 numerator_value := mulmod(numerator_value, addmod(round_challenge, P_SUB_2, p), p)
1347 numerator_value := mulmod(numerator_value, addmod(round_challenge, P_SUB_3, p), p)
1348 numerator_value := mulmod(numerator_value, addmod(round_challenge, P_SUB_4, p), p)
1349 numerator_value := mulmod(numerator_value, addmod(round_challenge, P_SUB_5, p), p)
1350 numerator_value := mulmod(numerator_value, addmod(round_challenge, P_SUB_6, p), p)
1351 numerator_value := mulmod(numerator_value, addmod(round_challenge, P_SUB_7, p), p)
1352
1353 // // Compute the next round target
1354 round_target := 0
1355 for { let i := 0 } lt(i, BATCHED_RELATION_PARTIAL_LENGTH) { i := add(i, 1) } {
1356 let term := mload(round_univariates_off)
1357 let inverse := mload(bary_inverses_off)
1358
1359 term := mulmod(term, inverse, p)
1360 round_target := addmod(round_target, term, p)
1361 round_univariates_off := add(round_univariates_off, 0x20)
1362 bary_inverses_off := add(bary_inverses_off, 0x20)
1363 }
1364
1365 round_target := mulmod(round_target, numerator_value, p)
1366
1367 // Partially evaluate POW
1368 let gate_challenge := mload(gate_challenge_off)
1369 let gate_challenge_minus_one := sub(gate_challenge, 1)
1370
1371 let univariate_evaluation := addmod(1, mulmod(round_challenge, gate_challenge_minus_one, p), p)
1372
1373 pow_partial_evaluation := mulmod(pow_partial_evaluation, univariate_evaluation, p)
1374
1375 gate_challenge_off := add(gate_challenge_off, 0x20)
1376 challenge_off := add(challenge_off, 0x20)
1377 }
1378
1379 if iszero(valid) {
1380 mstore(0x00, SUMCHECK_FAILED_SELECTOR)
1381 revert(0x00, 0x04)
1382 }
1383
1384 // The final sumcheck round; accumulating evaluations
1385 // Uses pow partial evaluation as the gate scaling factor
1386
1387 mstore(POW_PARTIAL_EVALUATION_LOC, pow_partial_evaluation)
1388 mstore(FINAL_ROUND_TARGET_LOC, round_target)
1389
1390 /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
1391 /* LOGUP RELATION */
1392 /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/
1393 {
1429 let w1q1 := mulmod(mload(W1_EVAL_LOC), mload(QL_EVAL_LOC), p)
1430 let w2q2 := mulmod(mload(W2_EVAL_LOC), mload(QR_EVAL_LOC), p)
1431 let w3q3 := mulmod(mload(W3_EVAL_LOC), mload(QO_EVAL_LOC), p)
1432 let w4q3 := mulmod(mload(W4_EVAL_LOC), mload(Q4_EVAL_LOC), p)
1433
1434 let q_arith := mload(QARITH_EVAL_LOC)
1435 // w1w2qm := (w_1 . w_2 . q_m . (QARITH_EVAL_LOC - 3)) / 2
1436 let w1w2qm :=
1437 mulmod(
1438 mulmod(
1439 mulmod(mulmod(mload(W1_EVAL_LOC), mload(W2_EVAL_LOC), p), mload(QM_EVAL_LOC), p),
1440 addmod(q_arith, P_SUB_3, p),
1441 p
1442 ),
1443 NEG_HALF_MODULO_P,
1444 p
1445 )
1446
1447 // (w_1 . w_2 . q_m . (q_arith - 3)) / -2) + (w_1 . q_1) + (w_2 . q_2) + (w_3 . q_3) + (w_4 . q_4) + q_c
1448 let identity :=
1449 addmod(
1450 mload(QC_EVAL_LOC),
1451 addmod(w4q3, addmod(w3q3, addmod(w2q2, addmod(w1q1, w1w2qm, p), p), p), p),
1452 p
1453 )
1454
1455 // if q_arith == 3 we evaluate an additional mini addition gate (on top of the regular one), where:
1456 // w_1 + w_4 - w_1_omega + q_m = 0
1457 // we use this gate to save an addition gate when adding or subtracting non-native field elements
1458 // α * (q_arith - 2) * (w_1 + w_4 - w_1_omega + q_m)
1459 let extra_small_addition_gate_identity :=
1460 mulmod(
1461 addmod(q_arith, P_SUB_2, p),
1462 addmod(
1463 mload(QM_EVAL_LOC),
1464 addmod(
1465 sub(p, mload(W1_SHIFT_EVAL_LOC)),
1466 addmod(mload(W1_EVAL_LOC), mload(W4_EVAL_LOC), p),
1467 p
1468 ),
1469 p
1470 ),
1471 p
1472 )
1473
1474 // Split up the two relations
1475 let contribution_0 :=
1476 addmod(identity, mulmod(addmod(q_arith, P_SUB_1, p), mload(W4_SHIFT_EVAL_LOC), p), p)
1477 contribution_0 := mulmod(mulmod(contribution_0, q_arith, p), mload(POW_PARTIAL_EVALUATION_LOC), p)
1478 mstore(SUBRELATION_EVAL_0_LOC, contribution_0)
1479
1480 let contribution_1 := mulmod(extra_small_addition_gate_identity, addmod(q_arith, P_SUB_1, p), p)
1481 contribution_1 := mulmod(contribution_1, q_arith, p)
1482 contribution_1 := mulmod(contribution_1, mload(POW_PARTIAL_EVALUATION_LOC), p)
1483 mstore(SUBRELATION_EVAL_1_LOC, contribution_1)
1484 }
1485
1486 /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
1487 /* PERMUTATION RELATION */
1488 /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/
1489 {
1490 let beta := mload(BETA_CHALLENGE)
1491 let gamma := mload(GAMMA_CHALLENGE)
1492
1501 let t1 :=
1502 mulmod(
1503 add(add(mload(W1_EVAL_LOC), gamma), mulmod(beta, mload(ID1_EVAL_LOC), p)),
1504 add(add(mload(W2_EVAL_LOC), gamma), mulmod(beta, mload(ID2_EVAL_LOC), p)),
1505 p
1506 )
1507 let t2 :=
1508 mulmod(
1509 add(add(mload(W3_EVAL_LOC), gamma), mulmod(beta, mload(ID3_EVAL_LOC), p)),
1510 add(add(mload(W4_EVAL_LOC), gamma), mulmod(beta, mload(ID4_EVAL_LOC), p)),
1511 p
1512 )
1513 let numerator := mulmod(t1, t2, p)
1514 t1 := mulmod(
1515 add(add(mload(W1_EVAL_LOC), gamma), mulmod(beta, mload(SIGMA1_EVAL_LOC), p)),
1516 add(add(mload(W2_EVAL_LOC), gamma), mulmod(beta, mload(SIGMA2_EVAL_LOC), p)),
1517 p
1518 )
1519 t2 := mulmod(
1520 add(add(mload(W3_EVAL_LOC), gamma), mulmod(beta, mload(SIGMA3_EVAL_LOC), p)),
1521 add(add(mload(W4_EVAL_LOC), gamma), mulmod(beta, mload(SIGMA4_EVAL_LOC), p)),
1522 p
1523 )
1524 let denominator := mulmod(t1, t2, p)
1525
1526 {
1527 let acc :=
1528 mulmod(addmod(mload(Z_PERM_EVAL_LOC), mload(LAGRANGE_FIRST_EVAL_LOC), p), numerator, p)
1529
1530 acc := addmod(
1531 acc,
1532 sub(
1533 p,
1534 mulmod(
1535 addmod(
1536 mload(Z_PERM_SHIFT_EVAL_LOC),
1537 mulmod(
1538 mload(LAGRANGE_LAST_EVAL_LOC),
1539 mload(PUBLIC_INPUTS_DELTA_NUMERATOR_CHALLENGE),
1540 p
1541 ),
1542 p
1543 ),
1544 denominator,
1545 p
1546 )
1547 ),
1548 p
1549 )
1550
1551 acc := mulmod(acc, mload(POW_PARTIAL_EVALUATION_LOC), p)
1552 mstore(SUBRELATION_EVAL_2_LOC, acc)
1553
1554 acc := mulmod(
1555 mulmod(mload(LAGRANGE_LAST_EVAL_LOC), mload(Z_PERM_SHIFT_EVAL_LOC), p),
1556 mload(POW_PARTIAL_EVALUATION_LOC),
1557 p
1558 )
1559 mstore(SUBRELATION_EVAL_3_LOC, acc)
1560 }
1561 }
1562
1563 /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
1564 /* LOGUP WIDGET EVALUATION */
1565 /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/
1566 // Note: Using beta powers for column batching and gamma for offset ensures soundness
1567 // beta and gamma must be independent challenges (they come from splitting the same hash)
1568 {
1569 let gamma := mload(GAMMA_CHALLENGE)
1570 let beta := mload(BETA_CHALLENGE)
1571 // Compute beta powers inline (β², β³) for lookup column batching
1572 let beta_sqr := mulmod(beta, beta, p)
1573 let beta_cube := mulmod(beta_sqr, beta, p)
1574
1575 // table_term = table_1 + γ + table_2 * β + table_3 * β² + table_4 * β³
1576 let t0 :=
1577 addmod(addmod(mload(TABLE1_EVAL_LOC), gamma, p), mulmod(mload(TABLE2_EVAL_LOC), beta, p), p)
1578 let t1 :=
1579 addmod(
1580 mulmod(mload(TABLE3_EVAL_LOC), beta_sqr, p),
1581 mulmod(mload(TABLE4_EVAL_LOC), beta_cube, p),
1582 p
1583 )
1584 let table_term := addmod(t0, t1, p)
1585
1586 // lookup_term = derived_entry_1 + γ + derived_entry_2 * β + derived_entry_3 * β² + q_index * β³
1587 t0 := addmod(
1588 addmod(mload(W1_EVAL_LOC), gamma, p),
1589 mulmod(mload(QR_EVAL_LOC), mload(W1_SHIFT_EVAL_LOC), p),
1590 p
1591 )
1592 t1 := addmod(mload(W2_EVAL_LOC), mulmod(mload(QM_EVAL_LOC), mload(W2_SHIFT_EVAL_LOC), p), p)
1593 let t2 := addmod(mload(W3_EVAL_LOC), mulmod(mload(QC_EVAL_LOC), mload(W3_SHIFT_EVAL_LOC), p), p)
1594
1595 let lookup_term := addmod(t0, mulmod(t1, beta, p), p)
1596 lookup_term := addmod(lookup_term, mulmod(t2, beta_sqr, p), p)
1597 lookup_term := addmod(lookup_term, mulmod(mload(QO_EVAL_LOC), beta_cube, p), p)
1598
1599 let lookup_inverse := mulmod(mload(LOOKUP_INVERSES_EVAL_LOC), table_term, p)
1600 let table_inverse := mulmod(mload(LOOKUP_INVERSES_EVAL_LOC), lookup_term, p)
1601
1602 let inverse_exists_xor := addmod(mload(LOOKUP_READ_TAGS_EVAL_LOC), mload(QLOOKUP_EVAL_LOC), p)
1603 inverse_exists_xor := addmod(
1604 inverse_exists_xor,
1605 sub(p, mulmod(mload(LOOKUP_READ_TAGS_EVAL_LOC), mload(QLOOKUP_EVAL_LOC), p)),
1606 p
1607 )
1608
1609 let accumulator_none := mulmod(mulmod(lookup_term, table_term, p), mload(LOOKUP_INVERSES_EVAL_LOC), p)
1610 accumulator_none := addmod(accumulator_none, sub(p, inverse_exists_xor), p)
1611 accumulator_none := mulmod(accumulator_none, mload(POW_PARTIAL_EVALUATION_LOC), p)
1612
1613 let accumulator_one := mulmod(mload(QLOOKUP_EVAL_LOC), lookup_inverse, p)
1614 accumulator_one := addmod(
1615 accumulator_one,
1616 sub(p, mulmod(mload(LOOKUP_READ_COUNTS_EVAL_LOC), table_inverse, p)),
1617 p
1618 )
1619
1620 let read_tag := mload(LOOKUP_READ_TAGS_EVAL_LOC)
1621 let read_tag_boolean_relation := mulmod(read_tag, addmod(read_tag, P_SUB_1, p), p)
1622 read_tag_boolean_relation := mulmod(read_tag_boolean_relation, mload(POW_PARTIAL_EVALUATION_LOC), p)
1623
1624 mstore(SUBRELATION_EVAL_4_LOC, accumulator_none)
1625 mstore(SUBRELATION_EVAL_5_LOC, accumulator_one)
1626 mstore(SUBRELATION_EVAL_6_LOC, read_tag_boolean_relation)
1627 }
1628
1629 /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
1630 /* DELTA RANGE RELATION */
1631 /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/
1632 {
1633 // TODO(md): optimise the calculations
1634 let minus_one := P_SUB_1
1635 let minus_two := P_SUB_2
1636 let minus_three := P_SUB_3
1637
1638 let delta_1 := addmod(mload(W2_EVAL_LOC), sub(p, mload(W1_EVAL_LOC)), p)
1639 let delta_2 := addmod(mload(W3_EVAL_LOC), sub(p, mload(W2_EVAL_LOC)), p)
1640 let delta_3 := addmod(mload(W4_EVAL_LOC), sub(p, mload(W3_EVAL_LOC)), p)
1641 let delta_4 := addmod(mload(W1_SHIFT_EVAL_LOC), sub(p, mload(W4_EVAL_LOC)), p)
1642
1643 {
1644 let acc := delta_1
1645 acc := mulmod(acc, addmod(delta_1, minus_one, p), p)
1646 acc := mulmod(acc, addmod(delta_1, minus_two, p), p)
1647 acc := mulmod(acc, addmod(delta_1, minus_three, p), p)
1648 acc := mulmod(acc, mload(QRANGE_EVAL_LOC), p)
1649 acc := mulmod(acc, mload(POW_PARTIAL_EVALUATION_LOC), p)
1650 mstore(SUBRELATION_EVAL_7_LOC, acc)
1651 }
1652
1653 {
1654 let acc := delta_2
1655 acc := mulmod(acc, addmod(delta_2, minus_one, p), p)
1656 acc := mulmod(acc, addmod(delta_2, minus_two, p), p)
1657 acc := mulmod(acc, addmod(delta_2, minus_three, p), p)
1658 acc := mulmod(acc, mload(QRANGE_EVAL_LOC), p)
1659 acc := mulmod(acc, mload(POW_PARTIAL_EVALUATION_LOC), p)
1660 mstore(SUBRELATION_EVAL_8_LOC, acc)
1661 }
1662
1663 {
1664 let acc := delta_3
1665 acc := mulmod(acc, addmod(delta_3, minus_one, p), p)
1666 acc := mulmod(acc, addmod(delta_3, minus_two, p), p)
1667 acc := mulmod(acc, addmod(delta_3, minus_three, p), p)
1668 acc := mulmod(acc, mload(QRANGE_EVAL_LOC), p)
1669 acc := mulmod(acc, mload(POW_PARTIAL_EVALUATION_LOC), p)
1670 mstore(SUBRELATION_EVAL_9_LOC, acc)
1671 }
1672
1673 {
1674 let acc := delta_4
1675 acc := mulmod(acc, addmod(delta_4, minus_one, p), p)
1676 acc := mulmod(acc, addmod(delta_4, minus_two, p), p)
1677 acc := mulmod(acc, addmod(delta_4, minus_three, p), p)
1678 acc := mulmod(acc, mload(QRANGE_EVAL_LOC), p)
1679 acc := mulmod(acc, mload(POW_PARTIAL_EVALUATION_LOC), p)
1680 mstore(SUBRELATION_EVAL_10_LOC, acc)
1681 }
1682 }
1683
1684 /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
1685 /* ELLIPTIC CURVE RELATION */
1686 /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/
1687 {
1688 // Contribution 10 point addition, x-coordinate check
1689 // q_elliptic * (x3 + x2 + x1)(x2 - x1)(x2 - x1) - y2^2 - y1^2 + 2(y2y1)*q_sign = 0
1690 let x_diff := addmod(mload(EC_X_2), sub(p, mload(EC_X_1)), p)
1691 let y1_sqr := mulmod(mload(EC_Y_1), mload(EC_Y_1), p)
1692 {
1693 let y2_sqr := mulmod(mload(EC_Y_2), mload(EC_Y_2), p)
1694 let y1y2 := mulmod(mulmod(mload(EC_Y_1), mload(EC_Y_2), p), mload(EC_Q_SIGN), p)
1695 let x_add_identity := addmod(mload(EC_X_3), addmod(mload(EC_X_2), mload(EC_X_1), p), p)
1696 x_add_identity := mulmod(mulmod(x_add_identity, x_diff, p), x_diff, p)
1697 x_add_identity := addmod(x_add_identity, sub(p, y2_sqr), p)
1698 x_add_identity := addmod(x_add_identity, sub(p, y1_sqr), p)
1699 x_add_identity := addmod(x_add_identity, y1y2, p)
1700 x_add_identity := addmod(x_add_identity, y1y2, p)
1701
1702 let eval := mulmod(x_add_identity, mload(POW_PARTIAL_EVALUATION_LOC), p)
1703 eval := mulmod(eval, mload(QELLIPTIC_EVAL_LOC), p)
1704 eval := mulmod(eval, addmod(1, sub(p, mload(EC_Q_IS_DOUBLE)), p), p)
1705 mstore(SUBRELATION_EVAL_11_LOC, eval)
1706 }
1707
1708 {
1709 let y1_plus_y3 := addmod(mload(EC_Y_1), mload(EC_Y_3), p)
1710 let y_diff := mulmod(mload(EC_Y_2), mload(EC_Q_SIGN), p)
1711 y_diff := addmod(y_diff, sub(p, mload(EC_Y_1)), p)
1712 let y_add_identity := mulmod(y1_plus_y3, x_diff, p)
1713 y_add_identity := addmod(
1714 y_add_identity,
1715 mulmod(addmod(mload(EC_X_3), sub(p, mload(EC_X_1)), p), y_diff, p),
1716 p
1717 )
1718
1719 let eval := mulmod(y_add_identity, mload(POW_PARTIAL_EVALUATION_LOC), p)
1720 eval := mulmod(eval, mload(QELLIPTIC_EVAL_LOC), p)
1721 eval := mulmod(eval, addmod(1, sub(p, mload(EC_Q_IS_DOUBLE)), p), p)
1722 mstore(SUBRELATION_EVAL_12_LOC, eval)
1723 }
1724
1725 {
1726 let x_pow_4 := mulmod(addmod(y1_sqr, GRUMPKIN_CURVE_B_PARAMETER_NEGATED, p), mload(EC_X_1), p)
1727 let y1_sqr_mul_4 := addmod(y1_sqr, y1_sqr, p)
1728 y1_sqr_mul_4 := addmod(y1_sqr_mul_4, y1_sqr_mul_4, p)
1729
1730 let x1_pow_4_mul_9 := mulmod(x_pow_4, 9, p)
1731
1732 let ep_x_double_identity := addmod(mload(EC_X_3), addmod(mload(EC_X_1), mload(EC_X_1), p), p)
1733 ep_x_double_identity := mulmod(ep_x_double_identity, y1_sqr_mul_4, p)
1734 ep_x_double_identity := addmod(ep_x_double_identity, sub(p, x1_pow_4_mul_9), p)
1735
1736 let acc := mulmod(ep_x_double_identity, mload(POW_PARTIAL_EVALUATION_LOC), p)
1737 acc := mulmod(mulmod(acc, mload(QELLIPTIC_EVAL_LOC), p), mload(EC_Q_IS_DOUBLE), p)
1738 acc := addmod(acc, mload(SUBRELATION_EVAL_11_LOC), p)
1739
1740 // Add to existing contribution - and double check that numbers here
1741 mstore(SUBRELATION_EVAL_11_LOC, acc)
1742 }
1743
1744 {
1745 let x1_sqr_mul_3 :=
1746 mulmod(addmod(addmod(mload(EC_X_1), mload(EC_X_1), p), mload(EC_X_1), p), mload(EC_X_1), p)
1747 let y_double_identity :=
1748 mulmod(x1_sqr_mul_3, addmod(mload(EC_X_1), sub(p, mload(EC_X_3)), p), p)
1749 y_double_identity := addmod(
1750 y_double_identity,
1751 sub(
1752 p,
1753 mulmod(
1754 addmod(mload(EC_Y_1), mload(EC_Y_1), p),
1755 addmod(mload(EC_Y_1), mload(EC_Y_3), p),
1756 p
1757 )
1758 ),
1759 p
1760 )
1761
1762 let acc := mulmod(y_double_identity, mload(POW_PARTIAL_EVALUATION_LOC), p)
1763 acc := mulmod(mulmod(acc, mload(QELLIPTIC_EVAL_LOC), p), mload(EC_Q_IS_DOUBLE), p)
1764 acc := addmod(acc, mload(SUBRELATION_EVAL_12_LOC), p)
1765
1766 // Add to existing contribution - and double check that numbers here
1767 mstore(SUBRELATION_EVAL_12_LOC, acc)
1768 }
1769 }
1770
1771 /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
1772 /* MEMORY RELATION */
1773 /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/
1774 {
1775 {
1827 // TODO(md): update these - formula has changed with lower degree
1828 let memory_record_check := mulmod(mload(W3_EVAL_LOC), mload(ETA_THREE_CHALLENGE), p)
1829 memory_record_check := addmod(
1830 memory_record_check,
1831 mulmod(mload(W2_EVAL_LOC), mload(ETA_TWO_CHALLENGE), p),
1832 p
1833 )
1834 memory_record_check := addmod(
1835 memory_record_check,
1836 mulmod(mload(W1_EVAL_LOC), mload(ETA_CHALLENGE), p),
1837 p
1838 )
1839 memory_record_check := addmod(memory_record_check, mload(QC_EVAL_LOC), p)
1840
1841 let partial_record_check := memory_record_check
1842 memory_record_check := addmod(memory_record_check, sub(p, mload(W4_EVAL_LOC)), p)
1843
1844 mstore(AUX_MEMORY_CHECK_IDENTITY, memory_record_check)
1845
1861 // index_delta = w_1_omega - w_1
1862 let index_delta := addmod(mload(W1_SHIFT_EVAL_LOC), sub(p, mload(W1_EVAL_LOC)), p)
1863
1864 // record_delta = w_4_omega - w_4
1865 let record_delta := addmod(mload(W4_SHIFT_EVAL_LOC), sub(p, mload(W4_EVAL_LOC)), p)
1866
1867 // index_is_monotonically_increasing = index_delta * (index_delta - 1)
1868 let index_is_monotonically_increasing := mulmod(index_delta, addmod(index_delta, P_SUB_1, p), p)
1869
1870 // adjacent_values_match_if_adjacent_indices_match = record_delta * (1 - index_delta)
1871 let adjacent_values_match_if_adjacent_indices_match :=
1872 mulmod(record_delta, addmod(1, sub(p, index_delta), p), p)
1873
1874 mstore(
1875 SUBRELATION_EVAL_14_LOC,
1876 mulmod(
1877 adjacent_values_match_if_adjacent_indices_match,
1878 mulmod(
1879 mload(QL_EVAL_LOC),
1880 mulmod(
1881 mload(QR_EVAL_LOC),
1882 mulmod(mload(QMEMORY_EVAL_LOC), mload(POW_PARTIAL_EVALUATION_LOC), p),
1883 p
1884 ),
1885 p
1886 ),
1887 p
1888 )
1889 )
1890
1891 // ROM_CONSISTENCY_CHECK_2
1892 mstore(
1893 SUBRELATION_EVAL_15_LOC,
1894 mulmod(
1895 index_is_monotonically_increasing,
1896 mulmod(
1897 mload(QL_EVAL_LOC),
1898 mulmod(
1899 mload(QR_EVAL_LOC),
1900 mulmod(mload(QMEMORY_EVAL_LOC), mload(POW_PARTIAL_EVALUATION_LOC), p),
1901 p
1902 ),
1903 p
1904 ),
1905 p
1906 )
1907 )
1908
1909 mstore(
1910 AUX_ROM_CONSISTENCY_CHECK_IDENTITY,
1911 mulmod(memory_record_check, mulmod(mload(QL_EVAL_LOC), mload(QR_EVAL_LOC), p), p)
1912 )
1913
1914 {
1941 let next_gate_access_type := mulmod(mload(W3_SHIFT_EVAL_LOC), mload(ETA_THREE_CHALLENGE), p)
1942 next_gate_access_type := addmod(
1943 next_gate_access_type,
1944 mulmod(mload(W2_SHIFT_EVAL_LOC), mload(ETA_TWO_CHALLENGE), p),
1945 p
1946 )
1947 next_gate_access_type := addmod(
1948 next_gate_access_type,
1949 mulmod(mload(W1_SHIFT_EVAL_LOC), mload(ETA_CHALLENGE), p),
1950 p
1951 )
1952 next_gate_access_type := addmod(mload(W4_SHIFT_EVAL_LOC), sub(p, next_gate_access_type), p)
1953
1954 // value_delta = w_3_omega - w_3
1955 let value_delta := addmod(mload(W3_SHIFT_EVAL_LOC), sub(p, mload(W3_EVAL_LOC)), p)
1956 // adjacent_values_match_if_adjacent_indices_match_and_next_access_is_a_read_operation = (1 - index_delta) * value_delta * (1 - next_gate_access_type);
1957
1958 let adjacent_values_match_if_adjacent_indices_match_and_next_access_is_a_read_operation :=
1959 mulmod(
1960 addmod(1, sub(p, index_delta), p),
1961 mulmod(value_delta, addmod(1, sub(p, next_gate_access_type), p), p),
1962 p
1963 )
1964
1965 // We can't apply the RAM consistency check identity on the final entry in the sorted list (the wires in the
1966 // next gate would make the identity fail). We need to validate that its 'access type' bool is correct. Can't
1967 // do with an arithmetic gate because of the `eta` factors. We need to check that the *next* gate's access
1968 // type is correct, to cover this edge case
1969 // deg 2 or 4
1975 let access_type := addmod(mload(W4_EVAL_LOC), sub(p, partial_record_check), p)
1976 let access_check := mulmod(access_type, addmod(access_type, P_SUB_1, p), p)
1977 let next_gate_access_type_is_boolean :=
1978 mulmod(next_gate_access_type, addmod(next_gate_access_type, P_SUB_1, p), p)
1979
1980 // scaled_activation_selector = q_arith * q_aux * alpha
1981 let scaled_activation_selector :=
1982 mulmod(
1983 mload(QO_EVAL_LOC),
1984 mulmod(mload(QMEMORY_EVAL_LOC), mload(POW_PARTIAL_EVALUATION_LOC), p),
1985 p
1986 )
1987
1988 mstore(
1989 SUBRELATION_EVAL_16_LOC,
1990 mulmod(
1991 adjacent_values_match_if_adjacent_indices_match_and_next_access_is_a_read_operation,
1992 scaled_activation_selector,
1993 p
1994 )
1995 )
1996
1997 mstore(
1998 SUBRELATION_EVAL_17_LOC,
1999 mulmod(index_is_monotonically_increasing, scaled_activation_selector, p)
2000 )
2001
2002 mstore(
2003 SUBRELATION_EVAL_18_LOC,
2004 mulmod(next_gate_access_type_is_boolean, scaled_activation_selector, p)
2005 )
2006
2007 mstore(AUX_RAM_CONSISTENCY_CHECK_IDENTITY, mulmod(access_check, mload(QO_EVAL_LOC), p))
2008 }
2009
2010 {
2011 // timestamp_delta = w_2_omega - w_2
2012 let timestamp_delta := addmod(mload(W2_SHIFT_EVAL_LOC), sub(p, mload(W2_EVAL_LOC)), p)
2013
2014 // RAM_timestamp_check_identity = (1 - index_delta) * timestamp_delta - w_3
2015 let RAM_TIMESTAMP_CHECK_IDENTITY :=
2016 addmod(
2017 mulmod(timestamp_delta, addmod(1, sub(p, index_delta), p), p),
2018 sub(p, mload(W3_EVAL_LOC)),
2019 p
2020 )
2021
2033 let memory_identity := mload(AUX_ROM_CONSISTENCY_CHECK_IDENTITY)
2034 memory_identity := addmod(
2035 memory_identity,
2036 mulmod(
2037 RAM_TIMESTAMP_CHECK_IDENTITY,
2038 mulmod(mload(Q4_EVAL_LOC), mload(QL_EVAL_LOC), p),
2039 p
2040 ),
2041 p
2042 )
2043
2044 memory_identity := addmod(
2045 memory_identity,
2046 mulmod(
2047 mload(AUX_MEMORY_CHECK_IDENTITY),
2048 mulmod(mload(QM_EVAL_LOC), mload(QL_EVAL_LOC), p),
2049 p
2050 ),
2051 p
2052 )
2053 memory_identity := addmod(memory_identity, mload(AUX_RAM_CONSISTENCY_CHECK_IDENTITY), p)
2054
2055 memory_identity := mulmod(
2056 memory_identity,
2057 mulmod(mload(QMEMORY_EVAL_LOC), mload(POW_PARTIAL_EVALUATION_LOC), p),
2058 p
2059 )
2060 mstore(SUBRELATION_EVAL_13_LOC, memory_identity)
2061 }
2062 }
2063 }
2064
2065 /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
2066 /* NON NATIVE FIELD RELATION */
2067 /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/
2068 {
2088 let limb_subproduct :=
2089 addmod(
2090 mulmod(mload(W1_EVAL_LOC), mload(W2_SHIFT_EVAL_LOC), p),
2091 mulmod(mload(W1_SHIFT_EVAL_LOC), mload(W2_EVAL_LOC), p),
2092 p
2093 )
2094
2095 let non_native_field_gate_2 :=
2096 addmod(
2097 addmod(
2098 mulmod(mload(W1_EVAL_LOC), mload(W4_EVAL_LOC), p),
2099 mulmod(mload(W2_EVAL_LOC), mload(W3_EVAL_LOC), p),
2100 p
2101 ),
2102 sub(p, mload(W3_SHIFT_EVAL_LOC)),
2103 p
2104 )
2105 non_native_field_gate_2 := mulmod(non_native_field_gate_2, LIMB_SIZE, p)
2106 non_native_field_gate_2 := addmod(non_native_field_gate_2, sub(p, mload(W4_SHIFT_EVAL_LOC)), p)
2107 non_native_field_gate_2 := addmod(non_native_field_gate_2, limb_subproduct, p)
2108 non_native_field_gate_2 := mulmod(non_native_field_gate_2, mload(Q4_EVAL_LOC), p)
2109
2110 limb_subproduct := mulmod(limb_subproduct, LIMB_SIZE, p)
2111 limb_subproduct := addmod(
2112 limb_subproduct,
2113 mulmod(mload(W1_SHIFT_EVAL_LOC), mload(W2_SHIFT_EVAL_LOC), p),
2114 p
2115 )
2116
2117 let non_native_field_gate_1 :=
2118 mulmod(
2119 addmod(limb_subproduct, sub(p, addmod(mload(W3_EVAL_LOC), mload(W4_EVAL_LOC), p)), p),
2120 mload(QO_EVAL_LOC),
2121 p
2122 )
2123
2124 let non_native_field_gate_3 :=
2125 mulmod(
2126 addmod(
2127 addmod(limb_subproduct, mload(W4_EVAL_LOC), p),
2128 sub(p, addmod(mload(W3_SHIFT_EVAL_LOC), mload(W4_SHIFT_EVAL_LOC), p)),
2129 p
2130 ),
2131 mload(QM_EVAL_LOC),
2132 p
2133 )
2134 let non_native_field_identity :=
2135 mulmod(
2136 addmod(
2137 addmod(non_native_field_gate_1, non_native_field_gate_2, p),
2138 non_native_field_gate_3,
2139 p
2140 ),
2141 mload(QR_EVAL_LOC),
2142 p
2143 )
2144
2145 mstore(AUX_NON_NATIVE_FIELD_IDENTITY, non_native_field_identity)
2146 }
2147
2148 {
2162 let limb_accumulator_1 := mulmod(mload(W2_SHIFT_EVAL_LOC), SUBLIMB_SHIFT, p)
2163 limb_accumulator_1 := addmod(limb_accumulator_1, mload(W1_SHIFT_EVAL_LOC), p)
2164 limb_accumulator_1 := mulmod(limb_accumulator_1, SUBLIMB_SHIFT, p)
2165 limb_accumulator_1 := addmod(limb_accumulator_1, mload(W3_EVAL_LOC), p)
2166 limb_accumulator_1 := mulmod(limb_accumulator_1, SUBLIMB_SHIFT, p)
2167 limb_accumulator_1 := addmod(limb_accumulator_1, mload(W2_EVAL_LOC), p)
2168 limb_accumulator_1 := mulmod(limb_accumulator_1, SUBLIMB_SHIFT, p)
2169 limb_accumulator_1 := addmod(limb_accumulator_1, mload(W1_EVAL_LOC), p)
2170 limb_accumulator_1 := addmod(limb_accumulator_1, sub(p, mload(W4_EVAL_LOC)), p)
2171 limb_accumulator_1 := mulmod(limb_accumulator_1, mload(Q4_EVAL_LOC), p)
2172
2186 let limb_accumulator_2 := mulmod(mload(W3_SHIFT_EVAL_LOC), SUBLIMB_SHIFT, p)
2187 limb_accumulator_2 := addmod(limb_accumulator_2, mload(W2_SHIFT_EVAL_LOC), p)
2188 limb_accumulator_2 := mulmod(limb_accumulator_2, SUBLIMB_SHIFT, p)
2189 limb_accumulator_2 := addmod(limb_accumulator_2, mload(W1_SHIFT_EVAL_LOC), p)
2190 limb_accumulator_2 := mulmod(limb_accumulator_2, SUBLIMB_SHIFT, p)
2191 limb_accumulator_2 := addmod(limb_accumulator_2, mload(W4_EVAL_LOC), p)
2192 limb_accumulator_2 := mulmod(limb_accumulator_2, SUBLIMB_SHIFT, p)
2193 limb_accumulator_2 := addmod(limb_accumulator_2, mload(W3_EVAL_LOC), p)
2194 limb_accumulator_2 := addmod(limb_accumulator_2, sub(p, mload(W4_SHIFT_EVAL_LOC)), p)
2195 limb_accumulator_2 := mulmod(limb_accumulator_2, mload(QM_EVAL_LOC), p)
2196
2197 let limb_accumulator_identity := addmod(limb_accumulator_1, limb_accumulator_2, p)
2198 limb_accumulator_identity := mulmod(limb_accumulator_identity, mload(QO_EVAL_LOC), p)
2199
2200 let nnf_identity := addmod(mload(AUX_NON_NATIVE_FIELD_IDENTITY), limb_accumulator_identity, p)
2201 nnf_identity := mulmod(
2202 nnf_identity,
2203 mulmod(mload(QNNF_EVAL_LOC), mload(POW_PARTIAL_EVALUATION_LOC), p),
2204 p
2205 )
2206
2207 mstore(SUBRELATION_EVAL_19_LOC, nnf_identity)
2208 }
2209
2210 /*
2211 * Poseidon External Relation
2212 */
2213 {
2214 let s1 := addmod(mload(W1_EVAL_LOC), mload(QL_EVAL_LOC), p)
2215 let s2 := addmod(mload(W2_EVAL_LOC), mload(QR_EVAL_LOC), p)
2216 let s3 := addmod(mload(W3_EVAL_LOC), mload(QO_EVAL_LOC), p)
2217 let s4 := addmod(mload(W4_EVAL_LOC), mload(Q4_EVAL_LOC), p)
2218
2219 // u1 := s1 * s1 * s1 * s1 * s1;
2220 let t0 := mulmod(s1, s1, p)
2221 let u1 := mulmod(t0, mulmod(t0, s1, p), p)
2222
2223 // u2 := s2 * s2 * s2 * s2 * s2;
2224 t0 := mulmod(s2, s2, p)
2225 let u2 := mulmod(t0, mulmod(t0, s2, p), p)
2226
2227 // u3 := s3 * s3 * s3 * s3 * s3;
2228 t0 := mulmod(s3, s3, p)
2229 let u3 := mulmod(t0, mulmod(t0, s3, p), p)
2230
2231 // u4 := s4 * s4 * s4 * s4 * s4;
2232 t0 := mulmod(s4, s4, p)
2233 let u4 := mulmod(t0, mulmod(t0, s4, p), p)
2234
2235 // matrix mul v = M_E * u with 14 additions
2236 t0 := addmod(u1, u2, p)
2237 let t1 := addmod(u3, u4, p)
2238
2239 let t2 := addmod(u2, u2, p)
2240 t2 := addmod(t2, t1, p)
2241
2242 let t3 := addmod(u4, u4, p)
2243 t3 := addmod(t3, t0, p)
2244
2245 let v4 := addmod(t1, t1, p)
2246 v4 := addmod(v4, v4, p)
2247 v4 := addmod(v4, t3, p)
2248
2249 let v2 := addmod(t0, t0, p)
2250 v2 := addmod(v2, v2, p)
2251 v2 := addmod(v2, t2, p)
2252
2253 let v1 := addmod(t3, v2, p)
2254 let v3 := addmod(t2, v4, p)
2255
2256 let q_pos_by_scaling :=
2257 mulmod(mload(QPOSEIDON2_EXTERNAL_EVAL_LOC), mload(POW_PARTIAL_EVALUATION_LOC), p)
2258
2259 mstore(
2260 SUBRELATION_EVAL_20_LOC,
2261 mulmod(q_pos_by_scaling, addmod(v1, sub(p, mload(W1_SHIFT_EVAL_LOC)), p), p)
2262 )
2263
2264 mstore(
2265 SUBRELATION_EVAL_21_LOC,
2266 mulmod(q_pos_by_scaling, addmod(v2, sub(p, mload(W2_SHIFT_EVAL_LOC)), p), p)
2267 )
2268
2269 mstore(
2270 SUBRELATION_EVAL_22_LOC,
2271 mulmod(q_pos_by_scaling, addmod(v3, sub(p, mload(W3_SHIFT_EVAL_LOC)), p), p)
2272 )
2273
2274 mstore(
2275 SUBRELATION_EVAL_23_LOC,
2276 mulmod(q_pos_by_scaling, addmod(v4, sub(p, mload(W4_SHIFT_EVAL_LOC)), p), p)
2277 )
2278 }
2279
2280 /*
2281 * Poseidon Internal Relation
2282 */
2283 {
2284 let s1 := addmod(mload(W1_EVAL_LOC), mload(QL_EVAL_LOC), p)
2285
2286 // apply s-box round
2287 let t0 := mulmod(s1, s1, p)
2288 let u1 := mulmod(t0, mulmod(t0, s1, p), p)
2289 let u2 := mload(W2_EVAL_LOC)
2290 let u3 := mload(W3_EVAL_LOC)
2291 let u4 := mload(W4_EVAL_LOC)
2292
2293 // matrix mul v = M_I * u 4 muls and 7 additions
2294 let u_sum := addmod(u1, u2, p)
2295 u_sum := addmod(u_sum, addmod(u3, u4, p), p)
2296
2297 let q_pos_by_scaling :=
2298 mulmod(mload(QPOSEIDON2_INTERNAL_EVAL_LOC), mload(POW_PARTIAL_EVALUATION_LOC), p)
2299
2300 let v1 := addmod(mulmod(u1, POS_INTERNAL_MATRIX_D_0, p), u_sum, p)
2301
2302 mstore(
2303 SUBRELATION_EVAL_24_LOC,
2304 mulmod(q_pos_by_scaling, addmod(v1, sub(p, mload(W1_SHIFT_EVAL_LOC)), p), p)
2305 )
2306 let v2 := addmod(mulmod(u2, POS_INTERNAL_MATRIX_D_1, p), u_sum, p)
2307
2308 mstore(
2309 SUBRELATION_EVAL_25_LOC,
2310 mulmod(q_pos_by_scaling, addmod(v2, sub(p, mload(W2_SHIFT_EVAL_LOC)), p), p)
2311 )
2312 let v3 := addmod(mulmod(u3, POS_INTERNAL_MATRIX_D_2, p), u_sum, p)
2313
2314 mstore(
2315 SUBRELATION_EVAL_26_LOC,
2316 mulmod(q_pos_by_scaling, addmod(v3, sub(p, mload(W3_SHIFT_EVAL_LOC)), p), p)
2317 )
2318
2319 let v4 := addmod(mulmod(u4, POS_INTERNAL_MATRIX_D_3, p), u_sum, p)
2320 mstore(
2321 SUBRELATION_EVAL_27_LOC,
2322 mulmod(q_pos_by_scaling, addmod(v4, sub(p, mload(W4_SHIFT_EVAL_LOC)), p), p)
2323 )
2324 }
2325
2326 // Scale and batch subrelations by subrelation challenges
2327 // linear combination of subrelations
2328 let accumulator := mload(SUBRELATION_EVAL_0_LOC)
2329
2330 // Below is an unrolled variant of the following loop
2331 // for (uint256 i = 1; i < NUMBER_OF_SUBRELATIONS; ++i) {
2332 // accumulator = accumulator + evaluations[i] * subrelationChallenges[i - 1];
2333 // }
2334
2335 accumulator := addmod(
2336 accumulator,
2337 mulmod(mload(SUBRELATION_EVAL_1_LOC), mload(ALPHA_CHALLENGE_0), p),
2338 p
2339 )
2340 accumulator := addmod(
2341 accumulator,
2342 mulmod(mload(SUBRELATION_EVAL_2_LOC), mload(ALPHA_CHALLENGE_1), p),
2343 p
2344 )
2345 accumulator := addmod(
2346 accumulator,
2347 mulmod(mload(SUBRELATION_EVAL_3_LOC), mload(ALPHA_CHALLENGE_2), p),
2348 p
2349 )
2350 accumulator := addmod(
2351 accumulator,
2352 mulmod(mload(SUBRELATION_EVAL_4_LOC), mload(ALPHA_CHALLENGE_3), p),
2353 p
2354 )
2355 accumulator := addmod(
2356 accumulator,
2357 mulmod(mload(SUBRELATION_EVAL_5_LOC), mload(ALPHA_CHALLENGE_4), p),
2358 p
2359 )
2360 accumulator := addmod(
2361 accumulator,
2362 mulmod(mload(SUBRELATION_EVAL_6_LOC), mload(ALPHA_CHALLENGE_5), p),
2363 p
2364 )
2365 accumulator := addmod(
2366 accumulator,
2367 mulmod(mload(SUBRELATION_EVAL_7_LOC), mload(ALPHA_CHALLENGE_6), p),
2368 p
2369 )
2370 accumulator := addmod(
2371 accumulator,
2372 mulmod(mload(SUBRELATION_EVAL_8_LOC), mload(ALPHA_CHALLENGE_7), p),
2373 p
2374 )
2375 accumulator := addmod(
2376 accumulator,
2377 mulmod(mload(SUBRELATION_EVAL_9_LOC), mload(ALPHA_CHALLENGE_8), p),
2378 p
2379 )
2380 accumulator := addmod(
2381 accumulator,
2382 mulmod(mload(SUBRELATION_EVAL_10_LOC), mload(ALPHA_CHALLENGE_9), p),
2383 p
2384 )
2385 accumulator := addmod(
2386 accumulator,
2387 mulmod(mload(SUBRELATION_EVAL_11_LOC), mload(ALPHA_CHALLENGE_10), p),
2388 p
2389 )
2390 accumulator := addmod(
2391 accumulator,
2392 mulmod(mload(SUBRELATION_EVAL_12_LOC), mload(ALPHA_CHALLENGE_11), p),
2393 p
2394 )
2395 accumulator := addmod(
2396 accumulator,
2397 mulmod(mload(SUBRELATION_EVAL_13_LOC), mload(ALPHA_CHALLENGE_12), p),
2398 p
2399 )
2400 accumulator := addmod(
2401 accumulator,
2402 mulmod(mload(SUBRELATION_EVAL_14_LOC), mload(ALPHA_CHALLENGE_13), p),
2403 p
2404 )
2405 accumulator := addmod(
2406 accumulator,
2407 mulmod(mload(SUBRELATION_EVAL_15_LOC), mload(ALPHA_CHALLENGE_14), p),
2408 p
2409 )
2410 accumulator := addmod(
2411 accumulator,
2412 mulmod(mload(SUBRELATION_EVAL_16_LOC), mload(ALPHA_CHALLENGE_15), p),
2413 p
2414 )
2415 accumulator := addmod(
2416 accumulator,
2417 mulmod(mload(SUBRELATION_EVAL_17_LOC), mload(ALPHA_CHALLENGE_16), p),
2418 p
2419 )
2420 accumulator := addmod(
2421 accumulator,
2422 mulmod(mload(SUBRELATION_EVAL_18_LOC), mload(ALPHA_CHALLENGE_17), p),
2423 p
2424 )
2425 accumulator := addmod(
2426 accumulator,
2427 mulmod(mload(SUBRELATION_EVAL_19_LOC), mload(ALPHA_CHALLENGE_18), p),
2428 p
2429 )
2430 accumulator := addmod(
2431 accumulator,
2432 mulmod(mload(SUBRELATION_EVAL_20_LOC), mload(ALPHA_CHALLENGE_19), p),
2433 p
2434 )
2435 accumulator := addmod(
2436 accumulator,
2437 mulmod(mload(SUBRELATION_EVAL_21_LOC), mload(ALPHA_CHALLENGE_20), p),
2438 p
2439 )
2440 accumulator := addmod(
2441 accumulator,
2442 mulmod(mload(SUBRELATION_EVAL_22_LOC), mload(ALPHA_CHALLENGE_21), p),
2443 p
2444 )
2445 accumulator := addmod(
2446 accumulator,
2447 mulmod(mload(SUBRELATION_EVAL_23_LOC), mload(ALPHA_CHALLENGE_22), p),
2448 p
2449 )
2450 accumulator := addmod(
2451 accumulator,
2452 mulmod(mload(SUBRELATION_EVAL_24_LOC), mload(ALPHA_CHALLENGE_23), p),
2453 p
2454 )
2455 accumulator := addmod(
2456 accumulator,
2457 mulmod(mload(SUBRELATION_EVAL_25_LOC), mload(ALPHA_CHALLENGE_24), p),
2458 p
2459 )
2460 accumulator := addmod(
2461 accumulator,
2462 mulmod(mload(SUBRELATION_EVAL_26_LOC), mload(ALPHA_CHALLENGE_25), p),
2463 p
2464 )
2465 accumulator := addmod(
2466 accumulator,
2467 mulmod(mload(SUBRELATION_EVAL_27_LOC), mload(ALPHA_CHALLENGE_26), p),
2468 p
2469 )
2470
2471 let sumcheck_valid := eq(accumulator, mload(FINAL_ROUND_TARGET_LOC))
2472
2473 if iszero(sumcheck_valid) {
2474 mstore(0x00, SUMCHECK_FAILED_SELECTOR)
2475 revert(0x00, 0x04)
2476 }
2477 }
2478
2479 /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
2480 /* SUMCHECK -- Complete */
2481 /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/
2482
2483 /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
2484 /* SHPLEMINI */
2485 /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/
2486
2487 // Compute powers of evaluation challenge
2488 let cache := mload(GEMINI_R_CHALLENGE)
2489 let off := POWERS_OF_EVALUATION_CHALLENGE_0_LOC
2490 mstore(off, cache)
2491
2492 for { let i := 1 } lt(i, LOG_N) { i := add(i, 1) } {
2493 off := add(off, 0x20)
2494 cache := mulmod(cache, cache, p)
2495 mstore(off, cache)
2496 }
2497
2498 // Compute Inverted Gemini Denominators
2499 let eval_challenge := mload(SHPLONK_Z_CHALLENGE)
2500
2501 // TO be inverted in the batch invert below
2502 // TODO: maybe not needed to go in memory
2503 mstore(
2504 INVERTED_GEMINI_DENOMINATOR_0_LOC,
2505 addmod(eval_challenge, sub(p, mload(POWERS_OF_EVALUATION_CHALLENGE_0_LOC)), p)
2506 )
2507
2508 mstore(
2509 POS_INVERTED_DENOM_0_LOC,
2510 addmod(eval_challenge, sub(p, mload(POWERS_OF_EVALUATION_CHALLENGE_0_LOC)), p)
2511 )
2512 mstore(NEG_INVERTED_DENOM_0_LOC, addmod(eval_challenge, mload(POWERS_OF_EVALUATION_CHALLENGE_0_LOC), p))
2513
2514 // Compute Fold Pos Evaluatios
2515
2516 // In order to compute fold pos evaluations we need
2517 let store_off := INVERTED_CHALLENEGE_POW_MINUS_U_{{ LOG_N_MINUS_ONE }}_LOC
2518 let pow_off := POWERS_OF_EVALUATION_CHALLENGE_{{ LOG_N_MINUS_ONE }}_LOC
2519 let sumcheck_u_off := SUM_U_CHALLENGE_{{ LOG_N_MINUS_ONE }}
2520
2521 // TODO: challengePower * (ONE - u) can be cached - measure performance
2522 for { let i := LOG_N } gt(i, 0) { i := sub(i, 1) } {
2523 let u := mload(sumcheck_u_off)
2524
2525 let challPowerMulMinusU := mulmod(mload(pow_off), addmod(1, sub(p, u), p), p)
2526
2527 mstore(store_off, addmod(challPowerMulMinusU, u, p))
2528
2529 store_off := sub(store_off, 0x20)
2530 pow_off := sub(pow_off, 0x20)
2531 sumcheck_u_off := sub(sumcheck_u_off, 0x20)
2532 }
2533
2534 // Compute
2535 {
2536 let pos_inverted_off := POS_INVERTED_DENOM_1_LOC
2537 let neg_inverted_off := NEG_INVERTED_DENOM_1_LOC
2538 pow_off := POWERS_OF_EVALUATION_CHALLENGE_1_LOC
2539
2540 let shplonk_z := mload(SHPLONK_Z_CHALLENGE)
2541 for { let i := 0 } lt(i, sub(LOG_N, 1)) { i := add(i, 1) } {
2542 let pow := mload(pow_off)
2543
2544 let pos_inv := addmod(shplonk_z, sub(p, pow), p)
2545 mstore(pos_inverted_off, pos_inv)
2546
2547 let neg_inv := addmod(shplonk_z, pow, p)
2548 mstore(neg_inverted_off, neg_inv)
2549
2550 pow_off := add(pow_off, 0x20)
2551 pos_inverted_off := add(pos_inverted_off, 0x20)
2552 neg_inverted_off := add(neg_inverted_off, 0x20)
2553 }
2554 }
2555
2556 // To be inverted
2557 // From: computeFoldPosEvaluations
2558 // Series of challengePower * (ONE - u)
2559 // gemini r challenge
2560 // Inverted denominators
2561 // (shplonkZ - powers of evaluaion challenge[i + 1])
2562 // (shplonkZ + powers of evaluation challenge[i + 1])
2563
2564 // Use scratch space for temps
2565
2566 let accumulator := mload(GEMINI_R_CHALLENGE)
2567
2570
2571 {
2572 mstore(0, 0x20)
2573 mstore(0x20, 0x20)
2574 mstore(0x40, 0x20)
2575 mstore(0x60, accumulator)
2576 mstore(0x80, P_SUB_2)
2577 mstore(0xa0, p)
2578 if iszero(staticcall(gas(), 0x05, 0x00, 0xc0, 0x00, 0x20)) {
2579 mstore(0x00, MODEXP_FAILED_SELECTOR)
2580 revert(0x00, 0x04)
2581 }
2582 accumulator := mload(0x00)
2583 }
2584
2587
2588 let unshifted_scalar := 0
2589 let shifted_scalar := 0
2590 {
2591 let pos_inverted_denominator := mload(POS_INVERTED_DENOM_0_LOC)
2592 let neg_inverted_denominator := mload(NEG_INVERTED_DENOM_0_LOC)
2593 let shplonk_nu := mload(SHPLONK_NU_CHALLENGE)
2594
2595 unshifted_scalar := addmod(pos_inverted_denominator, mulmod(shplonk_nu, neg_inverted_denominator, p), p)
2596
2597 // accumulator takes the value of `INVERTED_GEMINI_DENOMINATOR_0` here
2598 shifted_scalar := mulmod(
2599 accumulator, // (1 / gemini_r_challenge)
2600 // (inverse_vanishing_evals[0]) - (shplonk_nu * inverse_vanishing_evals[1])
2601 addmod(
2602 pos_inverted_denominator,
2603 // - (shplonk_nu * inverse_vanishing_evals[1])
2604 sub(p, mulmod(shplonk_nu, neg_inverted_denominator, p)),
2605 p
2606 ),
2607 p
2608 )
2609 }
2610
2611 // TODO: Write a comment that describes the process of accumulating commitments and scalars
2612 // into one large value that will be used on the rhs of the pairing check
2613
2614 // Accumulators
2615 let batching_challenge := 1
2616 let batched_evaluation := 0
2617
2618 let neg_unshifted_scalar := sub(p, unshifted_scalar)
2619 let neg_shifted_scalar := sub(p, shifted_scalar)
2620
2621 mstore(BATCH_SCALAR_0_LOC, 1)
2622 let rho := mload(RHO_CHALLENGE)
2623
2624 // Unrolled for the loop below - where NUMBER_UNSHIFTED = 36
2625 // for (uint256 i = 1; i <= NUMBER_UNSHIFTED; ++i) {
2626 // scalars[i] = mem.unshiftedScalar.neg() * mem.batchingChallenge;
2627 // mem.batchedEvaluation = mem.batchedEvaluation + (proof.sumcheckEvaluations[i - 1] * mem.batchingChallenge);
2628 // mem.batchingChallenge = mem.batchingChallenge * tp.rho;
2629 // }
2630
2631 // Calculate the scalars and batching challenge for the unshifted entities
2632 // 0: QM_EVAL_LOC
2633 mstore(BATCH_SCALAR_1_LOC, mulmod(neg_unshifted_scalar, batching_challenge, p))
2634 batched_evaluation := addmod(batched_evaluation, mulmod(mload(QM_EVAL_LOC), batching_challenge, p), p)
2635 batching_challenge := mulmod(batching_challenge, rho, p)
2636
2637 // 1: QC_EVAL_LOC
2638 mstore(BATCH_SCALAR_2_LOC, mulmod(neg_unshifted_scalar, batching_challenge, p))
2639 batched_evaluation := addmod(batched_evaluation, mulmod(mload(QC_EVAL_LOC), batching_challenge, p), p)
2640 batching_challenge := mulmod(batching_challenge, rho, p)
2641
2642 // 2: QL_EVAL_LOC
2643 mstore(BATCH_SCALAR_3_LOC, mulmod(neg_unshifted_scalar, batching_challenge, p))
2644 batched_evaluation := addmod(batched_evaluation, mulmod(mload(QL_EVAL_LOC), batching_challenge, p), p)
2645 batching_challenge := mulmod(batching_challenge, rho, p)
2646
2647 // 3: QR_EVAL_LOC
2648 mstore(BATCH_SCALAR_4_LOC, mulmod(neg_unshifted_scalar, batching_challenge, p))
2649 batched_evaluation := addmod(batched_evaluation, mulmod(mload(QR_EVAL_LOC), batching_challenge, p), p)
2650 batching_challenge := mulmod(batching_challenge, rho, p)
2651
2652 // 4: QO_EVAL_LOC
2653 mstore(BATCH_SCALAR_5_LOC, mulmod(neg_unshifted_scalar, batching_challenge, p))
2654 batched_evaluation := addmod(batched_evaluation, mulmod(mload(QO_EVAL_LOC), batching_challenge, p), p)
2655 batching_challenge := mulmod(batching_challenge, rho, p)
2656
2657 // 5: Q4_EVAL_LOC
2658 mstore(BATCH_SCALAR_6_LOC, mulmod(neg_unshifted_scalar, batching_challenge, p))
2659 batched_evaluation := addmod(batched_evaluation, mulmod(mload(Q4_EVAL_LOC), batching_challenge, p), p)
2660 batching_challenge := mulmod(batching_challenge, rho, p)
2661
2662 // 6: QLOOKUP_EVAL_LOC
2663 mstore(BATCH_SCALAR_7_LOC, mulmod(neg_unshifted_scalar, batching_challenge, p))
2664 batched_evaluation := addmod(batched_evaluation, mulmod(mload(QLOOKUP_EVAL_LOC), batching_challenge, p), p)
2665 batching_challenge := mulmod(batching_challenge, rho, p)
2666
2667 // 7: QARITH_EVAL_LOC
2668 mstore(BATCH_SCALAR_8_LOC, mulmod(neg_unshifted_scalar, batching_challenge, p))
2669 batched_evaluation := addmod(batched_evaluation, mulmod(mload(QARITH_EVAL_LOC), batching_challenge, p), p)
2670 batching_challenge := mulmod(batching_challenge, rho, p)
2671
2672 // 8: QRANGE_EVAL_LOC
2673 mstore(BATCH_SCALAR_9_LOC, mulmod(neg_unshifted_scalar, batching_challenge, p))
2674 batched_evaluation := addmod(batched_evaluation, mulmod(mload(QRANGE_EVAL_LOC), batching_challenge, p), p)
2675 batching_challenge := mulmod(batching_challenge, rho, p)
2676
2677 // 9: QELLIPTIC_EVAL_LOC
2678 mstore(BATCH_SCALAR_10_LOC, mulmod(neg_unshifted_scalar, batching_challenge, p))
2679 batched_evaluation := addmod(
2680 batched_evaluation,
2681 mulmod(mload(QELLIPTIC_EVAL_LOC), batching_challenge, p),
2682 p
2683 )
2684 batching_challenge := mulmod(batching_challenge, rho, p)
2685
2686 // 10: QMEMORY_EVAL_LOC
2687 mstore(BATCH_SCALAR_11_LOC, mulmod(neg_unshifted_scalar, batching_challenge, p))
2688 batched_evaluation := addmod(batched_evaluation, mulmod(mload(QMEMORY_EVAL_LOC), batching_challenge, p), p)
2689 batching_challenge := mulmod(batching_challenge, rho, p)
2690
2691 // 11: QNNF_EVAL_LOC
2692 mstore(BATCH_SCALAR_12_LOC, mulmod(neg_unshifted_scalar, batching_challenge, p))
2693 batched_evaluation := addmod(batched_evaluation, mulmod(mload(QNNF_EVAL_LOC), batching_challenge, p), p)
2694 batching_challenge := mulmod(batching_challenge, rho, p)
2695
2696 // 12: QPOSEIDON2_EXTERNAL_EVAL_LOC
2697 mstore(BATCH_SCALAR_13_LOC, mulmod(neg_unshifted_scalar, batching_challenge, p))
2698 batched_evaluation := addmod(
2699 batched_evaluation,
2700 mulmod(mload(QPOSEIDON2_EXTERNAL_EVAL_LOC), batching_challenge, p),
2701 p
2702 )
2703 batching_challenge := mulmod(batching_challenge, rho, p)
2704
2705 // 13: QPOSEIDON2_INTERNAL_EVAL_LOC
2706 mstore(BATCH_SCALAR_14_LOC, mulmod(neg_unshifted_scalar, batching_challenge, p))
2707 batched_evaluation := addmod(
2708 batched_evaluation,
2709 mulmod(mload(QPOSEIDON2_INTERNAL_EVAL_LOC), batching_challenge, p),
2710 p
2711 )
2712 batching_challenge := mulmod(batching_challenge, rho, p)
2713
2714 // 14: SIGMA1_EVAL_LOC
2715 mstore(BATCH_SCALAR_15_LOC, mulmod(neg_unshifted_scalar, batching_challenge, p))
2716 batched_evaluation := addmod(batched_evaluation, mulmod(mload(SIGMA1_EVAL_LOC), batching_challenge, p), p)
2717 batching_challenge := mulmod(batching_challenge, rho, p)
2718
2719 // 15: SIGMA2_EVAL_LOC
2720 mstore(BATCH_SCALAR_16_LOC, mulmod(neg_unshifted_scalar, batching_challenge, p))
2721 batched_evaluation := addmod(batched_evaluation, mulmod(mload(SIGMA2_EVAL_LOC), batching_challenge, p), p)
2722 batching_challenge := mulmod(batching_challenge, rho, p)
2723
2724 // 16: SIGMA3_EVAL_LOC
2725 mstore(BATCH_SCALAR_17_LOC, mulmod(neg_unshifted_scalar, batching_challenge, p))
2726 batched_evaluation := addmod(batched_evaluation, mulmod(mload(SIGMA3_EVAL_LOC), batching_challenge, p), p)
2727 batching_challenge := mulmod(batching_challenge, rho, p)
2728
2729 // 17: SIGMA4_EVAL_LOC
2730 mstore(BATCH_SCALAR_18_LOC, mulmod(neg_unshifted_scalar, batching_challenge, p))
2731 batched_evaluation := addmod(batched_evaluation, mulmod(mload(SIGMA4_EVAL_LOC), batching_challenge, p), p)
2732 batching_challenge := mulmod(batching_challenge, rho, p)
2733
2734 // 18: ID1_EVAL_LOC
2735 mstore(BATCH_SCALAR_19_LOC, mulmod(neg_unshifted_scalar, batching_challenge, p))
2736 batched_evaluation := addmod(batched_evaluation, mulmod(mload(ID1_EVAL_LOC), batching_challenge, p), p)
2737 batching_challenge := mulmod(batching_challenge, rho, p)
2738
2739 // 19: ID2_EVAL_LOC
2740 mstore(BATCH_SCALAR_20_LOC, mulmod(neg_unshifted_scalar, batching_challenge, p))
2741 batched_evaluation := addmod(batched_evaluation, mulmod(mload(ID2_EVAL_LOC), batching_challenge, p), p)
2742 batching_challenge := mulmod(batching_challenge, rho, p)
2743
2744 // 20: ID3_EVAL_LOC
2745 mstore(BATCH_SCALAR_21_LOC, mulmod(neg_unshifted_scalar, batching_challenge, p))
2746 batched_evaluation := addmod(batched_evaluation, mulmod(mload(ID3_EVAL_LOC), batching_challenge, p), p)
2747 batching_challenge := mulmod(batching_challenge, rho, p)
2748
2749 // 21: ID4_EVAL_LOC
2750 mstore(BATCH_SCALAR_22_LOC, mulmod(neg_unshifted_scalar, batching_challenge, p))
2751 batched_evaluation := addmod(batched_evaluation, mulmod(mload(ID4_EVAL_LOC), batching_challenge, p), p)
2752 batching_challenge := mulmod(batching_challenge, rho, p)
2753
2754 // 22: TABLE1_EVAL_LOC
2755 mstore(BATCH_SCALAR_23_LOC, mulmod(neg_unshifted_scalar, batching_challenge, p))
2756 batched_evaluation := addmod(batched_evaluation, mulmod(mload(TABLE1_EVAL_LOC), batching_challenge, p), p)
2757 batching_challenge := mulmod(batching_challenge, rho, p)
2758
2759 // 23: TABLE2_EVAL_LOC
2760 mstore(BATCH_SCALAR_24_LOC, mulmod(neg_unshifted_scalar, batching_challenge, p))
2761 batched_evaluation := addmod(batched_evaluation, mulmod(mload(TABLE2_EVAL_LOC), batching_challenge, p), p)
2762 batching_challenge := mulmod(batching_challenge, rho, p)
2763
2764 // 24: TABLE3_EVAL_LOC
2765 mstore(BATCH_SCALAR_25_LOC, mulmod(neg_unshifted_scalar, batching_challenge, p))
2766 batched_evaluation := addmod(batched_evaluation, mulmod(mload(TABLE3_EVAL_LOC), batching_challenge, p), p)
2767 batching_challenge := mulmod(batching_challenge, rho, p)
2768
2769 // 25: TABLE4_EVAL_LOC
2770 mstore(BATCH_SCALAR_26_LOC, mulmod(neg_unshifted_scalar, batching_challenge, p))
2771 batched_evaluation := addmod(batched_evaluation, mulmod(mload(TABLE4_EVAL_LOC), batching_challenge, p), p)
2772 batching_challenge := mulmod(batching_challenge, rho, p)
2773
2774 // 26: LAGRANGE_FIRST_EVAL_LOC
2775 mstore(BATCH_SCALAR_27_LOC, mulmod(neg_unshifted_scalar, batching_challenge, p))
2776 batched_evaluation := addmod(
2777 batched_evaluation,
2778 mulmod(mload(LAGRANGE_FIRST_EVAL_LOC), batching_challenge, p),
2779 p
2780 )
2781 batching_challenge := mulmod(batching_challenge, rho, p)
2782
2783 // 27: LAGRANGE_LAST_EVAL_LOC
2784 mstore(BATCH_SCALAR_28_LOC, mulmod(neg_unshifted_scalar, batching_challenge, p))
2785 batched_evaluation := addmod(
2786 batched_evaluation,
2787 mulmod(mload(LAGRANGE_LAST_EVAL_LOC), batching_challenge, p),
2788 p
2789 )
2790 batching_challenge := mulmod(batching_challenge, rho, p)
2791
2792 // 28: W1_EVAL_LOC
2793 mstore(BATCH_SCALAR_29_LOC, mulmod(neg_unshifted_scalar, batching_challenge, p))
2794 batched_evaluation := addmod(batched_evaluation, mulmod(mload(W1_EVAL_LOC), batching_challenge, p), p)
2795 batching_challenge := mulmod(batching_challenge, rho, p)
2796
2797 // 29: W2_EVAL_LOC
2798 mstore(BATCH_SCALAR_30_LOC, mulmod(neg_unshifted_scalar, batching_challenge, p))
2799 batched_evaluation := addmod(batched_evaluation, mulmod(mload(W2_EVAL_LOC), batching_challenge, p), p)
2800 batching_challenge := mulmod(batching_challenge, rho, p)
2801
2802 // 30: W3_EVAL_LOC
2803 mstore(BATCH_SCALAR_31_LOC, mulmod(neg_unshifted_scalar, batching_challenge, p))
2804 batched_evaluation := addmod(batched_evaluation, mulmod(mload(W3_EVAL_LOC), batching_challenge, p), p)
2805 batching_challenge := mulmod(batching_challenge, rho, p)
2806
2807 // 31: W4_EVAL_LOC
2808 mstore(BATCH_SCALAR_32_LOC, mulmod(neg_unshifted_scalar, batching_challenge, p))
2809 batched_evaluation := addmod(batched_evaluation, mulmod(mload(W4_EVAL_LOC), batching_challenge, p), p)
2810 batching_challenge := mulmod(batching_challenge, rho, p)
2811
2812 // 32: Z_PERM_EVAL_LOC
2813 mstore(BATCH_SCALAR_33_LOC, mulmod(neg_unshifted_scalar, batching_challenge, p))
2814 batched_evaluation := addmod(batched_evaluation, mulmod(mload(Z_PERM_EVAL_LOC), batching_challenge, p), p)
2815 batching_challenge := mulmod(batching_challenge, rho, p)
2816
2817 // 33: LOOKUP_INVERSES_EVAL_LOC
2818 mstore(BATCH_SCALAR_34_LOC, mulmod(neg_unshifted_scalar, batching_challenge, p))
2819 batched_evaluation := addmod(
2820 batched_evaluation,
2821 mulmod(mload(LOOKUP_INVERSES_EVAL_LOC), batching_challenge, p),
2822 p
2823 )
2824 batching_challenge := mulmod(batching_challenge, rho, p)
2825
2826 // 34: LOOKUP_READ_COUNTS_EVAL_LOC
2827 mstore(BATCH_SCALAR_35_LOC, mulmod(neg_unshifted_scalar, batching_challenge, p))
2828 batched_evaluation := addmod(
2829 batched_evaluation,
2830 mulmod(mload(LOOKUP_READ_COUNTS_EVAL_LOC), batching_challenge, p),
2831 p
2832 )
2833 batching_challenge := mulmod(batching_challenge, rho, p)
2834
2835 // 35: LOOKUP_READ_TAGS_EVAL_LOC
2836 mstore(BATCH_SCALAR_36_LOC, mulmod(neg_unshifted_scalar, batching_challenge, p))
2837 batched_evaluation := addmod(
2838 batched_evaluation,
2839 mulmod(mload(LOOKUP_READ_TAGS_EVAL_LOC), batching_challenge, p),
2840 p
2841 )
2842 batching_challenge := mulmod(batching_challenge, rho, p)
2843
2844 // Unrolled for NUMBER_OF_SHIFTED_ENTITIES = 5
2845 // for (uint256 i = NUMBER_UNSHIFTED + 1; i <= NUMBER_OF_ENTITIES; ++i) {
2846 // scalars[i] = mem.shiftedScalar.neg() * mem.batchingChallenge;
2847 // mem.batchedEvaluation = mem.batchedEvaluation + (proof.sumcheckEvaluations[i - 1] * mem.batchingChallenge);
2848 // mem.batchingChallenge = mem.batchingChallenge * tp.rho;
2849 // }
2850
2851 // 28: W1_EVAL_LOC
2852 mstore(
2853 BATCH_SCALAR_29_LOC,
2854 addmod(mload(BATCH_SCALAR_29_LOC), mulmod(neg_shifted_scalar, batching_challenge, p), p)
2855 )
2856 batched_evaluation := addmod(batched_evaluation, mulmod(mload(W1_SHIFT_EVAL_LOC), batching_challenge, p), p)
2857 batching_challenge := mulmod(batching_challenge, rho, p)
2858
2859 // 29: W2_EVAL_LOC
2860 mstore(
2861 BATCH_SCALAR_30_LOC,
2862 addmod(mload(BATCH_SCALAR_30_LOC), mulmod(neg_shifted_scalar, batching_challenge, p), p)
2863 )
2864 batched_evaluation := addmod(batched_evaluation, mulmod(mload(W2_SHIFT_EVAL_LOC), batching_challenge, p), p)
2865 batching_challenge := mulmod(batching_challenge, rho, p)
2866
2867 // 30: W3_EVAL_LOC
2868 mstore(
2869 BATCH_SCALAR_31_LOC,
2870 addmod(mload(BATCH_SCALAR_31_LOC), mulmod(neg_shifted_scalar, batching_challenge, p), p)
2871 )
2872 batched_evaluation := addmod(batched_evaluation, mulmod(mload(W3_SHIFT_EVAL_LOC), batching_challenge, p), p)
2873 batching_challenge := mulmod(batching_challenge, rho, p)
2874
2875 // 31: W4_EVAL_LOC
2876 mstore(
2877 BATCH_SCALAR_32_LOC,
2878 addmod(mload(BATCH_SCALAR_32_LOC), mulmod(neg_shifted_scalar, batching_challenge, p), p)
2879 )
2880 batched_evaluation := addmod(batched_evaluation, mulmod(mload(W4_SHIFT_EVAL_LOC), batching_challenge, p), p)
2881 batching_challenge := mulmod(batching_challenge, rho, p)
2882
2883 // 32: Z_PERM_EVAL_LOC
2884 mstore(
2885 BATCH_SCALAR_33_LOC,
2886 addmod(mload(BATCH_SCALAR_33_LOC), mulmod(neg_shifted_scalar, batching_challenge, p), p)
2887 )
2888 batched_evaluation := addmod(
2889 batched_evaluation,
2890 mulmod(mload(Z_PERM_SHIFT_EVAL_LOC), batching_challenge, p),
2891 p
2892 )
2893 batching_challenge := mulmod(batching_challenge, rho, p)
2894
2895 mstore(BATCHED_EVALUATION_LOC, batched_evaluation)
2896
2897 // Compute fold pos evaluations
2898 {
2899 // TODO: work out the stack here
2900 mstore(CHALL_POW_LOC, POWERS_OF_EVALUATION_CHALLENGE_{{ LOG_N_MINUS_ONE }}_LOC)
2901 mstore(SUMCHECK_U_LOC, SUM_U_CHALLENGE_{{ LOG_N_MINUS_ONE }})
2902 mstore(GEMINI_A_LOC, GEMINI_A_EVAL_{{ LOG_N_MINUS_ONE }})
2903 // Inversion of this value was included in batch inversion above
2904 let inverted_chall_pow_minus_u_loc := INVERTED_CHALLENEGE_POW_MINUS_U_{{ LOG_N_MINUS_ONE }}_LOC
2905 let fold_pos_off := FOLD_POS_EVALUATIONS_{{ LOG_N_MINUS_ONE }}_LOC
2906
2907 let batchedEvalAcc := batched_evaluation
2908 for { let i := LOG_N } gt(i, 0) { i := sub(i, 1) } {
2909 let chall_pow := mload(mload(CHALL_POW_LOC))
2910 let sum_check_u := mload(mload(SUMCHECK_U_LOC))
2911
2912 // challengePower * batchedEvalAccumulator * 2
2913 let batchedEvalRoundAcc := mulmod(chall_pow, mulmod(batchedEvalAcc, 2, p), p)
2914 // (challengePower * (ONE - u) - u)
2915 let chall_pow_times_1_minus_u := mulmod(chall_pow, addmod(1, sub(p, sum_check_u), p), p)
2916
2917 batchedEvalRoundAcc := addmod(
2918 batchedEvalRoundAcc,
2919 sub(
2920 p,
2921 mulmod(
2922 mload(mload(GEMINI_A_LOC)),
2923 addmod(chall_pow_times_1_minus_u, sub(p, sum_check_u), p),
2924 p
2925 )
2926 ),
2927 p
2928 )
2929
2930 batchedEvalRoundAcc := mulmod(batchedEvalRoundAcc, mload(inverted_chall_pow_minus_u_loc), p)
2931
2932 batchedEvalAcc := batchedEvalRoundAcc
2933 mstore(fold_pos_off, batchedEvalRoundAcc)
2934
2935 mstore(CHALL_POW_LOC, sub(mload(CHALL_POW_LOC), 0x20))
2936 mstore(SUMCHECK_U_LOC, sub(mload(SUMCHECK_U_LOC), 0x20))
2937 mstore(GEMINI_A_LOC, sub(mload(GEMINI_A_LOC), 0x20))
2938 inverted_chall_pow_minus_u_loc := sub(inverted_chall_pow_minus_u_loc, 0x20)
2939 fold_pos_off := sub(fold_pos_off, 0x20)
2940 }
2941 }
2942
2943 let constant_term_acc := mulmod(mload(FOLD_POS_EVALUATIONS_0_LOC), mload(POS_INVERTED_DENOM_0_LOC), p)
2944 {
2945 let shplonk_nu := mload(SHPLONK_NU_CHALLENGE)
2946
2947 constant_term_acc := addmod(
2948 constant_term_acc,
2949 mulmod(mload(GEMINI_A_EVAL_0), mulmod(shplonk_nu, mload(NEG_INVERTED_DENOM_0_LOC), p), p),
2950 p
2951 )
2952
2953 let shplonk_nu_sqr := mulmod(shplonk_nu, shplonk_nu, p)
2954 batching_challenge := shplonk_nu_sqr
2955
2956 // TODO: improve scheduling
2957 mstore(SS_POS_INV_DENOM_LOC, POS_INVERTED_DENOM_1_LOC)
2958 mstore(SS_NEG_INV_DENOM_LOC, NEG_INVERTED_DENOM_1_LOC)
2959
2960 mstore(SS_GEMINI_EVALS_LOC, GEMINI_A_EVAL_1)
2961 let fold_pos_evals_loc := FOLD_POS_EVALUATIONS_1_LOC
2962
2963 let scalars_loc := BATCH_SCALAR_37_LOC
2964
2965 for { let i := 0 } lt(i, sub(LOG_N, 1)) { i := add(i, 1) } {
2966 let scaling_factor_pos := mulmod(batching_challenge, mload(mload(SS_POS_INV_DENOM_LOC)), p)
2967 let scaling_factor_neg :=
2968 mulmod(batching_challenge, mulmod(shplonk_nu, mload(mload(SS_NEG_INV_DENOM_LOC)), p), p)
2969
2970 mstore(scalars_loc, addmod(sub(p, scaling_factor_neg), sub(p, scaling_factor_pos), p))
2971
2972 let accum_contribution := mulmod(scaling_factor_neg, mload(mload(SS_GEMINI_EVALS_LOC)), p)
2973 accum_contribution := addmod(
2974 accum_contribution,
2975 mulmod(scaling_factor_pos, mload(fold_pos_evals_loc), p),
2976 p
2977 )
2978
2979 constant_term_acc := addmod(constant_term_acc, accum_contribution, p)
2980
2981 batching_challenge := mulmod(batching_challenge, shplonk_nu_sqr, p)
2982
2983 mstore(SS_POS_INV_DENOM_LOC, add(mload(SS_POS_INV_DENOM_LOC), 0x20))
2984 mstore(SS_NEG_INV_DENOM_LOC, add(mload(SS_NEG_INV_DENOM_LOC), 0x20))
2985 mstore(SS_GEMINI_EVALS_LOC, add(mload(SS_GEMINI_EVALS_LOC), 0x20))
2986 fold_pos_evals_loc := add(fold_pos_evals_loc, 0x20)
2987 scalars_loc := add(scalars_loc, 0x20)
2988 }
2989 }
2990
2991 let precomp_success_flag := 1
2992 let q := Q // EC group order
2993 {
2994 // The initial accumulator = 1 * shplonk_q
2995 // WORKTODO(md): we can ignore this accumulation as we are multiplying by 1,
2996 // Just set the accumulator instead.
2997 mstore(SCALAR_LOCATION, 0x1)
2998 mcopy(G1_LOCATION, SHPLONK_Q_X_LOC, 0x40)
2999 precomp_success_flag := staticcall(gas(), 7, G1_LOCATION, 0x60, ACCUMULATOR, 0x40)
3000 }
3001
3002 // Accumulate vk points
3003 loadVk()
3004 {
3005 // Acumulator = acumulator + scalar[1] * vk[0]
3006 mcopy(G1_LOCATION, Q_M_X_LOC, 0x40)
3007 mstore(SCALAR_LOCATION, mload(BATCH_SCALAR_1_LOC))
3008 precomp_success_flag := and(
3009 precomp_success_flag,
3010 staticcall(gas(), 7, G1_LOCATION, 0x60, ACCUMULATOR_2, 0x40)
3011 )
3012 precomp_success_flag := and(
3013 precomp_success_flag,
3014 staticcall(gas(), 6, ACCUMULATOR, 0x80, ACCUMULATOR, 0x40)
3015 )
3016
3017 // Accumulator = accumulator + scalar[2] * vk[1]
3018 mcopy(G1_LOCATION, Q_C_X_LOC, 0x40)
3019 mstore(SCALAR_LOCATION, mload(BATCH_SCALAR_2_LOC))
3020 precomp_success_flag := and(
3021 precomp_success_flag,
3022 staticcall(gas(), 7, G1_LOCATION, 0x60, ACCUMULATOR_2, 0x40)
3023 )
3024 precomp_success_flag := and(
3025 precomp_success_flag,
3026 staticcall(gas(), 6, ACCUMULATOR, 0x80, ACCUMULATOR, 0x40)
3027 )
3028
3029 // Accumulator = accumulator + scalar[3] * vk[2]
3030 mcopy(G1_LOCATION, Q_L_X_LOC, 0x40)
3031 mstore(SCALAR_LOCATION, mload(BATCH_SCALAR_3_LOC))
3032 precomp_success_flag := and(
3033 precomp_success_flag,
3034 staticcall(gas(), 7, G1_LOCATION, 0x60, ACCUMULATOR_2, 0x40)
3035 )
3036 precomp_success_flag := and(
3037 precomp_success_flag,
3038 staticcall(gas(), 6, ACCUMULATOR, 0x80, ACCUMULATOR, 0x40)
3039 )
3040
3041 // Accumulator = accumulator + scalar[4] * vk[3]
3042 mcopy(G1_LOCATION, Q_R_X_LOC, 0x40)
3043 mstore(SCALAR_LOCATION, mload(BATCH_SCALAR_4_LOC))
3044 precomp_success_flag := and(
3045 precomp_success_flag,
3046 staticcall(gas(), 7, G1_LOCATION, 0x60, ACCUMULATOR_2, 0x40)
3047 )
3048 precomp_success_flag := and(
3049 precomp_success_flag,
3050 staticcall(gas(), 6, ACCUMULATOR, 0x80, ACCUMULATOR, 0x40)
3051 )
3052
3053 // Accumulator = accumulator + scalar[5] * vk[4]
3054 mcopy(G1_LOCATION, Q_O_X_LOC, 0x40)
3055 mstore(SCALAR_LOCATION, mload(BATCH_SCALAR_5_LOC))
3056 precomp_success_flag := and(
3057 precomp_success_flag,
3058 staticcall(gas(), 7, G1_LOCATION, 0x60, ACCUMULATOR_2, 0x40)
3059 )
3060 precomp_success_flag := and(
3061 precomp_success_flag,
3062 staticcall(gas(), 6, ACCUMULATOR, 0x80, ACCUMULATOR, 0x40)
3063 )
3064
3065 // Accumulator = accumulator + scalar[6] * vk[5]
3066 mcopy(G1_LOCATION, Q_4_X_LOC, 0x40)
3067 mstore(SCALAR_LOCATION, mload(BATCH_SCALAR_6_LOC))
3068 precomp_success_flag := and(
3069 precomp_success_flag,
3070 staticcall(gas(), 7, G1_LOCATION, 0x60, ACCUMULATOR_2, 0x40)
3071 )
3072 precomp_success_flag := and(
3073 precomp_success_flag,
3074 staticcall(gas(), 6, ACCUMULATOR, 0x80, ACCUMULATOR, 0x40)
3075 )
3076
3077 // Accumulator = accumulator + scalar[7] * vk[6]
3078 mcopy(G1_LOCATION, Q_LOOKUP_X_LOC, 0x40)
3079 mstore(SCALAR_LOCATION, mload(BATCH_SCALAR_7_LOC))
3080 precomp_success_flag := and(
3081 precomp_success_flag,
3082 staticcall(gas(), 7, G1_LOCATION, 0x60, ACCUMULATOR_2, 0x40)
3083 )
3084 precomp_success_flag := and(
3085 precomp_success_flag,
3086 staticcall(gas(), 6, ACCUMULATOR, 0x80, ACCUMULATOR, 0x40)
3087 )
3088
3089 // Accumulator = accumulator + scalar[8] * vk[7]
3090 mcopy(G1_LOCATION, Q_ARITH_X_LOC, 0x40)
3091 mstore(SCALAR_LOCATION, mload(BATCH_SCALAR_8_LOC))
3092 precomp_success_flag := and(
3093 precomp_success_flag,
3094 staticcall(gas(), 7, G1_LOCATION, 0x60, ACCUMULATOR_2, 0x40)
3095 )
3096 precomp_success_flag := and(
3097 precomp_success_flag,
3098 staticcall(gas(), 6, ACCUMULATOR, 0x80, ACCUMULATOR, 0x40)
3099 )
3100
3101 // Accumulator = accumulator + scalar[9] * vk[8]
3102 mcopy(G1_LOCATION, Q_DELTA_RANGE_X_LOC, 0x40)
3103 mstore(SCALAR_LOCATION, mload(BATCH_SCALAR_9_LOC))
3104 precomp_success_flag := and(
3105 precomp_success_flag,
3106 staticcall(gas(), 7, G1_LOCATION, 0x60, ACCUMULATOR_2, 0x40)
3107 )
3108 precomp_success_flag := and(
3109 precomp_success_flag,
3110 staticcall(gas(), 6, ACCUMULATOR, 0x80, ACCUMULATOR, 0x40)
3111 )
3112
3113 // Accumulator = accumulator + scalar[10] * vk[9]
3114 mcopy(G1_LOCATION, Q_ELLIPTIC_X_LOC, 0x40)
3115 mstore(SCALAR_LOCATION, mload(BATCH_SCALAR_10_LOC))
3116 precomp_success_flag := and(
3117 precomp_success_flag,
3118 staticcall(gas(), 7, G1_LOCATION, 0x60, ACCUMULATOR_2, 0x40)
3119 )
3120 precomp_success_flag := and(
3121 precomp_success_flag,
3122 staticcall(gas(), 6, ACCUMULATOR, 0x80, ACCUMULATOR, 0x40)
3123 )
3124
3125 // Accumulator = accumulator + scalar[11] * vk[10]
3126 mcopy(G1_LOCATION, Q_MEMORY_X_LOC, 0x40)
3127 mstore(SCALAR_LOCATION, mload(BATCH_SCALAR_11_LOC))
3128 precomp_success_flag := and(
3129 precomp_success_flag,
3130 staticcall(gas(), 7, G1_LOCATION, 0x60, ACCUMULATOR_2, 0x40)
3131 )
3132 precomp_success_flag := and(
3133 precomp_success_flag,
3134 staticcall(gas(), 6, ACCUMULATOR, 0x80, ACCUMULATOR, 0x40)
3135 )
3136
3137 // Accumulator = accumulator + scalar[12] * vk[11]
3138 mcopy(G1_LOCATION, Q_NNF_X_LOC, 0x40)
3139 mstore(SCALAR_LOCATION, mload(BATCH_SCALAR_12_LOC))
3140 precomp_success_flag := and(
3141 precomp_success_flag,
3142 staticcall(gas(), 7, G1_LOCATION, 0x60, ACCUMULATOR_2, 0x40)
3143 )
3144 precomp_success_flag := and(
3145 precomp_success_flag,
3146 staticcall(gas(), 6, ACCUMULATOR, 0x80, ACCUMULATOR, 0x40)
3147 )
3148
3149 // Accumulator = accumulator + scalar[13] * vk[12]
3150 mcopy(G1_LOCATION, Q_POSEIDON_2_EXTERNAL_X_LOC, 0x40)
3151 mstore(SCALAR_LOCATION, mload(BATCH_SCALAR_13_LOC))
3152 precomp_success_flag := and(
3153 precomp_success_flag,
3154 staticcall(gas(), 7, G1_LOCATION, 0x60, ACCUMULATOR_2, 0x40)
3155 )
3156 precomp_success_flag := and(
3157 precomp_success_flag,
3158 staticcall(gas(), 6, ACCUMULATOR, 0x80, ACCUMULATOR, 0x40)
3159 )
3160
3161 // Accumulator = accumulator + scalar[14] * vk[13]
3162 mcopy(G1_LOCATION, Q_POSEIDON_2_INTERNAL_X_LOC, 0x40)
3163 mstore(SCALAR_LOCATION, mload(BATCH_SCALAR_14_LOC))
3164 precomp_success_flag := and(
3165 precomp_success_flag,
3166 staticcall(gas(), 7, G1_LOCATION, 0x60, ACCUMULATOR_2, 0x40)
3167 )
3168 precomp_success_flag := and(
3169 precomp_success_flag,
3170 staticcall(gas(), 6, ACCUMULATOR, 0x80, ACCUMULATOR, 0x40)
3171 )
3172
3173 // Accumulator = accumulator + scalar[15] * vk[14]
3174 mcopy(G1_LOCATION, SIGMA_1_X_LOC, 0x40)
3175 mstore(SCALAR_LOCATION, mload(BATCH_SCALAR_15_LOC))
3176 precomp_success_flag := and(
3177 precomp_success_flag,
3178 staticcall(gas(), 7, G1_LOCATION, 0x60, ACCUMULATOR_2, 0x40)
3179 )
3180 precomp_success_flag := and(
3181 precomp_success_flag,
3182 staticcall(gas(), 6, ACCUMULATOR, 0x80, ACCUMULATOR, 0x40)
3183 )
3184
3185 // Accumulator = accumulator + scalar[16] * vk[15]
3186 mcopy(G1_LOCATION, SIGMA_2_X_LOC, 0x40)
3187 mstore(SCALAR_LOCATION, mload(BATCH_SCALAR_16_LOC))
3188 precomp_success_flag := and(
3189 precomp_success_flag,
3190 staticcall(gas(), 7, G1_LOCATION, 0x60, ACCUMULATOR_2, 0x40)
3191 )
3192 precomp_success_flag := and(
3193 precomp_success_flag,
3194 staticcall(gas(), 6, ACCUMULATOR, 0x80, ACCUMULATOR, 0x40)
3195 )
3196
3197 // Accumulator = accumulator + scalar[17] * vk[16]
3198 mcopy(G1_LOCATION, SIGMA_3_X_LOC, 0x40)
3199 mstore(SCALAR_LOCATION, mload(BATCH_SCALAR_17_LOC))
3200 precomp_success_flag := and(
3201 precomp_success_flag,
3202 staticcall(gas(), 7, G1_LOCATION, 0x60, ACCUMULATOR_2, 0x40)
3203 )
3204 precomp_success_flag := and(
3205 precomp_success_flag,
3206 staticcall(gas(), 6, ACCUMULATOR, 0x80, ACCUMULATOR, 0x40)
3207 )
3208
3209 // Accumulator = accumulator + scalar[18] * vk[17]
3210 mcopy(G1_LOCATION, SIGMA_4_X_LOC, 0x40)
3211 mstore(SCALAR_LOCATION, mload(BATCH_SCALAR_18_LOC))
3212 precomp_success_flag := and(
3213 precomp_success_flag,
3214 staticcall(gas(), 7, G1_LOCATION, 0x60, ACCUMULATOR_2, 0x40)
3215 )
3216 precomp_success_flag := and(
3217 precomp_success_flag,
3218 staticcall(gas(), 6, ACCUMULATOR, 0x80, ACCUMULATOR, 0x40)
3219 )
3220
3221 // Accumulator = accumulator + scalar[19] * vk[18]
3222 mcopy(G1_LOCATION, ID_1_X_LOC, 0x40)
3223 mstore(SCALAR_LOCATION, mload(BATCH_SCALAR_19_LOC))
3224 precomp_success_flag := and(
3225 precomp_success_flag,
3226 staticcall(gas(), 7, G1_LOCATION, 0x60, ACCUMULATOR_2, 0x40)
3227 )
3228 precomp_success_flag := and(
3229 precomp_success_flag,
3230 staticcall(gas(), 6, ACCUMULATOR, 0x80, ACCUMULATOR, 0x40)
3231 )
3232
3233 // Accumulator = accumulator + scalar[20] * vk[19]
3234 mcopy(G1_LOCATION, ID_2_X_LOC, 0x40)
3235 mstore(SCALAR_LOCATION, mload(BATCH_SCALAR_20_LOC))
3236 precomp_success_flag := and(
3237 precomp_success_flag,
3238 staticcall(gas(), 7, G1_LOCATION, 0x60, ACCUMULATOR_2, 0x40)
3239 )
3240 precomp_success_flag := and(
3241 precomp_success_flag,
3242 staticcall(gas(), 6, ACCUMULATOR, 0x80, ACCUMULATOR, 0x40)
3243 )
3244
3245 // Accumulator = accumulator + scalar[21] * vk[20]
3246 mcopy(G1_LOCATION, ID_3_X_LOC, 0x40)
3247 mstore(SCALAR_LOCATION, mload(BATCH_SCALAR_21_LOC))
3248 precomp_success_flag := and(
3249 precomp_success_flag,
3250 staticcall(gas(), 7, G1_LOCATION, 0x60, ACCUMULATOR_2, 0x40)
3251 )
3252 precomp_success_flag := and(
3253 precomp_success_flag,
3254 staticcall(gas(), 6, ACCUMULATOR, 0x80, ACCUMULATOR, 0x40)
3255 )
3256
3257 // Accumulator = accumulator + scalar[22] * vk[21]
3258 mcopy(G1_LOCATION, ID_4_X_LOC, 0x40)
3259 mstore(SCALAR_LOCATION, mload(BATCH_SCALAR_22_LOC))
3260 precomp_success_flag := and(
3261 precomp_success_flag,
3262 staticcall(gas(), 7, G1_LOCATION, 0x60, ACCUMULATOR_2, 0x40)
3263 )
3264 precomp_success_flag := and(
3265 precomp_success_flag,
3266 staticcall(gas(), 6, ACCUMULATOR, 0x80, ACCUMULATOR, 0x40)
3267 )
3268
3269 // Accumulator = accumulator + scalar[23] * vk[22]
3270 mcopy(G1_LOCATION, TABLE_1_X_LOC, 0x40)
3271 mstore(SCALAR_LOCATION, mload(BATCH_SCALAR_23_LOC))
3272 precomp_success_flag := and(
3273 precomp_success_flag,
3274 staticcall(gas(), 7, G1_LOCATION, 0x60, ACCUMULATOR_2, 0x40)
3275 )
3276 precomp_success_flag := and(
3277 precomp_success_flag,
3278 staticcall(gas(), 6, ACCUMULATOR, 0x80, ACCUMULATOR, 0x40)
3279 )
3280
3281 // Accumulator = accumulator + scalar[24] * vk[23]
3282 mcopy(G1_LOCATION, TABLE_2_X_LOC, 0x40)
3283 mstore(SCALAR_LOCATION, mload(BATCH_SCALAR_24_LOC))
3284 precomp_success_flag := and(
3285 precomp_success_flag,
3286 staticcall(gas(), 7, G1_LOCATION, 0x60, ACCUMULATOR_2, 0x40)
3287 )
3288 precomp_success_flag := and(
3289 precomp_success_flag,
3290 staticcall(gas(), 6, ACCUMULATOR, 0x80, ACCUMULATOR, 0x40)
3291 )
3292
3293 // Accumulator = accumulator + scalar[25] * vk[24]
3294 mcopy(G1_LOCATION, TABLE_3_X_LOC, 0x40)
3295 mstore(SCALAR_LOCATION, mload(BATCH_SCALAR_25_LOC))
3296 precomp_success_flag := and(
3297 precomp_success_flag,
3298 staticcall(gas(), 7, G1_LOCATION, 0x60, ACCUMULATOR_2, 0x40)
3299 )
3300 precomp_success_flag := and(
3301 precomp_success_flag,
3302 staticcall(gas(), 6, ACCUMULATOR, 0x80, ACCUMULATOR, 0x40)
3303 )
3304
3305 // Accumulator = accumulator + scalar[26] * vk[25]
3306 mcopy(G1_LOCATION, TABLE_4_X_LOC, 0x40)
3307 mstore(SCALAR_LOCATION, mload(BATCH_SCALAR_26_LOC))
3308 precomp_success_flag := and(
3309 precomp_success_flag,
3310 staticcall(gas(), 7, G1_LOCATION, 0x60, ACCUMULATOR_2, 0x40)
3311 )
3312 precomp_success_flag := and(
3313 precomp_success_flag,
3314 staticcall(gas(), 6, ACCUMULATOR, 0x80, ACCUMULATOR, 0x40)
3315 )
3316
3317 // Accumulator = accumulator + scalar[27] * vk[26]
3318 mcopy(G1_LOCATION, LAGRANGE_FIRST_X_LOC, 0x40)
3319 mstore(SCALAR_LOCATION, mload(BATCH_SCALAR_27_LOC))
3320 precomp_success_flag := and(
3321 precomp_success_flag,
3322 staticcall(gas(), 7, G1_LOCATION, 0x60, ACCUMULATOR_2, 0x40)
3323 )
3324 precomp_success_flag := and(
3325 precomp_success_flag,
3326 staticcall(gas(), 6, ACCUMULATOR, 0x80, ACCUMULATOR, 0x40)
3327 )
3328
3329 // Accumulator = accumulator + scalar[28] * vk[27]
3330 mcopy(G1_LOCATION, LAGRANGE_LAST_X_LOC, 0x40)
3331 mstore(SCALAR_LOCATION, mload(BATCH_SCALAR_28_LOC))
3332 precomp_success_flag := and(
3333 precomp_success_flag,
3334 staticcall(gas(), 7, G1_LOCATION, 0x60, ACCUMULATOR_2, 0x40)
3335 )
3336 precomp_success_flag := and(
3337 precomp_success_flag,
3338 staticcall(gas(), 6, ACCUMULATOR, 0x80, ACCUMULATOR, 0x40)
3339 )
3340
3341 // Accumulate proof points
3342 // Accumulator = accumulator + scalar[29] * w_l
3343 mcopy(G1_LOCATION, W_L_X_LOC, 0x40)
3344 mstore(SCALAR_LOCATION, mload(BATCH_SCALAR_29_LOC))
3345 precomp_success_flag := and(
3346 precomp_success_flag,
3347 staticcall(gas(), 7, G1_LOCATION, 0x60, ACCUMULATOR_2, 0x40)
3348 )
3349 precomp_success_flag := and(
3350 precomp_success_flag,
3351 staticcall(gas(), 6, ACCUMULATOR, 0x80, ACCUMULATOR, 0x40)
3352 )
3353
3354 // Accumulator = accumulator + scalar[30] * w_r
3355 mcopy(G1_LOCATION, W_R_X_LOC, 0x40)
3356 mstore(SCALAR_LOCATION, mload(BATCH_SCALAR_30_LOC))
3357 precomp_success_flag := and(
3358 precomp_success_flag,
3359 staticcall(gas(), 7, G1_LOCATION, 0x60, ACCUMULATOR_2, 0x40)
3360 )
3361 precomp_success_flag := and(
3362 precomp_success_flag,
3363 staticcall(gas(), 6, ACCUMULATOR, 0x80, ACCUMULATOR, 0x40)
3364 )
3365
3366 // Accumulator = accumulator + scalar[31] * w_o
3367 mcopy(G1_LOCATION, W_O_X_LOC, 0x40)
3368 mstore(SCALAR_LOCATION, mload(BATCH_SCALAR_31_LOC))
3369 precomp_success_flag := and(
3370 precomp_success_flag,
3371 staticcall(gas(), 7, G1_LOCATION, 0x60, ACCUMULATOR_2, 0x40)
3372 )
3373 precomp_success_flag := and(
3374 precomp_success_flag,
3375 staticcall(gas(), 6, ACCUMULATOR, 0x80, ACCUMULATOR, 0x40)
3376 )
3377
3378 // Accumulator = accumulator + scalar[32] * w_4
3379 mcopy(G1_LOCATION, W_4_X_LOC, 0x40)
3380 mstore(SCALAR_LOCATION, mload(BATCH_SCALAR_32_LOC))
3381 precomp_success_flag := and(
3382 precomp_success_flag,
3383 staticcall(gas(), 7, G1_LOCATION, 0x60, ACCUMULATOR_2, 0x40)
3384 )
3385 precomp_success_flag := and(
3386 precomp_success_flag,
3387 staticcall(gas(), 6, ACCUMULATOR, 0x80, ACCUMULATOR, 0x40)
3388 )
3389
3390 // Accumulator = accumulator + scalar[33] * z_perm
3391 mcopy(G1_LOCATION, Z_PERM_X_LOC, 0x40)
3392 mstore(SCALAR_LOCATION, mload(BATCH_SCALAR_33_LOC))
3393 precomp_success_flag := and(
3394 precomp_success_flag,
3395 staticcall(gas(), 7, G1_LOCATION, 0x60, ACCUMULATOR_2, 0x40)
3396 )
3397 precomp_success_flag := and(
3398 precomp_success_flag,
3399 staticcall(gas(), 6, ACCUMULATOR, 0x80, ACCUMULATOR, 0x40)
3400 )
3401
3402 // Accumulator = accumulator + scalar[34] * lookup_inverses
3403 mcopy(G1_LOCATION, LOOKUP_INVERSES_X_LOC, 0x40)
3404 mstore(SCALAR_LOCATION, mload(BATCH_SCALAR_34_LOC))
3405 precomp_success_flag := and(
3406 precomp_success_flag,
3407 staticcall(gas(), 7, G1_LOCATION, 0x60, ACCUMULATOR_2, 0x40)
3408 )
3409 precomp_success_flag := and(
3410 precomp_success_flag,
3411 staticcall(gas(), 6, ACCUMULATOR, 0x80, ACCUMULATOR, 0x40)
3412 )
3413
3414 // Accumulator = accumulator + scalar[35] * lookup_read_counts
3415 mcopy(G1_LOCATION, LOOKUP_READ_COUNTS_X_LOC, 0x40)
3416 mstore(SCALAR_LOCATION, mload(BATCH_SCALAR_35_LOC))
3417 precomp_success_flag := and(
3418 precomp_success_flag,
3419 staticcall(gas(), 7, G1_LOCATION, 0x60, ACCUMULATOR_2, 0x40)
3420 )
3421 precomp_success_flag := and(
3422 precomp_success_flag,
3423 staticcall(gas(), 6, ACCUMULATOR, 0x80, ACCUMULATOR, 0x40)
3424 )
3425
3426 // Accumulator = accumulator + scalar[36] * lookup_read_tags
3427 mcopy(G1_LOCATION, LOOKUP_READ_TAGS_X_LOC, 0x40)
3428 mstore(SCALAR_LOCATION, mload(BATCH_SCALAR_36_LOC))
3429 precomp_success_flag := and(
3430 precomp_success_flag,
3431 staticcall(gas(), 7, G1_LOCATION, 0x60, ACCUMULATOR_2, 0x40)
3432 )
3433 precomp_success_flag := and(
3434 precomp_success_flag,
3435 staticcall(gas(), 6, ACCUMULATOR, 0x80, ACCUMULATOR, 0x40)
3436 )
3437
3438 // Accumulate these LOG_N scalars with the gemini fold univariates
3439 {
3440 {
3443 }
3444 }
3445
3446 {
3447 // Accumulate the constant term accumulator
3448 // Accumulator = accumulator + 1 * costant term accumulator
3449 mstore(G1_LOCATION, 0x01)
3450 mstore(G1_Y_LOCATION, 0x02)
3451 mstore(SCALAR_LOCATION, constant_term_acc)
3452 precomp_success_flag := and(
3453 precomp_success_flag,
3454 staticcall(gas(), 7, G1_LOCATION, 0x60, ACCUMULATOR_2, 0x40)
3455 )
3456 precomp_success_flag := and(
3457 precomp_success_flag,
3458 staticcall(gas(), 6, ACCUMULATOR, 0x80, ACCUMULATOR, 0x40)
3459 )
3460
3461 // Accumlate final quotient commitment into shplonk check
3462 // Accumulator = accumulator + shplonkZ * quotient commitment
3463 mcopy(G1_LOCATION, KZG_QUOTIENT_X_LOC, 0x40)
3464
3465 mstore(SCALAR_LOCATION, mload(SHPLONK_Z_CHALLENGE))
3466 precomp_success_flag := and(
3467 precomp_success_flag,
3468 staticcall(gas(), 7, G1_LOCATION, 0x60, ACCUMULATOR_2, 0x40)
3469 )
3470 precomp_success_flag := and(
3471 precomp_success_flag,
3472 staticcall(gas(), 6, ACCUMULATOR, 0x80, ACCUMULATOR, 0x40)
3473 )
3474 }
3475
3476 // All G1 points were validated on-curve during input validation.
3477 // precomp_success_flag now only tracks ecAdd/ecMul precompile success.
3478 if iszero(precomp_success_flag) {
3479 mstore(0x00, SHPLEMINI_FAILED_SELECTOR)
3480 revert(0x00, 0x04)
3481 }
3482
3483 /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
3484 /* SHPLEMINI - complete */
3485 /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/
3486
3487 /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
3488 /* PAIRING CHECK */
3489 /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/
3490 {
3491 // P_1
3492 mstore(0xc0, mload(KZG_QUOTIENT_X_LOC))
3493 mstore(0xe0, sub(q, mload(KZG_QUOTIENT_Y_LOC)))
3494
3495 // p_0_agg
3496 // 0x80 - p_0_agg x
3497 // 0xa0 - p_0_agg y
3498 mcopy(0x80, ACCUMULATOR, 0x40)
3499
3500 /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
3501 /* PAIRING AGGREGATION */
3502 /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/
3503 // Read the pairing encoded in the first 8 field elements of the proof (2 limbs per coordinate)
3504 let p0_other_x := mload(PAIRING_POINT_0_X_0_LOC)
3505 p0_other_x := or(shl(136, mload(PAIRING_POINT_0_X_1_LOC)), p0_other_x)
3506
3507 let p0_other_y := mload(PAIRING_POINT_0_Y_0_LOC)
3508 p0_other_y := or(shl(136, mload(PAIRING_POINT_0_Y_1_LOC)), p0_other_y)
3509
3510 let p1_other_x := mload(PAIRING_POINT_1_X_0_LOC)
3511 p1_other_x := or(shl(136, mload(PAIRING_POINT_1_X_1_LOC)), p1_other_x)
3512
3513 let p1_other_y := mload(PAIRING_POINT_1_Y_0_LOC)
3514 p1_other_y := or(shl(136, mload(PAIRING_POINT_1_Y_1_LOC)), p1_other_y)
3515
3516 // Check if pairing points are default (all zero = infinity = no recursive verification)
3517 let pairing_points_are_default := iszero(or(or(p0_other_x, p0_other_y), or(p1_other_x, p1_other_y)))
3518
3519 let success := 1
3520 // Only aggregate if pairing points are non-default
3521 if iszero(pairing_points_are_default) {
3522 // Reconstructed coordinates must be < Q to prevent malleability
3523 if iszero(and(
3524 and(lt(p0_other_x, q), lt(p0_other_y, q)),
3525 and(lt(p1_other_x, q), lt(p1_other_y, q))
3526 )) {
3527 mstore(0x00, VALUE_GE_GROUP_ORDER_SELECTOR)
3528 revert(0x00, 0x04)
3529 }
3530
3531 // Validate p_0_other not point of infinity
3532 success := iszero(iszero(or(p0_other_x, p0_other_y)))
3533 // Validate p_1_other not point of infinity
3534 success := and(success, iszero(iszero(or(p1_other_x, p1_other_y))))
3535
3536 // p_0
3537 mstore(0x00, p0_other_x)
3538 mstore(0x20, p0_other_y)
3539
3540 // p_1
3541 mstore(0x40, p1_other_x)
3542 mstore(0x60, p1_other_y)
3543
3544 // p_1_agg is already in the correct location
3545
3546 let recursion_separator := keccak256(0x00, 0x100)
3547
3548 // Write separator back to scratch space
3549 mstore(0x00, p0_other_x)
3550
3551 mstore(0x40, recursion_separator)
3552 // recursion_separator * p_0_other
3553 success := and(success, staticcall(gas(), 0x07, 0x00, 0x60, 0x00, 0x40))
3554
3555 // (recursion_separator * p_0_other) + p_0_agg
3556 mcopy(0x40, 0x80, 0x40)
3557 // p_0 = (recursion_separator * p_0_other) + p_0_agg
3558 success := and(success, staticcall(gas(), 6, 0x00, 0x80, 0x00, 0x40))
3559
3560 mstore(0x40, p1_other_x)
3561 mstore(0x60, p1_other_y)
3562 mstore(0x80, recursion_separator)
3563
3564 success := and(success, staticcall(gas(), 7, 0x40, 0x60, 0x40, 0x40))
3565
3566 // Write p_1_agg back to scratch space
3567 mcopy(0x80, 0xc0, 0x40)
3568
3569 // 0xc0 - (recursion_separator * p_1_other) + p_1_agg
3570 success := and(success, staticcall(gas(), 6, 0x40, 0x80, 0xc0, 0x40))
3571 }
3572 // If default pairing points, use p_0_agg and p_1_agg directly (already at 0x80, 0xc0)
3573 if pairing_points_are_default {
3574 // Copy p_0_agg to 0x00 for pairing input
3575 mcopy(0x00, 0x80, 0x40)
3576 // p_1_agg stays at 0xc0
3577 }
3578
3579 // G2 [1]
3580 mstore(0x40, 0x198e9393920d483a7260bfb731fb5d25f1aa493335a9e71297e485b7aef312c2)
3581 mstore(0x60, 0x1800deef121f1e76426a00665e5c4479674322d4f75edadd46debd5cd992f6ed)
3582 mstore(0x80, 0x090689d0585ff075ec9e99ad690c3395bc4b313370b38ef355acdadcd122975b)
3583 mstore(0xa0, 0x12c85ea5db8c6deb4aab71808dcb408fe3d1e7690c43d37b4ce6cc0166fa7daa)
3584
3585 // G2 [x]
3586 mstore(0x100, 0x260e01b251f6f1c7e7ff4e580791dee8ea51d87a358e038b4efe30fac09383c1)
3587 mstore(0x120, 0x0118c4d5b837bcc2bc89b5b398b5974e9f5944073b32078b7e231fec938883b0)
3588 mstore(0x140, 0x04fc6369f7110fe3d25156c1bb9a72859cf2a04641f99ba4ee413c80da6a5fe4)
3589 mstore(0x160, 0x22febda3c0c0632a56475b4214e5615e11e6dd3f96e6cea2854a87d4dacc5e55)
3590
3591 let pairing_success := and(success, staticcall(gas(), 8, 0x00, 0x180, 0x00, 0x20))
3592 if iszero(and(pairing_success, mload(0x00))) {
3593 mstore(0x00, SHPLEMINI_FAILED_SELECTOR)
3594 revert(0x00, 0x04)
3595 }
3596
3597 /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
3598 /* PAIRING CHECK - Complete */
3599 /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/
3600 }
3601 {
3602 mstore(0x00, 0x01)
3603 return(0x00, 0x20) // Proof succeeded!
3604 }
3605 }
3606 }
3607 }
3608}
3609)";
3610
3611template <typename Field> std::string field_to_hex(const Field& f)
3612{
3613 std::ostringstream os;
3614 os << f;
3615 return os.str();
3616}
3617
3618inline std::string int_to_hex(size_t i)
3619{
3620 std::ostringstream os;
3621 os << "0x" << std::hex << i;
3622 return os.str();
3623}
3624
3625inline std::string get_optimized_honk_solidity_verifier(auto const& verification_key)
3626{
3627 std::string template_str = HONK_CONTRACT_OPT_SOURCE;
3628
3629 // Helper function to replace template variables
3630 auto set_template_param = [&template_str](const std::string& key, const std::string& value) {
3631 std::string::size_type pos = 0;
3632 std::string pattern = "{{ " + key + " }}";
3633 while ((pos = template_str.find(pattern, pos)) != std::string::npos) {
3634 template_str.replace(pos, pattern.length(), value);
3635 pos += value.length();
3636 }
3637 };
3638
3639 set_template_param("VK_HASH", field_to_hex(verification_key->hash()));
3640 set_template_param("CIRCUIT_SIZE", std::to_string(1 << verification_key->log_circuit_size));
3641 set_template_param("LOG_CIRCUIT_SIZE", std::to_string(verification_key->log_circuit_size));
3642 set_template_param("NUM_PUBLIC_INPUTS", std::to_string(verification_key->num_public_inputs));
3643 // REAL_NUM_PUBLIC_INPUTS excludes the 8 pairing point limbs that are part of the proof structure
3644 set_template_param("REAL_NUM_PUBLIC_INPUTS",
3645 std::to_string(verification_key->num_public_inputs - bb::PAIRING_POINTS_SIZE));
3646 set_template_param("LOG_N_MINUS_ONE", std::to_string(verification_key->log_circuit_size - 1));
3647 set_template_param("NUMBER_OF_BARYCENTRIC_INVERSES", std::to_string(verification_key->log_circuit_size * 8));
3648
3649 uint32_t gemini_fold_univariate_length = static_cast<uint32_t>((verification_key->log_circuit_size - 1) * 0x40);
3650 uint32_t gemini_fold_univariate_hash_length = static_cast<uint32_t>(gemini_fold_univariate_length + 0x20);
3651 uint32_t gemini_evals_length = static_cast<uint32_t>(verification_key->log_circuit_size * 0x20);
3652 uint32_t gemini_evals_hash_length = static_cast<uint32_t>(gemini_evals_length + 0x20);
3653
3654 set_template_param("GEMINI_FOLD_UNIVARIATE_LENGTH", int_to_hex(gemini_fold_univariate_length));
3655 set_template_param("GEMINI_FOLD_UNIVARIATE_HASH_LENGTH", int_to_hex(gemini_fold_univariate_hash_length));
3656 set_template_param("GEMINI_EVALS_LENGTH", int_to_hex(gemini_evals_length));
3657 set_template_param("GEMINI_EVALS_HASH_LENGTH", int_to_hex(gemini_evals_hash_length));
3658
3659 // Verification Key
3660 set_template_param("Q_L_X_LOC", field_to_hex(verification_key->q_l.x));
3661 set_template_param("Q_L_Y_LOC", field_to_hex(verification_key->q_l.y));
3662 set_template_param("Q_R_X_LOC", field_to_hex(verification_key->q_r.x));
3663 set_template_param("Q_R_Y_LOC", field_to_hex(verification_key->q_r.y));
3664 set_template_param("Q_O_X_LOC", field_to_hex(verification_key->q_o.x));
3665 set_template_param("Q_O_Y_LOC", field_to_hex(verification_key->q_o.y));
3666 set_template_param("Q_4_X_LOC", field_to_hex(verification_key->q_4.x));
3667 set_template_param("Q_4_Y_LOC", field_to_hex(verification_key->q_4.y));
3668 set_template_param("Q_M_X_LOC", field_to_hex(verification_key->q_m.x));
3669 set_template_param("Q_M_Y_LOC", field_to_hex(verification_key->q_m.y));
3670 set_template_param("Q_C_X_LOC", field_to_hex(verification_key->q_c.x));
3671 set_template_param("Q_C_Y_LOC", field_to_hex(verification_key->q_c.y));
3672 set_template_param("Q_LOOKUP_X_LOC", field_to_hex(verification_key->q_lookup.x));
3673 set_template_param("Q_LOOKUP_Y_LOC", field_to_hex(verification_key->q_lookup.y));
3674 set_template_param("Q_ARITH_X_LOC", field_to_hex(verification_key->q_arith.x));
3675 set_template_param("Q_ARITH_Y_LOC", field_to_hex(verification_key->q_arith.y));
3676 set_template_param("Q_DELTA_RANGE_X_LOC", field_to_hex(verification_key->q_delta_range.x));
3677 set_template_param("Q_DELTA_RANGE_Y_LOC", field_to_hex(verification_key->q_delta_range.y));
3678 set_template_param("Q_ELLIPTIC_X_LOC", field_to_hex(verification_key->q_elliptic.x));
3679 set_template_param("Q_ELLIPTIC_Y_LOC", field_to_hex(verification_key->q_elliptic.y));
3680 set_template_param("Q_MEMORY_X_LOC", field_to_hex(verification_key->q_memory.x));
3681 set_template_param("Q_MEMORY_Y_LOC", field_to_hex(verification_key->q_memory.y));
3682 set_template_param("Q_NNF_X_LOC", field_to_hex(verification_key->q_nnf.x));
3683 set_template_param("Q_NNF_Y_LOC", field_to_hex(verification_key->q_nnf.y));
3684 set_template_param("Q_POSEIDON_2_EXTERNAL_X_LOC", field_to_hex(verification_key->q_poseidon2_external.x));
3685 set_template_param("Q_POSEIDON_2_EXTERNAL_Y_LOC", field_to_hex(verification_key->q_poseidon2_external.y));
3686 set_template_param("Q_POSEIDON_2_INTERNAL_X_LOC", field_to_hex(verification_key->q_poseidon2_internal.x));
3687 set_template_param("Q_POSEIDON_2_INTERNAL_Y_LOC", field_to_hex(verification_key->q_poseidon2_internal.y));
3688 set_template_param("SIGMA_1_X_LOC", field_to_hex(verification_key->sigma_1.x));
3689 set_template_param("SIGMA_1_Y_LOC", field_to_hex(verification_key->sigma_1.y));
3690 set_template_param("SIGMA_2_X_LOC", field_to_hex(verification_key->sigma_2.x));
3691 set_template_param("SIGMA_2_Y_LOC", field_to_hex(verification_key->sigma_2.y));
3692 set_template_param("SIGMA_3_X_LOC", field_to_hex(verification_key->sigma_3.x));
3693 set_template_param("SIGMA_3_Y_LOC", field_to_hex(verification_key->sigma_3.y));
3694 set_template_param("SIGMA_4_X_LOC", field_to_hex(verification_key->sigma_4.x));
3695 set_template_param("SIGMA_4_Y_LOC", field_to_hex(verification_key->sigma_4.y));
3696 set_template_param("TABLE_1_X_LOC", field_to_hex(verification_key->table_1.x));
3697 set_template_param("TABLE_1_Y_LOC", field_to_hex(verification_key->table_1.y));
3698 set_template_param("TABLE_2_X_LOC", field_to_hex(verification_key->table_2.x));
3699 set_template_param("TABLE_2_Y_LOC", field_to_hex(verification_key->table_2.y));
3700 set_template_param("TABLE_3_X_LOC", field_to_hex(verification_key->table_3.x));
3701 set_template_param("TABLE_3_Y_LOC", field_to_hex(verification_key->table_3.y));
3702 set_template_param("TABLE_4_X_LOC", field_to_hex(verification_key->table_4.x));
3703 set_template_param("TABLE_4_Y_LOC", field_to_hex(verification_key->table_4.y));
3704 set_template_param("ID_1_X_LOC", field_to_hex(verification_key->id_1.x));
3705 set_template_param("ID_1_Y_LOC", field_to_hex(verification_key->id_1.y));
3706 set_template_param("ID_2_X_LOC", field_to_hex(verification_key->id_2.x));
3707 set_template_param("ID_2_Y_LOC", field_to_hex(verification_key->id_2.y));
3708 set_template_param("ID_3_X_LOC", field_to_hex(verification_key->id_3.x));
3709 set_template_param("ID_3_Y_LOC", field_to_hex(verification_key->id_3.y));
3710 set_template_param("ID_4_X_LOC", field_to_hex(verification_key->id_4.x));
3711 set_template_param("ID_4_Y_LOC", field_to_hex(verification_key->id_4.y));
3712 set_template_param("LAGRANGE_FIRST_X_LOC", field_to_hex(verification_key->lagrange_first.x));
3713 set_template_param("LAGRANGE_FIRST_Y_LOC", field_to_hex(verification_key->lagrange_first.y));
3714 set_template_param("LAGRANGE_LAST_X_LOC", field_to_hex(verification_key->lagrange_last.x));
3715 set_template_param("LAGRANGE_LAST_Y_LOC", field_to_hex(verification_key->lagrange_last.y));
3716
3717 // Generate unrolled sections based on LOG_N
3718 auto generate_unroll_section = [](const std::string& section_name, auto log_n) {
3719 std::ostringstream code;
3720
3721 if (section_name == "ACCUMULATE_INVERSES") {
3722 // Generate INVERTED_CHALLENEGE_POW_MINUS_U accumulations
3723 for (int i = 0; i < log_n; ++i) {
3724 code << " // i = " << i << "\n";
3725 code << " mstore(TEMP_" << i << "_LOC, accumulator)\n";
3726 code << " accumulator := mulmod(accumulator, mload(INVERTED_CHALLENEGE_POW_MINUS_U_" << i
3727 << "_LOC), p)\n";
3728 }
3729
3730 code << "\n // Accumulate pos inverted denom\n";
3731 int temp_idx = log_n;
3732 for (int i = 0; i < log_n; ++i) {
3733 code << " // i = " << i << "\n";
3734 code << " mstore(TEMP_" << temp_idx << "_LOC, accumulator)\n";
3735 code << " accumulator := mulmod(accumulator, mload(POS_INVERTED_DENOM_" << i
3736 << "_LOC), p)\n";
3737 temp_idx++;
3738 }
3739
3740 code << "\n // Accumulate neg inverted denom\n";
3741 for (int i = 0; i < log_n; ++i) {
3742 code << " // i = " << i << "\n";
3743 code << " mstore(TEMP_" << temp_idx << "_LOC, accumulator)\n";
3744 code << " accumulator := mulmod(accumulator, mload(NEG_INVERTED_DENOM_" << i
3745 << "_LOC), p)\n";
3746 temp_idx++;
3747 }
3748 } else if (section_name == "COLLECT_INVERSES") {
3749 int temp_idx = 3 * log_n - 1;
3750
3751 // Process NEG_INVERTED_DENOM in reverse order
3752 code << " // i = " << log_n << "\n";
3753 for (int i = log_n - 1; i >= 0; --i) {
3754 code << " {\n";
3755 code << " let tmp := mulmod(accumulator, mload(TEMP_" << temp_idx << "_LOC), p)\n";
3756 code << " accumulator := mulmod(accumulator, mload(NEG_INVERTED_DENOM_" << i
3757 << "_LOC), p)\n";
3758 code << " mstore(NEG_INVERTED_DENOM_" << i << "_LOC, tmp)\n";
3759 code << " }\n";
3760 if (i > 0) {
3761 code << " // i = " << i << "\n";
3762 }
3763 temp_idx--;
3764 }
3765
3766 code << "\n // Unrolled for LOG_N = " << log_n << "\n";
3767 code << " // i = " << log_n << "\n";
3768
3769 // Process POS_INVERTED_DENOM in reverse order
3770 for (int i = log_n - 1; i >= 0; --i) {
3771 code << " {\n";
3772 code << " let tmp := mulmod(accumulator, mload(TEMP_" << temp_idx << "_LOC), p)\n";
3773 code << " accumulator := mulmod(accumulator, mload(POS_INVERTED_DENOM_" << i
3774 << "_LOC), p)\n";
3775 code << " mstore(POS_INVERTED_DENOM_" << i << "_LOC, tmp)\n";
3776 code << " }\n";
3777 if (i > 0) {
3778 code << " // i = " << i << "\n";
3779 }
3780 temp_idx--;
3781 }
3782
3783 code << "\n // i = " << log_n << "\n";
3784
3785 // Process INVERTED_CHALLENEGE_POW_MINUS_U in reverse order
3786 for (int i = log_n - 1; i >= 0; --i) {
3787 code << " {\n";
3788 code << " let tmp := mulmod(accumulator, mload(TEMP_" << temp_idx << "_LOC), p)\n";
3789 code << " accumulator := mulmod(accumulator, mload(INVERTED_CHALLENEGE_POW_MINUS_U_" << i
3790 << "_LOC), p)\n";
3791 code << " mstore(INVERTED_CHALLENEGE_POW_MINUS_U_" << i << "_LOC, tmp)\n";
3792 code << " }\n";
3793 if (i > 0) {
3794 code << " // i = " << i << "\n";
3795 }
3796 temp_idx--;
3797 }
3798 } else if (section_name == "ACCUMULATE_GEMINI_FOLD_UNIVARIATE") {
3799 // Generate GEMINI_FOLD_UNIVARIATE accumulations
3800 // We need log_n - 1 folding commitments
3801 for (int i = 0; i < log_n - 1; ++i) {
3802 // Validate on curve then accumulate
3803 code << " {\n";
3804 code << " let x := mload(GEMINI_FOLD_UNIVARIATE_" << i << "_X_LOC)\n";
3805 code << " let y := mload(GEMINI_FOLD_UNIVARIATE_" << i << "_Y_LOC)\n";
3806 code << " let xx := mulmod(x, x, q)\n";
3807 code << " // validate on curve\n";
3808 code << " precomp_success_flag := and(eq(mulmod(y, y, q), addmod(mulmod(x, "
3809 "xx, q), 3, q)), precomp_success_flag)\n";
3810 code << " }\n";
3811 code << " mcopy(G1_LOCATION, GEMINI_FOLD_UNIVARIATE_" << i << "_X_LOC, 0x40)\n";
3812 code << " mstore(SCALAR_LOCATION, mload(BATCH_SCALAR_" << (37 + i) << "_LOC))\n";
3813 code << " precomp_success_flag :=\n";
3814 code << " and(precomp_success_flag, staticcall(gas(), 7, G1_LOCATION, 0x60, "
3815 "ACCUMULATOR_2, 0x40))\n";
3816 code << " precomp_success_flag :=\n";
3817 code << " and(precomp_success_flag, staticcall(gas(), 6, ACCUMULATOR, 0x80, "
3818 "ACCUMULATOR, 0x40))\n";
3819 if (i < log_n - 2) {
3820 code << "\n";
3821 }
3822 }
3823 } else if (section_name == "GEMINI_FOLD_UNIVARIATE_ON_CURVE") {
3824 // Generate GEMINI_FOLD_UNIVARIATE_ON_CURVE validations
3825 // We need log_n - 1 folding commitments to validate
3826 for (int i = 0; i < log_n - 1; ++i) {
3827 code << " success_flag := and(success_flag, "
3828 "validateProofPointOnCurve(GEMINI_FOLD_UNIVARIATE_"
3829 << i << "_X_LOC, q))\n";
3830 }
3831 }
3832
3833 return code.str();
3834 };
3835
3836 // Replace UNROLL_SECTION blocks
3837 int log_n = static_cast<int>(verification_key->log_circuit_size);
3838
3839 // Replace ACCUMULATE_INVERSES section
3840 {
3841 std::string::size_type start_pos = template_str.find("/// {{ UNROLL_SECTION_START ACCUMULATE_INVERSES }}");
3842 std::string::size_type end_pos = template_str.find("/// {{UNROLL_SECTION_END ACCUMULATE_INVERSES }}");
3843 if (start_pos != std::string::npos && end_pos != std::string::npos) {
3844 std::string::size_type start_line_end = template_str.find("\n", start_pos);
3845 std::string generated_code = generate_unroll_section("ACCUMULATE_INVERSES", log_n);
3846 template_str = template_str.substr(0, start_line_end + 1) + generated_code + template_str.substr(end_pos);
3847 }
3848 }
3849
3850 // Replace COLLECT_INVERSES section
3851 {
3852 std::string::size_type start_pos = template_str.find("// {{ UNROLL_SECTION_START COLLECT_INVERSES }}");
3853 std::string::size_type end_pos = template_str.find("// {{ UNROLL_SECTION_END COLLECT_INVERSES }}");
3854 if (start_pos != std::string::npos && end_pos != std::string::npos) {
3855 std::string::size_type start_line_end = template_str.find("\n", start_pos);
3856 std::string generated_code = generate_unroll_section("COLLECT_INVERSES", log_n);
3857 template_str = template_str.substr(0, start_line_end + 1) + generated_code + template_str.substr(end_pos);
3858 }
3859 }
3860
3861 // Replace ACCUMULATE_GEMINI_FOLD_UNIVARIATE section
3862 {
3863 std::string::size_type start_pos =
3864 template_str.find("/// {{ UNROLL_SECTION_START ACCUMULATE_GEMINI_FOLD_UNIVARIATE }}");
3865 std::string::size_type end_pos =
3866 template_str.find("/// {{ UNROLL_SECTION_END ACCUMULATE_GEMINI_FOLD_UNIVARIATE }}");
3867 if (start_pos != std::string::npos && end_pos != std::string::npos) {
3868 std::string::size_type start_line_end = template_str.find("\n", start_pos);
3869 std::string generated_code = generate_unroll_section("ACCUMULATE_GEMINI_FOLD_UNIVARIATE", log_n);
3870 template_str = template_str.substr(0, start_line_end + 1) + generated_code + template_str.substr(end_pos);
3871 }
3872 }
3873
3874 // Replace GEMINI_FOLD_UNIVARIATE_ON_CURVE section
3875 {
3876 std::string::size_type start_pos =
3877 template_str.find("/// {{ UNROLL_SECTION_START GEMINI_FOLD_UNIVARIATE_ON_CURVE }}");
3878 std::string::size_type end_pos =
3879 template_str.find("/// {{ UNROLL_SECTION_END GEMINI_FOLD_UNIVARIATE_ON_CURVE }}");
3880 if (start_pos != std::string::npos && end_pos != std::string::npos) {
3881 std::string::size_type start_line_end = template_str.find("\n", start_pos);
3882 std::string generated_code = generate_unroll_section("GEMINI_FOLD_UNIVARIATE_ON_CURVE", log_n);
3883 template_str = template_str.substr(0, start_line_end + 1) + generated_code + template_str.substr(end_pos);
3884 }
3885 }
3886
3887 // Replace Memory Layout
3888 {
3889 std::string::size_type start_pos = template_str.find("// {{ SECTION_START MEMORY_LAYOUT }}");
3890 std::string::size_type end_pos = template_str.find("// {{ SECTION_END MEMORY_LAYOUT }}");
3891 if (start_pos != std::string::npos && end_pos != std::string::npos) {
3892 std::string::size_type start_line_end = template_str.find("\n", start_pos);
3893 std::string generated_code = generate_memory_offsets(log_n);
3894 template_str = template_str.substr(0, start_line_end + 1) + generated_code + template_str.substr(end_pos);
3895 }
3896 }
3897
3898 return template_str;
3899}
std::string field_to_hex(const Field &f)
std::string get_optimized_honk_solidity_verifier(auto const &verification_key)
std::string generate_memory_offsets(int log_n)
std::string int_to_hex(size_t i)
constexpr decltype(auto) get(::tuplet::tuple< T... > &&t) noexcept
Definition tuple.hpp:13
std::string to_string(bb::avm2::ValueTag tag)