Try   HackMD

Proposal for Handling The Memory of zkVM

Hanh Tang (NTU), Minh Pham (Orochi Network), and Chiro Hiro (Orochi Network)

Generalize the memory for zkVM (zkMemory)

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 0
    • EveryREAD access for the same location, must have the value to be equal to the previous WRITE.
  • WRITE instruction
    • Every 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?

Memory trace

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.

(address,time_log,instruction,value)

  • address: The location that we applied the memory instruction.
  • time_log: Incremental value that will be increased for every access.
  • instruction: READ, WRITE.
  • value: Value of size WORD_SIZE.

Proposing for the first implementation

We suppose to implement the first version of zkMemory following this wishlist:

  • Building up the memory trace.
  • Committing every state of memory to the Verkle tree.
  • Providing the witness after each state is committed allowing the prover to prove the correctness of entier memory.

KZG Polynomial Commitment

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:

  • KZG commitment and opening proof sizes are constant, even when opening at multiple points. The proof of evaluation only consists of one group element. Thus, the scheme achieves constant proof size.
  • Verification time is also constant, namely, only a pairing operation.
  • The commitment is homomorphic. Given the commitment
    c
    and
    c
    and opening
    π
    and
    π
    of
    p
    and
    p
    , then the commitment and openings of
    p+p
    is just
    c+c
    and
    π+π
    .

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

ωi instead of
i
, where
ω
is a primitive root.

  • Setup(1λ)
    : Sample
    sF
    and output
    ({[si]1}i{0,,k1},{[si]2}i{0,,k1})
  • Commit(p(X)F<k[X],crs)
    : For
    p(X)=i=0k1piXi
    , output
    C=[p(s)]1=i=0k1pi[si]1
  • Open(C,p(X))
    : Output
    p(X)
    .
  • Verify(crs,C,p(X))
    : Check if
    [p(s)]1=i[k]pi[si]1=C
  • OpenWitness(p(X),ωi,crs)
    : To open
    p(X)
    at index
    ωi
    , let
    hi(X)=p(X)p(ωi)Xωi
    . Then, output
    π=(ωi,p(ωi),[hi(s)]2).
  • VerifyWitness(C,π=(ωi,y,hi(s)2),crs)
    : Verify
    p(ωi)=y
    by checking
    e(C[y]1,[1]2)=e([s]1[ωi]1,[hi(s)]2)
    .

Commitment to Verkle Tree

Verkle tree was introduced by John Kuszmaul.

It is a

kary tree having
+1
layers, where:

  • Each leaf node contains a key and a value.
  • Each parent node
    Nj(i)
    has
    k
    children and the value
    vj(i)
    of
    Nj(i)
    of is the commitment to its children.

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.

  • VerkleSetup: Sample
    sF
    and output
    ({[si]1}i{0,,k1},{[si]2}i{0,,k1})
    .

  • VerkleCommit: For integers
    k,j
    , let
    j=kj
    . For each node
    Nj(i)
    , where
    i{0,,k1}
    , with children whose values are
    vj(i+1),vj+1(i+1),,vj+k1(i+1)
    , find a polynomial
    pj(i)(X)
    such that
    pj(i)(ωt)=vj+t(i+1)
    for
    t=0,1,...,k1
    . Then the value
    vj(i)
    of
    Nj(i)
    is
    Commit(crs,pj(i)(X))
    . For the leaf layer, namely, layer
    , the value
    vj()
    for
    j{0,,21}
    is simply the original value at location
    j
    . Output
    v0(0)
    , the root of the tree.

  • VerkleOpen: For a path
    vj0(0)vj1(1)vj2(2)...vj()
    , we have to prove that
    pji(i)(ωji)=vji+1(i+1) i{0,,1}
    . We proceed the following steps:
    Let
    hji(i)(X)=pji(i)(X)vji+1(i+1)Xωji
    and
    r=H(v0(0),...,vj1(1),vj1,...,vj(),ωj0,...,ωjh1)
    .
    Let
    G(X)=i[h]rihi,ji(X)
    , compute
    D=[G(s)]1
    .
    Let
    r=H(D,r)
    and
    h(X)=i[]ripi,ji(X)rωji
    . Compute
    E=[h(s)]1
    . Note that
    E
    can be computed by both prover and verifier, si nce the verifier has already known
    [pii,ji(s)]
    , which belongs to the opening path.
    Finally, let
    y=i[]rivji+1(i+1)rωji
    .
    Output
    D,π=[h(s)G(s)ysr]1

  • VerkleVerify: Check if the root node element is equal to the first opening element and for
    r
    ,
    r
    ,
    y
    defined earlier, compute
    E=i[]ri[vji(i)]1rωji
    check whether
    e(ED[y]1,[1]2)=e(π,[s]2[r]2)

