## Tutorial 3 - Programs as Polynomials
In [tut1](https://hackmd.io/@qozymandias/rkqYWVNEa) we introduced polynomial representations and commitments; in [tut2](https://hackmd.io/@qozymandias/Hkqnf44VT) we detailed KZG and evaluation proofs; now, we will briefly describe how to bring this into the realm of programming proofs.

When constructing an evaluation proof, we have our evaluation points and the roots of the equation. For an arbitrary number of evaluation points, we turn them into an interpolation polynomial. The roots are multiplied in the divisor.

$$
H(X) = \frac{F(X) - I(X)}{Z(X)} = \frac{F(X) - I(\{(y_{0}, f(y_{0})),(y_{1}, f(y_{1})), \cdots \})(X)}{(X - z_{0})(X-z_{1})\cdots}
$$

Committing to this polynomial, $[H]$, is the proof. This was covered in [tut2](https://hackmd.io/@qozymandias/Hkqnf44VT).

Now, how can we encode a program into this system?
Because if we can do that then we can validate the correctness of execution, in others words, does the binary actually behave as it should according to the source code.

A polynomial can be used to define any function theoretically, and it can also describe the relationship between a function's current and next execution "steps", this is known as the constraint.
If the constraint fails at any step, then the program is not executing as expected.
Think of a "for loop", usually with formal methods, induction would be used, and we would define some invariant for the loop that must hold true at every step; then pre-conditions and post conditions would be defined and validated as well.
In this case we are doing something similar but with polynomials representing the invariant and the function itself.
So, we now must understand how to define a program's behaviour in terms of polynomials.
### Programs behaviour as constraints polynomials and KZG
We must consider an example for any of this to make sense.
#### Example program
Consider a simple accumulation program:

let acc = 0
for (i=0; i < 100; i++) {
    acc += i
}

##### Understanding the behaviour first
The acc and i are intermediate values, and rather than just checking inputs and outputs, we have to check the intermediate values at every step, as this would provide an indisputable proof of behaviour.
To do this, we have to understand the value changes between each "step" of the loop. The table of values goes something like this:

| acc | i | g |
|------|---|------|
| 0 | 0 | g^0 |
| 0 | 1 | g^1 |
| 1 | 2 | g^2 |
| 3 | 3 | g^3 |
| .. | . | .. |

$g$ is the generator for the curve -- important for later, but not relevant right now. Consider it some as just part of the program state we have to keep track of.

We can imagine each variable as a function call, and think about it recursively, then next depends on the current value.

$$
(acc, v) = [(0,0), (0,1), (1, 2), \cdots]
$$

$$(i, v) = [(0,0), (1, 1), (2, 2), (3, 3), \cdots]$$

How can we create a predicate that can act as an invariant for the loop? i.e. how can we constrain between the $acc(x)$ and $i(x)$ functions with a relationship, where x is the iteration of the loop.
$$acc(x + 1) = acc(x) + i(x)$$
This must hold true for all $x$ values, i.e. for every step of the loop.

One method of validation would just to brute force all the values, however, we would rather have some time let after its done ha ha.

Instead, we use the fact that we can reason about it as a polynomial equal to zero, and actually $acc(x) + i(x)$ is really just shifting some value along the polynomial by changing $x$ values.

Therefore, the constraint is:
$$acc(x) + i(x) - acc(x + 1) = 0$$
This is how we can encode the loop invariant as a polynomial constraint.
The next step is to prove it, however, we must first consider the group in which to source our elements from.
##### In terms of a finite field
The constraint has to be proven given a group of field elements.
So we must re-introduce the finite field elements to the equation because that is the domain in which we do these things.

The generator, $g$ will be the generator of the domain of our polynomial, that is, it controls what our x values can be.
When there exists a domain of a finite field, there will always be a generator, theoretically for any $x$ in the domain, there exists a $k$ such that $x = g^k$.
##### Curve point Generator
Now we have $g$ generator, however, what does it mean to be using the generator?
Well it means we can have any $x$ and $g$ will place it on the underlying elliptic curve, and since these curves have such nice properties that doing arithmetic on the curves acts as an equivalent proxy to arithmetic in our $x$ domain -- this is because we always change both LHS and RHS when we are doing the proof, therefore the equality holds.

Since we are on the curve, the notation is slightly different, be we are moving a base point on the curve around $x$ number of times: $xg$, that is $x$ gets transformed onto one of the curve points, $x = g^{0}, g^{1}, \dots, g^{n}$, with the generator $g$.
Now, we must think in terms of the elliptic curve from now on, and therefore we must introduce a new concept in order for us to use $g$ in our original constraint, that is a "shift" which basically allows us to arbitrary iterate over the generated points.
##### Polynomial Shift
For the proofs we need to be able to move between iterations arbitrary, i.e. our proof system needs to allow the prover to define this alongside the original constraint.

This is essentially an abstract iterator function for polynomials; it connects the current evaluation point with the previous (think: current - 1) and the next (think: current + 1), therefore allowing us to "step" through a polynomial, backwards, or forwards.
Therefore, evaluation can be done only with $x$ (i.e. a random point) and $g$ (the generator)

Therefore, it is up to the prover to define a shift function as a part of the basic operations alongside the polynomial.
Thus allow for arbitrary jumping between any points on the polynomial which represents the state of behaviour in our program.

For example, consider the accumulation example again.
Notice, $acc(x + 1)$, however, $x=g^k$, and we don't have the same concept of incrementing, therefore we must define our concept of incrementing $x$ in terms of a shift.

We want our shift to be moving $x$ onto the next curve point, from its current one.
Let the definition of shift be

$$s(F(x)) = F(xg)$$
That means we apply a shift by just moving $g$ around the curve $x$ times.
Therefore, we have the curve points for, $x = g^{0}, g^{1}, \dots, g^{n}$.
And since is an arbitrary curve point, $x=g^k$, it follows that the original equation can be rewritten using the fact that $s(F(x))$ is equivalent to $F(x + 1)$:
$$acc(x \cdot g^{1}) = acc(x) + i(x)$$
where $F=acc$

Fully expanding the equation we see it holds true for, $x = g^k$, as it follows $xg^{1} = g^{k} * g^{1} ==> g^{k+1}$
Therefore:
$$
acc(g^k \cdot g^1) = acc(g^k) + i(g^{k})

===>

acc(g^{k+1}) = acc(g^k) + i(g^k)
$$
Thus, $acc(xg)$ is the shift of the polynomial $acc(x)$, and now we can evaluate both "sides" of the equality constraint, by just supplying a random point on the curve, and with that we will be able to prove it for all points in the group, $x = g^{0}, g^{1}, \dots, g^{n}$ (with the generator $g$).
##### The final constraint
So now we finally have our constraint in terms of the correct field for KZG! Now we can use it to prove:
$$acc(x) + i(x) - acc(x \cdot g) = 0 ;\space\space\space\space \forall x = g^{0}, g^{1}, \dots, g^{n}$$
By verifying this equality is the same as proving the original invariant for all $x$, because we are performing the equivalent computations just in a different domain.

Now we have all the pieces of the puzzle, and we can plug it into KZG!
#### How to prove a thing between two parties; i.e. bringing it back to KZG!
To bring it into our KZG scheme, let this be $f(x)$
$$ f(x) = acc(x) + i(x) - acc(x \cdot g)$$
Then, prove
$$ f(x) = 0$$
For all: $x = g^{0}, g^{1}, \dots, g^{n}$

Now choose a random point $x=g^i$ (from our group), and determined what it evaluates to, $a$,
$$ f(x) = a_{i} \space \text{ at } \space x=g_i $$
Rewritten as:
$$ f(x) - a_i = 0$$
Let this be $f'(x)$
$$f'(x) = f(x) - a_i $$
Let $I(x)$ represent a interpolated polynomial of all the evaluation values given the points $x = g^{0}, g^{1}, \dots, g^{n}$
$$f'(x) = f(x) - I(x) $$
Since we know, $f'(x) = 0$ at $x = g^{0}, g^{1}, \dots, g^{n}$, these values are roots, and therefore we can re-introduce these values back into the equation, therefore, $f'(x)$ has a root at $r_i$. Where $r_i = g_0, g_1, \dots$, since $f(x) - I(x) == 0$ at these points.
The roots are placed in the divisor as not to break the equality:
$$
h(x) = \frac{f'(x)}{(x - g_0)(x- g_1)\cdots} = 0
$$
$h(x)$ will zero at all roots. We can let the divisor be $Z(x) = (x - g_0)(x- g_1)\cdots$:
$$
h(x) = \frac{f'(x)}{Z(x)} = 0
$$
Therefore the commitment to $h(x)$, $[h]$ is our proof, and it sent by the prover along with the evaluation polynomial.
$$
h(x) = \frac{f'(x)}{(x - g_0)(x- g_1)\cdots}
$$
We can construct our polynomial such that every $x=g^i$ produces an evaluation value in $I(x)$ such that it equals zero at every $x$, i.e. $I(x) = 0$ at the points given.
This means we are just proving $f(x) = 0$ instead of $f(x)=I(x)$ at $x=g^0, g^1, ..., g^n$, to simply the calculation:
$$
h(x) = \frac{f(x) - 0}{(x - g_0)(x- g_1)\cdots}
$$
And a single evaluation would prove it correct, any point on the curve can be chosen!

$$
[h(x)] \cdot [(x - g_0)(x- g_1)\cdots] = [f(x)]
$$
In other words, ensure this equality holds true, given a random $x$ which is generated (i.e. $[x] = xg$ where $g$ is generator for the Elliptic curve group).
Refer to [tut2](https://hackmd.io/@qozymandias/Hkqnf44VT) for explanation of how to compute the equality.
#### Conclusion and Plonk
Now, we have roughly explained how to connect a program invariant into constraint equations for KZG; I have tried to explain the intuition of connecting programs to polynomial proving systems; this all leads us to PLONK, because we now have intuition about how to plug programs into a proving system.

However, I have skipped over actually defining $f(x)$, it is not really a concrete function, $acc$ and $i$ have to be formally defined, we have only defined the constraining relationship between iterations and how to move between iterations.
Up until now we have treated them like black boxes which should return the correct value and I suppose the $acc(x)$ function would grow exponentially and the $i(x)$ would consistently equate to one.
We can interpolate a polynomial based on the values, but that would be time-consuming and not accurate enough nor generic enough!
Instead, we will use arthimatization!
Which is a method of transform programs into "circuits" which can then be easily represented as polynomials.
The PLONK paper specific a way of doing this for arbitrary functions, and with that we have the final piece of the puzzle.

PLONK is a proof system that efficiently checks proofs for arbitrary programs, using everything we have discussed so far.
PLONK specifies a key piece of the system: how to turn functions into polynomials; it specifies a process of arthimatization for arbitrary functions -- the process for converting a program into a set of polynomial equations that the polynomial commitments are then used to check. The resulting polynomials would then be plugged into KZG to complete the proof system.