Main Concept Behind Zero-Knowledge Proof

    2024, Jun 17

    This article is a summary of the main concepts behind Zero-Knowledge Proof (ZKP).

    Zero knowledge proofs are increasingly present in the blockchain ecosystem.

    • They are used either to improve privacy, by the fact that they allow a statement to be proven without revealing any additional information about the data behind the statement
    • Or to improve scalability/performance, for example with Ethereum layer2 (StarkNet, ZKsync, Polygon zkEVM)

    In a Zero knowledge system, there are three main “actors”:

    1. Prover: The entity in a ZKP protocol that generates the proof to convince the verifier of the statement’s truth.
    2. Verifier: The entity in a ZKP protocol that validates the proof provided by the prover.
    3. Statement: The assertion or proposition that the prover aims to prove to the verifier.

    The following properties represent the base of a zero-kwnoledge system:

    1. Completeness: This property defines that if the statement is true, an honest prover can convince an honest verifier of this fact.

    2. Soundness: This property defines that if the statement is false, no dishonest prover can convince the honest verifier that it is true with a sufficiently high probability.

    3. Zero-Knowledge: This property defines that the verifier learns nothing other than the fact that the statement is true; no additional information is revealed.

    [TOC]

    Basic concepts

    Zero-Knowledge Proof (ZKP)

    A cryptographic method that allows a prover to demonstrate the truth of a statement to a verifier without revealing any additional information.

    Example:

    • proving that a number n is of the form of the product of two prime number
    • Proving that one knows p,q such that n=pq
    • Proving that one knows x such gx mod p = y

    Reference: purdue.edu - Topic 23: Zero-Knowledge Proof and Cryptographic Commitment

    Main components

    There are the three main components:

    1. Prover: The entity in a ZKP protocol that generates the proof to convince the verifier of the statement’s truth.
    2. Verifier: The entity in a ZKP protocol that validates the proof provided by the prover.
    3. Statement: The assertion or proposition that the prover aims to prove to the verifier.

    zero-knowledge-proof.drawio

    Security Properties

    Main properties

    For our example, we take L – some language (usually not in P)

    These properties are the base of all zero-knowledge system

    1.Completeness: This property defines that if the statement is true, an honest prover can convince an honest verifier of this fact.

    If x ∈ L, then the probability that (P, V) rejects x is negligible in the length of x.

    2.Soundness: This property defines that if the statement is false, no dishonest prover can convince the honest verifier that it is true with a sufficiently high probability.

    A cheating prover cannot convince the verifier that x ∈ L if it is not true, except with some probability

    3.Zero-Knowledge: This property defines that the verifier learns nothing other than the fact that the statement is true; no additional information is revealed.

    The only thing that the verifier learns is that x ∈ L

    Reference: mimuw.edu.pl - Commitment Schemes and Zero‐Knowledge Protocols

    Others propreties

    1. Extractor/Extractability: This property defines that if a prover can convince a verifier of a statement, it is possible to extract the witness (the secret knowledge proving the statement). It concerns zero-knowledge proofs of knowledge which are zero-knowledge proofs which additionally guarantee that the prover indeed holds the witness.
    2. Simulator/Simulability: To prove the zero-knowledge property, here the concept of simulator: A

    A simulator gives the same probability distribution of the view of the interaction without invoking the prover. Contrary to the prover, the simulator has only access to public information and can not leak any information because it doesn’t have the witness.

    1. S is generally defined as follwing:
    • S is a probabilistic (expected) polynomial time algorithm.
    • It can interact with the Verifier V , but does not have access to its private randomness.

    Example:

    Upon receiving an input string x, Prover (P) and Verifier (V) pass a series of message strings a1, . . . , am, through which P attempts to convince V whether x is in the language L.

    Given any verifier V , and an honest prover P, there is some simulator S if x ∈ L, then the distribution of S(x) is indistinguishable from the interaction transcript a1, a2, . . . , am between P and V .

    References:

    Efficiency

    1. Efficiency: The measure of computational resources (time, space) required to generate and verify the proof, crucial for practical implementation.
    2. Succinctness: A feature of some ZKPs where the size of the proof is very small compared to the size of the statement or the witness, i.e., the size of the computation itself.
    3. Used in ZK-SNARKs and ZK-STARKs

    Types of Zero-Knowledge Proofs

    Interactive Zero-Knowledge Proofs

    ZKP protocols that require back-and-forth communication between the prover and verifier. This generally involved three steps:

    • The Prover sends a message (commitment) to the Verifier
    • The Verifier returns to the prover a challenge to resolve.
    • The Prover then responds to the challenge with the proof of the challenge

    Interactive ZKP is not suitable for blockchains since you can not verify the proof independently.

    Reference: hacken - Zero-Knowledge Proof – How It Works

    NIZK

    Protocols that do not require back-and-forth interaction between the prover and verifier after an initial setup phase.

    In this category, we have:

    1. zk-SNARKs (Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge): A type of NIZK with very short proofs and quick verification times, widely used in blockchain technologies.
    2. zk-STARKs (Zero-Knowledge Scalable Transparent Arguments of Knowledge): A type of zero-knowledge proof that does not rely on trusted setup and offers scalability and transparency.

    Here several concepts related to NIKZ:

    • The algorithm Fiat-Shamir is used to turn an interactive protocol to its non-interactive version.
    • Public Parameters: Values or settings known to both the prover and verifier, essential for running the ZKP protocol, used in NIZK. With zk-snark, these paramters are typically the proving key pk, and athe verification key vk.
    • A trusted setup ceremony is a ceremony between multiple participants using multi-party computation between users who are believed not to collude. In principle, this kind of ceremony required only one honest participant to create valid parameters.
    • The Common reference string (CSR) is a string shared between the verifier and prover, this string is generally generated during the trusted setup ceremony.

    Reference: Panther - Understanding Trusted Setups: A Guide, zk-SNARKs: A Gentle Introduction, ZK FAQ: What’s a trusted setup? What’s a Structured Reference String? What’s toxic waste?

    References

    Academic course & paper

    Other

    Feel free to contact me on
    # zeroknowledge # zkp

    Share button

    You might also enjoy

    Hypergraph and Hypertree - Overview

    Tornado Cash Circuits - Overview

    Recurrent Neural Networks (RNNs) - Overview