Implement and Benchmark LMD Ghost Fork-Choice

[rauljordan]

Hi all,

We need to implement and benchmark a simple version of Latest Message Driven (LMD) GHOST (Greediest Heaviest Observed Sub-Tree) as a fork-choice algorithm for the beacon chain. As defined in the latest specification:

Spec Definition

The beacon chain fork choice rule is a hybrid that combines justification and finality with Latest Message Driven (LMD) Greediest Heaviest Observed SubTree (GHOST). At any point in time a validator v subjectively calculates the beacon chain head as follows.

• Let store be the set of attestations and blocks that the validator v has observed and verified (in particular, block ancestors must be recursively verified). Attestations not part of any chain are still included in store.
• Let finalized_head be the finalized block with the highest slot number. (A block B is finalized if there is a descendant of B in store the processing of which sets B as finalized.)
• Let justified_head be the descendant of finalized_head with the highest slot number that has been justified for at least EPOCH_LENGTH slots. (A block B is justified if there is a descendant of B in store the processing of which sets B as justified.) If no such descendant exists set justified_head to finalized_head.
• Let get_ancestor(store, block, slot) be the ancestor of block with slot number slot. The get_ancestor function can be defined recursively as def get_ancestor(store, block, slot): return block if block.slot == slot else get_ancestor(store, store.get_parent(block), slot).
• Let get_latest_attestation(store, validator) be the attestation with the highest slot number in store from validator. If several such attestations exist, use the one the validator v observed first.
• Let get_latest_attestation_target(store, validator) be the target block in the attestation get_latest_attestation(store, validator).
• The head is lmd_ghost(store, justified_head) where the function lmd_ghost is defined below. Note that the implementation below is suboptimal; there are implementations that compute the head in time logarithmic in slot count.

def lmd_ghost(store, start):
    validators = start.state.validator_registry
    active_validators = [validators[i] for i in
                         get_active_validator_indices(validators, start.state.slot)]
    attestation_targets = [get_latest_attestation_target(store, validator)
                           for validator in active_validators]
    def get_vote_count(block):
        return len([target for target in attestation_targets if
                    get_ancestor(store, target, block.slot) == block])

    head = start
    while 1:
        children = get_children(head)
        if len(children) == 0:
            return head
        head = max(children, key=get_vote_count)

[vbuterin]

Here's a python implementation that avoids going through the entire chain from start to end and cuts the complexity down to O(n * log^2(t)): https://github.com/ethereum/research/blob/master/clock_disparity/lmd_node.py#L229

Though the above is not the only way to do it. Another possible approach is an "online" algorithm where you keep extra data that lets you compute an upper bound on how many blocks back you would have to recalculate (basically, at each height store the total deposits supporting that block minus the total deposits supporting its best competitor, and then decrease that value every time there are validator balance changes or a validator switches from supporting that chain to not supporting that chain, and recompute from that height when the value reaches zero). There's a large space of LMD GHOST optimizations that hasn't really been explored yet.

[terencechain]

Closed via #1933 see #1951 for further optimizations