binius_core::protocols::msetcheck

Function prove

source
pub fn prove<'a, U, F, FW>(
    oracles: &mut MultilinearOracleSet<F>,
    witness_index: MultilinearExtensionIndex<'a, U, FW>,
    msetcheck_claim: &MsetcheckClaim<F>,
    msetcheck_witness: MsetcheckWitness<'a, PackedType<U, FW>>,
    gamma: F,
    alpha: Option<F>,
) -> Result<MsetcheckProveOutput<'a, U, F, FW>, Error>
Expand description

Prove a multiset check instance reduction.

Given two $n$-arity tuples $(T_1, \ldots, T_n)$ and $(U_1, \ldots, U_n)$ of $\nu$-variate multilins, each representing an $n$-dimensional relation of cardinality $2^{\nu}$ (when treated as a multiset), this protocol reduces multiset equality predicate to a grand product check of the two polynomials of the form:

  1. $T’(x) = \gamma + T_1(x) + \alpha * T_2(x) + \ldots + \alpha^{n-1} * T_n(x)$
  2. $U’(x) = \gamma + U_1(x) + \alpha * U_2(x) + \ldots + \alpha^{n-1} * U_n(x)$

where $\gamma$ and $\alpha$ are some large field challenges sampled via Fiat-Shamir (alpha is non-None if $n \ge 2$).