Deep Technical Discussion -- Attacking the Blockchain

[etotheipi]

I have spent quite a bit of time studying how the Bitcoin network actually works, but I'm not sure I'm 100%, so these questions will hopefully clarify some of the gaps in my understanding.  Given the decentralized nature of the network, there is no single authority that decides which is the "current" block.  Nodes assume the longest chain is the "correct" one.  So:

(1)  If two blocks are computed simultaneously by nodes on opposite sides of the world,  both nodes will broadcast valid blocks with the target hashes at the same time.  Then the nodes closest to the "winners" will each start extending that chain.  Even when they get word of the other chain, they will continue to work on the first one they received.  But as soon as one of the chains gets extended, all nodes will switch to that chain, and the other chain will be orphaned. 
   -- Is this correct?
   -- If Deepbit reports a block as "Invalid," is this why?

(2)  Let's assume that a government has a massive banks of FPGAs which are not on the network right now, but actually would be more than 50% of the network speed if they were (not really feasible, but governments have a lot of money...).  Now, instead of joining the network, they start building an alternative blockchain branch, starting from some arbitrary block.  Because they have more computing power than the rest of the network, they can start building the blockchain faster than the "current" blockchain everyone is working on.  Could they build this alternate blockchain branch for 2 months, and then broadcast it to the network all at once?  If all blocks in the new chain are valid, and it's longer than the current, then won't all nodes switch to it?  Then all the transactions of the last two months will basically be reversed because they "never existed" in the new blockchain?   This would seriously disrupt the Bitcoin network...

(3) Are transaction scripts currently disabled in the main Bitcoin client software?  If not, then is anything stopping people for using scripts in their transactions?  If so, then what is stopping someone from including a script in all their transactions that says no private key is required to transfer the coins onward?  Once the main Bitcoin client software starts using the scripts, then that old transaction no longer requires a private key signature and the they can send the coins back to themself if they were never transfered out out of that account.

-Eto

[Maged]

I have spent quite a bit of time studying how the Bitcoin network actually works, but I'm not sure I'm 100%, so these questions will hopefully clarify some of the gaps in my understanding.  Given the decentralized nature of the network, there is no single authority that decides which is the "current" block.  Nodes assume the longest chain is the "correct" one.  So:

(1)  If two blocks are computed simultaneously by nodes on opposite sides of the world,  both nodes will broadcast valid blocks with the target hashes at the same time.  Then the nodes closest to the "winners" will each start extending that chain.  Even when they get word of the other chain, they will continue to work on the first one they received.  But as soon as one of the chains gets extended, all nodes will switch to that chain, and the other chain will be orphaned. 
   -- Is this correct?
   -- If Deepbit reports a block as "Invalid," is this why?

Yes on both counts.

(2)  Let's assume that a government has a massive banks of FPGAs which are not on the network right now, but actually would be more than 50% of the network speed if they were (not really feasible, but governments have a lot of money...).  Now, instead of joining the network, they start building an alternative blockchain branch, starting from some arbitrary block.  Because they have more computing power than the rest of the network, they can start building the blockchain faster than the "current" blockchain everyone is working on.  Could they build this alternate blockchain branch for 2 months, and then broadcast it to the network all at once?  If all blocks in the new chain are valid, and it's longer than the current, then won't all nodes switch to it?  Then all the transactions of the last two months will basically be reversed because they "never existed" in the new blockchain?   This would seriously disrupt the Bitcoin network...

Yes, that is what would happen. To prevent such a disaster, various ideas are being thrown around where, essentially, such a large reorganization would have to be resolved manually by all the other active nodes. However, if someone has a majority of the hashing power, we're still screwed.

(3) Are transaction scripts currently disabled in the main Bitcoin client software?  If not, then is anything stopping people for using scripts in their transactions?  If so, then what is stopping someone from including a script in all their transactions that says no private key is required to transfer the coins onward?  Once the main Bitcoin client software starts using the scripts, then that old transaction no longer requires a private key signature and the they can send the coins back to themself if they were never transfered out out of that account.

