Management of reverted transactions in StarkNet

[guthl]

As part of opening StarkNet Shamans for community discussions, we wanted to share our ongoing research on how StarkNet will handle reverted transactions, and prevent Sequencer DoS. This research has been going for the past 5 months, and we’ve come up with a few viable options. The goal of this post is to share those options in high-level, and to start an open conversation to help hear more inputs on those solutions.

This is an introductory post in which we present the problem. We intend to release two more posts that will describe in greater detail the two main approaches.

---

Problem Description

Let’s start with describing the problem - Cairo is not natively capable of proving reverted transactions. The reason is that for a transaction to fail, one needs to prove that the transaction resulted in an error.

Like in Bitcoin, on the current version of StarkNet Alpha, either a transaction is valid and can be included in a proof or it is unprovable and cannot be included.

The problem this triggers is that an unprovable transaction cannot pay fees and one can imagine sending expensive computation-wise transactions which consume sequencers’ resources without compensating for them. This allows DoS attacks on the sequencers.

Ethereum solves this problem by including reverted transactions and making users pay for the consumed resources. This is possible since Ethereum runs transactions in a virtual machine.

Approaches for a Solution

Few paths exist to solve this scenario attack vector.

Making All Transactions Provable

Making all transactions in StarkNet provable, will allow including them in a proof and taking their fees, similarly to Ethereum. This can be achieved by using a new programming language (whose syntax can be very similar to Cairo), in which the compiled contract will include the code to handle exceptions. We will publish a more detailed description of such a language in a separate post.

• Pros

  • It fully solves the DDoS vector
  • UX stays familiar
  • A first step towards enabling censorship-resistance via L1 forced transactions.

• Cons

  • User would pay for reverted transactions (like they do on Ethereum)
  • It would add an extra overhead in the proof
  • It requires significant engineering resources to implement this safe language

Economic Solution - “Red/Green”

We’ve been working on this approach with Prof. Tim Roughgarden for the past 3 months. StarkNet does not implement any restrictions on Cairo. In that case The main idea is that a sequencer can choose to include a transaction without executing it and receive a red fee, thus enabling it to ensure it receives a fee payment for their work. We can design the mechanism in such a way that a Sequencer will always be incentivized to execute a provable transaction and take the green fee instead of the red fee.

• Pros

  • StarkNet would only prove transactions that do something on the state
  • No extra engineering
  • No user cost on regular reversion (e.i: no more NFT minting where users pay for no reason)

• Cons

  • New approach means unknown attack vectors

Transaction level PoW

Users provide a PoW on top of their transactions based on the numbers of reverted txs. In such a way, a user would have to provide a small proof of work or none on the average case, but in the case too many reversions, the PoW will be much larger. A user would have their PoW requirement decay over time or could set it back to 0 by paying the sequencer.
This approach was less explored in work, but might still be a viable path.

---

We are opening the problem to the community to understand if we can explore the design space.

If the topic gathers enough interest, we will organize a research call around the topic to dive into the problem and the various existing approach. We would appreciate people to make comments and share their thoughts and questions

[xJonathanLEI]

I like the Green Fee / Red Fee model. But is it technically possible for the user in question to prove if the sequencer incorrectly asserted a provable transaction as un-provable? If yes then some form of slashing can be implemented to further deter not running transactions.

[liorgold]

But is it technically possible for the user in question to prove if the sequencer incorrectly asserted a provable transaction as un-provable?

No, it’s not possible to (easily) prove that the sequencer was malicious. The reason is that it requires knowing the exact state of the system at the time the sequencer tried to apply the transaction (an exception may be if we somehow move the red txs to the end of the block), but this requires the user to know all the transactions in the block which is not ideal.

The idea of this model is that the red fee (the fee that the sequencer is allowed to take, without proving anything, and without executing the transaction) will be much lower than the green fee, so a reasonable sequencer will prefer to include the transaction and take the green fee when possible.

The downside is that the sequencer may behave irrationally, in which case, it will lose money, but the user will get an annoying UX - their tx was revoked and they lost some money. Now they’ll have to resend it hoping the next sequencer will be nicer.

One optional addition is to allow the user to specify a list of sequencers that are not allowed to handle their tx. So if a user feels a specific sequencer is malicious, they can exclude it. We’re not sure how to maintain this list, and it seem to complicate the solution.

[toghrulmaharramov]

I think the Green/Red Fee model sounds interesting. From what I understand, it will not cost the user more in terms of calldata (since you are updating the same slots) and will cost slightly more in computation costs (since you are doing redundant computation by paying the fee twice). As @guthl confirmed to me on Twitter, the transaction is essentially split into two distinct parts: one paying the base fee and one invoking the arbitrary execution + paying the execution fee.

