Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
## 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment