Bitcoin’s race to outrun the quantum computer • Hacker News Board

Re: Bitcoin’s race to outrun the quantum computer

#31

Post by esotericn » Sun, Aug 18, 2019, 6:04 PM UTC

lixtra wrote: post #5

> Take the Bitcoin blockchain: an unencrypted public key is sent along with every bitcoin transaction, and left unencrypted during the time it takes for the network to confirm the block, around ten minutes. My understanding is that it remains unencrypted forever. That’s why it is a public key. As long as the coins are not moved to another account that public key stays a valuable target. Edit: As DennisP pointed out m…

Nitpick: What people like to call "Satoshi's coins" were actually mined in transactions to pubkeys rather than to pubkey hashes.

Early Bitcoin transactions did not use addresses.

Example from block 1:

https://www.blockchain.com/btc/tx/0e3e2357e806b6cdb1f70b54c3....

You'll see at the bottom that the opcode is a PUSH / CHECKSIG rather than the later DUP / HASH160 / PUSH / EQUALVERIFY / CHECKSIG format.

So this isn't true. (blockchain.info derives an address but actually the pubkeys are right there in plain sight. Have at it!)

Most transactions are indeed made to pubkey hashes though, yes.

Re: Bitcoin’s race to outrun the quantum computer

#32

Post by DennisP » Sun, Aug 18, 2019, 6:05 PM UTC

esotericn wrote: post #28

DennisP wrote: post #11

Earlier quoted context omitted.

Not if Satoshi's coins have never moved. A bitcoin address is a hash of a public key. The public key isn't revealed until the first time funds are transferred out of that address.

Nitpick: What you're calling "Satoshi's coins" were actually mined in transactions to pubkeys rather than to pubkey hashes. Early Bitcoin transactions did not use addresses. Example from block 1: https://www.blockchain.com/btc/tx/0e3e2357e806b6cdb1f70b54c3... You'll see at the bottom that the opcode is a PUSH / CHECKSIG rather than the later DUP / HASH160 / PUSH / EQUALVERIFY / CHECKSIG format. So this isn't true. (b…

Thanks, I had no idea!

Re: Bitcoin’s race to outrun the quantum computer

#33

Post by anaolykarpov » Sun, Aug 18, 2019, 6:05 PM UTC

jchanimal wrote: post #8

Finally a good use-case for bitcoin: a bounty for the first quantum computer to crack it.

That bounty is currently at 185 billion USD. Of course, it would be pretty difficult to sell all the bitcoins without slippage, but I guess one could cash in at least several tens of millions.

Re: Bitcoin’s race to outrun the quantum computer

#34

Post by kokx » Sun, Aug 18, 2019, 6:06 PM UTC

ridewinter wrote: post #16

krastanov wrote: post #4

Just to be clear, this has barely anything to do with any crypto-currency organization. It is a really regrettable framing for an event that should be of great interest to anyone dealing with cryptography, not just the fairly restricted group of crypto-currentcy enthusiasts. If scalable quantum computers can be built (which seems probable, as we are progressing fast in the number of qubits we can keep together), then…

The only truly safe encryption is quantum encryption. Any classical encryption algorithm should be breakable with quantum computers, even if we haven’t figured it out yet like with Shor’s.

What do you mean with quantum encryption? QKD (Quantum Key Distribution)?

Though the concept seems nice, it has quite a few issues in practice. Such as distance between coupled devices, and the need to have a dedicated physical communication line.

Oh and before you think you can just chain several devices to get longer distances: this opens you up to classical MitM attacks.

Source: https://www.nature.com/articles/npjqi201625

Re: Bitcoin’s race to outrun the quantum computer

#35

Post by gruez » Sun, Aug 18, 2019, 6:12 PM UTC

xiphias2 wrote: post #25

ddtaylor wrote: post #9

It's worth mentioning that Bitcoin addresses aren't exposed on the blockchain as public keys, but hashes of the public keys. If you want to steal the coins you'll need to turn ripemd160(sha256(sha256(publicKey))) into a private key. Good luck.

It's impossible to use a hardware wallet without exposing the master public key to an untrusted device (not hardware wallet). The only solution would be to run a Bitcoin node on the hardware wallet itself, which is not possible right now. So you have to treat the public key as a public key.

That would involve your computer being already compromised. If that's the case AND you have enough bitcoins to warrant running a quantum computer worthwhile, you're not securing your coins properly.

Re: Bitcoin’s race to outrun the quantum computer

#36

Post by zrm » Sun, Aug 18, 2019, 6:15 PM UTC

zazagura wrote: post #18

ridewinter wrote: post #16

Earlier quoted context omitted.

