Post Quantum Cryptography

[bitcoincashautist]

@TierNolan

That’s great. I assume tvl is total value?

Yes

@TierNolan

So, most of the coins would be potentially protected against quantum computers. The exceptions would be for ones that have key re-use.

Yes, and if keys are exposed it likely means the keys are not lost. So, if need be, they could be moved to non-exposed P2PKH.

I’ll see if I can extract the exposed vs non-exposed info, too.

@TierNolan

Even normal P2SH (160) would be moderately protected at 80-bit security. They would have lower than 128-bit security, but would be effort to break them one at a time.

More than “moderately”. I was wondering about post-quantum preimage resistance of HASH160 addresses (both P2PKH and P2SH), too. Turns out, it would be physically possible but still infeasible to crack even 1 address:

We could design a black box function to break both P2PKH and P2SH (and P2WSH, etc.) addresses in 2^80 single-threaded quantum computer cycles.
Assuming a clock speed on scale of GHz, this would take about 10 million years.
Important to note is that splitting the work and doing it in parallel is not as beneficial as with classic computers because it would offer only a quadratic speedup (Fluhrer, S., Reassessing Grover’s Algorithm).
In other words, doing the work in 1 year would require building 100 trillion quantum computers because sqrt(100T) == 10M.
Therefore, we can say that breaking a 160-bit hash preimage is physically possible because 10M years is a finite amount of time and less than age of the universe.
However, it is still infeasible.

.

@TierNolan

The only ones that are definately exposed would be the P2PK. They are likely mostly old and maybe private keys are lost.

Some old keys have been recently observed moving on BTC, but still, Satoshi’s P2PK stash didn’t move, and it is still the biggest quantum-computing bounty in the world.

[TierNolan]

@bitcoincashautist

Some old keys have been recently observed moving on BTC, but still, Satoshi’s P2PK stash didn’t move, and it is still the biggest quantum-computing bounty in the world.

Yeah. There isn’t much that can be really done about it.

Anyone who knows what their keys would likely have time before the break is possible.

Once/If quantum computers can trivially break the outputs, it would be impossible to distinguish the original owner from someone with a QC. It isn’t clear why anyone should get those outputs.

Before that it would be worth looking into having a system to handle hash protected outputs.

It would probably be some kind of on-chain two stage release system. Submit the digest of the insecure public key and one that works with a new algorithm. Once it is buried, the new public key can be used to spend the funds.

[bitcoincashautist]

@TierNolan

It would probably be some kind of on-chain two stage release system. Submit the digest of the insecure public key and one that works with a new algorithm. Once it is buried, the new public key can be used to spend the funds.

Sounds like a commit-delay-reveal scheme, I first saw it described here: Stewart, I., et. al. (2018). “Committing to quantum resistance: A slow defence for Bitcoin against a fast quantum computing attack”

On BCH, we can implement that as a smart-contract, here’s the proof-of-concept: Quantum-resistant One-time-use Lock

[TierNolan]

@bitcoincashautist

On BCH, we can implement that as a smart-contract, here’s the proof-of-concept: Quantum-resistant One-time-use Lock

I assume that requires moving all P2SH outputs to new outputs (with the smart contract) manually first to protect them?

In that case, they could just be moved to quantum resistant outputs.

If a quantum computer was suddenly able to break the elliptic curve signature algorithm, then there would need to be a soft fork to force all P2SH outputs to additionally require a commit transaction.

After the soft fork, you have to send the commit first because P2SH outputs would require the normal signature and a reference to a commit transaction.

Edit:
Also, it would be a good idea if it could handle pre-signed transactions. If someone had a valid transaction in a safe, then the client would take that transaction and produce a valid commit transaction for sending.

[BitcoinCashPodcast]

Really good talk from the BTC guys at OP_NEXT. I’ll need to watch this again, but for me the key points really were that the government is looking to be quantum secure 2030 - 2033, and somewhere in the range of 2026 to 2030 is probably ideal for Bitcoin.

This means if we’ve already locked in 2025 that we do need to get this onto the radar so that we can ship BCH quantum resistance changes 2026 - 2028 sometime.

It’s also a point of community discussion as to the economic effect. For instance, is there a case to hard fork in a “burn” of all Satoshi + other vulnerable coins after an announced window to move to quantum secure? Or do we let a huge amount of value in the UTXO set get grabbed by quantum computers?

The 2025 VM Limits upgrade may also help us out significantly I guess in terms of opening the ability for more cryptographic defenses.

See this graph of how you need to prep & migrate coins (with some margin for error) BEFORE the attack becomes viable obviously.

Government timeline:

Quantum Proofing Bitcoin With Hunter Beast - Blockspace Media

[bitcoincashautist]

@TierNolan

I assume that requires moving all P2SH outputs to new outputs (with the smart contract) manually first to protect them?

The PoC smart contract is only good for someone who’d want to preemtively move his funds to a quantum-resistant address. Once QCs become available, you’d want a fork to enable safely migrating funds from any stranded and vulnerable contracts (including any non-standard variations of P2PKH, P2PKH, P2SH) where a commit-delay-reveal could work to prove original ownership.

Caveat with commit-delay-reveal is that miners could collude to steal, making a 51% potentially more damaging (right now, 51% could only censor transactions, or execute a double-spend fraud, but not out-right steal someone else’s funds) but once signatures are broken there’s no way around it but to use your P2PKH / P2SH address as an aged hashlock. With a long enough aging requirement, I think this would not be a deal-breaker.

@TierNolan

If a quantum computer was suddenly able to break the elliptic curve signature algorithm, then there would need to be a soft fork to force all P2SH outputs to additionally require a commit transaction.

