Interactive and Non-interactive Zero-Knowledge Proofs

Technical Tutorials
Interactive and Non-interactive Zero-Knowledge Proofs https://celo.academy/uploads/default/optimized/2X/c/c6286965e58a2680ca9cf2b176a6d4e0765f3a1d_2_1024x576.png
none 5.0 1
1

SAMPLE (73)
SAMPLE (73)1600×900 414 KB

Introduction

Welcome to this comprehensive tutorial on Interactive and Non-Interactive Zero-Knowledge Proofs. The tutorial is divided into two parts. The first part covers interactive zero-knowledge proofs, which involve a series of back-and-forth communications between the prover and verifier. We will dive into the mathematics and computational aspects of these proofs, explaining how they work and why they’re secure.

The second part of the tutorial deals with non-interactive zero-knowledge proofs. These are a variant of zero-knowledge proofs where the proof consists of a single message from the prover to the verifier, with no need for any interaction. We will discuss how these proofs are constructed and how they maintain the zero-knowledge property.

By the end of this tutorial, you will have a solid understanding of both interactive and non-interactive zero-knowledge proofs, as well as their applications in real-world scenarios.

Interactive Zero-Knowledge Proofs

An interactive zero-knowledge proof involves a series of interactions between the prover and the verifier. Each interaction is called a round. In each round, the verifier sends a challenge to the prover, who then responds with a proof that they know the secret value.

Example - The Ali Baba cave

One of the most famous examples of interactive zero-knowledge proofs is the Ali Baba cave story. In this analogy, the cave is a circular tunnel with a door blocking a narrow part of it. The door can be opened with a secret word. The prover knows the secret word, and wants to prove this to the verifier without revealing the word itself.

Here’s how it works:

  1. The prover goes into the cave and stands at the door.
  2. The verifier stays outside the cave and cannot see the prover.
  3. The prover chooses to go out of the cave from either the same side they went in or the other side (which requires opening the door).
  4. The verifier, without seeing which path the prover took, guesses which side the prover will come out from.
  5. If the verifier’s guess is correct, the game continues. If the verifier’s guess is wrong, then it’s evidence that the prover knows the secret word, as they can choose which side to come out from.

This process is repeated multiple times to increase confidence in the prover’s knowledge.

Key Properties of Interactive Zero-Knowledge Proofs

There are three key properties of interactive zero-knowledge proofs:

  1. Completeness: If the statement is true and both the prover and verifier are honest, the verifier will be convinced of the truth of the statement.
  2. Soundness: If the statement is false, no cheating prover can convince the honest verifier that it is true, except with some small probability.
  3. Zero-Knowledge: If the statement is true, no cheating verifier learns anything other than this fact.

Schnorr Identification Protocol

Let’s understand the mathematicals and computational aspects of interactive zero-knowledge proofs using the Schnorr Identification Protocol as an example. This is a simple and efficient zero-knowledge proof for demonstrating knowledge of a discrete logarithm.

Suppose we have a prover, Alice, who knows a secret value s . Alice wants to prove to a verifier, Bob, that she knows s without revealing its value.

Here’s how the protocol works:

  1. Setup: Alice chooses a large prime number p and a generator g of a multiplicative group mod p. She computes v = g^s mod p and sends (p, g, v) to Bob.
  2. Commitment: Alice chooses a random number r from {1, 2, ..., p-2} and computes x = g^r mod p. She sends x to Bob.
  3. Challenge: Bob chooses a random number e from {1, 2, ..., p-2} and sends e to Alice.
  4. Response: Alice computes y = r + e * s mod (p-1) and sends y to Bob.
  5. Verification: Bob accepts the proof if g^y mod p = x * v^e mod p. This is because if Alice truly knows s, then g^y = g^(r + e * s) = g^r * g^(e * s) = x * v^e.

This protocol is a zero-knowledge proof because Bob cannot learn s from Alice’s responses. Even if Bob chooses e adaptively based on x, he cannot gain any information about s beyond what he could guess without Alice’s help.

Mathematical Properties

The Schnorr Identification Protocol has the following properties:

  1. Completeness: If Alice follows the protocol and knows s, Bob will be convinced that Alice knows s. This is because g^y mod p = g^(r + e * s) mod p = x * v^e mod p, as explained above.
  2. Soundness: If Alice does not know s, she cannot convince Bob that she knows s with a probability significantly greater than guessing. This is because without knowing s, Alice cannot compute y such that g^y mod p = x * v^e mod p.
  3. Zero-knowledge: If Alice knows s, Bob cannot learn anything about s beyond the fact that Alice knows it. This is because all values that Alice sends to Bob are either random or depend on s in a way that is computationally infeasible to reverse.

