ultra_circuit_checker.hpp

Go to the documentation of this file.

#pragma once
#include "barretenberg/flavor/ultra_flavor.hpp"
#include "barretenberg/relations/bilinear_or_batched_eq_check_relation.hpp"
#include "barretenberg/relations/delta_range_constraint_relation.hpp"
#include "barretenberg/relations/ecc_op_queue_relation.hpp"
#include "barretenberg/relations/elliptic_relation.hpp"
#include "barretenberg/relations/memory_relation.hpp"
#include "barretenberg/relations/non_native_field_relation.hpp"
#include "barretenberg/relations/poseidon2_external_relation.hpp"
#include "barretenberg/relations/poseidon2_initial_external_relation.hpp"
#include "barretenberg/relations/poseidon2_internal_relation.hpp"
#include "barretenberg/relations/poseidon2_quad_internal_relation.hpp"
#include "barretenberg/relations/poseidon2_quad_internal_terminal_relation.hpp"
#include "barretenberg/relations/poseidon2_transition_entry_relation.hpp"
#include "barretenberg/relations/relation_parameters.hpp"
#include "barretenberg/relations/ultra_arithmetic_relation.hpp"
#include "barretenberg/stdlib_circuit_builders/ultra_circuit_builder.hpp"
 
#include <optional>
 
namespace bb {
 
class UltraCircuitChecker {
  public:
    using FF = bb::fr;
    using Arithmetic = ArithmeticRelation<FF>;
    using BilinearBatchedEq = BilinearOrBatchedEqCheckRelation<FF>;
    using Elliptic = EllipticRelation<FF>;
    using Memory = MemoryRelation<FF>;
    using NonNativeField = NonNativeFieldRelation<FF>;
    using DeltaRangeConstraint = DeltaRangeConstraintRelation<FF>;
    using PoseidonExternal = Poseidon2ExternalRelation<FF>;
    using PoseidonInitialExternal = Poseidon2InitialExternalRelation<FF>;
    using PoseidonInternal = Poseidon2InternalRelation<FF>;
    using PoseidonQuadInternal = Poseidon2QuadInternalRelation<FF>;
    using PoseidonQuadInternalTerminal = Poseidon2QuadInternalTerminalRelation<FF>;
    using PoseidonTransitionEntry = Poseidon2TransitionEntryRelation<FF>;
    using Params = RelationParameters<FF>;
 
    template <typename Builder> static bool check(const Builder& builder_in);
 
    template <typename Relation, typename Builder, typename Block>
    static bool check_relation_at_row(Builder& builder, Block& block, size_t row_idx);
 
  private:
    struct TagCheckData;           // Container for data pertaining to generalized permutation tag check
    struct MemoryCheckData;        // Container for data pertaining to RAM/RAM record check
    using Key = std::array<FF, 4>; // Key type for lookup table hash table
    struct HashFunction;           // Custom hash function for lookup table hash table
    using LookupHashTable = std::unordered_set<Key, HashFunction>;
 
    template <typename Builder> static Builder prepare_circuit(const Builder& builder_in);
 
    template <typename Builder>
    static bool check_block(Builder& builder,
                            auto& block,
                            TagCheckData& tag_data,
                            MemoryCheckData& memory_data,
                            LookupHashTable& lookup_hash_table);
 
#ifdef ULTRA_FUZZ
    template <typename Builder> static bool relaxed_check_memory_relation(Builder& builder);
    template <typename Builder> static bool relaxed_check_delta_range_relation(Builder& builder);
#endif
 
    template <typename Relation> static bool check_relation(auto& values, auto& params);
 
    // Variant of `check_relation` for MemoryRelation. Per-row linearly-independent subrelations are checked
    // immediately; linearly-dependent subrelation contributions (the ROM-LogUp sum identity) are summed into
    // `memory_data.rom_logup_sum` for a final cross-row check.
    template <typename Memory>
    static bool check_memory_relation_with_logup(auto& values, auto& params, MemoryCheckData& memory_data);
 
    static bool check_lookup(auto& values, auto& lookup_hash_table);
 
    template <typename Builder> static bool check_databus_read(auto& values, Builder& builder);
 
    static bool check_tag_data(const TagCheckData& tag_data);
 
    template <typename Builder> static auto init_empty_values();
 
    template <typename Builder>
    static void populate_values(
        Builder& builder, auto& block, auto& values, TagCheckData& tag_data, MemoryCheckData& memory_data, size_t idx);
 
    struct TagCheckData {
        FF left_product = FF::one();           // product of (value + γ ⋅ tag)
        FF right_product = FF::one();          // product of (value + γ ⋅ tau[tag])
        const FF gamma = FF::random_element(); // randomness for the tag check
 
        // We need to include each variable only once
        std::unordered_set<size_t> encountered_variables;
    };
 
    struct MemoryCheckData {
        // randomness for constructing wire 4 mem records (eta powers and rom logup gamma)
        FF eta = FF::random_element();
        FF eta_two = eta * eta;       // eta²
        FF eta_three = eta_two * eta; // eta³
        FF rom_logup_gamma = FF::random_element();
 
        std::unordered_set<size_t> read_record_gates;  // row indices for gates containing RAM/ROM read mem record
        std::unordered_set<size_t> write_record_gates; // row indices for gates containing RAM/ROM write mem record
        std::unordered_set<size_t> rom_logup_gates;    // row indices for ROM-LogUp table-entry or read-access gates
        // Accumulator for MemoryRelation's linearly-dependent subrelation 7 (ROM-LogUp sum identity). Summed
        // across all rows by check_block; checked == 0 at the end of check_circuit.
        FF rom_logup_sum = 0;
        // Construct hash tables for memory read/write indices to efficiently determine if row is a memory record
        MemoryCheckData(const auto& builder)
        {
            for (const auto& gate_idx : builder.memory_read_records) {
                read_record_gates.insert(gate_idx);
            }
            for (const auto& gate_idx : builder.memory_write_records) {
                write_record_gates.insert(gate_idx);
            }
            for (const auto& gate_idx : builder.rom_logup_records) {
                rom_logup_gates.insert(gate_idx);
            }
        }
    };
 
    // Hash for lookups hash table for efficiently checking if lookups are present in set of tables used by circuit
    struct HashFunction {
        const FF mult_const = FF(uint256_t(0x1337, 0x1336, 0x1335, 0x1334));
        const FF mc_sqr = mult_const.sqr();
        const FF mc_cube = mult_const * mc_sqr;
 
        size_t operator()(const Key& entry) const
        {
            FF result = entry[0] + mult_const * entry[1] + mc_sqr * entry[2] + mc_cube * entry[3];
            return static_cast<size_t>(result.reduce_once().data[0]);
        }
    };
};
 
} // namespace bb