-Eto

The current client won't make, nor recognize, any transactions with a non-standard script. It CAN, however, verify scripts when they are spent. If you use a script that is spendable by anybody, someone would have to notice the transaction and then spend it. It wouldn't show up in everyone's client automatically.

Non-standard script transactions can currently be submitted to Eligius and put in a block for a small fee.

[theymos]

If someone releases a huge alternative chain, that chain would just get blacklisted by the next client version. The attacker could keep the network offline for as long as they maintain control, but it'd get sorted out eventually.

[etotheipi]

So you are saying that the client will not recognize a transaction with a non-standard script, unless someone knows about that transaction and spends the coins in compliance with its script?  Therefore, if a script were somehow included in a transaction, the new owner is still bound to the "terms and conditions" of the script, but if they're using the standard client, they won't see it to begin with.  Therefore, a vendor would not see the transaction in their history, and they would claim that you never paid them...?  By the way, who/what is Eligius?

There is really only one client right now, Bitcoin-0.3.23.  Is there anything wrong/unethical/prohibitive to create a new client?  I was considering trying to create a client that has built-in encryption and possibly even an option to automatically do business through Tor.  But it would have to compete with the "official" 0.3.23 client.  Is this a bad idea for the network?  If so, what's stopping someone who doesn't like Bitcoin from doing this?  From the outset, people would want it because it has useful features.    Even if it is "okay", someone could eventually sneak malicious code into the client.  What's stopping that from happening now?  Is the official bitcoin client codebase protected against this?  Could an attack of this sort cripple the network?

[Maged]

So you are saying that the client will not recognize a transaction with a non-standard script, unless someone knows about that transaction and spends the coins in compliance with its script?  Therefore, if a script were somehow included in a transaction, the new owner is still bound to the "terms and conditions" of the script, but if they're using the standard client, they won't see it to begin with.  Therefore, a vendor would not see the transaction in their history, and they would claim that you never paid them...?

That's exactly it. In fact, unless your client is aware of how the script can be solved (such as is the case for the current two scripts), it's (virtually) IMPOSSIBLE for the client to recognize that it can spend the transaction.

By the way, who/what is Eligius?

They are a major mining pool.

There is really only one client right now, Bitcoin-0.3.23.  Is there anything wrong/unethical/prohibitive to create a new client?

Absolutely not! PLEASE do! We need more competing clients!

Even if it is "okay", someone could eventually sneak malicious code into the client.  What's stopping that from happening now?  Is the official bitcoin client codebase protected against this?  Could an attack of this sort cripple the network?

Not much is stopping it right now, other than that we're open-source. This issue needs to be solved before we can offer automatic updates.

[etotheipi]

By the way, something else I've been wondering (and an excuse to get to 5 posts):  what is the incentive for a node to include any transaction in their block for free?  If you have a lot of transactions, isn't it going to take longer to hash?  If I was selfish, why wouldn't I calculate a block and only include my own coinbase transaction and nothing else?

Similarly, as the network picks up popularity aren't we running the risk that we'll have to start including millions of transactions in every block?  Even if the difficulty adjusts to accommodate the slower hashing, won't the blockchain get untolerably large (in terms of storage space)?

[Maged]

By the way, something else I've been wondering (and an excuse to get to 5 posts):  what is the incentive for a node to include any transaction in their block for free?

The only incentive is that it will help get more people to be willing to use Bitcoin.

If you have a lot of transactions, isn't it going to take longer to hash?  If I was selfish, why wouldn't I calculate a block and only include my own coinbase transaction and nothing else?

It DOESN'T take longer to hash. There's no reason NOT to include transactions.

Similarly, as the network picks up popularity aren't we running the risk that we'll have to start including millions of transactions in every block?  Even if the difficulty adjusts to accommodate the slower hashing, won't the blockchain get untolerably large (in terms of storage space)?

