permutation.test.cpp File Reference

#include "barretenberg/circuit_checker/circuit_checker.hpp"
#include "barretenberg/honk/library/grand_product_delta.hpp"
#include "barretenberg/honk/relation_checker.hpp"
#include "ultra_honk.test.hpp"

Go to the source code of this file.

Typedefs
using	FlavorTypes = testing::Types< UltraFlavor, UltraZKFlavor, UltraKeccakFlavor, UltraKeccakZKFlavor, UltraRollupFlavor >
template<typename T >
using	PermutationTests = UltraHonkTests< T >
using	NonZKFlavorTypes = testing::Types< UltraFlavor, UltraKeccakFlavor, UltraRollupFlavor >
template<typename T >
using	PermutationNonZKTests = UltraHonkTests< T >

Functions
	TYPED_TEST_SUITE (PermutationTests, FlavorTypes)
	TYPED_TEST_SUITE (PermutationNonZKTests, NonZKFlavorTypes)
	TYPED_TEST (PermutationTests, NonTrivialTagPermutation)
	Test that multiset-equality checks work.
	TYPED_TEST (PermutationTests, NonTrivialGeneralizedPerm)
	Test that generalized permutation argument works, i.e., copy constraints + multiset-equality checks.
	TYPED_TEST (PermutationTests, BadTagPermutation)
	Multiset-equality failure test.
	TYPED_TEST (PermutationNonZKTests, ZPermZeroedOutFailure)
	Test that zeroing out the z_perm grand product polynomial causes relation check failure.
	TYPED_TEST (PermutationNonZKTests, ZPermShiftNotZeroAtLagrangeLastFailure)
	Test that z_perm_shift must be zero at the last row (where lagrange_last = 1).
	TYPED_TEST (PermutationNonZKTests, SigmaCorruptionFailure)
	Test that tampering with a sigma polynomial breaks the permutation argument boundary check.
	TYPED_TEST (PermutationNonZKTests, PublicInputDeltaMismatch)
	Test that tampering with public_input_delta causes the permutation relation to fail.

Typedef Documentation

FlavorTypes

using FlavorTypes = testing::Types<UltraFlavor, UltraZKFlavor, UltraKeccakFlavor, UltraKeccakZKFlavor, UltraRollupFlavor>

Definition at line 17 of file permutation.test.cpp.

NonZKFlavorTypes

using NonZKFlavorTypes = testing::Types<UltraFlavor, UltraKeccakFlavor, UltraRollupFlavor>

Definition at line 22 of file permutation.test.cpp.

PermutationNonZKTests

template<typename T >

using PermutationNonZKTests = UltraHonkTests<T>

Definition at line 23 of file permutation.test.cpp.

PermutationTests

template<typename T >

using PermutationTests = UltraHonkTests<T>

Definition at line 20 of file permutation.test.cpp.

Function Documentation

TYPED_TEST() [1/7]

TYPED_TEST	(	PermutationNonZKTests	,
		PublicInputDeltaMismatch
	)

Test that tampering with public_input_delta causes the permutation relation to fail.

The permutation argument intentionally "breaks" cycles for public inputs. The prover's z_perm grand product is computed using the actual wire values at public input positions. At this point, we tamper with the public_input_delta; we compute a new one based on a tampered public_input. This causes the permutation relation to fail. The test further checks that the position where this fails is correct.

Note

We exclude ZK flavors because we manually tamper with relation parameters.

Definition at line 456 of file permutation.test.cpp.

TYPED_TEST() [2/7]

TYPED_TEST	(	PermutationNonZKTests	,
		SigmaCorruptionFailure
	)

Test that tampering with a sigma polynomial breaks the permutation argument boundary check.

The sigma polynomials encode copy cycles. In this test, we tamper with sigma in a place implicated by the copy-constriant and ensure that the relevant subrelation fails, both when we don't update z_perm and when we do. Moreover, we make sure the failure occurs "at the right row".

Note

There are no tags/multiset-equality checks in this test.

