Transaction diffusion

[ch1bo]

The paper(s) and all write-ups of Leios I have encountered so far (while catching up) are all starting from IBs. That is, transactions are put into IBs and those would be diffused across the network.

However, on a real system transactions would need to be diffused through the network such that block producing nodes have them ready to put them into blocks - this would be true for Praos (normal blocks) and Leios (input blocks).

Does this mean that transactions would be sent twice across the network still in Leios?

[SupernaviX]

That's my understanding, and the Rust simulation is simulating that.

[Quantumplation]

Yes, this is something I raised fairly early on; We've toyed with the idea of having input blocks be the "unit of diffusion", but haven't written down a concrete proposal as of yet.

The leading candidate at the Leios workshop was something like:

• Nodes can register as "IB Producers"; this would be wallets, blockfrost, or dApps like Sundae
• They get assigned some portion of the IB capacity, via a VRF, to minimize spam
• They accept transactions from users and put them directly into IBs, and propagate them around the network
• The network has some reasonable base-level of production that any SPO can utilize that uses the typical propagate / mempool arrangement, for censorship resistance, but it's not expected to be the primary source of txs

This would help avoid honest duplicate transactions (since txs aren't propagating to multiple mempools before the IBs are produced in parallel), but wouldn't protect the network from maliciously conflicting transactions. A user could submit two conflicting txs, one to blockfrost and one to maestro, and they would have no way of knowing not to include those txs.

[WhatisRT]

To see why input blocks are useful, let's make a little thought experiment. Let's change two things about IBs:

1. they must contain exactly transaction
2. anyone can produce them permissionless

I think it's pretty clear that with these two changes, an IB basically is a transaction. I.e. this would be the same system as the one described where EBs reference transactions directly and one could get rid of the mempool.

I think it's pretty clear that 1 is a nice feature, it lets you batch a bunch of transactions together. We can also easily add this to the IB-less design, so it's not very interesting. So really, the main issue here is whether the data EBs endorse is produced permissioned or permissionless.

In a permissionless IB production scenario, you have more ways to overwhelm the network. You can imagine sending a different valid IB to every node on the network, meaning you've caused n^2 traffic in n work. If you leverage conflicts (which you might, because we may not be able to have sharding in a permissionless system) that attack would cost you < 1 ada/s to execute (one transaction fee per settlement time window). I'm sure you also have other attacks as well in such a scenario.

This is why the option Pi mentioned at the top is probably a good middle ground. It's not permissionless since you'd have to register to be able to make IBs and the rate at which IBs can be made is limited by the protocol. But within the parameters of the system you can make your own IBs whenever you deem sensible. And if you make bad IBs (e.g. if we see you producing conflicts) we can just take some collateral to make up for extra work. With that system we also might not need much of a mempool, since each light wallet could just register its centralized server as an IB producer. A mempool would still be required, but most transactions would skip it.

[pagio]

My intuition says it's something about IBs providing the right tunable granularity for parallelism

The way I would put it is that we want to decentralize block production. A single person deciding what these 15000 txs will be has too much power and a big target above its head. Instead, with the current system, the EB producer has to include all honest IBs, otherwise its EB will not be upvoted, and which txs are selected is decided by multiple SPOs.

[ch1bo]

@WhatisRT Let me strongman your scenario of 1 IB = 1 tx and permission-less transaction diffusion. That is exactly the system that we have today with Praos (strike-through annotation by me):

In a permissionless IB tx production scenario, you have more ways to overwhelm the network. You can imagine sending a different valid IB tx to every node on the network, meaning you've caused $n^2$ traffic in $n$ work.

I don't think this would be the case as also today, you could try to send different valid transactions to every node on the network, but the Ouroboros network requires txs to be valid to propagate. See here in the consensus blueprint and the good ol' ouroboros network design docs. This is precisely to avoid asymmetric resource attacks like the one you describe. Intuitively, we can only create so many valid transactions as we have funds to spend. If we consider conflicting transactions only one of them will eventually remain in the network's mempools. If a node consistently serves invalid (= not applicable to the ledger state) I think we would consider that peer as adversarial and eventually stop talking to it.

---

Instead, with the current system, the EB producer has to include all honest IBs, otherwise its EB will not be upvoted, and which txs are selected is decided by multiple SPOs.

@pagio I understand this would also be the case in a design without IBs? If an EB would be proposing a list of transactions (instead of a list of IBs) upon which SPOs vote if they have those transactions available and they sequence is valid against the tip of the chain (just the same way as they would vote on IB availability). Which SPOs are eligible to select txs (= produce EBs) would be unchanged and decided by the EB lottery as far as I understand?

[WhatisRT]

I don't think this would be the case as also today, you could try to send different valid transactions to every node on the network, but the Ouroboros network requires txs to be valid to propagate.

Yes, but validity is the key difference here. In the mempool scenario, validity of a transaction may change because of conflicts, but validity of IBs cannot change. So if those n adversarially produced IBs are valid then they have to be delivered to all the nodes in the network even if only one of them contains a transaction that will be valid after serialization. There isn't really a way to drop IBs, and I'm pretty sure if we introduce any rules to do so it'd allow an adversary to censor or slow down the chain.

[WhatisRT]

For the particular proposal of "let's have EBs just reference transactions from the mempool", the issue is now that with the current mempool you have a size constraint and you're allowed to drop inconsistent transactions. So an EB could reference transactions you don't have in your mempool, possibly because you rejected them.

There's also a secondary issue, which is that conflicts actually must end up on chain. Node operators must be rewarded for the work they do, and so if different parts of the network see different conflicting transactions first & check them, they should be rewarded for that work. And a consistent mempool prevents that as well.

[nfrisby]

[The higher-level concern of this Discussion might supersede the rest of this comment. But I wanted to point out the similar area of concern.]

The Consensus Team has also been wondering about how today's Mempool would need to change for Leios.

• Currently, the Mempool maintains a list of all transactions that have been received and are valid with respect the node's current selection (ie its RB selection).
• My understanding is that in Leios each IB declares which ledger state (by identifying some RB) its txs should be validated in.

If there's no restriction (for security and/or performance reasons) on how young that RB reference can be, then I suppose the only change necessary for today's Mempool is that it'd be flushed into a fresh IB instead of being flushed into a fresh RB (assuming for now each RB only contains EBs). But if there is a restriction on its age, then the Mempool's current dynamics would need a related adjustment.

Also, Leios requires some "mempools" within the sequence of IBs -> EBs -> RBs. But those don't seem drastically different than today's Mempool other than which objects they contain. They'd still need to be updated as the local selection advances, eg. Although maybe their (multi-dimensional) size limits could be simpler?

Edit: and of course, sharding seems like it might require significant alterations.

[ch1bo]

My understanding right now is that most of the Leios design documents have not considered the mempool at all.

Replicating a mempoool of valid (!) transactions across the network seems to be serving the same purpose of diffusing IBs.

[bwbush]

My understanding right now is that most of the Leios design documents have not considered the mempool at all

A couple of the google docs discuss mempool and temporary blacklist of txs in them.

[bwbush]

If txs are assigned to shards, then the mempool may have to be logically split into shard-specific mempools. Otherwise, a DoS on a shard ID could starve other shard IDs from the mempool.