Standardized `ProvingKey`, `VerifyingKey`, and `Proof` ABIs

bhgomes commented 2 years ago

Especially as projects move towards mainnet adoption of ZK-Garage, it's important that we set some specifications on the expected format of the various circuit-specific components in PLONK, down to the binary level. Whenever there are optimizations to be made on the compiler, prover, or verifier side that don't break API/ABI compatibility we can give library users guarantees about the state of existing provers or verifiers that have already been deployed to a blockchain protocol.

Goals

A major goal of this project is to ensure that stabilizing the data formats is future-proof against extensions to PLONK like lookups, custom gates, an arbitrary number of wires, ... etc.

Draft Proposal

The following is a draft proposal of what a standard format could look like.

Configuration

First, we should consider the kind of PLONK that a circuit is using, notably the kinds of features it has access to. These can exist in some standard configurations that look like this:

trait Configuration {
    /// Total Number of Wires Accessible to the Compiler
    const WIRE_COUNT: usize;

    /// Scalar Field Type
    ///
    /// This type represents the underlying coefficient field for polynomial constraints.
    type Field: algebra::Field;

    /// Polynomial Commitment Type
    type Commitment;

    /// Polynomial Commitment Opening Type
    type Opening;

    /// Polynomial Commitment Scheme Type
    type PolynomialCommitment: commitment::PolynomialCommitment<
        Self::Field,
        Commitment = Self::Commitment,
        Proof = Self::Opening
    >;
}

/// Scalar Field Type
pub type Field<C> = <C as Configuration>::Field;

/// Polynomial Commitment Scheme Type
pub type PolynomialCommitment<C> = <C as Configuration>::PolynomialCommitment;

/// Public Parameters Type
pub type PublicParameters<C> = <
    PolynomialCommitment<C> as commitment::PolynomialCommitment<Field<C>>
>::PublicParameters;

The default configuration for this repo would have WIRE_COUNT = 4.

TODO: We can add more to this configuration related to lookups and custom gates.

In order to produce ProvingKey and VerifyingKey we should have the following interface

fn compile<C, R>(
    public_parameters: &PublicParameters<C>,
    circuit: StandardComposer<C>,
    rng: &mut R
) -> Result<(ProvingKey<C>, VerifyingKey<C>), Error>
where
    C: Configuration,
    R: CryptoRng + RngCore + ?Sized;

NOTE: See https://github.com/ZK-Garage/plonk/issues/127 for a desired interface for commitment::PolynomialCommitment.

Proving Key

The ProvingKey (under a given Configuration) should be sufficient for producing a proof. Here's a desirable API for this:

fn prove<C, R>(
    proving_key: &ProvingKey<C>,
    circuit: StandardComposer<C>,
    rng: &mut R
) -> Result<Proof<C>, Error>
where
    C: Configuration,
    R: CryptoRng + RngCore + ?Sized;

The standard format of the ProvingKey is as follows:

struct ProvingKey<C>
where
    C: Configuration,
{
    gate_polynomials: Vec<(DensePolynomial<C::Field>, Evaluations<C::Field>)>,
    sigma_polynomials: [(DensePolynomial<C::Field>, Evaluations<C::Field>), C::WIRE_COUNT],
    linear_evaluations: Evaluations<C::Field>,
    preprocessed_vanishing_polynomial_evaluations: Evaluations<C::Field>,
}

Sources:

Verifying Key

The VerifyingKey (under a given Configuration) should be sufficient for verifying a proof. Here's a desirable API for this:

fn verify<C>(
    verifying_key: &VerifyingKey<C>,
    input: &[F],
    proof: Proof<C>
) -> Result<bool, Error>
where
    C: Configuration;

The standard format of the VerifyingKey is as follows:

struct VerifyingKey<C>
where
    C: Configuration,
{
    public_input_positions: Vec<usize>,
    gate_commitments: Vec<C::Commitment>,
    permutation_commitments: [C::Commitment; C::WIRE_COUNT],
}

Sources:

Proof

The standard format of the Proof is as follows:

struct Proof<C> 
where
    C: Configuration,
{
    wire_commitments: [C::Commitment; C::WIRE_COUNT],
    permutation_polynomial_commitment: C::Commitment,
    quotient_polynomial_commitments: [C::Commitment; C::WIRE_COUNT],
    aggregate_witness_opening: C::Opening,
    shifted_aggregate_witness_opening: C::Opening,
    wire_evaluations: [C::Field; C::WIRE_COUNT],
    permutation_evaluations: [C::Field, C::WIRE_COUNT],
    custom_evaluations: ???,
}

Sources:

What's Next

Fix todo issues marked with TODO and unknown types above marked with ???.
Introduce binary format for particular instantiations of the polynomial commitment scheme.
Update the spec with the new lookup information in https://github.com/ZK-Garage/plonk/pull/123.
Update the compile, prove, and verify APIs to the desired ones above.
Address gate unification and custom gate design requirements to make sure that these specs are future-proof.

stechu commented 2 years ago

One thing that nice to specify (not sure how to enforce) is the canonical serialization/deserialization of things like group element. The ultimate control is the upstream library tho.

CPerezz commented 2 years ago

I really like the proposal!

Few questions:

I assume inputs in verification stands for the public inputs right? If so, how do we know the possitions at which they need to be placed?
For prove I've been thinking about the fact that we should be able to provide an encoded set of all the witness inputs. So that we can generate the witness vectors with external tools and digest them internally. That would work by passing a type: impl Into/TryInto<EncodedInputs> as input and also, implementing Into/TryInto<EncodedInputs> for StandardComposer. WDYT? I think would be a nice momment to add this!

bhgomes commented 2 years ago

@CPerezz

I really like the proposal!

Thanks!

I assume inputs in verification stands for the public inputs right? If so, how do we know the possitions at which they need to be placed?

Yeah, I forgot to add them to the VerifyingKey. I've edited the spec above to include them now.

For prove I've been thinking about the fact that we should be able to provide an encoded set of all the witness inputs. So that we can generate the witness vectors with external tools and digest them internally. That would work by passing a type: impl Into/TryInto<EncodedInputs> as input and also, implementing Into/TryInto<EncodedInputs> for StandardComposer. WDYT? I think would be a nice momment to add this!

Not sure if you meant verify, so that the public input can be transformed from some structured data into a vector of scalars before being checked? I think this is a good idea in general, but it shouldn't necessarily live at this level of the API. At the end of the day, we still want something like a vector of inputs (and then associated with their gate positions internally). So I would not recommend adding it to this API, but I think it would be cool to add tooling for this on top of the &[F] API.

This kind of infrastructure could actually be accomplished by something like serde where structured data is "serialized" into a "vector of scalars" format. I've been thinking about it for some time, but haven't formalized the requirements quite yet. Also, higher-level compilers can provide this infrastructure during transpiling from DSL or other mechanisms.

CPerezz commented 2 years ago

FYI; Spec document being worked on in: https://hackmd.io/3v8dBSfuQiGlGLAx2RQe9w?view will have a close relation with this.

We might want to extend it and do all at once :)

ZK-Garage / plonk