Strands, slots, and alignment with heights and rounds

[josef-widder]

After reviewing the blog entry and some discussions in the last weeks over figures like this, I use this place to collect some of my observation, so that we can start from them next year.

I will start with the figure. In the lucky path, the alignment between strands and blocks is quite nicely structured. However, in general, whenever a consensus round is not successful (e.g., if a proposer is down, or the proposer actually had not completed the proof in-time) the alignment becomes less structured. A proof for slot x>y can appear in the blockchain before the proof of slot y.

The intuition that I understood is that

• if a proposer has a proof for slot x and fails, the next proposer should be such that it has a proof for slot x+1.
• the proposer of height h round 0 should depend on the strand to which the proof in height h-1 belonged.

The way Starkware proposed to address is to have a static plan. A priori (that is offline) it is determined in which slot which proposer proposes a proof for which strand. This imposes a static scheduling on top of a rather dynamic system, namely,

• consensus is subjects to faults and asynchrony
• there might be issues with the prover (crash, being disconnected, etc.) so that the proof is not ready when needed

I think the same goals could be achieved by a different way of thinking about the problem.

Even with their static schedule, as we don't know in which round consensus decides (and whether the proof is actually ready when the proposers needs it), we can only have the following invariant:

• each block (after some initial blocks) contains a proof for some strand
  • that is, in theory, in height h you can have a proof for strand 1 and in height h+1 you could again have a proof for strand 1 (that is a corner case, of course) if a lot of rounds (the number of strands -1) are not successful

With the approach of using heights and rounds to figure out which strands we are in, we only introduce complexity in height h+1 if we haven't canonicalized height h yet. Therefore, I would like to think the following way:

• Let's assume the block contains a stand number and a proof of the previous block with this strand number (all within value, that is, we don't do the PBTS dataflow at all)
  • say, block[h].strandNr, and block[h].proof
• The sequence of proposers for the next height only depend on this. that is
  • the proposer for height h+1 round 0 should have the proof for strand block[h].strandNr + 1
  • the proposer for height h+1 round 1 should have the proof for strand block[h].strandNr + 2, etc.

In this way, we do not need to match global strand numbers, but only need to refer to the previous block. As far as I understand, we maintain the same schedule as the Starkware design, but in a different formulation (and without ambiguity around canonicalized commits).

The only difference we get in the following scenario:

• in round 0, the proposer P1 of round 1 locks on the value v proposed by the proposer P0 of round 0
• consensus goes into round 1 (with or without 2f+1 precommits for v are in-flight)

In this case:

• in the PBTS flow, the proof of P1 may make it into the block (but if there are sufficient precommits for round 0 around, in the next height also the proof of P0 could be canonicalized)
• in my approach, the proof of P0 will now be proposed by P1 (as far as I understand, P1 must have all the TXs and the proof locally, as it needed to validate the block anyway)

Interestingly, in my proposal

• P1 helps the proof of P0 to make it on-chain
• In the next block, P1 will be the proposer of round 0 (as this depends on which proof made it on the previous block)
• So in this scenario, instead of omitting the proof of P0, and postponing to a much later block, the proof stays in order with the proof of P1 (but this is just in this scenario, because if P1 did not set valid value in round 0, it will propose its proof)

[josef-widder]

It might also make sense to put some load balancing into proposer selection. Assume that for each strand we store what was the largest height of the block that contained a proof for strand i, say last(i).

So when starting a new consensus height, we order strands by increasing last(i), and then pick the proposers in this order.

pros

• in the lucky path, we fall back to the nice ordering that we find in the strand/slot figures
• if a consensus round fails because of some temporary network problem, the proof that belongs to that strand is not delayed (in the Starkware proposal it is delayed by "number of strands" block)

cons

• if the consensus round fails because there is a problem with the proof or the proposer, we will repeatedly miss round 0.

[josef-widder]

@ancazamfir proposed that if instead of putting the strand number (block[h].strandNr) into the block, we put a slot number into the block (block[h].slot) we would get closer to the way Starkware is thinking about the problem now.

