Order IBs by slot and VRF to limit EB producers discretion on Tx order.

[Saizan]

Currently ledger construction is specified to obey the order in which IB and EB references appear in EBs.

Ledger Construction. To extract the ledger, a party can parse the
ledger of the base chain, and list all referenced (Vote2-certified)
EBs by order of appearance; from this list, the party can extract
a list of Link-stage EBs (also in order of appearance), and finally
sequence all therein referenced IBs, finally defining an ordered list
of ledger transactions.

The above allows EB producers to influence how Tx conflicts are resolved, since the conflicting tx that is later in the sequence will be dropped. This kind of discretion raises concerns about the fairness of the system. A more predictable ordering of IBs could also open some preprocessing opportunities.

We could instead specify that to sequence the IBs referenced by an RB we should order them lexicographically on their slot,subslot, and VRF proof, with the appearance order as a tie breaker for the rare case the above fails.

IB producers still have discretion on which Txs to include in which order, which is not uncontroversial, but that's on par with Praos blocks today.

[dcoutts]

I completely agree that we do not want order to depend on the discretion of EB or RB producers (indeed this point is included in the first Leios CIP).

I see two plausible approaches, order IBs in the RB by (lexicographically), either by

1. (EB slot, EB VRF, IB slot, IB VRF)
2. (IB slot, IB VRF)

So the first option groups by EB, while the second interleaves IBs from different EBs.

Why might we want to group by EB? If we want a scheme where dependent transactions from different IBs can be included into blocks quicker than waiting for them to be included into an RB, then we would need EBs to be more frequent and IBs to reference previous EBs. In that case, we may want to group by EB so that we can usually reuse the EB ledger state.

[pagio]

All these sound reasonable to me. We should revisit this part as the ledger/mempool discussion gets more mature.