Building zk-SNARKs (volume 1)

Basic concepts and properties

The author thanks Benjamin Lehman and Unsplash for the image

Introduction

Welcome to this guide on how to build zk-SNARKs! Zero-Knowledge Succinct Non-Interactive Argument of Knowledge (zk-SNARK) is a cutting-edge technology that provides privacy and security in blockchain systems. It allows for verifying the authenticity of transactions without revealing the details. In this guide, we present an overview of zk-SNARKs, their applications, and how to build them.

You will also learn about the mathematical background behind zk-SNARKs. For example, you’ll learn how to generate the Quadratic Arithmetic Program (QAP) associated with an arithmetic circuit. The QAP is the central object used in zk-SNARKs, and its generation is a crucial step in building a zk-SNARK.

To understand the mathematical concepts behind zk-SNARKs you will need a strong background in algebra, particularly fields and groups.

Throughout this series of 3 Medium articles, we will also explain the steps to generate a QAP, including representing an arithmetic circuit as a system of linear equations, converting the linear system to a polynomial system, and transforming the polynomial system into a QAP.

We hope this guide will help you acquire a solid understanding of zk-SNARKs and the skills necessary to generate QAPs by hand. This guide provides the knowledge and tools necessary to build your own zk-SNARKs and contribute to developing this exciting field.

We plan to publish a collection of 3 Medium articles that we hope will help you understand this concept. To be precise:

1. Post 1: The one that you are reading. Here we will only set the main definitions and properties: what is a SNARK and what are the requirements for a SNARK. It will be short and easy to read, consider it a warm-up for what comes next.
2. Post 2: Here you will be assumed to know the basics (definitions and properties) of SNARKs, and will learn how to build a SNARK to prove knowledge of a polynomial. We will do it step by step departing from something that is not a proper SNARK and ending in a full zk-SNARK. The post will be longer, and maybe harder to follow, but we planned it to be easy to understand.
3. Post 3: In post 3 you will be assumed to be able to create SNARKs for polynomials, and will be eager to learn how to build SNARKs for any computation. Here you’ll learn how to do so. Post 3 is focused on QAPs and, in a subliminal way, R1CSs. Not as long as Post 2.

Definitions

A SNARK (Succinct Non-interactive Argument of Knowledge) is a cryptographic protocol between two users where a prover (P) proves to a verifier (V) that a computation C is correct. The computation is represented by a circuit and the circuit receives two inputs: a private value called witness (w), and a public value (x). The computation is considered correct if the output C(x, w) is equal to a known value y.

More formally, a SNARK is a set of three algorithms: Generation, Proof, and Verification, which all run in polynomial time, such that:

• The generation algorithm (Gen), takes as inputs the circuit C and a security parameter n. It returns a set of two keys, the proving key (pk) and the verification key (vk),
• The proving algorithm (Proof), takes as inputs the proving key pk associated with C, a public input x and returns a proof π.
• The verification algorithm (Ver) takes as inputs the proof π, the verification key vk associated with C, and the public input x. It returns either True or False depending on the results of the validation process.

Properties of SNARKs

We need that the following properties are satisfied by any SNARK:

• Correctness: An honest prover P will always generate vk and π such that Ver(π, vk, x) = 1 for values x and w satisfying the circuit C. In other words, if P is honest then the algorithms will always output valid proofs.
• Robustness: A malicious prover P providing values for x and w which do not satisfy C has a negligible probability of generating a proof π such that Ver(π, vk, x) = 1. In other words, if P is not able to run the computations described by C, it will not convince the verifier V with overwhelming probability.
• Efficiency: the size of π is bounded by a polynomial over the security parameter n used in Gen. This is the key property of succinctness.

If we also want to generate a zero-knowledge SNARK, we need one more property:

• Zero-knowledge: The verifier V is unable to obtain any further detail beyond the output of the verification algorithm Ver.

Conclusion

This is the end of our first post, where we focused only on the basic concepts and properties. As we said in the introduction, it is just a warm-up for what comes next: zkSNARKS for polynomials.