Topic: Bitcoin's Quantum Evolution (Read 211 times)

Are these posts that are here on this forum? I would love to dive into the discussions that were provoked by these words.

Is there a real difference between quantum-proof and quantum-resistant algorithms? Is there even such thing as an algorithm that is quantum-proof?

Navigating the Quantum Threat: A Call to the Bitcoin Community

To my fellow pioneers,

Over the past few decades, the cryptographic underpinnings that form the bedrock of our digital communications—and indeed, Bitcoin itself—have withstood numerous challenges. The secure, decentralized transactions that Bitcoin enables rely on public-key cryptosystems, notably ECC digital signatures, to ensure integrity and security within the network. These systems, however, rest on the computational intractability of problems like Integer Factorization and the Discrete Log Problem, a foundation that quantum computing threatens to unsettle.

In 1994, Peter Shor introduced an algorithm demonstrating that quantum computers could, in theory, solve these problems in polynomial time. This revelation places the security mechanisms of Bitcoin, and indeed all similar cryptosystems, at risk. Recognizing this impending challenge, entities like the NSA and NIST have initiated transitions towards quantum-resistant algorithms, signaling a shift that the cryptographic community must take seriously.

The evolution of quantum computing from theoretical curiosity to practical concern compels us to contemplate the future of Bitcoin in a post-quantum world. As developers, miners, and users vested in the ecosystem, the responsibility falls to us to anticipate and mitigate these threats. The dialogue around Post-Quantum Cryptography (PQC) is not just academic—it is a necessary evolution of our collective effort to preserve Bitcoin's legacy and ensure its resilience.

The NSA's 2015 announcement and NIST's subsequent call for quantum-resistant algorithms underscore the urgency of this transition. As a community that has thrived on innovation and adaptation, we are uniquely positioned to lead the charge in securing our technology against quantum vulnerabilities.

The path forward involves a collaborative effort to research, develop, and eventually deploy quantum-resistant cryptographic algorithms within the Bitcoin protocol. This task is neither small nor simple, but it is essential. Our proactive measures today will safeguard Bitcoin's security, decentralization, and integrity for the future.

Let this message serve as a call to action. I encourage developers, cryptographers, and all community members to engage in this vital discussion. Together, we can confront the quantum challenge and secure the future of Bitcoin against the unforeseen threats of tomorrow.

In unity and anticipation,

[A Legendary Member of Bitcointalk]

---

