Stopping an attacker who has >50% of the hashing power

[ByteCoin]

Bitcoin has been running successfully for over two years. Honest miners have generated over 120000 blocks. As admitted by Satoshi, if a well funded attacker develops a hashing ASIC or otherwise buys or gains access to >50% of the hashing power (by DDOSing some pools?) then all that honest historical hashing work doesn't matter one bit, Bitcoin belongs to the attacker.

This seems a shame.

Wouldn't it be nice for the honest mining done in the past to hinder the immediate takeover of the network by the attacker?

This can be achieved in the following scheme:

Miners which have previously won a block in the distant past get a discount on the difficulty of mining the current block.
The size of the discount increases with the age of the previously won block.
Once a new block is mined with the help of the discount from the old block then the old block is "spent".
Proof of ownership of the old block is proved by signing with the same address that the old coinbase credited.
Bitcoin maintains a discount difficulty target which varies over a short timescale with the aim of maintaining a fixed ratio of discounted blocks to normal blocks.
If the proportion of discounted blocks falls too far (so that the discount rises too much) then the overall difficulty is raised over a short timescale for that branch of the block chain.

If an attacker arrives with >50% of the hashing power then they will be able to generate enough normal blocks themselves to make sure they have the longest chain branch. However, they don't have any historical blocks (or their recently generated blocks have a zero or negative discount) so the recent proportion of of discounted blocks falls to zero. This acutely raises their difficulty on the attacker's chain branch and the attacker's generation rate falls precipitously.

Normal, honest miners recognize blocks generated by the attacker by observing the attempted double spending and chain reorgs. It's crucial that they don't contribute discounted blocks to the attacker's chain branch, so they ignore those blocks and continue building off the honest chain branch. Quickly, the attacker's chain branch is overtaken by the honest chain and the attack fails.

I believe that this scheme with correct parameters would prevent sudden takeovers by attackers with 95% or more of the hashing power.

Gradual attacks by an attacker who generates enough old blocks to maintain the discount proportion are not prevented but at least the attacker is supporting the honest network while generating the "old" blocks prior to the attack!

There are lots of vital details to thrash out but I believe the idea is sound and useful.

ByteCoin

[Gavin Andresen]

Neat idea!

I don't like the economics of it, though.

First, it reinforces the "if you started mining early you are rich only because you were lucky enough to be early" idea.  And a lot of people already think that is unfair; give the early miners a current mining discount and you're just "helping the rich get richer."

Second, what stops an attacker from offering early miners $$$ for their (already spent) coinbase private keys?  If they have value because they give a mining discount, then there WILL be a market for them.  A wealthy attacker could just buy up as many as they can find and then take over the network with less hashing power...

[casascius]

If honest miners looked at the transaction queue and rejected blocks that didn't contain transactions that could reasonably expected to be there, they could reject the block.  If someone with >50% of the power wanted to generate blocks and specifically exclude transactions that belong, and this bit of logic were added, most honest nodes could reject their blocks, and even if those blocks were long and numerous they would basically be forking their own chain and wouldn't be noticed, no matter what their size.

[slurch]

I was just thinking about this, and it seems like a simultaneous DDOS on the pools could be mitigated with a little miner code...say, if the pool you are in is inactive for a period of time due to a DDOS, it could automatically launch the Bitcoin client and switch you to a local mining state where you are still contributing to the network in an honest capacity (as opposed to spinning your wheels). I'm no programmer, so I have no idea if this is feasible...but it could be?

[caveden]

Bitcoin has been running successfully for over two years. Honest miners have generated over 120000 blocks. As admitted by Satoshi, if a well funded attacker develops a hashing ASIC or otherwise buys or gains access to >50% of the hashing power (by DDOSing some pools?) then all that honest historical hashing work doesn't matter one bit, Bitcoin belongs to the attacker.

Please, this is exaggerated. Stop propagating fear.
Bitcoin would not "belong" to the attacker. The only thing such attacker would be able to do is rewrite recent transaction history, and with that, double-spend. That is: big annoyance + potential to fraud against some victims with bad luck. Ok, it's not good, but it's way less harmful than "Bitcoin belongs to the attacker".

Now, about your suggestion, I don't think it'd work. Miners would spend their difficult discount as soon as they can use them on their advantage, meaning they wouldn't cumulate much anyway to resist the attacker. And the attacker could honestly mine for some months before turning rogue.

