Tezos and Post-Quantum Cryptography
It’s unlikely that quantum computers will endanger public-key cryptography within the next few years, but the “harvest-now, forge-later” problem means blockchains should still plan for migration. Tezos doesn’t need to rush adoption of immature post-quantum (PQ) primitives, but it does need a roadmap that anticipates how each cryptographic component would evolve.
Elliptic-curve–based systems (Ed25519, BLS12-381, etc.) are the parts at risk; symmetric ciphers and hash functions only need longer keys to offset Grover’s quadratic speedup. In Tezos, quantum-vulnerable primitives appear in:
-
Signatures for implicit (tz1/tz2/tz3/tz4) accounts
-
Aggregated attestations (BLS since the Seoul upgrade)
-
DAL data-availability proofs (KZG commitments on BLS12-381)
-
The class-group VDF used for randomness
-
Smart-contract primitives (Sapling’s Groth16 proofs, timelock puzzles)
Below is what a plausible post-quantum Tezos could look like.
1. Signatures for implicit accounts
The safest path is to follow the NIST-standardized lattice schemes.
-
Dilithium (ML-DSA, FIPS 204) is already standardized.
-
Falcon (to be FIPS 206) offers smaller signatures (≈ 666–750 B) and faster verification but relies on delicate floating-point sampling.
-
HAWK is experimental: faster signing, similar size, but not yet standardized.
For Tezos accounts, verification throughput matters more than signing speed, since each user signs their own transactions but bakers verify many. Falcon’s fast verification makes it appealing once it’s standardized and audited. Dilithium’s integer arithmetic, however, is simpler to implement securely and probably far better suited for aggregation in STARK circuits or batched verification proofs.
A realistic first step is hybrid signatures: require both an elliptic-curve and a PQ signature (following IETF LAMPS composite-signature profiles). This lets Tezos maintain current security while providing a PQ-secure fallback if and when quantum threats materialize.
Practical considerations:
-
Falcon-512 pk ≈ 897 B vs Ed25519 pk 32 B → reveals cost more gas and chain storage.
-
New
tz*prefixes would be needed for PQ keys. -
Hardware wallets and HSMs will lag behind Falcon; Dilithium is easier to support.
2. Aggregated attestations
Today’s aggregated attestations use BLS signatures (tz4) with proof-of-possession semantics introduced in Seoul. In a PQ world, BLS must be replaced. Three directions exist:
-
PQ multisignatures or aggregates (still research-grade).
-
Batch verification of individual PQ signatures proven correct inside a STARK.
-
Hybrid epoch certificates combining classical and PQ proofs until the transition completes.
The STARK-aggregation route is conceptually sound but expensive—hundreds of PQ signature verifications per block would make large circuits. Proof generation can be parallelized, though.
Given that, Dilithium’s integer arithmetic again helps: it’s likely simpler to arithmetize for STARK proofs than Falcon’s floating-point sampling, and the prover code can reuse existing STARK tooling.
3. DAL (Data-Availability Layer)
Tezos DAL commitments rely on KZG polynomial commitments over BLS12-381 pairings, which aren’t PQ-safe. A post-quantum DAL would likely move to FRI/STARK-style polynomial commitments or lattice-based commitments. This increases proof sizes and verifier cost but eliminates trusted setups and pairing dependencies.
4. Randomness (VDF and RANDAO)
Tezos randomness combines a RANDAO (which can be biased) with a class-group VDF (unbiasable). In a PQ world:
-
Class-group VDF security is likely broken
-
Alternatively, Tezos could drop the VDF and use RANDAO alone—simpler but a little bias-prone.
-
A “STARK-verified VDF” like VeeDo
5. Smart-contract primitives
Sapling’s Groth16 proofs and BLS verification opcodes rely on pairings and must eventually migrate to STARK-based or lattice-based systems. STARK proofs are bulkier (hundreds of kB vs hundreds of B) but can be aggregated or compressed by bakers. Timelock puzzles and other sequential-work primitives would need explicitly sequential, quantum-resistant designs like VeeDo (they aren’t in use in the protocol though).
6. The overall picture
A post-quantum Tezos likely means:
-
Dilithium (ML-DSA) for account keys initially; Falcon or HAWK as optional faster alternatives later.
-
Hybrid signatures combining classical and PQ schemes during the migration.
-
STARK or lattice-based commitments replacing pairings in the DAL and privacy features.
-
FRI-style verifier support at protocol level for efficient on-chain proof verification.
-
hash-chain–based VDFs instead of class groups.
