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 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 0
READ
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.
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 . Then open 's evaluations at specific points later.
KZG is widely used due to various reasons:
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 instead of , where is a primitive root.
Verkle tree was introduced by John Kuszmaul.
It is a ary tree having 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.
: Sample and output .
: For integers , let . For each node , where , with children whose values are , find a polynomial such that for . Then the value of is . For the leaf layer, namely, layer , the value for is simply the original value at location . Output , the root of the tree.
: For a path , we have to prove that . We proceed the following steps:
– Let and .
– Let , compute .
– Let and . Compute . Note that can be computed by both prover and verifier, si nce the verifier has already known , which belongs to the opening path.
– Finally, let .
– Output
Check if the root node element is equal to the first opening element and for , , defined earlier, compute check whether
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 in our solution employs the KZG polynomial commitment scheme and is realized by committing to a polynomial whose evaluations at , where is some reasonable primitive root, are equal to , 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 of degree at most is represented by
In case we would like to construct a polynomial satisfying for all , using Lagrange basis helps construct such polynomial in a cleaner way. That is,
Thus, in KZG polynomial commitment scheme, we can compute commitment to by computing either
by using the common reference string . However, commitment to by using Lagrange basis asks us to prepare 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 -element array . 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
by using . This computation is in fact equivalent to evaluating at a secret point .
We first describe the technique for handling READ
access to the memory. Specifically, we would like to prove that the -th element of array , namely, , is equal to for some public value . In case of polynomial commitment, it is equivalent to proving that .
The proof for opening at the -th position is computed as
And, to verify the correctness of the proof, we simply check that
R1CS-in-the-exponent for vector commitment. It is now reasonable for us to define the correct form of matrices , and , and witness vector .
WRITE
AccessNotice that, since is computed by Lagrange basis, to update to , we simply compute
which is a vector commitment to the vector .
Hence, to update to , we simply make the addition for and .
Recall that a -ary Verkle tree of height has layers, indexed from to , 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 to . 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
.