Threshold Blind Signatures

This page describes the cryptographic scheme implemented in fedimint-tbs: an ad-hoc threshold blind signature built from BLS signatures over the pairing-friendly curve BLS12-381. It is the primitive behind Fedimint's Chaumian e-cash: the federation blindly signs a note so that no guardian learns which note it signed, yet any later holder can verify the note against a single aggregate public key.

Sections 1–3 present the scheme with a single signer; Section 5 then replaces the signer by a $t$-of-$n$ federation of guardians — a standard transformation that exploits only the linearity of signing in the secret key.

Where this is used. This is the signature on Chaumian e-cash notes in Fedimint's mint module. A note is a pair $(\mathit{nonce}, \sigma)$, where the message $m = \mathsf{H}_{\mathbb{G}_1}(\mathit{nonce})$ is signed blindly at issuance and $\sigma$ is checked at redemption, with the federation marking each nonce spent to prevent double-spending. Crucially, a note's amount is not a signed attribute: the mint holds a separate keypair per denomination tier — a distinct key generation per tier — so the value of a note is fixed by which aggregate key verifies it. This is the point of departure from an attribute-based credential scheme, in which the amount would instead be a hidden message inside a single signature.

1. Setting and notation

Throughout, $K := \mathbb{Z}/p\mathbb{Z}$ denotes the field of integers modulo the prime $p$, and $K^n$ the $K$-vector space of (column) vectors of length $n$.

Let $\mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_T$ be the BLS12-381 pairing groups, all of order $p$ and written additively, with fixed generators $g_1 \in \mathbb{G}_1$, $g_2 \in \mathbb{G}_2$, and let $e : \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T$ be the pairing, a nondegenerate $K$-bilinear map. Messages and signatures live in $\mathbb{G}_1$; keys live in $\mathbb{G}_2$.

Groups as vector spaces. Since $|\mathbb{G}_i| = p$ is prime, scalar multiplication $K \times \mathbb{G}_i \to \mathbb{G}_i$, $(\lambda, v) \mapsto \lambda\, v$ is well defined and makes each $\mathbb{G}_i$ a one-dimensional $K$-vector space; every nonzero element is a basis. Consequently the group homomorphisms appearing below are exactly the $K$-linear maps between these spaces, and the whole scheme can be read in the language of linear algebra.

A note is identified by a message point obtained by hashing arbitrary bytes into the curve, $\mathsf{H}_{\mathbb{G}_1} : \{0,1\}^* \to \mathbb{G}_1$, modeled as a random oracle:

Because $\mathsf{H}_{\mathbb{G}_1}$ is a random oracle, no party knows the discrete logarithm of $m$ with respect to $g_1$, so a signature on $m$ cannot be produced by the holder alone.

2. Keys and the underlying signature

The signer's secret key is a single scalar $x \in K$, and the public key publishes it in $\mathbb{G}_2$:

Underlying primitive — BLS. A BLS signature on a message point $m \in \mathbb{G}_1$ is $$\sigma = x\, m \;\in\; \mathbb{G}_1,$$ verified by the single pairing equation $$e(m,\; \mathsf{pk}) \;=\; e(\sigma,\; g_2),$$ which holds because $e(m, x\,g_2) = e(m,g_2)^x = e(x\,m, g_2)$ by bilinearity. Signing is the $K$-linear map $x \mapsto x\,m$ in the key — the single fact that makes both blinding (§3) and thresholdizing (§5) work.

3. Blind signing

To have a note signed without revealing it, the user samples a blinding key $r \stackrel{\$}{\leftarrow} K \setminus \{0\}$ and sends the blinded message

The user verifies the response against the public key, $e(\bar{m}, \mathsf{pk}) = e(\bar{\sigma}, g_2)$, and removes the blinding by dividing out $r$ in the exponent:

a plain BLS signature on $m$ that verifies under $\mathsf{pk}$ via the equation of §2.

Why blinding hides the note. Multiplication by a uniformly random nonzero scalar is a bijection of $\mathbb{G}_1 \setminus \{0\}$, so $\bar{m} = r\,m$ is uniformly distributed and carries no information about $m$. The signer's entire view $(\bar{m}, \bar{\sigma})$ is therefore statistically independent of which note is being signed: blindness is perfect, not merely computational.

4. Security properties (informal)

5. The threshold construction

