eccvm_flavor.hpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: not started, auditors: [], date: YYYY-MM-DD }
// external_1:  { status: not started, auditors: [], date: YYYY-MM-DD }
// external_2:  { status: not started, auditors: [], date: YYYY-MM-DD }
// =====================
 
#pragma once
#include "barretenberg/commitment_schemes/ipa/ipa.hpp"
#include "barretenberg/common/assert.hpp"
#include "barretenberg/common/bb_bench.hpp"
#include "barretenberg/common/std_array.hpp"
#include "barretenberg/ecc/curves/bn254/bn254.hpp"
#include "barretenberg/ecc/curves/grumpkin/grumpkin.hpp"
#include "barretenberg/eccvm//eccvm_fixed_vk.hpp"
#include "barretenberg/eccvm/eccvm_circuit_builder.hpp"
#include "barretenberg/flavor/flavor.hpp"
#include "barretenberg/flavor/flavor_macros.hpp"
#include "barretenberg/flavor/relation_definitions.hpp"
#include "barretenberg/flavor/repeated_commitments_data.hpp"
#include "barretenberg/polynomials/polynomial.hpp"
#include "barretenberg/polynomials/univariate.hpp"
#include "barretenberg/relations/ecc_vm/ecc_bools_relation.hpp"
#include "barretenberg/relations/ecc_vm/ecc_lookup_relation.hpp"
#include "barretenberg/relations/ecc_vm/ecc_msm_relation.hpp"
#include "barretenberg/relations/ecc_vm/ecc_point_table_relation.hpp"
#include "barretenberg/relations/ecc_vm/ecc_set_relation.hpp"
#include "barretenberg/relations/ecc_vm/ecc_transcript_relation.hpp"
#include "barretenberg/relations/ecc_vm/ecc_wnaf_relation.hpp"
#include "barretenberg/relations/relation_parameters.hpp"
 
// NOLINTBEGIN(cppcoreguidelines-avoid-const-or-ref-data-members)
 
namespace bb {
 
class ECCVMFlavor {
  public:
    using CircuitBuilder = ECCVMCircuitBuilder;
    using CycleGroup = bb::g1;
    using Curve = curve::Grumpkin;
    using G1 = typename Curve::Group;
    using PCS = IPA<Curve>;
    using FF = typename Curve::ScalarField;
    using BF = typename Curve::BaseField;
    using Polynomial = bb::Polynomial<FF>;
    using GroupElement = typename G1::element;
    using Commitment = typename G1::affine_element;
    using CommitmentKey = bb::CommitmentKey<Curve>;
    using VerifierCommitmentKey = bb::VerifierCommitmentKey<Curve>;
    using MSM = bb::eccvm::MSM<CycleGroup>;
    using Transcript = NativeTranscript;
    using Proof = HonkProof;
 
    // indicates when evaluating sumcheck, edges must be extended to be MAX_PARTIAL_RELATION_LENGTH
    static constexpr bool USE_SHORT_MONOMIALS = false;
 
    // Indicates that this flavor runs with ZK Sumcheck.
    static constexpr bool HasZK = true;
    // ECCVM proof size and its recursive verifier circuit are genuinely fixed, hence no padding is needed.
    static constexpr bool USE_PADDING = false;
    // Fixed size of the ECCVM circuits used in Chonk
    // Important: these constants cannot be  arbitrarily changes - please consult with a member of the Crypto team if
    // they become too small.
    static constexpr size_t ECCVM_FIXED_SIZE = 1UL << CONST_ECCVM_LOG_N;
 
    static constexpr size_t NUM_WIRES = 85;
 
    // The number of entities added for ZK (gemini_masking_poly)
    static constexpr size_t NUM_MASKING_POLYNOMIALS = 1;
 
    // The number of multivariate polynomials on which a sumcheck prover sumcheck operates (including shifts). We often
    // need containers of this size to hold related data, so we choose a name more agnostic than `NUM_POLYNOMIALS`.
    // Note: this number does not include the individual sorted list polynomials.
    // Includes gemini_masking_poly for ZK (NUM_ALL_ENTITIES = 117 + NUM_MASKING_POLYNOMIALS)
    static constexpr size_t NUM_ALL_ENTITIES = 118;
    // The number of polynomials precomputed to describe a circuit and to aid a prover in constructing a satisfying
    // assignment of witnesses. We again choose a neutral name.
    static constexpr size_t NUM_PRECOMPUTED_ENTITIES = 4;
    // The total number of witness entities not including shifts.
    // Includes gemini_masking_poly for ZK (NUM_WITNESS_ENTITIES = 86 + NUM_MASKING_POLYNOMIALS)
    static constexpr size_t NUM_WITNESS_ENTITIES = 87;
    // The number of entities in ShiftedEntities.
    static constexpr size_t NUM_SHIFTED_ENTITIES = 26;
    // The number of entities in DerivedWitnessEntities that are not going to be shifted.
    static constexpr size_t NUM_DERIVED_WITNESS_ENTITIES_NON_SHIFTED = 1;
    // A container to be fed to ShpleminiVerifier to avoid redundant scalar muls, the first number is the index of the
    // first witness to be shifted.
    static constexpr RepeatedCommitmentsData REPEATED_COMMITMENTS =
        RepeatedCommitmentsData(NUM_PRECOMPUTED_ENTITIES + NUM_WITNESS_ENTITIES -
                                    NUM_DERIVED_WITNESS_ENTITIES_NON_SHIFTED - NUM_SHIFTED_ENTITIES,
                                NUM_PRECOMPUTED_ENTITIES + NUM_WITNESS_ENTITIES,
                                NUM_SHIFTED_ENTITIES);
 
    using GrandProductRelations = std::tuple<ECCVMSetRelation<FF>>;
    // define the tuple of Relations that comprise the Sumcheck relation
    template <typename FF>
    using Relations_ = std::tuple<ECCVMTranscriptRelation<FF>,
                                  ECCVMPointTableRelation<FF>,
                                  ECCVMWnafRelation<FF>,
                                  ECCVMMSMRelation<FF>,
                                  ECCVMSetRelation<FF>,
                                  ECCVMLookupRelation<FF>,
                                  ECCVMBoolsRelation<FF>>;
    using Relations = Relations_<FF>;
    using LookupRelation = ECCVMLookupRelation<FF>;
 
