eq_polynomial.test.cpp

Go to the documentation of this file.

#include "barretenberg/polynomials/eq_polynomial.hpp"
#include "barretenberg/common/assert.hpp"
#include "barretenberg/ecc/curves/bn254/fr.hpp"
#include "gate_separator.hpp"
#include <algorithm>
#include <array>
#include <cstdint>
#include <gtest/gtest.h>
#include <span>
#include <vector>
 
using namespace bb;
 
// -----------------------------------------------------------------------------
// Fixture with helpers (no logic changes)
// -----------------------------------------------------------------------------
class EqPolyTest : public ::testing::Test {
  public:
    using FF = bb::fr;
 
  protected:
    // eq(r,u) = ∏_i ((1 - r_i)(1 - u_i) + r_i u_i)
    static FF eq_manual(std::span<const FF> r, std::span<const FF> u)
    {
        EXPECT_EQ(r.size(), u.size());
        FF acc = FF(1);
        for (size_t i = 0; i < r.size(); ++i) {
            const FF term = (FF(1) - r[i]) * (FF(1) - u[i]) + r[i] * u[i];
            acc *= term;
        }
        return acc;
    }
 
    // Boolean vector of length d from mask (LSB -> index 0)
    static std::vector<FF> bool_vec_from_mask(size_t d, uint64_t mask)
    {
        std::vector<FF> v(d);
        for (size_t i = 0; i < d; ++i) {
            v[i] = FF((mask >> i) & 1ULL);
        }
        return v;
    }
 
    // γ = r / (1 - r)
    static std::vector<FF> to_gamma(std::span<const FF> r)
    {
        std::vector<FF> g(r.size());
        for (size_t i = 0; i < r.size(); ++i) {
            g[i] = r[i] * (FF(1) - r[i]).invert();
        }
        return g;
    }
};
 
// -----------------------------------------------------------------------------
// VerifierEqPolynomial tests
// -----------------------------------------------------------------------------
 
TEST_F(EqPolyTest, InitializeCoeffs)
{
    const std::vector<FF> r = { 0, 1, 2, 3 };
    VerifierEqPolynomial<FF> eq(r);
 
    ASSERT_EQ(eq.r.size(), 4);
    ASSERT_EQ(eq.a.size(), 4);
    ASSERT_EQ(eq.b.size(), 4);
 
    // a_i = 2r_i - 1 ; b_i = 1 - r_i
    EXPECT_EQ(eq.a[0], FF(-1));
    EXPECT_EQ(eq.a[1], FF(1));
    EXPECT_EQ(eq.a[2], FF(3));
    EXPECT_EQ(eq.a[3], FF(5));
 
    EXPECT_EQ(eq.b[0], FF(1));
    EXPECT_EQ(eq.b[1], FF(0));
    EXPECT_EQ(eq.b[2], FF(-1));
    EXPECT_EQ(eq.b[3], FF(-2));
}
 
TEST_F(EqPolyTest, EvaluateMatchesManualSmall)
{
    const std::vector<FF> r = { 0, 1, 2, 3, 4 };
    const std::vector<FF> u = { 5, 6, 7, 8, 9 };
 
    VerifierEqPolynomial<FF> eq(r);
    const FF got = eq.evaluate(u);
    const FF expect = eq_manual(r, u);
 
    EXPECT_EQ(got, expect);
}
 
TEST_F(EqPolyTest, StaticEvalMatchesMemberEvaluate)
{
    const std::vector<FF> r = { 2, 0, 5, 1 };
    const std::vector<FF> u = { 3, 7, 4, 6 };
 
    const FF s = VerifierEqPolynomial<FF>::eval(r, u);
    VerifierEqPolynomial<FF> eq(r);
    const FF m = eq.evaluate(u);
 
    EXPECT_EQ(s, m);
}
 
TEST_F(EqPolyTest, SymmetryEqRUEqualsEqUR)
{
    const std::vector<FF> r = { 0, 2, 4, 6, 8 };
    const std::vector<FF> u = { 1, 3, 5, 7, 9 };
 
    VerifierEqPolynomial<FF> eq_r(r);
    VerifierEqPolynomial<FF> eq_u(u);
 
    const FF ru = eq_r.evaluate(u);
    const FF ur = eq_u.evaluate(r);
 
    EXPECT_EQ(ru, ur);
}
 
TEST_F(EqPolyTest, BooleanDeltaBehavior)
{
    constexpr int d = 5;
 
    const auto make_bool_vec = [&](size_t mask) {
        std::vector<FF> v(d);
        for (size_t i = 0; i < d; ++i) {
            v[i] = FF((mask >> i) & 1);
        }
        return v;
    };
 
    for (size_t R = 0; R < (1u << d); ++R) {
        const auto r = make_bool_vec(R);
        VerifierEqPolynomial<FF> eq(r);
        for (size_t U = 0; U < (1u << d); ++U) {
            const auto u = make_bool_vec(U);
            const FF val = eq.evaluate(u);
            if (R == U) {
                EXPECT_EQ(val, FF(1)) << "R=" << R << " U=" << U;
            } else {
                EXPECT_EQ(val, FF(0)) << "R=" << R << " U=" << U;
            }
        }
    }
}
 
