ultra_circuit_builder.hpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: Complete, auditors: [Luke, Raju], commit: }
// external_1:  { status: not started, auditors: [], commit: }
// external_2:  { status: not started, auditors: [], commit: }
// =====================
 
#pragma once
#include "barretenberg/common/assert.hpp"
#include "barretenberg/honk/execution_trace/mega_execution_trace.hpp"
#include "barretenberg/honk/execution_trace/ultra_execution_trace.hpp"
#include "barretenberg/stdlib_circuit_builders/plookup_tables/plookup_tables.hpp"
#include "barretenberg/stdlib_circuit_builders/plookup_tables/types.hpp"
 
#include "circuit_builder_base.hpp"
#include "rom_ram_logic.hpp"
#include <deque>
#include <optional>
#include <unordered_set>
 
#include "barretenberg/serialize/msgpack.hpp"
 
namespace bb {
 
template <typename FF> struct non_native_multiplication_witnesses {
    // first 4 array elements = limbs
    std::array<uint32_t, 4> a;
    std::array<uint32_t, 4> b;
    std::array<uint32_t, 4> q;
    std::array<uint32_t, 4> r;
    std::array<FF, 4> neg_modulus;
};
 
template <typename FF> struct non_native_partial_multiplication_witnesses {
    // first 4 array elements = limbs
    std::array<uint32_t, 4> a;
    std::array<uint32_t, 4> b;
};
 
template <typename ExecutionTrace_>
class UltraCircuitBuilder_ : public CircuitBuilderBase<typename ExecutionTrace_::FF> {
  public:
    using ExecutionTrace = ExecutionTrace_;
    using FF = typename ExecutionTrace::FF;
    using RomRamLogic = RomRamLogic_<ExecutionTrace>;
 
    static constexpr size_t NUM_WIRES = ExecutionTrace::NUM_WIRES;
 
    static constexpr std::string_view NAME_STRING = "UltraCircuitBuilder";
    // The plookup-style range proof requires work linear in range size, thus cannot be used directly for
    // large ranges such as 2^64. For such ranges the element will be decomposed into smaller
    // chuncks according to the parameter below
    static constexpr size_t DEFAULT_PLOOKUP_RANGE_BITNUM = 14;
    static constexpr size_t DEFAULT_PLOOKUP_RANGE_STEP_SIZE = 3;
    static constexpr size_t DEFAULT_PLOOKUP_RANGE_SIZE = (1 << DEFAULT_PLOOKUP_RANGE_BITNUM) - 1;
    static constexpr size_t DEFAULT_NON_NATIVE_FIELD_LIMB_BITS = 68;
    // We offer two types of range constraints: small (which can be non-dyadic) and general. The below constants
    // determine their max values.
    static constexpr size_t MAX_SMALL_RANGE_CONSTRAINT_VAL = (1 << 16) - 1;
    static constexpr size_t MAX_NUM_BITS_RANGE_CONSTRAINT =
        253; // the Grumpkin scalar field modulus is between 2^253 and 2^254 and has 254 bits. Therefore the largest
             // non-vacuous dyadic range-constraint we can enforce is 2^253 - 1, i.e., `num_bits == 253`.
    enum MEMORY_SELECTORS {
        MEM_NONE,
        RAM_CONSISTENCY_CHECK,
        ROM_CONSISTENCY_CHECK,
        RAM_TIMESTAMP_CHECK,
        ROM_READ,
        RAM_READ,
        RAM_WRITE,
        ROM_LOGUP_TABLE, // single-value ROM table entry (LogUp scheme)
        ROM_LOGUP_READ,  // single-value ROM read access (LogUp scheme)
    };
 
    enum NNF_SELECTORS {
        NNF_NONE,
        LIMB_ACCUMULATE_1,
        LIMB_ACCUMULATE_2,
        NON_NATIVE_FIELD_1,
        NON_NATIVE_FIELD_2,
        NON_NATIVE_FIELD_3,
    };
 
    struct RangeList {
        uint64_t target_range; // range constraint will be for the range [0, target_range], i.e., is inclusive of
                               // `target_range`.
        uint32_t range_tag;    // Every variable that is range-constrained to a given `target_range` has the same tag,
                               // namely, `range_tag`. Never `DEFAULT_TAG`.
        uint32_t tau_tag;      // Tag assigned to the sorted reference set. Never `DEFAULT_TAG`.
        std::vector<uint32_t>
            variable_indices; // All variable-indices constrained to this range. During processing, this will be
                              // mutated: replaced by real-variable-indices, then deduplicated.
        bool operator==(const RangeList& other) const noexcept
        {
            return target_range == other.target_range && range_tag == other.range_tag && tau_tag == other.tau_tag &&
                   variable_indices == other.variable_indices;
        }
    };
 
