feat(plonk): support folding of public inputs in step circuit

[chaosma]

Currently, we don't allow step circuit contains public inputs. Thus, whenever we fold step circuit that contains public inputs, we have to modify the logic to include the public io information into z_in and z_out. This is cumbersome and not necessary, since it is possible to directly fold instance columns from step circuit. To do so, we also need add a new function to the step_circuit interface that return its public inputs..

Motivation In zkEVM circuit, the public inputs are keccak hash of the following data:

pub struct pi_bytes {
   chain_id,  
   prev_state_root, 
   after_state_root,
    swithdraw_trie_root,
    data_hash, 
    chunk_txbytes_hash, 
}

When we fold zkEVM circuit, there are several ways to modify it:

(1) z_in=prev_state_root, z_out=after_state_root. This requires least change, however, the public inputs verification is missing or not consumed.

(2) z_in=prev_pi_bytes, z_out=pi_bytes. In this case, we can re-use synthesize_sub method in pi_circuit to treat z_out. Additionally, we need add verification that after_state_root is in z_in andprev_pi_bytes.after_state_root=pi_bytes.prev_state_root. To do so, we have to modify pi_circuit which is okay. But we also need to import the auxiliary data from previous block/witness to verify the state_root is in prev_pi_byte. This requires changing the witness importing interface since the witness for the circuit doesn't have data_hash etc. of previous block/chunk. This is not a good practice

