relation_correctness.test.cpp

Go to the documentation of this file.

#include "barretenberg/flavor/mega_flavor.hpp"
#include "barretenberg/flavor/ultra_flavor.hpp"
#include "barretenberg/honk/library/grand_product_library.hpp"
#include "barretenberg/honk/relation_checker.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/logderiv_lookup_relation.hpp"
#include "barretenberg/relations/memory_relation.hpp"
#include "barretenberg/relations/non_native_field_relation.hpp"
#include "barretenberg/relations/permutation_relation.hpp"
#include "barretenberg/relations/relation_parameters.hpp"
#include "barretenberg/relations/ultra_arithmetic_relation.hpp"
#include "barretenberg/stdlib/hash/poseidon2/poseidon2.hpp"
#include "barretenberg/stdlib/primitives/bigfield/bigfield.hpp"
#include "barretenberg/stdlib/primitives/pairing_points.hpp"
#include "barretenberg/stdlib/special_public_inputs/special_public_inputs.hpp"
#include "barretenberg/stdlib_circuit_builders/plookup_tables/fixed_base/fixed_base.hpp"
#include "barretenberg/ultra_honk/prover_instance.hpp"
#include "barretenberg/ultra_honk/witness_computation_test_utils.hpp"
 
#include <gtest/gtest.h>
using namespace bb;
 
void ensure_non_zero(auto& polynomial)
{
    bool has_non_zero_coefficient = false;
    for (auto& coeff : polynomial.coeffs()) {
        has_non_zero_coefficient |= !coeff.is_zero();
    }
    ASSERT_TRUE(has_non_zero_coefficient);
}
 
template <typename Flavor> void create_some_add_gates(auto& circuit_builder)
{
    using FF = typename Flavor::FF;
    auto a = FF::random_element();
 
    // Add some basic add gates; incorporate a public input for non-trivial PI-delta
    uint32_t a_idx = circuit_builder.add_public_variable(a);
    FF b = FF::random_element();
    FF c = a + b;
    FF d = a + c;
    uint32_t b_idx = circuit_builder.add_variable(b);
    uint32_t c_idx = circuit_builder.add_variable(c);
    uint32_t d_idx = circuit_builder.add_variable(d);
    for (size_t i = 0; i < 16; i++) {
        circuit_builder.create_add_gate({ a_idx, b_idx, c_idx, 1, 1, -1, 0 });
        circuit_builder.create_add_gate({ d_idx, c_idx, a_idx, 1, -1, -1, 0 });
    }
 
    // Add an Ultra-style big add gate with use of next row to test q_arith = 2
    FF e = a + b + c + d;
    uint32_t e_idx = circuit_builder.add_variable(e);
 
    uint32_t zero_idx = circuit_builder.zero_idx();
    circuit_builder.create_big_add_gate({ a_idx, b_idx, c_idx, d_idx, -1, -1, -1, -1, 0 }, true); // use next row
    circuit_builder.create_big_add_gate({ zero_idx, zero_idx, zero_idx, e_idx, 0, 0, 0, 0, 0 }, false);
}
 
template <typename Flavor> void create_some_lookup_gates(auto& circuit_builder)
{
    using FF = typename Flavor::FF;
    // Add some lookup gates (related to pedersen hashing)
    auto pedersen_input_value = FF::random_element();
    const auto input_hi =
        uint256_t(pedersen_input_value)
            .slice(plookup::fixed_base::table::BITS_PER_LO_SCALAR,
                   plookup::fixed_base::table::BITS_PER_LO_SCALAR + plookup::fixed_base::table::BITS_PER_HI_SCALAR);
    const auto input_lo = uint256_t(pedersen_input_value).slice(0, bb::plookup::fixed_base::table::BITS_PER_LO_SCALAR);
    const auto input_hi_index = circuit_builder.add_variable(FF(input_hi));
    const auto input_lo_index = circuit_builder.add_variable(FF(input_lo));
 
    const auto sequence_data_hi =
        plookup::get_lookup_accumulators(bb::plookup::MultiTableId::FIXED_BASE_LEFT_HI, input_hi);
    const auto sequence_data_lo =
        plookup::get_lookup_accumulators(bb::plookup::MultiTableId::FIXED_BASE_LEFT_LO, input_lo);
 
    circuit_builder.create_gates_from_plookup_accumulators(
        plookup::MultiTableId::FIXED_BASE_LEFT_HI, sequence_data_hi, input_hi_index);
    circuit_builder.create_gates_from_plookup_accumulators(
        plookup::MultiTableId::FIXED_BASE_LEFT_LO, sequence_data_lo, input_lo_index);
}
 