I suggest reading this wiki page:
https://en.bitcoin.it/wiki/Scalability

Edit: to clarify, it's not the whole block that is hashed, just the headers, which includes the Merkle root. The amount of data hashed does not change - regardless of the number of transactions.

[etotheipi]

Absolutely not! PLEASE do! We need more competing clients!

So why aren't there competing clients?  I was under the impression that there's only one client option on both Windows and Linux because it's either really bad or really difficult. 

If I study the specification at https://en.bitcoin.it/wiki/Protocol_specification do you think I'll have enough knowledge to actually implement a client with all the networking/sockets to operate nicely with the rest of the network?  I suppose, the main client is open source, so perhaps I can use that source code to clear up gaps in my understanding.

-Eto

[NYConsultant]

By the way, something else I've been wondering (and an excuse to get to 5 posts):  what is the incentive for a node to include any transaction in their block for free?

The only incentive is that it will help get more people to be willing to use Bitcoin.

If you have a lot of transactions, isn't it going to take longer to hash?  If I was selfish, why wouldn't I calculate a block and only include my own coinbase transaction and nothing else?

It DOESN'T take longer to hash. There's no reason NOT to include transactions.

Similarly, as the network picks up popularity aren't we running the risk that we'll have to start including millions of transactions in every block?  Even if the difficulty adjusts to accommodate the slower hashing, won't the blockchain get untolerably large (in terms of storage space)?

I suggest reading this wiki page:
https://en.bitcoin.it/wiki/Scalability

Edit: to clarify, it's not the whole block that is hashed, just the headers, which includes the Merkle root. The amount of data hashed does not change - regardless of the number of transactions.

Who is responsible for constructing the merkle tree, and then the merkle root for inclusion in a block header?  Doesn't that take processing power?

[Maged]

Absolutely not! PLEASE do! We need more competing clients!

So why aren't there competing clients?  I was under the impression that there's only one client option on both Windows and Linux because it's either really bad or really difficult. 

If I study the specification at https://en.bitcoin.it/wiki/Protocol_specification do you think I'll have enough knowledge to actually implement a client with all the networking/sockets to operate nicely with the rest of the network?  I suppose, the main client is open source, so perhaps I can use that source code to clear up gaps in my understanding.

-Eto

Look into BitcoinJ -  it's better commented.

By the way, something else I've been wondering (and an excuse to get to 5 posts):  what is the incentive for a node to include any transaction in their block for free?

The only incentive is that it will help get more people to be willing to use Bitcoin.

If you have a lot of transactions, isn't it going to take longer to hash?  If I was selfish, why wouldn't I calculate a block and only include my own coinbase transaction and nothing else?

It DOESN'T take longer to hash. There's no reason NOT to include transactions.

Similarly, as the network picks up popularity aren't we running the risk that we'll have to start including millions of transactions in every block?  Even if the difficulty adjusts to accommodate the slower hashing, won't the blockchain get untolerably large (in terms of storage space)?

I suggest reading this wiki page:
https://en.bitcoin.it/wiki/Scalability

Edit: to clarify, it's not the whole block that is hashed, just the headers, which includes the Merkle root. The amount of data hashed does not change - regardless of the number of transactions.

Who is responsible for constructing the merkle tree, and then the merkle root for inclusion in a block header?  Doesn't that take processing power?

The miner. Yes, it takes processing power. However, given that miners have hashing speeds in terms of megahashes per second, and even gigahashes per second, the loss is extremely minimal. ALL clients need to hash each transaction anyway, so no work is lost there. Thus, you only "waste" 1 hash per merkle tree branch that's made. I don't know the math for approximately how many hashes need to be done per transaction, but let's just go to the extreme and say 10 for a 100 transaction block. That's 1000 hashes wasted. Compare that to the millions of hashes computed per second on the video card...