Threshold Signatures: Distributed Signing Without a Single Point of Failure

Threshold Signatures: Distributed Signing Without a Single Point of Failure

Threshold signatures are cryptographic schemes that allow a group of n participants to jointly produce a valid signature, where any subset of size t (threshold) can sign, but fewer than t cannot. Each participant holds a private key share, and the full private key is never reconstructed. The resulting signature verifies with a single public key and is indistinguishable from a signature produced by a regular (non-threshold) scheme. Threshold signatures eliminate single points of failure, increase security through distribution, and enable decentralized signing in blockchain validators, cryptocurrency wallets, and oracles.

To understand threshold signatures properly, it helps to be familiar with BLS signatures, public key cryptography, and secret sharing.

┌─────────────────────────────────────────────────────────────────────────┐
│                       Threshold Signatures (t-of-n)                      │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                          │
│   Setup: Public key pk (single) — Private key shares sk1, sk2, ..., skn │
│                                                                          │
│   ┌─────────┐   ┌─────────┐           ┌─────────┐   ┌─────────┐         │
│   │ Signer1 │   │ Signer2 │   ...     │ Signer3 │   │ Signer4 │         │
│   │  sk₁    │   │  sk₂    │           │  sk₃    │   │  sk₄    │         │
│   └────┬────┘   └────┬────┘           └────┬────┘   └────┬────┘         │
│        │             │                      │             │              │
│        ▼             ▼                      ▼             ▼              │
│    σ₁ = sign(sk₁)  σ₂ = sign(sk₂)       σ₃ = sign(sk₃)  σ₄ = sign(sk₄) │
│        │             │                      │             │              │
│        └─────────────┼──────────────────────┼─────────────┘              │
│                      │                      │                           │
│                      ▼                      ▼                           │
│                Combine(σ₁,σ₂,σ₃) ──→ σ (single signature)               │
│                                                                          │
│   Properties:                                                            │
│   • Single signature (indistinguishable from regular)                   │
│   • No single point of failure                                          │
│   • Threshold: any t of n signers can sign                             │
│   • Private key never reconstructed                                     │
│                                                                          │
└─────────────────────────────────────────────────────────────────────────┘

What Are Threshold Signatures?

A threshold signature scheme enables a group of n participants to collectively sign messages using a distributed key. The scheme has a threshold parameter t, meaning any subset of at least t participants can produce a valid signature, but any subset smaller than t cannot. The joint signature verifies with a single public key, exactly like a signature from a standard (non-threshold) scheme. The full private key is never assembled in any single location.

