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/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
    Point accumulator = point_at_infinity;
 
    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 prepending of subtables in physical memory).
    std::vector<ECCVMOperation> eccvm_ops_reconstructed;
 
    // Storage for the reconstructed ultra ops table in contiguous memory. (Intended to be constructed once and for all
    // prior to Translator circuit construction to avoid repeated prepending of subtables in physical memory).
    std::vector<UltraOp> ultra_ops_reconstructed;
 
    // 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 get_current_subtable_size() const { return ultra_ops_table.get_current_subtable_size(); }
 
    void merge(MergeSettings settings = MergeSettings::PREPEND, std::optional<size_t> ultra_fixed_offset = std::nullopt)
    {
        eccvm_ops_table.merge(settings);
        ultra_ops_table.merge(settings, ultra_fixed_offset);
    }
 
    // Construct polynomials corresponding to the columns of the full aggregate ultra ecc ops table
    std::array<Polynomial<Fr>, ULTRA_TABLE_WIDTH> construct_ultra_ops_table_columns() const
    {
        return ultra_ops_table.construct_table_columns();
    }
 
    // Construct polys corresponding to the columns of the aggregate ultra ops table, excluding the most recent
    // subtable
    std::array<Polynomial<Fr>, ULTRA_TABLE_WIDTH> construct_previous_ultra_ops_table_columns() const
    {
        return ultra_ops_table.construct_previous_table_columns();
    }
 
    // Construct polynomials corresponding to the columns of the current subtable of ultra ecc ops
    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 full table of ultra ops in contiguous memory from the independent subtables
    void construct_full_ultra_ops_table() { ultra_ops_reconstructed = ultra_ops_table.get_reconstructed(); }
 
    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
    size_t get_current_ultra_ops_subtable_num_rows() const { return ultra_ops_table.current_ultra_subtable_size(); }
    size_t get_previous_ultra_ops_table_num_rows() const { return ultra_ops_table.previous_ultra_table_size(); }
 
    // TODO(https://github.com/AztecProtocol/barretenberg/issues/1339): Consider making the ultra and eccvm ops
    // getters more memory efficient
 
    // Get the full table of ECCVM ops in contiguous memory; construct it if it has not been constructed already.
    // The hiding op (set via append_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_ultra_ops()
    {
        if (ultra_ops_reconstructed.empty()) {
            construct_full_ultra_ops_table();
        }
        return ultra_ops_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 });
        accumulator.self_set_infinity();
    }
 
    Point get_accumulator() { return accumulator; }
 
    UltraOp add_accumulate(const Point& to_add)
    {
        // Update the accumulator natively
        accumulator = 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)
    {
        // Update the accumulator natively
        accumulator = accumulator + to_mul * 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()
    {
        auto expected = accumulator;
        accumulator.self_set_infinity();
        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)
    {
        // Create an ECCVM operation with q_eq = 1, q_reset = 1 (opcode = 3) and the random Px, Py values.
        // We construct the base_point directly with the raw coordinates - it may not be on the curve.
        // Note: reset = true is required for Translator compatibility (only opcodes {0,3,4,8} are allowed)
        EccOpCode op_code{ .eq = true, .reset = true }; // q_eq = 1, q_reset = 1
        Point base_point;
        base_point.x = Px;
        base_point.y = Py;
        // Note: We don't call is_point_at_infinity() or any curve operations on this point
 
        // Store the hiding op for ECCVM - it will be prepended to the front during reconstruction (index 0 -> row 1)
        hiding_op_for_eccvm = ECCVMOperation{ .op_code = op_code, .base_point = base_point };
        has_hiding_op = true;
 
        // Push to Ultra ops through normal flow (appends to current subtable)
        // Decompose Px, Py (Fq) into hi-lo chunks (Fr)
        const size_t CHUNK_SIZE = 2 * stdlib::NUM_LIMB_BITS_IN_FIELD_SIMULATION;
        uint256_t x_256(Px);
        uint256_t y_256(Py);
        UltraOp ultra_op{
            .op_code = op_code,
            .x_lo = Fr(x_256.slice(0, CHUNK_SIZE)),
            .x_hi = Fr(x_256.slice(CHUNK_SIZE, CHUNK_SIZE * 2)),
            .y_lo = Fr(y_256.slice(0, CHUNK_SIZE)),
            .y_hi = Fr(y_256.slice(CHUNK_SIZE, CHUNK_SIZE * 2)),
            .z_1 = Fr(0),
            .z_2 = Fr(0),
            .return_is_infinity = false,
        };
        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:
    // === Hiding Op State ===
    // The hiding op is handled asymmetrically but ends up at the same functional relative position in both:
    // - ECCVM: Stored here and prepended at index 0 during get_eccvm_ops() reconstruction
    // - Ultra: Pushed to ultra_ops_table at index 4 (after 1 no-op + 3 random padding ops)
    //
    // Both end up with hiding op as the first "real" op because:
    // - ECCVM: prepending puts it at index 0; padding ops don't exist in ECCVM table
    // - Translator: skips first 4 Ultra ops (padding), so accumulation starts at the hiding op
    //
    // This alignment is required for the translation check (ECCVM and Translator must compute
    // the same accumulated_result). ECCVM places it at row 1 (lagrange_second) where on-curve
    // and eq constraints are gated off, allowing non-curve (x, y) values.
    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