This is the fourth post in a series of ZK-related research blogs from the Chainlink Labs Research Team. Check out the rest of the posts in the series:

• Introduction to Interactive Zero-Knowledge Proofs
• Background on Computation Complexity Metrics
• Commit-and-Prove ZKs

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

Synopsis

In the previous post, we introduced commit-and-prove zero-knowledge proofs, and explained at high-level how they can be used to prove statements using small memory. We provided a non-interactive CnP-ZK requiring public-key operations per gate. 

This time, we will present an interactive variant of such a protocol that achieves high efficiency and scalability using symmetric-key operations almost exclusively.

Similar to the CnP-ZK discussed in the last blog, this protocol involves two main building blocks, commitment and proof, but here we use an interactive commitment scheme and an interactive zero-knowledge proof protocol based on this commitment scheme. 

In this interactive ZK proof, one key ingredient is an additively homomorphic commitment scheme. The prover first commits to the input values. Then, the prover and the verifier jointly compute the commitments to the intermediate and output wires by topologically going through the gates. The commitments to output of the addition gates can be computed locally thanks to the homomorphic property of the commitment scheme. The computation and proofs of the commitments to output of multiplication incurs computation and communication costs. Research in the field focuses on reducing this cost. We present a scheme that allows proving that all committed multiplication relationships are correct at a cost independent of the number of gates. This is also known as batch checking. Conceptually, batch checking converts the correctness checks of all multiplications to a single check, verifying that all converted values owned by two parties satisfy a single linear relationship.

Overall, this ZK protocol is able to process tens of millions of gates per second, and can handle large circuits with billions of gates, while only requiring 1 to 2 GB of memory.

As a CnP-ZK, the protocol involves a commitment scheme and a method for proving relationships on committed values. We discuss both of these below. The full protocol described in this post uses Vector Oblivious Linear Evaluation (VOLE) to implement efficient commitments, and thus it is often referred to as VOLE-based ZK. We defer explaining VOLE itself to the next post.

Mathematical Background

Define a binary set $\mathbb{F}_{2}$ which consists of 0 and 1. Also, define a set $\mathbb{F}_{2^{128}}$ which consists of all 128-bit vectors. To be precise, $\mathbb{F}_{2}$ is called a field and $\mathbb{F}_{2^{128}}$ is an extension field of $\mathbb{F}_{2}$.

$\mathbb{F}_{2}$ and $\mathbb{F}_{2^{128}}$ support addition and multiplication. In $\mathbb{F}_{2}$, they are equivalent to logical XOR and AND. In $\mathbb{F}_{2^{128}}$, the addition of two bit vectors is done by XORing them. The multiplication between two $\mathbb{F}_{2^{128}}$ elements is more complicated but is directly supported by modern CPUs. It includes the following steps:

1. Regard each 128-bit string as a degree-127 polynomial where the bits are the coefficients.
2. Compute a carry-less multiplication of two polynomials.
3. Apply degree reduction by modulo an irreducible degree-127 polynomial.

For any value $x \in \mathbb{F}_{2}$ and $y \in \mathbb{F}_{2^{128}}$, we define the result of $y \cdot x$ to be y if $x = 1$ and 128-bit all-zero vector otherwise.

Interactive Commitment

As discussed last time, commitment is a cryptographic tool that allows an entity to first commit to a value and later open it. The commitment scheme used here is also known as information-theoretic message authentication code (IT-MAC), a primitive commonly used in dishonest-majority secure multi-party computation protocols. It is worth noting that IT-MAC can be implemented efficiently using VOLE, as explained in our next post.

The Commitment Scheme

Define a global key $\Delta\in\mathbb{F}_{2^{128}}$, which is only known by the verifier. Assume that the prover wants to commit to a bit $w$. The prover and verifier jointly create an  IT-MAC consisting of $(w, m, \Delta, k)$ with $m,k \in \mathbb{F}_{2^{128}}$ where only the prover has $(w,m)$ and only the verifier has $(\Delta, k)$, such that the values held by the prover and verifier satisfy $m = k – \Delta \cdot w$.

To open the commitment, the prover simply sends $(w,m)$ to the verifier, who checks whether $m = k – \Delta \cdot w$. To simplify the notation, we will use $[w]$ to denote the values associated with the commitment of $w$ that are distributed to two parties. We will describe in the next blog how the prover and verifier can jointly generate such a commitment so that the prover only knows $w$ and $m$, and the verifier only knows $\Delta$  and $k$.

Properties

Hiding:$\Delta $ and $k$ by themselves reveal no information regarding $w$, because the unknown value $m$ could be set to $m’ = k – \Delta \cdot w’$, for either value of $w \in \mathbb{F}_{2}$.

