Function univariate_round_message_extension_domain 

pub fn univariate_round_message_extension_domain<F>(
    log_words: usize,
    a_words: &[Word],
    b_words: &[Word],
    big_field_challenges: &[F],
    prover_message_domain: &BinarySubspace<Rijndael8b>,
) -> [F; 64]
where
    F: BinaryField + From<Rijndael8b>,

Generates a univariate polynomial for the sumcheck protocol in AND constraint reduction.

Let our oblong polynomials be A(Z, X₀, …), B(Z, X₀, …), and C(Z, X₀, …)

Let our zerocheck challenges be (r₀, …)

It turns out that the first k zerocheck challenges can actually be deterministic, since our polynomials have 1-bit coefficients as long as their tensor product expansion is an F2-linearly-independent set.

Note: Deterministic here means that the first k zerocheck challenges are a compile-time agreed-upon parameter to the proof, and not sampled randomly by the verifier

We choose k=3 because we want them to be in a field isomorphic to the 8-bit NTT domain field

Computes a univariate polynomial: R₀(Z) = ∑_{X₀,…,Xₙ₋₁ ∈ {0,1}} (A·B - C)·eq(X₀,…,Xₙ₋₁; r₀,…,rₙ₋₁)

This is zero at every point on the hypercube IFF A*B-C evaluates to zero at (r₀,…,rₙ₋₁) for every Z on the univariate domain. Since R₀(Z) is 0 on the univariate domain, the prover sends only enough values such that the verifier learns a domain of evaluations of size > deg(R₀(Z))

The product constraint column C is not an input. Each C word is derived in registers as the AND of the matching A and B words. A satisfying witness makes that derivation exact on every row. So no third column is ever built or streamed.

Arguments

• log_words - Base-2 logarithm of the constraint axis’s length
• a_words - First multiplicand (a) as a one-bit oblong multilinear polynomial
• b_words - Second multiplicand (b) as a one-bit oblong multilinear polynomial
• eq_ind_big_field_challenges - Partial equality indicator evaluations for big field variables
• prover_message_domain - The NTT domain subspace (dimension SKIPPED_VARS + 1) from which the low-degree-extension lookup table is built internally

Preconditions

• The two columns have equal length, at most 1 << log_words. They need not fill the constraint axis: a shorter column has its remaining rows read as zero. Such a row forces the derived C = A & B to zero as well, so A * B - C vanishes on it at every point of the univariate domain and it adds nothing to the message.

Returns

The evaluations of R₀(Z), a univariate polynomial of degree at most 2*(|D| - 1) where |D| is the domain size, on another, disjoint |D|-sized domain. This allows the verifier to construct R₀(Z), since it must equal zero on D.

Type Parameters

• F - The challenge field type (must be a binary field)

Panics

Panics if any of the following don’t hold:

• big_field_challenges.len() == log_words.saturating_sub(N_FIXED_SMALL_CHALLENGES)
• a_words.len() == b_words.len()
• a_words.len() <= 1 << log_words