    static constexpr size_t NUM_SUBRELATIONS = compute_number_of_subrelations<Relations>();
    using SubrelationSeparators = std::array<FF, NUM_SUBRELATIONS - 1>;
 
    static constexpr size_t MAX_PARTIAL_RELATION_LENGTH = compute_max_partial_relation_length<Relations>();
 
    // BATCHED_RELATION_PARTIAL_LENGTH = algebraic degree of sumcheck relation *after* multiplying by the `pow_zeta`
    // random polynomial e.g. For \sum(x) [A(x) * B(x) + C(x)] * PowZeta(X), relation length = 2 and random relation
    // length = 3.
    // The degree has to be further increased by 1 because the relation is multiplied by the Row Disabling    //
    // Polynomial
    static constexpr size_t BATCHED_RELATION_PARTIAL_LENGTH = MAX_PARTIAL_RELATION_LENGTH + 2;
    static constexpr size_t NUM_RELATIONS = std::tuple_size<Relations>::value;
 
    static constexpr size_t num_frs_comm = FrCodec::calc_num_fields<Commitment>();
    static constexpr size_t num_frs_fq = FrCodec::calc_num_fields<FF>();
 
    // Proof length formula
    static constexpr size_t PROOF_LENGTH_WITHOUT_PUB_INPUTS =
        /* 1. NUM_WITNESS_ENTITIES commitments */ ((NUM_WITNESS_ENTITIES + NUM_MASKING_POLYNOMIALS) * num_frs_comm) +
        /* 2. Libra concatenation commitment*/ (num_frs_comm) +
        /* 3. Libra sum */ (num_frs_fq) +
        /* 4. CONST_ECCVM_LOG_N sumcheck univariates commitments */
        (CONST_ECCVM_LOG_N * num_frs_comm) +
        /* 5. 2 * CONST_ECCVM_LOG_N sumcheck univariate evaluations */
        (2 * CONST_ECCVM_LOG_N * num_frs_fq) +
        /* 6. NUM_ALL_ENTITIES sumcheck evaluations*/ (NUM_ALL_ENTITIES * num_frs_fq) +
        /* 7. Libra claimed evaluation */ (num_frs_fq) +
        /* 8. Libra grand sum commitment */ (num_frs_comm) +
        /* 9. Libra quotient commitment */ (num_frs_comm) +
        /* 10. CONST_ECCVM_LOG_N - 1 Gemini Fold commitments */
        ((CONST_ECCVM_LOG_N - 1) * num_frs_comm) +
        /* 11. CONST_ECCVM_LOG_N Gemini a evaluations */
        (CONST_ECCVM_LOG_N * num_frs_fq) +
        /* 12. NUM_SMALL_IPA_EVALUATIONS libra evals */ (NUM_SMALL_IPA_EVALUATIONS * num_frs_fq) +
        /* 13. Shplonk Q commitment */ (num_frs_comm) +
        /* 14. Translator concatenated masking term commitment */ (num_frs_comm) +
        /* 15 Translator op evaluation */ (num_frs_fq) +
        /* 16 Translator Px evaluation */ (num_frs_fq) +
        /* 17 Translator Py evaluation */ (num_frs_fq) +
        /* 18 Translator z1 evaluation */ (num_frs_fq) +
        /* 19 Translator z2 evaluation */ (num_frs_fq) +
        /* 20 Translator concatenated masking term evaluation */ (num_frs_fq) +
        /* 21 Translator grand sum commitment */ (num_frs_comm) +
        /* 22 Translator quotient commitment */ (num_frs_comm) +
        /* 23 Translator concatenation eval */ (num_frs_fq) +
        /* 24 Translator grand sum shift eval */ (num_frs_fq) +
        /* 25 Translator grand sum eval */ (num_frs_fq) +
        /* 26 Translator quotient eval */ (num_frs_fq) +
        /* 27 Shplonk Q commitment */ (num_frs_comm);
 
    // The sub-protocol `compute_translation_opening_claims` outputs an opening claim for the batched univariate
    // evaluation of `op`, `Px`, `Py`, `z1`, and `z2`, and an array of opening claims for the evaluations of the
    // SmallSubgroupIPA witness polynomials.
    static constexpr size_t NUM_TRANSLATION_OPENING_CLAIMS = NUM_SMALL_IPA_EVALUATIONS + 1;
 
    // TODO(https://github.com/AztecProtocol/barretenberg/issues/989): refine access specifiers in flavors, this is
    // public as it is also used in the recursive flavor but the two could possibly me unified eventually
    template <typename DataType_> class PrecomputedEntities {
      public:
        bool operator==(const PrecomputedEntities& other) const = default;
        using DataType = DataType_;
        DEFINE_FLAVOR_MEMBERS(DataType,
                              lagrange_first,  // column 0
                              lagrange_second, // column 1 - hiding op row
                              lagrange_third,  // column 2 - first real op row
                              lagrange_last);  // column 3
 
        DataType get_selectors() { return get_all(); };
    };
 
