On November 15th, Bitcoin Cash will go though a scheduled hard fork. There are two competing proposals called BitcoinSV and BitcoinABC. One of the changes proposed by BitcoinABC is to modify how transactions are ordered in a block. Currently every block is ordered topologically, which means that a transaction must come after all transactions it spends from. The BitcoinABC proposal seeks to change that ordering into a lexicographical one, where transactions are ordered according to their transaction id.

In this post I want to discuss tradeoffs between lexicographical and topological transaction ordering (LTOR and TTOR) with respect to scaling. I don't want to look at possible limitations of the current implementation, but rather at the long term effects that a change could have.

In order to scale Bitcoin, we need to make the miners job more efficient. Miners fundamentally face three tasks:

1. Creating a new valid block
2. Sending that block over the network
3. Validating a block another miner has sent

The biggest hurdle to scaling bitcoin is sending the block over the network (see for example here or here), so lets look at that first.

Sending a block over the network

The best known solution to reducing block transfer times is a block propagation protocol called Graphene. Graphene can work without a canonical block ordering, however it almost an order of magnitude more efficient in the presence of a canonical ordering. The reason is that we can (probabilistically) encode a set with way fewer bytes than we would need to encode a list. If all miners agree on some canonical ordering then they can send a (efficiently encoded) set over the network and the receiving miner can locally recreate the list using the globally agreed upon ordering. It is important to understand that Graphene does not care which ordering is used, as long as all miners agree on the same ordering.

At this point we should talk about an important difference between TTOR and LTOR. TTOR is a rather weak requirement. All that it asks for is that a transaction comes after all transactions it spends from in that block. There are many different TTOR orderings of the same block. It is easy to pick a canonical ordering out of this set of possible orderings. For example, Gavin Andresen proposed the following canonical ordering that is also topological back in 2014.

Source: O(1) Block Propagation by Gavin Andresen

LTOR on the other hand is a very strict ordering requirement. There is only one lexicographical ordering for every given block. Unfortunately, LTOR is incompatible with TTOR for most blocks. This is why the introduction of LTOR is a consensus breaking change.

So maybe the reason is that developers of BitcoinABC want to introduce LTOR is that Graphene is much harder to implement in the presence TTOR. While this might be true, it is important to note that we already have an implementation of Graphene on top of TTOR built by the team of the inventor of Graphene, Professor Brian Levine. While I hear that that implementation currently only has about 40% "success rate" I'm thinking that it might a good idea to get the Graphene implementation we have working, before we change Bitcoin forever.

Bottom line: Graphene is amazing tech that will make Bitcoin scale much much better. However, LTOR is not required for Graphene to work efficiently. We already have an alpha implementation of Graphene on top of TTOR.

Creating a new valid block

In order to find a new valid block, a miner updates a 32 bit field in the block header called "the nonce" until she finds a block whose hash is smaller than the current difficulty target. Besides the nonce, the block header also contains the root of a Merkle tree of all transactions in the block. When a miner receives a new transaction, she wants to include that transaction in her block candidate as quickly as possible in order to claim the fees should she find the next block. To do so she needs to compute the root of a new Merkle tree that includes the new transaction.

In computer science, this is a problem know as incremental maintenance or incremental computing: Given a query (compute the Merkle root) and a data structure that changes (the candidate block), compute the new answer to the query every time the data structure changes. The naive approach is to recompute the entire query every time. However, in many cases it is possible to avoid redoing all the previous work and only recompute a small part of the query (for example when maintaining a sql join under inserts).

To see this in action, let's look at how Merkle trees can be incrementally maintained under TTOR. TTOR has the beautiful property that a miner can always append a new transaction he receives to the end of the block. This property makes it possible to maintain Merkle trees in logarithmic time: In every step, we only need to compute hash functions for the right most branch of the tree, all other hashes have been computed previously and can be looked up if all previous roots are stored.

.

So what happens if we switch from TTOR to LTOR? We loose the important property that a miner is able to append the transaction to the end of the block. Even worse, under LTOR the user (or an attacker) can force the miner to include a transaction at a specific position in the Merkle tree. An attacker could analyse the Merkle tree that a miner is currently storing and broadcast a transaction to force the miner to recalculate the entire Merkle tree. In the situation above, the attacker would pick a transaction x that is lexicographically smaller than all other transactions:

So maybe it's not a big del that we increase the complexity for maintaining a Merkle tree from logarithmic time to linear time? Especially as current Bitcoin implementations do not maintain Merkle incrementally anyways (I think currently the entire Merkle tree is recalculated every few seconds).

While recalculating the entire Merkle tree might be the right thing to do as long as blocks are small, this does not mean that this will be true when we scale to large blocks. There is a big difference between logarithmic time and linear time, especially for large n. For example, a 100 mb block will fit about 200k txs. Computing the Merkle tree from scratch will take about 200k hashing operations, incrementally maintaining it will require about 18.

Merkleix trees are advertised as the solution. However, there is a mistake in the write-up where it is stated that

The first line should read "... in time proportional to the height of the tree". The height of a binary tree is logarithmic in the number of leaves only if the tree is balanced. However, Merkleix trees are not balanced, as is correctly acknowledged in the post

The problem is that the attacker can broadcast transactions that produce a maximally unbalanced tree. Such a tree has linear height and hence insertions take linear time.

Bottom line: We can maintain Merkle trees on logarithmic time using TTOR but we need linear time (much longer) using LTOR. In addition LTOR changes the security model: Under TTOR miners are guarantied that they can add any new transaction to the end of the block, under LTOR a possible attacker can pick the point of insertion, thereby forcing the miner to recompute the Merkle tree from scratch.

Validating a block

It has been said that CTOR will make block validation embarrassingly parallel. A computation is embarrassingly parallel if it "can be divided into a number of completely independent parts, each of which can be executed by a separate processor". For example mapping the function "multiply-by-2" over an array of integers is embarrassingly parallel.

Block validation is not parallelizable under either LTOR or TTOR, a more accurate description would be embarrassingly sequential. Consider a block that contains only transaction with one input and one output. The first transaction spends from the second, the second spends from the third, and so on. It does not matter how many processes you have, you will need to validate the transactions in sequence.

To me it is unclear at this point which block ordering is more efficient with respect to validating a single block. However, when it comes to validating the entire blockchain (as nodes do when they start up) the situation is different: we already have 10 years of blockchain that is ordered according to TTOR. All nodes will forever contain code to validate under TTOR. If we switch to LTOR, code for validation under LTOR must be added. Maintaining more code is more work and leaves more room for errors and attack vectors.

Conclusion

I am not convinced that we have to change the block ordering right now. We should be conscious that the choices we make this week will be visible on the blockchain as long as it exists. We might have to explain to our grand children why we made the switch and I do not think that at this point we have the arguments to convince them.

There is another point I would like to make. There is something magical about Bitcoin. Invented by an annonymous genius that was decades ahead of it's peers, misunderstood by both academia and industry. Despite all odds Bitcoin survived and prospers until this day. It's a story that no alt-coin can ever match.

Satoshi left, and we are in charge now. We can either prove that Satoshi was wrong, and that we had to fix Bitcoin to make it work. The developers that can push through the change will likely get famous. However, they will be taking away from the magic of Bitcoin. If we change Bitcoin in fundamental ways it will not be Bitcoin, no matter how heavy the chain.

The alternative is a more conservative approach where we try to preserve what makes Bitcoin special. Noone will get famous for maintaining Bitcoin like it is, however everybody in the community will profit if we keep Bitcoin magical. I am a Bitcoin conservative.