Binding: If, at a later point, a cheating prover wants to claim she committed to $w’ \neq w$, she would need to find $m’$ such that $m’=m-(w’-w) \cdot \Delta$ and send $(w, m’)$ to the verifier. However, this requires the prover to guess $\Delta$. Unless the prover obtains information about $\Delta$ , correctly guessing it only happens with negligible probability since $\Delta$ could be any value in $\mathbb{F}_{2^{128}}$.

Additive homomorphism: Two parties can perform linear transformation on the committed values without any communication. Assume two commitments $[w_1]$ and $[w_2]$ such that the prover has $(w_1, m_1, w_2, m_2)$ and the verifier has $(k_1, k_2, \Delta)$. Two parties can derive $[w] = [w_1] + [w_2]$ where $w = w_1 + w_2$ by locally computing $m = m_1 + m_2$ and $k = k_1 + k_2$. The resulting values $(w, m, \Delta, k)$ are a valid commitment for the sum $w$. For any element $a \in \mathbb{F}_{2}$, they can also derive $[w \cdot a]$ from $[w]$ by updating values $(m, k)$ to $(m \cdot a, k \cdot a)$, and derive $[w + a]$ from $[w]$ by (the verifier) updating $k$ to $k + a$ . In general, for any public bits $c_0, c_1, …, c_n$ and commitments $[w_1], …, [w_n]$, the prover and verifier can compute

$$[w] = c_0 + c_1 \cdot [w_1] + … + c_n \cdot [w_n]$$

locally without interactions. The resulting commitment $[w]$ is a commitment to $w = c_0 + c_1 \cdot w_1 + … + c_n \cdot w_n$. We will discuss in the next section how this feature enables our CnP-ZK to handle any linear operations on commitments “for free” (i.e., the verifier can compute such commitments without further input from the prover).

The Quicksilver Protocol

We now describe Quicksilver, which was introduced by Yang et al. Following the discussion of circuits from previous blogs, we assume that a statement is represented as a Boolean circuit $C$ which consists of only logical XOR and AND gates. With a public circuit C, the prover proves that it knows a private vector $\textbf{x}$ such that $C(\textbf{x}) = 1$, without revealing $\textbf{x}$.

Quicksilver is a CnP-ZK protocol. It utilizes the IT-MAC-based commitments and a special consistency check protocol as the basic building blocks. Both building blocks invoke the VOLE-based IT-MAC commitment protocol (as mentioned, this will be discussed in the next blog).

Commitment Phase

In Quicksilver, first, the prover and the verifier jointly generate the commitments (IT-MAC) for all wire values in the circuits. Then the prover proves that the committed values satisfy the correct relations. 

To be more specific, 

• Prover and verifier generate commitments for two types of wires (i) input wires of the circuit and (ii) output wires of the AND gates. 
• The commitment to the output wires of the XOR gates are generated locally by prover and verifier thanks to the additive homomorphic property of IT-MAC.
• The input wires to gates are either circuit input or outputs of other gates, thus they are covered by types (i) and (ii). 
• Similarly, the circuit outputs are covered by type (ii).

Proving Phase

At this phase, the prover and verifier already hold the commitments to all wires. To prove that the committed values are consistent with the statement $C(\textbf{x}) = 1$, the prover needs to prove that

• The commitment for the output wire of the circuit is a commitment to the value 1. This only requires the prover to open the commitment of the output wire $w_o$. Specifically, the prover sends its IT-MAC $m_o$. The verifier fetches the corresponding $k_o$ and checks whether $m_o = k_o – w_o \cdot \Delta$.
• For all AND gates with commitments for input wire values $[w_a], [w_b]$ and output wire values $[w_c]$, they satisfy $w_c = w_a \cdot w_b$.

The consistency check in Quicksilver is inspired by the LPZK (ITC 21) protocol. The prover only needs to send a few bytes in order to prove that all AND gates have correct input and output commitments. 

We first explain the proof protocol for a single AND gate. Given an AND gate with commitments of input and output wires $[w_a], [w_b], [w_c]$, the verifier wants to check:

• $w_c = w_a \cdot w_b$,
• $m_a = k_a – w_a \cdot \Delta$,
• $m_b = k_b – w_b \cdot \Delta$,
• $m_c = k_c – w_c \cdot \Delta$.

The verifier knows $\Delta$ and $k_a, k_b, k_c$, the prover knows $w_a, w_b, w_c$ and $m_a, m_b, m_c$. Using simple arithmetic manipulations, the verifier combines its local values to one value, denoted $B$, and the prover combines its local values to two values, denoted $A_0$, $A_1$, such that these three values represent the gate constraints. In particular, $A_0 = B – A_1 \cdot \Delta$, i.e., they form a commitment $[A_1]$.

More specifically, the protocol can convince the verifier that the $w_c$ equals  $w_a \cdot w_b$ by constructing the following correlated values:

• The verifier computes: $B = k_a \cdot k_b – k_c \cdot \Delta$
• The prover computes: $A_0 = m_a \cdot m_b$,
• $A_1 = w_a \cdot m_b + w_b \cdot m_a – m_c$.

