## 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](https://a16zcrypto.com/posts/article/17-misconceptions-about-snarks/#section--6)) ---  --- ### CCS - definition and R1CS->CCS - [CCS notes (click me)](https://hackmd.io/nQtquuk9QCGiB9EhUPgXvg) - Definition - R1CS->CCS - [CCS paper](https://eprint.iacr.org/2023/552.pdf) --- ### 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 - 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 Note: George --- ## Multifolding PoC (part 2) - Slides: https://github.com/arnaucube/math/blob/master/slides_hypernova-part2-multifolding-unfolded.pdf Note: Arnau --- ## Integration & Upstream effort - Goal: Integrate & upstream end-to-end with [microsoft/Nova](https://github.com/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](https://github.com/privacy-scaling-explorations/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](https://github.com/microsoft/Nova/pull/175) - 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](github.com/privacy-scaling-explorations/nova): [issues](https://github.com/privacy-scaling-explorations/Nova/issues), [sumcheck verifier](https://github.com/privacy-scaling-explorations/Nova/pull/28), [complete folding](https://github.com/privacy-scaling-explorations/Nova/issues/50) - [Upstream PRs](https://github.com/microsoft/Nova/pulls) - 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](https://hackmd.io/y8xoiHZ2SEGVTnDqWMJ-dQ?view) - [Sumcheck notes](https://hackmd.io/JOKCtRxGQM-HysukpW_yqQ)