gate_patterns.test.cpp

Go to the documentation of this file.

 
#include "gate_patterns.hpp"
#include "barretenberg/flavor/mega_flavor.hpp"
#include "barretenberg/flavor/ultra_flavor.hpp"
#include "barretenberg/relations/bilinear_or_batched_eq_check_relation.hpp"
#include "barretenberg/relations/databus_lookup_relation.hpp"
#include "barretenberg/relations/delta_range_constraint_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/poseidon2_external_relation.hpp"
#include "barretenberg/relations/poseidon2_internal_relation.hpp"
#include "barretenberg/relations/relation_parameters.hpp"
#include "barretenberg/relations/ultra_arithmetic_relation.hpp"
#include <gtest/gtest.h>
#include <set>
 
using namespace bb;
using namespace bb::gate_patterns;
 
using FF = fr;
using Entities = MegaFlavor::AllValues;
using UltraEntities = UltraFlavor::AllValues;
 
template <typename EntitiesT = Entities> EntitiesT get_random_entities()
{
    EntitiesT entities;
    for (auto& field : entities.get_all()) {
        field = FF::random_element();
    }
    return entities;
}
 
template <typename EntitiesT> FF& get_wire(EntitiesT& entities, Wire wire)
{
    switch (wire) {
    case Wire::W_L:
        return entities.w_l();
    case Wire::W_R:
        return entities.w_r();
    case Wire::W_O:
        return entities.w_o();
    case Wire::W_4:
        return entities.w_4();
    case Wire::W_L_SHIFT:
        return entities.w_l_shift();
    case Wire::W_R_SHIFT:
        return entities.w_r_shift();
    case Wire::W_O_SHIFT:
        return entities.w_o_shift();
    case Wire::W_4_SHIFT:
        return entities.w_4_shift();
    }
    __builtin_unreachable();
}
 
template <typename EntitiesT> Selectors make_selectors(const EntitiesT& entities, int64_t gate_selector_value)
{
    Selectors selectors{
        .gate_selector = gate_selector_value,
        .q_m_nz = !entities.q_m().is_zero(),
        .q_1_nz = !entities.q_l().is_zero(),
        .q_2_nz = !entities.q_r().is_zero(),
        .q_3_nz = !entities.q_o().is_zero(),
        .q_4_nz = !entities.q_4().is_zero(),
        .q_c_nz = !entities.q_c().is_zero(),
    };
    // q_5 is committed only in the Mega flavors (used by the bilinear gate's second product).
    if constexpr (requires { entities.q_5(); }) {
        selectors.q_5_nz = !entities.q_5().is_zero();
    }
    return selectors;
}
 
std::set<Wire> get_pattern_wires(const GatePattern& pattern, const Selectors& selectors)
{
    std::set<Wire> result;
    for (const auto& wire_spec : pattern.wires) {
        if (wire_spec.condition(selectors)) {
            result.insert(wire_spec.wire);
        }
    }
    return result;
}
 
template <typename Relation, typename EntitiesT>
std::set<Wire> get_actually_constrained_wires(const EntitiesT& entities, const auto& parameters)
{
    std::set<Wire> constrained;
 
    // Evaluate relation at base point
    typename Relation::SumcheckArrayOfValuesOverSubrelations base_result{};
    Relation::accumulate(base_result, entities, parameters, FF(1));
 
    // For each wire position, perturb a copy and check if output changes
    for (Wire wire : { Wire::W_L,
                       Wire::W_R,
                       Wire::W_O,
                       Wire::W_4,
                       Wire::W_L_SHIFT,
                       Wire::W_R_SHIFT,
                       Wire::W_O_SHIFT,
                       Wire::W_4_SHIFT }) {
        EntitiesT perturbed = entities;
        get_wire(perturbed, wire) += FF::random_element();
 
        typename Relation::SumcheckArrayOfValuesOverSubrelations perturbed_result{};
        Relation::accumulate(perturbed_result, perturbed, parameters, FF(1));
 
        if (base_result != perturbed_result) {
            constrained.insert(wire);
        }
    }
 
    return constrained;
}
 
