The Intersection of Zero-knowledge Proofs and Verifiable Computing

Table of Links

Abstract & Introduction

Preliminaries

Zero-knowledge proofs and verifiable computing

Privacy-preserving computations

Requirements: an application’s perspective

Verifiable, privacy-preserving computing

Open challenges and future directions

Conclusion & References

3. Zero-knowledge proofs and verifiable computing

A zero-knowledge proof allows parties to prove correctness of a certain statement (i.e., claim), whilst hiding all related private information [17]. This is useful in circumstances where correctness of a claim is not evident, but the prover does hold private information that is sufficient to provide a proof of correctness.

Examples of ZKP use cases include proving adulthood without revealing birth data related information, proving that one has access to a building without revealing identity, or proving knowledge of the pre-image of a hash value.

3.1. Terminology

We follow the terminology as defined in [18] and use proving adulthood as a running example:

• Instance: Input that is commonly known — often publicly available information — to both prover and verifier, and is used to define the statement that needs to be proven. Commonly denoted as x. (Example: Tamperproof ID-chip.)

• Witness: Input that is only known to the prover. Commonly denoted as w. (Example: Birthdate and ID-data.)

• Relation: Condition that determines the validity of an instance-witness pair. Denoted as R. (Example: Birthdate on ID-chip is at least 18 years ago.)

• Language: The set of all instances x, for which a valid witness w exists with respect to R: {x : ∃w : (x, w) ∈ R}. Denoted as L. (Example: All ID-chips with birthdate at least 18 years ago.)

• Statement: Claims that an instance x belongs to a language L: x ∈ L. Alternatively, ∃w : (x, w) ∈ R. (Example: I am an adult.) We note that some authors use the terms “instance” and “statement” interchangeably.

A ZKP system should satisfy at least the following (informal) requirements:

• Complete: An honest prover should be able to convince the verifier of the validity of any true statement.

• Sound: A prover should not be able to convince the verifier of the validity of a false statement.

• Zero-knowledge: Given a true statement, the protocol should not reveal any other information than the validity of a statement to the verifier, as long as the prover follows the protocol. In particular, no information should be leaked regarding the witness.

The output of a ZKP protocol can be either a proof or an argument. Where a proof needs to be sound against any computationally unbounded prover, an argument needs to be sound only against computationally bounded provers. In most literature, the term proof is used to denote both proofs and arguments. We follow this convention.

Based on the type of claim and the type of soundness provided by the scheme, we distinguish two types of a ZKP scheme:

• A zero-knowledge proof of membership proves only that a statement x ∈ L is true, i.e., that there exists a witness w such that the instance x is part of L.

• A zero-knowledge proof of knowledge (ZKPoK) not only proves that there exists such a witness w, but also that the prover knows w.

Any zero-knowledge proof of knowledge (ZKPoK) has to satisfy a stronger notion of soundness known as knowledge soundness: A prover that does not know the witness to a statement should not be able to convince the verifier of knowing a valid witness for this statement. Following common convention, we will use ZKP to also denote ZKPoK, and be specific when necessary.

3.2. Concrete NIZK schemes

Initially, most ZKP schemes were solutions for specific problems, mostly in the form of Σ-protocols, e.g., Schnorr’s protocol [19]. The downside of these schemes is that they provide no solution for generic computations, and that verification time and proof size scale linearly (or worse) with respect to the computation size.

Moreover, they are interactive and require an honest verifier. On the plus side, these schemes can be made non-interactive using the Fiat-Shamir (FS) heuristic [20], implying public verifiability and security against malicious verifiers. Because of the downsides of interactive ZKPs, we will narrow our focus to non-interactive zero-knowledge proofs (NIZKs).

A NIZK scheme is generally described by three (probabilistic) polynomial-time algorithms (Setup,Prove, Verify). In general, these algorithms are defined and used as follows:

• Setup(1κ ,params) → (ppR,ppP ,ppV ,aux): Takes as input a security parameter κ and additional scheme specific input params. It produces public parameters for the prover ppP and the verifier ppV . In case the setup is dependent on the input relation R, we put the corresponding parameters in ppR. Additional setup parameters are returned in aux;

• Prove(ppP , x, w) → π: The prover takes as input the proof parameters ppP and an instance-witness pair (x, w) ∈ R and returns a proof π;

• Verify(ppV , x, π)− > {0, 1}: The verification algorithm takes as input the verification parameters ppV , instance x, and proof π and returns 0 (reject) or 1 (accept).

The introduction of Pinocchio [21] as the first succinct ZKP or zero-knowledge succinct non-interactive argument of knowledge (zk-SNARK) gave the first scheme without the earlier mentioned drawbacks. Moreover, it also allowed for verification of any computation that can be described as an arithmetic circuit, i.e., it supports verifiable computing. Pinocchio was followed by many schemes with lower prover or verification time and smaller proof sizes. Groth16 [22], Marlin [23], and PLONK [24] are examples of popular schemes with publicly available implementations.

Another line of efficient NIZKs was started with the introduction of Bulletproofs [25]. More recently, the efficient construction used for Bulletproofs has been applied to create Σ-bullets [26], or compressed Σ-protocol theory [27]. These latter protocols can be used to construct zero-knowledge proofs for arithmetic circuits from standard security assumptions, which is not the case for zk-SNARKs, at the cost of an increased proof size and verification time.

For a more extensive and up-to-date overview of ZKP schemes we refer the reader to, e.g., [28], [29].