Post-Quantum Migration of Blockchains
Every code listing from this chapter of Applied Post-Quantum Cryptography — 1 in total, 1 runnable here. Edit any cell and press Run.
The book's snippets build on each other down the chapter, but a Sage Cell
kernel runs one cell and keeps no state afterwards, so each cell replays the
earlier listings with apqc_book. That call is the only thing added
to the book's own code.
Listing 1 — Migration is bounded by blockspace
Here is the constraint that the roadmap debates tend to skip. Migrating a coin is not a database update; it is a transaction, and transactions compete for a fixed and quite small amount of blockspace. So there is a floor on how fast any migration can possibly proceed, and it depends only on arithmetic — the number of outputs to move, the size of a post-quantum spend, and the throughput of the chain.
Write N for the number of unspent outputs to migrate, w for the weight a single migration transaction consumes, W for the weight available per block, and T for the block interval. If migration were given every unit of every block, it would still take
and at a share σ of blockspace the figure scales by 1/σ.
Two features of this bound deserve emphasis. It is a lower bound assuming all of the chain's capacity goes to migration and nothing else — no payments, no ordinary economic activity — which no live chain would tolerate. And it is driven by w, which for a post-quantum spend is dominated by the signature and public key, exactly the quantities that are one to two orders of magnitude larger than what they replace. The sizes tabulated throughout this book are not merely a bandwidth annoyance: they set the clock on the migration itself.
A published analysis of this question for Bitcoin reports a required downtime on the order of a few months of exclusive blockspace, under its own assumptions about which outputs must move and what a migration spend costs. The exercise below builds a cruder model and gets a larger answer; the discrepancy is the instructive part, and reconciling the two is the point.
remark[Why this reframes the whole chapter] Every other quantity in this chapter is contested: when Q-Day arrives, whether a freeze is legitimate, which signature scheme wins. The throughput bound is not. It follows from block size, signature size, and arithmetic, and it says that even a perfectly coordinated ecosystem with universal agreement and instant wallet support could not complete the migration quickly. That is the strongest available argument for starting early, and it does not require winning any argument about quantum hardware. remark
*Exercise: compute the bound
The formula above is worth evaluating rather than reading, because the sensitivity to w is the lesson. Using the tools of the “SageMath Basics for Post-Quantum Cryptography” chapter: