# 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 ?