Folding schemes have been burgeoning lately! While you wait for our explanation of what folding schemes are, take a look at what we have to say about one of the latest scheme released out there: ProtoStar. In today’s post, we’ll talk about one of its feature: circuit selection.

While ProtoStar achieves our well-known incrementally verifiable computation (IVC), it does more than that: it also allows to switch the main IVC logic to a selection of hardcoded circuits.

The rest of this post takes an “FAQ” approach that might be useful to anyone looking to further their understanding into the circuit selection feature of ProtoStar.

What are the values added to the scheme for circuit selection to work?

ProtoStar adds two values to the scheme:

• pc: a public input that stands for “program counter”
• b: a private input that represents pc as a one-hot

A one one-hot is a vector of all zeros except for one element set to 1. For example [0, 0, 1, 0] is a one-hot of size 4.

ProtoStar doesn’t really have other public inputs (besides the main public input of the protocol) and so it extends the public input as $\text{pi} := (pc, \text{pi}’)$ where $\text{pi}’$ is the public input used by whatever circuit you choose to run.

What are the values pc and b for?

The program counter pc is used to select which circuit to run. ProtoStar’s idea is that each instruction of a zkVM should be encoded as a circuit, with the program counter being used to select which circuit to run. It is a poorly named variable if you’re asking me, as usually the program counter doesn’t tell you the next instruction to run, but rather the next instruction’s address. But I digress.

The witness value b is here as a helper to actually do the selection. You can think of pc as a short encoding or compression of b in some way.

How do we know that these values are correct?

pc is most likely set to some value initially (which can be checked by the circuit to be 1 or something), and then updated as part of any circuit logic. To be useful, it should be updated to point to the circuit that represents the next instruction to run.

b is a witness value and thus needs to be checked for correctness. In the special-sound protocol the verifier checks that the witness value is well-formed by checking:

• that its elements are bits: $b_i \cdot (b_i - 1) = 0$ for all $i \in [n]$
• that its pc-th element is set to 1: $b_i \cdot (pc - i) = 0$ for all $i \in [n]$

Are these values folded as well?

Since pc is part of the public input, it is folded like the public input (in the accumulation scheme). And since b is a private input, it’ll be part of the witness and will be folded as well.

How does the circuit selection impacts the verifier?

In the special-sound protocol, if there are $I$ circuits, the verifier computes the circuit-related checks using the b value as such:

• permutation checks (only in plonk) as $\sum_{j=1}^I b_j \cdot (w_i - w_{\sigma_j(i)}) = 0$
• gates checks (in plonk, but similar in CCS) as $\sum_{j=1}^I b_j \cdot [\sum_{i=1}^m s_{j,i} \cdot G_{j,i}(\cdots)] = 0$ where $s_{j,i}$ (resp. $G_{j, i}$ is the $i$-th gate selector (resp. custom gate) in the $j$-th circuit
• (one of) the lookup check as $\sum_{j=1}^I b_j \cdot [h_i \cdot (w_{L_j[i]} + r)] = 1$

This means that the verifier degree is increased by 1.

In addition the verifier also performs some checks on $\vec{b}$ ($b_i \cdot (b_i - 1) = 0$ and $b_i \cdot (pc - i) = 0$) which can be aggregated with the other checks using the $\beta$ optimization.

What about the prover side?

In the computation of the error term, the prover has to multiply every gate check with the corresponding $b_j$ value. Note that due to the folding, they actually have to multiply each of the checks with $(X \cdot \pi.b_j + \text{acc}.b_j)$ which will be equal to $\text{acc}.b_j$ on non-taken circuits.

This means that in practice, the more circuits your IVC supports, the heavier the computation of the error terms.

Why is the circuit selection free for the prover?

It’s not clear to us why the circuit selection adds no overhead (as the paper claim) due to the observation on the previous Q/A.

Where does the accumulation verifier run?

The IVC circuit works by running two sub circuits: an accumulation verifier and a function F that performs a state transition on the state.

Both subcircuits take the previous state as input. The F function uses it for obvious purposes (i.e. to transition it to a new state). The accumulation verifier uses it as it is part of the public input of the incoming accumulator. Thus by folding the public input of the incoming accumulator, the accumulation verifier postpones the authentication of the previous state to the decider.

You should see the circuit selection as choosing which F function will run in the IVC. Since the function F is the one that updates the IVC state, each circuit should update the IVC state. At the very least, an IVC encoding a zkVM would update pc to point to the next instruction circuit to run.

The paper doesn’t specify where the accumulation verifier should run but there’s two ways:

1. you either run the accumulation verfier in each circuit
2. or you run it outside of the circuit selection: you do not add the $\sum_{j=1}^I$ in front of the accumulation verifier circuit

Does the public input of all circuits have to be the same size? What about the witness?

The witness (and public input) needs to be folded at each step, no matter the circuit used. As such, all the circuits’ witnesses and public inputs need to have the same size.

In practice, it’s easy to just pad the shorter vectors with zeros to reach the size of the other vectors.

When we commit to these vectors (public input or witness) as the prover, having shorter vectors probably does not matter. This is because commitments are most likely done using an algorithm like Pedersen commitments where having no entry is the same as having a zero entry (which when multiplied by its associated basis point contributes nothing to the commitment).

Do the circuits have to have the same sizes?

No, since ProtoStar performs a randomized linear combination of all the constraint/gate of a circuit, it does not matter if the circuits have different sizes.

Of course in Plonk the size of the circuit is correlated with the size of the witness. So the size of the witness will be a multiple of the size of the largest circuit found in the circuit set.

How many circuits can you support?

As said previously, the number of circuits increases the computation of the error term on the prover side, and increases the verifier check.

It also increase the size of the $\vec{b}$ witness, which is part of the witness. But this increase should be negligible compared to the rest.