Imperfect atomic execution

[nikeshnazareth]

Overview

• I had some thoughts (two incremental ones and one interesting one) that could improve the flexibility of rollups
• They seem to work well together
• I haven't really thought them through in detail. I just want to put the ideas on the table so we can riff on them.

Include post-state in publication

The first incremental idea is that I think the proposer (excluding the delayed inclusion publications) should include a claimed L2 state root (ie. the checkpoint after applying this publication) within the publication as one of the attributes. The whole publication should be considered invalid if it does not result in this root.

The idea is just to exploit an existing asymmetry:

• there is a very valuable piece of information (the new L2 state root) that users want to know
• the proposer already knows it and it would be trivial for them to tell us
• we should give them a strong incentive to do so

This is, of course, not a proof that the publication is valid but some observers might consider it enough. I think this is just an extension of the insight that security is a property of the confirmation rule. Depending on your use case, you might require a transaction to be finalized, or 6 blocks deep, or optimistically "proven", or just proposed, or preconfirmed, or in the mempool, or whatever. In all cases you're comparing the probability that this is a reliable indicator against the value of whatever you're doing. This suggestion is a simple and cheap way of creating a pretty strong signal.

Make invalid post-states a slashable offence

This is an extension of the same idea. We have already assumed a bunch of infrastructure is in place to encourage proposers to make preconfirmations. We can reuse it to encourage everything else we want them to do. I also think that binding their stake to group properties like the state of the whole chain can reduce the scope for shenanigans.

In this case, it could be something like:

• if the claimed root is invalid, the proposer's stake is slashed
• in addition to providing their own state root, the next proposer has to indicate whether they're building on the previous one (or whether they consider it to be a no-op). In this way, agreement/disputes are automatically recorded in order to increase the strength of the signal. Perhaps the next proposer should receive some of the slashed stake on a successful dispute.
  • I realise this sounds like the optimistic rollup mechanism, but it doesn't change the fact that actual proofs are still required.
  • I wouldn't suggest this if the proposer weren't already staked (because of centralisation concerns) but since we've already accepted that condition, we might as well include the optimistic signal while waiting for the proof.

We should consider if there are other properties that could also be slashable offences. I have a tentative design for a partial atomic execution mechanism, but it requires a new transaction type and it might not be necessary if the next idea makes sense.

Condition transactions on future rollup states

My interesting idea is that I think it should be possible for user transactions to be conditioned on the final state that is posted to L1 at publication time, which could be useful for things like flash loans that span multiple transactions. We can even do it across rollups, which can be useful for (partial / imperfect) atomic execution.

Background

This seems to me to be a generalisation of Nethermind's single-slot L1 -> L2 mechanism. Let me try to explain that through a particular lens. As I understand the mechanism:

• A user makes a transaction on L1, which creates a permanent record in the L1 signal service
• The proposer sees this and can tell a contract on L2 that it occurred.
  • in this case the signal was a deposit and knowing that it occurred allows the L2 bridge to mint a token, but the details are not relevant for my point.
• This will eventually be validated at the time of the publication (or at least, the L2 requires those signals to be included in the anchor transcation and the signals that are claimed to exist are checked at the time of publication)
• Importantly, since the inbox checks the L1 signal service at publication time, it's really only checking that the signal was sent at some point before the publication. The proposer can rely on this signal existing because there is no way to clear the signal from the L1 signal service contract.

To emphasise the point (but this is not an actual suggestion), if the L1 proposer was confident at some time X, that a signal would be published to L1 at some later time Y, before they were required to submit their publication at even later time Z, then they could inject the signal into L2 at time X. As far as I can tell, nothing about the rest of the publishing or proving mechanism can distinguish if the signal was actually published at X or Y - we just need to ensure it exists by Z.

Future L2 states

My extension is that the same logic is true (and more powerful) for L2 states. If the L2 proposer can predict an L2 state (which he should be able to, because he has 100% control over all transactions), then he can inject that state earlier into the stream. Moreover, the requirement that the conditioning state (the L1 signal) must be write-once was a consequence of the proposer needing to know it will still exist at publication time. In the L2 case, we can allow them to use multi-use storage slots, and bidirectional conditional dependencies.

