Topic: The way how to double protection bitcoin network against 51% attack (Read 19861 times)

Well, it depends on how you define "centralized." Currently Bitcoin is 100% owned by the mining cartel. I think that among the "core developer" only Gavin isn't running a mining operation. So if Mt.Gox or other exchange succeeds at breaking into the mining cartel then Bitcoin will actually become more diversified.

In a Bitcoin client unrated blocks could never replace rated blocks. So the 51% attack as it is known now would be a threat only for those who don't trust any rating service: hard-core anarchists, people from the fringes of society, etc. For everybody else the rating services will be the defense. Some will buy the ratings online, some will periodically download the ratings in the public library, very much like the access to financial ratings is happening right now. There is whole spectrum of speed-of-access vs. cost trade-offs that are possible.

Obviously the current hard-coded values in the clients will need to change: 6, 150, 500, probably many others. Right now the trust spectrum is: 100% gavinandresen & fabianhjr, 0% all others. This should change in the future.
 

I still prefer my idea of adding exponential difficulty deltas beyond a shallow reorg.  It doesn't require that the client track any new data sources and it doesn't require an AI to interpret trends.  It also allows a recipient to calculate a waiting time (depth really) for an incoming transaction that provides them with whatever level of concrete mathematical security they desire.

How it would work if you missed all of my posts on this last summer and fall:

First, we want to be able to handle ordinary "honest" reorgs exactly like we've been doing it.  The usual estimate I use for this is once every 300 blocks on average for a single block shuffle.  The reorglog on block explorer says there have been 29 reorgs in the 23523 blocks, or about 1 in 800.  In practice, blockexplorer will be on the winning side about half the time (and thus not record a reorg), so the real number is 1 in 400, which means that my 1 in 300 estimate is fairly close, and is on the conservative side.

That means that on average, we will get a single block reorg every other day.  And a two block reorg every other year.  And a three block reorg twice per millennium.  Beyond that, it gets silly, because there probably won't be an honest six block reorg before the sun burns out.

So, we pick a parameter, call it S, and set it to a number higher than we ever expect to see from an ordinary reorg.  6 would probably be good here, but just to be really safe, I'll go with 12 in my example.

Now, any reorg of depth <= S is handled normally.  The fun happens when an attacker wants to replace more than S blocks in a single shot.

I'm going to call the second parameter P, and it is the base of the exponential function.  Any number greater than 1 will work here.  Bigger numbers work more quickly, but small numbers still work great.  For this example, I'm going to go with 1.05.

Now, we do some calculating.  We go back in our chain to the last common ancestor, the point where the potential new chain split off.  We add up all of the difficulty stored in the blocks after this point, and we call it X, while we are doing that, we count how many of our blocks will need to be thrown out if the reorg succeeds, and we call that D.  Then we add up all of the difficulty beyond this point in the new chain, and we call it Y.  Finally, we calculate F=P^(D-S).

With me so far?  We have:

D - depth of the reorg from our point of view, the number of blocks that will be invalidated
X - difficulty of the reorg, again from our point of view, the amount of work that will be discarded
Y - difficulty of the new chain, the amount of work that will replace X
S - the number of blocks we are discarding
F - The exponential difficulty function that starts small, but grows more or less rapidly

Again, if D <= S, then the comparison is just is Y>X?  If yes, then reorg, if no, then no reorg.  This is simply the current logic.
However, if D > S, then the comparison is Y>(X*F).

If we assume blocks of constant difficulty, P=1.05 and S=12, we get:

12 blocks requires 12 * 1.00 blocks = 12.00 = 13 blocks (the new chain must be longer)
13 blocks requires 13 * 1.05 blocks = 13.65 = 14 blocks
14 blocks requires 14 * 1.10 blocks = 15.43 = 16 blocks
15 blocks requires 15 * 1.15 blocks = 17.36 = 18 blocks
21 blocks requires 21 * 1.55 blocks = 32.57 = 33 blocks (the chain is 50% stronger after just 3.5 hours)
24 blocks requires 24 * 1.79 blocks = 43.10 = 44 blocks
27 blocks requires 27 * 2.08 blocks = 56.13 = 57 blocks (twice as strong after 4.5 hours)
36 blocks requires 36 * 3.22 blocks = 116.10 = 117 blocks
60 blocks requires 60 * 10.4 blocks = 624.07 = 625 blocks (ten times the work needed after 10 hours)
144 blocks requires 144 * 626 blocks = 90229 blocks (after a day, the attacker needs to do over 600 times as much work)

