Distributed Key Generation

This page describes the cryptographic ceremony implemented in fedimint-server's configuration setup: a Pedersen distributed key generation (DKG) over BLS12-381. It is run once, when a federation is created, to produce the threshold keys used by the rest of the system without any trusted dealer — no single party ever holds the secret key. Concretely, the DKG produces exactly the Shamir-shared key that the threshold blind signature and threshold point encryption schemes take as given.

Two instances, one protocol. The ceremony is run separately for each pairing group: run_dkg_g1 produces a key whose public material lives in $\mathbb{G}_1$ (as tpe needs), and run_dkg_g2 produces one whose public material lives in $\mathbb{G}_2$ (as tbs needs). The two are identical line for line apart from the group in which commitments are formed, so we describe a single generic instance over a group $\mathbb{G}$ with generator $g$.

Where this is used. The ceremony runs once, during federation setup, before consensus begins. Each module that needs a threshold key drives one run per key: the mint module runs a $\mathbb{G}_2$ ceremony per denomination tier to obtain that tier's blind-signing key (tbs), and lnv2 runs a $\mathbb{G}_1$ ceremony for its decryption key (tpe). In each case the module's secret key exists only as the resulting threshold sharing — no guardian ever holds it.

1. Setting and notation

$K := \mathbb{Z}/p\mathbb{Z}$ is the field of integers modulo the prime $p$. Let $\mathbb{G}$ be one of the BLS12-381 groups of order $p$, written additively, with fixed generator $g \in \mathbb{G}$; scalar multiplication $\lambda \mapsto \lambda\,g$ is the map $K \to \mathbb{G}$ used throughout.

Groups as vector spaces. Since $|\mathbb{G}| = p$ is prime, $\mathbb{G}$ is a one-dimensional $K$-vector space, and $\lambda \mapsto \lambda\, g$ is a $K$-linear isomorphism $K \xrightarrow{\sim} \mathbb{G}$. Every operation below — committing to a polynomial, evaluating it, summing per-guardian contributions — is linear, so the whole ceremony is one extended exercise in carrying linear algebra "into the exponent".

A federation has $n$ guardians, indexed by $\mathsf{PeerId}$s. Guardian $i$ is assigned the evaluation point $$x_i \;=\; i + 1 \;\in\; K,$$ shifting peer indices by one so that the point $0$ — which will carry the secret — is never an evaluation point. With at most $f = \lfloor (n-1)/3 \rfloor$ faulty guardians, the reconstruction threshold is $$t \;=\; n - f,$$ and every guardian samples a secret polynomial of degree $t-1$ (i.e. $t$ coefficients), so that any $t$ shares determine it and any $t-1$ reveal nothing.

2. Committing to a secret polynomial

Each guardian $i$ samples a uniformly random polynomial of degree $t-1$ over $K$, $$f_i(X) \;=\; \sum_{k=0}^{t-1} a_{i,k}\, X^k, \qquad a_{i,k} \stackrel{\$}{\leftarrow} K,$$ and publishes a Feldman commitment to its coefficients — the coefficient vector mapped into the group: $$C_i \;=\; \bigl(C_{i,0}, \dots, C_{i,t-1}\bigr), \qquad C_{i,k} \;=\; a_{i,k}\, g \;\in\; \mathbb{G}.$$

What a Feldman commitment buys. Because $g$ is a generator, $a \mapsto a\,g$ is injective, so $C_i$ binds guardian $i$ to a unique polynomial. And because it is linear, the commitment to a polynomial evaluated at a point is the same linear combination of the $C_{i,k}$ — which lets any recipient check a privately received share against the public commitment (§3.3) without learning the polynomial.

3. The protocol

The ceremony runs in three message rounds over authenticated peer-to-peer links. Guardian $i$ tracks the others' hash commitments, full commitments, and the secret shares addressed to it; a round advances only once a message has been received from every guardian.

3.1 Round 1 — hash commitment

Each guardian first broadcasts only a hash of its commitment vector, $$h_i \;=\; \mathsf{SHA256}\bigl(\mathsf{encode}(C_i)\bigr),$$ and waits until it holds $h_j$ from all $n$ guardians before revealing anything more.

Why commit to the commitment first? Broadcasting $h_i$ before any $C_j$ is revealed forces every guardian to fix its polynomial before seeing the others'. Without this round, a guardian who spoke last could choose its coefficients adaptively in response to everyone else's commitments and so bias the joint public key. The hash round removes that rushing advantage.

3.2 Round 2 — reveal and verify

