Proposal: Pre-emptive measures against 51% attacks

[casascius]

Was thinking a bit... about what would happen in the event of a 51% attack.

Imagine a 51% attack against Bitcoin that was begun in secret, to create a large alternate chain that simply reversed a very large number of blocks, and persistently prevented any transactions from confirming.  The chain would be published all at once as a surprise and would propagate across the network faster than any worm.

Even if many of us could deal with that, the news would say "BITCOIN HACKED", that would be the end of Bitcoin as we know it, at least for a short while, until we all scattered around and figured out what to do about it.  

The problem with a 51% attack done this way is its effects would be sudden and instant.  The repair would be several days while the developers figure out what to do, and several more while the bugs get fixed, and plenty more time while people download it, repair their block chains, backport the patch to their customized clients, get back in business... meanwhile, we'd have lots of angry miners whose mining work on the fake chain got reversed, etc...

I would like to propose a couple simple things now relating to checkpointing so that the solution is known and the disaster preventable all the way in advance.

Basically, what I am proposing is that a) trusted entities put signed checkpoints in the block chain - which are nothing more than assertions that "I have seen the block with hash x", and b) that the client have some sort of list of trusted public keys (modifiable by power users, but otherwise pre-seeded by client authors) so that trusted parties can be recognized but also removed if needed.

Signatures would appear periodically in blocks, which would be part of real or dummy transactions.  MtGox, for example, may occasionally initiate a transaction to itself (or embed in one of its payout transactions) a signature referencing the hash of a prior block, simply to say "I saw this".  MtGox need not sign every single block - since each signature acknowledges all blocks before it, there will be other signers participating, and the scheme is mainly targeted at attacks on 6+ blocks, the signatures could be done three or ten or any other reasonable number of blocks apart.

Mining pools would do the same except would likely use the coinbase transaction as the location for their signature.

Very simply - if I as a client have block X, which I know has been seen by MtGox, TradeHill, and a dozen mining pools and trusted parties... I can quickly and confidently reject block Y which purports to replace block X with a higher proof of work.

To implement this proposal, all that would need to happen is:

• client gets a mini database to track trusted public keys, possibly kept in wallet.dat, but pre-seeded from hardcoded values in the client
• client gets an RPC call to modify this database for power users
• definition of "standard transaction" amended to include one that packs an OP_DROPped signature so that trusted parties can count on their stamps of approval being relayed
• the logic for handling chain reorgs more than 3 blocks deep is revised such that blocks known to have been seen by a majority of the trusted crowd are impervious to being preempted by blocks that have not.

The vast majority of client users would be using the default list of trusted public keys and would be unlikely to modify it, so the onus would be on the authors of clients to appropriately judge who belongs to be on the list.  The idea of allowing the client author to update the list remotely isn't out of the question - a suggestion probably not appropriate for the reference client - but entirely plausible for smaller-time clients whose users could just quit using if the authors were up to shenanigans.

[1714694233]

1714694233

[1714694233]

1714694233

[1714694233]

1714694233

[ByteCoin]

Very simply - if I as a client have block X, which I know has been seen by MtGox, TradeHill, and a dozen mining pools and trusted parties... I can quickly and confidently reject block Y which purports to replace block X with a higher proof of work.

As long as the blocks contain adequate proof of work, they are all eligible to be accepted. It's not a beauty contest where the one with the highest proof of work wins. The reasoning works if we replace "block" with "blockchain" on the basis that longer blockchains are preferred.

Suppose the bitcoin network divides into two roughly equal portions in terms of hashing power and trusted parties but without any attack. Life goes on for a while at roughly half the block rate and with half the trusted signatures missing. When the network reconnects what happens to the losing chain and the trusted parties' signatures of the losing chain's block hashes?

ByteCoin

[casascius]

The signatures only mean "I saw block X".  If block X is unknown or ends up being rejected, the signature then means nothing. the signature doesn't sign the block it is in, it simply acknowledges receipt of some other (earlier) block and is still a valid transaction in any block it gets put in.

In the event of a bona fide net split, where exactly half the trusted parties get separated from the other half, neither chain will meet the threshold of having a sufficient majority if the threshold is set any higher than half - so the longest proof of work would win as it does now.

[iddo]

So if those few "trusted parties" are malicious then they can carry out a double-spending attack even though they have a tiny proportion of the total hash power, by preparing their own fork and signing it? I think that this is a bad idea, both in a technical sense, and from a PR standpoint.