The typical objections to my scheme involve honest network partitions.  I don't see that as a problem.  The worst case would be the network split exactly in half (by hashing power, not node count or geography), and staying divided for about 4 hours (assuming S=12), which is something we would notice, since it would involve aliens blowing up all of our communication satellites and putting the earth on a gigantic bandsaw to cut it into halves along a great circle through Minnesota and Texas.

This would be the case for a network split where one of the parts has roughly half the hashpower. An even split cannot be expected or relied upon. Block chain reorganizations as a result of network reconnections are likely to be complex events and I think that simple rules for coping with them yield the least unpleasant surprises.

A better metric for inferring an attack would be to estimate the implied aggregate hashpower. If a longer blockchain arrives that invalidates the last 10 blocks and the generation rate has been normal then one could reasonably infer that the aggregate hashpower has doubled and that there is cause for concern.
A reorganization which contains double spends would certainly be suspicious.

I would not recommend inferring anything from timestamps, the originating miner's identity or transaction amounts/numbers/sizes. Such rules would contain arbitrary hard-to-justify "magic numbers", be difficult to test, have complex failure modes and a large security perimiter.   

What should be done if a new chain arrives which invalidates an AAA rated block at depth 4 but now the new chain has incoming AAA ratings. The added complexity of sorting out conflicting ratings will have lots of nasty edge cases and be hard to test.

ByteCoin

This is the first suggestion (combined w/ heuristic block ratings) that makes me think one could make it very difficult to pull off a 51% attack.  I am already convinced there is no such thing as an economical 51% but heuristic block scoring and auto-lock checkpointing (if widely used enough) could keep the majority of the network on the "good chain". 

Your comment on differences between blockchain split and 51% attack are also insightful.  If the network splits and re-orgs the timing of the prior blocks should be longer than normal.

Some elements on heuristic block scoring:
* the block was first scene by multiple points in the network
* the signer of the block (if a known signer.  database of know reward addresses could be used)
* length of prior block(s)

yay, i just realized we have lots of methods that we could combine and help detect or mitigate any 51% attack.

Yes.

The times the blocks are announced also matters; if my node suddenly sees a longer 10-block chain it has never seen before, then either it is a 51% attack or the network was split and just came back together.

If the network was split 10 blocks ago then I should see that those 10 blocks took twice as long to create as expected.

Rating blocks is a neat idea; I can think of several potential criteria, there are probably more we could come up with:

• Did I first see the block announcement long after the block's timestamp?
• Does it look like it is part of a network split?  (two chains that are both producing blocks more slowly than usual)
• Are they part of a sub-chain with a 'normal' distribution of blocks from the well-known mining pools? (an attacker's chain won't have blocks from ANY of the mining pools)
• Does it contain any double-spends that conflict with alternate chains I know about?
• Do the transactions in it look 'normal'?  (reasonable number of transactions, reasonable amounts)

Somebody should simulate some 51% attacks and network splits and try out various detection algorithms.

And maybe see if it would be practical to have a checkpoint lock-in rule of something like "auto-checkpoint any AAA-rated block once it is 4-deep in the best chain". I don't think that should be built-in to bitcoind, but a little side program that monitored the block chain and the pools and told bitcoind to add a checkpoint once an hour or so would be pretty spiffy...

Why would they need to deny anything? They will ride it as the best thing they did since inventing credit cards - they saved the world consumers from the claws of secretive money-laundering illegal drug-consuming tax-evading anarchists! They might even get tax deductions for their heroic efforts. They will also most likely have the approval of law enforcements agencies. "Sorry, ma'am, I know it's hot and noisy in our office, but we're fighting against cyber terrorists, so your money can be safe in our bank."

This has happened before (more than once): representatives from antivirus companies break into botnet C&C servers and shut them down. Good for them, the general public and the media say. But in reality, the are illegaly hacking into computers hosted in another country, computers who are sometimes owned by botnet masters or used with permission. Without a court order, most often than not even without informing local law enforcement. The are cyber attackers just like the botnet operators. They are heroes.

Question: if I break into a stolen car and I dismantle something so the car is unusable, am I a hero? Or did I just do something illegal? Both?

I'd say we shouldn't underestimate the power of FUD/PR. If Bitcoin will die, I think this is where the fatal blow will come from.

The most important metric would be when the block was received.  If I receive a block that tries to replace a block 6 or 10 or 100 blocks ago on the chain I already know about, and I have no reason to believe I've been segregated from the network at large, I'm not going to vouch for it.