template <typename Relation, typename EntitiesT = Entities>
void verify_pattern(const GatePattern& pattern, auto configure_selectors)
{
    EntitiesT entities = get_random_entities<EntitiesT>();
    FF gate_selector = configure_selectors(entities);
    int64_t gate_selector_value = static_cast<int64_t>(uint64_t(gate_selector));
 
    Selectors selectors = make_selectors(entities, gate_selector_value);
    auto pattern_claims = get_pattern_wires(pattern, selectors);
 
    auto parameters = RelationParameters<FF>::get_random();
    auto actually_constrained = get_actually_constrained_wires<Relation>(entities, parameters);
 
    EXPECT_EQ(actually_constrained, pattern_claims);
}
 
// =============================================================================
// Pattern Tests
// =============================================================================
 
TEST(PatternTest, Arithmetic1)
{
    verify_pattern<ArithmeticRelation<FF>>(ARITHMETIC, [](Entities& e) { return e.q_arith() = FF(1); });
}
 
TEST(PatternTest, Arithmetic2)
{
    verify_pattern<ArithmeticRelation<FF>>(ARITHMETIC, [](Entities& e) { return e.q_arith() = FF(2); });
}
 
TEST(PatternTest, Arithmetic3)
{
    verify_pattern<ArithmeticRelation<FF>>(ARITHMETIC, [](Entities& e) { return e.q_arith() = FF(3); });
}
 
TEST(PatternTest, Arithmetic3WithQmZero)
{
    verify_pattern<ArithmeticRelation<FF>>(ARITHMETIC, [](Entities& e) {
        e.q_m() = FF(0);
        return e.q_arith() = FF(3);
    });
}
 
TEST(PatternTest, EllipticAdd)
{
    verify_pattern<EllipticRelation<FF>>(ELLIPTIC, [](Entities& e) {
        e.q_m() = FF(0);
        e.q_l() = FF(-1);
        return e.q_elliptic() = FF(1);
    });
}
 
TEST(PatternTest, EllipticDouble)
{
    verify_pattern<EllipticRelation<FF>>(ELLIPTIC, [](Entities& e) {
        e.q_m() = FF(1);
        e.q_l() = FF(-1);
        return e.q_elliptic() = FF(1);
    });
}
 
TEST(PatternTest, DeltaRange)
{
    verify_pattern<DeltaRangeConstraintRelation<FF>>(DELTA_RANGE,
                                                     [](Entities& e) { return e.q_delta_range() = FF(1); });
}
 
TEST(PatternTest, NNFLimbAccum1)
{
    verify_pattern<NonNativeFieldRelation<FF>>(NON_NATIVE_FIELD, [](Entities& e) {
        e.q_r() = FF(0);
        e.q_o() = FF(1);
        e.q_4() = FF(1);
        e.q_m() = FF(0);
        return e.q_nnf() = FF(1);
    });
}
 
TEST(PatternTest, NNFLimbAccum2)
{
    verify_pattern<NonNativeFieldRelation<FF>>(NON_NATIVE_FIELD, [](Entities& e) {
        e.q_r() = FF(0);
        e.q_o() = FF(1);
        e.q_4() = FF(0);
        e.q_m() = FF(1);
        return e.q_nnf() = FF(1);
    });
}
 
TEST(PatternTest, NNFProduct1)
{
    verify_pattern<NonNativeFieldRelation<FF>>(NON_NATIVE_FIELD, [](Entities& e) {
        e.q_r() = FF(1);
        e.q_o() = FF(1);
        e.q_4() = FF(0);
        e.q_m() = FF(0);
        return e.q_nnf() = FF(1);
    });
}
 
TEST(PatternTest, NNFProduct2)
{
    verify_pattern<NonNativeFieldRelation<FF>>(NON_NATIVE_FIELD, [](Entities& e) {
        e.q_r() = FF(1);
        e.q_o() = FF(0);
        e.q_4() = FF(1);
        e.q_m() = FF(0);
        return e.q_nnf() = FF(1);
    });
}
 