Subject: The Quantum Quandary: NIST's Candidates vs. Bitcoin's Block Size Limit`

Fellow visionaries,

As we delve deeper into the realm of Post-Quantum Cryptography (PQC) and its implications for Bitcoin, an emerging challenge becomes increasingly apparent. The heart of the matter lies in the signature sizes of the three leading candidates proposed by NIST for quantum-resistant algorithms. While these candidates offer promising security against quantum computing threats, their integration into Bitcoin's ecosystem presents a notable hurdle: the significantly larger signature sizes compared to our current ECDSA secp256k1 standard.

Bitcoin's existing block size limit, meticulously designed to balance efficiency, security, and decentralization, has served us well. However, the augmented signature sizes of NIST's PQC candidates pose a risk of bloating the block space, potentially impacting transaction throughput and, by extension, the network's scalability and performance. The elegance and compactness of ECDSA secp256k1 signatures have been instrumental in maintaining Bitcoin's streamlined and efficient operation. Transitioning to a post-quantum cryptographic standard without addressing the increased signature size could introduce constraints that challenge this delicate balance.

The crux of our discourse should not be whether to adapt to the quantum threat—this is a given—but how we can do so while preserving the fundamental attributes that define Bitcoin. We are tasked with a formidable challenge: to innovate within the confines of our current architecture or to re-envision aspects of it to accommodate the future of quantum-resistant cryptography.

This situation calls for a collective effort to explore and develop solutions that align with Bitcoin's principles. Whether through optimizing the proposed PQC algorithms to reduce signature size, rethinking the block size limit, or devising novel cryptographic techniques that offer both quantum resistance and efficiency, our path forward must be forged with careful consideration and collaborative ingenuity.

As we stand at this crossroads, I invite the community to engage in a profound and forward-thinking dialogue. Let us pool our knowledge, creativity, and spirit of innovation to address this challenge. Together, we can navigate the complexities of integrating quantum-resistant algorithms into Bitcoin, ensuring its security and legacy in the face of quantum advancements.

In the spirit of collaboration and progress,

[A Legendary Member of Bitcointalk]

Mod note: Consecutive posts merged

Bitcoin-qt at that time used to mine block rewards to P2PK addresses, but transaction between wallets uses addresses.
Legacy to Bech32 and Bech32m didn't gain traction earlier on because many exchanges either didn't recognize these addresses or were still generating legacy addresses. The general reluctance would probably be gone once they realize it's either getting your coins stolen or transfer to a new address.
FWIW, BHT algorithm lowers the complexity for collision finding, which can be dangerous if and only if it is feasible. Finding pre-image of SHA256 would be tougher and isn't a concern, specifically relating to mining. The speedup from doing so is not high enough, complexity should still be around 2^80, IIRC.

Both. Because for example Satoshi used P2PK in the Genesis Block: https://mempool.space/address/04678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5f
But people sent a lot of coins into P2PKH: https://mempool.space/address/1A1zP1eP5QGefi2DMPTfTL5SLmv7DivfNa

Also note, that even if someone used P2PKH, the public key can be known, if there was at least one transaction. It doesn't even have to be confirmed, just created. For example: the famous Value Overflow Incident used P2PKH address: https://mempool.space/address/17TASsYPbdLrJo3UDxFfCMu5GXmxFwVZSW

But note that the public key was revealed in the transaction, which generated a lot of coins out of thin air, so it is known: https://mempool.space/address/046B5D97AEED2979207F4CA7D9E75CDEBF9EBB2A47D0B715370645F6845EDFA7ADFB0627AD7BDA601AD2D129EBF037C5750841E9BA64AB199C4CB8280A95335D96

SHA256 is the least of our worries. It's not particularily vulnerable to quantum computing and SHA256 ASICs are likely to outpace quantum computing even well after they've become capable of deriving private keys.

Also be aware that you're mixing apples and oranges. The 3 algorithms you mentioned are signature schemes whereas SHA256 is a hash function. Those are fundamentally different things used in fundamentally different manners.

On a side note, can someone remind whether address (which assumed to be owned by Satoshi) use P2PK or P2PKH? After all, P2PKH exist since Bitcoin 0.1.0.



Short answer, improve what we've done to make people move from legacy address (starts with either 1... or 3...) to Bech32/Bech32m address.


It depends on the cryptography algorithm itself. Usually it has either bigger signature size or longer verification time as the downside.

Bitcoin contains no encryption. You probably mean cryptography, i.e., ECDSA.

We are not afraid of quantum computers working out collisions of hash functions like SHA256. Only solution to the ECDLP is what will potentially be feasible. Address management is also very vague. There is no direct relation with SHA256 and "address management" apart from HASH160 which involves SHA256.

I think the quantum transition involves the encryption used by Bitcoin, sha256 will not be safe enough to keep operating the nodes and address management, so, new encryption algorithms will substitute sha256, the best options now are 3 algorithms: CRYSTALS-Dilithium, FALCON and SPHINCS+, this ones are quantum resistant cryptographic algorithms. And it looks like these ones will be the future of cryptography.

Sources:
https://www.nist.gov/news-events/news/2022/07/nist-announces-first-four-quantum-resistant-cryptographic-algorithms
https://pq-crystals.org/dilithium/index.shtml
https://falcon-sign.info/
https://sphincs.org/

Yes. All Bitcoin holders will have to generate keys that are quantum resistant and transfer their coins there.

Probably. If Satoshi does not transfer them to the future quantum safe addresses, then they'll end up being stolen.

Depends on the definition of "lost". Not all lost coins can be reclaimed. Coins sent to public keys whose private keys are considered "lost" by their owners, can be reclaimed. Coins sent to addresses which haven't revealed their private keys cannot be claimed by solving the ECDLP (as with the former), until they spend their coins and be forced to reveal it. These coins' vulnerability to being claimed will depend on how quickly the attacker can solve the ECDLP. For example, if they can solve it in less than 10 minutes, then they could double-spend your transaction while it is unconfirmed.

I'm not the best person to discuss quantum computers, but to alleviate your concerns, I believe that by the time they pose a significant threat, people will have already transitioned to quantum-safe algorithms years in advance.

In this forum, a recurrent theme centers around the growing apprehension concerning the advancements in quantum computing and its potential implications for Bitcoin's security. Numerous responses assert that, when the time comes, the network will undergo an upgrade to adopt a quantum-resistant encryption algorithm, thereby reinforcing its security.

My inquiry delves into the logistical intricacies of such a transition. Does this create a scenario where all users must transfer their Bitcoin holdings to these new quantum-resistant addresses? Moreover, the consideration arises regarding the implications for dormant Bitcoin holdings, such as those belonging to Satoshi. Without an entity to initiate the transfer to these fortified addresses, does this proposition imply the eventual reactivation of dormant bitcoins? Will all "lost" coins eventually be reclaimed by the advancement of quantum computing?

How would the transition to a quantum-resistant encryption algorithm impact the overall user experience, especially considering the potential requirement for users to transfer their Bitcoin holdings to new addresses?

Are there any potential downsides or trade-offs associated with the adoption of quantum-resistant encryption that the community should carefully consider before moving forward with such a significant upgrade?

In the event of transitioning to quantum-resistant addresses, what measures could be put in place to ensure a seamless and secure migration, considering the diverse range of users with varying levels of technical expertise?