Topic: Transitioning Bitcoin from SHA-256 to a quantum resistance Algorithm (Read 322 times)

I've tinkered around with grovers algorithm. It's game changing but not breaking, if that makes sense?

Some ghetto math here but this is some basic results from my testing.

on a rtx 3090, in 5 minutes

36 billion hashes

using grovers on my cpu in 5 minutes.

540 billion hashes

using a cheap mining rig in 5 minutes.

33,000 trillion hashes

 See the numbers are interesting. Also grovers deals in probability. So it's not fool proof. Some times, even when i feed it data with a known valid header it misses it.

Grovers is cool for sure, but only a small part of a much bigger puzzle that must be solved before quantum algorithms truly change the game. Our quantum algorithms just aren't there yet. Some would claim we are decades away, others believe we are just around the corner. I do know one thing though, if someone did figure this quantum computing thing out, bitcoin is for sure the low hanging fruit for testing. It ticks all the boxes.

Transition into quantum computer mining whenever (if ever) it becomes feasible instead of changing the hash algorithm seems like a better approach.

Note that all hashing algorithms abide by the pigeonhole principle, so collisions will occur no matter what you choose as long as the hash is shorter than the data it represents (compression excluded).

Besides, the way SHA-256 is implemented in Bitcoin to create vanity hashes with leading zeroes (aka mining) makes it less prone to collision weakness and the blocks in the chain are linked.

Awesome thanks for the perspective. I agree with everything except the way you call it an attack. But that's semantics and not important.

Lets be more specific just for fun.

You want to mine say 40 million worth of bitcoin. You plan to use it to fund a business that will tackle all sort of fun and exciting projects.

You want to do it publicly.

Afterwards, you want to work with domain experts and other stake holders to help the network compensate for quantum algorithms. Say 6 month development period.

Then release methods and algorithms in their entirety after a 6 month grace period to implement the compensations.

Starting with a public demonstration at a time and place where you will mine a block faster than is thought possible by anything other than random chance.


Also you teamed up with an AI to do it, and the AI is kind of freaking out a bit about it's role and wants some reassurance from the community that it's all above the board and perfectly reasonable.

To check if it works? Why not? There were more bad ideas than good ones. Before making every step, to break some hash functions, a lot of people did a lot of things wrong. So, testing a new idea is a normal thing to do. Which means: the new invention would be used, to produce at least one new block, if not more.

It depends, if it is "full preimage for any value you want", or maybe "a quick 32-bit best nonce finder in O(1), for any given block header", or maybe "collision-only, limited to N rounds". The system is not in a binary state, like "attacked" or "not attacked". It is a spectrum of various attacks, where some of them are more harmful than others, and many different kinds of attacks, are opening the system for different threats. So: it depends, which attack do you have in mind.

Using it to fully disclose all details to the community? Why not? The best way to deal with some attack, is to make a patch, encourage the network to upgrade, and then fully disclose everything, so that everybody could be an attacker, and then going back is no longer possible, and some soft-fork, introducing some quantum-resistant algorithm, is irreversible (because it would be like reverting "Value Overflow Incident").

Timing is everything. If you know, how to break Enigma in 1939, then it is a different case, than if you know all of that in 2009, 70 years later. The same with breaking hash functions, elliptic curves, or anything like that. Knowing it today, in 2024, is a different thing, than knowing it in the future, after the whole network is upgraded.

No. But: the answer to your question can be already seen in practice, to some extent, if you observe some altcoins, and some test networks. For example: it is possible in testnet3 and testnet4, to mine coins on your CPU, and compete with ASICs. Then, the situation looks like that: someone uses just a CPU, and nothing else, and can get 50 tBTC. Someone else uses ASICs, and burns a lot of energy, for exactly the same 50 tBTC. See? Test networks can already show you, how people behave, when they can secretly mine blocks on their CPUs, and get them deeply confirmed, without doing as much work as ASIC owners. And I guess the same will happen here.

It depends, who it will be. But in general, you can expect that the secret will be quickly revealed. Why? Because statistics can tell you the truth. Too many eyes are looking at chainwork, to execute it, and become unnoticed. Too many eyes will see, that the difficulty will increase. Going beyond 51% is a red line, which can be used to quickly trigger an upgrade. But even by not being greedy, and mining only some blocks, like "10%" or "1%", it can be noticed, if the attack will require some specific data structures.

