Transaction Reordering in smartBCH

Ethereum's mining pools can decide the exact transaction order in a block. The mining pools prefer to pack a bundle of more profitable transactions. This opens the door of "front-running", such as the "sandwich attacks" towards uniswap.

In smartBCH, the order in which transactions take effects are different from the order specified by the validator who proposes the block. Instead, they are reordered by a deterministic algorithm, to meet two goals:

1. Maximize the execution parallelism among transactions

2. Mitigate the problem of front-running

To meet goal #1, slight adjustment to the transaction order is enough for most of the cases. To meet goal #2, the orders must be reordered thoroughly in a pseudo random way.

In smartBCH's golang implementation, the transaction list is pseudo-randomly shuffled after it is got from a new committed block, and before it is further processed and stored into the node's local storage. In the transaction list there may be multiple transactions from the same account, whose nonces are in an increasing order. We must keep the partial order of the transactions from the same account, to make sure the transactions will be executed in a nonce-increasing order.

The pseudo-random shuffle algorithm has following steps:

1. Get a from-address list and a from-address-to-transactions 1-to-n map from the transaction list

2. Calculate the seed for pseudo random generator, using the current block's DataHash (the Merkle root of transactions)

3. Shuffle the from-address list using the pseudo random number sequence generated by the algorithm MT19937-64.

4. Get a shuffled transaction list using the from-address list and the from-addrss-to-transactions map

In the shuffled transaction list, the transactions from the same address are adjacent, but they are not executed back-to-back. Actually, during execution, in an enforced bundle we only execute the first one of the several transactions from the same address and the others will be put to the end of standby list and get executed at the very last.

If a malicious validator want to enforce several partial orders among several specific transactions, its must try different transaction sets and thus different seeds for pseudo random generator, and see which one leads to an expected order. As the number of partial orders it wants to enforce increases, the computation needed for trying different seeds increases exponentially.

In the future, VDF will also be used to generate the seed for pseudo random generator, which can reduce the time window in which a malicious validator can try different seeds.