In threshold cryptography, participants need to run a Distributed Key Generation before anything. After the DKG has been succesfully completed, nodes can then uses theirs shares for threshold signing or encryption. The most famous and used DKG is the Pedersen one but it lacks several properties that we would like to have in order to use threshold cryptography at scale in a permissionless environment.
This documents highlights what would be the properties of an ideal / perfect DKG. It first presents in which settings the DKG would be run and some notations then define the properties.
We assume the DKG protocol is ran in permissionless setting where each participant has an associated known public key and a public stake. We assume we can express the stakes in "small units", i.e. discretize the stakes of each participants to integers (note it can be that all stakes = 1). Participants to the DKG are chosen randomly in proportion to their stake. The random selection is assumed to be public (at the beginning - we may want to relax that assumption to have private "election" as in Single Secret Leader Election).
We assume the existence of a bulletin board (BB). It does not have necessarily to be a blockchain with "computation features" but we should assume it's highly likely that it is the case. In case it is not, we assume clients can always refer to the BB and run any computations locally with the data stored on the BB.
We assume there is a proportion of faulty nodes $f$ and a proportion of byzantine nodes $t$. (TODO: fix notation with common notations).
Note that in the context of stakes/weight, we are considering f and t to be stake proportions rather than absolute numbers.
We assume the DKG participants can communicate via a gossip network.
We want the shares of each node to be a scalar field element (using elliptic curves). More specifically, if we use an elliptic curve $E(F_q)$ of order $r$, we want the share of each node to be an element from $F_r$. As opposed to some publicly verifiable DKG schemes where the resulting share lies in the elliptic curve itself $E(F_q)$. Even better if this is the scalar field of a pairing equipped curve such as BLS12-381. The end goal is to be able to rely on all the previous and compatible signature & encryption schemes which have nice properties (random beacon with BLS combined with identity based world, etc)
While aggregatable DKG is a great system (because of aggregatability and verifiability), the biggest problem is that they rely on PVSS and their sig + enc schemes leads have higher complexity and requires $G_T$ computations (3 $G_T$ computations to derive the randomness from the VUF)
TODO: give more detail on that, may actually be workable. Anoma is using this in prod.
Gaining an order of magnitude more: targeting a thousand nodes would be ideal.
Each node should have weights in proportion to their stakes. Trivial solution is to have different number of shares according to the stakes.
The threshold protocols (signatures generation & "partial" enc/decryption) should work with this notion of weights. (Using naive approach, a node will sign with each share it has for example).