    template <typename DataType> struct DerivedWitnessEntities {
        DEFINE_FLAVOR_MEMBERS(DataType,
                              z_perm,           // column 0
                              lookup_inverses); // column 1
    };
    template <typename DataType> class WireNonShiftedEntities {
      public:
        DEFINE_FLAVOR_MEMBERS(DataType,
                              transcript_add,                             // column 0
                              transcript_eq,                              // column 1
                              transcript_msm_transition,                  // column 2
                              transcript_Px,                              // column 3
                              transcript_Py,                              // column 4
                              transcript_z1,                              // column 5
                              transcript_z2,                              // column 6
                              transcript_z1zero,                          // column 7
                              transcript_z2zero,                          // column 8
                              transcript_op,                              // column 9
                              transcript_msm_x,                           // column 10
                              transcript_msm_y,                           // column 11
                              precompute_point_transition,                // column 12
                              precompute_s1lo,                            // column 13
                              precompute_s2hi,                            // column 14
                              precompute_s2lo,                            // column 15
                              precompute_s3hi,                            // column 16
                              precompute_s3lo,                            // column 17
                              precompute_s4hi,                            // column 18
                              precompute_s4lo,                            // column 19
                              precompute_skew,                            // column 20
                              msm_size_of_msm,                            // column 21
                              msm_add2,                                   // column 22
                              msm_add3,                                   // column 23
                              msm_add4,                                   // column 24
                              msm_x1,                                     // column 25
                              msm_y1,                                     // column 26
                              msm_x2,                                     // column 27
                              msm_y2,                                     // column 28
                              msm_x3,                                     // column 29
                              msm_y3,                                     // column 30
                              msm_x4,                                     // column 31
                              msm_y4,                                     // column 32
                              msm_collision_x1,                           // column 33
                              msm_collision_x2,                           // column 34
                              msm_collision_x3,                           // column 35
                              msm_collision_x4,                           // column 36
                              msm_lambda1,                                // column 37
                              msm_lambda2,                                // column 38
                              msm_lambda3,                                // column 39
                              msm_lambda4,                                // column 40
                              msm_slice1,                                 // column 41
                              msm_slice2,                                 // column 42
                              msm_slice3,                                 // column 43
                              msm_slice4,                                 // column 44
                              transcript_reset_accumulator,               // column 45
                              lookup_read_counts_0,                       // column 46
                              lookup_read_counts_1,                       // column 47
                              transcript_base_infinity,                   // column 48
                              transcript_base_x_inverse,                  // column 49
                              transcript_base_y_inverse,                  // column 50
                              transcript_add_x_equal,                     // column 51
                              transcript_add_y_equal,                     // column 52
                              transcript_add_lambda,                      // column 53
                              transcript_msm_intermediate_x,              // column 54
                              transcript_msm_intermediate_y,              // column 55
                              transcript_msm_infinity,                    // column 56
                              transcript_msm_x_inverse,                   // column 57
                              transcript_msm_count_zero_at_transition,    // column 58
                              transcript_msm_count_at_transition_inverse) // column 59
    };
 
    template <typename DataType> class MaskingEntities {
      public:
        DEFINE_FLAVOR_MEMBERS(DataType, gemini_masking_poly)
    };
 
    template <typename DataType> class WireToBeShiftedWithoutAccumulatorsEntities {
      public:
        DEFINE_FLAVOR_MEMBERS(DataType,
                              transcript_mul,        // column 60
                              transcript_msm_count,  // column 61
                              precompute_scalar_sum, // column 62
                              precompute_s1hi,       // column 63
                              precompute_dx,         // column 64
                              precompute_dy,         // column 65
                              precompute_tx,         // column 66
                              precompute_ty,         // column 67
                              msm_transition,        // column 68
                              msm_add,               // column 69
                              msm_double,            // column 70
                              msm_skew,              // column 71
                              msm_accumulator_x,     // column 72
                              msm_accumulator_y,     // column 73
                              msm_count,             // column 74
                              msm_round,             // column 75
                              msm_add1,              // column 76
                              msm_pc,                // column 77
                              precompute_pc,         // column 78
                              transcript_pc,         // column 79
                              precompute_round,      // column 80
                              precompute_select)     // column 81
    };
 
    template <typename DataType> class WireToBeShiftedAccumulatorEntities {
      public:
        DEFINE_FLAVOR_MEMBERS(DataType,
                              transcript_accumulator_not_empty, // column 82
                              transcript_accumulator_x,         // column 83
                              transcript_accumulator_y)         // column 84
    };
 
    template <typename DataType>
    class WitnessEntities : public WireNonShiftedEntities<DataType>,
                            public WireToBeShiftedWithoutAccumulatorsEntities<DataType>,
                            public WireToBeShiftedAccumulatorEntities<DataType>,
                            public DerivedWitnessEntities<DataType> {
      public:
        DEFINE_COMPOUND_GET_ALL(WireNonShiftedEntities<DataType>,
                                WireToBeShiftedWithoutAccumulatorsEntities<DataType>,
                                WireToBeShiftedAccumulatorEntities<DataType>,
                                DerivedWitnessEntities<DataType>)
        auto get_wires()
        {
            return concatenate(WireNonShiftedEntities<DataType>::get_all(),
                               WireToBeShiftedWithoutAccumulatorsEntities<DataType>::get_all(),
                               WireToBeShiftedAccumulatorEntities<DataType>::get_all());
        };
 
        // Used to amortize the commitment time when the ECCVM size is fixed
        auto get_accumulators() { return WireToBeShiftedAccumulatorEntities<DataType>::get_all(); };
        auto get_wires_without_accumulators()
        {
            return concatenate(WireNonShiftedEntities<DataType>::get_all(),
                               WireToBeShiftedWithoutAccumulatorsEntities<DataType>::get_all());
        }
    };
 
    template <typename DataType> class ShiftedEntities {
      public:
        DEFINE_FLAVOR_MEMBERS(DataType,
                              transcript_mul_shift,                   // column 0
                              transcript_msm_count_shift,             // column 1
                              precompute_scalar_sum_shift,            // column 2
                              precompute_s1hi_shift,                  // column 3
                              precompute_dx_shift,                    // column 4
                              precompute_dy_shift,                    // column 5
                              precompute_tx_shift,                    // column 6
                              precompute_ty_shift,                    // column 7
                              msm_transition_shift,                   // column 8
                              msm_add_shift,                          // column 9
                              msm_double_shift,                       // column 10
                              msm_skew_shift,                         // column 11
                              msm_accumulator_x_shift,                // column 12
                              msm_accumulator_y_shift,                // column 13
                              msm_count_shift,                        // column 14
                              msm_round_shift,                        // column 15
                              msm_add1_shift,                         // column 16
                              msm_pc_shift,                           // column 17
                              precompute_pc_shift,                    // column 18
                              transcript_pc_shift,                    // column 19
                              precompute_round_shift,                 // column 20
                              precompute_select_shift,                // column 21
                              transcript_accumulator_not_empty_shift, // column 22
                              transcript_accumulator_x_shift,         // column 23
                              transcript_accumulator_y_shift,         // column 24
                              z_perm_shift);                          // column 25
    };
 
