ecc_op_queue.hpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: Complete, auditors: [Raju], commit: }
// external_1:  { status: not started, auditors: [], commit: }
// external_2:  { status: not started, auditors: [], commit: }
// =====================
 
#pragma once
 
#include "barretenberg/common/bb_bench.hpp"
#include "barretenberg/ecc/curves/bn254/bn254.hpp"
#include "barretenberg/eccvm/eccvm_builder_types.hpp"
#include "barretenberg/op_queue/ecc_ops_table.hpp"
#include "barretenberg/op_queue/eccvm_row_tracker.hpp"
#include "barretenberg/polynomials/polynomial.hpp"
namespace bb {
 
class ECCOpQueue {
    using Curve = curve::BN254;
    using Point = Curve::AffineElement;
    using Fr = Curve::ScalarField;
    using Fq = Curve::BaseField; // Grumpkin's scalar field
    static constexpr size_t ULTRA_TABLE_WIDTH = UltraEccOpsTable::TABLE_WIDTH;
    Point point_at_infinity = Curve::Group::affine_point_at_infinity;
 
    // The operations written to the queue are also performed natively; the result is stored in accumulator.
    // The accumulator is kept in jacobian form and scalar muls are deferred and evaluated as a batch on read:
    // evaluating each mul eagerly on an affine accumulator costs a full scalar mul plus a normalization
    // (field inversion) per op.
    Curve::Element accumulator = Curve::Element::infinity();
    std::vector<Point> deferred_mul_points;
    std::vector<Fr> deferred_mul_scalars;
 
    // Fold the deferred scalar muls into the accumulator via a single batched MSM.
    void flush_deferred_muls()
    {
        if (deferred_mul_points.empty()) {
            return;
        }
        accumulator += Curve::Element::straus_msm(deferred_mul_points, deferred_mul_scalars);
        deferred_mul_points.clear();
        deferred_mul_scalars.clear();
    }
 
    void reset_accumulator()
    {
        accumulator.self_set_infinity();
        deferred_mul_points.clear();
        deferred_mul_scalars.clear();
    }
 
    EccvmOpsTable eccvm_ops_table;    // table of ops in the ECCVM format
    UltraEccOpsTable ultra_ops_table; // table of ops in the Ultra-arithmetization format
 
    // Storage for the reconstructed eccvm ops table in contiguous memory. (Intended to be constructed once and for
    // all prior to ECCVM construction to avoid repeated traversal of the per-subtable storage.)
    std::vector<ECCVMOperation> eccvm_ops_reconstructed;
 
    // Storage for the reconstructed ultra ops tables in contiguous memory. (Intended to be constructed once and for
    // all prior to Translator circuit construction to avoid repeated traversal of the per-subtable storage.)
    std::vector<UltraOp> ultra_ops_zk_reconstructed;    // Chonk table
    std::vector<UltraOp> ultra_ops_no_zk_reconstructed; // AVM table
 
    // Tracks number of muls and size of eccvm in real time as the op queue is updated
    EccvmRowTracker eccvm_row_tracker;
 
  public:
    static const size_t OP_QUEUE_SIZE = 1 << CONST_OP_QUEUE_LOG_SIZE;
    ECCOpQueue() { initialize_new_subtable(); }
 
    void initialize_new_subtable()
    {
        eccvm_ops_table.create_new_subtable();
        ultra_ops_table.create_new_subtable();
    }
 
    size_t num_subtables() const { return eccvm_ops_table.num_subtables(); }
 
    size_t get_current_subtable_size() const { return ultra_ops_table.get_current_subtable_size(); }
 
    size_t get_append_offset_for_prover() const { return get_append_offset(get_current_subtable_size()); }
    static size_t get_append_offset_for_verifier() { return get_append_offset(bb::HIDING_KERNEL_ULTRA_OPS); }
 
    // Shift size of the merge / row offset at which the fixed-append subtable's polynomial begins.
    // See UltraEccOpsTable::compute_fixed_append_offset.
    static constexpr size_t compute_fixed_append_offset(size_t append_offset, bool include_zk_prefix = true)
    {
        return UltraEccOpsTable::compute_fixed_append_offset(append_offset, include_zk_prefix);
    }
 
