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:
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:
The relations between the states of registries can be translated into identities in the polynomial setting as follows:
However, the previous identities do not correctly and uniquely describe our sequence because:

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}\] 
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:
With this auxiliary registry, we can now fix the polynomial identities as follows:
Note that now at \(x = \omega^8\) the identities are satisfied:
Observe that we can also use other initial conditions \((A_1, B_1)\) slightly modifying our polynomial identities:
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 FRIbased.
Commitment schemes are binding and hiding:
 Binding: The prover can not change the polynomial she committed to.
 Hiding: The verifier can not deduce which is the committed polynomial by only looking at the commitment.