CAP: 0014
Title: Adversarial Transaction Set Ordering
Authors: Jeremy Rubin
Status: Draft
Created: 2018-11-16
Discussion: None
Protocol version: TBD
As of protocol version 10, orders are sorted in protocol such that transactions for an account are sorted by sequence number (ascending) the order between accounts is randomized. We propose leaving the transactions un-sorted, but checking that the order satisfies certain properties.
As of protocol version 10, orders are sorted in protocol such that transactions for an account are sorted by sequence number (ascending) the order between accounts is randomized. We propose leaving the transactions un-sorted, but checking that the order satisfies certain properties. The new properties ensure that transactions can apply in-order, but permit a malicious nominator to easily place a specific transaction to occur before another. This is not a change from current behavior, because a nominator may (with a small number of tries), adjust the TxSetFrame to place that transaction in front anyways.
The current requirement of a randomized sort is intended to prevent malicious nominators from front-running a transaction, but it does not achieve that goal because a nominator may front-run a transaction in small number of trials.
Randomized ordering does, however, neccessitate that the result of a transaction is tri-valent (succeed, fail, invalid).
If instead, we force the order to be determined by the nominator according to some rules, this opens the door to them only including transactions which succeed in a TxSetFrame.
It also, as a side-benefit, reduces the asymptotic latency of validating a ledger because the ordering must only be verified by each node.
In this version we iterate over the TxSet transactions and check that they are in a valid order with respect to the sequences of each account such that each transaction can be applied. This implies nominators must propose the exact ordering validly.
We also eagerly consider BumpSequence operations during this check to ensure that transactions are also properly linearized with respect to BumpSequence. This implies that certain types of transaction graphs with two BumpSequences may be impossible to linearize, however we specify that the ordering of transactions may change in future ledger versions so this cannot be depended on.
This ensures that the mTransactions are sorted in an order such that the transactions can all be applied and consume a Sequence number.
We do not check for any other property to allow flexiblity for the nominator to decide the ordering.
For previous ledger versions we must maintain the old behavior.
Making this adjustment makes it more clear that relying on the randomization of the transaction set ordering is an anti-pattern because it is insecure; the order that the nominator selects is arbitary and attacker-controlled.
Checking consistency given BumpSequences fixes an issue which can cause fees to be paid unexpectedly with a contract written to use bump sequence.
The old sorting algorithm for sortForApply and sortForHash must remain for
ledgers with earlier versions.
Nominators wishing to propose a TxSet in a valid order may simply call sortForApply with a salt of their choice to generate a valid ordering, and then run through the transactions to eliminate any transactions which break the BumpSequence linearization invariant. There is no requirement that this is the order though, any valid order suffices.
In new versions, we may want to enforce stricter rules on the order of transactions.
The arbitary ordering at the nominator layer makes it easy for futures changes to further constrict the behavior, e.g., enforcing that the ordering must be such that no transaction fails in the ledger, enforcing that the ordering is grouped by account, etc.
Such changes are then something that downstream software must already be able to handle witout surprise.
It's possible that CAP-0014 does not specify a forwards compatible set of rules, in which case the rule should be incompatibly updated. Because we specify that the linearization properties shall not be relied on for future ledger versions, this does not break expectations but may require rewriting software designs.
If there is a need for other orders for compact lookup proofs for light clients, the commitments should be generated and verified separately from the base ordering.
None yet.