PeerDAS fork-choice part 2

This post follows a previous one on the fork-choice of PeerDAS, incorporating changes stemming from the recent developments in the design of PeerDAS.

Roles of peer sampling

Peer sampling for full nodes: transaction confirmation

The first role of peer sampling concerns full nodes, in particular the security of transaction confirmations. Still, we do not need to use peer sampling for the safe head rule, because this already relies on an honest majority assumption, which, if satisfied, would already guarantee availability. Instead, as far as transaction confirmation is concerned, we only need to use peer sampling to ensure availability of finalized checkpoints.

Peer sampling for attesters: resistance to supermajority attacks

As discussed in the interop update on PeerDAS, peer sampling is not necessary in order for consensus to function, as long as we have a sufficiently high custody requirement. In other words, as long as we have enough subnet sampling to ensure that at most a small percentage of the validators can ever vote for something unavailable.

Still, peer sampling can play a role in improving a validator's response to supermajority attacks which invole the justification or finalization of an unavailable block. In such a situation, we would like to ensure two things:

An honest validator never votes with an unavailable source, i.e., to finalize an unavailable checkpoint. This would end up locking them on an unavailable chain, unable to even manually switch without slashing themselves through surround voting.
If an unavailable block is finalized, honest validators are able to construct a minority chain. If we can ensure that, we know that the attacker cannot easily disrupt this chain, because voting outside of the subtree rooted at the unavailable finalized block would lead to slashing.

Peer sampling for proposers? Reorg resilience

The last role of peer sampling could be to provide some protection against reorg attacks to proposers that are not supernodes. In particular, the reorg attacks we are concerned with are ones in which the attacker tricks the proposer into believing that a block is available. The proposer then builds on an unvailable block, and no one attests to it. To be precise, the attack requires for there to be one slot between the unavailable block and the honest slot, because otherwise proposer boost reorging would be triggered due to the lack of votes. The attacker would then need to control at least two consecutive slots.

In the previously linked document, we have suggested switching the fork-choice to a variant of the (block, slot) fork-choice, there called "the majority fork-choice", which would completely prevent this attack vector. However, this would come with the added complexity of a backoff scheme. If we do wish to avoid it for the time being, we could instead employ peer sampling as an extra defensive measures for proposers. In particular, we can have
proposers do peer sampling on very weak blocks, for example ones whose total weight is $< 20$ % of a committee's weight, the threshold that we currently use to decide whether to attempt a proposer boost reorg. If peer sampling fails, such blocks would be considered unavailable and not extended by the proposer, even if other conditions would normally prevent attempting proposer boost reorg, like the reorg depth being > 1.

In order to carry out the attack, it would then be necessary to "defeat" peer sampling, by satisfying all of the proposer's sampling queries without actually making the data available. This does not seem much easier than directly DoSing the proposer, which is already possible today. Moreover, recall that this attack is only applicable to proposers that do not download all of the data, so the vast majority of proposers would not be vulnerable, if the validator custody prescription is widely followed.

Peer sampling in the fork-choice spec

To fulfill the first two roles of peer sampling discussed in the previous section, we employ it in two places in the fork-choice spec. For now we leave out the third role, because there is a lot of room for specifying exactly how and when proposers should use peer sampling in combination with proposer boost reorgs, if indeed that turns out to be the preferred way to handle the attack vector we described.

on_block

We do not import a block whose unrealized justified checkpoint is unavailable with respect to peer sampling:

pulled_up_state = state.copy()
process_justification_and_finalization(pulled_up_state)
assert is_chain_available(store, pulled_up_state.current_justified_checkpoint.root)

With this, we get two benefits:

We never update store.justified_checkpoint or store.finalized_checkpoint to something unavailable with respect to peer sampling (neither directly nor through realization of unrealized justification), nor do we ever have a block in the store whose justified checkpoint is unavailable with respect to peer sampling. Any API which exposes justifications and finalizations, either in the store or in the state, will never expose something unavailable, ensuring security of transaction confirmation.
We never attempt to vote with an unavailable voting source, because we do not have any such block imported. Therefore, we cannot ever end up locked on an unavailable chain, unable to switch without surround voting.

get_head

We are only left with the last goal, i.e., allowing honest validators to react to the finalization of an unavailable checkpoint by building a minority fork. To do so, we want to ensure that, in any such situation, get_head will filter out the unavailable chain and allow the validator to vote on some other branch. Note that this cannot lead to self slashing because we have already ensured that we never vote with an unavailable source.

When running get_head and determining whether a block should be filtered out because of unavailability, we require peer sampling to be satisfied only as long the block's epoch is at least two epochs in the past. When that is the case, it is possible that this block is already finalized, on some branch which we would not have imported due to the availability check in on_block. At this point, we consider this block unviable (at least until peer sampling succeeds) and try to contribute to another chain.

def is_peer_sampling_required(store, slot):
    return compute_epoch_at_slot(slot) + 2 <= get_current_epoch(store)

def get_head(store: Store) -> Root:
    # Get filtered block tree that only includes viable branches
    blocks = get_filtered_block_tree(store)
    # Execute the LMD-GHOST fork choice
    head = store.justified_checkpoint.root
    while True:
        # Get available children for the current slot
        children = [
            root for (root, block) in blocks.items()
            if (
                block.parent_root == head
                and is_data_available(
                    root, 
                    require_peer_sampling=is_peer_sampling_required(store, block.slot)
                )
            )
        ]
        if len(children) == 0:
            return head
        # Sort by latest attesting balance with ties broken lexicographically
        # Ties broken by favoring block with lexicographically higher root
        head = max(children, key=lambda root: (get_weight(store, root), root))