Motivation
The primary motivation of this suggestion is to establish a lightweight sequencing protocol on L2 which:
- Can support a relatively large number of sequencers without burdening the network
- Will guarantee that StarkNet is alive as long as Ethereum is
On the downside - this suggestion doesn’t emphasize the importance of extremely fast/strong finality.
Stake management
In this suggestion, L1 manages the stake of the sequencers. L1 is the only place where slashing can happen.
Sequencing Order
Sequencers are chosen according to their stake. The randomness source and algorithm for selecting the specific sequencer for each slot are out of scope.
Each proposer will be chosen for a short period (around 10-60 seconds). L1 is aware of the sequencing order (including the time slot each sequencer is responsible for). To accomplish that, we can either save explicitly on L1 the sequencer at each slot or store a “seed” and repeat the computation when needed.
How does sequencing work? The earliest-longest-chain protocol
The sequencer creates a block (as with Ethereum, the mere creation of a block does not guarantee that the consensus will eventually include it in the chain). A block is based on a previous block and adds a certain number of transactions on top of it. The sequencer will send the information of the new (suggested) block off-chain to the other sequencers.
The protocol rewards sequencers only when their block becomes fully final - when L1 accepts a proof to the chain that contains the block they proposed.
An honest sequencer will choose the chain with the largest number of (all valid. What exactly “valid” means is to be defined shortly) blocks, and if a few sequencers suggested chains of the same length, it would choose the earliest one. We call this behaviouis the earliest-longest-chain.
Therefore, we expect that usually, each sequencer will build its block on top of the block proposed by the previous sequencer. However, there are a few cases this won’t be the case:
- The sequencer is malicious. It may try to reorder the transactions.
- The sequencer thinks that the block proposed by the previous sequencer is invalid. A block can be invalid due to the following reasons:
- It was not built over the earliest-longest chain
- The block can be proved, or rely on an earlier block that this sequencer can’t prove. (Either because it contains invalid transaction, or because the sequencer doesn’t have the data needed for proving what happened in the block).
- It contains a transaction that the sequencer can prove yet is classified as “bad.” An example of such a transaction is a transaction that takes the maximal fee from a user without considering factors that might give the user a refund.
- The sequencer didn’t get the previous block due to a network failure
This mechanism incentivizes the sequencers to share their block data with the next sequencers (they want the accepted chain to include their block). Knowing that many of the other sequencers follow the earliest-longest-chain protocol incentivizes a single sequencer to follow this protocol - If they continue a chain that is not the longest, the next sequencers are unlikely to continue their block, and the accepted chain won’t include their block.
Generating proofs of validity and publishing them on L1
Life Cycle of a Sequencer
Blocks are accumulating on StarkNet according to the scheme described above.
The current sequencer, in each slot, is allowed (according to conditions described below) to initiate a proof. The sequencer would choose the exact block to prove according to the scheme described below.
Prove the blocks to L1 - the template
We will now detail the proving algorithm while treating to the questions of:
- When can a sequencer initiate a proof?
- What block is the sequencer choosing for this process?
as a black box. We will get to how to answer these questions in the subsequent sections.
The sequencer commits the expected state diff to L1 by sending the expected block’s hash to initiate a proof.
After which, they must submit proof to L1 attesting to the validity of this block hash within a certain period.
L1 checks that the transaction submitter is the expected sequencer for that time slot.
After the commitment submission, honest sequencers should check if they have the information required to prove the commitment. If so, they will base their new block only on chains that contain it (even if they would otherwise choose not to do so due to the reasons explained above). This behavior creates a scenario where sequencers are “racing” for the next block that L2 can commit, and then the “race” resets
:
A future commitment that relies on the current commitment may be submitted before the first commitment is proven, allowing for parallel proving of different chain segments. However, commitments that contradict the current commitment cannot be submitted.
When the sequencer publishes the proof for its commitment, it is rewarded for being the prover.
If the sequencer doesn’t publish this proof within time T , there is a second-time window T in which anyone can prove this commitment. If someone proves the commitment in the second time window, the protocol rewards him for being the prover and on top of that he receives a stake from the originally declared prover, which is slashed by the L1 contract.
Suppose the second time window is over without any proof submission. In that case, L1 will slash all the sequencers that submitted any commitment on top of the unproven commitment and be open to getting another (potentially conflicting) commitment on top of the last proven state, rebooting the process.
The following diagram is an example of the L1 contract state machine:
To complete the picture, we need to instantiate the two details we left out:
- On what conditions can a sequencer commit to a block to be proven?
- What are the blocks that the sequencer will prove in such a case?
Attempt No. 0
Let’s start with the simplest instantiation possible:
- Any sequencer, in its turn, can publish a commitment
- The commitment includes the blocks accumulated on StarkNet, starting the previous commitment until (and including) the block just added by the sequencer.
The issue with Attempt No. 0
This protocol allows committing on each block. In particular - this nullifies the earliest-longest chain protocol. Consider, for example, a case where 10% of the stake is malicious. We would expect that StarkNet would work well in such a scenario. However, if the malicious sequencers can commit on chains with length one, 10% of the time.
Such power can delay the network by a noticeable amount - since other sequencers may not have the data needed to build upon the committed block before a proof to this block ( with a state diff, though on-chain data availability) is sent to L1 (which would take time T).
Attempt No. 0 fix - Attempt No. I
We want to ensure that the committed block has some kind of consensus on L2. Therefore, we wouldn’t want to commit to the last block accumulated on L2, which might result from a single sequencer whim.
To achieve this, we define the unproven buffer. You can think of the unproven buffer as ~30 blocks.
The unproven buffer includes blocks that are not proven or committed to L1 - yet it provides an agreed continuation to the chain to be committed. As part of a commitment, the commitment-generator would attest that enough sequencers signed on a continuation for the committed block. L1 can easily check this attestation by verifying that the signing identities match the block proposers at the relevant block numbers.
Now, a commitment on an invalid or bad block can happen only if the malicious party were the first to reach a chain with a length of 30 after the previous commitment without support from the honest/rational sequencers.
Therefore, now the instantiation is:
- Any sequencer, in its turn, can publish a commitment if at least “ unproven buffer +1” new blocks have been accumulated on L2 since the last commit.
- The commitment includes the blocks accumulated on StarkNet, starting the previous commitment until (and including) the block just added by the sequencer minus unproven buffer blocks.
The Issue With Attempt No. I
While it’s true that now whatever is committed to L1 has a significant continuation, we still can’t be sure that the honest stake participated.
Imagine, for example, that (still) 10% of the stake is malicious, the unproven buffer has a size of 30, but proof submission becomes profitable only if it attests at least 500 blocks.
In such a case, there is a high probability that the malicious 10% will reach a chain with unproven buffer +1 blocks before any rational sequencers commit to L1 the (much longer, yet still non-profitable) chain the rational sequencers agreed on.
This scenario throws us back to the original problem!
Attempt No. I fix - Attempt No. II
We want to ensure that too-short chains are not submitted to L1, when “too-short” is correlated with the profitability threshold of the proving mechanism.
Notice that setting the unproven buffer size to 500 does not make sense since we perform on L1 checks linearly with the unproven buffer size.
Therefore we will define a “proving threshold” as the minimal number of new blocks present in a new commitment. While the proving threshold is determined statically by the protocol, its value should be configurable to roughly reflect the area in which positing blocks become profitable.
Therefore, now the instantiation is:
- Any sequencer, in its turn, can publish a commitment if at least “proving threshold + unproven buffer ” new blocks have been accumulated on L2 since the last commit.
- The commitment includes the blocks accumulated on StarkNet, starting the previous commitment until (and including) the block just added by the sequencer minus unproven buffer blocks.
The Issue With Attempt No. II
While the unproven buffer solves a problem, it also introduces a new one - the “race” doesn’t “resets” anymore. This problem will materialize when a party has a large stake for a brief period.
For example, say that a malicious sequencer controls half of the unproven buffer and does not share the data with the rest of the sequencers. It is now having an advantageous position for “winning the next race” - since it needs to add “proving threshold” to the chain tip, while the rest of the state needs to add “unproven buffer/2 + proving threshold.”
Attempt No. II fix - Attempt No. III
The L1 contract will save the time of the last block found in the unproven buffer. We change the instantiation to:
- Any sequencer, in its turn, can publish a commitment if at least “proving threshold + unproven buffer ” new blocks have been accumulated on L2 since the last block in the previous unproven buffer.
- The commitment commits to all the blocks on StarkNet so far, from the previous commitment until the block just added by the sequencer minus unproven buffer blocks.