TEST(PatternTest, NNFProduct3)
{
    verify_pattern<NonNativeFieldRelation<FF>>(NON_NATIVE_FIELD, [](Entities& e) {
        e.q_r() = FF(1);
        e.q_o() = FF(0);
        e.q_4() = FF(0);
        e.q_m() = FF(1);
        return e.q_nnf() = FF(1);
    });
}
 
TEST(PatternTest, MemoryRamRomAccess)
{
    verify_pattern<MemoryRelation<FF>>(MEMORY, [](Entities& e) {
        e.q_l() = FF(1);
        e.q_m() = FF(1);
        return e.q_memory() = FF(1);
    });
}
 
TEST(PatternTest, MemoryRamTimestamp)
{
    verify_pattern<MemoryRelation<FF>>(MEMORY, [](Entities& e) {
        e.q_l() = FF(1);
        e.q_4() = FF(1);
        return e.q_memory() = FF(1);
    });
}
 
TEST(PatternTest, MemoryRomConsistency)
{
    verify_pattern<MemoryRelation<FF>>(MEMORY, [](Entities& e) {
        e.q_l() = FF(1);
        e.q_r() = FF(1);
        return e.q_memory() = FF(1);
    });
}
 
TEST(PatternTest, MemoryRamConsistency)
{
    verify_pattern<MemoryRelation<FF>>(MEMORY, [](Entities& e) {
        e.q_o() = FF(1);
        return e.q_memory() = FF(1);
    });
}
 
TEST(PatternTest, Poseidon2Internal)
{
    verify_pattern<Poseidon2InternalRelation<FF>, UltraEntities>(
        POSEIDON2_INTERNAL, [](UltraEntities& e) { return e.q_poseidon2_internal() = FF(1); });
}
 
TEST(PatternTest, Poseidon2External)
{
    verify_pattern<Poseidon2ExternalRelation<FF>>(POSEIDON2_EXTERNAL,
                                                  [](Entities& e) { return e.q_poseidon2_external() = FF(1); });
}
 
TEST(PatternTest, LookupBasic)
{
    verify_pattern<LogDerivLookupRelation<FF>>(LOOKUP, [](Entities& e) {
        // No shifted wires (step_size selectors all zero)
        e.q_r() = FF(0);
        e.q_m() = FF(0);
        e.q_c() = FF(0);
        return e.q_lookup() = FF(1);
    });
}
 
TEST(PatternTest, LookupWithShiftedWires)
{
    verify_pattern<LogDerivLookupRelation<FF>>(LOOKUP, [](Entities& e) {
        // Enable all shifted wires
        e.q_r() = FF(1);
        e.q_m() = FF(1);
        e.q_c() = FF(1);
        return e.q_lookup() = FF(1);
    });
}
 
TEST(PatternTest, DatabusRead)
{
    // The kernel_calldata bus relation is shape-equivalent to every other Mega bus relation;
    // verifying it covers the pattern check for q_busread reads.
    using KernelCalldataLookup = bb::SingleBusLookupRelation<FF,
                                                             MegaFlavor::EntityId::kernel_calldata,
                                                             MegaFlavor::EntityId::kernel_calldata_read_counts,
                                                             MegaFlavor::EntityId::kernel_calldata_inverses,
                                                             MegaFlavor::EntityId::kernel_calldata_indicator,
                                                             MegaFlavor::EntityId::q_l>;
    verify_pattern<KernelCalldataLookup>(DATABUS, [](Entities& e) { return e.q_busread() = FF(1); });
}
 
TEST(PatternTest, BilinearFull)
{
    // BILINEAR mode (q_bilinear_batched_eq = 1): all selectors non-zero, so both products and all linear
    // terms are present and the four wires are constrained.
    verify_pattern<BilinearOrBatchedEqCheckRelation<FF>>(BILINEAR,
                                                         [](Entities& e) { return e.q_bilinear_batched_eq() = FF(1); });
}
 
