Skip to main content

binius_verifier/protocols/
bitand.rs

1// Copyright 2025 Irreducible Inc.
2// Copyright 2026 The Binius Developers
3
4use std::iter::{self};
5
6use binius_field::{BinaryField, field::FieldOps};
7use binius_ip::channel::IPVerifierChannel;
8use binius_math::{BinarySubspace, univariate::EvaluationDomain};
9
10use super::rerand::RerandOutput;
11use crate::Error;
12
13/// log2 size of the univariate domain
14pub const SKIPPED_VARS: usize = binius_core::Word::LOG_BITS;
15
16/// Size of the univariate domain
17pub const ROWS_PER_HYPERCUBE_VERTEX: usize = 1 << SKIPPED_VARS;
18
19/// Output of the univariate skip.
20#[derive(Debug, Clone, PartialEq, Eq)]
21pub struct UnivariateSkipOutput<F> {
22	/// The univariate challenge `z` sampled for the bit-index variable.
23	pub z_challenge: F,
24	/// The univariate polynomial at `z`, `g(z)`: the claim the multilinear rounds prove.
25	pub claim: F,
26}
27
28/// Output of the whole BitAnd reduction: the univariate skip, then the batched sumcheck.
29#[derive(Debug, Clone, PartialEq, Eq)]
30pub struct AndCheckOutput<F> {
31	/// The univariate challenge `z` sampled for the bit-index variable.
32	pub z_challenge: F,
33	/// The batched sumcheck's evaluation claims. See [`super::rerand`].
34	pub rerand: RerandOutput<F>,
35}
36
37/// Verifies the univariate skip of the AND constraint reduction.
38///
39/// Note: Following section 4.4 of the Binius64 writeup, Z is the bit index within a word, and X is
40/// the word index
41///
42/// Let our oblong polynomials be A(Z, X₀, ...), B(Z, X₀, ...), and C(Z, X₀, ...)
43///
44/// Let our zerocheck challenges be (r₀, ...)
45///
46/// The reduction checks A·B-C = 0 on every row. That holds if and only if, for all Z, the
47/// multilinear extension of A·B-C evaluates to zero at a random point (Z,r₀,...,rₙ₋₁), up to some
48/// negligible error probability.
49///
50/// The prover sends a univariate polynomial R₀(Z) that encodes the sum:
51///
52/// R₀(Z) = ∑_{X₀,...,Xₙ₋₁ ∈ {0,1}} (A(Z,X₀,...,Xₙ₋₁)·B(Z,X₀,...,Xₙ₋₁) -
53/// C(Z,X₀,...,Xₙ₋₁))·eq(X₀,...,Xₙ₋₁; r₀,...,rₙ₋₁)
54///
55/// Z ranges over a univariate domain of size 2^(SKIPPED_VARS + 1). The polynomial R₀(Z) has degree
56/// at most 2*(|D| - 1). The prover only sends evaluations on the upper half of the domain, since
57/// R₀(Z) = 0 on the base domain when all AND constraints are satisfied.
58///
59/// The verifier samples a challenge z for Z. The claim R₀(z) is then proven by the batched
60/// sumcheck in [`super::rerand`], over the remaining variables X₀,...,Xₙ₋₁.
61pub fn verify_univariate_skip<F, C>(
62	channel: &mut C,
63	domain: &BinarySubspace<F>,
64) -> Result<UnivariateSkipOutput<C::Elem>, Error>
65where
66	F: BinaryField,
67	C: IPVerifierChannel<F>,
68	// This bound is necessary to make Barycentric evaluation constants symbolic
69	C::Elem: From<F>,
70{
71	let univariate_message_coeffs_ext_domain = channel.recv_many(ROWS_PER_HYPERCUBE_VERTEX)?;
72
73	let univariate_message_coeffs = iter::chain(
74		iter::repeat_n(C::Elem::zero(), ROWS_PER_HYPERCUBE_VERTEX),
75		univariate_message_coeffs_ext_domain,
76	)
77	.collect::<Vec<_>>();
78
79	let z_challenge = channel.sample();
80	let claim = domain.extrapolate(&univariate_message_coeffs, &z_challenge);
81
82	Ok(UnivariateSkipOutput { z_challenge, claim })
83}