Canonical order not respected

[tuloski]

See: https://www.xrpchat.com/topic/23466-found-transaction-not-ordered-with-canonical-order/?tab=comments#comment-396136

I found a ledger where the same account has two transactions with TransactionIndex = 43 and TransactionIndex = 49.

Shouldn't all transactions of the same account in one ledger be consecutive? Or was the canonical ordering changed recently?

[nbougalis]

Canonical order comes in play in how we apply transactions, and under canonical order it is true that transactions are ordered first by account and then by sequence. However, this doesn't mean that they will, necessarily, be consecutive.

The relevant part is https://github.com/ripple/rippled/blob/develop/src/ripple/app/consensus/RCLConsensus.cpp#L678-L723, which attempts to apply transactions in canonical order. But it does so in multiple passes, and within each pass transactions are executed in canonical order.

By way of example, let's say account A sorts before account B. Let's also say that Account A has two transactions, called A.1 and A.2; it doesn't matter what they are. Let's say that B has one transaction, called B.1 which sends 100 XRP to A.

The only transactions to apply are A.1, A.2 and B.1, and their canonical ordering is A.1, A.2, B.1.

We begin Pass 0:

• We attempt to apply A.1. The transaction succeeds, but it causes the balance of A to drop below the reserve;
• We attempt to apply A.2. The execution can't succeed because A doesn't have enough XRP. We mark A.2 as retriable and continue;
• We attempt to apply B.1. The transaction succeeds, raising A's account balance above the reserve.

Pass 0 is now done. Since there's one transaction that can be retried (A.2) still left, we begin Pass 1:

• We attempt to apply A.2. The transaction succeeds.

Pass 1 is now done. Since there are no transactions left, we are done.

In the resulting ledger, the ordering is A.1, B.1, A.2.

[JoelKatz]

When the ledger design was originally written, we considered each transaction precious and tried to get it the best possible outcome. If a transaction got an outcome that was clearly not optimal -- for example, if a payment couldn't find enough liquidity or the sender had insufficient funds -- we would retry that transaction on a later pass in the hope of getting a better result.

This doesn't really align with our current philosophy of minimizing the effort done for each transaction to keep transaction fees as low as possible and transaction throughput as high as possible. But many cases where this can happen still remain in the code.

Since transactions issued by the same account cannot be reordered relative to each other and must execute in their numbered sequence, hitting a retriable transaction causes us to skip to the next account in canonical order. During the "final" pass, all results are accepted as is since there's no way to try again in the same ledger.

[tuloski]

As curiosity: if an OfferCreate transaction has FillOrKill flag and in the "first pass" there is not enough liquidity such that it should be killed, can it be delayed to next pass where the liquidity can become available, or it just get applied and killed? Also in my case the second transaction (the delayed one) was an OfferCreate (without KillOrFill): I can't see a condition for which the transaction is delayed because it can get better with more transactions to come. Maybe when it's unfunded?

PS: BTW it's nice to learn something new about RCL every time :)

[JoelKatz]

The old philosophy was to return a "ter" (retry) error if this wasn't the final transaction pass. That would cause the transaction to be retried on subsequent passes in the hopes that it could obtain a better result. Very few transactions still follow this old logic. The thinking now is that it's more important to minimize resource consumption than to try to get each transaction the very best possible outcome.

There are still some cases that follow the old logic, but they tend to be cases where it's a very early check (so few resources are expended) and something unusually likely to succeed on a retry. A good example would be a CreateOffer transaction where the issuer account doesn't exist. It's a very early check and it's possible that the issuer account was just created by a payment and your transactions are just executing in the "wrong" order.