For example it could take those malicious parties one day to prepare a secret fork of 6 blocks, while the rest of the network generated 144 blocks during that time, and still the malicious fork of 6 blocks will win?

You didn't describe which threshold of trusted parties would be needed? If all the parties are required then a single malicious party could cancel the entire scheme, and if a majority of the trusted party is required then a malicous majority can double-spend, etc.

And equating mining pools with trusted parties is a step in the wrong direction imho, it would be better to think of ways to enhance security of the overall bitcoin network by decentralizing the power of mining pools, rather than giving them more power. This was discussed at https://bitcointalk.org/index.php?topic=9137.0 , as well as p2pool, and there's also the idea of preventing mining pools at protocol level by requiring that if you have (privkey,pubkey)=(sk,pk) and block reward address corresponds to pk then you try to generate the block by: hash(txns,nonce,sign_sk(txns,nonce))

Edit: on a more basic level, if we officially condone having an easily modifiable list of trusted nodes as being a correct behavior of honest clients, then in the scenario where the mining power is truly decentralized it means that it becomes easier to have clients who don't follow the same rules, i.e. more possibilities for forking the chain.

[casascius]

So if those few "trusted parties" are malicious then they can carry out a double-spending attack even though they have a tiny proportion of the total hash power, by preparing their own fork and signing it? I think that this is a bad idea, both in a technical sense, and from a PR standpoint.

Most of those trusted parties aren't mining, so they wouldn't really have the means to carry out the attack.  Remember, they'd already have to have 51% of the mining power, and in my proposal, they'd have to have 51% of the "trust" (however that is allocated).  This ups the ante even more.  A lot of other trusted people simply won't sign a new chain of replacement blocks that just show up out of nowhere, as a matter of policy.

Someone with a policy of "I sign the first thing I see right away as I see it, and I am trusted only so long as I continue to do so" will have self-prohibited himself from signing an alternate chain that replaces blocks, because by doing so he would have met the conditions to delete himself as a trusted person.  Decentralization doesn't mean "trust nobody"...could you see MtGox or Gavin trying to do a double spending attack?

For example it could take those malicious parties one day to prepare a secret fork of 6 blocks, while the rest of the network generated 144 blocks during that time, and still the malicious fork of 6 blocks will win?

I expect there should be far more trusted parties than to make this feasible.  But let's suppose that happened.  We would know exactly who those parties were, we'd dump them from the trust list, and then they would never have a second opportunity.  Sure, Bitcoin might get some bad press, but it would also prove that the contingency plan worked.  They wouldn't gain anything in the process.

You didn't describe which threshold of trusted parties would be needed? If all the parties are required then a single malicious party could cancel the entire scheme, and if a majority of the trusted party is required then a malicous majority can double-spend, etc.

I left it vague on purpose.  A majority, sure.  But remember there's more factors that a client can use to weigh two competing chains of blocks - Gavin enumerated a few on another thread.  A flexible algorithm would be desirable over a hard and fast rule.  If I have chain A and chain B competing with one another, and chain B is longer, doesn't contain any double spends against A, and contains everything from chain A, I (as an algorithm) probably should just consider choosing chain B without worrying much about majorities.  On the other hand, if 6 blocks come along and purport to be better than 144 they want to replace, they may merit needing a much higher percentage of the trust than even 51% to be acceptable.

And equating mining pools with trusted parties is a step in the wrong direction imho, it would be better to think of ways to enhance security of the overall bitcoin network by decentralizing the power of mining pools, rather than giving them more power. This was discussed at https://bitcointalk.org/index.php?topic=9137.0 , as well as p2pool, and there's also the idea of preventing mining pools at protocol level by requiring that if you have (privkey,pubkey)=(sk,pk) and block reward address corresponds to pk then you try to generate the block by: hash(txns,nonce,sign_sk(txns,nonce))

Trust doesn't mean a block is assumed valid just because it was signed by someone special (unlike SSL for example, which does work this way, much to our demise).  In this sense, a signature only means "I saw this block".  I as a client should prefer a chain that I know has been seen by a lot of stakeholders, over one that has been seen by none.  Having mining pools sign blocks helps everyone confirm that the mining pools are still in contact with one another and that there isn't a "net split".

Edit: on a more basic level, if we officially condone having an easily modifiable list of trusted nodes as being a correct behavior of honest clients, then in the scenario where the mining power is truly decentralized it means that it becomes easier to have clients who don't follow the same rules, i.e. more possibilities for forking the chain.

