= 27d567bc2d48d9f40e9ccc20ea370b15)
Metus comments on A proposed inefficiency in the Bitcoin markets - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (138)
Not sure what the lesson is, or the question. 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. In this model we have efficient markets as in all knowledge is encoded, random walk and exponential growth.
I am sleepy so have mercy with my reasoning.
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.)
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.
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/
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.
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.