TEST_F(EqPolyTest, EdgeCases)
{
    // d = 0: empty product = 1
    {
        std::vector<FF> r, u;
        const FF val = VerifierEqPolynomial<FF>::eval(r, u);
        EXPECT_EQ(val, FF(1));
    }
 
    // d = 1: explicit formula check
    {
        const std::vector<FF> r = { 2 };
        const std::vector<FF> u = { 7 };
        const FF expect = (FF(1) - r[0]) * (FF(1) - u[0]) + r[0] * u[0];
 
        VerifierEqPolynomial<FF> eq(r);
        const FF got = eq.evaluate(u);
        EXPECT_EQ(got, expect);
    }
 
    // all zeros
    {
        const std::vector<FF> r(8, FF(0));
        const std::vector<FF> u(8, FF(0));
        VerifierEqPolynomial<FF> eq(r);
        EXPECT_EQ(eq.evaluate(u), FF(1));
    }
 
    // all ones
    {
        const std::vector<FF> r(8, FF(1));
        const std::vector<FF> u(8, FF(1));
        VerifierEqPolynomial<FF> eq(r);
        EXPECT_EQ(eq.evaluate(u), FF(1));
    }
 
    // alternating Boolean pattern
    {
        const std::vector<FF> r = { 0, 1, 0, 1, 0, 1, 0, 1 };
        const std::vector<FF> u = { 1, 0, 1, 0, 1, 0, 1, 0 };
        VerifierEqPolynomial<FF> eq(r);
        EXPECT_EQ(eq.evaluate(u), FF(0));
    }
}
 
// -----------------------------------------------------------------------------
// Prover/Verifier consistency
// -----------------------------------------------------------------------------
 
TEST_F(EqPolyTest, ProverTableMatchesVerifierOnBooleanPoints)
{
    const size_t d = 5;
 
    std::vector<FF> r(d);
    for (size_t i = 0; i < d; ++i) {
        r[i] = FF(2 * i + 7);
    }
 
    VerifierEqPolynomial<FF> v(r);
    // Assumes a static factory `construct(r, logN)` and `.at(idx)` accessor exist.
    auto peq = ProverEqPolynomial<FF>::construct(r, d);
 
    for (uint64_t ell = 0; ell < (1ULL << d); ++ell) {
        const auto u = bool_vec_from_mask(d, ell);
        const FF got_ver = v.evaluate(u);
        const FF got_prov = peq.at(ell);
        EXPECT_EQ(got_prov, got_ver) << "ell=" << ell;
    }
}
 
TEST_F(EqPolyTest, VerifierVsProverForArbitraryU)
{
    const size_t d = 5;
 
    std::vector<FF> r(d), u(d);
    for (size_t i = 0; i < d; ++i) {
        r[i] = FF(13 + i);
        u[i] = FF(17 + 2 * i);
    }
 
    VerifierEqPolynomial<FF> v(r);
    const FF ver_val = v.evaluate(u);
 
    // Prover-side normalized evaluation (no table here):
    FF C = FF(1);
    for (size_t i = 0; i < d; ++i) {
        C *= (FF(1) - r[i]);
    }
    const auto gamma = to_gamma(r);
 
    FF prov_val = FF(1);
    for (size_t i = 0; i < d; ++i) {
        prov_val *= (FF(1) + u[i] * (gamma[i] - FF(1)));
    }
    prov_val = C * prov_val;
 
    EXPECT_EQ(ver_val, prov_val);
}
 
TEST_F(EqPolyTest, PartialEvaluationConsistency)
{
    constexpr size_t d = 21;
    std::vector<FF> r(d);
    std::vector<FF> u(d);
    std::vector<FF> u_part(d);
    for (size_t i = 0; i < d; i++) {
        r[i] = FF::random_element();
        u[i] = FF::random_element();
        u_part[i] = 0;
    }
    auto current_element = VerifierEqPolynomial<FF>::eval(r, u_part);
    auto pol = ProverEqPolynomial<FF>::construct(r, d);
    for (size_t i = 0; i < d; i++) {
        u_part[i] = 1;
        auto new_element = VerifierEqPolynomial<FF>::eval(r, u_part);
        current_element = current_element + u[i] * (new_element - current_element);
        u_part[i] = u[i];
        EXPECT_EQ(current_element, VerifierEqPolynomial<FF>::eval(r, u_part));
    }
    EXPECT_EQ(current_element, VerifierEqPolynomial<FF>::eval(r, u));
}
 
// -----------------------------------------------------------------------------
// GateSeparatorPolynomial sanity checks
// -----------------------------------------------------------------------------
 
