Struct TwoAdicFriPcs

pub struct TwoAdicFriPcs<Val, Dft, InputMmcs, FriMmcs> { /* private fields */ }

A polynomial commitment scheme using FRI to generate opening proofs.

We commit to a polynomial f via its evaluation vectors over a coset gH where |H| >= 2 * deg(f). A value f(z) is opened by using a FRI proof to show that the evaluations of (f(x) - f(z))/(x - z) over gH are low degree.

Implementations

impl<Val, Dft, InputMmcs, FriMmcs> TwoAdicFriPcs<Val, Dft, InputMmcs, FriMmcs>

pub const fn new(dft: Dft, mmcs: InputMmcs, fri: FriParameters<FriMmcs>) -> Self

Trait Implementations

impl<Val: Clone, Dft: Clone, InputMmcs: Clone, FriMmcs: Clone> Clone for TwoAdicFriPcs<Val, Dft, InputMmcs, FriMmcs>

fn clone(&self) -> TwoAdicFriPcs<Val, Dft, InputMmcs, FriMmcs>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<Val: Debug, Dft: Debug, InputMmcs: Debug, FriMmcs: Debug> Debug for TwoAdicFriPcs<Val, Dft, InputMmcs, FriMmcs>

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

Formats the value using the given formatter.

impl<Val, Dft, InputMmcs, FriMmcs, Challenge, Challenger> Pcs<Challenge, Challenger> for TwoAdicFriPcs<Val, Dft, InputMmcs, FriMmcs>

where Val: TwoAdicField, Dft: TwoAdicSubgroupDft<Val>, InputMmcs: Mmcs<Val>, FriMmcs: Mmcs<Challenge>, Challenge: ExtensionField<Val>, Challenger: FieldChallenger<Val> + CanObserve<FriMmcs::Commitment> + GrindingChallenger<Witness = Val>,

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

Get the unique subgroup H of size |H| = degree.

Panics:

This function will panic if degree is not a power of 2 or degree > (1 << Val::TWO_ADICITY).

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

Commit to a collection of evaluation matrices.

Each element of evaluations contains a coset shift * H and a matrix mat with mat.height() = |H|. Interpreting each column of mat as the evaluations of a polynomial p_i(x) over shift * H, this computes the evaluations of p_i over gK where g is the chosen generator of the multiplicative group of Val and K is the unique subgroup of order |H| << self.fri.log_blowup.

This then outputs a Merkle commitment to these evaluations.

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

Given the evaluations on a domain gH, return the evaluations on a different domain g'K.

Arguments:

• prover_data: The prover data containing all committed evaluation matrices.
• idx: The index of the matrix containing the evaluations we want. These evaluations are assumed to be over the coset gH where g = Val::GENERATOR.
• domain: The domain g'K on which to get evaluations on. Currently, this assumes that g' = g and K is a subgroup of H and panics if this is not the case.

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

Open a batch of matrices at a collection of points.

Returns the opened values along with a proof.

This function assumes that all matrices correspond to evaluations over the coset gH where g = Val::GENERATOR and H is a subgroup of appropriate size depending on the matrix.

const ZK: bool = false

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

type Domain = TwoAdicMultiplicativeCoset<Val>

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

type Commitment = <InputMmcs as Mmcs<Val>>::Commitment

The commitment that’s sent to the verifier.

type ProverData = <InputMmcs as Mmcs<Val>>::ProverData<DenseMatrix<Val>>

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

type EvaluationsOnDomain<'a> = RowIndexMappedView<BitReversalPerm, DenseMatrix<Val, &'a [Val]>>

Type of the output of get_evaluations_on_domain.

type Proof = FriProof<Challenge, FriMmcs, Val, Vec<BatchOpening<Val, InputMmcs>>>

The opening argument.

type Error = FriError<<FriMmcs as Mmcs<Challenge>>::Error, <InputMmcs as Mmcs<Val>>::Error>

The type of a proof verification error.

fn get_quotient_ldes( &self, evaluations: impl IntoIterator<Item = (Self::Domain, RowMajorMatrix<Val>)>, _num_chunks: usize, ) -> Vec<RowMajorMatrix<Val>>

When committing to quotient polynomials in batch-STARK, it is simpler to first compute the LDE evaluations before batch-committing to them.

fn commit_ldes( &self, ldes: Vec<RowMajorMatrix<Val>>, ) -> (Self::Commitment, Self::ProverData)

Commits to a collection of LDE evaluation matrices.

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

Verify that a collection of opened values is correct.

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.

const PREPROCESSED_TRACE_IDX: usize = _

Index of the preprocessed trace commitment in the computed opened values.

fn commit_preprocessing( &self, evaluations: impl IntoIterator<Item = (Self::Domain, DenseMatrix<<Self::Domain as PolynomialSpace>::Val>)>, ) -> (Self::Commitment, Self::ProverData)

Same as commit but without randomization. This is used for preprocessed columns which do not have to be randomized even when ZK is enabled. Note that the preprocessed columns still need to be padded to the extended domain height.

fn commit_quotient( &self, quotient_domain: Self::Domain, quotient_evaluations: DenseMatrix<<Self::Domain as PolynomialSpace>::Val>, 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.

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

This is the same as get_evaluations_on_domain but without randomization. This is used for preprocessed columns which do not have to be randomized even when ZK is enabled.

fn open_with_preprocessing( &self, commitment_data_with_opening_points: Vec<(&Self::ProverData, Vec<Vec<Challenge>>)>, fiat_shamir_challenger: &mut Challenger, _is_preprocessing: bool, ) -> (Vec<Vec<Vec<Vec<Challenge>>>>, Self::Proof)

Open a collection of polynomial commitments at a set of points, when there is preprocessing data. It is the same as open when ZK is disabled. Produce the values at those points along with a proof of correctness.

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