owned this note
owned this note
Published
Linked with GitHub
---
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$ !
![](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 point addition ($P + G$) for example:
![](https://i.imgur.com/crj5noe.jpg)
----
For scalar multplication ($rG$) is "double and add":
**First transform $r$ to bits** and then
![](https://i.imgur.com/ybOQSM4.jpg)
----
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.
![](https://i.imgur.com/hsYqDQm.png)
----
### 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
![](https://i.imgur.com/CEJxCo9.png)
---
## 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$
![](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
(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.