Over the last several days I've been looking into detail at numerous aspects of the now infamous CTOR change to that is scheduled for the November hard fork. I'd like to offer a concrete overview of what exactly CTOR is, what the code looks like, how well it works, what the algorithms are, and outlook. If anyone finds the change to be mysterious or unclear, then hopefully this will help them out. This document is placed into public domain.
What is TTOR? CTOR? AOR?
Currently in Bitcoin Cash, there are many possible ways to order the transactions in a block. There is only a partial ordering requirement in that transactions must be ordered causally -- if a transaction spends an output from another transaction in the same block, then the spending transaction must come after. This is known as the Topological Transaction Ordering Rule (TTOR
) since it can be mathematically described as a topological ordering
of the graph of transactions held inside the block.
The November 2018 hard fork will change to a Canonical Transaction Ordering Rule (CTOR
). This CTOR will enforce that for a given set of transactions in a block, there is only one valid order (hence "canonical"). Any future blocks that deviate from this ordering rule will be deemed invalid. The specific canonical ordering that has been chosen for November is a dictionary ordering
(lexicographic) based on the transaction ID. You can see an example of it in this testnet block
, provided this testnet is still alive). Note that the txids are all in dictionary order, except
for the coinbase transaction which always comes first. The precise canonical ordering rule can be described as "coinbase first, then ascending lexicographic order based on txid".
(If you want to have your bitcoin node join this testnet, see the instructions here
. Hopefully we can get a public faucet and ElectrumX server running soon, so light wallet users can play with the testnet too.)
Another ordering rule that has been suggested is removing restrictions on ordering (except that the coinbase must come first) -- this is known as the Any Ordering Rule (AOR
). There are no serious proposals to switch to AOR but it will be important in the discussions below.
Two changes: removing the old order (TTOR->AOR), and installing a new order (AOR->CTOR)
The proposed November upgrade combines two changes in one step:
- Removing the old causal rule: now, a spending transaction can come before the output that it spends from the same block.
- Adding a new rule that fixes the ordering of all transactions in the block.
In this document I am going to distinguish these two steps (TTOR->AOR, AOR->CTOR) as I believe it helps to clarify the way different components are affected by the change.
Code changes in Bitcoin ABC
In Bitcoin ABC, several thousand lines of code have been changed from version 0.17.1 to version 0.18.1 (the current version at time of writing). The differences can be viewed here, on github
. The vast majority of these changes appear to be various refactorings, code style changes, and so on. The relevant bits of code that deal with the November hard fork activation can be found by searching for "MagneticAnomaly"; the variable magneticanomalyactivationtime sets the time at which the new rules will activate.
The main changes relating to transaction ordering are found in the file src/validation.cpp:
- Function ConnectBlock previously had one loop, that would process each transaction in order, removing spent transaction outputs and adding new transaction outputs. This was only compatible with TTOR. Starting in November, it will use the two-loop OTI algorithm (see below). The new construction has no ordering requirement.
- Function ApplyBlockUndo, which is used to undo orphaned blocks, is changed to work with any order.
- Function ContextualCheckBlock will include a direct check on sorting order. (it is only these few lines of code that enforce CTOR)
There are other changes as well:
- For mining (src/mining.cpp), CreateNewBlock will start sorting the transactions according to CTOR.
- When orphaning a block, transactions will be returned to the mempool using addForBlock that now works with any ordering (src/txmempool.cpp).
Serial block processing (one thread)
One of the most important steps in validating blocks is updating the unspent transaction outputs (UTXO) set. It is during this process that double spends are detected and invalidated.
The standard way to process a block in bitcoin is to loop through transactions one-by-one, removing spent outputs and then adding new outputs. This straightforward approach requires exact topological order and fails otherwise (therefore it automatically verifies TTOR). In pseudocode:
for tx in transactions: remove_utxos(tx.inputs) add_utxos(tx.outputs)
Note that modern implementations do not apply these changes immediately, rather, the adds/removes are saved into a commit. After validation is completed, the commit is applied to the UTXO database in batch.
By breaking this into two loops, it becomes possible to update the UTXO set in a way that doesn't care about ordering. This is known as the outputs-then-inputs (OTI
for tx in transactions: add_utxos(tx.outputs) for tx in transactions: remove_utxos(tx.inputs)
Benchmarks by Jonathan Toomim with Bitcoin ABC
, and by myself with ElectrumX
, show that the performance penalty of OTI's two loops (as opposed to the one loop version) is negligible.
Concurrent block processing
The UTXO updates actually form a significant fraction of the time needed for block processing. It would be helpful if they could be parallelized.
There are some concurrent algorithms for block validation that require quasi-topological order to function correctly. For example, multiple workers could process the standard loop shown above, starting at the beginning. A worker temporarily pauses if the utxo does not exist yet, since it's possible that another worker will soon create that utxo.
There are issues with such order-sensitive concurrent block processing algorithms:
- Since TTOR would be a consensus rule, parallel validation algorithms must also verify that TTOR is respected. The naive approach described above actually is able to succeed for some non-topological orders; therefore, additional checks would have to be added in order to enforce TTOR.
- The worst-case performance can be that only one thread is active at a time. Consider the case of a block that is one long chain of dependent transactions.
In contrast, the OTI algorithm's loops are fully parallelizable: the worker threads can operate in an independent manner and touch transactions in any order. Until recently, OTI was thought to be unable to verify TTOR, so one reason to remove TTOR was that it would allow changing to parallel OTI. It turns out however that this is not true: Jonathan Toomim has shown that TTOR enforcement is easily added
by recording new UTXOs' indices within-block, and then comparing indices during the remove phase.
In any case, it appears to me that any concurrent validation algorithm would need such additional code to verify that TTOR is being exactly respected; thus for concurrent validation TTOR is a hindrance at best.
Advanced parallel techniques
With Bitcoin Cash blocks scaling to large sizes, it may one day be necessary to scale onto advanced server architectures involving sharding. A lot of discussion has been made over this possibility, but really it is too early to start optimizing for sharding. I would note that at this scale, TTOR is not going to be helpful, and CTOR may or may not lead to performance optimizations.
Block propagation (graphene)
A major bottleneck that exists in Bitcoin Cash today is block propagation. During the stress test, it was noticed that the largest blocks (~20 MB) could take minutes
to propagate across the network. This is a serious concern since propagation delays mean increased orphan rates, which in turn complicate the economics and incentives of mining.
'Graphene' is a set reconciliation technique using bloom filters and invertible bloom lookup tables. It drastically reduces the amount of bandwidth required to communicate a block. Unfortunately, the core graphene mechanism does not provide ordering information, and so if many orderings are possible then ordering information needs to be appended. For large blocks, this ordering information makes up the majority
of the graphene message.
To reduce the size of ordering information while keeping TTOR, miners could optionally decide to order their transactions in a canonical ordering (Gavin's order
, for example) and the graphene protocol could be hard coded so that this kind of special order is transmitted in one byte. This would add a significant technical burden on mining software (to create blocks in such a specific unusual order) as well as graphene (which must detect this order, and be able to reconstruct it). It is not clear to me whether it would be possible to efficiently parallelize sorting algortithms that reconstruct these orderings.
The adoption of CTOR gives an easy solution to all this: there is only one ordering, so no extra ordering information needs to be appended. The ordering is recovered with a comparison sort, which parallelizes better than a topological sort. This should simplify the graphene codebase and it removes the need to start considering supporting various optional ordering encodings.
Reversibility and technical debt
Can the change to CTOR be undone at a later time? Yes and no.
For block validators / block explorers that look over historical blocks, the removal of TTOR will permanently rule out usage of the standard serial processing algorithm. This is not really a problem (aside from the one-time annoyance), since OTI appears to be just as efficient in serial, and it parallelizes well.
For anything that deals with new
blocks (like graphene, network protocol, block builders for mining, new block validation), it is not a problem to change the ordering at a later date (to AOR / TTOR or back to CTOR again, or something else). These changes would add no long term technical debt, since they only involve new blocks. For past-block validation it can be retroactively declared that old blocks (older than a few months) have no ordering requirement.
Summary and outlook
- Removing TTOR is the most disruptive part of the upgrade, as other block processing software needs to be updated in kind to handle transactions coming in any order. These changes are however quite small and they naturally convert the software into a form where concurrency is easy to introduce.
- In the near term, TTOR / CTOR will show no significant performance differences for block validation. Note that right now, block validation is not the limiting factor in Bitcoin Cash, anyway.
- In medium term, software switching over to concurrent block processing will likely want to use an any-order algorithm (like OTI). Although some additional code may be needed to enforce ordering rules in concurrent validation, there will still be no performance differences for TTOR / AOR / CTOR.
- In the very long term, it is perhaps possible that CTOR will show advantages for full nodes with sharded UTXO databases, if that ever becomes necessary. It's probably way too early to care about this.
- With TTOR removed, the further addition of CTOR is actually a very minor change. It does not require any other ecosystem software to be updated (they don't care about order). Not only that, we aren't stuck with CTOR: the ordering can be quite easily changed again in the future, if need be.
- The primary near-term improvement from the CTOR will be in allowing a simple and immediate enhancement of the graphene protocol. This impacts a scaling bottleneck that matters right now: block propagation. By avoiding the topic of complex voluntary ordering schemes, this will allow graphene developers to stop worrying about how to encode ordering, and focus on optimizing the mechanisms for set reconciliation.
Taking a broader view, graphene is not the magic bullet for network propagation. Even with the CTOR-improved graphene, we might not see vastly better performance right away. There is also work needed in the network layer to simply move the messages faster between nodes. In the last stress test, we also saw limitations on mempool performance (tx acceptance and relaying). I hope both of these fronts see optimizations before the next stress test, so that a fresh set of bottlenecks can be revealed.
Posted in r/Bitcoin by u/bit_novosti • 20 points and 177 comments Developer and Mining expert., Was one of the people talking about the problem of DAA in BCH. We will deploy the aserti3-2d difficulty adjustment algorithm (Asert DAA) on Bitcoin Cash on November 15th, 2020, as designed by Mark Lundeberg and implemented by Jonathan Toomim alongside other ... In the last year, the DAA subject has come up often and just recently the conversation has become more contentious. Recently, software developer Jonathan Toomim introduced a DAA concept called Aserti3-2d and the specification is available on Gitlab. The BCHN full node team has the code hosted on the “Bitcoin Cash upgrade specifications” page. /r/btc was created to foster and support free and open Bitcoin discussion, Bitcoin news, and exclusive AMA (Ask Me Anything) interviews from top...
Jonathan Toomim Karol Trzeszczkowski Bitcoin Cash Coffeehouse is a new series that brings together developers and other members in the community for thoughtful discussion in order to figure out ... Bitcoin ABC developers Amaury Sechet, Shammah Chancellor, Jason B. Cox and Antony Zegers are joined by Chris Pacia, Jonathan Toomim, Juan Garavaglia and Guillermo Paoletti to discuss Canonical ... Skip navigation Sign in. Search This video is unavailable. Watch Queue Queue. Watch Queue Queue Bitcoin Cash Difficulty Adjustment Algorithm Development Meeting; discuss progress in developing, reviewing and implementing a new BCH DAA in the different implementations. July 27th 2020, 19:00 ...