Distributed Key Generation for Blockchains

Distributed Key Generation (DKG) is a cryptographic protocol that allows multiple parties to jointly generate a shared public-private key pair without relying on a trusted authority. The private key is never fully reconstructed; instead, it remains secret-shared among participants, ensuring security even in the presence of malicious parties. Through full decentralization, DKG enhances trust minimization in cryptographic systems, including threshold signatures, threshold encryption, distributed VRFs,  secure multiparty computation, etc. In particular, as these primitives are widely used in blockchain applications such as consensus protocols, state/execution commitments, and mitigating MEV/ordering, DKG plays a crucial role in order to maintain a ‘no single point of trust’ requirement.

With threshold cryptography continuing to gain prominence in blockchains and distributed systems, DKG has become a crucial area of research. While numerous studies have explored efficient solutions to the DKG problem, they primarily focus on standalone settings, aiming to generate a final public key and corresponding secret keys among a group of participants. However, with the increasing adoption of blockchain technology, many on-chain applications require the ability to validate threshold signatures directly on-chain. In particular, on-chain smart contracts need access to the DKG public key to verify threshold signatures within the blockchain environment.

This blog post highlights a new problem: DKG for blockchain, which mandates that the final public key generated through the DKG process be available on the blockchain for on-chain verification. Here, the DKG protocol should be agnostic to the network assumptions of the (destination) blockchain that uses it. In particular, the design must be asynchronous to ensure that the network assumptions of the employed blockchain system remain unchanged. In addition, it is ideal for the DKG protocol to generate field element secrets to ensure compatibility with widely-used threshold cryptosystems such as BLS signatures, ECDSA, EdDSA, El Gamal Encryption or Boneh-Franklin Identity-based encryption.

Existing standalone asynchronous DKG protocols can be adapted for blockchain by first executing the DKG and then posting the final public key on-chain. However, this approach inherits the high communication and computation costs of the underlying asynchronous DKG and increases round complexity due to the need for multiple consensus instances. It also demands greater on-chain storage for publishing the public key. Alternatively, while non-interactive DKG protocols achieve minimal round complexity, they typically incur significant on-chain storage and high computational overhead.

A Fresh Look: Leveraging Blockchain’s Unique Capabilities

In this blog post, we present a simple and efficient high-threshold DKG for blockchain. Our solution uses the blockchain itself to solve the DKG problem. Indeed, we solve the DKG problem for use over the blockchain by using the same blockchain itself. In particular, we rely on the in-built consensus/ordering mechanism of the blockchain to solve the agreement on a core set (ACS) problem, which identifies the set of dealers who have shared their secret correctly. Additionally, we use random beacons—commonly available as a service on most blockchains—to sample a sub-committee of dealers, enhancing efficiency.

Using Blockchain for Consensus/Ordering

Our first key idea is to leverage the blockchain’s built-in consensus mechanism to solve the ACS problem. In our DKG protocol, we use point-to-point channels for message exchange during the secret sharing phase, avoiding consensus primitives except for ACS. Crucially, the blockchain is utilized only once—to solve ACS and post the final DKG public key—significantly reducing the round complexity.

Using Random Committees via Randomness Beacon

Existing standalone DKG approaches require all parties to act as dealers, resulting in high communication and computation costs. In this work, we leverage publicly verifiable and unpredictable random beacons, widely available on blockchains like Supra, Algorand, and Aptos, to elect an honest majority sub-committee of n_c << n nodes with high probability (based on the hypergeometric distribution). We call such an honest majority sub-committee as clans. These clan nodes act as dealers and verifiers for secret sharing. This committee-based approach enables us to significantly reduce overhead while maintaining security.

We begin by exploring a few strawman solutions that leverage random beacons and the blockchain’s built-in consensus mechanism to build intuition. We then introduce our efficient DKG protocol. Throughout, we refer to the entire set of n parties as a tribe.

Towards Efficient DKG for blockchains

Using random beacons, we can elect a clan of dealers and have them perform secret sharing using via non-interactive publicly verifiable secret sharing scheme where the dealers simply post the vector of publicly verifiable encrypted shares (PVSS vector) on to the blockchain for consensus (as shown in figure below). A set of f_c+1 valid PVSS vectors output by the blockchain can then be used to derive the public and corresponding secret keys, where f_c < n⁄2 represents the number of Byzantine parties in the clan. This approach has lower round complexity but incurs higher on-chain storage of 𝜅n_cn and computation costs of at least n_cn per party, where 𝜅 is the security parameter. This is undesirable due to high on-chain storage cost.

