implement strong types for chunked evaluations

[mimoo]

In https://github.com/o1-labs/proof-systems/pull/680 we removed code related to chunked evaluations: when a polynomial is too big so we have to split it into "chunks" and evaluate these chunks separately.

We used to have that due to one polynomial (the quotient polynomial) but we actually do not evaluate it anymore (thanks to Maller's optimization)

We decided against going with #680 because we might want to actually support a different path going forward: a smaller URS which would mean that everything is chunked.

The goal of this PR is to clean these chunked evaluations that #680 tried to remove:

• in proof.rs::ProofEvaluations and other similar types, F should become ChunkedEvaluations<F>.
• the code related to these chunked evaluations (I think in prover.rs or verifier.rs should be moved to methods on this ChunkedEvaluations
• there's already some Chunked types in the utils crate, so it probably is a good place to create that new type
• as long as that new type has a nice API that could be used outside of kimchi by other people, it'll be a good thing!

protip: just look at #680 to find places that are impacted by this issue

[mimoo]

some more information on what would be in such a type. I think it should closely look like ChunkedPolynomial (in that it also tracks the size of each chunk).

we should only be able to create it by evaluating a polynomial, ideally the evaluate_chunks function should return a ChunkedPolynomial.

I think introducing this type first would be a good idea. Then two things can be done (I can help provide more support there as well):

first: simplify the handling of chunks

second: replace all the vectors in ProofEvaluations and LookupEvaluations with this new type

[duguorong009]

@mimoo Can you add the simple commit including the ChunkedEvaluations type implementation? I tried to update the Vec<F> inside ProofEvaluations and LookupEvaluations, but not much successful. I think I need more help, like rough commit or more guide detail. Thanks in advance.

[mimoo]

I tried to update the Vec<F> inside ProofEvaluations and LookupEvaluations, but not much successful.

it probably would be easier to start like this:

1. create a type called ChunkedEvaluations { chunks: Vec<F> } in utils/src/chunked_evaluations.rs
2. replace the Vec<F> in the structures you mentioned with that wrapper structure

if you have that I think that would be a good start

[duguorong009]

@mimoo Thanks for the tips! :+1:

[duguorong009]

@mimoo I started implementing the type ChunkedEvaluations. Atm, I created a test PR on my github fork. https://github.com/duguorong009/proof-systems/pull/1 Now, I stuck with serde issue. Can you check the PR commit and the snapshot for more recommend? Thanks in advance.

[mimoo]

so some comments:

• yeah you will need to use serde_as on your ChunkedEvaluations type to implement serde serialize/deserialize. You can see how this is done on all the types in this proof.rs file.
• You should change this line to read pub evals: [ProofEvaluations<G::ScalarField>; 2] and have the ChunkedEvaluations type be a real type (not an instantiation of a type parameter)

[duguorong009]

so some comments:

• yeah you will need to use serde_as on your ChunkedEvaluations type to implement serde serialize/deserialize. You can see how this is done on all the types in this proof.rs file.
• You should change this line to read pub evals: [ProofEvaluations<G::ScalarField>; 2] and have the ChunkedEvaluations type be a real type (not an instantiation of a type parameter)

I am not sure if my thought is okay. @mimoo I think your second recommend meaning is that I should keep the pub evals: [ProofEvaluations<G::ScalarField>;2] in the definition. And I should update the ProverProof implementation so that it can use the ChunkedEvaluations in the place of G::ScalarField. As far as I know, the G::ScalarField is for one evaluation value. But, the ChunkedEvaluations is for representing the multiple evaluation values. Then, how can I keep the G::ScalarField in the pub evals: ... definition?

[mimoo]

eventually the other structures should be generic based on a type of Field, not a Vec<Field>. For example:

pub struct ProofEvaluations<F> {
    /// witness polynomials
    pub w: [ChunkedEvaluations<F>; COLUMNS],

    /// permutation polynomial
    pub z: ChunkedEvaluations<F>,

does that make sense?

Also, I think serde might need help there as well:

#[serde(bound = "ChunkedEvaluations<F>: Serialize + DeserializeOwned")]
pub struct ProofEvaluations<F> {
    /// witness polynomials
    pub w: [ChunkedEvaluations<F>; COLUMNS],

    /// permutation polynomial
    pub z: ChunkedEvaluations<F>,

[mimoo]

basically something that looks like this:

Thing2<F> {
  a: F,
}

Thing {
  thing2: Thing2<Vec<F>>

should change to something that looks like this:

Thing2<F> {
  a: Vec<F>,
}

Thing {
  thing2: Thing2<F>

(but using this chunkedevaluations type of course)

[duguorong009]

Thanks for the guidance! @mimoo I updated the commit with the recommended changes. Now, there are 2 issues left(just for my eyes). zero proofevaluations generic scalars calculus

@mimoo Can you check the current PR update & let me know where to fix up?

[mimoo]

had a pass at it and it looks good to me

[duguorong009]

had a pass at it and it looks good to me

Thanks for the review on the test PR! @mimoo 👍 I will create a real PR after resolve the issues I mentioned.

[duguorong009]

@mimoo I have been trying to fix the ProofEvaluations::dummy_with_witness_evaluations(https://github.com/duguorong009/proof-systems/blob/guorong/impl-chunked-evaluations/kimchi/src/proof.rs#L236-L250) after introducing ChunkedEvaluations. I think the dummy_with_witness_evaluations is simply filling the w field with [F: COLUMNS] and other fields as ark_ff::Zero value. Then, how can we apply the ChunkedEvaluations concept here? (I tried to omit the impl, but looks like they are used in other utils like EndoSclMul and turshi.)

[mimoo]

you could create a dummy function for the new type as well

[mimoo]

btw @duguorong009 don't hesitate to let me know if you're stuck on something and need help : ) I think you had a good PR!

[duguorong009]

Thanks! @mimoo Yes, will reach out for help.

[duguorong009]

@mimoo Can you give me more detail about the following codes?

1. Dummy function for the ProofEvaluation.
2. Transpose function for the ProofEvaluation.

Thanks in advance.

[mimoo]

1. dummy is most likely something like a default() function, and should be used in tests. (It'd be nice if these kind of things were gated behind a #[cfg(test)])
2. transpose is like a matrix transpose: IIRC I got rid of it in my own PR, I don't think it needs to exist : o

[duguorong009]

@mimoo Can you let me know if we still need these evals? These evals output the ProofEvaluation of SINGLE Field, which explains why current ProofEvaluation has this comment.

/// Polynomial evaluations contained in a `ProverProof`.
/// - **Chunked evaluations** `Field` is instantiated with vectors with a length that equals the length of the chunk
/// - **Non chunked evaluations** `Field` is instantiated with a field, so they are single-sized#[serde_as]

[mimoo]

hey! Sorry this escaped me. I would say yes

[duguorong009]

Hmm, if so, it means that there is a case when the ProofEvaluations<F> could be struct of single Field element. Then, how about using the ChunkedEvaluations type wherever the ProofEvaluations<Vec<F>> is?
Or, how about closing this issue now, and re-opening in the future? @mimoo 🤔

[duguorong009]

@mimoo I think this issue should be close now & re-open in the future. The reason is that there are still cases when the ProofEvaluations<F> could be instantiated with SINGLE F elements. I will stop here(closed my own PR), and come back later.

[mimoo]

I think this task is getting a bit harder with the recent changes, but we should keep it around as it's still something that would be great to have as a type even if we have to use it by instantiating a type parameter (instead of inlining it). Basically, the Vec<F> in some places should be ChunkedEvaluations<F>

[duguorong009]

Thanks for additional tips! @mimoo I will try to retackle the issue.

[github-actions[bot]]

Stale issue message

[github-actions[bot]]

Stale issue message