Full Leios without Ledger optimizations

[WhatisRT]

I thought I'd make a thread here about what I proposed on our last call. First, an overview: The Leios paper mentions the issue of speculative validation on page 8, specifically pointing to the bottleneck in account based ledgers and how it can be alleviated in UTxO based ledgers. My main concern is that this optimization adds a non-trivial amount of complexity to the ledger and that it increases the potential for DOS and resource attacks.

With the current smart contract design on Cardano, there is a collateral mechanism that results in the following guarantee: If a transaction passes all "basic" (e.g. all the crypto, accounting, etc) checks, it is guaranteed to be a valid transaction and we can include it in a block and collect its fees. This is a DOS prevention mechanism, since it means that you can only get the node to run the basic checks on a transaction for free. If you run a script for free, you could easily make very small but expensive to verify transactions which amplify the attack potential. For the basic checks however, given a fixed ledger state, the work necessary to do them scales linearly with the size of the transaction.

This guarantee goes away with speculative transaction validation, or more specifically speculative script validation. If we run scripts as part of input block validation, we run the risk of not collecting the fees in the case of conflicts.

It's a bit difficult to construct a proper attack out of this, since this depends on the details of IB validation, which we don't really have AFAIK. But in the simplest scenario, an attacker could make a single output, make different transactions spending it for every stake pool, and send them out. If they all get included in input blocks, say n in total, the attacker gets a multiplier of n` on work done for the paid fees. This is just a resource attack, but depending on the IB validation logic, there might be DOS attacks.

The way I see it, not doing that validation as part of IB processing introduces only a CPU bottleneck (if implemented correctly, otherwise there might also be a memory bottleneck), since it just comes down to delayed compute. It is well-known that CPU usage of Nodes is currently very low, so it might be very interesting to estimate how much slowdown this would actually cause and to compare this with other parameters. To do this, we could estimate our peak transaction throughput/peak transactions per pipeline and get numbers on how long the current ledger needs to validate mainnet transactions of one full pipeline. Additionally, we would need to know how much of that time is being spent on script validation.

I don't necessarily think that we need to do this soon, but once it's time to come up with a proper implementation plan I think we should definitely know these things.

[Saizan]

We want to keep in mind that current execution unit limits on transactions are a bottleneck/pain point for smart contracts, and from what I understand they are that small not because the nodes have limited CPU capacity overall, but because they have a limited time window to complete script validation. Speculative execution allows to spread out that work instead.

[WhatisRT]

That's true, but there might be an opportunity to relax this limitation. Currently all work is done sequentially without knowledge when the next piece of work arrives, so things need to be very quick. With Leios embracing parallelism, it might be fine if updating the ledger state lags behind since you'll still be able to make your input blocks.

[pagio]

I describe next some ideas on how to ensure that the fees of (most) of the transactions included in IBs are collected.
The design is based on the following ideas:

1. Shard txs based on the fee-paying UTXO

Assume txs have a (unique) designated fee paying input. By hashing this UTXO we get the tx's type.
Similarly, assume that IBs also have a randomly selected type, e.g., computed by hashing the winning VRF value.
Then, require that IBs contain only txs of the same type.
By making the number of types (say k) large enough, it is ensured that with high probability
no two IBs with the same type are generated within a slot interval of size w, and thus
fee-paying UTXOs included in these blocks are not doubly spend.

2. Avoid re-including in IBs txs seen on other valid (and on-time) IBs.

IB producers avoid re-including txs seen on valid and somewhat on-time (but not necessarily serialized) IBs received earlier.
There exists a minimum slot interval length l such that any IB not received after l slots will not be serialized eventually.
Length l can be used to parametrize the receive window within which an IB should be taken in account for this mechanism.
For large enough k, this ensures txs are not included in IBs of the same type (as these are far apart with good probability).

3. All transactions included in a serialized IB pay fees (if possible), even if they are not included in the ledger due to conflicts.

The idea is that the tx issuer is responsible for the creation of conflicting txs, and thus he/she should anyway pay
for the resources of the network it consumed. Consequently, smart contracts should be built in a way that avoids double spending and contention for the same resources.

Given these three ideas, and for appropriately set parameters we get that:

• Most of the time (with high probability) transactions included in blocks pay the required fees, and thus sufficient funds are gathered to pay SPOs.

• Txs are delayed from inclusion in an IB for some limited time related to l. Appropriately setting l limits to some small inclusion latency.

• By appropriate smart contract design, malicious parties cannot make honest parties' txs to become invalid at
  the ledger level, and thus good honest user experience is ensured.

We have not covered the case of maliciously crafted IBs that contain invalid txs. This case can be dealt with by adding a collateral from the side of the IB producer. I'll post more details in a subsequent post.

Note, that the design of concurrency safe smart-contracts is orthogonal to this solution.

[pagio]

1 is key to get 3. The idea is that you have a single input where the fee output "comes" from (is this a reasonable assumption/requirement to make in practice? I need your input on this). Then, IB producers only include txs whose fee is of the same type on each IB. Hence, for some desired interval, with some probability, no two IBs produced will have the same type, and thus no input related to a fee output would be double spend by two different IBs (as this would imply that they have the same type). (Here, I'm also assuming that we are only allowing using inputs that are in the stable part of the chain to pay for fees).
What do you think?

[WhatisRT]

I see. At the moment, we have a collateral field in the transaction body that contains inputs that are being spent if script validation fails. Those cane be multiple inputs, but in principle it might be possible to only allow a single output here. But maybe the better approach would be a single address, which is less restrictive but should offer similar guarantees. However, if we actually want to be able to keep track of stable and non-stable outputs in the ledger that might be a large piece of work.

[pagio]

So what happens in the current system if (i) script validation fails, (ii) collateral inputs are in the unstable part of the chain and are eventually lost, ? I suppose you are not getting compensated for your work. We can leave it like that for Leios, if we do not think it is a serious concern.

[WhatisRT]

Yes, that's the case. Note that script validation failure isn't even necessary for this case, the same thing happens if the script validation succeeds.

[pagio]

1 seems to have potential major drawbacks for latency. I'm not sure if we have the leeway to add additional latency on top of the latency hit we'll already paying for with Leios.

Regarding this point, note that users can submit the same tx with different fee-paying input UTXOs resulting in inclusion in multiple IBs, i.e, there is a trade-off of cost vs. latency here. While not optimal, it offers a way to speed up inclusion if really needed.

[pagio]

@WhatisRT Any other issues you see with this design? Otherwise, I'll try to write it down and get comments from a wider set of parties.