One could optimize on-chain storage by having dealers disseminate the PVSS vector to the clan and collect a proof of data availability (PoA), ensuring that at least one honest party has received the PVSS vector with high probability. This PoA is then submitted to blockchain for consensus, allowing the valid PVSS to be retrieved later for establishing DKG keys, as shown in the figure above. However, this approach still results in on-chain storage costs of 𝜅n_c+n_c² (when using multi-signatures) and computation costs of at least n_cn  per party.

To reduce computation costs, we can build upon the Simplified VSS protocol, where a dealer individually distributes secret shares along with a commitment to the coefficients of the secret-sharing polynomial. This commitment allows parties to verify the correctness of their received shares. Each party then returns a signature on the commitment to the dealer if their share is consistent with the commitment. The dealer collects a quorum of valid signatures and publishes publicly verifiable encryptions of secret shares only for parties that did not provide signatures. A dealer is accepted if there is a quorum of valid signatures and the encryptions for missing shares are valid. Notably, each party only verifies encryptions for missing signatures, reducing computational overhead. However, this approach still requires sending the commitment to all parties, resulting in at least 𝜅n_c²n off-chain communication for n_c dealers.

Our Approach

We refine the Simplified VSS approach to minimize communication while preserving its computational efficiency. In our protocol, the dealer P_j directly sends each party P_i its secret share s_j,i without any commitment (Step 1). Instead, party P_i generates an individual commitment g^s_j,i, signs it and returns the signature to the dealer (Step 2). The dealer then gathers a quorum of signatures and constructs a vector of encryptions for parties that did not provide signatures. Additionally, the dealer creates a commitment to the evaluations of the secret sharing polynomial (i.e., g^s_j,0, …,g^s_j,n) and submits the quorum of signatures on the individual commitment, encryptions and the commitment only to the parties in clan (Step 3). If at least f_c+1 parties in the clan verify these components, the dealer’s secret sharing is accepted as valid. This approach reduces the communication to 𝜅n_c²n for n_c dealers. Moreover, only the clan members need to verify the encryptions, resulting in a computational overhead of n_cn per clan party, while all other parties perform only n_c computations.

After the secret sharing phase, valid secret sharing instances must be posted on the blockchain for consensus/ordering. However, directly posting them incurs high on-chain storage costs. To mitigate this, we aim to minimize blockchain interactions. To achieve this, we elect a small family of n_a (n_a << n_c) parties, ensuring with high probability that at least one is honest. Only these family members are responsible for posting on the blockchain, reducing storage overhead while maintaining correctness.

The parties in the clan verify the encryptions, signatures and commitment and send a vote to the parties in the family (Step 4). The family members construct a meta DKG instance that aggregates information from at least f_c+1 valid secret sharing instances. Specifically, the meta DKG includes the Merkle root of the commitment and the encryption vector for each of these instances. Additionally, it contains proof in the form of votes from clan members, ensuring that at least one honest party has received and verified each secret sharing instance. However, the meta DKG can grow to 𝜅n_c+n_c² in size due to the inclusion of n_c² signatures, making on-chain posting costly.

Instead, we disseminate the meta DKG to the clan and collect a proof of availability (PoA) of size only 𝜅+n_c, when using multi-signatures (Step 5 and 6).  In our protocol, only the PoA of the meta DKG is posted on the blockchain (Step 7). Once the blockchain outputs the first valid PoA, clan members retrieve it along with the corresponding meta DKG, followed by all commitments and encryptions. They then distribute the aggregated commitment and encryptions to all parties in the tribe in a communication-efficient manner using erasure codes. The aggregated encryption is used by all parties to compute the final secret key.

Overall, our protocol achieves 𝜅n_c²n+ n_an_c³ + 𝜅n² off-communication complexity, 𝜅n_a + n_an_c on-chain storage and terminates in 11 rounds while tolerating f < n⁄3 Byzantine faults.

Experimental Evaluation

We evaluated our protocol and compared it with the state-of-the-art (SOTA) standalone DKG protocol by Das et al. when used for solving DKG for blockchain. Our experiments were conducted on machines with 2 vCPUs, spanning 8 geo-distributed GCP regions. As shown in the figure below, our protocol achieves faster completion compared to the SOTA approach. In the figure, the optimistic case refers to an execution where the dealer collects signatures from all parties, eliminating the need for encryption generation and verification by the clan nodes. In the regular case, the dealer receives n-f signatures and generates encryptions for the remaining f parties.

In the above evaluation, most of the time was spent on cryptographic operations, which can be parallelized with more compute resources. We enhanced our implementation by parallelizing the majority of cryptographic computations and verifications. When deployed on machines with 32 vCPUs across the same 8 geo-distributed GCP regions, we observed a significant reduction in DKG completion time. At n=256n = 256n=256, our protocol completes in approximately 11 seconds in the regular case and around 6 seconds in the optimistic case, demonstrating the scalability of our solution.