My only concern with this model is that account abstraction permits the user to define arbitrary spending conditions and therefore the sequencer can only find out whether the base fee payment is valid or not after it executes that part of the transaction, which still opens up a DDoS vector on the sequencers (though with a smaller computation cost than in a scenario where the entire transaction is executed).

[xJonathanLEI]

@liorgold

an exception may be if we somehow move the red txs to the end of the block

Sounds like a solution

The sequencer will have to run the transaction twice though, because a transaction failing in the middle of the block might succeed when placed at the end. And if any such transaction is found, it needs to be moved back to the list of “normal txs” and all re-run failed transactions before it need to be re-run again.

There’s still one minor issue though. The end-of-block state that users compute from L1 data isn’t exactly the same as the context in which those failed transactions are evaluated: the sequencer’s balance is different due to fee collection. If any of the failing transaction depends on sequencer balance, there can be false positive/negative unless L1 also contains data required to derive the end-of-block state before adding in the fees.

IMO some kind of slashing is needed, otherwise the UX problem can be quite annoying (i.e. txs failing for no reason).

[neozaru]

About the solution 1, what % of proof overhead are we talking about for non-reverted tx proofs ? (order of magnitude)

For the User would pay for reverted transactions (like they do on Ethereum) I would argue that this can be solved by an extra layer ontop of StarkNet, which I imagine most non-technical users will probably end up interacting with anyway when mass adoption. As a “power-user” I am already sufficiently educated about transaction revert risks.
I believe Flashbot Protect RPC is another example of solution that works with Ethereum - but I admit that I don’t know the technicals of StarkNet so maybe a similar system cannot be implemented there.

About the solution 2:
Green/Red option: I’ll quote <boog @boogooboog>'s Tweet as he haven’t forwarded it here:
"Is it just me or does the green/red fee proposal incentivize reordering transactions to increase reverts when the block is full?"

Also could the base fee be made proportional to the computation costs ? (otherwise it might be low enough to not discourage DDoSers, who could send code that runs in a loop before failing for example)
PoW option: I am unsure about what defines an “user” there. Can’t a computer emulate 10M users with a fresh history ? Or would every new users start with an high PoW requirement from the start ?

With my non-knowledge I think I’d feel more comfortable with (1) if the overhead was of a few percent for successful txs, and if it is correct that the issue of paying for reverting txs could be tackled on an extra layer.

@xJonathanLEI

the sequencer’s balance is different due to fee collection

Is it set in stone that this balance is activated / part of the state at the moment of tx inclusion ? Couldn’t sequencer’s balances be credited at the end of the block ?

[xJonathanLEI]

@neozaru

Or would every new users start with an high PoW requirement from the start ?

I believe that’d indeed the case in the transaction-level PoW solution.

@neozaru

Couldn’t sequencer’s balances be credited at the end of the block ?

I believe end-of-block credit will be the case. That’s also what I had in mind when I wrote that reply. But it’s still an issue because at the time these reverted transactions are evaluated on the sequencer’s side, the fees haven’t been credited yet, meaning the context of evaluation is different from the state which can be computed from L1 data.

Even if the system instead credits the sequencer for successful txs first before evaluating failed txs, there will still be issues:

(1) a tx might fail before fee credit but succeed after credit, making it impossible to be included in either segments of a block, despite being a perfectly legit tx otherwise;
(2) the evaluation context is still different from state derived from L1 data since the sequencer still needs to be credited the fees from failed txs.

A possible mitigation for (2) would be to credit both successful and failed tx fees before evaluating failed txs. However, issue (1) still remains.

[lior-stark]

@toghrulmaharramov

My only concern with this model is that account abstraction permits the user to define arbitrary spending conditions and therefore the sequencer can only find out whether the base fee payment is valid or not after it executes that part of the transaction, which still opens up a DDoS vector on the sequencers

Wouldn’t this be mitigated if the validation part of the transaction (by an account contract) be limited in what they can do?
So this part of the transaction (validating the payment), is fairly small, and therefore the chance DoS decreases significantly (or should I say the cost of DoS increases significantly).

[satoshi]

@guthl

Transaction level PoW

Is this sybil resistant? If this is indeed a DDoS attack, then the attacker could just create thousands of wallets with invalid transactions, and the PoW isn’t a big obstacle, since it is only one transaction per wallet.

[RoboTeddy]

It’s interesting to consider how these solutions might affect censorship resistance long term.

Making all transactions provable could eventually lend more censorship resistance:

StarkNet could later add a special way to include any transactions that are suffering from censorship by sequencers. StarkNet could have an L1 inbox contract that allows users to submit L2 transactions directly to L1 (as calldata). The main StarkNet contract could then require that tx in the L1 inbox are included in the next L2 batch, i.e., the STARK proof would show that each L2 tx listed in the L1 inbox was either executed or reverted. This would make StarkNet inherit Ethereum’s level of censorship resistance.

