row_disabling_polynomial.test.cpp

Go to the documentation of this file.

#include "barretenberg/polynomials/row_disabling_polynomial.hpp"
#include "barretenberg/ecc/curves/bn254/fr.hpp"
#include "barretenberg/flavor/sumcheck_test_flavor.hpp"
#include "barretenberg/sumcheck/sumcheck.hpp"
#include "barretenberg/transcript/transcript.hpp"
 
#include <gtest/gtest.h>
 
using namespace bb;
 
template <typename Flavor> class RowDisablingPolynomialTest : public ::testing::Test {
  public:
    using FF = typename Flavor::FF;
    using ProverPolynomials = typename Flavor::ProverPolynomials;
    using SumcheckRound = SumcheckProverRound<Flavor>;
    using ZKData = ZKSumcheckData<Flavor>;
    using SubrelationSeparators = std::array<FF, Flavor::NUM_SUBRELATIONS - 1>;
 
    struct SumcheckSetup {
        RelationParameters<FF> relation_parameters;
        std::vector<FF> gate_challenges;
        GateSeparatorPolynomial<FF> gate_separators;
        SubrelationSeparators alphas;
        FF alpha;
    };
 
    static SumcheckSetup create_sumcheck_setup(size_t multivariate_d)
    {
        auto transcript = Flavor::Transcript::test_prover_init_empty();
        FF alpha = transcript->template get_challenge<FF>("Sumcheck:alpha");
 
        std::vector<FF> gate_challenges(multivariate_d);
        for (size_t idx = 0; idx < multivariate_d; idx++) {
            gate_challenges[idx] =
                transcript->template get_challenge<FF>("Sumcheck:gate_challenge_" + std::to_string(idx));
        }
 
        GateSeparatorPolynomial<FF> gate_separators(gate_challenges, multivariate_d);
 
        // Compute alphas as consecutive powers of alpha
        SubrelationSeparators alphas;
        alphas[0] = alpha;
        for (size_t i = 1; i < Flavor::NUM_SUBRELATIONS - 1; ++i) {
            alphas[i] = alphas[i - 1] * alpha;
        }
 
        RelationParameters<FF> relation_parameters{
            .beta = FF(2),
            .gamma = FF(3),
            .public_input_delta = FF::one(),
        };
 
        return SumcheckSetup{
            .relation_parameters = relation_parameters,
            .gate_challenges = gate_challenges,
            .gate_separators = gate_separators,
            .alphas = alphas,
            .alpha = alpha,
        };
    }
};
 
