Certified EBs stuck in Limbo?

[SupernaviX]

If I understand the protocol correctly, Leios EBs will be generated faster than Praos blocks which could include them. We generate one Praos block every ~20 seconds, but some number of EBs every L seconds (and presumably L < 20). Every Praos block can reference exactly one EB, and (in Simple Leios at least) those EBs cannot reference other EBs. If L == 5, every 20 seconds we expect to "build" 4 pipelines' worth of EBs, but only "use" 1.

My concern is, in the happy path I don't think those 3 extra pipelines' worth of EBs ever go away. An individual IB can "expire" if no EB includes it in time, and an EB can be safely ignored if it doesn't get enough votes in time. But once an EB has enough votes, it "could" get included in an RB at any time. Even if the transactions it references expire or conflict with the base chain, the EB could still be published. And during periods of low TX volume, some EBs won't reference any transactions at all. if I understand the protocol right, an "empty" EB minted in 2025 could still reach the chain in 20025. And we'd expect nodes to store that certified EB, all of its referenced IBs, and a few hundred votes for all those millennia.

This seems like it causes a few problems:

• Most transactions will never make it on-chain, because they're included in an IB in a bunch of EBs in this limbo state. If L == 10 than I'd expect half of all transactions to reach that state, and lower values of L would generate more (smaller) EBs and make the problem worse.
• The set of certified EBs in limbo will grow constantly over time, even though older/emptier EBs would probably not be worth including on-chain.
• Even if we discard certified EBs after enough time has passed, we'd still only be publishing a fraction of all generated IBs unless Leios stage lengths were at least 20 slots.

My questions:

• Am I right that this is a problem in Short Leios, or did I read the research paper wrong (or incorrectly assume that L should be small)?
• Is this also a problem in Full Leios. or do chains of EBs allow us to avoid it?
• If we know that a given IB can no longer reach the chain, should we put its transactions back in the mempool?

[Saizan]

Certified EBs needing an expiration is something to be worked out: #26 (reply in thread)
What to do with TXs in corresponding IBs is interesting, but most likely by the time the EB expires you'd want to make a new one? So maybe it's fine to have this behave similarly to rollbacks, where you need to resubmit.

Although, regarding Full Leios it would be good to clarify the meaning of lemma 4.2:

Half of all successful pipelines are covered from the base protocol.

does this mean that even in Full Leios half of the pipelines won't have any EB that is included (directly or indirectly) in a RB? and so their IBs with them?

[SupernaviX]

So maybe it's fine to have this behave similarly to rollbacks, where you need to resubmit.

My worry with that is, rollbacks are relatively rare, but EB "expiration" will happen more often than not.

[SupernaviX]

Quoting the paper:

It is therefore necessary to produce EBs at a rate high enough such that there is at least one honest EB for every block in the base protocol.
However, at such a high rate, not all EBs can be included in the low-throughput base protocol, and including only a subset of all EBs will not solve the fairness problem since it is unclear which EBs are from honest parties. Leios therefore adopts an approach wherein EBs may also reference other EBs.

That's encouraging! It makes it sound like since Full Leios can reference EBs from prior pipelines, it wouldn't suffer from a constant buildup of old EBs. But I still think that Simplified Leios has the issue, since EBs only reference other EBs from within the same pipeline. And Short Leios has the issue too, since EBs don't reference each other at all.

[Saizan]

Indeed, though given that lemma 4.2 quoted above is about Full Leios it's unclear to me if we should still expect a significant amount of "stranded" pipelines even in that version of the protocol.

[pagio]

@SupernaviX @Saizan :

• Regarding the claim about Lemma 4.2, I copy from the paper: "All successful pipelines are covered from the base
  protocol, except with probability ...". See here : https://iohk.io/en/research/library/papers/high-throughput-blockchain-consensus-under-realistic-network-assumptions/ . What is the source of the other claim ?

• In general Simplified Leios and Short Leios do suffer from the issue you mentioned @SupernaviX . The issue is resolved by adding the Full Leios modification (it can be added in both of them), which basically allows EBs referencing older certified EBs. As I mentioned above, this will allow all pipelines where a certified EB was created to be covered by the base protocol.

[Saizan]

@pagio I see, my source was the version under docs in this repo: leiospaper-submitted.pdf, probably best to remove it then.

[SupernaviX]

@pagio it sounds like the slot length for Short Leios is likely to be ~20 anyway, which also resolves the issue. On average, certified EBs will be consumed at ~the rate they are produced.