Struct HyraxPC

pub struct HyraxPC<G: AffineRepr, P: MultilinearExtension<G::ScalarField>> { /* private fields */ }

Hyrax polynomial committment scheme: A polynomial commitment scheme based on the hardness of the discrete logarithm problem in prime-order groups. This is a Fiat-Shamired version of the PCS described in the Hyrax paper [WTsTW17].

Future optimisations

• Add parallelisation. There is at least one natural place where parallelisation could bring performance gains: in essence, the prover commits to the polynomial by expressing it as an evaluation matrix and Pederson-multi-committing to each row. Each of this commitments can be computed independently from the rest, and therefore, in parallel. It is still to be seen how much of an improvement this would entail, since each Pederson multi-commitment boils down to a multi-exponentiation and this operation is itself parallelised.
• Due to the homomorphic nature of Pedersen commitments, it is likely some of the following methods can be designed more efficiently than their default implementations: batch_open, batch_check, open_combinations, check_combinations. This is not discussed in the reference article, but the IPA and KZG modules might be a good starting point.
• On a related note to the previous point, there might be a more efficient way to open several polynomials at a single point (this is the functionality of the open method) than the currently implemented technique, where only the computation of the vectors L and R is shared across polynomials.
• The cited article proposes an optimisation in the section Reducing the cost of proof-of-dot-prod. It allows for non-square matrices (and hence removes the requirement for the number of variables to be even) and introduces a tradeoff between proof size and verifier time. It is probably worth pursuing.

Trait Implementations

impl<G, P> PolynomialCommitment<<G as AffineRepr>::ScalarField, P> for HyraxPC<G, P>

where G: AffineRepr, G::ScalarField: Absorb, P: MultilinearExtension<G::ScalarField>,

fn setup<R: RngCore>( _max_degree: usize, num_vars: Option<usize>, _rng: &mut R, ) -> Result<Self::UniversalParams, Self::Error>

Outputs mock universal parameters for the Hyrax polynomial commitment scheme. It does not return random keys across calls and should never be used in settings where security is required - it is only useful for testing.

Panics

Panics if num_vars is None or contains an odd value.

fn trim( pp: &Self::UniversalParams, _supported_degree: usize, _supported_hiding_bound: usize, _enforced_degree_bounds: Option<&[usize]>, ) -> Result<(Self::CommitterKey, Self::VerifierKey), Self::Error>

Trims a key into a prover key and a verifier key. This should only amount to discarding some of the points in said key if the prover and verifier only wish to commit to polynomials with fewer variables than the key can support. Since the number of variables is not considered in the prototype, this function currently simply clones the key.

fn commit<'a>( ck: &Self::CommitterKey, polynomials: impl IntoIterator<Item = &'a LabeledPolynomial<G::ScalarField, P>>, rng: Option<&mut dyn RngCore>, ) -> Result<(Vec<LabeledCommitment<Self::Commitment>>, Vec<Self::CommitmentState>), Self::Error>

where P: 'a,

Produces a list of commitments to the passed polynomials. Cf. the section “Square-root commitment scheme” from the reference article.

Panics

Panics if rng is None, since Hyrax requires randomness in order to commit to a polynomial

fn open<'a>( ck: &Self::CommitterKey, labeled_polynomials: impl IntoIterator<Item = &'a LabeledPolynomial<G::ScalarField, P>>, commitments: impl IntoIterator<Item = &'a LabeledCommitment<Self::Commitment>>, point: &'a P::Point, sponge: &mut impl CryptographicSponge, states: impl IntoIterator<Item = &'a Self::CommitmentState>, rng: Option<&mut dyn RngCore>, ) -> Result<Self::Proof, Self::Error>

where Self::Commitment: 'a, Self::CommitmentState: 'a, P: 'a,

Opens a list of polynomial commitments at a desired point. This requires the list of original polynomials (labeled_polynomials) as well as the random values using by the Pedersen multi-commits during the commitment phase (randomness). Cf. sections “Square-root commitment scheme” and appendix A.2 from the reference article.

Panics

Panics if

• rng is None, since Hyrax requires randomness in order to open the commitment to a polynomial.
• The point doesn’t have an even number of variables.
• The labels of a commitment doesn’t match that of the corresponding polynomial.
• The number of variables of a polynomial doesn’t match that of the point.

