eccvm_relation_corruption.test.cpp File Reference

Corruption/negative tests for ECCVM relation constraints. More...

#include "barretenberg/eccvm/eccvm_flavor.hpp"
#include "barretenberg/eccvm/eccvm_test_utils.hpp"
#include "barretenberg/honk/library/grand_product_library.hpp"
#include "barretenberg/honk/proof_system/logderivative_library.hpp"
#include "barretenberg/honk/relation_checker.hpp"
#include <gtest/gtest.h>

Go to the source code of this file.

Classes
class	ECCVMRelationCorruptionTests

Functions
	TEST_F (ECCVMRelationCorruptionTests, MSMAccumulatorCorruptionAtTransitionRowIsHarmless)
	Show that corrupting the accumulator at row 1 (msm_transition=1) does NOT break the MSM relation.
	TEST_F (ECCVMRelationCorruptionTests, MSMAccumulatorCorruptionAtInteriorAndNoOpRows)
	Corrupt the MSM accumulator at an interior active row and at a trailing no-op row.
	TEST_F (ECCVMRelationCorruptionTests, MSMRelationFailsOnShiftedMSMTable)
	Shift every MSM column down by one row, inserting a zero row at row 1.
	TEST_F (ECCVMRelationCorruptionTests, TranscriptNoOpRowRejectsAccumulatorNotEmpty)
	On a transcript no-op row, setting accumulator_not_empty=1 must be caught by the ACCUMULATOR_EMPTY_UPDATE subrelation.
	TEST_F (ECCVMRelationCorruptionTests, ShiftableInitFailsOnZPermNonZeroAtFirstRow)
	Test that z_perm must be zero at the lagrange_first row.
	TEST_F (ECCVMRelationCorruptionTests, MSMRelationRejectsMissingRoundMinus31Inverse)
	Verify that the DOUBLE_SHIFT_FORBIDS_ROUND_31 gate catches a missing round != 31 witness.
	TEST_F (ECCVMRelationCorruptionTests, MSMRelationRejectsTransitionZeroOnFirstRow)
	Regression test for the MSM-start anchor (MSM_TRANSITION_AT_ACTIVE_START).
	TEST_F (ECCVMRelationCorruptionTests, MSMRelationRejectsInteriorMsmPcTamper)
	MSM_PC_CONTINUITY rejects any tamper of msm_pc on an interior ADD or DOUBLE row.
	TEST_F (ECCVMRelationCorruptionTests, MSMRelationRejectsInteriorSkewMsmPcTamper)
	Reject an arbitrary msm_pc on an interior SKEW row.

Detailed Description

Corruption/negative tests for ECCVM relation constraints.

Each test builds valid ProverPolynomials from a real ECCVMCircuitBuilder, asserts that relations pass on clean data, then corrupts specific witness values and verifies detection.

Definition in file eccvm_relation_corruption.test.cpp.

Function Documentation

TEST_F() [1/9]

TEST_F	(	ECCVMRelationCorruptionTests	,
		MSMAccumulatorCorruptionAtInteriorAndNoOpRows
	)

Corrupt the MSM accumulator at an interior active row and at a trailing no-op row.

Part 1 targets an interior addition row (q_add=1, msm_transition=0). Unlike the transition row, the interior addition directly uses acc as input to the point-addition chain, so corrupting it breaks the addition subrelations.

Part 2 targets a trailing no-op row where all MSM selectors are zero. Here the no-op preservation constraints (subrelations 45-46) enforce acc_shift == acc.

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

TEST_F() [2/9]

TEST_F	(	ECCVMRelationCorruptionTests	,
		MSMAccumulatorCorruptionAtTransitionRowIsHarmless
	)

Show that corrupting the accumulator at row 1 (msm_transition=1) does NOT break the MSM relation.

Row 1 is the first active MSM row with msm_transition=1. The first_add lambda in the MSM relation replaces the accumulator with the offset generator when msm_transition=1: x = xo * msm_transition + acc_x * (-msm_transition + 1) So when msm_transition=1, acc_x and acc_y are completely unused — corrupting them is harmless. This test documents that behavior explicitly.

Definition at line 190 of file eccvm_relation_corruption.test.cpp.

TEST_F() [3/9]

TEST_F	(	ECCVMRelationCorruptionTests	,
		MSMRelationFailsOnShiftedMSMTable
	)

Shift every MSM column down by one row, inserting a zero row at row 1.

For every MSM polynomial p, we set: p_new[0] = p[0] (row 0 is reserved for shifts, always zero) p_new[1] = 0 (injected blank row) p_new[k] = p[k-1] for k >= 2

This shifts all real MSM data one row later. Row 1, which was the first active MSM row (msm_transition = 1, q_add = 1, nonzero accumulator), becomes a no-op with zero accumulator. But the non-MSM columns (e.g. lagrange polynomials, precompute columns) are NOT shifted, so there's a mismatch. The no-op constraint (subrelations 45-46) forces acc_shift == acc at the now-empty row 1, but the shifted row 2 carries a nonzero accumulator from what was originally the row-1 computation, causing a detected violation.

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

