ZK Summit 11 Folded

Note: This is a guest post written by Jack Gilcrest of Mach 34 detailing learnings from their integration of folding schemes into Cursive's ZK Summit 11 app. Thanks to Jack and Ian for their amazing work!

At the end of the year, your Instagram and Twitter feed is probably plagued with "Spotify Wrapped" posts. Spotify provides a service for you to tell your friends that you listened to 4,000 hours of Taylor Swift this year. But what if we could recreate this experience for live events?

If you missed the the previous blog post, check it out for context on Cursive's app. As a quick summary, zkSummit 11 issued NFC cards to every attendee and speaker, and also placed cards at each presentation. These NFC cards could produce Babyjubjub-ECDSA signatures, and the keys on these cards were grouped into Merkle trees of attendees, speakers, or talks. At zkSummit 11, you could tap any of these cards with your phone and prove you met an attendee or attended a talk by verifying the authenticity of the signature and the existence of the corresponding public key in the tree. Most importantly, Cursive deployed a 2PC/PSI service that allowed two users to discover the people they both met and the talks they both attended without revealing any extra information.

Cursive built the infrastructure for verifying the social layer at live events. With all of these signatures lying around, the idea to aggregate these signatures into a summary of an attendee's event experience presented itself. With some slight tweaks to the core signature/tree inclusion circuits developed by Cursive, we were able to combine these proofs to create a statement like "I met X other zkSummit 11 attendees" or "I attended Z unique talks at zkSummit 11." Once all your signatures have been aggregated, the Cursive app stores the proofs and creates a shareable webpage for you to easily show off private* and cryptographically verifiable metrics on the social network you built at zkSummit 11.

See the demo here

Why Folding

Cursive provides us a bunch of signatures by keys grouped in trees. Sure, we could batch a bunch of signatures together into a single proof, but that could get expensive and can't be amortized as you meet new people. What if we could recursively verify signatures into a single running sum as we acquire them?

Recursion is a huge part of real-world use of ZK proofs. In the past year, a novel approach to recursion called "Folding" has become quite popular. Folding has pros and cons, but in many cases can end up being far cheaper to recurse than FRI or EC-based aggregation. Folding has been explored across infrastructure use cases, but few have explored folding on the client side—and none have yet shipped to production. We decided to run zkSummit Folded to experiment with the UX of folding in consumer applications.

Tools for folding are really easy, too—zkSummit Folded was built using Nova-Scotia, a fantastic repository that allows Circom circuit developers to easily turn their circuits into IVC proofs used in a Nova proof.

Sonobe is a newer SDK for using folding.

• It already supports Circom, Arkworks, and Noname as circuit front ends
• Developers can currently use Nova+Cyclefold, with other folding schemes like Protogalaxy in the works
• IVC proofs can be wrapped in Groth16, which can comfortably settle onchain
• ZK IVC is on the way

If you're interested in working with folding, please start here!

In a normal Circom circuit, you'd define a set of input/output signals and mark some of them public. If you had some public hash you wanted to prove you know the secret preimage for, you'd supply the preimage as a private input and the hash as a public input (or output).

Nova is a bit different. Every circuit will take in an array step_in[N] and pass out an array step_out[N]. For step I of your circuit, step_in is constrained to be the step_out of I-1, and whatever you assign step_out to be in I will similarly be the step_in of I+1. In this way, you can constrain the sequential construction of some final output across many instantiations of your circuit.

In short, we can use this construction to combine many circuits verifying collected signatures, and amortize this work to be done as each signature is acquired rather than in one large batch at the end!

Anti zkSNARK Club

Nova folding is really two different proofs:

1. An "Incrementally Verifiable Computation" (IVC) which "folds" two relaxed witnesses into one.
2. A zkSNARK that "compresses" the proof and hides the witness.

An IVC proof demonstrates the correctness of a serialized computation, but the folded witness is used by the verifier and can leak info. Compressing the IVC proof will ensure that the entire IVC computation does not leak any information. Sounds great, right?

