# Introduction

## First Example: The Fibonacci State Machine

Let's consider that we want to validate that a certain number is a number of a Fibonacci sequence given certain initial conditions. To do so, we can build a state machine with two registries, $$A$$ and $$B$$ as shown in the following picture:

Notice that the initial conditions for the state machine are $$A_1=0$$ and $$B_1=1$$ and that we have the following relations between the states of these registries:

\begin{aligned} A_{i+1} &= B_i, \\ B_{i+1} &= A_i + B_i. \end{aligned}

Let's represent the states of these registries as polynomials in $$\mathbb{Z}_p[x]$$ evaluated on the subgroup $$H = \{\omega, \omega^2, \omega^3, \omega^4, \omega^5, \omega^6, \omega^7, \omega^8 = 1\}$$ of $$8$$-roots of unity in $$\mathbb{Z}_p^*$$. Then, we have the following relations:

\begin{aligned} A(\omega^i) &= A_i \quad \Longrightarrow \quad A = [0, 1, 1, 2, 3, 5, 8, 13] \\ B(\omega^i) &= B_i \quad \Longrightarrow \quad B = [1, 1, 2, 3, 5, 8, 13, 21] \end{aligned}

The relations between the states of registries can be translated into identities in the polynomial setting as follows:

\begin{aligned} A(x\omega) &= \bigg\lvert_H B(x), \\ B(x\omega) &= \bigg\lvert_H A(x) + B(x). \end{aligned}

However, the previous identities do not correctly and uniquely describe our sequence because:

1. The registries are not cyclic: When we evaluate the identities at $$\omega^8$$:

\begin{aligned} A(\omega^9) &= A(\omega) = 0 \neq 21 = B(\omega^8), \\ B(\omega^9) &= B(\omega) = 1 \neq 34 = A(\omega^8) + B(\omega^8). \end{aligned}
2. We can use other initial conditions, for example $$(2,4)$$, that also fulfill the identities: $$(2,4)\to(4,6)\to(6,10)\to(10,16)\to(16,26)\to(26,42)\to(42,68)\to(68,110).$$

We have to modify a little our solution in order correctly and uniquely describe the Fibonacci sequence with cyclic polynomial identities. To do that, let's add an auxiliary registry $$C$$:

The corresponding polynomial $$C$$ is:

\begin{aligned} C(\omega^i) &= C_i \quad \Longrightarrow \quad C = [1, 0, 0, 0, 0, 0, 0, 0]. \end{aligned}

With this auxiliary registry, we can now fix the polynomial identities as follows:

\begin{aligned} A(x\omega) &= \bigg\lvert_H B(x)(1 - C(x\omega)), \\ B(x\omega) &= \bigg\lvert_H (A(x) + B(x))(1 - C(x\omega)) + C(x\omega). \end{aligned}

Note that now at $$x = \omega^8$$ the identities are satisfied:

\begin{aligned} A(\omega^9) &= A(\omega) = 0 = B(\omega^8)(1 - C(\omega)), \\ B(\omega^9) &= B(\omega) = 1 = (A(\omega^8) + B(\omega^8))(1 - C(\omega)) + C(\omega). \end{aligned}

Observe that we can also use other initial conditions $$(A_1, B_1)$$ slightly modifying our polynomial identities:

\begin{aligned} A(x\omega) &= \bigg\lvert_H B(x)(1 - C(x\omega))+ A_1C(x\omega), \\ B(x\omega) &= \bigg\lvert_H (A(x) + B(x))(1 - C(x\omega)) + B_1 C(x\omega). \end{aligned}

In our previous example $$(A_1, B_1) = (0, 1)$$.

## Proving our State Machine (High Level)

The previous polynomial relations can be efficiently proven through polynomial commitments such as Kate and FRI-based.

Commitment schemes are binding and hiding:

1. Binding: The prover can not change the polynomial she committed to.
2. Hiding: The verifier can not deduce which is the committed polynomial by only looking at the commitment.