A constraint system

Note that the condition that $F_4^2$ is correctly computed according to the Fibonacci recursive definition is equivalent to the following conditions:

• The left and right inputs to the first gate are $0$ and $1$ respectively.
• For all gates 1 to 3 the output is computed as the sum of the left and right inputs
• For gates 2 and 3 the left input of gate $k$ is equal to the right input to gate $k-1$ and the right input of gate $k$ is the output of gate $k-1$.
• For gate 4, the left and right inputs are the output of gate 3, and the output is the multiplication of the inputs.

We can visualize this as follows:

Or mathematically, consider the set of indexes $I=\{1,2,3,4\}$ and denote the left inputs as a function

$$LI:I\to \mathbb{N}$$

and similarly the right inputs $RI$ and the outputs $O$. Then we could say:

$$\begin{array}{rl}& \text{Constraint}1:LI(1)=0,RI(1)=1,\\ & \text{Constraint}2:\mathrm{\forall }i\in I\setminus \{4\}:LI(i)+RI(i)=O(i),\\ & \text{Constraint}3:\mathrm{\forall }i\in I\setminus \{3,4\}:(LI(i+1)=RI(i))\wedge (RI(i+1)=O(i)),\\ & \text{Constraint}4:LI(4)=RI(4)=O(3),\\ & \text{Constraint}5:LI(4)\ast RI(4)=O(4),\\ & ⟹O(4)=F_4^2.\end{array}$$

So if the processor $P$ can convince the validator $V$ that the above defined constraints hold for the table representation of the circuit computation, then the validator will be convinced that $F_4^2$ was computed correctly. Let us now explore a way to do so by leveraging on polynomials and so-called zero-equality tests.

Exercise 2

Check that the five constraints above hold over the arrays defined in Exercise 1. Consider as an example the given implementation of the first two constraints.

#Constraint 1
assert LI[1]== 0 and RI[1]==1

#Constraint 2
for i in I:
    if i != 4:
        assert LI[i] + RI[i] == O[i]
#Constraint 3

#Constraint 4

#Constraint 5