    // AUDITTODO: this is not a large optimization (~0.5% reduction for ultra rec verifier); consider removing
    struct cached_partial_non_native_field_multiplication {
        std::array<uint32_t, 4> a;
        std::array<uint32_t, 4> b;
        uint32_t lo_0;
        uint32_t hi_0;
        uint32_t hi_1;
 
        bool operator==(const cached_partial_non_native_field_multiplication& other) const
        {
            bool valid = true;
            for (size_t i = 0; i < 4; ++i) {
                valid = valid && (a[i] == other.a[i]);
                valid = valid && (b[i] == other.b[i]);
            }
            return valid;
        }
 
        static void deduplicate(std::vector<cached_partial_non_native_field_multiplication>& vec,
                                UltraCircuitBuilder_<ExecutionTrace>* circuit_builder)
        {
            std::unordered_set<cached_partial_non_native_field_multiplication, Hash, std::equal_to<>> seen;
 
            std::vector<cached_partial_non_native_field_multiplication> uniqueVec;
 
            for (const auto& item : vec) {
                auto [existing_element, not_in_set] = seen.insert(item);
                // Memorize if not in set yet
                if (not_in_set) {
                    uniqueVec.push_back(item);
                } else {
                    // If we already have a representative, we need to connect the outputs together
                    circuit_builder->assert_equal(item.lo_0, (*existing_element).lo_0);
                    circuit_builder->assert_equal(item.hi_0, (*existing_element).hi_0);
                    circuit_builder->assert_equal(item.hi_1, (*existing_element).hi_1);
                }
            }
 
            vec.swap(uniqueVec);
        }
 
        bool operator<(const cached_partial_non_native_field_multiplication& other) const
        {
            if (a < other.a) {
                return true;
            }
            if (other.a < a) {
                return false;
            }
            if (b < other.b) {
                return true;
            }
            return other.b < b;
        }
 
        struct Hash {
            size_t operator()(const cached_partial_non_native_field_multiplication& obj) const
            {
                size_t combined_hash = 0;
 
                // C++ does not have a standard way to hash values, so we use the
                // common algorithm that boot uses.
                // You can search for 'cpp hash_combine' to find more information.
                // Here is one reference:
                // https://stackoverflow.com/questions/2590677/how-do-i-combine-hash-values-in-c0x
                auto hash_combiner = [](size_t lhs, size_t rhs) {
                    return lhs ^ (rhs + 0x9e3779b9 + (lhs << 6) + (lhs >> 2));
                };
 
                for (const auto& elem : obj.a) {
                    combined_hash = hash_combiner(combined_hash, std::hash<uint32_t>()(elem));
                }
                for (const auto& elem : obj.b) {
                    combined_hash = hash_combiner(combined_hash, std::hash<uint32_t>()(elem));
                }
 
                return combined_hash;
            }
        };
    };
 
  private:
    // The set of lookup tables used by the circuit, plus the gate data for the lookups from each table
    std::deque<plookup::BasicTable> lookup_tables;
 
  public:
    // Storage for wires and selectors for all gate types
    ExecutionTrace blocks;
 
    // The set of variables which have been constrained to a particular value via an arithmetic gate
    std::unordered_map<FF, uint32_t> constant_variable_indices;
 
    // Rom/Ram logic
    RomRamLogic rom_ram_logic;
 
    // Stores gate index of ROM/RAM reads (required by proving key)
    std::vector<uint32_t> memory_read_records;
    // Stores gate index of RAM writes (required by proving key)
    std::vector<uint32_t> memory_write_records;
    // Stores gate index of ROM-LogUp rows (both table-entry and read-access)
    std::vector<uint32_t> rom_logup_records;
    // Range constraints to be batched, keyed by target_range. See create_small_range_constraint() for details.
    std::map<uint64_t, RangeList> range_lists;
 
    std::vector<cached_partial_non_native_field_multiplication> cached_partial_non_native_field_multiplications;
 
    std::vector<fr> ipa_proof;
 
    void populate_public_inputs_block();
 
    void process_non_native_field_multiplications();
 
