19 Proving knowledge and keeping secrets: Zero knowledge using pairings
This chapter covers
- Description of zero-knowledge proofs
- Constructing quadratic arithmetic programs
- Using common reference strings for proofs
In this chapter, I’ll get to the edge of cryptographic protocol research by explaining zk-SNARKs. Because this is an active area of research, I’ll use a very popular paper, which has over 1,200 citations to explain the concepts. This is complicated, so get a beer and relax. I had to read many SNARK papers a dozen times, so, hopefully, it will only take you a few times through this chapter to understand the ideas.
The chapter starts with a definition of interactive zero knowledge using Ali Baba’s cave. Then I’ll explain noninteractive zero knowledge and quadratic arithmetic programs. From there, I’ll explain the idea of a common reference string, followed by the SNARK mathematics.
19.1 SNARK defined
First, let’s look at the origin of the word snark. Sometime around 1875, Lewis Carroll wrote in "The Hunting of the Snark":
- They sought it with thimbles, they sought it with care;
- They pursued it with forks and hope;
- They threatened its life with a railway-share;
- They charmed it with smiles and soap.
- And the Banker, inspired with a courage so new
- It was matter for general remark,
- Rushed madly ahead and was lost to their view
- In his zeal to discover the Snark.