I don't see how it follows.  This proposal doesn't create forks, it simply provides an element of human control over how to deal with forks if and when they happen.  They have to happen first on their own, either deliberately as part of an attack, or unintentionally if there are disconnects in the network.

[fastandfurious]

Was thinking a bit... about what would happen in the event of a 51% attack.

Imagine a 51% attack against Bitcoin that was begun in secret, to create a large alternate chain that simply reversed a very large number of blocks, and persistently prevented any transactions from confirming.  The chain would be published all at once as a surprise and would propagate across the network faster than any worm.

Even if many of us could deal with that, the news would say "BITCOIN HACKED", that would be the end of Bitcoin as we know it, at least for a short while, until we all scattered around and figured out what to do about it.  

The problem with a 51% attack done this way is its effects would be sudden and instant.  The repair would be several days while the developers figure out what to do, and several more while the bugs get fixed, and plenty more time while people download it, repair their block chains, backport the patch to their customized clients, get back in business... meanwhile, we'd have lots of angry miners whose mining work on the fake chain got reversed, etc...

I would like to propose a couple simple things now relating to checkpointing so that the solution is known and the disaster preventable all the way in advance.

Basically, what I am proposing is that a) trusted entities put signed checkpoints in the block chain - which are nothing more than assertions that "I have seen the block with hash x", and b) that the client have some sort of list of trusted public keys (modifiable by power users, but otherwise pre-seeded by client authors) so that trusted parties can be recognized but also removed if needed.

Signatures would appear periodically in blocks, which would be part of real or dummy transactions.  MtGox, for example, may occasionally initiate a transaction to itself (or embed in one of its payout transactions) a signature referencing the hash of a prior block, simply to say "I saw this".  MtGox need not sign every single block - since each signature acknowledges all blocks before it, there will be other signers participating, and the scheme is mainly targeted at attacks on 6+ blocks, the signatures could be done three or ten or any other reasonable number of blocks apart.

Mining pools would do the same except would likely use the coinbase transaction as the location for their signature.

Very simply - if I as a client have block X, which I know has been seen by MtGox, TradeHill, and a dozen mining pools and trusted parties... I can quickly and confidently reject block Y which purports to replace block X with a higher proof of work.

To implement this proposal, all that would need to happen is:

• client gets a mini database to track trusted public keys, possibly kept in wallet.dat, but pre-seeded from hardcoded values in the client
• client gets an RPC call to modify this database for power users
• definition of "standard transaction" amended to include one that packs an OP_DROPped signature so that trusted parties can count on their stamps of approval being relayed
• the logic for handling chain reorgs more than 3 blocks deep is revised such that blocks known to have been seen by a majority of the trusted crowd are impervious to being preempted by blocks that have not.

The vast majority of client users would be using the default list of trusted public keys and would be unlikely to modify it, so the onus would be on the authors of clients to appropriately judge who belongs to be on the list.  The idea of allowing the client author to update the list remotely isn't out of the question - a suggestion probably not appropriate for the reference client - but entirely plausible for smaller-time clients whose users could just quit using if the authors were up to shenanigans.

Casascius, I really don't think people understand how important it is to understand what your proposal is saying. For me when thinking about it, it says exactly what will be the doom of Bitcoin it this in some way wont get implemented in the future.

I am sure that your proposal of checkpoints of trusted entities is pretty much unnecessary when the total market cap of Bitcoin is $100M or even as much as $1 Billion, but the question is what this does if and when the market cap is nearing $10 Billion? Bitcoin is going head to head against central banks, politicians, all fiat money and the status quo of everything that the average joe knows and accepts about rules of finance and economics in the world. When something like Bitcoin comes in and changes this, trust me, let me repeal that, TRUST ME the establishment will do anything to prevent Bitcoin to get to higher adoption. And one way of doing this is a 51 % attack, it is very effective and for them probably not that expensive way of destroying the hole Bitcoin project.

Just some thoughts. The trusted entities that you choose is probably good ones, but I think they are very few in number. Maybe it should be as much as 349 trusted entities /persons (we have to see BTC as a global phenomenon and because of that 349 or even more trusted entities are necessary) and there should be a voting system that chooses these persons, like once every year or two like a parliament. Everyone should have the opportunity to get elected, and the election can take place on the Bitcoin.org site. You vote with your BTC, Every BTC in the wallet that it is sent from is one vote, and you send one satoshi as a way of showing the person/entities you want to vote for. All entities tells the Bitcoin community who they are and what they stand for.

