This is the first post in a series of ZK-related research blogs from the Chainlink Labs Research Team.

Author: Xiao Wang
Contributors: Lorenz Breidenbach, Alex Coventry, Siam Hussain, Dahlia Malkhi, Alexandru Topliceanu, Chenkai Weng, Fan Zhang

Preamble

Zero-knowledge proofs (“ZKP”) have received much attention in the blockchain world. The main focus has been committing transactions to publicly on-chain with succinctness and/or privacy. Generally, this use case requires verification by anyone at any time; hence, ZKPs in this case must be non-interactive.

There is another type of zero-knowledge proofs, interactive proofs (“IR-ZKP”), which are uniquely suited for the oracle technology domain. Briefly, oracles form a decentralized off-chain network that coordinates tasks by consensus. Oracles can help decentralize proof systems off-chain with minimized trust. That is, each oracle can independently carry out a certain proof task, and then oracles coordinate an attestation output as a group, avoiding any point of centralization or trust. In particular, oracles can participate in interactive ZK dialogues with provers and jointly attest to the verification conclusions. This blog will feature a series of posts explaining state-of-art IR-ZKP protocols and specific use cases.

Zero-Knowledge Proofs

Given some public function f and value y, a zero-knowledge proof protocol allows a party (a.k.a. prover) to show to a verifier that it knows some x, such that f(x; y)=1, without revealing the value x. For example, the following Coke-or-Pepsi ZKP protocol allows a prover to show that it knows how to differentiate between Coke and Pepsi without revealing how:

1. The verifier prepares a glass of Coke and Pepsi and randomly shuffles them.
2. With the verifier looking away, the prover observes/tastes both glasses and decides which one is Coke.
3. Repeat the above process 40 times, and the verifier accepts that the prover indeed knows how to differentiate between Coke and Pepsi if the prover is correct every time.

The above ZKP protocol is not necessarily useful, but in fact, any function f running with polynomial space can be proven in zero-knowledge.

What Is a Non-Interactive Zero-Knowledge Proof?

Traditionally, many zero-knowledge protocols can be made non-interactive, a.k.a. non-interactive zero-knowledge (NIZK) proofs. This means that the prover only needs to run a program taking (f, x, y) as input and outputs the proof pi. Any verifier with (f, y, pi) can verify it and be convinced that the prover indeed knows x without seeing it. The workflow of an NIZK proof resembles a digital signature: The signer signs a public document using its private signing key and generates a signature; any verifier with the document, signature, and verification key can check the validity of the signature.

Non-interactive zero-knowledge proofs have found many applications in the blockchain domain due to their attractive feature of transferability: The prover, without knowing the identity of the verifier, can generate one proof that can be used to convince anyone who receives it. NIZKs with very small proofs are generally categorized as zk-SNARKs.¹ They are particularly suitable for open systems where there can be many verifiers interested in checking the proof. In this case, the proof only needs to be computed once and verified by many verifiers cheaply. However, these advantages of succinct zero-knowledge come with some downsides: Succinct NIZKs often have a high overhead on the prover side in computation and memory. The resource needed to prove a function is orders of magnitude higher than what is needed to evaluate the function in the clear.

¹_{Many NIZKs have a constant-sized proof; while others have a polylogarithmic proof size. We treat them all as zk-SNARKs.}

What Is an Interactive Zero-Knowledge Proof?

Another type of zero-knowledge proof protocol is interactive zero-knowledge proofs. The Coke-or-Pepsi example above is an interactive ZKP between the prover and verifier: the two parties need to communicate in rounds with information flowing in both directions throughout the protocol. Outside the zero-knowledge domain, interactive protocols are commonly used in practice. For example, for a user to authenticate via password, they can run an interactive protocol:

1. The server sends a nonce y to the client
2. The client replies to the server with H(username || password || nonce) for some cryptographic hash function H.
3. The server checks if the value is valid by recomputing the same value locally.

An interactive protocol allows a server-generated nonce and thus prevents replay attacks (where an attacker captures the message and resends it at a later time to the server for authentication). Allowing a round of interaction is crucial because preventing replay attacks would be much more difficult if the password authentication only consists of one message from the client to the server.

Upcoming Posts

Interactive zero-knowledge proofs are generally a broader set of protocols that contain non-interactive zero-knowledge proofs protocols (in particular, one can always add interaction to an NIZK proof to turn it into an interactive ZKP). However, interaction can lead to features that succinct NIZKs do not exhibit, e.g., high scalability to very large statements, cheap computation, avoidance of trusted setup, and minimal use of memory. This is useful when the statement only needs to be proved to a small and known set of parties. This blog series will introduce the foundations of current state-of-the-art interactive ZK protocols. In the upcoming posts, we will cover the following content:

• Memory complexity when evaluating a circuit. Here, we will delve into the details of circuit evaluation to understand why many zero-knowledge protocols need to use a huge amount of memory and how to overcome this issue.
• Zero-knowledge proofs with small memory: complexities and tradeoffs. As the first step to reducing memory consumption, we will introduce some non-interactive zero-knowledge protocols that enjoy small memory complexity. Although small in memory use, these protocols do not perform well in other metrics.
• Scalable and affordable interactive zero-knowledge based on interactive commitment. We talk about interactive ZK, which can be thought of as the interactive variations of the above protocol. These protocols rely on a special type of commitment and feature super cheap computation though they require linear communication.
• Recent progress on interactive commitments. We talk about how to instantiate the commitment needed in interactive zero-knowledge protocols based on recent works on function secret sharing and pseudorandom correlation generators. This needs a quantum-secure assumption called learning parity with noise.
• Overview of engineering difficulties and future developments. Finally, we will talk about the difficulties in making these interactive zero-knowledge protocols efficient and cutting-edge research directions.