Computation

The Schnorr Identification Protocol is computationally efficient:

  1. Commitment: Alice’s computation of x = g^r mod p involves a modular exponentiation, which can be computed in O((log p)^3) time using the square-and-multiply algorithm.
  2. Response: Alice’s computation of y = r + e * s mod (p-1) involves a modular addition and multiplication, which can be computed in O(log p) time.
  3. Verification: Bob’s computation of g^y mod p = x * v^e mod p involves two modular exponentiations and a modular multiplication, which can be computed in O((log p)^3) time.

Note that in practice, p would be chosen to be a large prime number (e.g., 2048 bits) to ensure the security of the protocol.

Examples of Interactive Zero-Knowledge Proofs:

  1. Schnorr’s Protocol: The interactive version of Schnorr’s protocol proves knowledge of a discrete logarithm without revealing it. The prover generates a commitment, the verifier sends a random challenge, and the prover sends a response based on the challenge. The verifier can then confirm the validity of the proof without learning the discrete logarithm.
  2. Graph Isomorphism: This protocol proves that two graphs are isomorphic without revealing the isomorphism. In each round of the protocol, the prover creates a new isomorphic copy of one of the graphs, and the verifier challenges the prover to demonstrate an isomorphism between this new graph and one of the original graphs.
  3. Sudoku Solutions: An interactive protocol can prove that a Sudoku puzzle has a solution without revealing the solution itself. The protocol involves a series of commitments, challenges, and responses based on permutations of the puzzle’s rows, columns, and blocks.
  4. Hamiltonian Cycle: This protocol proves the existence of a Hamiltonian cycle in a graph without revealing the cycle. It uses a similar commitment-challenge-response structure to the graph isomorphism protocol.

Non-Interactive Zero-Knowledge Proofs

Non-interactive zero-knowledge proofs (NIZKPs) are a variant of zero-knowledge proofs where no interaction is required between the prover and verifier. Instead, the prover generates a single proof that can convince anyone that they know the secret, without revealing any other information.

Implementing Non-Interactive Zero-Knowledge Proofs

Now, let’s see how to implement non-interactive zero-knowledge proofs. We’ll use the Schnorr’s Identification Protocol, which is a simple and efficient zero-knowledge proof for demonstrating knowledge of a discrete logarithm.

Here’s how it works:

  1. The prover chooses a random secret s and computes v = g^s mod p, where g is a generator of a group of prime order p. The prover wants to prove they know s without revealing it.
  2. To create a non-interactive proof, the prover first chooses a random r and computes x = g^r mod p.
  3. The prover then computes e = H(g, v, x), where H is a cryptographic hash function.
  4. The prover calculates y = r + es mod p - 1.
  5. The prover sends (x, y) as the proof.
  6. The verifier checks the proof by computing e' = H(g, v, g^y * v^e mod p). If e' = e, the proof is accepted. Otherwise, it is rejected.

Here, the prover proves they know s without revealing it, and without any interaction with the verifier.

Mathematical properties

We’ll start with a group G of order p, where p is a prime number, and g is a generator of this group. The prover has a secret s, and he computes v = g^s mod p. The task is to prove knowledge of s without revealing it.

  1. Commitment: The prover selects a random number r from the group and computes x = g^r mod p.
  2. Challenge: Instead of receiving a challenge from the verifier, the prover generates their own challenge. This is done by hashing the commitment and some public information. In our case, e = H(g, v, x), where H is a cryptographic hash function.
  3. Response: The prover computes a response y = r + es mod (p - 1).
  4. Proof: The prover sends the pair (x, y) as the proof of knowledge of the discrete logarithms

Verification of Non-Interactive Zero-Knowledge Proofs

Upon receiving the proof (x, y), the verifier checks it as follows:

  1. The verifier computes e' = H(g, v, g^y * v^e mod p).
  2. If e’ equals e, then the proof is accepted; otherwise, it is rejected.

Computation

Let’s understand how this works computationally using a simplified Python-like pseudocode:

# Prover's side
def prover(g, p, s):
    # Generate a random number r
    r = random.randint(1, p - 1)

    # Compute x = g^r mod p
    x = pow(g, r, p)

    # Compute e = H(g, v, x)
    e = hash((g, pow(g, s, p), x))

    # Compute y = r + es mod (p - 1)
    y = (r + e * s) % (p - 1)

    return (x, y)