Also one more big point is that this checkpoints of this trusted entities is not something that is hard coded in the client, the way it works right now will be enough with hard coding with every new client the development team releases, BUT when and if there is a 51 % attack then we should have this emergency checkpoint system come in in to work and only then when there is a 51 % attack that he Bitcoin community didn't know about and recognize as a 51 % attack this parliament will get activated and the checkpoints of this parliament will be the ones that will get hard coded in to the client. This is a way of telling any government that any attack will not get Bitcoin on the knees.

Any thoughts?  

[cunicula]

Trusted parties should be people who have an ownership stake in the system. If you want to identify who truly wants bitcoin to succeed, ask who is willing to bet money on its success. The trustworthy people will plunk their money down. Proof-of-stake. Ownership and control in the same hands, not separated. It's that simple. Anything else can and will be gamed.

[da2ce7]

Having the pools include a signture within the blocks they produce is a very good starting point.

It dosn't harm the network in any-way... However makes the post 51% attack 'cleanup' much easier.

[da2ce7]

This has been a problem that has been on the back of my mind for a very long time also.

The core component is that this will provide a 2nd line of security against attacks based upon a web-of-trust style of security model, rather than the absolute ‘who hashes the most’ security model.

From the start-out the web-of-trust and computational problem security models have different ‘qualities of truth statements.’
The quality of the security that a cryptographic problem provides is a provable solution, which is non-relative.  All parties in the system will come to the same exact solution.  It can be summarised as the quality statement:  “This is absolutely true for everyone”
In legal terms it may be said as:  “This is true without any doubt”
This can be dramatically contrasted with the quality of the security that a web-of-trust provides.  A web-of-trust gives a relative prospective for the solution.   Each party may or may not come to the exact same conclusion, based upon whom they trust.  It can be summarised as: “This is good enough for me”
In legal terms it may be said as:  “This is true enough for my purposes”

Now…  Having such a strong truth statement comes at a much higher cost that a ‘less rigorous’ truth statement.   The cost in the case for bitcoin is that there is no ‘human’ element in deciding what chain is valid or not…. Instead it is entirely left up to ‘whoever can gather the most hashing power.’
Economically, such a high level of truth statement is affordable to protect bitcoin against internal attacks, (people within the bitcoin community).  Namely those whom want to seal through double spending bitcoins.
However, the economics doesn’t provide any natural protection against an externally motivated attacker.  The attacker whom gains the finance through taxation, or the protection of established systems that bitcoin competes with.

Much higher levels of security can be gained far more cheaply by lowering the required truth statement.
Think?  Is the precise order of the transactions important; if the network is being attacked by an attacker who stops all the transactions?

This is where casascius gets his idea of a ‘trust’ based system to protect against the 51% attack…  It is more important that we gain an “Extremely High” level of security against a motivated 51% attack, than maintain our “Extremely Strong” level of truth statement.

PS.  For a long time, I have been conceptually designing a ‘web-of-trust’ coin… However I’ve never came up with a good way to ‘issue’ the new coins… However It could work as a low-cost security backend for a pre-allocated *coin.

[da2ce7]

My proposal:

1.   Miners release signatures of their blocks by-default.  If they want to remain anon, either don’t release one… or use a new identity for every block.
2.   Bitcoin will display a warning if the current chain contains a very unexpectedly long time without any blocks from its ‘favourite’ miners.
3.   Bitcoin also displays warning when ‘favourite miner’ blocks consistently get orphaned.
4.   Upon detecting an active alternative fork, that contains many blocks made by the nodes ‘favourite’ miners, an option will be given to the user to move to the forked chain.


Edit:  By ‘Favourite’ I mean, whoever the developer of the particular client decides are trusted.
The user should be provided with a clear and simple way to change the ‘default’ favourite miners.

[CIYAM]

I'm not sure if anything like this is feasible or not but is there perhaps a way that some sort of voting by standard clients (rather than miners) could be used in order to decide about checkpoints (perhaps by unique IP addresses)?

[da2ce7]

I'm not sure if anything like this is feasible or not but is there perhaps a way that some sort of voting by standard clients (rather than miners) could be used in order to decide about checkpoints (perhaps by unique IP addresses)?

A web-of-trust based system will never work without two main features:

1.   Active Human Thinking Trusted Parties.
2.   Cryptographically Secure Announcement of Trust Relationships

You cannot have a secure web-of-trust without active human maintenance… figuratively you are trading computational security through the proof-of-work.  With trust gained by human interactions.

