Trait Pcs

pub trait Pcs<Challenge, Challenger>
where
    Challenge: ExtensionField<Val<Self::Domain>>,
{
    type Domain: PolynomialSpace;
    type Commitment: Clone + Serialize + DeserializeOwned;
    type ProverData;
    type EvaluationsOnDomain<'a>: Matrix<Val<Self::Domain>> + 'a;
    type Proof: Clone + Serialize + DeserializeOwned;
    type Error: Debug;

    const ZK: bool;
    const TRACE_IDX: usize = _;
    const QUOTIENT_IDX: usize = _;

    // Required methods
    fn natural_domain_for_degree(&self, degree: usize) -> Self::Domain;
    fn commit(
        &self,
        evaluations: impl IntoIterator<Item = (Self::Domain, RowMajorMatrix<Val<Self::Domain>>)>,
    ) -> (Self::Commitment, Self::ProverData);
    fn get_evaluations_on_domain<'a>(
        &self,
        prover_data: &'a Self::ProverData,
        idx: usize,
        domain: Self::Domain,
    ) -> Self::EvaluationsOnDomain<'a>;
    fn open(
        &self,
        commitment_data_with_opening_points: Vec<(&Self::ProverData, Vec<Vec<Challenge>>)>,
        fiat_shamir_challenger: &mut Challenger,
    ) -> (OpenedValues<Challenge>, Self::Proof);
    fn verify(
        &self,
        commitments_with_opening_points: Vec<(Self::Commitment, Vec<(Self::Domain, Vec<(Challenge, Vec<Challenge>)>)>)>,
        proof: &Self::Proof,
        fiat_shamir_challenger: &mut Challenger,
    ) -> Result<(), Self::Error>;

    // Provided methods
    fn commit_quotient(
        &self,
        quotient_domain: Self::Domain,
        quotient_evaluations: RowMajorMatrix<Val<Self::Domain>>,
        num_chunks: usize,
    ) -> (Self::Commitment, Self::ProverData) { ... }
    fn get_opt_randomization_poly_commitment(
        &self,
        _domain: Self::Domain,
    ) -> Option<(Self::Commitment, Self::ProverData)> { ... }
}

A polynomial commitment scheme, for committing to batches of polynomials defined by their evaluations over some domain.

In general this does not have to be a hiding commitment scheme but it might be for some implementations.

Required Associated Constants

const ZK: bool

Set to true to activate randomization and achieve zero-knowledge.

Provided Associated Constants

const TRACE_IDX: usize = _

Index of the trace commitment in the computed opened values.

const QUOTIENT_IDX: usize = _

Index of the quotient commitments in the computed opened values.

Required Associated Types

type Domain: PolynomialSpace

The class of evaluation domains that this commitment scheme works over.

type Commitment: Clone + Serialize + DeserializeOwned

The commitment that’s sent to the verifier.

type ProverData

Data that the prover stores for committed polynomials, to help the prover with opening.

type EvaluationsOnDomain<'a>: Matrix<Val<Self::Domain>> + 'a

Type of the output of get_evaluations_on_domain.

type Proof: Clone + Serialize + DeserializeOwned

The opening argument.

type Error: Debug

The type of a proof verification error.

Required Methods

fn natural_domain_for_degree(&self, degree: usize) -> Self::Domain

This should return a domain such that Domain::next_point returns Some.

fn commit( &self, evaluations: impl IntoIterator<Item = (Self::Domain, RowMajorMatrix<Val<Self::Domain>>)>, ) -> (Self::Commitment, Self::ProverData)

Given a collection of evaluation matrices, produce a binding commitment to the polynomials defined by those evaluations. If zk is enabled, the evaluations are first randomized as explained in Section 3 of https://eprint.iacr.org/2024/1037.pdf .

Returns both the commitment which should be sent to the verifier and the prover data which can be used to produce opening proofs.

fn get_evaluations_on_domain<'a>( &self, prover_data: &'a Self::ProverData, idx: usize, domain: Self::Domain, ) -> Self::EvaluationsOnDomain<'a>

Given prover data corresponding to a commitment to a collection of evaluation matrices, return the evaluations of those matrices on the given domain.

This is essentially a no-op when called with a domain which is a subset of the evaluation domain on which the evaluation matrices are defined.

fn open( &self, commitment_data_with_opening_points: Vec<(&Self::ProverData, Vec<Vec<Challenge>>)>, fiat_shamir_challenger: &mut Challenger, ) -> (OpenedValues<Challenge>, Self::Proof)

Open a collection of polynomial commitments at a set of points. Produce the values at those points along with a proof of correctness.

Arguments:

• commitment_data_with_opening_points: A vector whose elements are a pair:
  • data: The prover data corresponding to a multi-matrix commitment.
  • opening_points: A vector containing, for each matrix committed to, a vector of opening points.
• fiat_shamir_challenger: The challenger that will be used to generate the proof.

Unwrapping the arguments further, each data contains a vector of the committed matrices (matrices = Vec<M>). If the length of matrices is not equal to the length of opening_points the function will error. Otherwise, for each index i, the matrix M = matrices[i] will be opened at the points opening_points[i].

This means that each column of M will be interpreted as the evaluation vector of some polynomial and we will compute the value of all of those polynomials at opening_points[i].

The domains on which the evaluation vectors are defined is not part of the arguments here but should be public information known to both the prover and verifier.

fn verify( &self, commitments_with_opening_points: Vec<(Self::Commitment, Vec<(Self::Domain, Vec<(Challenge, Vec<Challenge>)>)>)>, proof: &Self::Proof, fiat_shamir_challenger: &mut Challenger, ) -> Result<(), Self::Error>

Verify that a collection of opened values is correct.

Arguments:

• commitments_with_opening_points: A vector whose elements are a pair:
  • commitment: A multi matrix commitment.
  • opening_points: A vector containing, for each matrix committed to, a vector of opening points and claimed evaluations.
• proof: A claimed proof of correctness for the opened values.
• fiat_shamir_challenger: The challenger that will be used to generate the proof.

Provided Methods

fn commit_quotient( &self, quotient_domain: Self::Domain, quotient_evaluations: RowMajorMatrix<Val<Self::Domain>>, num_chunks: usize, ) -> (Self::Commitment, Self::ProverData)

Commit to the quotient polynomial. We first decompose the quotient polynomial into num_chunks many smaller polynomials each of degree degree / num_chunks. This can have minor performance benefits, but is not strictly necessary in the non zk case. When zk is enabled, this commitment will additionally include some randomization process to hide the inputs.

Arguments

• quotient_domain the domain of the quotient polynomial.
• quotient_evaluations the evaluations of the quotient polynomial over the domain. This should be in standard (not bit-reversed) order.
• num_chunks the number of smaller polynomials to decompose the quotient polynomial into.

fn get_opt_randomization_poly_commitment( &self, _domain: Self::Domain, ) -> Option<(Self::Commitment, Self::ProverData)>

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors

impl<Val, Dft, Challenge, Challenger> Pcs<Challenge, Challenger> for TrivialPcs<Val, Dft>

where Val: TwoAdicField, Challenge: ExtensionField<Val>, Challenger: CanSample<Challenge>, Dft: TwoAdicSubgroupDft<Val>, Vec<Vec<Val>>: Serialize + for<'de> Deserialize<'de>,

const ZK: bool = false

type Domain = TwoAdicMultiplicativeCoset<Val>

type Commitment = Vec<Vec<Val>>

type ProverData = Vec<DenseMatrix<Val>>

type EvaluationsOnDomain<'a> = <Dft as TwoAdicSubgroupDft<Val>>::Evaluations

type Proof = ()

type Error = ()