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.
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.