    template <typename DataType, typename PrecomputedAndWitnessEntitiesSuperset>
    static auto get_to_be_shifted(PrecomputedAndWitnessEntitiesSuperset& entities)
    {
        // NOTE: must match order of ShiftedEntities above!
        return RefArray{ entities.transcript_mul,                   // column 0
                         entities.transcript_msm_count,             // column 1
                         entities.precompute_scalar_sum,            // column 2
                         entities.precompute_s1hi,                  // column 3
                         entities.precompute_dx,                    // column 4
                         entities.precompute_dy,                    // column 5
                         entities.precompute_tx,                    // column 6
                         entities.precompute_ty,                    // column 7
                         entities.msm_transition,                   // column 8
                         entities.msm_add,                          // column 9
                         entities.msm_double,                       // column 10
                         entities.msm_skew,                         // column 11
                         entities.msm_accumulator_x,                // column 12
                         entities.msm_accumulator_y,                // column 13
                         entities.msm_count,                        // column 14
                         entities.msm_round,                        // column 15
                         entities.msm_add1,                         // column 16
                         entities.msm_pc,                           // column 17
                         entities.precompute_pc,                    // column 18
                         entities.transcript_pc,                    // column 19
                         entities.precompute_round,                 // column 20
                         entities.precompute_select,                // column 21
                         entities.transcript_accumulator_not_empty, // column 22
                         entities.transcript_accumulator_x,         // column 23
                         entities.transcript_accumulator_y,         // column 24
                         entities.z_perm };                         // column 25
    }
 
    template <typename DataType>
    class AllEntities : public MaskingEntities<DataType>,
                        public PrecomputedEntities<DataType>,
                        public WitnessEntities<DataType>,
                        public ShiftedEntities<DataType> {
      public:
        DEFINE_COMPOUND_GET_ALL(MaskingEntities<DataType>,
                                PrecomputedEntities<DataType>,
                                WitnessEntities<DataType>,
                                ShiftedEntities<DataType>)
        auto get_unshifted()
        {
            return concatenate(MaskingEntities<DataType>::get_all(),
                               PrecomputedEntities<DataType>::get_all(),
                               WitnessEntities<DataType>::get_all());
        };
        auto get_to_be_shifted() { return ECCVMFlavor::get_to_be_shifted<DataType>(*this); }
        auto get_shifted() { return ShiftedEntities<DataType>::get_all(); };
        auto get_precomputed() { return PrecomputedEntities<DataType>::get_all(); };
    };
 
    class AllValues : public AllEntities<FF> {
      public:
        using Base = AllEntities<FF>;
        using Base::Base;
    };
 
    template <size_t LENGTH> using ProverUnivariates = AllEntities<bb::Univariate<FF, LENGTH>>;
 
    using ExtendedEdges = ProverUnivariates<MAX_PARTIAL_RELATION_LENGTH>;
 
    class ProverPolynomials : public AllEntities<Polynomial> {
      public:
        // Define all operations as default, except copy construction/assignment
        ProverPolynomials() = default;
        ProverPolynomials& operator=(const ProverPolynomials&) = delete;
        ProverPolynomials(const ProverPolynomials& o) = delete;
        ProverPolynomials(ProverPolynomials&& o) noexcept = default;
        ProverPolynomials& operator=(ProverPolynomials&& o) noexcept = default;
        ~ProverPolynomials() = default;
        [[nodiscard]] size_t get_polynomial_size() const { return this->lagrange_first.size(); }
 
