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

#include "gate_patterns.hpp"
#include "barretenberg/flavor/mega_flavor.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

Functions
Entities	get_random_entities ()

FF &	get_wire (Entities &entities, Wire wire)

Selectors	make_selectors (const Entities &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 >
std::set< Wire >	get_actually_constrained_wires (const Entities &entities, const auto &parameters)
	Get the set of wires that actually affect a relation's output.

template<typename Relation >
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, 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 31 of file gate_patterns.test.cpp.

◆ FF

using FF = fr

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

Function Documentation

◆ get_actually_constrained_wires()

template<typename Relation >

std::set< Wire > get_actually_constrained_wires	(	const Entities &	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 98 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 81 of file gate_patterns.test.cpp.

◆ get_random_entities()

Entities get_random_entities ( )

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

◆ get_wire()

FF & get_wire	(	Entities &	entities,
		Wire	wire
	)

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

◆ make_selectors()

Selectors make_selectors	(	const Entities &	entities,
		int64_t	gate_selector_value
	)

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

◆ TEST() [1/23]

TEST	(	PatternTest	,
		Arithmetic1
	)

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

◆ TEST() [2/23]

TEST	(	PatternTest	,
		Arithmetic2
	)

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

◆ TEST() [3/23]

TEST	(	PatternTest	,
		Arithmetic3
	)

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

◆ TEST() [4/23]

TEST	(	PatternTest	,
		Arithmetic3WithQmZero
	)

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

◆ TEST() [5/23]

TEST	(	PatternTest	,
		DatabusRead
	)

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

◆ TEST() [6/23]

TEST	(	PatternTest	,
		DeltaRange
	)

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

◆ TEST() [7/23]

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 343 of file gate_patterns.test.cpp.

◆ TEST() [8/23]

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 390 of file gate_patterns.test.cpp.

◆ TEST() [9/23]

TEST	(	PatternTest	,
		EllipticAdd
	)

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

◆ TEST() [10/23]

TEST	(	PatternTest	,
		EllipticDouble
	)

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

◆ TEST() [11/23]

TEST	(	PatternTest	,
		LookupBasic
	)

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

◆ TEST() [12/23]

TEST	(	PatternTest	,
		LookupWithShiftedWires
	)

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

◆ TEST() [13/23]

TEST	(	PatternTest	,
		MemoryRamConsistency
	)

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

◆ TEST() [14/23]

TEST	(	PatternTest	,
		MemoryRamRomAccess
	)

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

◆ TEST() [15/23]

TEST	(	PatternTest	,
		MemoryRamTimestamp
	)

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

◆ TEST() [16/23]

TEST	(	PatternTest	,
		MemoryRomConsistency
	)

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

◆ TEST() [17/23]

TEST	(	PatternTest	,
		NNFLimbAccum1
	)

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

◆ TEST() [18/23]

TEST	(	PatternTest	,
		NNFLimbAccum2
	)

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

◆ TEST() [19/23]

TEST	(	PatternTest	,
		NNFProduct1
	)

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

◆ TEST() [20/23]

TEST	(	PatternTest	,
		NNFProduct2
	)

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

◆ TEST() [21/23]

TEST	(	PatternTest	,
		NNFProduct3
	)

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

◆ TEST() [22/23]

TEST	(	PatternTest	,
		Poseidon2External
	)

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

◆ TEST() [23/23]

TEST	(	PatternTest	,
		Poseidon2Internal
	)

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

◆ verify_pattern()