Plonkish Working Group ZKProof6 Session

23 May 2024, 10:00
Scribe: Ying Tong

[repo: https://github.com/zkpstandard/wg-plonkish]

PlonKish relation

[https://github.com/zkpstandard/wg-plonkish/blob/main/src/relation.md]

  • [Daira-Emma] selectors are not separately specified, since they can be represented after optimisation as fixed columns (which might not be boolean because of selector combining)
  • [Daira-Emma] TODO: instead of separately specifying copy constraints for instance, fixed, and advice, we should generalise the equivalence relation \(\equiv_A\) to work for all three cases
  • [Ariel] re: custom constraints, \(p_u\) seems to only take a single row \(\mathsf{ROW}_j\), whereas in real circuits we need to access multiple offsets
    • [Daira-Emma] the abstract representation of the circuit uses virtual cells for simplicity; this can later be compiled to a version that uses offsets
    • [Ariel] a designer may find it more intuitive to have a constraint that can be applied across multiple rows
    • [Daira-Emma] writing it as a functional program is easier to reason about, rather than trying to express state which is a semantic concept; row offsets are an implementation detail which should be handled by the compiler
    • [Daira-Emma] hard-coding row offsets may be over-specifying the implementation, thereby possibly excluding more optimal layouts

Backend optimisations

[https://github.com/zkpstandard/wg-plonkish/blob/main/src/optimizations.md]

  • [Mary] a difficult judgment call – these complicate the specification, but some of them may be necessary to encourage adoption
  • [Daira-Emma] want to define a framework for optimisations, as opposed to specific optimisations
  • rotation constraints
    • more clarification needed on what these are; differs slightly across implementations
    • sometimes used instead of copy constraints: rotated columns can be re-used and don't need to be committed again
    • rotations require specific orderings => need a backend with some linear ordering of trace
    • excluding these from the abstract model preserves the desirable trait of allowing rows to be arbitrarily reordered
  • [Daira-Emma] are there circuits which use large rotations dependent on "wrap-around" (modulo n)?
    • e.g. "wrapping around" grand product that is too large
    • Decision: we don't need wrap-around, but should define shifts so that they don't underflow or overflow for used cells. (In the halo2 library they are not allowed to observably underflow or overflow regions.)

Action items

  • [PlonKish relation] instead of separately specifying copy constraints for instance, fixed, and advice, we should generalise the equivalence relation to work for all three cases
  • remove the wrap-around
  • currently, the definition of a multivariate polynomial outputs only a single element, so it isn't correct to use just one multivariate polynomial in a table lookup; instead, use the right number of multivariate polynomials for the corresponding table width.
    • this supports the specification of vector lookups
Select a repo