By the way, I don't have to be the only person "signing" blocks.  If pools signed their own blocks, the signatures in the blocks themselves could also be taken into consideration as self-vouching, as the attacker is not going to be able to fake those signatures.

With respect to the argument that the attack chain could/would be built in secret... this is 100% correct.  If I were MtGox, I would probably program my bitcoind to simply shut down if it ever came across a need to reorganize 6 or more blocks, so that the desired reorganization results could be sorted out manually.  (in effect, this could already be accomplished with just a few lines of code, and the desired outcome signaled via another block checkpoint, just like what the namecoin exchange did when faced with a threat).

Not sure I like the idea of Mt. Gox consolidating even more power.  A pool as in mining pool?  Possibly one of the largest mining pools someday.  The single company running largest exchange, largest pool, largest rating service?  Kinda flies in the eye of decentralized.

Still that wasn't the impression I got at all.  What you be the metric for AAA vs AA vs A?  You do understand that waiting is no protecting from a 51% attack right?   The attack chain would be built in secret.  It wouldn't be released until it is longer than the valid change.  So a block rated quadruple AAAA would instantly be erased without warning by a longer chain and the transaction replaced.

I don't know what you & Casascius have in your minds exactly, but my understanding of the "checkpoint services" would be that they will provide ratings for each block: AAA, AA, A and so on. The big exchange like MtGox would run its own pool and its own block rating service. Then instead of the fixed "6 confirmations" to consider the transaction valid people would agree to make the conditions more involved, eg: transaction is valid when MtGox rates the block containing it at least A and Casascius at least AA and slush|TradeHill-conglomerated at least AAA. There wouldn't be a single point to attack. The attacks would result mostly in  delays of the settlement.

cool man, then we could take our measures in case anything nasty happens

what?

I think your understanding of block singing and network validation is flawed.  In a 51% attacker miners are irrelivent.  The attacker has more hashing power than all legit miners.  It isn't an issue of good miners being "confused" and continuing the bad chain.  Their actions are utterly irrelivent.  The double spend will happen in a matter of seconds or minutes.


The attacker will build a private block chain and not release it until it is sufficiently longer than the good chain.  Instantly clients will recognize the logner chain as valid.  

The attacker wouldn't care what miners know or think they are irrelevant.  What CLIENTS know and think is what matters. If clients are relying on your service attackers would only need to disrupt it (though finger nail pulling or large bank accounts in the Caymans) for seconds.  The false chain will be PRE-MINED and bad blocks released in rapid succession which you will sign as valid.  Clients accept it and double spends are confirmed as good transactions.

What happens AFTER that is also irrelevant.  The damage is already done.


Exactly if necessary you would be under the control of the adversary or simply dead and your keys under their control.  Also this concept of a heroic ongoing war between good and evil isn't factually valid.  There will be absolutely no warning of a 51% attack until it has already happened.  The entire bad chain will hit the network simultaneously and be propogated in a matter of seconds.  There will be nothing to fight.  

Why worry about large banks? Worry about medical imaging centers, even the small ones. Consider the architecture of modern medical imaging machines like CT,MRI,PET,etc. Think of all the FPGAs sitting between the actual image acquisition sensors and the RAID where the images are getting stored.

Now imagine that you could put a bitcoin mining bitstream on an average MRI machine, instead of the usual image filtering bitstream. The power that goes to the pre-processing cabinet is minuscule compared to the power going into the coil and its cooling. The tera-hashes would send shivers down your spine.

The only people that would matter the most are those who are mining, because the point of my service would be to hint which of two competing block chains to prefer in the event of a conflict/chain reorg, both of which would have to be credible (in the sense that they meet the difficulty requirements).  Most people aren't solo mining, they don't count for much.  I think even a minor chain reorg that contained a double spend conflict would already catch someone's attention today, somewhere.  News would spread fast.  I would have to do is alienate a few pool operators, and I'd be history, the same way if I started selling bogus Casascius coins.