    void merge()
    {
        eccvm_ops_table.merge();
        ultra_ops_table.merge();
    }
 
    void merge_fixed_append(size_t ultra_fixed_offset)
    {
        eccvm_ops_table.merge();
        ultra_ops_table.merge_with_fixed_append_offset(ultra_fixed_offset);
    }
 
    std::array<Polynomial<Fr>, ULTRA_TABLE_WIDTH> construct_zk_columns()
    {
        auto [column_polynomials, hiding_op] = ultra_ops_table.construct_zk_columns();
        this->hiding_op_for_eccvm = hiding_op;
        this->has_hiding_op = true;
 
        return column_polynomials;
    }
 
    std::vector<std::array<Polynomial<Fr>, ULTRA_TABLE_WIDTH>> construct_subtable_columns() const
    {
        return ultra_ops_table.construct_subtable_columns();
    }
 
    // Construct column polynomials for the full aggregate ultra ops table
    std::array<Polynomial<Fr>, ULTRA_TABLE_WIDTH> construct_ultra_ops_table_columns(
        const bool include_zk_ops = true) const
    {
        return ultra_ops_table.construct_table_columns(include_zk_ops);
    }
 
    // Construct column polynomials for the aggregate table up to and including the tail subtable.
    std::array<Polynomial<Fr>, ULTRA_TABLE_WIDTH> construct_table_columns_up_to_tail() const
    {
        return ultra_ops_table.construct_table_columns_up_to_tail();
    }
 
    // Construct column polynomials for the most recently merged subtable
    std::array<Polynomial<Fr>, ULTRA_TABLE_WIDTH> construct_current_ultra_ops_subtable_columns() const
    {
        return ultra_ops_table.construct_current_ultra_ops_subtable_columns();
    }
 
    // Reconstruct the full table of eccvm ops in contiguous memory from the independent subtables
    void construct_full_eccvm_ops_table() { eccvm_ops_reconstructed = eccvm_ops_table.get_reconstructed(); }
 
    // Reconstruct the ZK-prefixed full table of ultra ops in contiguous memory from the independent subtables.
    void construct_zk_reconstructed_ultra_ops_table()
    {
        ultra_ops_zk_reconstructed = ultra_ops_table.get_zk_reconstructed_ultra_ops();
    }
 
    // Reconstruct the non-ZK full table of ultra ops in contiguous memory from the independent subtables.
    void construct_no_zk_reconstructed_ultra_ops_table()
    {
        ultra_ops_no_zk_reconstructed = ultra_ops_table.get_no_zk_reconstructed_ultra_ops();
    }
 
    // Excludes the optional ZK prefix; see UltraEccOpsTable::num_ultra_rows
    size_t get_ultra_ops_table_num_rows() const { return ultra_ops_table.num_ultra_rows(); }
    size_t get_ultra_ops_count() const { return ultra_ops_table.num_ops(); } // actual operation count without padding
    // Excludes the optional ZK prefix, same as get_ultra_ops_table_num_rows.
    size_t get_ultra_ops_table_num_rows_up_to_tail() const { return ultra_ops_table.ultra_table_size_up_to_tail(); }
 
    // Get the full table of ECCVM ops in contiguous memory; construct it if it has not been constructed already.
    // The hiding op is always prepended at index 0.
    std::vector<ECCVMOperation>& get_eccvm_ops()
    {
        if (eccvm_ops_reconstructed.empty()) {
            construct_full_eccvm_ops_table();
            // Prepend the hiding op at index 0 (required for ZK)
            if (!has_hiding_op) {
                throw_or_abort("Hiding op must be set before calling get_eccvm_ops()");
            }
            eccvm_ops_reconstructed.insert(eccvm_ops_reconstructed.begin(), hiding_op_for_eccvm);
        }
        return eccvm_ops_reconstructed;
    }
 
    std::vector<UltraOp>& get_no_zk_reconstructed_ultra_ops()
    {
        if (ultra_ops_no_zk_reconstructed.empty()) {
            construct_no_zk_reconstructed_ultra_ops_table();
        }
        return ultra_ops_no_zk_reconstructed;
    }
 