        AllValues get_row(const size_t row_idx) const
        {
            AllValues result;
            for (auto [result_field, polynomial] : zip_view(result.get_all(), this->get_all())) {
                result_field = polynomial[row_idx];
            }
            return result;
        }
        // Set all shifted polynomials based on their to-be-shifted counterpart
        void set_shifted()
        {
            for (auto [shifted, to_be_shifted] : zip_view(get_shifted(), get_to_be_shifted())) {
                shifted = to_be_shifted.shifted();
            }
        }
 
#ifdef FUZZING
        ProverPolynomials(const CircuitBuilder& builder, bool disable_fixed_dyadic_trace_size = false)
#else
        ProverPolynomials(const CircuitBuilder& builder)
#endif
        {
            // compute rows for the three different sections of the ECCVM execution trace
            // Note: the first operation (index 0) is always a hiding op with random Px, Py values
            const auto transcript_rows =
                ECCVMTranscriptBuilder::compute_rows(builder.op_queue->get_eccvm_ops(), builder.get_number_of_muls());
            const std::vector<MSM> msms = builder.get_msms();
            const auto point_table_rows =
                ECCVMPointTablePrecomputationBuilder::compute_rows(CircuitBuilder::get_flattened_scalar_muls(msms));
            const auto result = ECCVMMSMMBuilder::compute_rows(
                msms, builder.get_number_of_muls(), builder.op_queue->get_num_msm_rows());
            const auto& msm_rows = std::get<0>(result);
            const auto& point_table_read_counts = std::get<1>(result);
 
            const size_t num_rows = std::max({ point_table_rows.size(), msm_rows.size(), transcript_rows.size() }) +
                                    NUM_DISABLED_ROWS_IN_SUMCHECK;
            vinfo("Num rows in the ECCVM: ", num_rows);
            const auto log_num_rows = static_cast<size_t>(numeric::get_msb64(num_rows));
            size_t dyadic_num_rows = 1UL << (log_num_rows + (1UL << log_num_rows == num_rows ? 0 : 1));
            BB_ASSERT_LTE(dyadic_num_rows,
                          ECCVM_FIXED_SIZE,
                          "The ECCVM circuit size has exceeded the fixed upper bound! Fixed size: " +
                              std::to_string(ECCVM_FIXED_SIZE) + " actual size: " + std::to_string(dyadic_num_rows));
 
#ifdef FUZZING
            // We don't want to spend all the time generating the full trace if we are just fuzzing eccvm.
            if (disable_fixed_dyadic_trace_size) {
                dyadic_num_rows = num_rows;
            } else {
                dyadic_num_rows = ECCVM_FIXED_SIZE;
            }
#else
            dyadic_num_rows = ECCVM_FIXED_SIZE;
#endif
            size_t unmasked_witness_size = dyadic_num_rows - NUM_DISABLED_ROWS_IN_SUMCHECK;
 
            for (auto& poly : get_to_be_shifted()) {
                poly = Polynomial{ /*memory size*/ dyadic_num_rows - 1,
                                   /*largest possible index*/ dyadic_num_rows,
                                   /* offset */ 1 };
            }
            // allocate polynomials; define lagrange and lookup read count polynomials
            for (auto& poly : get_all()) {
                if (poly.is_empty()) {
                    poly = Polynomial(dyadic_num_rows);
                }
            }
            lagrange_first.at(0) = 1;
            lagrange_second.at(1) = 1;
            lagrange_third.at(2) = 1;
            lagrange_last.at(unmasked_witness_size - 1) = 1;
            for (size_t i = 0; i < point_table_read_counts[0].size(); ++i) {
                // Explanation of off-by-one offset:
                // When computing the WNAF slice for a point at point counter value `pc` and a round index `round`, the
                // row number that computes the slice can be derived. This row number is then mapped to the index of
                // `lookup_read_counts`. We do this mapping in `ecc_msm_relation`. We are off-by-one because we add an
                // empty row at the start of the WNAF columns that is not accounted for (index of lookup_read_counts
                // maps to the row in our WNAF columns that computes a slice for a given value of pc and round)
                lookup_read_counts_0.at(i + 1) = point_table_read_counts[0][i];
                lookup_read_counts_1.at(i + 1) = point_table_read_counts[1][i];
            }
 
            // compute polynomials for transcript columns
            parallel_for_range(transcript_rows.size(), [&](size_t start, size_t end) {
                for (size_t i = start; i < end; i++) {
                    transcript_accumulator_not_empty.set_if_valid_index(i, transcript_rows[i].accumulator_not_empty);
                    transcript_add.set_if_valid_index(i, transcript_rows[i].q_add);
                    transcript_mul.set_if_valid_index(i, transcript_rows[i].q_mul);
                    transcript_eq.set_if_valid_index(i, transcript_rows[i].q_eq);
                    transcript_reset_accumulator.set_if_valid_index(i, transcript_rows[i].q_reset_accumulator);
                    transcript_msm_transition.set_if_valid_index(i, transcript_rows[i].msm_transition);
                    transcript_pc.set_if_valid_index(i, transcript_rows[i].pc);
                    transcript_msm_count.set_if_valid_index(i, transcript_rows[i].msm_count);
                    transcript_Px.set_if_valid_index(i, transcript_rows[i].base_x);
                    transcript_Py.set_if_valid_index(i, transcript_rows[i].base_y);
                    transcript_z1.set_if_valid_index(i, transcript_rows[i].z1);
                    transcript_z2.set_if_valid_index(i, transcript_rows[i].z2);
                    transcript_z1zero.set_if_valid_index(i, transcript_rows[i].z1_zero);
                    transcript_z2zero.set_if_valid_index(i, transcript_rows[i].z2_zero);
                    transcript_op.set_if_valid_index(i, transcript_rows[i].opcode);
                    transcript_accumulator_x.set_if_valid_index(i, transcript_rows[i].accumulator_x);
                    transcript_accumulator_y.set_if_valid_index(i, transcript_rows[i].accumulator_y);
                    transcript_msm_x.set_if_valid_index(i, transcript_rows[i].msm_output_x);
                    transcript_msm_y.set_if_valid_index(i, transcript_rows[i].msm_output_y);
                    transcript_base_infinity.set_if_valid_index(i, transcript_rows[i].base_infinity);
                    transcript_base_x_inverse.set_if_valid_index(i, transcript_rows[i].base_x_inverse);
                    transcript_base_y_inverse.set_if_valid_index(i, transcript_rows[i].base_y_inverse);
                    transcript_add_x_equal.set_if_valid_index(i, transcript_rows[i].transcript_add_x_equal);
                    transcript_add_y_equal.set_if_valid_index(i, transcript_rows[i].transcript_add_y_equal);
                    transcript_add_lambda.set_if_valid_index(i, transcript_rows[i].transcript_add_lambda);
                    transcript_msm_intermediate_x.set_if_valid_index(i,
                                                                     transcript_rows[i].transcript_msm_intermediate_x);
                    transcript_msm_intermediate_y.set_if_valid_index(i,
                                                                     transcript_rows[i].transcript_msm_intermediate_y);
                    transcript_msm_infinity.set_if_valid_index(i, transcript_rows[i].transcript_msm_infinity);
                    transcript_msm_x_inverse.set_if_valid_index(i, transcript_rows[i].transcript_msm_x_inverse);
                    transcript_msm_count_zero_at_transition.set_if_valid_index(
                        i, transcript_rows[i].msm_count_zero_at_transition);
                    transcript_msm_count_at_transition_inverse.set_if_valid_index(
                        i, transcript_rows[i].msm_count_at_transition_inverse);
                }
            });
 
            parallel_for_range(point_table_rows.size(), [&](size_t start, size_t end) {
                for (size_t i = start; i < end; i++) {
                    // first row is always an empty row (to accommodate shifted polynomials which must have 0 as 1st
                    // coefficient). All other rows in the point_table_rows represent active wnaf gates (i.e.
                    // precompute_select = 1)
                    precompute_select.set_if_valid_index(i, (i != 0) ? 1 : 0);
                    precompute_pc.set_if_valid_index(i, point_table_rows[i].pc);
                    precompute_point_transition.set_if_valid_index(
                        i, static_cast<uint64_t>(point_table_rows[i].point_transition));
                    precompute_round.set_if_valid_index(i, point_table_rows[i].round);
                    precompute_scalar_sum.set_if_valid_index(i, point_table_rows[i].scalar_sum);
                    precompute_s1hi.set_if_valid_index(i, point_table_rows[i].s1);
                    precompute_s1lo.set_if_valid_index(i, point_table_rows[i].s2);
                    precompute_s2hi.set_if_valid_index(i, point_table_rows[i].s3);
                    precompute_s2lo.set_if_valid_index(i, point_table_rows[i].s4);
                    precompute_s3hi.set_if_valid_index(i, point_table_rows[i].s5);
                    precompute_s3lo.set_if_valid_index(i, point_table_rows[i].s6);
                    precompute_s4hi.set_if_valid_index(i, point_table_rows[i].s7);
                    precompute_s4lo.set_if_valid_index(i, point_table_rows[i].s8);
                    // If skew is active (i.e. we need to subtract a base point from the msm result),
                    // write `7` into rows.precompute_skew. `7`, in binary representation, equals `-1` when converted
                    // into WNAF form
                    precompute_skew.set_if_valid_index(i, point_table_rows[i].skew ? 7 : 0);
                    precompute_dx.set_if_valid_index(i, point_table_rows[i].precompute_double.x);
                    precompute_dy.set_if_valid_index(i, point_table_rows[i].precompute_double.y);
                    precompute_tx.set_if_valid_index(i, point_table_rows[i].precompute_accumulator.x);
                    precompute_ty.set_if_valid_index(i, point_table_rows[i].precompute_accumulator.y);
                }
            });
 
            // compute polynomials for the msm columns
            parallel_for_range(msm_rows.size(), [&](size_t start, size_t end) {
                for (size_t i = start; i < end; i++) {
                    msm_transition.set_if_valid_index(i, static_cast<int>(msm_rows[i].msm_transition));
                    msm_add.set_if_valid_index(i, static_cast<int>(msm_rows[i].q_add));
                    msm_double.set_if_valid_index(i, static_cast<int>(msm_rows[i].q_double));
                    msm_skew.set_if_valid_index(i, static_cast<int>(msm_rows[i].q_skew));
                    msm_accumulator_x.set_if_valid_index(i, msm_rows[i].accumulator_x);
                    msm_accumulator_y.set_if_valid_index(i, msm_rows[i].accumulator_y);
                    msm_pc.set_if_valid_index(i, msm_rows[i].pc);
                    msm_size_of_msm.set_if_valid_index(i, msm_rows[i].msm_size);
                    msm_count.set_if_valid_index(i, msm_rows[i].msm_count);
                    msm_round.set_if_valid_index(i, msm_rows[i].msm_round);
                    msm_add1.set_if_valid_index(i, static_cast<int>(msm_rows[i].add_state[0].add));
                    msm_add2.set_if_valid_index(i, static_cast<int>(msm_rows[i].add_state[1].add));
                    msm_add3.set_if_valid_index(i, static_cast<int>(msm_rows[i].add_state[2].add));
                    msm_add4.set_if_valid_index(i, static_cast<int>(msm_rows[i].add_state[3].add));
                    msm_x1.set_if_valid_index(i, msm_rows[i].add_state[0].point.x);
                    msm_y1.set_if_valid_index(i, msm_rows[i].add_state[0].point.y);
                    msm_x2.set_if_valid_index(i, msm_rows[i].add_state[1].point.x);
                    msm_y2.set_if_valid_index(i, msm_rows[i].add_state[1].point.y);
                    msm_x3.set_if_valid_index(i, msm_rows[i].add_state[2].point.x);
                    msm_y3.set_if_valid_index(i, msm_rows[i].add_state[2].point.y);
                    msm_x4.set_if_valid_index(i, msm_rows[i].add_state[3].point.x);
                    msm_y4.set_if_valid_index(i, msm_rows[i].add_state[3].point.y);
                    msm_collision_x1.set_if_valid_index(i, msm_rows[i].add_state[0].collision_inverse);
                    msm_collision_x2.set_if_valid_index(i, msm_rows[i].add_state[1].collision_inverse);
                    msm_collision_x3.set_if_valid_index(i, msm_rows[i].add_state[2].collision_inverse);
                    msm_collision_x4.set_if_valid_index(i, msm_rows[i].add_state[3].collision_inverse);
                    msm_lambda1.set_if_valid_index(i, msm_rows[i].add_state[0].lambda);
                    msm_lambda2.set_if_valid_index(i, msm_rows[i].add_state[1].lambda);
                    msm_lambda3.set_if_valid_index(i, msm_rows[i].add_state[2].lambda);
                    msm_lambda4.set_if_valid_index(i, msm_rows[i].add_state[3].lambda);
                    msm_slice1.set_if_valid_index(i, msm_rows[i].add_state[0].slice);
                    msm_slice2.set_if_valid_index(i, msm_rows[i].add_state[1].slice);
                    msm_slice3.set_if_valid_index(i, msm_rows[i].add_state[2].slice);
                    msm_slice4.set_if_valid_index(i, msm_rows[i].add_state[3].slice);
                }
            });
            this->set_shifted();
        }
    };
 
