## DKG in SNARK?

VSS:
Dealer $a_0$
Deal Phase:
1. Create $f(x) = a_0 + a_1 * x + ... + a_{t-1}*x^{t-1}$
2. Compute shares $f(1), \dots, f(n)$
3. Encrypt each shares $Enc(f(1),PK_1), \dots$
4. Compute commitment to $f(x)$ : $F(x) = [f(x)] G$
5. Send everything
Response phase (by each "receiver" $i$):
1. Try to decrypt their encrypted share
2. Verify consistency with public polynomial $f(i)*G = F(i)$
3. If Sucess -> GOOD
4. If Fail -> go to justification phase
Justification:
Dealer reveals $f(i)$ in the clear

$t < n$
PCS version:
Dealer $a_0$
Deal Phase:
1. Create $f(x) = a_0 + a_1 * x + ... + a_{t-1}*x^{t-1}$
2. Compute shares $f(1), \dots, f(n)$
3. Encrypt each shares $Enc(f(1),PK_1), \dots$
4. Compute $F(0) = f(0) * G$ + Schnorr proof to prove exponent
5. Compute commitment to $f(x)$ : $Comm_f$
6. Compute opening proofs for each i $\pi_i = PCS.Open(Comm_f,i,f(i))$
7. Send everything

Response phase (by each "receiver" $i$):
1. Try to decrypt their encrypted share
2. Verify consistency with public polynomial $PCS.Verify(Comm_f,\pi_i,i,f(i))$
3. Verify Schnorr proof
4. If Sucess -> GOOD
5. If Fail -> go to justification phase
Justification:
Dealer reveals $f(i)$ in the clear

Reonstruct $a_0 = \sum \delta_i(0) * f(i)$ where $\delta_i(0)$
are the Lagrange coefficients

**Relies on**: $(x_1,y_1),\dots, (x_t,y_t)$ -> uniquely define a polynomial $f(x)$ such that $f(x_i) = y_i$ of degree $t-1$

DKG
n VSS in parallel: n dealers & n receivers
Final secret share $s_i = \sum f_j(i)$
Final public key $P = \sum F_j(0)$

Resharing: n dealers and m receivers
DKG but $a_{i,0} = f(i)$

BLS:
1. Partial signature $\sigma_i = H(m)^{s_i}$
2. Reconstruct final signature $\sigma = \sum_i \delta_i(0) \sigma_i$

Hash ElGamal within SNARK ?:
$c = \{ g^r, H(PK_i^r) + m\}$
Regular hash elgamal:
$c = \{ g^r, H(PK_i^r) XOR m\}$

DKG with weights: Participant $i$ gets $W$ shares $s_{i,0}\dots s_{i,W}$ according its weight

Problems:
* PCS SNARK Friendly + Enc Scheme Snark Friendly
* BLS12-381 or not ?
* BLS12-377 could already work out with KZG openings
* Enc Scheme: can we use jubjub
* scalar field 2^46-primitive roots of unity
* $f(w^1) \dots f(w^{2^{46}})$
* IF Bls12-381: need to use EC-FFT instead, comes with pb:
* $2^{32}$ is the number
* Size of the ciruit is key to find the first curve of the right order
* 2^15 is the max found currently, bruteforce search, exp. work to the power required
* No primitive roots of unity within the group so harder/longer work
* Enc Scheme: is Hash El Gamal within SNARK secure ?
* KZG openings ?
* Evaluation proofs: can we use [Fast Amortized KZG evaluations](https://raw.githubusercontent.com/khovratovich/Kate/master/Kate_amortized.pdf) to compute ?
* Can we use techniques from Halo Infinite to verify ?