    std::vector<UltraOp>& get_zk_reconstructed_ultra_ops()
    {
        if (ultra_ops_zk_reconstructed.empty()) {
            construct_zk_reconstructed_ultra_ops_table();
        }
        return ultra_ops_zk_reconstructed;
    }
 
    size_t get_num_msm_rows() const { return eccvm_row_tracker.get_num_msm_rows(); }
 
    size_t get_num_rows() const { return eccvm_row_tracker.get_num_rows(); }
 
    uint32_t get_number_of_muls() const { return eccvm_row_tracker.get_number_of_muls(); }
 
    void set_eccvm_ops_for_fuzzing(std::vector<ECCVMOperation>& eccvm_ops_in)
    {
        eccvm_ops_reconstructed = eccvm_ops_in;
    }
 
    void add_erroneous_equality_op_for_testing()
    {
        EccOpCode op_code{ .eq = true, .reset = true };
        append_eccvm_op(ECCVMOperation{ .op_code = op_code, .base_point = Point::random_element() });
    }
 
    void empty_row_for_testing()
    {
        append_eccvm_op(ECCVMOperation{ .base_point = point_at_infinity });
        reset_accumulator();
    }
 
    Point get_accumulator()
    {
        flush_deferred_muls();
        return Point(accumulator);
    }
 
    UltraOp add_accumulate(const Point& to_add)
    {
        // Update the accumulator natively
        accumulator += to_add;
        EccOpCode op_code{ .add = true };
        // Store the eccvm operation
        append_eccvm_op(ECCVMOperation{ .op_code = op_code, .base_point = to_add });
 
        // Construct and store the operation in the ultra op format
        return construct_and_populate_ultra_ops(op_code, to_add);
    }
 
    UltraOp mul_accumulate(const Point& to_mul, const Fr& scalar)
    {
        BB_BENCH_NAME("ECCOpQueue::mul_accumulate");
        // Defer the native accumulator update; the buffered muls are folded in as a batch when the
        // accumulator is next read (see flush_deferred_muls).
        deferred_mul_points.push_back(to_mul);
        deferred_mul_scalars.push_back(scalar);
        EccOpCode op_code{ .mul = true };
 
        // Construct and store the operation in the ultra op format
        UltraOp ultra_op = construct_and_populate_ultra_ops(op_code, to_mul, scalar);
 
        // Store the eccvm operation
        append_eccvm_op(ECCVMOperation{
            .op_code = op_code,
            .base_point = to_mul,
            .z1 = ultra_op.z_1,
            .z2 = ultra_op.z_2,
            .mul_scalar_full = scalar,
        });
 
        return ultra_op;
    }
 
    UltraOp no_op_ultra_only()
    {
        UltraOp no_op{};
        ultra_ops_table.push(no_op);
        return no_op;
    }
 
    UltraOp random_op_ultra_only()
    {
        UltraOp random_op{ .op_code = EccOpCode{ .is_random_op = true,
                                                 .random_value_1 = Fr::random_element(),
                                                 .random_value_2 = Fr::random_element() },
                           .x_lo = Fr::random_element(),
                           .x_hi = Fr::random_element(),
                           .y_lo = Fr::random_element(),
                           .y_hi = Fr::random_element(),
                           .z_1 = Fr::random_element(),
                           .z_2 = Fr::random_element(),
                           .return_is_infinity = false };
        ultra_ops_table.push(random_op);
        return random_op;
    }
 
    UltraOp eq_and_reset()
    {
        const Point expected = get_accumulator();
        reset_accumulator();
        EccOpCode op_code{ .eq = true, .reset = true };
        // Store eccvm operation
        append_eccvm_op(ECCVMOperation{ .op_code = op_code, .base_point = expected });
 
        // Construct and store the operation in the ultra op format
        return construct_and_populate_ultra_ops(op_code, expected);
    }
 
