Simplified Polynomial Commitment Trait

[bhgomes]

For PLONK, we only need a subset of the ark-poly-commit interface and a lot of the ark-poly-commit APIs are unnecessarily restrictive. I propose the following trait for the generic PLONK interface:

/// Polynomial Commitment
trait PolynomialCommitment<F>
where
    F: Field,
{
    /// Commit Key Type
    ///
    /// This type is required for the [`commit`](Self::commit), [`commit_many`](Self::commit_many),
    /// and [`open`](Self::open) methods which form the prover-side of the commitment scheme.
    type CommitKey;

    /// Verify Key Type
    ///
    /// This type is required for the [`verify`](Self::verify) method which forms the verifier-side
    /// of the commitment scheme.
    type VerifyKey;

    /// Randomness Type
    ///
    /// Randomly sampled data used to blind the polynomial scheme.
    type Randomness;

    /// Commitment Type
    ///
    /// This type is the return type of the [`commit`](Self::commit) and
    /// [`commit_many`](Self::commit_many) methods.
    type Commitment;

    /// Proof Type
    ///
    /// This type is the return type of the [`open`](Self::open) method which proves that a set of
    /// polynomials were opened at a particular point.
    type Proof;

    /// Error Type
    type Error;

    /// Samples a randomness element for a polynomial commitment.
    fn sample_randomness<R>(rng: &mut R) -> Self::Randomness
    where
        R: CryptoRng + RngCore + ?Sized;

    /// Commits to the `polynomial` with `randomness`.
    fn commit<P>(
        key: &Self::CommitKey,
        polynomial: &P,
        randomness: &Self::Randomness,
    ) -> Result<Self::Commitment, Self::Error>
    where
        P: Polynomial<F>;

    /// Commits to all the `polynomials`, randomly sampling [`Randomness`](Self::Randomness) values
    /// using [`sample_randomness`](Self::sample_randomness).
    #[inline]
    fn commit_many<'p, P, PI, R>(
        key: &Self::CommitKey,
        polynomials: I,
        rng: &mut R,
    ) -> Result<(Vec<Self::Commitment>, Vec<Self::Randomness>), Self::Error>
    where
        P: 'p + Polynomial<F>,
        PI: IntoIterator<Item = &'p P>,
        R: CryptoRng + RngCore + ?Sized,
    {
        let mut commitments = Vec::with_capacity(polynomials.len());
        let mut randomness = Vec::with_capacity(randomness.len());
        for polynomial in polynomials {
            let sampled_randomness = Self::sample_randomness(rng);
            commitments.push(Self::commit(key, polynomial, &sampled_randomness)?);
            randomness.push(sampled_randomness);
        }
        Ok((commitments, randomness))
    }

    /// Opens the `polynomials` at `point` with the opening `challenge` provided by the verifier,
    /// returning a proof ensuring that the `polynomials` are consistent with their `commitments`
    /// and `randomness`.
    fn open<'p, 'c, 'r, P, PI, CI, RI, R>(
        key: &Self::CommitKey,
        polynomials: PI,
        point: &F,
        challenge: &F,
        commitments: CI,
        randomness: RI,
        rng: &mut R,
    ) -> Result<Self::Proof, Self::Error>
    where
        Self::Commitment: 'c,
        Self::Randomness: 'r,
        P: 'p + Polynomial<F>,
        PI: IntoIterator<Item = &'p P>,
        CI: IntoIterator<Item = &'c Self::Commitment>,
        RI: IntoIterator<Item = &'r Self::Randomness>,
        R: CryptoRng + RngCore + ?Sized;

    /// Verifies that the polynomials committed to in `commitments` evaluate to `values` at the
    /// given `point` using the `proof` from the prover.
    fn verify<'f, 'c, FI, CI, R>(
        key: &Self::VerifyKey,
        point: &F,
        values: FI,
        commitments: CI,
        challenge: &F,
        proof: &Self::Proof,
        rng: &mut R,
    ) -> Result<bool, Self::Error>
    where
        F: 'f,
        Self::Commitment: 'c,
        FI: IntoIterator<Item = &'f F>,
        CI: IntoIterator<Item = &'c Self::Commitment>,
        R: CryptoRng + RngCore + ?Sized;
}

This design has some advantages over the ark-poly-commit interfaces like:

• No labeled polynomials and commitments: we aren't using the checks that are part of this API in our code and it introduces unnecessary Strings that we are also not using
• Remove necessary "multi-commit" implementation: The ark-poly-commit interfaces require a method called commit which performs an iterated sequence of commits. For each of the implementations in the standard arkworks library, this method does exactly the same thing (the implementation defined in commit_many) but makes it required, not optional.
• Remove unnecessary arkworks types/constraints: Some extra associated types and trait constraints are removed as not necessary to express the core logic of a polynomial commitment and are not used by PLONK
• Remove batched API: We are not using any of the batched methods (which are all optional anyway), so we can add them back in if they ever become useful.
• Explicit random sampling API: Arkworks does this weird RNG API that is too restrictive and non-canonical, and we should just be explicit about RNGs, especially if we want to use a specific implementation of an RNG

It would then be relatively easy to implement KZG, IPA, etc. under this new API and expose them to users. Also, it would also be relatively easy to write an adapter from any ark_poly_commit implementer to this API since we have fewer requirements.

[bhgomes]

Open Design Questions:

• How to incorporate the HomomorphicCommitment trait?
• How to calculate the blinding level (depending on whether or not the PolynomialCommitment is hiding)?

[bhgomes]

And a setup method on an extension trait:

trait PolynomialCommitmentSetup<F>: PolynomialCommitment<F>
where
    F: Field,
{
    /// Samples a [`CommitKey`](Self::CommitKey) and [`VerifyKey`](Self::VerifyKey) for
    /// this polynomial commitment scheme.
    ///
    /// # Safety
    ///
    /// In general, this sampling is not secure and could leak a trapdoor for this commitment scheme.
    /// Instead, use keys generated by a multi-party trusted setup for more security against
    /// trapdoor-based attacks.
    fn setup<R>(rng: &mut R) -> (Self::CommitKey, Self::VerifyKey)
    where
        R: CryptoRng + RngCore + ?Sized;
}