Trusted Setup: KZG and PST

• Trusted Setup: KZG and PST
• KZG trusted setup
  • First Player
  • Second Player
  • Verifications
    • Tau update check:
    • Consecutive powers check
    • Optional: G2 check
• PST trusted setup
  • First player
  • Second player
  • Verification steps
    • Tau update check
    • G2 / G1 check: same element are used in both groups
    • Doing it efficiently

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

$$\begin{gathered} [ts{]}_1,[t^2{s}^2{]}_1... \\ [ts{]}_1,[(ts{)}^2{]}_1,... \end{gathered}$$
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)

$$\begin{gathered} e([(st{)}^2,G_2)==e([st{]}_1,[st{]}_2) \\ e([(st{)}^3,G_2)==e([(st{)}^2{]}_1,[st{]}_2) \\ ... \end{gathered}$$

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:

$$\begin{gathered} e([st{]}_1,G_2)==e(G_1,[st{]}_2) \\ e([(st{)}^2{]}_1,G_2)==e(G_1,[(st{)}^2{]}_2) \\ ... \end{gathered}$$

PST trusted setup

Notation: Let

$s_1,\dots ,s_n$ be in

$Z_q$ or

$\overrightarrow{s}=[s_1,\dots ,s_n]$ Let

$i\in \{0,1{\}}^n$, we can denote

$i=[i_1\dots i_n]$ with

$i_j\in \{0,1\}$. Then with

${\overrightarrow{s}}^i$ we denote the value

$\prod _j{s}_j^{i_j}$. We note

$<{\overrightarrow{t}}^{\overrightarrow{i}}\circ {\overrightarrow{s}}^{\overrightarrow{i}}>$ the Hadamard product between vectors

$\{[{\overrightarrow{s}}^{\overrightarrow{i}}{]}_1{\}}_{\overrightarrow{i}=\overrightarrow{0}}^{\overrightarrow{n}}$ and

$\{[{\overrightarrow{t}}^{\overrightarrow{i}}{]}_1{\}}_{\overrightarrow{i}=\overrightarrow{0}}^{\overrightarrow{n}}$ (in other words, generate all possible polynomials from

$2^n$ possibilities on

$\overrightarrow{s}$ and

$\overrightarrow{t}$ and compute the product entry-wise.)

On both

$G_1$ and

$G_2$

First player

First player with random coefficeints

$\overrightarrow{t}$ generates:

$$\begin{gathered} {\overrightarrow{A}}_1=[s_1{]}_1,[s_1{s}_2{]}_1,[s_2{]}_1...=\{[{\overrightarrow{s}}^{\overrightarrow{i}}{]}_1{\}}_{\overrightarrow{i}=\overrightarrow{0}}^{\overrightarrow{n}} \\ {\overrightarrow{A}}_2=[s_1{]}_2,[s_1{s}_2{]}_2,[s_2{]}_2...=\{[{\overrightarrow{s}}^{\overrightarrow{i}}{]}_2\} \end{gathered}$$

Second player

Second player generates:

$$\begin{gathered} {\overrightarrow{B}}_1=[(t_1)s_1{]}_1,[(t_1{t}_2)s_1{s}_2{]}_1,[(t_2)s_2{]}_1...=\{[<{\overrightarrow{t}}^{\overrightarrow{i}}\circ {\overrightarrow{s}}^{\overrightarrow{i}}>{]}_1\} \\ {\overrightarrow{B}}_2=[(t_1)s_1{]}_2,[(t_1{t}_2)s_1{s}_2{]}_2,[(t_2)s_2{]}_2...=\{[<{\overrightarrow{t}}^{\overrightarrow{i}}\circ {\overrightarrow{s}}^{\overrightarrow{i}}>{]}_2\} \end{gathered}$$
which is the entry wise multiplication of the two random vectors

Also for verification it is needed to share:

$$\overrightarrow{T}=[{\overrightarrow{t}}^{\overrightarrow{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 (

$\overrightarrow{B}$):

$$\begin{gathered} \mathrm{\forall }\overrightarrow{i}\in \{0,1{\}}^n: \\ e([{\overrightarrow{t}}^{\overrightarrow{i}}{]}_1,[{\overrightarrow{s}}^{\overrightarrow{i}}{]}_2)==e(<{\overrightarrow{t}}^{\overrightarrow{i}}\circ {\overrightarrow{s}}^{\overrightarrow{i}}>,G_2) \end{gathered}$$
or written differently

$$e(\overrightarrow{T}[i],{\overrightarrow{A}}_2[i])==e(B_1[i],G_2)$$

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

$$\mathrm{\forall }i\in 0...n:e(B_1[i],G_2)==e(G_1,B_2[i])$$
or written differently

$$\mathrm{\forall }i\in 0...n:e([<{\overrightarrow{t}}^{\overrightarrow{i}}\circ {\overrightarrow{s}}^{\overrightarrow{i}}>{]}_1,G_2)==e(G_1,[<{\overrightarrow{t}}^{\overrightarrow{i}}\circ {\overrightarrow{s}}^{\overrightarrow{i}}>{]}_2)$$

Doing it efficiently

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

Derive randomness

$u$, then

$$\begin{gathered} Q=\sum _i([{\overrightarrow{s}}^{\overrightarrow{i}}{]}_2{)}^{u^i} \\ P=\sum _i([{\overrightarrow{t}}^{\overrightarrow{i}}{]}_1{)}^{u^i} \\ R=\sum _i{B}_1[i{]}^{u^i} \\ S=\sum _i{B}_2[i{]}^{u^i} \end{gathered}$$
then do

$$e(R,G_2)==e(G_1,S)$$

The second check will resolve to:

$$\begin{gathered} 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<{\overrightarrow{t}}^{\overrightarrow{i}}\circ {\overrightarrow{s}}^{\overrightarrow{i}}>[i]{]}_1,G_2)=e(G_1,[\sum _i{u}^i<{\overrightarrow{t}}^{\overrightarrow{i}}\circ {\overrightarrow{s}}^{\overrightarrow{i}}>[i]{]}_2) \end{gathered}$$

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