Nova and Memory

why can't memory just be treated as part of the input / output

One thing that Nova does not exactly do (but Supernova does?) is supporting VM memory. We can think of memory as part of the state of computation and is abstractly just a vector that is "carried" with the computation.

Is this just making a new row/vector in the R1CS?

A natural design ^[1] for supporting memory that is folding friendly would be the following:

1. we assume that our memory is a
   $k$-element array
   $\mathbf{v}=(v_0,\dots ,v_{k-1})$.
2. we commit the entire memory using KZG commitments. This means we commit to
   $\mathbf{v}$ with
   
   $$c=[p(X)]=\sum _{i=0}^{k-1}{v}_i\cdot [L_i(X)]$$
   using some secret point
   $\{[s^i]{\}}_{i\in \{0,\dots ,k-1\}}$ as in KZG.
3. we define 3 operations on memory, READ, ADD, and WRITE, and make them folding-friendly.

READ

First, we describe READ access. Specifically, this means proving 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

$$w_i=\left[\frac{p(X)-p({\omega }^i)}{X-{\omega }^i}\right].$$

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

$$e([s]-[{\omega }^i],w_i)=e(c-[y_i],[1]).$$

Now, we build an R1CS and define its components. Notice that the verification of evaluation at

${\omega }^i$ require the involvement of

$[s],c,[{\omega }^i],[y_i],w_i$ and

$[1]$, with no secret elements, so the witness vector is exactly this information.

variable	value
$\mathbf{w}$	${\left(\begin{array}{cccccc}[s]& c& [{\omega }^i]& [y_i]& w_i& [1]\end{array}\right)}^T.$
$\mathbf{A}$	$\left(\begin{array}{cccccc}1& 0& -1& 0& 0& 0\end{array}\right).$
$\mathbf{B}$	$\left(\begin{array}{cccccc}0& 0& 0& 0& 1& 0\end{array}\right).$
$\mathbf{C}$	$\left(\begin{array}{cccccc}0& 1& 0& -1& 0& 0\end{array}\right).$

ADD

Suppose we want to change

$x_i$ to

$x_i+t$. Then we want to commit to a new vector

$(x_0,\dots ,x_{i-1},x_i+t,x_{i+1},\dots ,x_{k-1})$, with commitment

$$\begin{array}{rl}{c}^{\prime }& =t\cdot [L_i(X)]+\sum _j{x}_j\cdot [L_j(X)]\\ & =c+t\cdot [L_i(X)]\end{array}$$

Hence, to update

$c$ to

$c^{\prime }$, we simply make the addition for

$c$ and

$t\cdot [L_i(X)]$.

WRITE

Suppose we want to change

$x_i$ to

$x_i^{\prime }$. We first perform a READ to prove the value of

$x_i$. Then we set

$t=x_i^{\prime }-x_i$, and ADD

$t$ to

$x_i$.

Note that opening a commitment is expensive, so READ is more expensive than ADD.

From Oskar:

Supernova is about supporting different types of F, that correspond to e.g. diff opcodes, like ADD, MUL etc, in a VM. This reduces the prover overhead because an additional opcodes doesn't incur additional cost on the circuit. See https://zkresear.ch/t/towards-a-nova-based-zk-vm/105#supernova-vm-10

I don't think there's any else specific to memory in SuperNova.

More for other doc: It might also be useful to make a distinction between stack vs heap memory since they have diff characteristics

References

---

1. Proposal for Handling The Memory of zkVM, https://hackmd.io/vF1jobzsRoubyUASqQG0Zw?both ↩︎