TEST(PatternTest, BilinearSecondProductAndItsLinearsAbsent)
{
    // BILINEAR mode with the second product (q_5) and the w_o/w_4 linear terms (q_o/q_4) zeroed: only
    // w_l and w_r remain constrained.
    verify_pattern<BilinearOrBatchedEqCheckRelation<FF>>(BILINEAR, [](Entities& e) {
        e.q_5() = FF(0);
        e.q_o() = FF(0);
        e.q_4() = FF(0);
        return e.q_bilinear_batched_eq() = FF(1);
    });
}
 
TEST(PatternTest, BatchedEq)
{
    // BATCHED_EQ mode (q_bilinear_batched_eq = 2): two independent equalities. Each half-pattern claims its own
    // pair of wires; their union must equal the wires the relation actually constrains.
    Entities entities = get_random_entities();
    entities.q_bilinear_batched_eq() = FF(2);
 
    Selectors selectors = make_selectors(entities, 2);
    auto half_1 = get_pattern_wires(BATCHED_EQ_HALF_1, selectors);
    auto half_2 = get_pattern_wires(BATCHED_EQ_HALF_2, selectors);
 
    EXPECT_EQ(half_1, (std::set<Wire>{ Wire::W_L, Wire::W_R }));
    EXPECT_EQ(half_2, (std::set<Wire>{ Wire::W_O, Wire::W_4 }));
 
    std::set<Wire> combined = half_1;
    combined.insert(half_2.begin(), half_2.end());
 
    auto parameters = RelationParameters<FF>::get_random();
    auto actually_constrained =
        get_actually_constrained_wires<BilinearOrBatchedEqCheckRelation<FF>>(entities, parameters);
    EXPECT_EQ(actually_constrained, combined);
}
 
TEST(PatternTest, BatchedEqSingleHalf)
{
    // A single-half BATCHED_EQ row leaves batched-eq-half-2 zero (its q_o, q_4 selectors and the q_m constant), so
    // only w_l and w_r are constrained and BATCHED_EQ_HALF_2 claims nothing.
    Entities entities = get_random_entities();
    entities.q_o() = FF(0);
    entities.q_4() = FF(0);
    entities.q_m() = FF(0);
    entities.q_bilinear_batched_eq() = FF(2);
 
    Selectors selectors = make_selectors(entities, 2);
    auto half_1 = get_pattern_wires(BATCHED_EQ_HALF_1, selectors);
    auto half_2 = get_pattern_wires(BATCHED_EQ_HALF_2, selectors);
 
    EXPECT_EQ(half_1, (std::set<Wire>{ Wire::W_L, Wire::W_R }));
    EXPECT_TRUE(half_2.empty());
 
    std::set<Wire> combined = half_1;
    combined.insert(half_2.begin(), half_2.end());
 
    auto parameters = RelationParameters<FF>::get_random();
    auto actually_constrained =
        get_actually_constrained_wires<BilinearOrBatchedEqCheckRelation<FF>>(entities, parameters);
    EXPECT_EQ(actually_constrained, combined);
}
 
// =============================================================================
// Failure Detection Tests
//
// These tests verify the perturbation testing mechanism catches pattern errors.
// They use intentionally wrong patterns to demonstrate both over-constrained
// and under-constrained specifications are detected.
// =============================================================================
 
