epic: Processor Component

[zmalatrax]

What needs to be done?

• Produce the main trace (interaction phase 1)
  • Sort by instruction pointer clk (already done)
• Produce the interaction trace (interaction phase 2)
• Is there a need for constant columns? (interaction phase 0) - Yes, $\text{is\_first}$ to apply boundary constraints
• • Claim on log sizes and InteractionClaim on LogUp claimed sum
• Implement the FrameworkEval and derive the component from FrameworkComponent: ProcessorComponent
  • Especially the evalutate function (defining all the constraints linked to this component)

Trace

UPDATE: The design of Stwo makes it easier to evaluate transition constraints on a single row, thus having the $i$ and $i + 1$ value on the same row of the component ; rather than doing bit-reversals to obtain the neighboring row (+ much cheaper, we don't have much columns).

Sorted by clk.

clk	ip	ci	ni	mp	mv	mvi	next_clk	next_ip	next_ci	next_ni	next_mp	next_mv	next_mvi
Clock Cycle Pointer	Instruction Pointer	Current Instruction	Next Instruction	Memory Pointer	Memory Value	Memory Value Inverse	Next Clock Cycle Pointer	Next Instruction Pointer	Next Current Instruction	Next Next Instruction	Next Memory Pointer	Next Memory Value	Next Memory Value Inverse

This way, in the constraints defined below $clk_i$ would be clk and $clk_{i+1}$ would be next_clk.

Constraints

Constraints taken from the BrainSTARK project

Constraints independent of the current instruction ci

Constraint description	Polynomial	Type
clk increases by 1	${clk}_{i+1} - {clk}_i - 1 = 0$	Transition
mvi is the inverse of mv	${mvi} \cdot ({mvi} \cdot {mv} - 1) = 0$	Consistency
mv is the inverse of mvi	${mv} \cdot ({mvi} \cdot {mv} - 1) = 0$	Consistency - Is it needed?

Constraints dependent of the current instruction ci

The deselector polynomial is defined as such:
Let $\phi \in \Phi = \{ \verb| [ |, \verb| ] |, \verb| < |, \verb| > |, \verb| - |, \verb| + |, \verb| , | \verb| . | \}$ a symbol of an existing instruction.
The, the deselector polynomial of a symbol $\phi$ is:

$$\sigma_\phi({ci}) = ci \cdot \prod_{\psi \in \Phi_{\\\phi}}(ci - \psi)$$

This deselector polynomial evaluates to something non-zero when ${ci} = \phi$, otherwise it evaluates to zero.
It is used to conditionally render AIR constraints inactive in a single component.

You just multiply the polynomial constraints by the deselector polynomial with the wanted instruction.
But this is highly inefficient, making constraints of high degree...

JumpIfZero - [

Constraint description	Polynomial	Type
jump to ni if mv = 0, skip two otherwise	${mv}_i \cdot ({ip}_{i+1} - {ip}_i - 2) + {iszero} \cdot ({ip}_{i+1} - {ni}_i) = 0$	Transition
mp remains the same	${mp}_{i+1} - {mp}_i = 0$	Transition
mv remains the same	${mv}_{i+1} - {mv}_i = 0$	Transition

JumpIfNonZero - ]

Constraint description	Polynomial	Type
jump to ni if mv != 0, skip two otherwise	${iszero} \cdot ({ip}_{i+1} - {ip}_i - 2) + {mv}_i \cdot ({ip}_{i+1} - {ni}_i) = 0$	Transition
mp remains the same	${mp}_{i+1} - {mp}_i = 0$	Transition
mv remains the same	${mv}_{i+1} - {mv}_i = 0$	Transition

ShiftLeft - <

Constraint description	Polynomial	Type
ip increments by one	${ip}_{i+1} - {ip}_i - 1 = 0$	Transition
mp decrements by one	${mp}_{i+1} - {mp}_i + 1 = 0$	Transition

ShiftRight - >

Constraint description	Polynomial	Type
ip increments by one	${ip}_{i+1} - {ip}_i - 1 = 0$	Transition
mp increments by one	${mp}_{i+1} - {mp}_i - 1 = 0$	Transition

MemoryDecrement - -

Constraint description	Polynomial	Type
ip increments by one	${ip}_{i+1} - {ip}_i - 1 = 0$	Transition
mp remains the same	${mp}_{i+1} - {mp}_i = 0$	Transition
mv decrements by one	${mv}_{i+1} - {mv}_i + 1 = 0$	Transition

MemoryIncrement - +

Constraint description	Polynomial	Type
ip increments by one	${ip}_{i+1} - {ip}_i - 1 = 0$	Transition
mp remains the same	${mp}_{i+1} - {mp}_i = 0$	Transition
mv increments by one	${mv}_{i+1} - {mv}_i - 1 = 0$	Transition

Input - ,

Constraint description	Polynomial	Type
ip increments by one	${ip}_{i+1} - {ip}_i - 1 = 0$	Transition
mp remains the same	${mp}_{i+1} - {mp}_i = 0$	Transition

Output - .

Constraint description	Polynomial	Type
ip increments by one	${ip}_{i+1} - {ip}_i - 1 = 0$	Transition
mp remains the same	${mp}_{i+1} - {mp}_i = 0$	Transition
mv remains the same	${mv}_{i+1} - {mv}_i = 0$	Transition

Permutation arguments

There are 2 permutation arguments:

• One with the Instruction component, on the registers ip, ci anb ni.
• One with the Memory component, on the registers clk, mp and mv.

Evaluation arguments

There are 2 evaluation arguments:

• One with the Input table: accumulates mv when ci = ,
• One with the Output table: accumulates mv when ci = .

Recap

• 3 constraints independent of ci: 1 transition and 2 consistency
• 2 to 3 transition constraints per instruction, with 8 instructions : 21 constraints
• 2 Permutation arguments
• 2 Evaluation arguments

NOTE: Following the initial design, we're making a single Processor component to handle all the instructions.
However, modern ZK-VM designs are leaning towards having a component per instruction, which provides flexibility & lighter constraints.

Making a component for each instruction would allow lifting the deselector polynomial, and avoid implementing it.
Taking inspo from the SP1 source code, which uses Plonky3 & LogUp could help.

• Make a ProcessorComponent component which contains all the registers and the execution trace
• Make a sub-components for each instruction: JumpIfZeroComponent, ShiftLeftComponent etc, which has the required registers for its constraints
  • Each sub-component trace would only have the states for which ci corresponds to their instruction.
  • Like this, how to prove the correct execution of the instruction? Some constraints requires the next row.
    • Either flatten the two rows into a single row (add registers to the sub-component), or add the ci row and the one that follow (requires to prove that clk increases by 1 every two row for each component, meh)
• Link the ProcessorComponent to the sub-component with a lookup arguments, pretty straightforward actually

Main Trace

Preview Give feedback

1. feat: add a struct for the Processor component trace #67
   +0
   
2. feat: implement From<Vec<Registers>> for ProcessorTable #68
   +0
   
3. feat: implement the trace_evaluation method for the ProcessorTable struct #88
   +0
   
4. feat: add Processor trace generation to the prove_brainfuck entrypoint #87
   +0
   
5. refactor: refactor ProcessorTable to flatten evaluation of transition constraints #111
   +0
   

Interaction Trace

Preview Give feedback

1. Design lookup for processor component
2. feat: construct the required lookup for processor elements for the Processor interaction trace #115
   +0
   
3. feat: generate Processor interaction trace #116
   +0
   
4. feat: add Processor interaction trace to prove_brainfuck entrypoint #145
   +0
   

Component

Preview Give feedback

1. feat: scaffold FrameworkEval for Processor component #123
   +0
   
2. feat: add Processor component to BrainfuckComponent #146
   +0
   
3. feat: add constraints to Processor component #147
   +0