    class PartiallyEvaluatedMultivariates : public AllEntities<Polynomial> {
 
      public:
        PartiallyEvaluatedMultivariates() = default;
        PartiallyEvaluatedMultivariates(const size_t circuit_size)
        {
            // Storage is only needed after the first partial evaluation, hence polynomials of size (n / 2)
            for (auto& poly : this->get_all()) {
                poly = Polynomial(circuit_size / 2);
            }
        }
        PartiallyEvaluatedMultivariates(const ProverPolynomials& full_polynomials, size_t circuit_size)
        {
            for (auto [poly, full_poly] : zip_view(get_all(), full_polynomials.get_all())) {
                // After the initial sumcheck round, the new size is CEIL(size/2).
                size_t desired_size = full_poly.end_index() / 2 + full_poly.end_index() % 2;
                poly = Polynomial(desired_size, circuit_size / 2);
            }
        }
    };
 
    class ProvingKey {
      public:
        size_t circuit_size = ECCVM_FIXED_SIZE; // The circuit size is fixed for the ECCVM.
        size_t log_circuit_size = CONST_ECCVM_LOG_N;
 
        // Used to amortize the commitment time if the `fixed size` > `real_size`.
        size_t real_size = 0;
 
        ProverPolynomials polynomials; // storage for all polynomials evaluated by the prover
        CommitmentKey commitment_key;
 
        // Constructor for fixed size ProvingKey
        ProvingKey(const CircuitBuilder& builder)
            : real_size(builder.get_circuit_subgroup_size(builder.get_estimated_num_finalized_gates()))
            , polynomials(builder)
        {}
    };
 
    class VerificationKey : public NativeVerificationKey_<PrecomputedEntities<Commitment>, Transcript> {
      public:
        bool operator==(const VerificationKey&) const = default;
 
        // IPA verification key requires one more point.
        VerifierCommitmentKey pcs_verification_key = VerifierCommitmentKey(ECCVM_FIXED_SIZE + 1);
 
        // Default construct the fixed VK that results from ECCVM_FIXED_SIZE
        VerificationKey()
            : NativeVerificationKey_(ECCVM_FIXED_SIZE, /*num_public_inputs=*/0)
        {
            this->pub_inputs_offset = 0;
 
            // Populate the commitments of the precomputed polynomials using the fixed VK data
            for (auto [vk_commitment, fixed_commitment] :
                 zip_view(this->get_all(), ECCVMFixedVKCommitments::get_all())) {
                vk_commitment = fixed_commitment;
            }
        }
 
        VerificationKey(const size_t circuit_size, const size_t num_public_inputs)
            : NativeVerificationKey_(circuit_size, num_public_inputs)
        {}
 
