The Key to FROST: What is Distributed Key Generation?

Multisig is a familiar concept for most in Bitcoin: a multisig transaction requires approval from multiple parties before it can be executed. We distinguish between “n-of-n” multi-signatures, where the number of involved parties is n, and they all need to approve, and “t-of-n” threshold signatures, where only a smaller number t of participants need to approve. Cryptographic schemes like MuSig, MuSig-DN and MuSig2 for multi-signatures and FROST by Komlo and Goldberg for threshold signatures can reduce transaction cost and improve privacy of multisig wallets.

So far, in the Bitcoin Community FROST has only been used in experimental implementations. In this post, we explain why this is the case and how we aim to advance FROST in a Bitcoin production environment through our recent publication of a BIP draft for the ChillDKG distributed key generation protocol.

First, what are the benefits of FROST?

Privacy and Efficiency Gains with MuSig2 and FROST

With MuSig2 and FROST, even though multiple participants contribute to the signing process, the outcome is a single signature.

This not only gives better privacy to the participants by making the transaction look like as ordinary singlesig-wallet transaction. It also trims down the transaction, reducing its size and therefore lowering the transaction fee. All great things!

MuSig2 and FROST allow Bitcoin users to operate a multisig wallet with the same transaction cost as a regular single-signature wallet. The cost benefits are especially significant for systems with a large number of signers and frequent transactions, such as federated sidechains like Liquid or Fedimint. Unlike traditional multisig, which leaves a distinct fingerprint that allows blockchain observers to identify transactions of the wallet, FROST-based wallets are indistinguishable from regular single-signature wallets on the blockchain. Therefore, they provide an improvement in privacy compared to traditional multisig wallets.

While MuSig2 has seen adoption from the Bitcoin industry, the same cannot be said for FROST as far as we know. This may be surprising, considering the existence of multiple FROST implementations, such as in ZF FROST (by the Zcash Foundation), secp256kfun (by Lloyd Fournier), and an experimental implementation in libsecp256k1-zkp (by Jesse Posner and Blockstream Research). There is even a IETF specification for FROST, RFC 9591 (though it is not compatible with Bitcoin due to Taproot tweaking and x-only public keys). One of the most plausible explanations is that FROST’s key generation process is considerably more complex compared to MuSig2.

The Unresolved Puzzle of FROST in Production Systems

FROST essentially consists of two parts: key generation and signing. While the signing process closely resembles that of MuSig2, key generation is significantly more involved than in MuSig2. Key generation in FROST is either trusted or distributed:

Trusted key generation involves a “trusted dealer” who generates the key and distributes key shares to the signers. The dealer represents a single point of failure: if malicious or hacked, the FROST wallet is at risk of being emptied.Distributed key generation (DKG), while eliminating the need for a trusted dealer, presents its own challenges: All participants need to be involved in an interactive key generation “ceremony” run before signing can start.

The Core Challenge: Agreement

DKG typically requires secure (i.e., authenticated and encrypted) channels between participants to deliver secret shares to individual signers, and a secure agreement mechanism. The purpose of the secure agreement mechanism is to ensure that all participants eventually reach agreement over the results of the DKG, which include not only parameters such as the generated threshold public key, but also whether no error occurred and the ceremony was not disrupted by a misbehaving participant.

While the IETF specification considers DKG out of scope entirely, the FROST implementations mentioned above do not implement secure agreement, leaving this task to the library user. But agreement is not trivial to implement: there exist countless protocols and flavors of agreement, ranging from simple echo broadcast schemes to full-fledged Byzantine consensus protocols, and their security and availability guarantees differ significantly, and sometimes subtly.

Despite the confusion that may arise due to this jungle of agreement protocols, the exact flavor of agreement that DKG relies on is often not clearly communicated to engineers, leaving them in the dark.

ChillDKG: a Standalone DKG for FROST

To overcome this obstacle, we propose ChillDKG, a new “ready-to-use” DKG protocol tailored to the use in FROST (draft). We provide a detailed description in the form of a draft of a Bitcoin Improvement Proposal (BIP), which is intended to serve as a specification for implementers.

The main feature of ChillDKG is that it is standalone: The establishment of secure communications and secure agreement is done within the protocol, while all of this underlying complexity is hidden behind a simple and hard-to-misuse API. As a result, ChillDKG is ready to use in practice and does not rely on any setup assumption, except that each signer has decided on the set of co-signers as identified by individual public keys. ChillDKG is based on the SimplPedPop protocol, in whose design and formal security proof Blockstream Research has been involved, see, the CRYPTO 2023 paper “Practical Schnorr Threshold Signatures Without the Algebraic Group Model” by Chu, Gerhart, Ruffing (Blockstream Research), and Schröder

Additional goals for ChillDKG’s design include:

Broad applicability: ChillDKG supports a wide range of scenarios, from those where the signing devices are owned and connected by a single individual to those where multiple owners manage the devices from distinct locations.Simple backups: Instead of having to back up secrets received from the other signers in a secure location, ChillDKG allows restoring the wallet solely from the device seed and public data that is the same for all DKG participants. Consequently, an attacker gaining access to the public backup data does not obtain the secret signing key, and if a user loses their backup, they can request it from another honest signer.

The ChillDKG BIP is currently in draft stage, and we are seeking feedback on design choices and implementation details. While the specification is mostly complete, it lacks test vectors, and we are considering adding some additional features (e.g., “identifiable aborts”). Once finalized, the ChillDKG BIP can be used in combination with a BIP for FROST signing to instantiate the entire FROST protocol.

This is a guest post by Jonas Nick, Kiara Bickers, and Tim Ruffing. Opinions expressed are entirely their own and do not necessarily reflect those of BTC Inc or Bitcoin Magazine.