All things DKG!

<aside> 🗒️ Aims to survey the myriad of DKG protocols for the various key settings

</aside>

Related work survey

Paper	Network Model	Fault tolerance	Adaptive adversary	Discrete log key	Comm. Complexity	Comp. Complexity	Round Complexity	Cryptographic Assumptions	Setup Assumptions	Notes
Pedersen DKG	Sync.	1/2	❌	✅	$O(n\mathcal{B}(\kappa t))$	$O(nt^3)$	$O(\mathcal{R})$	DDH	CRS	‣
JF-DKG	Sync.	1/2	❌	✅	$O(n\mathcal{B}(\kappa t))$	$O(nt^3)$	$O(\mathcal{R})$	DDH	CRS	‣
Canetti et al. DKG	Sync.	1/2	✅	✅	$O(n\mathcal{B}(\kappa t))$	$O(nt^3)$	$O(\mathcal{R})$	DDH	CRS	‣
Foque-Stern DKG	Sync.	1/2	⁉️	✅	$O(n\mathcal{B}(\kappa n))$	$O(n^3)$	$O(\mathcal{R})$	DCR, RO	PKI	‣
Neji et al.	Sync.	1/2	❌	✅	$O(n\mathcal{B}(\kappa ))$	$O(nt^3)$	$O(\mathcal{R})$	CDH	CRS, PKI	‣
Aggregatable DKG	Sync.	1/2	❌	❌	$O(\log{n}\mathcal{B}\left(\kappa n\right)+n\mathcal{B}\left(\kappa\right))$	$O(n^2\log^2{n})$	$O(\mathcal{R}+\log{n})$	SXDH, RO	CRS, PKI	‣
ETHDKG	Sync.	1/2	❌	✅	$O(n\mathcal{B}(\kappa n))$	$O(n+t^2)$	$O(\mathcal{R})$	DDH, RO	CRS, PKI	‣
NIDKG	Sync.	1/2	❌	✅	$O(n\mathcal{B}(\kappa n))$	$O(n^3)$	$O(\mathcal{R})$	DDH, RO	CRS, PKI	‣
Canny and Sorkin - Practical Large scale DKG	Sync.	$1/2-\varepsilon$	❌	✅	$O(n\log^3{n} + \mathcal{B}(\log{n}))$	$O(n^2\log{n})$	$O(\mathcal{R})$	RO	CRS, PKI	‣
Synchronous DKG without broadcasts	Sync.	1/2	❌	✅	$O(\kappa n^3\log{n})$	$O(nt^3)$	$O(1)$	DDH, RO	CRS, PKI	‣
Hybrid-DKG	Weak Sync.	1/3	❌	✅	$O(\kappa n^4)$	$O(n^4)$	$O(n)$	RO	CRS, PKI	‣
Asynchronous DKG	Async.	1/3	⁉️	✅	$O(\kappa n^4)$	$O(n^4)$	$O(n)$	DDH, RO	PKI	‣
Reaching consensus for DKG	Async.	1/3	❌	❌	$O(\kappa n^3\log{n})$	$O(n^3)$	$O(1)$	SXDH, RO	CRS, PKI	‣
Gao et al. DKG	Async.	1/3	❌	❌	$O(\kappa n^3)$	$O(n^3)$	$O(1)$	SXDH, RO	CRS, PKI	‣
Practical ADKG	Async.	1/3	❌	✅	$O(\kappa n^3)$	$O(n^4)$	$O(\log{n})$	DDH, DCR, RO	CRS, PKI	‣

Notes

Fouque-Stern DKG (‣) claims adaptive security. It proves static security and sketches adaptive security. Is it still an adaptively secure DKG?
Pedersen DKG and JF-DKG (‣) both have a worst-case computation cost of $O(nt^3)$. This comes from all nodes $(n)$ have to verify $(2t)$ dealer complaints (in the first half, honest nodes are complaining against Byzantine dealers, and in the second half, the Byzantine nodes are complaining against honest dealers), each of which contains $t$ individual complaints, and each verification operation costs $t+1$ computations.
Pedersen DKG and JF-DKG (‣) have a worst-case communication complexity of $O(n\mathcal{B}(\kappa t))$ since each dealer has to post the commitments to the polynomials (size $O(\kappa t)$).
Neji DKG (‣) has a worst-case communication complexity of $O(n\mathcal{B}(\kappa))$. In their disputation protocols, $n-2$ nodes need to post some values.
Neji DKG (‣) has a worst-case computation complexity of $O(nt^3)$ since $n-2$ nodes verify $2t^2$ dealer complaints, in each of which there are $O(t)$ computation operations.

