Vm Arithmetization

# Arithmetization of Ooty VM In the previous blog we discussed the different tables, why we need them, which registers they contain and various kind of constraints such as boundary, transition and the terminal constraints. Now, we will explore how to apply different type of constraints on different table and determine which tables satisfy which specific constraints. --- ## Constraints The two-stage constraint formation in which in first stage we define constraints for the base columns and in second stage we define constraints for the extension columns, in between these stages the verifier supplies random scalars such as $a, b, c, d, e, f,\alpha ,\beta ,\delta, \gamma, \eta$. ### ProcessorTable We have seen that processor table contain 7 base columns and 4 extension columns. 1. The **boundary constraints** for the base columns mandate that all registers, except for ci and ni, must be initialized to zero. In the extension columns, InstructionPermutation and MemoryPermutation begin with random initial values chosen by the prover. However, since these values must remain confidential, their validity is enforced using a difference constraint across tables. On the other hand, the InputEvaluation and OutputEvaluation columns start at zero, as there is no need to maintain secrecy or handle any symbols being read or written. 2. The **transition constraints** for the base columns are rather involved because they capture dependence on the instruction. Let ci be the variable representing the current instruction register ci in the current row. Then define the deselector polynomial for symbol a $\psi \in \Phi = \{[,], <, >, +, -, \cdot, ,,\} \quad \text{as} \quad \zeta_\psi(c_i) = c_i \prod_{\phi \in \Phi \setminus \{\psi\}} (c_i - \phi)$ This deselector polynomial evaluates to zero for any instruction other than $\psi$, but produces a nonzero value for $\psi$. Its usefulness lies in its ability to conditionally deactivate any AIR constraint it is multiplied with—specifically, when the current instruction differs from $\psi$. This approach enables us to focus solely on the AIR transition constraint polynomials that define the correct behavior under the assumption of a specific instruction. Finally, we multiply the resulting polynomials by the deselector polynomial to deactivate them whenever the assumption does not hold. 3. Another useful trick is to describe the transition constraints in [disjunctive normal form](https://en.wikipedia.org/wiki/Disjunctive_normal_form), also known as OR-of-ANDs. This form is useful because an OR of constraints corresponds to a multiplication of constraint polynomials. Keeping all these tricks in mind let's construct transition AIR for all the instructions. Let $clk$, $ip$, $ci$, $ni$, $mp$, $mv$, $inv$, $clk^*$, $ip^*$, $ci^*$, $ni^*$, $mp^*$, $mv^*$, $inv^*$ be the variables that capture two consecutive rows of base columns. Let futhermore **iszero** can be written as **1-$mv.inv$**, which takes the value 1 whenever mv is zero and 0 otherwise. Now, we will construct the transition constriants for all the instructions and all these equation staisfied when the left hand side evaluates to zero. * ci = [ : - jump if $mv = 0$ and skip two otherwise $(ip^*-ip-2).mv$ + $(ip^*-ni)$.**iszero** - memory pointer remains same **$mp^* - mp$** memory value remains same **$mv^* - mv$** * ci = ] : - jump if $m v \neq 0$ and skip two otherwise:$(ip^*-ip-2).$ **iszero** + $(ip^*-ni).mv$ - memory pointer remains same $mp^*-mp$ - memory value remains same $mv^*-mv$ * ci = > : - instruction pointer increments by one $ip^*-ip-1$ - memory pointer remains same $mp^*-mp-1$ - memory value is unconstrained. * ci = < : - instruction pointer increments by one $ip^*-ip-1$ - memory pointer remains same $mp^*-mp+1$ - memory value is unconstrained. * ci = + : - instruction pointer increments by one $ip^*-ip-1$ - memory pointer remains same $mp^*-mp$ - memory value increments by one $mv^*-mv-1$ * ci = - : - instruction pointer increments by one $ip^*-ip-1$ - memory pointer remains same $mp^*-mp$ - memory value decrements by one $mv^*-mv+1$ * ci = , : - instruction pointer increments by one $ip^*-ip-1$ - memory pointer remains same $mp^*-mp$ - memory value is unconstrained. * ci = . : - instruction pointer increments by one $ip^*-ip-1$ - memory pointer remains same $mp^*-mp$ - memory value remains same $mv^*-mv$ In addition to the above constraints, there are some constraints that do not depend on the current instruction $ci$. * clock increases by one $clk^*-clk-1$ * inverse is the correct inverse of the meemory value $inv.(1-inv.mv)$ Above are the transition constraints for the base columns . Now, We are going to see how we can construct the transition constraints for the extension columns. Let $d, a, b, c, e, f$ are random number assigned to the first six columns. The evaluation and permutation argumnets apply to a single column, which in reality is a weighted sum of some selected columns. Let $ipa, mpa, iea, oea, ipa^*, mpa^*, iea^*, oea^*$ be the variables that capture two consecutive rows of extension columns. * The instruction permutation argument applies to columns $ip, ci$ and $ni$. Every next element accumulates one factor, but only if the current row is not a padding row because then it remains the same: $ci.(ipa.(a.ip+b.ci+c.ni- \alpha)- ipa^*)$ * The memory permutation argument applies to columns $clk$, $mp$, $mv$. Every next element accumulates one factor: $(mpa \cdot (d \cdot clk + e \cdot mp + f \cdot mv - \beta) - mpa^*)$. * The input evaluation argument applies to just one column ($mv$), so the weight is superfluous. The constraint stipulates that the running sum accumulates a term whenever $ci = ,$ and remains intact otherwise: $\zeta_{\phi}(ci) \cdot (iea \cdot \gamma + mv-iea^*) + (ci - ',') \cdot (iea - iea^*)$ * The output evaluation argument is analogous to the input evaluation argument except that the relevant instruction is $.$ rather than $,$. The constraint stipulates that the running sum accumulates a term whenever $ci = .$ and remains intact otherwise: $\zeta_{\phi}(ci) \cdot (oea \cdot \delta + mv-oea^*) + (ci - '.') \cdot ( oea - oea^*).$ The Processor Table has four table relation arguments, and so the prover supplies the verifier with four terminals, $T_{ipa}$, $T_{mpa}$, $T_{iea}$, $T_{oea}$. These terminal values determine terminal constraints, which apply in the last row of extension columns. These terminal constraints are part of what proves the (sub)set and (sub)list relations. * For the instruction permutation argument, the last row is the only row that was not accumulated into the running product: $ipa \cdot (a \cdot ip + b \cdot ci + c \cdot ni - \alpha) - T_{ipa}$ * For the memory permutation argument, once again, the last row is the only row that was not accumulated into the running product: $mpa \cdot (d \cdot clk + e \cdot mp + f \cdot mv - \beta) - T_{mpa}$ * For the input evaluation argument, the last element is identical to the terminal: $iea - T_{iea}$ * For the output evaluation argument, the last element is likewise identical to the terminal: $oea - T_{oea}$ --- ### Instruction Table The instruction Table consists of three base columns $ip,ci,ni$ and two extension columns $ppa$ and $pea$. The base columns are weighted with $a,b,c$ and the extension columns operate relative to $\alpha$ and $\eta$ respectively. 1. The **boundary constraints** for the base columns are $ip=0$ in the first row. The extension $ppa$ is constrained by a difference constraint and $pea$ should be equal to the weighted sum $a. ip + b.ci+ c.ni-pea$. 2. There are four **transition constraints** that apply to the base columns:- * The instruction pointer increases by one or not at all $(ip^*-ip).(ip^*-ip-1)$ * If the instruction pointer does increase by one, then the next instruction of the current row has to be equal to the current instruction of the next row $(ip^*-ip).(ni-ci^*)$ * If the instruction pointer remains the same, then so does the current instruction $(ip^*-ip-1).(ci^*-ci)$ * If the instruction pointer remains the same, then so does the next instruction $(ip^*-ip-1).(ni^*-ni)$ The second bullet point is redundant because it is implied by the evaluation argument. Speaking of which — the extension columns evolve in accordance with the permutation and evaluation arguments: - The **permutation argument** accumulates one factor in every row if the row is not padding and if the instruction pointer does not increase. Otherwise, it remains the same. This gives rise to a sum of three separate constraints. Recall that in padded rows, $ci = 0$: - $ci \cdot (ip^\star + 1 - ip^\star) \cdot (ppa^\star - ppa \cdot (a \cdot ip^\star + b \cdot ci^\star + c \cdot ni^\star - \alpha))$ + $(ip - ip^\star) \cdot (ppa^\star - ppa)$ - The **evaluation argument** accumulates a term in every row that follows a change in $ip$, and remains the same in every row that does not. This constraint is separable into two terms: + $(ip^\star - ip - 1) \cdot (pea^\star - pea)$ + $(ip^\star - ip) \cdot (pea^\star - pea \cdot \eta - (a \cdot ip^\star + b \cdot ci^\star + c \cdot ni^\star))$ There are two terminals, one for each extension column. The terminal for the processor permutation argument coincides with the terminal for the instruction permutation argument in the ProcessorTable, $T_{ppa} = T_{ipa}$, and is sent by the prover. The terminal for the evaluation argument, $T_{pea}$, is computed locally by the verifier. These terminals give rise to the following terminal constraints: - The processor permutation argument has accumulated all rows: $ppa - T_{ppa}$. - The program evaluation argument has also accumulated all rows: $pea - T_{pea}$. ### Memory Table The Memory Table consists of three base columns, $clk,mp,mv$ and one extension column $ppa$. It uses $d,e,f$ as random weights for the base column and a running product relative to $\beta$. 1. The **boundary constraints** for the base columns are $clk=mp=mv=0$ in the first row. The extension column is unconstrained in the first row, because this value should be the secret random initial. 2. The **transition constraints** that apply to the base columns are as follows:- * The memory pointer increases by one or remains the same: $(mp + 1 - mp^*) \cdot (mp - mp^*$). * If the memory pointer increases by one, then the new memory value must be zero: $(mp - mp^*) \cdot mv^*$. * If: a) Whenever mp changes, the new mv is zero(sice RAM is intialized to zero) b) Whenever mp is unchanged and the clk jumps by more than one, the mv cannot change. $(clk + 1 - clk^*) \cdot (mv^* - mv)\cdot(mp+1- mp^*)$. The extension column $ppa$ computes a running product in line with a straightforward permutation argument. In every consecutive pair of rows, the previous row, weighted by $d$, $e$, $f$ for columns $clk$, $mp$, $mv$ respectively, is accumulated into the next row’s running product: $(ppa \cdot (d \cdot clk + e \cdot mp + f \cdot mv - \beta) - ppa^*)$. The table has one terminal, $T_{ppa}$, which coincides with the $T_{mpa}$ terminal for the Processor Table and is sent by the prover. It defines a terminal constraint, which enforces the notion that the running product has accumulated all rows but the last: $ppa \cdot (d \cdot clk + e \cdot mp + f \cdot mv - \beta) - T_{ppa}$. --- ### Input and Output Tables The Input Table and the Output Table are analogous; both are specializations of a more general $IO$ Table. The differences, as far as this section is concerned, is the challenge with respect to which the evaluation argument is made: for the Input Table it is $\gamma$ whereas for the Output Table it is $\delta$. The terminal is $not$ sent by the prover but computed by the verifier from the input and output. Let $c$ denote the base column and $ea$ the extension column. The challenge $\zeta$ refers to either $\gamma$ or $\delta$. * The boundary constraint applies only to the extension column and stipulates that the running sum starts with the column element: $ea - c$. * The transition constraint applies the multiply-and-add rule of evaluation arguments: $\zeta \cdot ea + c^* - ea^*$ * The terminal constraint, which is relative to the terminal $T_{ea}$, stipulates that the final running evaluation takes this value: $T_{ea} - ea$ ---- ## Difference Constraints There are two permutation arguments concerning columns that should remain hidden if the STARK proof should achieve zero-knowledge. But the permutation argument yields the value of a polynomial determined by the columns in question, so clearly the terminal value of this permutation argument leaks information. To avoid this, the first value of the extension columns that compute these permutation arguments is set by the prover to a random initial value. Accordingly, there is no boundary constraint that constrains these columns’ initial values. Columns of different tables that compute the same permutation argument start with the same initial. As a result, the terminal is uniformly random and leaks no information about the column without damaging the soundness of the permutation argument. It is still necessary to establish that the columns in question do in fact start with the same value. Difference constraints achieve this. Specifically, column $ipa$ of the Processor Table and column $ppa$ of the Instruction Table compute matching permutation arguments. The interpolants of these columns, $f_{ipa}(X)$ and $f_{ppa}(X)$, evaluate to the same initial in $X = o^0 = 1$. Therefore, the polynomial $f_{ipa}(X) - f_{ppa}(X)$ must evaluate to $0$ in $X = 1$. Phrased differently, this difference polynomial must be divisible by $X - 1$. The resulting **difference quotient** must be proven to have degree bounded by $\max(\deg(f_{ipa}(X)), \deg(f_{ppa}(X))) - 1$ and to this end the quotient is added to the nonlinear combination. Likewise, the column $mpa$ of the Processor Table and the column $ppa$ of the Memory Table compute the same permutation argument and so start with the same initial. Therefore, the prover should additionally establish that $\frac{f_{mpa}(X) - f_{ppa}(X)}{X - 1}$ has degree bounded by $\max(\deg(f_{mpa}(X)), \deg(f_{ppa}(X))) - 1$. --- We have seen all the AIR constraints and Arithmetization in detail. Now we will finally bring all of this together, and discuss the workflow of our zkVM in the [next blogpost](https://hackmd.io/@Muskan05/Bkt1N-tv1g).