Nothing above requires a single signer. Because signing $$\bar{\sigma} \;=\; x\, \bar{m}$$ is $K$-linear in the secret key $x$, the signer can be replaced by a $t$-of-$n$ federation via Shamir secret sharing plus Lagrange interpolation in the exponent — the textbook threshold-BLS construction.

5.1 Key sharing

The key $x$ is Shamir-shared: pick a random polynomial $f \in K[X]$ of degree at most $t-1$ with $f(0) = x$, and give guardian $i \in \{1, \dots, n\}$ the key share and public key share $$\mathsf{sk}_i = f(i) \in K, \qquad \mathsf{pk}_i = f(i)\, g_2 \in \mathbb{G}_2.$$ The aggregate public key is unchanged: $\mathsf{pk} = f(0)\, g_2 = x\, g_2$. (Evaluation points are the indices $i = \texttt{peer} + 1$, since the point $0$ is reserved for the secret itself.) In a real federation this sharing is set up without a trusted dealer by a distributed key generation.

5.2 Share signing and aggregation

Each guardian signs the blinded message with its own share, $$\bar{\sigma}_i \;=\; f(i)\, \bar{m},$$ and the user verifies each share independently against $\mathsf{pk}_i$ by the pairing equation $e(\bar{m}, \mathsf{pk}_i) = e(\bar{\sigma}_i, g_2)$ — so a misbehaving guardian is identified immediately and its share discarded. Any set $S$ of $t$ valid shares then interpolates to the federation signature. Write $\lambda_i^S$ for the Lagrange coefficients that reconstruct a degree-$(t-1)$ polynomial at the point $0$: $$\lambda_i^S \;=\; \prod_{\substack{j \in S \\ j \neq i}} \frac{j}{\,j - i\,}, \qquad\text{so that}\qquad \sum_{i \in S} \lambda_i^S\, f(i) \;=\; f(0) \;=\; x \quad\text{for every } f \text{ with } \deg f \le t-1.$$

The aggregation is this same combination carried out in the exponent. It lands on the single-signer signature because scalar multiplication $K \times \mathbb{G}_1 \to \mathbb{G}_1$, $(\lambda, v) \mapsto \lambda\,v$, is bilinear — in particular linear in its scalar argument — so it commutes with the Lagrange sum, letting the interpolation run on the group element $\bar{m}$ rather than on the field values $f(i)$: $$\begin{aligned} \bar{\sigma} &\;=\; \sum_{i \in S} \lambda_i^S\, \bar{\sigma}_i && \text{(combine the shares)} \\[2pt] &\;=\; \sum_{i \in S} \lambda_i^S\, \bigl(f(i)\, \bar{m}\bigr) && \text{(each share is } \bar{\sigma}_i = f(i)\,\bar{m}) \\[2pt] &\;=\; \Bigl(\sum_{i \in S} \lambda_i^S\, f(i)\Bigr) \bar{m} && \text{(linearity in the scalar argument)} \\[2pt] &\;=\; f(0)\, \bar{m} && \text{(Lagrange interpolation at } 0) \\[2pt] &\;=\; x\, \bar{m}. && (f(0) = x) \end{aligned}$$ The middle equality is the crux: pulling the coefficients $\lambda_i^S$ out through the scalar multiplication is exactly the bilinear map commuting with the interpolation, and it turns $t$ independent group elements back into the evaluation of the joint key polynomial at the secret point $0$. (For a $1$-of-$1$ federation the single share is already the aggregate and no interpolation is needed.)

The user then unblinds as in §3, $\sigma = r^{-1}\bar{\sigma} = x\,m$, and the result verifies against the aggregate public key $\mathsf{pk}$ — identical to the single-signer scheme. Fewer than $t$ guardians learn nothing about $x$ and cannot assemble a valid combination.

Aggregating public keys. The same Lagrange-at-$0$ formula recombines public key shares $\mathsf{pk}_i = f(i)\,g_2$ into the aggregate $\mathsf{pk} = f(0)\,g_2$. The library exposes this as aggregate_public_key_shares, though the aggregate is more directly obtained by evaluating the DKG polynomial at $0$ during setup.

Implementation caveat (prototype). Hash-to-group is implemented by seeding a ChaCha RNG with SHA-256 rather than a standard hash_to_curve ciphersuite — fine as a random oracle into the group, but non-interoperable with other BLS implementations.