Discover more from Cryptocurrency and Friends
Where Is the One Honest Party for a Rollup?
Is it a Sequencer? An executor? What problems arise?
As discussed in a previous post, the goal of decentralization in the context of rollups is to enable a single honest party to step up, assist the bridge smart contract, and ultimately protect the rollup against an all-powerful adversary.
In this article, our task is to find who can be the honest party and how they can participate in the rollup protocol.
Thanks for reading Cryptocurrency and Friends! Subscribe for free to receive new posts and support my work.
It all begins with the protocol agents:
Sequencer → Responsible for taking user-generated transactions, deciding the final order of execution, and passing it on.
Executor → Takes an ordered list of transactions, executes them against the database, and proposes the database update to the bridge smart contract.
As explained in a previous post, a good mental model for the agents is to consider the Sequencer as offering the user facing frontend of the service for collecting transactions. It is up to the executors, the backend of the service, to process and protect all transactions.
Sequencers are Optional
The Sequencer offers the fast path for transaction inclusion and it can be argued that the role is optional.
All rollups must have a slow path available that allows the user to bypass all sequencers and send their transaction directly to the bridge smart contract for ordering. This is called the forced inclusion safeguard and a rollup is only considered secure if it actually implements it.
Rollups vs sidechains — The core difference between a rollup and a sidechain is whether a user can forcefully order a transaction for execution.
The forced inclusion safeguard is designed to handle the worst-case scenario of an adversary trying to censor a user’s transaction. If we only consider this absolute worst-case, then there is no need for an honest party to participate as a Sequencer. Thus, in the strictest sense, the Sequencer role is optional.
On the other hand, if we consider the average-case, then it can be very desirable for an honest party to participate as the Sequencer(s):
Prevent or fairly extract MEV,
Guaranteed inclusion of time sensitive transactions (liquidations),
Reliable user experience (no dropped transactions, up to date info, etc)
Interestingly — the pursuit of decentralising Sequencers — may have a significant impact on the long-term architecture and roadmap of a rollup based on user experience needs — a topic for a future article.
But, as discussed here, it is strictly not necessary as users can bypass all Sequencers and single-handedly order their transaction for execution.
An Honest Executor
Executors form the backend of a rollup and they are tasked with updating the off-chain database.
Their tasks include:
Take an ordered list of user-generated transactions,
Execute them against the database,
Propose a new database update to the bridge smart contract.
With this in mind, it is the executor who sits in-between the bridge smart contract and the off-chain database, responsible for sending messages about the off-chain world to the bridge smart contract.
This brings us to the need for one honest executor who can enforce the following properties:
Liveness → Ordered and pending transactions will eventually be executed by the executors.
Safety → There is convincing evidence that every proposed update to the database is valid.
Interestingly, depending on whether the rollup involves fraud proofs or validity proofs, it impacts the rules enforced by the honest executor:
Optimistic Rollup → An honest executor protects safety and liveness.
Validity Rollup → An honest executor only protect liveness.
Let’s take this opportunity to dive further into the topics of liveness and safety from the perspective of one honest executor.
Honest Executor for Safety
We need to define what it means for an adversary to attack the safety of a system and what an honest party is trying to fend against:
Adversary’s goal: Convincing the bridge smart contract of a database update that has a single invalid state transition (i.e., steals all funds).
Let’s consider the type of proofs in turn:
Validity proof → cryptography. A cryptographic proof replaces the need for an honest party to protect the database update’s integrity. An adversary needs to break the underlying cryptography before they can produce a fake proof — which is no small feat.
Fraud proof → honest executor. When an executor attests to a database update via the bridge, all other executors have an opportunity to review the attestation and potentially issue a challenge for it.
As a result — we are only concerned with the fraud proof approach when evaluating how an honest executor can protect safety.
There are two style of attacks an adversary can deploy against a fraud proof:
Break safety. Honest executor is not available and the bridge is convinced of an invalid update.
Delay attacks. Purposely forfeit staked funds with the goal of delaying the finality of executed transactions.
The fraud proof mechanism is only designed to protect safety as an honest executor can issue a challenge against all adversarial executors who have voted in favour of it. As long as the executor is honest, they are guaranteed to win every challenge against the adversary.
Delay attacks are an unfortunate side-effect for state-of-the-art challenge game designs. The fundamental issue is that a challenge game does not prove that an attestation is invalid, but that one player lost the game. An adversary can take advantage of this limitation by stretching out the challenge game for the full allocated time (~1 week or so) and publishing a new invalid attestation before the previous challenge game finishes. By repeating the two steps, it can prevent the finalisation of an honest attestation.
Of course, every challenge game will require the adversary to forfeit staked assets, so it is an expensive attack. There is a trade-off on the financial cost to perform a delay attack and the benefits of doing so. There are some hints that Arbitrum V3 will alleviate delay attacks, but there is no publicly known design for doing so.
Regardless, delay attacks represent an attack on liveness and not safety which brings us to the next topic!
Honest Executor for Liveness
It is up to one honest executor to “pick up the slack” and force the execution of all ordered transactions. To this end, success depends on the their ability to step in at the right time and how the adversary may stop them.
Again, we should define what it means for an adversary to attack the liveness of a rollup:
Adversary’s goal: Halt the execution of user generated transactions
In nearly all rollup designs, the current appointment protocol for picking an honest executor relies on a first-come-first serve basis which essentially relies on whoever can post the attestation first.
There are subtle race condition issues with the first-come-first-serve approach that can be leveraged by an adversary to stop the honest party’s participation indefinitely. For example, if two or more executors submit a proposed database update at the same time, then the adversary can simply front-run the honest party with a minimal database update.
At first-sight, the obvious solution is to offer an honest party, and all parties, a dedicated time slot for proposing a database update and remove the potential for race conditions altogether. The effectiveness of a dedicated time slot depends on how long it takes for an honest party to obtain it. The most significant threat to fend against is an adversary filling up all the slots and again delaying the honest executor’s opportunity to participate.
Another aspect to consider is the database update content. We can imagine an appointment protocol that slashes and ejects an executor that fails to propose a database update on time. In this case, we may want to prevent the adversary from posting empty database updates and effectively halting transaction execution by refusing to execute them.
Some projects like Arbitrum have implemented:
Forced a minimum quantity of computation per database update,
A deterministic transaction fee that cannot be tampered with by the system operators.
The combination forces a minimum execution progress as the executor must propose a meaningful database update. Additionally, it makes it expensive for an adversary to fill the ordered transaction queue with “junk”.
To summarise, we must ensure:
An honest party has a guaranteed slot to propose a database slot,
An honest party will obtain a slot in a timely manner,
It is financially expensive for an adversary to fill the rollup with junk execution.
The above goals provide some rules of thumbs to help design new appointment protocols for onboarding executors and ensuring that one honest executor can step up at the right time. However, while rules of thumbs are great, there is still a lack of defined appointment protocols that rollup projects can adopt today.
On top of this, the entire discussion assumes that a single executor will perform all the work to produce a single database update and the entire set of executors are not cooperating with each other. This may very well be the case for Optimistic Rollups, but not for ZK Rollups.
Additional task: In a ZK Rollup, the executors need to replay all transactions and produce a validity proof that the execution of transactions is correct, an additional task than executors in an Optimistic Rollup.
It is already known that proof generation can be outsourced and parallelised amongst multiple provers, but there is still a lack of appointment protocols that can fairly segment transaction load, enable an open-membership group of provers to work together and ultimately aggregate all the independent proofs into a single proof that is published on-chain.
For example, one executor will prove transactions 1 to 1000 and the next executor will prove transactions 1001 to 2000. In the end, all sub-task proofs can be aggregated / recursively combined into a single proof.
We already have a trusted third party — the bridge smart contract — that can be leveraged to allocate transaction segments to specific executors and hold them accountable (slashing / ejection) if they fail to perform their task on time. So we have all the ingredients at our disposal, but it still remains a mostly unexplored research and design space to leverage this additional power of the bridge.
Hopefully, someone will propose an appointment protocol that 99.9% of the time enables an open-membership set of provers to collaboratively work together, but in the worst-case empowers one honest executor to forcefully make progress for all participants. :)
Thanks for reading Cryptocurrency and Friends! Subscribe for free to receive new posts and support my work.