TEST(RowDisablingPolynomial, MasksRandomPaddingRows)
{
    using Flavor = SumcheckTestFlavorZK;
    using FF = typename Flavor::FF;
    using ProverPolynomials = typename Flavor::ProverPolynomials;
    using ZKData = ZKSumcheckData<Flavor>;
 
    // Use same circuit size as existing ZK tests
    const size_t multivariate_d = 3; // log2(circuit_size) = 3 → 8 rows
    const size_t multivariate_n = 1 << multivariate_d;
    const size_t virtual_log_n = multivariate_d; // No padding rounds
    const size_t NUM_POLYNOMIALS = Flavor::NUM_ALL_ENTITIES;
 
    // Setup: Valid relations at rows 4+ (after disabled region), random junk at rows 0-3.
    // The first 4 rows are disabled by the row-disabling polynomial.
    std::array<FF, multivariate_n> w_l = { 0, 0, 0, 0, 1, 2, 0, 0 };
    std::array<FF, multivariate_n> w_r = { 0, 0, 0, 0, 1, 2, 0, 0 };
    std::array<FF, multivariate_n> w_o = { 0, 0, 0, 0, 2, 4, 0, 0 };
    std::array<FF, multivariate_n> w_4 = { 0, 0, 0, 0, 0, 0, 0, 0 };
    std::array<FF, multivariate_n> q_m = { 0, 0, 0, 0, 0, 1, 0, 0 };
    std::array<FF, multivariate_n> q_l = { 0, 0, 0, 0, 1, 0, 0, 0 };
    std::array<FF, multivariate_n> q_r = { 0, 0, 0, 0, 1, 0, 0, 0 };
    std::array<FF, multivariate_n> q_o = { 0, 0, 0, 0, -1, -1, 0, 0 };
    std::array<FF, multivariate_n> q_c = { 0, 0, 0, 0, 0, 0, 0, 0 };
    std::array<FF, multivariate_n> q_arith = { 0, 0, 0, 0, 1, 1, 0, 0 };
 
    // Critical: Add RANDOM values to the first 4 rows (indices 0-3, the disabled region).
    // These would normally break sumcheck, but RowDisablingPolynomial disables their contribution.
    for (size_t i = 0; i < NUM_DISABLED_ROWS_IN_SUMCHECK; i++) {
        w_l[i] = FF::random_element();
        w_r[i] = FF::random_element();
        w_o[i] = FF::random_element();
        w_4[i] = FF::random_element();
        q_m[i] = FF::random_element();
        q_l[i] = FF::random_element();
        q_r[i] = FF::random_element();
        q_o[i] = FF::random_element();
        q_c[i] = FF::random_element();
        q_arith[i] = FF(1); // Enable arithmetic relation
    }
 
    // Setup z_perm, lookup_inverses with random values in disabled rows
    // SumcheckTestFlavor doesn't need z_perm, lookup_inverses, lookup_read_counts
    // Random values in witness polynomials are sufficient for testing row disabling
 
    // Create zero polynomials for all entities
    std::vector<bb::Polynomial<FF>> zero_polynomials(NUM_POLYNOMIALS);
    for (auto& poly : zero_polynomials) {
        poly = bb::Polynomial<FF>(multivariate_n);
    }
 
    // Assign to ProverPolynomials
    ProverPolynomials full_polynomials;
    for (auto [full_poly, zero_poly] : zip_view(full_polynomials.get_all(), zero_polynomials)) {
        full_poly = zero_poly.share();
    }
 
    // Override with our constructed polynomials
    full_polynomials.w_l = bb::Polynomial<FF>(w_l);
    full_polynomials.w_r = bb::Polynomial<FF>(w_r);
    full_polynomials.w_o = bb::Polynomial<FF>(w_o);
    full_polynomials.w_4 = bb::Polynomial<FF>(w_4);
    full_polynomials.q_m = bb::Polynomial<FF>(q_m);
    full_polynomials.q_l = bb::Polynomial<FF>(q_l);
    full_polynomials.q_r = bb::Polynomial<FF>(q_r);
    full_polynomials.q_o = bb::Polynomial<FF>(q_o);
    full_polynomials.q_c = bb::Polynomial<FF>(q_c);
    full_polynomials.q_arith = bb::Polynomial<FF>(q_arith);
 
    // SumcheckTestFlavor doesn't have z_perm, lookup_inverses, lookup_read_counts
    // The row disabling mechanism will handle the random values in witness polynomials
 
    // Set relation parameters (SumcheckTestFlavor doesn't need beta/gamma)
    RelationParameters<FF> relation_parameters{};
 
    // Prover: Run ZK Sumcheck with RowDisablingPolynomial
    auto prover_transcript = Flavor::Transcript::test_prover_init_empty();
    FF prover_alpha = prover_transcript->template get_challenge<FF>("Sumcheck:alpha");
 
    std::vector<FF> prover_gate_challenges(virtual_log_n);
    for (size_t idx = 0; idx < virtual_log_n; idx++) {
        prover_gate_challenges[idx] =
            prover_transcript->template get_challenge<FF>("Sumcheck:gate_challenge_" + std::to_string(idx));
    }
 
    SumcheckProver<Flavor> sumcheck_prover(multivariate_n,
                                           full_polynomials,
                                           prover_transcript,
                                           prover_alpha,
                                           prover_gate_challenges,
                                           relation_parameters,
                                           virtual_log_n);
 
    // ZK Sumcheck: this will use RowDisablingPolynomial to mask the last 4 rows
    ZKData zk_sumcheck_data = ZKData(multivariate_d, prover_transcript);
    SumcheckOutput<Flavor> prover_output = sumcheck_prover.prove(zk_sumcheck_data);
 
    // Verifier
    auto verifier_transcript = Flavor::Transcript::test_verifier_init_empty(prover_transcript);
 
    // Extract challenges from verifier transcript (must match prover)
    FF verifier_alpha = verifier_transcript->template get_challenge<FF>("Sumcheck:alpha");
    std::vector<FF> verifier_gate_challenges(virtual_log_n);
    for (size_t idx = 0; idx < virtual_log_n; idx++) {
        verifier_gate_challenges[idx] =
            verifier_transcript->template get_challenge<FF>("Sumcheck:gate_challenge_" + std::to_string(idx));
    }
 
    auto sumcheck_verifier = SumcheckVerifier<Flavor>(verifier_transcript, verifier_alpha, virtual_log_n);
 
    auto verifier_output = sumcheck_verifier.verify(relation_parameters, verifier_gate_challenges);
 
    // Verification: Despite random values in last 4 rows, sumcheck succeeds
    EXPECT_TRUE(verifier_output.verified)
        << "ZK Sumcheck should succeed with RowDisablingPolynomial masking random padding rows";
 
    // Verify challenges match
    EXPECT_EQ(prover_output.challenge.size(), verifier_output.challenge.size());
    for (size_t i = 0; i < prover_output.challenge.size(); i++) {
        EXPECT_EQ(prover_output.challenge[i], verifier_output.challenge[i]);
    }
}
 
