Topic: A valid criticism of Bitcoin's design? (Read 2576 times)

D-Wave produces an adiabatic quantum computer with a lot of limitations (high noise and error rate). It can only solve particular problems that are solvable by quantum annealing with very high error rates, such as protein folding. Running Shor's/Grover's algorithms with that amount of decoherence would produce nothing meaningful. And I'm not even sure you could construct Shor's algorithm in such a way that it runs in a D-Wave computer because their implementation is very specific and not general purpose.

TL;DR decoherence fucks you up

And as others have said, classic cryptographic algorithms that are impervious to quantum computers do exist. It is the general consensus that quantum computers will never be able to solve NP-hard problems. If a quantum cpu is close to factoring large numbers everyone will see it coming, and new algos will be implemented pretty much everywhere, not only for Bitcoin.

You would be correct. I'm pretty sure D-Wave's computers couldn't break ECDSA. Also, there is a debate (more like a universally-empathetic rejection) as to whether or not he's built an actual quantum computer. My opinion is that he's got a really complex analog computer, but it is not a Turing state machine using qubits. 

http://www.wired.com/wiredenterprise/2012/02/dwave-quantum-cloud/

I'm glad he's doing research in this field, but I'm a bit peeved (as is everyone in his field, it would seem) that he's marketing it as quantum computing.

Sure, they are the canaries in the coalmine. 

I wonder if he would consider using HTTPS.

Except for unspent block rewards from early on in Bitcoin's life, which were all pay-to-pubkey and therefore not safe. There's actually quite a few of those from what I recall.

You are correct.  The lame thing is I actually know that.  https://bitcointalksearch.org/topic/m.651428

tl;dr: ECDSA will break terribly, but we can use another pubkey algorithm if necessary, and all addresses with no spent coins should be safe since they're also protected by the hashes.

Thanks for the elaborate rebuttal. I have to say, if I'm going to be wrong this is a very nice way to be wrong. I have to admit I wasn't thinking about blockchain size and I'm not familiar with Lamport.


Right D-Wave has some quantum products and some computing products, but the quantum component is not a computer. It's more of a quantum sorting machine than a quantum computing machine. It's great for protein folding though.

Uh. This is untrue.

First, grover just gives you a sqrt() speedup.  So double the number of bits and you're done against it. It's very important, but not terribly relevant to crypto security.

Lamport signatures are intuitively QC and classically strong, and I have never heard anyone even suggest an attack class that would attack lamport signatures without breaking all other practical signature implementations (because all practical signature algorithms use a hash on the input first).   The down side is that you're looking at 16kb+ signatures, which is why we don't have them in Bitcoin today.  (AFAIK all of the other post QC signature systems have big signatures/keys/ or both... as well as the questionable classical security that you mention).

Which brings up a point that has been missed in this discussion: ECDSA is not fundamental to bitcoin's "design"— e.g. you don't see it mentioned in bitcoin.pdf.  Should ECDSA begin looking like it may be becoming practically insecure, one of the reserved nop instructions could be deployed to activate another signature scheme (Lamport, perhaps, if nothing better comes along) in a way which is backward compatible with existing software.

Moreover, when Bitcoin is used correctly— addresses only used once— the fact that we send coins to the hash of a pubkey and only disclose the pubkey on spending constitutes a kind of abbreviated Guy Fawkes signature system, so an ECDSA weakness would not be an effective attack unless it could be pulled off in the limited time between announcing a transaction and it becoming buried in the chain.

I can't imagine how the implementation of Bitcoin could be any better relative to this issue when considering the need to balance speculative security against basic viability— as I think the blockchain would already be about 1TB if it used 512bit lamport. Using ECDSA and having a flexible and upgradable script system that will allow upgrading it is really the only prudence decision. The limited pubkey exposure with proper use provides a little more security.

Dwave's products are not quantum _computers_, and there isn't any debate about that— there is some debate over if they use quantum effects at all but even if they do they're to quantum computers what a machine that can only add is to a classical computer. They aren't even claimed to be quantum turing complete, their design doesn't have any obvious path to become quantum turing complete... and right, they can't do crypto because of this.

This company claims it's not just theoretical (but I think those "quantum computers" - if they're real - can't break ECDSA right now): http://www.dwavesys.com/en/products-services.html

UOV looks promising and hasn't been worked around yet, but it is still a bit too soon to trust with anything of value. I'm kind of surprised it hasn't been incorporated into one of the alt-coins yet, but those projects tend to fuss a bit more on "proof of " and reward issues more than securing the system indefinitely.

Try some Unbalanced Oil & Vinegar.

I think it is important to note with this that the quantum resistant algorithms that have been published tend to fall rather quickly to classical cryptanalysis. In a couple decades there will probably be a few quantum resistant public key algorithms that have passed rigorous review, but at the moment there isn't really a more secure alternative to ECDSA. At least not a more secure alternative against Shore and Grover.

