Ref: https://ethresear.ch/t/das-fork-choice/19578

<aside> 💡 δ-safety of sampling: If some data is less than half-available, at most a fraction δ of the honest validators will perceive it as available. As a consequence, no more than a fraction δ of the honest validators would vote for an unavailable block.

</aside>

• Note that the attacks and mitigation presented here happen in a votes per slot protocol (Ethereum).
• Peer DAS
  • The distribution phase can also serve as a kind of preliminary sampling phase, enabling a validator to consider data available if all the columns it’s required to custody are available, even before completing the actual sampling phase.
• Fork-choice rules
  • Tight fork-choice
    • Peer Sampling. Require a sufficiently high amount of sampling to be completed before ever voting for a block.
    • We call the fraction of validators that would be tricked using peer sampling $\delta_p$
  • Trailing fork-choice
    • Subnet Sampling: Validators would base their vote on the outcome of the column distribution; if all the data within its assigned subnets is available, a validator deems the entire block available and votes accordingly.
    • Peer sampling for this block would then only be required to be completed before the next slot.
    • We call the fraction of validators that would be tricked using subnet sampling $\delta_s$
• Attacks
  • Ex-ante reorgs
    1. Adversarial blocks B and C are withheld together with adversarial attestations comprising 21% of each committee.
    2. An honest proposer extends block A with block D, and the adversary then reveals the withheld objects before the attestation deadline.
  • Proposer sees unavailable, attesters see available: enhanced ex-ante reorgs
    • With tight fork-choice
      1. Adversary publishes block B but not the associated data. Maximizes the amount of honest validators whose subnet sampling is successful, who think that B is available.
      2. Therefore, δ such validators vote for B, joining the β adversarial validators.
      3. The adversary then extends B with another block C, itself fully available. Again, δ honest validators and β adversarial validators vote for C
      4. This continues until an honest slot, whose proposer attempts to fork B out. At this point, the adversary makes B available, and the honest proposal does not get voted if the votes on the adversarial chain overcome the proposer boost.
    • With trailing fork-choice
      • With subnet sampling, the previous attack can become significantly easier.
    • Mitigation
      • Attesters of slot n+1 complete peer sampling 10s into slot n, while the proposer can keep trying to sample until they propose.
      • If the proposer extends a block which an attester sees as unavailable, they try to sample again.
      • Attesters of slot 4 do not see B as available unless the proposer of D does as well: either the proposer sees B as available and D extends C, or the proposer sees B as unavailable and so do attesters. In either case, they vote for D.
  • Proposer sees available, attesters see unavailable
    • Tricking an honest proposer into extending an unavailable chain
      1. The adversary only publishes a single unavailable block B during slot 2 and does not publish any block in slot 3.
      2. The adversary convinces the proposer for slot 4 that B is available. As a result, the proposer for slot 4 does not attempt to reorg B.
      3. As a result:
         • Since all other validators see B as unavailable, they continue to vote for A.
         • The proposer for slot 5 extends A with D, effectively reorging the honest and available block C
         • The attack could even target multiple honest proposers in a row.
• (block-slot) fork-choice

  • The attacks discussed above can be effectively addressed by employing a variation of the fork-choice rule known as the (block, slot) fork-choice function: At any given slot t, considering a proposal B extending the head of the canonical chain A, we also take into account the empty slot identified by A.

    

  • In the attack Proposer sees available, attesters see unavailable

    1. The majority of validators would then effectively vote for the pair (A, t+1).
    2. Continuing the sequence of events in the attack, at slot t+2, the adversary abstains from proposing any block. Consequently, the majority of validators will opt to vote for A which effectively means voting for the pair (A, t+2).
    3. At this point, although the adversary makes the honest proposer for slot t+3 believes that B is available, such proposer would still extend A since the chain (A, t+2) is heavier compared to the chain with head (B, t+1).

  • Backoff scheme

    • One of the disadvantages of the current proposal is that the performance under bad network conditions becomes worse. Chain growth stops completely if block latency is > SECONDS_PER_SLOT / 3 (= 4 seconds in the current config).
    • Therefore, a backoff scheme is necessary to facilitate chain progression during periods of extended latency. Without such a mechanism, the chain would continuously build on the same (empty) block, resulting in a sequence of empty blocks and an inability to extend the chain with non-empty ones.
    • An active backoff has the effect of delaying by one slot the counting of votes for the empty slot: votes for A only count for the empty slot (A,s) if they are at least from slot s+1. In other words, we take all votes directly for empty slots and move them back by one slot: votes to (A,t+1) count for (A,t), votes for (A,t+2) count for (A,t+1).
• A direction for further improvement: the majority fork-choice
  • At slot t, we could find the best_child and then pit it against all of the voting weight from slots ≥ t which did not vote on the best_child’s subtree. In other words, we require a block from slot t to have a majority of all attesting weight from slots ≥ t. This way, it wouldn’t matter if the adversary finds ways to split honest votes: a vote is against a block whenever it could have been for it but isn’t.