This would mean that a block contains a slot number that corresponds to the height/round in which the value was proposed. This contrasts the PBTS flow, we the goal would be to put the slot number of the height/round of the decision (which leads to the one-off complication that the round is only fixed one block later)

[ancazamfir]

Hi, picking up on this, not sure my reasoning is good, please correct.
iiuc the current starkware proof proposal uses slots (and strands) for proof generation and verification. It seems to assume a fairly constant frequency, i.e. a slot (empty or full) "exists" every ~n seconds.

The intuition is that if the slots follow the consensus (decision) rounds this can be achieved in the following way:
The decision (quorum) round number is only known by the proposer at next height. So for this case we would need to have the proof (and slot) outside of value (ala PBTS version 1) with the complexity of the one-off.

Here is an example to illustrate further (not showing the strands), with p or q being full slot, - empty or non existent.

block     1               2   3
slot      1   2   3   4   5   6
round     0   0   1   2   3   0
polka     p   -   p   -   -   p
quorum    q   -   -   -   q   q   

Here we have blocks that occupy slots 1, 5, 6.
The problem of equal spacing of these slots in time still needs to be resolved.
Not sure if and how we can make guarantees. The timeout commit (to_commit) is the minimum time between heights decided in one round. Observing existing chains where most blocks decide in one round the block times are fairly constant.
The time between two empty slots could be anywhere in this interval:
(to_propose, to_propose + to_prevote + to_precommit + propagation_of_nil_votes)

In this discussion we explore making the proof and slot part of the value (PBTS version 2). The implication is that the slot numbers will not strictly follow the consensus decision round numbers but rather the proposal's polka round.
In the same example, now blocks occupy slots 1, 3, 4 while consensus took 6 rounds from start to block 3.

block     1               2   3
slot      1   2   3   -   -   4
round     0   0   1   2   3   0
polka     p   -   p   -   -   p
quorum    q   -   -   -   q   q   

The minimum time between two slots is min(to_commit, to_propose) in both cases, with to_commit dictating the spacing between blocks finalized in one round while to_propose between slots/ rounds within a height. With the proposal in this discussion (proof and slot part of value), the elapsed time between slots may be higher with multiple height rounds.

I think this should not be a problem, at most it gives future proposers more time to build a proof, as the slot where they need to include if may occur further in the future than approximated. In the example slot 4 occurs later in second proposal as compared with first. @josef-widder @cason
But should double check with starkware team.

[josef-widder]

I looked again at the blog, and post about the incentives and market for proofs (post IV) is one of the longest with many open questions. It would be great to sync with the Starkware team to discuss with them how they currently think about this complex. There are a couple of questions:

• How big are the proofs. Would it be feasibly to put 2 or more proofs into one block? (I guess that would be great to recover from missed slots, and don't delay all the proofs forever)
• If there is a business for computing proofs (similar to validation on a blockchain)? What is the connection between organizations who run provers and organizations who run validators? Is there a 1-to-1 mapping (as seems to be somehow implicated by the discussions we had about strands)? But then there seems no independent business for proving (as is indicated in the blog post)
• If validation and proving is done at different machines, there are the possibilities the the proposer is ready to provide a block, but
  • that the prover is disconnected
  • that the prover is slower than expected (e.g., it crashed and recovered, or due to misconfiguration, the prover program got less CPU time than expected, etc.
    I understand that empty slots are allowed but the more open the systems are (market) the more unreliable it may become.
• The provers may become faster. Wouldn't it make sense to adapt the schedule of writing proofs to the blockchain to increase of performance automatically, instead of having a fixed assignment of strands to slots that is based on worst case execution time of blocks?
• What is the relation of the proofs that are put onto the sequencer, and the proofs that are put onto L1?
  • How are the L1 proofs computed, that is, what information do they need on-chain to find L2 proofs
  • How often is this done (I guess there is also proving time involved)
  • Who is doing that? (is there again a market condition to consider)