etothepi is right. The only risk that occurs from the end user perspective is from address reuse, and we're still going to see this coming, not to mention the whole idea of "secure online purchasing" is going to break down while this occurs. If anything, this will completely invalidate HTTPS which will be a much bigger deal.

Also, keep in mind that QCs aren't really anything but theoretical right now. We could use some combination of symmetric encryption plus ECDSA if needs be.

Wow, this has been a compact college lecture on cryptography and computer science -- I'm glad to see that there are so many brilliant folks in the Bitcoin community.  

Just listen to this discussion and think about what computers could be like in the year 4000... I think even the computers of 2050 will blow our minds... Perhaps someday we'll compute the true state of Schrödinger's cat! lol

Hashing appears to be totally resistant to quantum attacks.  Grover's algorithm can solve any circuit quickly, but circuit has a peculiar meaning, and it is a tricky thing.  We don't have or expect to be able to have the capability in the foreseeable future to build a classical circuit for SHA, much less a quantum one.  If you don't believe that, read up on the SHA algorithm, and then think about what you'd need to do to unroll that in the time dimension to a single flat circuit that doesn't use iteration or memory.  Your VHDL compiler would stab you if it could.

An ECDSA break due to Shor's is likely to be a bigger problem, possibly even within my lifetime (say, the next 50 years or so).  In 2001, a (maybe) quantum computer factored 15 into 3*5.  This feat was achieved again in 2012, but this time with a computer that we are almost positive is actually quantum.  They've moved up to factoring 21 now.

But keeping quantum systems stable gets harder as you add complexity, meaning that the issue isn't merely one of applying well known classical techniques to shrink and replicate gates.  We sorta strongly suspect that quantum computing is possible, in the sense that our current understanding of physics doesn't explicitly disallow it, but it will be a long and ugly road getting up to useful scales.

Quantum computers indeed would break ECDSA, allowing private keys to be derived from public keys in polynomial time.   I suppose a mathematical breakthrough in finite field theory could do the same, but astoundingly unlikely.  But Bitcoin is the least of the world's problems when this happens:  the entire web of trust, SSL/PKI/CA architecture would be broken, rendering useless most internet crypto that we all rely on.  The world will have a lot of problems when QCs start to come into regular existence.  In particular, there will be a gap between when they start to become available to the wealthy, but are not ubiquitous enough to enable widespread quantum encryption to replace it.

But it still wouldn't be that bad.  There are quantum-resistant algorithms that can be run on classical computers.  So it's pretty ridiculous to single out Bitcoin for being susceptible to QCs without mentioning that all sensitive communications on the internet will be susceptible.  And without mentioning that there are alternatives.  

In fact, Bitcoin is wholly prepared to deal with this:

(1) By avoiding address reuse, you're 99% safe even in a world full of quantum computers -- because your address is the hash of your public key, and thus no one knows your public key until you've already submitted a signed transaction to the network.  Even in 50 years when QCs are "fast", they probably won't be fast see your public key, back out your private key, sign your coins to themselves, and then broadcast that tx ... all before your transaction has propagated to a majority of nodes.  Yes yes, isolation attacks... but see #2

(2) The Bitcoin network has the property that you can actually change stuff like crypto algorithms, hashing algorithms, etc, by incrementing a version number and encouraging all nodes to use the new [QC-resistant] algorithms.  Of course, it's not a trivial change, but the network would survive and users would be able to continue using the old encryption for a short time until the transition is made, as long as they never reuse addresses.   Especially large transactions could be submitted directly to miners to avoid isolation issues.

I would say the OP quote is simply under-informed.

P.S. -- Also, these worst case scenarios assume that QCs just pop out of nowhere and suddenly exist on everyone's desktops.  The fact is, we'll see QCs coming decades in advance... so all this "OMG need to swap crypto algorithms immediately!" stuff is overblown.

That was the general thinking, maybe 20 years ago. General cryptography has advanced sufficiently enough in recent years that no computer, ever, will be fast enough to crack them. Let me quote a real expert:

You're thinking of Grover's algorithm. Shor's algorithm does indeed break ECDSA in polynomial time, though we're a very long way off a useful implementation. And note that Bitcoin public keys are 256 bits, not 160 bits - the hash is 160 bits, but this is not broken by Shor's algorithm.

It just cuts the effective key size in half.  The current 160-bit signatures will be brute forced in 2^80 operations.  That sounds weak, but it's going to be a long time before quantum computers reach 160-bit levels (if ever), and even when they do the operations per second will be very low and 2^80 will be infeasible for a long time thereafter.


The OP was talking about ECDSA, though.  There's certainly a chance that a weakness will be found, but there's no expected timeframe for that.  It's not a case where increasing computer power will break it in 5-10 years.

I thought Shor's algorithm will break elliptic curve encryption once quantum computers are sufficiently large?