Well, this means that we can't do "multi-prover" IVC with private computations—we can either compress to ZK or pass sensitive witness data. In our project Grapevine, this means we can't recurse to derive a social graph. But zkSummit Folded only has one prover, so who cares? Also, this compression step is pretty expensive. On desktop, we benchmarked compression of our IVC proofs at over two minutes. zkSummit Folded on Cursive's app, a mobile experience limited to ~1GB of memory, would have been prohibitively expensive to compress client-side.

(Hyper)Nova creator Srinath Setty recently proposed some measures for decimating the cost of Spartan proving here: https://x.com/srinathtv/status/1817241873163133034

But if Grapevine using Nova can't do private multi-prover folding, why even work on it? Turns out, you can have ZK in your IVC proof after all. Our first attempt in Grapevine V1 and zkSummit Folded was simple—we just multiplexed in an "obfuscation" step that adds a step with as much random data as possible to the end of the proof. However, this turned out to be insecure as the witness toggling off the computation in the obfuscation step would reveal enough to leak information about the preceding logic step.

Fortunately, the new HyperNova](https://eprint.iacr.org/2023/573) paper defines a mechanic for achieving zero-knowledgeness inside the Nova IVC by rerandomizing the proof. This method involves folding in three instances instead of two—folding the real step on the running instance/witness, then folding a "blinding" step with a randomly sampled witness. In short, the new folding proof checks the instance from running -> real -> blind, and checks the blind witness against the blind instance, implicitly proving that the real instance is valid.

Now, we can either pass the IVC proof directly to the end verifier, or pass the IVC to a server to compress for us. With the time constraints of shipping for zkSummit Folded, we chose to provide the IVC proof, but we expect the pattern of "blinding" IVC proofs on the client for servers to compress will become increasingly common given the high degree of flexibility it provides!

Deployment Considerations

Recursion Overhead

Folding presents an overhead of ~10,000 constraints. In the case of small circuits, folding may not make sense unless the only alternative is verifying many proofs onchain. In earnest, a similar "zkSummit Wrapped" that never went onchain would be far more performant if it was a collection of dozens of groth16 proofs. zkSummit Folded's circuits were actually designed for batching to make the recursive overhead worthwhile, but this would make amortization of proofs more difficult and was otherwise scrapped at the app level due to time constraints.

Web Workers

One key accelerant of real proving times was the use of "web workers" to parallelize (what does it parallelize here?). Using wasm_bindgen_rayon, we can spawn web workers to simulate multithreaded computation. This method uses "SharedArrayBuffer" which will introduce certain incompatibilities in web apps that must be reckoned with.

The performance enhancements are considerable. Here is a rough sample taken by hand (average of 3 samples) on a 2^13 sized circuit (4784 constraints):

Conculsion

While proof times shown in the benchmarks above seem reasonable, they were benched on a desktop running the Cursive application. Unfortunately, we saw proof times range from 10-20 seconds depending on mobile hardware. There are certainly optimizations that were overlooked given a short development cycle, and further improvements would manifest with MoPro integration.

Arguably a bigger deterrent is the consequence of mobile apps and browser tabs needing to be in the foreground to run. A big benefit of using any type of recursion over a proof batching many signatures together was the ability to amortize the proving cost as actions happened. This vision was difficult to realize in the mobile context.

While the mobile experience left a lot to be desired, the same infrastructure used for zkSummit Folded would likely work incredibly well in a desktop-native context. So long as a user keeps the tab open, an app can asynchronously build up parts of an incremental computation for a quick and easy proof later on.

We expect ourselves (and others!) to explore this pattern more—whether with existing tooling in desktop contexts, or more efficient tooling retried in the mobile context—and look forward to sharing this experience in the future!

Mentions

• Nalin: Creating Nova-Scotia
• DMPierre, Arnaucube: Creating Sonobe, assisting in understanding and deployment of folding
• Barrywhitehat: Instigating the exploration of folding for recursion with multi-prover
• Srinath Setty: Making (Hyper)Nova, assisting with understanding of zk IVC
• Vivek & Andrew: Building the platform we could test this on, all of the setup, inviting us to work on it, and hacking through the night with us to get it working in time