There are several benefits of commiting to a Verkle tree using KZG than hashing in a Merkle tree.

  • Because the width Verkle tree is larger, the opening path is much shorter.
  • The opening proof of Verkle tree is constant sized. As mentioned by Buterin in his blog,the proof size is much smaller than a Merkle proof (6 to 8 times smaller).

Proposal of Folding Scheme for Vector Commitment

We construct a folding scheme for correct evaluation of vector commitment by R1CS-in-the-exponent. The vector commitment to a vector

x=(x0,,xk1) in our solution employs the KZG polynomial commitment scheme and is realized by committing to a polynomial
p(X)
whose evaluations at
ω0,,ωk1
, where
ω
is some reasonable primitive root, are equal to
x0,,xk1
, 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.

Polynomial representation by coefficients

The coefficient representation of a polynomial

p(X)F<k[X] of degree at most
k1
is represented by
p(X)=p0+p1X+p2X2++pk1Xk1.

Polynomial representation by Lagrange basis

In case we would like to construct a polynomial

p(X)F<k[X] satisfying
p(ωi)=xi
for all
i{0,,k1}
, using Lagrange basis
{Li(X)}i{0,,k1}
helps construct such polynomial in a cleaner way. That is,
p(X)=i=0k1xiLi(X).

Polynomial commitment by
2
ways of representations

Thus, in KZG polynomial commitment scheme, we can compute commitment to

p(X) by computing either
[p(X)]=i=0k1pi[si] or [p(X)]=i=0k1xi[Li(X)]

by using the common reference string
{[si]}i{0,,k1}
. However, commitment to
p(X)
by using Lagrange basis asks us to prepare
{[Li(X)]}i{0,,k1}
in advance.

Proposal of Folding Scheme for Memory Accesses with Polynomial Commitments

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
v=(v0,,vk1)
. 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

c=[p(X)]=i=0k1xi[Li(X)]
by using
{[si]}i{0,,k1}
. 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
v
, namely,
vi
, is equal to
y
for some public value
y
. In case of polynomial commitment, it is equivalent to proving that
p(ωi)=yi
.

The proof for opening at the

i-th position is computed as
wi=[p(X)p(ωi)Xωi].

And, to verify the correctness of the proof, we simply check that

e([s][ωi],wi)=e(c[yi],[1]).

R1CS-in-the-exponent for vector commitment. It is now reasonable for us to define the correct form of matrices

A,
B
and
C
, and witness vector
w
.

  • We first realize the structure of witness vector
    w
    . Notice that the verification of evaluation at
    ωi
    require the involvement of
    [s],c,[ωi],[yi],wi
    and
    [1]
    . Since there is no secret element here, we simply define the witness vector
    w
    to be
    w=([s]c[ωi][yi]wi[1]).
  • The matrix
    A
    simply computes
    [s][ωi]
    . Hence,
    A=(101000).
  • Similarly, matrix
    B
    is defined to be
    B=(000010).
  • Matrix
    C
    is defined to be
    C=(010100).

Handling WRITE Access

Notice that, since

c=[p(X)]=i=0k1xi[Li(X)] is computed by Lagrange basis, to update
xi
to
xi
, we simply compute
c=xi[Li(X)]+jixj[Lj(X)]=(xi[Li(X)]+jixj[Lj(X)])+(xixi)[Li(X)]=c+(xixi)[Li(X)]

which is a vector commitment to the vector
(x0,,xi1,xi,xi+1,,xk1)
.

Hence, to update

c to
c
, we simply make the addition for
c
and
(xixi)[Li(X)]
.

Proposal of Verkle Tree with R1CS-in-the-Exponent

Recall that a

k-ary Verkle tree of height
has
+1
layers, indexed from
0
to
, of the following structure:

  • The unique node in level
    0
    is the root of the tree and its value is denoted by
    v0(0)
    which is a vector commitment to the sequence of values
    (v0(1),,vk1(1))
    of its direct
    k
    child nodes in layer
    1
    , to be described later.
  • For each intermediate layer from
    1
    to
    1
    , the
    i
    -th layer has exactly
    ki
    nodes with values denoted by
    vj(i)
    for
    j{0,,ki1}
    . The value
    vj(i)
    is a vector commitment to the sequence of values
    (vkj(i+1),,vk(j+1)1(i+1))
    in the
    (i+1)
    -th layer.
  • The last layer, namely, layer
    , has exactly
    k
    nodes with values denoted by
    v0(),,vk1()
    .

To prove correct opening of Mekle tree, we need to prove correct opening of each respective vector commitment in each layer from

0 to
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.

Conclusion

  • We can provide a library/crate that handle memory commitment for multiple prover, especially the prove that friendly with KZG.
  • The library/crate we're developing can be used in any zkVM with configurable WORD_SIZE.
  • Verkle tree will redurce the overhead to commit and open at arbitrary node.
  • Constructing folding scheme for vector commitment.