Slot of IBs in an RB versus slot of preceding RB and its IBs

[nfrisby]

The IBs included by an RB will likely lag behind it. For example, the RB in slot 200 will probably not have any IBs in slots 190..199.

Suppose X and Y are RBs such that Y extends X.

• Is it possible/intended that Y will include IBs older than some of the IBs included by X?
• Is it possible/intended that Y will include IBs that are older than X itself?

Especially with the "recursive EBs"/short-to-full spec, it's not obvious to me that the answer is No.

I ask because it seems very surprising if the IBs included by Y might "override/retcon" some of the IBs included by X (... conflicting txs is one example of this, but I'm not sure it's the only possible "override/retcon"). It'd resemble an "IB/EB" rollback without being an "RB rollback".

Remark. Txs directly contained in X is not a necessary condition for this topic, but it might make the question clearer: if X itself contains txs then they are presumably "in" the same slot as X. So the same surprise would be happening if Y's IBs have older slots than X itself.

[WhatisRT]

Yes, this is intended. A while ago there was a nice animation that shows how RBs can fill in old "gaps" in adopted IBs, which was probably shown at some Leios Monthly, but I don't quite remember. Maybe one of @will-break-it @bwbush @SupernaviX remembers (trying to guess who could have produced it).

We discussed this issue a bit at the Leios Workshop, and it seems we cannot "fix" the inclusion order later, because the state recomputation would be a nightmare. It also opens up all sorts of attacks forcing lots of expensive recomputations.

That means inclusion order must most likely be the RB order. One implication here is that you have "time-traveling" transactions, where slot order of transactions can be opposite to their inclusion order. This might be weird for smart contracts that keep track of time, but it's unclear if it would cause any problems. I don't think we have a full picture of all of the implications here.

[Quantumplation]

do we compare the tx's validity interval to the RB's slot or to the IB's slot

The latter, is my understanding.

And if the tx has a vote in it, eg, do we determine whether that vote is too late based on the IB's slot or the RB's slot (... has to be the RB's, right?).

No idea, that's a bit outside of my remit :) I'd assume IB as well, but 🤷

[nfrisby]

@WhatisRT please confirm: this question is below the level of detail in the formal spec, right? Seems like this field eg abstracts over it: https://github.com/input-output-hk/ouroboros-leios-formal-spec/blob/51157f83c2f52e02f74f26e2ae82a6ac70835c01/formal-spec/Leios/Base.agda#L42C11-L42C59

And now that I'm looking closer, it does seem a little off to me that the abstraction over the base protocol is expected to be able to process an RB and/or EB...

[WhatisRT]

And I think we have the property that any two txs that are chained or visible to each other via reference inputs will see monotonic slots, which should avoid causality problems even for oracles etc.

Sadly, this is not the case, at least not if you deliberately create transactions to violate this. You can just make a pair of transactions tx1, tx2 where tx2 depends on an output of tx1 but the validity window of tx1 begins after the one of tx2 ends. Then, you "just" manipulate block production such that tx2 makes it in first and then tx1.

For example, a tx might include a governance vote that is before the deadline in the IB in slot U but is after the deadline in the RB in slot V that references that IB. Yuck.

Indeed. This is odd, but I don't think it's a big problem since that can happen to you already on Praos if your transaction just doesn't get included at all.

In the second step, do we compare the tx's validity interval to the RB's slot or to the IB's slot?

I think it needs to be the IB's slot, since you want to include that transaction if it made sense in the IB's context. It's (presumably) not the transaction submitter's fault that it is so late so you don't want to collect the collateral for that reason, meaning it should make it in.

And if the tx has a vote in it, eg, do we determine whether that vote is too late based on the IB's slot or the RB's slot (... has to be the RB's, right?).

We don't really check time when you vote. If the GA is there for you to vote the vote gets cast, otherwise the transaction is invalid. So without changing the current logic you can just be unlucky and your vote gets tossed out. Which, again, can happen to you today already.

@WhatisRT please confirm: this question is below the level of detail in the formal spec, right?

Yes, we currently don't model the Ledger at all. And you're right, this is all part of the 'base chain' abstraction. Though maybe it'd be a good idea to split Praos and Ledger into separate abstractions so that we can model details of them independently if we want to include them.

[Quantumplation]

@WhatisRT but tx2 can't make it into a block first because it spends or references an input that doesn't exist; the local IB producers wouldnt include it in an IB unless it also included tx1, or tx1 was visible in the ledger state it was validating; or if they did, it wouldn't get included in an EB; nor would it be voted in by the stake.

So I guess this is dependent on which ledger state the IBs use, and how an EB recursive reference fills in the ledger state when the RB is produced.

Maybe this is an argument for validating against a recent (peras boosted) ranking block instead of doing something fancy. Having tx1 update a datum with a validity window from t3 to t4, then having it update with t1 to t2 could be very intuitive for scripts and might violate some assumptions they made for their security.

[WhatisRT]

Yes, there are schemes in which this is impossible. But if you don't have such a scheme then a malicious IB producer can do it even if it's unlikely. The question is what downsides are you willing to accept to prevent this type of behaviour.

There is a simple punishment based option here that might not be too bad. Because I can see after the fact that the producer of the IB that included tx2 was either reckless or malicious because it depended on a transaction that was either unavailable or known to lead to 'local time-travel' (if the IB producer knows about tx1). So we can punish this IB producer by e.g. not paying rewards for that IB.

Another option might be to remember the slot an output was produced in and reject blocks containing transactions that consume it before it was produced. That way this behaviour is impossible and it's prevented purely at the Ledger level. This adds a few bytes to every UTxO entry though (which can be shared a bit, but still).

[bwbush]

the IBs included by Y might "override/retcon" some of the IBs included by X

We need to forbid this. Otherwise, there is an opportunity for "retroactive front running".

[ch1bo]

Isn't the validity range of a transaction its complete "view" of time? i.e. there is no slot recorded in the tx and hence any slot within the validity range is valid and the actual sequence does not matter (as long as all inputs are available)

Or are there things in a transaction which affect its validity (or change its effect on the ledger state) that only depend on its inclusion sequence with respect to other txs? i.e. account based ledger style.

Edit: #372 (reply in thread) suggests that the latter is true.. which is worrying indeed!

[WhatisRT]

Yes, we do have a few things that are "account-like". Many of these are still somewhat safe in this context, e.g. withdrawals of reward accounts. You can only withdraw all your rewards at once, so the first transaction that gets in resets the state to zero and it needs to say how much lovelace are in your reward account. But some things aren't like that, e.g. certificates and votes.

A certificate usually is valid if the thing it's doing isn't already in the state. So if you deregister a DRep it actually has to exist, and if you want to register it it can't exist. So if you chain a registration and deregistation in different transactions either both transactions might be valid and effectively nothing happens (except your deposit might be different) but if they get in in the opposite order the final state is now different. For votes it's a similar thing, except that votes are always valid. So if you have two transactions with a 'yes' and 'no' vote on the same action respectively, the final state of your vote depends on the inclusion order.

However, all of this is already true today. The only thing that changes in Leios is that transactions that are invalid today might be considered 'conflicting' instead and actually be on the chain.