    UltraOp append_hiding_op(const Fq& Px, const Fq& Py)
    {
        auto [ultra_op, eccvm_op] = UltraEccOpsTable::make_hiding_op_pair(Px, Py);
 
        hiding_op_for_eccvm = eccvm_op;
        has_hiding_op = true;
        ultra_ops_table.push(ultra_op);
 
        // Do NOT update the accumulator - the hiding op doesn't perform any actual EC computation
        return ultra_op;
    }
 
  private:
    static size_t get_append_offset(size_t current_subtable_size)
    {
        constexpr size_t reserved_op_slots = UltraEccOpsTable::APPEND_TRACE_OFFSET / UltraEccOpsTable::NUM_ROWS_PER_OP;
        constexpr size_t zk_op_slots = UltraEccOpsTable::ZK_ULTRA_OPS / UltraEccOpsTable::NUM_ROWS_PER_OP;
        return OP_QUEUE_SIZE - current_subtable_size - reserved_op_slots - zk_op_slots;
    }
 
    // === Hiding Op State ===
    // The hiding op exists in both the ECCVM and Ultra tables (same Px, Py values, opcode q_eq=q_reset=1) so the
    // translation check holds. It is set by exactly one of two entry points, depending on the proving flow:
    //   - Chonk: UltraEccOpsTable::construct_zk_columns() builds the full ZK prefix (1 no-op + 3 random + 1 hiding)
    //     at the front of the reconstructed Ultra table; the hiding op lands at index 4.
    //   - Goblin AVM: append_hiding_op() pushes the Ultra side into the current subtable directly, with no surrounding
    //     prefix.
    // In both cases the ECCVM side is stored here and prepended to the reconstructed ECCVM table at index 0 by
    // get_eccvm_ops(), placing it at row 1 (lagrange_second) where the on-curve and eq constraints are gated off
    // so that non-curve (x, y) values are accepted.
    ECCVMOperation hiding_op_for_eccvm;
    bool has_hiding_op = false;
 
    void append_eccvm_op(const ECCVMOperation& op)
    {
        eccvm_row_tracker.update_cached_msms(op);
        eccvm_ops_table.push(op);
    }
    UltraOp construct_and_populate_ultra_ops(EccOpCode op_code, const Point& point, const Fr& scalar = Fr::zero())
    {
        UltraOp ultra_op;
        ultra_op.op_code = op_code;
 
        // Decompose point coordinates (Fq) into hi-lo chunks (Fr)
        const size_t CHUNK_SIZE = 2 * stdlib::NUM_LIMB_BITS_IN_FIELD_SIMULATION;
        uint256_t x_256(point.x);
        uint256_t y_256(point.y);
        ultra_op.return_is_infinity = point.is_point_at_infinity();
        // if we have a point at infinity, set x/y to zero
        // in the biggroup_goblin class we use `assert_equal` statements to validate
        // the original in-circuit coordinate values are also zero
        if (point.is_point_at_infinity()) {
            x_256 = 0;
            y_256 = 0;
        }
        ultra_op.x_lo = Fr(x_256.slice(0, CHUNK_SIZE));
        ultra_op.x_hi = Fr(x_256.slice(CHUNK_SIZE, CHUNK_SIZE * 2));
        ultra_op.y_lo = Fr(y_256.slice(0, CHUNK_SIZE));
        ultra_op.y_hi = Fr(y_256.slice(CHUNK_SIZE, CHUNK_SIZE * 2));
 
        // Split scalar into 128 bit endomorphism scalars
        Fr z_1 = 0;
        Fr z_2 = 0;
        auto converted = scalar.from_montgomery_form();
        uint256_t converted_u256(scalar);
        // if our scalar is small, don't split.
        if (converted_u256.get_msb() < 128) {
            ultra_op.z_1 = scalar;
            ultra_op.z_2 = 0;
        } else {
            Fr::split_into_endomorphism_scalars(converted, z_1, z_2);
            ultra_op.z_1 = z_1.to_montgomery_form();
            ultra_op.z_2 = z_2.to_montgomery_form();
        }
 
        ultra_ops_table.push(ultra_op);
 
        return ultra_op;
    }
};
 
} // namespace bb