    UltraCircuitBuilder_(bool is_write_vk_mode = false)
        : CircuitBuilderBase<FF>(is_write_vk_mode)
    {
        this->set_zero_idx(put_constant_variable(FF::zero()));
        // The identity permutation on the set `{DEFAULT_TAG}`. We therefore assume that the
        // `DEFAULT_TAG` is not involved in any non-trivial multiset-equality checks.
        this->set_tau_at_index(DEFAULT_TAG, DEFAULT_TAG);
    };
 
    UltraCircuitBuilder_(const std::vector<FF>& witness_values,
                         const std::vector<uint32_t>& public_inputs,
                         const bool is_write_vk_mode)
        : CircuitBuilderBase<FF>(is_write_vk_mode)
    {
        // Real (ACIR) circuits create far more variables than the witness count (limb
        // decompositions, gadget internals — typically 4-40x); reserve generously so the
        // per-variable bookkeeping vectors do not repeatedly reallocate during construction.
        // 4x keeps the transient over-allocation for large-witness circuits within a few MB.
        constexpr size_t VARIABLES_PER_ACIR_WITNESS_HINT = 4;
        constexpr size_t MIN_VARIABLES_RESERVE = 1 << 16;
        this->reserve_variables(
            std::max(witness_values.size() * VARIABLES_PER_ACIR_WITNESS_HINT, MIN_VARIABLES_RESERVE));
        for (const auto value : witness_values) {
            this->add_variable(value);
        }
 
        // Initialize the builder public_inputs directly from the acir public inputs.
        this->initialize_public_inputs(public_inputs);
 
        // Add the const zero variable after the acir witness has been
        // incorporated into variables.
        this->set_zero_idx(put_constant_variable(FF::zero()));
        this->set_tau_at_index(DEFAULT_TAG,
                               DEFAULT_TAG); // tau fixes the `DEFAULT_TAG`, as we assume that `DEFAULT_TAG` is not
                                             // involved in any non-trivial multiset-equality checks.
    };
    UltraCircuitBuilder_(const UltraCircuitBuilder_& other) = default;
    UltraCircuitBuilder_(UltraCircuitBuilder_&& other) = default;
    UltraCircuitBuilder_& operator=(const UltraCircuitBuilder_& other) = default;
    UltraCircuitBuilder_& operator=(UltraCircuitBuilder_&& other) = default;
    ~UltraCircuitBuilder_() override = default;
 
    void finalize_circuit();
 
    void create_add_gate(const add_triple_<FF>& in);
    void create_big_mul_add_gate(const mul_quad_<FF>& in, const bool use_next_gate_w_4 = false);
    void create_big_add_gate(const add_quad_<FF>& in, const bool use_next_gate_w_4 = false);
    void create_bilinear_batched_eq_gate(const bilinear_batched_eq_gate_<FF>& in);
 
    void create_bool_gate(const uint32_t a);
    void create_arithmetic_gate(const arithmetic_triple_<FF>& in);
    void create_ecc_add_gate(const ecc_add_gate_& in);
    void create_ecc_dbl_gate(const ecc_dbl_gate_<FF>& in);
 
    void fix_witness(const uint32_t witness_index, const FF& witness_value);
 
    void create_small_range_constraint(const uint32_t variable_index,
                                       const uint64_t target_range,
                                       std::string_view msg = "create_small_range_constraint");
 
    void create_dyadic_range_constraint(const uint32_t variable_index, const size_t num_bits, std::string_view msg)
    {
        if (num_bits == 1) {
            create_bool_gate(variable_index);
        } else if (num_bits <= DEFAULT_PLOOKUP_RANGE_BITNUM) {
            // Add an unconstrained gate to ensure variable_index appears in a wire. (See warning in
            // `create_small_range_constraint` for more details.)
            create_unconstrained_gate(
                blocks.arithmetic, variable_index, this->zero_idx(), this->zero_idx(), this->zero_idx());
            create_small_range_constraint(variable_index, (1ULL << num_bits) - 1, msg);
        } else {
            create_limbed_range_constraint(variable_index, num_bits, DEFAULT_PLOOKUP_RANGE_BITNUM, msg);
        }
    }
 
    uint32_t put_constant_variable(const FF& variable);
 
    size_t get_num_constant_gates() const override { return 0; }
 
    size_t get_num_finalized_gates() const override
    {
        BB_ASSERT(this->circuit_finalized);
        return this->num_gates();
    }
 
    size_t get_num_finalized_gates_inefficient() const
    {
        UltraCircuitBuilder_ builder_copy = *this;
        builder_copy.finalize_circuit();
        return builder_copy.get_num_finalized_gates();
    }
 
