Why is Mina so tasty ? part 1 : Kimchi

This post explores the zero knowledge proof system that Mina uses to create zkSNARKS, I do assume some knowledge of zero knowledge proofs, if this area is new to you, please read some of our introductory articles such as
A gentle introduction to zero knowledge proofs, or our guide to using Zokrates. I have tried to explain the concepts here with using mathematical formulae.

Mina have a proof system that creates recursive proofs called Pickles, which relies on a protocol called Kimchi to produce the proofs, it is Kimchi that we will look at in this post.

For their proving systems Mina has built upon a family of protocols such as PLONK, SONIC and Marlin which have ‘knowledge of exponent’ as an underlying cryptographic assumption.

Cryptographic assumptions

Most cryptographic systems rely on a security assumption, that is something that is thought to be unfeasible in practice, such as finding a hash collision, or the discrete log in a group. For the family of proof systems that PLONK belongs to, we rely on the knowledge of exponent assumption.

These protocols have improved upon earlier protocols such as Groth16 to give improved performance (though not in all aspects as we shall see) and more flexibility around making changes to the system after the trusted setup has been completed. Let’s start by looking at PLONK.

PLONK

PLONK stands for Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge ( a backronym I suspect)

Where PLONK made our lives easier is in how the trusted setup can be used.

Our system starts with a program that tests the claim we are trying to prove, such as “I know the square root of 25” or “The inputs and. outputs in this transaction are valid”

Earlier protocols required that any change to the program we used would require a new trusted setup.

Trusted setups and related ceremonies may be fun and help build a community, but we don’t want to repeat them too often.

With PLONK the same trusted setup could be used even if we make changes (within limits) to our program. This setup is then referred to as a universal setup, the values (curve points etc.) needed in the setup are called the universal ( since it applies to many programs) structured reference string.