Universal zk-VM circuit & instance data

[morganthomas]

Make Valida into a universal zk-VM circuit by making the following changes:

1. Program goes in the main trace of the program chip, not the preprocessed trace
2. Program and static data are exposed as part of the instance data

[morganthomas]

I'm noting that it doesn't appear that Valida has any notion of instance data currently. We'll need to implement instance data and include in the instance data the contents of the output tape and the program.

[morganthomas]

Here are my current thoughts on instance data. I'm basing my answer on the way that instance data works in PLONK.

In PLONK, you let T(x) be the trace polynomial and v(x) the instance data polynomial, and you let the domain of the instance data be {ω^(-i) | i ∈ {0, ..., |I|}}, where |I| is the size of the instance data and ω is the generator of the domain of the trace polynomial. You use a zero test to check that T(x) - v(x) vanishes on the domain of the instance data.

In Valida, the traces are row major matrices, which means that values in the same row are close together. This means we can't just group all of the instance data at the end of the trace domain like we do in PLONK. What I'm proposing a slight generalization of the PLONK solution to instance data which accounts for the instance data being non-consecutive in the trace domain.

Here's what I'm proposing. Let D be the domain of the instance data: a subset of the domain of the main trace. Let I(x) be the zerofier polynomial of D, the lowest degree polynomial which vanishes on D and is non-zero everywhere else. Let T(x) be the main trace polynomial. Let v(x) be the instance data polynomial. Use a zero test to verify that I(x) * (P(x) - S(x)) vanishes over the main trace domain.

[morganthomas]

Noting (thanks @dorebell !) that currently the verifier re-runs the program, which shouldn't be happening.