(3) similar to (2) but remove prev_state_root1 inpi_bytes`, this requires even more changes than (2).

However, after we support folding of the public inputs (i.e. instance columns), we can adopt (1) and only has minimal code modification without changing the witness importing interface.

[cyphersnake]

• [ ] Spec
• [ ] off-circuit
• [ ] on-circuit
• [ ] e2e

[cyphersnake]

Waiting for spec for estimate

[chaosma]

Spec

The idea is not to touch on-circuit part and just the off-circuit part. Here are a draft list of items to be modified:

• halo2 expr -> sirius expr for instance column
• witness collector/witness collection for instance column
• Add step circuit instance columns as part of witness W0 and C0=Comm(W0) changed as well
• In step circuit interface add a new fn to output public inputs
• is_sat_relaxed and is_sat : commitment checking should include public io and accumulated public io
• copy constraint only for one instance col -> for multiple instance columns

Especially, the verifier need a good way to calculate step circuit's public io and also keep track of its accumulated value for final verification. This probably should be done in the ivc::fold_step level. e.g.

fn fold_step(a,b,..,); => fn fold_step(a,b,...,public_io)

[cyphersnake]

I.e. your idea is not to minimize the instance, but just to take it on a common basis with witness, while leaving X0,X1 in the current implementation

am I summarizing this correctly?

Regarding the last point, isn't public input not the responsibility of the step-circuit? We can collect it by having a specific circuit on hand, can't we?

[chaosma]

"take it on a common basis with witness, while leaving X0,X1 in the current implementation", that's right. But I am not quite get the "minimize the instance" part.

It is the responsibility of the step-circuit to provide the public input, we can define an function fn public_io() in the interface. We will try to avoid duplicate synthesize (i.e. process_step as of now) if possible, at least together with process_step. We eventually want to remove the duplicated synthesize

[cyphersnake]

It is the responsibility of the step-circuit to provide the public input, we can define an function fn public_io() in the interface. We will try to avoid duplicate synthesize (i.e. process_step as of now) if possible, at least together with process_step. We eventually want to remove the duplicated synthesize

Well on the other hand within halo2, any public_io is passed separately to prover. In general, let's discuss the design of a specific API by code example in future impl-draft, the general idea is clear

[cyphersnake]

Before

z_in: [F; ARITY]

After

struct StepCircuitInput {
    z_in: [F; ARITY],
    instances: Vec<Vec<F>>,
}

Double check logic

1. Push instances columns as part of witness
2. Use accumulated instances column in is_sat_acc for use it as part of W_commitment check

Pub API of everything

Two options of API:

• Maybe fn pub_io in step-circuit
• pub_io: Vec<Vec<_>> as part of IVC design (like halo2)

Impl

• Modify API | 1 sp
• StepCircuit instance-commitment work | 2 sp
• Add off-circuit FoldingScheme::fold_instances | 1 sp
• Modify is_sat_acc | 3 sp (because only at this point we can debug\test two previous one)
• Modify is_sat_perm | 3 sp

Estimate: 10 sp * 1.5 = 15 sp

Tests

New Test Circuits | 1 sp

[cyphersnake]

The last idea with instance-verification is not suitable, let's continue searching for possible variants

[cyphersnake]

Pub api problem now is #329

[chaosma]

There is one issue in above proposal. To calculate the rlc of step circuits' public inputs, the verifier needs to know the randomness of folding in each step which is not exposed to outside. One way is the verifier can follow the same process to absorb the instances of each step and calculate the randomness using poseidon hash. However, we can overcome it by following:

We add a new variable Y in ivc circuit F' inputs: (i, z_0, z_i, U_i, u_i, IO). At each step, suppose the step circuit has public inputs as y: [F; num_io] (in halo2, y is a vector of vector, but the idea is the same). F' will update Y by Y'=H(Y, H(y)). This way, the verifier is easy to compute the final accumulated public inputs by himself.

However, the prover still have to relate the public io of each step to the corresponding cells through copy constraints. For example, assume there is only one public io, i.e. $y=y[0]$. The ivc circuit will update Y by first assign $y$ to some cell $T[a_0,b_0]$ and calculate poseidon hash accordingly. And in step circuit, it defined copy constraint from some cell $T[i_0, j_0]$ to $y[0]$. i.e. There should be a copy constraint between $T[a_0,b_0]\leftrightarrow T[i_0,j_0]$. Thus, the ivc circuit should do the following:

let y = step_circuit.public_inputs();
let cell = assign(a_0,b_0, y);
constrain_equal(cell, instance_column, 0);

The folding now will consists of the folding of step circuit's instance columns as well. Although the verifier cannot verify the folded instance columns, we use the instance column as a bridge to ensure the consistency between $T[a_0,b_0]\leftrightarrow T[i_0,j_0]$

One small optimization is to throw away public inputs. To do so, we have to modify the underlying copy constraint data from the ConstraintSystem. i.e. when we build the permutation cycles from copy constraint, we should record which permutation cycle contains instance columns. At the end, we should remove all the public instances of step circuit and only keep one instance column for the ivc circuit. However, since usually the number of io is quite small, it not worth the effort in general.

[cyphersnake]

let y = step_circuit.public_inputs();
let cell = assign(a_0,b_0, y);
constrain_equal(cell, instance_column, 0);

The method from step circuit returns the values themselves, not the cells. So it will be necessary during configure step-folding-circuit to understand which instance columns there are and aggregate all their values in random oracle.

But there is a security problem here, that step-circuit in theory may return different public inputs and we will not be able to trace it in any way, but it is not so critical.

[chaosma]

let y = step_circuit.public_inputs();
let cell = assign(a_0,b_0, y);
constrain_equal(cell, instance_column, 0);

The method from step circuit returns the values themselves, not the cells. So it will be necessary during configure step-folding-circuit to understand which instance columns there are and aggregate all their values in random oracle.

But there is a security problem here, that step-circuit in theory may return different public inputs and we will not be able to trace it in any way, but it is not so critical.

This is the tricky part. Although it is possible that the prover assign different/invalid public inputs at each step, there are copy constraints (1) between step circuit to public inputs and (2) between ivc circuit to public inputs. This way, the copy constraint between step circuit and the ivc circuit will fail, if assign diff values. Now the folding of public input columns are not really matter. What matter is that we can calculate and update the public inputs by H(acc, H(new_io)), which the verifier can easily compute offline.