template <typename Flavor> void create_some_delta_range_constraint_gates(auto& circuit_builder)
{
    // Add an `enforce_small_deltas` gate (simply checks that consecutive inputs have a difference of < 4)
    using FF = typename Flavor::FF;
    auto a_idx = circuit_builder.add_variable(FF(0));
    auto b_idx = circuit_builder.add_variable(FF(1));
    auto c_idx = circuit_builder.add_variable(FF(2));
    auto d_idx = circuit_builder.add_variable(FF(3));
    circuit_builder.enforce_small_deltas({ a_idx, b_idx, c_idx, d_idx });
}
 
template <typename Flavor> void create_some_RAM_gates(auto& circuit_builder)
{
    using FF = typename Flavor::FF;
    // Add some RAM gates
    uint32_t ram_values[8]{
        circuit_builder.add_variable(FF::random_element()), circuit_builder.add_variable(FF::random_element()),
        circuit_builder.add_variable(FF::random_element()), circuit_builder.add_variable(FF::random_element()),
        circuit_builder.add_variable(FF::random_element()), circuit_builder.add_variable(FF::random_element()),
        circuit_builder.add_variable(FF::random_element()), circuit_builder.add_variable(FF::random_element()),
    };
 
    size_t ram_id = circuit_builder.create_RAM_array(8);
 
    for (size_t i = 0; i < 8; ++i) {
        circuit_builder.init_RAM_element(ram_id, i, ram_values[i]);
    }
 
    auto a_idx = circuit_builder.read_RAM_array(ram_id, circuit_builder.add_variable(FF(5)));
    EXPECT_EQ(a_idx != ram_values[5], true);
 
    auto b_idx = circuit_builder.read_RAM_array(ram_id, circuit_builder.add_variable(FF(4)));
    auto c_idx = circuit_builder.read_RAM_array(ram_id, circuit_builder.add_variable(FF(1)));
 
    circuit_builder.write_RAM_array(ram_id, circuit_builder.add_variable(FF(4)), circuit_builder.add_variable(FF(500)));
    auto d_idx = circuit_builder.read_RAM_array(ram_id, circuit_builder.add_variable(FF(4)));
 
    EXPECT_EQ(circuit_builder.get_variable(d_idx), 500);
 
    // ensure these vars get used in another arithmetic gate
    const auto e_value = circuit_builder.get_variable(a_idx) + circuit_builder.get_variable(b_idx) +
                         circuit_builder.get_variable(c_idx) + circuit_builder.get_variable(d_idx);
    auto e_idx = circuit_builder.add_variable(e_value);
 
    circuit_builder.create_big_add_gate({ a_idx, b_idx, c_idx, d_idx, -1, -1, -1, -1, 0 }, true);
    circuit_builder.create_big_add_gate(
        {
            circuit_builder.zero_idx(),
            circuit_builder.zero_idx(),
            circuit_builder.zero_idx(),
            e_idx,
            0,
            0,
            0,
            0,
            0,
        },
        false);
}
 
template <typename Flavor> void create_some_elliptic_curve_addition_gates(auto& circuit_builder)
{
    // Add an elliptic curve addition gate
    grumpkin::g1::affine_element p1 = grumpkin::g1::affine_element::random_element();
    grumpkin::g1::affine_element p2 = grumpkin::g1::affine_element::random_element();
 
    grumpkin::g1::affine_element p3(grumpkin::g1::element(p1) - grumpkin::g1::element(p2));
 
    uint32_t x1 = circuit_builder.add_variable(p1.x);
    uint32_t y1 = circuit_builder.add_variable(p1.y);
    uint32_t x2 = circuit_builder.add_variable(p2.x);
    uint32_t y2 = circuit_builder.add_variable(p2.y);
    uint32_t x3 = circuit_builder.add_variable(p3.x);
    uint32_t y3 = circuit_builder.add_variable(p3.y);
 
    circuit_builder.create_ecc_add_gate({ x1, y1, x2, y2, x3, y3, /*is_addition=*/false });
}
 
template <typename Flavor>
void create_some_ecc_op_queue_gates(auto& circuit_builder)
    requires(Flavor::HasEccOpQueue)
{
    using G1 = typename Flavor::Curve::Group;
    using FF = typename Flavor::FF;
    const size_t num_ecc_operations = 10; // arbitrary
    for (size_t i = 0; i < num_ecc_operations; ++i) {
        auto point = G1::affine_one * FF::random_element();
        auto scalar = FF::random_element();
        circuit_builder.queue_ecc_mul_accum(point, scalar);
    }
}
 
