Quantum Computers META THREAD Defacto STICKY

[Come-from-Beyond]

No, not yet another topic on quantum computers and bitcoin... A sticky should be placed at the newbie section covering this topic with its popularity.

Search on this forum sux. That why u see so many duplicate topics.

[1713503007]

1713503007

[1713503007]

1713503007

[1713503007]

1713503007

[1713503007]

1713503007

[1713503007]

1713503007

[1713503007]

1713503007

[jubalix]

No, not yet another topic on quantum computers and bitcoin... A sticky should be placed at the newbie section covering this topic with its popularity.

Sticky this one

[Etlase2]

This thread has some very detailed discussion that would be a bit more useful as a sticky, imo.

[jubalix]

This thread has some very detailed discussion that would be a bit more useful as a sticky, imo.

looks fine but needs a bundle of links at the top

[Come-from-Beyond]

Don't forget this thread - Why is Bitcoin safe against a quantum computer? (https://bitcointalk.org/index.php?topic=153302.0)

PS: Btw, seems Bitcoin is NOT safe.

[wumpus]

For a moment I thought this was going to be another speculative pre-order thread 

[jubalix]

For a moment I thought this was going to be another speculative pre-order thread 

haha.

quantumfly labs...first qubit comupter......pay now 1024 qbit device by November....

pay 100 BTC to sig address pm me

[gmaxwell]

This thread is borderline off-topic for this sub-forum. Or rather, I think it's off-topic but there isn't a subforum that it would be more on-topic in.