TEST_F() [4/9]

TEST_F	(	ECCVMRelationCorruptionTests	,
		MSMRelationRejectsInteriorMsmPcTamper
	)

MSM_PC_CONTINUITY rejects any tamper of msm_pc on an interior ADD or DOUBLE row.

Before this subrelation existed, the MSM relation's only msm_pc constraint (MSM_TRANSITION_PC) was gated by msm_transition_shift, so it fired only at MSM segment boundaries. An attacker could swap msm_pc between two same-base MSMs on a single interior round and the WNAF/lookup multisets would still balance (both swapped tuples are valid writes). MSM_PC_CONTINUITY pins msm_pc constant across every interior ADD or DOUBLE row, so the constraint at the row immediately preceding any such swap detects it.

Definition at line 656 of file eccvm_relation_corruption.test.cpp.

TEST_F() [5/9]

TEST_F	(	ECCVMRelationCorruptionTests	,
		MSMRelationRejectsInteriorSkewMsmPcTamper
	)

Reject an arbitrary msm_pc on an interior SKEW row.

MSM_PC_CONTINUITY excludes q_skew from its active phase, and MSM_TRANSITION_PC only pins the last skew row of a segment. For an MSM with a skew round of >= 3 rows (msm_size >= 9), the interior skew rows are pinned by neither, so a prover could swap msm_pc on such a row between two segments; the point-table lookup multiset still balances but the skew corrections are applied to the wrong accumulators. MSM_PC_SKEW_CONTINUITY (q_skew * q_skew_shift) pins msm_pc across every pair of consecutive skew rows, detecting the tamper at the preceding skew row.

Definition at line 701 of file eccvm_relation_corruption.test.cpp.

TEST_F() [6/9]

TEST_F	(	ECCVMRelationCorruptionTests	,
		MSMRelationRejectsMissingRoundMinus31Inverse
	)

Verify that the DOUBLE_SHIFT_FORBIDS_ROUND_31 gate catches a missing round != 31 witness.

Background: this gate guards against a soundness gap in the original ECCVM MSM relation, where the converse "round = 31 ==> q_skew_shift = 1" was not constrained. The fix is the new subrelation q_double_shift * (1 - (round - 31) * round_minus_31_inv) = 0, which forces the prover to witness an inverse of (round - 31) at every row whose successor is a double, making round = 31 unreachable there. This test exercises the gate the simple way: at a valid q_double_shift = 1 row, zero out the inverse witness and confirm only this gate fires.

The original full PoC (kept as commentary so an attentive reader/LLM can reconstruct it):

Setup: a size-1 MSM with a 128-bit odd scalar s, e.g. Fr s = Fr(uint256_t(0x0123456789abcdefULL, 0x0fedcba987654321ULL, 0, 0)); op_queue.mul_accumulate(P, s); op_queue.eq_and_reset(); op_queue.merge(); // followed by add_hiding_op_for_test(op_queue) so the trace finalizes. Such a scalar gives z2 = 0 (single-mul MSM) and odd LSB so wnaf_skew = false, hence precompute_skew = 0 — the precondition for the round 31->32 phase swap.

Honest layout, with R = the unique row carrying msm_skew = 1, msm_round = 32: row R-1: q_add = 1, round = 31 (last add of digit 31) row R : q_skew = 1, round = 32, (msm_x1, msm_y1) = T[0] = -15*P (lookup with slice1 = 0) row R+1: synthetic final (msm_transition = 1, round = 0, all selectors = 0) row R+2: padding (all zero)

Malicious patch: turn row R into a q_double, append a same-MSM q_add at row R+1 with round = 32 and slice1 = 0 (so the lookup forces (x1, y1) = T[0] = -15*P), and shift the synthetic final to row R+2: row R: msm_skew = 0, msm_double = 1; witness lambdas l1..l4 of the four doublings d1 = 2*acc_R, d2 = 2*d1, d3 = 2*d2, d4 = 2*d3 = 16*acc_R; clear msm_add1, msm_x1, msm_y1, msm_collision_x1. row R+1: msm_transition = 0, msm_add = 1, msm_round = 32, msm_count = 0, msm_size_of_msm = 1, msm_pc = msm_pc[R], msm_add1 = 1, msm_slice1 = 0, (msm_x1, msm_y1) = -15*P; lambda1 = (d4.y - (-15*P).y) / (d4.x - (-15*P).x), collision_x1 = 1 / ((-15*P).x - d4.x); accumulator = d4. row R+2: msm_transition = 1; (acc_x, acc_y) = malicious_acc, where malicious_acc = d4 + (-15*P) = 16 * (2^124*OFFSET + s*P) - 15*P = 2^128 * OFFSET + (16s - 15) * P.

Transcript columns also need to be patched at the row t with transcript_msm_transition = 1: transcript_msm_x/y = malicious_acc; intermediate = malicious_acc - 2^124 * ECCVM_OFFSET_GENERATOR (do this via affine subtraction; remember offset_affine.y is negated to subtract); transcript_msm_intermediate_x/y = intermediate; transcript_msm_x_inverse = 1 / (malicious_acc.x - (-offset).x); transcript_base_x_inverse = 1 / intermediate.x; transcript_base_y_inverse = 1 / intermediate.y; at row t+1 (transcript accumulator after add): (transcript_accumulator_x/y, Px, Py) = intermediate (the running accumulator was empty after eq_and_reset, so add returns lhs).

