Integrate with ark-sponge

[tsunrise]

Summary

Currently, opening challenges are univariate, such that challenges={x, x^2, x^3, ...} where x is random. Now ark-sponge is stable, so we want to use the sponge API instead. Specifically, opening challenges will have two strategies:

• Univariate: Squeeze a field element x from sponge, and challenges[i] = x^{i+1}
• Multivariate: For each opening challenge, we squeeze a field element

Challenge Generator and Challenge Strategy

We define the strategy as an enum, and define a challenge generator to replace opening_challenges: dyn Fn(u64)-> F.

#[derive(Copy, Clone)]
pub struct ChallengeGenerator<'a, S: 'a + CryptographicSponge> {
    sponge_state: &'a mut S,
    strategy: ChallengeStrategy
}

pub enum ChallengeStrategy {
    Multivariate, 
    Univariate
}

ChallengeGenerator will have method next() to get the next random challenge.

New Interface for PolyCommit

pub trait PolynomialCommitment<F: Field, P: Polynomial<F>: Sized, S: CryptographicSponge> {
    fn setup<R: RngCore>(
        max_degree: usize,
        num_vars: Option<usize>,
        rng: &mut R,
    ) -> Result<Self::UniversalParams, Self::Error>;
    
    fn trim(
        pp: &Self::UniversalParams,
        supported_degree: usize,
        supported_hiding_bound: usize,
        enforced_degree_bounds: Option<&[usize]>,
    ) -> Result<(Self::CommitterKey, Self::VerifierKey), Self::Error>;

    fn commit<'a>(
        ck: &Self::CommitterKey,
        polynomials: impl IntoIterator<Item = &'a LabeledPolynomial<F, P>>,
        rng: Option<&mut dyn RngCore>,
    ) -> Result<
        (
            Vec<LabeledCommitment<Self::Commitment>>,
            Vec<Self::Randomness>,
        ),
        Self::Error,
    >
    where
        P: 'a;
    
    fn open<'a>(
        ck: &Self::CommitterKey,
        labeled_polynomials: impl IntoIterator<Item = &'a LabeledPolynomial<F, P>>,
        commitments: impl IntoIterator<Item = &'a LabeledCommitment<Self::Commitment>>,
        point: &'a P::Point,
        opening_challenges: ChallengeGenerator<_, S>,
        rands: impl IntoIterator<Item = &'a Self::Randomness>,
        rng: Option<&mut dyn RngCore>,
    ) -> Result<Self::Proof, Self::Error>;
    
    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>,
        opening_challenges: ChallengeGenerator<_, S>,
        rands: impl IntoIterator<Item = &'a Self::Randomness>,
        rng: Option<&mut dyn RngCore>,
    ) -> Result<Self::BatchProof, Self::Error>;
    
    fn check<'a>(
        vk: &Self::VerifierKey,
        commitments: impl IntoIterator<Item = &'a LabeledCommitment<Self::Commitment>>,
        point: &'a P::Point,
        values: impl IntoIterator<Item = F>,
        proof: &Self::Proof,
        opening_challenge: ChallengeGenerator<_, S>,
    ) -> Result<bool, Self::Error>
    where
        Self::Commitment: 'a;
    
    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,
        opening_challenge: ChallengeGenerator<_, S>,
    ) -> Result<bool, Self::Error>
    where
        Self::Commitment: 'a;
    
     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>,
        opening_challenge: ChallengeGenerator<_, S>,
        rands: impl IntoIterator<Item = &'a Self::Randomness>,
        rng: Option<&mut dyn RngCore>,
    ) -> Result<BatchLCProof<F, P, Self>, Self::Error>
    where
        P: 'a,
        Self::Randomness: 'a,
        Self::Commitment: 'a;
    
     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, P, Self>,
        opening_challenge: ChallengeGenerator<_, S>,
    ) -> Result<bool, Self::Error>
    where
        Self::Commitment: 'a;
}

---

For Admin Use

• Not duplicate issue
• Appropriate labels applied
• Appropriate contributors tagged
• Contributor assigned/self-assigned

[weikengchen]

Just found out one possible way to simplify ChallengeGenerator, by merging the struct and the enum.

pub enum ChallengeGenerator<'a, S: 'a + CryptographicSponge> {
    MultivariateFromSponge(&'a mut S), 
    UnivariateFromSponge(&'a mut S),
}

(untested)

[tsunrise]

Just found out one possible way to simplify ChallengeGenerator, by merging the struct and the enum.

pub enum ChallengeGenerator<'a, S: 'a + CryptographicSponge> {
    MultivariateFromSponge(&'a mut S), 
    UnivariateFromSponge(&'a mut S),
}

(untested)

Let me try this