        VerificationKey(const std::shared_ptr<ProvingKey>& proving_key)
        {
            this->log_circuit_size = CONST_ECCVM_LOG_N;
            this->num_public_inputs = 0;
            this->pub_inputs_offset = 0;
 
            for (auto [polynomial, commitment] :
                 zip_view(proving_key->polynomials.get_precomputed(), this->get_all())) {
                commitment = proving_key->commitment_key.commit(polynomial);
            }
        }
 
        fr hash_with_origin_tagging([[maybe_unused]] const std::string& domain_separator,
                                    [[maybe_unused]] Transcript& transcript) const override
        {
            throw_or_abort("Not intended to be used because vk is hardcoded in circuit.");
        }
 
        // TODO(https://github.com/AztecProtocol/barretenberg/issues/1324): Remove `circuit_size` and `log_circuit_size`
        // from the verification key.
    };
 
    class CommitmentLabels : public AllEntities<std::string> {
      private:
        using Base = AllEntities<std::string>;
 
      public:
        CommitmentLabels()
            : AllEntities<std::string>()
        {
            Base::transcript_add = "TRANSCRIPT_ADD";
            Base::transcript_mul = "TRANSCRIPT_MUL";
            Base::transcript_eq = "TRANSCRIPT_EQ";
            Base::transcript_msm_transition = "TRANSCRIPT_MSM_TRANSITION";
            Base::transcript_pc = "TRANSCRIPT_PC";
            Base::transcript_msm_count = "TRANSCRIPT_MSM_COUNT";
            Base::transcript_Px = "TRANSCRIPT_PX";
            Base::transcript_Py = "TRANSCRIPT_PY";
            Base::transcript_z1 = "TRANSCRIPT_Z1";
            Base::transcript_z2 = "TRANSCRIPT_Z2";
            Base::transcript_z1zero = "TRANSCRIPT_Z1ZERO";
            Base::transcript_z2zero = "TRANSCRIPT_Z2ZERO";
            Base::transcript_op = "TRANSCRIPT_OP";
            Base::transcript_accumulator_x = "TRANSCRIPT_ACCUMULATOR_X";
            Base::transcript_accumulator_y = "TRANSCRIPT_ACCUMULATOR_Y";
            Base::transcript_msm_x = "TRANSCRIPT_MSM_X";
            Base::transcript_msm_y = "TRANSCRIPT_MSM_Y";
            Base::precompute_pc = "PRECOMPUTE_PC";
            Base::precompute_point_transition = "PRECOMPUTE_POINT_TRANSITION";
            Base::precompute_round = "PRECOMPUTE_ROUND";
            Base::precompute_scalar_sum = "PRECOMPUTE_SCALAR_SUM";
            Base::precompute_s1hi = "PRECOMPUTE_S1HI";
            Base::precompute_s1lo = "PRECOMPUTE_S1LO";
            Base::precompute_s2hi = "PRECOMPUTE_S2HI";
            Base::precompute_s2lo = "PRECOMPUTE_S2LO";
            Base::precompute_s3hi = "PRECOMPUTE_S3HI";
            Base::precompute_s3lo = "PRECOMPUTE_S3LO";
            Base::precompute_s4hi = "PRECOMPUTE_S4HI";
            Base::precompute_s4lo = "PRECOMPUTE_S4LO";
            Base::precompute_skew = "PRECOMPUTE_SKEW";
            Base::precompute_dx = "PRECOMPUTE_DX";
            Base::precompute_dy = "PRECOMPUTE_DY";
            Base::precompute_tx = "PRECOMPUTE_TX";
            Base::precompute_ty = "PRECOMPUTE_TY";
            Base::msm_transition = "MSM_TRANSITION";
            Base::msm_add = "MSM_ADD";
            Base::msm_double = "MSM_DOUBLE";
            Base::msm_skew = "MSM_SKEW";
            Base::msm_accumulator_x = "MSM_ACCUMULATOR_X";
            Base::msm_accumulator_y = "MSM_ACCUMULATOR_Y";
            Base::msm_pc = "MSM_PC";
            Base::msm_size_of_msm = "MSM_SIZE_OF_MSM";
            Base::msm_count = "MSM_COUNT";
            Base::msm_round = "MSM_ROUND";
            Base::msm_add1 = "MSM_ADD1";
            Base::msm_add2 = "MSM_ADD2";
            Base::msm_add3 = "MSM_ADD3";
            Base::msm_add4 = "MSM_ADD4";
            Base::msm_x1 = "MSM_X1";
            Base::msm_y1 = "MSM_Y1";
            Base::msm_x2 = "MSM_X2";
            Base::msm_y2 = "MSM_Y2";
            Base::msm_x3 = "MSM_X3";
            Base::msm_y3 = "MSM_Y3";
            Base::msm_x4 = "MSM_X4";
            Base::msm_y4 = "MSM_Y4";
            Base::msm_collision_x1 = "MSM_COLLISION_X1";
            Base::msm_collision_x2 = "MSM_COLLISION_X2";
            Base::msm_collision_x3 = "MSM_COLLISION_X3";
            Base::msm_collision_x4 = "MSM_COLLISION_X4";
            Base::msm_lambda1 = "MSM_LAMBDA1";
            Base::msm_lambda2 = "MSM_LAMBDA2";
            Base::msm_lambda3 = "MSM_LAMBDA3";
            Base::msm_lambda4 = "MSM_LAMBDA4";
            Base::msm_slice1 = "MSM_SLICE1";
            Base::msm_slice2 = "MSM_SLICE2";
            Base::msm_slice3 = "MSM_SLICE3";
            Base::msm_slice4 = "MSM_SLICE4";
            Base::transcript_accumulator_not_empty = "TRANSCRIPT_ACCUMULATOR_NOT_EMPTY";
            Base::transcript_reset_accumulator = "TRANSCRIPT_RESET_ACCUMULATOR";
            Base::precompute_select = "PRECOMPUTE_SELECT";
            Base::lookup_read_counts_0 = "LOOKUP_READ_COUNTS_0";
            Base::lookup_read_counts_1 = "LOOKUP_READ_COUNTS_1";
            Base::transcript_base_infinity = "TRANSCRIPT_BASE_INFINITY";
            Base::transcript_base_x_inverse = "TRANSCRIPT_BASE_X_INVERSE";
            Base::transcript_base_y_inverse = "TRANSCRIPT_BASE_Y_INVERSE";
            Base::transcript_add_x_equal = "TRANSCRIPT_ADD_X_EQUAL";
            Base::transcript_add_y_equal = "TRANSCRIPT_ADD_Y_EQUAL";
            Base::transcript_add_lambda = "TRANSCRIPT_ADD_LAMBDA";
            Base::transcript_msm_intermediate_x = "TRANSCRIPT_MSM_INTERMEDIATE_X";
            Base::transcript_msm_intermediate_y = "TRANSCRIPT_MSM_INTERMEDIATE_Y";
            Base::transcript_msm_infinity = "TRANSCRIPT_MSM_INFINITY";
            Base::transcript_msm_x_inverse = "TRANSCRIPT_MSM_X_INVERSE";
            Base::transcript_msm_count_zero_at_transition = "TRANSCRIPT_MSM_COUNT_ZERO_AT_TRANSITION";
            Base::transcript_msm_count_at_transition_inverse = "TRANSCRIPT_MSM_COUNT_AT_TRANSITION_INVERSE";
            Base::z_perm = "Z_PERM";
            Base::z_perm_shift = "Z_PERM_SHIFT";
            Base::lookup_inverses = "LOOKUP_INVERSES";
            // The ones beginning with "__" are only used for debugging
            Base::lagrange_first = "__LAGRANGE_FIRST";
            Base::lagrange_second = "__LAGRANGE_SECOND";
            Base::lagrange_third = "__LAGRANGE_THIRD";
            Base::lagrange_last = "__LAGRANGE_LAST";
        };
    };
 