    size_t get_tables_size() const
    {
        size_t tables_size = 0;
        for (const auto& table : lookup_tables) {
            tables_size += table.size();
        }
        return tables_size;
    }
 
    size_t get_finalized_total_circuit_size() const
    {
        BB_ASSERT(this->circuit_finalized);
        auto num_filled_gates = get_num_finalized_gates() + this->num_public_inputs();
        return std::max(get_tables_size(), num_filled_gates);
    }
 
    void assert_equal_constant(const uint32_t a_idx, const FF& b, std::string const& msg = "assert equal constant")
    {
        if (this->get_variable(a_idx) != b && !this->failed()) {
            this->failure(msg);
        }
        auto b_idx = put_constant_variable(b);
        this->assert_equal(a_idx, b_idx, msg);
    }
 
    plookup::BasicTable& get_table(const plookup::BasicTableId id);
    plookup::MultiTable& get_multitable(const plookup::MultiTableId id);
 
    // Accessors for lookup tables
    const std::deque<plookup::BasicTable>& get_lookup_tables() const { return lookup_tables; }
    std::deque<plookup::BasicTable>& get_lookup_tables() { return lookup_tables; }
    size_t get_num_lookup_tables() const { return lookup_tables.size(); }
 
    plookup::BasicTable* register_basic_lookup_table(plookup::BasicTable&& table);
 
    void create_lookup_gate(uint32_t key_idx,
                            uint32_t val1_idx,
                            uint32_t val2_idx,
                            plookup::BasicTable& table,
                            const plookup::BasicTable::LookupEntry& entry,
                            FF column_1_step_size = 0,
                            FF column_2_step_size = 0,
                            FF column_3_step_size = 0);
 
    plookup::ReadData<uint32_t> create_gates_from_plookup_accumulators(
        const plookup::MultiTableId& id,
        const plookup::ReadData<FF>& read_values,
        const uint32_t key_a_index,
        std::optional<uint32_t> key_b_index = std::nullopt);
 
    std::vector<uint32_t> create_limbed_range_constraint(
        const uint32_t variable_index,
        const uint64_t num_bits,
        const uint64_t target_range_bitnum = DEFAULT_PLOOKUP_RANGE_BITNUM,
        std::string_view msg = "create_limbed_range_constraint");
 
    void create_unconstrained_gate(
        auto& block, const uint32_t& idx_1, const uint32_t& idx_2, const uint32_t& idx_3, const uint32_t& idx_4)
    {
        block.append_gate({ .wires = { idx_1, idx_2, idx_3, idx_4 } });
        this->increment_num_gates();
    }
    void create_unconstrained_gates(const std::vector<uint32_t>& variable_index);
 
    void enforce_small_deltas(const std::vector<uint32_t>& variable_indices);
    void create_sort_constraint_with_edges(const std::vector<uint32_t>& variable_indices,
                                           const FF& start,
                                           const FF& end);
 
    void assign_tag(const uint32_t variable_index, const uint32_t tag)
    {
        BB_ASSERT_LTE(tag, this->_current_tag);
        // If we've already assigned this tag to this variable, return (can happen due to copy constraints)
        if (this->real_variable_tags[this->real_variable_index[variable_index]] == tag) {
            return;
        }
 
        BB_ASSERT_EQ(this->real_variable_tags[this->real_variable_index[variable_index]], DEFAULT_TAG);
        this->real_variable_tags[this->real_variable_index[variable_index]] = tag;
    }
    void set_tau_at_index(const uint32_t tag_index, const uint32_t tau_index)
    {
        auto [it, inserted] = this->_tau.insert({ tag_index, tau_index });
        BB_ASSERT_DEBUG(inserted, "tag reuse detected");
    }
    void set_tau_transposition(const uint32_t tag_index_1, const uint32_t tag_index_2)
    {
        set_tau_at_index(tag_index_1, tag_index_2);
        set_tau_at_index(tag_index_2, tag_index_1);
    }
 
    uint32_t get_new_tag()
    {
        this->_current_tag++;
        return this->_current_tag;
    }
 
    RangeList create_range_list(const uint64_t target_range);
    void process_range_list(RangeList& list);
    void process_range_lists();
 