For example, imagine the rollup introduces an SLOAD_AT_PUB_TIME opcode. An example scenario is:

• there is a multi-sig wallet that increments count when the sign function is called
• it requires at least three signatures at publication time to call execute
  • this means its execute function is guarded by something like require(L2_state_at_publication_time.count >= 3)
• Alice and Bob both publish sign transactions to the mempool
• Charlie publishes a transaction that calls sign if his DAI balance is at least 50 before publication time.
• Diane, who wants the execution to go through, sends Charlie 50 DAI conditional on the signal that execute was called existing at publication time.

The L2 proposer sees all of these transactions in the mempool and arranges them in any order.

• he knows L2_state_at_publication_time.count will be three, so he can inject that value when processing the execute call.
• he knows the L2_state_at_publication_time.message_sent boolean will be true, so he can inject that value when processing Diane's call
• he knows L2_state_at_publication_time.dai.balances.charlie will be 50, so he can inject that value when processing Charlie's call.

Eventually when he makes his publication he includes the final L2 state as one of the attributes.

• the provers can check that all of his injected values match this state.
• if the final result is not equal to that state, the whole publication is invalid.

(Imperfect) Atomic Execution

I think the same basic logic applies across different rollups, with some caveats.

Consider a proposer that is building blocks for two rollups. The expected behaviour is for him to:

• package both sets of transactions into the same blobs
• call publish on both rollup inboxes in the same transaction, so they can share the blobs
• this will produce two different publication hashes, one per rollup

Under my previous recommendation, they would also publish the claimed state root as an attribute in each publication hash. We could also require them to forward both state roots to both inboxes. We will need to verify they are actually the same, but that could be done during the transaction or by checking the publication hashes afterwards.

Now rollup A transactions can have access to Rollup_B_state_at_publication_time values. Since it's the same proposer, he can inject the known state (as it will be at publication time) into either rollup.

For the rollup A nodes and provers, they can check that all of the injected values match the published rollup B state. Importantly, this is not necessarily the same as the actual rollup B state. It is possible that the rollup B publication is invalid.

Nevertheless, there is no ambiguity about it. The rollup A nodes and provers are executing a deterministic process that is not dependent on anything happening on rollup B. The rollup A chain will not stall if the rollup B state is never proven. The rollup A transactions are merely conditional on a particular claimed (but not proven) rollup B state, and there is a strong economic argument to suggest that it's probably the correct one (otherwise the whole rollup B publication is invalid and the proposer will be slashed). That's probably good enough for many use cases, and whether it is good enough is decided by the users.

[nikeshnazareth]

