pragma solidity ^0.8.0;
import "./PairingsBn254.sol";
import "./TranscriptLib.sol";
import "./UncheckedMath.sol";
uint256 constant STATE_WIDTH = {{STATE_WIDTH}};
uint256 constant NUM_G2_ELS = {{NUM_G2_ELS}};
struct VerificationKey {
uint256 domain_size;
uint256 num_inputs;
PairingsBn254.Fr omega;
PairingsBn254.G1Point[{{NUM_GATES}}] gate_selectors_commitments;
PairingsBn254.G1Point[{{NUM_MAIN_GATE_SELECTORS}}] gate_setup_commitments;
PairingsBn254.G1Point[STATE_WIDTH] permutation_commitments;
{{#if has_lookup}}
PairingsBn254.G1Point lookup_selector_commitment;
PairingsBn254.G1Point[{{NUM_LOOKUP_TABLES}}] lookup_tables_commitments;
PairingsBn254.G1Point lookup_table_type_commitment;
{{/if}}
PairingsBn254.Fr[STATE_WIDTH-1] non_residues;
PairingsBn254.G2Point[NUM_G2_ELS] g2_elements;
}
contract Plonk4VerifierWithAccessToDNext {
using PairingsBn254 for PairingsBn254.G1Point;
using PairingsBn254 for PairingsBn254.G2Point;
using PairingsBn254 for PairingsBn254.Fr;
using TranscriptLib for TranscriptLib.Transcript;
using UncheckedMath for uint256;
struct Proof {
uint256[] input_values;
// commitments
PairingsBn254.G1Point[STATE_WIDTH] state_polys_commitments;
PairingsBn254.G1Point copy_permutation_grand_product_commitment;
PairingsBn254.G1Point[STATE_WIDTH] quotient_poly_parts_commitments;
// openings
PairingsBn254.Fr[STATE_WIDTH] state_polys_openings_at_z;
PairingsBn254.Fr[1] state_polys_openings_at_z_omega;
{{#if has_rescue_custom_gate}}
PairingsBn254.Fr[1] gate_selectors_openings_at_z;
{{/if}}
PairingsBn254.Fr[STATE_WIDTH-1] copy_permutation_polys_openings_at_z;
PairingsBn254.Fr copy_permutation_grand_product_opening_at_z_omega;
PairingsBn254.Fr quotient_poly_opening_at_z;
PairingsBn254.Fr linearization_poly_opening_at_z;
{{#if has_lookup}}
// lookup commitments
PairingsBn254.G1Point lookup_s_poly_commitment;
PairingsBn254.G1Point lookup_grand_product_commitment;
// lookup openings
PairingsBn254.Fr lookup_s_poly_opening_at_z_omega;
PairingsBn254.Fr lookup_grand_product_opening_at_z_omega;
PairingsBn254.Fr lookup_t_poly_opening_at_z;
PairingsBn254.Fr lookup_t_poly_opening_at_z_omega;
PairingsBn254.Fr lookup_selector_poly_opening_at_z;
PairingsBn254.Fr lookup_table_type_poly_opening_at_z;
{{/if}}
PairingsBn254.G1Point opening_proof_at_z;
PairingsBn254.G1Point opening_proof_at_z_omega;
}
struct PartialVerifierState {
PairingsBn254.Fr zero;
PairingsBn254.Fr alpha;
PairingsBn254.Fr beta;
PairingsBn254.Fr gamma;
PairingsBn254.Fr[{{NUM_ALPHA_CHALLENGES}}] alpha_values;
{{#if has_lookup}}
PairingsBn254.Fr eta;
PairingsBn254.Fr beta_lookup;
PairingsBn254.Fr gamma_lookup;
PairingsBn254.Fr beta_plus_one;
PairingsBn254.Fr beta_gamma;
{{/if}}
PairingsBn254.Fr v;
PairingsBn254.Fr u;
PairingsBn254.Fr z;
PairingsBn254.Fr z_omega;
PairingsBn254.Fr z_minus_last_omega;
PairingsBn254.Fr l_0_at_z;
PairingsBn254.Fr l_n_minus_one_at_z;
PairingsBn254.Fr t;
PairingsBn254.G1Point tp;
}
function evaluate_l0_at_point(
uint256 domain_size,
PairingsBn254.Fr memory at
) internal view returns (PairingsBn254.Fr memory num) {
PairingsBn254.Fr memory one = PairingsBn254.new_fr(1);
PairingsBn254.Fr memory size_fe = PairingsBn254.new_fr(domain_size);
PairingsBn254.Fr memory den = at.copy();
den.sub_assign(one);
den.mul_assign(size_fe);
den = den.inverse();
num = at.pow(domain_size);
num.sub_assign(one);
num.mul_assign(den);
}
function evaluate_lagrange_poly_out_of_domain(
uint256 poly_num,
uint256 domain_size,
PairingsBn254.Fr memory omega,
PairingsBn254.Fr memory at
) internal view returns (PairingsBn254.Fr memory res) {
// (omega^i / N) / (X - omega^i) * (X^N - 1)
require(poly_num < domain_size);
PairingsBn254.Fr memory one = PairingsBn254.new_fr(1);
PairingsBn254.Fr memory omega_power = omega.pow(poly_num);
res = at.pow(domain_size);
res.sub_assign(one);
require(res.value != 0); // Vanishing polynomial can not be zero at point `at`
res.mul_assign(omega_power);
PairingsBn254.Fr memory den = PairingsBn254.copy(at);
den.sub_assign(omega_power);
den.mul_assign(PairingsBn254.new_fr(domain_size));
den = den.inverse();
res.mul_assign(den);
}
function evaluate_vanishing(
uint256 domain_size,
PairingsBn254.Fr memory at
) internal view returns (PairingsBn254.Fr memory res) {
res = at.pow(domain_size);
res.sub_assign(PairingsBn254.new_fr(1));
}
function initialize_transcript(Proof memory proof, VerificationKey memory vk) internal pure returns (PartialVerifierState memory state) {
TranscriptLib.Transcript memory transcript = TranscriptLib.new_transcript();
for(uint256 i =0; i < vk.num_inputs; i = i.uncheckedInc()){
transcript.update_with_u256(proof.input_values[i]);
}
for(uint256 i = 0; i < STATE_WIDTH; i = i.uncheckedInc()){
transcript.update_with_g1(proof.state_polys_commitments[i]);
}
{{#if has_lookup}}
state.eta = transcript.get_challenge();
transcript.update_with_g1(proof.lookup_s_poly_commitment);
{{/if}}
state.beta = transcript.get_challenge();
state.gamma = transcript.get_challenge();
transcript.update_with_g1(proof.copy_permutation_grand_product_commitment);
{{#if has_lookup}}
state.beta_lookup = transcript.get_challenge();
state.gamma_lookup = transcript.get_challenge();
transcript.update_with_g1(proof.lookup_grand_product_commitment);
{{/if}}
state.alpha = transcript.get_challenge();
for(uint256 i =0; i < proof.quotient_poly_parts_commitments.length; i = i.uncheckedInc()){
transcript.update_with_g1(proof.quotient_poly_parts_commitments[i]);
}
state.z = transcript.get_challenge();
transcript.update_with_fr(proof.quotient_poly_opening_at_z);
for(uint256 i =0; i < proof.state_polys_openings_at_z.length; i = i.uncheckedInc()){
transcript.update_with_fr(proof.state_polys_openings_at_z[i]);
}
for(uint256 i =0; i < proof.state_polys_openings_at_z_omega.length; i = i.uncheckedInc()){
transcript.update_with_fr(proof.state_polys_openings_at_z_omega[i]);
}
{{#if has_rescue_custom_gate}}
for(uint256 i =0; i < proof.gate_selectors_openings_at_z.length; i = i.uncheckedInc()){
transcript.update_with_fr(proof.gate_selectors_openings_at_z[i]);
}
{{/if}}
for(uint256 i =0; i < proof.copy_permutation_polys_openings_at_z.length; i = i.uncheckedInc()){
transcript.update_with_fr(proof.copy_permutation_polys_openings_at_z[i]);
}
state.z_omega = state.z.copy();
state.z_omega.mul_assign(vk.omega);
transcript.update_with_fr(proof.copy_permutation_grand_product_opening_at_z_omega);
{{#if has_lookup}}
transcript.update_with_fr(proof.lookup_t_poly_opening_at_z);
transcript.update_with_fr(proof.lookup_selector_poly_opening_at_z);
transcript.update_with_fr(proof.lookup_table_type_poly_opening_at_z);
transcript.update_with_fr(proof.lookup_s_poly_opening_at_z_omega);
transcript.update_with_fr(proof.lookup_grand_product_opening_at_z_omega);
transcript.update_with_fr(proof.lookup_t_poly_opening_at_z_omega);
{{/if}}
transcript.update_with_fr(proof.linearization_poly_opening_at_z);
state.v = transcript.get_challenge();
transcript.update_with_g1(proof.opening_proof_at_z);
transcript.update_with_g1(proof.opening_proof_at_z_omega);
state.u = transcript.get_challenge();
}
// compute some powers of challenge alpha([alpha^1, .. alpha^8])
function compute_powers_of_alpha(PartialVerifierState memory state) public pure {
require(state.alpha.value != 0);
state.alpha_values[0] = PairingsBn254.new_fr(1);
state.alpha_values[1] = state.alpha.copy();
PairingsBn254.Fr memory current_alpha = state.alpha.copy();
for(uint256 i= 2; i < state.alpha_values.length; i = i.uncheckedInc()){
current_alpha.mul_assign(state.alpha);
state.alpha_values[i] = current_alpha.copy();
}
}
function verify(Proof memory proof, VerificationKey memory vk) internal view returns (bool) {
// we initialize all challenges beforehand, we can draw each challenge in its own place
PartialVerifierState memory state = initialize_transcript(proof, vk);
if(verify_quotient_evaluation(vk, proof, state)== false){
return false;
}
require(proof.state_polys_openings_at_z_omega.length == 1);
PairingsBn254.G1Point memory quotient_result = proof.quotient_poly_parts_commitments[0].copy_g1();
{
// block scope
PairingsBn254.Fr memory z_in_domain_size = state.z.pow(vk.domain_size);
PairingsBn254.Fr memory current_z = z_in_domain_size.copy();
PairingsBn254.G1Point memory tp;
// start from i =1
for(uint256 i = 1; i < proof.quotient_poly_parts_commitments.length; i = i.uncheckedInc()) {
tp = proof.quotient_poly_parts_commitments[i].copy_g1();
tp.point_mul_assign(current_z);
quotient_result.point_add_assign(tp);
current_z.mul_assign(z_in_domain_size);
}
}
Queries memory queries = prepare_queries(vk, proof, state);
queries.commitments_at_z[0] = quotient_result;
queries.values_at_z[0] = proof.quotient_poly_opening_at_z;
queries.commitments_at_z[1] = aggregated_linearization_commitment(vk, proof, state);
queries.values_at_z[1] = proof.linearization_poly_opening_at_z;
require(queries.commitments_at_z.length == queries.values_at_z.length);
PairingsBn254.G1Point memory aggregated_commitment_at_z = queries.commitments_at_z[0];
PairingsBn254.Fr memory aggregated_opening_at_z = queries.values_at_z[0];
PairingsBn254.Fr memory aggregation_challenge = PairingsBn254.new_fr(1);
PairingsBn254.G1Point memory scaled;
for(uint256 i = 1; i < queries.commitments_at_z.length; i = i.uncheckedInc()){
aggregation_challenge.mul_assign(state.v);
scaled = queries.commitments_at_z[i].point_mul(aggregation_challenge);
aggregated_commitment_at_z.point_add_assign(scaled);
state.t = queries.values_at_z[i];
state.t.mul_assign(aggregation_challenge);
aggregated_opening_at_z.add_assign(state.t);
}
aggregation_challenge.mul_assign(state.v);
PairingsBn254.G1Point memory aggregated_commitment_at_z_omega = queries.commitments_at_z_omega[0].point_mul(aggregation_challenge);
PairingsBn254.Fr memory aggregated_opening_at_z_omega = queries.values_at_z_omega[0];
aggregated_opening_at_z_omega.mul_assign(aggregation_challenge);
for(uint256 i = 1; i < queries.commitments_at_z_omega.length; i = i.uncheckedInc()){
aggregation_challenge.mul_assign(state.v);
scaled = queries.commitments_at_z_omega[i].point_mul(aggregation_challenge);
aggregated_commitment_at_z_omega.point_add_assign(scaled);
state.t = queries.values_at_z_omega[i];
state.t.mul_assign(aggregation_challenge);
aggregated_opening_at_z_omega.add_assign(state.t);
}
return final_pairing(
vk.g2_elements,
proof,
state,
aggregated_commitment_at_z,
aggregated_commitment_at_z_omega,
aggregated_opening_at_z,
aggregated_opening_at_z_omega
);
}
function verify_quotient_evaluation(VerificationKey memory vk, Proof memory proof, PartialVerifierState memory state) internal view returns(bool){
uint256[] memory lagrange_poly_numbers = new uint256[](vk.num_inputs);
for (uint256 i = 0; i < lagrange_poly_numbers.length; i = i.uncheckedInc()) {
lagrange_poly_numbers[i] = i;
}
require(vk.num_inputs > 0);
PairingsBn254.Fr memory inputs_term = PairingsBn254.new_fr(0);
for(uint256 i =0; i < vk.num_inputs; i = i.uncheckedInc()) {
state.t = evaluate_lagrange_poly_out_of_domain(i, vk.domain_size, vk.omega, state.z);
state.t.mul_assign(PairingsBn254.new_fr(proof.input_values[i]));
inputs_term.add_assign(state.t);
}
{{#if has_rescue_custom_gate}}
inputs_term.mul_assign(proof.gate_selectors_openings_at_z[0]);
{{/if}}
PairingsBn254.Fr memory result = proof.linearization_poly_opening_at_z.copy();
result.add_assign(inputs_term);
// compute powers of alpha
compute_powers_of_alpha(state);
PairingsBn254.Fr memory factor = state.alpha_values[{{copy_permutation_alpha_idx}}].copy();
factor.mul_assign(proof.copy_permutation_grand_product_opening_at_z_omega);
// - alpha_0 * (a + perm(z) * beta + gamma)*()*(d + gamma) * z(z*omega)
require(proof.copy_permutation_polys_openings_at_z.length == STATE_WIDTH-1);
PairingsBn254.Fr memory t; // TMP;
for(uint256 i = 0; i < proof.copy_permutation_polys_openings_at_z.length; i = i.uncheckedInc()){
t = proof.copy_permutation_polys_openings_at_z[i].copy();
t.mul_assign(state.beta);
t.add_assign(proof.state_polys_openings_at_z[i]);
t.add_assign(state.gamma);
factor.mul_assign(t);
}
t = proof.state_polys_openings_at_z[3].copy();
t.add_assign(state.gamma);
factor.mul_assign(t);
result.sub_assign(factor);
// - L_0(z) * alpha_1
PairingsBn254.Fr memory l_0_at_z = evaluate_l0_at_point(vk.domain_size, state.z);
l_0_at_z.mul_assign(state.alpha_values[{{copy_permutation_alpha_idx}} + 1]);
result.sub_assign(l_0_at_z);
{{#if has_lookup}}
PairingsBn254.Fr memory lookup_quotient_contrib = lookup_quotient_contribution(vk, proof, state);
result.add_assign(lookup_quotient_contrib);
{{/if}}
PairingsBn254.Fr memory lhs = proof.quotient_poly_opening_at_z.copy();
lhs.mul_assign(evaluate_vanishing(vk.domain_size, state.z));
return lhs.value == result.value;
}
{{#if has_lookup}}
function lookup_quotient_contribution(VerificationKey memory vk, Proof memory proof, PartialVerifierState memory state) internal view returns(PairingsBn254.Fr memory result){
PairingsBn254.Fr memory t;
PairingsBn254.Fr memory one = PairingsBn254.new_fr(1);
state.beta_plus_one = state.beta_lookup.copy();
state.beta_plus_one.add_assign(one);
state.beta_gamma = state.beta_plus_one.copy();
state.beta_gamma.mul_assign(state.gamma_lookup);
// (s'*beta + gamma)*(zw')*alpha
t = proof.lookup_s_poly_opening_at_z_omega.copy();
t.mul_assign(state.beta_lookup);
t.add_assign(state.beta_gamma);
t.mul_assign(proof.lookup_grand_product_opening_at_z_omega);
t.mul_assign(state.alpha_values[{{lookup_alpha_idx}}]);
// (z - omega^{n-1}) for this part
PairingsBn254.Fr memory last_omega = vk.omega.pow(vk.domain_size -1);
state.z_minus_last_omega = state.z.copy();
state.z_minus_last_omega.sub_assign(last_omega);
t.mul_assign(state.z_minus_last_omega);
result.add_assign(t);
// - alpha_1 * L_{0}(z)
state.l_0_at_z = evaluate_lagrange_poly_out_of_domain(0, vk.domain_size, vk.omega, state.z);
t = state.l_0_at_z.copy();
t.mul_assign(state.alpha_values[{{lookup_alpha_idx}} + 1]);
result.sub_assign(t);
// - alpha_2 * beta_gamma_powered L_{n-1}(z)
PairingsBn254.Fr memory beta_gamma_powered = state.beta_gamma.pow(vk.domain_size-1);
state.l_n_minus_one_at_z = evaluate_lagrange_poly_out_of_domain(vk.domain_size-1, vk.domain_size, vk.omega, state.z);
t = state.l_n_minus_one_at_z.copy();
t.mul_assign(beta_gamma_powered);
t.mul_assign(state.alpha_values[{{lookup_alpha_idx}} + 2]);
result.sub_assign(t);
}
{{/if}}
function aggregated_linearization_commitment(VerificationKey memory vk, Proof memory proof, PartialVerifierState memory state) internal view returns(PairingsBn254.G1Point memory result){
// qMain*(Q_a * A + Q_b * B + Q_c * C + Q_d * D + Q_m * A*B + Q_const + Q_dNext * D_next)
result = PairingsBn254.new_g1(0, 0);
// Q_a * A
PairingsBn254.G1Point memory scaled = vk.gate_setup_commitments[0].point_mul(proof.state_polys_openings_at_z[0]);
result.point_add_assign(scaled);
// Q_b * B
scaled = vk.gate_setup_commitments[1].point_mul(proof.state_polys_openings_at_z[1]);
result.point_add_assign(scaled);
// Q_c * C
scaled = vk.gate_setup_commitments[2].point_mul(proof.state_polys_openings_at_z[2]);
result.point_add_assign(scaled);
// Q_d * D
scaled = vk.gate_setup_commitments[3].point_mul(proof.state_polys_openings_at_z[3]);
result.point_add_assign(scaled);
// Q_m* A*B or Q_ab*A*B
PairingsBn254.Fr memory t = proof.state_polys_openings_at_z[0].copy();
t.mul_assign(proof.state_polys_openings_at_z[1]);
scaled = vk.gate_setup_commitments[{{MAIN_GATE_AB_COEFF_IDX}}].point_mul(t);
result.point_add_assign(scaled);
{{#if is_selector_optimized_main_gate}}
// Q_AC* A*C
t = proof.state_polys_openings_at_z[0].copy();
t.mul_assign(proof.state_polys_openings_at_z[2]);
scaled = vk.gate_setup_commitments[{{MAIN_GATE_AC_COEFF_IDX}}].point_mul(t);
result.point_add_assign(scaled);
{{/if}}
// Q_const
result.point_add_assign(vk.gate_setup_commitments[{{CONSTANT_TERM_COEFF_INDEX}}]);
// Q_dNext * D_next
scaled = vk.gate_setup_commitments[{{D_NEXT_TERM_COEFF_INDEX}}].point_mul(proof.state_polys_openings_at_z_omega[0]);
result.point_add_assign(scaled);
{{#if has_rescue_custom_gate}}
result.point_mul_assign(proof.gate_selectors_openings_at_z[0]);
PairingsBn254.G1Point memory rescue_custom_gate_linearization_contrib = rescue_custom_gate_linearization_contribution(vk, proof, state);
result.point_add_assign(rescue_custom_gate_linearization_contrib);
{{/if}}
require(vk.non_residues.length == STATE_WIDTH-1);
PairingsBn254.Fr memory one = PairingsBn254.new_fr(1);
PairingsBn254.Fr memory factor = state.alpha_values[{{copy_permutation_alpha_idx}}].copy();
for(uint256 i = 0; i < proof.state_polys_openings_at_z.length; ){
t = state.z.copy();
if(i == 0){
t.mul_assign(one);
}else{
t.mul_assign(vk.non_residues[i-1]);
}
t.mul_assign(state.beta);
t.add_assign(state.gamma);
t.add_assign(proof.state_polys_openings_at_z[i]);
factor.mul_assign(t);
unchecked {
++i;
}
}
scaled = proof.copy_permutation_grand_product_commitment.point_mul(factor);
result.point_add_assign(scaled);
// - (a(z) + beta*perm_a + gamma)*()*()*z(z*omega) * beta * perm_d(X)
factor = state.alpha_values[{{copy_permutation_alpha_idx}}].copy();
factor.mul_assign(state.beta);
factor.mul_assign(proof.copy_permutation_grand_product_opening_at_z_omega);
for(uint256 i = 0; i < STATE_WIDTH-1; i = i.uncheckedInc()){
t = proof.copy_permutation_polys_openings_at_z[i].copy();
t.mul_assign(state.beta);
t.add_assign(state.gamma);
t.add_assign(proof.state_polys_openings_at_z[i]);
factor.mul_assign(t);
}
scaled = vk.permutation_commitments[3].point_mul(factor);
result.point_sub_assign(scaled);
// + L_0(z) * Z(x)
state.l_0_at_z = evaluate_lagrange_poly_out_of_domain(0, vk.domain_size, vk.omega, state.z);
require(state.l_0_at_z.value != 0);
factor = state.l_0_at_z.copy();
factor.mul_assign(state.alpha_values[{{copy_permutation_alpha_idx}} + 1]);
scaled = proof.copy_permutation_grand_product_commitment.point_mul(factor);
result.point_add_assign(scaled);
{{#if has_lookup}}
PairingsBn254.G1Point memory lookup_linearization_contrib = lookup_linearization_contribution(proof, state);
result.point_add_assign(lookup_linearization_contrib);
{{/if}}
}
{{#if has_rescue_custom_gate}}
function rescue_custom_gate_linearization_contribution(VerificationKey memory vk, Proof memory proof, PartialVerifierState memory state) public view returns(PairingsBn254.G1Point memory result){
PairingsBn254.Fr memory t;
PairingsBn254.Fr memory intermediate_result;
// a^2 - b = 0
t = proof.state_polys_openings_at_z[0].copy();
t.mul_assign(t);
t.sub_assign(proof.state_polys_openings_at_z[1]);
// t.mul_assign(challenge1);
t.mul_assign(state.alpha_values[{{rescue_alpha_idx}}]);
intermediate_result.add_assign(t);
// b^2 - c = 0
t = proof.state_polys_openings_at_z[1].copy();
t.mul_assign(t);
t.sub_assign(proof.state_polys_openings_at_z[2]);
t.mul_assign(state.alpha_values[{{rescue_alpha_idx}}+1]);
intermediate_result.add_assign(t);
// c*a - d = 0;
t = proof.state_polys_openings_at_z[2].copy();
t.mul_assign(proof.state_polys_openings_at_z[0]);
t.sub_assign(proof.state_polys_openings_at_z[3]);
t.mul_assign(state.alpha_values[{{rescue_alpha_idx}}+2]);
intermediate_result.add_assign(t);
result = vk.gate_selectors_commitments[1].point_mul(intermediate_result);
}
{{/if}}
{{#if has_lookup}}
function lookup_linearization_contribution(Proof memory proof, PartialVerifierState memory state) internal view returns(PairingsBn254.G1Point memory result) {
PairingsBn254.Fr memory zero = PairingsBn254.new_fr(0);
PairingsBn254.Fr memory t;
PairingsBn254.Fr memory factor;
// s(x) from the Z(x*omega)*(\gamma*(1 + \beta) + s(x) + \beta * s(x*omega)))
factor = proof.lookup_grand_product_opening_at_z_omega.copy();
factor.mul_assign(state.alpha_values[{{lookup_alpha_idx}}]);
factor.mul_assign(state.z_minus_last_omega);
PairingsBn254.G1Point memory scaled = proof.lookup_s_poly_commitment.point_mul(factor);
result.point_add_assign(scaled);
// Z(x) from - alpha_0 * Z(x) * (\beta + 1) * (\gamma + f(x)) * (\gamma(1 + \beta) + t(x) + \beta * t(x*omega))
// + alpha_1 * Z(x) * L_{0}(z) + alpha_2 * Z(x) * L_{n-1}(z)
// accumulate coefficient
factor = proof.lookup_t_poly_opening_at_z_omega.copy();
factor.mul_assign(state.beta_lookup);
factor.add_assign(proof.lookup_t_poly_opening_at_z);
factor.add_assign(state.beta_gamma);
// (\gamma + f(x))
PairingsBn254.Fr memory f_reconstructed;
PairingsBn254.Fr memory current = PairingsBn254.new_fr(1);
PairingsBn254.Fr memory tmp0;
for(uint256 i=0; i< STATE_WIDTH-1; i = i.uncheckedInc()){
tmp0 = proof.state_polys_openings_at_z[i].copy();
tmp0.mul_assign(current);
f_reconstructed.add_assign(tmp0);
current.mul_assign(state.eta);
}
// add type of table
t = proof.lookup_table_type_poly_opening_at_z.copy();
t.mul_assign(current);
f_reconstructed.add_assign(t);
f_reconstructed.mul_assign(proof.lookup_selector_poly_opening_at_z);
f_reconstructed.add_assign(state.gamma_lookup);
// end of (\gamma + f(x)) part
factor.mul_assign(f_reconstructed);
factor.mul_assign(state.beta_plus_one);
t = zero.copy();
t.sub_assign(factor);
factor = t;
factor.mul_assign(state.alpha_values[{{lookup_alpha_idx}}]);
// Multiply by (z - omega^{n-1})
factor.mul_assign(state.z_minus_last_omega);
// L_{0}(z) in front of Z(x)
t = state.l_0_at_z.copy();
t.mul_assign(state.alpha_values[{{lookup_alpha_idx}} + 1]);
factor.add_assign(t);
// L_{n-1}(z) in front of Z(x)
t = state.l_n_minus_one_at_z.copy();
t.mul_assign(state.alpha_values[{{lookup_alpha_idx}} + 2]);
factor.add_assign(t);
scaled = proof.lookup_grand_product_commitment.point_mul(factor);
result.point_add_assign(scaled);
}
{{/if}}
struct Queries {
PairingsBn254.G1Point[{{num_commitments_at_z}}] commitments_at_z;
PairingsBn254.Fr[{{num_commitments_at_z}}] values_at_z;
PairingsBn254.G1Point[{{num_commitments_at_z_omega}}] commitments_at_z_omega;
PairingsBn254.Fr[{{num_commitments_at_z_omega}}] values_at_z_omega;
}
function prepare_queries(
VerificationKey memory vk,
Proof memory proof,
PartialVerifierState memory state
) public view returns(Queries memory queries){
// we set first two items in calee side so start idx from 2
uint256 idx = 2;
for(uint256 i = 0; i<STATE_WIDTH; i = i.uncheckedInc()){
queries.commitments_at_z[idx] = proof.state_polys_commitments[i];
queries.values_at_z[idx] = proof.state_polys_openings_at_z[i];
idx = idx.uncheckedInc();
}
{{#if has_rescue_custom_gate}}
require(proof.gate_selectors_openings_at_z.length == 1);
queries.commitments_at_z[idx] = vk.gate_selectors_commitments[0];
queries.values_at_z[idx] = proof.gate_selectors_openings_at_z[0];
idx = idx.uncheckedInc();
{{/if}}
for(uint256 i = 0; i<STATE_WIDTH-1; i = i.uncheckedInc()){
queries.commitments_at_z[idx] = vk.permutation_commitments[i];
queries.values_at_z[idx] = proof.copy_permutation_polys_openings_at_z[i];
idx = idx.uncheckedInc();
}
queries.commitments_at_z_omega[0] = proof.copy_permutation_grand_product_commitment;
queries.commitments_at_z_omega[1] = proof.state_polys_commitments[STATE_WIDTH-1];
queries.values_at_z_omega[0] = proof.copy_permutation_grand_product_opening_at_z_omega;
queries.values_at_z_omega[1] = proof.state_polys_openings_at_z_omega[0];
{{#if has_lookup}}
PairingsBn254.G1Point memory lookup_t_poly_commitment_aggregated = vk.lookup_tables_commitments[0];
PairingsBn254.Fr memory current_eta = state.eta.copy();
for(uint256 i = 1; i < vk.lookup_tables_commitments.length; i = i.uncheckedInc()){
state.tp = vk.lookup_tables_commitments[i].point_mul(current_eta);
lookup_t_poly_commitment_aggregated.point_add_assign(state.tp);
current_eta.mul_assign(state.eta);
}
queries.commitments_at_z[idx] = lookup_t_poly_commitment_aggregated;
queries.values_at_z[idx] = proof.lookup_t_poly_opening_at_z;
idx = idx.uncheckedInc();
queries.commitments_at_z[idx] = vk.lookup_selector_commitment;
queries.values_at_z[idx] = proof.lookup_selector_poly_opening_at_z;
idx = idx.uncheckedInc();
queries.commitments_at_z[idx] = vk.lookup_table_type_commitment;
queries.values_at_z[idx] = proof.lookup_table_type_poly_opening_at_z;
queries.commitments_at_z_omega[2] = proof.lookup_s_poly_commitment;
queries.values_at_z_omega[2] = proof.lookup_s_poly_opening_at_z_omega;
queries.commitments_at_z_omega[3] = proof.lookup_grand_product_commitment;
queries.values_at_z_omega[3] = proof.lookup_grand_product_opening_at_z_omega;
queries.commitments_at_z_omega[4] = lookup_t_poly_commitment_aggregated;
queries.values_at_z_omega[4] = proof.lookup_t_poly_opening_at_z_omega;
{{/if}}
}
function final_pairing(
// VerificationKey memory vk,
PairingsBn254.G2Point[NUM_G2_ELS] memory g2_elements,
Proof memory proof,
PartialVerifierState memory state,
PairingsBn254.G1Point memory aggregated_commitment_at_z,
PairingsBn254.G1Point memory aggregated_commitment_at_z_omega,
PairingsBn254.Fr memory aggregated_opening_at_z,
PairingsBn254.Fr memory aggregated_opening_at_z_omega
) internal view returns(bool){
// q(x) = f(x) - f(z) / (x - z)
// q(x) * (x-z) = f(x) - f(z)
// f(x)
PairingsBn254.G1Point memory pair_with_generator = aggregated_commitment_at_z.copy_g1();
aggregated_commitment_at_z_omega.point_mul_assign(state.u);
pair_with_generator.point_add_assign(aggregated_commitment_at_z_omega);
// - f(z)*g
PairingsBn254.Fr memory aggregated_value = aggregated_opening_at_z_omega.copy();
aggregated_value.mul_assign(state.u);
aggregated_value.add_assign(aggregated_opening_at_z);
PairingsBn254.G1Point memory tp = PairingsBn254.P1().point_mul(aggregated_value);
pair_with_generator.point_sub_assign(tp);
// +z * q(x)
tp = proof.opening_proof_at_z.point_mul(state.z);
PairingsBn254.Fr memory t = state.z_omega.copy();
t.mul_assign(state.u);
PairingsBn254.G1Point memory t1 = proof.opening_proof_at_z_omega.point_mul(t);
tp.point_add_assign(t1);
pair_with_generator.point_add_assign(tp);
// rhs
PairingsBn254.G1Point memory pair_with_x = proof.opening_proof_at_z_omega.point_mul(state.u);
pair_with_x.point_add_assign(proof.opening_proof_at_z);
pair_with_x.negate();
// Pairing precompile expects points to be in a `i*x[1] + x[0]` form instead of `x[0] + i*x[1]`
// so we handle it in code generation step
PairingsBn254.G2Point memory first_g2 = g2_elements[0];
PairingsBn254.G2Point memory second_g2 = g2_elements[1];
return PairingsBn254.pairingProd2(pair_with_generator, first_g2, pair_with_x, second_g2);
}
}