VOLE-Based Interactive Commitments
This is the fifth 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
- Vole-Based ZK
Author: Chenkai Weng
Contributors: Alex Coventry, Siam Hussain, Dahlia Malkhi, Alexandru Topliceanu, Xiao Wang, Fan Zhang
Synopsis
In the previous post, we introduced VOLE-based ZK protocols assuming there is a way to construct VOLE-based commitment efficiently. In this post, we describe the transition from VOLE to commitments. The random VOLE correlations are prepared in the setup phase and (repeatedly) used during online interaction. It significantly decreases the computation cost and achieves constant round-trip communication. Also, we explain how to generate VOLE correlations in a higher degree via a packing technique.
A future post will present an efficient VOLE implementation based on Learning Parity with Noise (LPN) assumption.
Interactive Commitment From Vector Oblivious Linear Evaluation
A Single Commitment From OLE
An Oblivious Linear Evaluation (OLE) is a two-party protocol between the prover and verifier which generates a tuple of correlated values $(r, m, \Delta, k)$ such that
$m = k\ – r\cdot\Delta$.
The prover receives $(r, m)$ and the verifier receives $(\Delta, k)$. Using the notation of the field $\mathbb{F}_2$ and its extension field $\mathbb{F}_{2^{128}}$ defined in our fourth blog in the series, we require that $r\in\mathbb{F}_2$ and $(m,\Delta, k)$ are all in $\mathbb{F}_{2^{128}}$. Each party has no information regarding the values obtained by the other party.
Given an OLE correlation, a prover can commit to an arbitrary value $w \in \mathbb{F}_2$ by sending an additional bit $d \in \mathbb{F}_2$ to the verifier. The steps are as follows
- The prover computes $d=r-w$ and sends $d$ to the verifier.
- The verifier computes $k’=k-d\cdot\Delta$.
Now a commitment $[w]$ is the tuple $(w, m)$ held by the prover and $(\Delta, k’)$ held by the verifier, which satisfy
$m = k’-w\cdot\Delta$.
The property of hiding is preserved in this process since the verifier obtains no information regarding $w$. Specifically, we know from the security of OLE that the verifier has no information regarding $(r, m)$. Thus she cannot deduce $w=r-d$ given $d$, or $w=(m-k’)\cdot\Delta^{-1}$ from $(\Delta, k’)$.
Similarly, the property of binding is also guaranteed by the fact that the prover knows nothing about $(\Delta, k)$ by definition of OLE.
Multiple Commitments From VOLE
The number of commitments in a CnP ZKP protocol is linear in the size of the circuit. Define $N$ to be the number of values to commit. As explained in the fourth blog in this series, the use of the same global key $\Delta$ across all commitments for wire values $w_1, \ldots, w_N$ facilitates lightweight batch proof while preserving soundness. We now explain a scheme known as Vector Oblivious Linear Evaluation (VOLE) which efficiently generates a large number of such correlated tuples.
In order to be utilized for $N$ commitments, the VOLE setup protocol provides the prover with:
- A length-$N$ vector $\vec{m}$ of which all individual elements belong to the field $\mathbb{F}_{2^{128}}$.
- A length-$N$ vector $\vec{r}$ of which all individual elements belong to the field $\mathbb{F}_2$.
Correspondingly, the verifier will receive
- A global key $\Delta$ that belongs to the field $\mathbb{F}_{2^{128}}$.
- A length-$N$ vector $\vec{k}$ of which all individual elements belong to the field $\mathbb{F}_{2^{128}}$.
Together they satisfy
$\vec{m}=\vec{k}-\Delta\cdot\vec{r}$
($\Delta\cdot\vec{r}$ means $\Delta$ is multiplied with each element in $\vec{r}$)
$\vec{m}$ and $\vec{k}$ are correlated by the product of $\Delta$ and $\vec{r}$. The security of VOLE protocol requires that each party has no information regarding the values that are received by the other party. Hence, there is a negligible probability for the prover to come up with a $\vec{r}’\neq \vec{r}$ and $\vec{m}’ \neq \vec{m}$ such that $\vec{m}’ = \vec{k} – \Delta\cdot \vec{r}’$.
Similar to the previous section, the prover commits to a vector $\vec{w}$ of witnesses by sending $\vec{d}=\vec{r}-\vec{w}$. The verifier locally computes $\vec{k}’$ by computing $\vec{k}’=\vec{k}-\Delta\cdot\vec{d}$.
Packing VOLE
As mentioned in the fourth blog in this series, the final consistency check during the proving phase requires an additional VOLE correlation in the form of $C_0 = D\ – C_1 \cdot \Delta$ where $C_0, C_1, D, \Delta \in \mathbb{F}_{2^{128}}$. We describe a packing technique to generate such a correlation from the VOLE described above. We use the following notations for simplicity, and now the goal is to generate
$M = K – R\cdot\Delta$,
where $ R, M, K, \Delta \in \mathbb{F}_{2^{128}}$, and the prover holds $(R, M)$ while the verifier holds $(K, \Delta)$. This differs from the previous correlation where $(r, m, k,\Delta)$ has $r \in \mathbb{F_2}$. Luckily, we don’t need another protocol to generate this new form of correlation. Instead we prepare 128 correlations $(r_0, m_0, k_0, \Delta), …, (r_{127}, m_{127}, k_{127}, \Delta)$, where $r_0, …, r_{127} \in \mathbb{F}_2$ , and transform them into one correlation $(R, M, K, \Delta) \in \mathbb{F}_{2^{128}}$.
For $i\in [0,127]$, define a series of gadgets $g_{i}$ to be a vector with only the $i$-th bit to be 1 and the rest are 0s. In the extension field $\mathbb{F}_{2^{128}}$, $g_{i}$ is regarded as a degree-127 polynomial where only the degree-$i$ term has coefficient 1 and other terms all have coefficient 0. The prover computes
$R = r_0 \cdot g_{0} + r_1 \cdot g_{1} + … + r_{127} \cdot g_{127} \in \mathbb{F}_{2^{128}}$
$M = m_0 \cdot g_{0} + m_1 \cdot g_{1} + … + m_{127} \cdot g_{127} \in \mathbb{F}_{2^{128}}$
The verifier computes
$K = k_0 \cdot g_{0} + k_1 \cdot g_{1} + … + k_{127} \cdot g_{127} \in \mathbb{F}_{2^{128}}$
The correctness of this transformation follows from $m_i \cdot g_{i} = k_i \cdot g_{i} – \Delta \cdot r_i \cdot g_{i}$ for each $i$. So together they hold $M = K – X \cdot \Delta$.
Efficiency
The reason to use the VOLE-based interactive commitments is due to its efficiency. The commitment protocol is separated into two phases: setup and online. During the setup phase, two parties invoke the VOLE protocol to generate $N$ VOLE correlations. The state of the art of such protocol incurs communication complexity only polylogarithmic in N. In practice, for $N = 10^7$, the average time to generate one VOLE correlation is less than 20 nanoseconds. During the online phase, the prover generates the commitments by sending N field elements. The communication complexity is linear in N, but the computational cost is low because the two parties only need to perform field element additions and multiplications.
By comparison, existing, additively homomorphic non-interactive commitments often rely on public-key operations, which results in large computational overhead for commit-and-open operations. The VOLE-based commitment scheme trades non-interactiveness for efficient, lightweight computation.
A future post will present the actual mathematical construction of a VOLE protocol which is based on a learning parity with noise (LPN) assumption.