template <typename Flavor>
void create_some_databus_gates(auto& builder)
    requires Flavor::HasDataBus
{
    using FF = typename Flavor::FF;
    auto val = builder.add_variable(FF::random_element());
    builder.add_public_calldata(BusId::KERNEL_CALLDATA, val);
    builder.read_calldata(BusId::KERNEL_CALLDATA, builder.add_variable(FF(0)));
    for (size_t app_idx = 0; app_idx < MAX_APPS_PER_KERNEL; ++app_idx) {
        auto bus_id = static_cast<BusId>(static_cast<size_t>(BusId::APP_CALLDATA) + app_idx);
        builder.add_public_calldata(bus_id, val);
        builder.read_calldata(bus_id, builder.add_variable(FF(0)));
    }
    builder.add_public_return_data(val);
    builder.read_return_data(builder.add_variable(FF(0)));
}
 
template <typename Flavor> void create_some_non_native_field_gates(auto& builder)
{
    using Builder = typename Flavor::CircuitBuilder;
    using fq_ct = stdlib::bigfield<Builder, bb::Bn254FqParams>;
 
    auto a = fq_ct::from_witness(&builder, bb::fq::random_element());
    auto b = fq_ct::from_witness(&builder, bb::fq::random_element());
    [[maybe_unused]] auto c = a * b;
}
 
template <typename Flavor> void create_some_bilinear_batched_eq_gates(auto& builder)
{
    using FF = typename Flavor::FF;
 
    // BILINEAR row: enforce the full identity
    //   q_m·a·b + q_5·a·c + q_l·a + q_r·b + q_o·c + q_4·d + q_c = 0
    // with two products sharing wire a, a linear term on each wire, and a constant. Pick a, b, c and
    // solve for the linear-only wire d so the identity holds.
    FF qm = FF(3);
    FF q5 = -FF(5);
    FF ql = FF(2);
    FF qr = -FF(1);
    FF qo = FF(7);
    FF q4 = FF(4);
    FF qc = FF(11);
    FF a_val = FF::random_element();
    FF b_val = FF::random_element();
    FF c_val = FF::random_element();
    // q_4·d = −(q_m·a·b + q_5·a·c + q_l·a + q_r·b + q_o·c + q_c)  ⇒  d = rest / q_4
    FF rest = -(qm * a_val * b_val + q5 * a_val * c_val + ql * a_val + qr * b_val + qo * c_val + qc);
    FF d_val = rest * q4.invert();
    uint32_t a_idx = builder.add_variable(a_val);
    uint32_t b_idx = builder.add_variable(b_val);
    uint32_t c_idx = builder.add_variable(c_val);
    uint32_t d_idx = builder.add_variable(d_val);
    builder.create_bilinear_batched_eq_gate({ BilinearBatchedEqMode::Bilinear,
                                              a_idx,
                                              b_idx,
                                              c_idx,
                                              d_idx,
                                              /*q_l=*/ql,
                                              /*q_r=*/qr,
                                              /*q_o=*/qo,
                                              /*q_4=*/q4,
                                              /*q_c=*/qc,
                                              /*q_m=*/qm,
                                              /*q_5=*/q5 });
 
    // BATCHED_EQ row: pair two equality-with-const constraints into one row.
    // Half 1: w_l + 2·w_r − k1 = 0
    // Half 2: 3·w_o − w_4 − k2 = 0
    FF w_l_val = FF::random_element();
    FF w_r_val = FF::random_element();
    FF w_o_val = FF::random_element();
    FF k1 = w_l_val + FF(2) * w_r_val;
    FF k2 = FF(3) * w_o_val;
    FF w_4_val = k2 * -FF(1) + FF(3) * w_o_val; // makes 3·w_o − w_4 − k2 = 0
    uint32_t wl_idx = builder.add_variable(w_l_val);
    uint32_t wr_idx = builder.add_variable(w_r_val);
    uint32_t wo_idx = builder.add_variable(w_o_val);
    uint32_t w4_idx = builder.add_variable(w_4_val);
    builder.create_bilinear_batched_eq_gate({ BilinearBatchedEqMode::BatchedEq,
                                              wl_idx,
                                              wr_idx,
                                              wo_idx,
                                              w4_idx,
                                              /*q_l=*/FF(1),
                                              /*q_r=*/FF(2),
                                              /*q_o=*/FF(3),
                                              /*q_4=*/-FF(1),
                                              /*q_c=*/-k1,
                                              /*q_m=*/-k2,
                                              /*q_5=*/0 });
}
 