AKA... You cannot have your cake and eat it.

Edit: I suggest that using Unique IP address would be a poor security model against a motivated 51% attack.  As it would tend to lead to many different solutions, as the attacker would also flood the network with malicious nodes.  (Remember that a 51% attacker must be externally motivated to the bitcoin network)… Therefor it is likely that the attacker would have many times the financial resources disposable than the entire bitcoin network can use to defend against it.

[hazek]

I was thinking about this last night and I was wondering, what would happen if we added another stricter block-validity rule that says if more than half of blocks of all the blocks created within a day are created by 1 IP, the IP get's ignored by the rest for the next 24h?

[da2ce7]

I was thinking about this last night and I was wondering, what would happen if we added another stricter block-validity rule that says if more than half of blocks of all the blocks created within a day are created by 1 IP, the IP get's ignored by the rest for the next 24h?

Nothing... the attacker will just use bounces, many IP addresses, connect to different nodes block, or mines over TOR.  The latency for release of the attacking chain that has been mined with 51% hashing power isn't important in the long run.

[hazek]

What if they couldn't change their IP, would that rule solve the problem?

[da2ce7]

What if they couldn't change their IP, would that rule solve the problem?

I think you have a large misunderstanding on how bitcoin operates.  How would you enforce this, when you want the network to remain opon for new miners?

2nd IP addresses are very very poor at identifying a node. IP black lists will never work.

[cbeast]

I'm not sure if anything like this is feasible or not but is there perhaps a way that some sort of voting by standard clients (rather than miners) could be used in order to decide about checkpoints (perhaps by unique IP addresses)?

A web-of-trust based system will never work without two main features:

1.   Active Human Thinking Trusted Parties.
2.   Cryptographically Secure Announcement of Trust Relationships

You cannot have a secure web-of-trust without active human maintenance… figuratively you are trading computational security through the proof-of-work.  With trust gained by human interactions.

AKA... You cannot have your cake and eat it.

Edit: I suggest that using Unique IP address would be a poor security model against a motivated 51% attack.  As it would tend to lead to many different solutions, as the attacker would also flood the network with malicious nodes.  (Remember that a 51% attacker must be externally motivated to the bitcoin network)… Therefor it is likely that the attacker would have many times the financial resources disposable than the entire bitcoin network can use to defend against it.

A human coalition of trust is a good idea. However, it must also be able to recognise when a friendly ally comes online with additional hashing power that is enough to offset the 51% attack. OTOH how would you know if there even was an attack until after the damage was done? You wouldn't be able to just roll back the transactions. It might be best to stop worrying about it and let Bitcoin trust the competetive nature of man to maintain a balance of power.

[hazek]

If there is a way to recognize blocks by their owners and we can determine that a certain owners is finding a lot of blocks, we can simply put in place a rule that once you find a certain amount of blocks out of all the blocks found in a certain time period you get a forced break from getting your blocks accepted by the rest.

The blockchain exists as a copy in every single client. Meaning that because of our decentralization, just because someone has over 51% of hashing power, there's nothing that forces the 49% to accept their blocks into their copy of the blockchain, they do it voluntarily.

What I'm suggesting is to solve this problem with ostracism. Simply ignore blocks found by someone having too much hashing power. Yes, this would create a fork, but the owner of the over 51% of hashing power will find himself all alone in his fork while the rest of us carry on as if nothing happened.

[TT]

If it is possible for any single player to manage to amass that much computing power relative to the rest of the network, it seems to me that the whole proof-of-work concept is invalidated, fundamentally. We're just back to human webs of trust relations. Those who then claim that bitcoin has been hacked would be right to do so...and perhaps it would be best to abandon the block chain concept altogether.

Having said that, I believe it is possible to modify the proof-of-work algorithm to make it less likely to favor people with a particular type of specialized hardware.

[cunicula]

If it is possible for any single player to manage to amass that much computing power relative to the rest of the network, it seems to me that the whole proof-of-work concept is invalidated, fundamentally. We're just back to human webs of trust relations. Those who then claim that bitcoin has been hacked would be right to do so...and perhaps it would be best to abandon the block chain concept altogether.

Having said that, I believe it is possible to modify the proof-of-work algorithm to make it less likely to favor people with a particular type of specialized hardware.

Umm yes, proof-of-work might lose all credibility, but there would still be proof-of-stake standing untarnished. No need to get rid of blockchains altogether, that is throwing the baby out with the bath water.