- Updates
- Why
- How
- Latest Design:
- Milestones
- Q1’22
- Next Steps Orientations & Problems:
- Q2’22
- Notes
- Optimizations
- Potential endgame systems:
- BLS on BLS12-377 + BW6
- Nova/Halo2 using secp/secq bitcoin curves
- Regular DKG onchain + threshold ECDSA,
- Notes
- 28/02/2022 w/ Porcu
- 08/02/2022 w/ Nicola

# Updates

10/02/2022:

- Presentation done https://drive.google.com/file/d/1gjwdzruJCgIgJM9qSrYBCnj39BuxoGje/view
- Next step are to
- Polish code and write blog post
- decide what to do with this, where to go, what is the end goal

03/01/22:

- Public inputs problems now resolved
- Commitment of the inputs and verified inside the SNARK
- Lots of problem with the encoding
- Presentation to be done on the 4th

27/01/22:

- DKG in SNARK PoC passing !
- Planning on doing presentation and quick benchmark for next week
- Future work may be looking at threshold ECDSA -
- Can it be used for randomness beacon ?

20/01/22:

- Feldman commitment done, ECIES with Poseidon encryption implemented
- Two potential paths for the polynomial evaluation
- Either do NonNativeField computations directly in the same circuit
- Either do a separate Groth16 directly on BLS12377 that computes the polynomials evaluation, public inputs would be the coefficients and all evaluations. Then verify the Groth16 inside the higher level proof.
- TODO:
- Benchmark small solutions on the two approaches and decide which one will be best

# Why

Being able to do a DKG inside a SNARK would bring us a lot closer to the Holy Grail DKG target as this provide both

- Public Verifiability via the SNARK guarantees
- Aggregatibility via SnarkPack or other

**In details:**

In essence a DKG consists of the following:

- Create a secret polynomial $f(x) = a_0 + \dots + a_{t-1}*x^{t-1}$ where $t$ is the threshold
- Create the public polynomial $F(x) = f(x)G$ where $G$ is a generator of the group
- Create encrypted shares $Enc(P_1,f(1)), \dots, Enc(P_n,f(n))$ where $n$ is the number of participants and $P_i$ is the public key of the $i$-th participant
- Prove that the encrypted shares are correctly constructed from $f(x)$

The last step is the problematic one as there is no verifiable encryption scheme that fits our needs here.

# How

We describe here first the "naive" way and then a more optimized way that trade-offs some

**Computing the shares and encryption inside the SNARK: **Basically doing all the steps inside a SNARK.

### Latest Design:

- Overall SNARK on BW6 that proves:
- The Feldman commitment is correctly computed
- The encryption shares are correctly computed
- Verification of second below proof is correct
- SNARK proof over bls12-377 that proves
- The correct evaluation of the polynomial, i.e. correct computation of all the shares

The whole design is detailled in these slides.

# Milestones

## Q1’22

- Sharing ideas with Collaborators (redacted)
- output is that the basic design was aligned with what XXX had in mind if he were to do it now
- Description & implementation of MVP
- Benchmark of the MVP
- TODO: Blog post, what have I learned etc

### Next Steps Orientations & Problems:

- Continue on same Groth16 path with optimizations:
- Better arithmetic constraints for encryption of the shares
- Less hashing of points (only X and not X Y Z in Poseidon)
- Better evaluation verification for share evaluation
- How to
*not*be linear in public inputs (public keys, encryption shares etc): - Regardless of proof system, that is gonna be a bottleneck
- Can we use rollup style ? proof that uses all the public inputs and makes a proof that it corresponds to commitment inputs to each proofs. Problem is how to trust he used correct ones, and if he shares the data ?
- Look out for recursive snark systems:
- Big potential of not being limited by CRS like Groth16
- Big downside of being limited to pairing based
- Look out for Plonkish snark systems:
- Big potential of getting larger number of participants (< recursive though)
- Keeps the pairing curves
- Cons: Very early implementations, gadgets are not necessarily ready
- Use MVP proof and design & implement MVP protocol

## Q2’22

# Notes

We have

$BW6: \#E(F_{q_1}) = |F_r|\\ BLS12-377: \#E(F_r) = |F_{q_2}|\\$So to verify a SNARK over $E(F_r)$ inside a circuit of the higher level proof we have:

- High level proof over $E(F_{q_1})$, constraints are written in $F_r$
- Sub level proof over $E(F_r)$, constraints are written in $F_{q_2}$

# Optimizations

- Getting the same randomness r for each encryption
- DONE
- Getting the public inputs as commitment inside of a hash
- DONE
- Do IPP instead of evaluation because we can BATCH IPP evaluation
- OR For evaluation, special formulas for doing batch scalar multiplication, pippenger style a1G + a2G2 + ...
- Pack the Fr into Fq for hashing and still performs Fq addition → since r << q it’s fine for one addition

TODO:

- Actually hash the public key insides !

## Potential endgame systems:

## BLS on BLS12-377 + BW6

That gets us

- BLS signature scheme is pretty efficient and known
- a and b : we can do identity based encryption or things like “witness decryption”

Pros:

- We can do it now !

Cons:

- curves not well supported, relatively expensive

## Nova/Halo2 using secp/secq bitcoin curves

That gets us:

- Threshold ECDSA
- El Gamal only
- Compatible with Eth
- Compatible with signing

Pros:

- Potentially really scalable because of recursive SNARK structure

Cons:

- Lot of engineer work to make it work with bitcoin curves - by default it’s using pasta curves
- Decryption less efficient: one decryption per ciphertext

## Regular DKG onchain + threshold ECDSA,

That gets us similar to previous.

Pros:

- We can do it now, very easy

Cons:

- Not so scalable & interactive (every message has to be posted on the bulletin board, multiple rounds needed)
- Decryption less efficient: one decryption per ciphertext

# Notes

## 28/02/2022 w/ Porcu

Nova: where it is, where to go, recursion, GPU ? ASM?

Bitcoin curve ?

ARG ?

Nova:

- Split accumulator step implemented but recursion is in stage, done this week hopefully
- Final SNARK implemented, better than Spartan
- different circuits (coprocessors) → it’s in the plan
- we can do now for circuit size of m+n
- in the plan to make it two different circuits, but recursive step will be more expensive
- Binary Merkle IVC to parallel operations

## 08/02/2022 w/ Nicola

We would like the ideal system to be:

- Compatible with popular signature scheme
- Compatible with simple to use enc/dec scheme
- El Gamal
- Identity based encryption / “threshold witness decryption”
- Compatible with Eth (now or later)
- Compatible with transaction signing on major blockchains (like ecdsa with secp)
- This enables the network to sign regular transactions for themselves -
- is it really useful ? Would need network to have funds, and that makes things more complex...

- What’s the main endgoal here
- Seems like general threhsold network may be the endgoal
- Ethereum compatibility ?
- BLS12-377 + BW6 not supported
- We need either BN254 / BLS12-381, seckp curves (or maybe pasta curves)
- Requirements:
- Comp. with popular sig scheme
- Comp. simple to use/prove threshold enc/dec scheme
- Comp. with MPC based “setting”
- Compatibility with Eth.
- Signature scheme compatible with “transaction signing”