• Notation
• Curves Recap
• Cycle of Curves
• 2chain of pairing based curves
• Embedded curve
• DKG operations
• In a SNARK
• Solution 1: Do Non Native Field Arithmetic:
• Solution 2: We use a 2-chain set of curves w/ 2 proofs
• Solution 3: Use a full cycle of curves
• List of curves compatibility
• Proof System & Curves Landscape
• Curves & Proof system
• Status Quo: NI DKG BLS12-377/BW6 with Groth16
• Cool & Futuristic: NI DKG Secp (Bitcoin) curves with Nova
• Hammer way: NI DKG BLS12-381 / BN254
• Interactive DKG
• Platform, L1 L2
• Starkware
• Arbitrum
• Aztec
• Aleo
• Ethereum
• Cost of storing onchain
• Ethereum (TODO)
• Economics Model

Notation

A curve $E(F_q)$ of order $r$ A point is $(x,y) \in F_q^2$ A scalar is $x \in F_r$ Scalar multiplication $xG$

DKG requires operation both on $F_r$ and $E(F_q)$

1. Add, Mul, Inv on $F_r$ -> this for evaluating polynomials $f(1),f(2)...$
2. Add, Sub, Scalar Multiplication on $E(F_q)$

Curves Recap

Cycle of Curves

Two curves “connected” with each other: $E_1(F_q)$ of order $r$ -> can write circuits on $F_r$ $E_2(F_r)$ of order $q$ -> can write circuits on $F_q$

Required for Halo2, Nova, Non Succinct Argument... Why ? Because we need to implement a verifier of the previous proof inside a circuit. Verifier needs to do Group operations -> circuit in $F_r$, verifier needs to do operation in circuit in $F_q$

List: Secp (Bitcoin curves), Pasta curves & many others (”easy” to find a cycle).

2chain of pairing based curves

2 pairing based curves where one is defined on top of the other. Typically used to have a circuit that can verify another pairing based proof.

We have two proofs, one that deals with $F_q$ circuit and one that deals with $F_r$ circuit and the former proof verifies the latter inside its circuit.

• Outer curve $E_1(F_w)$of order $q$ -> circuits can be written on $F_q$
• Allows to write point operations
• Write a circuit that verifies a proof done on the inner curve i.e. verify a Groth16 made on $E_2(F_q)$
• Inner curve $E_2(F_q)$ of order $r$ -> circuits can be written on $F_r$ -> Allows to write scalar operations

Note: There also exists cycle of pairing based curves but these are very costly so it’s not considered here

Embedded curve

Similar to 2chain but the inner curve is a regular DLOG curve.

Take a pairing equipped curve $E(F_q)$ of order $r$ I can also define another DLOG EC $E_d(F_r)$ of order $t$ -> I can write circuits about points in $E_d(F_r)$ -> Useful verify easily ECDSA signatures in SNARK -> Can NOT write circuits about scalars in $F_t$

List: Bandersnatch (on BLS12-381), Jubjub (on BLS12-381), Baby JubJub (on BN254)

DKG operations

$t = n/2 + 1$

1. Create random polynomial $f(x) = a_1 + ... + a_t*x^t$ of degree $t$
2. Evaluate shares $f(1),f(2)...f(n)$ -> operations in $F_r$ -> O(n*t) work on field operation -> Right now, doing Horner's rule (-> Can we use PCS opening proofs to batch verify $f(1),...$ like in Alin’s post? Is it worthwhile ?)
3. Encrypt shares $Enc(f(1)),...,$ -> Hashed El Gamal $\{rG, H(rPK_i) + s_i\}$ or ECIES -> operations in $F_r$ and $F_q$
4. Commit to coefficients $A_1 = a_1G, ...$ -> operations in $F_q$

In a SNARK

→ How to do these operations in a SNARK ?

Within a SNARK, circuit is described in terms of elements of a field $F_p$

• Let's take Groth16: $F_p$ is the order of the pairng curve that we use to make the proof $E(F_w)$

Operations:

• To do 1., we need $r = p$ so it's natural to write the scalar operations
• To do 2., we need $q = p$ so it's natural to write the point operations

Problem: We can't have both $r = p$ AND $q = p$

Solution 1: Do Non Native Field Arithmetic:

