An improvised model for explaining the seemingly exponential growth is the belief that there is inherent risk of being forgotten as a currency but that this risk falls exponentially with time or price itself.
There no reason why that risk should fall.
Bitcoins has such risks as a mathematician inventing a way to break public key crypto that would completely destroy it. Again if people build useable quantum computers, bitcoin is gone.
For being an digital currency bitcoin has massive amounts of transfer costs. It’s possible that someone creates a better online currency.
Bitcoins has such risks as a mathematician inventing a way to break public key crypto that would completely destroy it. Again if people build useable quantum computers, bitcoin is gone.
This is not completely true—since only hashes of the public key are posted until funds are spent from an address, you need both (a quantum computer or a public key crypto break) and a major break in SHA256. If only one thing breaks, there may be enough time for bitcoin devs to make a fix. It’d be relatively easy to switch to a different address hashing algo, and the whole internet is going to hurt badly if public key crypto can’t be fixed when quantum computers become common, so there’s a lot of motivation to find a replacement.
(It’s hard to imagine a break in SHA256 that’s complete enough to affect mining—weakenings are just the equivilent of running extra hardware.)
(It’s also not completely false, as I still expect events like that to still cause a large temporary depression in bitcoin price.)
Grover’s algorithm cuts hash strength in half. As I understand it, the whole point of 256 bit crypto is to survive the advent of quantum computers, when it degrades to 128 bits. Yes, a quantum computer shouldn’t break SHA256, but quantum computers would almost immediately account for the vast majority of the hashing power, centralizing control of the currency.* Once everyone has quantum computers, it would work again (with a replacement public key system), but given such a disruption, I don’t see much point to salvaging the old currency, rather than starting over.
* I think a gigahertz quantum computer would have the hashing power of the current bitcoin network.
Some relevant numbers: Based on the current target, I estimate that miners compute 5*10^18 hashes per block, 8*10^15 hashes per second. To match that, quantum computers working in mining need to compute 9*10^7 hashes per second.
I think a gigahertz quantum computer would have the hashing power of the current bitcoin network.
My math agrees with you. Looks like I was underestimating the effect of quantum computers.
Difficulty is currently growing at 30-40% per month. That won’t last forever, obviously, but we can expect it to keep going up for a while, at least. (https://blockchain.info/charts/hash-rate) Still, it looks like you’d need an unrealistic amount of ASICs to match the output of just 1000 quantum computers.
Given that, there’ll probably be a large financial incentive to mine bitcoins with the first quantum computers. The incentive goes away if you destroy the network in the process, though. It seems difficult to predict what will happen. Single pools have controlled > 50% of the mining briefly in the past.
...given such a disruption, I don’t see much point to salvaging the old currency, rather than starting over.
A lot of unhappy btc holders may see a point, though. :)
That’s true, but there’s some precedent for picking a block that everyone agrees upon (that exists before quantum computers) and changing the rules at that block to prevent someone from rewriting the blockchain. A lot depends on how much warning we have.
It looks like making a cryptocoin that can survive quantum computers might be a high value activity.
Pubkeys are protected by a dual construction of SHA-256 and RIPEMD-160, resulting in 80 bits of keyspace in a post-quantum world (assuming that existing quantum constructions can be extended into this dual-hash-of-ecdsa-key construction, which is not at all clear).
I always forget about the RIPEMD-160 step. The bitcoin wiki claims that it’s strictly more profitable to mine than to search for collisions, but it seems to me that that’s a function of block reward vs. value of address you’re trying to hack, so I don’t know if I believe that. https://en.bitcoin.it/wiki/Technical_background_of_Bitcoin_addresses
It’s unclear to me how you would actually implement this in a quantum computer; do you have to essentially build a set of quantum gates that implement RIPEMD-160(SHA256(pubkey))? Does this imply you need enough qubits to hold all stages of the calculation in memory at the same time? I haven’t been able to figure out from wikipedia how I’d arrange qubits to do a single hashing operation. Given that it’s a lot of sequential steps, perhaps it actually takes a lot of qubits chained together?
do you have to essentially build a set of quantum gates that implement RIPEMD-160(SHA256(pubkey))?
Actually RIPEMD-160(SHA-256(pubkey(privkey))).
Does this imply you need enough qubits to hold all stages of the calculation in memory at the same time?
That’s a massive understatement. Grover’s algorithm can be used to reverse either RIPEMD-160 or SHA-256 with sqrt speedup. In principle it should also handle RIPEMD-160(SHA-256(x)), just with a lot more qubits. Shor’s algorithm can be used to reverse the pubkey-from-privkey step. I’ll hand-wave and pretend there’s a way to combine the two into a single quantum computation [citation needed].
It’s … a lot of qubits. And you still need 2^80 full iterations of this algorithm, without errors, before you are 50% likely to have found a key. Which must be performed within ~10 minutes unless there is key reuse. So really it’s of zero practical relevance in the pre-singularity foreseeable future.
The bitcoin wiki claims that it’s strictly more profitable to mine than to search for collisions, but it seems to me that that’s a function of block reward vs. value of address you’re trying to hack, so I don’t know if I believe that
Technically you are correct. But in no conceivable & realistic future will it ever be more profitable to search for collisions then mine bitcoins, so for practical purposes the wiki is not wrong.
Thanks for the explanation, it seems like I’m not wildly misreading wikipedia. :)
It seems like the more qubits are required for this attack, the more likely we are to have a long warning time to prepare ourselves. The other attack of just cracking the pubkey when a transaction comes through and trying to beat the transaction, seems vastly more likely to be an actual problem.
Do you have any idea how I’d go about estimating the number of qubits required to implement just the SHA256(SHA256(...)) steps required by mining?
This is not completely true—since only hashes of the public key are posted until funds are spent from an address
So what? Then the attacker waits till someone spents his funds and double spends them and gives the double spending transaction a high processing fee.
the whole internet is going to hurt badly if public key crypto can’t be fixed when quantum computers become common, so there’s a lot of motivation to find a replacement.
Public key crypto is nice but not essential as long as you have central authorities that you trust.
We already have to trust certificate authorties. There no reason why they can’t facilitate key exchange more directly.
There motivation to find a replacement but that doesn’t mean that there’s a replacement to be found.
This is not completely true—since only hashes of the public key are posted until funds are spent from an address
So what? Then the attacker waits till someone spents his funds and double spends them and gives the double spending transaction a high processing fee.
This can be fixed by a protocol addition, which can be implemented as long as there’s warning. (First publish a hash of your transaction. Once that’s been included in a block, publish the transaction. Namecoin already does something like this to prevent that exact attack.)
No, that won’t work. Blocks are rejected if any transaction contained within is invalid (this is required for SPV modes of operation, and so isn’t a requirement that can be dropped). Therefore a miner that works on a block containing transactions he didn’t personally verify can be trivially DoS’d by the competition. They would have a very large incentive not to include your transaction.
I think you misunderstood me—the transaction could still be rejected when you try to get it included in a subsequent block if it’s not valid. The hash of the transaction is just to prove that the transaction is the first spend from the given address; the transaction doesn’t/can’t get checked when the hash is included in the blockchain. Miners wouldn’t be able to do it for free—the protocol addition would be that you pay (from a quantum-safe address) to include a hash of a transaction into the blockchain. You publish the actual transaction some number of blocks later.
It really only makes sense as an emergency “get your coins into an address that’s quantum computer proof” sort of addition. Hopefully the problem is solved and everyone moves their funds before it becomes an emergency.
Suppose you publish hash HT1 of a transaction T1 spending address A, and then several blocks later when you publish T1 itself, someone hacks your pubkey and publishes transaction T2 also spending address A. Miners would hypothetically prefer T1 to T2, because there’s proof that T1 was made earlier.
In the case where someone had even earlier published hash HT0 of transaction T0 also spending address A, but never bothers to publish T0 (perhaps because their steal bot—which was watching for spends from A—crashed), well, they’re out of luck, because A no longer has funds as soon as T1 is included in the blockchain.
The pre-published hashes would be used only to break ties among transactions not yet included in any blocks.
Also, in this hypothetical scenario, the steal-bot from above means you shouldn’t trust funds that haven’t yet been moved into a quantum-computer-safe address; you wouldn’t know who all might have a old hash published with a bot just waiting to spend your funds as soon as you try to move them.
I see. I understand your proposal now at least. The downside is that it requires infinitely increasing storage for validating nodes, although you could get around that by having a hash commitment have a time limit associated with it.
Infinitely is a bit of an overstatement, especially if there’s a fee to store a hash. I agree it might still be prudent to have a time limit, though. Miners can forget the hash once it’s been referenced by a transaction.
The ability to pay to store a hash in the blockchain could be interesting for other reasons, like proving knowledge at a particular point in the past. There’s some hacky ways to do it now that involve sending tiny amounts of BTC to a number of addresses, or I suppose you could also hash your data as if it were a pubkey and send 1e-8 btc to that hash—but that’s destructive.
If you make it part of the validation process, then every validating node needs to keep the full list of seen hashes. Nodes would never be allowed to forget hashes that they haven’t seen make it onto the block chain, meaning that anyone could DoS bitcoin itself by registering endless streams of hashes. Perhaps this isn’t obvious, but note that fully validating nodes do not need to store the entire block chain history, currently, just the set of unspent transaction outputs, and there are proposals to eliminate the need for validators to store even that. If it’s just a gentleman’s agreement then it would be doable but wouldn’t really have any teeth against a motivated attacker.
You certainly don’t want to store data on the block chain by sending bitcoins to fake addresses, sacrificing coins, or other nonsense. That is inefficient and hurts the entire network, not just you. Please don’t do it.
There are already mechanisms to store hashes on the block chain which require no changes to the bitcoin protocol. You simply store the root hash of a Merkle list or prefix tree to the coinbase string, or an RETURN output of any transaction. An output can have zero value assigned to it, and if prefixed by the RETURN scripting opcode, is kept out of the unspent transaction output set entirely. I proposed one such structure for storing arbitrary data here:
Just stick the root hash in a coinbase string or the PUSHDATA of a RETURN output, then provide the path to the transaction containing it and the path through the structure as proof.
Perhaps this isn’t obvious, but note that fully validating nodes do not need to store the entire block chain history, currently, just the set of unspent transaction outputs, and there are proposals to eliminate the need for validators to store even that. If it’s just a gentleman’s agreement then it would be doable but wouldn’t really have any teeth against a motivated attacker.
That’s a good point. To make this work, it’d probably make the most sense to treat the pre-published hash the same as unspent outputs. It can’t be free to make these or you could indeed DoS bitcoin.
I did not know you could have zero value outputs. I’ll look into that. (And don’t worry, I wasn’t planning on destroying any coins!)
There’s nothing wrong with sacrificing coins (there are in fact, legitimate uses of that—see the Identity Protocol for example). The problem is creating outputs which you know to be unspendable, but can’t be proven by the deterministic algorithm the rest of the network uses (prefixing with RETURN).
This is not completely true—since only hashes of the public key are posted until funds are spent from an address
So what? Then the attacker waits till someone spents his funds and double spends them and gives the double spending transaction a high processing fee.
The idea is that the attacker doesn’t get to start attacking the public key until the first transaction is spent. Assuming the attack takes a nontrivial amount of time (more than an hour or so) the spend will already have a few confirmations before the attacker can write their double spend, so they’ll be uselessly behind.
It’s not guaranteed that the first break won’t be something really fast, but people seem to expect it not to be.
Assuming the attack takes a nontrivial amount of time (more than an hour or so) the spend will already have a few confirmations before the attacker can write their double spend, so they’ll be uselessly behind.
Even if the attacker takes on average a day to crack a key that doesn’t mean that he doesn’t have 0.01% to crack a key in a minute.
If there a good reason to assume that the attack needs to last a minimum of an hour to produce a key?
Yes, you are talking about a search in a 2^80 keyspace, even with quantum speedups. It’ll be a long, long time before anyone has the capability to o 2^80 large quantum computations in the span of 10 minutes, much longer until the cost of doing that computation will be less than the value of the coins.
So long as you are not stupid enough to reuse keys, it’s a non-issue.
Yes, you are talking about a search in a 2^80 keyspace, even with quantum speedups.
I have no problem with searching in a 2^80 keyspace with conventional means in a second. I have a low likelihood of finding the key but the likelihood is around the same if I do 100000 searches that take 1 second or one search that takes 100000 seconds.
If I want to stay under a 10 minute time threshold I can just switch the key I’m attacking every second.
I don’t know enough about quantum computation to know whether switching the attacked key frequently possible in the same way with the quantum algortihms but I would expect it to be.
I’m sorry, I don’t understand. That doesn’t make it any more economical. 2^80 is a big, big number: 1,208,925,819,614,629,174,706,176. Assuming you could try a billion keys a second (that’s quite the quantum computer!) then it’d still take you nearly 40 million years before you have a reasonable chance of guessing a single key.
But you can’t attack the ECDSA by Shor’s algorithm if you don’t know the public key, as is the case with a pubkey-hash address that has never been used. If you avoid key reuse, the only moment when coins are vulnerable is that ~10 minute interval after you’ve broadcast a transaction spending the coins but it hasn’t yet made it into a block.
No, first of all they are qualitatively different. Not all targets are the same. At best you could attack whatever the largest input in your current mempool is, perhaps a few dozen bitcoins at most. Whereas if you could choose your targets, something like this is better:
Second, it doesn’t change the fact that you’d still have this insanely powerful quantum supercomputer running for millions of years before you have a chance at double-spending a single coin. Not economically viable as I said before.
Second, it doesn’t change the fact that you’d still have this insanely powerful quantum supercomputer running for millions of years before you have a chance at double-spending a single coin. Not economically viable as I said before.
Various people do consider ECDSA to be effectively broken with quantum computers. It’s hard to estimate what a quantum computer of a certain power is going to cost in 20 years.
That said, I don’t need to capture enough coins to pay for the attack. I can buy options on failing bitcoin price and attack. If it’s known that there’s an attacker who randomly hijacks transactions the bitcoin price takes a blow.
I didn’t downvote you, but your points about cracked crypto or replacement currencies didn’t seem to support the statement that there’s no reason the risk should fall.
It seems to me that there are a variety of risks, of which some should go down with adoption and some should not.
There no reason why that risk should fall.
Bitcoins has such risks as a mathematician inventing a way to break public key crypto that would completely destroy it. Again if people build useable quantum computers, bitcoin is gone.
For being an digital currency bitcoin has massive amounts of transfer costs. It’s possible that someone creates a better online currency.
This is not completely true—since only hashes of the public key are posted until funds are spent from an address, you need both (a quantum computer or a public key crypto break) and a major break in SHA256. If only one thing breaks, there may be enough time for bitcoin devs to make a fix. It’d be relatively easy to switch to a different address hashing algo, and the whole internet is going to hurt badly if public key crypto can’t be fixed when quantum computers become common, so there’s a lot of motivation to find a replacement.
(It’s hard to imagine a break in SHA256 that’s complete enough to affect mining—weakenings are just the equivilent of running extra hardware.)
(It’s also not completely false, as I still expect events like that to still cause a large temporary depression in bitcoin price.)
Grover’s algorithm cuts hash strength in half. As I understand it, the whole point of 256 bit crypto is to survive the advent of quantum computers, when it degrades to 128 bits. Yes, a quantum computer shouldn’t break SHA256, but quantum computers would almost immediately account for the vast majority of the hashing power, centralizing control of the currency.* Once everyone has quantum computers, it would work again (with a replacement public key system), but given such a disruption, I don’t see much point to salvaging the old currency, rather than starting over.
* I think a gigahertz quantum computer would have the hashing power of the current bitcoin network.
Some relevant numbers: Based on the current target, I estimate that miners compute 5*10^18 hashes per block, 8*10^15 hashes per second. To match that, quantum computers working in mining need to compute 9*10^7 hashes per second.
My math agrees with you. Looks like I was underestimating the effect of quantum computers.
Difficulty is currently growing at 30-40% per month. That won’t last forever, obviously, but we can expect it to keep going up for a while, at least. (https://blockchain.info/charts/hash-rate) Still, it looks like you’d need an unrealistic amount of ASICs to match the output of just 1000 quantum computers.
Given that, there’ll probably be a large financial incentive to mine bitcoins with the first quantum computers. The incentive goes away if you destroy the network in the process, though. It seems difficult to predict what will happen. Single pools have controlled > 50% of the mining briefly in the past.
A lot of unhappy btc holders may see a point, though. :)
In particular, the ability to roll back the blockchain breaks the patches you’ve mentioned for the fact that QC also breaks elliptic curve crypto.
That’s true, but there’s some precedent for picking a block that everyone agrees upon (that exists before quantum computers) and changing the rules at that block to prevent someone from rewriting the blockchain. A lot depends on how much warning we have.
It looks like making a cryptocoin that can survive quantum computers might be a high value activity.
Pubkeys are protected by a dual construction of SHA-256 and RIPEMD-160, resulting in 80 bits of keyspace in a post-quantum world (assuming that existing quantum constructions can be extended into this dual-hash-of-ecdsa-key construction, which is not at all clear).
/nitpick
I always forget about the RIPEMD-160 step. The bitcoin wiki claims that it’s strictly more profitable to mine than to search for collisions, but it seems to me that that’s a function of block reward vs. value of address you’re trying to hack, so I don’t know if I believe that. https://en.bitcoin.it/wiki/Technical_background_of_Bitcoin_addresses
It’s unclear to me how you would actually implement this in a quantum computer; do you have to essentially build a set of quantum gates that implement RIPEMD-160(SHA256(pubkey))? Does this imply you need enough qubits to hold all stages of the calculation in memory at the same time? I haven’t been able to figure out from wikipedia how I’d arrange qubits to do a single hashing operation. Given that it’s a lot of sequential steps, perhaps it actually takes a lot of qubits chained together?
Actually RIPEMD-160(SHA-256(pubkey(privkey))).
That’s a massive understatement. Grover’s algorithm can be used to reverse either RIPEMD-160 or SHA-256 with sqrt speedup. In principle it should also handle RIPEMD-160(SHA-256(x)), just with a lot more qubits. Shor’s algorithm can be used to reverse the pubkey-from-privkey step. I’ll hand-wave and pretend there’s a way to combine the two into a single quantum computation [citation needed].
It’s … a lot of qubits. And you still need 2^80 full iterations of this algorithm, without errors, before you are 50% likely to have found a key. Which must be performed within ~10 minutes unless there is key reuse. So really it’s of zero practical relevance in the pre-singularity foreseeable future.
Technically you are correct. But in no conceivable & realistic future will it ever be more profitable to search for collisions then mine bitcoins, so for practical purposes the wiki is not wrong.
Thanks for the explanation, it seems like I’m not wildly misreading wikipedia. :)
It seems like the more qubits are required for this attack, the more likely we are to have a long warning time to prepare ourselves. The other attack of just cracking the pubkey when a transaction comes through and trying to beat the transaction, seems vastly more likely to be an actual problem.
Do you have any idea how I’d go about estimating the number of qubits required to implement just the SHA256(SHA256(...)) steps required by mining?
So what? Then the attacker waits till someone spents his funds and double spends them and gives the double spending transaction a high processing fee.
Public key crypto is nice but not essential as long as you have central authorities that you trust. We already have to trust certificate authorties. There no reason why they can’t facilitate key exchange more directly.
There motivation to find a replacement but that doesn’t mean that there’s a replacement to be found.
This can be fixed by a protocol addition, which can be implemented as long as there’s warning. (First publish a hash of your transaction. Once that’s been included in a block, publish the transaction. Namecoin already does something like this to prevent that exact attack.)
No, that won’t work. Blocks are rejected if any transaction contained within is invalid (this is required for SPV modes of operation, and so isn’t a requirement that can be dropped). Therefore a miner that works on a block containing transactions he didn’t personally verify can be trivially DoS’d by the competition. They would have a very large incentive not to include your transaction.
I think you misunderstood me—the transaction could still be rejected when you try to get it included in a subsequent block if it’s not valid. The hash of the transaction is just to prove that the transaction is the first spend from the given address; the transaction doesn’t/can’t get checked when the hash is included in the blockchain. Miners wouldn’t be able to do it for free—the protocol addition would be that you pay (from a quantum-safe address) to include a hash of a transaction into the blockchain. You publish the actual transaction some number of blocks later.
It really only makes sense as an emergency “get your coins into an address that’s quantum computer proof” sort of addition. Hopefully the problem is solved and everyone moves their funds before it becomes an emergency.
How does the miner know that there is no other conflicting transaction whose hash appeared earlier?
They don’t.
Suppose you publish hash HT1 of a transaction T1 spending address A, and then several blocks later when you publish T1 itself, someone hacks your pubkey and publishes transaction T2 also spending address A. Miners would hypothetically prefer T1 to T2, because there’s proof that T1 was made earlier.
In the case where someone had even earlier published hash HT0 of transaction T0 also spending address A, but never bothers to publish T0 (perhaps because their steal bot—which was watching for spends from A—crashed), well, they’re out of luck, because A no longer has funds as soon as T1 is included in the blockchain.
The pre-published hashes would be used only to break ties among transactions not yet included in any blocks.
Also, in this hypothetical scenario, the steal-bot from above means you shouldn’t trust funds that haven’t yet been moved into a quantum-computer-safe address; you wouldn’t know who all might have a old hash published with a bot just waiting to spend your funds as soon as you try to move them.
I see. I understand your proposal now at least. The downside is that it requires infinitely increasing storage for validating nodes, although you could get around that by having a hash commitment have a time limit associated with it.
Infinitely is a bit of an overstatement, especially if there’s a fee to store a hash. I agree it might still be prudent to have a time limit, though. Miners can forget the hash once it’s been referenced by a transaction.
The ability to pay to store a hash in the blockchain could be interesting for other reasons, like proving knowledge at a particular point in the past. There’s some hacky ways to do it now that involve sending tiny amounts of BTC to a number of addresses, or I suppose you could also hash your data as if it were a pubkey and send 1e-8 btc to that hash—but that’s destructive.
If you make it part of the validation process, then every validating node needs to keep the full list of seen hashes. Nodes would never be allowed to forget hashes that they haven’t seen make it onto the block chain, meaning that anyone could DoS bitcoin itself by registering endless streams of hashes. Perhaps this isn’t obvious, but note that fully validating nodes do not need to store the entire block chain history, currently, just the set of unspent transaction outputs, and there are proposals to eliminate the need for validators to store even that. If it’s just a gentleman’s agreement then it would be doable but wouldn’t really have any teeth against a motivated attacker.
You certainly don’t want to store data on the block chain by sending bitcoins to fake addresses, sacrificing coins, or other nonsense. That is inefficient and hurts the entire network, not just you. Please don’t do it.
There are already mechanisms to store hashes on the block chain which require no changes to the bitcoin protocol. You simply store the root hash of a Merkle list or prefix tree to the coinbase string, or an RETURN output of any transaction. An output can have zero value assigned to it, and if prefixed by the RETURN scripting opcode, is kept out of the unspent transaction output set entirely. I proposed one such structure for storing arbitrary data here:
https://github.com/maaku/bips/blob/master/drafts/auth-trie.mediawiki
Just stick the root hash in a coinbase string or the PUSHDATA of a RETURN output, then provide the path to the transaction containing it and the path through the structure as proof.
That’s a good point. To make this work, it’d probably make the most sense to treat the pre-published hash the same as unspent outputs. It can’t be free to make these or you could indeed DoS bitcoin.
I did not know you could have zero value outputs. I’ll look into that. (And don’t worry, I wasn’t planning on destroying any coins!)
There’s nothing wrong with sacrificing coins (there are in fact, legitimate uses of that—see the Identity Protocol for example). The problem is creating outputs which you know to be unspendable, but can’t be proven by the deterministic algorithm the rest of the network uses (prefixing with RETURN).
The idea is that the attacker doesn’t get to start attacking the public key until the first transaction is spent. Assuming the attack takes a nontrivial amount of time (more than an hour or so) the spend will already have a few confirmations before the attacker can write their double spend, so they’ll be uselessly behind.
It’s not guaranteed that the first break won’t be something really fast, but people seem to expect it not to be.
Even if the attacker takes on average a day to crack a key that doesn’t mean that he doesn’t have 0.01% to crack a key in a minute.
If there a good reason to assume that the attack needs to last a minimum of an hour to produce a key?
Yes, you are talking about a search in a 2^80 keyspace, even with quantum speedups. It’ll be a long, long time before anyone has the capability to o 2^80 large quantum computations in the span of 10 minutes, much longer until the cost of doing that computation will be less than the value of the coins.
So long as you are not stupid enough to reuse keys, it’s a non-issue.
I have no problem with searching in a 2^80 keyspace with conventional means in a second. I have a low likelihood of finding the key but the likelihood is around the same if I do 100000 searches that take 1 second or one search that takes 100000 seconds.
If I want to stay under a 10 minute time threshold I can just switch the key I’m attacking every second.
I don’t know enough about quantum computation to know whether switching the attacked key frequently possible in the same way with the quantum algortihms but I would expect it to be.
I’m sorry, I don’t understand. That doesn’t make it any more economical. 2^80 is a big, big number: 1,208,925,819,614,629,174,706,176. Assuming you could try a billion keys a second (that’s quite the quantum computer!) then it’d still take you nearly 40 million years before you have a reasonable chance of guessing a single key.
The point is that the 10 minute time limited in which transactions get confirmed is irrelevant and provides no protection.
Shor’s algorithm runs in polynomial time and can thus effectively used to attack public key crypto if you have a quantum computer at your disposal.
Bitcoin public key crypto also runs on ECDSA and Bruce Scheiner annouced earlier this year that he fears the NSA might have the ability to hack into ECDSA: http://www.wired.com/opinion/2013/09/black-budget-what-exactly-are-the-nsas-cryptanalytic-capabilities/
But you can’t attack the ECDSA by Shor’s algorithm if you don’t know the public key, as is the case with a pubkey-hash address that has never been used. If you avoid key reuse, the only moment when coins are vulnerable is that ~10 minute interval after you’ve broadcast a transaction spending the coins but it hasn’t yet made it into a block.
Yes, but as I said above that 10 minutes interval is irrelevant when you can just change your target key every minute.
As a attacker it’s quite okay to capture random transactions instead of attacking specific transactions.
No, first of all they are qualitatively different. Not all targets are the same. At best you could attack whatever the largest input in your current mempool is, perhaps a few dozen bitcoins at most. Whereas if you could choose your targets, something like this is better:
http://blockchain.info/address/1933phfhK3ZgFQNLGSDXvqCn32k2buXY8a
Second, it doesn’t change the fact that you’d still have this insanely powerful quantum supercomputer running for millions of years before you have a chance at double-spending a single coin. Not economically viable as I said before.
Various people do consider ECDSA to be effectively broken with quantum computers. It’s hard to estimate what a quantum computer of a certain power is going to cost in 20 years.
That said, I don’t need to capture enough coins to pay for the attack. I can buy options on failing bitcoin price and attack. If it’s known that there’s an attacker who randomly hijacks transactions the bitcoin price takes a blow.
Why are we both downvoted?
I’m probably downvoted because lavalamp argued that I’m wrong on a factual level and my rebuttal of his post wasn’t yet online.
I didn’t downvote you, but your points about cracked crypto or replacement currencies didn’t seem to support the statement that there’s no reason the risk should fall.
It seems to me that there are a variety of risks, of which some should go down with adoption and some should not.