Skip to content

Zero-Knowledge (ZK)

Summary

Ways to prove knowledge of a piece of information without revealing that information. More specifically, the goal is usually to prove knowledge of a witness for some statement in a language without revealing the witness.

Background

First, we define what an NP language is. A language is some set of elements that meet a particular property. For instance, the language \(L_{HAM}\) is the set of graphs which contain a Hamiltonian cycle. A less mathy example might be the set of words which have double-letters ("hello" is in this language because it contains two back-to-back L's, but "world" is not).

Loosely defined, a language is in NP if it is difficult to decide whether an element belongs to a language, but easy to confirm that it is when provided some evidence (called a witness). In the case of \(L_{HAM}\), it's difficult to check if a graph contains a Hamiltonian cycle because finding such a cycle is hard. But if you are given a graph and a supposed cycle in the graph, it's easy to check that the graph really does contain that cycle.

In the case of our less abstract example, think of a computer program that determes whether a word is in the double-letter language: we have to check all the pairs of consecutive letters in the word and see if any of them match. If we are told exactly which two letters repeat and where they are in the word (that is, given the witness ll, 2 for the word "hello"), we can quickly jump to the letter at index 2 in the word and only check that the next two letters both equal l. (This is not a perfect example, since cycling through the entire length of the word doesn't take all that much time, but the point is that the witness simplifies the verification process.)

ZK

Zero-knowledge (ZK) protocols occur between two parties: a prover and a verifier. The prover's goal is to convince the verifier that some statement \(x\) is in some language \(L\), by convincing the verifier that it knows some witness \(w\) for that statement. The verifier's goal is to be sure the prover knows such a witness.

ZK protocols are only interesting if the prover doesn't want to reveal its witness (the zero-knowledge property). (If we didn't care about revealing the witness, the prover could simply send the witness to verifier and we'd be done.)

Example: Where's Waldo? in zero-knowledge

Properties

Completeness
For honest prover P and verifier V, the protocol will accept only on "correct" (true) statements (except with negligible probability).
Honest-verifier zero-knowledge (HVZK)
Non-interactive
No interaction is required; that is, a proof consists of a single message sent by the prover to the verifier (1 round).
Soundness
Intuitively, a cheating (malicious) prover P* cannot (except with negligible probability) provide a valid proof of a false statement.
  • Knowledge Soundness
    This property is stronger than soundness. Intuitively, it says that any valid proof has a corresponding witness. Formally, for any valid proof, there exists an extractor which can extract the witness when given the proof. What does this actually mean? It says that if a prover provides a valid proof, it must have known the witness. In other words, a cheating prover cannot provide a proof of even a true statement if it does not know the witness.
  • Special Soundness
    This lies between soundness and knowledge soundness (?) and applies only to interactive proof systems. Given two (or \(s\), in the case of \(s\)-special soundness) valid transcripts for the same statement and with the same first message, there exists an efficient extractor which can recover the witness corresponding to the statement.
    The "special" part means that this property implies soundness.
  • Simulation Soundness
    This property requires that soundness holds even when P* has seen many simulated proofs (potentially even for false statements), i.e. P* is additionally given an arbitrary number of statement-proof pairs \((x,\pi)\) such that \(V(x,\pi)=1\).
  • Simulation Extractability
    aka simulation-knowledge soundness. A combination of knowledge soundness and simulation soundness, this notion says that knowledge soundness holds even when given access to arbitrarily many simulated proofs. This notion was formulated to capture the notion of non-malleability (which it implies), since knowledge soundness on its own says nothing about the capabilities of a prover that has seen a valid proof to produce a new valid proof by "mauling" the honest proof (malleability). A good discussion can be found in the introduction of [2019/641].
Succinct
  1. the proof size is "small"
  2. verification is "fast"

There is some disagreement on exactly how to define "small" and "fast" in the above: constant, polynomial in the security parameter, polylogarithmic in the statement size, sublinear in the witness? What exactly is meant often depends on the author.

"Small" often means polynomial in the security parameter (\(\lvert \pi \rvert \in \mathrm{poly}(\lambda)\)) or polylogarithmic in the statement size (\(\lvert \pi \rvert \in \mathrm{polylog}(\lvert x \rvert)\)), but could be as general as sublinear in the size of the witness.
"Fast" could mean polylogarithmic in the security parameter and statement size (\(V(x,\pi) \in O(\mathrm{polylog}(\lambda + \lvert x \rvert))\)).

Witness indistinguishable (WI)
Given a proof, the (malicious?) verifier cannot distinguish between which of two valid witnesses was used to generate the proof with more than negligible probability.
Zero-knowledge (ZK)
(With overwhelming probability,) a malicious verifier V* learns nothing about the prover's witness. Formally, there exists a simulator which, given access only to the statement \(x\), can generate a view for V* that is indistinguishable from its view in the real execution. This property comes in computational and information-theoretic variants (depending on the type of indistinguishability of the two transcripts).

Proofs and Arguments

By definition, proof systems are complete and sound. Based on the strength of the soundness, we make a distinction betweeen "arguments" and "proofs":

Argument
Completeness holds perfectly. Soundness holds only against a computationally bounded cheating prover (i.e., computational soundness). For this reason, arguments are sometimes referred to as "computationally sound proofs".
Proof
Completeness holds perfectly. Soundness holds against a computationally unbounded cheating prover (i.e., statistical or even perfect soundness).

Types of zero-knowledge proofs

Zero-knowledge proofs are named in a fairly self-explanatory way by combining their properties into an acronym.

Argument of Knowledge (AoK)
Argument where the (computational) soundness is knowledge soundness.
Properties: completeness, computational knowledge soundness.
Proof of Knowledge (PoK)
Proof where the soundness is knowledge soundness.
Properties: completeness, knowledge soundness.
Probabilistically Checkable Proof (PCP)
Interactive Oracle Proof (IOP)
Sometimes referred to as probabilistically checkable interactive proofs (PCIP), this is an interactive variant of PCPs.
NIWI
Non-Interactive Witness Indistinguishable proof.
Properties: non-interactivity ("NI"), witness indistinguishability ("WI"), completeness and soundness ("proof").
NIZK
Non-Interactive Zero Knowledge proof.
Properties: non-interactivity ("NI"), zero-knowledge ("ZK"), completeness and soundness ("proof").
SNARG/SNArg
Succinct Non-interactive Argument.
Properties: succinctness ("S"), non-interactivity ("N"), completeness and computational soundness ("Arg").
SNARK/SNArK

Succinct Non-interactive Argument of Knowledge.
Properties: succinctness ("S"), non-interactivity ("N"), completeness and knowledge soundness ("ArK").

zk-SNARK
zero-knowledge SNARK.
Properties: the above plus zero-knowledge ("zk").
STARK/STArK
Scalable Transparent Argument of Knowledge.
Properties: Fast verifier and prover time ("S"), transparent/no trusted setup ("T"), completeness and knowledge soundness ("ArK").
DV-NIZK
Designated Verifier NIZK.

Polynomial IOPs

Sigma protocols

A sigma protocol (Σ-protocol) is a 3-round interactive HVZK PoK. Put another way, a sigma-protocol has the following properties:

Any sigma protocol proving that \((x, w)\) is in some relation \(R\) follows the same outline:

  1. Prover P sends a first message \(a\) (the commitment)
  2. Verifier V responds with a uniformly random challenge \(c\)
  3. P uses the challenge to generate a response \(z\)

Lastly, V must output either "accept" or "reject" as a deterministic function of \(x\) and the transcript \((a, c, z)\).

Sigma protocols can be made non-interactive via the Fiat-Shamir transform. They can also be composed in the following ways, so that the languages they operate over are composed:

OR composition
AND composition

Further Reading

"On Σ-protocols" by Ivan Damgård
"Sigma Protocols" slides by Benny Pinkas

Sigma protocol: DLog [Schnorr'89]

Public parameters: Group \(\mathbb{G}\) of prime order \(p\).
Prover: \(y, b \in \mathbb{G}\) and \(x \in \mathbb{Z}_p\).
Verifier: \(y, b \in \mathbb{G}\)
To prove knowledge of the discrete logarithm \(x\) such that \(y = b^x\),

  1. The prover P samples \(r \stackrel{\$}{\gets} \mathbb{Z}_p\) and sends \(a := b^r\) to the verifier V
  2. V sends back a uniform challenge \(c \stackrel{\$}{\gets} \mathbb{Z}_p\)
  3. P sends \(z := r + c \cdot x\)
  4. V checks that \(b^z = a \cdot y^{c}\)

Correctness holds since \(a \cdot y^{c} = (b^r) \cdot (b^x)^{c} = b^{r + x \cdot c}\).

  • HVZK
  • PoK
  • [Cramer'97] generalizes this to knowledge of a homomorphism preimage

Sigma protocol: DDH

Sigma protocol: DLEq [Chaum-Pedersen'92]

Public parameters: Group \(\mathbb{G}\) of prime order \(p\).
Prover: \(y_1,b_1,y_2,b_2 \in \mathbb{G}\) and \(x \in \mathbb{Z}_p\).
Verifier: \(y_1,b_1,y_2,b_2 \in \mathbb{G}\)
To prove equality of the discrete logarithms of \(y_1,y_2\) w.r.t. \(b_1,b_2\), i.e., \(y_1 = b_1^x\) and \(y_2 = b_2^x\):

  1. The prover P samples \(r \stackrel{\$}{\gets} \mathbb{Z}_p\) and sends \(a_1 := b_1^r\), \(a_2 := b_2^r\) to the verifier V
  2. V sends back a uniform challenge \(c \stackrel{\$}{\gets} \mathbb{Z}_p\)
  3. P sends \(z := r + c \cdot x\)
  4. V checks that \(b_1^z = a_1 \cdot y_1^{c}\) and \(b_2^z = a_2 \cdot y_2^{c}\)

Correctness holds since \(a_i \cdot y_i^{c} = (b_i^r) \cdot (b_i^x)^{c} = b_i^{r + x \cdot c}\) for \(i=1,2\) where (crucially) the same \(r,z\) are used.

Sigma protocol: Pedersen opening

Example Protocols

3-coloring [GMW]