Why ABC’s CTOR Will Not Scale

There are two problems with the sharding proposal by Bitcoin ABC. First, the proposed lexicographical transaction ordering is unnecessary to implement it. Second, but more importantly, the sharding (scaling by distributing data to multiple machines) proposal won’t actually work.

The source of the confusion is that engineers are not examining the entire network stack, and because of that the proposal ignores two important operations:

  1. Validation of transaction inputs
  2. Transaction information requests by end user wallets

Validation of Transaction Inputs

(or Why CTOR is unnecessary for scaling)

Since TX id’s are pseudorandom, only 1/S parents will be in your local shard and so (S-1)/S parents are in remote shards, where S is number of shards. This means that for S > 2 most parents will require sending a message to a remote shard.

So for a conservative 8 shards, ⅞ of the parents need remote validation. There is at least one parent per transaction (except the single coinbase), so at a minimum ⅞ of the transactions require a remote request. But 2 parents is a more reasonable number for the average number of inputs per transaction. In this case, given N transactions in the block, you need 7N/4 remote requests to validate the block, and each shard makes 7N/4S remote requests.

If the average number of parents per transaction is P, the general equation for the total number of remote requests is (S-1)/S * PN, with (S-1)/S² * PN requests per shard.

To switch gears for a moment, the scaling advantage that CTOR offers is that it is easy to break the block up and pass transactions to shards because the block can be split generally sequentially — approximately the first N/S transactions go to shard 1, the second to shard 2 and so on.

However, let us imagine an unordered block and break it similarly, passing exactly N/S transactions to the “API Request Processor & Transaction Router” nodes defined in Chancellor’s sharding proposal (figure 2). These nodes route every transaction to the appropriate UTXO shard. This requires N messages, spread over S nodes, with a resulting load of N/S per shard.

So this “top-level” routing requires N/S messages per shard, but the “validation routing” requires (S-1)/S² * PN messages per shard.

For reasonable values of S (number of shards, for example >= 4) and P (number of parents per tx, for example >=2), the validation routing requires more messages (3/8N) than the top level routing (1/4N) per shard.

If this sharding scheme can handle the validation routing load, it can handle the top level routing of unsorted transactions. CTOR is therefore not necessary.

Additionally, the CTOR sharding architecture exposes the sharding algorithm to everyone. This can therefore be easily attacked by mining a block containing transaction ids that are entirely located within a single shard (the miner could malleate existing transactions or create his own “vanity” transactions). It is unclear what this would do to a system that requires processing to be distributed, but it won’t be pretty. (Credit Tom Zander for this attack)

Transaction Requests By End User Wallets

(or why this sharding proposal is broken)

Chancellor’s sharding proposal ignores light wallet (SPV wallets, mobile wallets, etc) access to transactions. But the Bitcoin Cash architecture is focused on access via light wallets and Bitcoin Cash’s scalability is plan is founded on the idea that the end-user won’t run a full node. The ratio of light wallets to full nodes will be analogous to the ratio of email users to email servers today. Let us conservatively propose that each full node serves 1000 light wallets. Given the volumes, this message is clearly the most important in terms of scalability. Every block received will result in 1000 messages to light wallets per node, or 1000 times the activity. Yet this activity is not addressed in the proposal.

Light wallets need to be notified of transactions that match addresses they are interested in. This is done via the MERKLE_BLOCK message which provides the light wallet a block without all of the transactions it is not interested in.

In Chancellor’s proposal the UTXO set is sharded by transaction id, which has no relationship to addresses. So how to create a MERKLE_BLOCK message?

The light client request must be sent to every shard by the “API Request Processor & Transaction Router” node specified in his proposal. Every shard must then search its portion of the block for matching transaction addresses and respond. The “API Request Processor & Transaction Router” nodes then pull this information together into a MERKLE_BLOCK. There is no scalability when a common message requires the involvement of every shard.

Note that even if we moved away from the MERKLE_BLOCK message, we still need to search every shard for transactions that involve addresses of interest. For the vast majority of wallets that have made no transactions in the last 10 minutes, we still need to search every shard to create a “there’s nothing of interest to you” response.

The only way to solve this problem is to put the data that a light wallet needs into a single shard. Could wallets generate “vanity” transactions (transactions with a common prefix) that all land in one shard? Unfortunately, it’s the sending wallet that generates the transaction while the receiving wallet does the search and so needs to specify the transaction prefix. And what about transactions sending to multiple destinations?

To solve the light wallet access problem, which is the biggest problem, a completely different sharding mechanism must be used. If we deploy CTOR, it will be hard to reverse it in order to deploy a technique that actually helps shard the blockchain.

Appendix A: What about Graphene et. al?

There are other arguments for CTOR that were provided before the “pivot” to sharding/scalability. Debunking these has already occurred and is beyond the scope of this document. But in general, understand that a non-hard fork optional sorting can be used instead of a miner-enforced (CTOR) sorting.

Let’s look at Graphene. It does not care what the order is, it only cares that there is one. Miners can voluntarily choose to sort transactions in a manner that Graphene understands, and Graphene can accept multiple sorts. So if we discover a sort that really does aid scalability, Graphene can be updated to use it.

An optional, no hard fork, not consensus enforced, transaction sort provides the much the same benefits as CTOR. Should we accept the risk of an accidental fork that a major consensus change brings when it is unnecessary?