Structure and semantics of EBs and RBs, IB order, IB tiebreakers, etc

[nfrisby]

I'm unclear on the structure & semantics of EBs and RBs, in particular how exactly one should be applied to a ledger state.

I'm going to ask several questions here. If any are individually meaty, perhaps they should be promoted to a dedicated GitHub Discussion.

• The latest available paper that I'm aware of (https://iohk.io/en/research/library/papers/high-throughput-blockchain-consensus-under-realistic-network-assumptions/) refers to an "order" of IBs, but doesn't specify it as far as I can tell.
  • 
  • (I had a second Image of that same Figure 2 here, but I removed it due to Pi's clarifying comment below.)
  • I skimmed the rest of the paper, but didn't notice any clarifications.
• The evolving Google Doc that describes Short-Pipeline Leios and the Doc that describes its enrichment with EB recursion do not specify. (Edit: I asked some of these in Comments on that Doc; I'll summarize the answers as "that's a Ledger Design question, not a Protocol Question and so it still hasn't been studied".)
• The Agda spec just hands an EB to the base protocol---it abstracts over the details I'm asking about here.

Questions:

• I've only ever seen an RB listing one EB or none, never more than one. (Recursive EBs effectively let one EB represent many.) Has that been explicitly decided?
• Is there a restriction on the order of IBs within a valid EB? Even if there isn't, should the IBs referenced by an EB first be sorted by ascending slot etc or something like that before being applied to the preceding ledger state?
  • If IBs should be applied in slot-order, then doesn't the latency between an IB becoming public and being included in an RB provide an adversarial IB producer a (limited) opportunity to frontrun? An SPO would delay the production of their IB if elected early within some pipeline in case later IBs in that same pipeline make a big move that the SPO wants to frontrun. The duration they might usefully delay is bounded by one or two stage/slice lengths, which is still being tuned but is at least several seconds.
• With recursive IBs, does the order of EBs within an EB matter? Or should the entire EB tree be dereferenced to a bag of IBs, which is then sorted eg according to slot? (Edit: @pagio clarified that it's not a tree. When one EB refers to another, it inherits the references to IBs but not the references to EBs.) (Edit: see What if the ledger ignored blocks included via "Recursive EBs" and "Late IBs" that are from older pipeline instances than the EB in the latest RB? #390)
• If IBs should be slot-ordered, then what's the tiebreaker for IBs in the same slot? Since both can simultaneously earn rewards for being included in the chain (unlike RB tiebreakers), perhaps an objective random tiebreaker is sufficient (eg the election's VRF output is fine).

[Quantumplation]

I think set in that figure is a verb, not a noun 😅

[SupernaviX]

I don't think anyone has explicitly said that an RB only contains a single EB, but from the beginning our model has been that an RB only contains one endorsement and an endorsement only references one EB.

The rust sim hasn't had to figure out ordering of IBs or EBs, because it's not currently modeling conflicts.

[nfrisby]

Andre said below that certs aren't small, and so limiting it to one EB per RB seems important. And "recursive EBs" means not much expressiveness is lost.

[WhatisRT]

• I've only ever seen an RB listing one EB or none, never more than one. (Recursive EBs effectively let one EB represent many.) Has that been explicitly decided?

I don't think this question has been discussed much, but I think including more than one EB might not be so great because of the size of the certificate that needs to go into the RB. It also doesn't offer much benefit, since if you have multiple EBs in one pipeline the EBs that didn't make it can be included in future RBs via EB references. That means slower settlement for unlucky transactions but I'm not sure if this would actually be a problem.

• Is there a restriction on the order of IBs within a valid EB? Even if there isn't, should the IBs referenced by an EB first be sorted by ascending slot etc or something like that before being applied to the preceding ledger state?

  • If IBs should be applied in slot-order, then doesn't the latency between an IB becoming public and being included in an RB provide an adversarial IB producer a (limited) opportunity to frontrun? An SPO would delay the production of their IB if elected early within some pipeline in case later IBs in that same pipeline make a big move that the SPO wants to frontrun. The duration they might usefully delay is bounded by one or two stage/slice lengths, which is still being tuned but is at least several seconds.

It seems that frontrunning is possible no matter what. If an EB producer can order things arbitrarily they can use any IB under their control of the same pipeline to frontrun. If we impose an order (slot order seems to be the most obvious one) then they have fewer opportunities because they need to wait with publishing some IBs as you describe. This is a more risky strategy for them (if they wait too long the IB might not make it into the pipeline). Also, note that frontrunning (in the UTxO set) always relies on conflicts (any transaction that doesn't conflict commutes, and so it can also be included in a later block) so all the collateral/sharding discussions apply.

• With recursive IBs, does the order of EBs within an EB matter? Or should the entire EB tree be dereferenced to a bag of IBs, which is then sorted eg according to slot?

I don't think the order of EBs should matter, sorting by slot makes more sense to me. But I don't have any good arguments here right now.

• If IBs should be slot-ordered, then what's the tiebreaker for IBs in the same slot? Since both can simultaneously earn rewards for being included in the chain (unlike RB tiebreakers), perhaps an objective random tiebreaker is sufficient (eg the election's VRF output is fine).

I think all we need to do is to make sure nobody gets an advantage in the case of conflicts, so the VRF should be fine. This also has some effect on rewards since conflicting transactions may pay different fees, so you could try to optimize for that. But that gives you more frontrunning opportunities again.

[nfrisby]

Also, note that frontrunning (in the UTxO set) always relies on conflicts (any transaction that doesn't conflict commutes, and so it can also be included in a later block) so all the collateral/sharding discussions apply.

If some real-world dApp (eg an exchange) relies on the order of Cardano txs to determine when things actually happened in the real world, then frontrunning txs don't necessary conflict. (I don't know whether that's such a bad idea for reasons I haven't considered that no reputable dApp would do it?)

[bwbush]

The paper seemed to imply that IBs were order by their message ID, but I now see that isn't explicitly mentioned.

Also, the front running problem might be more severe if txs are allowed both in RBs and IBs. Opportunities are smaller if txs are not allowed in RBs and IB are strictly ordered by (slot, VRF).

[ch1bo]

I don't see the problem, I probably missed something? Your question seems to imply that we would record a slot in IBs, which I have not read anywhere so far and (gut feeling) am not sure if that would be a good idea?

So I went ahead in sketching an answer to challenge my understanding:

---

• RBs decide on the sequence of EBs (0 or 1?)
  • EBs decide on the sequence of IBs
    • IBs decide on the sequence of txs

Validating an EB in order to vote or not, we need to (re-)validate all referenced IBs / txs in the endorsed sequence against either (a) the current slot (b) a slot recorded in the EB or (c) the last RB + 1 (as you said is used in the praos mempool). To make the vote as independent as possible of timing (b) or (c) would probably work better?

Especially for "late IBs" this could mean that some txs are not valid anymore (e.g. validity range exceeded). This should be avoidable by the EB producer by not endorsing the now invalid tx in the first place? Depending on protocol variant this can either be done by not referencing the IB/tx or blacklisting ("tombstoning") the tx.

I don't see why we would want to complicate this process by allowing an EB to reference past EBs and not just "pick up" the IBs of a past, certified, but not included EB instead? This would imply those IBs transactions will need to be valid in whatever sequence the current EB endorses them and everything from above would apply equally.

Validating an IB is only done to not forward invalid data through the network ¹ so using the current slot should suffice. The ultimate sequence and thus slot is decided by the EB.

Validating an RB means validating the EB if one is contained. In case (a) or (c) from above, where no slot would be recorded in an EB, the certified sequence of txs (or some of the txs) might become invalid against the slot of the RB. We could employ a similar technique where a (ranking) block producer would only include an EB referencing a valid tx sequence. If some txs are not valid anymore the blacklisting technique could also be used here?

In summary, I think I would propose to have RBs determine the "passing of time" on the chain and ideally all txs validate against them. This would be the same "ledger experience" as you would get if the system runs in "Praos mode" where your transaction is ultimately included in one or the other block; whose exact slot you would not be able to predict nor given access to as a transaction creator.

Footnotes

1. IMO it is the same as tx diffusion ↩

[Quantumplation]

Your question seems to imply that we would record a slot in IBs

I haven't read the rest of your post yet, but yes, this is implied by us doing a VRF lottery to produce IBs. Whether we use that slot is the question.

[WhatisRT]

in order to vote or not, we need to (re-)validate all referenced IBs / txs in the endorsed sequence

I don't know why everyone thinks so much validation work is necessary. Especially in the case of EBs (but also in the case of RBs that don't contain transactions themselves) there isn't any decision to be made based on the contents of blocks. If you get an EB that references valid IBs and has all the right properties you vote for it. The contents of the IBs don't matter because they're already valid (whatever that means) - there's nothing else to learn from it that would make you reject anything. Yes, you can learn about conflicts, but you're not going to reject a block because it has too many conflicts or something.