o1-labs
[types] refactoring types
There are two issues that I'd like to address in this thread:
- the lack of types
- the semantic of current types
The lack of types
In the first case, we sometimes build logic through functions passing tuples of primitive types to one another. The best example of this is the polynomial commitment code:
pub fn verify<EFqSponge, RNG>(
&self,
group_map: &G::Map,
batch: &mut Vec<(
EFqSponge,
Vec<Fr<G>>,
Fr<G>, // scaling factor for polynomials
Fr<G>, // scaling factor for evaluation point powers
Vec<(
&PolyComm<G>,
Vec<&Vec<Fr<G>>>,
Option<usize>,
)>,
&OpeningProof<G>, // batched opening proof
)>,
rng: &mut RNG,
) -> bool
where
EFqSponge: FqSponge<Fq<G>, G, Fr<G>>,
RNG: RngCore + CryptoRng,
I think in general, we should think and build types first, and then method on types. As Rob Pike says:
Rule 5. Data dominates. If you've chosen the right data structures and organized things well, the algorithms will almost always be self-evident. Data structures, not algorithms, are central to programming.
In the commitment tests I proposed a series of types that could help us make the API more understandable, as well as handle the individual types more easily:
/// A commitment
pub struct Commitment {
/// the commitment itself, potentially in chunks
chunked_commitment: PolyComm<Affine>,
/// an optional degree bound
bound: Option<usize>,
}
/// An evaluated commitment (given a number of evaluation points)
pub struct EvaluatedCommitment {
/// the commitment
commit: Commitment,
/// the chunked evaluations given in the same order as the evaluation points
chunked_evals: Vec<ChunkedCommitmentEvaluation>,
}
/// A polynomial commitment evaluated at a point. Since a commitment can be chunked, the evaluations can also be chunked.
pub type ChunkedCommitmentEvaluation = Vec<Fp>;
mod prover {
use super::*;
/// This struct represents a commitment with associated secret information
pub struct CommitmentAndSecrets {
/// the commitment evaluated at some points
pub eval_commit: EvaluatedCommitment,
/// the polynomial
pub poly: DensePolynomial<Fp>,
/// the blinding part
pub chunked_blinding: PolyComm<Fp>,
}
}
/// This struct represents an aggregated evaluation proof for a number of polynomial commitments, as well as a number of evaluation points.
pub struct AggregatedEvaluationProof {
/// a number of evaluation points
eval_points: Vec<Fp>,
/// a number of commitments evaluated at these evaluation points
eval_commitments: Vec<EvaluatedCommitment>,
/// the random value used to separate polynomials
polymask: Fp,
/// the random value used to separate evaluations
evalmask: Fp,
/// an Fq-sponge
fq_sponge: DefaultFqSponge<VestaParameters, SC>,
/// the actual evaluation proof
proof: OpeningProof<Affine>,
}
Semantic of types
The best example is the polynomial commitment type:
pub struct PolyComm<C> {
pub unshifted: Vec<C>,
pub shifted: Option<C>,
}
which is used for:
- non-hiding polynomial commitments (
PolyComm<G>) - hidden polynomial commitments (
PolyComm<G>) - the blinding factors associated to a hidden polynomial commitment (
PolyComm<F>)
As such, I would argue that the PolyComm structure is too generic and leaks abstractions. We should enforce the semantic of what we're using through the types, and have distinct types that can hold and represent the three different use-cases previously mentioned.
Another example are indexes.
pub struct Index<'a, G: CommitmentCurve>
where
G::ScalarField: CommitmentField,
{
/// constraints system polynomials
#[serde(bound = "ConstraintSystem<Fr<G>>: Serialize + DeserializeOwned")]
pub cs: ConstraintSystem<Fr<G>>,
/// polynomial commitment keys
#[serde(skip)]
pub srs: SRSValue<'a, G>,
/// maximal size of polynomial section
pub max_poly_size: usize,
/// maximal size of the quotient polynomial according to the supported constraints
pub max_quot_size: usize,
/// random oracle argument parameters
#[serde(skip)]
pub fq_sponge_params: ArithmeticSpongeParams<Fq<G>>,
}
// TODO(mimoo): a lot of this stuff is kinda redundant with the Index/ProverIndex. There probably should be a "commonIndex" and then a ProverIndex and VerifierIndex that includes it.
#[serde_as]
#[derive(Serialize, Deserialize)]
pub struct VerifierIndex<'a, G: CommitmentCurve> {
/// evaluation domain
#[serde_as(as = "o1_utils::serialization::SerdeAs")]
pub domain: D<Fr<G>>,
/// maximal size of polynomial section
pub max_poly_size: usize,
/// maximal size of the quotient polynomial according to the supported constraints
pub max_quot_size: usize,
/// polynomial commitment keys
#[serde(skip)]
pub srs: SRSValue<'a, G>,
// index polynomial commitments
/// permutation commitment array
pub sigma_comm: [PolyComm<G>; PERMUTS],
/// wire commitment array
pub qw_comm: [PolyComm<G>; GENERICS],
/// multiplication commitment
pub qm_comm: PolyComm<G>,
/// constant wire commitment
pub qc_comm: PolyComm<G>,
// poseidon polynomial commitments
/// round constant polynomial commitment array
pub rcm_comm: [[PolyComm<G>; PlonkSpongeConstants15W::SPONGE_WIDTH]; ROUNDS_PER_ROW],
/// poseidon constraint selector polynomial commitment
pub psm_comm: PolyComm<G>,
// ECC arithmetic polynomial commitments
/// EC addition selector polynomial commitment
pub add_comm: PolyComm<G>,
/// EC doubling selector polynomial commitment
pub double_comm: PolyComm<G>,
/// EC variable base scalar multiplication selector polynomial commitment
pub mul_comm: PolyComm<G>,
/// endoscalar multiplication selector polynomial commitment
pub emul_comm: PolyComm<G>,
/// wire coordinate shifts
// #[serde(bound = "Fr<G>: CanonicalDeserialize + CanonicalSerialize")]
#[serde_as(as = "[o1_utils::serialization::SerdeAs; PERMUTS]")]
pub shift: [Fr<G>; PERMUTS],
/// zero-knowledge polynomial
#[serde(skip)]
pub zkpm: DensePolynomial<Fr<G>>,
// TODO(mimoo): isn't this redundant with domain.d1.group_gen ?
/// domain offset for zero-knowledge
#[serde(skip)]
pub w: Fr<G>,
/// endoscalar coefficient
#[serde(skip)]
pub endo: Fr<G>,
// random oracle argument parameters
#[serde(skip)]
pub fr_sponge_params: ArithmeticSpongeParams<Fr<G>>,
#[serde(skip)]
pub fq_sponge_params: ArithmeticSpongeParams<Fq<G>>,
}
A few problems with indexes is that:
- there are some common fields between prover and verifier index.
- there isn't a clean distinction between global parameters (SRS) and per-circuit parameters (constraint system)
- it mixes types that are needed for the protocols, and pre-computed types for optimizations only
While I make no suggestion on how to change that, I think we should come up with a proposal.
Note that for the VerifierIndex, we end up creating our own version for the OCaml binding:
#[derive(ocaml::IntoValue, ocaml::FromValue, OcamlGen)]
pub struct CamlPlonkDomain<Fr> {
pub log_size_of_group: ocaml::Int,
pub group_gen: Fr,
}
#[derive(ocaml::IntoValue, ocaml::FromValue, OcamlGen)]
pub struct CamlPlonkVerificationEvals<PolyComm> {
pub sigma_comm: Vec<PolyComm>,
pub qw_comm: Vec<PolyComm>,
pub qm_comm: PolyComm,
pub qc_comm: PolyComm,
pub rcm_comm: Vec<Vec<PolyComm>>,
pub psm_comm: PolyComm,
pub add_comm: PolyComm,
pub double_comm: PolyComm,
pub mul_comm: PolyComm,
pub emul_comm: PolyComm,
}
#[derive(ocaml::IntoValue, ocaml::FromValue, OcamlGen)]
pub struct CamlPlonkVerificationShifts<Fr> {
pub r: Fr,
pub o: Fr,
}
#[derive(ocaml::IntoValue, ocaml::FromValue, OcamlGen)]
pub struct CamlPlonkVerifierIndex<Fr, SRS, PolyComm> {
pub domain: CamlPlonkDomain<Fr>,
pub max_poly_size: ocaml::Int,
pub max_quot_size: ocaml::Int,
pub srs: SRS,
pub evals: CamlPlonkVerificationEvals<PolyComm>,
pub shifts: CamlPlonkVerificationShifts<Fr>,
}
I think it'd be great if we didn't have to do this, and if we could directly use our struct. For this, the relevant stuff would have to move to its own substruct.
Chunked types is another one that I think should see some refactors. Basically some types are generic and either contain single field elements, or vectors of field elements (chunked evaluations).
![github-actions[bot] avatar](https://avatars.githubusercontent.com/in/15368?v=4 "Published by a pub.dev verified publisher"){kind=small}