    using GateRowT = GateRow<FF, ExecutionTrace::NUM_WIRES>;
    // Build the selector/gate-kind part of a memory or nnf gate row; the caller fills in the wires
    // and appends the completed row.
    GateRowT memory_selectors_row(const MEMORY_SELECTORS type) const;
    GateRowT nnf_selectors_row(const NNF_SELECTORS type) const;
 
    void range_constrain_two_limbs(const uint32_t lo_idx,
                                   const uint32_t hi_idx,
                                   const size_t lo_limb_bits = DEFAULT_NON_NATIVE_FIELD_LIMB_BITS,
                                   const size_t hi_limb_bits = DEFAULT_NON_NATIVE_FIELD_LIMB_BITS,
                                   std::string_view msg = "range_constrain_two_limbs");
    std::array<uint32_t, 2> evaluate_non_native_field_multiplication(
        const non_native_multiplication_witnesses<FF>& input);
    std::array<uint32_t, 2> queue_partial_non_native_field_multiplication(
        const non_native_partial_multiplication_witnesses<FF>& input);
    using scaled_witness = std::pair<uint32_t, FF>;
    using add_simple = std::tuple<scaled_witness, scaled_witness, FF>;
    std::array<uint32_t, 5> evaluate_non_native_field_subtraction(add_simple limb0,
                                                                  add_simple limb1,
                                                                  add_simple limb2,
                                                                  add_simple limb3,
                                                                  std::tuple<uint32_t, uint32_t, FF> limbp);
    std::array<uint32_t, 5> evaluate_non_native_field_addition(add_simple limb0,
                                                               add_simple limb1,
                                                               add_simple limb2,
                                                               add_simple limb3,
                                                               std::tuple<uint32_t, uint32_t, FF> limbp);
 
    size_t create_ROM_array(const size_t array_size);
    void set_ROM_element(const size_t rom_id, const size_t index_value, const uint32_t value_witness);
    void set_ROM_element_pair(const size_t rom_id,
                              const size_t index_value,
                              const std::array<uint32_t, 2>& value_witnesses);
 
    uint32_t read_ROM_array(const size_t rom_id, const uint32_t index_witness);
    std::array<uint32_t, 2> read_ROM_array_pair(const size_t rom_id, const uint32_t index_witness);
 
    size_t create_RAM_array(const size_t array_size);
    void init_RAM_element(const size_t ram_id, const size_t index_value, const uint32_t value_witness);
 
    uint32_t read_RAM_array(const size_t ram_id, const uint32_t index_witness);
    void write_RAM_array(const size_t ram_id, const uint32_t index_witness, const uint32_t value_witness);
 
    void create_poseidon2_external_gate(const poseidon2_external_gate_<FF>& in);
    void create_poseidon2_internal_gate(const poseidon2_internal_gate_<FF>& in);
 
    // ========================================================================================
    // TOOLING: Boomerang Detection
    // ========================================================================================
    // The boomerang mechanism enables detection of variables used in only one gate, which may
    // indicate bugs.
    // Note: some patterns (like x*(x^-1)=1 for non-zero checks) intentionally employ single-use witnesses. These
    // members and methods allow excluding such witnesses from boomerang detection.
 
  private:
    // Witnesses that can be in one gate, but that's intentional (used in boomerang catcher)
    std::vector<uint32_t> used_witnesses;
    // Witnesses that appear in finalize method (used in boomerang catcher). Need to check
    // that all variables from some connected component were created after finalize method was called
    std::unordered_set<uint32_t> finalize_witnesses;
 
  public:
    const std::vector<uint32_t>& get_used_witnesses() const { return used_witnesses; }
    const std::unordered_set<uint32_t>& get_finalize_witnesses() const { return finalize_witnesses; }
 
    void update_used_witnesses(uint32_t var_idx) { used_witnesses.emplace_back(var_idx); }
 
    void update_used_witnesses(const std::vector<uint32_t>& used_indices)
    {
        used_witnesses.reserve(used_witnesses.size() + used_indices.size());
        for (const auto& it : used_indices) {
            used_witnesses.emplace_back(it);
        }
    }
 
    void update_finalize_witnesses(uint32_t var_idx) { finalize_witnesses.insert(var_idx); }
 
    void update_finalize_witnesses(const std::vector<uint32_t>& finalize_indices)
    {
        for (const auto& it : finalize_indices) {
            finalize_witnesses.insert(it);
        }
    }
 
    // ========================================================================================
 
    msgpack::sbuffer export_circuit();
};
using UltraCircuitBuilder = UltraCircuitBuilder_<UltraExecutionTraceBlocks>;
} // namespace bb