- 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
- Cost of storing onchain
- Ethereum (TODO)
- Economics Model
A curve of order A point is A scalar is Scalar multiplication
DKG requires operation both on and
- Add, Mul, Inv on -> this for evaluating polynomials
- Add, Sub, Scalar Multiplication on
Cycle of Curves
Two curves “connected” with each other: of order -> can write circuits on of order -> can write circuits on
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 , verifier needs to do operation in circuit in
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 circuit and one that deals with circuit and the former proof verifies the latter inside its circuit.
- Outer curve of order -> circuits can be written on
- Allows to write point operations
- Write a circuit that verifies a proof done on the inner curve i.e. verify a Groth16 made on
- Inner curve of order -> circuits can be written on -> 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
Similar to 2chain but the inner curve is a regular DLOG curve.
Take a pairing equipped curve of order I can also define another DLOG EC of order -> I can write circuits about points in -> Useful verify easily ECDSA signatures in SNARK -> Can NOT write circuits about scalars in
List: Bandersnatch (on BLS12-381), Jubjub (on BLS12-381), Baby JubJub (on BN254)
- Create random polynomial of degree
- Evaluate shares -> operations in -> O(n*t) work on field operation -> Right now, doing Horner's rule (-> Can we use PCS opening proofs to batch verify like in Alin’s post? Is it worthwhile ?)
- Encrypt shares -> Hashed El Gamal or ECIES -> operations in and
- Commit to coefficients -> operations in
In a SNARK
→ How to do these operations in a SNARK ?
Within a SNARK, circuit is described in terms of elements of a field
- Let's take Groth16: is the order of the pairng curve that we use to make the proof
- To do 1., we need so it's natural to write the scalar operations
- To do 2., we need so it's natural to write the point operations
Problem: We can't have both AND
Solution 1: Do Non Native Field Arithmetic:
This basically emulate operations within . 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.
Cycle, no FFT
Eth, BTC, Fil...
Zcash, ETH (with VDF?)
Eth (Q4 2022), FIL, many are coming to it
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
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.
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)
- 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
Similar to Starkware Compatible with:
- Interactive DKG with Secp, BLS12-381, (BN254?)
- 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
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 ?
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
- Interactive DKG with Secp
- Interactive DKG with BN254/BabyJubjub , JubJub with BLS12-381 (Q4 2022)
- 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
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
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