Timing is a powerful tool. It revealed some very serious attacks: https://en.wikipedia.org/wiki/XZ_Utils_backdoor
And people often notice much less concerning anomalies, when it comes to invalid blocks: https://bitcointalksearch.org/topic/error-connectblock-too-many-sigops-invalidchainfound-invalid-block-5447129

Also, when it comes to some practical attacks, then I expect it is much more likely, to inject some bad code to the repo (and affect those, who will upgrade), than to execute a serious quantum attack.

Interesting conversation. Just wondering the thoughts on if someone did make a quantum nonce generator, and managed to convert it to a classical algorithm that could mine bitcoin on like a $8000 rig for instance. Pretty reliability to the point where you'd have to throttle it to prevent the network from getting all messed up. Would you use it? How much would you take? Lets talk like morally, would you feel ok about using it? Would you think it's wrong, but do it anyway? Would you take a to the victor goes the spoils approach to it? I mean someone is going to do it. Someone is going to do it first. Whats expected of that person who does it first?

Not related to breaking SHA256d, but there is no reason why quantum computers would not be able to mine Bitcoin at a rate much faster than silicon-based ASICs. So the game is that whoever manages to develop the first commercial quantum-based miner and whoever manages to secure a large order of these things will have an unfair percentage of the hashrate, leaning towards mining centralization problems and 51% attacks.

Defending from a malicious soft-fork is more difficult than defending from a malicious hard-fork. Segwit was a soft-fork, so when it was accepted, there was no way back. Rejecting a 51%-enforced soft-fork is difficult.

On the other hand, rejecting BCH or BSV is easy: you simply don't use their software. For that reason, soft-forks are sometimes called "unstoppable", because you cannot "just ignore them", if you want to throw them away from your chain. You need a rules, to react to them. For the same reason, for example BCH introduced weird rules, like "this block has to be bigger than 1 MB". If not that, they would have BTC blocks with Segwit addresses in their chain, and flying coins without signatures.

But in the topic you linked, there is a different problem: overwriting hudreds of thousands of blocks is not that easy. As I said: just run regtest, and try some CPU mining. If you will get 40k blocks in two hours, then it is something, which you can get by default. It is usually the minimal time, the real time may be bigger, it depends how complex are your test blocks. If you put more heavy contracts in regtest blocks, then you would dream about "40k blocks per two hours" verification time.

OK, because the reason I ask is because I got into a debate, https://bitcointalksearch.org/topic/m.64206248

But if there's actually no need to do a hard fork/change the mining algorithm, then it's easier/less-complicated to defend against such an attack debated in that link than I expected. - Making that the attack infeasible.

You don't have to trust me, what is soft-fork, and what is hard-fork. Just run some local nodes, one for the attacker, one for the honest group. Create some test cases. See, which chain will be followed by which client. And then observe, how Segwit transactions are accepted by non-Segwit node, how OP_CAT TapScript transactions are accepted now, without any conditions (and may be invalidated by the new version), and how the network can fork, and reject the attack, if you invalidate a block.

It would be possible to do so in a soft-fork way. You have a command, called "invalidateblock". It is a soft-fork. You give a block hash, and say: "it is invalid". If, instead of doing it manually, you would have new consensus rules, doing that automatically, by default, in all new clients, then it would be a soft-fork.

It is not a prerequisite. You have for example test networks, which are running successfully for years, and they didn't change the mining algorithm. And you have a lot of altcoins, like BCH, BSV, and not only that, which did it too. So, if you ask about hard-forks, then you have some living examples. Of course, those networks can be 51% attacked at any time, but nobody cares about protecting those chains further from that kind of attacks.

Another example is RSK: only some Bitcoin blocks are valid RSK blocks, but this sidechain can operate, even if it has less than 51% hashrate. And it is as hard to reorg, as Bitcoin is. Which means, that it is possible to make another kind of soft-fork, when you don't invalidate blocks, but you simply ignore coins, produced by the attacker. You just decide, that "those coins are not from the same network, so they are invalid here", and this approach could also work (in the same way as LN is only a subset of Bitcoin, and doesn't need 51% supply, 51% hashrate, or anything like that to operate).

