50%+ Attack Nodes

[Traktion]

Hi,

Firstly, I'd just like to say that Bitcoins are a great concept. I'm impressed with the distributed nature, as well as the incentive to create coins.

My only concern, is one of security. I have read the PDF and it seems convincing from a software engineer's perspective, but I am concerned/confused as to what happens if attack nodes become the majority. Hopefully, someone hear can clear the below questions up:

1. If over 50% of the CPU power is coming from attack nodes, what is the damage they can do? Could they just make phantom payments between consenting parties or could they make up completely fictitious payments? From the PDF, I think it is only the former (as the process requires the receivers' key) and it would be difficult to maintain. Could someone explain this further, as it seems to be the main potential chink in the armour I can see.
 
2. Would it be possible to have a 'stability rating' of some sort, which shows the (rough) percentage of disagreeing nodes? If there is a 45/55% split, people would likely be cautious when receiving payments. While this would hopefully be a rare occurrence, it would be good to know if, and to what degree, nodes are in disagreement.

3. If attackers create hardware to process the code very quickly (rather than generic CPUs running the code), would the 50%+ attacker scenario be more easily exploited? What sort of precautions could be put in place to prevent this from being a problem?

I'm keen to learn more about this project and I've already started generating coins with the Linux client (good to see support there so soon!). I the world is crying out for a reliable, distributed money and while governments may fear it, they may be glad of it if the current fiat structures continue their collapse.

[1714101784]

1714101784

[1714101784]

1714101784

[dete]

I think I have a pretty good handle on how BitCoin works, but this is just my understanding.  Grain of salt and all that.

The concern is not just that "the bad guys" will run more nodes, the weakness is very specific:

A malicious entity can "unspend" coins if they can generate more valid blocks than the swarm.

Here is the scenario:

Black Bart sends you 100 BTC, you wait an hour to get 6 confirmations on the payment before considering that payment valid and giving BB the gold bar he just bought from you.  At that point, Black Bart releases a new chain of hashes which is at least one block longer than the "truth" that the swarm produced.  The BitCoin algorithm takes a longer chain as being "more valid" than the shorter chain, so the "real" chain gets rejected for BB's chain.  But, of course, in BB's chain, you didn't get paid.  He keeps his 100 BTC and uses it to buy a second gold bar.

A few notes:

• A node chain is easily verified to be "correct", so BB needs to generate a valid block chain which is larger than the swarm.  Thus, he needs more CPU power than the swarm.
  
  
• That's kind of a lie: He doesn't strictly need more CPU power, block generation is probabilistic.  It's possible that BB could be running a single client on a 486SX, and still be "lucky enough" to produce more blocks than the swarm.  I haven't done the math, but I'm pretty sure the probability of this scenario is somewhere along the lines of winning the lotto every week for your entire life.  (The research paper gives a few sample probabilities for this.)
  
  
• Even with all this CPU power and/or luck, BB can only spend as many coins as are in his wallet.  He can't ever steal your coins, he can't create "fake" coins.  The potential value to BB of throwing all this CPU power at tricking the system is very, very low.  If such an attack ever did come, it would be far more likely that it would be intended to destroy the BitCoin system (by undermining confidence), rather than for direct financial gain.
  
  

[ichi]

If I were selling gold for BTC, I wouldn't count my BTC until I had transferred them from the receiving node to a storage node.  If the amount were large, I'd require multiple confirmed transfers.

So, Black Bart sends 100 BTC to a receiving node set up specifically for that transfer.  That node is scripted to transfer the BTC to my storage node as soon as it's been confirmed N times, and to email me.  My storage node is scripted to email me when that transfer has been confirmed M times.

Does such chaining increase the difficulty of "unspending" by more than N+M?

[dete]

Interim steps like you suggest don't really change anything.  What matters is the total number of transactions processed between the time Black Bart spends his coin and the point at which you (unrevokably) transfer something to him in return.  (Called "confirmations" in the current UI.)

If Black Bart controls fewer CPU resources than the swarm, increasing the total number of confirmations (again, regardless of the number of interim transactions) dramatically decreases the probability that Black Bart can "change history" by providing an alternate block chain.

However, if Black Bart controls more CPU resources than the swarm, all bets are off.  He can change history pretty much at any point he chooses.

I'll reiterate however, that the cost of dedicating more CPU resources than the swarm to ripping off BTCs is virtually guaranteed to be many times greater than any amount of value you could extract from the swarm.

[Traktion]

Thanks, Dete - some good detail there, especially in regard to my first question.

It's good to confirm that coins can only be 'unspent' by such actions, which limits the scope of such an attack. As you say, if you had to turn 50%+ CPU resources on reverting a payment, the payment would have to be worth an awful lot of Bitcoins - that CPU power would probably be better put to actually minting new Bitcoins (or processing them, with a fee). With this in mind, I agree that it would be a sort of DoS or a general attempt at undermining of the system, rather than a way to gain financially.

With the above in mind, I can also see why a small processing fee should be levied, once Bitcoin minting loses its incentive, as it removes the incentive to try to hack the system. This is very clever, as a bit of carrot is always preferable than the stick. By helping to make the current system run smoothly, they will gain much more than attempting to game it. This, in itself, should encourage CPU power to be turned toward the greater good, with faster hardware generating more income for the fair nodes.

That said, I still think an early warning system would be a good idea. Would I be correct in thinking that several, random, nodes are queried to ensure that there is chain consensus? If so, it would be good to raise a flag if it appears that there is a substantial disagreement.

The more I learn about the system, the more I am convinced that it is well thought out. It's all rather ingenious and if it scales well, I can see it flourishing. I have a feeling that the bankers and their governmental buddies will be watching on nervously, but IMO, this is something they will need to embrace in the long term.

P.S. Going OT, but I think the value of the currency will continue to come from the destruction of regular currencies. A bout of hyperinflation in one of the main fiat currencies could be just the sort of Bitcoin incentive people need. Of course, there are many other documented advantages too.

[Traktion]

I just realised that my point 2 has already been considered of in the PDF too:

One strategy to protect against this would be to accept alerts from network nodes when they detect an invalid
block, prompting the user's software to download the full block and alerted transactions to confirm the inconsistency.

Another question, which I had forgot to ask: Could attacker nodes create new coins to spend? If a huge amount of CPU power was maintained, presumably the bad nodes could validate invalid Bitcoins (their own, cheaply minted)? Or would this be impossible, as even a thin client (the 'Simplified Payment Verification' clients, which haven't been programmed yet) would flag such coins as invalid?

Thanks again!

[Traktion]

I just realised that my point 2 has already been considered of in the PDF too:

One strategy to protect against this would be to accept alerts from network nodes when they detect an invalid
block, prompting the user's software to download the full block and alerted transactions to confirm the inconsistency.

Another question, which I had forgot to ask: Could attacker nodes create new coins to spend? If a huge amount of CPU power was maintained, presumably the bad nodes could validate invalid Bitcoins (their own, cheaply minted)? Or would this be impossible, as even a thin client (the 'Simplified Payment Verification' clients, which haven't been programmed yet) would flag such coins as invalid?

Thanks again!

Anyone have a good answer for the above? It would complete my knowledge on how it all hangs together and it would give me confidence in the system.

[ByteCoin]

I just realised that my point 2 has already been considered of in the PDF too:

One strategy to protect against this would be to accept alerts from network nodes when they detect an invalid
block, prompting the user's software to download the full block and alerted transactions to confirm the inconsistency.

Another question, which I had forgot to ask: Could attacker nodes create new coins to spend? If a huge amount of CPU power was maintained, presumably the bad nodes could validate invalid Bitcoins (their own, cheaply minted)? Or would this be impossible, as even a thin client (the 'Simplified Payment Verification' clients, which haven't been programmed yet) would flag such coins as invalid?

The only way "new coins" are generated at the moment is through block generation. This is not a good way for an attacker to generate large amounts of BitCoins to use to defraud people. Under the current scheme you can't mint invalid BitCoins (barring software bugs) and under certain reasonable assumptions all BitCoin generation requires a similar amount of work.

There is an attack resembling what you have in mind however. The current scheme where the rate of block generation is only regulated by "difficulty" makes it possible. My proposed scheme outlined in http://bitcointalk.org/index.php?topic=425.0 would make it effectively impossible. This is how it works....

The attacker can buy computer time from a botnet owner which provides access to a large amount of hash generation power or alternatively he has access to many HPC Amazon EC2 instances. The price of the computer processing is the power multiplied by the time.
The attacker also runs modified BitCoin software at a huge number of different IP addresses but because the software just acts like a network node and doesn't do any block generation it doesn't cost much to run.

He perhaps waits until the "difficulty" is lower than average and then generates a transaction which represents a huge transfer of bitcoins from one address to another. The originating address does not have the BitCoins but that doesn't matter. He then fires up his vast computing resources and generates enough sucessive hash blocks by himself to make the transaction go confirmed. He only transmits these hashblocks to merchants running the "Simplified Payment Verification" who only connect to IP addresses that he controls so the rest of the network doesn't even know anything is wrong. He does not forward network traffic which might alert the merchants to the fraud such as contradictory hashblocks. He then buys goods from those merchants using the credit implied by the transfer he's just rendered confirmed. He continues to generate enough hashblocks to render those transactions confirmed. The scammed merchant transfers the goods. The attacker shuts everything down and walks away with the goods.

ByteCoin

[Quantumplation]

Interim steps like you suggest don't really change anything.  What matters is the total number of transactions processed between the time Black Bart spends his coin and the point at which you (unrevokably) transfer something to him in return.  (Called "confirmations" in the current UI.)

Not quite accurate.  It relies on the number of BLOCKS generated, which is a collection of all transactions made in a rough timespan.  So, if only one person out of all bitcoin users transfers money in 10 minutes, or every bitcoin user spends bitcoins like mad for 1000000 transactions in 10 minutes, only one block has elapsed in either case.  Then, each block is "buried" under the blocks after it, resulting in more and more security for said transaction.

The attacker can buy computer time from a botnet owner which provides access to a large amount of hash generation power or alternatively he has access to many HPC Amazon EC2 instances. The price of the computer processing is the power multiplied by the time.
The attacker also runs modified BitCoin software at a huge number of different IP addresses but because the software just acts like a network node and doesn't do any block generation it doesn't cost much to run.

He perhaps waits until the "difficulty" is lower than average and then generates a transaction which represents a huge transfer of bitcoins from one address to another. The originating address does not have the BitCoins but that doesn't matter. He then fires up his vast computing resources and generates enough sucessive hash blocks by himself to make the transaction go confirmed. He only transmits these hashblocks to merchants running the "Simplified Payment Verification" who only connect to IP addresses that he controls so the rest of the network doesn't even know anything is wrong. He does not forward network traffic which might alert the merchants to the fraud such as contradictory hashblocks. He then buys goods from those merchants using the credit implied by the transfer he's just rendered confirmed. He continues to generate enough hashblocks to render those transactions confirmed. The scammed merchant transfers the goods. The attacker shuts everything down and walks away with the goods.

ByteCoin

The transfer requires the private key of both parties.  Thus, it's impossible to "create" faulty transactions.  Also, transmitting directly by IP still alerts the rest of the network.  You can't initiate ANY transaction without either a) propagating said transaction throughout the entire network of nodes, or b) creating an isolated graph, where you control ALL the nodes, and aren't connected to anyone else.  As soon as an outside client connects to your "bad island", he starts downloading your block chain.  He can easily verify each step in that block chain, tracing the validity of coin transfers.  He can't "transfer" coins out of thin air, nor can he transfer coins away from an unwilling party, as he doesn't have their private key.  The merchant in your example, running the "simplified payment verification", would need to download the block chain, and thus would see that it was invalid.

[knightmb]

The only catch to that is even if he has a bunch of fake computers to confirm his fake transaction, it won't fit the transaction block properly because it uses previous transaction to build off of. So the other clients would have a problem of the "known" transaction blocks and the "new ones" which don't fit properly.

I don't think they would accept it, but any devs willing to comment are certainly welcome.

[ByteCoin]

I'm looking at the BitCoin white paper which says "He can't check the transaction for himself,but by linking it to a place in the chain, he can see that a network node has accepted it, and blocks added after it further confim the network has accepted it."

The attack I outlined is the one implied in Section 8. The implied "Simplified Payment Verification" behaviour results in it inferring positive balances if it can see a confirmed transaction.

The whole point of the "Simplified" bit as far as I can tell is that it doesn't bother checking the whole block chain as that's potentially quite a lot of work. THAT's why this attack is possible.

ByteCoin

[knightmb]

I'm looking at the BitCoin white paper which says "He can't check the transaction for himself,but by linking it to a place in the chain, he can see that a network node has accepted it, and blocks added after it further confim the network has accepted it."

The attack I outlined is the one implied in Section 8. The implied "Simplified Payment Verification" behaviour results in it inferring positive balances if it can see a confirmed transaction.

The whole point of the "Simplified" bit as far as I can tell is that it doesn't bother checking the whole block chain as that's potentially quite a lot of work. THAT's why this attack is possible.

ByteCoin

Yeah, but the server it's connected to is suppose to. I think you are saying that the attacker controls both his own nodes, network, super-computers, and the server that the client is connected to. If the attacker has control over all that, then the attacker might as well have control of the computer that is running the client for the simplified payment verification.

[Quantumplation]

I'm looking at the BitCoin white paper which says "He can't check the transaction for himself,but by linking it to a place in the chain, he can see that a network node has accepted it, and blocks added after it further confim the network has accepted it."

The attack I outlined is the one implied in Section 8. The implied "Simplified Payment Verification" behaviour results in it inferring positive balances if it can see a confirmed transaction.

The whole point of the "Simplified" bit as far as I can tell is that it doesn't bother checking the whole block chain as that's potentially quite a lot of work. THAT's why this attack is possible.

ByteCoin

A) That functionality hasn't been programmed yet and is only speculative (it's called a Merkle hash tree)
B) That would be used for some smaller actions like checking balance and such.  Verifying the entire block chain (which happens when connecting to a network after a long period of time, or when first downloading the block chain, would still catch inconsistencies AFAIK.
C) I took "Simplified Payment Verification Clients" to mean that the client does nothing but verify, (aka, not generating), thus saving huge amounts of CPU.