Problems 🧰

Different access structures
Separate parties from stake
Zero-knowledge circuit to make DKG publicly verifiable (GOAL: use in mainstream production systems)
Arbitrum is an L2 solution to execute contracts, Holy-grail DKG is a proposed L2 solution to perform DKG

Secret Sharing

Paper	Network Model	Fault tolerance	Adaptive adversary	Scalar secret	Comm. Complexity	Comp. Complexity	Round Complexity	Cryptographic Assumptions	Setup Assumptions	Notes
Feldman VSS	Sync.	1/2	✅	✅	$O(\mathcal{B}(\kappa t) + t\mathcal{B}(\kappa) + n\kappa)$	$O(nt)$	$O(1)$	DL		‣
Pedersen VSS	Sync.	1/2	✅	✅	$O(\mathcal{B}(\kappa t) + t\mathcal{B}(\kappa) + n\kappa)$	$O(nt)$	$O(1)$	DL	CRS	‣
Hybrid VSS	Weak Sync.	1/3	❌	✅	$O(\kappa n^2 +\mathcal{B}(1))$	$O(n^2)$	$O(\mathcal{R})$	DL, RO	CRS, PKI	Hybrid-VSS (‣)
Cachin et al. - Async VSS	Async.	1/3	❌	✅	$O(\kappa n^3 )$	$O(n^2 )$	$O(1 )$	DL	PKI	‣
eAVSS	Async.	1/3	✅	✅	$O(\kappa n^2 )$	$O(n^2 )$	$O(1 )$	DL, SXDH, q-SDH	CRS, PKI	‣
VSSR	Weak Sync.	1/3	❌(/✅)	✅	$O(\kappa n^3 )$	$O(n^2 )$	$O(1 )$	DL, SXDH, q-SDH, RO	CRS, PKI	‣
hbACSS	Async.	1/3	❌(/✅)	✅	$O(\kappa n^2\log{n} )$	$O(n^2 )$	$O(1 )$	DL, SXDH, q-SDH, RO	CRS, PKI	‣
eVSS	Sync.	1/2	✅	✅	$O( t\mathcal{B}(\kappa) + n\kappa)$	$O(nt)$	$O(1)$	DL, SXDH, q-SDH	CRS, PKI	eVSS (‣)
HAVEN	Async.	1/3	✅	✅	$O(\kappa n^2\log{n} )$	$O(n^2 )$	$O(1)$	DL, Bulletproof?	CRS, PKI	‣
Schoenmakers PVSS	Sync.	1/2	❌	❌	$O(\mathcal{B}(\kappa n) )$	$O(n^2t )$	$O(\mathcal{R} )$	DDH, RO	CRS, PKI	‣
Heidaravand et al. - HV09	Sync.	1/2	❌	❌	$O(\mathcal{B}(\kappa n) )$	$O(n^2t )$	$O(\mathcal{R} )$	SXDH	CRS, PKI	‣
SCRAPE	Sync.	1/2	❌	❌	$O(\mathcal{B}(\kappa n) )$	$O(n^2 )$	$O(\mathcal{R} )$	SXDH	CRS, PKI	‣
NIDKG	Sync.	1/2	❌	✅	$O(\mathcal{B}(\kappa n) )$	$O(n^2 )$	$O(\mathcal{R} )$	DDH, RO	CRS, PKI	‣
Eurocrypt Gentry et al.
Towards Scalable threshold cryptosystems

Implementation Survey

Implementation	Language	Networking core	Network
Ferveo	Rust	Tendermint	Sync.
Dfinity	Rust	ICC	P. Sync.
AggDKG	Rust	🚫	🚫
DRand	Golang	Custom	Sync.
ETH-DKG	Solidity	Ethereum	Sync.
DKG on EVM	Solidity	Ethereum	Sync.
DKGPG	C	Custom	Sync.
Gnosis	Golang	🚫	🚫
HERB	Golang	Cosmos	Sync.