# Tutorial 1 - Polynomials on Finite Field

## Polynomials Representations
#### 1. coefficient representation:
polynomial is defined by its coefficient at each of its powers of $x$
> $f(x) = a_0x^0 + a_1x^1 + a_2x^2 + \cdots + a_nx^n$
#### 2. evaluation representation
polynomial is defined as a series of point-values pairs, that is we have points with concrete evaluations associated with it.
> $f(w_0) = e_0,$
> $f(w_1) = e_1,$
> $\cdots$
> $f(w_n) = e_n$

if degree is $d$, you need $d$ pairs to represent a polynomial
#### orth repr, another representation of 2:
$f(x) = a_0h_0(x) + a_1h_1(x) + a_2h_2(x) + \cdots + a_nh_n(x)$

This is just a fancy way of defining a evaluation form because, we would have our values, $w_0, w_1, \cdots, w_n$
and to get our corresponding point on the poly, we let our $h_i$ hold this property for each value given:
$h_i(w_i) = 1$, but $0$ else where.

thus, at each evaluation we isolate the coefficient we care about for the point:
$f(w_0) = a_0h_0(w_0) + a_1h_1(w_0) + a_2h_2(w_0) + \cdots = a_0$
$f(w_0) = a_0(1) + 0 + 0 + \cdots = a_0$

and so on and so forth
$f(w_1) = a_0h_0(w_1) + a_1h_1(w_1) + a_2h_2(w_1) .... = a_1$
$f(w_1) = 0 + a_1(1) + 0 .... = a_1$
##### Conclusion: just two key representations.
Orth repr is just a form of evaluation representation.

In halo2 library used phantom types to specific Coefficent or Evaluation representation. Where the phantom data is used only for type information.

Vec<F> ---> struct Polynomial<F, REPR> = {Vec<F>, phantom<REPR>}

## Commitments
#### 1. commitment of a number
To begin lets imagine commit to a specific number, $a$ (e.g. guessing game), and we want to wrap it in a envelope that enforces no lying and doesnt reveal $a$.

We can hide it by mapping it to elliptic curve points - chosen because its a one way map and thus cannot reveal $a$.

$c$ is called the commitment of $a$. $g$ envelopes $a$ so we check it hasnt changed without checking $a$ itself
$c = a * g = g + g + g + g + \cdots$

where $g$ is a point on elliptic curve. We can think of $g$ as a random elements from a finite field (in this case all the elements in this field are points on the elliptic curve)
$g = (x, y)$ where $x,y \in F$.
##### Quick note on elliptic curve points
From now on we have to specific something about elliptic curve notation.
Square bracket notation is used to specify a mapping to an elliptic curve group (which can be thought of as a finite set of points).
e.g. $[x] = xG = G + \cdots + G$
^ $x$ times

In other words, $[x]$ converts $x$ into a point on an elliptic curve --> it will correspond to on of the point $G$.

It is helpful to think of any operation involving $g$ as a mapping to an elliptic curve point.

Thus, we you see $[x]$, $xg$, or $xG$, dont panic! its just elliptic curve notation can we are in a whole new realm of numbers now.
And remember, we can generate an entire group of elliptic curve points from just a single base point and a random number

#### 2. commitment of a polynomial:
Now we can extend this concept to a representation of many numbers - a polynomial - which is essentially just a series of numbers.
In this case, we have a special polynomial $a =\{a_0, a_1,\cdots,a_n\}$, represented in coefficient form.
Now to apply the $g$ ( represented also now as a polynomial of coefficients $g =\{g_0, g_1,\cdots,g_n\}$ ) and with the result (called a commitment) we have successfully produced a scrabbled version of our original polynomial which hids it completely but preserves it entirely.
Basically, the output commitment allows evaluation at points on the polynomial without revealing the polynomial and ensuring the polynomial is no a fake (i.e. switched out by malicious party)

Creating the commitment involves summing up the pair wise multiplication of the coefficients.
$\sum^{n}_{i=0} a_ig_{i} = a_0g_0 + a_1g_1 + a_2g_2 + \cdots + a_n*g_n$

