This ad hoc update features a "guest post" from Nalin Bhardwaj, who has been starting to drive more of our efforts around the research<>infrastructure boundary.

The proving system developments that Nalin is describing here are really exciting. For those with less technical background, here are a few pieces of background context:

• We've been gaining conviction in the last 12-18mo that ZK recursion is going to be an important tool. In the last six months in particular, we've ramped up our efforts to better understand the trajectory of ZK recursion, and how to take advantage of it.
  • What does ZK recursion enable? A highly reductive but not-too-inaccurate mental model is that, if zkSNARKs are a 0 to 1, ZK recursion is a 1 to n on many application use cases (both on the dimension of "privacy" capabilities, as well as on the dimension of performance capabilities). More on this, from Nalin.
  • Robust infrastructure around recursion and composition are likely to be critical for our PCD agenda!
• Nova is a relatively recent piece of "ZK machinery" that enables new capabilities in ZK recursion. Nova (and the family of techniques it suggests) is looking very promising, from a performance, modularity, and simplicity standpoint.
• Throughout this post, Nalin makes a lot of comparisons to PLONKish. PLONKish is a family of zkSNARK proving systems that the ecosystem has largely converged around over the past 4 years, also due to (potentially similar) performance, modularity, and simplicity characteristics. The core argument here is that, what PLONKish did for zkSNARKs, Nova may do for ZK recursion.

One thing that Nalin touches on here is how Nova's characteristics, besides being first-order promising in and of themselves, are also important because they may be particularly amenable to creating second-order feedback loops between different levels of the R&D stack. In a future post, we'll discuss what these feedback loops look like and why it's particularly important for 0xPARC to orient around this kind of thinking.

Nova may be the next PLONK

Nova is a new scheme for accelerating repeated computations in a SNARK. One (oversimplified) way to think about it is that, in terms of verifier time and resources, you can use Nova to "compress" any computation that occurs N times (like a hash function, or a neural net layer) that you're trying to SNARK-ify into just a single instance of that computation. It belongs to a broader class of research ideas called split accumulation that focus on ways of “accumulating” verification of many claims of computation into another one thats cheaper (most popularly, this class includes the Halo 2 split accumulation scheme). Nova, in particular, is perhaps the mathematically simplest and most performant split accumulation scheme.

The pace of acceleration for Nova has really picked up over the past few weeks.

Research → Tooling

Here’s a diagram evidencing this claim in terms of research/implementation output:

Pay attention to the dates in the diagram above: much of the boxes in the Nova line were made in the last few weeks (even so, many of those already have implementations). We believe this acceleration has to do with the near-optimality of Nova, both in performance and simplicity. Simplicity is what enabled Nova to be implemented with minimal security assumptions, for its features to be modeled into proving system tooling, and for its real-world benchmarks to improve rapidly, ultimately driving a feedback loop and demand for more research.

Let’s compare Nova to Halo 2 split accumulation, another split accumulation scheme that zcash has been championing over the past couple years. Both schemes theoretically provide similar performance/capability unlocks, i.e. specifically the ability to accelerate zkSNARK proving for repeated computations. However, this comparison really sheds light on the second-order benefits of Nova's simplicity:

• There are no production-ready code implementations of Halo 2’s accumulation scheme, despite the paper fully describing it in English two and a half years ago. (as zcash have discovered, implementing the required complicated big-integer arithmetic securely and rapidly is quite difficult)
• Supernova is a generic improvement that applies to all split accumulation schemes (including Halo2’s) but it was derived on Nova’s construction first, likely due to Nova’s conceptual simplicity.

PLONK : zkSNARKs :: Nova : {split accumulation; IVC; recursive zkSNARKs;}

To better understand Nova's important role in the zkSNARK ecosystem, let's use an analogy.

In the last couple years, PLONK-ish proving systems have become the industry-standard SNARK proving system. PLONK-ish performance and simplicity came as a result of a series of iterations on the core components of the “modular SNARK”. For instance, just at the Polynomial IOP level, the lineage for the key ideas can be traced to Sonic → AuroraLight → Marlin → PLONK.