feat(plonk): support multiple phase halo2 circuit

[chaosma]

Currently, we only support one phase in halo2 circuit synthesize. Need add support for for multiple phases circuit (e.g. zkEVM circuit)

[cyphersnake]

• [x] Investigation

[chaosma]

A multi-phase halo2 synthesize works as follows: (1) generate the witness for columns of first phase, i.e. [W00, W01,..]; [C00, C01,...] =[comm(W00), comm(W01),...]; (2) generate challenges for phase 2 (if any): ro.absorb(C00); ro.absorb(C01);...; ro.squeeze(W0). (3) continue as step (1) and (2) for other phases.

If we follow the same process as halo2, we have to use the same ro as halo2 and split the witness into columns and produce many commitments. We can simplify this part by not split into columns but as a whole. However, we still have to separate the single commitment of witness into multiple commitments (one for each phase).

After modify the witness collection according to each phase, the next task is to modify evaluation method to include the challenges for each phase. To do so, we need append these newly challenges into the challenges vector from sps.

With this change, the number of commitments in RelaxedPlonkInstance will increased by num_phase - 1....

[cyphersnake]

We have two types of challenges:

• plonk-instance (generated in circuit-runner between phases)
• sps (generated after circuit-runner::collect)

WitnessCollector

Add support of phases in WitnessCollector; Just adapt from halo2 implementation

Estimation: 2 sp

CircuitRunner

Have phases-run loop

• Run synth for 1,2,3 phase
• Fill on-step-circuit challenges between phases

Estimation: 5 sp

SPS

Now

We have <= 3 challenges at sps level, they generated with witness+lookup

After

On-Step-Circuit

We will have N1,N2 challenges, they generated from witness of 1,2 phases of circuit

sps

We should not using all witness for generate, but split it into phases-witness-data

Estimation: 2 sp

Verify

Impl verify logic with new PlonkInstace

Estimation: 2 sp

---

11 sp * 1.5 = 17 sp

[cyphersnake]

• 326

• 327

• 328

[cyphersnake]

This task is left to track the context of the entire functionality if any details were missed during planning