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

The following opinion piece on Canonical Transaction Ordering (CTOR) was written by Jonald Fyookball the lead developer of Electron Cash. 

Canonical Transaction Ordering (“CTOR”) is one of the planned changes for the November 2018 Bitcoin Cash protocol upgrade. There has been quite a bit of discussion in the Bitcoin Cash community about this change.

Also read: Philippines Okays PDAX Crypto Exchange

I had previously published an article explaining in simple terms what the change is. Although that article satisfied some readers and convinced them that CTOR is not dangerous, others were still critical and wanted to know if the change is necessary. The questions on many people’s minds are: “Why do we need CTOR? Why do we need it now? And are there other proposals that could accomplish the same thing?”

I attempt to answer those questions here. CTOR is part of a comprehensive technical roadmap designed to help Bitcoin Cash become peer to peer electronic cash for the entire world. More specifically, there is a clear and major benefit in CTOR which is that of faster block propagation. There are also some additional minor benefits. Unfortunately, much of the technical discussion about CTOR has been in the area of block validation rather than block propagation, which has brought considerable complexity and confusion to the overall debate.

Review of Four Different Transaction Ordering Schemes

Let’s begin our analysis by considering four different ways we could do transaction ordering in Bitcoin Cash.

1.TTOR – Topological Transaction Ordering Rule This is the current consensus rule for Bitcoin Cash. Transactions have a partial ordering rule. They can be in any order but must enforce the topology which puts parent transactions before child transactions. 2. ATOR – Any Transaction Ordering Rule

This ordering would remove the current TTOR rule and allow any order of transactions. It’s an idea that has been discussed as both an alternative to CTOR and also a precursor.

3.GTOR – Gavin’s Transaction Ordering Rule

This was proposed by Gavin Andresen in 2014. It is essentially a canonical transaction ordering, but the ordering is not mandatory (non-consensus) and it also preserves the current TTOR rule. 4. CTOR – Canonical Transaction Ordering Rule

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

One objection to CTOR (that does not seem valid) is the idea that miners should be free to come up with their own order — that they should be allowed to “compete” for the best ways to structure blocks and that forcing an order on them is tantamount to “central planning”. I am a staunch supporter of the free market in all its forms. However, this idea that miners should compete on transaction ordering doesn’t make any more sense than competing on transaction formats, or ECDSA curve parameters, or any number of protocol details. There are certain parts of the protocol that are simply infrastructure “plumbing”. It may even be counterproductive to the system as an inefficient ordering scheme must be supported by all nodes.

The “Optimize First” Objection

Certain developers (Tom Zander in particular) have expressed a desire to continue efforts to optimize the code using the current topological ordering. They do not want to upgrade or modify the transaction ordering because they believe we should explore and exhaust the possibilities of the existing scheme.  

Protocol development should not be stalled for the sole reason of a developer wishing to continue exploring on a certain trajectory.

Although optimizing within the current protocol limits is a possible approach, it is not necessarily the best approach. At the end of the day, we must choose a distinct path even if that means discarding other paths. More importantly, this approach prioritizes optimizations over choosing correct data structures, which runs counter to best practices in computer programming.

Development Roadmap

Bitcoin ABC has published a technical roadmap that details how we can improve the protocol and meet our goals of better scaling, usability, and extensibility for Bitcoin Cash. It is the best example of a comprehensive and practical plan for our future.

CTOR is one small but important building block in this roadmap. Although the Bitcoin Cash community is much larger than Bitcoin ABC, it should be noted that the ABC roadmap is compatible with the other roadmap statements published from various groups following a multi-group meetup in London in November 2017. In fact, the exact same canonical ordering proposal appeared on Nchain’s roadmap in December, 2017.20   A Holistic Approach May Be Best CTOR should be evaluated not as an independent protocol change, but as an integral part of the well planned technical approach that Bitcoin ABC is spearheading. There is more than one way to scale the Bitcoin Cash protocol, but it makes more sense to take a “holistic”, logical approach rather than one based on isolated changes and “hacky” fixes.   For example, we could use GTOR to get some of the benefits of the canonical ordering, but it would require a topological sort during graphene block reconstruction, and would be more complicated.

It would also be possible to implement the OTI algorithm to handle parallel validation with the current topological ordering, but why take a piecemeal approach when CTOR also allows this, provides tangible benefits, and simplifies the code?     Is CTOR a Safe and Proven Protocol Change? As explained in the “ELI5 article”, a different transaction order is fundamentally NOT a radical change. Although more testing and benchmarking would be nice, it is necessary to have the correct data structures in place before further development can commence. It is unrealistic for some groups to work for months building on protocol changes that are not guaranteed to exist later. There is a risk/reward tradeoff for most protocol changes. I have seen a misguided comment that changes should be proved for 3-5 years on testnet before deploying. But attempting to mitigate risk with hyperextended caution beyond the point of reasonableness is not necessarily prudent. We are in a race against payment solution competitors, both traditional and other cryptocurrencies, as well as in a race with ourselves to grow the transaction volume ahead of the block reward halvings. Some thoughtful calculated risks are required, and there is also risk in stagnating.

CTOR has been on the roadmap for nearly a year and has been discussed at large for multiple years. As a challenger to the incumbent systems, we must be an order of magnitude better. And we must establish the technical base for scalability sooner rather than later so that businesses and applications have the confidence to choose Bitcoin Cash as a platform.

On a final note, solid evidence that Graphene will benefit greatly from CTOR can be found from data collected during the BCH stress test.

Conclusion

There has been considerable debate, discussion, and confusion over the CTOR proposal. After review, it seems that CTOR is a sensible change with clear benefits and no significant drawbacks. It is part of a well-planned roadmap for scaling Bitcoin Cash. Miners, developers, users, and businesses should support its inclusion in the November 2018 protocol upgrade.

What do you think about Canonical Transaction Ordering (CTOR)? Let us know in the comment section below.

Images via Shutterstock, and Bitcoin Cash 

OP-ed disclaimer: This is an Op-ed article. The opinions expressed in this article are the author’s own. Bitcoin.com does not endorse nor support views, opinions or conclusions drawn in this post. Bitcoin.com is not responsible for or liable for any content, accuracy or quality within the Op-ed article. Readers should do their own due diligence before taking any actions related to the content. Bitcoin.com is not responsible, directly or indirectly, for any damage or loss caused or alleged to be caused by or in connection with the use of or reliance on any information in this Op-ed article.

The post Op-ed: The Case for Adding CTOR to Bitcoin Cash in November appeared first on Bitcoin News.