fork choice test format

[djrtwo]

Issue

We need to come to consensus on a fork choice test case format relatively soon. I'd argue that this should come before the full-blown state tests because it can test a very isolated component of the spec before everything else is done.

As I began to sculpt the test case format, I realized there are two potential paths -- one that is very abstract wrt to the actual mechanics of the spec or one that is more concrete using validators/attestations in the test case.

I would like to air on the side of abstract for simplicity but am worried that if it is too abstract, it might actually make more work on client side to get tests running.

An abstract version of the fork choice test case would look something like the following, where blocks just defines abstractly defines a block tree, weights is the integer amount of total weight given to a block (akin to the latest attestations), and head is the result of running the fork choice on the block tree + weights.

blocks:
  - id: <block-id>
    parent: <block-id>
weights:
  # if no matching key for block-id, weight = 0
  - <block-id>: <int>
  - ...
head: <block-id>

The benefit is that it is very easy to reason about and can easily even test the fork choice against an implementation not deeply embedded in a 2.0 implementation. The downside is that a client must be able to take this structure and convert it into something usable (create real blocks, validators, and attestations of blocks) or they must be able to take the real spec objects and distill them into this more abstract form to run their fork choice.

A concrete version would have an actual list of validators, weights, slots for blocks, and latest attestations.

I lean in the direction of the abstract version but want to get more input before I work toward a polished proposal.

[djrtwo]

cc: @mratsim, @ChihChengLiang, @ChihChengLiang, @jannikluhn, @hwwhww

[jannikluhn]

I also like the abstract version as it specifies exactly what's being tested and nothing more. Everything else would just add more free parameters which make the tests harder to read and write, but are actually irrelevant for the test result. As far as I can see, translating the abstract chain structure into actual blocks should be fairly easy.

[AgeManning]

I also like this abstract version. Lighthouse intends to implement these as isolated tests for fork choice and as mentioned have more thorough tests which check block slots, validators etc.

[AgeManning]

The head for an equally weighted fork is not deterministic right? If so, perhaps the head field could have multiple answers?

blocks:
  - id: <block-id>
    parent: <block-id>
weights:
  # if no matching key for block-id, weight = 0
  - <block-id>: <int>
  - ...
heads:
  - id: <block-id>

[djrtwo]

Ties can actually occur at various branch decisions when performing the GHOST rule so I think we don't want to require the complexity of having to follow both branches.

Ties in practice will be incredibly rare and it actually won't matter how a client decides to locally break them. Both lowest hash and earliest received are reasonable strategies.

For this test, I suggest breaking ties via earlier in the blocks list (simulating earlier received).

[jannikluhn]

For this test, I suggest breaking ties via earlier in the blocks list (simulating earlier received).

Depending on how the fork choice rule is implemented, it might be hard to add a special tie break rule that's used in tests only. Could we either

• add the tie break rule to the spec so that there's never any ambiguity or
• don't have any ties in tests or
• specify all possible heads as suggested by @AgeManning?

For the last option, implementations wouldn't be required to answer with all possible heads, they could just check if their result is one of the valid ones.

[AgeManning]

Ties in practice will be incredibly rare and it actually won't matter how a client decides to locally break them. Both lowest hash and earliest received are reasonable strategies.

We are currently testing the optimised version as proposed by Vitalik. This implementation uses bitwise LMD GHOST and definitely finds different heads compared to standard GHOST and the spec implementation. I guess until the spec decides which way to go with which fork-choice, I should consider this implementation as non-spec and build separate tests for it?. Just FYI this implementation prefers smaller hashes to break ties.

In regards to the complexity (and perhaps useful in designing the tests), I've assumed that the blocks are given in order (to avoid any recursion logic in building the block dag). More specifically, any parent: <block_id> I expect that the <block_id> has previously been defined (apart from genesis, where I've assumed parent == id.)

I'm finishing up constructing a handful of basic test cases for bitwise LMD ghost and standard LMD ghost and can share if anyone is interested.

[djrtwo]

For the last option, implementations wouldn't be required to answer with all possible heads, they could just check if their result is one of the valid ones.

That is an interesting proposal. The test generator at least would need to go down both paths.

If we do decide to have a deterministic tie breaker, using block hash is very straight forward to adapt in this proposal as long as implementations can take a block hash defined in this test and override whatever computed hash the actual block data structure produces. This would essentially just require converting id into a root and parent to parent_root.

There is a tiny grinding opportunity to win a tie, but ties in practices will be exceedingly rare and fleeting if they occur due to the 100s of attestations coming in every second. If an attacker is sophisticated enough to construct a tie, they would more likely just force the block to win over the alternative.

blocks:
  - root: <block-root>
    parent_root: <block-root>
weights:
  # if no matching key for block-root, weight = 0
  - <block-root>: <int>
  - ...
head: <block-root>

[djrtwo]

We are currently testing the optimised version as proposed by Vitalik. This implementation uses bitwise LMD GHOST and definitely finds different heads compared to standard GHOST and the spec implementation.

Can you share the bitwise one? Something is in error if they are not finding the same head. Any optimized version should be the same result given a set of inputs as the naive version.

[AgeManning]

We implemented this:
https://github.com/ethereum/research/blob/master/ghost/ghost.py
Note the choose_best_child function, which utilizes bitwise LMD ghost. I understand it has benefits when transitioning to CBC casper.

It can re-write the choose_best_child function to remove the bitwise aspect, wasn't sure which way the spec was heading.

For reference: https://ethresear.ch/t/bitwise-lmd-ghost/4749

[djrtwo]

The trajectory as of now is the use the the functionality found in the spec rather than the bitwise modification (which can indeed return different results in some cases). My understanding is that if we adopted bitwise it would not be in phase 0. Asking Vitalik and others to make sure