TEST(RowDisablingPolynomial, ComputeDisabledContribution)
{
    using Flavor = SumcheckTestFlavorZK;
    using TestFixture = RowDisablingPolynomialTest<Flavor>;
    using FF = typename Flavor::FF;
    using ProverPolynomials = typename Flavor::ProverPolynomials;
    using SumcheckRound = typename TestFixture::SumcheckRound;
 
    const size_t multivariate_d = 4; // 16 rows
    const size_t multivariate_n = 1 << multivariate_d;
    const size_t NUM_POLYNOMIALS = Flavor::NUM_ALL_ENTITIES;
    const size_t NUM_DISABLED_ROWS = 4;
 
    // Create simple test polynomials with known values in the first 4 rows (disabled region)
    std::vector<bb::Polynomial<FF>> test_polynomials(NUM_POLYNOMIALS);
    for (auto& poly : test_polynomials) {
        poly = bb::Polynomial<FF>(multivariate_n);
        // Set specific values in the disabled rows (0-3) for easier verification
        for (size_t i = 0; i < NUM_DISABLED_ROWS; i++) {
            poly.at(i) = FF(i + 1); // Non-zero, predictable values
        }
    }
 
    ProverPolynomials full_polynomials;
    for (auto [full_poly, test_poly] : zip_view(full_polynomials.get_all(), test_polynomials)) {
        full_poly = test_poly.share();
    }
 
    // Use fixture to create standard sumcheck setup
    auto setup = TestFixture::create_sumcheck_setup(multivariate_d);
 
    // Initialize row disabling polynomial
    RowDisablingPolynomial<FF> row_disabling_polynomial; // Default constructor
 
    // Test Round 1: After partially evaluating with u_0
    {
        FF u_0 = FF::random_element();
 
        // Create partially evaluated polynomials (simplified for test)
        typename Flavor::PartiallyEvaluatedMultivariates partially_evaluated(full_polynomials, multivariate_n);
        for (auto [pe_poly, full_poly] : zip_view(partially_evaluated.get_all(), full_polynomials.get_all())) {
            // Simulate partial evaluation: P(u_0, X_1, ...)
            for (size_t i = 0; i < multivariate_n / 2; i++) {
                // P(u_0, i_1, i_2, ...) = P(0, i_1, ...) + u_0 * (P(1, i_1, ...) - P(0, i_1, ...))
                pe_poly.at(i) = full_poly[2 * i] + (u_0 * (full_poly[(2 * i) + 1] - full_poly[2 * i]));
            }
        }
 
        SumcheckRound round(multivariate_n / 2);
 
        // Update row disabling polynomial after round 0 with challenge u_0
        row_disabling_polynomial.update_evaluations(u_0, 0);
        // After round 0: no change to eval_at_0 or eval_at_1 (rounds 0,1 don't accumulate products)
        EXPECT_EQ(row_disabling_polynomial.eval_at_0, FF(1));
        EXPECT_EQ(row_disabling_polynomial.eval_at_1, FF(1));
 
        // Now update for round 1
        FF u_1 = FF::random_element();
        row_disabling_polynomial.update_evaluations(u_1, 1);
        // After round 1: eval_at_1 becomes 0 (L collapses to a single edge pair)
        EXPECT_EQ(row_disabling_polynomial.eval_at_0, FF(1));
        EXPECT_EQ(row_disabling_polynomial.eval_at_1, FF(0));
    }
 
    // Test that row disabling factor equals X_2 × X_3 × ... × X_{d-1}
    {
        std::vector<FF> challenges(multivariate_d);
        for (auto& c : challenges) {
            c = FF::random_element();
        }
 
        // Compute using the optimized method
        FF eval = RowDisablingPolynomial<FF>::evaluate_at_challenge(challenges, multivariate_d);
 
        // The disabled rows are 0,1,2,3. Their Lagrange polys are:
        // L_0 = (1-X_0)(1-X_1)(1-X_2)...(1-X_{d-1})
        // L_1 = X_0(1-X_1)(1-X_2)...(1-X_{d-1})
        // L_2 = (1-X_0)X_1(1-X_2)...(1-X_{d-1})
        // L_3 = X_0 X_1(1-X_2)...(1-X_{d-1})
        // Sum = (1-X_2)...(1-X_{d-1}) * [(1-X_0)(1-X_1) + X_0(1-X_1) + (1-X_0)X_1 + X_0 X_1]
        //     = ∏_{i≥2}(1-X_i)
 
        FF expected_sum_lagranges = FF(1);
        for (size_t i = 2; i < multivariate_d; i++) {
            expected_sum_lagranges *= (FF(1) - challenges[i]);
        }
 
        FF expected_eval = FF(1) - expected_sum_lagranges;
 
        EXPECT_EQ(eval, expected_eval) << "Row disabling polynomial should equal 1 - ∏_{i≥2}(1 - X_i)";
    }
}
 
