In this series of posts, we will look at zero-knowledge proofs (ZKPs): a family of probabilistic protocols, first described by Goldwasser, Micali and Rackoff in 1985, which has garnered increased popularity with the rise of distributed ledger technology (DLT). We will start by introducing some of the theory behind this groundbreaking work and showing how to implement the different components of its intricate machinery. Eventually, this will result in an end-to-end zero-knowledge proof for a toy problem, following the Pinocchio protocol and implemented in Python. The main goal is to provide a gentle introduction to the topic, breaking down the terse mathematics involved in ZKPs and discussing some of the intuition behind it. Along the way, we will also touch on some of the exciting applications, enabled by this technology.
So, what is a ZKP and why should you care?
A ZKP allows a prover, let’s call her Peggy, to demonstrate beyond any reasonable doubt to a verifier, let’s call him Victor, that she knows some secret without revealing what the secret is. For example, Peggy might want to prove to Victor that she knows the factorization of a very large non-prime number without revealing the factors; or that she knows the solution to a given Sudoku puzzle without revealing it. More generally, ZKPs can be used as the building blocks for verifiable computation: a method of offloading computation from a weak client to a more computationally powerful worker, which enables the client to cryptographically verify the correctness of the computation that was carried out by the worker with a much smaller computational effort compared to executing the original program. This is an extremely powerful paradigm, which affects online privacy, scalability of DLT and mobile phone applications, as well as the security of cloud computing, among many other applications.
Another very promising application of ZKPs lies in the field of mac...