In order to illustrate how these different components work together, let us consider an example in which the program counter pc points to memory location 0x00000004, containing the binary encoding of the instruction ADDI x10 x8 3
. Moreover, for the sake of this example, let us assume the following about the state of the VM.
- Current clock cycle: 256
- Current trace row: 255
- Total number of rows: 216
- R[x8]=0x000000FF was last updated with timestamp 32
- R[x10]=0x00000005 was last updated with timestamp 7
- Prog[0x00000004] has been accessed 2 times before the current clock cycle
In the following we describe the relevant trace columns associated with each component, their expected values at row 255 associated with the current clock cycle 256, and the associated constraints that they must satisfy.
CPU Component Trace Columns and Constraints
In order to verify the correct execution of the ADDI x10 x8 3
instruction at clock cycle 256, the CPU component will perform the following operations:
- Ensure a correct state transition;
- Fetch the instruction
ADDI x10 x8 3
from the program memory component;
- Decode the contents of the instruction and check the correctness of its format;
- Read contents of register x8 from the register memory component;
- Interact with the execution component to execute the instruction
ADDI x10 x8 3
; and
- Update the contents of register x10 based on the output of the execution component.
Let us now show how each of these operations is performed.
Ensuring a Correct State Transition
In this step, the CPU component ensures that the state transition is performed correctly in order to guarantee the correct ordering of instructions during the execution of a program.
In order to do so, the CPU component performs the following checks:
- It verifies that the program counter in the present row matches the value of the next program counter from the preceding row;
- It checks that clock values have been updated correctly; and
- It ensures that padding rows cannot be followed by a non-padding row.
According to the current state of virtual machine, the index i for the current row is 255, the total number of rows is 216, the program counter pc points to memory location 0x00000004 containing an instruction ADDI x10 x8 3
. Hence, the following holds:
- i=255
- pc(1)[255] = 0x04
- pc(2)[255] = 0x00
- pc(3)[255] = 0x00
- pc(4)[255] = 0x00
- clk(1)[255] = 0x00
- clk(2)[255] = 0x01
- clk(3)[255] = 0x00
- clk(4)[255] = 0x00
- is_first[255] = 0
- is_last[255] = 0
- is_add[255] = 1
- imm_c[255] = 1
- is_pad[255] = 0
From the above description, we note that some values, such as the program counter, are split over multiple limbs. Here, pc(1)[255] is the limb contain the least significant bits of the program counters.
In order to verify that the program counter in the present row matches the value of the next program counter from the preceding row, the following constraint is enforced:
//Transition constraints for pc[i] for row i>0 unless is_pad[i]=1//Comparing two limbs at a time∙ (1−is_first[i])⋅(1−is_pad[i]) ⋅ (pc(1)[i]+pc(2)[i]⋅28−pc_next(1)[i−1]−pc_next(2)[i−1]⋅28)=0,∙ (1−is_first[i])⋅(1−is_pad[i]) ⋅ (pc(3)[i]+pc(4)[i]⋅28−pc_next(3)[i−1]−pc_next(4)[i−1]⋅28)=0,
Since is_pad[255]=0 and is_first[255]=0 and since each limb of pc and pc_next is in the range {0,…,255}, in order for the above constraint to be satisfied, it must be the case that:
- pc_next(1)[254] = 0x04
- pc_next(2)[254] = 0x00
- pc_next(3)[254] = 0x00
- pc_next(4)[254] = 0x00
Likewise, in order to verify that the clock values have been updated correctly, the following transition constraint must be satisfied:
//Transition constraints for clk[i] for row i>0//clk_carry(j) for j=1,2 used for handling carries//Adding two limbs at a time∙ clk(1)[i]+clk(2)[i]⋅28+clk_carry(1)[i]⋅216= clk(1)[i−1]+clk(2)[i−1]⋅28+1∙ clk(3)[i]+clk(4)[i]⋅28+clk_carry(2)[i]⋅216= clk(3)[i−1]+clk(4)[i−1]⋅28+clk_carry(1)[i]//Enforcing clk_carry(j)∈{0,1} for j=1,2∙ (clk_carry(1)[i])⋅(1−clk_carry(1)[i])=0,∙ (clk_carry(2)[i])⋅(1−clk_carry(2)[i])=0,//Range check for clk(j) for j=1,2,3,4//More limbs would be needed if T≥232∙ clk(j)∈[0,28−1] for j=1,2,3,4,
For that to happen, it must be the case:
- clk(1)[254] = 0xFF
- clk(2)[254] = 0x00
- clk(3)[254] = 0x00
- clk(4)[254] = 0x00
- clk_carry(1)[255] = 0
- clk_carry(2)[255] = 0
Note that the above constraints introduce additional helper/auxiliary trace variables to account for any carry that may arise while performing the clock update. The prover sets the values for these variables as specified above.
Finally, in order to ensure that padding rows cannot be followed by a non-padding row, the following constraint must be satisfied:
//Ensuring that is_pad remains 1 once it is set to 1 for row i>0∙ (1−is_first[i])⋅(1−is_pad[i])⋅(is_pad[i−1])=0.
Since is_pad[255]=0 and is_first[255]=0, this implies that:
- is_pad[254]=0
Fetching the Instruction
In order to fecth the instruction being executed at the current clock cycle (ADDI x10 x8 3
), the CPU component must interact with the program memory to read the instruction stored at the memory location pointed by the program counter. It must also ensure that the program counter pc is memory-aligned (i.e., a multiple of 4).
Remark: Whenever constraints involve trace columns restricted to the same row, we omit the explicit [i] index for readability. For instance, in the description below, we write instr_val(1) instead of instr_val(1)[255]. All values set in the remainder of this section, unless explicitly specified, apply only to the row indexed by [255] of the corresponding trace column.
In the specification, the CPU interaction with the program memory is captured by a call to the ReadProg interface with parameters pc and clk to obtain instr_val. Note that the CPU component does not check the consistency of the program memory, which is handled separately by the program memory component.
In the actual implementation, this interface is not explicitly implemented since the trace columns for pc, clk, and instr_val are shared between the CPU and program memory components.
As a result of this interaction, the value of these columns will be as follows:
- instr_val(1) = Prog[0x00000004] = 0b00010011
- instr_val(2) = Prog[0x00000005] = 0b00000101
- instr_val(3) = Prog[0x00000006] = 0b00110100
- instr_val(4) = Prog[0x00000007] = 0b00000000
The values of the 4 limbs of instr_val follow from the fact that the binary encoding for the instruction ADDI x10 x8 3
is as follows:
- Bits 0-6: 0b0010011 corresponds to a constant associated with ADDI.
- Bits 7-11: 0b01010 corresponds to destination register x10. This should match the value of op_a;
- Bits 12-14: 0b000 corresponds to a second constant associated with ADDI;
- Bits 15-19: 0b01000 corresponds to the source register x8. This should match the value of op_b;
- Bits 20-31: 0b000000000011 corresponds to the immediate value 3. This should match the value of op_c;
In order to ensure the program counter is a multiple of 4 due to the memory alignment requirement, the following constraint needs to be satisfied:
//Ensuring that pc is a multiple of 4∙ pc_aux(1)⋅4−pc(1)=0,//Enforcing pc_aux(1)∈[0,26−1]∙ pc_aux(1)∈[0,26−1].
To show that this is indeed the case, the prover must set the following auxiliary variable to be:
- pc_aux(1)=0x01
Decoding the Instruction
In this step, the CPU component decodes the instruction ADDI x10 x8 3
that was fetched from the program memory and checks the correctness of the binary encoding.
To achieve this goal, the prover provides several auxiliary values (advices) to help verify the correctness of the binary encoding. More precisely, the prover will provide the following values:
- op_a: The address of the destination register in the instruction
ADDI x10 x8 3
. This corresponds to the destination register 10
.
- op_b: The address of the source register in the instruction
ADDI x10 x8 3
. This corresponds to the destination register 8
.
- op_c: The address of the third operand. This corresponds to the immediate value
3
- op_b_flag: A flag indicating whether operand op_b is used. Should be
1
.
- imm_c: A flag indicating whether operand op_c is an immediate value, Should be
1
.
- is_add: a selector flag which indicates an ADD or ADDI operation. Should be
1
.
- is_alu_imm_no_shift: a flag which indicates this is an ALU instruction with non-shift immediate values. Should be
1
.
- is_type_i: a flag which indicates that this is a Type I instruction. Should be
1
.
- is_pad: a selector flag which indicates whether the current row is being used for padding. Should be
0
.
- is_first: a flag which indicates whether the current row is the first row. Should be
0
.
- is_last: a flag which indicates whether the current row is the last row. Should be
0
.
Moreover, since the operands are spread over several limbs of instr_val, the prover additionally provides the following values to help with verification of the binary encoding of the instruction ADDI x10 x8 3
:
- op_a0 =
0
(bit 0 from op_a)
- op_a1_4 =
5
(bits 1—4 from op_a)
- op_b0 =
0
(bit 0 from op_b)
- op_b1_4 =
4
(bits 1—4 from op_b)
- op_c0_3 =
3
(bits 0—3 from op_c)
- op_c4_7 =
0
(bits 4—7 from op_c)
- op_c8_10 =
0
(bits 8—10 from op_c)
- op_c11 =
0
(bit 11 from op_c)
In order to check the correctness of the values provided by the prover, the following set of constrains are enforced by the CPU component, where we only include those that are relevant for ALU instructions:
- Checking that only one instruction or padding flag is set
//Enforcing exactly one instruction flag is set to 1is_lui+is_auipc+is_jal+is_jalr+is_ecall+is_ebreak+is_lui+is_auipc+is_jal+is_jalr+is_ecall+is_ebreak+is_unimp+is_beq+is_bne+is_blt+is_bge+is_bltu+is_bgeu+is_lb+is_lh+is_lw+is_lbu+is_lhu+is_sb+is_sh+is_sw+is_add+is_sub+is_sll+is_slt+is_sltu+is_xor+is_srl+is_sra+is_or+is_and+is_pad=1
Since is_add is set to 1, all the other flags in the above constraint are set to 0. Our specification also uses additional constraints to ensure that the flags can only be assigned 0/1 values, ensuring that setting all the other flags to be 0 is the only way to satisfy the above constraint. For simplicity, in this document we do not specify the binary constraint on the flags, and refer the reader to the documentation.
- Ensuring that the flag op_b_flag for operand op_b is set to 1 for all instructions except LUI, AUIPC, JAL, UNIMP
//Ensuring that op_b_flag=1 for all instructions//except lui, auipc, jal, unimp(is_sb+is_sh+is_sw+is_lb+is_lh+is_lw+is_lbu+is_lhu+is_jalr+is_add+is_sub+is_slt+is_sltu+is_xor+is_or+is_and+is_sll+is_srl+is_sra+is_beq+is_bne+is_blt+is_bge+is_bltu+is_bgeu+is_ecall+is_ebreak−op_b_flag)=0
Setting is_add=1, op_b_flag=1 and all the other flags to be 0 ensures that the above constraint is satisfied. Note that this assignement of values to the flag is consistent with the prior constraints.
- Ensuring that imm_c=1 for all non-ALU instructions
//Ensuring that imm_c=1 for all non-ALU instructions(is_lui+is_auipc+is_jal+is_jalr+is_ecall+is_ebreak+is_sb+is_sh+is_sw+is_lb+is_lh+is_lw+is_lbu+is_lhu+is_beq+is_bne+is_blt+is_bge+is_bltu+is_bgeu)(1−imm_c)=0
- Matching the instruction flag with the instruction opcode
In the case of the ADD and ADDI instructions, this corresponds to the following constraint:
(is_add)⋅(opcode−ADD)=0
opcode is set to match the constant corresponding to ADD as is_add is set to 1.
- Checking ALU flags
//ALU instructions∙ is_alu=is_add+is_sub+is_slt+is_sltu+is_xor+is_or+is_and+ is_sll+is_srl+is_sra∙ is_alu_imm_shift=imm_c⋅(is_sll+is_srl+is_sra)∙ is_alu_imm_no_shift=imm_c⋅(is_add+is_slt+is_sltu + is_xor+is_or+is_and)//Type I instructions with non-shift immediate values∙ is_type_i_no_shift=is_load+is_alu_imm_no_shift+is_jalr//Type I instructions∙ is_type_i=is_load+is_alu_imm_no_shift+is_alu_imm_shift+is_jalr
The new flags above are used to group instructions so the appropriate constraints are enforced subsequently. Since is_add and imm_c are set to 1, the new flags are set as below to ensure that the constraints are satisfied.
- is_alu =
1
- is_alu_imm_shift =
0
(all the flags on the right have already been set to 0)
- is_alu_imm_no_shift =
1
- is_type_i_no_shift =
1
- is_type_i =
1
- Making sure that the decomposition of each operand is correct
//Making sure op_a is consistent with intermediate parts∙ (is_type_i_no_shift)⋅(op_a0+op_a1_4⋅2−op_a)=0//Range checking the different op_a parts∙ (is_type_i_no_shift)⋅(op_a0)⋅(1−op_a0)=0∙ (is_type_i_no_shift)⋅(op_a1_4∈[0,24−1])//Making sure op_b is consistent with intermediate parts∙ (is_type_i_no_shift)⋅(op_b0+op_b1_4⋅2−op_b)=0//Range checking the different op_b parts∙ (is_type_i_no_shift)⋅(op_b0)⋅(1−op_b1)=0∙ (is_type_i_no_shift)⋅(op_b1_4∈[0,24−1])//Making sure op_c is consistent with intermediate parts∙ (is_type_i_no_shift)⋅(op_c0_3+op_c4_7⋅24+op_c8_10⋅28+op_c11⋅211−op_c)=0//Range checking the different op_c parts∙ (is_type_i_no_shift)⋅(op_c0_3∈[0,24−1])∙ (is_type_i_no_shift)⋅(op_c4_7∈[0,24−1])∙ (is_type_i_no_shift)⋅(op_c8_10∈[0,23−1])∙ (is_type_i_no_shift)⋅(op_c11)⋅(1−op_c11)=0
With is_type_i_no_shift set to 1, and with the additional values for the operands specified previously, the reader can verify that all of the above constraints are satisfied.
- Performing sign extension to derive operand c_val from op_c
//Performing sign extension to compute c_val from op_c∙ (is_type_i_no_shift)⋅(op_c0_3+op_c4_7⋅24−c_val(1))=0∙ (is_type_i_no_shift)⋅(op_c8_10+op_c11⋅(25−1)⋅23−c_val(2))=0∙ (is_type_i_no_shift)⋅(op_c11⋅(28−1)−c_val(3))=0∙ (is_type_i_no_shift)⋅(op_c11⋅(28−1)−c_val(4))=0
As op_c11 is set to 0, the sign extension fills in 0 in the higher order bits of c_val. In particular, the prover sets the values for the limbs for c_val as below to ensure that the constraints are satisfied.
- c_val(1)=0x03
- c_val(2)=0x00
- c_val(3)=0x00
- c_val(4)=0x00
- Checking the format of the instruction
//Checking instruction format for limb 1∙ (is_alu_imm_no_shift)⋅(0b0010011+op_a0⋅27−instr_val(1))=0//Checking instruction format for limb 2∙ (is_add)⋅(imm_c)⋅(op_a1_4+0b000⋅24+op_b_0⋅27−instr_val(2))=0//Checking instruction format for limb 3∙ (is_type_i_no_shift)⋅(op_b1_4+op_c0_3⋅24−instr_val(3))=0//Checking instruction format for limb 4∙ (is_type_i_no_shift)⋅(op_c4_7+op_c8_10⋅24+op_c11⋅27−instr_val(4))=0
With is_type_i_no_shift, is_alu_imm_no_shift, is_add and imm_c set to be 1, and all the other values in the constraints already set previously, the reader can verify that the above constraints are satisfied by those values.
Reading the Contents of Register x8
In order to read the contents of register op_b=x8 at the current clock cycle, the CPU component must interact with the register memory component.
In the specification, the interaction with the register memory is captured by a call to the ReadReg interface with parameters (op_b,clk,1), where 1 indicates that this is the source register reg1, to obtain the value b_val. Like in the program memory case, the CPU component does not check the consistency of the register memory, which is handled separately by the register memory component.
In the actual implementation, this interface is not explicitly implemented since the trace columns for op_b, clk, b_val, reg1_addr, and reg1_val_cur are shared between the CPU and the register memory components.
As a result of this interaction, reg1_addr will be set to op_b. Moreover, the value of the limbs for b_val will be set to the limbs of reg1_val_cur:
- b_val(1) = reg1_val_cur(1) = 0xFF
- b_val(2) = reg1_val_cur(2) = 0x00
- b_val(3) = reg1_val_cur(3) = 0x00
- b_val(4) = reg1_val_cur(4) = 0x00
The values of the 4 limbs of b_val follow from the fact that, by assumption, register op_b=x8 contains 0x00000000FF before the execution of the ADDI instruction.
Executing the Instruction
In order to execute the instruction ADDI x10 x8 3
at the current clock cycle, the CPU component must interact with the execution component.
In the specification, the interaction with the execution memory is captured by a call to the exec interface with parameters (pc,opcode,a_val,b_val,c_val) to obtain the value pc_next. Since this is an ADD operation, the execution component also updates the value of a_val.
In the actual implementation, this interface is not explicitly implemented since the trace columns for pc, opcode, a_val, b_val, c_val, and pc_next are shared between the CPU and the execution components.
As a result of this interaction, the values of the limbs for a_val pc_next will be updated as follows:
- a_val(1) = 0x02
- a_val(2) = 0x01
- a_val(3) = 0x00
- a_val(4) = 0x00
- pc_next(1) = 0x08
- pc_next(2) = 0x00
- pc_next(3) = 0x00
- pc_next(4) = 0x00
The values of the 4 limbs of a_val follow from the fact that b_val=0x000000FF and c_val=0x00000003. While the value of b_val is based on current state of the virtual machine at the current clock cycle, c_val follows from the sign extension of op_c=3.
The values of the 4 limbs of pc_next follow from the fact that pc=0x00000004 gets incremented by 4 after an ADD instruction.
Updating the contents of register x10
In order to update the contents of register op_a=x10 at the current clock cycle, the CPU component must interact with the register memory component.
To do so, the CPU first needs to ensure that the value of register x0 remains 0. For that, the CPU component uses an auxiliary value a_val_effective, which is supposed to be equal to a_val whenever op_a=0 and 0 otherwise. This is enforced via the following set of constraints.
//Determining a_val_effective from op_a//a_val_effective_flag is an auxiliary flag//a_val_effective_flag_{aux,aux_inv} are non-zero auxiliary variables//a_val_effective_flag=1 indicates op_a=0//a_val_effective_flag=0 indicates op_a=0∙ op_a⋅a_val_effective_flag_aux=a_val_effective_flag//Ensuring a_val_effective_flag_aux=0∙ a_val_effective_flag_aux⋅a_val_effective_flag_aux_inv=1//Enforcing a_val_effective_flag∈{0,1}∙ (a_val_effective_flag)⋅(1−a_val_effective_flag)=0//Enforcing relation between a_val and a_val_effective∙ a_val(1)⋅a_val_effective_flag=a_val_effective(1)∙ a_val(2)⋅a_val_effective_flag=a_val_effective(2)∙ a_val(3)⋅a_val_effective_flag=a_val_effective(3)∙ a_val(4)⋅a_val_effective_flag=a_val_effective(4)
Since op_a=x10, the following must be true:
- a_val_effective_flag = 1
- a_val_effective_flag_aux = 1/10
- a_val_effective_flag_aux_inv = 10
- a_val_effective(1) = a_val(1) = 0x02
- a_val_effective(2) = a_val(2) = 0x01
- a_val_effective(3) = a_val(3) = 0x00
- a_val_effective(4) = a_val(4) = 0x00
Next, the CPU component must interact with the register memory component to update the contents of register op_a=x10 with the value a_val_effective.
In the specification, the interaction with the register memory is captured by a call to the WriteReg interface with parameters (op_a,a_val_effective,clk,3), where 3 indicates that this is the destination register reg3, to write the value a_val_effective. As before, the CPU component does not check the consistency of the register memory, which is handled separately by the register memory component.
In the actual implementation, this interface is not explicitly implemented since the trace columns for op_a, clk, a_val_effective, reg3_addr, and reg3_val_cur are shared between the CPU and the register memory components.
As a result of this interaction, the values of the limbs for reg3_val_cur associated with address reg3_addr=op_a=x10 will be updated as follows:
- reg3_val_cur(1) = a_val_effective(1) = 0x02
- reg3_val_cur(2) = a_val_effective(2) = 0x01
- reg3_val_cur(3) = a_val_effective(3) = 0x00
- reg3_val_cur(4) = a_val_effective(4) = 0x00
Execution Component Trace Columns and Constraints
In order to verify the correct execution of the ADDI x10 x8 3
instruction at clock cycle 256, the execution component first enforces that the ADD operation is executed via the following set of constraints:
//Carry handling for the add instruction∙ (is_add)⋅(op_a_val(1)+h_carry(1)⋅28−op_b_val(1)−op_c_val(1))=0∙ (is_add)⋅(op_a_val(2)+h_carry(2)⋅28−op_b_val(2)−op_c_val(2)−h_carry(1))=0∙ (is_add)⋅(op_a_val(3)+h_carry(3)⋅28−op_b_val(3)−op_c_val(3)−h_carry(2))=0∙ (is_add)⋅(op_a_val(4)+h_carry(4)⋅28−op_b_val(4)−op_c_val(4)−h_carry(3))=0//Enforcing that helper carries are binary∙ (is_add)⋅(h_carry(1))⋅(1−h_carry(1))=0∙ (is_add)⋅(h_carry(2))⋅(1−h_carry(2))=0∙ (is_add)⋅(h_carry(3))⋅(1−h_carry(3))=0∙ (is_add)⋅(h_carry(4))⋅(1−h_carry(4))=0
Since b_val=0x000000FF and c_val=0x00000003, in order to satisfy the set of constraints above, it must be the case that:
- a_val(1) = 0x02
- a_val(2) = 0x01
- a_val(3) = 0x00
- a_val(4) = 0x00
- h_carry(1) = 1
- h_carry(2) = 0
- h_carry(3) = 0
- h_carry(4) = 0
Next, the execution component checks whether this instruction is one of those for which pc gets incremented by 4 (which is the case for ADDI). This is done via the following set of constraints:
//Check if instruction is one that pc is incremented∙ (is_alu+is_load+is_type_s+is_type_u+ is_type_sys⋅(1−is_sys_halt)−is_pc_inc_std)=0//pc is incremented by 4 handling two limbs at a time//pc_carry is used to keep track of carries∙ (is_pc_inc_std)⋅(pc_next(1)+pc_next(2)⋅28+pc_carry(1)⋅216 −pc(1)−pc(2)⋅28−4)=0∙ (is_pc_inc_std)⋅(pc_next(3)+pc_next(4)⋅28+pc_carry(2)⋅216 −pc(3)−pc(4)⋅28−pc_carry(1))=0//Ensuring pc_carry is binary∙ (is_pc_inc_std)⋅(pc_carry(1))⋅(1−pc_carry(1))=0∙ (is_pc_inc_std)⋅(pc_carry(2))⋅(1−pc_carry(2))=0
Since pc=0x00000004, it must be the case that carries pc_next should be set as follows:
- pc_next(1) = 0x08
- pc_next(2) = 0x00
- pc_next(3) = 0x00
- pc_next(4) = 0x00
- pc_carry(1) = 0
- pc_carry(2) = 0
Program Memory Component Trace Columns and Constraints
As mentioned in the Proving Memory section, the program memory component uses well-known offline memory checking techniques to maintain the consistency of the read accesses to the program memory. Since this is a read-only memory, the program memory component only requires a simplified version of the offline memory checking technique, in which each memory cell is associated with a counter that keeps track of the number of times a particular memory cell has been read.
More precisely, the program memory component defines the following set of trace elements:
- pc: the word-aligned base address associated with a program instruction
- instr_val(1): bits 0-7 of the instruction word instr_val stored at address pc
- instr_val(2): bits 8-15 of the instruction word instr_val stored at address pc+1
- instr_val(3): bits 16-23 of the instruction word instr_val stored at address pc+2
- instr_val(4): bits 24-31 of the instruction word instr_val stored at address pc+3
- prog_ctr_prev: 4 limbs for the previous counter value associated with base address pc
- prog_ctr_cur: 4 limbs for the current counter value associated with base address pc
- prog_read_digest: a digest of the read set, used for logups
- prog_write_digest: a digest of the write set, used for logups
To enforce the consistency of the read accesses, every time a read operation takes place, the program memory component performs the following actions:
- it checks that the counter associated with the address being accessed is updated correctly; and
- it verifies that the digests of the read and write sets are correctly updated.
Enforcing the correct update of access counters
In order to enforce the correct update of access counters, the program memory component verifies that the following set of constraints are satisfied.
//Enforcing prog_ctr_cur=prog_ctr_prev+1//prog_ctr_carry used for carry handling∙ prog_ctr_prev(1)+1−prog_ctr_carry(1)⋅28−prog_ctr_cur(1)∙ prog_ctr_prev(2)+prog_ctr_carry(1)−prog_ctr_carry(2)⋅28−prog_ctr_cur(2)∙ prog_ctr_prev(3)+prog_ctr_carry(2)−prog_ctr_carry(3)⋅28−prog_ctr_cur(3)∙ prog_ctr_prev(4)+prog_ctr_carry(3)−prog_ctr_carry(4)⋅28−prog_ctr_cur(4)//Enforcing prog_ctr_carry(j)∈{0,1} for j=1,2,3,4∙ (prog_ctr_carry(1))⋅(1−prog_ctr_carry(1))=0∙ (prog_ctr_carry(2))⋅(1−prog_ctr_carry(2))=0∙ (prog_ctr_carry(3))⋅(1−prog_ctr_carry(3))=0∙ (prog_ctr_carry(4))⋅(1−prog_ctr_carry(4))=0
Since Prog[0x00000004] has been accessed 2 times before the current clock cycle according to the initial assumption, we have:
- prog_ctr_prev(1)=2
- prog_ctr_prev(2)=0
- prog_ctr_prev(3)=0
- prog_ctr_prev(4)=0
As a result, in order to satisfy the constraints above, the following must be true:
- prog_ctr_cur(1)=3
- prog_ctr_cur(2)=0
- prog_ctr_cur(3)=0
- prog_ctr_cur(4)=0
- prog_ctr_carry(1)=0
- prog_ctr_carry(2)=0
- prog_ctr_carry(3)=0
- prog_ctr_carry(4)=0
Enforcing the Correct Update of Read- and Write-Set Digests
Let fp(pc,instr_val,prog_ctr) denote a fingerprint function which takes as input the tuple (pc(1), …, pc(4), instr_val(1), …, instr_val(4), prog_ctr(1), …, prog_ctr(4)) and returns a field element in the secure extension field used by Stwo using a random value β chosen by the verifier.
In order to ensure that the digests for the read and write sets are updated correctly, one needs to make sure that the logup contribution associated with the entry (pc, instr_val, prog_ctr_prev) gets added to the read set digest and that the logup contribution associated with the entry (pc, instr_val, prog_ctr_cur) gets added to the write set digest.
More precisely, the following set of transition constraints need to be enforced by the program memory component, where α is a random value chosen by the verifier and i>0 is the row index:
∙ prog_read_digest[i]−prog_read_digest[i−1]= 1/(fp(pc[i],instr_val[i],prog_ctr_prev[i])+α)∙ prog_write_digest[i]−prog_write_digest[i−1]= 1/(fp(pc[i],instr_val[i],prog_ctr_cur[i])+α).
As stated before,
- pc(1)[255]=0x04
- pc(2)[255]=0x00
- pc(3)[255]=0x00
- pc(4)[255]=0x00
- instr_val(1)[255] = Prog[0x00000004] = 0b00010011
- instr_val(2)[255] = Prog[0x00000005] = 0b00000101
- instr_val(3)[255] = Prog[0x00000006] = 0b00110100
- instr_val(4)[255] = Prog[0x00000007] = 0b00000000
Therefore, the following constraints must be satisfied:
∙ prog_read_digest[255]−prog_read_digest[254]= 1/(fp(pc[255],instr_val[255],prog_ctr_prev[255])+α)∙ prog_write_digest[255]−prog_write_digest[254]= 1/(fp(pc[255],instr_val[255],prog_ctr_cur[255])+α).
Remark: In addition to the above specified constraints, the limbs for instr_val, prog_ctr_prev and prog_ctr_curv have range checks specified to ensure they encode the correct number of bits. Here we only note that the above set values satisfy the range constraints, and refer the reader to the formal specification for further details.
Register Memory Component Trace Columns and Constraints
Like the program memory component, the register memory component uses well-known offline memory checking techniques to maintain the consistency of read and write accesses to the register memory. However, since this is a read-write memory, the register memory component needs to associate a timestamp to each memory cell in order to keep track of the last time a particular memory cell has been accessed.
As in the program memory component, the register memory also makes use of logups to check the consistency between the read and write sets, where each element of the set has the form (reg_addr, reg_val, reg_ts) indicating that the value reg_val was written to address (reg_addr at time reg_ts.
Hence, to properly handle an access to a register address, one needs to maintain a set (reg_addr, reg_val_prev, reg_val_cur, reg_ts_prev, reg_ts_cur) consisting of the register address, the previous and current values for that address, and previous and current time stamps. Moreover, since up to three register addresses can be accessed during an execution cycle, the register memory component defines 3 such sets of values.
More precisely, the program memory component defines the following set of trace elements:
- clk: the current execution time
- reg1_addr, reg2_addr, reg3_addr: register addresses
- reg1_val_cur, reg2_val_cur, reg3_val_cur: 32-bit values used to update register contents
- reg1_ts_cur, reg2_ts_cur, reg3_ts_cur: current timestamps for the registers
- reg1_val_prev, reg2_val_prev, reg3_val_prev: previous 32-bit values stored at the registers
- reg1_ts_prev, reg2_ts_prev, reg3_ts_prev: previous timestamps for the registers
- reg_read_digest: a digest of the read set, used for logups.
- reg_write_digest: a digest of the write set, used for logups.
- reg1_accessed, reg2_accessed, reg3_accessed: flags indicating whether the set of trace elements (regj_addr, regj_val_prev, regj_val_cur, regj_ts_prev, regj_ts_cur) for j=1,2,3 are being used
To enforce the consistency of the read and write accesses to the register memory, the register memory component performs the following actions:
- it ensures that the current timestamps associated for reg1_addr, reg2_addr, reg3_addr satisfy the following constraints:
- reg1_ts_cur=3⋅clk−2
- reg2_ts_cur=3⋅clk−1
- reg3_ts_cur=3⋅clk
- it checks that the previous timestamps associated with the addresses being accessed preceed their current timestamps. That is,
- reg1_ts_prev∈{0,…,reg1_ts_cur−1}
- reg2_ts_prev∈{0,…,reg2_ts_cur−1}
- reg3_ts_prev∈{0,…,reg3_ts_cur−1}
- it verifies that the digests of the read and write sets are correctly updated.
Below, we provide more details about the third step and we refer the reader to the formal specification for further details on the first two checks.
Remark: As stated in the specification, reg1_addr, reg2_addr, reg3_addr should be accessed in this order and only reg3_addr can be modified in a given clock cycle.
Enforcing the Correct Update of Read- and Write-Set Digests
Let fp(reg_addr,reg_val,reg_ts) denote a fingerprint function which takes as input the tuple (reg_addr, reg_val(1), …, reg_val(4), reg_ts(1), …, reg_ts(4)) and returns a field element in the secure extension field used by Stwo using a random value β chosen by the verifier.
In order to ensure that the digests for the read and write sets are updated correctly, one needs to make sure that, whenever a register reg_addr is accessed in a clock cycle, the logup contribution associated with the entry (reg_addr, reg_val, reg_ts_prev) must be added to the read set digest and that the logup contribution associated with the entry (reg_addr, reg_val, reg_ts_cur) must be added to the write set digest.
More precisely, the following set of transition constraints need to be enforced by the register memory component, where α is a random value chosen by the verifier and i>0 is the row index:
∙ reg_read_digest[i]−reg_read_digest[i−1]= reg1_accessed[i]/(fp(reg1_addr[i],reg1_val[i],reg1_ts_prev[i])+α) + reg2_accessed[i]/(fp(reg2_addr[i],reg2_val[i],reg2_ts_prev[i])+α) + reg3_accessed[i]/(fp(reg3_addr[i],reg3_val[i],reg3_ts_prev[i])+α)∙ reg_write_digest[i]−reg_write_digest[i−1]= reg1_accessed[i]/(fp(reg1_addr[i],reg1_val[i],reg1_ts_cur[i])+α) + reg2_accessed[i]/(fp(reg2_addr[i],reg2_val[i],reg3_ts_cur[i])+α) + reg3_accessed[i]/(fp(reg3_addr[i],reg3_val[i],reg3_ts_cur[i])+α).
According to the assumptions used for the current example, we have
- R[x8]=0x000000FF was last updated with timestamp 32;and
- R[x10]=0x00000005 was last updated with timestamp 7.
Moreover, based on the interactions with the other components and the constraints for the current timestamps, we also know the following:
- clk[255]=256
- reg1_ts_cur[255]=3⋅256−2=766
- reg3_ts_cur[255]=3⋅256=768
- reg1_accessed[255]=1
- reg2_accessed[255]=0
- reg3_accessed[255]=1
- R[x10] gets updated to 0x00000102 at the current clock cycle
Hence, to satisfy the logup constraints mentioned above for i=255, the following must be true for the current clock cycle:
- reg1_ts_prev(1)[255]=32
- reg1_ts_prev(2)[255]=0
- reg1_ts_prev(3)[255]=0
- reg1_ts_prev(4)[255]=0
- reg1_val_prev(1)[255]=reg1_val_cur(1)[255]=0xFF
- reg1_val_prev(2)[255]=reg1_val_cur(2)[255]=0x00
- reg1_val_prev(3)[255]=reg1_val_cur(3)[255]=0x00
- reg1_val_prev(4)[255]=reg1_val_cur(4)[255]=0x00
- reg1_ts_cur(1)[255]=254
- reg1_ts_cur(2)[255]=2
- reg1_ts_cur(3)[255]=0
- reg1_ts_cur(4)[255]=0
- reg3_ts_prev(1)[255]=7
- reg3_ts_prev(2)[255]=0
- reg3_ts_prev(3)[255]=0
- reg3_ts_prev(4)[255]=0
- reg3_val_prev(1)[255]=0x05
- reg3_val_prev(2)[255]=0x00
- reg3_val_prev(3)[255]=0x00
- reg3_val_prev(4)[255]=0x00
- reg3_ts_cur(1)[255]=0
- reg3_ts_cur(2)[255]=3
- reg3_ts_cur(3)[255]=0
- reg3_ts_cur(4)[255]=0
- reg3_val_cur(1)[255]=0x02
- reg3_val_cur(2)[255]=0x01
- reg3_val_cur(3)[255]=0x00
- reg3_val_cur(4)[255]=0x00