epbs/DAS/FOCIL all-in-1 fork-choice

This is a proposal for structuring the fork choice in a manner that is compatible with the goals and constraints of epbs, FOCIL, and PeerDAS.

Overall, the slot still very much resembles the epbs slot from the PTC proposal, which has seen quite a bit of iteration since and has been the basis for EIP-7732. In particular, we still have the main phases of the epbs slot: beacon block proposal, attesting (so far just like in today's slot), payload release and finally a committee voting on the payload. This committee, formerly known as the payload timeliness committee (PTC), is renamed to availability committee (AC), because it now not only has the responsibility to vote both on payload timeliness (which itself could also be thought of as payload availability at the time of the vote), but also on the availability of the blob data associated to the payload (columns in PeerDAS).

In addition to these phases from the existing epbs proposals, we have a "freeze" deadline similar to that in in FOCIL (generally inspired by the view-merge concept), which is used both to ensure that the next proposer has enough time to satisfy all ILs that end up being enforced by attesters, and to ensure that its view of the AC's vote coincides with that of the attesters.. This is all to ensure that an honest proposer can be sure to do the right thing, i.e., extend the correct chain so that its proposal is attested to and becomes part of the canonical chain.

There are a few actors in the pipeline, so let's separately break down what each of them are doing and how their behaviors all fit together. We focus on a slot N, where a beacon block \(B\) is proposed, committing to a payload \(P\), and then look at the whole chain of actions that play a role in the outcome, including the proposal and attestations of slot \(N+1\). We assume that the chain is fully stable up until this point.

Builder

Payload construction

Firstly, a builder, including a local block builder, has to make a payload, with the added constraint of satisfying ILs. Compared to vanilla FOCIL, without epbs, IL enforcement is initially done by the AC members rather than by attesters. The reasoning for this is that the next proposer (slot N+1) needs to know whether the current payload "passed the IL check" (which is time dependent, so not objective), and thus whether it should extend it or not, before the next round of attestations even happens. As in FOCIL, validators will enforce the ILs that that they have seen by the freeze deadline (10s in the slot structure above, though could be earlier), and a builder can ensure that they satisfy all of them by taking into account all ILs they see until later in the slot, up until constructing the payload.

However, one of the goals of epbs is to not require the AC members to execute the payload before voting, so that we relax the timing constraints for payload execution. Without executing, the AC members cannot by themselves check whether the payload actually satisfies the ILs: a certain IL tx might not be contained, but only because it was invalidated during execution of the payload, which after EIP-7702 might even happen without a transaction from the same sender being in the block. In order to aid the AC member in their enforcement role, the payload contains a bitfield specifying from which of the IL proposers the builder has received an IL. We explain later how this is used in enforcement.

Payload exchange (epbs)

The default builder behavior is quite simple:

1. As soon as it sees \(B\), a beacon block committing to the payload \(P\) which the builder bid for, it propagates the blob data associated to its payload, in particular columns in PeerDAS. It can do so because it now has a signed header against which the columns can be verified. The builder at this point might have very little assurances about \(B\) becoming canonical, as it could be reorged if it doesn't get enough attestation weight, so it does not want to reveal the execution payload yet, but it should not have a problem releasing the columns regardless. This would normally give the columns nearly 7s to be propagated, and at least ~4s.
2. If the builder observes 40% (proposer boost) of attestations for \(B\), and it does not oberve an equivocation from the proposer (a conflicting block), it releases the payload. The exact timing for doing so is flexible, and depends on how quickly the builder can propagate the payload. In principle it can release it even quite close to 7s, the time at which the availability committee votes on it, but a more cautious builder might decide to only release it if it sees at least 40% of attestations before some earlier deadline. For example at 5s, giving it both 2s to observe attestations and 2s to propagate the payload.

Payment processing

Though it is not part of the builder's behavior, it is crucial to specify a payment processing rule. In the good case where \(P\) is released and becomes canonical the payment is immediately processed, and otherwise the payment is held up for some time to try to attribute whose fault it was that the exchange did not work out:

• Good case: payload is canonical. The payment is immediately processed as part of processing \(P\) (for example in the state transition of the first beacon block that extends "\(B\) with \(P\)"). The proposer clearly held up their end of the bargain, so payment can be immediately released. Note that this rule has nothing to do with whether or not \(P\) is at some point reorged, or generally how stable it is in the fork-choice. If you're on a branch where \(P\) is present, the payment is processed immediately. If you then switch to another branch where \(P\) is missing, you also switch to a beacon state where the payment may not have yet been processed.
• Bad case: payload is not canonical. If you're on a branch where \(P\) is missing, the payment from the builder to the proposer is only triggered if \(B\) receives at least 60% of attestations from its committee and if no proposer equivocations are detected by the end of the following epoch, i.e., in the transition from epoch E+1 to E+2, where E = epoch(slot(N)).

Properties for the builder

We are going to argue that, assuming sufficient network synchrony and connectedness of the builder, the protocol achieves the following properties:

1. Honest-builder payment safety: if an honest builder's payment is processed, their payload becomes canonical. This holds up to a 20% adversary.
2. Honest-builder payload safety: if an honest builder publishes a payload, it becomes a canonical. This just requires honest majority.

The rationale for the default release rule used by the builder is simple, and immediately gives us these properties:

• Timely, well-attested beacon block: if \(B\) gets at least 40% of attestations, it cannot be reorged by the next proposer, as 40% is exactly the proposer boost value. To be precise, this is unless there's a conflicting beacon block proposed in slot N, as this could also accrue some attestation weight of its own and be within 40% of \(B\), making a reorg through proposer boost possible. There are then two cases:
  • No equivocation detected: the builder releases, and \(B\) does indeed become canonical, because if there was an equivocation it would be very late and would not accrue any weight. \(P\) becomes canonical as well if released on time. The reason for this is that, if no equivocation is detected at this point, all AC members would have "headlocked" on \(B\), and will therefore vote for \(P\) (see the AC member section), which ensures that it becomes canonical (we see why in the attestation logic). Best case for everyone.
  • Equivocation detected: the builder does not release, and there's a whole epoch for the proposer to be slashed on-chain, which will prevent the payment.
• Late or poorly attested beacon block: if the builder does not see at least 40% of attestations by the latest point at which it would consider releasing \(P\), and we assume the builder is sufficiently well connected, then \(B\) can only cross the 60% threshold for the payment to be released if there are over 20% very late attestations, which we assume is not the case (attesting on time is part of honest behavior).

Proposer

Very little changes about the behavior of the proposer. Here, we focus on the proposer of slot N+1 to continue with our analysis of the process started at slot N. Firstly, the proposer runs the fork-choice just like today, with the exception of blocks with and without payloads being separate and competing fork-choice objects. If the head of the chain is not a beacon block proposed in slot N, it just extends it normally. If instead it is a beacon block \(B\) from slot N, and it is not subject to proposer boost reorging, it has to determine whether to extend \(B\) or its payload \(P\) (more precisely, the object "\(B\) with payload"). At this point, it cannot do so based on attestations from slot \(N\), because attesters in slot \(N\) did not have a chance to attest to \(P\) yet. Instead, it uses the availability committee to make this determination, by using a relative majority threshold: if a majority of the AC votes it received (not necessarily of all possible votes) is positive, it extends \(P\), and otherwise extends \(B\) (without a payload). As we'll see in the upcoming section about attesters, this is the same criterion they use to decide what to attest to.

In order to prevent cases where the AC is roughly evenly divided and a few strategically released adversarial votes can sway attesters against what the proposer chose, we use a lightweight view-merge, only applied to the AC votes from the previous slot:

1. The proposer includes all AC votes it knows of in its beacon block
2. Upon receiving the beacon block, attesters consider all AC votes received before \(t=10s\) as well as all AC votes included in the beacon block

As usual, one needed clarification is what to do with equivocating AC votes. Luckily, in this case we have a very simple way of dealing with them:

1. Only consider and propagate the first vote you see
2. When receiving a beacon block with a vote that conflicts with one you already have, use the former

With this, assuming sufficient network synchrony, the AC votes used by attesters in slot N+1 will exactly coincide with the AC votes used by the proposer. The reasoning is simple: the set of votes seen by the proposer is a superset of the votes seen by any attester, except possibly in the case of equivocations, and in the case of equivocations the attesters will just default to agreeing with the proposer. More explicitly:

• If an attester has seen a vote \(v_i\) from validator i by \(t=10s\), then the proposer also sees \(v_i\) or a conflicting vote \(v'_i\) from the same validator. Either way, such a vote shows up in the beacon block. In the previous case, both the attester and the proposer will use vote \(v_i\) for validator \(i\), while in the latter they will both use \(v'_i\), because the attester will go with the proposer's choice in case of equivocation.
• If an attester has not seen a vote from validator \(i\) but the proposer has, the proposer includes the vote in its beacon block and the attester uses it.
• If neither an attester nor the proposer have seen a vote from validator \(i\), neither of them uses such a vote.

AC voter

The availability committee has three purposes:

1. Like the PTC, it votes on timeliness/availability of the payload, to enforce that the next state is publicly known some time before the end of the slot
2. It votes on the availability of the data associated to the payload, to provide an availability signal to the next proposer, in case it does not subscribe to all column subnets (it does not download all of the blob data).
3. It makes an initial, very limited determination of IL satisfaction, which does not require executing the payload.

An AC member acts like this throughout slot N:

1. As soon as it sees a beacon block \(B\) from the proposer of slot N, it "locks on it" (see headlock), meaning that as an AC member it will vote for or against the payload \(P\) that \(B\) commits to. This is to prevent proposer equivocation from impacting the builder: if the builder does not detect an equivocation and releases \(P\), then all AC members should have already headlocked on \(B\) and will vote for \(P\), even if they later see another conflicting beacon block and payload.
2. At 7s, it votes for a payload matching its "headlock", if it has seen one and:
   • DA check is satisfied: all of its custody columns are available
   • Optimistic IL satisfaction: the bitfield included in the payload has a 1 for all IL senders for which an IL was seen by the freeze deadline of slot N-1 (10s).

As we already discussed, the proposer and attesters of slot N+1 require the payload to get a majority of AC votes. Assuming the AC is majority honest (or a bit more in the case of the DA check, to account for the error induced by partial availability views), this means that the AC can succesfully enforce that the payload be published on time and with a bitfield that commits to satisfying all timely sent ILs.

The DA check differs somewhat from the rest, in that attesters in the next slot will again do their own DA check, and so will attesters in future slots as well: no one will attest to something unavailable, even if for whatever reason this has happened in previous slots. As already mentioned at the beginning, the AC is not so much enforcing DA, but rather providing an early signal about DA to the next proposer, in case it cannot make a full availability determination by itself.

IL enforcement

While the timeliness and DA enforcement is straightforward, the IL enforcement is not so, so let's discuss it a bit more in detail. The bitfield is used by the next slot's proposer to decide whether to extend the payload or not, by checking satisfaction of the ILs it implicitly references, and in the same way it will be used by the next slot's attesters to decide whether to vote for the payload (or a block extending it) or not. In other words, IL enforcement is split into two parts:

1. The bitfield implicitly establishes a set of ILs that the payload commits to satisfying, and the AC just enforces that the bitfield is sufficiently inclusive, i.e., that the payload commits to satisfying all ILs it should, based on the AC member's own view.
2. Given that a payload has passed the bitfield check of the AC, by receiving 50% of the AC's votes, the attesters of slot N+1 actually check compliance of the payload with the ILs that it committed to satisfying, which requires execution of the payload (at least with EIP-7702)

A small caveat here is that a bitfield over IL proposers does not uniquely specify an IL in the case of IL proposer equivocation, where the builder might have seen and satisfied one IL but other nodes might expect another one to be satisfied. However, our propagation rule for ILs prescribes to propagate up to two ILs per IL proposer, so that equivocation evidence spreads by default. Then, attesters of slot N+1 will simply ignore any ILs from equivocating IL proposers: even if the bitfield has a 1 for a certain equivocating IL proposer, attesters will treat it as a 0, so they will not put any extra constraint on the payload based on ILs sent by that proposer.

Attesters

Finally, we are getting to the last actors in our pipeline, the ultimate enforcers of everything that we have discussed, because responsible for solidifying temporary local decisions and AC votes into the fork-choice.

Fork-choice

Let's first discuss exactly how the fork-choice works in this context. Instead of just beacon blocks, the block tree now has two kinds of objects: empty and full beacon blocks, or in other words beacon blocks without and with a payload. For a given beacon block \(B\) committing to payload \(P\), both "\(B\) with \(P\)" and "\(B\) without \(P\)", or \(B\) empty and \(B\) full, have the same parent in the fork-choice tree, which is \(B\)'s parent (and which could itself be an empty or a full block). As usual for objects with the same parent in the fork-choice tree, \(B\) empty competes with \(B\) full, meaning that only one of the two branches can be chosen when the fork-choice is run.

Choosing a branch is done by picking the subtree with the most attestation weight, as always, but with a small caveat: the votes to \(B\) empty from \(slot(B)\) are counted both for \(B\) empty and \(B\) full, whereas votes from slots \(> slot(B)\) can only fall in one of the two subtrees. There's a simple reason for this: attesters in \(slot(B)\) can only attest to \(B\) empty, because at that point the payload has not been released yet. The decision between \(B\) empty and \(B\) full is initially made by the AC, and it is then solidified by the round of attestations in \(slot(B)+1\), as we discuss in the next section. At that point, those attestations are the only fork-choice weight that distinguishes \(B\) empty from \(B\) full, since the attestations from \(slot(B)\) count for both, and they therefore fully determine the final decision between them.

Attestation behavior

Attesters at slot N+1 run the fork-choice and figure out what the head of the chain is. There are two cases depending on whether or not a beacon block from slot \(N\) is reached:

• Head of the chain is from slot < N: in this case, the AC votes from slot \(N\) are irrelevant, as the determination of whether or not the head of the chain is a beacon block with or without a payload is made purely based on previous attestations. For example, say the head of the chain is a beacon block \(A\) from slot \(N-1\). Then, attesters of slot \(N\) have already had a chance to vote on \(A\) empty and \(A\) full, and the ultimate decision between them depends on their votes. In this case, the attester votes either for the head of the chain or for a new beacon block extending it, if there is one.
• Head of the chain is from slot \(N\): in this case, they now have to determine whether or not to vote for the payload being present, based on the AC votes. This has a two steps:
  1. They first merge their view of AC votes with the current proposer's view, in the way we already described in the proposer's section (if the current beacon block has a conflicting AC vote from that in your frozen view, use that vote instead of yours)
  2. If the payload meets a 50% threshold among the AC votes they are now considering, all of the custody columns are available and all ILs referenced by the bitfield are satisfied, they vote for the payload (\(P\)) or for a new beacon block extending it, if there is one. If instead the payload does not meet the 50% threshold, they vote against the payload, meaning either for the beacon block from slot \(N\) (\(B\)) or for a new beacon block extending it

As already mentioned in the section about the availability committee, "ILs referenced by the bitfield" means "all ILs sent by IL proposers with a 1 in the bitfield, excluding only equivocators".