Once all hashes are in, each guardian broadcasts its full commitment vector $C_i$. On receiving $C_j$, guardian $i$ checks that

Any mismatch aborts the ceremony. The protocol proceeds once all $n$ commitments are in.

3.3 Round 3 — deal and verify shares

Each guardian $i$ now evaluates its polynomial at every guardian's point and sends the result privately: $$s_{i \to j} \;=\; f_i(x_j) \;\in\; K \qquad (\text{kept for } j = i,\ \text{sent over the private link otherwise}).$$ On receiving the share $s_{j \to i}$ from guardian $j$, guardian $i$ verifies it against $j$'s public commitment with the Feldman check $$s_{j \to i}\, g \;\stackrel{?}{=}\; \sum_{k=0}^{t-1} x_i^{\,k}\, C_{j,k}.$$

Why the check works. The right-hand side is the commitment $C_j$ "evaluated at $x_i$ in the exponent": $$\sum_{k=0}^{t-1} x_i^{\,k}\, C_{j,k} \;=\; \sum_{k=0}^{t-1} x_i^{\,k}\, a_{j,k}\, g \;=\; \Bigl(\sum_{k=0}^{t-1} a_{j,k}\, x_i^{\,k}\Bigr) g \;=\; f_j(x_i)\, g.$$ So the check passes exactly when $s_{j\to i} = f_j(x_i)$ — a guardian cannot send a share inconsistent with the polynomial it already committed to.

3.4 Combine

After collecting a valid share from every guardian, guardian $i$ sums them into its secret key share, and sums the per-guardian commitments coefficient-wise into the public commitment: $$\mathsf{sk}_i \;=\; \sum_{j=1}^{n} s_{j \to i}, \qquad \mathsf{PK}_k \;=\; \sum_{j=1}^{n} C_{j,k} \quad (k = 0, \dots, t-1).$$

4. What the ceremony produces

Define the joint secret polynomial as the sum of all the guardians' polynomials, $$F(X) \;=\; \sum_{j=1}^{n} f_j(X) \;=\; \sum_{k=0}^{t-1} A_k\, X^k, \qquad A_k = \sum_{j=1}^{n} a_{j,k}.$$ Then the outputs of §3.4 are exactly $$\mathsf{sk}_i \;=\; \sum_{j} f_j(x_i) \;=\; F(x_i), \qquad \mathsf{PK}_k \;=\; \sum_{j} a_{j,k}\, g \;=\; A_k\, g,$$ i.e. each guardian holds the value of $F$ at its own point, and everyone holds the Feldman commitment $\mathsf{PK} = (A_0 g, \dots, A_{t-1} g)$ to $F$.

This is precisely the Shamir sharing the other schemes assume. The federation's secret key is $x = F(0) = \sum_j a_{j,0}$ — the sum of every guardian's constant term — which is never reconstructed anywhere. Its public key is $\mathsf{PK}_0 = x\, g$, and guardian $i$'s public key share is obtained by evaluating the public commitment at $x_i$, $$\mathsf{pk}_i \;=\; \sum_{k=0}^{t-1} x_i^{\,k}\, \mathsf{PK}_k \;=\; F(x_i)\, g \;=\; \mathsf{sk}_i\, g.$$ Setting $f := F$, this is exactly the polynomial, shares $f(i)$, evaluation points $i+1$, and aggregate key of tbs §5.1 and tpe §6.1 — so signing or decryption shares produced afterwards interpolate to a signature or decryption key under the single aggregate public key $x\,g$.

5. Security properties (informal)

Implementation note — cooperative ceremony with abort.

The implementation assumes all guardians are present and cooperative: there is no complaint-and-disqualification phase, and an invalid hash, commitment, or share causes the whole ceremony to abort rather than excluding the offending guardian. This is appropriate for a one-time setup among a known guardian set — a failed run is simply retried — but it means liveness requires every guardian to behave during setup, even though the resulting key tolerates up to $f$ faults thereafter.

More subtly, formally guaranteeing a uniformly distributed key in a dealerless DKG is notoriously delicate: Gennaro, Jarecki, Krawczyk and Rabin showed that plain Joint-Feldman admits a small bias in the public key, exploited through the disqualification phase. The hash-commit-then-reveal round here fixes each guardian's polynomial before any are opened, and aborting on any fault removes the disqualification phase that the classic attack turns on; the design thus targets an honest-majority-with-abort model rather than a formally analysed uniform-key DKG. The residual bias is harmless for the threshold schemes built on top, which only require that fewer than $t$ shares hide the key.