Much easier and straightforward than that, IMHO, would be to periodically mark old blocks. It should be possible to calculate the chances of a honest chain split, and also calculate the probability of a honest split lasting a certain amount of days. For example, I believe that a honest split would never last an entire week, or maybe even much less than that - but it would be nice some math to demonstrate that of course. Suppose it's true. People could agree to, every week, mark the block produced one week in the past. Only chains containing the marked block would be treated as valid. This way, the most the attacker could do is to revert one week of transactions - that would be resent anyway. So this makes politically motivated attacks quite silly. And regarding profit oriented attacks, there wouldn't be much margin for double-spending in this short time window. The costs and risks of getting caught would probably outcome the potential benefits of such fraud.

EDIT: Just trying to explain better what I meant, maybe marking once a week was not the right way to say it. The best way to do so is to make block reorganizations that rewrite a number of blocks higher than a constant C illegal. If a node receives a larger block chain which rewrites more than one week of blocks, for ex., it just ignores this longer chain and stick with the shorter one.

[eMansipater]

"Long" takeovers are already very predictable, and trivial to prevent algorithmically as long as there is not severe fragmentation of the network.  "short" takeovers are mathematically very difficult to differentiate from genuine issues.  It's hard for me to think of anything offhand that addresses the "short" takeover problem better than Satoshi did.  Cool ideas though!

[Nefario]

If your car keys ever fall into a river of lava, just let them go, cause man, they're gone.

[Mike Hearn]

Bitcoin would not "belong" to the attacker. The only thing such attacker would be able to do is rewrite recent transaction history, and with that, double-spend.

Well ..... this isn't correct if you assume most users end up on clients implementing simplified payment verification - which is how Satoshi imagined the network would evolve and I agree that's the likely route (who knows, perhaps even using BitCoinJ as the dominant codebase). An attacker who can dominate the network can make SPV clients believe almost anything. They can create value out of thin air, for example. Running a full node is already kind of painful due to the long initial startup and in future, it'll get even more so as the transaction rate increases.

That said, the people most at risk of tx reversal are merchants, and running a full BitCoin node will certainly always be less painful than complying with the PCI requirements today. So perhaps it won't really be an issue.

Much easier and straightforward than that, IMHO, would be to periodically mark old blocks.

This is already done in an ad-hoc way with the checkpointing system. Currently checkpoints are hard coded into the client. I'm toying with the idea of allowing downloads of signed "last known good block" hashes from a remote server in BitCoinJ so you can stay on a chain even if there's a longer one available.

I like the way ByteCoin is exploring alternative voting rules, but any changes to this part of BitCoin frankly scare me. The current rules are very carefully thought out and have been studied over a fairly long period of time now. Changes to it have the potential to introduce complicated new problems nobody anticipated. Frying pan, fire, etc.

[caveden]

Well ..... this isn't correct if you assume most users end up on clients implementing simplified payment verification - which is how Satoshi imagined the network would evolve and I agree that's the likely route (who knows, perhaps even using BitCoinJ as the dominant codebase). An attacker who can dominate the network can make SPV clients believe almost anything. They can create value out of thin air, for example. Running a full node is already kind of painful due to the long initial startup and in future, it'll get even more so as the transaction rate increases.

Wait, if I understood you correctly, this is another issue. You're saying that light-clients may be tricked if their server is compromised. That's true and indeed dangerous, but it has nothing to do with an attacker with more computing power than the honest network of miners. An attacker of this kind has no way of creating more new bitcoins than what the protocol allows, for example.

I like the way ByteCoin is exploring alternative voting rules, but any changes to this part of BitCoin frankly scare me. The current rules are very carefully thought out and have been studied over a fairly long period of time now. Changes to it have the potential to introduce complicated new problems nobody anticipated. Frying pan, fire, etc.

Surely. That's why I said a mathematical demonstration of the soundness of the change would be welcome.... but that's for researchers I'd say...

[gigabytecoin]

If your car keys ever fall into a river of lava, just let them go, cause man, they're gone.

You must play minecraft.

[forgotmypassword6x]

this is an absolutely terrible idea, in addition to the reasons gavin mentioned, because your "fix" has just actually allowed an attacker to take over the network with much less than 50%.  If your system means 95% of new clients cannot control the network, then 5% of old clients can.  So the 5% oldest miners just get together and collude to doublespend.

[AntiVigilante]

This is a great concept with a bigger hole. Unintended consequences will never be the same.

Instead I'd suggest something involving transactions and difficulty.

I'm starting to think the best option is the political hack perpetrated 235 years ago.

Separation of powers, bicameral decision making. Miners, speculators, traders, lenders. Miners and speculators seem like one and the same given recent predictability in dips and spread squeezes. Traders of various products and lenders can restore some spectrum to the market.

We should be making sales at different times because we want a profit on our investments not merely me too buying and selling. Once that becomes chaotic enough mix that with the defense against attacks.