• 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

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:

1. Overall SNARK on BW6 that proves:
1. The Feldman commitment is correctly computed
2. The encryption shares are correctly computed
3. Verification of second below proof is correct
2. SNARK proof over bls12-377 that proves
1. 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
• Code & slides detailing the circuit
• Benchmark of the MVP
• benches
• 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

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

Potential endgame systems:

BLS on BLS12-377 + BW6

That gets us

1. BLS signature scheme is pretty efficient and known
2. 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:

1. Threshold ECDSA
2. El Gamal only
3. Compatible with Eth
4. 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:

1. Compatible with popular signature scheme
2. Compatible with simple to use enc/dec scheme
1. El Gamal
2. Identity based encryption / “threshold witness decryption”
3. Compatible with Eth (now or later)
4. 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”