eq_polynomial.hpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: Complete, auditors: [Nishat], commit: 94f596f8b3bbbc216f9ad7dc33253256141156b2 }
// external_1:  { status: not started, auditors: [], commit: }
// external_2:  { status: not started, auditors: [], commit: }
// =====================
 
#pragma once
#include "barretenberg/common/bb_bench.hpp"
#include "barretenberg/common/compiler_hints.hpp"
#include "barretenberg/common/thread.hpp"
#include "barretenberg/numeric/bitop/get_msb.hpp"
#include "barretenberg/stdlib/primitives/bool/bool.hpp"
#include "gate_separator.hpp"
 
#include <cstddef>
#include <vector>
namespace bb {
 
template <typename FF> class ProverEqPolynomial {
 
  public:
    static Polynomial<FF> construct(std::span<const FF> challenges, size_t log_num_monomials)
    {
        // Prevent OOB read: compute_beta_products below (and construct_eq_with_edge_cases on the fallback path) read
        // challenges[0..log_num_monomials).
        BB_ASSERT_GTE(challenges.size(),
                      log_num_monomials,
                      "ProverEqPolynomial::construct: challenges.size() must be >= log_num_monomials");
 
        // eq over 0 variables is the empty product 1.
        if (log_num_monomials == 0) {
            Polynomial<FF> result(/*size=*/1, /*virtual_size=*/1);
            result.at(0) = FF(1);
            return result;
        }
 
        // Compute scaling factor C = ∏_i (1 - r_i)
        FF scaling_factor = compute_scaling_factor(challenges);
 
        // In production, challenges are generated by hashing the transcript, hence with high probability
        // none of them equals 1. If C = 0, at least one r_i = 1, so we must use the fallback method.
        if (scaling_factor.is_zero()) {
            return construct_eq_with_edge_cases(challenges, log_num_monomials);
        }
 
        // Optimal path: transform to γ_i = r_i / (1 - r_i) and delegate to pow_β algorithm
        return GateSeparatorPolynomial<FF>::compute_beta_products(
            transform_challenge(challenges), log_num_monomials, scaling_factor);
    };
 
    static FF compute_scaling_factor(std::span<const FF> challenge)
    {
        FF out(1);
        const FF one(1);
        for (auto u_i : challenge) {
            out *= (one - u_i);
        }
        return out;
    }
 
    static std::vector<FF> transform_challenge(std::span<const FF> challenges)
    {
        std::vector<FF> result;
        std::vector<FF> denominators;
        denominators.reserve(challenges.size());
        result.reserve(challenges.size());
        for (const auto& challenge : challenges) {
            denominators.push_back((FF(1) - challenge));
        }
 
        FF::batch_invert(denominators);
 
        for (const auto& [denom_inverted, challenge] : zip_view(denominators, challenges)) {
            result.push_back(denom_inverted * challenge);
        }
 
        return result;
    }
 
    static Polynomial<FF> construct_eq_with_edge_cases(std::span<const FF> r, size_t log_num_monomials)
    {
        const size_t d = r.size();
        BB_ASSERT_EQ(d, log_num_monomials, "expect log_num_monomials == r.size()");
        const size_t N = 1UL << d;
 
        // Precompute per-variable linear/constant coeffs:
        // eq(X,r) = ∏_i ( b_i + a_i X_i ),  a_i = 2r_i - 1,  b_i = 1 - r_i
        std::vector<FF> eq_linear_coeffs(d);
        std::vector<FF> eq_constant_coeffs(d);
        for (size_t i = 0; i < d; ++i) {
            eq_linear_coeffs[i] = r[i] + r[i] - FF(1); // a_i
            eq_constant_coeffs[i] = FF(1) - r[i];      // b_i
        }
 
        // Start with table size 1: [1]
        Polynomial<FF> current(
            /*size*/ 1, /*virtual_size*/ N, /*start_index*/ 0, Polynomial<FF>::DontZeroMemory::FLAG);
        current.at(0) = FF(1);
 
        // Grow one variable at a time: size doubles each round
        for (size_t var_idx = 0; var_idx < d; ++var_idx) {
            const FF a_i = eq_linear_coeffs[var_idx];
            const FF b_i = eq_constant_coeffs.at(var_idx);
 
            const size_t prev_size = current.size();
            const size_t next_size = prev_size << 1;
 
            Polynomial<FF> next(/*size*/ next_size,
                                /*virtual_size*/ N,
                                /*start_index*/ 0,
                                Polynomial<FF>::DontZeroMemory::FLAG);
 
            // Write lower and upper halves
            const FF* src = current.data();
            FF* dst = next.data();
 
            for (size_t j = 0; j < prev_size; ++j) {
                const FF v = src[j];
                dst[j] = v * b_i;                     // bit_i = 0: multiply by b_i
                dst[j + prev_size] = v * (b_i + a_i); // bit_i = 1: multiply by (b_i + a_i)
            }
 
            current = std::move(next);
        }
 
        // current now holds all 2^d coefficients, index = mask over {X_i}
        return current;
    }
};
 
template <typename FF> struct VerifierEqPolynomial {
    // --- Instance data (fixed for a proof) ---
    std::vector<FF> r; // instance challenges r_i
    std::vector<FF> a; // a_i = 2 r_i - 1
    std::vector<FF> b; // b_i = 1 - r_i
 
    explicit VerifierEqPolynomial(const std::vector<FF>& r_in) { initialize(r_in); }
 
    void initialize(const std::vector<FF>& r_in)
    {
        r = r_in;
        a.resize(r.size());
        b.resize(r.size());
        for (size_t i = 0; i < r.size(); ++i) {
            a[i] = r[i] + r[i] - FF(1); // 2 r_i - 1
            b[i] = FF(1) - r[i];        // 1 - r_i
        }
    }
 
    // ---- Evaluate eq(X, r) at u ----
    FF evaluate(std::span<const FF> u) const
    {
        BB_ASSERT_EQ(u.size(), r.size(), "expect u.size() == r.size()");
        FF acc = FF(1);
        for (size_t i = 0; i < u.size(); ++i) {
            // term_i = b_i + u_i * a_i
            acc *= (b[i] + u[i] * a[i]);
        }
        return acc;
    }
 
    // ---- Compute eq(r, u) without constructing the object ----
    static FF eval(std::span<const FF> r_in, std::span<const FF> u)
    {
        BB_ASSERT_EQ(r_in.size(), u.size(), "expect r_in.size() == u.size()");
        FF acc = FF(1);
        for (size_t i = 0; i < r_in.size(); ++i) {
            const FF ai = r_in[i] + r_in[i] - FF(1);
            const FF bi = FF(1) - r_in[i];
            acc *= (bi + u[i] * ai);
        }
        return acc;
    }
};
 
} // namespace bb