Oh, something I forgot to mention. Another thing that makes this imperfect is that the conditional transactions are still all included, whether or not the condition succeeds. For instance, in the previous example, the L2 proposer could skip Diane's transaction. Then Alice and Bob's sign transactions still go through (they weren't dependent on anything), Charlie's transaction reverts (he doesn't have 50 DAI and the L2 proposer can still include his transaction and use the state where his DAI balance is zero) and the execute call reverts.

The ideal UX is that the transactions are not even valid (so the L2 proposer cannot include them).

[nikeshnazareth]

It occurs to me that "the state at publication time" is just one example of "the state at a time the L2 proposer can predict". So we can use any state before the publication time if we want. Of course, to use the cross-rollup mechanism the other rollup's state root has to be available on L1 (which probably means "state at publication time" is necessary)

[nikeshnazareth]

To minimise changes required to the VM (eg. to avoid introducing a new opcode), I think we can implement this using the (per-block) anchor transaction and a final end-of-publication transaction. So the prover will just need to show that:

• this last transaction was called, and
• its inputs are consistent with the publication's metadata

I also think the existing single-slot deposit and proposed real time data feed could be integrated in the same way.

I'll make a PR (probably on Tuesday) explaining what I mean.

[dantaik]

@nikeshnazareth Let me try to summarize my understanding of your idea.

Currently, L2 blocks are derived using the following inputs:

• The L2 block state corresponding to the parent block
• Publication metadata
• A list of signed transactions in DA (txList), whose hash is included in the metadata

In your proposal, the proposer first constructs the L2 block — since they are fully in control and know exactly what the txList will be — and then publishes the metadata on L1. However, in some cases, the metadata might depend on external contract calls (e.g., oracles), making the final metadata unpredictable and possibly out of the proposer’s control. This introduces uncertainty in block derivation.

To address this, the idea is to include an expectedBlockHash field in the metadata. If, using the standard derivation rules, the resulting block ($block^1$) has a hash that differs from expectedBlockHash, the protocol forces the node to re-derive an empty block ($block^2$) containing only the anchor transaction.

This might differ slightly from your original idea, but I think it introduces a form of atomicity to block derivation: valid transactions are either fully included or completely discarded.

However, I still have a hard time to understand how this can help with the "building blocks for two rollups" scenario.

[nikeshnazareth]

There is a more structured version of the idea described in this PR.

It should be noted that the preemptive assertions are made well before the final L2 state is known. They could be things like:

• from L1 block 1500 onwards, a call to someContract.aFunction() on L1 will return X.
• At L1 block 1500 specifically, this particular L1 storage value was X.
• At future L2 block 1600, this particular L2 storage value will be X. Note that I'm assuming there are multiple L2 blocks within a single publication that are being preconfirmed in realtime. The relevant "future L2 block" still needs to be within the overall publication.
• At publication time (in the future - let's say L1 block 2000), the L2 storage value in another rollup will be X.

These assertions could be made several (L1 and L2) blocks before publication time and in the mean time the proposer is still accepting new L2 transactions and issuing preconfirmations. They won't know the final L2 state until much later, but the point is that L2 contracts can depend on the assertions as soon as they are made, and all of these assertions can be proven at publication time (or before).

As explained here to achieve the last assertion (about cross-rollup storage reads):

• I assume the proposer is currently sequencing both rollups (let's call them A and B), but I don't assume a generalised shared sequencer. The next rollup A proposer might only be sequencing rollup A, and cannot be assumed to know anything about what's happening on rollup B.
• Immediately before publication, the proposer computes the final L2 state for both rollups
• The proposer publishes those final states along with the publications. If the claimed L2 state for rollup A is incorrect, the whole publication for rollup A is invalid (and treated like a no-op). Same logic for rollup B.
• The cross-rollup assertion on rollup A is not strictly "the L2 storage value in rollup B will be X at publication time", but rather "the claimed L2 state for rollup B at publication time will imply this particular storage value in rollup B will be X, whether or not that claimed state root is eventually proven correct". Note that this assertion is completely verifiable by rollup A nodes using information available on L1.

Now back to your objection.

However, in some cases, the metadata might depend on external contract calls (e.g., oracles), making the final metadata unpredictable and possibly out of the proposer’s control. This introduces uncertainty in block derivation.

I'm not sure I'm tracking this. Which publication metadata is relevant to the L2 state computation? Do you mean the metadata fields that get injected into the anchor transaction (the anchor block number and hash)? Whatever it is, if we're in the based rollup case and we're talking about an L1 proposer who is about to propose L1 block 2000, aren't they able to retrieve whatever L1 data will be available at L1 block 1999, which should be sufficient to compute the L2 state? Note that they need to be able to publish the final L2 state but not necessarily the final L2 block hash (although that also seems like it should be possible). I'm also not saying that the claimed L2 state has to be part of the L2 block derivation, merely that it is published to L1 along with the publication (so it is directly accessible to anyone following the L1). Have I missed something?

Also, are you saying that instead of calling it a no-op if the claimed L2 block hash is incorrect, I should say it should be treated as a publication with a single L2 block with a single anchor transaction? Good point! I agree that's better than an actual no-op because it means the next set of L2 transaction can use the latest L1 anchor block.

Having said all that, as explained here, part of this idea includes a circular dependency, where the final claimed L2 state needs to be injected into the final L2 transaction in the publication. Because of the predictable structure of this last transaction, I think that still works, but even if not, we can just publish the "claimed L2 state before the last transaction in the publication" rather than the "claimed L2 state at the end of the publication".

Does that all make sense?