[Traktion]

...

Thanks, ByteCoin - that is pretty much the sort of scenario I was considering. It sounds like it would be very hard to do, but it is possible. However, this would assume that:

1. The transaction was of a large enough value to make it all worth doing.
2. That the merchant does insufficient checking, considering the large value of the transaction.
3. That the attacker nodes can swamp the network sufficiently, that there would be no doubt that the attacker nodes appear to be the honest nodes.

I would say that 1 and 2 should be mutually exclusive - any large transfers would surely be checked thoroughly by the merchant. I would say that 3 would also be very difficult to do, without raising suspicion/alarm from the rest of the honest network*.

* This in itself is perhaps a DoS vulnerability - if honest nodes have a mechanism to flag an alarm if they fear the network is under attack, this could be mimicked by attack nodes as a denial of service attempt. It would only result in people refusing to transact during this period, which would surely not be worth the CPU power to do this, but still.

I think I'm sufficiently convinced in the theory, so it will be interesting to see how the system develops. I would imagine that while the system is small, but growing, such attacks may only be a matter of time away. We will then see how well the system copes, but I think it will do admirably well.

[Quantumplation]

2. That the merchant does insufficient checking, considering the large value of the transaction.

That will cause ANYONE to be able to invalidate the currency, depending on the extent to which the merchant does insufficient checking.  It'd the the equivalent of me drawing a crude approximation of the dollar bill with crayon, and the cashier being so lazy he/she doesn't notice. =P

[Traktion]

2. That the merchant does insufficient checking, considering the large value of the transaction.

That will cause ANYONE to be able to invalidate the currency, depending on the extent to which the merchant does insufficient checking.  It'd the the equivalent of me drawing a crude approximation of the dollar bill with crayon, and the cashier being so lazy he/she doesn't notice. =P

haha! Indeed - well put!