Summary

This blog provides a high-level description of what cryptographic proofs are and what they can do. We dive into applications and use cases powered by cryptographic proofs that exist today. We introduce different types and forms of proof systems and discuss important tradeoffs.

A Principle to Convince Someone

Cryptographic proofs can be used by a party, called the prover, to convince another party, called the verifier, of a computational expression or statement. The caveat of cryptographic proofs is that the party acting as the verifier does not need to re-execute the computation that is proven. Instead, the verifier is convinced of the proven fact if the proof verification succeeds.

alibabacave 100 centered Figure 1: Alibaba cave where a prover convinces a verifier of owning a key that opens a door in the back of the cave.

To illustrate a cryptographic proof with an analogy, we consider the well-known example of Alibaba's cave (cf. Figure 1). In this example, the prover tries to convince the verifier of the statement "I own the key to the back door of the cave". Here, the prover commits to a path by entering the cave and, in our example, selects path A. The verifier cannot see which path the prover selected but has the opportunity to call out the prover via a randomly chosen path. In our example, the verifier calls out the prover via path B. If the prover appears at path B, the verifier is happy and builds up an initial confidence that the prover might actually possess the key to the cave's back door. If the prover does not appear via the called out path, then the verifier remains unsettled and aborts the game.

Notice that the prover has a $\frac{1}{2}$ or 50% chance of correctly guessing the random choice of the verifier. This likelihood of $\frac{1}{2}$ is quite low and would allow a malicious prover without the key to the cave's back door to build up an initial confidence in convincing the verifier. To prevent a malicious prover from falsely convincing the verifier, both parties play the same game over and over again. After running the same game $n$ times, the prover has a change of $\frac{1}{2^{n}}$ in convincing the verifier. If $n$ is large, then convincing the verifier without possessing the key to the cave's back door becomes impossible. Cryptographic proofs leverage this principle of challenging a prover in a game, where convincing the verifier becomes impossible if the prover does not satisfy the statement. In other words, a cryptographic proof only convinces the verifier if the prover satisfies the fact expressed by the statement.

In the next section, we show how the principles to convince someone can be implemented by computers that run the math.

Cryptographic Proofs

We explain cryptographic proofs by taking the Schnorr Proof of Knowledge of Discrete Log as an example. This Schnorr protocol was first proposed in the research paper [1] and proven secure in the paper [2]. You can find a sample implementation on the asecuritysite website. Before we show the protocol, we explain the following notations:

We need a natural number $n \in \mathbb{N}$ and define the ring of integers $\mathbb{Z}_n$ modulo $n$. This means $\mathbb{Z}_n$ is the set of numbers {1, ..., n}.
Next, we need parameters of a Key Authentication Center (KAC) which will allow us to generate a private and public key. The first parameters are prime numbers $p,q$, where $q$ divides $p-1$ (also noted as $q|p-1$) and $q$ has at least 140 bits and $p$ has at least 512 bits (also noted as $q\geq 2^{140}$, $p\geq 2^{512}$, $t\geq 2^{72}$).
Next, we sample a generator element $g\in\mathbb{Z}_p$ with order $q$ such that $g^{q}$=1 (mod $p$) and $g\neq1$ hold. To pick $g$, check this resource.
Next, we consider a hash function $h$: $\mathbb{Z}_q\times\mathbb{Z} \rightarrow$ {1, ..., $2^{t}-1$} mapping the numbers of the groups $\mathbb{Z}_q$ and $\mathbb{Z}$ to the set of numbers {1, ..., $2^{t}-1$}.
With this scheme, the values $q,p,g,h$ can be disclosed.
Now, we can define a private key as $x \xleftarrow[]{r} \mathbb{Z}_q$ which is randomly sampled from the set {1, 2, ..., $q$}. The corresponding public key is computed as $\text{X}$=$g^{-x}$ (mod $p$).
Important: Notice that, without access to $x$, computing the inverse of the public key via the discrete logarithm with the base $g$ as $x$=$-\text{log}_{g}(\text{X})$ is a hard problem which is assumed to be infeasible.

schnorrpokdl 75 centered Figure 2: Interactive Schnorr Proof of Knowledge of Discrete Log. The prover convinces the verifier of knowing a secret $x$ as the discrete logarithm of $\text{X}\in\mathbb{Z}_p$ with the base $g$.

Now we look at the cryptographic proof, where the prover convinces the verifier of the statement "I know the private key that corresponds to the public key". To do so, both parties execute an interactive protocol (cf. Figure 2). The private key is referred to as the witness which the prover must possess in order to convince the verifier. The security of a cryptographic proof depends on following properties which have to be shown for every proof system:

