(Defining) zero-knowledge proofs

tl;dr: A zero-knowledge proof (ZKP) system for an NP relation $R$ allows a prover, who has a statement $\mathbf{x}$ and a witness $\mathbf{w}$ to convince a verifier, who only has the statement $\mathbf{x}$, that $R(\mathbf{x};\mathbf{w})=1$. Importantly, the proof leaks nothing about the secret witness $\mathbf{w}$. (e.g., a ZKP can be used to convince a verifier that the prover knows the solution $\mathbf{w}$ to a Sudoku puzzle $\mathbf{x}$, without leaking anyhting about the solution!)

Introduction

This blog post formalizes zero-knowledge proof (ZKP) systems, mostly deferring to Groth’s formalization from [Grot16]¹.

For a more mild, high-level introduction to ZKPs via a Sudoku puzzle example, see these slides.

Preliminaries

• We assume familiarity with the NP computational class and its NP relation characterization
• Let $\mathsf{negl}(\cdot )$ denote a negligible function
• We denote NP relations by $R$
• We denote an NP statement by $\mathbf{x}$ and a witness by $\mathbf{w}$
• We often denote $R(\mathbf{x};\mathbf{w})=1$ as $(\mathbf{x},\mathbf{w})\in R$.
• We use $(x||y)\leftarrow (\mathcal{A}||\mathcal{X})(a,b,c)$ to denote that an algorithm $\mathcal{A}$ on input $(a,b,c)$ returns $x$ and another algorithm $\mathcal{X}$ on the same input $(a,b,c)$ returns $y$
• We denote the set of all relations outputted by a relation generator $\mathcal{R}$ by ${\mathcal{R}}_{\lambda }\stackrel{\mathsf{def}}{=}\mathsf{Image}(\mathcal{R})$

Algorithms

A zero-knowledge proof (ZKP) system is a tuple of algorithms:

• a relation generator, used to formalize the fact that the ZKP works for all NP relations
• a setup algorithm, used to generate the proving key and verifying key for an NP relation
• a proving algorithm
• a proof verification algorithm
• a proof simulation algorithm

We describe each algorithm in detail below.

$\mathcal{R}(1^{\lambda })\to (R,\mathsf{aux})$

A relation generator that, given a security parameter $\lambda$ returns a binary relation $R(\mathbf{x};\mathbf{w})$ decidable in polynomial time, together with some auxiliary information $\mathsf{aux}$². The set of all possible binary relations it can output (i.e., its image) is denoted by ${\mathcal{R}}_{\lambda }$.

A recent impossibility result³${}^{,}$⁴ requires that the relation generator be benign. Otherwise, knowledge-soundness cannot be achieved.

Groth points out¹ that for ZKPs built from bilinear groups (e.g., Groth16), it is natural to let the bilinear group be returned via $\mathsf{aux}$.

$\mathsf{ZKP}.\mathsf{Setup}(1^{\lambda },R)\Rightarrow (\mathsf{prk},\mathsf{vk},\mathsf{td})$

Derives a proving key $\mathsf{prk}$ and its associated verifying key $\mathsf{vk}$ from the NP relation $R$. Provers will use the (large) $\mathsf{prk}$ to create proofs. Verifiers will use the (succinct) $\mathsf{vk}$ to verify proof. Also, derives a trapdoor $\mathsf{td}$ (a.k.a., toxic waste) which can be used to simulate (fake) zero-knowledge proofs.

$\mathsf{ZKP}.\mathsf{Prove}(\mathsf{prk},\mathbf{x};\mathbf{w})\Rightarrow \pi$

Computes a zero-knowledge proof $\pi$ for $R(\mathbf{x};\mathbf{w})=1$ using the proving key $\mathsf{prk}$.

$\mathsf{ZKP}.\mathsf{Verify}(\mathsf{vk},\mathbf{x};\pi )\Rightarrow \{0,1\}$