# Verifier's side
def verifier(g, p, v, x, y):
    # Compute e' = H(g, v, g^y * v^e mod p)
    e_prime = hash((g, v, pow(g, y, p) * pow(v, e, p) % p))

    # Check if e' equals e
    return e_prime == e

In this pseudocode, hash is a cryptographic hash function, and pow is a function that computes the power with modulo (i.e., pow(a, b, c) computes a^b mod c).

Why does this work

The key to understanding why this works is the mathematical structure of the group and the properties of the hash function. The group operation (multiplication modulo p) and the exponentiation operation have certain properties that make the protocol work:

  1. Exponentiation distributes over multiplication: (g^(a+b) mod p) = (g^a *g^b mod p). This property is used when computing y and checking the proof.
  2. Hash functions are preimage resistant and collision resistant: It’s computationally infeasible to find any input which hashes to a specific output (preimage resistance), or to find any two distinct inputs that hash to the same output (collision resistance). This ensures that the prover can’t cheat by finding a different (x, y) that hashes to the same value.
  3. The prover’s knowledge of s: This is required to compute the response y = r + es mod (p - 1). Without knowing s, it’s computationally infeasible to compute a valid y that passes the verification check.

Examples of Non-Interactive Zero-Knowledge Proofs:

  1. Schnorr’s Protocol (Non-Interactive version): As described earlier in this conversation, Schnorr’s protocol can be transformed into a non-interactive protocol using the Fiat-Shamir heuristic. This protocol proves knowledge of a discrete logarithm without revealing it.
  2. zk-SNARKs , which stands for “Zero-Knowledge Succinct Non-Interactive Argument of Knowledge,” is a type of non-interactive zero-knowledge proof protocol that has become particularly notable due to its use in blockchain and cryptocurrency applications. “Succinct” here means that the proofs are small and quick to verify, which is a valuable property for scalable systems.
  3. Bulletproofs: Bulletproofs are a type of non-interactive zero-knowledge proof protocol that can prove a wide range of statements. They are notable for their short proof lengths and do not require a trusted setup, unlike zk-SNARKs.
  4. STARKs (Scalable Transparent ARguments of Knowledge): STARKs are a type of non-interactive zero-knowledge proof that is transparent (does not require a trusted setup) and scalable (the verification time is much shorter than the time needed to generate the proof). They are being explored for use in scalable blockchain protocols.

Conclusion

Interactive and non-interactive zero-knowledge proofs are both indispensable tools in cryptographic protocols, each providing distinct benefits depending on the scenario.

Interactive zero-knowledge proofs, characterized by a sequence of communication exchanges between the prover and verifier, offer greater flexibility. This flexibility can be advantageous in dynamic environments where conditions might change during the course of proof verification. For example, in real-time gaming or bidding systems, where the ability to respond quickly to changing circumstances is crucial, interactive zero-knowledge proofs may be the preferred choice.

On the other hand, non-interactive zero-knowledge proofs, which require only a single message from the prover to the verifier, offer increased convenience and are especially valuable in asynchronous settings. They do not require both parties to be online at the same time, making them ideal for systems such as blockchain transactions. In blockchain-based systems like Bitcoin and Zcash, non-interactive zero-knowledge proofs are used to verify transactions while preserving the privacy of the users involved.

Both types of zero-knowledge proofs share the essential property of protecting security and privacy. They allow a prover to demonstrate possession of a piece of information without divulging any specific details about it. In an era where data breaches are commonplace, and privacy concerns are increasingly at the forefront of the digital world, understanding and implementing these zero-knowledge proof systems are of immense importance.

I encourage you to continue your exploration of topics on zk proofs. If you’re interested in diving deeper, you can follow up on the pathway here Zero-Knowledge Proofs on the Celo Blockchain: A Comprehensive Tutorial Series - Pathways - Celo Academy

About the author

I’m Jonathan Iheme, A full stack block-chain Developer from Nigeria. With a great passion for Zero Knowledge Technology.

linkedIn
Twitter

7 Likes
2

Hey, this seems to be a proposal but wrongly posted on the tutorials section. Right?

3 Likes
3

yea…slight oversight

3 Likes
4

A good reference for any one who wants to learn about Zero-knowledge proofs.

2 Likes
5

Hi @4undRaiser I noticed path on this piece is quite abberative, Perhaps we can talk mor about it on private chat

3 Likes
6

Good work boss!

2 Likes
7

LinkedIn, please pay attention to brand name