Completeness ensures that an honest prover can convince an honest verifier if the prover knows a valid witness. Completeness of the Schnorr proof of knowledge of discrete log is guaranteed by the equation $g^{z}$=$g^{cx+y}$=$g^{y}g^{xc}$=$\text{Y}g^{xc}$. Now if we multiply the equation by $g^{-xc}$, then the following relation holds $\text{Y}$=$g^{z}g^{-xc}$=$g^{z}\text{X}^{c}$ which is checked by the verifier.
Soundness ensures that a cheating pover without access to the valid witness cannot convince a verifier. To show soundness in a proof protocol, the verifier is theoretically assumed obtain two accepting conversations ($\text{Y}$, $c$, $z$) and ($\text{Y}$, $c'$, $z'$). This means that the verifier runs the protocol twice with different challenges $c\neq c'$ and the prover uses the same parameters. In reality, this case should never happen as it would allow the verifier to learn the witness. With two accepting conversations, the verifier runs an witness extracting algorithm which takes $\text{Y}$=$g^{z}\text{X}^{c}$ and $\text{Y}$=$g^{z'}\text{X}^{c'}$ to compute $g^{z-z'}$=$\text{X}^{c'-c}$. With that, it is possible to extract the witness by computing $-x$=$\frac{z-z'}{c'-c}\text{ (mod }q\text{)}$=$\text{log}_g(X)$. This concept convinces the verifier that an actual witness and, with that, a satisfying solution for the proven statement exists.
Honest Verifier Zero-knowledge (HVZK) ensures that an semi-honest verifier (follows the protocol specification and performs passive attacks only) does not learn anything beyond the statement validity. HVZK is verified with the help of a simulator concept. The simulator is supposed to take the role of the verifier and simulates an ideal transcript of the proof protocol $T_{\text{sim}}$=($x$, $c$, $z$). To do so, the simulator randomly samples $z, c\xleftarrow[]{r}\mathbb{Z}q$ and computes $x$=$\frac{g^z}{X^c}$. If, in the eyes of an adversary, the simulated transcript is statistically indistinguishable from the real protocol transcript $T_{\text{real}}$, then HVZK holds.
Zero-knowledge (ZK) ensures that a cheating verifier cannot learn anything beyond the statement validity which is proven by the prover. The Schnorr proof protocol can be made zero-knowledge by applying the Fiat-Shamir heuristic. The Fiat-Shamir heuristic turns the interactive proof protocol into a non-interactive protocol because the prover computes the random challenge $c$=$h(\text{Y})$ locally. The simulator computes an $c$=$h(T)$ by hashing the transcript.

Types of Proof Systems

The above depicted proof system is dedicated to proving a single statement, which is knowledge of the discrete log computation. Luckily, the evolution of cryptography research has led to general-purpose proof systems which allow the computation of arbitrary statements. In this case, proof systems consist of different components which we outline next:

Arithmetic circuit representations of computation, which can be satisfied by a system of equations.
(Quadratic) Arithmetic program, which turns the circuit into a system of equations over polynomials. This is typically used to express the completeness equation of the proof system.
Functional commitment scheme, which is a cryptographic object (can be instantiated using cryptographic algorithms) that decouples the evaluation of the completeness equation between the prover and the verifier.
Compatible interactive oracle proof (IOP), which is an information theoretic protocol that defines how the prover and verifier evaluate and exchange messages.

In the following, we categorize different functional commitment schemes and mention how they can be instantiated. Commitment schemes can be differentiated based on the structure they commit to as shown here. This means there exist:

Polynomial commitments
Multilinear commitments
Vector commitments (e.g. Merkle Tree)
Inner product commitments (inner product arguments - IPAs), which can be instantiated transparently as done in the bulletproofs paper. For example, the polynomial commitment scheme can be instantiated with the KZG algorithm which makes use of bilinear groups. This algorithm requires a trusted setup, where a trusted external party is supposed to honestly generate, encrypt, and delete randomness. If the trusted external party misbehaves, it could use the secret randomness to attack soundness of the proof system. The gnark framework lets you instantiate Gorth16 proofs with KZG commitments. Bulletproofs rely on IPAs that are instantiated with elliptic curve cryptography (making use of the discrete log assumption) and, hence, do not require a trusted setup assumption. Another alternative to create transparent proofs is by using hash functions to create vector commitments via Merkle Trees.

IOPs can be categorized based on the powers of the verifier, as shown here. Hence, a system can have:

Oracle access, where the verifier may query provers messages.
Randomness, where the verifier is probabilistic
Interaction, where the verifier and prover exchange messages
Multi-prover, where multiple provers exist but remain isolated

The combination of the IOP and polynomial commitment scheme yields multiple interesting constructions of proof systems with key properties. In the following, we mention popular types of proof systems with a key property:

zkSNARK, where succinctness guarantees short proofs that are fast to verify. Here, fast means that the verifier computation complexity is sub-linear in the size of the witness. In other words, the verifier can verify a proof faster than evaluating the circuit with witness access.
zkSTARK, where transparent guarantees that the proof system does not requires a trusted setup
MPC-based ZKPs achieve efficient prove computations for non-algebraic statements
Recursive ZKPs, which allow proving of proofs
zkVMs are a virtual machines that execute programs (e.g. zkEVM for Ethereum smart contract transactions) while verifying cryptographic proofs

If you want to learn how different types commitment schemes and compatible IOPs work together, please check out the related works Section 3.2 of the resource [3].

Applications

With the technology of cryptographic proofs and their unique combination of interesting properties, novel online application fields emerge. Before we mention some applications, lets take a look at the high-level properties that proof systems achieve:

Confidentiality which holds inputs that are kept private during a proof verification. Private inputs are called witness and never leave the prover.
Credibility which ensures that the integrity of a computation statement is kept.
Compression (if succinctness holds) which optimizes the computation cost at the verifier.

Today's applications that benefit from these properties are:

Credential systems that equip online accounts with new privacy features.
Blockchain scalability solutions in the form of zkRollups which leverage the compression feature.
Authentication systems which inherit trust by presenting cryptographic proofs.
Content provenance systems which ensure the correct origin of a digital resource.

More applications can be found by checking this resource.

Upcoming Blogs

We will publish a blog on how to compute and verify cryptographic proofs in a setting with two online parties as well as a setting with a client and a blockchain smart contract which takes over the verification of the proof.

Resources:

If you spot any errors or inconsistencies, feel free to report it and contact us here. We highly appreciate your help!

Cryptographic Proofs

Created at 01.07.2024 by jp

Tags

Download as