Verify gate patterns match actual relation constraints via perturbation testing. More...

#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>

Typedefs
using	FF = fr

using	Entities = MegaFlavor::AllValues

using	UltraEntities = UltraFlavor::AllValues

Functions
template<typename EntitiesT = Entities>
EntitiesT	get_random_entities ()

template<typename EntitiesT >
FF &	get_wire (EntitiesT &entities, Wire wire)

template<typename EntitiesT >
Selectors	make_selectors (const EntitiesT &entities, int64_t gate_selector_value)

std::set< Wire >	get_pattern_wires (const GatePattern &pattern, const Selectors &selectors)
	Get the set of wires that a pattern claims are constrained.

template<typename Relation , typename EntitiesT >
std::set< Wire >	get_actually_constrained_wires (const EntitiesT &entities, const auto &parameters)
	Get the set of wires that actually affect a relation's output.

template<typename Relation , typename EntitiesT = Entities>
void	verify_pattern (const GatePattern &pattern, auto configure_selectors)
	Generic test: verify a pattern matches what the relation actually constrains.

	TEST (PatternTest, Arithmetic1)

	TEST (PatternTest, Arithmetic2)

	TEST (PatternTest, Arithmetic3)

	TEST (PatternTest, Arithmetic3WithQmZero)

	TEST (PatternTest, EllipticAdd)

	TEST (PatternTest, EllipticDouble)

	TEST (PatternTest, DeltaRange)

	TEST (PatternTest, NNFLimbAccum1)

	TEST (PatternTest, NNFLimbAccum2)

	TEST (PatternTest, NNFProduct1)

	TEST (PatternTest, NNFProduct2)

	TEST (PatternTest, NNFProduct3)

	TEST (PatternTest, MemoryRamRomAccess)

	TEST (PatternTest, MemoryRamTimestamp)

	TEST (PatternTest, MemoryRomConsistency)

	TEST (PatternTest, MemoryRamConsistency)

	TEST (PatternTest, Poseidon2Internal)

	TEST (PatternTest, Poseidon2External)

	TEST (PatternTest, LookupBasic)

	TEST (PatternTest, LookupWithShiftedWires)

	TEST (PatternTest, DatabusRead)

	TEST (PatternTest, BilinearFull)

	TEST (PatternTest, BilinearSecondProductAndItsLinearsAbsent)

	TEST (PatternTest, BatchedEq)

	TEST (PatternTest, BatchedEqSingleHalf)

	TEST (PatternTest, DetectOverConstrained)
	Verify detection of OVER-constrained pattern (claims more wires than relation uses)

	TEST (PatternTest, DetectUnderConstrained)
	Verify detection of UNDER-constrained pattern (misses wires that relation uses)

Detailed Description

Verify gate patterns match actual relation constraints via perturbation testing.

A wire is constrained by a relation if and only if perturbing that wire changes the relation's output. We test this empirically by:

Evaluating the relation at a base point
Individually perturbing each wire and checking if the output changes
Comparing the set of actually constrained wires with what the pattern claims

Definition in file gate_patterns.test.cpp.

Typedef Documentation

◆ Entities

using Entities = MegaFlavor::AllValues

Definition at line 33 of file gate_patterns.test.cpp.

◆ FF

using FF = fr

Definition at line 32 of file gate_patterns.test.cpp.

◆ UltraEntities

using UltraEntities = UltraFlavor::AllValues

Definition at line 34 of file gate_patterns.test.cpp.

Function Documentation

◆ get_actually_constrained_wires()

template<typename Relation , typename EntitiesT >

std::set< Wire > get_actually_constrained_wires	(	const EntitiesT &	entities,
		const auto &	parameters
	)

Get the set of wires that actually affect a relation's output.

This is the ground truth: perturb each wire and see if the output changes.

Definition at line 106 of file gate_patterns.test.cpp.

◆ get_pattern_wires()

std::set< Wire > get_pattern_wires	(	const GatePattern &	pattern,
		const Selectors &	selectors
	)

Get the set of wires that a pattern claims are constrained.

Definition at line 89 of file gate_patterns.test.cpp.

◆ get_random_entities()

template<typename EntitiesT = Entities>

EntitiesT get_random_entities ( )

Definition at line 36 of file gate_patterns.test.cpp.

◆ get_wire()

template<typename EntitiesT >

FF & get_wire	(	EntitiesT &	entities,
		Wire	wire
	)

Definition at line 45 of file gate_patterns.test.cpp.

◆ make_selectors()

template<typename EntitiesT >

Selectors make_selectors	(	const EntitiesT &	entities,
		int64_t	gate_selector_value
	)

Definition at line 68 of file gate_patterns.test.cpp.

◆ TEST() [1/27]

TEST	(	PatternTest	,
		Arithmetic1
	)

Definition at line 162 of file gate_patterns.test.cpp.

◆ TEST() [2/27]

TEST	(	PatternTest	,
		Arithmetic2
	)

Definition at line 167 of file gate_patterns.test.cpp.

◆ TEST() [3/27]

