On Bitcoin's "Big O Scaling"

In computer science, there’s something called “大O符号” (pronounced “oh,” not zero). It’s a way of describing how an algorithm performs when faced with a larger problem to solve.

In the debate over Bitcoin block expansion, many people claim that "Bitcoin's O(n^2) expansion method is not feasible" and that N squared expansion is unsustainable. If it doubles N, then you need four times the resources (memory or CPU).

I had the pleasure of speaking to some of the attendees at the Scaling Bitcoin Conference in Montreal and asked them what exactly they were talking about. Turns out they were talking about a few different things.

Some of these people are talking about梅特卡夫定律(" the value of a telecommunications network is proportional to the square of the number of users connected to it "), and applying it to Bitcoin transactions, assume that if N people use the Bitcoin network, then they will generate N^2 transactions. This is silly because even if everyone could theoretically use Bitcoin to transact with others, they won't do so. I've probably transacted with about 100 people or companies in the past five years; the demand for transactions grows linearly with the number of people using it.

Furthermore, assuming the number of transactions "n" grows over time, the entire transaction history will grow O(n^2) (see Patrick Strateman's recent talk). This will grow faster than CPU power or disk space, and eventually no new people will be able to verify the entire blockchain.

If you believe that being a true Bitcoiner requires you to validate the entire blockchain from the genesis block, this is a problem. This is an unnecessarily narrow view, in my opinion, and I think people should be able to freely trade trust/convenience. For example, a new user can get a snapshot of the blockchain ledger (get the UTXO set) of the most recent blocks, so as not to download the entire history of the blockchain. This is faster and more convenient than getting the entire history of the blockchain, and its security is almost perfect, even if you get a broken copy of the ledger, the worst thing that can happen is that there will be extra entries in the ledger (maybe the attacker gave you 1 million bitcoins, but they don't exist) or some entries are missing from the ledger. If there are extra entries, then the attacker can send you invalid transactions, but these transactions will never be confirmed. They can send you a transaction and send the rest of the network a double spend transaction, which is actually the same thing, and the double spend transaction will not be confirmed.

If the entries are missing, your wallet may be in a situation where it thinks a valid transaction is invalid. Once the transaction is verified on the blockchain, it will discover its error and restore the ledger through a more reliable peer node.

Finally, there is one more argument:

Assume we have 'n' users, a fixed percentage (say 1%) of which run full nodes, and each user generates a certain number of transactions per day... then the total validation work done by all full nodes is O(n^2). (Actually, it should be O((n/100)^2 ), but the persistence factor is ignored in big O notation)

There are two things wrong with this statement:

First, as the network grows, it is probably incorrect to assume that a constant percentage of users will run full nodes. It is likely that an increasing percentage of people will choose to run partial validation nodes. In the future, there may be a billion people using Bitcoin, but only tens of thousands of people running full nodes, rather than the tens of millions that are expected. That would be a bright, successful, decentralized, and secure future for Bitcoin.

The second incorrect point is that while the entire network may indeed have to perform O(n^2) verifications, each of the n individual nodes may only perform O(n) verifications. This is an important metric because each individual does not care how much verification work the rest of the network will do, they only care about how much work their computer has to do.

－－－－