Background
Some development teams in Bitcoin community presented different opinions on BCH update scheduled on November 15.
Generally, there are two typical opinions:
One party with Bitcoin ABC’s development team as the representative advocates replacing original TTOR (Topological Transaction Ordering Rule) with CTOR (Canonical Transaction Ordering Rule) and introducing the script code OP_DATASIGVERIFY.
The other party with nChain’s development team as the representative advocates raising the maximum size of blocks to 128MB and the limit will be raised step by step until it is cancelled. More original script codes of Bitcoin will be recovered at the same time, and remove the limit of 201 codes for every script.
Those differences of opinions on technical update means an action of POW consensus mechanism on decentralized network, and will definitely be a significant event in Bitcoin’s history.
As a BCH mining pool, Rawpool.com is going to make a deep involvement in the test and evaluation of various updated versions, actively facilitate community’s understanding and recognition on new technology, and issue objective and impartial technical reports based on the principle of maximizing BCH’s ecological benefits.
Prerequisite
A research on Bitcoin ABC 0.18.0 shows that CTOR was added in but TTOR was still there. That is to say, the two orderings coexist in the version. In most cases, new added codes usually bring worse performance other than a performance improvement. That’s why we give up test plan on this version.
We made communication with ABC’s developers immediately to ask their intention of retaining TTOR codes. They replied that retaining TTOR codes was to assure the compatibility before the update, otherwise the blocks on the main chain cannot be validated. Their reply is reasonable as far as the compatibility is concerned. But it also proves that the current version is not helpful for any performance improvement.
Test Content
This report is about the code evaluation on CTOR function in v0.18.0 version released by Bitcoin ABC. Since the version didn’t adopt fully optimized CTOR codes which makes it impossible to do real test, only code evaluation was made.
Notice
About some problems of CTOR codes and their application, Rawpool has made numerous email communication with Amaury, leading developer of Bitcoin ABC. who always replied every email in time and made detailed explanation. We highly appreciate and are grateful for the contribution of Bitcoin ABC team to our community participants.
The reports issued by Rawpool BCH Lab are all about blockchain technology without any preference to any parties or stakeholders.
Please feel free to send email to Hi@rawpool.com and contact our developing team.
Terms
- TTOR（Topological Transaction Ordering Rule)：
It refers to an interdependent network of transactions. As shown below: if Transaction B’s input is from the output of Transaction A, apparently Transaction B is dependent on Transaction A. For the complex dependence among numerous transactions in mempool, DAG (also be called topological graph) can be used to demonstrate such data structure as follows:
Transaction A is an ancestor tx, and B, C, and D are all its descendant tx, because all their input data use the output data of Transaction A. Meanwhile, we can see that Transaction C is also the ancestor tx of Transaction D, because Transaction D’s input data uses the output data of Transaction C.
If we make ordering for those 4 transactions above, the reasonable ordering could be ABCD, ACDB or ACBD, but ABDC is absolutely impossible because descendant transactions cannot be placed before their ancestor transactions.
2. CTOR（ Canonical Transaction Ordering Rule）:
CTOR is very simple and intuitive. It is an ascending ordering of transaction ID (a string of hexadecimal digits)
Code Analysis
1. Comprehensive Assessment on CTOR
After the conference held in Bangkok, Rawpool’s developing team made an analysis on the CTOR and TTOR codes in Bitcoin ABC’s v0.18.0 version.
Almost all articles and other technical documents about CTOR mentioned better performance of CTOR, especially in case of a large number of transactions and larger blocks, under which its performance is much better than TTOR. Additionally, it also avoids some attacks which we think is just an added advantage, since TTOR has not occurred any security problem so far.
Thus, our research focuses on whether CTOR has realized the optimized transaction ordering and whether it is beneficial to the whole network or more efficient.
In Canonical Transaction Ordering for Bitcoin, there is sufficiently clear analysis on time complexity. It concludes that CTOR is obviously better than TTOR.
2. TTOR Ordering Processing
Software developers know it well that speed and memory usage may trade off for different demands on calculation design. Thus a fully optimized speed inevitably results in a large memory usage.
In a common way, in order to realize higher computation speed in the implementation level, more optimizations should be done. One of them is to trade off between speed and memory usage. Original data need several backups for different demands and their structures may be different. Then intermediate data may be saved, which enables you not to start from scratch every time for computation. With the support of memory usage, the amount of calculation is reduced substantially and the overall computation speed is boosted. However, the disadvantage of this method is more occupation on memory.
Based on the above conclusion, we can deduce that the way of transaction storage in memory is significant and directly determines the speed of ordering processing in the TTOR processing of Bitcoin.
Then we will analyze how bitcoind realizes ordering and how transaction data is saved.
First, we locate related codes for block packaging as follows:
For ordering function, only the following codes briefly call std::sort. The last parameter of this templating method is a comparison opt code which determines priority. We can see the following by tracking the function:
It used CtxMemPool::GetCountWithAncestors, which is an attribute reader.
A brief summary: TTOR, which is considered as substantial performance overhead, just makes integer ordering according to the number of ancestor transactions at the code level. That is to say, the transaction which has the most ancestors is considered as the junior and its ordering will at the back.
3. CTOR Ordering Processing
Let’s check how CTOR which is considered to have better performance works.
The code of CTOR is as follows:
The ordering of CTOR is just based on transaction ID, which is a string of digits. We may consider it as an integer.
4. Conclusion of Preliminary Comparison
CTOR is quite similar to TTOR. The difference between them is CTOR’s ordering is based on transaction ID and TTOR’s ordering is based on the number of ancestors. But they are both integer ordering. Then we can make a conclusion that their performances are almost the same as far as the process of ordering is concerned.
However, the performance difference between maintaining transaction ID and maintaining the number of ancestors would be the determining factor for the performance difference of the two ordering methods.
5. Maintaining Transaction ID
In fact, transaction ID is a random value without any workload. In order to have a better understanding on codes, let’s have a look on the value of the number of ancestors. Firstly, there is a graph based on abstract summary:
There are two core data structures: one is mapTx, which is a real lexicographical library saving transactions and its Value is CtxMempoolEntry with four Keys (ID, fee, time, and score).
Firstly, let’s talk about transaction ID. The transaction ID of current version 0.18 is equivalent to the hash value of transactions without additional workload for maintenance.
6. Maintaining the Number of Ancestors
Secondly, let’s talk about the number of ancestors. There are two related data structures: mapTx and mapLinks. They are both lexicographical structure. The elaboration on them will be as follows:
（1) The Value of mapTx is CtxMempoolEntry with four Keys (ID, fee, time, and score).
The details are as follows:
（2）In order to easily find the ancestors and descendants of transactions, the variable of mapLinks is introduced.
It is also a lexicographical library with transaction ID as the key. Its value is a struct including parents and children which are set type. Zero index, which is iterator of transactions, is saved. As a result, when we know the ID of a transaction, we can find out all its ancestors and descendants at the first time with high efficiency and O(1) time complexity.
Then when will those data make updates? It happens when a new transaction comes into mempool or a transaction is taken away from mempool.
When there are transactions in and out of mempool, the system need frequently browse the ancestor and descendent transactions of the current one to update those data. The updated content includes the number of ancestors we mentioned before. The structure of the set of date is elegantly designed by trading off computation time with memory space smartly.
Conclusions from Rawpool Lab
- By comparison between codes of CTOR and TTOR, we noticed that the function of maintaining the relationship between ancestors and descendants hided in TTOR, and that is exactly the fundamental function which should be realized under UTXO consensus mechanism. Thus, even though CTOR is added into the codes in Bitcoin ABC 0.18.0 version, TTOR codes cannot be removed hastily as long as codes which maintaining the relationship between ancestors and descendants still exist in TTOR codes.
- Current TTOR codes has shaped excellent computation design after long-time accumulation of experience with continuous version iteration to be highly efficient. Furthermore, under current operation, its heavy workload hasn’t brought any burden on nodes.
- The prerequisite of the comparison between CTOR and TTOR’s performance is based on their similar functions. TTOR has the function of maintaining the relationship between ancestors and descendants transactions, while CTOR has no such function. Such comparison is meaningless without basing on the same functions.
- However, it is inevitable for traditional TTOR to face problems such as increasing memory overhead and more calculation time as blocks are scaling with more and more transactions. On the other hand, the fully-optimized CTOR, which includes maintaining the relationship between ancestors and descendants transactions and has removed TTOR, should be a brand-new data maintenance system with considerable complexity. A certain conclusion cannot be made at present whether CTOR can make a performance boost on memory overhead and calculation speed etc. whether at theoretical level or code implementation level.
- A fact that we cannot ignore: under UTXO consensus mechanism, the maintenance of ancestor-descendant relationship is rooted in the essence of Bitcoind. From TTOR to memory and data structure, all are at the service of UTXO consensus. Thus, the ancestor-descendant relationship of transactions will always exist, and TTOR just makes ordering operation in a natural way. That is to say, if the ancestor-descendant relationship is maintained, the removal of TTOR function will result in a large-scale rectification on data structure. The situation must be treated with extreme prudence. ABC’s engineers also said frankly that they won’t make a large-scale rectification on codes in the near future.
Finally, if Bitcoin ABC can introduce a fully-optimized CTOR Beta test version before the update, Rawpool will start an assessment at once.
Rawpool will keep on the communication with the development teams of Bitcoin ABC and nChain. At present, the deployment of tested nodes has been finished. Rawpool will actively take part in the test of the newly-updated version and stress test throughout network.
