In order to illustrate how these different components work together, let us consider an example in which the program counter pcpc points to memory location 0x00000004\mathtt{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: 256256
  • Current trace row: 255255
  • Total number of rows: 2162^{16}
  • R[x8]=0x000000FFR[\mathtt{x8}] = \mathtt{0x000000FF} was last updated with timestamp 3232
  • R[x10]=0x00000005R[\mathtt{x10}] = \mathtt{0x00000005} was last updated with timestamp 77
  • Prog[0x00000004]Prog[\mathtt{0x00000004}] has been accessed 22 times before the current clock cycle

In the following we describe the relevant trace columns associated with each component, their expected values at row 255255 associated with the current clock cycle 256256, 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 256256, 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\mathtt{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\mathtt{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:

  1. It verifies that the program counter in the present row matches the value of the next program counter from the preceding row;
  2. It checks that clock values have been updated correctly; and
  3. It ensures that padding rows cannot be followed by a non-padding row.

According to the current state of virtual machine, the index ii for the current row is 255255, the total number of rows is 2162^{16}, the program counter pcpc points to memory location 0x00000004\mathtt{0x00000004} containing an instruction ADDI x10 x8 3. Hence, the following holds:

  • i=255i=255
  • pc(1)[255]\mathtt{{pc}^{(1)}[255]} == 0x04\mathtt{0x04}
  • pc(2)[255]\mathtt{{pc}^{(2)}[255]} == 0x00\mathtt{0x00}
  • pc(3)[255]\mathtt{{pc}^{(3)}[255]} == 0x00\mathtt{0x00}
  • pc(4)[255]\mathtt{{pc}^{(4)}[255]} == 0x00\mathtt{0x00}
  • clk(1)[255]\mathtt{{clk}^{(1)}[255]} == 0x00\mathtt{0x00}
  • clk(2)[255]\mathtt{{clk}^{(2)}[255]} == 0x01\mathtt{0x01}
  • clk(3)[255]\mathtt{{clk}^{(3)}[255]} == 0x00\mathtt{0x00}
  • clk(4)[255]\mathtt{{clk}^{(4)}[255]} == 0x00\mathtt{0x00}
  • is_first[255]\mathtt{is\_first}[255] == 00
  • is_last[255]\mathtt{is\_last}[255] == 00
  • is_add[255]\mathtt{is\_add}[255] == 11
  • imm_c[255]\mathtt{imm\_c}[255] == 11
  • is_pad[255]\mathtt{is\_pad}[255] == 00

From the above description, we note that some values, such as the program counter, are split over multiple limbs. Here, pc(1)[255]\mathtt{{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 (1is_first[i])(1is_pad[i])    (pc(1)[i]+pc(2)[i]28pc_next(1)[i1]pc_next(2)[i1]28)=0, (1is_first[i])(1is_pad[i])    (pc(3)[i]+pc(4)[i]28pc_next(3)[i1]pc_next(4)[i1]28)=0,\small \begin{array}{l} {/\!\!/\, \texttt{Transition constraints for} \ \mathtt{pc}[i] \ \texttt{for row} \ i > 0 \ \texttt{unless} \ \mathtt{is\_pad}[i]=1} \\[1pt] {/\!\!/\, \texttt{Comparing two limbs at a time}} \\[1pt] \bullet \ (1-\mathtt{is\_first}[i]) \cdot (1-\mathtt{is\_pad}[i]) \ \cdot \\ \ \ \ (\mathtt{pc}^{(1)}[i] + \mathtt{pc}^{(2)}[i] \cdot 2^{8} - \mathtt{pc\_next}^{(1)}[i-1] - \mathtt{pc\_next}^{(2)}[i-1] \cdot 2^{8}) = 0, \\[1pt] \bullet \ (1-\mathtt{is\_first}[i]) \cdot (1-\mathtt{is\_pad}[i]) \ \cdot \\ \ \ \ (\mathtt{pc}^{(3)}[i] + \mathtt{pc}^{(4)}[i] \cdot 2^{8} - \mathtt{pc\_next}^{(3)}[i-1] - \mathtt{pc\_next}^{(4)}[i-1] \cdot 2^{8}) = 0, \\[4pt] \end{array}

Since is_pad[255]=0\mathtt{is\_pad}[255]=0 and is_first[255]=0\mathtt{is\_first}[255]=0 and since each limb of pc\mathtt{pc} and pc_next\mathtt{pc\_next} is in the range {0,,255}\{0,\ldots,255\}, in order for the above constraint to be satisfied, it must be the case that:

  • pc_next(1)[254]\mathtt{{pc\_next}^{(1)}}[254] == 0x04\mathtt{0x04}
  • pc_next(2)[254]\mathtt{{pc\_next}^{(2)}}[254] == 0x00\mathtt{0x00}
  • pc_next(3)[254]\mathtt{{pc\_next}^{(3)}}[254] == 0x00\mathtt{0x00}
  • pc_next(4)[254]\mathtt{{pc\_next}^{(4)}}[254] == 0x00\mathtt{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)[i1]+clk(2)[i1]28+1 clk(3)[i]+clk(4)[i]28+clk_carry(2)[i]216=   clk(3)[i1]+clk(4)[i1]28+clk_carry(1)[i]/ ⁣ ⁣/Enforcing clk_carry(j){0,1} for j=1,2 (clk_carry(1)[i])(1clk_carry(1)[i])=0, (clk_carry(2)[i])(1clk_carry(2)[i])=0,/ ⁣ ⁣/Range check for clk(j) for  j=1,2,3,4/ ⁣ ⁣/More limbs would be needed if T232 clk(j)[0,281] for j=1,2,3,4,\small \begin{array}{l} {/\!\!/\, \texttt{Transition constraints for} \ \mathtt{clk}[i] \ \texttt{for row} \ i > 0} \\[1pt] {/\!\!/\, \mathtt{clk\_carry}^{(j)} \ \texttt{for} \ j = 1,2 \texttt{ used for handling carries}} \\[1pt] {/\!\!/\, \texttt{Adding two limbs at a time}} \\[1pt] \bullet \ \mathtt{clk}^{(1)}[i] + \mathtt{clk}^{(2)}[i] \cdot 2^{8} + \mathtt{clk\_carry}^{(1)}[i] \cdot 2^{16} = \\ \ \ \ \mathtt{clk}^{(1)}[i-1] + \mathtt{clk}^{(2)}[i-1] \cdot 2^{8} + 1 \\[1pt] \bullet \ \mathtt{clk}^{(3)}[i] + \mathtt{clk}^{(4)}[i] \cdot 2^{8} + \mathtt{clk\_carry}^{(2)}[i] \cdot 2^{16} = \\ \ \ \ \mathtt{clk}^{(3)}[i-1] + \mathtt{clk}^{(4)}[i-1] \cdot 2^{8} + \mathtt{clk\_carry}^{(1)}[i] \\[8pt] {/\!\!/\, \texttt{Enforcing} \ \mathtt{clk\_carry}^{(j)} \in \{0,1\} \ \texttt{for} \ j = 1,2} \\[1pt] \bullet \ (\mathtt{clk\_carry}^{(1)}[i]) \cdot (1 - \mathtt{clk\_carry}^{(1)}[i]) = 0, \\[4pt] \bullet \ (\mathtt{clk\_carry}^{(2)}[i]) \cdot (1 - \mathtt{clk\_carry}^{(2)}[i]) = 0, \\[8pt] {/\!\!/\, \texttt{Range check for } \mathtt{clk}^{(j)} \texttt{ for } \ j=1,2,3,4} \\ {/\!\!/\, \texttt{More limbs would be needed if} \ T \geq 2^{32}} \\[1pt] \bullet \ \mathtt{clk}^{(j)} \in \left[0,2^{8}-1\right] \ \texttt{for} \ j=1,2,3,4, \\[4pt] \end{array}

For that to happen, it must be the case:

  • clk(1)[254]\mathtt{{clk}^{(1)}}[254] == 0xFF\mathtt{0xFF}
  • clk(2)[254]\mathtt{{clk}^{(2)}}[254] == 0x00\mathtt{0x00}
  • clk(3)[254]\mathtt{{clk}^{(3)}}[254] == 0x00\mathtt{0x00}
  • clk(4)[254]\mathtt{{clk}^{(4)}}[254] == 0x00\mathtt{0x00}
  • clk_carry(1)[255]\mathtt{{clk\_carry}^{(1)}}[255] == 00
  • clk_carry(2)[255]\mathtt{{clk\_carry}^{(2)}}[255] == 00

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 (1is_first[i])(1is_pad[i])(is_pad[i1])=0.\small \begin{array}{l} \hspace{0pt}{/\!\!/\, \texttt{Ensuring that} \ \mathtt{is\_pad} \ \texttt{remains} \ 1 \ \texttt{once it is set to} \ 1 \ \texttt{for row} \ i > 0} \\[1pt] \bullet \ (1 - \mathtt{is\_first}[i]) \cdot (1 - \mathtt{is\_pad}[i]) \cdot (\mathtt{is\_pad}[i-1]) = 0. \\[4pt] \end{array}

Since is_pad[255]=0\mathtt{is\_pad}[255]=0 and is_first[255]=0\mathtt{is\_first}[255]=0, this implies that:

  • is_pad[254]=0\mathtt{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\mathtt{pc} is memory-aligned (i.e., a multiple of 44).

Remark: Whenever constraints involve trace columns restricted to the same row, we omit the explicit [i][i] index for readability. For instance, in the description below, we write instr_val(1)\mathtt{{instr\_val}^{(1)}} instead of instr_val(1)[255]\mathtt{{instr\_val}^{(1)}}[255]. All values set in the remainder of this section, unless explicitly specified, apply only to the row indexed by [255][255] of the corresponding trace column.

In the specification, the CPU interaction with the program memory is captured by a call to the ReadProg\mathtt{Read}_{Prog} interface with parameters pc\mathtt{pc} and clk\mathtt{clk} to obtain instr_val\mathtt{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\mathtt{pc}, clk\mathtt{clk}, and instr_val\mathtt{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)\mathtt{{instr\_val}^{(1)}} = Prog[0x00000004]Prog[\mathtt{0x00000004}] = 0b00010011\mathtt{0b00010011}
  • instr_val(2)\mathtt{{instr\_val}^{(2)}} = Prog[0x00000005]Prog[\mathtt{0x00000005}] = 0b00000101\mathtt{0b00000101}
  • instr_val(3)\mathtt{{instr\_val}^{(3)}} = Prog[0x00000006]Prog[\mathtt{0x00000006}] = 0b00110100\mathtt{0b00110100}
  • instr_val(4)\mathtt{{instr\_val}^{(4)}} = Prog[0x00000007]Prog[\mathtt{0x00000007}] = 0b00000000\mathtt{0b00000000}

The values of the 4 limbs of instr_val\mathtt{instr\_val} follow from the fact that the binary encoding for the instruction ADDI x10 x8 3 is as follows:

  • Bits 0-6: 0b0010011\mathtt{0b0010011} corresponds to a constant associated with ADDI.
  • Bits 7-11: 0b01010\mathtt{0b01010} corresponds to destination register x10\mathtt{x10}. This should match the value of op_a\mathtt{op\_a};
  • Bits 12-14: 0b000\mathtt{0b000} corresponds to a second constant associated with ADDI;
  • Bits 15-19: 0b01000\mathtt{0b01000} corresponds to the source register x8\mathtt{x8}. This should match the value of op_b\mathtt{op\_b};
  • Bits 20-31: 0b000000000011\mathtt{0b000000000011} corresponds to the immediate value 33. This should match the value of op_c\mathtt{op\_c};

In order to ensure the program counter is a multiple of 44 due to the memory alignment requirement, the following constraint needs to be satisfied:

/ ⁣ ⁣/Ensuring that pc is a multiple of 4 pc_aux(1)4pc(1)=0,/ ⁣ ⁣/Enforcing pc_aux(1)[0,261] pc_aux(1)[0,261].\small \begin{array}{l} {/\!\!/\, \texttt{Ensuring that} \ \mathtt{pc} \ \texttt{is a multiple of 4}} \\[1pt] \bullet \ \mathtt{pc\_aux}^{(1)} \cdot 4 - \mathtt{pc}^{(1)} = 0, \\[4pt] \hspace{0pt}{/\!\!/\, \texttt{Enforcing} \ \mathtt{pc\_aux}^{(1)} \in \left[0,2^{6}-1\right]} \\[1pt] \bullet \ \mathtt{pc\_aux}^{(1)} \in \left[0,2^{6}-1\right]. \\[4pt] \end{array}

To show that this is indeed the case, the prover must set the following auxiliary variable to be:

  • pc_aux(1)=0x01\mathtt{pc\_aux}^{(1)}=\mathtt{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\mathtt{op\_a}: The address of the destination register in the instruction ADDI x10 x8 3. This corresponds to the destination register 10.
  • op_b\mathtt{op\_b}: The address of the source register in the instruction ADDI x10 x8 3. This corresponds to the destination register 8.
  • op_c\mathtt{op\_c}: The address of the third operand. This corresponds to the immediate value 3
  • op_b_flag\mathtt{{op\_b\_flag}}: A flag indicating whether operand op_b\mathtt{op\_b} is used. Should be 1.
  • imm_c\mathtt{{imm\_c}}: A flag indicating whether operand op_c\mathtt{op\_c} is an immediate value, Should be 1.
  • is_add\mathtt{is\_add}: a selector flag which indicates an ADD or ADDI operation. Should be 1.
  • is_alu_imm_no_shift\mathtt{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\mathtt{is\_type\_i}: a flag which indicates that this is a Type I instruction. Should be 1.
  • is_pad\mathtt{is\_pad}: a selector flag which indicates whether the current row is being used for padding. Should be 0.
  • is_first\mathtt{is\_first}: a flag which indicates whether the current row is the first row. Should be 0.
  • is_last\mathtt{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\mathtt{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\mathtt{op\_a0} = 0 (bit 0 from op_a\mathtt{op\_a})
  • op_a1_4\mathtt{op\_a1\_4} = 5 (bits 1—4 from op_a\mathtt{op\_a})
  • op_b0\mathtt{op\_b0} = 0 (bit 0 from op_b\mathtt{op\_b})
  • op_b1_4\mathtt{op\_b1\_4} = 4 (bits 1—4 from op_b\mathtt{op\_b})
  • op_c0_3\mathtt{op\_c0\_3} = 3 (bits 0—3 from op_c\mathtt{op\_c})
  • op_c4_7\mathtt{op\_c4\_7} = 0 (bits 4—7 from op_c\mathtt{op\_c})
  • op_c8_10\mathtt{op\_c8\_10} = 0 (bits 8—10 from op_c\mathtt{op\_c})
  • op_c11\mathtt{op\_c11} = 0 (bit 11 from op_c\mathtt{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:

  1. 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\small \begin{array}{l} {/\!\!/\, \texttt{Enforcing exactly one instruction flag is set to 1}} \\[1pt] \mathtt{is\_lui} + \mathtt{is\_auipc} + \mathtt{is\_jal} + \mathtt{is\_jalr} + \mathtt{is\_ecall} + \mathtt{is\_ebreak} +\\ \mathtt{is\_lui} + \mathtt{is\_auipc} + \mathtt{is\_jal} + \mathtt{is\_jalr} + \mathtt{is\_ecall} + \mathtt{is\_ebreak} +\\ \mathtt{is\_unimp} + \mathtt{is\_beq} + \mathtt{is\_bne} + \mathtt{is\_blt} + \mathtt{is\_bge} + \mathtt{is\_bltu} + \mathtt{is\_bgeu} +\\ \mathtt{is\_lb} + \mathtt{is\_lh} + \mathtt{is\_lw} + \mathtt{is\_lbu} + \mathtt{is\_lhu} + \mathtt{is\_sb} + \mathtt{is\_sh} + \mathtt{is\_sw} + \\ \mathtt{is\_add} + \mathtt{is\_sub} + \mathtt{is\_sll} + \mathtt{is\_slt} + \mathtt{is\_sltu} + \mathtt{is\_xor} + \mathtt{is\_srl} + \mathtt{is\_sra} +\\ \mathtt{is\_or} + \mathtt{is\_and} + \mathtt{is\_pad} = 1 \end{array}

Since is_add\mathtt{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.

  1. Ensuring that the flag op_b_flag\mathtt{op\_b\_flag} for operand op_b\mathtt{op\_b} is set to 11 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_ebreakop_b_flag)=0\small \begin{array}{ll} & {/\!\!/\, \texttt{Ensuring that } \mathtt{op\_b\_flag = 1} \texttt{ for all instructions}} \\[1pt] & {/\!\!/\, \texttt{except lui, auipc, jal, unimp}} \\[1pt] &(\mathtt{is\_sb} + \mathtt{is\_sh} + \mathtt{is\_sw} + \mathtt{is\_lb} + \mathtt{is\_lh} + \mathtt{is\_lw} + \mathtt{is\_lbu} + \mathtt{is\_lhu} + \mathtt{is\_jalr} \\ &+\mathtt{is\_add} + \mathtt{is\_sub} + \mathtt{is\_slt} + \mathtt{is\_sltu} + \mathtt{is\_xor} + \mathtt{is\_or} + \mathtt{is\_and} + \mathtt{is\_sll} \\ &+ \mathtt{is\_srl} + \mathtt{is\_sra} + \mathtt{is\_beq} + \mathtt{is\_bne} + \mathtt{is\_blt} + \mathtt{is\_bge} + \mathtt{is\_bltu} + \mathtt{is\_bgeu}\\ &+ \mathtt{is\_ecall} + \mathtt{is\_ebreak} - \mathtt{op\_b\_flag}) = 0 \end{array}

Setting is_add=1\mathtt{is\_add}=1, op_b_flag=1\mathtt{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.

  1. Ensuring that imm_c=1\mathtt{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)(1imm_c)=0\small \begin{array}{ll} & {/\!\!/\, \texttt{Ensuring that } \mathtt{imm\_c=1} \texttt{ for all non-ALU instructions}} \\[1pt] &(\mathtt{is\_lui} + \mathtt{is\_auipc} + \mathtt{is\_jal} + \mathtt{is\_jalr} + \mathtt{is\_ecall} + \mathtt{is\_ebreak} + \mathtt{is\_sb} \\ &+ \mathtt{is\_sh} + \mathtt{is\_sw} + \mathtt{is\_lb} + \mathtt{is\_lh} + \mathtt{is\_lw} + \mathtt{is\_lbu} + \mathtt{is\_lhu} + \mathtt{is\_beq} \\ &+ \mathtt{is\_bne} + \mathtt{is\_blt} + \mathtt{is\_bge} + \mathtt{is\_bltu} + \mathtt{is\_bgeu} )(1 - \mathtt{imm\_c}) = 0 \end{array}
  1. 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)(opcodeADD)=0\small (\mathtt{is\_add}) \cdot (\mathtt{opcode} − \mathtt{ADD}) = 0

opcode\mathtt{opcode} is set to match the constant corresponding to ADD\mathtt{ADD} as is_add\mathtt{is\_add} is set to 1.

  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\small \begin{array}{l} {/\!\!/\, \texttt{ALU instructions}} \\[1pt] \bullet \ \mathtt{is\_alu} = \mathtt{is\_add} + \mathtt{is\_sub} + \mathtt{is\_slt} + \mathtt{is\_sltu} + \mathtt{is\_xor} + \mathtt{is\_or} + \mathtt{is\_and} +\\ \ \ \ \mathtt{is\_sll} + \mathtt{is\_srl} + \mathtt{is\_sra} \\[1pt] \bullet \ \mathtt{is\_alu\_imm\_shift} = \mathtt{imm\_c} \cdot (\mathtt{is\_sll} + \mathtt{is\_srl} + \mathtt{is\_sra}) \\[1pt] \bullet \ \mathtt{is\_alu\_imm\_no\_shift} = \mathtt{imm\_c} \cdot (\mathtt{is\_add} + \mathtt{is\_slt} + \mathtt{is\_sltu} \ +\\[1pt] \ \ \ \mathtt{is\_xor} + \mathtt{is\_or} + \mathtt{is\_and}) \\[4pt] {/\!\!/\, \texttt{Type I instructions with non-shift immediate values}} \\[1pt] \bullet \ \mathtt{is\_type\_i\_no\_shift} = \mathtt{is\_load} + \mathtt{is\_alu\_imm\_no\_shift} + \mathtt{is\_jalr} \\[4pt] {/\!\!/\, \texttt{Type I instructions}} \\[1pt] \bullet \ \mathtt{is\_type\_i} = \mathtt{is\_load} + \mathtt{is\_alu\_imm\_no\_shift} + \mathtt{is\_alu\_imm\_shift} + \mathtt{is\_jalr} \\[1pt] \end{array}

The new flags above are used to group instructions so the appropriate constraints are enforced subsequently. Since is_add\mathtt{is\_add} and imm_c\mathtt{imm\_c} are set to 1, the new flags are set as below to ensure that the constraints are satisfied.

  • is_alu\mathtt{is\_alu} = 1
  • is_alu_imm_shift\mathtt{is\_alu\_imm\_shift} = 0 (all the flags on the right have already been set to 0)
  • is_alu_imm_no_shift\mathtt{is\_alu\_imm\_no\_shift} = 1
  • is_type_i_no_shift\mathtt{is\_type\_i\_no\_shift} = 1
  • is_type_i\mathtt{is\_type\_i} = 1
  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_42op_a)=0/ ⁣ ⁣/Range checking the different op_a parts (is_type_i_no_shift)(op_a0)(1op_a0)=0 (is_type_i_no_shift)(op_a1_4[0,241])/ ⁣ ⁣/Making sure op_b is consistent with intermediate parts (is_type_i_no_shift)(op_b0+op_b1_42op_b)=0/ ⁣ ⁣/Range checking the different op_b parts (is_type_i_no_shift)(op_b0)(1op_b1)=0 (is_type_i_no_shift)(op_b1_4[0,241])/ ⁣ ⁣/Making sure op_c is consistent with intermediate parts (is_type_i_no_shift)(op_c0_3+op_c4_724+op_c8_1028+op_c11211op_c)=0/ ⁣ ⁣/Range checking the different op_c parts (is_type_i_no_shift)(op_c0_3[0,241]) (is_type_i_no_shift)(op_c4_7[0,241]) (is_type_i_no_shift)(op_c8_10[0,231]) (is_type_i_no_shift)(op_c11)(1op_c11)=0\small \begin{array}{l} {/\!\!/\, \texttt{Making sure } \mathtt{op\_a} \texttt{ is consistent with intermediate parts}} \\[1pt] \bullet \ (\mathtt{is\_type\_i\_no\_shift}) \cdot (\mathtt{op\_a0} + \mathtt{op\_a1\_4} \cdot 2 - \mathtt{op\_a}) = 0 \\[4pt] {/\!\!/\, \texttt{Range checking the different } \mathtt{op\_a} \texttt{ parts}} \\[1pt] \bullet \ (\mathtt{is\_type\_i\_no\_shift}) \cdot (\mathtt{op\_a0}) \cdot (1-\mathtt{op\_a0}) = 0 \\[1pt] \bullet \ (\mathtt{is\_type\_i\_no\_shift}) \cdot (\mathtt{op\_a1\_4} \in \left[0, 2^{4} - 1\right]) \\[4pt] {/\!\!/\, \texttt{Making sure } \mathtt{op\_b} \texttt{ is consistent with intermediate parts}} \\[1pt] \bullet \ (\mathtt{is\_type\_i\_no\_shift}) \cdot (\mathtt{op\_b0} + \mathtt{op\_b1\_4} \cdot 2 - \mathtt{op\_b}) = 0 \\[4pt] {/\!\!/\, \texttt{Range checking the different } \mathtt{op\_b} \texttt{ parts}} \\[1pt] \bullet \ (\mathtt{is\_type\_i\_no\_shift}) \cdot (\mathtt{op\_b0}) \cdot (1-\mathtt{op\_b1}) = 0 \\[1pt] \bullet \ (\mathtt{is\_type\_i\_no\_shift}) \cdot (\mathtt{op\_b1\_4} \in \left[0, 2^{4} - 1\right]) \\[4pt] {/\!\!/\, \texttt{Making sure } \mathtt{op\_c} \texttt{ is consistent with intermediate parts}} \\[1pt] \bullet \ (\mathtt{is\_type\_i\_no\_shift}) \cdot (\mathtt{op\_c0\_3} + \mathtt{op\_c4\_7} \cdot 2^{4} + \mathtt{op\_c8\_10} \cdot 2^{8} + \mathtt{op\_c11} \cdot 2^{11} - \mathtt{op\_c}) = 0 \\[4pt] {/\!\!/\, \texttt{Range checking the different } \mathtt{op\_c} \texttt{ parts}} \\[1pt] \bullet \ (\mathtt{is\_type\_i\_no\_shift}) \cdot (\mathtt{op\_c0\_3} \in \left[0,2^{4}-1\right]) \\[1pt] \bullet \ (\mathtt{is\_type\_i\_no\_shift}) \cdot (\mathtt{op\_c4\_7} \in \left[0,2^{4}-1\right]) \\[1pt] \bullet \ (\mathtt{is\_type\_i\_no\_shift}) \cdot (\mathtt{op\_c8\_10} \in \left[0,2^{3}-1\right]) \\[1pt] \bullet \ (\mathtt{is\_type\_i\_no\_shift}) \cdot (\mathtt{op\_c11}) \cdot (1-\mathtt{op\_c11}) = 0 \\[4pt] \end{array}

With is_type_i_no_shift\mathtt{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.

  1. Performing sign extension to derive operand c_val\mathtt{c\_val} from op_c\mathtt{op\_c}
/ ⁣ ⁣/Performing sign extension to compute c_val from op_c (is_type_i_no_shift)(op_c0_3+op_c4_724c_val(1))=0 (is_type_i_no_shift)(op_c8_10+op_c11(251)23c_val(2))=0 (is_type_i_no_shift)(op_c11(281)c_val(3))=0 (is_type_i_no_shift)(op_c11(281)c_val(4))=0\small \begin{array}{l} {/\!\!/\, \texttt{Performing sign extension to compute } \mathtt{c\_val} \texttt{ from } \mathtt{op\_c}} \\[1pt] \bullet \ (\mathtt{is\_type\_i\_no\_shift}) \cdot (\mathtt{op\_c0\_3} + \mathtt{op\_c4\_7} \cdot 2^{4} - \mathtt{c\_val}^{(1)}) = 0 \\[1pt] \bullet \ (\mathtt{is\_type\_i\_no\_shift}) \cdot (\mathtt{op\_c8\_10} + \mathtt{op\_c11} \cdot (2^{5}-1) \cdot 2^{3} - \mathtt{c\_val}^{(2)}) = 0 \\[1pt] \bullet \ (\mathtt{is\_type\_i\_no\_shift}) \cdot (\mathtt{op\_c11} \cdot (2^{8}-1) - \mathtt{c\_val}^{(3)}) = 0 \\[1pt] \bullet \ (\mathtt{is\_type\_i\_no\_shift}) \cdot (\mathtt{op\_c11} \cdot (2^{8}-1) - \mathtt{c\_val}^{(4)}) = 0 \\[4pt] \end{array}

As op_c11\mathtt{op\_c11} is set to 0, the sign extension fills in 0 in the higher order bits of c_val\mathtt{c\_val}. In particular, the prover sets the values for the limbs for c_val\mathtt{c\_val} as below to ensure that the constraints are satisfied.

  • c_val(1)=0x03\mathtt{c\_val}^{(1)} =\mathtt{0x03}
  • c_val(2)=0x00\mathtt{c\_val}^{(2)} =\mathtt{0x00}
  • c_val(3)=0x00\mathtt{c\_val}^{(3)} =\mathtt{0x00}
  • c_val(4)=0x00\mathtt{c\_val}^{(4)} = \mathtt{0x00}
  1. Checking the format of the instruction
/ ⁣ ⁣/Checking instruction format for limb 1 (is_alu_imm_no_shift)(0b0010011+op_a027instr_val(1))=0/ ⁣ ⁣/Checking instruction format for limb 2 (is_add)(imm_c)(op_a1_4+0b00024+op_b_027instr_val(2))=0/ ⁣ ⁣/Checking instruction format for limb 3 (is_type_i_no_shift)(op_b1_4+op_c0_324instr_val(3))=0/ ⁣ ⁣/Checking instruction format for limb 4 (is_type_i_no_shift)(op_c4_7+op_c8_1024+op_c1127instr_val(4))=0\small \begin{array}{l} {/\!\!/\, \texttt{Checking instruction format for limb 1}} \\[1pt] \bullet \ (\mathtt{is\_alu\_imm\_no\_shift}) \cdot (\mathtt{0b0010011} + \mathtt{op\_a0} \cdot 2^{7} - \mathtt{instr\_val}^{(1)}) = 0 \\[4pt] {/\!\!/\, \texttt{Checking instruction format for limb 2}} \\[1pt] \bullet \ (\mathtt{is\_add}) \cdot (\mathtt{imm\_c}) \cdot (\mathtt{op\_a1\_4} + \mathtt{0b000} \cdot 2^{4} + \mathtt{op\_b\_0} \cdot 2^{7} - \mathtt{instr\_val}^{(2)}) = 0 \\[4pt] {/\!\!/\, \texttt{Checking instruction format for limb 3}} \\[1pt] \bullet \ (\mathtt{is\_type\_i\_no\_shift}) \cdot (\mathtt{op\_b1\_4} + \mathtt{op\_c0\_3} \cdot 2^{4} - \mathtt{instr\_val}^{(3)}) = 0 \\[4pt] {/\!\!/\, \texttt{Checking instruction format for limb 4}} \\[1pt] \bullet \ (\mathtt{is\_type\_i\_no\_shift}) \cdot (\mathtt{op\_c4\_7} + \mathtt{op\_c8\_10} \cdot 2^{4} + \mathtt{op\_c11} \cdot 2^{7} - \mathtt{instr\_val}^{(4)}) = 0 \\[4pt] \end{array}

With is_type_i_no_shift\mathtt{is\_type\_i\_no\_shift}, is_alu_imm_no_shift\mathtt{is\_alu\_imm\_no\_shift}, is_add\mathtt{is\_add} and imm_c\mathtt{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\mathtt{x8}

In order to read the contents of register op_b=x8\mathtt{op\_b}=\mathtt{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\mathtt{Read}_{Reg} interface with parameters (op_b,clk,1)(\mathtt{op\_b}, \mathtt{clk},1), where 11 indicates that this is the source register reg1\mathtt{reg1}, to obtain the value b_val\mathtt{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\mathtt{op\_b}, clk\mathtt{clk}, b_val\mathtt{b\_val}, reg1_addr\mathtt{reg1\_addr}, and reg1_val_cur\mathtt{reg1\_val\_cur} are shared between the CPU and the register memory components.

As a result of this interaction, reg1_addr\mathtt{reg1\_addr} will be set to op_b\mathtt{op\_b}. Moreover, the value of the limbs for b_val\mathtt{b\_val} will be set to the limbs of reg1_val_cur\mathtt{reg1\_val\_cur}:

  • b_val(1)\mathtt{{b\_val}^{(1)}} = reg1_val_cur(1)\mathtt{{reg1\_val\_cur}^{(1)}} = 0xFF\mathtt{0xFF}
  • b_val(2)\mathtt{{b\_val}^{(2)}} = reg1_val_cur(2)\mathtt{{reg1\_val\_cur}^{(2)}} = 0x00\mathtt{0x00}
  • b_val(3)\mathtt{{b\_val}^{(3)}} = reg1_val_cur(3)\mathtt{{reg1\_val\_cur}^{(3)}} = 0x00\mathtt{0x00}
  • b_val(4)\mathtt{{b\_val}^{(4)}} = reg1_val_cur(4)\mathtt{{reg1\_val\_cur}^{(4)}} = 0x00\mathtt{0x00}

The values of the 4 limbs of b_val\mathtt{b\_val} follow from the fact that, by assumption, register op_b=x8\mathtt{op\_b}=\mathtt{x8} contains 0x00000000FF\mathtt{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\mathtt{exec} interface with parameters (pc,opcode,a_val,b_val,c_val)(\mathtt{pc}, \mathtt{opcode},\mathtt{a\_val},\mathtt{b\_val},\mathtt{c\_val}) to obtain the value pc_next\mathtt{pc\_next}. Since this is an ADD operation, the execution component also updates the value of a_val\mathtt{a\_val}.

In the actual implementation, this interface is not explicitly implemented since the trace columns for pc\mathtt{pc}, opcode\mathtt{opcode}, a_val\mathtt{a\_val}, b_val\mathtt{b\_val}, c_val\mathtt{c\_val}, and pc_next\mathtt{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\mathtt{a\_val} pc_next\mathtt{pc\_next} will be updated as follows:

  • a_val(1)\mathtt{{a\_val}^{(1)}} = 0x02\mathtt{0x02}
  • a_val(2)\mathtt{{a\_val}^{(2)}} = 0x01\mathtt{0x01}
  • a_val(3)\mathtt{{a\_val}^{(3)}} = 0x00\mathtt{0x00}
  • a_val(4)\mathtt{{a\_val}^{(4)}} = 0x00\mathtt{0x00}
  • pc_next(1)\mathtt{{pc\_next}^{(1)}} = 0x08\mathtt{0x08}
  • pc_next(2)\mathtt{{pc\_next}^{(2)}} = 0x00\mathtt{0x00}
  • pc_next(3)\mathtt{{pc\_next}^{(3)}} = 0x00\mathtt{0x00}
  • pc_next(4)\mathtt{{pc\_next}^{(4)}} = 0x00\mathtt{0x00}

The values of the 4 limbs of a_val\mathtt{a\_val} follow from the fact that b_val=0x000000FF\mathtt{b\_val}=\mathtt{0x000000FF} and c_val=0x00000003\mathtt{c\_val}=\mathtt{0x00000003}. While the value of b_val\mathtt{b\_val} is based on current state of the virtual machine at the current clock cycle, c_val\mathtt{c\_val} follows from the sign extension of op_c=3\mathtt{op\_c}=3.

The values of the 4 limbs of pc_next\mathtt{pc\_next} follow from the fact that pc=0x00000004\mathtt{pc}=\mathtt{0x00000004} gets incremented by 44 after an ADD instruction.

Updating the contents of register x10\mathtt{x10}

In order to update the contents of register op_a=x10\mathtt{op\_a}=\mathtt{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\mathtt{x0} remains 00. For that, the CPU component uses an auxiliary value a_val_effective\mathtt{a\_val\_effective}, which is supposed to be equal to a_val\mathtt{a\_val} whenever op_a0\mathtt{op\_a} \not= 0 and 00 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_a0/ ⁣ ⁣/a_val_effective_flag=0 indicates op_a=0 op_aa_val_effective_flag_aux=a_val_effective_flag/ ⁣ ⁣/Ensuring a_val_effective_flag_aux0 a_val_effective_flag_auxa_val_effective_flag_aux_inv=1/ ⁣ ⁣/Enforcing a_val_effective_flag{0,1} (a_val_effective_flag)(1a_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)\small \begin{array}{l} {/\!\!/\, \texttt{Determining } \mathtt{a\_val\_effective} \texttt{ from } \mathtt{op\_a}} \\[1pt] {/\!\!/\, \mathtt{a\_val\_effective\_flag} \texttt{ is an auxiliary flag}} \\[1pt] {/\!\!/\, \mathtt{a\_val\_effective\_flag\_\{aux,aux\_inv\}} \texttt{ are non-zero auxiliary variables}} \\[1pt] {/\!\!/\, \mathtt{a\_val\_effective\_flag = 1} \texttt{ indicates } \mathtt{op\_a \not= 0}} \\[1pt] {/\!\!/\, \mathtt{a\_val\_effective\_flag = 0} \texttt{ indicates } \mathtt{op\_a = 0}} \\[1pt] \bullet \ \mathtt{op\_a} \cdot \mathtt{a\_val\_effective\_flag\_aux} = \mathtt{a\_val\_effective\_flag} \\[4pt] {/\!\!/\, \texttt{Ensuring } \mathtt{a\_val\_effective\_flag\_aux \not= 0}} \\[1pt] \bullet \ \mathtt{a\_val\_effective\_flag\_aux} \cdot \mathtt{a\_val\_effective\_flag\_aux\_inv} = 1 \\[4pt] {/\!\!/\, \texttt{Enforcing } \mathtt{a\_val\_effective\_flag} \in \{0,1\}} \\[1pt] \bullet \ (\mathtt{a\_val\_effective\_flag}) \cdot (1-\mathtt{a\_val\_effective\_flag}) = 0 \\[4pt] {/\!\!/\, \texttt{Enforcing relation between } \mathtt{a\_val} \texttt{ and } \mathtt{a\_val\_effective}} \\[1pt] \bullet \ \mathtt{a\_val^{(1)}} \cdot \mathtt{a\_val\_effective\_flag} = \mathtt{a\_val\_effective^{(1)}} \\%[4pt] \bullet \ \mathtt{a\_val^{(2)}} \cdot \mathtt{a\_val\_effective\_flag} = \mathtt{a\_val\_effective^{(2)}} \\%[4pt] \bullet \ \mathtt{a\_val^{(3)}} \cdot \mathtt{a\_val\_effective\_flag} = \mathtt{a\_val\_effective^{(3)}} \\%[4pt] \bullet \ \mathtt{a\_val^{(4)}} \cdot \mathtt{a\_val\_effective\_flag} = \mathtt{a\_val\_effective^{(4)}} \\[4pt] \end{array}

Since op_a=x10\mathtt{op\_a} = \mathtt{x10}, the following must be true:

  • a_val_effective_flag\mathtt{a\_val\_effective\_flag} = 11
  • a_val_effective_flag_aux\mathtt{a\_val\_effective\_flag\_aux} = 1/101/10
  • a_val_effective_flag_aux_inv\mathtt{a\_val\_effective\_flag\_aux\_inv} = 1010
  • a_val_effective(1)\mathtt{{a\_val\_effective}^{(1)}} = a_val(1)\mathtt{{a\_val}^{(1)}} = 0x02\mathtt{0x02}
  • a_val_effective(2)\mathtt{{a\_val\_effective}^{(2)}} = a_val(2)\mathtt{{a\_val}^{(2)}} = 0x01\mathtt{0x01}
  • a_val_effective(3)\mathtt{{a\_val\_effective}^{(3)}} = a_val(3)\mathtt{{a\_val}^{(3)}} = 0x00\mathtt{0x00}
  • a_val_effective(4)\mathtt{{a\_val\_effective}^{(4)}} = a_val(4)\mathtt{{a\_val}^{(4)}} = 0x00\mathtt{0x00}

Next, the CPU component must interact with the register memory component to update the contents of register op_a=x10\mathtt{op\_a} = \mathtt{x10} with the value a_val_effective\mathtt{a\_val\_effective}.

In the specification, the interaction with the register memory is captured by a call to the WriteReg\mathtt{Write}_{Reg} interface with parameters (op_a,a_val_effective,clk,3)(\mathtt{op\_a}, \mathtt{a\_val\_effective},\mathtt{clk},3), where 33 indicates that this is the destination register reg3\mathtt{reg3}, to write the value a_val_effective\mathtt{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\mathtt{op\_a}, clk\mathtt{clk}, a_val_effective\mathtt{a\_val\_effective}, reg3_addr\mathtt{reg3\_addr}, and reg3_val_cur\mathtt{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\mathtt{reg3\_val\_cur} associated with address reg3_addr=op_a=x10\mathtt{reg3\_addr}=\mathtt{op\_a} = \mathtt{x10} will be updated as follows:

  • reg3_val_cur(1)\mathtt{{reg3\_val\_cur}^{(1)}} = a_val_effective(1)\mathtt{{a\_val\_effective}^{(1)}} = 0x02\mathtt{0x02}
  • reg3_val_cur(2)\mathtt{{reg3\_val\_cur}^{(2)}} = a_val_effective(2)\mathtt{{a\_val\_effective}^{(2)}} = 0x01\mathtt{0x01}
  • reg3_val_cur(3)\mathtt{{reg3\_val\_cur}^{(3)}} = a_val_effective(3)\mathtt{{a\_val\_effective}^{(3)}} = 0x00\mathtt{0x00}
  • reg3_val_cur(4)\mathtt{{reg3\_val\_cur}^{(4)}} = a_val_effective(4)\mathtt{{a\_val\_effective}^{(4)}} = 0x00\mathtt{0x00}

Execution Component Trace Columns and Constraints

In order to verify the correct execution of the ADDI x10 x8 3 instruction at clock cycle 256256, 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)28op_b_val(1)op_c_val(1))=0 (is_add)(op_a_val(2)+h_carry(2)28op_b_val(2)op_c_val(2)h_carry(1))=0 (is_add)(op_a_val(3)+h_carry(3)28op_b_val(3)op_c_val(3)h_carry(2))=0 (is_add)(op_a_val(4)+h_carry(4)28op_b_val(4)op_c_val(4)h_carry(3))=0/ ⁣ ⁣/Enforcing that helper carries are binary (is_add)(h_carry(1))(1h_carry(1))=0 (is_add)(h_carry(2))(1h_carry(2))=0 (is_add)(h_carry(3))(1h_carry(3))=0 (is_add)(h_carry(4))(1h_carry(4))=0\small \begin{array}{l} {/\!\!/\, \texttt{Carry handling for the add instruction}} \\[1pt] \bullet \ (\mathtt{is\_add}) \cdot \left( \mathtt{op\_a\_val}^{(1)} + \mathtt{h\_carry}^{(1)} \cdot 2^{8} - \mathtt{op\_b\_val}^{(1)} - \mathtt{op\_c\_val}^{(1)} \right) = 0 \\[1pt] \bullet \ (\mathtt{is\_add}) \cdot \left( \mathtt{op\_a\_val}^{(2)} + \mathtt{h\_carry}^{(2)} \cdot 2^{8} - \mathtt{op\_b\_val}^{(2)} - \mathtt{op\_c\_val}^{(2)} - \mathtt{h\_carry}^{(1)} \right) = 0 \\[1pt] \bullet \ (\mathtt{is\_add}) \cdot \left( \mathtt{op\_a\_val}^{(3)} + \mathtt{h\_carry}^{(3)} \cdot 2^{8} - \mathtt{op\_b\_val}^{(3)} - \mathtt{op\_c\_val}^{(3)} - \mathtt{h\_carry}^{(2)} \right) = 0 \\[1pt] \bullet \ (\mathtt{is\_add}) \cdot \left( \mathtt{op\_a\_val}^{(4)} + \mathtt{h\_carry}^{(4)} \cdot 2^{8} - \mathtt{op\_b\_val}^{(4)} - \mathtt{op\_c\_val}^{(4)} - \mathtt{h\_carry}^{(3)} \right) = 0 \\[4pt] {/\!\!/\, \texttt{Enforcing that helper carries are binary}} \\[1pt] \bullet \ (\mathtt{is\_add}) \cdot \left( \mathtt{h\_carry}^{(1)} \right) \cdot \left(1 - \mathtt{h\_carry}^{(1)}\right) = 0 \\[1pt] \bullet \ (\mathtt{is\_add}) \cdot \left( \mathtt{h\_carry}^{(2)} \right) \cdot \left(1 - \mathtt{h\_carry}^{(2)}\right) = 0 \\[1pt] \bullet \ (\mathtt{is\_add}) \cdot \left( \mathtt{h\_carry}^{(3)} \right) \cdot \left(1 - \mathtt{h\_carry}^{(3)}\right) = 0 \\[1pt] \bullet \ (\mathtt{is\_add}) \cdot \left( \mathtt{h\_carry}^{(4)} \right) \cdot \left(1 - \mathtt{h\_carry}^{(4)}\right) = 0 \\[4pt] \end{array}

Since b_val=0x000000FF\mathtt{b\_val} = \mathtt{0x000000FF} and c_val=0x00000003\mathtt{c\_val} = \mathtt{0x00000003}, in order to satisfy the set of constraints above, it must be the case that:

  • a_val(1)\mathtt{{a\_val}^{(1)}} = 0x02\mathtt{0x02}
  • a_val(2)\mathtt{{a\_val}^{(2)}} = 0x01\mathtt{0x01}
  • a_val(3)\mathtt{{a\_val}^{(3)}} = 0x00\mathtt{0x00}
  • a_val(4)\mathtt{{a\_val}^{(4)}} = 0x00\mathtt{0x00}
  • h_carry(1)\mathtt{{h\_carry}^{(1)}} = 11
  • h_carry(2)\mathtt{{h\_carry}^{(2)}} = 00
  • h_carry(3)\mathtt{{h\_carry}^{(3)}} = 00
  • h_carry(4)\mathtt{{h\_carry}^{(4)}} = 00

Next, the execution component checks whether this instruction is one of those for which pc\mathtt{pc} gets incremented by 44 (which is the case for ADDI\texttt{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(1is_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)284)=0 (is_pc_inc_std)(pc_next(3)+pc_next(4)28+pc_carry(2)216   pc(3)pc(4)28pc_carry(1))=0/ ⁣ ⁣/Ensuring pc_carry is binary (is_pc_inc_std)(pc_carry(1))(1pc_carry(1))=0 (is_pc_inc_std)(pc_carry(2))(1pc_carry(2))=0\small \begin{array}{l} {/\!\!/\, \texttt{Check if instruction is one that pc is incremented}} \\[1pt] \bullet \ (\mathtt{is\_alu} + \mathtt{is\_load} + \mathtt{is\_type\_s} + \mathtt{is\_type\_u} + \\[1pt] \ \ \ \mathtt{is\_type\_sys} \cdot (1 - \mathtt{is\_sys\_halt}) - \mathtt{is\_pc\_inc\_std}) = 0 \\[4pt] {/\!\!/\, \texttt{pc is incremented by 4 handling two limbs at a time}} \\[1pt] {/\!\!/\, \mathtt{pc\_carry} \texttt{ is used to keep track of carries}} \\[1pt] \bullet \ (\mathtt{is\_pc\_inc\_std}) \cdot (\mathtt{pc\_next}^{(1)} + \mathtt{pc\_next}^{(2)} \cdot 2^{8} + \mathtt{pc\_carry}^{(1)} \cdot 2^{16} \\[1pt] \ \ \ - \mathtt{pc}^{(1)} - \mathtt{pc}^{(2)} \cdot 2^{8} - 4) = 0 \\[1pt] \bullet \ (\mathtt{is\_pc\_inc\_std}) \cdot (\mathtt{pc\_next}^{(3)} + \mathtt{pc\_next}^{(4)} \cdot 2^{8} + \mathtt{pc\_carry}^{(2)} \cdot 2^{16} \\[1pt] \ \ \ - \mathtt{pc}^{(3)} - \mathtt{pc}^{(4)} \cdot 2^{8} - \mathtt{pc\_carry}^{(1)}) = 0 \\[4pt] {/\!\!/\, \texttt{Ensuring } \mathtt{pc\_carry} \texttt{ is binary}} \\[1pt] \bullet \ (\mathtt{is\_pc\_inc\_std}) \cdot \left( \mathtt{pc\_carry}^{(1)} \right) \cdot \left(1 - \mathtt{pc\_carry}^{(1)}\right) = 0 \\[1pt] \bullet \ (\mathtt{is\_pc\_inc\_std}) \cdot \left( \mathtt{pc\_carry}^{(2)} \right) \cdot \left(1 - \mathtt{pc\_carry}^{(2)}\right) = 0 \\[4pt] \end{array}

Since pc=0x00000004\mathtt{pc} = \mathtt{0x00000004}, it must be the case that carries pc_next\mathtt{pc\_next} should be set as follows:

  • pc_next(1)\mathtt{{pc\_next}^{(1)}} = 0x08\mathtt{0x08}
  • pc_next(2)\mathtt{{pc\_next}^{(2)}} = 0x00\mathtt{0x00}
  • pc_next(3)\mathtt{{pc\_next}^{(3)}} = 0x00\mathtt{0x00}
  • pc_next(4)\mathtt{{pc\_next}^{(4)}} = 0x00\mathtt{0x00}
  • pc_carry(1)\mathtt{{pc\_carry}^{(1)}} = 00
  • pc_carry(2)\mathtt{{pc\_carry}^{(2)}} = 00

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\mathtt{pc}: the word-aligned base address associated with a program instruction
  • instr_val(1)\mathtt{{instr\_val}^{(1)}}: bits 0-7 of the instruction word instr_val\mathtt{{instr\_val}} stored at address pc\mathtt{pc}
  • instr_val(2)\mathtt{{instr\_val}^{(2)}}: bits 8-15 of the instruction word instr_val\mathtt{{instr\_val}} stored at address pc+1\mathtt{pc}+1
  • instr_val(3)\mathtt{{instr\_val}^{(3)}}: bits 16-23 of the instruction word instr_val\mathtt{{instr\_val}} stored at address pc+2\mathtt{pc}+2
  • instr_val(4)\mathtt{{instr\_val}^{(4)}}: bits 24-31 of the instruction word instr_val\mathtt{{instr\_val}} stored at address pc+3\mathtt{pc}+3
  • prog_ctr_prev\mathtt{prog\_ctr\_prev}: 4 limbs for the previous counter value associated with base address pc\mathtt{pc}
  • prog_ctr_cur\mathtt{prog\_ctr\_cur}: 4 limbs for the current counter value associated with base address pc\mathtt{pc}
  • prog_read_digest\mathtt{prog\_read\_digest}: a digest of the read set, used for logups
  • prog_write_digest\mathtt{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)+1prog_ctr_carry(1)28prog_ctr_cur(1) prog_ctr_prev(2)+prog_ctr_carry(1)prog_ctr_carry(2)28prog_ctr_cur(2) prog_ctr_prev(3)+prog_ctr_carry(2)prog_ctr_carry(3)28prog_ctr_cur(3) prog_ctr_prev(4)+prog_ctr_carry(3)prog_ctr_carry(4)28prog_ctr_cur(4)/ ⁣ ⁣/Enforcing prog_ctr_carry(j){0,1} for j=1,2,3,4 (prog_ctr_carry(1))(1prog_ctr_carry(1))=0 (prog_ctr_carry(2))(1prog_ctr_carry(2))=0 (prog_ctr_carry(3))(1prog_ctr_carry(3))=0 (prog_ctr_carry(4))(1prog_ctr_carry(4))=0\small \begin{array}{l} {/\!\!/\, \texttt{Enforcing } \mathtt{prog\_ctr\_cur} = \mathtt{prog\_ctr\_prev} + 1} \\[1pt] {/\!\!/\, \mathtt{prog\_ctr\_carry} \texttt{ used for carry handling}} \\[1pt] \bullet \ \mathtt{{prog\_ctr\_prev}^{(1)}} + 1 - \mathtt{{prog\_ctr\_carry}^{(1)}} \cdot 2^{8} - \mathtt{{prog\_ctr\_cur}^{(1)}} \\%[4pt] \bullet \ \mathtt{{prog\_ctr\_prev}^{(2)}} + \mathtt{{prog\_ctr\_carry}^{(1)}} - \mathtt{{prog\_ctr\_carry}^{(2)}} \cdot 2^{8} - \mathtt{{prog\_ctr\_cur}^{(2)}} \\%[4pt] \bullet \ \mathtt{{prog\_ctr\_prev}^{(3)}} + \mathtt{{prog\_ctr\_carry}^{(2)}} - \mathtt{{prog\_ctr\_carry}^{(3)}} \cdot 2^{8} - \mathtt{{prog\_ctr\_cur}^{(3)}} \\%[4pt] \bullet \ \mathtt{{prog\_ctr\_prev}^{(4)}} + \mathtt{{prog\_ctr\_carry}^{(3)}} - \mathtt{{prog\_ctr\_carry}^{(4)}} \cdot 2^{8} - \mathtt{{prog\_ctr\_cur}^{(4)}} \\[4pt] {/\!\!/\, \texttt{Enforcing } \mathtt{{prog\_ctr\_carry}^{(j)}} \in \{0,1\} \texttt{ for } j=1,2,3,4} \\[1pt] \bullet \ (\mathtt{{prog\_ctr\_carry}^{(1)}}) \cdot (1-\mathtt{{prog\_ctr\_carry}^{(1)}}) = 0 \\%[4pt] \bullet \ (\mathtt{{prog\_ctr\_carry}^{(2)}}) \cdot (1-\mathtt{{prog\_ctr\_carry}^{(2)}}) = 0 \\%[4pt] \bullet \ (\mathtt{{prog\_ctr\_carry}^{(3)}}) \cdot (1-\mathtt{{prog\_ctr\_carry}^{(3)}}) = 0 \\%[4pt] \bullet \ (\mathtt{{prog\_ctr\_carry}^{(4)}}) \cdot (1-\mathtt{{prog\_ctr\_carry}^{(4)}}) = 0 \\[4pt] \end{array}

Since Prog[0x00000004]Prog[\mathtt{0x00000004}] has been accessed 22 times before the current clock cycle according to the initial assumption, we have:

  • prog_ctr_prev(1)=2\mathtt{{prog\_ctr\_prev}^{(1)}}=2
  • prog_ctr_prev(2)=0\mathtt{{prog\_ctr\_prev}^{(2)}}=0
  • prog_ctr_prev(3)=0\mathtt{{prog\_ctr\_prev}^{(3)}}=0
  • prog_ctr_prev(4)=0\mathtt{{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\mathtt{{prog\_ctr\_cur}^{(1)}}=3
  • prog_ctr_cur(2)=0\mathtt{{prog\_ctr\_cur}^{(2)}}=0
  • prog_ctr_cur(3)=0\mathtt{{prog\_ctr\_cur}^{(3)}}=0
  • prog_ctr_cur(4)=0\mathtt{{prog\_ctr\_cur}^{(4)}}=0
  • prog_ctr_carry(1)=0\mathtt{{prog\_ctr\_carry}^{(1)}}=0
  • prog_ctr_carry(2)=0\mathtt{{prog\_ctr\_carry}^{(2)}}=0
  • prog_ctr_carry(3)=0\mathtt{{prog\_ctr\_carry}^{(3)}}=0
  • prog_ctr_carry(4)=0\mathtt{{prog\_ctr\_carry}^{(4)}}=0

Enforcing the Correct Update of Read- and Write-Set Digests

Let fp(pc,instr_val,prog_ctr)\mathtt{fp}(\mathtt{pc},\mathtt{instr\_val}, \mathtt{prog\_ctr}) denote a fingerprint function which takes as input the tuple (pc(1)(\mathtt{{pc}^{(1)}}, \ldots, pc(4)\mathtt{{pc}^{(4)}}, instr_val(1)\mathtt{{instr\_val}^{(1)}}, \ldots, instr_val(4)\mathtt{{instr\_val}^{(4)}}, prog_ctr(1)\mathtt{{prog\_ctr}^{(1)}}, \ldots, prog_ctr(4))\mathtt{{prog\_ctr}^{(4)}}) and returns a field element in the secure extension field used by Stwo\mathtt{Stwo} using a random value β\beta 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(\mathtt{pc}, instr_val\mathtt{instr\_val}, prog_ctr_prev)\mathtt{prog\_ctr\_prev}) gets added to the read set digest and that the logup contribution associated with the entry (pc(\mathtt{pc}, instr_val\mathtt{instr\_val}, prog_ctr_cur)\mathtt{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 α\alpha is a random value chosen by the verifier and i>0i>0 is the row index:

 prog_read_digest[i]prog_read_digest[i1]=   1/(fp(pc[i],instr_val[i],prog_ctr_prev[i])+α) prog_write_digest[i]prog_write_digest[i1]=   1/(fp(pc[i],instr_val[i],prog_ctr_cur[i])+α).\small \begin{array}{l} \bullet \ \mathtt{prog\_read\_digest}[i] - \mathtt{prog\_read\_digest}[i-1] = \\[1pt] \ \ \ {1} / {(\mathtt{fp}(\mathtt{pc}[i],\mathtt{instr\_val}[i],\mathtt{prog\_ctr\_prev}[i])+\alpha)} \\[1pt] \bullet \ \mathtt{prog\_write\_digest}[i] - \mathtt{prog\_write\_digest}[i-1] = \\[1pt] \ \ \ {1} / {(\mathtt{fp}(\mathtt{pc}[i], \mathtt{instr\_val}[i], \mathtt{prog\_ctr\_cur}[i])+\alpha)}.\\[1pt] \end{array}

As stated before,

  • pc(1)[255]=0x04\mathtt{{pc}^{(1)}}[255]=0x04
  • pc(2)[255]=0x00\mathtt{{pc}^{(2)}}[255]=0x00
  • pc(3)[255]=0x00\mathtt{{pc}^{(3)}}[255]=0x00
  • pc(4)[255]=0x00\mathtt{{pc}^{(4)}}[255]=0x00
  • instr_val(1)[255]\mathtt{{instr\_val}^{(1)}}[255] = Prog[0x00000004]Prog[\mathtt{0x00000004}] = 0b00010011\mathtt{0b00010011}
  • instr_val(2)[255]\mathtt{{instr\_val}^{(2)}}[255] = Prog[0x00000005]Prog[\mathtt{0x00000005}] = 0b00000101\mathtt{0b00000101}
  • instr_val(3)[255]\mathtt{{instr\_val}^{(3)}}[255] = Prog[0x00000006]Prog[\mathtt{0x00000006}] = 0b00110100\mathtt{0b00110100}
  • instr_val(4)[255]\mathtt{{instr\_val}^{(4)}}[255] = Prog[0x00000007]Prog[\mathtt{0x00000007}] = 0b00000000\mathtt{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])+α).\small \begin{array}{l} \bullet \ \mathtt{prog\_read\_digest}[255] - \mathtt{prog\_read\_digest}[254] = \\[1pt] \ \ \ {1} / {(\mathtt{fp}(\mathtt{pc}[255],\mathtt{instr\_val}[255],\mathtt{prog\_ctr\_prev}[255])+\alpha)} \\[1pt] \bullet \ \mathtt{prog\_write\_digest}[255] - \mathtt{prog\_write\_digest}[254] = \\[1pt] \ \ \ {1} / {(\mathtt{fp}(\mathtt{pc}[255], \mathtt{instr\_val}[255], \mathtt{prog\_ctr\_cur}[255])+\alpha)}.\\[1pt] \end{array}

Remark: In addition to the above specified constraints, the limbs for instr_val\mathtt{instr\_val}, prog_ctr_prev\mathtt{prog\_ctr\_prev} and prog_ctr_curv\mathtt{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(\mathtt{reg\_addr}, reg_val\mathtt{reg\_val}, reg_ts)\mathtt{reg\_ts}) indicating that the value reg_val\mathtt{reg\_val} was written to address (reg_addr(\mathtt{reg\_addr} at time reg_ts\mathtt{reg\_ts}.

Hence, to properly handle an access to a register address, one needs to maintain a set (reg_addr(\mathtt{reg\_addr}, reg_val_prev\mathtt{reg\_val\_prev}, reg_val_cur\mathtt{reg\_val\_cur}, reg_ts_prev\mathtt{reg\_ts\_prev}, reg_ts_cur)\mathtt{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\mathtt{clk}: the current execution time
  • reg1_addr\mathtt{reg1\_addr}, reg2_addr\mathtt{reg2\_addr}, reg3_addr\mathtt{reg3\_addr}: register addresses
  • reg1_val_cur\mathtt{reg1\_val\_cur}, reg2_val_cur\mathtt{reg2\_val\_cur}, reg3_val_cur\mathtt{reg3\_val\_cur}: 32-bit values used to update register contents
  • reg1_ts_cur\mathtt{reg1\_ts\_cur}, reg2_ts_cur\mathtt{reg2\_ts\_cur}, reg3_ts_cur\mathtt{reg3\_ts\_cur}: current timestamps for the registers
  • reg1_val_prev\mathtt{reg1\_val\_prev}, reg2_val_prev\mathtt{reg2\_val\_prev}, reg3_val_prev\mathtt{reg3\_val\_prev}: previous 32-bit values stored at the registers
  • reg1_ts_prev\mathtt{reg1\_ts\_prev}, reg2_ts_prev\mathtt{reg2\_ts\_prev}, reg3_ts_prev\mathtt{reg3\_ts\_prev}: previous timestamps for the registers
  • reg_read_digest\mathtt{reg\_read\_digest}: a digest of the read set, used for logups.
  • reg_write_digest\mathtt{reg\_write\_digest}: a digest of the write set, used for logups.
  • reg1_accessed\mathtt{reg1\_accessed}, reg2_accessed\mathtt{reg2\_accessed}, reg3_accessed\mathtt{reg3\_accessed}: flags indicating whether the set of trace elements (regj_addr(\mathtt{reg}j\mathtt{\_addr}, regj_val_prev\mathtt{reg}j\mathtt{\_val\_prev}, regj_val_cur\mathtt{reg}j\mathtt{\_val\_cur}, regj_ts_prev\mathtt{reg}j\mathtt{\_ts\_prev}, regj_ts_cur)\mathtt{reg}j\mathtt{\_ts\_cur}) for j=1,2,3j=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:

  1. it ensures that the current timestamps associated for reg1_addr\mathtt{reg1\_addr}, reg2_addr\mathtt{reg2\_addr}, reg3_addr\mathtt{reg3\_addr} satisfy the following constraints:
  • reg1_ts_cur=3clk2\mathtt{reg1\_ts\_cur} = 3 \cdot \mathtt{clk} - 2
  • reg2_ts_cur=3clk1\mathtt{reg2\_ts\_cur} = 3 \cdot \mathtt{clk} - 1
  • reg3_ts_cur=3clk\mathtt{reg3\_ts\_cur} = 3 \cdot \mathtt{clk}
  1. it checks that the previous timestamps associated with the addresses being accessed preceed their current timestamps. That is,
  • reg1_ts_prev{0,,reg1_ts_cur1}\mathtt{reg1\_ts\_prev} \in \{0,\ldots,\mathtt{reg1\_ts\_cur-1}\}
  • reg2_ts_prev{0,,reg2_ts_cur1}\mathtt{reg2\_ts\_prev} \in \{0,\ldots,\mathtt{reg2\_ts\_cur-1}\}
  • reg3_ts_prev{0,,reg3_ts_cur1}\mathtt{reg3\_ts\_prev} \in \{0,\ldots,\mathtt{reg3\_ts\_cur-1}\}
  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\mathtt{reg1\_addr}, reg2_addr\mathtt{reg2\_addr}, reg3_addr\mathtt{reg3\_addr} should be accessed in this order and only reg3_addr\mathtt{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)\mathtt{fp}(\mathtt{reg\_addr},\mathtt{reg\_val}, \mathtt{reg\_ts}) denote a fingerprint function which takes as input the tuple (reg_addr(\mathtt{reg\_addr}, reg_val(1)\mathtt{{reg\_val}^{(1)}}, \ldots, reg_val(4)\mathtt{{reg\_val}^{(4)}}, reg_ts(1)\mathtt{{reg\_ts}^{(1)}}, \ldots, reg_ts(4))\mathtt{{reg\_ts}^{(4)}}) and returns a field element in the secure extension field used by Stwo\mathtt{Stwo} using a random value β\beta 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\mathtt{reg\_addr} is accessed in a clock cycle, the logup contribution associated with the entry (reg_addr(\mathtt{reg\_addr}, reg_val\mathtt{reg\_val}, reg_ts_prev)\mathtt{reg\_ts\_prev}) must be added to the read set digest and that the logup contribution associated with the entry (reg_addr(\mathtt{reg\_addr}, reg_val\mathtt{reg\_val}, reg_ts_cur)\mathtt{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 α\alpha is a random value chosen by the verifier and i>0i>0 is the row index:

 reg_read_digest[i]reg_read_digest[i1]=   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[i1]=   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])+α).\small \begin{array}{l} \bullet \ \mathtt{reg\_read\_digest}[i] - \mathtt{reg\_read\_digest}[i-1] = \\ \ \ \ {\mathtt{reg1\_accessed}[i]} / {(\mathtt{fp}(\mathtt{reg1\_addr}[i],\mathtt{reg1\_val}[i],\mathtt{reg1\_ts\_prev}[i])+\alpha)} \ + \\[1pt] \ \ \ {\mathtt{reg2\_accessed}[i]} / {(\mathtt{fp}(\mathtt{reg2\_addr}[i],\mathtt{reg2\_val}[i],\mathtt{reg2\_ts\_prev}[i])+\alpha)} \ + \\[1pt] \ \ \ {\mathtt{reg3\_accessed}[i]} / {(\mathtt{fp}(\mathtt{reg3\_addr}[i],\mathtt{reg3\_val}[i],\mathtt{reg3\_ts\_prev}[i])+\alpha)} \\[1pt] \bullet \ \mathtt{reg\_write\_digest}[i] - \mathtt{reg\_write\_digest}[i-1] = \\ \ \ \ {\mathtt{reg1\_accessed}[i]} / {(\mathtt{fp}(\mathtt{reg1\_addr}[i], \mathtt{reg1\_val}[i], \mathtt{reg1\_ts\_cur}[i])+\alpha)} \ + \\[1pt] \ \ \ {\mathtt{reg2\_accessed}[i]} / {(\mathtt{fp}(\mathtt{reg2\_addr}[i], \mathtt{reg2\_val}[i], \mathtt{reg3\_ts\_cur}[i])+\alpha)} \ + \\[1pt] \ \ \ {\mathtt{reg3\_accessed}[i]} / {(\mathtt{fp}(\mathtt{reg3\_addr}[i], \mathtt{reg3\_val}[i], \mathtt{reg3\_ts\_cur}[i])+\alpha)}. \\[1pt] \end{array}

According to the assumptions used for the current example, we have

  • R[x8]=0x000000FFR[\mathtt{x8}] = \mathtt{0x000000FF} was last updated with timestamp 3232;and
  • R[x10]=0x00000005R[\mathtt{x10}] = \mathtt{0x00000005} was last updated with timestamp 77.

Moreover, based on the interactions with the other components and the constraints for the current timestamps, we also know the following:

  • clk[255]=256\mathtt{clk}[255] = 256
  • reg1_ts_cur[255]=32562=766\mathtt{reg1\_ts\_cur}[255] = 3 \cdot 256 - 2 = 766
  • reg3_ts_cur[255]=3256=768\mathtt{reg3\_ts\_cur}[255] = 3 \cdot 256 = 768
  • reg1_accessed[255]=1\mathtt{reg1\_accessed}[255] = 1
  • reg2_accessed[255]=0\mathtt{reg2\_accessed}[255] = 0
  • reg3_accessed[255]=1\mathtt{reg3\_accessed}[255] = 1
  • R[x10]R[\mathtt{x10}] gets updated to 0x00000102\mathtt{0x00000102} at the current clock cycle

Hence, to satisfy the logup constraints mentioned above for i=255i=255, the following must be true for the current clock cycle:

  • reg1_ts_prev(1)[255]=32\mathtt{{reg1\_ts\_prev}^{(1)}}[255]=32
  • reg1_ts_prev(2)[255]=0\mathtt{{reg1\_ts\_prev}^{(2)}}[255]=0
  • reg1_ts_prev(3)[255]=0\mathtt{{reg1\_ts\_prev}^{(3)}}[255]=0
  • reg1_ts_prev(4)[255]=0\mathtt{{reg1\_ts\_prev}^{(4)}}[255]=0
  • reg1_val_prev(1)[255]=reg1_val_cur(1)[255]=0xFF\mathtt{{reg1\_val\_prev}^{(1)}}[255]=\mathtt{{reg1\_val\_cur}^{(1)}}[255]=\mathtt{0xFF}
  • reg1_val_prev(2)[255]=reg1_val_cur(2)[255]=0x00\mathtt{{reg1\_val\_prev}^{(2)}}[255]=\mathtt{{reg1\_val\_cur}^{(2)}}[255]=\mathtt{0x00}
  • reg1_val_prev(3)[255]=reg1_val_cur(3)[255]=0x00\mathtt{{reg1\_val\_prev}^{(3)}}[255]=\mathtt{{reg1\_val\_cur}^{(3)}}[255]=\mathtt{0x00}
  • reg1_val_prev(4)[255]=reg1_val_cur(4)[255]=0x00\mathtt{{reg1\_val\_prev}^{(4)}}[255]=\mathtt{{reg1\_val\_cur}^{(4)}}[255]=\mathtt{0x00}
  • reg1_ts_cur(1)[255]=254\mathtt{{reg1\_ts\_cur}^{(1)}}[255] = 254
  • reg1_ts_cur(2)[255]=2\mathtt{{reg1\_ts\_cur}^{(2)}}[255] = 2
  • reg1_ts_cur(3)[255]=0\mathtt{{reg1\_ts\_cur}^{(3)}}[255] = 0
  • reg1_ts_cur(4)[255]=0\mathtt{{reg1\_ts\_cur}^{(4)}}[255] = 0
  • reg3_ts_prev(1)[255]=7\mathtt{{reg3\_ts\_prev}^{(1)}}[255]=7
  • reg3_ts_prev(2)[255]=0\mathtt{{reg3\_ts\_prev}^{(2)}}[255]=0
  • reg3_ts_prev(3)[255]=0\mathtt{{reg3\_ts\_prev}^{(3)}}[255]=0
  • reg3_ts_prev(4)[255]=0\mathtt{{reg3\_ts\_prev}^{(4)}}[255]=0
  • reg3_val_prev(1)[255]=0x05\mathtt{{reg3\_val\_prev}^{(1)}}[255]=\mathtt{0x05}
  • reg3_val_prev(2)[255]=0x00\mathtt{{reg3\_val\_prev}^{(2)}}[255]=\mathtt{0x00}
  • reg3_val_prev(3)[255]=0x00\mathtt{{reg3\_val\_prev}^{(3)}}[255]=\mathtt{0x00}
  • reg3_val_prev(4)[255]=0x00\mathtt{{reg3\_val\_prev}^{(4)}}[255]=\mathtt{0x00}
  • reg3_ts_cur(1)[255]=0\mathtt{{reg3\_ts\_cur}^{(1)}}[255]=0
  • reg3_ts_cur(2)[255]=3\mathtt{{reg3\_ts\_cur}^{(2)}}[255]=3
  • reg3_ts_cur(3)[255]=0\mathtt{{reg3\_ts\_cur}^{(3)}}[255]=0
  • reg3_ts_cur(4)[255]=0\mathtt{{reg3\_ts\_cur}^{(4)}}[255]=0
  • reg3_val_cur(1)[255]=0x02\mathtt{{reg3\_val\_cur}^{(1)}}[255]=\mathtt{0x02}
  • reg3_val_cur(2)[255]=0x01\mathtt{{reg3\_val\_cur}^{(2)}}[255]=\mathtt{0x01}
  • reg3_val_cur(3)[255]=0x00\mathtt{{reg3\_val\_cur}^{(3)}}[255]=\mathtt{0x00}
  • reg3_val_cur(4)[255]=0x00\mathtt{{reg3\_val\_cur}^{(4)}}[255]=\mathtt{0x00}