# LMD GHOST Balancing Attack Mitigation Implementation

Proosed solution: https://notes.ethereum.org/6EAsltAXSIeMHeRztEGRdg

## Current Status in Teku

Currently, Teku's fork choice implementation uses the protoarray approach. As each attestation is processed, the current vote for that validator is updated but the new weightings are not actually applied to blocks.

1/3rd into the slot, a "full" fork choice is run which applies any pending weighting changes and then selects the best block as the canonical chain head. It is only at this point that Teku can reorg to a different chain.

When blocks are imported, if they are the child of the current chain head, they automatically become the new chain head.

Validator clients currently support two modes - a legacy one where they produce attestations only when that "full" fork choice completes, so timing is based off of the beacon chain, and a new one where attestation timing is based entirely off the validator's clock so there's no guarantee the full fork choice has completed before attestations are created. The new approach will be the default in the next release as it is required to work with the standard REST API.

Operations that modify the protoarray or votes are performed on a single fork choice thread (though most verification happens prior to moving to the fork choice thread). This include block and attesation processing as well as the full fork choice runs. The fork choice queue processes operations in the order they are submitted (though prioritisation may be considered in the future).

## Requirements
Restating the required changes:

1. Attestations in slot $N + 1$ should be created based only on the attestations received by the end of slot $N$. ie if at the end of slot $N$ a full fork choice run would select block $A$ as the chain head, and then further attestations are received in the first third of slot $N + 1$ which are enough to instead select block $B$ as the chain head, the created attestatations in slot $N + 1$ should be for $A$.
- Attestations from slot $N$ received after the end of slot $N$ are however still valid, so assuming no further attestations were received in the example above, in slot $N + 2$ the attestations would switch to $B$.
2. When a block for slot $N$ is received within the first third of slot $N$, it is imported as usual but also acts as an additional attestation with weight of $\frac{W}{4}$ (weight of attesters scheduled for that slot / 4).
- At the start of slot $N + 1$ the "proposer attestation" added above is reversed.
- This implies that at the start of a new slot (based on wall clock time), all "proposer attestations" can be reversed, regardless of which fork they are on (because you can't import a block from a future slot).

## Implementation Plan

### Attestation Timing

- Track the last slot that full fork choice was run on (in memory only)
- When a request to create a block is received
- if fork choice has not yet been triggered for that slot, start it.
- Wait for fork choice for that slot to complete
- Create the block
- At start of slot, if full fork choice hasn't already been triggered, add one to the fork choice thread queue.
- This timing of full fork choice run will ensure that the node selects the best branch based on attestations that had been received and at least queued on the fork choice thread by the end of the slot. Attestations after that point won't have their weighting applied until the next full fork choice run at the start of the next slot.

### Extra Proposer Weighting
- At the start of the slot, get the list of current proposer weightings, and for each of them reduce block node weight by the proposer weighting and delete the weighting. Same process as below but with a negative delta instead of positive. May need to run `updateBestDescendantOfParent` in second pass.
- If fork choice thread receives a block before 1/3rd of the way through the slot, after applying the block:
- Calculate $\frac{W}{4}$
- Record a proposer vote (`slot`, `block_root`, $\frac{W}{4}$)
- Apply weight by starting at new block's node and adding weight to it and each of it's ancestors
- Iterate backwards through protonodes applying `updateBestDescendantOfParent` to each (can we do this in one pass here because there's only a single change to apply? Probably)
- Ensure that recentChainData.updateHead is called if the block resulted in a chain re-org.
- Ensure `BlockImportResult` is marked as canonical

## Potential Challenges

1. Calculating the total weight of all attestors for a slot is a new and potentially expensive operation. It would iterating through $\frac{1}{32}$ of validators to sum their balance. Could be precomputed and cached, possibly even when calculating the committee.
2. Block production, especially for the first slot of an epoch, is already one of the most performance sensitive parts of the system. This change would require a full fork choice run to be completed prior to block proposal, delaying it further.
- Teku was considering moving the fork choice run to just before the start of the slot to ensure a more up to date view for block production. Would be useful to understand the impact of making the cut off for attestations even 1 second prior to the end of the slot instead of at the end of the slot to improve performance. Would it be any different to clock skew?

## Questions

1. Any issues with how this with fit in with validator clients using independent timing?
- What if they attest slightly early and so attest to empty slot, then block is received prior to cut off and gets extra boost?
- If they attest slightly late so the block is received after cut off but before attestations are made, should they attest to the block being present or not?
2. Does a block received after 1/3rd of the way through the slot still become the canonical head immediately?
3. How does this relate to the fork choice by (block, slot) pair change?