Decentralized Consensus Potential Candidate (Longest Chain)

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:

  1. The sequencer is malicious. It may try to reorder the transactions.
  2. 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.
22 Likes

Please, feel very free to offer variants, analyze potential attacks, or otherwise give feedback! Building StarkNet’s algorithms with you and for you is very important for us!

4 Likes

The mev does not seem to be identified in a timeslot in any of the sequencer ?

2 Likes

Great suggestion! A few questions, to see I understood correctly:

  • "will be chosen for a short period " will you use L1 blocks as unit of time, or some time oracle?
  • “would choose the earliest one” how is early defined here? Based on time? Also, it’s a chain, so each block may have a different time stamp.
  • “It was not built over the earliest-longest chain” I now realize the definition of earliest-longest is something defined recursively? I.e. to settle it (or validity) i need to recursively look backwards into the chain? A proper and formal definition of “valid” and the earliest-longest would be helpful here.
  • “When the sequencer publishes the proof for its commitment, it is rewarded for being the prover.” What rewards do non-proving sequencers get? If they don’t get rewarded, why sequence without a proof?
  • diagram of L1 contract state: Sequencer X can grief, hence blackmail, Sequencer Y. This becomes worse if after Y you allow Z, etc. Perhaps slashing reduces with depth, so that if X doesn’t submit he’s slashed more than Y and Z?
  • attempts I, II, III - It’s too hard for me to follow the sequence of suggestions and fixes. Can you please state the final suggestion in one bulk explanation, i.e., what is the final protocol?
3 Likes

1 + 2 : I assume that L1 manage a mapping between L1 block numbers and who should be the sequencer in these block numbers. In particular, this means that the “short periods” are <1minute but >1 block time. So around 20-30 seconds. Also, blocks on L2 would have incremental slot numbers, where each slot number is associated with a sequencer, and earliest is defined as the earliest slot.

  1. Obviously transaction fees will be splited between what sequencers receive and that the prover would receive. The intention is that the prover will get the proof reward only after he provides a proof

  2. Sequencer Y shouldn’t commit on proving something that is based on sequencer X’s proof if he isn’t convinced he can replace X in proving the same claim, shall go down. Thus, there is no “griefing attack” possible here, not we should slash Y any less than X.

  3. For your convenience I copy-pasted the general rtemplate and put the sentences from Attempt III in the right place. I hope this would help to follow earlier attempts as well.

"Blocks are accumulating on StarkNet according to the scheme described above.

The current sequencer, in each slot, is allowed (if at least “proving threshold + unproven buffer ” new blocks have been accumulated on L2 since the last block in the previous unproven buffer.) to initiate a proof. The sequencer would choose the chain-segment to prove to be all the blocks on StarkNet so far, from the previous commitment until the block just added by the sequencer minus unproven buffer blocks.

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.

5 Likes

I think this topic deserves at least online presentation to make it easier to understand. How about including it in one of community calls? @henri.lieutaud

5 Likes

Agreed! Let’s plan it.

2 Likes

Yep yep yep! Let’s do this

Nice model @Ohad-StarkWare ! Some questions about it:

  1. How the proving threshold would be defined and who would do it on the model? Because even if not completely clear to me, it seems that if its update would follow the same L2 consensus mechanism, maybe there could be some attack vector. My line of thought is that this threshold could potentially be “subjective”, so not even easy to determine if the entity suggesting a change on it is acting honestly.
  2. On the proposed second-time window, when the chosen sequencer didn’t publish the proof, would the “racing” sequencers be rewarded even if in the end they are not the ones submitting the proof? Thinking about their profitability model, if it would to a model similar to PoW.
  3. As you mention on StarkNet decentralization : Kicking off the discussion, one of the challenges is The problem is that the rate at which transactions are collected is faster than proving those transactions. If I understand correctly this model, even if the time slots from sequencing until proof-submitted are short, both sequencing and proving need to be completed sequentially; so it is not that sequencers are ordering txs on one side, while provers are on another side. Does this have implications on the finality of the L2 txs? (which I think is quite important).
  4. How is managed election of the next sequencer on L1? As I assume this process would involve submitting a regular transaction to L1, so could it be a problem to have too short time and in cases of network congestion (L1) affecting the election dynamics? (and with them the whole consensus of L2).