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.

[Saizan]

Regarding the workshop discussion about EB ordering, I think we should clarify whether we want the following property.

Definition Transaction stability.

• If a transaction is committed in a chain, then it will stay committed in any extension of that chain.

where a Tx is committed in a chain if it appears before any conflicting Txs in the order used for ledger construction. The intent is that the outputs of a committed Tx are in the ledger state of the tip, or have been consumed by another committed Tx.

At the level of RBs, to maintain transaction stability, it's sufficient that any new Txs added by a later block (directly, or by reference) are ordered after the Txs of its previous block.

The above is why I framed this discussion as deciding the order of IBs within a single RB. In a chain RB[n] <- RB[n+1] you could in principle have

RB[n] := EB[t+k]
RB[n+1] := EB[t]

and a pair of conflicting txs tx0,tx1 where tx0 is in (an IB in) EB[t] and tx1 is in (an IB in) EB[t], and which have no other conflicts.

For RB[n] we have that tx0 is committed. For RB[n+1], as long as we don't reorder across RBs, we keep tx0 committed, discarding tx1. However, if ordering by EB slot takes precedence, then RB[n+1] would toss tx0 out and consider tx1 committed instead, losing transaction stability.

Going back to the issue of ledger states for EBs, you could similarly enforce you can't reorder across EBs: if EB[n] references (even indirectly) EB[m] then any new Txs/IBs from EB[n] are later than any from EB[m].

Note that this can be a little awkward because EBs form a DAG. In particular in Full Leios, using i as a pipeline index, you might typically have a sequence

EB[i]   := {ebs: [EB[i-3],EB[i-4],...], ibs: [IB[i  ]]}
EB[i+1] := {ebs: [EB[i-2],EB[i-3],...], ibs: [IB[i+1]]}
EB[i+2] := {ebs: [EB[i-1],EB[i-2],...], ibs: ...}
EB[i+3] := {ebs: [EB[i  ],EB[i-1],...], ibs: ...}
EB[i+4] := {ebs: [EB[i+1],EB[i  ],...], ibs: ...}

where, assuming IB[i] and IB[i+1] have conflicting txs, some transactions committed in the chain for constructing the ledger of EB[i+1] are no longer committed in the chain for EB[i+4], because the ones from EB[i] take precedence instead. Basically there's a sliding window of 3 pipelines which should be considered concurrent, because we don't have direct references and transaction stability does not apply.

It gets worse though, the Tx order given by just the graph of EBs might not agree with the Tx order from the chain of RBs: it can easily be that we have a chain segment RB[n] <- RB[n+1] with:

RB[n] := [EB[i+1]]
RB[n+1] := [EB[i+4]]

but now the chain for RB[n] already includes IB[i+1], while IB[i] is only included with RB[n+1] and so we should order IB[i+1] before IB[i] for ledger reconstruction, which is the opposite order you get when looking at EB[i+4] alone.

[Saizan]

@dcoutts it doesn't look like enforcing that we only include in a new RB an EB that references previously included EBs is enough. In fact my example above is already respecting this constraint but poses a problem.
Here's a diagram to illustrate the situation, relative position of blocks is according to generation time. Not included is RB[n-1], which we assume references some older EB all of these reference.

Because IB[i] is only referenced by RB[n+1] then it should come after all IBs referenced by RB[n], so in particular after IB[i+1], otherwise we would violate transaction stability (see post I'm replying to). However, when generating/validating IB[i+k] we only have EB[i+4] to go by, so we don't know how to order IB[i] and IB[i+1] in a way that will be consistent with which EBs will be referenced by the future RBs.

Note that because of the structure of the pipeline EB[i+1] is generated when EB[i] is just starting to be voted on, so the lack of reference here should be expected. RB[n] on the other hand we would expect earlier, but I figured this timeline would make my point clearer.

[WhatisRT]

I think the transaction stability you define is almost a requirement. Without it, you could imagine an adversary withholding an IB containing a transaction that brings down a long chain of other transactions, forcing recomputation of a lot of state. And, depending on the details of the system, it might be possible to withhold multiple such IBs, revealing an earlier one every time such an upset of the ledger state happens. Not only would that waste a lot of resources, it would also really hurt the confidence in the system.

[Saizan]

The protocol needs to forbid old enough EB/IB from making it into the ledger via a new RB just so they can be dropped from storage, but I think your point still stands: there's a cost to rolling back the ledger state, especially over a long sequence, so we don't want to introduce new ways to trigger it (it already happens with forks, but thankfully those are typically short).