Scalability
The core BitCoin network can scale to very high transaction rates assuming a distributed version of the node software is built. This would not be very complicated.
Note to readers
If you're coming here because of Dan Kaminsky's criticisms related to this page you're deserved a forward:
When techies hear about how bitcoin works they frequently stop at the word "flooding" and say "Oh-my-god! that can't scale!". The purpose of this article is to take an extreme example, the peak transaction rate of Visa, and show that bitcoin _could_ technically reach that kind of rate without any kind of questionable reasoning, changes in the core design, or non-existent overlays. As such, it's merely an extreme example— not a plan for how bitcoin will grow to address wider needs (as a decentralized system it is the bitcoin using public who will decide how bitcoin grows)— it's just an argument that shows that bitcoin's core design can scale much better than an intelligent person might guess at first.
Dan rightly criticizes the analysis presented here— pointing out that operating at this scale would significantly reduce the decentralized nature of bitcoin: If you have to have many terabytes of disk space to run a "full validating" node then fewer people will do it, and everyone who doesn't will have to trust the ones who do to be honest. Dan appears (from his slides) to have gone too far with that argument: he seems to suggest that this means bitcoins will be controlled by the kind of central banks that are common today. His analysis fails for two reasons (and the second is the fault of this page being a bit misleading):
First, even at the astronomic scale presented here the required capacity is well within the realm of (wealthy) private individuals, and certainly would be at some future time when that kind of capacity was required. A system which puts private individuals, or at least small groups of private parties, on equal footing with central banks could hardly be called a centralized one, though it would be less decentralized than the bitcoin we have today. The system could also not get to this kind of scale without bitcoin users agreeing collectively to increase the maximum block size, so it's not an outcome that can happen without the consent of bitcoin users.
Second, and most importantly, the assumed scaling described here deals with Bitcoin replacing visa. This is a poor comparison because bitcoin alone is not a perfect replacement for visa for reasons completely unrelated to scaling: Bitcoin does not offer instant transactions, credit, or various anti-fraud mechanisms (which some people want, even if not everyone does), for example. Bitcoin is a more complete replacement for checks, wire transfers, money orders, gold coins, CDs, savings accounts, etc. and if widely adopted probably replace the uses of credit cards which would be better served by these other things if they worked better online.
Bitcoin users sometimes gloss over this fact too quickly because people are too quick to call it a flaw but this is unfair. No one system is ideal for all usage and Bitcoin has a broader spectrum of qualities than most monetary instruments. If the bitcoin community isn't willing to point out some things would better be done by other systems then it becomes easy to make strawman arguments: If we admit that bitcoin could be used as a floor wax and desert topping, someone will always point out that it's not the best floorwax or best desert topping.
It's trivial to build payment processing and credit systems _on top_ of bitcoin, both classic ones (like Visa itself!) as well as decentralized ones like Ripple. These systems could handle higher transaction volumes with lower costs, and settle frequently to the bitcoin that backs them. These could use other techniques with different tradeoffs than bitcoin, but still be backed and denominated by bitcoin so still enjoy its lack of central control. We see the beginnings of this today with bitcoin exchange and wallet services allowing instant payments between members.
These services would gain the benefit of the stable inflation resistant bitcoin currency, users would gain the benefits of instant transactions, credit, and anti-fraud, bitcoin overall would enjoy improved scaling from offloaded transaction volume without compromising its decentralized nature. In a world where bitcoin was widely used payment processing systems would probably have lower prices because they would need to compete with raw-bitcoin transactions, they also could be afford lower price because frequent bitcoin settling (and zero trust bitcoin escrow transactions) would reduce their risk. This is doubly true because bitcoin could conceivably scale to replace them entirely, even if that wouldn't be the best idea due to the resulting reduction in decentralization.
Scalability targets
VISA handles on average around 2,000 transactions/sec, so call it a daily peak rate of 4,000/sec. They have burst capacity for over 10,000 transactions per second which they need to handle the busiest points of the holiday period (~8,500tps). [1]
PayPal, in contrast, handles around 4 million transactions per day for an average of 46tps or a probably peak rate of 100tps.
Let's take 4,000 tps as starting goal. Obviously if we want BitCoin to scale to all economic transactions worldwide, including cash, it'd be a lot higher than that, perhaps more in the region of a few hundred thousand transactions/sec. And the need to be able to withstand DoS attacks (which VISA does not have to deal with) implies we would want to scale far beyond the standard peak rates. Still, picking a target let's us do some basic calculations even if it's a little arbitrary.
Current bottlenecks
Today the BitCoin network is restricted to a sustained rate of 7 tps by some artificial limits. These were put in place to stop people from ballooning the size of the block chain before the network and community was ready for it. Once those limits are lifted, the maximum transaction rate will go up significantly.
CPU
The protocol has two parts. Nodes send "inv" messages to other nodes telling them they have a new transaction. If the receiving node doesn't have that transaction it requests it with a getdata.
The big cost is the crypto and block chain lookups involved with verifying the transaction. An ECDSA verification of a transaction input takes around 3msec on a modern Intel core. RIPEMD-160 runs at 106 megabytes/sec (call it 100 for simplicity) and SHA256 is about the same. So hashing 1 megabyte should take around 10 milliseconds and hashing 1 kilobyte would take 0.01 milliseconds, ie it's dwarfed by the cost of the ECDSA and thus can be ignored.
So the slowest part of verifying a transaction is verifying its inputs, which is ~3 msec per input on todays hardware. It seems like in the current blockchain most transactions have only one input, and a few have more like 5/6 inputs. Let's call it an average of 2 inputs overall. However each transaction input is verified twice: once when first received, and a second time when a block containing that transaction is received, so call it 12msec in total per transaction.
This means a single core today can probably, with tuning and the block chain held in RAM but no special hardware beyond that, verify and accept about 80 transactions/sec. This means a network node capable of keeping up with VISA would need roughly 50 cores + whatever is used for mining (done by separate machines/GPUs). Whilst building a single machine with 50 cores would be kind of a pain load balancing inbound "tx" messages over multiple machines would be very easy. Certainly a single machine could easily load balance all of VISAs transactions to a small group of verification machines which would then send the verified tx hash to the miners for incorporation into the merkle tree.
For receiving and handling all the "tx" messages, you therefore could build a rack of 12 4-core machines that would keep up.
That leaves the inbound inv messages. The cost of handling an inv is basically reading a small message from the network and then doing a RAM lookup to see if we already have the transaction. This is really, really fast. A single core could easily handle several thousand inv messages per second before breaking a sweat, even assuming it needs to read from a sharded in-memory block chain index.
Network
Let's assume an average rate of 2000tps, so just VISA. Transactions vary in size from about 0.2 kilobytes to over 1 kilobyte, but from looking at the block explorer it's probably averaging half a kilobyte today. So let's assume the way people use BitCoin gets more complicated and call it 1kb per transaction.
A solved block will then be around (1024 bytes * 2000tps * 60 seconds in a minute * 10minutes) / 1024 bytes in a kilobyte / 1024 kilobytes in a megabyte / 1024 megabytes in a gigabyte = 1.14 gigabytes per block.
But you only have to transmit a solved block to your connected peers. If we assume these big futuristic supernodes have something like 40 or 50 peered connections, that means in the worst case scenario where you solve a block OR you receive a block but none of your peers have it yet (unlikely), you have to send ~57 gigabytes of data (call it 60).
Shifting 60 gigabytes of data in, say, 60 seconds means an average rate of 1 gigabyte per second, or 8 gigabits per second.
The real question you want to know is how much does that sort of bandwidth cost? Well, bandwidth prices are a very tricky thing as some of the largest consumers pay the least due to how peering agreements work. The Googles and Akamais of this world will pay way less for a 10G wave than a small operator would. And, you wouldn't be hitting the 8Gbps very frequently .... only when you solve a block, really, as when relaying a block the peers you connect to will likely have already received it from some other peer anyway so only a subset would need to receive it from you.
Luckily, a node would very likely not have to transfer this much data this quickly. Assuming all nodes are equally well connected to other nodes with the same number of connections, each node would only have to send one copy of each block received, on average. Even if you are the first node to become aware of a block, once you send the block to 3 or 4 others, it would propagate among the others in exponentially growing numbers, similar to the bit-torrent protocol.
Take a look at [2] to get a feel for data transfer costs.
Storage
At very high transaction rates each block can be over a gigabyte in size. These blocks must be stored somewhere. Whilst for speed it'd be ideal to store the block chain entirely in RAM, for cheapness storing only the hot parts in RAM and the rest on disk is the way to go. A 3 terabyte hard disk costs less than $200 today and will be cheaper still in future, so you'd need one such disk for every 21 days of operation (at 1gb per block).
Network structure
Today BitCoin is a flat peer to peer network in which all nodes are equal. However the intention is to evolve it towards a more typical two-tier structure in which low powered client nodes connect to long-lived, high powered supernodes. The protocol already has some support for this (see the services flags in the version/address messages). However client mode is only partially implemented and no code exists to decide if and when to switch between supernode/client node status.
As the network scales up, the costs of running a supernode that stores the full block chain and verifies every transaction will get progressively higher, but the two tier structure ensures everyone can still get started quickly. Client nodes only need to download a small number of headers the first time they connect (from their last checkpoint until the chain head). It's quite possible to run such nodes on a modern smartphone. The security model for lightweight clients is slightly different to a full node: whilst they don't need to talk to a trusted node (ie any network node will do), in that configuration it's important that the network be very difficult to attack as the block contents are not verified.
Optimizations
The description above applies to the current software. However several optimizations exist that can dramatically cheapen the cost of running a node and these are fairly easy to implement.
CPU
The CPU cost of a transaction is doubled by the fact that the current software verifies each input twice. There's no need for this. Once a transaction is received the fact that it passed verification can be stored, and when it re-appears in a block the second verification can be skipped. This would roughly double per-core capacity, ie you would need only 25 cores to verify VISA-level traffic loads. This can actually fit into a single high-end server.
Storage
The storage costs of the block chain calculated above assume transactions are never deleted. Satoshi's paper explains how transactions with fully spent outputs can be pruned from long term storage due to how they are arranged in a Merkle tree. Nodes try to avoid accumulating lots of small unspent outputs as that means to send a reasonable quantity of coins would require transactions with lots of inputs and thus, be large and perhaps requiring a fee. Because nodes fight fragmentation, as time goes by it's likely that many blocks can be completely pruned of all or nearly all transactions, reducing their storage costs in the best case down to 80 bytes. As of May, 2011, the software does not implement pruning, and the potential savings are calculated at 71% of transactions or 73% of raw block bytes.
Bandwidth
The network costs of distributing blocks can be minimized by changing the protocol to send blocks as a header plus a list of hashes. Because nodes are very likely to have already seen a transaction when it was first broadcast, this means the size of a block to download would be trivial (80 bytes + 32 bytes per transaction). If a node didn't see a transaction broadcast, it can ask the connected node to provide it.
Network structure
The peer-finding mechanism today relies on IRC. Switching to DNS would give dramatically faster startup times that do not scale with the size of the network.
Simplified payment verification
It's possible to build a Bitcoin implementation that does not verify everything, but instead relies on either connecting to a trusted node, or puts its faith in high difficulty as a proxy for proof of validity. BitCoinJ is an implementation of this mode.
In SPV mode, named after the section of Satoshis paper that describes it, clients connect to an arbitrary full node and download only the block headers. They verify the chain headers connect together correctly and that the difficulty is high enough. They then request transactions matching particular patterns from the remote node (ie, payments to your addresses), which provides copies of those transactions along with a Merkle branch linking them to the block in which they appeared. This exploits the Merkle tree structure to allow proof of inclusion without needing the full contents of the block. The pattern matching protocol message isn't implemented yet, a proposal was discussed in May 2011.
As a further optimization, block headers that are buried sufficiently deep can be thrown away after some time (eg, you only really need to store say 1000 blocks).
The level of difficulty required to obtain confidence the remote node is not feeding you fictional transactions depends on your threat model. If you are connecting to a node that is known to be reliable, the difficulty doesn't matter. If you want to pick a random node, the cost for an attacker to mine a block sequence containing a bogus transaction should be higher than the value to be obtained by defrauding you. By changing how deeply buried the block must be, you can trade off confirmation time vs cost of an attack.
Programs implementing this approach can have fixed storage/network overhead in the null case of no usage, and resource usage proportional to received/sent transactions.