Struct MultilinearKzgPCS

pub struct MultilinearKzgPCS<E: Pairing> { /* private fields */ }

KZG Polynomial Commitment Scheme on multilinear polynomials.

Trait Implementations

impl<E: Pairing> PolynomialCommitmentScheme for MultilinearKzgPCS<E>

fn trim( srs: impl Borrow<Self::SRS>, supported_log_degree: usize, supported_num_vars: Option<usize>, ) -> Result<(<(MultilinearUniversalParams<E>, UnivariateUniversalParams<E>) as StructuredReferenceString>::ProverParam, <(MultilinearUniversalParams<E>, UnivariateUniversalParams<E>) as StructuredReferenceString>::VerifierParam), PCSError>

Trim the universal parameters to specialize the public parameters. Input both supported_log_degree for univariate and supported_num_vars for multilinear.

fn commit( prover_param: impl Borrow<<(MultilinearUniversalParams<E>, UnivariateUniversalParams<E>) as StructuredReferenceString>::ProverParam>, poly: &Self::Polynomial, ) -> Result<Self::Commitment, PCSError>

Generate a commitment for a polynomial.

This function takes 2^num_vars number of scalar multiplications over G1.

fn batch_commit( prover_param: impl Borrow<<(MultilinearUniversalParams<E>, UnivariateUniversalParams<E>) as StructuredReferenceString>::ProverParam>, polys: &[Self::Polynomial], ) -> Result<Self::Commitment, PCSError>

Batch commit a list of polynomials.

This function takes 2^(num_vars + log(polys.len()) number of scalar multiplications over G1.

fn open( prover_param: impl Borrow<<(MultilinearUniversalParams<E>, UnivariateUniversalParams<E>) as StructuredReferenceString>::ProverParam>, polynomial: &Self::Polynomial, point: &Self::Point, ) -> Result<(Self::Proof, Self::Evaluation), PCSError>

On input a polynomial p and a point point, outputs a proof for the same. This function does not need to take the evaluation value as an input.

This function takes 2^{num_var +1} number of scalar multiplications over G1:

• it proceeds with num_var number of rounds,
• at round i, we compute an MSM for 2^{num_var - i + 1} number of G2 elements.

fn batch_open( prover_param: impl Borrow<<(MultilinearUniversalParams<E>, UnivariateUniversalParams<E>) as StructuredReferenceString>::ProverParam>, batch_commitment: &Self::BatchCommitment, polynomials: &[Self::Polynomial], points: &[Self::Point], ) -> Result<(Self::BatchProof, Vec<Self::Evaluation>), PCSError>

Input

• the prover parameters for univariate KZG,
• the prover parameters for multilinear KZG,
• a list of polynomials,
• a (batch) commitment to all polynomials,
• and the same number of points, compute a batch opening for all the polynomials.

For simplicity, this API requires each MLE to have only one point. If the caller wish to use more than one point per MLE, it should be handled at the caller layer.

Returns an error if the lengths do not match.

Returns the proof, consists of

• the multilinear KZG opening
• the univariate KZG commitment to q(x)
• the openings and evaluations of q(x) at omega^i and r

Steps:

1. build l(points) which is a list of univariate polynomials that goes through the points
2. build MLE w which is the merge of all MLEs.
3. build q(x) which is a univariate polynomial W circ l
4. commit to q(x) and sample r from transcript transcript contains: w commitment, points, q(x)’s commitment
5. build q(omega^i) and their openings
6. build q(r) and its opening
7. get a point p := l(r)
8. output an opening of w over point p
9. output w(p)

fn verify( verifier_param: &<(MultilinearUniversalParams<E>, UnivariateUniversalParams<E>) as StructuredReferenceString>::VerifierParam, commitment: &Self::Commitment, point: &Self::Point, value: &E::ScalarField, proof: &Self::Proof, ) -> Result<bool, PCSError>

Verifies that value is the evaluation at x of the polynomial committed inside comm.

This function takes

• num_var number of pairing product.
• num_var number of MSM

fn batch_verify<R: RngCore + CryptoRng>( verifier_param: &<(MultilinearUniversalParams<E>, UnivariateUniversalParams<E>) as StructuredReferenceString>::VerifierParam, batch_commitment: &Self::BatchCommitment, points: &[Self::Point], values: &[E::ScalarField], batch_proof: &Self::BatchProof, _rng: &mut R, ) -> Result<bool, PCSError>

Verifies that value is the evaluation at x_i of the polynomial poly_i committed inside commitment. steps:

1. put q(x)’s evaluations over (1, omega,...) into transcript
2. sample r from transcript
3. check q(r) == value
4. build l(points) which is a list of univariate polynomials that goes through the points
5. get a point p := l(r)
6. verifies p is verifies against proof

type SRS = (MultilinearUniversalParams<E>, UnivariateUniversalParams<E>)

Structured reference string

type Polynomial = Arc<DenseMultilinearExtension<<E as Pairing>::ScalarField>>

Polynomial and its associated types

type Point = Vec<<E as Pairing>::ScalarField>

Polynomial input domain

type Evaluation = <E as Pairing>::ScalarField

Polynomial Evaluation

type Commitment = Commitment<E>

Commitments

type BatchCommitment = Commitment<E>

Batch commitments

type Proof = MultilinearKzgProof<E>

Proofs

type BatchProof = MultilinearKzgBatchProof<E>

Batch proofs

fn load_srs_from_file( supported_degree: usize, file: Option<&str>, ) -> Result<Self::SRS, PCSError>

Load public parameter in production environment. These parameters are loaded from files with serialized pp bytes, and the actual setup is usually carried out via MPC and should be implemented else where. We only load them into memory here.

fn multi_open( prover_param: impl Borrow<<Self::SRS as StructuredReferenceString>::ProverParam>, polynomial: &Self::Polynomial, points: &[Self::Point], ) -> Result<(Vec<Self::Proof>, Vec<Self::Evaluation>), PCSError>

Open a single polynomial at multiple points. The naive default implementation just open them individually.