On November 15th, the Bitcoin Cash protocol implementation used by a majority  of Bitcoin Cash nodes, Bitcoin ABC, will undergo a scheduled upgrade. This upgrade is known as a “hard fork” because it introduces backwards incompatible changes, even though it represents the majority of Bitcoin Cash nodes. The fork contains two primary changes: enforcing new rules that govern the order in which transactions can occur in a Bitcoin Cash block (CTOR), and introducing new programming language operations. This post primarily focuses on one of the most divisive changes, CTOR.
What is Canonical Transaction Ordering (CTOR)?
Canonical transaction ordering (CTOR) refers to placing transactions in a block based on an agreed upon, “canonical”, ordering. This feature has several motivations in the general theme of Bitcoin Cash scaling. One of the work’s primary goals is to optimize block propagation, the process by which nodes in the network share information about new blocks in the Bitcoin Cash blockchain. An additional motivation is to facilitate sharding. It is worth noting that CTOR development work is not without its detractors, and criticism of the approach is included in the conclusion of this post.
CTOR and block propagation
Block propagation is the process by which new blocks spread through the Bitcoin and Bitcoin Cash networks. As an example, if several blocks are simultaneously discovered by different miners, nodes need to come to consensus on the next block by conferring with their peers. If it takes longer for nodes to share information about Block A over Block B, the faster-spreading block (Block B) is selected as the next one in the chain, with the slower propagating Block A not included in the chain (also known as becoming “orphaned”). Miners with orphaned blocks are not rewarded with new Bitcoin or Bitcoin Cash created in a coinbase transaction.
As a result, long block propagation times favor centralized mining pools — members of the pool are quickly able to share information about new blocks with one another. From the perspective of Jonathan Toomim:
“No rational miner or pool will intentionally orphan their own blocks, and they will always receive their own blocks with a delay of zero.
Toomins also comments that:
A pool with 35% of the hashrate will instantly have 30% more support for their blocks than a pool with only 5% of the network hashrate, and will see a 30% lower block orphan rate as a result. This results in more revenue for larger pools compared to smaller ones when orphan rates are high, and will encourage all miners to join large pools
The pressure to join large mining pools undermines the decentralization of the Bitcoin Cash network, and this pressure will grow stronger as the size of blocks grows — during a recent stress test of the Bitcoin Cash network, there was a significant increase in orphan rate . Additionally, the race to propagate blocks incentivizes miners to limit block size and process fewer transactions — larger blocks encode more data and require more time to travel through the network than smaller blocks.
How could CTOR improve block propagation?
Based on this motivation, many in the Bitcoin Cash and Bitcoin Unlimited communities are pursuing technical improvements to the problem of block propagation. Previous work to optimize block propagation exists in the form of compact blocks, Xthin. and Graphene (original proposal here, published paper). While these systems are used to varying degrees, Graphene has shown significant promise in terms of the efficiency that the protocol uses to transmit block data.
The Graphene protocol works by encoding information about the transactions in a block into two primary data structures — a bloom filter (S) and an IBLT (I). The receiving node uses the bloom filter to determine which transactions in its mempool are in the block. The transactions that are both in the node’s mempool and in the block are used to create an additional IBLT (the Graphene paper calls this I’). The subtraction of the I and I’ IBLTs generates a set of transactions that are in the block, but that the receiving node does not have. If this set is empty, the receiving node can go ahead and construct the block on its own. If the set is not empty, it can retrieve data for the transactions that are in the block, but are missing from the receiving node’s mempool.
An additional, optional data structure can be used that contains information about the order of transactions in a block. This is where CTOR comes in. As measured during the BCH stress test, approximately “86% of the data that Graphene without CTOR needs is for transaction order information” . This information is needed for a node to construct and validate a block if there is no canonical order. If there is a canonical order, the node only needs to know which transactions are in the block, then iterate over the set of transactions in the block to construct it.
CTOR and sharding
Another motivation for CTOR is to support sharding, or the process of splitting up transaction data so that it can be processed in parallel.
How could CTOR allow sharding?
In particular, the Bitcoin ABC developers argue that CTOR could allow parallel validation of blocks, transactions as they enter a mempool, and queries against the data.
It is argued that blocks could be verified in parallel because of how a Merkle root for a block is created and verified. A Merkle tree contains subtrees, with transaction hashes as leaf nodes. The argument is that a shard would contain all of the transaction data (assuming data locality is important) necessary to generate a subtree hash, and multiple shards could be processed at a time, with one thread for each shard. Subtree hashes could then be merged together to generate the Merkle root.
The article also argues that shards could facilitate parallel processing as transactions are received. For example, a load balancer could forward incoming transaction data to a processor responsible for maintaining a specific shard.
Arguments against CTOR
As mentioned earlier, there is a significant amount of discussion in the Bitcoin Cash and Bitcoin Unlimited communities about CTOR (additional critique and summary available from nChain here).
[Graphene] 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.
On reddit, /u/jessquit commented:
Where I come from, when you want to reengineer a thing to get a benefit, you must at least have a working prototype of the end goal before embarking on reengineering, to at least demonstrate that the end goal is conceivably achievable.
Others argue that changing to CTOR shouldn’t happen without performance benchmarks, and there is no telling what will happen at scale. The nChain paper argues that:
Even with sufficient testing, and even with sufficient evidence produced from multiple implementations on testnet, changes may introduce subtle bugs that are not immediately obvious.
In short, some of the main arguments against CTOR are that it either won’t provide the benefits it claims to facilitate, or that the benefits do not outweigh the potential risks of the consensus change.
Enforcing a CTOR in Bitcoin Cash blocks will take effect on November 15th, although the changes are somewhat contentious. Some members of the development community are strongly opposed to the work on the grounds that the changes won’t facilitate the performance and scalability improvements that are claimed. Regardless of this specific set of changes, developers in both the Bitcoin Cash and Bitcoin Unlimited communities are working to improve their software to allow for on-chain scaling, and it will be exciting to see their progress towards this goal.
 https://cash.coin.dance/nodes as of 2018–11–08