I have only read a few dozen articles on these issues, so I am by no means an expert. Perhaps some of this has already been better solved. I am simply trying to get some of my thoughts on "paper" so to say, as it helps me organize them (especially when revisiting them later). This is not intended to be a well-organized article.

The Problem

Bitcoin keeps track of transactions in a database known as the block chain. It contains every confirmed transaction since the very first Bitcoins were mined, and new blocks are being added to it every 10 minutes (ostensibly). A block can be up to 1MB currently, this means the block chain could grow 144MB every day, 4GB+ monthly, and so on. The chain is currently approaching 17GB, large enough that "small" clients already can not hold the whole chain, and enough for many desktop users to notice the space requirements.

As Bitcoin becomes more commonly used this number is estimated to explode. The current scalability target is something akin to Visa (the credit card processor), who can handle about 10,000 transaction per second. The block chain would grow by whole megabytes every second under these conditions (possibly 30-40 GB per day at peak spending times). I've read about two potential solutions to this issue, and currently believe a mixture of both will be necessary. I am including some of my own thoughts in explaining these as well, and at this point I'm not entirely sure who originally came up with the concepts.

Solution 1 - Hierarchical Nodes

This is perhaps the simplest solution, and there is already work underway to support it. Divide participants into 4 "classes" of nodes: Super, Current, Thin, Non. Each has a different portion of the block chain, most to least respectively.

Super Node

This node has a complete copy of the block chain, just like most current clients. At some point these systems will have to have storage in the TBs just to hold one year's worth of data. These will be relatively expensive systems and will require beefy processing capabilities to not only store that data but be able to use it in a relevant time-frame (eg, processing an availability of funds confirmation request). The lessor nodes below would rely on super nodes for historical data as well as transaction processing needs. These could be further divided into active and archival nodes, but the idea is the same, they keep a complete copy of the block chain for their own analytical needs.

Current Nodes

This node has a complete copy of the unspent transactions in the block chain. This would allow the node to know if an incoming transaction is valid. It may keep a copy of completed transactions around for a short time, to allow synchronization with nodes that are slightly outdated (perhaps a day or two's worth of data) and to allow the transactions to be removed by a garbage collection process. Removing old transactions has some processing overhear, and will easily fragment storage unless the storage is regularly consolidated, so there are already some drawbacks to this node. But this node type can verify any new transaction, which is the heart of any currency system.

Thin Nodes

This node only keeps a copy of transactions destined for its own address(es). This way it knows how to spend its money, it can generate new transactions without any external information. But it would need to rely one of the above nodes to verify incoming payments since it has no knowledge of any other transactions.

Non-Node

This node really isn't a node on the network, and does not connect to other nodes as the above node types do. It's simply a front-end to another system which does contain a node, relying on whatever other system to both keep track of it's addresses (a hosted wallet solution). It does not keep it's private key on the device, though it might keep a key to unlock the private key, allowing it to initiate transactions and safeguarding against others (mainly using ECC addition or multiplication, another topic for another day).

Problems

There is still only the one block chain and it will have a hard time coping with 10ktps with 1kB per transaction and blocks every 10 minutes (6GB blocks under current worst-case scenarios). The Super/Current Nodes would need rather extreme bandwidth just to keep up, assuming ideal dissemination of information throughout the network. The Super/Current nodes would need more bandwidth to transmit those transactions to all the Thin Nodes as well. Additionally the synchronicity of the network would become increasingly important. With millions of transactions per minute, double-spend attacks would become increasingly easy on nodes without enough bandwidth to keep perfectly synchronized. Mandating confirmations before transactions can be considered complete is already normal for certain financial transactions online, but would be entirely too cumbersome for daily in-person transaction.

This essentially only solve the problem of block chain storage, particularly the historical chain transactions. It also introduces a new issue, if clients don't really need all the history to be able to participate in the network, then free access to that data might be restricted. This is not necessarily a bad thing, as the systems required to store all that data will become increasingly expensive and something has to pay for it to ensure its operation and longevity.

Solution 2 - Local Chains

This "solution" would create Local Block Chains where transactions would be aggregated and processed "locally". These chains could operate as the same 10 minute interval as the main block chain, or at different multiples/fractions thereof. Users could connect to either nodes in the main block chain or to nodes in a local chain, and could transition between relatively easily. This system does have a number of issues, I'm sure I haven't though of them all...

Further Reading: Pettycoin

There's an interesting SlideShare on Pettycoin , an adjunct coin idea. This is a complete separate cryptocurrency/network with gateway addresses where gateway nodes pass value transactions, but uses an existing network's addresses (eg, you would use Bitcoin addresses both in the Bitcoin network and in the Pettycoin network). It does solve the issue, but by essentially creating a whole other currency, exchanging your currency (though retaining your address(es). The immediate problem I have with this scheme is that you could receive payments in either block chain simultaneously, so your client would have to monitor transactions in both (and anytime you want to spend you might need to run a transaction through a gateway, waiting for confirms on that intermediate transaction). It does solve the gateway node issue by requiring some fees to be paid to such nodes. It also uses shading to distribute storage, nodes would participate in certain shards of the network. There doesn't appear to be any guarantee at least one node participating in each shard however.

The presentation also covers some ideas that it does not appear would work at all...

In and Out

Everyone would need to know where your address's transactions are being aggregated. This could easily be accomplished by a "transaction" designating your address as belonging to a local chain being confirmed in the main chain. Similarly the address could be withdrawn from a local chain by a transaction "revoking" an address being confirmed in the local chain, then being confirmed in the main chain. This does have the disadvantage of the main chain having to "know about" the transactions of the local chain. I don't have an elegant solution to this, the best I can think of, there would have to be a bridge node which could generate the relevant transactions in the correct chain. I need to read up on others ideas more toughly, they've probably solved the issue already. This would create a dual step to spending from one local chain to another, and there would need to be transactions in both local chains. There might be a need for a transaction in the main chain as well, I need to think this through more thoroughly.

Mining Incentivization

Local chains would need local miners. This presents two issues: rewarding the miners to incentivize their participation, and ensuring the local chain had sufficient mining power to preventing hijacking. The mining power issue could be solved rather easily by allowing dual-mining with the main chain. This is already done to a great extent with Namecoin. Several large pools mine for both Bitcoin and Namecoin simultaneously. This could be expanded to local block chains, if there is incentive for mining these blocks then sufficient pools would likely join that there would be sufficient mining power to prevent 51% attacks. Mining would need to be incentivized to ensure a local block chain doesn't become difficult-frozen (a state where the difficulty rises because of mining power, but then a sudden lack of mining power results in a difficulty too hight for current miners - this problem could also be addressed by modifying the formula that changes the difficulty, responding to the time since the last block in addition to the mean time between blocks over a larger range of time - this itself creates a new problem where nodes must have synchronized time). The source of this incentive would have to be transaction fees (a part of the network now that is expected to incentivize miners at some point in the future). At this time mining fees would be insufficient to incentivize mining (current mining profit comes almost exclusively from block rewards and not transactions fees within blocks). This situation is likely to remedy itself in the future, but only for local chains which have enough transactions to collect enough fees to incentivize pools to dual-mine the local chain.

Acceptance and Development

Possibly the largest hurdle to local chains would be the need for all existing nodes to upgrade their software to accept the new transaction types. This wouldn't require significant changes to main chain nodes, but would require all of them to be changed, and not everyone runs the reference software. Additionally software that could run a local chain would need to be developed, likely this would be an extension of the main software so that a single piece of reference software could participate as any node in any chain (main or local - to be clear this is all within a single currency, like Bitcoin).