TEST(RowDisablingPolynomial, FailsWithoutRowDisabling)
{
    using Flavor = SumcheckTestFlavor; // Non-ZK flavor (no RowDisablingPolynomial)
    using FF = typename Flavor::FF;
    using ProverPolynomials = typename Flavor::ProverPolynomials;
 
    const size_t NUM_RANDOM_ROWS = 4;
    const size_t multivariate_d = 4;
    const size_t multivariate_n = 1 << multivariate_d;
    const size_t virtual_log_n = multivariate_d;
    const size_t NUM_POLYNOMIALS = Flavor::NUM_ALL_ENTITIES;
    const size_t valid_rows = multivariate_n - NUM_RANDOM_ROWS;
 
    // Create arrays for polynomial coefficients
    std::vector<FF> w_l(multivariate_n);
    std::vector<FF> w_r(multivariate_n);
    std::vector<FF> w_o(multivariate_n);
    std::vector<FF> w_4(multivariate_n);
    std::vector<FF> q_m(multivariate_n);
    std::vector<FF> q_l(multivariate_n);
    std::vector<FF> q_r(multivariate_n);
    std::vector<FF> q_o(multivariate_n);
    std::vector<FF> q_c(multivariate_n);
    std::vector<FF> q_arith(multivariate_n);
 
    // Setup valid circuit in first rows
    for (size_t i = 0; i < valid_rows; i++) {
        w_l[i] = FF(i);
        w_r[i] = FF(i + 1);
        w_o[i] = -FF((2 * i) + 1);
        w_4[i] = FF(0);
        q_m[i] = FF(0);
        q_l[i] = FF(1);
        q_r[i] = FF(1);
        q_o[i] = FF(1);
        q_c[i] = FF(0);
        q_arith[i] = FF(1);
    }
 
    // Add random values to last rows (this WILL break sumcheck for non-ZK flavor)
    for (size_t i = valid_rows; i < multivariate_n; i++) {
        w_l[i] = FF::random_element();
        w_r[i] = FF::random_element();
        w_o[i] = FF::random_element();
        w_4[i] = FF::random_element();
        q_m[i] = FF::random_element();
        q_l[i] = FF::random_element();
        q_r[i] = FF::random_element();
        q_o[i] = FF::random_element();
        q_c[i] = FF::random_element();
        q_arith[i] = FF(1); // Keep enabled
    }
 
    // SumcheckTestFlavor doesn't need z_perm, lookup_inverses, lookup_read_counts
 
    // Create random polynomials for remaining entities
    std::vector<bb::Polynomial<FF>> random_polynomials(NUM_POLYNOMIALS);
    for (auto& poly : random_polynomials) {
        poly = bb::Polynomial<FF>(multivariate_n);
        for (size_t i = 0; i < multivariate_n; i++) {
            poly.at(i) = FF::random_element();
        }
    }
 
    ProverPolynomials full_polynomials;
    for (auto [full_poly, random_poly] : zip_view(full_polynomials.get_all(), random_polynomials)) {
        full_poly = random_poly.share();
    }
 
    // Override with our constructed polynomials
    full_polynomials.w_l = bb::Polynomial<FF>(w_l);
    full_polynomials.w_r = bb::Polynomial<FF>(w_r);
    full_polynomials.w_o = bb::Polynomial<FF>(w_o);
    full_polynomials.w_4 = bb::Polynomial<FF>(w_4);
    full_polynomials.q_m = bb::Polynomial<FF>(q_m);
    full_polynomials.q_l = bb::Polynomial<FF>(q_l);
    full_polynomials.q_r = bb::Polynomial<FF>(q_r);
    full_polynomials.q_o = bb::Polynomial<FF>(q_o);
    full_polynomials.q_c = bb::Polynomial<FF>(q_c);
    full_polynomials.q_arith = bb::Polynomial<FF>(q_arith);
 
    // SumcheckTestFlavor doesn't have z_perm, lookup_inverses, lookup_read_counts
 
    // Set relation parameters (SumcheckTestFlavor doesn't need beta/gamma)
    RelationParameters<FF> relation_parameters{};
 
    auto prover_transcript = Flavor::Transcript::test_prover_init_empty();
    FF prover_alpha = prover_transcript->template get_challenge<FF>("Sumcheck:alpha");
 
    std::vector<FF> prover_gate_challenges(virtual_log_n);
    for (size_t idx = 0; idx < virtual_log_n; idx++) {
        prover_gate_challenges[idx] =
            prover_transcript->template get_challenge<FF>("Sumcheck:gate_challenge_" + std::to_string(idx));
    }
 
    SumcheckProver<Flavor> sumcheck_prover(multivariate_n,
                                           full_polynomials,
                                           prover_transcript,
                                           prover_alpha,
                                           prover_gate_challenges,
                                           relation_parameters,
                                           virtual_log_n);
 
    // Non-ZK Sumcheck (no RowDisablingPolynomial)
    SumcheckOutput<Flavor> prover_output = sumcheck_prover.prove();
 
    auto verifier_transcript = Flavor::Transcript::test_verifier_init_empty(prover_transcript);
 
    // Extract challenges from verifier transcript (must match prover)
    FF verifier_alpha = verifier_transcript->template get_challenge<FF>("Sumcheck:alpha");
    std::vector<FF> verifier_gate_challenges(virtual_log_n);
    for (size_t idx = 0; idx < virtual_log_n; idx++) {
        verifier_gate_challenges[idx] =
            verifier_transcript->template get_challenge<FF>("Sumcheck:gate_challenge_" + std::to_string(idx));
    }
 
    auto sumcheck_verifier = SumcheckVerifier<Flavor>(verifier_transcript, verifier_alpha, virtual_log_n);
 
    auto verifier_output = sumcheck_verifier.verify(relation_parameters, verifier_gate_challenges);
 
    // Without RowDisablingPolynomial, sumcheck should FAIL with random padding
    EXPECT_FALSE(verifier_output.verified)
        << "Non-ZK Sumcheck should FAIL when random values break relations (no RowDisablingPolynomial)";
}