ghost_implementation.py

## Code NOT run or tested or audited. For exposition purposes only.

latest_messages = [_ for i in range(len(validators))]
scores = {}

# Note re big O notation: N = messages, B = balance changes, T = history length

def update_latest_messages(new_messages: List[Tuple[int, int, bytes32]]):
    # new_messages: (validator index, slot of new target, block_hash of new target) for each new message
    starting_slot = 0
    activations = {}
    # Preprocessing (O(N))
    for index, slot, block_hash in new_messages:
        # Add a record for when to start processing the validator's new message
        if slot not in activations:
            activations[slot] = {}
        if block_hash not in activations[slot]:
            activations[slot][block_hash] = {}
        activations[slot][block_hash][index] = 1

        # Add a record for when to start removing the validator's old message
        old_slot, old_block_hash = latest_messages[index]
        if old_slot not in activations:
            activations[old_slot] = {}
        if old_block_hash not in activations[old_slot]:
            activations[old_slot][old_block_hash] = {}
        activations[old_slot][old_block_hash][index] = -1

        starting_slot = max(starting_slot, slot)
        assert slot > old_slot

    # The set of blocks whose scores we are modifying, for each block
    # storing {validator index: flag} (+1 if that object is representing that
    # validator's new message, -1 if it's representing its old message)
    active_blocks = {}
    # Walk backwards through history
    for slot in range(starting_slot, -1, -1):
        # If there are new or old messages at this slot for some hash, introduce them
        # into the active_blocks map
        # O(N) total as there are 2N total activations
        if slot in activations:
            for block_hash, validators in activations[slot].items():
                total_delta = sum([
                    get_balance_at_block(block_hash, index) * flag
                    for index, flag in activations[block_hash].items()
                ])
                active_blocks[block_hash] = (activations[block_hash], total_delta)
        # For every block in the active blocks map... (O(T + B) total as there are a total of maximum
        # T blocks and B balance changes)
        for block_hash, (validators, delta) in active_blocks:
            # Avoid processing blocks multiple times in the case of skips
            if get_slot(block_hash) != slot:
                continue
            # Update its score by the total delta
            scores[b] += delta
            # Update the delta based on any balance changes (this assumes these balance changes are saved)
            for index, old_balance, new_balance in get_balance_changes_at(block_hash):
                if index in validators:
                    active_blocks[block_hash][1] += (old_balance - new_balance) * validators[index][flag]
        # Update the active blocks map (O(N * log N) for processing intersections, O(T) for processing
        # parent-merges, O(T) for walking back through the block tree structure). The goal is to make sure
        # that active_blocks continues to represent the old and new blocks each validator is voting for
        # *at the slot we're currently walking through*
        new_active_blocks = {}
        for block_hash, (validators, delta) in active_blocks:
            # Either the parent, or the same block in case of skips
            parent_hash = get_ancestor_at_height(block_hash, slot-1)
            if parent_hash not in new_active_blocks:
                new_active_blocks[parent_hash] = active_blocks[block_hash]
            else:
                deletes = []
                for v, flag in validators.items():
                    if v in new_active_blocks[parent_hash][0]:
                        existing_flag = new_active_blocks[parent_hash][0][v]
                        # Sanity check: if a validator appears twice, it's because one is an old message and
                        # the other is a new message
                        assert existing_flag * flag == -1
                        new_active_blocks[parent_hash][1] -= get_balance_at_block(parent_hash, v) * existing_flag
                        # If the ancestor of a block
                        deletes.append(v)
                    else:
                        new_active_blocks[parent_hash][0][v] = flag
                        new_active_blocks[parent_hash][1] += get_balance_at_block(parent_hash, v) * flag
                for v in deletes:
                    del new_active_blocks[parent_hash][0][v]
        active_blocks = new_active_blocks