    template <typename Commitment, typename VerificationKey>
    class VerifierCommitments_ : public AllEntities<Commitment> {
      public:
        VerifierCommitments_(const std::shared_ptr<VerificationKey>& verification_key)
        {
            this->lagrange_first = verification_key->lagrange_first;
            this->lagrange_second = verification_key->lagrange_second;
            this->lagrange_third = verification_key->lagrange_third;
            this->lagrange_last = verification_key->lagrange_last;
        }
    };
 
    using VerifierCommitments = VerifierCommitments_<Commitment, VerificationKey>;
 
    class IPATranscript : public NativeTranscript {
      public:
        uint32_t ipa_poly_degree;
        std::vector<Commitment> ipa_l_comms;
        std::vector<Commitment> ipa_r_comms;
        Commitment ipa_G_0_eval;
        FF ipa_a_0_eval;
 
        IPATranscript() = default;
 
        void deserialize_full_transcript()
        {
            // take current proof and put them into the struct
            size_t num_frs_read = 0;
            ipa_poly_degree = NativeTranscript::template deserialize_from_buffer<uint32_t>(NativeTranscript::proof_data,
                                                                                           num_frs_read);
 
            for (size_t i = 0; i < CONST_ECCVM_LOG_N; ++i) {
                ipa_l_comms.emplace_back(NativeTranscript::template deserialize_from_buffer<Commitment>(
                    NativeTranscript::proof_data, num_frs_read));
                ipa_r_comms.emplace_back(NativeTranscript::template deserialize_from_buffer<Commitment>(
                    NativeTranscript::proof_data, num_frs_read));
            }
            ipa_G_0_eval = NativeTranscript::template deserialize_from_buffer<Commitment>(NativeTranscript::proof_data,
                                                                                          num_frs_read);
            ipa_a_0_eval =
                NativeTranscript::template deserialize_from_buffer<FF>(NativeTranscript::proof_data, num_frs_read);
        }
 
        void serialize_full_transcript()
        {
            size_t old_proof_length = NativeTranscript::proof_data.size();
            NativeTranscript::proof_data.clear();
 
            NativeTranscript::serialize_to_buffer(ipa_poly_degree, NativeTranscript::proof_data);
            for (size_t i = 0; i < CONST_ECCVM_LOG_N; ++i) {
                NativeTranscript::serialize_to_buffer(ipa_l_comms[i], NativeTranscript::proof_data);
                NativeTranscript::serialize_to_buffer(ipa_r_comms[i], NativeTranscript::proof_data);
            }
 
            serialize_to_buffer(ipa_G_0_eval, proof_data);
            serialize_to_buffer(ipa_a_0_eval, proof_data);
 
            BB_ASSERT_EQ(NativeTranscript::proof_data.size(), old_proof_length);
        }
    };
 
    template <typename ProverPolynomialsOrPartiallyEvaluatedMultivariates, typename EdgeType>
    static bool skip_entire_row([[maybe_unused]] const ProverPolynomialsOrPartiallyEvaluatedMultivariates& polynomials,
                                [[maybe_unused]] const EdgeType edge_idx)
    {
        // SKIP CONDITIONS:
        // The most important skip condition is that `z_perm == z_perm_shift`. This implies that none of the wire values
        // for the present input are involved in non-trivial copy constraints. Edge cases where nonzero rows do not
        // contribute to permutation:
        //
        // 1: If `lagrange_last != 0`, the permutation polynomial identity is updated even if
        //    z_perm == z_perm_shift. Therefore, we must force it to be zero.
        //
        // 2: The final MSM row won't add to the permutation but still has polynomial identitiy
        //    contributions. This is because the permutation argument uses the SHIFTED msm columns when performing
        //    lookups i.e. `msm_accumulator_x[last_edge_idx]` will change `z_perm[last_edge_idx - 1]` and
        //    `z_perm_shift[last_edge_idx - 1]`
        //
        // 3. The value of `transcript_mul` is non-zero at the end of an MSM of points-at-infinity, which will
        //    cause `full_msm_count` to be non-zero while `transcript_msm_count` vanishes. We therefore force
        //    transcript_mul == 0 as a skip-row condition.
        //
        // 4: We also force that `transcript_op==0`.
        return (polynomials.z_perm[edge_idx] == polynomials.z_perm_shift[edge_idx]) &&
               (polynomials.z_perm[edge_idx + 1] == polynomials.z_perm_shift[edge_idx + 1]) &&
               (polynomials.lagrange_last[edge_idx] == 0 && polynomials.lagrange_last[edge_idx + 1]) == 0 &&
               (polynomials.msm_transition[edge_idx] == 0 && polynomials.msm_transition[edge_idx + 1] == 0) &&
               (polynomials.transcript_mul[edge_idx] == 0 && polynomials.transcript_mul[edge_idx + 1] == 0) &&
               (polynomials.transcript_op[edge_idx] == 0 && polynomials.transcript_op[edge_idx + 1] == 0);
    }
};
} // namespace bb