A first example

Consider the following scenario: You have a low resource device $V$ (a validator) that can delegate computations to a processor $P$, which has more computing capabilities. Sometimes the processor $P$ makes mistakes in the computations, so $V$ wants to do some sanity checks on $V$ to make sure the final value of the computation is correct.

Squared Fibonacci

For example, let's assume that $V$ asks $P$ to compute the $4$-th Fibonacci number squared, that is $F_4^2$. Recall that the Fibonacci sequence is defined by:

$$F_n=F_{n-1}+F_{n-2}$$

with the base cases $F_0=0$ and $F_1=1$.

Note that this computation can be expressed as a circuit as illustrated in Figure 1.

The goal of this example will be to design a first simple protocol that allows us to validate whether this circuit has been correctly evaluated by the processor $P$ without having to recompute every single intermediate state (wire value) of the circuit. In other words the question is: can we devise a protocol that can (efficiently) guarantee that the $F_4$ value of the sequence has been correctly computed and then squared? Are the base cases $F_0$ and $F_1$ correct, and have all intermediate computations of the circuit correctly performed?

To achieve this, let us start by picturing the circuit and all intermediate computations as a table. Consider the following picture.

Exercise 1

Consider the set of indexes from 1 to 4 as the vector $I$ given below. Represent the left and right columns as vectors of integers $LI$ and $RI$. Likewise, represent the output as vector $O$.

Note: Since Python/Sage arrays are numbered from $0$ to $n$ instead of $1$ to $n$, we will use dictionaries in the following to represent mappings from $I\to \mathbb{N}$ as in the example below for $LI$.

I = [1,2,3,4]
LI = {1:0,2:1,3:1,4:3}
RI = 
O =