# DKG in SNARK - demo day
---
## Recap on DKG
* **Goal:** Distributed key pair $P$ amongst $n$ parties such that
* $n/2 \lt t \lt n$ parties are required to collaborate to reconstruct it.
* Set of less than $t$ parties can not learn anything about $P$
* **Why**: Used by drand for example, other system now like Axelar
* **How**: basic version is usually $n$ instances Verifiable Secret Sharing (VSS) in parallel
---
## Recap on VSS
* There are three phases:
* Deal Phase <- Crux of the protocol
* Complaint Phase
* Justification Phase
---
## Deal Phase
* **Random polynomial**:
* $f(x) = a_1 + a_2x + \dots + a_tx^t$
* **Share evaluation**:
* $s_1 = f(1), s_2 = f(2),\dots, s_n = f(n)$
* **Share Encryption**:
* $C_{i,j} = \{rG, H(rPK_j) + s_j \} \in E(F_q) \times F_r$
* random $r$.
* **Commitment**: $F(x) = f(x)G$
* $A_1 = a_1G, A_2 = a_2G,\dots, A_t = a_tG$
* In other words, $F(x) = f(x)G$
---
# Verification of the deal
* **Correct Decryption**: each party i tries to decrypt their $C_i$
* **Consistent Share**: $s_i * G =?= F(i)$
* If one of the two steps doesn't work, then issue a Complaint
* !! **Reason why VSS is interactive protocol** !!
---
## Non Interactive DKG
The goal is to have a proof of correct
1. share evaluation
2. share encryption and
3. polynomial commitment.
We can do this in a SNARK !
---
## Polynomial Evaluation in SNARK
This one is easy:
* **Input**:
* coefficients $a_1,\dots,a_t$, indices $1,\dots,n$
* shares $s_1,\dots,s_n$
* **Circuit**:
* For each indices $i$:
* Evaluate $f(i)$ and check $f(i) == s(i)$
---
## Encryption & Commitment Problem
* **Encryption**: $\{rG, H(rPK_i) + s_i \} \in E(F_q) \times F_r$
* **Commitment**: $A_1 = a_1G, A_2 = a_2G,\dots, A_t = a_tG$
* **Problem**:
* <span style="color:red">**Need to express constraints in $F_q$**</span>
* Scalar multiplication deals with points in $(x,y) \in F_q^2$
* <span style="color:red">But circuits constrants are in $F_r$ !</span>
---
## 1 Layer recursive proof
Solution is to use a proof where
* Constraints are in $F_q$ !
* Link with the previous proof by having the new one on $E'(F_p)$ with subgroup of prime order $q$
![](https://i.imgur.com/haOAeQx.png)
---
## Circuit Layout
Now we have 2 circuits:
![](https://i.imgur.com/J7LcMeM.png)
---
## Commitment of coefficients
Now that we have circuits in $F_q$, we can do ellitptic curve point arithmetic easily.
For scalar multplication ($rG$) is "double and add":
**First transform $r$ to bits** and then
![](https://i.imgur.com/ybOQSM4.jpg)
---
## Share Encryption
$\{rG, H(rPK_i) + s_i \} \in E(F_q) \times F_r$
* $rG$ is scalar multiplication as in the commitment part.
* <span style="color:red">**Problem 1**: $H(rPK_i) + s_i$ happens in $F_r$, but circuit is in $F_q$ now!</span>
---
**Problem**: $H(rPK_i) + s_i$ happens in $F_r$, but circuit is in $F_q$ now!
**Solution** (implemented): use Non Native Arithmetic (emulate $F_r$ operation inside $F_q$)
---
$\{rG, H(rPK_i) + s_i \} \in E(F_q) \times F_r$
<span style="color:purple">Optimization Implemented:</span>: No need to have a distinct $r$ for each encryption
---
### Public inputs in DKG
**Problem**: Going at (medium) scale, i.e. 1000, means doing at least a $3000$ sized scalar multiplication. That's too long.
---
### Reducing public inputs
**Solution**: Commit to the inputs and give that as public input
Given we are using _all_ inputs, hashing is enough.
$H(allmypublicinputs)$
---
## Results
Very basic benchmark, done on a AWS machine with 48 cores and 192GB of memory
Memory needed by trusted setup.
Threshold is set each time at 50% of $n$.
Curves: BLS12-377 for proofs on $F_r$ and BW6 for proofs on $F_q$
* $F_q$ is 377 bits
* $F_p$ (BW6) is more like ~700 bits, so costly !
----
### Total Constraints
16 millions for $n = 800$
![](https://i.imgur.com/fDksGah.jpg)
----
### Inner proof constraints
600k for $n=800$
![](https://i.imgur.com/5oPHKI1.jpg)
----
### Proving time
8mn for $n=800$
![](https://i.imgur.com/5XGl8yN.jpg)
----
### Verifying time
**Including the hash of the commitment**
117ms for $n=800$
![](https://i.imgur.com/rMKsAzD.jpg)
---
## Future
----
### General Scaling problem
Regardless of how many participants to we allow, we need:
1. the "public input verification" to scale as well (no linear number of inputs!)
2. and/or an efficient way to pack each individual proofs
----
### Snarkpack it
Because we have only 1 public input, Snarkpack the proofs can be efficient.
One proof per participant,all bundled together. Verification times will be bounded by computing the public input commitment hash though.
----
### Alternative polynomial evaluation check
(w/ Rosario)
----
### Alternative proofs systems
* We pay a high price for using 1 level recursion pairing based curves
* Halo2 / Nova are recursive proofs based on DLOG
* **No bounds on number of shares** unlike CRS size for Groth16
* Are we ok to use DLOG systems only ?
* Threshold Schnorr can be used as randomness beacon if designed carefully
* Threshold encryption works the same way
* **No identity based** tricks anymore though
* How are public inputs dealt with ?
----
### Alternative proofs systems 2
* We could also use Groth16 still but only do the DKG with a DLOG based curve
* JubJub curve is what is used in Zcash (and many other places)
* Base field of Jubjub is the scalar field of BLS so constraints are good for doing group operations
* Problem: we can't do scalar operations on the Jubjub curve now (we don't have that "inner" proof)
----
#### Weights
Assume we *weights* participants with different number of shares
Ex: A has 3 shares, B has 10 shares etc
* Requires _more_ shares now
* Means reduces the number of _participants_
{"metaMigratedAt":"2023-06-16T19:24:50.693Z","metaMigratedFrom":"YAML","title":"DKG in SNARK - demo day","breaks":"true","contributors":"[{\"id\":\"186a5b34-2ac6-4991-adab-15982380b05d\",\"add\":7801,\"del\":1829}]"}