This censorship “escape hatch” may prove important in a world where it’s relatively easy to be censored because there aren’t many sequencers due to the large requirements for running one (massive parallel computation, etc)

By comparison, the economic solution (red/green) means that a sequencer could censor a tx and lose only the difference in price between the green and red fees. Sequencers that are maximizing MEV might e.g. forgo green - red in order to drop a tx from their batch.

---

More broadly: making all transactions provable feels like the pure/correct solution, but I imagine there might be a large amount of work involved. Perhaps the roadmap could involve using the Red/Green solution for the time-being, and then eventually migrating to the proof-based reverts?

[xJonathanLEI]

@RoboTeddy

making all transactions provable feels like the pure/correct solution

Agreed. IMO one of the major downside of the red/green model is that a malicious sequencer would be able to “punish” users by censoring their transactions (making them pay the red fee). Compare that to the worst case scenario in alternative solutions, where the censored (ignored) transaction would simply be included by the next honest sequencer instead.

[bbrandtom]

This is a very good point - provable transactions can allow general L1 forced transactions (as opposed to applicative L1 forced transactions, which is also possible today). I think it is worth adding it to the pros of this approach.

Note though that this feature requires an extra requirement - the compiler needs to be part of the OS. I think it will be easier to explain once we expand on that approach, but in high-level, the OS need to ensure all contracts that were deployed on the state are indeed fully provable. Otherwise, malicious sequencer can deploy an unprovable contract and freeze the system by sending a forced L1 transaction to it.

[guthl]

making all transactions provable feels like the pure/correct solution

I’m not sure I agree here. There is a small nuanced difference between failed txs on Ethereum and on StarkNet. On Ethereum, when a transaction fails, the sequencer already did all the computational work. On StarkNet, the sequencer knows a tx failed (at the end of the trace execution) long before engaging most of the computation works (proving the trace).

While it might not matter, it seems like a waste of resources to spend such a computation power on useless computation, especially after knowing they will fail.

What I like about the PoW/VDF approach (although incomplete in its definition) is that it basically says:
The sequencer will accept the sunk cost of execution but if a user abuses it, they will have to pay retroactively for the effort (either through PoW or through a difficulty reset).

[RoboTeddy]

While it might not matter, it seems like a waste of resources to spend such a computation power on useless computation, especially after knowing they will fail.

This is a good point. I wonder what fraction of tx on Ethereum were reverted; this could give us an estimate of the overhead.

What I like about the PoW/VDF approach

A question about this approach:

but in the case too many reversions, the PoW will be much larger

How will it be determined whether there was a reversion, if reversions can’t be proven?

---

I should note that overall I don’t have a view of which solution is best, I’m just helping discuss the pros/cons of the various approaches.

[xJonathanLEI]

@guthl

the sequencer knows a tx failed (at the end of the trace execution) long before engaging most of the computation works (proving the trace)

Thanks for the input. I didn’t realize this is the case.

@guthl

it seems like a waste of resources to spend such a computation power on useless computation

However, IMO those computation power isn’t wasted if the big picture is to be taken into account, as that would be part of the cost of:

• maintaining a good UX: no tx failing for no reasons (red/green), nor unnecessary delays (tx PoW)
• eliminating DDoS vector for good

Of course, given the additional development effort required, red/green with slashing (which requires proving incorrectly-failed txs to L1) seems to be the best solution for now.

[maciejka]

I totally second adding censorship resistance to the pros list of solution 1.

Currently there is no good solution to this very problem. Applicative escape hatch is problematic as it gives extra power of being able to selectively stop applications to the sequencer.
Decentralization should help, but it is not clear what resources will be necessary to run the sequncer and how decentralized it will eventually be.

Another pro of solution 1 is that contract call semantics with reverts will be equivalent to EVM which will make efforts like Warp simpler.

[guthl]

I just want to point out that I found a critical problem in the PoW approach, which should be discarded as a result.

A rejected tx due to reversion could return to be valid in the future, resulting in undefined behavior after the operator announced the reversion. This problem emerges due to the Account model that StarkNet is using.
In any case, once rejected, a tx should be unreusable and a potential fix would probably look like the Red/Green approach.

Under this new realization, I’m leaning in favor of Sierra, as most people seem to agree that it is a pure approach.

[bbrandtom]

Good point, added it to the the pros of the Sierra approach.

[dericecourcy]

@guthl @bbrandtom What is the “Sierra” approach? Any resources where i can read about it?

[NIC619]

Is there an update on this? I assume the upcoming fee mechanism would not include any of the approaches mentioned here so the sequencer might still be open to DoS attack?