Verifies a zero-knowledge proof $\pi$ against the verifying key $\mathsf{vk}$. The proof argues that the prover knows some witness $\mathbf{w}$ such that $R(\mathbf{x};\mathbf{w})=1$, without leaking any information about $\mathbf{w}$.

$\mathsf{ZKP}.\mathsf{Sim}(\mathsf{td},\mathbf{x})\Rightarrow \pi$

Creates a zero-knowledge proof $\pi$ for $\mathbf{x}$, given only the simulation trapdoor $\mathsf{td}$. This is referred to as simulating a proof [without access to a valid witness]. The simulated proof argues that the prover knows some witness $\mathbf{w}$ such that $R(\mathbf{x};\mathbf{w})=1$, even though the prover does not actually know such a witness; it just has access to the trapdoor $\mathsf{td}$. Importantly, the distribution of simulated proofs is indistinguishable from the distribution of honestly-generated proofs via $\mathsf{ZKP}.\mathsf{Prove}$.

The existence of a $\mathsf{ZKP}.\mathsf{Sim}$ algorithm is actually used to formalize the zero-knowledge property of a ZKP system.

Perfect correctness

Correctness says that any proof $\pi$ returned by $\mathsf{ZKP}.\mathsf{Prove}$ should verify via $\mathsf{ZKP}.\mathsf{Verify}$.

[Perfect correctness]: $\mathrm{\forall }$ security parameters $\lambda \in \mathbb{N}$, $\mathrm{\forall }$ relations $R\in {\mathcal{R}}_{\lambda }$, $\mathrm{\forall }(\mathbf{x},\mathbf{w})\in R$, $$\begin{array}{}\text{(1)}& Pr\left[\begin{array}{}(\mathsf{prk},\mathsf{vk},\cdot )\leftarrow \mathsf{ZKP}.\mathsf{Setup}(1^{\lambda },R),\\ \pi \leftarrow \mathsf{ZKP}.\mathsf{Prove}(\mathsf{prk},\mathbf{x};\mathbf{w}):\\ \mathsf{ZKP}.\mathsf{Verify}(\mathsf{vk},\mathbf{x};\pi )=1\end{array}\right]=1\end{array}$$

The definition above can be relaxed by only requiring that the probability is non-negligible (i.e., $1-\mathsf{negl}(\lambda )$) instead of 1.

Knowledge-soundness

Intuitively, knowledge-soundness says that if a proof verifies for a statment $\mathbf{x}$, then the prover knows a witness $\mathbf{w}$ such that $R(\mathbf{x};\mathbf{w})=1$. One way this is formalized is by saying that, for any adversary $\mathcal{A}$, there exists an extractor ${\mathcal{X}}_{\mathcal{A}}$ (potentially-specialized for $\mathcal{A}$⁵) such that if $\mathcal{A}$ produces a valid proof $\pi$ for $\mathbf{x}$ then the extractor, given $\mathcal{A}$, the statement $\mathbf{x}$ and proof $\pi$ as input, produces a valid witness $\mathbf{w}$. (In fact, the opposite is what is typically formalized: that it is not possible for the adversary to output a valid proof whose witness cannot be extracted.)

[Computational knowledge-soundness]: $\mathrm{\forall }$ security parameters $\lambda \in \mathbb{N}$, $\mathrm{\forall }$ polynomial-time (non-uniform) adversaries $\mathcal{A}$, $\mathrm{\exists }$ a polynomial-time (non-uniform) extractor ${\mathcal{X}}_{\mathcal{A}}$, such that: $$\begin{array}{}\text{(2)}& Pr\left[\begin{array}{}(R,\mathsf{aux})\leftarrow \mathcal{R}(1^{\lambda }),\\ (\mathsf{prk},\mathsf{vk},\cdot )\leftarrow \mathsf{ZKP}.\mathsf{Setup}(1^{\lambda },R),\\ ((\mathbf{x},\pi )||\mathbf{w})\leftarrow \left(\mathcal{A}||{\mathcal{X}}_{\mathcal{A}}\right)(\mathsf{prk},\mathsf{vk},R,\mathsf{aux}):\\ (\mathbf{x},\mathbf{w})\notin R\wedge \mathsf{ZKP}.\mathsf{Verify}(\mathsf{vk},\mathbf{x};\pi )=1\end{array}\right]=\mathsf{negl}(\lambda )\end{array}$$