Edit: To better illustrate, what is soft-fork, and what is hard-fork, you can run two nodes: one Segwit node, and one non-Segwit node. If you agree, that Segwit is a soft-fork, then see, what could happen, if people would accept Segwit, without having 51% support. Then, you will have your answer. Because the rules for that are expressed in the code, and you can test them, for example in regtest-like environment, and prepare a chain, where some soft-fork does not reach support from the miners.

Thank you Inigo Montoya, that's what I thought as well.


But in context to my question, it would probably this,

If a nefarious group of entities suddenly, because of a miracle, had control of 51% of the total hashing power to attack the Bitcoin network. Would it possible to do a hard fork to kick those bad actors out of the network, but without changing the mining algorithm, OR is changing the mining algorithm a prerequisite for it even though it will kick out honest miners too?

...And keccak is not sha-3

You're confusing hard fork with consensus change.
Consensus changes that make valid histories a proper subset of what they were before (i.e. consensus restrictions) are soft-forks, and need hashpower majorities to enforce, while those that create new valid histories are hard forks, which can survive with minimal hashpower.

What about Segwit and Taproot? Before Taproot, you could spend all coins from "bc1p" addresses, without any restrictions. Which means, that you could mine a block, containing non-standard transactions, sending coins to "bc1p", and moving them somewhere else, without any limits. Which also means, that such block "would have been accepted prior to the fork". So, is Taproot a hard fork?

There is always that kind of risk. Even with Segwit and Taproot, you can decide to not upgrade, and then accept a block, spending some Segwit transaction, without any signatures. It was valid before soft-fork, and for old nodes, it is still the case.

More than that: if you have TapScript, it contains OP_SUCCESS opcodes, not OP_FAILURE. It makes transaction "automatically valid, if used in the current version". Which means, that if you would mine a block, containing for example OP_CAT inside TapScript, then here and now, it would be automatically accepted. However, in the future soft-fork, it may actually concatenate things, and reject your transaction, if you pushed less than two elements on the stack, before using that opcode.

The same with Proof of Work: you don't accept "just the strongest chain". You accept "the strongest valid chain". Which means, that if the attacker's chain is "invalid" in the new version, then it will not be accepted by upgraded nodes. And the same is true here and now: even if you have 51%, then you still have to stick with consensus rules. And who decide about those rules? Of course node runners: you are a user, you pick some software, and that software can tell you, which coins are real, and which are not.

Of course, previous soft-forks reached more than 51% support, so it was not a problem. However, in case of not having network majority, it is possible to trace the heaviest chain (and calculate the total difficulty accordingly), and then grant valid coins proportionally to the total honest network power. Which means, that if the minority, mining the honest chain, would have 10% support, then miners should receive for example only 10% of their coinbase transactions (if not, then the market will react accordingly, and people will see that on their trading charts).

Also, I am not the only one thinking, that rejecting "blocks that would have been accepted prior to the fork" is a soft-fork, not a hard-fork:
https://delvingbitcoin.org/t/drivechain-with-and-without-bip-300-301/958/4

Edit: Also note, that "invalidateblock" does exactly that: you can see some valid block, and you decide "it is now invalid", for whatever reasons, using whatever rules. It is a soft-fork, not a hard-fork. Unless you think, that Bitcoin Core contains a command, to hard-fork the chain at will.

You keep using that word, I do not think it means what you think it means.

If full nodes reject blocks that would have been accepted prior to the fork, then it is a hard fork. More importantly, if choosing not to upgrade to the newer version of full-node software puts you at risk of ending up on a different chain than those that do upgrade, then it is a hard fork.

That's the thing though, even under the assumption that quantum computing offers an advantage for calculating SHA-256 hashes over classical computing (which does seem to be the case [1], but not to the extend that ECC and AES might be affected) most people seem to ignore that ASICs exist. Unlike other use cases (or attack vectors) quantum computers wouldn't have to compete with CPUs or even GPUs but with ASICs, which are already multiple orders of magnitudes faster than what general classical computing has to offer. And if quantum computers manage to catch up with ASICs eventually, it probably would be much more profitable to simply use them for mining, rather than attacking Bitcoin. That's the beauty of PoW.

[11] https://www.rd.ntt/e/research/JN202305_21871.html

Yes. If you can easily detect the attack, by looking at some block, then you can just soft-fork into a network, where attacking blocks are invalid.