Let's just say I was totally rogue, and I signed whatever the hell I pleased.  As long as I only signed one version of a block at any given height, and committed to always sign it within 4 blocks of having received it, it shouldn't really matter what I sign.  That's because to enable a double spend, I'd have to convince the network to discard a chain of at least 6 blocks (assuming that's the threshold for confirmation) and replace them with something better.  That's impossible if I'm committing to signing valid-looking blocks sooner as a condition of my signature stream being valid.

I would need to BE the adversary, or under the control of the adversary, to sign the wrong block stream.  And remember, no one would want or need to subscribe to my service during times of network peace - I'd only be a defensive countermeasure available to those who are actively fighting the attack.  Assuming I did a good honest job, others would see the value of making my service redundant, and then the assumption that 11+ other people might be doing the same thing for the good of the network wouldn't seem so silly as someone suggested.

The damage would already be done.  The double spend would have already occurred.  The theft/fraud completed and irreversable.  The fact that in future people would stop using the service would be immaterial.

While you may think 11 other providers would form they may not.  Mt. Gox still controls 90% of currency trades.  The top 3 pools control 70%+ of mining traffic.  

I understand the concept you are describing however it relies on you always being factual and accurate.  Through hacking, sabotage, coercion, or bribery you may not be so any security it provides is a false sense of security. In other words it will work until the moment it is needed the most and then it will fail.

I was working on user-defined checkpoints today-- command-line/bitcoin.conf (and maybe a RPC call) that just says "Add this block hash at this height as a checkpoint."

You and your 10 trusted friends could then run a little program that coordinated automatic lock-ins whenever you like...

But it would take hours, if not days for enough people to notice and start ignoring you.  In that time a lot of damage would be done.

My registry wouldn't be of much use if I signed bogus blocks, because people would just unsubscribe from it, and because the other 11 (or n) operators probably aren't going to be signing the same bogus blocks, any manipulation I make would likely get outvoted by the others.  The network shouldn't ever grow "dependent" on my service - it need only have a spot where the user can pop in a URL to subscribe to block validity hints - the same way you can point a mail server at the antispam blacklist of your choice since they all have a similar DNS-based protocol.  My service would essentially be to offer a tiebreaker to choose the more legitimate of two competing blocks, each hint I sign would be open to scrutiny.  If I start publishing crap (for example, I am favoring a revision of a block that contains an obvious double spend against an earlier revision of that same block, or condemning a block with perfectly valid transactions, or am attempting to roll back several blocks at the same time without a flamingly obvious well-known good reason), people would see this, they would ignore me and go elsewhere for the same service.

I don't like it.   I hope you read on as to why ...

The dependency on individuals makes the network weaker not stronger.  Say Bitcoin someday did process billions of dollars.  The potential for large scale fraud will attract organized crime.  Coercion, bribery, or outright assault of registry operators isn't a far fetched idea.  Organize d crime uses violence and intimidation to orchestrate much smaller crimes today.

If a family member ends up kidnapped are you going to put the network over their life?  Or will you "approve" and sign the malicious blocks and anything else they "ask" you to do to ensure your loved ones aren't harmed?  Alternatively if the network ever did grow dependent on your service expect leverage and pressure from a government.  For example they would want backdoors so they can flag transactions they deem as illegitimate as not valid.

I think a "proof of stake" or "proof of history" is a potential mechanism but it needs to be more protocol based where those w/ stake or history are chosen by the protocol and the number of entities needs to be much larger not a handful but maybe a couple hundred.  Granted a couple hundred nodes having a more important role is "more centralized" but still sufficiently decentralized to make attacking an individual ineffective.

I have thought of one way the block chain could be defended in an attack...

I could start up a "Casascius Block Registry" by myself, which would be some RPC web service where I sign all the blocks that I think are good, and allow people to query me for my signature for any given block.  No one has to care, nor does anyone have to pay attention to what I'm doing, and more than likely, I get very few hits from only a few curious geeks.

A few other individuals who think alike might do the same thing.  So after all, you have a bunch of obscure geeks signing blocks, nobody cares about these signatures, nobody queries them.  Consider it a form of digital masturbation.  Maybe a dozen people do this.

Then along comes an attacker.  Panic ensues, along with widespread disagreement as to what to do next.

One option on the countermeasure table becomes to incorporate querying the "Casascius Block Registry" into clients, as well as the other dozen registries created the same way, as an assistive tool to decide which blocks are legitimate and which should be discarded.  This effectively puts the whole of Bitcoin into the hands of a dozen individuals, which of course is far from decentralized as Bitcoin would like to be, but would be better than the status quo in the event of an attack that experiences success.

By starting my registry long in advance, I would have already defined an RPC query protocol and established in people's minds that such a database exists as a countermeasure.  I'll have a sense of established legitimacy and reputation for having Bitcoin's best interest in mind, and by analyzing what I sign, people will have already had a sense for how I decide whether a block is good or bad before they point their clients at me as a source of validation for blocks.

If it successfully mitigates a 51% attack, others start to realize what a good idea it was, and start their own block registries so defensive power isn't in control of a dozen individuals for very long.  And if the attacker gives up and the registries aren't needed anymore, the world can go back to simply using the longest proof of work as is done now.