Formalizing Blockchain PQC migration: When Is the Migration Deadline?

Abstract

It is widely recognized that quantum computers pose a fundamental threat to blockchain security. Post-quantum cryptography (PQC) migration is therefore an urgent challenge, yet the following question has remained unanswered: by when must the migration be completed to maintain the security of crypto assets? To address this question, we first formalize the migration process and the quantum adversary based on the Bitcoin backbone protocol framework. We then establish a threshold on the tolerable quantum adversary's capability. Specifically, we prove that a security property migration liveness holds with overwhelming probability if and only if Δeff ≥ Δ∗= ⌈4/(1 − )⌉, where Δeff is the number of rounds from the broadcast of a migration transaction until the quantum adversary can produce a forged transaction, is the honest mining success probability, and is the concentration quality of the underlying random variables. We further extend the analysis to encompass broader classes of blockchains and migration paths by parameterizing the number of honest blocks required during the migration window, with practical implications for real-world deployment.