# 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$  --- ## Circuit Layout Now we have 2 circuits:  --- ## 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  --- ## 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$  ---- ### Inner proof constraints 600k for $n=800$  ---- ### Proving time 8mn for $n=800$  ---- ### Verifying time **Including the hash of the commitment** 117ms for $n=800$  --- ## 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_