Optimise flag representation in Cairo gate

[mrmr1993]

Currently, the flag representation in the cairo gate family uses one witness value per flag. Due to the low degrees of the constraint polynomials, it should be possible to reduce the number of witness values used by grouping the flags together.

For example,

//! - dst_reg \[0\] = fDST_REG : indicates what pointer off_dst refers to ( 0 => ap , 1 => fp )
//! - op0_reg \[1\] = fOP0_REG : indicates what pointer off_op0 refers to ( 0 => ap , 1 => fp )
let dst_op0_reg be any value in [0, 1, 2, 3], constrained by
dst_op0_reg * (dst_op0_reg - 1) * (dst_op0_reg - 2) * (dst_op0_reg - 3) = 0
let dst_reg = dst_op0_reg * (dst_op0_reg - 2)
let op0_reg = dst_op0_reg * (dst_op0_reg - 1)

//! - op1_src \[2..4\] : encodes the type of second operand
//!  · 0: indicates off_op1 is b in the double indexing \[\[ point + a \] + b \]
//!  · 1: indicates off_op1 is an immediate value = fOP1_VAL = 1
//!  · 2: indicates offset off_op1 relative to fp = fOP1_FP = 1
//!  · 4: indicates offset off_op1 relative to ap = fOP1_AP = 1
let op1_src be any value in [0, 1, 2, 4], constrained by
op1_src * (op1_src - 1) * (op1_src - 2) * (op1_src - 4)
let op1_ptr = (op1_src - 1) * (op1_src - 2) * (op1_src - 4)
let op1_val = op1_src * (op1_src - 2) * (op1_src - 4)
let op1_fp = op1_src * (op1_src - 1) * (op1_src - 4)
let op1_ap = op1_src * (op1_src - 1) * (op1_src - 2)

etc.

Handily, it appears that this allows us to fit all of the values needed for 1 Cairo gate into a single double-width Kimchi gate witness. For example,

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
pc	ap	fp	off_dst	off_op0	off_op1	flag_dst_op0	flag_op1_src	flag_res_logic	flag_pc_update	flag_ap_update	flag_opcode	immediate = lookup_{pc+1}
pc_next	ap_next	fp_next	res	op0_addr	lookup_{op0_addr}	op1_addr	lookup_{op1_addr}	dst_addr	lookup_{dst_addr}	op1_addr_aux	lookup_{op1_addr_aux}

[github-actions[bot]]

Stale issue message