pub fn verify_univariate_skip<F, C>(
channel: &mut C,
domain: &BinarySubspace<F>,
) -> Result<UnivariateSkipOutput<C::Elem>, Error>Expand description
Verifies the univariate skip of the AND constraint reduction.
Note: Following section 4.4 of the Binius64 writeup, Z is the bit index within a word, and X is the word index
Let our oblong polynomials be A(Z, X₀, …), B(Z, X₀, …), and C(Z, X₀, …)
Let our zerocheck challenges be (r₀, …)
The reduction checks A·B-C = 0 on every row. That holds if and only if, for all Z, the multilinear extension of A·B-C evaluates to zero at a random point (Z,r₀,…,rₙ₋₁), up to some negligible error probability.
The prover sends a univariate polynomial R₀(Z) that encodes the sum:
R₀(Z) = ∑_{X₀,…,Xₙ₋₁ ∈ {0,1}} (A(Z,X₀,…,Xₙ₋₁)·B(Z,X₀,…,Xₙ₋₁) - C(Z,X₀,…,Xₙ₋₁))·eq(X₀,…,Xₙ₋₁; r₀,…,rₙ₋₁)
Z ranges over a univariate domain of size 2^(SKIPPED_VARS + 1). The polynomial R₀(Z) has degree at most 2*(|D| - 1). The prover only sends evaluations on the upper half of the domain, since R₀(Z) = 0 on the base domain when all AND constraints are satisfied.
The verifier samples a challenge z for Z. The claim R₀(z) is then proven by the batched
sumcheck in super::rerand, over the remaining variables X₀,…,Xₙ₋₁.