Post Quantum Crypto is Big.
Bitcoin blocks are not.

The facts: Qunatum Computers are coming [1]. Quantum Computers break public key crypto [2]. Bitcoin relies on public key crypto for control & ownership of Bitcoin [3]. Bitcoin must migrate to Post Quantum (PQ) crypto before Qauntum arrives [4]. Bitcoin blocks are small [5]. PQ crypto is Big [6].

Let's look at some PQ signature options and the impact they would have on Bitcoin.

Assumptions:

  • Bitcoin blocks have a weight limit of 4,000,000 WU (1,000,000 vbytes, ~4MB physical size) and will not change.
  • Bitcoin will opt for a simple & straightforward upgrade path compared to more involved & novel changes.
  • Let's assume that there *might* be a further witness discount. This does not change the physical storage increase.
  • We will use these assumptions for calcualting impact on TPS.
  • The PQ Zoo is in progress. We will use this refernce as our source of truth.
↓ let's do some math ↓

A Project Eleven (P11) thing.

0% bigger than ECDSA

256-bit ECDSA

Total Bytes: 102

Hardness Assumptions: Discrete Logarithm Problem

Total Size: 102 bytes

Public Key Size: 70 bytes

Signature Size: 32 bytes

Cycles to sign: 29938 cycles

Cycles to verify: 11842 cycles

Bits of security: 128 bits

Reduction in TPS with no witness discount: 0%

Witness discount to maintain TPS: 0

Falcon-512 | FN-DSA-512 | FIPS 206

Total Bytes: 1563

Hardness Assumptions: NTRU lattice-based

Total Size: 1563 bytes

Public Key Size: 897 bytes

Signature Size: 666 bytes

Cycles to sign: 1009764 cycles

Cycles to verify: 81036 cycles

Bits of security: 128 bits

Reduction in TPS with no witness discount: 0%

Witness discount to maintain TPS: 0

Falcon-1024 | FN-DSA-1024 | FIPS 206

Total Bytes: 3073

Hardness Assumptions: NTRU lattice-based

Total Size: 3073 bytes

Public Key Size: 1793 bytes

Signature Size: 1280 bytes

Cycles to sign: 2053080 cycles

Cycles to verify: 160596 cycles

Bits of security: 256 bits

Reduction in TPS with no witness discount: 0%

Witness discount to maintain TPS: 0

CRYSTALS-Dilithium2 | ML-DSA-44 | FIPS 204

Total Bytes: 3732

Hardness Assumptions: Lattice-based learning with Errors (LWE)

Total Size: 3732 bytes

Public Key Size: 1312 bytes

Signature Size: 2420 bytes

Cycles to sign: 333013 cycles

Cycles to verify: 118412 cycles

Bits of security: 128 bits

Reduction in TPS with no witness discount: 0%

Witness discount to maintain TPS: 0

CRYSTALS-Dilithium3 | ML-DSA-65 | FIPS 204

Total Bytes: 5261

Hardness Assumptions: Lattice-based learning with Errors (LWE)

Total Size: 5261 bytes

Public Key Size: 1952 bytes

Signature Size: 3309 bytes

Cycles to sign: 529106 cycles

Cycles to verify: 179424 cycles

Bits of security: 192 bits

Reduction in TPS with no witness discount: 0%

Witness discount to maintain TPS: 0

CRYSTALS-Dilithium5 | ML-DSA-87 | FIPS 204

Total Bytes: 7291

Hardness Assumptions: Lattice-based learning with Errors (LWE)

Total Size: 7291 bytes

Public Key Size: 2592 bytes

Signature Size: 4627 bytes

Cycles to sign: 642192 cycles

Cycles to verify: 279936 cycles

Bits of security: 256 bits

Reduction in TPS with no witness discount: 0%

Witness discount to maintain TPS: 0

SPHINCS+-128s | SLH-DSA-SHAKE-128s | FIPS 205

Total Bytes: 7888

Hardness Assumptions: Hash functions

Total Size: 7888 bytes

Public Key Size: 32 bytes

Signature Size: 7865 bytes

Cycles to sign: 4682570992 cycles

Cycles to verify: 4764084 cycles

Bits of security: 128 bits

Reduction in TPS with no witness discount: 0%

Witness discount to maintain TPS: 0

SPHINCS+-192s | SLH-DSA-SHAKE-192s | FIPS 205

Total Bytes: 16272

Hardness Assumptions: Hash functions

Total Size: 16272 bytes

Public Key Size: 48 bytes

Signature Size: 16224 bytes

Cycles to sign: 8091419556 cycles

Cycles to verify: 6465506 cycles

Bits of security: 192 bits

Reduction in TPS with no witness discount: 0%

Witness discount to maintain TPS: 0

SPHINCS+-128f | SLH-DSA-SHAKE-128f | FIPS 205

Total Bytes: 17120

Hardness Assumptions: Hash functions

Total Size: 17120 bytes

Public Key Size: 32 bytes

Signature Size: 17088 bytes

Cycles to sign: 239793806 cycles

Cycles to verify: 12909924 cycles

Bits of security: 128 bits

Reduction in TPS with no witness discount: 0%

Witness discount to maintain TPS: 0

SPHINCS+-256s | SLH-DSA-SHAKE-256s | FIPS 205

Total Bytes: 29856

Hardness Assumptions: Hash functions

Total Size: 29856 bytes

Public Key Size: 64 bytes

Signature Size: 29792 bytes

Cycles to sign: 7085272100 cycles

Cycles to verify: 10216560 cycles

Bits of security: 256 bits

Reduction in TPS with no witness discount: 0%

Witness discount to maintain TPS: 0

SPHINCS+-192f | SLH-DSA-SHAKE-192f | FIPS 205

Total Bytes: 35712

Hardness Assumptions: Hash functions

Total Size: 35712 bytes

Public Key Size: 48 bytes

Signature Size: 35664 bytes

Cycles to sign: 386861992 cycles

Cycles to verify: 19876926 cycles

Bits of security: 192 bits

Reduction in TPS with no witness discount: 0%

Witness discount to maintain TPS: 0

SPHINCS+-256f | SLH-DSA-SHAKE-256f | FIPS 205

Total Bytes: 49920

Hardness Assumptions: Hash functions

Total Size: 49920 bytes

Public Key Size: 64 bytes

Signature Size: 49856 bytes

Cycles to sign: 763942250 cycles

Cycles to verify: 19886032 cycles

Bits of security: 256 bits

Reduction in TPS with no witness discount: 0%

Witness discount to maintain TPS: 0