TEST	(	PatternTest	,
		Arithmetic3
	)

Definition at line 172 of file gate_patterns.test.cpp.

◆ TEST() [4/27]

TEST	(	PatternTest	,
		Arithmetic3WithQmZero
	)

Definition at line 177 of file gate_patterns.test.cpp.

◆ TEST() [5/27]

TEST	(	PatternTest	,
		BatchedEq
	)

Definition at line 366 of file gate_patterns.test.cpp.

◆ TEST() [6/27]

TEST	(	PatternTest	,
		BatchedEqSingleHalf
	)

Definition at line 389 of file gate_patterns.test.cpp.

◆ TEST() [7/27]

TEST	(	PatternTest	,
		BilinearFull
	)

Definition at line 346 of file gate_patterns.test.cpp.

◆ TEST() [8/27]

TEST	(	PatternTest	,
		BilinearSecondProductAndItsLinearsAbsent
	)

Definition at line 354 of file gate_patterns.test.cpp.

◆ TEST() [9/27]

TEST	(	PatternTest	,
		DatabusRead
	)

Definition at line 333 of file gate_patterns.test.cpp.

◆ TEST() [10/27]

TEST	(	PatternTest	,
		DeltaRange
	)

Definition at line 203 of file gate_patterns.test.cpp.

◆ TEST() [11/27]

TEST	(	PatternTest	,
		DetectOverConstrained
	)

Verify detection of OVER-constrained pattern (claims more wires than relation uses)

When q_arith==3, the multiplication term q_m * w_l * w_r is disabled (scaled by q_arith - 3 = 0). So w_r is only constrained via the linear term q_2 * w_r. A pattern that includes w_r whenever q_m != 0 (without checking q_arith != 3) over-constrains when q_arith=3, q_m!=0, q_2=0.

Definition at line 430 of file gate_patterns.test.cpp.

◆ TEST() [12/27]

TEST	(	PatternTest	,
		DetectUnderConstrained
	)

Verify detection of UNDER-constrained pattern (misses wires that relation uses)

The RAM consistency relation (q_3 != 0) constrains all 8 wires. A pattern that only extracts 6 wires (omitting w_l and w_r) under-constrains.

Definition at line 477 of file gate_patterns.test.cpp.

◆ TEST() [13/27]

TEST	(	PatternTest	,
		EllipticAdd
	)

Definition at line 185 of file gate_patterns.test.cpp.

◆ TEST() [14/27]

TEST	(	PatternTest	,
		EllipticDouble
	)

Definition at line 194 of file gate_patterns.test.cpp.

◆ TEST() [15/27]

TEST	(	PatternTest	,
		LookupBasic
	)

Definition at line 311 of file gate_patterns.test.cpp.

◆ TEST() [16/27]

TEST	(	PatternTest	,
		LookupWithShiftedWires
	)

Definition at line 322 of file gate_patterns.test.cpp.

◆ TEST() [17/27]

TEST	(	PatternTest	,
		MemoryRamConsistency
	)

Definition at line 291 of file gate_patterns.test.cpp.

◆ TEST() [18/27]

TEST	(	PatternTest	,
		MemoryRamRomAccess
	)

Definition at line 264 of file gate_patterns.test.cpp.

◆ TEST() [19/27]

TEST	(	PatternTest	,
		MemoryRamTimestamp
	)

Definition at line 273 of file gate_patterns.test.cpp.

◆ TEST() [20/27]

TEST	(	PatternTest	,
		MemoryRomConsistency
	)

Definition at line 282 of file gate_patterns.test.cpp.

◆ TEST() [21/27]

TEST	(	PatternTest	,
		NNFLimbAccum1
	)

Definition at line 209 of file gate_patterns.test.cpp.

◆ TEST() [22/27]

TEST	(	PatternTest	,
		NNFLimbAccum2
	)

Definition at line 220 of file gate_patterns.test.cpp.

◆ TEST() [23/27]

TEST	(	PatternTest	,
		NNFProduct1
	)

Definition at line 231 of file gate_patterns.test.cpp.

◆ TEST() [24/27]

TEST	(	PatternTest	,
		NNFProduct2
	)

Definition at line 242 of file gate_patterns.test.cpp.

◆ TEST() [25/27]

TEST	(	PatternTest	,
		NNFProduct3
	)

Definition at line 253 of file gate_patterns.test.cpp.

◆ TEST() [26/27]

TEST	(	PatternTest	,
		Poseidon2External
	)

Definition at line 305 of file gate_patterns.test.cpp.

◆ TEST() [27/27]

TEST	(	PatternTest	,
		Poseidon2Internal
	)

Definition at line 299 of file gate_patterns.test.cpp.

◆ verify_pattern()

template<typename Relation , typename EntitiesT = Entities>

void verify_pattern	(	const GatePattern &	pattern,
		auto	configure_selectors
	)

Generic test: verify a pattern matches what the relation actually constrains.

Parameters

configure_selectors Lambda that configures entity selectors and returns the gate selector field value

Definition at line 143 of file gate_patterns.test.cpp.

Typedefs

Functions