Struct BatchPCS

pub struct BatchPCS<P, FE, InnerPCS>
where
    P: PackedField,
    FE: ExtensionField<P::Scalar>,
    InnerPCS: PolyCommitScheme<P, FE>,
{ /* private fields */ }

A block-box batching scheme for multilinear commitments, as explained in [Section 5.3, DP24].

In particular, the scheme allows us to open the evaluations of a collection of multilinear polynomials at a point $\vec{r}$.

Given a collection of $2^m$ multilinear $n$-variate polynomials $t_u$, jointly commit to them with the following functionality: jointly open the evaluations of the polynomials at a point $\vec{r}=(r_0,\ldots,r_{n-1})$.

Suppose we have a collection of $2^m$ multilinear polynomials $t_u$, each of which is $n$-variate, and we want to prove the evaluations at a point $\vec{r}=(r_0,\ldots ,r_{n-1})$ are $(s_u)$. Build the multilinear, $n+m$-variate polynomial T, whose values on $B_{m+n}$ are given as: $T(v||u) = t_u(v)$, for all u in ${0,1}^m$ and v in ${0,1}^n$. Sample random challenges $\vec{r’}:=(r’0,\ldots,r’{m-1})$. Finally, pass off the evaluation of $T$ at $(r_0,\ldots,r_{n-1}, r’0,\ldots,r’{m-1})$ to the inner polynomial commitment scheme.

If the prover is honest, $T(\vec{r}||\vec{r’})$ is the dot product of the tensor expansion of $\vec{r’}$ with $(s_u)$. Equivalently, it is the evaluation of the multilinear polynomial defined via MLE on the hypercube: $B_m\rightarrow \mathbb F$ by $u\mapsto s_u$ at the point $(r’0,\ldots, r’{m-1})$. Therefore, given the claimed evaluations $(s_u)$, the verifier can compute the desired mixing herself.

Type parameters

• P - the packed coefficient subfield
• FE - an extension field of P::Scalar (used for the inner PCS)
• Inner - the inner polynomial commitment scheme over the extension field

Implementations

impl<F, FE, P, Inner> BatchPCS<P, FE, Inner>

where F: Field, P: PackedField<Scalar = F>, FE: ExtensionField<F>, Inner: PolyCommitScheme<P, FE>,

pub fn new( inner: Inner, n_vars: usize, log_num_polys: usize, ) -> Result<Self, Error>

Trait Implementations

impl<P, FE, InnerPCS> Debug for BatchPCS<P, FE, InnerPCS>

where P: PackedField + Debug, FE: ExtensionField<P::Scalar> + Debug, InnerPCS: PolyCommitScheme<P, FE> + Debug,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<F, FE, P, Inner> PolyCommitScheme<P, FE> for BatchPCS<P, FE, Inner>

where F: Field, P: PackedField<Scalar = F>, FE: ExtensionField<F>, Inner: PolyCommitScheme<P, FE>,

type Commitment = <Inner as PolyCommitScheme<P, FE>>::Commitment

type Committed = <Inner as PolyCommitScheme<P, FE>>::Committed

type Proof = Proof<<Inner as PolyCommitScheme<P, FE>>::Proof>

type Error = Error

fn n_vars(&self) -> usize

fn commit<Data>( &self, polys: &[MultilinearExtension<P, Data>], ) -> Result<(Self::Commitment, Self::Committed), Self::Error>

where Data: Deref<Target = [P]> + Send + Sync,

Commit to a batch of polynomials

fn prove_evaluation<Data, CH, Backend>( &self, challenger: &mut CH, committed: &Self::Committed, polys: &[MultilinearExtension<P, Data>], query: &[FE], backend: Backend, ) -> Result<Self::Proof, Self::Error>

where Data: Deref<Target = [P]> + Send + Sync, CH: CanObserve<FE> + CanObserve<Self::Commitment> + CanSample<FE> + CanSampleBits<usize>, Backend: ComputationBackend,

Generate an evaluation proof at a random challenge point.

fn verify_evaluation<CH, Backend>( &self, challenger: &mut CH, commitment: &Self::Commitment, query: &[FE], proof: Self::Proof, values: &[FE], backend: Backend, ) -> Result<(), Self::Error>

where CH: CanObserve<FE> + CanObserve<Self::Commitment> + CanSample<FE> + CanSampleBits<usize>, Backend: ComputationBackend,

Verify an evaluation proof at a random challenge point.

fn proof_size(&self, _n_polys: usize) -> usize

Return the byte-size of a proof.