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:
  • Need to express constraints in \(F_q\)
    • 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

Potential optimization #1:: 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.

Potential optimization #2:: hash directly in projective form

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

Optimization Implemented:: 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.

The more public inputs there are, the longer the verification time is.

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.
Need more constraint to make sure both are equal
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

Potential optimization #3:: 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 !

For points in the witness, I don't check correct subgroup membership.

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

Potential optimization #4:: 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.