The only truly safe encryption is quantum encryption. Any classical encryption algorithm should be breakable with quantum computers, even if we haven’t figured it out yet like with Shor’s.

Citation needed? Symmetric encryption algorithms like AES (with at least 256 bit key) are considered safe even against quantum computers, based on some reasonable math/qm assumptions.

Not only that, there are asymmetric encryption algorithms not vulnerable to Shor's algorithm, we're just not using them yet (because they're slower and haven't been as well-studied as RSA or ECC).

Re: Bitcoin’s race to outrun the quantum computer

#37

Post by gruez » Sun, Aug 18, 2019, 6:16 PM UTC

DennisP wrote: post #12

ddtaylor wrote: post #9

It's worth mentioning that Bitcoin addresses aren't exposed on the blockchain as public keys, but hashes of the public keys. If you want to steal the coins you'll need to turn ripemd160(sha256(sha256(publicKey))) into a private key. Good luck.

Yes, but the public key is exposed when you send from that address. If a quantum computer is quick enough, it could get your private key and issue its own transaction, racing you to get into a block.

Cracking a public key in 10 minutes is much harder than cracking a public key (at all). Considering we haven't cracked anything yet, I wouldn't be worried about that. Also, if you're transferring thousands of bitcoin and want to be safe, you could always privately send it to a miner rather than broadcasting it. In that case the tx would have 1 confirmation before the the public knows about it, requiring them to also pull off a 50% attack.

Re: Bitcoin’s race to outrun the quantum computer

#38

Post by charleslmunger » Sun, Aug 18, 2019, 6:16 PM UTC

zazagura wrote: post #18

ridewinter wrote: post #16

Earlier quoted context omitted.

The only truly safe encryption is quantum encryption. Any classical encryption algorithm should be breakable with quantum computers, even if we haven’t figured it out yet like with Shor’s.

Citation needed? Symmetric encryption algorithms like AES (with at least 256 bit key) are considered safe even against quantum computers, based on some reasonable math/qm assumptions.

Yeah, so far as I know the only algorithm that provides an asymptomatic speedup (for AES or similar symmetric key crypto) over a classical computer is Grover's algorithm. That would reduce a 256 bit key to 128, which is hardly disastrous.

Re: Bitcoin’s race to outrun the quantum computer

#39

Post by krastanov » Sun, Aug 18, 2019, 6:18 PM UTC

tialaramex wrote: post #19

krastanov wrote: post #4

Just to be clear, this has barely anything to do with any crypto-currency organization. It is a really regrettable framing for an event that should be of great interest to anyone dealing with cryptography, not just the fairly restricted group of crypto-currentcy enthusiasts. If scalable quantum computers can be built (which seems probable, as we are progressing fast in the number of qubits we can keep together), then…

> which seems probable, as we are progressing fast in the number of qubits we can keep together Are we? Every so often I check back to see how well they're doing with actually running Shor's algorithm. In 2012 they managed to find that 21 = 3 x 7. And today... 21 = 3 x 7. That doesn't sound like progressing fast. Quantum annealing is doing well for itself, but it isn't any sort of threat to encryption.

We definitely are getting closer. Look at any graph of "qubit lifetime" and you will see how we have orders of magnitude improvements. (a quick google search gives me page 9 of https://hpcuserforum.com/presentations/tuscon2018/QCOverview...). We still need a couple more orders of magnitude before the qubits are useful, but the signs of exponential progress are unmistakable.

I would not take any experiment performing Shor's algorithm today or in the past particularly seriously, since they would probably be showing something fine tuned for the particular instance of the problem (e.g. 21). We do not have anything that can be called an "error-corrected logical qubit", and we need this before we can make serious claims about running algorithms like Shor's.

Re: Bitcoin’s race to outrun the quantum computer

#40

Post by gruez » Sun, Aug 18, 2019, 6:22 PM UTC

zazagura wrote: post #30

rolltiide wrote: post #24

Earlier quoted context omitted.

Its not much harder for bitcoin... The community will just do a blockchain snapshot of balances at an agreed upon block and start a new distributed ledger with quantum resistant encryption Snapshots have been done hundreds of times

Everybody will need new private keys. What do you do with old coins? Satoshi's one for example? Or lost coins that nobody has the key for? Do you set a threshold day, after which all unclaimed coins are just marked destroyed forever? If not, how do you know someone claiming some coins didn't use a quantum computer to get the key?

>Do you set a threshold day

yeah pretty much.

>What do you do with old coins? Satoshi's one for example? Or lost coins that nobody has the key for?

If those coins hasn't been touched for decades, despite widespread announcements of pre-quantum cryptography (presumably it wouldn't happen overnight), it's safe to say that nobody is going to claim them.