TEST(PatternTest, DetectOverConstrained)
{
    // Pattern that unconditionally includes w_r when q_m != 0 (ignoring q_arith value)
    const GatePattern OVERCONSTRAINED_PATTERN = { .name = "overconstrained",
                                                  .wires = {
                                                      { Wire::W_L,
                                                        [](const Selectors& sel) { return sel.q_1_nz || sel.q_m_nz; } },
                                                      { Wire::W_R,
                                                        [](const Selectors& sel) {
                                                            return sel.q_2_nz || sel.q_m_nz;
                                                        } }, // should check q_arith!=3
                                                      { Wire::W_O, [](const Selectors& sel) { return sel.q_3_nz; } },
                                                      { Wire::W_4,
                                                        [](const Selectors& sel) {
                                                            return sel.q_4_nz || sel.gate_selector >= 2;
                                                        } },
                                                      { Wire::W_4_SHIFT,
                                                        [](const Selectors& sel) { return sel.gate_selector >= 2; } },
                                                      { Wire::W_L_SHIFT,
                                                        [](const Selectors& sel) { return sel.gate_selector == 3; } },
                                                  } };
 
    // q_arith=3 disables mul term, q_2=0 means w_r has no linear term, so w_r is unconstrained
    Entities entities = get_random_entities();
    entities.q_arith() = FF(3);
    entities.q_m() = FF(1);
    entities.q_l() = FF(1);
    entities.q_r() = FF(0); // q_2 = 0
 
    Selectors selectors = make_selectors(entities, 3);
    auto pattern_claims = get_pattern_wires(OVERCONSTRAINED_PATTERN, selectors);
    auto correct_claims = get_pattern_wires(ARITHMETIC, selectors);
    auto parameters = RelationParameters<FF>::get_random();
    auto actually_constrained = get_actually_constrained_wires<ArithmeticRelation<FF>>(entities, parameters);
 
    EXPECT_TRUE(pattern_claims.contains(Wire::W_R)) << "Over-constrained pattern claims W_R";
    EXPECT_FALSE(actually_constrained.contains(Wire::W_R)) << "Relation does not constrain W_R in this config";
    EXPECT_NE(pattern_claims, actually_constrained) << "Over-constrained pattern should not match relation";
    EXPECT_EQ(correct_claims, actually_constrained) << "Correct ARITHMETIC pattern should match relation";
}
 
TEST(PatternTest, DetectUnderConstrained)
{
    // Pattern missing w_l and w_r for RAM consistency
    const GatePattern
        UNDERCONSTRAINED_PATTERN = { .name = "underconstrained",
                                     .wires = {
                                         { Wire::W_O, [](const Selectors& sel) { return sel.q_3_nz; } },
                                         { Wire::W_4, [](const Selectors& sel) { return sel.q_3_nz; } },
                                         { Wire::W_L_SHIFT, [](const Selectors& sel) { return sel.q_3_nz; } },
                                         { Wire::W_R_SHIFT, [](const Selectors& sel) { return sel.q_3_nz; } },
                                         { Wire::W_O_SHIFT, [](const Selectors& sel) { return sel.q_3_nz; } },
                                         { Wire::W_4_SHIFT, [](const Selectors& sel) { return sel.q_3_nz; } },
                                     } };
 
    // RAM consistency check: q_3 != 0
    Entities entities = get_random_entities();
    entities.q_memory() = FF(1);
    entities.q_o() = FF(1); // q_3
 
    Selectors selectors = make_selectors(entities, 1);
    auto pattern_claims = get_pattern_wires(UNDERCONSTRAINED_PATTERN, selectors);
    auto correct_claims = get_pattern_wires(MEMORY, selectors);
    auto parameters = RelationParameters<FF>::get_random();
    auto actually_constrained = get_actually_constrained_wires<MemoryRelation<FF>>(entities, parameters);
 
    EXPECT_FALSE(pattern_claims.contains(Wire::W_L)) << "Under-constrained pattern missing W_L";
    EXPECT_FALSE(pattern_claims.contains(Wire::W_R)) << "Under-constrained pattern missing W_R";
    EXPECT_TRUE(actually_constrained.contains(Wire::W_L)) << "Relation constrains W_L";
    EXPECT_TRUE(actually_constrained.contains(Wire::W_R)) << "Relation constrains W_R";
    EXPECT_NE(pattern_claims, actually_constrained) << "Under-constrained pattern should not match relation";
    EXPECT_EQ(correct_claims, actually_constrained) << "Correct MEMORY pattern should match relation";
}