Validator Sets and Censorship Resistance

[cason]

Validator Sets Basic Claims, from Matan on Slack and Google Doc, to start this discussion:

1. STRK will be the token used for staking.
   a. Assumes users in Ethereum can get access to STRK.
2. All staked STRK is stored in L1.
   a. Assumes L1 is more secure than L2.
3. L1 has control over Starknet’s validator set.
   a. Assumes L1 is more secure than L2.
   • "we don’t want to blindly trust L2 consensus, and we will utilize L1 to enforce security guarantees".
   • "The L1 contract will then enforce that these updates are reflected in Starknet."
4. All registrations for Starknet validator sets are via the L1 contract.
   a. This is for simplicity since (3) indicates we must have L1 registration and we find little value in adding a Starknet only flow.
   b. Why not have a Starknet only path? For simplicity.
   • We assume there is a high cost to be a Starknet Sequencer and so the cost of an L1 transaction to register is relatively low.
   • We assume the validator epochs will be long, so low latency to validator registrations is unimportant.
   • We assume there will be few validators, so high throughput is unimportant.
5. A validator should only be punished if it can be shown to act maliciously.
   a. Therefore if the validator set as a whole is faulty, we will aim to dilute its relative power without slashing.
   b. Therefore a bad validator set is handled by adding new validators.
6. Tendermint is not strictly time based and so validator resets do not require strict coordinations.

Non-goals:

1. Low latency responsiveness to validator updates.
   a. Validators are expected to be long lived and so the latency of sending the registration on L1, reflecting it into L2, and getting this approved in L1 is acceptable.
2. Cheap validator updates.
   a. The fee for sending the registration on L1 is considered minimal in reference to the bar for being a Starknet sequencer.

[cason]

My general assumptions for the good scenario, they call it "Sunny Day".

The Starkware blockchain includes a command/operation/special transaction for updating the validator set:

1. This command is included in the block by the block proposer
   • In contrast to Comet, where there is an implicit agreement on valset updates. Namely, the proposer includes in a block the (hash of the) next validator set. A validator accepts a block if the locally computed next validator set matches the block's next validator set.
   • Not sure how the validation of this command occurs at other nodes (i.e., can they reject a block for including an invalid or non interesting valset update command?)
2. The command specifies the next validator set and the height at which it will take effect
   • In Comet, the next validator set is the validator set to be adopted from the next block
   • Maybe the effectiveness of a change is given by H + X, where H is the block including the command and X is a constant.
3. The block at which the command was included must be proven, and the proof is sent to L1
   • From what I understood, the proof is produced by the same validator set that has committed this block
   • The reception of this proof works like an acknowledgment to L1. Once it is received, L1 will consider that L2 has behaved well and accepted the (imposed) validator update. The current validator set, in this case, should not be "punished" by L1.
4. The new validator set is installed at the configured height, starting a new epoch in L2. Proofs for blocks in this new epoch must be produced by the new validator set, otherwise they will be rejected by L1.
   • Not clear to me how, once a new epoch is started, proofs for blocks from the previous epoch are handled. Those blocks were produced in the previous epoch, with the previous validator set. Could them be proved by the new validator set?
   • This becomes even more complex if when we consider the possibility of rollbacks and forks (not in a sunny day).
5. L1 should only be sure that the new validator set was indeed installed upon receiving a proof a block produced in the new epoch.
   • In the same lines as in point 5., L1 can only be sure that the reconfiguration went well when the validator set of the new epoch produces a block (e.g., the block starting the new epoch) and eventually produces, within the same epoch (i.e., with the same validator set), a proof of the execution of this block, which is accepted/confirmed by L1.
   • If a new epoch, potentially with a new validator set, is started before a proof of a block produced in the current epoch is produced and accepted by L1, we are potentially in trouble.

Regarding the concept of epoch, what I understand by now:

• The validator set does not change within an epoch. This does not mean that a new epoch necessarily implies a new validator set.
• It seems from their description that there is more than one epoch between including a reconfiguration (validator set update) command in a block and the installation of the new validator set.
• The last point becomes tricky when we consider that multiple reconfiguration commands could be proposed/scheduled at the same time. It is possible that a reconfiguration R1: S -> S' is scheduled, and we have another reconfiguration R2: S' -> S'' proposed. R1 would be applied while R2 is already scheduled, and we have three validator sets to consider.

[cason]

Not clear to me how, once a new epoch is started, proofs for blocks from the previous epoch are handled. Those blocks were produced in the previous epoch, with the previous validator set. Could them be proved by the new validator set?

This should not be a problem, according to them in the Feb 22th meeting. We should just assume that "anyone" can produce a proof and there is data availability guarantees to ensure that new validators have access to the data they need to produce proofs.

[cason]

5. L1 should only be sure that the new validator set was indeed installed upon receiving a proof a block produced in the new epoch.

This probably has to be rephrased. Once accepting the proof produced in item 3., for the block where the reconfiguration was scheduled, L1 will not accept proofs produced from the block where the reconfiguration should take place if the proofs are not produced by new, reconfigured validator set. Also the proof for blocks produced after this reconfiguration height are only accepted if the blocks were produced by the new validator set.

I am not 100% sure if we understand well the corner cases here, this is by now a general explanation.