---
type: slide
header-includes:
\usepackage{xcolor}
---

# How to perform a DKG with SNARKs

---

## Recap on Threshold Cryptography

* **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$

* **How**: basic version is usually $n$ instances Verifiable Secret Sharing (VSS) in parallel

---

## Notation

* Elliptic curve $E(F_q)$ defined over $F_q$
* Prime order subgroup $F_r$ of order $r$
* Generator $G \in E(F_q)$ of the subgroup
* Affine coordinates for any point $(x,y) \in F_q^2$
* Projective coordinates for any point $(x,y,z) \in F_q^2$
* We have $n$ parties, each with a public key $PK_i \in E$
* Threshold is $t$

---

## Recap on VSS

* There are three phases:
* Deal Phase <- Crux of the protocol
* Complaint Phase
* Justification Phase

---

## Deal Phase

Party $i$ do the following:
* **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 !

---

## SNARK constraints

One can write these checks in constraints. Each constraint is of the form
* $a + b + \dots = c$
* $a * b = c*$

Each proof can have public inputs and private inputs (witness), in $F_r$
For Groth16:
* Each element is in $F_r$.
* The prover, proof and verification happens with points on $E(F_q)$

---

## Polynomial Evaluation in SNARK

This one is easy:
* **Input**:
* coefficients $a_1,\dots,a_t$
* indices $1,\dots,n$
* evaluations $s_1,\dots,s_n$
* **Circuit**:
* For each indices $i$:
* Evaluate $a_1 +a_2*i +\dots + a_t*i^t$
* Check if consistent with $s_i$
* **Output**:
* Groth16 proof ($A,B,C \in F_q^3$)

---

## 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$
* But circuits constrants are in $F_r$ !

---

## 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 point addition ($P + G$) for example:

----

For scalar multplication ($rG$) is "double and add":
**First transform $r$ to bits** and then

----

Transforming $r \in F_r$ to bits is not "free" because we need to constraint each "bit" in the witness is really boolean.
TODO: put the constraints

---

## Share Encryption

$\{rG, H(rPK_i) + s_i \} \in E(F_q) \times F_r$

* $rG$ is scalar multiplication as in the commitment part.

* **Problem 1**: $H(rPK_i) + s_i$ happens in $F_r$, but circuit is in $F_q$ now!

----

**Problem 1**: $H(rPK_i) + s_i$ happens in $F_r$, but circuit is in $F_q$ now!
* **Solution 1** (implemented): use Non Native Arithmetic (emulate $F_r$ operation inside $F_q$)
* **Solution 2** : Give the two elements $H(rPK_i)$ and $s_i$ to the proof on $F_r$ and make the addition there

<span style="color:purple">Potential optimization #1:</span>: Look which one is best

----

**Problem 2**: Hashing with Poseidon takes inputs as $F_q$ but need to hash a point in $E(F_q)$

**Detail**: We therefore need to do $H(x,y)$ for a point $(x,y) \in E(F_q)$
However point computation are in *projective form* in circuit.
Library does the conversion automatically -> cost some constraints.

<span style="color:purple">Potential optimization #2:</span>: hash directly in projective form

----

$\{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

The _same_ prover is doing all the encryptions, so it doesn't matter if the same _r_ is re_used.
(I think this is ok :D )
We go from $n$ scalar multiplication to $1$ for $rG$ in circuit.

---

## Inputs to the circuit

These are elements the verifier needs to provide.
In Groth16, verifier needs to compute many scalar multiplication:
$\sum_i a_iV_i$

where $a_i \in F_q$ is the public input and $V_i \in E(F_q)$ is a point.

<span style="color:red">The more public inputs there are, the longer the verification time is.</span>

----

### Public inputs in DKG

So far our public inputs would be:
* $t$ points as the coefficients, i.e. $2t$ $F_q$ elements
* $n$ ciphertexts, i.e. $(2+1)n$ $F_q$ elements

**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.

**Problem**: Some inputs are in $F_q$ (coefficients) but some are in $F_r$ !

**Solution**:In the curve we are using, $r < q$ so we can embed a $F_r$ element inside a $F_q$ element.

----

**Status**: now a share is represented as bits AND as $F_q$ element.
<span style="color:red">Need more constraint to make sure both are equal</span>
This costs >256 constraints to pass from the embedded $F_q$ to the bits representation and check equality, per scalar.


----

### Reducing public inputs

**Cons**:
* additional cost in circuit, longer prover time !
* Verifier still computes hash outside, and it's Poseidon hashing.

**Pros**:
* Only one public input needed now on Groth16

<span style="color:purple">Potential optimization #3:</span>: More compact representation of public inputs & compare


---

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

<span style="color:red"> For points in the witness, I don't check correct subgroup membership. </span>

----

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

(from Rosario)
* IPP can be used to verify polynomial evaluations
* Can batch IPP evaluation proofs so $n$ in batches are much cheaper than $n$ individual evaluations
* Can we use KZG as well in the outer proof ?
* Need to make sure commitment = polynomial commitment as well ?

----

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

----

Solution 1: Need to go to thousands of shares in a SNARK

We distribute more shares to those with more weights

<span style="color:purple">Potential optimization #4:</span>: use roots of unity and FFTs when doing the polynomial evaluation

Cons: big SNARK if we stay in the Groth16 model

----

Solution 2: Allow multiple SNARKs per prover
* 1st SNARK distributes one share to everyone
* 2nd SNARK distributes one share to $m < n$
* 3nd SNARK distributed one share to $p < m$
* ...

Cons: Granularity of weight defined by number of snarks prover can do.