Last week, a strange paper (by Wilson Nguyen et al.) came out: Revisiting the Nova Proof System on a Cycle of Curves. Its benign title might have escaped the attention of many, but within its pages lied one of the most impressive and devastating attack on a zero-knowledge proof (ZKP) system that we’ve ever seen. As the purpose of a ZKP system is to create a cryptographic proof certifying the result of a computation, the paper demonstrated a false computation result accompanied with a valid proof.
To put things into context, we had just launched zkSecurity (the company behind this blog) a month ago, on the observation that many user applications built on top of ZKP frameworks were going to be buggy. But seldom had we seen complete breakage of the frameworks and systems themselves. There was the 00 attack (by Nguyen Thoi Minh Quan) but it targeted a bad (plonk) implementation (which accepted the value 0 as a valid proof, always). There was also the counterfeiting vulnerability on Zcash discovered in 2018, and which could have allowed anyone to produce false proofs for their circuits, due to a vulnerability in the setup phase of the original paper.
But since then, nothing. And then just last week, one of the most important implementations of a ZKP system, Nova (from Microsoft nonetheless), got casually broken. We’re half way through 2023, but we’re pretty confident that it’s going to be hard to top this one as ZK attack of the year.
Note that Nova was fixed, and that the attack came with a security proof for the fix. Furthermore, Nova is one of the cleanest ZK implementation, accompanied by one of the most well-written paper in the field. If there’s one take away from this, is that these systems are complex and that no one is immune from bugs.
But what is Nova?
Nova is an Incrementally Verifiable Computation (IVC) scheme. In layman’s term, it allows you to repeat the same computation ad-infinitum, and then stop whenever you want to create a proof for the whole thing. Why would we want that? Usually for two reasons. The first is that it allows us to create proofs for long-running (or never-ending) computations at different points in time (for example, to create proofs at different point in time of a Fibonacci sequence, or of blocks being added on top of a blockchain). The second is that our ZKP systems are currently often quite limited and need to constrain the size of the programs they can prove. Breaking them down to repeatable pieces (trust me that it’s possible) and using this IVC thing seems to be the way to go.
More formally, the new paper has this excellent diagram that resumes what IVC looks like visually:
As you can see, the first state is $z_0$, and this is fed as input to some function $F$ repeatedly (with some other auxiliary inputs $text{aux}_i$ at the different steps) to finally return $z_i$. Nova, or IVC schemes in general, allow us to create a proof of that entire computation.
At the core of Nova lies a folding scheme
The particularity of Nova, and of many recent schemes that follow the same techniques (e.g. Protostar and Hypernova), is that the IVC is performed before any actual ZKP is produced. This means that this recursive procedure is usually quite cheap, as you’re avoiding the creation and verification of an actual proof at every step.
What’s more, is that all of these schemes are sort of constructed in the same way:
- they first construct a folding scheme (also called split accumulator by others)
- and then they use that inside of a ZKP circuit to construct this IVC thing
The folding / accumulator thing is not necessary to understand the attack (or the IVC) so we can simplify it and abstract it in this article. The way you should think about it, is that a folding scheme takes two things (I’ll call accumulators) and reduce them to one thing (a new accumulator).
If you’re curious, we do this all over the place in ZKP systems, and it’s often done in the same way: by taking a random linear combination of the things.
Folding schemes are often split into two parts: a prover and a verifier part, where the verifier handles a shorter description/summary of the accumulator (usually produced using commitments).
Splitting the folding into two parts allows most of the heavy work to be done outside of the circuit (by running the prover part), and the circuit to only verify that the work’s been done correctly (by running the verifier part). This is also why other papers call this scheme a “split accumulator” scheme.
But from here on,
