bb::ProverEqPolynomial< FF > Class Template Reference

Prover-side eq(X, r) polynomial over Boolean hypercube. More...

#include <eq_polynomial.hpp>

Static Public Member Functions
static Polynomial< FF >	construct (std::span< const FF > challenges, size_t log_num_monomials)
	Construct eq(X, r) coefficient table over Boolean hypercube {0,1}^d.
static FF	compute_scaling_factor (std::span< const FF > challenge)
	Compute the scaling factor C = ∏_i (1 - r_i) for coordinate transformation.
static std::vector< FF >	transform_challenge (std::span< const FF > challenges)
	Transform challenges r_i to γ_i = r_i / (1 - r_i) for optimal method.
static Polynomial< FF >	construct_eq_with_edge_cases (std::span< const FF > r, size_t log_num_monomials)
	Fallback method: direct construction of eq(X, r) coefficient table for edge cases.

Detailed Description

template<typename FF>
class bb::ProverEqPolynomial< FF >

Prover-side eq(X, r) polynomial over Boolean hypercube.

eq(X, r) = ∏_{i=0}^{d-1} ((1 - r_i)(1 - X_i) + r_i X_i) = ∏_{i=0}^{d-1} (b_i + a_i X_i), where a_i = 2r_i - 1, b_i = 1 - r_i

This class provides two construction strategies:

1. Optimal method (default): Uses coordinate transformation + GateSeparatorPolynomial
   • Transforms eq(X, r) = C · ∏_i (1 + (γ_i - 1) X_i), where γ_i = r_i / (1 - r_i), C = ∏_i (1 - r_i)
   • Delegation to GateSeparatorPolynomial::compute_beta_products uses the optimal pow_β algorithm
   • Cost: ~2^d multiplications (ignoring lower-order terms from transformation)
   • Requirement: All challenges r_i ≠ 1 (to avoid division by zero in γ_i = r_i / (1 - r_i))
2. Fallback method: Direct incremental table construction for edge cases
   • Builds the 2^d coefficient table by expanding one variable at a time
   • Cost: 2^(d+1) - 2 multiplications (sum over rounds: ∑_{i=0}^{d-1} 2^(i+1) = 2^(d+1) - 2)
   • Usage: Automatically invoked when any r_i = 1 (detected by checking if ∏_i (1 - r_i) = 0)
   • Performance: ~2× slower than optimal method, but handles all edge cases correctly

In production, challenges are typically generated by hashing the transcript, so with high probability no r_i = 1, and the optimal method is used.

Definition at line 42 of file eq_polynomial.hpp.

Member Function Documentation

compute_scaling_factor()

template<typename FF >

static FF bb::ProverEqPolynomial< FF >::compute_scaling_factor ( std::span< const FF >  challenge )

inlinestatic

Compute the scaling factor C = ∏_i (1 - r_i) for coordinate transformation.

Used to detect edge cases: if C = 0, then at least one r_i = 1, and we must use the fallback method.

Parameters

challenge

The evaluation point r = (r_0, ..., r_{d-1})

Returns

FF The product C = (1 - r_0) · (1 - r_1) · ... · (1 - r_{d-1})

Definition at line 80 of file eq_polynomial.hpp.

construct()

template<typename FF >

static Polynomial< FF > bb::ProverEqPolynomial< FF >::construct ( std::span< const FF >  challenges, size_t  log_num_monomials  )

inlinestatic

Construct eq(X, r) coefficient table over Boolean hypercube {0,1}^d.

Automatically selects between optimal and fallback methods based on challenge values:

• If all r_i ≠ 1: uses optimal method (~2^d muls) via GateSeparatorPolynomial
• If any r_i = 1: uses fallback method (~2^(d+1) muls) via direct construction

Parameters

challenges	The evaluation point r = (r_0, ..., r_{d-1})
log_num_monomials	The dimension d (must equal challenges.size())

Returns

Polynomial<FF> Coefficient table of size 2^d indexed by Boolean masks

Definition at line 56 of file eq_polynomial.hpp.

construct_eq_with_edge_cases()

template<typename FF >

static Polynomial< FF > bb::ProverEqPolynomial< FF >::construct_eq_with_edge_cases ( std::span< const FF >  r, size_t  log_num_monomials  )

inlinestatic

Fallback method: direct construction of eq(X, r) coefficient table for edge cases.

Builds the 2^d coefficient table incrementally by processing one Boolean variable at a time. Each iteration doubles the table size by appending coefficients for X_i = 1 to those for X_i = 0.

Algorithm: For each variable i ∈ {0, ..., d-1}:

• Given table T of size 2^i representing eq restricted to first i variables
• Expand to size 2^(i+1) by computing:
  • T[mask] = T[mask >> 1] · b_i if bit i of mask is 0
  • T[mask] = T[mask >> 1] · (b_i + a_i) if bit i of mask is 1 where a_i = 2r_i - 1, b_i = 1 - r_i

Cost analysis:

• Round i processes 2^i coefficients, producing 2^(i+1) outputs
• Each output requires: 1 addition + 1 multiplication (for upper half) or 1 multiplication (for lower half)
• Total multiplications: ∑_{i=0}^{d-1} 2^(i+1) = 2^(d+1) - 2 ≈ 2 · 2^d
• Performance: ~2× slower than optimal method, but works for all challenge values

Parameters

r	The evaluation point r = (r_0, ..., r_{d-1})
log_num_monomials	The dimension d (must equal r.size())

Returns

Polynomial<FF> Coefficient table of size 2^d indexed by Boolean masks

Definition at line 141 of file eq_polynomial.hpp.

transform_challenge()

template<typename FF >

static std::vector< FF > bb::ProverEqPolynomial< FF >::transform_challenge ( std::span< const FF >  challenges )

inlinestatic

Transform challenges r_i to γ_i = r_i / (1 - r_i) for optimal method.

The coordinate transformation eq(X, r) = C · ∏_i (1 + γ_i X_i) enables use of the optimal pow_β algorithm. Uses batch inversion for efficiency.

Parameters

challenges

The evaluation point r = (r_0, ..., r_{d-1})

Returns

std::vector<FF> The transformed challenges γ = (γ_0, ..., γ_{d-1})

Note

Requires all r_i ≠ 1 to avoid division by zero. Caller must check via compute_scaling_factor.

Definition at line 101 of file eq_polynomial.hpp.

---

The documentation for this class was generated from the following file:

• src/barretenberg/polynomials/eq_polynomial.hpp