fn check<'a>( vk: &Self::VerifierKey, commitments: impl IntoIterator<Item = &'a LabeledCommitment<Self::Commitment>>, point: &'a P::Point, _values: impl IntoIterator<Item = G::ScalarField>, proof: &Self::Proof, sponge: &mut impl CryptographicSponge, _rng: Option<&mut dyn RngCore>, ) -> Result<bool, Self::Error>

where Self::Commitment: 'a,

Verifies a list of opening proofs and confirms the evaluation of the committed polynomials at the desired point.

Panics

• If the point doesn’t have an even number of variables.
• If the length of a commitment does not correspond to the length of the point (specifically, commitment length should be 2^(point-length/2)).

Disregarded arguments

• rng

type UniversalParams = HyraxUniversalParams<G>

The universal parameters for the commitment scheme. These are “trimmed” down to Self::CommitterKey and Self::VerifierKey by Self::trim.

type CommitterKey = HyraxUniversalParams<G>

The committer key for the scheme; used to commit to a polynomial and then open the commitment to produce an evaluation proof.

type VerifierKey = HyraxUniversalParams<G>

The verifier key for the scheme; used to check an evaluation proof.

type Commitment = HyraxCommitment<G>

The commitment to a polynomial.

type CommitmentState = HyraxCommitmentState<<G as AffineRepr>::ScalarField>

Auxiliary state of the commitment, output by the commit phase. It contains information that can be reused by the committer during the open phase, such as the commitment randomness. Not to be shared with the verifier.

type Proof = Vec<HyraxProof<G>>

The evaluation proof for a single point.

type BatchProof = Vec<<HyraxPC<G, P> as PolynomialCommitment<<G as AffineRepr>::ScalarField, P>>::Proof>

The evaluation proof for a query set.

type Error = Error

The error type for the scheme.

fn batch_open<'a>( ck: &Self::CommitterKey, labeled_polynomials: impl IntoIterator<Item = &'a LabeledPolynomial<F, P>>, commitments: impl IntoIterator<Item = &'a LabeledCommitment<Self::Commitment>>, query_set: &QuerySet<P::Point>, sponge: &mut impl CryptographicSponge, states: impl IntoIterator<Item = &'a Self::CommitmentState>, rng: Option<&mut dyn RngCore>, ) -> Result<Self::BatchProof, Self::Error>

where P: 'a, Self::CommitmentState: 'a, Self::Commitment: 'a,

Open several polynomials at one or more points each (possibly different for each polynomial). Each entry in the in the query set of points contains the label of the polynomial which should be queried at that point.

fn batch_check<'a, R: RngCore>( vk: &Self::VerifierKey, commitments: impl IntoIterator<Item = &'a LabeledCommitment<Self::Commitment>>, query_set: &QuerySet<P::Point>, evaluations: &Evaluations<P::Point, F>, proof: &Self::BatchProof, sponge: &mut impl CryptographicSponge, rng: &mut R, ) -> Result<bool, Self::Error>

where Self::Commitment: 'a,

Verify opening proofs for several polynomials at one or more points each (possibly different for each polynomial). Each entry in the query set of points contains the label of the polynomial which was queried at that point.

fn open_combinations<'a>( ck: &Self::CommitterKey, linear_combinations: impl IntoIterator<Item = &'a LinearCombination<F>>, polynomials: impl IntoIterator<Item = &'a LabeledPolynomial<F, P>>, commitments: impl IntoIterator<Item = &'a LabeledCommitment<Self::Commitment>>, query_set: &QuerySet<P::Point>, sponge: &mut impl CryptographicSponge, states: impl IntoIterator<Item = &'a Self::CommitmentState>, rng: Option<&mut dyn RngCore>, ) -> Result<BatchLCProof<F, Self::BatchProof>, Self::Error>

where Self::CommitmentState: 'a, Self::Commitment: 'a, P: 'a,

Open commitments to all polynomials involved in a number of linear combinations (LC) simultaneously.

fn check_combinations<'a, R: RngCore>( vk: &Self::VerifierKey, linear_combinations: impl IntoIterator<Item = &'a LinearCombination<F>>, commitments: impl IntoIterator<Item = &'a LabeledCommitment<Self::Commitment>>, eqn_query_set: &QuerySet<P::Point>, eqn_evaluations: &Evaluations<P::Point, F>, proof: &BatchLCProof<F, Self::BatchProof>, sponge: &mut impl CryptographicSponge, rng: &mut R, ) -> Result<bool, Self::Error>

where Self::Commitment: 'a,

Verify opening proofs for all polynomials involved in a number of linear combinations (LC) simultaneously.