I don’t consider P2SH or P2PKH preimage to be breakable, so consideration here is just vulnerability of redeem scripts, where they’d become vulnerable only after exposing a vulnerable redeem script, same how P2PKH becomes vulnerable only after exposing the committed key.

With P2SH, it is more complex, because some contracts may already be quantum-resistant (signatureless covenants etc.), and only some would be vulnerable to QCs. Having a SF to require a commit for all of P2SH could inconvenience non-vulnerable contracts or could even break them (if contract requires a particular number of inputs & outputs and commitment would be provided by an additional input or output).

Therefore, I think a complete solution would be to extend the TX format so that this commit-delay-reveal happens “outside” the legacy TX, so that it doesn’t interfere with functioning of existing contracts and it would only be required for any script that executes OP_CHECKSIG, CHECKDATASIG, or CHECKMULTISIG with elliptic curve keys.

[BitcoinCashPodcast]

BTC Core has a speculative PR for Quantum resistant addresses as a soft fork: QuBit - P2QRH spending rules by cryptoquick · Pull Request #1670 · bitcoin/bips · GitHub

[bitcoincashautist]

Of course it’s overengineered, yet another level of segregating the witness.
But anyway, nice doc, here’s the link to view the doc: https://github.com/bitcoin/bips/blob/e186b52cff5344c789bc5996de86697e62244323/bip-p2qrh.mediawiki

[kanat]

We are in big trouble if true?
https://x.com/0xRacist/status/1866952585644576835

[bitcoincashautist]

smells like FUD, and conveniently there’s a bunch of new coins claiming quantum resistance

[_minisatoshi]

Check the community note. This is an industry/insider joke.

[tom]

Look guys, you need to not just follow what some companies or governments say.

Companies and universaties have had this quantum computing “dream” for more than a century and billions have gone into actual research for 40 years. The results are basically that we see papers and results published at a rate that is really only about getting more funding.

Governments are a really big part of getting funding nowadays, they are afterall experts in spending other people’s money.

And in the meantime we see no real progress. And the next billions burned in research and building something to make it look good.

There is basically zero risk to old funds stored in p2pkh transactions, even if some quantum crypto is available tomorrow with actually a useful amount of bits. So stop worrying and wasting money on protecting against something that literally doesn’t exist.

[_minisatoshi]

You have some reading up to do. It is evolving, it is not just for more research dollars. There is and will be a market. Things take time.
Google’s latest QC breakthrough

[_minisatoshi]

This is not to say it is close to being a threat, on that I would agree, but it also does not mean we should ignore it or assume:

@tom

There is basically zero risk

[tom]

@_minisatoshi

or assume

That is not an assumption. A ripe160 hashed pubkey on chain is safe from quantum computers for quite some time yet.

(also, as ps. Please be more careful about quoting actual statements, not one that looks like one but isn’t)

[tom]

@_minisatoshi

You have some reading up to do

Interesting, this is your response to my stating it is all about getting more funding. You might make the connection yourself, how google is indeed getting work from nasa based on this, how the Department of Energy is stating it will buy contracts based on this. (that took me 5 minutes of research, follow the money is not that hard!)

So, do your research and again: you need to not just follow what some companies or governments say.

[BitcoinCashPodcast]

Welcome to BCH Research! Good to see you!

[BitcoinCashPodcast]

I love how terrified they are of a blocksize increase, author specifically mentions it several times (emphasis mine).

This approach for adding a post-quantum secure output type does not require a hard fork or block size increase.

Also pretty funny they have to split things up even further with a new type of address as they’re trying to avoid even more Inscriptions & SegWit disaster. Tech debt always stacking up for them.

But otherwise yeah a pretty good summary and worth us keeping an eye on.

[BitcoinCashPodcast]

Good thread to keep an eye on with regards to Quantum Discussion from the BTC guys: https://groups.google.com/g/bitcoindev/c/Aee8xKuIC2s/m/cu6xej1mBQAJ

[TierNolan]

@bitcoincashautist

I don’t consider P2SH or P2PKH preimage to be breakable, so consideration here is just vulnerability of redeem scripts, where they’d become vulnerable only after exposing a vulnerable redeem script, same how P2PKH becomes vulnerable only after exposing the committed key.

It would depend on how fast the QCs are.

You could spend P2SH / P2PKH outputs safely if the time to break them was much longer than the block time and there was at least 1 honest miner. By the time an attacker could find the private key, your transaction would be buried in the blockchain.

There are effectively 3 cases

A) QC can’t break ECC: current situation
B) QC can break ECC slowly (it takes days, or more, to find the private key)
C) QC can break ECC quickly (it takes < 1 minute to find the private key)

We would probably move through B for a while before we hit C. A massive breakthough might move things from A to C suddenly though.

If the first seen rule is enforced widely, then that helps even in case C. An attacker would have to break your key and then get a new transaction broadcast before your transaction got to any of the miners.

I take your point that some P2SH outputs might already be quantum safe. It would be sufficient if there was a way to “lock” outputs before releasing the key.

For example, with P2SH, you could release the RIPEMD preimage without releasing the actual script.

You could publish

<SHA256(old_script), SHA256(nonce, old_script, new_script>>

in a commit transaction.

This can be checked by computing RIPEMD160<SHA256<old_script>>. This proves that the owner of the output wants it locked.

An attacker could publish alternative versions of the commit script, but none of them would be valid since they wouldn’t know old_script.

Once it is buried deeply enough, then the owner can publish nonce, old_script, new_script and spend their coins.

There is still a potential timing issue when the actual publication occurs. A dishonest miner (cartel) could try to block publication of the spending transaction while submitting an “updated” lock/commit transaction.