VerifyingKey Serialisation

[nalinbhardwaj]

Closes #449 by storing selectors (the input to compress_selectors) as part of the serialised vkey. On reads, reruns the selector compression on the cs object. This also partly completes #643 (by creating the "post' version as the default, afaict no place needs serialisation for the pre version in the current codebase).

Tested using the circuits from https://github.com/nalinbhardwaj/zordle and https://github.com/icemelon/halo2-examples/tree/master/src/fibonacci. This is also extremely useful for faster wasm verifiers!

[parazyd]

Are there any plans to merge this?

[str4d]

We discussed this PR in Halo 2 Office Hours today, and decided that we will not merge it as-is. The core issue is that the serialization format being defined here is tightly coupled to the current implementation, and will be very difficult to retain support for after the planned optimisation / FloorPlanner refactorings occur.

For example, during keygen we extend the set of fixed column commitments to include commitments to the post-selector-combining selector columns: https://github.com/zcash/halo2/blob/5678a506cbec60d593a21ff618d09bed48abf7f2/halo2_proofs/src/plonk/keygen.rs#L222-L227

Then in VerifyingKey::read we read the post-selector-combining fixed commitments, read the pre-selector-combining selector definitions, re-compress the selector columns, and throw away the resulting selector polynomials (without checking that the effect of the compression on the constraint system's gates was correct or consistent with the parsed fixed commitments): https://github.com/zcash/halo2/blob/58e797da937c5193ce43ad333f22ead664f1ba61/halo2_proofs/src/plonk.rs#L101-L103 https://github.com/zcash/halo2/blob/58e797da937c5193ce43ad333f22ead664f1ba61/halo2_proofs/src/plonk.rs#L129

So as-is, the implicit serialization format is cutting half-way through the selector-combining optimisation, instead of picking a side. This specific issue could for instance be averted by not serializing the fixed commitments for the selectors, and always re-deriving them afterwards. Alternatively we could re-derive them and check they match, but then we're doing the same computational work during parsing with no benefit to encoding size. Solving this specific issue is a blocker on this PR (and it would be good to check for any other similar specific issues).

But if we did make that fix, we are then in a situation where the implicit serialization format is still cutting part-way through the logic that we want the FloorPlanner to be responsible for. Maintaining compatibility with this format would place strong constraints on how we designed the new FloorPlanner APIs, and probably require special-casing the selector-combining optimisation near-indefinitely (rather than it becoming an implementation detail of specific floor planners).

The most productive route forward would I think be to work on creating a post-optimisation VerifyingKey struct (the second half of #643), and then defining an encoding format for it. This can be done without blocking on the FloorPlanner refactoring, as it's about defining the type that would exist on the output side of the FloorPlanner rather than anything within its boundaries. It would require defining canonical encodings for polynomials as well as the polynomial ASTs we use to represent gates; we probably want to look at https://crates.io/crates/postcard for actually producing the encoding format.

[jonathanpwang]

I'm curious - how do you feel about just using #[derive(Serialize, Deserialize)]? That would avoid all of this. I have yet to benchmark but I would guess the bincode serialization/deserialization will be faster than what's currently implemented. This would involve the PrimeField to also implement Serialize, Deserialize.

[str4d]

I'm curious - how do you feel about just using #[derive(Serialize, Deserialize)]? That would avoid all of this.

That would not solve the above problem, and in fact would make the implicit encoding even more tightly coupled to the current implementation.

Once the types issue is addressed however, and a VerifyingKey type exists that contains precisely what should be encoded in precisely the internal form required for circuit correctness, then that could be an approach taken (using postcard as I suggested above).

[str4d]

The most productive route forward would I think be to work on creating a post-optimisation VerifyingKey struct (the second half of https://github.com/zcash/halo2/issues/643), and then defining an encoding format for it.

I'm going to try working on this some time next week.

[str4d]

The most productive route forward would I think be to work on creating a post-optimisation VerifyingKey struct (the second half of #643), and then defining an encoding format for it.

I'm going to try working on this some time next week.

We did the first phase of this in Halo 2 Office Hours today. The resulting exploratory changes are in #781, along with the conclusions we drew from them about how the real refactor should work.

[parazyd]

@str4d For retaining compatibility and more comfortable API usage for users which do not use serde, why not define the encoding and decoding format explicitly in the halo2 crate?

It seems like it would give you finer-grained control over the format, and it is also low overhead for people that use different serialization methods (i.e. they only have to wrap the defined halo2 encoding format in whatever trait their serialization library needs).

[hanzhichao]

any update about the provingkey and verifyingkey serialization?

[themighty1]

@hanzhichao , PSE fork supports key serialization https://github.com/privacy-scaling-explorations/halo2/blob/main/book/src/user/experimental-features.md#provingkey--verifyingkey-deserialization-and-serdeformat