A Decentralized Ethos: Distributed Key Generation and Secret Sharing

September 01, 2023 - 7 min read

DKG and secret-sharing schemes embody decentralization in multi-party computation, safeguarding participants from Byzantine risks.

Introduction to DKG

Distributed Key Generation is a decentralized computation protocol used to generate cryptographic keys in distributed, transparent, and yet secure ways. Basically, network nodes collaboratively generate a secret key so that not a single participant knows the entirety of keys, but subsets of nodes can jointly reconstruct them.

The individual components generated by each participant are often referred to as shares of the secret key, or keyshares. Neither single nodes nor small subsets can have actionable knowledge about the secret key. Developers will set a threshold number of nodes which must produce a quorum certificate as validation when keys are utilized to transfer digital assets in smart contracts, for instance.

This stands in stark contrast to setups in which the key is generated by a central dealer who must be trusted by other participants and perhaps more crucially, participants joining the network after the matter. Such arrangements are unacceptable when it comes to DeFi, as decentralization and trustless smart contracts are really at the heart of the value propositions for these emergent technologies.

Therefore, a decentralized generation event should take place in addition to the decentralized storage of validation power. In this article, we’ll cover some DKG and the context in which it exists, some of its goals, strengths and weaknesses, and why it matters for a decentralized web. Spoiler: it is rather important for the adoption of digital assets, among other things.

DKG and secret-sharing schemes are commonly used in secure multi-party computation, like for threshold signature schemes in blockchains and DeFi applications. Since no single entity holds the entire key, there is a reduced risk of Byzantine behavior or otherwise dishonest tampering. This is the essence of trustless P2P interactions over the web; single points of failure can’t be tolerated or adoption will simply not take hold.

While decentralization is often understood to be inherent to DeFi protocols, it is not always the case – and often centralized trade offs are made for the sake of convenience or costs, sadly. Fortunately, advances in DKG further the goals of decentralization by incorporating it into the infrastructure of key generation, while secret sharing does the same for the storage of those keys.

Even if some participants are malicious or compromised, as long as a predefined subset is honest, the security of the distributed keyshares are preserved. Some DKG protocols even allow for periodic key renewals without forking the network, which is useful for maintaining dynamic and long-term security guarantees.

Protocols to ensure that the DKG is done securely involve complex mathematical operations and communication steps to ensure that a single point of failure doesn’t emerge. That is to say that the nodes are unable to collude or gain knowledge of the entirety of the keyshares. This is all founded upon the basis of a method called Shamir’s Secret Sharing Scheme, which we’ll cover next.

DKG draws upon and extends Shamir’s Secret Sharing Scheme, introduced back in 1979 by Adi Shamir. The difference is that DKG is about the generation of the keys whereas secret sharing involves the storage of keys and a consensus protocol for validating state changes via a quorum of nodes. In the case of DeFi, a threshold number of nodes must cooperate to reconstruct a quorum proof that validates new transactions.

In any case, secret-sharing schemes divide a secret into multiple shares in such a way that the secret isn’t useful without a threshold number of participants working to reconstruct the original secret for validation. However, possessing fewer shares than the threshold won’t provide actionable information about the secret.

Keyshares are represented as polynomials, with nodes holding values at points along the slope.

The sharing scheme achieves security by employing polynomial interpolation over finite fields. Here’s a quick breakdown of how it works in three simple steps:

Polynomial Construction: For a given secret, a polynomial of degree t−1 (where t is the threshold number of keyshares needed to reconstruct the secret) is randomly generated such that the constant term is the secret which was just generated.
Share Distribution: To generate keyshares, the polynomial is evaluated at different points. Each evaluated point, excluding the constant term, is a keyshare. Thus, depending on how many keyshares devs use for their security parameters, they would evaluate the polynomials at varying distinct points corresponding to the keyshares.
Secret Reconstruction: To reconstruct the secret, a threshold of keyshares needs to be combined to interpolate the polynomial and compute its constant term to retrieve the secret.

Nevertheless, Shamir Secret Sharing Schemes have several shortcomings, one of which being that it’s often impossible for share-recipients to know if the keyshares they hold are consistent with those of the other participants. This problem is solved by using Verifiable Secret Sharing schemes. Verifiable Secret Sharing is a way to distribute shares that assures all parties that their counterparts are honestly in possession of valid keyshares.

In essence, VSS nodes simply make commitments to coefficients of the line representing the key in its entirety, which is verified by other nodes. This allows participants the opportunity to validate that the keyshares of other participants are in alignment with their fractions of the keyshares.

keyshare interpolation using partial knowledge

Attackers could still attempt to guess the remaining keyshare values and reconstruct the key.

Using the keyshares of a small subset of nodes below the necessary threshold, a Byzantine attacker might try interpolating a sloped curve by guessing the missing keyshare values. Interpolating here just means to guess the keyshare values which represent points along a sloped curve.

Setting a modulus limits the predictability of the polynomial slope and makes interpolation less probable if not impossible.

However, this is easily mitigated by not using a simple polynomial slope, but by implementing something called a modulus. This modulus makes the keyshare polynomial into a cyclic function, which is to say that it looks more like a set of slopes which return to the y-axis instead of a single slope. The result is that interpolation of the entire secret key becomes increasingly more difficult if not wholly impossible.

DKG is Critical for Trustless, Scalable Security

It is clear that DKG is incredibly useful for realizing secure multi-party computation and practical applications for threshold cryptography. The robustness and mathematical elegance of DKG and advanced secret-sharing schemes is a bedrock upon which trustless networks might interoperate, and thus scaling the utility of DeFi.

What’s more, since DeFi is dynamic, meaning participants might continuously join or leave, DKG and secret-sharing allow for the periodic renewal of keys without bringing the entire system offline. This lends favorably to the scalability and longevity of a given project since new users can join it trustlessly, knowing that early members, or a key “dealer” is not or has not behaved Byzantine.

As decentralized protocols aim for greater adoption, developers must ensure that security is robust to the point of redundancy without sacrificing on performance. DKG and secret-sharing schemes offer this happy equilibrium at the most foundational level, enabling DeFi platforms to handle more users, more assets, and add greater complexity to their applications.

Resources

Kate, A., Huang, Y., & Goldberg, I. (2012). Distributed key generation in the wild. IACR Cryptology ePrint Archive, Paper 2012/377.
Kate, A., Mangipudi, E. V., Mukherjee, P., Saleem, H., Thyagarajan, S. A. (2023). Non-interactive VSS using class groups and application to DKG. IACR Cryptology ePrint Archive, Paper 2023/451.
Nugent, D. (2022, 4 Oct.). Shamir’s secret sharing: Explanation and visualization. Evervault.
Shamir, A. (1979). How to share a secret. Communications of the ACM, 22(11), 612-613.