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

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 notes (click me)
  • Definition
  • R1CS->CCS
• CCS paper

CCS -> Plonkish

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

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

• Code: https://github.com/privacy-scaling-explorations/multifolding-poc

Multifolding PoC (part 1)

• Slides https://docs.google.com/presentation/d/13aRS8LA5fuNUOFX_c8Im6LOcsMSWeMezP8NurtsfCMA/edit?usp=sharing

Multifolding PoC (part 2)

• Slides: https://github.com/arnaucube/math/blob/master/slides_hypernova-part2-multifolding-unfolded.pdf

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

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

• pse/Nova: issues, sumcheck verifier, complete folding
• Upstream PRs
• Benchmarks: E2E working -> MinRoot
  • For more complex benchmark need time+Plonk conversion (not worth it now?)
• Basic write-up

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.

Misc links

• HyperNova study notes
• Sumcheck notes