where the multiplications are finite-field multiplication of extension field elements as described above.

To verify $A_0 = B – A_1 \cdot \Delta$, the prover could in principle send $A_0$ and $A_1$ to the verifier. Based on the security definition of IT-MACs and the properties of our interactive commitments, the prover has no information regarding $B$ and $\Delta$, so the verifier would be convinced that the prover has honestly committed to $w_c =w_a \cdot w_b$, if the prover can provide the correct $A_0$ and $A_1$ to satisfy the correlation.

We can check the verification equation $A_0 = B – A_1 \cdot \Delta$ using high-school algebra (but over an extension field) as follows:

$B = k_a  \cdot  k_b – k_c \cdot \Delta$

    $= (m_a + w_a  \cdot  \Delta)  \cdot  (m_b + w_b  \cdot ) – (m_c + w_c \cdot \Delta) \cdot \Delta$

                                                                                      (by definition)

    $=  m_a  \cdot  m_b + (m_a  \cdot  w_b + m_b  \cdot  w_a – m_c)  \cdot  \Delta + (w_a  \cdot  w_b – w_c) \cdot \Delta^2$

                                                                                      ($w_a  \cdot  w_b – w_c$ get canceled if correct)

    $= A_0 + A_1 \cdot \Delta$

There is still one challenge:  the prover cannot directly send $A_0$ and $A_1$ for the verifier to check: we still need to maintain the zero-knowledge property, and $A_0$ and $A_1$ contain some information about the witness $\textbf{x}$.

To preserve confidentiality, the prover and verifier generate another tuple of correlated elements $(C_0, C_1, D)$, that belong to the set $\mathbb{F}_{2^{128}}$ and satisfy $C_0 = D  – C_1\cdot \Delta$. The prover holds $(C_0, C_1)$ and the verifier holds $D$. We note that all elements are 128-bit vectors, same as $(A_0, A_1, B)$. Generating such correlations from VOLE only requires communication costs of less than 10 bytes (see details in the next blog post).

The values $(C_0, C_1)$ are random and independent from the private input $\textbf{x}$, so it is safe for the prover to use them to cover $(A_1, A_0)$. The checking can be done in the following steps:

1. The prover computes $U = C_0 – A_0$ and $V = C_1 – A_1$.
2. The verifier computes $W = D – B$.
3. The prover sends $U$ and $V$ to the verifier.
4. The verifier checks whether $U = W – V \cdot \Delta$.

As usual, a cheating prover who doesn’t have correct $A_0$ and $A_1$ would need to guess the value of $\Delta$ to derive correct $U$ and $V$.

Batch Checking

The above check requires the prover and verifier to generate an additional tuple of correlated elements (the $C_0$, $C_1$, $D$ above) for each AND gate. The next step is a batch consistency check protocol that can prove the correctness of a large number of AND gates with only one additional correlated tuple. 

We use the random linear combination: assuming that two parties already hold an additional correlated tuple $(C_0, C_1, D)$ and they are checking $N$ AND gates in a batch.

1. For $N$ AND gates, the prover computes $(A_{0,1}, A_{1,1}), …, (A_{0,N}, A_{1,N})$ while the verifier computes $B_1, …, B_N$.
2. The verifier samples a random seed $s$ and sends it to the prover. Two parties use a PRG to expand it to $N$ random coefficients $\chi_1, …, \chi_N$.
3. The prover computes $U = C_0 – \sum_{i=1}^N \chi_i \cdot A_{0,i}$ and $V = C_1 – \sum_{i=1}^N \chi_i \cdot A_{1,i}$. The verifier computes $W = D – \sum_{i=1}^N \chi_i \cdot B_i$.
4. The prover sends $U$ and $V$ to the verifier.
5. The verifier checks whether $U = W – V \cdot \Delta$.

For each gate, two parties only need a few finite-field operations: The prover needs two multiplications, while the verifier needs three multiplications.

Recent Extensions

The QuickSilver protocol is based on ideas from Wolverine (Weng et al. S&P 21) and LPZK (Dittmer et al. ITC 21). In addition to these, there are other VOLE protocols that provide extra features. Mac’N’Cheese (Baum et al. CRYPTO 21) allows proving statements with branches, with communication linear only in the largest branch. LPZKv2 (Dittmer et al. CCS 22) provides an improvement on communication overhead up to a factor of two. Mystique (Weng et al. USENIX 21) allows one to prove consistency between Boolean and arithmetic values efficiently. Appenzeller to Brie (Buam et al. CCS 21) and MozZarella (Baum et al. CRYPTO 22) extend the ZK protocols from statements over finite fields to statements over integers. Franzese et al. (CCS 21) added the capability to perform private RAM access efficiently. Antman (Weng et al. CCS 22) designed an IR-ZKP with sublinear communication but needs extra cryptographic building blocks.