ecc_set_relation_impl.hpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: Complete, auditors: [Raju], commit: 2a49eb6 }
// external_1:  { status: not started, auditors: [], commit: }
// external_2:  { status: not started, auditors: [], commit: }
// =====================
 
#pragma once
#include "barretenberg/ecc/curves/grumpkin/grumpkin.hpp"
#include "ecc_set_relation.hpp"
#include <type_traits>
 
namespace bb {
 
template <typename FF>
template <typename Accumulator, typename AllEntities, typename Parameters>
Accumulator ECCVMSetRelationImpl<FF>::compute_grand_product_numerator(const AllEntities& in, const Parameters& params)
{
    using View = typename Accumulator::View;
 
    const auto& precompute_round = View(in.precompute_round);
    const auto precompute_round2 = precompute_round + precompute_round;
    const auto precompute_round4 = precompute_round2 + precompute_round2;
 
    const auto& gamma = params.gamma;
    const auto& beta = params.beta;
    const auto& beta_sqr = params.beta_sqr;
    const auto& beta_cube = params.beta_cube;
    const auto& precompute_pc = View(in.precompute_pc);
    const auto& precompute_select = View(in.precompute_select);
 
    // OPTIMIZE(@zac-williamson #2226) optimize degrees
 
    Accumulator numerator(1); // degree-0
    {
        const auto& s0 = View(in.precompute_s1hi);
        const auto& s1 = View(in.precompute_s1lo);
 
        auto wnaf_slice = s0 + s0;
        wnaf_slice += wnaf_slice;
        wnaf_slice += s1;
 
        const auto wnaf_slice_input0 = wnaf_slice + gamma + precompute_pc * beta + precompute_round4 * beta_sqr;
        numerator *= wnaf_slice_input0; // degree-1
    }
    {
        const auto& s0 = View(in.precompute_s2hi);
        const auto& s1 = View(in.precompute_s2lo);
 
        auto wnaf_slice = s0 + s0;
        wnaf_slice += wnaf_slice;
        wnaf_slice += s1;
 
        const auto wnaf_slice_input1 = wnaf_slice + gamma + precompute_pc * beta + (precompute_round4 + 1) * beta_sqr;
        numerator *= wnaf_slice_input1; // degree-2
    }
    {
        const auto& s0 = View(in.precompute_s3hi);
        const auto& s1 = View(in.precompute_s3lo);
 
        auto wnaf_slice = s0 + s0;
        wnaf_slice += wnaf_slice;
        wnaf_slice += s1;
 
        const auto wnaf_slice_input2 = wnaf_slice + gamma + precompute_pc * beta + (precompute_round4 + 2) * beta_sqr;
        numerator *= wnaf_slice_input2; // degree-3
    }
    {
        const auto& s0 = View(in.precompute_s4hi);
        const auto& s1 = View(in.precompute_s4lo);
 
        auto wnaf_slice = s0 + s0;
        wnaf_slice += wnaf_slice;
        wnaf_slice += s1;
        const auto wnaf_slice_input3 = wnaf_slice + gamma + precompute_pc * beta + (precompute_round4 + 3) * beta_sqr;
        numerator *= wnaf_slice_input3; // degree-4
    }
    {
        // skew product if relevant
        const auto& skew = View(in.precompute_skew);
        const auto& precompute_point_transition = View(in.precompute_point_transition);
        const auto skew_input =
            precompute_point_transition * (skew + gamma + precompute_pc * beta + (precompute_round4 + 4) * beta_sqr) +
            (-precompute_point_transition + 1);
        numerator *= skew_input; // degree-5
    }
    {
        // in `EccvmProver` and `ECCVMVerifier`, we see that `eccvm_set_permutation_delta` is initially computed as
        // (γ)·(γ + β²)·(γ + 2β²)·(γ + 3β²) and _then_ inverted. Therefore, `eccvm_set_permutation_delta` == 1 / (γ)·(γ
        // + β²)·(γ + 2β²)·(γ
        // + 3β²)
        const auto& eccvm_set_permutation_delta = params.eccvm_set_permutation_delta;
        // if `precompute_select == 1`, don't change the numerator. if it is 0, then to get the grand product argument
        // to work (as we have zero-padded the rows of the MSM table), we must multiply by the inverse of the
        // fingerprint of (0, 0, 0).
        numerator *= precompute_select * (-eccvm_set_permutation_delta + 1) + eccvm_set_permutation_delta; // degree-7
    }
 
    {
        const auto& table_x = View(in.precompute_tx);
        const auto& table_y = View(in.precompute_ty);
 
        const auto& precompute_skew = View(in.precompute_skew);
        const auto negative_inverse_seven = []() {
            if constexpr (std::same_as<FF, grumpkin::fr>) {
                static constexpr FF negative_inverse_seven = FF(-7).invert();
                return negative_inverse_seven;
            } else {
                FF negative_inverse_seven = FF(-7).invert();
                return negative_inverse_seven;
            }
        };
        auto adjusted_skew =
            precompute_skew * negative_inverse_seven(); // `precompute_skew` ∈ {0, 7}, `adjusted_skew`∈ {0, -1}
 
        const auto& wnaf_scalar_sum = View(in.precompute_scalar_sum);
        const auto w0 = convert_to_wnaf<Accumulator>(View(in.precompute_s1hi), View(in.precompute_s1lo));
        const auto w1 = convert_to_wnaf<Accumulator>(View(in.precompute_s2hi), View(in.precompute_s2lo));
        const auto w2 = convert_to_wnaf<Accumulator>(View(in.precompute_s3hi), View(in.precompute_s3lo));
        const auto w3 = convert_to_wnaf<Accumulator>(View(in.precompute_s4hi), View(in.precompute_s4lo));
 
        auto row_slice = w0;
        row_slice += row_slice;
        row_slice += row_slice;
        row_slice += row_slice;
        row_slice += row_slice;
        row_slice += w1;
        row_slice += row_slice;
        row_slice += row_slice;
        row_slice += row_slice;
        row_slice += row_slice;
        row_slice += w2;
        row_slice += row_slice;
        row_slice += row_slice;
        row_slice += row_slice;
        row_slice += row_slice;
        row_slice += w3; // row_slice = 2^12 w_0 + 2^8 w_1 + 2^4 w_2 + 2^0 w_3
 
        auto scalar_sum_full = wnaf_scalar_sum + wnaf_scalar_sum;
        scalar_sum_full += scalar_sum_full;
        scalar_sum_full += scalar_sum_full;
        scalar_sum_full += scalar_sum_full;
        scalar_sum_full += scalar_sum_full;
        scalar_sum_full += scalar_sum_full;
        scalar_sum_full += scalar_sum_full;
        scalar_sum_full += scalar_sum_full;
        scalar_sum_full += scalar_sum_full;
        scalar_sum_full += scalar_sum_full;
        scalar_sum_full += scalar_sum_full;
        scalar_sum_full += scalar_sum_full;
        scalar_sum_full += scalar_sum_full;
        scalar_sum_full += scalar_sum_full;
        scalar_sum_full += scalar_sum_full;
        scalar_sum_full += scalar_sum_full;
        scalar_sum_full +=
            row_slice + adjusted_skew; // scalar_sum_full = 2^16 * wnaf_scalar_sum + row_slice + adjusted_skew
 
        auto precompute_point_transition = View(in.precompute_point_transition);
 
        auto point_table_init_read =
            (precompute_pc + table_x * beta + table_y * beta_sqr + scalar_sum_full * beta_cube);
        point_table_init_read =
            precompute_point_transition * (point_table_init_read + gamma) + (-precompute_point_transition + 1);
 
        numerator *= point_table_init_read; // degree-9
    }
    {
        const auto& lagrange_first = View(in.lagrange_first);
        const auto& partial_msm_transition_shift = View(in.msm_transition_shift);
        const auto msm_transition_shift = (-lagrange_first + 1) * partial_msm_transition_shift;
        const auto& msm_pc_shift = View(in.msm_pc_shift);
 
        const auto& msm_x_shift = View(in.msm_accumulator_x_shift);
        const auto& msm_y_shift = View(in.msm_accumulator_y_shift);
        const auto& msm_size = View(in.msm_size_of_msm);
 
        // msm_transition = 1 when a row BEGINS a new msm
        //
        // row msm tx  acc.x acc.y pc  msm_size
        // i   0       no    no    no  yes
        // i+1 1       yes   yes   yes no
        //
        // at row i we are at the final row of the current msm
        // at row i the value of `msm_size` = size of current msm
        // at row i + 1 we have the final accumulated value of the msm computation
        // at row i + 1 we have updated `pc` to be `(pc at start of msm) + msm_count`
        // at row i + 1 q_msm_transtiion = 1
 
        auto msm_result_write = msm_pc_shift + msm_x_shift * beta + msm_y_shift * beta_sqr + msm_size * beta_cube;
 
        // msm_result_write = degree 2
        msm_result_write = msm_transition_shift * (msm_result_write + gamma) + (-msm_transition_shift + 1);
        numerator *= msm_result_write; // degree-11
    }
    return numerator;
}
 
template <typename FF>
template <typename Accumulator, typename AllEntities, typename Parameters>
Accumulator ECCVMSetRelationImpl<FF>::compute_grand_product_denominator(const AllEntities& in, const Parameters& params)
{
    using View = typename Accumulator::View;
 
    // OPTIMIZE(@zac-williamson). The degree of this contribution is 17! makes overall relation degree 19.
    // Can potentially optimize by refining the algebra.
    const auto& gamma = params.gamma;
    const auto& beta = params.beta;
    const auto& beta_sqr = params.beta_sqr;
    const auto& beta_cube = params.beta_cube;
    const auto& msm_pc = View(in.msm_pc);
    const auto& msm_count = View(in.msm_count);
    const auto& msm_round = View(in.msm_round);
 
    Accumulator denominator(1); // degree-0
    {
        const auto& add1 = View(in.msm_add1);
        const auto& msm_slice1 = View(in.msm_slice1);
 
        auto wnaf_slice_output1 =
            add1 * (msm_slice1 + gamma + (msm_pc - msm_count) * beta + msm_round * beta_sqr) + (-add1 + 1);
        denominator *= wnaf_slice_output1; // degree-2
    }
    {
        const auto& add2 = View(in.msm_add2);
        const auto& msm_slice2 = View(in.msm_slice2);
 
        auto wnaf_slice_output2 =
            add2 * (msm_slice2 + gamma + (msm_pc - msm_count - 1) * beta + msm_round * beta_sqr) + (-add2 + 1);
        denominator *= wnaf_slice_output2; // degree-4
    }
    {
        const auto& add3 = View(in.msm_add3);
        const auto& msm_slice3 = View(in.msm_slice3);
 
        auto wnaf_slice_output3 =
            add3 * (msm_slice3 + gamma + (msm_pc - msm_count - 2) * beta + msm_round * beta_sqr) + (-add3 + 1);
        denominator *= wnaf_slice_output3; // degree-6
    }
    {
        const auto& add4 = View(in.msm_add4);
        const auto& msm_slice4 = View(in.msm_slice4);
        auto wnaf_slice_output4 =
            add4 * (msm_slice4 + gamma + (msm_pc - msm_count - 3) * beta + msm_round * beta_sqr) + (-add4 + 1);
        denominator *= wnaf_slice_output4; // degree-8
    }
 
    {
        const auto& transcript_pc = View(in.transcript_pc);
 
        const auto& transcript_Px = View(in.transcript_Px);
        const auto& transcript_Py = View(in.transcript_Py);
        const auto& z1 = View(in.transcript_z1);
        const auto& z2 = View(in.transcript_z2);
        const auto& z1_zero = View(in.transcript_z1zero);
        const auto& z2_zero = View(in.transcript_z2zero);
        const auto& base_infinity = View(in.transcript_base_infinity);
        const auto& transcript_mul = View(in.transcript_mul);
 
        const auto& lookup_first = (-z1_zero + 1);
        const auto& lookup_second = (-z2_zero + 1);
        FF cube_root_unity = FF(bb::fq::cube_root_of_unity());
 
        auto transcript_input1 =
            transcript_pc + transcript_Px * beta + transcript_Py * beta_sqr + z1 * beta_cube; // degree = 1
        auto transcript_input2 = (transcript_pc - 1) + transcript_Px * cube_root_unity * beta -
                                 transcript_Py * beta_sqr + z2 * beta_cube; // degree = 2
 
        // The following diagram expresses a fingerprint of part of the tuple. It does not include `transcript_pc` and
        // has not weighted the X and Y with beta and beta_sqr respectively. The point is nonetheless to show exactly
        // when a tuple is added to the multiset: iff it corresponds to a non-trivial (128-bit) scalar mul. If neither
        // z1 nor z2 are zero, then we implicitly add _two_ tuples to the multiset.
        //
        // | q_mul | z2_zero | z1_zero | base_infinity | partial lookup              |
        // | ----- | ------- | ------- | ------------- |-----------------------      |
        // | 0     | -       | -       |             - | 1                           |
        // | 1     | 0       | 0       |             0 | 1                           |
        // | 1     | 0       | 1       |             0 | X + gamma                   |
        // | 1     | 1       | 0       |             0 | Y + gamma                   |
        // | 1     | 1       | 1       |             0 | (X + gamma)(Y + gamma)      |
        // | 1     | 0       | 0       |             1 | 1                           |
        // | 1     | 0       | 1       |             1 | 1                           |
        // | 1     | 1       | 0       |             1 | 1                           |
        // | 1     | 1       | 1       |             1 | 1                           |
        transcript_input1 = (transcript_input1 + gamma) * lookup_first + (-lookup_first + 1);   // degree 2
        transcript_input2 = (transcript_input2 + gamma) * lookup_second + (-lookup_second + 1); // degree 3
 
        // transcript_product = degree 6
        auto transcript_product = (transcript_input1 * transcript_input2) * (-base_infinity + 1) + base_infinity;
 
        // point_table_init_write = degree 7
        auto point_table_init_write = transcript_mul * transcript_product + (-transcript_mul + 1);
        denominator *= point_table_init_write; // degree 17
    }
    {
        const auto& transcript_pc_shift = View(in.transcript_pc_shift);
        const auto& transcript_msm_x = View(in.transcript_msm_x);
        const auto& transcript_msm_y = View(in.transcript_msm_y);
        const auto& transcript_msm_transition = View(in.transcript_msm_transition);
        const auto& transcript_msm_count = View(in.transcript_msm_count);
        const auto& z1_zero = View(in.transcript_z1zero);
        const auto& z2_zero = View(in.transcript_z2zero);
        const auto& transcript_mul = View(in.transcript_mul);
        const auto& base_infinity = View(in.transcript_base_infinity);
 
        // do not add to count if point at infinity!
        auto full_msm_count =
            transcript_msm_count + transcript_mul * ((-z1_zero + 1) + (-z2_zero + 1)) * (-base_infinity + 1);
        // msm_result_read = degree 2
        auto msm_result_read =
            transcript_pc_shift + transcript_msm_x * beta + transcript_msm_y * beta_sqr + full_msm_count * beta_cube;
        msm_result_read = transcript_msm_transition * (msm_result_read + gamma) + (-transcript_msm_transition + 1);
        denominator *= msm_result_read; // degree-20
    }
    return denominator;
}
 
template <typename FF>
template <typename ContainerOverSubrelations, typename AllEntities, typename Parameters>
void ECCVMSetRelationImpl<FF>::accumulate(ContainerOverSubrelations& accumulator,
                                          const AllEntities& in,
                                          const Parameters& params,
                                          const FF& scaling_factor)
{
    using Accumulator = typename std::tuple_element_t<0, ContainerOverSubrelations>;
    using View = typename Accumulator::View;
    using ShortView = typename std::tuple_element_t<1, ContainerOverSubrelations>::View;
 
    // degree-11
    Accumulator numerator_evaluation = compute_grand_product_numerator<Accumulator>(in, params);
 
    // degree-20
    Accumulator denominator_evaluation = compute_grand_product_denominator<Accumulator>(in, params);
 
    const auto& lagrange_first = View(in.lagrange_first);
    const auto& lagrange_last = View(in.lagrange_last);
    const auto& lagrange_last_short = ShortView(in.lagrange_last);
 
    const auto& z_perm = View(in.z_perm);
    const auto& z_perm_shift = View(in.z_perm_shift);
    const auto& z_perm_shift_short = ShortView(in.z_perm_shift);
 
    // degree-21
    std::get<0>(accumulator) +=
        ((z_perm + lagrange_first) * numerator_evaluation - (z_perm_shift + lagrange_last) * denominator_evaluation) *
        scaling_factor;
 
    // Contribution (2)
    std::get<1>(accumulator) += lagrange_last_short * z_perm_shift_short * scaling_factor;
}
} // namespace bb