MINA’s Groundbreaking Proof System – the Lightest Chain

MINA’s Groundbreaking Proof System – the Lightest Chain

Limitation of Bitcoin’s design

With proof of work, it detects any tampering immediately, which discourages bad actors form submitting invalid historical transactions. However, they do not provide a rapid evidence of correctness. For the process of verifying correctness, everytime a new participant joins the network, they must check every transaction since the beginning of the network. This requirement and cost to verify the blockchain grows proportionally with total transaction throughput, which has become out of reach for most real-world users on resource constrained devices like smartphones.

To tackle this issue, MINA protocol replaces the blockchain with an easily verifiable proof. Introducing recursive zk-SNARKs, they enable constant-time correctness-verification of a historical ledger. Instead of each participant on the network verifying historical transactions for themselves, the network collaborates to generate proofs-of-correctness for transactions (zk-SNARKs), and then shares those around the network. So instead of end users trusting intermediaries to provide accurate information about the state of the ledger, they are given the state along with a zk-SNARK which cryptographically guarantees that state is accurate.

To put it simply, Bitcoin store hundreds of gigabytes of data, and as time goes on, their blockchains will only increase in size. With MINA however, no matter how much the usage grows, the blockchain always stays the same size – about 22kb (the size of a few tweets). This means participants can quickly sync and verify the network.

About MINA

MINA is the world’s lightest blockchain. It uses advanced cryptography and recursive zk-snarks to design an entire blockchain that is about 22kb. Additionally, instead of using computational brute force, MINA uses a provably-secure proof-of-stake (PoS) consensus protocol for succinct blockchains called Ouroboros Samasika. This is a modification of the peer-reviewed PoS consensus protocol first used in the Cardano blockchain.

What is a zero knowledge proof system?

Figure 1: zero knowledge proof system

1. Alice a has a sudoku puzzle. She sends it to Bob, who has a solution to the puzzle. However, Bob doesn’t want to share his solution.
2. With protocols like PLONK, 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 progra returned ture in this case). The sudoku is the public input, as it is known by others (like Alice), and the solution the private input, as Bob wants it to remain secret.
3. Now, Bob can simply give the proof to Alice, and Alice can verify it with another algorithm called verify. If the verify function returns true, she knows that Bob correctly ran the program verify solution to completion (using her sudoku puzzle and his solution).

What are zkApps on MINA?

Figure 2: zkApps

In MINA, zkApps (zero-knowledge smart contracts) can be written in typescript using the snarky’s library, and then compiled down to some intermediary representation with snarky. The verifier index is uploaded on chain, which allows anyone to verify proofs contained in transactions that claim that they executed a zkApp correctly.

How recursive zero knowledge works contributes to a light blockchain

It makes it possible to prove something without needing to provide any information to support that proof. Imagine a scenario, you have dedicated your whole lives digging for diamonds. After years of digging, you managed to dig up a pile of green diamonds and you want to share it with your friends. Instead of sending diamonds to each of your friends, you would ideally send an image of your diamonds to each of your friends which is much faster.

In cryptographic terms, sending over the massive pile of green diamonds is equivalent to downloading a cryptocurrency blockchain’s transaction history, which is tedious and hard to scale. Contrastingly, sending an image is equivalent to a snapshot of a cryptocurrency’s blockchain transaction history is much more efficient and easier to scale.

MINA protocol uses recursive zero knowledge proofs. Instead of turning every transaction and block into a 22-kb snapshot, each additional transaction and block becomes part of the 22-kb snapshot. This saves space, making the blockchain much lighter and more efficient.

To further enhance your understanding, let’s say you discovered a small, rare red diamond, which is significantly smaller than a pile of diamonds. Hence, a photo of the pile of green diamonds and red diamond will make it difficult for your friends to spot the rare, red diamond. Therefore, a better alternative would be a snapshot of a picture of the green diamonds and a picture of the red diamond. Now, you have one photo as proof to show your friends. This is the core of how recursive zero knowledge proof works: a photo of a set of photos, a proof of a proof of a set of proofs.

About Kimchi – the latest update to MINA

Now, we will focus on Kimchi, which is the latest update to MINA protocol. Kimchi is a compiler that can be used to compile the program as shown in figure 2, into prover and verifier indexes, and both sides can use kimchi provided functionalities to produce proofs as well as verify them. It is a collection of improvements, optimizations, and alterations made on top of PLONK.

Examples of such improvements:

1. Kimchi overcomes the trusted setup limitation of PLONK by using a bulletproof-style polynomial commitment inside of the protocol. Through this, there is no need to trust that the participants of the trusted setup were honest (if they were not, they could break the protocol).
2. Kimchi has added 12 registers to the 3 registers PLONK already had (figure 3). More registers equates to gates that can take multiple inputs instead of just one as shown in figure 4. This leads to new opportunities. For example, a scalar multiplication gate would require at least three inputs (a scalar, and two coordinates for the curve point).
3. Another performance improvement implemented in Kimchi are lookups. Kimchi builds a table to simply perform a lookup into the table to fetch the result of the operation.

To sum up: Kimchi brings several optimizations and quality-of-life improvements to circuit builders. This should allow for faster provers, larger circuits, and potentially shorter proof sizes!

Figure 3: Registers

Figure 4: Gates that take multiple inputs