Thus, this is our commitment for our secret polynomial.
$[f] = a_0g_0 + a_1g_1 + a_2g_2 + \cdots + a_n*g_n$ //msm

And we can thing of this as just some curve point.
Usually, we dont deal with $g$ directly but rather it is multiplied we another secret polynomial $s$ (or rather $s$ is mapped to an elliptic curve point on $g$) that requires a trusted setup from a third party.

### Bringing it together: the full formula of commitment of polynomial
Starting with the general orth repr of polynomial
$f(x) = a_0h_0(x) + a_1h_1(x) + a_2h_2(x) + \cdots + a_nh_n(x)$
We take this form to easy construct polynomials from just a few points rather than constructing them the coefficient way.

This is some polynomial we want to choose and wrap up in our envelope so we can commit to it.
We will require some algebraic rearrangement to efficiently turn the polynomial into commitment, let $g$ be a point on elliptic curve from our field and multiply both sides of the equation by $g$.

$f(x)*g = (a_0h_0(x) + a_1h_1(x) + a_2h_2(x) + \cdots + a_nh_n(x)) * g$
$= a_0h_0(x) * g + a_1h_1(x) * g + a_2h_2(x)*g + \cdots + a_nh_n(x)*g$

Thus our polynomial is hidden behind this group element $g$ .
And this is impossible to undo because of elliptic curve point properities - you cannot simply divide by $g$ to retrieve $f(x)$

We can see all the strength in the secrecy comes from multiplying the coefficient with the group elements $g$ , where each coefficient gets mapped to a point on the elliptic curve.
So its important to have good and secret curve, and this is done by seeding its construction with a random value.

To do this we pick a random number from our field (during a trusted setup), $\xi$, where $\xi\in F$ such that
$f(\xi)*g = a_0h_0(\xi) * g + a_1h_1(\xi) * g + \cdots + a_nh_n(\xi) * g$

Now, since we remember $g$ is just a point generator, we can see each application of our random function to $g$ will in fact place it somewhere is a finite field of points on an elliptic curve.
Thus
$g_i = h_i(\xi) * g$ with $\xi$ randomly picked.

$g_i$ is known as the **Common Reference String (CRS)**, hides the original random number $\xi$ and can be publicly known.

> relating it back to the secret $s$ number that seeded all of this, we are essentially starting with a base point $g$ and going $s$ times around the curve, producing a new point.
> It is impossible to get back to the original point (see discrete log problem)
> This is usually done for increasing powers of $s$ (up until the degree of the polynomial - in this case, $h_i(\xi)$ encapsulates out set of $s$.
> So you might see the CRS written as the following set $\{ s^{0}G, s^{1}G, \cdots , s^{n}G \}$ which is the same thing as $\{ h_{0}(\xi)g, h_{1}(\xi)g, \cdots , h_{n}(\xi)g \}$
> I found [this](https://andrea.corbellini.name/ecc/interactive/reals-mul.html) online visualiser quite good at thinking about this concept, you can increase $n$ (the scalar multiplier) and see all the points you get.

Now in elliptic curve notation it can look a bit weird, but this is what our commitment can be defined as
$[f] = g^{f(\xi)} = g^{a_0h_0(\xi) + a_1h_1(\xi) + \cdots + a_nh_n(\xi)}$
### Key takeaway
We can compute a commitment to a polynomial without knowing the secret value $\xi$ (since it is mapped to points on elliptic curve)

This is done by multiplying every coefficient with its corresponding $g_i$ (common reference string), and then summing up the results to get the commitment (a point on the curve).
This is essentially the same as what we started with.
$\sum^{n}_{i=0} a_ig_{i} = a_0g_0 + a_1g_1 + a_2g_2 + \cdots + a_n*g_n$

However, the key different is we can mapping everything to a field of elliptic curve points, which are, by design, unreversible.

Since we are now dealing with elliptic curve points, they give us nice properties and thus the proving can be done in constant time.
Proving the commitment is valid with evaluation proofs will be covered later.