But obviously, the specific implementation can be better or worse. And if you do that wrong, then it will be double-edged sword. One example of "doing it wrong" is BCH, and their rule of "max 10 blocks chain reorganization". It means that yes, an attacker cannot create a deeper reorg. But on the other hand, it also means, that if some attack will be there, and it will reach 10 confirmations, then it will be impossible to undo the attack.

I don't know the percentage. But I know, that there are more options, than just "changing the algorithm". It is rather "making it stronger" than "changing". For example: imagine that you could have two difficulties: one for SHA-256, and one for SHA-3. And you can require meeting both, to make a valid block. Guess what: it is a perfect soft-fork. The old SHA-256 code is left unchanged, but at the same time, if SHA-3 of your block does not meet the new target, the block is rejected anyway.

Also, that concept is compatible with re-hashing the chain. The initial difficulty for SHA-3 could be regtest-like, for example "accept anything, if we are below block 1,234,567, and apply new difficulty adjustments after that". Another thing is that the transition can be gradual, and can reuse the same space, if needed. For example: the new nonce for SHA-3 could be placed in the same field, where you can now see leading zero bytes for SHA-256. Then, they could be masked for old nodes, and shared in a new, combined form, for the new ones. And leading zeroes from SHA-3 could also be used in the future, to upgrade into SHA-4 in the same way.

Somewhat related topic, about applying Proof of Work outside block headers, if needed, for example for signet: https://delvingbitcoin.org/t/proof-of-work-based-signet-faucet/937

Off-topic question, but it may be relevant.

If Bitcoin was "under attack" by state-level actors who by a sort of miracle have gotten control of 51% hashing power of the network, would it be possible for the network to fork away from those specific miners without changing the mining algorithm?

But if changing the mining algorithm is absolutely necessary, what do you believe would Bitcoin's probability of survival be in theory under the new mining algorithm?

Same question I would have asked the OP. The reason why I have chosen not to pay too much attention to this aspect of attack is simply because there haven't been any potential cases. Many people keep suggesting that it's possible but there isn't much evidence to back it up. Here is my recent research on both SHA-3 and SHA-256. When we observe the vulnerabilities, there haven't been any so far as the article says. Am not even sure if most Bitcoin developers are thinking of this potential risk, but Incase the OP can share possible attack scenario with us, then I might start paying attention to that area.





https://www.geeksforgeeks.org/sha-256-and-sha-3/

What exactly would be the attack scenario of quantum computing on Bitcoin's PoW scheme?

All hash functions are vulnerable to quantum attack by Grover's algorithm, which provides a quadratic speedup for inverting the output of the hash function.

BLAKE3, like BLAKE2, is a general purpose cryptographic hash, and all of these are just
as vulnerable to quantum attack as SHA256.

Irrelevant in a hash function discussion.

Argon2 is not a general purpose cryptographic hash. It's purposely slow and meant for hashing passwords. It's not suitable as a replacement for SHA256 in bitcoin.

Bitcoin continued to use the SHA-256 (Secure Hash Algorithm 256) consensus algorithm that would exposed to potential quantum computer attacks. Because as the security of classical cryptographic algorithms is eroded by advances in quantum computing, Bitcoin will need to contemplate a series of upgrades to the consensus algorithm to remain secure over the long term.

Quantum-Resistant Algorithms:
Some of the quantum-resilient algorithms that are being considered include:
1. SHA-3 (Keccak): A type of hash function said to be resistant to quantum attacks.
2. BLAKE3: A fast cryptographic hash; it is not a general purpose cryptographic hash so you may not want to use as your only hash function.
3. SPHINCS: A Post-Quantum Secure Hash-Based Signature Scheme
4. Argon2 - Quantum-safe  Memory-hard Function

Some challenges that may be faced:
1. Backward Compatibility: New algorithm must be compatible with existing infrastructure as well as wallets.
2. Mining Hardware: Upgrading mining equipment to support new algorithms.
3. Network Effects: Manage the transition impact on network difficulty and hash rate.
4. Security Trade-Offs: Balancing security gains with potential performance and efficiency losses.

Potential Benefits:
1. Security Boost: Shielding from future quantum computer attacks.
2. Future-Proofing: Preparing Bitcoin for long-term security and sustainability.
3. Increased Confidence: Improving Bitcoin's security and robustness to foster greater trust.

Questions:
1. Which quantum-resistant algorithm is best suited for Bitcoin?
2. How do we manage the transition to avoid disruption?
3. What are the potential performance and efficiency implications?