Recall the $\left(\mathcal{A}||{\mathcal{X}}_{\mathcal{A}}\right)(\mathsf{prk},\mathsf{vk},R,\mathsf{aux})$ notation from the preliminaries.

Describe computational soundness and explain where it suffices.

Zero-knowledge

The notion of a zero-knowledge proof was first proposed by Goldwasser, Micali and Rackoff⁶ and later generalized to any NP language by Goldreich, Micali and Wigderson⁷.

The key idea around defining zero-knowledge is to show that there exists a $\mathsf{ZKP}.\mathsf{Sim}$ algorithm, similar to the $\mathsf{ZKP}.\mathsf{Prove}$ proving algorithm albeit with a bit more power, that can produce proofs with the same statistical distribution for any statement $\mathbf{x}$ but without actually knowing a witness $\mathbf{w}$.

This is formalized by arguing that no adversary can distinguish between proofs produced via $\mathsf{ZKP}.\mathsf{Prove}$ and those produced via $\mathsf{ZKP}.\mathsf{Sim}$.

For the purpose of this blog post, the simulator’s extra power will be that it knows the trapdoor $\mathsf{td}$ behind the proving key $\mathsf{prk}$.

[Perfect zero-knowledge]: $\mathrm{\forall }$ security parameters $\lambda \in \mathbb{N}$, $\mathrm{\forall }(\mathbf{x},\mathbf{w})\in R$, where $(R,\mathsf{aux})\leftarrow \mathcal{R}(1^{\lambda })$, $\mathrm{\forall }$ adversaries $\mathcal{A}$, $$\begin{array}{}\text{(3)}& Pr\left[\begin{array}{}(\mathsf{prk},\mathsf{vk},\mathsf{td})\leftarrow \mathsf{ZKP}.\mathsf{Setup}(1^{\lambda },R),\\ \pi \leftarrow \mathsf{ZKP}.\mathsf{Prove}(\mathsf{prk},\mathbf{x};\mathbf{w}):\\ \mathcal{A}(\mathsf{prk},\mathsf{vk},\mathsf{td},\mathsf{aux},\mathbf{x};\pi )=1\end{array}\right]=Pr\left[\begin{array}{}(\mathsf{prk},\mathsf{vk},\mathsf{td})\leftarrow \mathsf{ZKP}.\mathsf{Setup}(1^{\lambda },R),\\ \pi \leftarrow \mathsf{ZKP}.\mathsf{Sim}(\mathsf{td},\mathbf{x}):\\ \mathcal{A}(\mathsf{prk},\mathsf{vk},\mathsf{td},\mathsf{aux},\mathbf{x};\pi )=1\end{array}\right]\end{array}$$

The adversary is even given the trapdoor $\mathsf{td}$.

The many flavors of zero-knowledge

There are many ways of defining the zero-knowledge property of a ZKP scheme.

• Interactive: Some proof systems are interactive. Their zero-knowledge property is defined in terms of the existence of a simulator who, unlike a dishonest verifier, need not interact with the prover. This gives the simulator a bit more power to forge proofs.
• HVZK + Fiat-Shamir: Some interactive proof systems (e.g., Bulletproofs⁸) satisfy a relaxed version of zero-knowledge, called honest-verifier zero-knowledge (HVZK), where the verifier cannot be malicious and must follow the protocol. Such schemes are then converted to non-interactive ZKP schemes via the Fiat-Shamir (FS)⁹ transform.

---