# Trusted Setup: KZG and PST
[TOC]

# KZG trusted setup

## First Player

First player has secret $s$ and generates
$$
[s]_1, [s^2]_1 ...
$$
as well as the "check" point
$$
[s]_2
$$

## Second Player

then second player generates secret $t$ and takes the first sequence and generates
$$
[ts]_1, [t^2s^2]_1 ... \\
[ts]_1, [(ts)^2]_1, ...
$$
and also update a running "check" point
$$
[t]_2, [st]_2
$$

## Verifications

Then contribution of second player can be checked:

### Tau update check:

Check second player really took last valid contribution:
$$
e([s]_1,[t]_2) == e([ts]_1, G_2)\\
$$

### Consecutive powers check

Check second player really updated each consecutive term by multiplying by his secret again (t, t², etc)
$$
e([(st)^2,G_2) == e([st]_1, [st]_2)\\
e([(st)^3,G_2) == e([(st)^2]_1, [st]_2)\\
...
$$

### Optional: G2 check

If needed, (and in Testudo we will need), players can also submit a full "chain" on G2 as well. In this case, we can simply check the pairing between
the element in G1 and elements in G2, like:
$$
e([st]_1,G_2) == e(G_1,[st]_2)\\
e([(st)^2]_1,G_2) == e(G_1,[(st)^2]_2)\\
...
$$

# PST trusted setup

**Notation:** Let $s_1,\ldots,s_n$ be in $Z_q$ or $\vec{s}=[s_1,\ldots,s_n]$ Let $i\in\{0,1\}^n$, we can denote $i=[i_1\ldots i_n]$ with $i_j \in \{0,1\}$. Then with $\vec{s}^{\;i}$ we denote the value $\prod_j s_j^{i_j}$. We note $\lt \vec{t}^{\vec{i}} \circ \vec{s}^{\vec{i}} \gt$ the Hadamard product between vectors
$\{[\vec{s}^{\vec{i}}]_1\}_{\vec{i}=\vec{0}}^{\vec{n}}$ and $\{[\vec{t}^{\vec{i}}]_1\}_{\vec{i}=\vec{0}}^{\vec{n}}$ (in other words, generate all possible polynomials from $2^n$ possibilities on $\vec{s}$ and $\vec{t}$ and compute the product entry-wise.)

On both $G_1$ and $G_2$

## First player

First player with random coefficeints $\vec{t}$ generates:
$$
\vec{A}_1 = [s_1]_1, [s_1s_2]_1, [s_2]_1 ... = \{[\vec{s}^{\vec{i}}]_1\}_{\vec{i}=\vec{0}}^{\vec{n}} \\
\vec{A}_2 = [s_1]_2, [s_1s_2]_2, [s_2]_2 ... = \{[\vec{s}^{\vec{i}}]_2\}
$$

## Second player

Second player generates:
$$
\vec{B}_1 = [(t_1)s_1]_1, [(t_1t_2)s_1s_2]_1, [(t_2)s_2]_1 ... = \{[\lt \vec{t}^{\vec{i}} \circ \vec{s}^{\vec{i}} \gt]_1\}\\
\vec{B}_2 = [(t_1)s_1]_2, [(t_1t_2)s_1s_2]_2, [(t_2)s_2]_2 ... = \{[\lt \vec{t}^{\vec{i}} \circ \vec{s}^{\vec{i}} \gt]_2\}\\
$$
which is the entry wise multiplication of the two random vectors

Also for verification it is needed to share:
$$
\vec{T} = [\vec{t}^{\vec{i}}]_1
$$

## Verification steps

### Tau update check

Check new player really used last valid contribution (from first player) to build its chain of $G_1$ elements ($\vec{B}$):

$$
\forall \vec{i} \in \{0,1\}^n:\\
e([\vec{t}^{\vec{i}}]_1,[\vec{s}^{\vec{i}}]_2) == e(\lt \vec{t}^{\vec{i}} \circ \vec{s}^{\vec{i}} \gt, G_2)
$$
or written differently
$$
e(\vec{T}[i],\vec{A}_2[i]) == e(B_1[i], G_2)
$$

### G2 / G1 check: same element are used in both groups

$$
\forall i \in 0...n: e(B_1[i], G_2) == e(G_1, B_2[i])
$$
or written differently
$$
\forall i \in 0...n: e([\lt \vec{t}^{\vec{i}} \circ \vec{s}^{\vec{i}} \gt]_1, G_2) == e(G_1, [\lt \vec{t}^{\vec{i}} \circ \vec{s}^{\vec{i}} \gt]_2)
$$

### Doing it efficiently

* Second verification should not perform 2 * n pairings, but rather use linear combination of pairings results

Derive randomness $u$, then
$$
Q = \sum_i ([\vec{s}^{\vec{i}}]_2)^{u^i} \\
P = \sum_i ([\vec{t}^{\vec{i}}]_1)^{u^i} \\
R = \sum_i B_1[i]^{u^i} \\
S = \sum_i B_2[i]^{u^i} \\
$$
then do
$$
e(R,G_2) == e(G_1,S)
$$

The second check will resolve to:
$$
e(\sum_i B_1[i]^{u^i}, G_2) == e(G_1, \sum_i B_2[i]^{u^i})\\
e([\sum_i u^i\lt \vec{t}^{\vec{i}} \circ \vec{s}^{\vec{i}}\gt[i]]_1, G_2) = e(G_1, [\sum_i u^i\lt \vec{t}^{\vec{i}} \circ \vec{s}^{\vec{i}}\gt[i]]_2)\\
$$

TODO: How to do for first check ? linear comb doesn't work - only batch millerloop + final exponentiation will make it work ?