It also begins with a misrepresentation of the expected performance of quantum computers: They are not even theorized to provide an exponential speedup in the general case. (If it did lamport wouldn't be strong against QC either)

There is no way in hell that I'm going to sticky it.

[qualalol]

I thought that if 51%  of miner adopted a client change eg 50 millcoins that would then happen

No, the 51% attack is to reverse transactions.

If I send a coin to you and then later send it to someone else.  Who owns the coin?  Encryption can't tell you, you need to know which transaction happened first.

That is what the hashing is for, it locks in transaction ordering.

Nobody can spend your coins but you, unless they break the encryption.  It doesn't matter how much hashing power someone has.

However, with 51% of the hashing power, they can "rewind" the clock so the coin never belonged to you in the first place.

He's not talking about a 51% attack. He is talking about 51% of all miners (well actually, 51% of all hashing power, not necessarily proportional to the individual "miner") switching to a new client with different rules in place. If that happens then the main branch (i.e. longest) of the blockchain will be the one following the new rules. This is essentially what is happening with the block size change on 15th May where most miners will switch to a new set of "rules" (in this case not an explicit rule, but an implementation specific implied rule). The rules of bitcoin are decided by whatever the majority (51%) of the miners agree on.

[gglon]

EDIT 1:This is going to happen sooner than later...when it does, that it for Bitcoin/CC. So we need a solution now....though.

Adding qubits is not as trivial as adding bits. It can be 2^N problem (i think), so we may never have enough qubits. There was a lot of experimental breakthroughs lately, but still we are very, very far from the goal of creating scalable quantum computer.

EDIT 2:  So a n qubit QC can solve roughly a 2^N problem..........is kinda mind blowing......if it works....

Roughly, but for n qubits we need another k times n (k may be quite large) for error correction.

EDIT 3: If BTC does this sooner, it will be a massive pro of BTC uptake, as we would be the first an currently only banking system that is QC ready.

Some Swiss banks have already established quantum key distribution as 2 years test by SwissQuantum ended in 2011 was a success: http://en.wikipedia.org/wiki/Quantum_key_distribution#Quantum_Key_Distribution_Networks, so maybe it's not that stupid to think about quantum computers that early. But I think that right now there are many much more important things to do.

Public-key schemes based on Multivariate Quadratic polynomials where claimed to resist quantum computer attacks: http://eprint.iacr.org/2008/349.pdf

[jubalix]

This thread is borderline off-topic for this sub-forum. Or rather, I think it's off-topic but there isn't a subforum that it would be more on-topic in.

It also begins with a misrepresentation of the expected performance of quantum computers: They are not even theorized to provide an exponential speedup in the general case. (If it did lamport wouldn't be strong against QC either)

There is no way in hell that I'm going to sticky it.

Your call it will just go on anyway!!!!

However, the first youtube link by the Australian Usyd research team (and they have actually made a working 1qbit device) gives a fairly solid view,  as to the expected performance which appears to be a doubleing for every qubit added. So there's that...not sure your claim "its not even thoerized" holds water as clearly that Prof Usyd team are theorizing and a whole lot and more by actually making a qbit chip

In this thread alone there appears to be at least 2 Physics PHD's who are in the filed who give similar views.

But hey its cutting edge tech and will be open to a lot of different views, but it needs to be addressed.

This thread is borderline off-topic for this sub-forum. Or rather, I think it's off-topic but there isn't a subforum that it would be more on-topic in.

your kinda right on this point in both counts, and this was my initial view as well when I posted, I wrote i wasn't sure this belongs in this sub forum....but it is an issue, and it keeps raising its head....some one else suggested newbs.....I think that this is probably as close as it gets...

(If it did lamport wouldn't be strong against QC either)

well I will cross that out!

[kjj]

Meh.  The world record for quantum computing is 21.  Not 21 qubits, but 21=3*7 at least a few percent of the time.  This was after roughly a decade of work since the previous record of 15=3*5.  But, to be fair, a good chunk of that decade was in making the initial 15=3*5 result actually be a quantum effect.

Then there is the tricky part about building quantum circuits.  Turns out that those get harder the bigger you make them, while classical circuits only get harder at changes of scale.  As in, when we shrink a transistor, we can suddenly put billions of them on a die, instead of millions.  But adding qubits isn't simply a matter of finding physical room for them, they interact, so the difficulty multiplies for each one added.

I suspect that we have at least a couple of decades, minimum, before quantum attacks on ECDSA become a serious threat.  And even if they do, good key hygiene (for example, what the stock client has been doing since day 1) will make the attacks pointless.

[gmaxwell]

(If it did lamport wouldn't be strong against QC either)

well I will cross that out!

**facepalm**

Lamport is fine.

Quantum computation does not give an exponential speedup in the general case. It can not solve arbitrary  problems that take 2^N time on a classical computer.  For general non-linear search (which is _most things_) quantum computation is theorized to give at least and at most a sqrt() speedup,  in other words something that takes 2^N operations on a classical computer takes 2^(N/2) operations on a sufficiently large quantum computer.   This means that e.g. for a hash or block cipher you can double the number of bits and get back to where you started in terms of operation count.

There are some problems like factoring and the related discrete-log problem which can be expressed in a way which has a special periodic structure which has much greater speedup, but this is not usual.  It's why it's believed that RSA and ECDSA will not be strong against large QC's.

All this is predicated on "sufficiently large" QC's which may actually turn out to be physically impossible to construct, e.g. the noise level or coherence time my degraded exponentially in the number of qbits based on some yet undiscovered issues... so who knows.

Fortunately the way Bitcoin is constructed we are already somewhat hardened against quantum computers: When you use Bitcoin correctly and only use each address once the public key is only known for the brief window between announcement and mining, limiting the time under which a ECDSA attack could happen. The script system is flexible and we could introduce quantum-computer secure signatures at any point in time in a backwards compatible way, and start running them in-parallel with ECDSA signatures.

Unfortunately, while I'm a great fan of lamport the signatures are between 16KiB and 65KiB (for 128 and 256 bits of QC security, respectively).  Basically a 150 fold increase in transaction size and bandwidth.  Imagine a blockchain of 1TB instead of 7GB now. While we'd introduce them if QCs started to look like they might become an actual threat in the next decade, they just aren't viable absent that kind of threat.

[jubalix]

um ok so your arguing against.... yourself here...or I am misreading you....

you said (If it did lamport wouldn't be strong against QC either) then Lamport is fine?

subtle.

good point about the size issue!!!!

(If it did lamport wouldn't be strong against QC either)

well I will cross that out!

**facepalm**

Lamport is fine.

Quantum computation does not give an exponential speedup in the general case. It can not solve arbitrary  problems that take 2^N time on a classical computer.  For general non-linear search (which is _most things_) quantum computation is theorized to give at least and at most a sqrt() speedup,  in other words something that takes 2^N operations on a classical computer takes 2^(N/2) operations on a sufficiently large quantum computer.   This means that e.g. for a hash or block cipher you can double the number of bits and get back to where you started in terms of operation count.

There are some problems like factoring and the related discrete-log problem which can be expressed in a way which has a special periodic structure which has much greater speedup, but this is not usual.  It's why it's believed that RSA and ECDSA will not be strong against large QC's.

All this is predicated on "sufficiently large" QC's which may actually turn out to be physically impossible to construct, e.g. the noise level or coherence time my degraded exponentially in the number of qbits based on some yet undiscovered issues... so who knows.

Fortunately the way Bitcoin is constructed we are already somewhat hardened against quantum computers: When you use Bitcoin correctly and only use each address once the public key is only known for the brief window between announcement and mining, limiting the time under which a ECDSA attack could happen. The script system is flexible and we could introduce quantum-computer secure signatures at any point in time in a backwards compatible way, and start running them in-parallel with ECDSA signatures.

Unfortunately, while I'm a great fan of lamport the signatures are between 16KiB and 65KiB (for 128 and 256 bits of QC security, respectively).  Basically a 150 fold increase in transaction size and bandwidth.  Imagine a blockchain of 1TB instead of 7GB now. While we'd introduce them if QCs started to look like they might become an actual threat in the next decade, they just aren't viable absent that kind of threat.

[Etlase2]

um ok so your arguing against.... yourself here...or I am misreading you....

you said (If it did lamport wouldn't be strong against QC either) then Lamport is fine?

subtle.

Lamport signatures are known for being QC-resistant, but they are also one-time use. There is a way to combine them with a merkle tree to get more uses out of them, but it increases both the public key size and the signature size, I believe--but perhaps just one or the other, I don't remember. NTRUsign is a QC-resistant DSA that is far more data friendly than any other, but it also has a very limited lifespan in the number of times a public key can be used to sign something before the private key can be discovered. Not as big of an issue for bitcoin, but keys and signatures are still quite a bit larger than ECDSA.

[wumpus]

There is no way in hell that I'm going to sticky it.

Agreed. I think an article on the Wiki would be more appropriate than a sticky. It's not like quantum computers are an urgent must-read topic for the development forum.

On the other hand as (some form of) QCs are more realistic than the average sci-fi threat, we do get a lot of questions about them, some writing from an expert that'd reassure people that they're 1) not really an issue or 2) we can adopt when they come, would be nice to refer them to.

For a moment I thought this was going to be another speculative pre-order thread  

quantumfly labs...first qubit comupter......pay now 1024 qbit device by November....

pay 100 BTC to sig address pm me

Hehe, exactly. November, 20000 AD.

[Come-from-Beyond]

good point about the size issue!!!!

There are some other hash-based signature schemes with much lower key sizes. For example, Qubic uses 64 bytes only for 2-step signing. There is a gap in time between each step though.

[Peter Todd]

All this is predicated on "sufficiently large" QC's which may actually turn out to be physically impossible to construct, e.g. the noise level or coherence time my degraded exponentially in the number of qbits based on some yet undiscovered issues... so who knows.

FWIW the experience of people working in the lab building QC prototypes has been that the engineering effort required to get them to actually work increases exponentially as the number of qbits goes up. Of course the most qbits used in a calculation is currently just six IIRC, so that trend doesn't have very much data backing it.

[jubalix]

All this is predicated on "sufficiently large" QC's which may actually turn out to be physically impossible to construct, e.g. the noise level or coherence time my degraded exponentially in the number of qbits based on some yet undiscovered issues... so who knows.

FWIW the experience of people working in the lab building QC prototypes has been that the engineering effort required to get them to actually work increases exponentially as the number of qbits goes up. Of course the most qbits used in a calculation is currently just six IIRC, so that trend doesn't have very much data backing it.

A bit out there suggestion....but I wonder if in someway, QC can be leveraged in a way to reveal new ways to build QC, I.E some sort of algorithm that reveals or solves a problem to build on the next Qbit....again I know this is quite an out there suggestion, given its largely a material/science nano tech exercise with FM' and STM domain...

Another interesting to note that biological systems have no trouble making complex 3D nano pick and place systems....I intuitively feel the solution to this problem will be in understanding how biological systems pick and place atoms at 36C!

then of course cool to run.....

[TierNolan]

If quantum computers was capable of breaking ECC but not breaking RIPEMD-160, then people would still not be able to spend old coins that they don't own using the standard address system.

However, to spend the coin, the owner inherently has to publish their public key in the spend transaction.  This gives a window where someone else can break the ECC and send the coin to themselves.

Maybe it would be worth having some system where you publish a hash of the signature first and then once that is incorporated into the chain, then you publish the public key.  This would require an opcode that you can ask to find a previous transaction and extract data from it.