Hanh Tang (NTU), Minh Pham (Orochi Network), and Chiro Hiro (Orochi Network)
The idea is to create an independent module that can be used by any zkVM. You might aware that the memory can be constructed as a simple state machine with \(2\) instructions READ and WRITE, and configurable WORD_SIZE. Our memory state machine is only able access the exactly WORD_SIZE for every executed instruction. That is, if you want to access arbitrary data size, it must be translated to multiple accesses.
These instructions need to be satisfied following conditions:
READ instruction
READ on a memory was not wrote should return 0READ access for the same location, must have the value to be equal to the previous WRITE.WRITE instruction
WRITE access must write on writable memory chunks (some areas of the memmory might be read only).Questions:
- How could we handle the memory boundaries?
- Do we need to deal with memory allocation/deallocation?
- How could we deal with configurable WORD_SIZE?
To prove the accuracy and consistent of the memory, every memory accesss needs to be recorded. We propose the following trace table, (this table might be a well know among many zkVM projects).
| Address | Time Log | Instruction | Value |
|---|---|---|---|
| 0x0000000000000000 | 1 | READ | 0x0000000000000000 |
| 0x0000000000000000 | 2 | WRITE | 0x0000000000000a20 |
| 0x0000000000000020 | 3 | WRITE | 0x0000000000000010 |
| 0x0000000000000020 | 4 | READ | 0x0000000000000010 |
| 0x… | .. | … | … |
We're epxecting these tuple for every memory access.
\[(\text{address}, \text{time_log}, \text{instruction}, \text{value})\]
READ, WRITE.WORD_SIZE.We suppose to implement the first version of zkMemory following this wishlist:
KZG polynomial commitment scheme was introduced by Kate, Zaverucha and Goldberg. It allows us to commit to a polynomial \(p(X)\). Then open \(p\)'s evaluations at specific points later.
KZG is widely used due to various reasons:
\(\Rightarrow\) Using KZG commitment scheme greatly reduces communication cost.
Now, we give a formal description to the KZG commitment scheme. Notice that for indexing, we use \(\omega^i\) instead of \(i\), where \(\omega\) is a primitive root.
Verkle tree was introduced by John Kuszmaul.
It is a \(k-\)ary tree having \(\ell+1\) layers, where:
We see that, unlike Merkle tree, which is a binary tree, in a Verkle tree each parent node can have many more children.
To provide proof for a Verkle tree, we just need to provide a path from the node to the root. To do so, we employ the KZG commitment scheme.
Now, we will describe how to commit and open a path in a Verkle tree. It is possible to open multiple paths using the same technique. More details can be found in Dankrad Feist's blog.
\(\mathsf{VerkleSetup}\): Sample \(s \in \mathbb{F}\) and output \(\left(\{[s^i]_1\}_{i \in \{0,\dots, k-1\}},\{[s^i]_2\}_{i \in \{0,\dots, k-1\}}\right)\).
\(\mathsf{VerkleCommit}\): For integers \(k, j\), let \(j' = k\cdot j\). For each node \(\mathbf{N}_j^{(i)}\), where \(i \in \{0,\dots,k - 1\}\), with children whose values are \(v_{j'}^{(i+1)}, v_{ j'+1}^{(i+1)},\dots,v_{j'+k-1}^{(i+1)}\), find a polynomial \(p^{(i)}_{j}(X)\) such that \(p^{(i)}_{j}(\omega^t)=v_{j'+t}^{(i+1)}\) for \(t=0,1,...,k-1\). Then the value \(v^{(i)}_{j}\) of \(\mathbf{N}_j^{(i)}\) is \(\mathsf{Commit}\left(crs,p^{(i)}_{j}(X)\right)\). For the leaf layer, namely, layer \(\ell\), the value \(v^{(\ell)}_{j}\) for \(j \in \{0, \dots, 2^\ell - 1\}\) is simply the original value at location \(j\). Output \(v_0^{(0)}\), the root of the tree.
\(\mathsf{VerkleOpen}\): For a path \(\mathbf{v}_{j_0}^{(0)} \rightarrow \mathbf{v}_{j_1}^{(1)} \rightarrow \mathbf{v}_{j_2}^{(2)} \rightarrow...\rightarrow \mathbf{v}_{j_\ell}^{(\ell)}\), we have to prove that \(p^{(i)}_{j_i}(\omega^{j_i})=\mathbb{v}_{j_{i+1}}^{(i+1)} ~\forall i \in \{0,\dots, \ell - 1\}\). We proceed the following steps:
– Let \(h^{(i)}_{j_i}(X)=\dfrac{p^{(i)}_{j_i}(X)-\mathbb{v}_{j_{i+1}}^{(i+1)}}{X-\omega^{j_i}}\) and \(r=H(\mathbf{v}_{0}^{(0)},...,\mathbf{v}_{j_{\ell-1}}^{(\ell-1)},\mathbf{v}_{j_1},...,\mathbf{v}_{j_{\ell}}^{(\ell)},\omega^{j_0},...,\omega^{j_{h-1}})\).
– Let \(G(X)=\sum_{i \in [h]}r^ih_{i,j_i}(X)\), compute \(D=[G(s)]_1\).
– Let \(r'=H(D,r)\) and \(h(X)=\sum_{i \in [\ell]}r^i\dfrac{p_{i,j_i}(X)}{r'-\omega^{j_i}}\). Compute \(E=[h(s)]_1\). Note that \(E\) can be computed by both prover and verifier, si nce the verifier has already known \([p_i{i,j_i}(s)]\), which belongs to the opening path.
– Finally, let \(y=\sum_{i \in [\ell]}r^i\dfrac{\mathbb{v}_{j_{i+1}}^{(i+1)}}{r'-\omega^{j_i}}\).
– Output \(D,\pi=\left[\dfrac{h(s)-G(s)-y}{s-r'}\right]_1\)
\(\mathsf{VerkleVerify:}\) Check if the root node element is equal to the first opening element and for \(r\), \(r'\), \(y\) defined earlier, compute \(E=\sum_{i \in [\ell]}r^i\dfrac{[v_{j_i}^{(i)}]_1}{r'-\omega^{j_i}}\) check whether \(e(E-D-[y]_1,[1]_2)=e(\pi,[s]_2-[r']_2)\)
There are several benefits of commiting to a Verkle tree using KZG than hashing in a Merkle tree.
We construct a folding scheme for correct evaluation of vector commitment by R1CS-in-the-exponent. The vector commitment to a vector \(\mathbf{x} = (x_0, \dots, x_{k - 1})\) in our solution employs the KZG polynomial commitment scheme and is realized by committing to a polynomial \(p(X)\) whose evaluations at \(\omega^0, \dots, \omega^{k - 1}\), where \(\omega\) is some reasonable primitive root, are equal to \(x_0, \dots, x_{k - 1}\), respectively.
Remark. The solution we propose here, following Nova, is not complete for R1CS-in-the-exponent for vector commitment with respect to KZG commitment scheme and Verkle tree. It requires additonal adaptations to make it suitable with the form of relaxed R1CS-in-the-exponent.
To make polynomial commitment suitable with folding scheme, we remind the polynomial representations (i) by coefficients and (ii) by Lagrange basis, and show how to commit such a polynomial with respect to these presentations.
The coefficient representation of a polynomial \(p(X) \in \mathbb{F}_{<k}[X]\) of degree at most \(k - 1\) is represented by
\begin{equation}
p(X) = p_0 + p_1X + p_2X^2 + \dots + p_{k - 1}X^{k - 1}.
\end{equation}
In case we would like to construct a polynomial \(p(X) \in \mathbb{F}_{<k}[X]\) satisfying \(p(\omega^i) = x_i\) for all \(i \in \{0, \dots, k - 1\}\), using Lagrange basis \(\{L_i(X)\}_{i \in \{0, \dots, k -1\}}\) helps construct such polynomial in a cleaner way. That is,
\begin{equation}
p(X) = \sum_{i = 0}^{k - 1} x_i L_i(X).
\end{equation}
Thus, in KZG polynomial commitment scheme, we can compute commitment to \(p(X)\) by computing either
\begin{equation}
[p(X)]= \sum_{i = 0}^{k - 1} p_i\cdot [s^i]
\quad\text{ or }\quad
[p(X)] = \sum_{i = 0}^{k - 1}x_i \cdot [L_i(X)]
\end{equation}
by using the common reference string \(\{[s^i]\}_{i \in \{0, \dots, k - 1\}}\). However, commitment to \(p(X)\) by using Lagrange basis asks us to prepare \(\{[L_i(X)]\}_{i \in \{0, \dots, k - 1\}}\) in advance.
In this section, we discuss the technique for constructing folding scheme for memory accesses with respect to polynomial commitments. In particular, we assume that our memory is a \(k\)-element array \(\mathbf{v} = (v_0, \dots, v_{k - 1})\). We commit the entire memory by using the KZG commitment scheme and describe the proof of correct accesses, namely, reading and writing, to the memory.
Using the KZG commitment scheme, we assume that the commitment to the memory is equal to
\begin{equation}
c = [p(X)] = \sum_{i = 0}^{k - 1}x_i \cdot [L_i(X)]
\end{equation}
by using \(\{[s^i]\}_{i \in \{0,\dots, k - 1\}}\). This computation is in fact equivalent to evaluating \(p(X)\) at a secret point \(s\).
We first describe the technique for handling READ access to the memory. Specifically, we would like to prove that the \(i\)-th element of array \(\mathbf{v}\), namely, \(v_i\), is equal to \(y\) for some public value \(y\). In case of polynomial commitment, it is equivalent to proving that \(p(\omega^i) = y_i\).
The proof for opening at the \(i\)-th position is computed as
\begin{equation}
w_i = \left[\frac{p(X) - p(\omega^i)}{X -\omega^i}\right].
\end{equation}
And, to verify the correctness of the proof, we simply check that
\begin{equation}
e([s] - [\omega^i], w_i) = e(c - [y_i], [1]).
\end{equation}
R1CS-in-the-exponent for vector commitment. It is now reasonable for us to define the correct form of matrices \(\mathbf{A}\), \(\mathbf{B}\) and \(\mathbf{C}\), and witness vector \(\mathbf{w}\).
WRITE AccessNotice that, since \(c = [p(X)] = \sum_{i = 0}^{k - 1}x_i \cdot [L_i(X)]\) is computed by Lagrange basis, to update \(x_i\) to \(x'_i\), we simply compute
\begin{align}
c'&= x'_i \cdot [L_i(X)] + \sum_{j \not= i}x_j \cdot [L_j(X)]\\
&= \left(x_i \cdot [L_i(X)] + \sum_{j \not= i}x_j \cdot [L_j(X)]\right) + (x'_i - x_i) \cdot [L_i(X)]\\
&= c + (x'_i - x_i)\cdot [L_i(X)]
\end{align}
which is a vector commitment to the vector \((x_0, \dots, x_{i - 1}, x'_i, x_{i + 1}, \dots, x_{k - 1})\).
Hence, to update \(c\) to \(c'\), we simply make the addition for \(c\) and \((x'_i - x_i)\cdot [L_i(X)]\).
Recall that a \(k\)-ary Verkle tree of height \(\ell\) has \(\ell + 1\) layers, indexed from \(0\) to \(\ell\), of the following structure:
To prove correct opening of Mekle tree, we need to prove correct opening of each respective vector commitment in each layer from \(0\) to \(\ell - 1\). Hence, in this way, we can concatenate all component of all verifications, i.e., for all opening according to a path in Verkle tree, to make it an R1CS form.
WORD_SIZE.
-
Any changes
Be notified of any changes
-
Mention me
Be notified of mention me
-
Unsubscribe
Subscribe