TEST_F(EqPolyTest, GateSeparatorPartialEvaluationConsistency)
{
    constexpr size_t d = 5;
 
    std::vector<FF> betas(d);
    for (auto& beta : betas) {
        beta = FF::random_element();
    }
 
    GateSeparatorPolynomial<FF> poly(betas);
 
    std::array<FF, d> variables{};
    for (auto& u_i : variables) {
        u_i = FF::random_element();
        poly.partially_evaluate(u_i);
    }
 
    FF expected_eval = FF(1);
    for (size_t i = 0; i < d; ++i) {
        expected_eval *= (FF(1) - variables[i]) + variables[i] * betas[i];
    }
 
    EXPECT_EQ(poly.partial_evaluation_result, expected_eval);
}
 
TEST_F(EqPolyTest, GateSeparatorBetaProductsOnPowers)
{
    const std::vector<FF> betas{ FF(2), FF(4), FF(16) };
    GateSeparatorPolynomial<FF> poly(betas, betas.size());
 
    const std::vector<FF> expected_values{
        FF(1), FF(2), FF(4), FF(8), FF(16), FF(32), FF(64), FF(128),
    };
 
    EXPECT_EQ(Polynomial<FF>(expected_values), Polynomial<FF>(poly.beta_products));
}
 
TEST_F(EqPolyTest, ProverEqAllChallengesAreOnes)
{
    // r = [1,1,...,1]  =>  eq(X,r) = ∏ X_i
    // Coeff table is zero everywhere except the mask with all bits set.
    const size_t d = 6;
    const size_t N = 1UL << d;
 
    const std::vector<FF> r(d, FF(1));
 
    const auto coeffs = ProverEqPolynomial<FF>::construct(r, d);
    ASSERT_EQ(coeffs.size(), N);
 
    const size_t all_ones_mask = N - 1;
 
    for (size_t m = 0; m < N; ++m) {
        const FF got = coeffs.get(m);
        const FF expect = (m == all_ones_mask) ? FF(1) : FF(0);
        EXPECT_EQ(got, expect) << "mask=" << m;
    }
}
 
TEST_F(EqPolyTest, ProverEqSomeChallengesAreOnes)
{
    // Force a couple of indices to 1 so those bits must be set in any nonzero coefficient.
    // Choose unfixed entries away from 1 so batch invert is safe.
    // d = 5, force bits {1,3}
    const size_t d = 5;
    const size_t N = 1UL << d;
    std::vector<FF> r = { FF(7), FF(1), FF(9), FF(1), FF(11) }; // indices 1 and 3 are forced
    const std::vector<size_t> forced = { 1, 3 };
 
    const auto coeffs = ProverEqPolynomial<FF>::construct(r, d);
    ASSERT_EQ(coeffs.size(), N);
 
    VerifierEqPolynomial<FF> verifier(r);
 
    for (size_t mask = 0; mask < N; ++mask) {
        // Build Boolean u from mask and compare against verifier eval.
        const auto u = bool_vec_from_mask(d, mask);
        const FF verifier_val = verifier.evaluate(u);
 
        // Structural property: coeff[mask] == 0 unless all forced bits are set in mask.
        const bool has_all_forced = std::ranges::all_of(forced, [&](size_t bit) { return ((mask >> bit) & 1U) != 0; });
 
        const FF table_val = coeffs.get(mask);
 
        if (!has_all_forced) {
            EXPECT_EQ(table_val, FF(0)) << "mask missing forced bits, mask=" << mask;
        } else {
            // When forced bits are present, table coefficient should match eq(r, u) on that Boolean point.
            EXPECT_EQ(table_val, verifier_val) << "mask=" << mask;
        }
    }
}
 
// ProverEqPolynomial::construct asserts when challenges.size() < log_num_monomials.
TEST_F(EqPolyTest, ConstructRejectsTooFewChallenges)
{
    GTEST_FLAG_SET(death_test_style, "threadsafe");
    std::vector<FF> r = { FF(7), FF(9) }; // size 2, but we ask for 3 variables
    ASSERT_THROW_OR_ABORT(ProverEqPolynomial<FF>::construct(r, /*log_num_monomials=*/3), ".*");
}
 
// ProverEqPolynomial::construct accepts challenges.size() > log_num_monomials (truncated eq-table).
TEST_F(EqPolyTest, ConstructAcceptsExtraChallenges)
{
    std::vector<FF> r = { FF(7), FF(11), FF(13), FF(17), FF(19) }; // size 5
    const size_t log_num_monomials = 3;
    const auto coeffs = ProverEqPolynomial<FF>::construct(r, log_num_monomials);
    EXPECT_EQ(coeffs.size(), 1UL << log_num_monomials);
}
 
// ProverEqPolynomial::construct returns the empty-product constant [1] for log_num_monomials=0.
TEST_F(EqPolyTest, ConstructZeroVariablesReturnsOne)
{
    std::vector<FF> empty_challenges;
    const auto coeffs = ProverEqPolynomial<FF>::construct(empty_challenges, /*log_num_monomials=*/0);
    ASSERT_EQ(coeffs.size(), 1UL);
    EXPECT_EQ(coeffs.get(0), FF(1));
}