Lookup-inverse hygiene: row R is no longer active for the lookup relation after the q_skew -> q_double swap, but compute_logderivative_inverse only overwrites active rows, so explicitly clear polynomials.lookup_inverses.at(R) = 0 before re-running set_shifted().

With the fix, the new gate rejects the malicious trace at row R: msm_double[R+1] = 1 demands an inverse witness for (msm_round[R] - 31), and msm_round[R] - 31 = 0 has none. Without the fix, every relation (MSM, Bools, Transcript, Set, Lookup) accepted the patched trace.

Definition at line 535 of file eccvm_relation_corruption.test.cpp.

TEST_F() [7/9]

TEST_F	(	ECCVMRelationCorruptionTests	,
		MSMRelationRejectsTransitionZeroOnFirstRow
	)

Regression test for the MSM-start anchor (MSM_TRANSITION_AT_ACTIVE_START).

The full attack (pre-fix): first_add is gated on msm_transition: when msm_transition = 0 the chain begins from the row's witness (acc_x, acc_y) instead of offset_generator. A prover flips msm_transition[first_msm_row] from 1 to 0, replaces (acc_x, acc_y) at that row with any chosen point A, recomputes lambda1 and the resulting acc_shift, and propagates the new (acc_x, acc_y) chain through every subsequent ADD/DOUBLE/SKEW row of the MSM. The set relation's third term cross-checks (msm_acc_x_shift, msm_acc_y_shift) at the synthetic-final sentinel against the transcript's transcript_msm_(x,y), which the prover patches to match. The transcript subtracts a fixed offset_generator, so the user-visible MSM result is shifted by (A - offset_generator).

What this test proves: that the new MSM_TRANSITION_AT_ACTIVE_START subrelation fires on the msm_transition flip. We do NOT recompute the acc/lambda chain or the transcript patches – the point of the test is to certify that the missing pin is now in place, not to reconstruct the full forgery.

Why the minimal flip is a faithful regression target: On the honest trace, (acc_x, acc_y) at the first MSM row is exactly offset_generator. With those values, first_add produces the same output for both msm_transition branches (selector = 1 plants offset_generator literal; selector = 0 reads (acc_x, acc_y) which equals offset_generator). So the flip is invisible to every relation that consumes acc downstream – pre-fix every relation passed despite the flip (this is precisely what made the attack viable). Post-fix, the new gate detects the flip directly and the rest of the trace is unchanged.

Trace layout (recall TRACE_OFFSET disabled rows precede the active region): rows 0..TRACE_OFFSET-1 – disabled head region row TRACE_OFFSET – lagrange_first, all phase selectors off row TRACE_OFFSET + 1 – first MSM row: q_add = 1, msm_transition = 1 honestly

Where the new subrelation is non-trivial: curr_not_phase * next_phase * (msm_transition_shift - 1) is checked at every row. The first two factors are simultaneously non-zero only at "MSM-start boundaries" – rows whose successor activates a phase: lagrange_first -> first MSM, and synthetic-final sentinel of one MSM -> start of the next. The third factor pins msm_transition to 1 on the next row at every such boundary. This fixture has a single MSM, so the lagrange_first row is the only such boundary. Flipping msm_transition[TRACE_OFFSET + 1] from 1 to 0 makes the third factor -1 at row TRACE_OFFSET and the relation fails.

Definition at line 608 of file eccvm_relation_corruption.test.cpp.

TEST_F() [8/9]

TEST_F	(	ECCVMRelationCorruptionTests	,
		ShiftableInitFailsOnZPermNonZeroAtFirstRow
	)

Test that z_perm must be zero at the lagrange_first row.

The set relation grand product relies on z_perm[lagrange_first row] = 0 so that (z_perm + lagrange_first) evaluates to 1 at the first row. Sub-relation Z_PERM_INIT (lagrange_first * z_perm = 0) — housed in ECCVMShiftableInitRelation — enforces this.

We cross-check the lagrange_first position two ways:

1. Structurally: z_perm.start_index() - 1 (the zero row before the shiftable region)
2. By scanning the lagrange_first polynomial for its non-zero entry

Definition at line 427 of file eccvm_relation_corruption.test.cpp.

TEST_F() [9/9]

TEST_F	(	ECCVMRelationCorruptionTests	,
		TranscriptNoOpRowRejectsAccumulatorNotEmpty
	)

On a transcript no-op row, setting accumulator_not_empty=1 must be caught by the ACCUMULATOR_EMPTY_UPDATE subrelation.

The accumulator_infinity_from_noop term in that subrelation forces is_accumulator_empty_shift = 1 whenever all selectors are zero. This test corrupts the shifted value (i.e. accumulator_not_empty at row+1) to 1 and verifies detection.

Definition at line 390 of file eccvm_relation_corruption.test.cpp.