Op-ed: The Case for Adding CTOR to Bitcoin Cash in November

This is the current proposal. “Canonical” refers to the requirement that only ordering is permitted. The current proposal is also “lexical” or “lexicographic” meaning that all transactions in a block except the coinbase are sorted in dictionary order. This aspect is referred to elsewhere in discussions as “LTOR”.

For the sake of simplicity, the remainder of this document will typically use “CTOR” to refer to the current proposal (which also happens to be LTOR) even if a particular point applies more to the lexical property.  

Block Propagation

Let’s start at the beginning. In 2014, Gavin proposed a new approach to block propagation and one ingredient of his idea was the canonical ordering for transactions in a block. The “secret sauce” of his proposal was the use of Invertible Bloom Lookup Tables (IBLTs) to communicate the differences in the set of transactions in a node’s mempool with that of a peer.

This line of thinking formed the roots of the now famous Graphene protocol.

Gavin’s original ordering proposal is not currently part of any BCH implementation proposal but it is important historically to show the roots of the idea. The most obvious application for CTOR today is that it helps Graphene work better.

A more intuitive explanation of why a unique ordering helps propagation is that you can save bandwidth if you only have to transmit data for missing transactions without communicating anything about the order of the transactions in a block. Thus, a canonical ordering can help other block propagation schemes such as Xthin; its benefits are not just limited to Graphene.

In a published critique, a developer had implied CTOR isn’t beneficial for block propagation because a miner can choose to re-order his own transactions under the current rules. However, no explanation is given how that would improve efficiency, except to provide a link to a forum post which states “… The rest of the transactions are completely free to be reordered. For instance by sorting them by txid…”

In other words, avoid canonical ordering so miners can be free to choose… a canonical ordering?

If the point is freedom of choice, we will address that consideration later.

It is also noteworthy that the author of the critique (Awemany) shifted his opinions on CTOR subsequent to his publication and after the Bangkok miner meeting… and he emphasizes that none of the proposed changes are worth splitting the coin over.

Block Validation

A benefit of the CTOR proposal is to simplify parallel processing for block validation. This is a result of removing the topological ordering requirement. However, parallelization is not a unique benefit; you can still parallelize the process even under the existing topological ordering scheme.

The entire debate over block validation is a bit of (an unintentional) red herring since block propagation is a much bigger bottleneck than block validation.

Still, it may be helpful to readers to review the history of the main arguments on this specific topic. The original debate went something like this:

CTOR critics noted that (at least in a naive implementation) nodes can verify transactions more quickly under TTOR since the dependencies for each transaction will have already been processed. CTOR supporters pointed out that the topological restriction is an additional burden that needs to be verified. (In other words you cannot simply divide up the transactions in a block into parallel partitions and be done.)   

Jonathan Toomim then published an algorithm showing how parallel validation can be accomplished using the current topological ordering by processing outputs first, then inputs (e.g. “OTI”).

The OTI method can be applied to both TTOR and CTOR. In the case of TTOR, a map of positions for each transaction needs to be generated in the first loop, and the second loop ensures that each transaction only spends coins that are older than itself. The requisite multiple loops here render the TTOR advantage in the naive implementation a moot point.  

To summarize, both TTOR and CTOR can be parallelized. Initial tests produced roughly equal performance. But to reiterate, this is a tangential issue because CTOR clearly helps block propagation which is a more important bottleneck.

Other Benefits of CTOR

There are some other benefits to CTOR. UTXO handling may be improved because sequential inserts can make the use of tree structures for the UTXO cache more efficient as well as expanding the possibilities for UTXO commitments.

SPV/Light wallets may also enjoy a minor benefit of transaction exclusion proofs. CTOR can also allow routing to shards to coincide with merkle construction and validation.

But the biggest secondary benefit seems to be a simplification of the code. Allowing any transaction order makes the code more complicated as any order must be supported. By contrast, assuming the lexicographic ordering allows blocks to be constructed the same way each time and makes testing easier.

TTOR vs ATOR vs CTOR

Some of the arguments surrounding the validation issue are not specific to CTOR; they are more of a TTOR vs ATOR issue. In other words, should we keep this topological ordering requirement or get rid of it?

Some experts have pointed out that fundamentally, the ordering of transactions holds no inherent value. I interpret this to mean that while it’s true that topological order handles dependencies, there is a cost to creating that order initially. Most developers do not oppose removing TTOR. This even applies to the lead developers from Nchain.

Furthermore, once the topological requirement is discarded, it is a relatively small change to adopt a canonical ordering. This is one of the principles behind the CTOR proposal. In the ABC implementation, adding CTOR on top of ATOR is 20 lines of code.

The “Central Planning” Objection