This work presents a formal, state-machine-based treatment of protocol-level quantum safety in Bitcoin under quantum polynomial-time (QPT) adversaries. We model Bitcoin as a deterministic state transition system over the UTXO set and define authorization as a game-based property. We introduce a set of invariants including authorization integrity, no double-spend, and deterministic validation, and formally prove their preservation under valid state transitions. We provide a reduction showing that any unauthorized spend implies either a break of EUF-CMA security of the signature scheme or a violation of hash-based binding properties, in both the classical and quantum random oracle model (QROM), without relying on oracle reprogramming or rewinding techniques. The model explicitly incorporates adversarial network conditions, including mempool observation, transaction reordering, and chain reorganizations, and proves that such capabilities do not enable unauthorized state transitions. We formalize a consensus-semantic equivalence relation over transactions via a normalization function, ensuring that validation and state transitions are invariant under representation-level differences. Additionally, we analyze identifier integrity under quantum collision search (BHT) and provide system-level bounds relative to the active UTXO set. Finally, we prove a no-free-migration result: under purely cryptographic authorization, no transformation of the current UTXO set can simultaneously preserve both safety (no unauthorized spend under quantum adversaries) and liveness (all coins remain spendable), making migration trade-offs unavoidable. This work aims to distinguish between localized constructions and system-wide security guarantees, and to provide a formal foundation for evaluating quantum safety claims at the protocol level.
This work presents a formal, state-machine-based treatment of protocol-level quantum safety in Bitcoin under quantum polynomial-time (QPT) adversaries. We model Bitcoin as a deterministic state transition system over the UTXO set and define authorization as a game-based property. We introduce a set of invariants including authorization integrity, no double-spend, and deterministic validation, and formally prove their preservation under valid state transitions. We provide a reduction showing that any unauthorized spend implies either a break of EUF-CMA security of the signature scheme or a violation of hash-based binding properties, in both the classical and quantum random oracle model (QROM), without relying on oracle reprogramming or rewinding techniques. The model explicitly incorporates adversarial network conditions, including mempool observation, transaction reordering, and chain reorganizations, and proves that such capabilities do not enable unauthorized state transitions. We formalize a consensus-semantic equivalence relation over transactions via a normalization function, ensuring that validation and state transitions are invariant under representation-level differences. Additionally, we analyze identifier integrity under quantum collision search (BHT) and provide system-level bounds relative to the active UTXO set. Finally, we prove a no-free-migration result: under purely cryptographic authorization, no transformation of the current UTXO set can simultaneously preserve both safety (no unauthorized spend under quantum adversaries) and liveness (all coins remain spendable), making migration trade-offs unavoidable. This work aims to distinguish between localized constructions and system-wide security guarantees, and to provide a formal foundation for evaluating quantum safety claims at the protocol level.
Bitcoin and its underlying blockchain protocol have recently received significant attention in the context of building distributed systems and foundations of the consensus problem. At the same time, the rapid development in quantum computing makes the threats to cryptography more and more concerning. In this work, we revisit the formal security of the core of the Bitcoin consensus protocol, called the Bitcoin backbone (Eurocrypt 2015), in the presence of quantum adversaries -- i.e. adversaries equipped with quantum computers.
We show that the security of the Bitcoin backbone holds under a quantum analogue of the ``honest majority'' assumption that we develop. The critical ingredient of proving security of the blockchain is to analyzing the quantum query complexity of a Chain-of-Proofs-of-Work search problem. This problem in turn reduces to a problem we call multi-solution Bernoulli search, for which we establish its quantum query complexity. This can be viewed as an extension of a threshold direct product theorem to an average-case unstructured search problem. Our proof, adding to active recent efforts, simplifies and generalizes the powerful recording technique due to Zhandry (Crypto 2019).
Our analysis indicates that the security of the Bitcoin backbone protocol is guaranteed provided that the number of adversarial quantum queries is bounded so that each quantum query is worth O(p−1/2) classical ones, where p is the probability of success of a single classical query to the protocol's underlying hash function. Perhaps surprisingly, the wait time for safe settlement of transactions in the case of quantum adversaries matches (up to a constant) the safe settlement time in the classical case and thus does not result in any further overhead.
Blockchain systems are fundamentally dependent on classical cryptographic primitives, which are increasingly threatened by the rapid advancement of quantum computing. In cross-chain communication and interoperability protocols, where safe asset transfer and validation across heterogeneous networks are crucial, this danger is especially serious. Ensuring quantum-resilient interoperability is crucial for preserving security, trust, and long-term sustainability as next-generation blockchain ecosystems move toward multi-chain architectures. Relays, bridges, and atomic swaps are examples of existing interoperability methods that mostly rely on public-key cryptography, which is susceptible to quantum assaults like Shor's algorithm. In the post-quantum era, this vulnerability puts digital assets and cross-chain transactions at risk of compromise. This paper suggests a quantum-resilient cross-chain interoperability protocol framework to overcome this difficulty and allow safe and effective communication between various blockchain platforms. The suggested design incorporates post-quantum cryptographic techniques, such as hash-based and lattice-based signature algorithms, with consensus bridging and cross-chain transaction validation procedures. Additionally, a hybrid cryptographic transition model is presented to provide a progressive transition towards quantum-safe primitives while guaranteeing backward compatibility with current classical systems. The proposed structure greatly increases resilience against quantum attackers while maintaining interoperability efficiency, according to experimental evaluation. Robustness against replay attacks, signature forging, and key compromise under quantum threat models is confirmed by security analysis. The suggested protocol ensures strong and quantum-resilient interoperability in next-generation blockchain infrastructures by offering a scalable and future-ready foundation for safe multi-chain ecosystems.
Bitcoin transaction relay is decentralized and governed by locally defined, non consensus policies that are neither globally enforced nor externally observable as explicit configuration. While the effects of these policies may in principle be indirectly inferred through relay metadata only under aggregate adversary level observation accumulated over time and with significant uncertainty, their opacity results in probabilistic and heterogeneous propagation behavior. Each node maintains an independent mempool and propagates transactions according to local rules and network conditions. Under hypothetical cryptographically relevant quantum computer (CRQC) assumptions, transaction relay behavior becomes a relevant factor in public key exposure risk. This paper presents a defensive threat model in which an adversary operates a coordinated network of protocol compliant Bitcoin peer to peer nodes to probabilistically obtain preferential locally first seen visibility at standard broadcast time into transactions that reveal public key material. Observation occurs only upon normal transaction broadcast from ordinary network nodes and is limited to what individual nodes receive and infer relative to their connected peers and local mempool state. The model relies on probabilistic network positioning rather than pre broadcast access, protocol deviation, or relay interference. The analysis does not assume deterministic control of relay, miner collusion, eclipse attacks, privileged network access, or present day quantum feasibility. Instead, it formalizes how partial node local observability, relay variance, and adaptive analytical selection may increase expected adversarial value under uncertainty while remaining indistinguishable from benign network participation. A quantitative expected value framework and a lightweight simulation are introduced to bound adversarial advantage as a function of network coverage, propagation delay variance, and cryptographic feasibility. The work is grounded in prior empirical measurement literature and is intended to inform defensive monitoring and mitigation research rather than predict specific attacks or timelines.
The concept of blockchain technology has transformed the digital ecosystem to allow decentralized, transparent and immutable transactions in various sectors. Its security is closely dependent on classical cryptography like ECDSA and RSA to perform digital signatures and SHA-256 to achieve consensus, which are becoming more susceptible to quantum computing. The cryptographic principles underpinning blockchain could be compromised with the emergence of the quantum algorithms of Shor and Grover, endangering the integrity of transactions, authentication and consensus protocols. This paper discusses the implications that quantum computing could have on blockchain security, analyses vulnerabilities of current cryptographic primitives and assesses post-quantum cryptographic (PQC) protocols, including lattice-based protocols, hash-based protocols, and code-based protocols. To guarantee backwards compatibility, as well as a gradual upgrade process to quantum-resistant protocols, a hybrid migration approach that involves transactions with two signatures is suggested. Experimental analysis shows that PQC integration attains reasonable performance trade-offs, that preserve verification costs, block size growth, and throughput effects within feasible limits, and that zero-loss resilience is achieved during reorganization tests. The conclusion is that blockchains with PQC support can reach post-quantum levels of security without major operation interruption, and they provide a viable roadmap to moving towards distributed ledger systems that are future-ready.
Recent developments in quantum computers pose an imminent threat to cryptography since many widely used cryptographic schemes will no longer be secure. This worrisome scenario motivated a growing interest in the field of post-quantum cryptography, which aims to design cryptosystems that are postquantum secure, i.e. secure against quantum-capable adversaries. While finding post-quantum computational hardness assumptions is pivotal to achieve this goal, an issue that is often overlooked is provable security. In fact, to prove that the post-quantum computational hardness necessarily implies post-quantum security of the derived cryptosystem, the reduction argument that establishes this implication also needs to be post-quantum. As such, many new methods have been devised in the last few years to handle this adaptation to the quantum setting. In particular, the quantum analogue of the Random Oracle Model has garnered special interest, as it is the foundation of many cryptographic schemes, from public-key encryption to digital signatures. It is also very problematic and usually the main culprit of the failure of security proofs when transitioning to the quantum setting. This work offers a comprehensive exposition on the most influential techniques developed in the last decade to enable or facilitate the construction of security proofs in the Quantum Random Oracle Model (QROM). Each presented technique offers an unique purpose and a solution to a problem provoked by the QROM, and, as such, as a whole, this works allows for an understanding of the most common strategies to construct these type of security proofs. This is accomplished by presenting and analyzing the security proof of three cryptographic schemes set in this model, which underlines the central role these techniques take in provable quantum security.
As quantum computing advances, classical cryptographic systems - signature schemes, key exchange protocols, public-key encryption, and certain hash constructions - that secure most blockchain platforms come under threat, raising serious concerns about their long-term security and integrity. Transitioning to post-quantum primitives is rarely straightforward: their larger sizes and higher computation costs can have unintended consequences, and in some cases make such a transition impractical. We examine the impact of post-quantum migration on blockchain systems across three dimensions. First, we dissect the cryptographic primitives most vulnerable to quantum attacks within the consensus, identity, and transaction-validation layers. Next, we survey proposed post-quantum adaptations and evaluate their practical feasibility. Finally, we assess how substituting classical primitives with post-quantum alternatives affects system performance, protocol behavior, and the underlying incentive and trust structures. Our findings show that PQ adoption is far from a drop-in replacement: it demands careful architectural reconsideration, as naive substitution risks destabilizing core protocol operations and weakening the security and efficiency guarantees blockchains rely upon.