template <typename Flavor> void create_some_poseidon2_gates(auto& builder)
{
    using field_ct = stdlib::field_t<typename Flavor::CircuitBuilder>;
    using witness_ct = stdlib::witness_t<typename Flavor::CircuitBuilder>;
    using FF = typename Flavor::FF;
 
    std::vector<field_ct> inputs;
    for (size_t i = 0; i < 4; ++i) {
        inputs.emplace_back(witness_ct(&builder, FF::random_element()));
    }
    stdlib::poseidon2<typename Flavor::CircuitBuilder>::hash(inputs);
}
 
class UltraRelationCorrectnessTests : public ::testing::Test {
  protected:
    static void SetUpTestSuite() { bb::srs::init_file_crs_factory(bb::srs::bb_crs_path()); }
};
 
// TODO(luke): Add a gate that sets q_arith = 3 to check secondary arithmetic relation
TEST_F(UltraRelationCorrectnessTests, Ultra)
{
    using Flavor = UltraFlavor;
 
    // Create a builder and then add an assortment of gates designed to ensure that the constraint(s) represented
    // by each relation are non-trivially exercised.
    auto builder = UltraCircuitBuilder();
 
    // Create an assortment of representative gates
    create_some_add_gates<Flavor>(builder);
    create_some_lookup_gates<Flavor>(builder);
    create_some_delta_range_constraint_gates<Flavor>(builder);
    create_some_elliptic_curve_addition_gates<Flavor>(builder);
    create_some_RAM_gates<Flavor>(builder);
    create_some_non_native_field_gates<Flavor>(builder);
    create_some_poseidon2_gates<Flavor>(builder);
    stdlib::recursion::honk::DefaultIO<UltraCircuitBuilder>::add_default(builder);
 
    // Create a prover (it will compute proving key and witness)
    auto prover_inst = std::make_shared<ProverInstance_<Flavor>>(builder);
 
    complete_prover_instance_for_test<Flavor>(prover_inst);
 
    // Check that selectors are nonzero to ensure corresponding relation has nontrivial contribution
    for (auto selector : prover_inst->polynomials.get_gate_selectors()) {
        ensure_non_zero(selector);
    }
 
    auto& prover_polynomials = prover_inst->polynomials;
    auto params = prover_inst->relation_parameters;
 
    auto relation_failures = RelationChecker<Flavor>::check_all(prover_polynomials, params);
    EXPECT_TRUE(relation_failures.empty());
}
 
TEST_F(UltraRelationCorrectnessTests, Mega)
{
    using Flavor = MegaFlavor;
 
    // Create a composer and then add an assortment of gates designed to ensure that the constraint(s) represented
    // by each relation are non-trivially exercised.
    auto builder = MegaCircuitBuilder();
 
    // Create an assortment of representative gates
    create_some_add_gates<Flavor>(builder);
    create_some_lookup_gates<Flavor>(builder);
    create_some_delta_range_constraint_gates<Flavor>(builder);
    create_some_elliptic_curve_addition_gates<Flavor>(builder);
    create_some_RAM_gates<Flavor>(builder);
    create_some_ecc_op_queue_gates<Flavor>(builder);
    create_some_databus_gates<Flavor>(builder);
    create_some_non_native_field_gates<Flavor>(builder);
    create_some_poseidon2_gates<Flavor>(builder);
    create_some_bilinear_batched_eq_gates<Flavor>(builder);
    stdlib::recursion::honk::DefaultIO<MegaCircuitBuilder>::add_default(builder);
 
    // Create a prover (it will compute proving key and witness)
    auto prover_inst = std::make_shared<ProverInstance_<Flavor>>(builder);
 
    complete_prover_instance_for_test<Flavor>(prover_inst);
 
    // Check that selectors and databus inverses are nonzero to ensure relations are non-trivially exercised
    for (auto selector : prover_inst->polynomials.get_gate_selectors()) {
        ensure_non_zero(selector);
    }
 
    // Check the databus read counts/tags/inverses are non-zero (data columns may be zero with DEFAULT_VALUE=0)
    for (auto poly : prover_inst->polynomials.get_databus_inverses()) {
        ensure_non_zero(poly);
    }
 
    auto& prover_polynomials = prover_inst->polynomials;
    auto params = prover_inst->relation_parameters;
 
    auto relation_failures = RelationChecker<Flavor>::check_all(prover_polynomials, params);
    EXPECT_TRUE(relation_failures.empty());
}