A primer on Zero-Knowledge Proof Systems in Web3

The term of Zero-Knowledge Proofs was first introduced by MIT researchers Shafi Goldwasser, Silvio Micali and Charles Rackoff when they were working on interactive proof systems. A ZKP system will involve two parties: Prover and Verifier, in which the Prover exchanges messages with the Verifier to convince the Verifier that some statement is true while leaking nothing but the validity of the assertion.

Informally, a generic ZKP protocol, involving to two parties works as follows:

• Peggy, the Prover: Peggy has some information that she wants to prove to Victor, but she doesn’t want to tell the secret itself to Victor.

• Victor, the Verifier: Victor asks Peggy a series of questions, trying to find out if Peggy really knows the secret or not. Victor does not learn anything of the secret itself, even if he would cheat or not adhere to the protocol.

Remark: There are two types of ZKP systems: interactive and non-interactive. The former requires more than one massages exchanged between two parties for a proof, making it suitable for client-server type systems. In the later system, only a single message sent from the Prover to the Verifier, making it suitable for systems where having one Prover and multiple Verifiers, e.g., a cryptocurrency transaction on blockchains. An interactive ZKP system can be converted to a non-interactive ZKP system by using the Fiat-Shamir transformation [2].

(Source: trailofbits.com)

As a real-world example, consider the traditional authentication system with a username and password. Often, the server stores the username and the hash value of the password in its database. Knowing that the password’s hash was generated from an one-way cryptographic hash function such as SHA256. Without knowledge of the input, a.k.a, password, it is infeasible to produce the correct hash. An authorized user in the role of the Prover will interact with the server to prove that he knows his Password that is matching with the hash value stored on the server’s database while leaking nothing to a man-in-the-middle, or the server.

A Formal Definition

Formally, ZKP model of computational is defined as an interactive proof system $(P,V)$, where $P$ is a prover and $V$ is a verifier. Protocol $(P,V)$ is for proving a language membership statement for a language over ${0, 1}$. Let $L$ be a language over ${0,1}^*$, for a membership instance $x \in L$, $P$ and $V$ must share the common input $x$, proof instance is denoted as $(P,V)(x)$.

$P$ and $V$ are linked by a communication channel over which exchange a sequence, called proof transcript $a_1, b_1, a_2, b_2, \ldots, a_n, b_n$. Proof transcript interleaves prover’s transcript and verifier transcript. Each element $a_i, b_i$ exchange is bounded by polynomial time in $|x|$ and proof instance $(P,V)(x)$ must terminate in polynomial time in $|x|$. Upon completing the interaction, the output of the protocol should be of form $(P,V)(x) \in {\mathbf{Accept}, \, \mathbf{Reject}}$ representing $V$’s acceptance or rejection of $P$’s claim that $x \in L$. Note that, an interactive ZKP system can be converted to a non-interactive ZKP system by using the Fiat-Shamir transformation~\cite{Fiat-Shamir-heuristic}.

A zero-knowledge proof must have the following properties:

• Completeness: If the statement is correct, then the verifier will always accept.
• Soundness: If the statement is incorrect, then the verifier will always reject.
• Zero Knowledge: No (malicious) verifier can get any extra information beyond $x \in L$ from the proof procedure, except the correctness of the statement.
• Succinct: This requires both the length of the proof and the verification time are bounded by polylog functions with respect to the size of the circuit $C$ representing $x \in L$~\cite{Kil92}.
• Proof of Knowledge (POK) or Argument of Knowledge (AOK): It would be efficient to extract a witness from an acceptable proof/argument.

Zero Knowledge Proofs in Web3

Bitcoin came out with the pseudonymity of its transactions. No real personal identifiable information rather than a public Bitcoin wallet address is available on the public blockchain. However, this is not enough. Transactions are still be linked and tracked

Recently, ZKP has been attracting lots of attention due to its applications in cryptocurrencies. Zcash implements zk-SNARKs allowing a transaction to be verified its validity without reavealing any details about the transaction itself. Data is concealed using zk-SNARKs and stored to the Zcash network as other cryptocurrencies. Zcash’s proofs are both succinct and non-interactive, meaning that the proofs could be verified without requiring communication between the sender and verifier.

In practice, at least in Web 3, ZKPs are often used differently. Most applications don’t use ZKPs to show ownership of proprietary data. Instead, ZKPs are used to improve trust though verifiability. We expect ZKPs to be the standard trust model between entities in the future. The reason is that the two main components of ZKPs, proving and verification, are separated in a way that enables a unique interaction scheme between a trust-seeking entity and its users.

References

[1] Shafi Goldwasser, Silvio Micali, and Charles Rackoff (1985): The Knowledge Complexity of Interactive Proof-Systems, SIAM Journal on Computing, 18 (1): 186–208.

[2] Amos Fiat, Adi Shamir (1987): How to Prove Yourself: Practical Solutions to Identification and Signature Problems. Advances in Cryptology — CRYPTO’ 86. Lecture Notes in Computer Science. Vol. 263. Springer Berlin Heidelberg. pp. 186–194