This basically emulate $F_q$ operations within $F_r$ . This solution is quite costly because the modulo reduction after each operation (+ * etc) is costly to do in a different field ! Expect 1-2 orders of magnitude more than native.

Solution 2: We use a 2-chain set of curves w/ 2 proofs

Solution 3: Use a full cycle of curves

List of curves compatibility

We say a curve is compatible if there is a precompile operations on miners/smart contract that can execute the operations (scalar multiplication, group operation etc).

Note that it’s difficult in Eth to have a lot of compatibility because of sheer size of network, parties involved etc makes any change much harder. But Rollups are changing the game, have the power to improve things much faster on their side.

Proof System & Curves Landscape

Curves & Proof system

NI DKG = Non Interactive DKG, i.e. in a SNARK

Status Quo: NI DKG BLS12-377/BW6 with Groth16

• Pros: less constraints, "straightforward" implementation
• Cons: Not compatible with mainstream

Cool & Futuristic: NI DKG Secp (Bitcoin) curves with Nova

• Pros: Compatible everywhere
• Cons: DLOG only (no BLS etc), Nova not ready yet (Q3 2022 ?)

Hammer way: NI DKG BLS12-381 / BN254

Either code non native field arithmetic for the point operations (extremely costly) OR use the embedded DLOG curve as the DKG curve (JubJub or Baby JubJub or Bandersnatch)

• Pros: compatible everywhere, pairing
• Cons: NNA is expensive and Jubjub is not well recognized

Interactive DKG

Regular interactive (3 rounds) DKG using blockchain as broadcast channel Compatibility with: BLS12-381,BN254,Secp !

Platform, L1 L2

We’re here considering the usage of L2s as the broadcast layer given the frequency and relatively cheap operations. However that opens now the problem of moving information from L2 to L1 given we want to be “cross chain compatible” or at the very least “eth” reachable.

Starkware

Write the DKG as a Cairo program with secret inputs and public output: there will be a central smart contract that gets these outputs. Compatible with:

• Interative DKG, on Secp (Bitcoin - Cairo library) and BN254 (Cairo library)

Incompatible with:

• NI DKG (proof systems) since there is no privacy unlike Aleo, so the private polynomial in DKG is revealed to the Starkware prover

Pros: Fast resolution from L2→L1 since it’s zkRollup

Cons: Specialized platform (Cairo), can’t re-use future work on other L2 or need to be careful about transpiling from Solidity → Cairo

Arbitrum

Similar to Starkware Compatible with:

• Interactive DKG with Secp, BLS12-381, (BN254?)

Incompatible with:

• NI DKG (proof systems) since there is no privacy

Pros: Compatible natively with EVM smart contracts, so very easy to deploy / change and map from chains

Cons: L2->L1 have to wait for dispute period

Aztec

Not possible now but later down with Noir lang, will be able to build private smart contract on their L2. Compatible with: NI DKG on Baby Jubjub ?

Aleo

Private smart contract, with Noir lang. Compatible with: BLS12-377 !

Ethereum

Compatible with:

• Interactive DKG with Secp
• Interactive DKG with BN254/BabyJubjub , JubJub with BLS12-381 (Q4 2022)

Incompatible with:

• NI DKG with BLS12-377 → BUT there is an EIP https://eips.ethereum.org/EIPS/eip-2539 !

Pros: Direct mainstream adoption

Cons: May be expensive ?

Cost of storing onchain

General formula to get number of kB that each participant must submit to the DKG using 32bytes scalar and points representation (i.e. Secp):

// signature + rG (encryption) + shares for all + coefficients
(32*2 + 32 + 32*1000 + 32*(n/2+1))/1024

Ethereum (TODO)

Storing onchain: According to this table, it costs:

According to this post:

• 20'000 gas / 32byte to write
• > we have 640000 gas for writing 1kB -> for n=1000 961280000 gas, 1gwei, 1$ (32 + 32*1000 + 32*(n/2+1))*20000/1e9

Storing in transaction set only: which is what we need in the end is much less costly

• TODO

Economics Model

We need to think of the way to get crypto economics right within the DKG protocol:

• How do we choose participants ?
• If according to stake, it's not trivial:
• We need n phyiscal participants
• Each participant has more weights than the other
• Are we setting up the threshold in terms of weight or in terms of physical participation ?
• The latter is easier but the former makes more sense