- 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)$

- Add, Mul, Inv on $F_r$ -> this for evaluating polynomials $f(1),f(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$

- Create random polynomial $f(x) = a_1 + ... + a_t*x^t$ of degree $t$
- 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 ?)
- Encrypt shares $Enc(f(1)),...,$ -> Hashed El Gamal $\{rG, H(rPK_i) + s_i\}$ or ECIES -> operations in $F_r$ and $F_q$
- 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.

Curve | Type | Property | Compatibility |

Secp256k1 | dlog | Cycle, no FFT | Eth, BTC, Fil... |

Pasta curves | dlog | Cycle, FFT | Zcash, ETH (with VDF?) |

BN254 | pairing | Embedded curve | Eth (EVM) |

BLS12-381 | pairing | Embedded curve | Eth (Q4 2022), FIL, many are coming to it |

BLS12-377 | pairing | 2chain, embedded | Celo, .... |

# 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 !

**Incompatible with: **Ethereum since it doesn’t support this curve yet (and no plan of doing so)

- Can we do an “oracle

### 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