Post-Quantum Signature Libraries for a Substrate-Based Blockchain

Research
1

Summary

  • Evaluation of PQ signature schemes for transactions and consensus
  • Comparison of schemes: SPHINCS+, WOTS+, Dilithium, Falcon, XMSS
  • Analysis of available libraries
  • Highlighted Trade-offs: security, performance, signature size, statefulness
  • Recommended:
    • Dilithium → consensus
    • SPHINCS+ (or WOTS+) → transactions
    • liboqs → backend

1. Objectives

Design a post-quantum (PQ) blockchain using Substrate with:

  • Reliable support for well-tested PQ signature schemes
  • Open-source implementations suitable for production use
  • Preferably Rust-native.

2. Signatures in Substrate

2.1 Transaction (extrinsic) Signatures

  • Used by wallets and users
  • Verified in runtime
  • Requirements:
    • Strong security
    • Reasonable signature size
    • Deterministic verification

2.2 Consensus Signatures

  • Used by validators
    • BABE → produces blocks (fast, probabilistic)
    • GRANDPA → finalizes blocks (slow, deterministic)
  • Requirements:
    • Fast signing & verification
    • Small signatures
    • Stateless operation

2.3 Supported signature schemes in substrate

Substrate supports three native signature schemes, with some ecosystem extensions

  • sr25519: Based on Schnorr signatures over Ristretto (Curve25519 variant)

    Fast, Small signatures (~64 bytes), Good randomness properties (VRF support)

  • ed25519: Based on Edwards-curve Digital Signature Algorithm

    Simple, Deterministic, Highly audited

  • ecdsa: secp256k1

    EVM compatible

Scheme Transactions BABE GRANDPA
sr25519 :white_check_mark: :white_check_mark: (primary) :warning: optional
ed25519 :white_check_mark: :cross_mark: :white_check_mark: (primary)
ecdsa :white_check_mark: :cross_mark: :cross_mark:

3. Practical PQ Signature Schemes

Scheme Type Standardization Pros Cons Libraries / Use Case
XMSS Hash-based RFC 8391 Conservative security; Proven in production Stateful (sync issues); Key reuse risk xmss-rs; liboqs; QRL implementation
SPHINCS+ Hash-based NIST (2024) Stateless; Strong security guarantees Large signatures (10–50 KB); Slower verification liboqs; pqcrypto (Rust bindings)
WOTS+ Hash-based (building block) Simple construction One-time use only; Requires external state management Used in XMSS/SPHINCS+; custom wallets
CRYSTALS-Dilithium Lattice-based NIST Fast; Moderate size (~2–3 KB); Stateless More complex mathematics liboqs; pqcrypto-dilithium
Falcon Lattice-based NIST Very small signatures (~700 bytes) Complex implementation; Floating-point sensitivity liboqs; PQClean; CIRCL (Cloudflare)

4. Libraries

Organization Library / Stack Language Implements Used In Strengths Weaknesses
Open Quantum Safe liboqs C Dilithium, Falcon, SPHINCS+ OpenSSL, TLS experiments Broad support; Widely used; Continuous testing ABI instability; Requires strict version pinning
Cloudflare CIRCL Go Dilithium, Falcon (partial) TLS experiments High engineering quality; Performance-focused Go-only; Limited algorithm coverage
Google BoringSSL (internal) C/C++ (Limited PQ, mostly KEMs) PQ TLS (hybrid) Real-world deployment; Strong infrastructure No standalone PQ signature library; Not developer-facing
Microsoft (Various contributions) Mixed (Via PQClean, NIST PQC work) Windows, Azure Strong research + standardization involvement No standalone library; Mostly internal/experimental
AWS s2n-tls C (via liboqs integration) TLS Production-grade TLS stack No independent PQ signature implementation
IBM / Intel (Optimized impls) Mixed Dilithium, Falcon Research, hardware optimization Performance optimization; Hardware acceleration No unified developer-facing library

5. Comparison of PQ Libraries

Backing PQ signatures Maturity Language TLS usage Substrate compatibility
liboqs Multi-org Full High C (+ Rust bindings) Yes Yes
CIRCL Cloudflare Partial High Go Yes No
Google (BoringSSL) Google Minimal Medium C++ Yes No

6. Key Observations

  • Large companies contribute to shared implementations (PQClean, liboqs) but at the same time avoid building standalone PQ libraries.
  • No fully mature PQ stack yet, APIs still evolving, limited long-term audits.
  • liboqs is effectively the de facto standard integration layer across the ecosystem.

7. Recommendations

7.1 Transaction Layer

Option A (recommended baseline)

  • SPHINCS+
    • Stateless
    • Safer for wallet UX

Option B (advanced / research)

  • WOTS+
    • Requires:
      • State synchronization
      • Failure recovery logic

7.2 Consensus Layer

  • Dilithium

Reasons:

  • Fast
  • Stateless
  • Moderate size
  • Suitable for validator workloads

7.3 Implementation Stack

Substrate runtime (Rust)
		↓
Crypto trait abstraction
		↓
Rust wrapper (oqs / pqcrypto)
		↓
liboqs (C, pinned version)
  • Vendor liboqs (avoid system installs)
  • Pin exact commits
  • Abstract crypto via traits
  • Plan for algorithm upgrades

8 References

Signature Scheme Specs

Libraries