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/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_initial_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
template<typename E >
E	get_random_entities ()

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

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

template<typename Relation , typename E = 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, Poseidon2InitialExternal)

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

◆ FF

using FF = fr

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

Function Documentation

◆ get_actually_constrained_wires()

template<typename Relation , typename E >

std::set< Wire > get_actually_constrained_wires	(	const E &	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 100 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 83 of file gate_patterns.test.cpp.

◆ get_random_entities()

template<typename E >

E get_random_entities ( )

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

◆ get_wire()

template<typename E >

FF & get_wire	(	E &	entities,
		Wire	wire
	)

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

◆ make_selectors()

template<typename E >

Selectors make_selectors	(	const E &	entities,
		int64_t	gate_selector_value
	)

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

◆ TEST() [1/24]

TEST	(	PatternTest	,
		Arithmetic1
	)

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

◆ TEST() [2/24]

TEST	(	PatternTest	,
		Arithmetic2
	)

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

◆ TEST() [3/24]

TEST	(	PatternTest	,
		Arithmetic3
	)

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

◆ TEST() [4/24]

TEST	(	PatternTest	,
		Arithmetic3WithQmZero
	)

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

◆ TEST() [5/24]

TEST	(	PatternTest	,
		DatabusRead
	)

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

◆ TEST() [6/24]

TEST	(	PatternTest	,
		DeltaRange
	)

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

◆ TEST() [7/24]

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

◆ TEST() [8/24]

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

◆ TEST() [9/24]

TEST	(	PatternTest	,
		EllipticAdd
	)

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

◆ TEST() [10/24]

TEST	(	PatternTest	,
		EllipticDouble
	)

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

◆ TEST() [11/24]

TEST	(	PatternTest	,
		LookupBasic
	)

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

◆ TEST() [12/24]

TEST	(	PatternTest	,
		LookupWithShiftedWires
	)

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

◆ TEST() [13/24]

TEST	(	PatternTest	,
		MemoryRamConsistency
	)

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

◆ TEST() [14/24]

TEST	(	PatternTest	,
		MemoryRamRomAccess
	)

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

◆ TEST() [15/24]

TEST	(	PatternTest	,
		MemoryRamTimestamp
	)

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

◆ TEST() [16/24]

TEST	(	PatternTest	,
		MemoryRomConsistency
	)

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

◆ TEST() [17/24]

TEST	(	PatternTest	,
		NNFLimbAccum1
	)

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

◆ TEST() [18/24]

TEST	(	PatternTest	,
		NNFLimbAccum2
	)

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

◆ TEST() [19/24]

TEST	(	PatternTest	,
		NNFProduct1
	)

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

◆ TEST() [20/24]

TEST	(	PatternTest	,
		NNFProduct2
	)

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

◆ TEST() [21/24]

TEST	(	PatternTest	,
		NNFProduct3
	)

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

◆ TEST() [22/24]

TEST	(	PatternTest	,
		Poseidon2External
	)

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

◆ TEST() [23/24]

TEST	(	PatternTest	,
		Poseidon2InitialExternal
	)

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

◆ TEST() [24/24]

TEST	(	PatternTest	,
		Poseidon2Internal
	)

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

◆ verify_pattern()

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

Typedefs

Functions

Detailed Description

Typedef Documentation

◆ Entities

◆ FF

Function Documentation

◆ get_actually_constrained_wires()

◆ get_pattern_wires()

◆ get_random_entities()

◆ get_wire()

◆ make_selectors()

◆ TEST() [1/24]

◆ TEST() [2/24]

◆ TEST() [3/24]

◆ TEST() [4/24]

◆ TEST() [5/24]

◆ TEST() [6/24]

◆ TEST() [7/24]

◆ TEST() [8/24]

◆ TEST() [9/24]

◆ TEST() [10/24]

◆ TEST() [11/24]

◆ TEST() [12/24]

◆ TEST() [13/24]

◆ TEST() [14/24]

◆ TEST() [15/24]

◆ TEST() [16/24]

◆ TEST() [17/24]

◆ TEST() [18/24]

◆ TEST() [19/24]

◆ TEST() [20/24]

◆ TEST() [21/24]

◆ TEST() [22/24]

◆ TEST() [23/24]

◆ TEST() [24/24]

◆ verify_pattern()