• t-of-n Threshold: t participants required to sign, n total participants. Example: 3-of-5 (any 3 can sign), 2-of-2 (both required).
• Distributed Key Generation (DKG): Protocol where n participants generate key shares without a trusted dealer (no single party knows full private key).
• Secret Sharing: Basis for threshold signatures (Shamir's secret sharing, Feldman VSS). Shares distributed so that t shares reconstruct secret.
• Non-Interactive: Signers can produce partial signatures independently, then combine without further coordination (for BLS threshold).

Why Threshold Signatures Matter

Threshold signatures solve fundamental problems in distributed systems where a single private key is a dangerous single point of failure.

• Crypto Wallets (Multisig Alternative): Traditional multisig requires multiple signatures (blockchain storage and gas per signer). Threshold signature is a single signature (one transaction, one gas fee). Lower cost, better privacy (external observer cannot see how many signers).
• Validator Consensus (Blockchains): Block proposer aggregates t signatures from validators into a single signature. Verifies faster, stores less data. No single validator holds signing power. Used in Chainlink, some BFT protocols.
• Decentralized Oracles (Chainlink): Multiple oracle nodes sign the same data (price feed). Threshold t ensures data reliability (t-of-n honest nodes). Aggregated signature proves data authenticity.
• Certificate Authorities (CA): Distribute CA signing key across n HSM modules. Threshold t required to issue certificates. No single compromised module compromises CA.
• Enterprise Key Management: Approve financial transactions requiring t approvals. Tamper-proof audit logs: which signers contributed. No single person has full signing authority.

Aspect                  Threshold Signature          Multisignature (Bitcoin)
─────────────────────────────────────────────────────────────────────────────
Blockchain Storage      1 signature (48-64 bytes)     t × 64 bytes (3-of-5 = 192B)
Verification Cost       1 verification               t verifications
Privacy (signer count)  Hidden (single signature)     Visible (t signatures)
Key Generation          Distributed (no single key)   Individual keys (can be separate)
Smart Contract Needed?  No (single key in blockchain) Yes (multisig address)
Flexibility             t-of-n                       m-of-n (more flexible)
Standardization         BLS threshold, FROST          Bitcoin multisig, Ethereum multisig

Threshold Signature Schemes

Scheme      Aggregation   Key Gen         Signing        Verified By
─────────────────────────────────────────────────────────────────────────────
BLS-thresh  Multiply      DKG possible    Non-interactive Pairings
            (non-interactive)
FROST       Sum           DKG (complex)   2 rounds       EC arithmetic
GG20        Complex       Multi-party     3-5 rounds     EC arithmetic
Naive        N/A           Dealer          N/A           N/A

Recommendation by context:
  • Blockchain with pairings (BLS12-381) → Threshold BLS
  • Schnorr-based chains (Bitcoin, Cardano) → FROST
  • ECDSA-only environment (Ethereum) → GG20 or Shamir+ECDSA

How Threshold BLS Works

Threshold BLS based on Shamir's secret sharing (Lagrange interpolation). Private key shared among n participants, threshold t can reconstruct.

Setup:
  1. Choose polynomial f(x) = sk + a1·x + a2·x² + ... + a_{t-1}·x^{t-1}
  2. sk_i = f(i) (private share for participant i)
  3. Public key pk = g^{sk}

Signing (t participants):
  1. Each participant computes σ_i = H(m)^{sk_i}
  2. σ_agg = ∏ σ_i^{λ_i}   (λ_i = Lagrange coefficient for subset S)
  3. σ_agg is valid signature for message m

Verification:
  Verify σ_agg against pk (standard BLS verification)
  e(σ_agg, g₂) == e(H(m), pk)

Properties:
  • Any t participants can sign (using Lagrange interpolation)
  • Less than t participants cannot produce valid signature
  • Full private key never reconstructed

Distributed Key Generation (DKG)

DKG eliminates the trusted dealer problem. Participants jointly generate key shares without any single party ever holding full private key.

• Pedersen DKG: Each participant shares their polynomial (verifiable secret sharing). Combines shares into final public key. Verifiable: participants can verify each other's shares.
• Joint-Feldman DKG: Variant of Pedersen DKG (public key commitments). Communication complexity O(n²) (each participant broadcasts to all).
• Verifiable Secret Sharing (VSS): Enables participants to verify received shares are consistent. Prevents malicious dealers from giving inconsistent shares.
• Public Key Computation: Combined public key computed from all participant commitments.

Each participant (i = 1 to n):
  1. Generate secret polynomial f_i(x) of degree t-1
  2. Compute commitments C_{i,k} = g^{a_{i,k}} for k=0..t-1
  3. Compute shares s_{i,j} = f_i(j) for participants j=1..n
  4. Send s_{i,j} secretly to participant j
  5. Broadcast commitments C_{i,k} to all

After receiving all shares and commitments:
  Each participant verifies: g^{s_{i,j}} == ∏_{k=0}^{t-1} (C_{i,k})^{j^k}
  If valid, compute final private share: sk_j = ∑_{i=1}^{n} s_{i,j}
  Compute public key: pk = ∏_{i=1}^{n} C_{i,0}

Result:
  • Each participant has sk_i (private share)
  • No one knows full private key sk = ∑ sk_i
  • Public key pk is known to all

FROST (Flexible Round-Optimized Schnorr Threshold)

FROST is a threshold Schnorr signature scheme optimized for minimal rounds (2-round signing) and no trusted dealer (using DKG). Popular for Bitcoin and other Schnorr-based blockchains.

• Round 1 (Commitment): Each participant generates random nonce (hiding, binding). Broadcasts commitment (hiding value).
• Round 2 (Sign): Compute group challenge (binding value). Each participant uses nonce and private share to compute partial signature. Send partial signature to designated aggregator.
• Aggregation: Aggregator combines partial signatures into one Schnorr signature.
• Security: Prevents rogue key attacks, nonce reuse, and malicious participation.

Round 1 (preprocessing):
  Each signer i:
    • Generate random nonce pair (d_i, e_i)
    • Compute commitment (D_i = g^{d_i}, E_i = g^{e_i})
    • Broadcast (D_i, E_i) to all

Round 2 (signing):
  Each signer i:
    • Compute binding factor ρ = H_1( (D_j, E_j), group_public_key, message)
    • Compute challenge c = H_2(group_public_key, ρ, message)
    • Compute response z_i = d_i + e_i·ρ + λ_i·sk_i·c
    • Send z_i to aggregator

Aggregation:
  z = sum(z_i)
  Signature = (ρ, z)

Verification:
  Standard Schnorr verification

Note: λ_i is Lagrange coefficient for participant i

Threshold Signatures Anti-Patterns

• Reconstructing Full Private Key: Defeats purpose of threshold: key exists in single location. Use DKG to avoid trusted dealer. Never reconstruct key, even in memory.
• Using Naive Secret Sharing Without VSS: Malicious dealer can give inconsistent shares (some participants cannot reconstruct). Always use Verifiable Secret Sharing (VSS) to validate shares.
• Nonce Reuse in FROST/GG20: Reusing nonces across different signers or messages leaks private keys (catastrophic). Always fresh random nonces per signing session. Use deterministic nonce generation (RFC 6979).
• Incorrect Lagrange Coefficient Calculation: Using wrong modulus (over integer vs over field). Use modular arithmetic with modulus equal to group order. Verify formula with small test cases.
• No Identifiable Aborts (Malicious Signers): One malicious participant can send invalid share, aborting entire protocol. Implement identifiable abort (identify misbehaving participant).

❌ Reconstructing private key (even temporarily)
❌ Trusted dealer without verification
❌ Nonce reuse across signing sessions
❌ No mechanism to identify malicious signers
❌ Incorrect Lagrange interpolation (modulus)
❌ No timeout for unresponsive participants

✓ DKG for distributed key generation
✓ Verifiable secret sharing (VSS)
✓ Fresh nonces per signing (cryptographically random)
✓ Identifiable abort (malicious participants)
✓ Small test threshold (2-of-3) at development

Threshold Signatures Best Practices

• Choose Appropriate Scheme: BLS threshold for pairing-friendly blockchains (Ethereum 2.0, BLS12-381). FROST for Schnorr-based chains (Bitcoin, Cardano, Solana). GG20/GG18 for ECDSA-only environments (Ethereum, Bitcoin via secp256k1).
• Use DKG (No Trusted Dealer): Eliminate single point of trust. Use Pedersen DKG (simpler, verifiable). Joint-Feldman is suitable for many use cases. Complexity O(n²) but acceptable for n ≤ 100.
• Implement Identifiable Abort: Detect which participant sent invalid shares, exclude misbehaving participants. Log abort events for auditing. Allows protocol continuation with remaining honest participants.
• Secure Nonce Generation: Use cryptographic random number generator (RNG). For FROST, derive nonces from signing session ID to prevent reuse. Consider RFC 6979 for deterministic nonces.
• Test with Small Thresholds: Test 2-of-3, 3-of-5 configurations before large deployment. Verify that all subsets of size t produce same signature. Validate that t-1 signers cannot forge (test negative cases).

Use Case                               Recommended Scheme
─────────────────────────────────────────────────────────────────────────────
Ethereum 2.0 validator                 Threshold BLS (BLS12-381)
Bitcoin Taproot wallet                 FROST (Schnorr)
Ethereum EOA (externally owned acct)   GG20 (ECDSA)
Secure oracle (Chainlink)              Threshold BLS
Multi-party computation                FROST
Certificate authority                  Threshold BLS or FROST
Enterprise key management              FROST (auditable)

Popular Threshold Signature Libraries

Frequently Asked Questions

1. What is the difference between threshold signatures and multisig?
   Multisig requires t separate signatures (each signer produces separate signature). Threshold signature produces one signature indistinguishable from regular signature. Multisig verification checks each signature individually (higher cost). Threshold verification checks one signature (lower cost). Multisig reveals number of signers; threshold hides it.
2. Do threshold signatures require a trusted dealer?
   Not necessarily. Distributed Key Generation (DKG) protocols allow n parties to generate key shares without any trusted dealer (no single party knows full key). Security against malicious participants up to t-1. DKG is more complex than trusted dealer but eliminates single point of trust.
3. Can threshold signatures be used for Bitcoin?
   Bitcoin supports Schnorr signatures (Taproot). FROST threshold Schnorr works on Bitcoin. ECDSA threshold (GG20) also works but less efficient. Traditional Bitcoin multisig (OP_CHECKMULTISIG) is not threshold signature (multiple signatures).
4. What is the minimum number of participants for threshold?
   Minimum t = 2, n = 2 (2-of-2 requires both). t = 1 is trivial (single signer, not threshold). Common thresholds: 2-of-3 (tolerates 1 failure), 3-of-5 (tolerates 2 failures), 5-of-9 (tolerates 4 failures).
5. How does key recovery work after losing shares?
   With DKG, there is no master key to recover shares. Lost shares cannot be recovered (prevents single point of failure). Solution: Re-run DKG to generate new key. Or, pre-approve threshold t+1 participants (each participant stores shares, tolerance for loss).
6. What should I learn next after threshold signatures?
   After mastering threshold signatures, explore Distributed Key Generation (DKG), BLS signatures for aggregation, FROST in depth (RFC 9591), Verifiable Secret Sharing (VSS), and Multi-Party Computation (MPC).