Ok, here's what happened and what it means. Bitcoin is built on a chain of blocks, each of which contains a set of transactions, the hash of the previous block, and a cryptographic proof-of-work which takes a lot of computing power to construct. Whichever block-chain is highest (that is, has the most total computing power invested in it) is considered valid, and has more blocks added to it by miners. People "mine" by taking outstanding transactions, writing them into a block together with the hash of the current highest-numbered block, performing cryptographic proof-of-work and publishing their new block.
A block was mined (by the Slush mining pool) which is accepted as valid by 0.8 clients, but rejected by 0.7 clients. More than half of the mining power was on 0.8, so the longest chain includes this block - but the 0.7 clients reject it, and have built a side-chain. The developers have asked all miners and mining pools to switch from 0.8 to 0.7, so that the 0.7 chain will grow to be longer than the 0.8 chain; once this happens, all Bitcoin clients will agree that it is the real one. In the meantime, however, merchants running Bitcoin 0.8 may be targeted by double-spend attacks: if they receive money in a transaction that exists only in the 0.8 blockchain, the same money is spent in a different way on the 0.7 blockchain so the transaction can't just be copied over, and they act on the receipt of money by sending goods before the situation is resolved, then they could lose money. This is why MtGox has suspended Bitcoin deposits. (This can only happen if the coins were sent by someone who is using malicious, nonstandard software; transactions made by honest users will be copied to the 0.7 fork and mined without any issue.)
The height of the two chains can be monitored at https://coinbase.com/network/blocks . Currently the 0.7 chain is 13 blocks behind, which (since the normal mining rate is 6 blocks per hour) sets a lower bound of about two hours on resolution - assuming everyone switches their mining power immediately - but realistically it will probably be more like 6-12 hours.
So at least (13 blocks x 25btc * $40/btc =) $13,000 in block rewards miners thought they had -- and possibly more -- will be reassigned into the favored chain's winners.
This is part of why it takes much longer for mining rewards to be confirmed than other payments.
Since most people mine as part of pools these days, it probably doesn't matter too much. The average rate for the pool won't be affected too much (though I suppose pools which have been on the 0.8 block chain will hurt a little bit). There may be a one or two individuals who have mined a block and lose out by this, but if so, they were rolling the dice anyhow by mining outside of a pool; you can't expect a consistent income by mining over a span of 13 blocks.
Most pools pay out as soon as the block is mined, or at most one or two blocks later, and pay for any blocks that are later reorganized out of the chain from their own pockets. I fully expect to see several pools fail and take some or all of their miner's funds with them as a result of this incident.
Most pools don't distribute funds to their users until 120 confirmations have been reached so none of the coin that they mined will show up in their users' accounts. The only way this could cause problems is if the pool's maintainer is somehow still mining on the 0.8 branch which would not happen as the 0.7 branch blockchain has surpassed it in length.
If you are solo-mining and you found a block on the 0.8 branch of the fork, the standard client prevents spending newly minted coin with less than 120 confirmations. It will be the same as what happens when you get any other orphaned block, the funds will just disappear.
bzzt wrong. Most pools payout only after 100-120 blocks after the block they have mined is built upon by other miners (they go via an "estimate" then "unconfirmed" stage first). Additionally, the biggest mining pools either 1) only pay out their slave-miners after these confirms or 2) factor this in to their PPLNS slaves as a mining pool cost. Either way, you can bet they have enough in reserves to cover a small number of orphaned blocks. There will be no pools that fail after this event and I am prepared to bet on this.
"The developers have asked all miners and mining pools to switch..."
In the grand scheme of things, how much control over bitcoin do the developers have? My understanding of bitcoin is that there is no central authority controlling it like a central bank, but this statement almost implies that the developers have some kind of control, or influence at least, over bitcoin.
They have no actual control over what the miners do, but they have a lot of respect in the community, and most miners are likely to listen to their advice.
It's in the miners best interest to work for the bitcoin economy as a whole since their coins value depend on a coherent response to these types of black swan events.
Its in the banker's best interest to work for the US Economy as a whole, since their money and investments depend on the valid repayment of subprime mortgages.
I don't want to start an argument here, but that's not true; the banks' (i.e., shareholders') money depended on the US Economy. The bankers' money (salaries and bonuses) got paid even after the crisis.
The bankers were playing with other people's money, not their own.
Sure, they fired a lot of employees, but I wasn't exactly talking about the branch managers or salaried analysts when I said bankers. The Lehman Brothers executives still paid themselves $100M three days before the bankrupcy, and the others weren't exactly on ramen noodles either.
Perhaps. But they would have made even more money if the financial crisis never happened. We've got a case where executives make bad decisions for short-term personal gain.
This assumption that people always work for the long-term gain, even for themselves, was proven wrong in the financial crisis. The economy is made up of humans, and humans make mistakes.
Later, you bring up the point of $100 million paid to the Lehman Brothers executives. Do you know how much they got every year ? These guys are paid $50 million / year or $30 million / year PLUS stock options... if they wanted to make more money, they should have kept Lehman Brothers operating for just 3 more years.
The rules governing bitcoin are maintained by consensus, and the bitcoin developers have a large sway on this consensus.
If the majority of people decided they didnt like the current rules (eg all the people complaining about bitcoin deflation) they could very well change them by simple agreement.
Not really. For example if 51% (or even 99.99999999999%) of miners decided they wanted to go back to 50 BTC block reward (or even a new 5,000 BTC block reward) that would simply create an incompatible fork. A fork which would most likely be promptly rejected by the consensus of users, merchants, exchanges, and service providers.
One can't simply force a change to the rules. All you can do is make a hard fork in the network. If nobody adopts your hard fork well you can keep mining worthless coins but people can continue to use/mine the existing fork.
Bitcoin is highly resistant to change (almost to a fault). It is a common myth that the person who controls the majority of hashing power can change the rules.
A (malicious) person who controls a majority of the hashing power can change the rules. Central to bitcoin is the idea that the longest chain is the valid one. If you control 51% of the network, you can create a chain that looks however you want it to look, and then publish that chain. Because your chain is longer than the correct one, it will be accepted, and your changes will be accepted. Using this, you can modify the chain to be what it would look like according to your rules.
Of course, this is only possible becuase your chain looks as if it was following the rules. If you have a non malicious computational majority, than any change in the rules would make an incompatible block-chain and a hardfork.
The software is the central authority. As far as I have been able to tell there is no decent specification, like an RFC, that you could use to build other client implementations from so you are all at the mercy of the bugs in a single piece of software.
"Homesteading the Noosphere" by Eric Raymond covers exactly this topic. He compares the open source software ownership to Lockean land titles. With Bitcoin, it's interesting since the project itself is a system of value and transactions.
Would they need to start a rival block chain? Or do they just need 51% of the current community to run their clients to take over the current block chain? (as suggested by a comment above)
Technically speaking, getting 51% of the community to switch is still creating a rival block chain. You don't even need 51%. As was the case in this incident, if you have incompatible nodes, the block chain would fork itself naturally.
0.8 clients were wrong to accept it, because doing so caused a failure of consensus.
Unfortunately the limit that was hit (which isn't quite as simple as 'size') was implicit in BDB and how Bitcoin prior to 0.8 used BDB. So no one was aware of it.
Extensive testing during 0.8 turned up several consensus breaking issues that were created during the database switch out, and very large blocks were tested... but the particular kind of very large block required to reveal this difference in behavior was not.
0.8 and 0.7 have different databases (LevelDB and BDB respectively). The 0.7 database doesn't accept some high-volume blocks under certain conditions (not 100% sure what those conditions are, that's for the devs to fix now). As a result, the chains forked when an 0.8 node mined a block 0.7 could not handle.
Everyone followed proper behaviors, it's just a compatibility problem. So miners should resort to 0.7 until 0.8 can prevent a fork like this from happening again.
They do not need everyone to stop using 0.8, just a majority (so that the 0.7 chain becomes the strongest).
You would need to get everyone to stop using 0.7 (or much more than a majority, or as soon as another block of this kind resurfaces the clients would be useless again).
0.8 accepts blocks that 0.7 rejects, 0.8 does not reject any blocks that 0.7 accepts. So 0.7 is more compatible going forward until the problem is solved with 0.9 etc.
There's a bug in 0.7. That bug means 0.7 clients reject what is, by spec, a valid block, while 0.8 clients accept it. So they can coexist for a while, until a block comes along that causes 0.7 to reject it.
Even once that happens, if there are more 0.7 clients than 0.8 clients, they will keep mining, eventually generating a longer chain, and the 0.8 clients will start accepting that longer chain. It's only once 0.8 has more mining power behind it that you get a split; now the 0.8 clients will keep forming a longer chain, and the 0.7 clients will be left behind, as they still see that chain as invalid (due to the invalid block), so they only see the 0.7 chain.
So, while the 0.8 clients were not "wrong" in accepting the bad block, it's pretty hard to fix the problem by convincing everyone to update to 0.8; some people may just not be able to or want to update. But it is easier to fix the problem by getting just enough people to downgrade to 0.7; as long as more than 50% of the mining power is on 0.7, that block chain will be the longest and both 0.7 and 0.8 will work fine with it.
Another way to look at it is to ignore the spec, and just look at the reality of implementation. According to the reality, 0.8 introduced a non-backwards-compatible feature allowing it to accept new kinds o blocks. In terms of protocols, this is sometimes known as "embrace and extend"; support the open protocol that everyone else supports, but add extra incompatible features. While this probably wasn't intended, the effect was that 0.8 miners got an advantage on mining new blocks; they would accept block mined by 0.7 miners, thus keeping ahead of the chain, but once they managed to mine an incompatible block, they would now be a block ahead of the 0.7 miners.
Now, what does this mean in terms of transaction security? Most likely nothing, unless there were any double spends, where the same coins were spent in one way on one chain and another way on the other. If there were double spends, you could look at both block chains and find them; given how quickly this was caught, it's pretty likely you could track down where the double spends went, and it's unlikely that the double spends have changed hands more than once given how short this split is. But there are other factors that make the double spends unlikely. Most transactions will propagate throughout the network pretty quickly, to miners on both sides of the block chain split, meaning that both block chains are likely to record the same transactions. You would have to notice this split, and target transactions at each side of the split so that miners on each side would pick up separate transactions, without the person that you are sending the coins to (and who is presumably sending you something else in return) noticing, all within the span of a few hours.
Now, given that this has happened once, I would be surprised if someone doesn't write a bot that noticed this kind of split and do just that, to see if they can get any double transactions accepted. To defend against this, anyone who cares that much (such as any large Bitcoin merchants or payment processors) can do the converse, monitoring for any chain splits and following both sides to watch for double payments, treating those as fraud and returning (or keeping) them without actually delivering the goods in question.
Good luck tracking down all the double-spends, because there were an awful lot of them: http://blockchain.info/double-spends Most of the ones I've looked at so far are Satoshi Dice bets, but there may be more substantial double-spending hiding amongst the list.
I don't understand this. If 0.8 fixed the bug that 0.7 contains, shouldn't encourage everyone to upgrade instead of downgrade? And it's fine that the longest blockchain is on 0.8; that is the latest version. If you're not patching your software, I am not so surprised that you're vulnerable (in this case to double-spending attacks).
A second thing that I don't understand is why 0.8 people are vulnerable to double-spending attacks. It wasn't said that 0.7 was safe, but it was said that 0.8 was vulnerable. But with two separate blockchains, wouldn't both be vulnerable? Or at least 0.7 because they don't accept 0.8's blockchain?
If they pushed for people upgrading to 0.8 then everyone not upgrading would have their own blockchain. By getting more than 50% of the users to use 0.7, the rest of the 0.8 clients will discover that everyone else uses the 0.7 chain and thus replay all of the transactions on that chain.
Upgrading: Those who doesn't upgrade end up with their own chain.
Downgrading: Those who doesn't downgrade will automatically use the other chain when it becomes dominant.
> But with two separate blockchains, wouldn't both be vulnerable?
It's only the chain that doesn't become the main chain that is vulnerable. Because they're pushing for 0.7 to be the main chain you don't have to worry about double spending there.
The choice was made for backwards compatibility. People are still running version 0.3-0.7 of bitcoind and up to this point that was not a problem. If we decided the 0.8 fork was canonical we'd lose a big chunk of the userbase.
They don't (can't) rule with an iron fist, but they have a lot of good will with the community, so most will listen to them.
EDIT- The good/bad news is that since most mining (and thus transaction verification) has consolidated into large pools of machines, only a few people have to agree with "them". So in a sense, there is a central committee of people who run the large mining pools that does have a fair amount of power.
Yes, you could say that ultimately the miners rule which blockchain grows, but have strong reasons to defer to the judgement core developers.
Even though the pool operators have large discretion, the computational power that makes up their pools can be moved elsewhere... a little like a transferable proxy. Most smaller miners probably trust the pools who they've grown confident in... but a large enough controversy or campaign could conceivably shift the mining-power away from pool operators who make unpopular decisions.
Yes. A large enough controversy could also threaten to devalue Bitcoin drastically. No one wants to store assets in a currency which could potentially lose the faith of all of its merchants, vendors when it forks and no one can agree on which fork is the 'correct' one. It's in everyone's best interest to do whatever it takes to get back to a single long blockchain.
It's easy to fall prey to the idea that the ideal is that there is no authorities anywhere, but that's not the goal. The point is that you can choose your authority freely, and if enough people decide a given authority is no longer worthwhile, they can choose a new one freely.
Open source works the same way. Of course there are authorities for a given project who can choose what the final release is, but if they get too full of themselves or something it's easy enough to bypass them. It's happened quite frequently, so it's not an idle threat, either. You can't prevent authority from developing, that's wouldn't even be a good thing, but you can prevent it from abusing its current position of authority to lock in future authority.
Exactly, no-one is forcing the miners to do this. The 0.8 miners could decide to keep that branch alive, and if it stays longest, then the "central committee" would be SOL and just have to accept it.
> .7 and older nodes use BDB for storing the blockchain databases. It seems this database has a limit on the size of the modification it can make atomically to the database. With the larger blocks of the past days, it seems to have triggered the limit. The result is that 0.7 (by default, it can be tweaked manually) will not accept "too large" blocks (we don't yet know what exactly causes it, but it is very likely caused by many transactions in the block). Specifically, block 000000000000015c50b165fcdd33556f8b44800c5298943ac70b112df480c023 (height=225430) with >1700 transactions.
> However. 0.8 (which uses a different database system) has no such limit, and happily accepts the block. As the majority of the hash power was on 0.8, the longest chain ended up using this block, which is not accepted by older nodes.
I use BDB and I doubt they are actually running in to any kind of hard limit of the database. They are probably just running out of locks. Number of locks is a configuration option.
Each modified database page needs an allocated lock that is held during the database transaction until it is committed.
> It seems this database has a limit on the size of the modification it can make atomically to the database.
If this were an unlucky edge case, I could understand. But it seems like they allowed larger block sizes without testing them on pre v0.8 miners - which might be 25% of miners and the upgrade to v0.8 was less than 1 month ago. It's nice to think that 100% of people will upgrade within a few weeks, but that's just not how some people work.
> If this were an unlucky edge case, I could understand. But it seems like they allowed larger block sizes without testing them on pre v0.8 miners
That is not entirely correct. Multiple large blocks were tested on v0.7 (and older clients). Blocks up to the 1MB hard limits were validated and relayed by older clients.
The "problem block" in particular wasn't rejected due to simply being too large. It was somewhat rare in that it exceeded the number of low level locks available to v0.7 clients. It had a large number of transactions with a large number of inputs and outputs and those happened to have a large number of compressed keys. Without using a high number of compressed keys it wouldn't be possible to have a block with this number of inputs and outputs in the 1MB limit.
Granted in hindsight more testing should have been done but it wasn't like nobody said "hey we should test large blocks, nah I am sure it will be fine".
I wasn't involved at all in the discussions, but the cryptopunk in me wonders if this isn't malice. Running out of DB entries in the client can be predicted with reasonable accuracy. "Accidentally" slip in this bug, and "fix" it in a future version. Then time a major transaction to coincide with the fork you know will happen, and bam! Engineered transaction reversal.
That would be one great hack. But my imagination is probably just getting the best of me.
Not to mention one giant hack that would be recorded in the publicly available block chain. Given how high-profile this bug is, I suspect that many people will check both chains to see how much double spending occured, and if any of them are suspicious.
Is there a sensible fashion by which two robust blockchain forks might merge?
Widespread use of the currency is troublesome if it's possible for anyone to have reasonable odds of forking the chain. If it's possible for a mass panic to reverse transactions, it's not as reliable.
If Asia (4 billion people), banking institution (US federal debt = ~23% of world GDP), or a social group (Catholicism: 63% of the Americas) buys a bunch of stuff then decides, en masse, to revert to an earlier blockchain, it could drive instability. Large groups of people sometimes do unpredictable things (Gangnam Style: 1.4 billion views).
"Is there a sensible fashion by which two robust blockchain forks might merge?"
They will not merge, but transactions will homogeneize.
I have simulated this scenario, forking the Bitcoin chain on a private network 2 years ago. What happens is that if the chain is forked, and if a client unexpectedly sees that another chain (say chain B) suddenly replaces the chain it was following (say chain A), thereby reverting a bunch of transactions, then the client will automatically retransmits its transactions that it had saved in chain A, to have them saved again in chain B.
That is how a non-malicious client operates.
Of course, if you are a malicious person, you can actually kill the client and manually wipe out its cache of transactions before it has time to retransmit transactions for chain B (therefore recovering coins that you had spent on chain A).
I think this scenario is worse because in theory the transactions aren't going to get copied over from the 0.8 chain to the 0.7 chain until the 0.7 chain overtakes the 0.8 one. The two versions aren't database-compatible, so anyone who follows the advice and manually downgrades to get on the right chain is going to lose all the transactions from the previous chain whether they want to or not.
The fork was at the block level not transaction level.
The transactions are on both chains. While they may be in v0.8 blocks and still unconfirmed in the v0.7 fork they do exist in the v0.7 fork. The only transactions which couldn't exist in the v0.7 fork are those generated in "v0.8 only blocks" and those are hard locked by the protocol for 100 blocks.
Had both halves of the fork existed for more than 100 blocks that would have presented a more serious problem. This is why the stakeholders (exchanges, merchants, miners, and developers) moved quickly to halt transactions, warn users, and move to the v0.7 version of the chain BEFORE one chain got more than 100 blocks from the fork point.
They never merge. But each should want to (and be able to) subsume all non-conflicting transactions from the sibling chain, so it's only a small number of 'double-spends' that wouldn't live in both. Eventually one history will win, and only the conflicting transactions from the losing history lose out.
Unless...
Perhaps an enduring, permanent split, under the right conditions, with people motivated to keep both chains alive indefinitely, could be a good thing. Among other things, it might solve the deflation problem, or allow a runt network to continue if the mother network were compromised by technical or legal attacks. (Or depending on your perspective, allow the mother network to continue if a runt network is created by certain attacks.)
> Is there a sensible fashion by which two robust blockchain forks might merge?
No, but the "transaction graph" which underlies both chains can (and will) be merged, in some sense.
> If [lots of people conspire] to revert to an earlier blockchain, it could drive instability.
The blockchain will only ever split inadvertently, or due to probability (the unlikelihood of multiple blocks being orphaned). A majority of miners would have to conspire to begin mining on a chain with less than 50% of the hashrate, which would be a waste of resources if the chain fails (which it will).
There's not just an incentive but a probabilistic force preventing forks from occurring.
What if, rather than a client failing blocks that should succeed, a client is designed that accepts things (and generates things) that should fail, and yet becomes the most popular client among a very large subgroup (either by accident, or on purpose). I think that's the question being asked with regards to the "Asia, banks, etc." scenario.
Those are equivelent scenerios. If client A generates and accepts coins that client B rejects, it is the same as client B regecting the same coins that client A accepts.
Yes: I understand that they are equivalent in the final problem, which is precisely why I went to the effort to try to make the formation more specific; the argument ewillbefull was making that it is highly unlikely for this kind of thing to be a problem due to probabilistic reasons doesn't apply when you setup the problem in reverse.
There are two ways that a fork could occur. 1) 2 transactions happen at the same time and one of them happens to win. This is normal, and the loosing transaction simply re-transmits. This is also why you should wait (I think) ~5 minutes before you consider a transaction `validated`. 2) All of Asia (or another group) decides to fork. This is equivelent to all of Asia saying that they do not acknowledge all transactions made after a certain time. There are the same consequences as in a traditional currency when this happens.
The way the Bitcoin community handled this mornings fork in the bitcoin blockchain is nothing short of incredible. This event significantly increases my confidence in the Bitcoin ecosystem to thrive even when faced with critical issues.
If only the global finance institutions had a fraction of bitcoins capacity to resolve crises with the same unconditional transparency and full cooperation with all agents in the ecosystem.
"This event significantly increases my confidence in the Bitcoin ecosystem to thrive even when faced with critical issues."
It does the opposite for me, because it demonstrates that Bitcoin is extremely vulnerable to double spending. Either everyone uses the same version of the software, or you have to deal with the possibility that this event will happen again. Worse still, an attacker might use some kind of malware to modify Bitcoin clients, until they are able to fork the network and double spend.
Yes, making cryptosystems that are secure against malicious majorities is difficult, and experts have published tons of papers and several books on the subject. If Bitcoin's developers want people to trust their system for anything non-trivial, they really need to fix this problem. To break David Chaum's digital cash systems, an attacker would have required exponential computing power in a security parameter that could be scaled arbitrarily, while the users only require polynomial computing power in that same parameter; to break Bitcoin, an attacker only requires a little more than half the sum of all the computing power in the Bitcoin network. The Germans learned the hard way that just because an attack seems too pricey for anyone to bother with does not mean that the attack actually is too pricey for anyone to bother with.
The ability for clients to erroneously or maliciously fork the chain can't be designed out whilst keeping the system open and decentralised. The blockchain is a distributed copy of a shared truth which takes time to propagate and has to be agreed upon by all participants. If the network is open, then me, or me and 500,000 friends, can join the network and attempt to propagate a different truth.
If you compare the way the Bitcoin community responded to this with the response you might have expected from even a very well run company, I think the Bitcoin community comes out ahead.
It would be useful and or interesting to compare the Bitcoin community response with a specific failure and response of a for-profit closed-technology company, but I'm not sure what case to use for comparison.
"The ability for clients to erroneously or maliciously fork the chain can't be designed out whilst keeping the system open and decentralised"
That is not true. Cryptographers have published many thousands of papers on securing multiparty computation against malicious participants over the past twenty years. Here is a very brief introduction:
The relevant citations in this field, like the relevant citations about digital cash protocols, are conspicuously absent from Satoshi's writeup about Bitcoin. This is one of the things that bugs me the most about the Bitcoin community: nobody seems to have done any background research at all. There is a huge volume of work that has been done in this field, but little mention of it among Bitcoin's developers. The Bitcoin developers do not even seem to be worried about the fact that the work required to attack Bitcoin scales linearly with the work required to run the Bitcoin system:
"If you compare the way the Bitcoin community responded to this with the response you might have expected from even a very well run company, I think the Bitcoin community comes out ahead."
OK, the community is great at admitting that there are bugs and finding workarounds. That does not count for much in a secure multiparty system, where subtle problems in a protocol can undermine the security of the entire system. Security in a system like Bitcoin is about more than just "avoid X, remember to do Y, and patch bugs quickly!" Malicious clients are going to have to be dealt with in Bitcoin, and they are going to have to be dealt with better than what we saw today.
The thing you must realize is that those previous systems didn't solve the problem Bitcoin solves. It's not quite obvious - I read the Bitcoin paper when it had pretty much just come out, didn't recognize the actual problem it was solving, and ignored it as yet another "contradictory-caveat" system (eg. paper title: "Anonymous Offline Payments!!@" ... later section: "identity escrow, merchant accounts, only offline for honest parties, etc"). It sucks that there's finally a widespread digital currency and it's non-anonymous, but that's not the problem Satoshi actually solved.
"The thing you must realize is that those previous systems didn't solve the problem Bitcoin solves"
That is not the point. Previous work in the field of digital cash and in multiparty computation is very much relevant to Bitcoin, even if Bitcoin addresses a modified problem. The failure to even mention that such work has been done, coupled with a woefully deficient analysis, indicates that the author of the Bitcoin paper had not done much background research.
What stands out the most is the security analysis for Bitcoin. First, the author makes the claim that the system is secure as long as the attacker controls less than half the sum of the computing power of all nodes in the system. This is not really a well-understood model of security; cryptography researchers usually speak of either "honest but curious" models i.e. everyone follows the protocol faithfully or "malicious" models i.e. some parties may deviate from the protocol in arbitrary ways. The idea of a party that can deviate, but only as long as their work is less than the sum of the work done by all other parties, is strange -- but this new security model is not discussed in any depth, nor is it even mentioned as being a new model of security. No time is spent actually proving the claim, which is unsurprising given that the security model itself is not even formalized.
Worse still, the security analysis that is presented only deals with a specific attack carried out in a specific way. The author proves in a somewhat-formal way that this particular attack cannot be carried out in the way he envisioned. No evidence is given that another method of carrying out the attack is impossible, nor is any evidence given that other attacks are impossible.
There is an old proverb in cryptography: anyone can come up with a cryptosystem they themselves cannot break. That is what you are seeing with Bitcoin, but even worse, because the developers know how to break it but do not believe that anyone would be willing to put in the effort. The German cryptographers were surprised to discover that the Allies were willing to build the code-breaking machine necessary to crack Enigma; they knew it had weaknesses but believed that the cost of exploiting those weaknesses was too high for anyone to justify.
My point is less about what problem Bitcoin solves, and more about whether or not Bitcoin's developers are aware of just how much work has been done on secure multiparty computation or digital cash systems.
I don't really disagree with anything you're saying. Bitcoin has a lack of rigor all around, and it's quite annoying to see the masses of people defending Bitcoin as being anonymous (etc) when they've no context to place it in.
What I am trying to point out is that Bitcoin has a design property that enables it to actually be adopted (no "bank" - something no other ecash system had, as they were mostly designed in an era when people still believed that banks would be interested in preserving their customers' privacy. lol). This is important if someone is to ever build a better system.
I'm less familiar with recent MPC literature, but the general concept strikes me as more of an existence proof, given the actual efficiency of resulting implementations. Practical ZK/WI results seem to generally decompose larger domain-specific chunks of the problem into primitive operations, rather than one crypto op per generic logic gate. Which seems to be what Bitcoin is doing, in a bumbling sort of way. And I don't see too much of a philosophical leap between "majority of parties" and "majority of computation", given that the former is wishful thinking that admits Sybil attacks.
"What I am trying to point out is that Bitcoin has a design property that enables it to actually be adopted (no "bank" - something no other ecash system had, as they were mostly designed in an era when people still believed that banks would be interested in preserving their customers' privacy. lol). This is important if someone is to ever build a better system."
Keep in mind that there is more to digital cash than just maintaining customer privacy (and Bitcoin itself does not really give you anonymity, at least with any reliable guarantees). Banks benefits from digital cash because of the difficulty of committing fraud and (assuming offline transactions) the reduced load on their transaction processing systems. The real issue is not that banks have no incentive to deploy such a system, but rather that their existence fraud-mitigation measures are more cost effective (in the short term). As my colleagues who have worked with banks have explained it to me, the banks only want to know what amount of fraud would occur; if your system can reduce that fraud more than it costs to deploy, then the bank will spend the money to deploy it.
The same design that has led to Bitcoin's adoption is also something of a liability for the system. Without any banks, converting Bitcoin to other currencies requires the use of an exchange, which carries increased costs and risks. The lack of stability in the price of Bitcoin relative to USD is a result of this issue. It is easy to forget that there is a source of demand for USD, one that is grounded in legal structures like the tax code, debt law, torts, etc. Even when people use Bitcoin for their business, they still need to eventually exchange Bitcoin for some national currency to pay taxes and repay debts (and perhaps to pay employees who lack the time or sophistication needed to use a Bitcoin exchange).
Another issue is more technical: there is no secure way to process an offline Bitcoin transaction. In one of his published papers, Chaum proved a property of offline digital cash systems that is as relevant to Bitcoin as it is to Chaum's design: the amount of information that needs to be exchanged in an offline transaction must grow linearly in the length of the offline transaction chain (imagine if a dollar bill became heavier every time it was given from one person to another). What this means is that either you need the ability to "refresh" the unit of value (e.g. reissuing the token in Chaum's system) or else your offline transactions are either insecure or not scalable. As there is nothing in Bitcoin that can "reissue" currency (which involves creating fresh units and destroying old units), Bitcoin is either insecure, insecure for offline transactions, or it does not scale (note that "secure" in this case refers to formal notions of security; Bitcoin does not actually meet that standard, so this point may be moot anyway).
"Practical ZK/WI results seem to generally decompose larger domain-specific chunks of the problem into primitive operations, rather than one crypto op per generic logic gate."
Right, and that is within the field of MPC research. General MPC using circuits or some other description of functions is much slower than special-purpose protocols, which are themselves usually slower than just using a trusted third party. You are correct that Bitcoin is an example of special-purpose protocol; the problem is that Bitcoin as it exists today would only be secure in a minutely stronger variant of the honest-but-curious model. Honest-but-curious is really just a research tool, a model that is used to give feasibility results or to test new designs, and it is certainly not the right security model for anything involving money (of any sort).
"I don't see too much of a philosophical leap between "majority of parties" and "majority of computation","
The leap is this: a single party might gather immense computing power without corrupting any other party. As a simple example, my research group has access to a supercomputer run by the University of Texas, which I could potentially run anything on (not necessarily legally). If you and I were going to use a two-party protocol of some kind, would you really want to use one that forced you to get access to a similarly powerful supercomputer just to be secure?
Worse still, you might not be aware of the computing resources available to other parties. The Germans were not aware of the Enigma-cracking effort until after the end of the war. In today's world, it is possible that your adversary has a botnet, a bunch of EC2 credits, or that you are dealing with the NSA. In all cases, you do not want to rely on a system that requires you to get equal computing power to remain secure.
Some MPC protocols are secure unconditionally, meaning that even an attacker whose computing power is completely unbounded will not be able to violate the security property of the system. In such a case, controlling a majority of the computing power of all parties is not even a relevant detail, because increased computing power does not convey any advantage.
It is more common to assume some bound on the attacker's computing power and to use complexity theoretic arguments about security. Typically, the attacker is assumed to be able to scale their computing power up by some polynomial in the parameters of the system, which includes the participants. Again, it is because there are real-world adversaries who control large amounts of computing power, potentially in secret, that such models are used. The justification is intuitively this: if you have one desktop and your adversary requires a cluster of ten thousand desktops to break the security of the system, you can get a second desktop and double the work you need to do while forcing your adversary to find ten thousand clusters of ten thousand desktops (i.e. squaring his workload). Super-polynomial growth tends to "run away" at the second half of the chess board, so that a modest increase in the work done by honest parties can result in the attacker needing to keep working until the heat death of the sun.
On the other hand, a powerful adversary could potentially corrupt or control parties in the system. The Mafia is not going to buy NSA-level computers; they are going to find the participants and beat them with wrenches. A more real-world example would be the suspicious appearance of lots of highly-reliable anonymous remailers after the September 11th attacks. Having a lot of computing power does little to defeat the remailer system, but if you control all the remailers you can deanonymize anyone. Remailers have a nice security property: only one honest remailer is required to preserve your security (assuming you send your messages through all the remailers and that the remailer protocol itself has certain security properties which real-world remailers lack).
Sorry if that was a bit long. This is a pretty deep topic, and even the foundations are highly technical.
> Banks benefits from digital cash because of the difficulty of committing fraud and (assuming offline transactions) the reduced load on their transaction processing systems
Decades of non-adoption say otherwise. It's hard to say what the exact reason is - paralyzing conservatism, business models built on decommoditizing money into an identity-based instrument, conspiracy via government regulation, or something else. But enough time has passed that if banks were remotely receptive to the idea of digital cash, it would have caught on somewhere.
> there is nothing in Bitcoin that can "reissue" currency
Every new wallet address, no? Offline transactions are vulnerable to double spends, but this is the case with every digital cash system. IIRC, the ones that protect against offline double spends do so by revealing the fraudster's identity if a token is spent twice - requiring a bank and legal system for recourse.
> It is more common to assume some bound on the attacker's computing power and to use complexity theoretic arguments about security.
Sure, and this is what the SHA2/DSA parts of Bitcoin do. Nobody can forge transactions, the worry comes about from double-spending. You have to remember, digital currency is not a two-party problem - every involved party is what gives the currency value. This is essentially a coordination problem (which database copy is authoritative?), and is precisely the novel problem that Bitcoin solved. Previous p2p attempts would do something like "majority of parties", which is always vulnerable to Sybil attacks. Bitcoin went for something that can be algorithmically enforced, staking its outcome on the belief that NSA-level computing would both not dwarf the rest of the network, and that double spends would be detected and could be somehow mitigated down the line.
"enough time has passed that if banks were remotely receptive to the idea of digital cash, it would have caught on somewhere."
Again, the way I understand it, the problem is not a lack of benefit but that the benefit is not sufficient to convince any bank to switch. Banks are very concerned about fraud; the problem is that they do not get enough fraud protection from digital cash to outweigh the cost, because they already have good fraud mitigation methods. Why switch to a car that gets one more mile per gallon of fuel, when the cost of doing so would not be recouperated for decades?
"Offline transactions are vulnerable to double spends, but this is the case with every digital cash system."
The difference is that a person can double-spend in Bitcoin over and over again, even if the double spending is detected at some point. In Chaum's design, a person who double-spends is eventually ejected from the system, and so a person can only double spend until the double-spent money makes its way back to the bank. A legal system is not strictly needed here; all it takes is the bank blacklisting cheaters.
"this is what the SHA2/DSA parts of Bitcoin do. Nobody can forge transactions"
One does not follow from the other. SHA2 is a (hopefully) secure hash function. DSA is a secure signature system. People might still be able to forge transactions, due to some other property of the Bitcoin protocol that composes poorly with DSA/SHA2. A transaction in Bitcoin is not merely a signed message; there is a protocol that is used to decide the validity of the transaction, and that protocol might be vulnerable to attack (and maybe vulnerable to attack as a result of using DSA, as opposed to some other signature system). Without a formal proof of security for the entire transaction protocol, it is hard to say.
A simpler example might help to illustrate the point. Imagine a system for telling employees that they have been fired that works as follows: the boss signs and encrypts the letter "F" using his signing key and the target's encryption key. It may appear that forging a firing notification is hard, because the signature marks it as authentic and the encryption designates the target (i.e. if you cannot open the message, then you were not fired). However, it is possible for an employee who is fired to turn around and fire others by re-encrypting the message and signature -- which works even if the signature and encryption systems used are secure.
"This is essentially a coordination problem (which database copy is authoritative?),"
What does "authoritative" actually mean in the absence of an authority? Without a good definition, it is hard to actually say what a solution would have to look like.
"the novel problem that Bitcoin solved."
The fact that Tuesday's fork could happen is pretty strong evidence that Bitcoin is not really a solution to the problem (assuming we even know what the problem actually is). The fact that a double spending attack was made possible by the fork is a sign that Bitcoin is either (a) solving the wrong problem or (b) not solving the problem at all.
Even if we limit ourselves to considering only Sybil attacks, Bitcoin does not truly solve the problem. Sybil attacks are still possible; the only difference is that now the attacker will need more CPU power (maybe; more sophisticated attacks are certainly conceivable).
"Bitcoin went for something that can be algorithmically enforced"
Except that it is not enforced (at least not under any well-understood definition of that word), it is based on this sort of thing:
"staking its outcome on the belief that NSA-level computing would both not dwarf the rest of the network"
In other words, it is assumed that the adversary could never accumulate as much computing power as all the Bitcoin users combined have accumulated. This is a pretty bad assumption to make, since it fails under any number of entirely plausible circumstances. NSA-level computing is a complete mystery to the outside world; maybe they are using computing technology nobody else has, that works substantially more efficiently. How do you know your adversary does not have such systems? Every so often, Bitcoin "miners" switch to some faster technology for that task; is an adversary who invents a new technology for this really so hard to believe?
"double spends would be detected and could be somehow mitigated down the line"
What exactly can be done to "mitigate" double spending in Bitcoin? There is no system for denying access to the network. An attacker who double-spends Bitcoin could keep coming back and could keep double-spending. In Chaum's system, double-spending carries the cost of losing one's access to the system; with Bitcoin, it carries no cost at all (one might just sell the equipment used for the attack, and so one only really needs sufficient capital or credit to procure the equipment in the first place).
> because they already have good fraud mitigation methods
Then why is it such a big topic, with the banks even deflecting the blame by inventing "identity theft" etc? And even if the banks are fine, the merchants are not, and a new bank should have sprung up to address that. Which leaves us with the remaining option - incumbent banks are cooperating to prevent new competition. I'm not trying to specifically convince you of this paranoia, but provide it as something that may have to be overcome by a digital payment system to be adopted.
> Chaum's design, a person who double-spends is eventually ejected from the system
I'm hazy on my ecash citations. Is "Chaum's design" the one where merchants are assigned identities, payment is offline but specific to the merchant's identity, and a double spender's identity is revealed if a coin has been spent at two different merchants? That's the system that's stuck in my head as best-in-breed if there is a bank on board.
But what I've been trying to get across here is that Bitcoin provides a property none of those other systems provided - freedom from a trusted "issuer"/bank/etc. (While those protocols don't trust the bank to preserve privacy, they do trust the bank to administer the currency by being the counterparty to the tokens.)
> People might still be able to forge transactions, due to some other property of the Bitcoin protocol that composes poorly with DSA/SHA2
Oh sorry, you caught me with my rigor-pants down. What I meant to say is that being built from those primitives, it could be proved as secure as those primitives. Unlike the Byzantine agreement component, which will always have other security tradeoffs beyond SHA2.
> What does "authoritative" actually mean in the absence of an authority? Without a good definition, it is hard to actually say what a solution would have to look like.
When we give up trusted authorities (and specific "parties" necessarily created by some trusted authority), what remains? What differentiates "the majority" ? One of the few things I see is computing power.
> Sybil attacks are still possible; the only difference is that now the attacker will need more CPU power
No, Sybil attacks have been defined away, as they depend on some notion of "parties". The "honest parties" wishful-thinking has vanished, leaving only "majority of computation" as the network authority. Of course the merits of this security model are still up for debate, but it seems to mostly work.
> The fact that Tuesday's fork could happen is pretty strong evidence that Bitcoin is not really a solution to the problem
Erm, given that the fork was a rare event, it actually shows that Bitcoin is mostly solving the problem, just not perfectly.
> What exactly can be done to "mitigate" double spending in Bitcoin? There is no system for denying access to the network
Lol. "no system for" is not the same as "system prevents" (see what happened to the End to End principle). I guarantee we will eventually see exchanges exerting control over what constitutes "valid transactions" and "the network". This is Bitcoin's real weakness.
"Is "Chaum's design" the one where merchants are assigned identities, payment is offline but specific to the merchant's identity, and a double spender's identity is revealed if a coin has been spent at two different merchants?"
More or less; the important concept is that a double-spending attack will not only be detected, but that it will both reveal the identity of the attacker and allow the attacker to be blacklisted. It is not necessary to differentiate "merchants" and "spenders;" re-spending a transferred coin in an offline protocol is possible (without sacrificing the "double-spending reveals the attacker's identity" property).
"Bitcoin provides a property none of those other systems provided - freedom from a trusted "issuer"/bank/etc"
Bitcoin may do this, but it does so by sacrificing rigorous security and offline payments. Even if we assume that a monetary system without any authorities makes sense (I am doubtful about that), a system where the attacker's effort is linear in the system's parameters is not a system that can be trusted with any significant amount of money.
"What I meant to say is that being built from those primitives, it could be proved as secure as those primitives"
Except that Bitcoin is not a signature system, nor is it a hash function. The only statement that can really be made is this, "Bitcoin's security is dependent on the use of a secure signature system and a secure hash function." Again, look at the email robustness example; a system built from secure cryptographic primitives can still fail to meet its security goal.
"When we give up trusted authorities (and specific "parties" necessarily created by some trusted authority), what remains? What differentiates "the majority" ? One of the few things I see is computing power."
Parties are not created by authorities; parties are what communicate in a distributed system. In the commonly used model, the attacker is allowed to control some number of parties and coordinate their actions; any party, honest or malicious, can scale their computation by some polynomial of the system parameters.
In the case of Bitcoin, parties can enter or leave the computation at any time, without having to send messages to the other parties. That introduces an entirely different challenge, since the attacker can keep adding parties to the system, eventually controlling a majority of whatever capability the parties have. That is not to say that some notion of security cannot be achieved; rather, it means that any notion of security based on a "majority" of anything cannot be achieved without some way to restrict the number of parties the adversary can enter in the system.
The anonymous remailer system faces a similar problem: an attacker can create as many remailers as he wants. In the case of anonymous remailers, however, it is OK for the attacker to control a majority of parties, since it only takes one honest remailer for the system to be secure (i.e. for messages to be anonymized). That should be the goal of Bitcoin: the ability to prevent forgery and double spending as long as some honest parties remain in the system (assuming such a thing is even possible without a central authority; it could be the case that no such protocol can exist).
"Sybil attacks have been defined away, as they depend on some notion of "parties"."
I think the parties in Bitcoin are the people who use it. After all, the point of Bitcoin is to facilitate monetary transactions between its users.
"The "honest parties" wishful-thinking has vanished, leaving only "majority of computation" as the network authority"
No, there is still an issue of "honest parties" versus "malicious parties." Honest parties in Bitcoin are people who are willing to follow the rules and who are not trying to double spend their money or spend money they did not mine/receive. Malicious parties are those who are trying to break the rules by whatever means are available to them. The fact that the majority of computational resources is what decides the validity of the transactions just means that a malicious party needs to collect the majority of computational resources; this is not infeasible, and it is only somewhat impractical (and only really impractical for individual people).
"Of course the merits of this security model are still up for debate, but it seems to mostly work."
It seems to mostly work because nobody with the resources needed to carry out the known attacks cares enough about Bitcoin to do so. The NSA is too busy spying on people to worry about Bitcoin, and companies with large numbers of computers like Amazon or Google are busy using those computers to run their businesses.
This does bring up an interesting point, however: an attacker would only really need such large computing resources during the duration of the attack. The hardware would still be useful after the attack, and the attacker might simply sell it or use it for some profitable purpose. I think the only thing that really prevents fraudsters from doing this is the lack of capital/credit needed to procure the equipment in the first place (let's put it this way: if you were running a bank, would you give a billion dollar loan to someone whose business plan was "defrauding Bitcoin users?").
"Erm, given that the fork was a rare event, it actually shows that Bitcoin is mostly solving the problem, just not perfectly."
The problem is that the fork was caused by parties failing to adhere to the protocol. If Bitcoin is not resilient to parties failing to follow the protocol due to a bug, then it is also not resilient to parties that do not follow the protocol because of a coordinated attack. In other words, Bitcoin is not secure against malicious parties (which are defined as parties that do not faithfully follow the protocol).
> Bitcoin may do this, but it does so by sacrificing rigorous security and offline payments
Both seem like definite hard tradeoffs to me. Offline transactions imply there is some ultimate real-world identity that can be punished for fraud. By "sacrificing rigorous security", I assume you're referring to the majority of CPU power controlling the network. If we give up having a central authority and verified identities, we necessitate some measure of "majority of power" in the system (although it doesn't necessarily have to be CPU).
> a system built from secure cryptographic primitives can still fail to meet its security goal
Sure, but one can formalize the properties of Bitcoin, and could prove that it indeed meets those properties.
One of these properties is "network is controlled by the majority of computing power". I'm not saying this is a universal good thing or ultimate solution. What I am saying is that this property is what provides independence from a central authority, which is possibly what has enabled Bitcoin to actually be adopted.
> Parties are not created by authorities; parties are what communicate in a distributed system
No, "parties" are a convenient abstraction for distributed systems papers in that they bound the pervasiveness of an attacker. The reader intuitively understands them as some notion of identity (IP address, digital certificate, etc), but here we have no luxury. As you later touch upon, once you get rid of identities, a single attacker can create an unlimited number of parties.
I think general MPC has only been proved secure if a majority of parties are honest. Bitcoin is substituting 'parties' with computing power, for precisely the reason you describe. Would we say MPC is insecure because the effort required to attack it (number of malicious parties to establish) is linear in the size of the system (total number of parties)?
I understand this isn't the best security guarantee, but you seem to be having an allergic reaction to it. Complexity theoretic guarantees are useful because they work. However, most real-world power balances are close to linear.
I guess my main point has been that Bitcoin provides a property (authority-independence) that previous ecash papers have not. Its guarantees of this aren't the strongest, but if we're to improve it we must recognize the problem it's solving.
Maybe there's another way of implementing authority-independence that doesn't succumb to something as simplistic as computing power. As it is, it seems that Bitcoin will continue to centralize as miners further specialize and the requirements to be "on the network" (versus transacting through an agent) grow.
"Sure, but one can formalize the properties of Bitcoin, and could prove that it indeed meets those properties."
This seems a bit backwards. Rather than formalizing the properties of Bitcoin, it seems that we should be formalizing the goal of Bitcoin i.e. the properties we want, and then prove that Bitcoin satisfies those properties (if it does actually satisfy them). I think that such a formalization would require a formalization of the entire Bitcoin concept of money, which would probably be beneficial in and of itself.
"If we give up having a central authority and verified identities, we necessitate some measure of "majority of power" in the system"
I think that really depends on your notion of money. If you are like me, you believe that money has value because of its utility: fiat currencies have utility that is defined by a legal system (taxes, debt law, torts, etc.), but one could imagine something else. Suppose, for example, that you had a digital cash system in which the money was redeemable for CPU time in a secure outsourcing system; this could potentially be decentralized. Controlling more computing resources would not give an attacker greater power over the network, but would allow a party to receive more payments (because they are basically selling access to their CPU). It is of course possible that such a system could not be securely realized for technical reasons.
"One of these properties is "network is controlled by the majority of computing power"."
This is not a very precise definition, at least not in the cryptographic sense. What is the formal definition of computing power here -- what is the computation model? It would be very hard to prove that a system has this property in a rigorous way.
On the other hand, in the system I described above, you could formalize the measure of how much work a node did (and how much payment was received) by using circuit families as the computation model and the number of gates evaluated as the measure of work. This sort of abstraction would allow a rigorous proof of various properties of the protocol; e.g. maybe you want to show that the payment a party receives will be some proportion of the number of gates the party evaluates.
"As you later touch upon, once you get rid of identities, a single attacker can create an unlimited number of parties."
Not unlimited; the attacker's ability to enter parties into the system is bounded by the computing power of the attacker. If the attacker can only scale their computation by some polynomial in the parameters of the system, the attacker can only enter some polynomial number of parties. If the protocol is secure as long as there is one honest party, the attacker would not be able to win even under such a scenario.
"I think general MPC has only been proved secure if a majority of parties are honest."
There is a protocol that is secure even if only one party is honest. The problem here is that "secure" does not have a single meaning in MPC. There are various adversary models: an adversary might only be able to choose which parties to corrupt before the protocol runs, or might be able to corrupt parties while the protocol is running; he might be allowed to adapt the attack between the computation rounds and the output round, as in that paper; he might be allowed to compose protocols together in arbitrary ways; etc. Some protocols require a setup phase or an authority, some are standalone (as in the paper), some require a broadcast channel, and so forth.
> you had a digital cash system in which the money was redeemable for CPU time in a secure outsourcing system ... It is of course possible that such a system could not be securely realized for technical reasons
I don't see how it could be possible to design a system were useful CPU work done for others was turned into tokens, as one could simply create a whole bunch of fake work. The fundamental question is who is the counterparty to the tokens? If it's the entity selling CPU time, then you're dealing with a gift card system that doesn't scale to a real currency. If it's not, then you're no longer describing the payment system but have switched to describing an application of it.
> What is the formal definition of computing power here
Clearly it's just the ability to calculate SHA2 preimages. If you want something better, you've got to come up with that formality and an implementation to show that it is practical.
I'm having a hard time responding because it seems like you want to postulate systems with these nice-sounding properties, but it seems apparent to me that you'd never be able to connect them with proofs to make a system. You simply won't be able to build proofs of work for something as simplistic as "number of gates evaluated" (and if you're talking about 'gates' in MPC, you're really just talking about eg group operations).
> If the attacker can only scale their computation by some polynomial in the parameters of the system, the attacker can only enter some polynomial number of parties
What you're describing here is Bitcoin. You've just been spoiled with attackers usually needing exponential resources. As I said, your formalities are misleading you - crypto algorithms may work this way, but not everything does! An algorithm cannot discern good guys from bad guys, meaning they're both on equal footing and the best we can do is have a power balance.
It was great to see in action, but given the way the system is right now it wasn't that incredible.
The maintainers of the biggest pools are all very active in the community; it would just take 2-3 of the big mining pools to say "hey, let's go back to 0.7" for this to be resolved automatically.
I agree. In the past few weeks, Bitcoin has really picked up lots of speed. So much in fact, that I'm wondering whether we're witnessing an exponential adoption where years of people doubting Bitcoin were simply the beginning of the curve. That would also mean that things are going to explode pretty soon.
I sincerely hope that the aftermath of said explosion will leave Bitcoin as the strong contender to established monetary systems that it always was - just "proven by reality" now. That would certainly be all I need to finally jump on board.
Does this mean, that basically any functional change in the block verification code can be used to leverage the hashing power of all users of one version into a 51% attack?
The attack would be essentially to create the current situation artificially by crafting a block that is only valid by one version of bitcoind, therefore splitting the block chain. Then one needs to include two different transactions into the two blockchains. ( In the theoretical scenario, by mining another block for one of the chains. ) For this I do not need to have 51% of the hashing power, but the branch of the blockchain needs to be supported by 50% of the hashing power.
EDIT: Thinking a bit more about this, it seems that the probability to suceed with such an attack seems to rely on the attackers abbility to craft a 'splitting block', which should be proportional to the share of the attacker controlled hashing power and the ability of the 'incompatible' clients to outgrow the standard block chain. ( So that a merchant with an 'incompatible' client accepts a payment based on the fork of the blockchain.) This means that the attack is probably impossible, if the one CPU one vote approach is not only used for valid transactions, but also for valid clients.
Assume that mining reward is approximately equal to investment. This will tend to be the case, though it fluctuates.
Right now we're rewarding 25 bitcoins, at a price of $45, every ten minutes, or $6,750 per hour. Let's say half the required investment is hardware, half electricity at the national average of 11 cents per kWh. Divide 3375/.11 for 30,681 kW power devoted to bitcoin at this moment.
With similar calculations, I recently figured out that if bitcoin were to reach the size of the U.S. dollar in about 20 years, it would be consuming about a gigawatt. It was less than I expected, because the number of new coins per block keeps decreasing, and you only pay electricity for the new ones. This doesn't account for transaction fees, which increase the mining investment that can be sustained. At the moment I think they're a small percentage of the mining award. I'm also neglecting miners' profit margins, which decrease our energy investment.
Coal is 22% of U.S. power production, and generates 2,460 kWh/ton. (30,681 * .22) / 2460 happens to equal almost exactly one ton of coal burned per hour to support bitcoin.
The U.S. generates 227 GW from coal, so our 6.7 MW is about one part in 33,000 of total U.S. coal consumption.
Sources: just type questions into google and all the numbers come right up. I assumed, perhaps incorrectly, that U.S. numbers were more typical of the bitcoin population than global numbers.
Math goof, can't edit: 30,681 * .22 is 6750 kWh, which divided by 2460 kWh/ton is of course 2.74 tons of coal per hour, not sure how I came up with 1 ton.
The same could be asked of most any form of currency and of many different ways of generating wealth and value (and I'm sure many of them generate orders of magnitudes worse pollution).
Take, for example, reddit karma - people pay to power their computers and purchase hardware/software to create memes and original content that will reap positive karma. What notion or idea will be "valuable" to the reddit hive mind next is anyone's guess, so your best bet is to keep plugging away at it and generating as much original content as possible. While there's no direct translation of earned karma to a national currency (yet), it can carry a social/fame value.
These people paying their internet, hardware, software, and electricity bills provide a basis for an exchange rate of <national currency> to <reddit karma>.
The only differences between this and bitcoin are that people can give bitcoin to one another and that there are bitcoin to <national currency> exchanges.
I stretched the analogy a bit thin with reddit karma, but I'm sure people can think of other similar electricity->money "pure technology" wealth/value generation methods (high frequency trading hardware/software, for instance).
What you say is true but bitcoin is specifically designed to require massive amounts of computing power, which specifically equates to massive electric power consumption.
In other words its purposely designed to be excessively taxing on resources.
The other activities you mention have resource consumption as a side effect and not necessarily exhaustive.
A lot of electricity is used on other forms of security as well, such as SSL or password encryption. Although SSL uses up less resources, it is used by far more servers, which I suspect would exceed the amount of processing power of the Bitcoin network.
Individually SSL takes less CPU time, but in aggregate there is an awful lot of SSL traffic in comparison to Bitcoin. I suspect that overall the cumulative amount of CPU time spent on more conventional cryptographic security far exceeds the CPU time spent on Bitcoin's blockchain.
The difference is that Bitcoin creates strong incentives for people to burn through electricity. Worse still, for Bitcoin to be secure it has to be the case that no attacker can control more than half the total computing power of the entire Bitcoin network, which means that the network can only be secure if people keep devoting more and more computer power to it; doubling the attacker's work means doubling everyone's work. Compare that to Chaum's digital cash systems -- where tokens were issued at low computational cost by a bank, transactions were peer to peer and did not require connecting to a global network of any kind, and where the attacker's work was exponential while the users work was polynomial in an arbitrarily-scalable security parameter. Bitcoin is exceptionally wasteful of computing resources; if it were a mainstream currency, we would eventually have to commit half the world's total computing power to it just to keep it secure.
If the cost of electricity is more than the value of the awarded coins, miners will drop off because they're losing money, and the difficulty will decrease.
Therefore the total electricity usage per ten minutes cannot sustainably be worth more than the value of the new coins generated in that ten minutes. Meanwhile the number of coins awarded each time is cut in half every four years. If, in 20 years, bitcoins are worth 32 times as much as they are right now, the total electricity usage will be the same as it is now.
The amount of electricity used is surprisingly low; for details see my comment above.
Edit: with further thought, I wonder whether this is a long-term security flaw. Previously I calculated that if bitcoin were to reach the market cap of the dollar in 20 years, it would consume a gigawatt of power. An attacker with a nuclear reactor could conceivably control a blockchain with over a trillion dollars of market value.
Transaction fees would make it more expensive (by increasing the power usage sustainable by honest miners) but the hope is to keep fees fairly low.
However, a 51% attack still doesn't allow the attacker to steal all the money, only to double spend. So the attack may not be worthwhile, unless you already have very large bitcoin holdings...in which case, you may be more interested in maintaining the soundness of the currency.
>>If the cost of electricity is more than the value of the awarded coins, miners will drop off because they're losing money, and the difficulty will decrease.
Is that assumption correct? I am not as knowledgeable as you are, but I would reason differently. As the size of the BC economy expands, vested parties will have increasingly strong motivation to secure their investments; likewise for attackers. A mining arms race will ensue, whose costs in power usage will have little to do with the ROI from mining. Costs will have to scale roughly with the value of the economy. Today, the miners went out of their way to save the network for the general good - thank you. Tomorrow we might have to incent them to continue do so.
True, and as the value of those potentially doubly-spent coins increases, so does the cost of preventing such an infraction. This is necessary to protect the at-risk merchants whose presence on the network is vital if BC is to succeed.
Also, massive loss of confidence resulting in destruction of the value of my assets would have the same net effect to my wallet as theft.
So, it is in our general interest that BC transactions by required to pay into a commonwealth of miners who will burn GPU for us. This should be taken out of the now-optional transaction fee. Satoshi apparently had anticipated this. Under such circumstances, I believe your models of power consumption are heavily understated.
Given that there's nobody who can force any particular action, it'd be interesting to think through the game theory and whether that's actually likely to happen.
An assumption I have made is that most merchants in the "normals" category would demand near-as-dammit watertight protection from theoretical yet systemic risks. FUD from competing systems would drive this requirement. I cannot imagine a lab experiment to test my assumption; it would need to be demonstrated in the marketplace. The cost of providing a very strong defence is entirely disproportionate to cost of offence, so we are looking at an asymmetric arms race.
Many Game Theory experiments are concerned with discerning underlying morality in economic exchanges. An interesting perspective here is that there should be no room for morality when Bitcoin gets up to scale. (But thanks again for the good guys who saved the day this week). No black/white hats; only those who have been paid to protect and those whose interests lie in exploitation. Eventually no actor will have the resources to do the right thing, unless it is also explicitly in their short term material interests. That ethos seems to be prevalent in the Bitcoin and one of the reasons that I find it interesting to watch.
This line of reasoning reminds me of an anecdote about the German cryptographers' reaction to the Enigma code-breaking program. They were not shocked by the fact that the machine had a weakness; what they were shocked by was the fact that anyone would be willing to bear the cost of exploiting that weakness.
You might be surprised by the attacker's motive or by their willingness to invest in the resources needed to attack the system.
I might not be all that surprised, given that I just dreamed up this potential weakness in the first place. It's entertaining to speculate on who might be willing to spend billions of dollars and lose additional billions in market value, for the sake of damaging the network. But I think it would be difficult to directly profit by doing it.
That is completely stupid given the existence of other secure digital cash systems that support offline payments. Go implement Chaum's work if you do not trust banks to facilitate transactions, and you'll get a more secure and more robust currency at a lower energy cost than Bitcoin.
"Well DigiCash failed. Bitcoin is succeeding. That speaks of itself as to which system is better designed..."
Really, you think that success in the market is indicative of a system having a better design? You must not be paying attention to the market then, or to the forces that affect the market. Better designed products and systems fail where their poorly designed competitors succeed all the time.
"By "secure" I meant secure from governments seizing accounts, financial companies restricting transferts, etc."
That's nice, but I doubt you would use Bitcoin if there were easy double spending attacks.
I do use Bitcoin. I have been for 2+ years. I do so because I trust its design. I do not believe it is easy to double spend bitcoins. Yesterday's chain fork is an extremely rare and short-lived event.
From news in #bitcoin-dev, it looks like miners on 0.8 are being instructed to downgrade to 0.7, and that'll be the winning fork of the chain going forward. There shouldn't even be any lost bitcoin transactions.
There shouldn't even be any lost bitcoin transactions.
That can only be true if there are not conflicting transactions in the two chains. That might be the lucky outcome, but it's certainly not guaranteed to be the case.
Any transactions that were confirmed on the faulty chain will have to be re-confirmed in the correct chain. How long that will take would depend on just how many transactions need to be processed, and how big their payload is. Until that is completed, the state of the bitcoins involved in those transactions is ambiguous.
Because "intrinsic value" is not as important than just "value". Bitcoin has a value in the sense that people can use it as a currency that has features that are desirable and useful.
The asset's capacity to facilitate economic trade causes individuals to store it so that they can participate in such exchanges when opportunities present themselves.
The sane price is the total amount of such wealth that individuals are storing or will store in the future, discounted for time, divided by the number of such assets.
Wild runs are typically- not by requirement, but typically- indicative of a crash in the near future. This is because speculation is usually the main driving force behind very steep ramps.
As has been shown time and time again in academic and corporate research, the single best predictor of an asset's value is the current market trading price for that asset.
You are establishing a pattern of responding to comments with maximal brevity and offering zero constructive input.
Ok, so you think RickHull was using "Exceedingly rudimentary technical analysis based on non-scientific trends"? What have you got for us that is so much better?
IMHO, bitcoin appeals for various reasons that compare favorably with national currencies such as the USD. Those reasons being: anonymity, ease of use, and freedom to send my money any where in the world.
err... I think I disagree on those first two points.
Managing a wallet in a manner that won't result in it getting stolen (as in, disconnected from your main machine) is not easy. Though I suppose tools can be created to make this easier, they don't exist yet.
Also, bitcoin is very traceable. Publicly traceable even. You know which group is getting what, when, and once you ask those recipients for who, you know who's being getting what, when, where, and maybe a bit about how much they have.
Apparently this can be improved? I have no idea how without trusting someone.
I think there are ways to obfuscate who owns what, e.g. always use new addresses and send your coins around a few times to other addresses to hide the true origin. As far as I understand it, it's very hard to track that kind of obfuscation (though certainly not impossible, sure).
As for managing your wallet, you could use a service like coinbase.com. They keep their coins offline. And you could browse to their site through Tor.
> As far as I understand it, it's very hard to track that kind of obfuscation
You understand it incorrectly, then. Bitcoin is not anonymous and transaction flows through the network are very easy to trace. Additionally, it is very easy to link specific transactions to regions or even specific network addresses/services.
Yes, it's not inherently anonymous. But it is possible to obscure the owner of the coins. It's not foolproof, but it probably makes it a little harder to figure out who is doing what...
Slightly off-topic, but it is well-known that one can embed arbitrary data in the bitcoin block chain, so you pretty much have to expect that at some point someone will inevitably insert one of the many illegal numbers into it, putting everyone running it openly at risk, regardless of the political attitudes towards bitcoin itself. I know anonymity isn't one of bitcoin's purported purposes, but I think it will ultimately be necessary to make it one because of this.
Anonymity would not necessarily solve this problem. Just because you cannot correlate 2 transactions or a transaction with a person does not mean that you cannot allow people to embed arbitrary data.
Sorry for the confusion. I mean't anonymity of operation, not of transactions. The anonymity I'm talking about could be achieved by running Bitcoin over Tor (which most people don't do yet, and which clients aren't really designed for), or integrating something like Tor in the client. Either way, the possibility of such an attack (an "illegal number" in some jurisdiction), IMHO, means the Bitcoin community has a vested interested in anonymity of those running the client. Of course, that's also true for political reasons... Politicians and banks already don't want an unregulated currency. However, I still view that as hypothetical threat to Bitcoin, whereas illegal numbers pose an immediate threat: anyone with Bitcoins to spend can insert something that would make running the Bitcoin client (participating in verifying the blockchain) a liability. The easy example is illegal pornography, but people could also use it for state secrets, which would likely get a more forceful military response. This could cause a massive market crash in a heartbeat, with very little skill. IMHO, it's bound to happen as soon as someone finds himself in a position to profit from a total Bitcoin crash. It's a glaring Achilles' heel.
>If this is a widespread problem, it is an emergency. We risk having (several) forked chains with smaller blocks, which are accepted by 0.7 nodes. Can people contact pool operators to see which fork they are on? Blockexplorer and blockchain.info seem to be stuck as well.
So, what would happen to the coins used in those forked transactions? If the chain does fork what would the best strategy be for performing the merger?
And more interestingly: since bitcoin transactions are considered to not be reversible bitcoins are easily converted to and from other currencies with non-reversible transactions. If one were to convert his or her bitcoins to, e.g., Liberty Reserve right now and the chain got reversed that would result in pretty much a perfect scam, wouldn't it?
The chains do not get merged. It is just, that the longest block chain is the consensus history of all transaction ( and it needs to be consistent). So if the .7 branch overtakes the .8 branch, then legitimate clients will detect that a transaction was not carried out and retransmit it. ( And the scam you are describing is precisely why Mt Gox did stop accepting bitcoins. They are afraid that someone can take advantage of the situation.)
This is the first large occurrence of an issue that has always been known to be possible to people who are reasonably familiar with BitCoin, due inherently to it's design. This could be bad for BitCoin because now a much large portion of BitCoin users/investors are also aware of this risk.
The difference is that enough people accept the current system without understanding it that you can use it for your needs. Not enough people use bitcoins that you can gloss over details.
If the Bitcoin monetary system breaks, only those using Bitcoin for savings or investment get hurt. Those who use BTC as a means of payment (buyers and sellers) have little reason to care, so long as they frequently convert excess BTC into other currencies.
That's not so different from the U.S. dollar. You can buy and sell stuff using U.S. dollars, but unless you foresee the value of USD going up (a kind of deflation), you don't want a pile of USD under your mattress. (Also, it's uncomfortable.) Depending on your economic outlook, you want the money in something else: metals, some sort of investment vehicle, or a basket of [foreign] currencies.
This is for the miners, people with more knowledge about the inner workings of Bitcoin than the average user.
The advice for users is wait until we have a definite dominate blockchain and continue on as normal. Users do not need to downgrade, upgrade or do anything else. This is a miner issue.
There was a fork in the blockchain, and the community will have to decide how to resolve it. Some transactions which were "confirmed" could be reverted.
The good thing about this is that there is no major conflict among people regarding which block-chain is correct. Almost everyone agrees that we need to solve the problem of having a huge portion of nodes not being compatible with the current block chain. Only one of the two blockchains meets this criteria.
I was asleep when this happend, but waking up to check HN, reddit and my mtgox got me up to speed. For some reason, this doesn't worry me a bit. Mostly because of the steady and strong growth I've see recently.
Prices have been above $36 for barely a week, 5th/6th rally saw high volumes; the recovery (8th to 11th) was weaker and did not break the high. The volume of both sell-offs was comparable, but the today's low is higher. I reckon it might flatten out around $40 for a bit, then pick up again.
How could this possibly result in Bitcoins going up? Even if this is handled without any hiccups, this should shake a lot of people's faith (myself included).
This should be a wakeup call for anyone that thinks that Bitcoins are totally secure. What if next time the bug in the client is more exploitable? Someone malicious could potentially take out the entire Bitcoin economy in one day by exploiting it.
Only because the community is so small that telling "everyone" to downgrade to 0.7 is actually doable. Now imagine a future where everyone uses bitcoin - imagine getting an institution like a bank to get on the "right" version...
While dropping to v0.7 was a method to resolve this in a manner which protected v0.7 users it wasn't necessary. Miners could have continued to mine v0.8 chain. Transactions from the v0.7 blocks would be included in v0.8 blocks.
Users could be warned to STOP using v0.7 and upgrade to v0.8. The advantage of downgrading it is resolve the situation quicker. Far easier to get a half dozen mining pools to switch to v0.7 then get thousands (tens of thousands) of users to upgrade to v0.8. A v0.7 user who followed the warning and stopped engaging in transactions either until v0.7 was the longest chain or until they upgraded to v0.8 was not in any danger. Existing transactions flowed across both halves of the split.
Well, I thought that limited access to bitcoins may result in price going up. But as I see, there is a panic on the market, so btc/usd is dropping quite fast.
It depends how it is resolved. If no one loses money, then yeah, it could go up. Otherwise people could lose confidence in Bitcoin and the price could plummet.
After all this is "dealt" with if they are still in limbo use something like pywallet to fix the coins in limbo (if there are still no confirmations after hours)
thanks for the reply. I always have bitcoinity open. (dark theme FTW).
The answer to the question I was trying to ask is https://coinbase.com/network/blocks which enables me to check in on how far behind the future legitimate blockchain is (7 blocks at time of writing).
A block was mined (by the Slush mining pool) which is accepted as valid by 0.8 clients, but rejected by 0.7 clients. More than half of the mining power was on 0.8, so the longest chain includes this block - but the 0.7 clients reject it, and have built a side-chain. The developers have asked all miners and mining pools to switch from 0.8 to 0.7, so that the 0.7 chain will grow to be longer than the 0.8 chain; once this happens, all Bitcoin clients will agree that it is the real one. In the meantime, however, merchants running Bitcoin 0.8 may be targeted by double-spend attacks: if they receive money in a transaction that exists only in the 0.8 blockchain, the same money is spent in a different way on the 0.7 blockchain so the transaction can't just be copied over, and they act on the receipt of money by sending goods before the situation is resolved, then they could lose money. This is why MtGox has suspended Bitcoin deposits. (This can only happen if the coins were sent by someone who is using malicious, nonstandard software; transactions made by honest users will be copied to the 0.7 fork and mined without any issue.)
The height of the two chains can be monitored at https://coinbase.com/network/blocks . Currently the 0.7 chain is 13 blocks behind, which (since the normal mining rate is 6 blocks per hour) sets a lower bound of about two hours on resolution - assuming everyone switches their mining power immediately - but realistically it will probably be more like 6-12 hours.