We exclude ZK flavors because we manually tamper with precomputed polynomials.

Definition at line 349 of file permutation.test.cpp.

TYPED_TEST() [3/7]

TYPED_TEST	(	PermutationNonZKTests	,
		ZPermShiftNotZeroAtLagrangeLastFailure
	)

Test that z_perm_shift must be zero at the last row (where lagrange_last = 1).

The permutation argument includes a boundary constraint: z_perm_shift * lagrange_last = 0.

This test:

1. Builds a valid circuit and verifies the permutation relation holds
2. Expands z_perm and z_perm_shift to full polynomials (to access the boundary)
3. Tampers with z_perm_shift at the lagrange_last position, making it non-zero
4. Verifies the permutation relation now fails at that row

Note

This test excludes ZK flavors because we manually tamper with z_perm, which would conflict with the ZK masking applied to witness polynomials.

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

TYPED_TEST() [4/7]

TYPED_TEST	(	PermutationNonZKTests	,
		ZPermZeroedOutFailure
	)

Test that zeroing out the z_perm grand product polynomial causes relation check failure.

The z_perm polynomial is the grand product accumulator for the permutation argument. It must satisfy specific recurrence relations at each row. This test:

1. Builds a valid circuit with a copy constraint (a_idx == a_copy_idx)
2. Verifies the permutation relation initially holds
3. Tampers with z_perm by setting all values to zero
4. Verifies the permutation relation now fails

This confirms that z_perm cannot be arbitrarily modified without detection.

Note

This test excludes ZK flavors because we manually tamper with z_perm, which would conflict with the ZK masking applied to witness polynomials.

This test does not use prove_and_verify. Indeed, there is no straightforward way to tamper with z_perm, created after finalization, using prove_and_verify.

Definition at line 207 of file permutation.test.cpp.

TYPED_TEST() [5/7]

TYPED_TEST	(	PermutationTests	,
		BadTagPermutation
	)

Multiset-equality failure test.

This test verifies that multiset-equality check fails when the multisets are not equal. It creates a circuit where the multisets are:

• {x, y}
• {y, x+1}

The second sub-test creates the same circuit WITHOUT tags to confirm that the circuit's arithmetic constraints are satisfied, proving the failure above is due to multiset-equality mismatch.

Definition at line 137 of file permutation.test.cpp.

TYPED_TEST() [6/7]

TYPED_TEST	(	PermutationTests	,
		NonTrivialGeneralizedPerm
	)

Test that generalized permutation argument works, i.e., copy constraints + multiset-equality checks.

The generalized permutation argument is a way to test both copy constraints and multiset-equality checks. This test checks that these two features work compatibly, by setting up

1. copy constraints via assert_equal(); and
2. multiset-equality checks via tags.

The test verifies that both mechanisms can coexist: the grand product argument must account for both the wire permutation cycles AND the tag-based multiset equality check.

Definition at line 85 of file permutation.test.cpp.

TYPED_TEST() [7/7]

TYPED_TEST	(	PermutationTests	,
		NonTrivialTagPermutation
	)

Test that multiset-equality checks work.

Tags provide a mechanism to enforce multiset-equality checks. In our codebase, this is mediated by a "permutation on tags", tau, which is, for our examples, always of order 2, i.e., the product of disjoint transpositions. This test creates two tags, linked via a tau transposition, then assigns:

• first_tag to variables with values {x, y}
• second_tag to variables with values {y, x}

The tag permutation check verifies that the multiset of values with first_tag equals the multiset of values with second_tag (after applying tau). Here both multisets are {x, y}, so the check passes.

Definition at line 39 of file permutation.test.cpp.

TYPED_TEST_SUITE() [1/2]

TYPED_TEST_SUITE	(	PermutationNonZKTests	,
		NonZKFlavorTypes
	)

TYPED_TEST_SUITE() [2/2]

TYPED_TEST_SUITE	(	PermutationTests	,
		FlavorTypes
	)