Skip to content

Zero knowledge proofs and zk SNARKs

Jump to bottom
Matej Penciak edited this page May 17, 2022 · 5 revisions

Let's consider the following example of a Zero-Knowledge proof protocol:

Suppose Alice has two (very large) graphs G₁ and G₂ that she knows are isomorphic (she has an explicit isomorphism on hand). She wants to convince Bob that they are isomorphic without revealing to him the explicit isomorphism. A zero-knowledge protocol for this program can be described below:

Alice chooses a random permutation of the vertices of G₁, say π, and applies the permutation to yield a graph G' = π(G₁). She sends the graph to Bob.

Bob now chooses a random number: i = 1 or 2, and sends that number to Alice. He expects back from Alice a permutation taking G' to Gᵢ. If Alice did not already know the isomorphism between G₁ and G₂, if Bob makes enough of these demands it would be computationally very hard for Alice to fool Bob with the correct answer each time.

But Alice does know the isomorphism φ : G₁ → G₂! If Bob chooses i = 1, she simply sends π. This exactly satisfies π(G₁) = G'. If Bob chooses i = 2 then Alice sends the the composition π ∘ φ⁻¹. This also satisfies the desired property:

G₂ →[φ⁻¹] G₁ →[π] G'

This protocol can be repeated a number of times with Alice choosing a different permutation π each time, and as long as the number of repetitions is small compared to nᵥ! (nᵥ being the number of vertices of the graphs G₁ and G₂) the risk that Bob can reverse engineer the isomorphism φ is bounded and small.

Of course a "zero knowledge proof protocol" is rigorously defined, and to prove the above constitutes such a protocol we need to establish three facts:

  1. Completeness: Alice can always satisfy the verifier challenge with minimal computation effort on her part
  2. Soundness: If G₁ and G₂ are not actually isomorphic, then Alice may be able to trick Bob, but she would only be able to do so with probability 1/2.
  3. Zero-knowledge: A protocol being zero-knowledge is defined in relation to a third actor, referred to as a simulator. In order to verify this part it is necessary to show that a hypothetical simulator that has been keeping track of the transmissions between Alice and Bob does not gain any computational power. This is treated in more detailed in some of the references below.

Other zero-knowledge proof examples:

  • Schnorr Signatures

    Given n, and x, y ∈ ℤₙ, Schnorr signature protocols allow Alice to convince Bob she can fined some a for which xᵃ ≃ y ⊧ n.

  • Graph 3-coloring

    Given a graph G, Alice wants to convince Bob that she knows a 3-coloring for G without revealing what the exact 3-coloring is.

  • Zero Knowledge Range Proofs

    Alice has some natural number x, and wants to convince Bob it is in some interval range [a, b], without revealing x.

Some good references:

zk-SNARKs

Clone this wiki locally