Agenda

  • CCS
  • Multifolding PoC
  • E2E Integration & Upstream effort
  • Next steps

Customizable Constraint System (CCS)

  • R1CS generalization; translate R1CS statement into CCS statement (NP-complete equivalance)
    • only matrix-vector products and Hadamard (entry-wise) vector products
  • Capture R1CS, Plonkish and AIR w/o overhead
  • Not tightly coupled to proof system

Note:
Oskar

CCS continue

  • Promise: Unify R1CS/Plonkish/Air, separate constraint system and back-end
  • Nova not limited to R1CS, use Plonkish for different proof systems, etc

(From Thaler's 17 misconceptions about SNARKs)

CCS - definition and R1CS->CCS

CCS -> Plonkish

See: https://hackmd.io/nQtquuk9QCGiB9EhUPgXvg#CCS-and-Plonkish-intro

Note:
Emphasithe on witness deduplication.

CCS - Lookup

CCS - Future?

  • We lack a working Plonkish translation.
    • Fast enough?
    • Big changes for lookups? Dynamic lookups possible?
  • Traction/motivation for tooling to switch?
  • We need a standard plonk format to transpile from. PLAF?
  • Follow up from new papers as ProtoStar for CCS. (Already not in ProtoGalaxy).

Multifolding PoC

Multifolding PoC (part 1)

Note:
George

Multifolding PoC (part 2)

Note:
Arnau

Integration & Upstream effort

  • Goal: Integrate & upstream end-to-end with microsoft/Nova
    • E.g. ParaNova PoC not upstreamed, harder to get feedback loops with community
  • Rationale 1: Nova->HyperNova small diff, less work for E2E PoC with realistic benchmarks
  • Rationale 2: Schelling point for Nova work (Nova Scotia, Lurk Labs, ParaNova PoC etc)

Integration cont

  • Above was in theory, in practice many challenges
  • Work done in pse/Nova main branch, ~4k LOC
  • A lot of problems in terms of libraries, polynomial APIs/representations, etc

Note:
Oskar

Current status

  • E2E Integration mostly done but missing some WIP things: sumcheck verifier circuit; final folding steps; MinRoot benchmarks
  • Upstream PRs
    • WIP PR in microsoft/Nova
    • Addressing major issues/feedback then updating this
    • Splitting up into smaller chunks, some merged

Some problems we faced

  • Extremely abstracted trait system in Nova (premature opt).
    • Group trait re-impl.
    • Some inline impls for poly ops (also fixed to R1CS case only).
  • VirtualPoly/MLE EqPoly, endianness & others.
  • Providers needed.

Some problems we faced

  • Sumcheck embedded into Nova. Hard to extract and generalize.
  • Lots of legacy code that would need refactor.
  • Bellpearson makes write circuits almost imposible.

Next steps

Decisions to take for future

  1. Current path: Finish integration + benchmarks
  2. Move to arkworks (now or later)
  3. Change focus to shiny new thing

Current path (cont)

  • Lookup integration?
  • Put severe work on refactoring Nova to get rid of Providers & others.
  • Start exploring a Nova as a Blackbox impl too.
  • Focus on a parallel client for HyperNova (ParaHyperNova).
  • Own some middle libs like zkcrypto/poly or zkcrypto/sumcheck.
Select a repo