I initially posted this on https://minaprotocol.com/blog/kimchi-the-latest-update-to-minas-proof-system
(photo taken from https://unsplash.com/photos/M_mDgb8guhA)
We recently released an update to our proof system for Mina called Kimchi. Kimchi is the main machinery we use to generate the recursive proofs that allow the Mina blockchain to remain of a fixed size of 22KB. It will also soon enable privacy and local execution of smart contracts with our snapps update. In this post, we’ll go through what Kimchi is and what’s different about it.
First, it is good to see where in the stack we are. Looking at the edge of the network, what we can see is a big blackbox: Mina.
If you’re curious enough, you can open it and see what’s inside. At some point you’ll end up with pickles. Pickles is the recursion layer, it is the protocol that we use to create proofs of proofs of proofs of … and reduce the blockchain to a fixed-size of under 22KB.
Pickles need something to create proofs though, and this is what Kimchi is:
In this post, we’ll attempt to create some abstractions and simplifications to teach intuitions about what Kimchi is. We will try to keep explanations at a relatively high level, so it will be up to you to open the blackboxes that we will lay before you.
One of these black boxes, for example, are the pasta curves.
There’s clearly a theme here. All that’s left is to change Mina’s name to another pickled condiment.
A bit of context
Kimchi is based on PLONK, a proof system released in 2019 by Ariel Gabizon, Zachary J. Williamson, and Oana Ciobotaru. Since then, many ameliorations and extensions have been proposed. There’s been fflonk, turbo PLONK, ultra PLONK, plonkup, and recently plonky2. It’s hard to follow, but essentially all these protocols implement variants of PLONK. Thus, we call them plonkish protocols. Kimchi is such a plonkish protocol.
Today, PLONK is regarded as one of the most ambitious general-purpose zero-knowledge proof constructions. Many projects like Zcash, Polygon Zero (formerly known as Mir Protocol), Aztec network, Dusk, MatterLabs (zksync), Astar, and anoma, have their own implementation of the proof system.
But first, what is a proof system?
Let’s look at a scenario that should shed some light on the construction’s interface. If you understand this section, you’re halfway there, as you’ll be able to think for yourself on how general-purpose zero knowledge proofs can be used without having to figure out what’s going on inside of it.
Let’s imagine that Alice has a sudoku puzzle. She sends it to Bob, and Bob finds a solution to the puzzle. To prove it to her, he sends her the solution.
Alice can then run the solution, with the sudoku, in a program that will return true if the solution is correct.
The problem is that Bob doesn’t really want to share his solution… So instead, he runs the program himself, on his laptop, and tells Alice “I know a solution, trust me, I just ran the verify solution program on my laptop and it returned true“.
Obviously Alice has no reason to trust Bob. We’re in a bit of a pickle. This is where protocols like PLONK can be useful. The first step is to take our verify solution program in a special format (I’ll come back to that later) and compile it down to two distinct blobs of data:
- the prover index (sometimes called the prover key, although it’s not a real key)
- the verifier index (sometimes called the verifier key, not a key either)
Then the prover (Bob) can use a prove algorithm with the prover index, the sudoku puzzle, as well as his solution to execute the program and produce a proof of correct execution (a proof that the program returned true in this case).
We call the sudoku the public input, as it is known by others (like Alice), and the solution the private input, as Bob wants it to remain secret.
Note: here we don’t really care a
