Try   HackMD

Lido Oracle
Associated slashings research

The purpose of this research is to find possible solutions to the algorithm for finalizing requests in the bunker mode, taking into account the associated slashings. We will consider a slashing associated with an request if it started before the request and ended after.

Everything described below applies only to bunker mode. In turbo mode, we do not limit request finalization by associated slashings.

Let's start with the specifications.

Initial slashing

When a validator is slashed the following happens:

def slash_validator(state: BeaconState,
                    slashed_index: ValidatorIndex,
                    whistleblower_index: ValidatorIndex=None) -> None:
    """
    Slash the validator with index ``slashed_index``.
    """
    epoch = get_current_epoch(state)
    initiate_validator_exit(state, slashed_index)
    validator = state.validators[slashed_index]
    validator.slashed = True
    validator.withdrawable_epoch = max(validator.withdrawable_epoch, Epoch(epoch + EPOCHS_PER_SLASHINGS_VECTOR))
    state.slashings[epoch % EPOCHS_PER_SLASHINGS_VECTOR] += validator.effective_balance
    decrease_balance(state, slashed_index, validator.effective_balance // MIN_SLASHING_PENALTY_QUOTIENT_ALTAIR)

    # Apply proposer and whistleblower rewards
    proposer_index = get_beacon_proposer_index(state)
    if whistleblower_index is None:
        whistleblower_index = proposer_index
    whistleblower_reward = Gwei(validator.effective_balance // WHISTLEBLOWER_REWARD_QUOTIENT)
    proposer_reward = Gwei(whistleblower_reward * PROPOSER_WEIGHT // WEIGHT_DENOMINATOR)
    increase_balance(state, proposer_index, proposer_reward)
    increase_balance(state, whistleblower_index, Gwei(whistleblower_reward - proposer_reward))

def initiate_validator_exit(state: BeaconState, index: ValidatorIndex) -> None:
    """
    Initiate the exit of the validator with index ``index``.
    """
    # Return if validator already initiated exit
    validator = state.validators[index]
    if validator.exit_epoch != FAR_FUTURE_EPOCH:
        return

    # Compute exit queue epoch
    exit_epochs = [v.exit_epoch for v in state.validators if v.exit_epoch != FAR_FUTURE_EPOCH]
    exit_queue_epoch = max(exit_epochs + [compute_activation_exit_epoch(get_current_epoch(state))])
    exit_queue_churn = len([v for v in state.validators if v.exit_epoch == exit_queue_epoch])
    if exit_queue_churn >= get_validator_churn_limit(state):
        exit_queue_epoch += Epoch(1)

    # Set validator exit epoch and withdrawable epoch
    validator.exit_epoch = exit_queue_epoch
    validator.withdrawable_epoch = Epoch(validator.exit_epoch + MIN_VALIDATOR_WITHDRAWABILITY_DELAY)

def compute_activation_exit_epoch(epoch: Epoch) -> Epoch:
    """
    Return the epoch during which validator activations and exits initiated in ``epoch`` take effect.
    """
    return Epoch(epoch + 1 + MAX_SEED_LOOKAHEAD)
Name Value Unit Duration
EPOCHS_PER_SLASHINGS_VECTOR uint64(2**13) 8,192 epochs ~36 days
MIN_VALIDATOR_WITHDRAWABILITY_DELAY uint64(2**8) 256 epochs ~27 hours
MAX_SEED_LOOKAHEAD uint64(2**2) 4 epochs 25.6 minutes

What is interesting for us here:

  • There is no easy way to tell by looking at a validator exactly when it was slashed.
  • The larger the exit queue, the further exit_epoch and withdrawable_epoch are.
  • The difference between withdrawable_epoch and exit_epoch can be pretty wide ranging from MIN_VALIDATOR_WITHDRAWABILITY_DELAY to EPOCHS_PER_SLASHINGS_VECTOR - 1 - MAX_SEED_LOOKAHEAD depending on the queue length.

Correlation slashing

def process_slashings(state: BeaconState) -> None:
    epoch = get_current_epoch(state)
    total_balance = get_total_active_balance(state)
    adjusted_total_slashing_balance = min(sum(state.slashings) * PROPORTIONAL_SLASHING_MULTIPLIER_ALTAIR, total_balance)
    for index, validator in enumerate(state.validators):
        if validator.slashed and epoch + EPOCHS_PER_SLASHINGS_VECTOR // 2 == validator.withdrawable_epoch:
            increment = EFFECTIVE_BALANCE_INCREMENT  # Factored out from penalty numerator to avoid uint64 overflow
            penalty_numerator = validator.effective_balance // increment * adjusted_total_slashing_balance
            penalty = penalty_numerator // total_balance * increment
            decrease_balance(state, ValidatorIndex(index), penalty)

What is interesting for us here:

  • Correlation slashing occurs at withdrawable_epoch - EPOCHS_PER_SLASHINGS_VECTOR // 2 epoch. So it counts from the end, and the time to its occurrence depends on the queue at the moment of slashing.

Request finalization

We want to finalize only requests which associated slashed validators have reached withdrawable_epoch. With both slash boundaries, it would be easy to determine which slashes should be accounted for and which should not, but slashed_epoch is not stored in the validator object.

Let's consider some scenarios and see how the numbers behave. For simplicity the current churn_limit is minimal and = 4.

Small or empty queue

A number of validators are slashed at the same time in the 10,000 epoch. In this case the validator states will change as follows:

[
  {
    exit_epoch: 10005, // epoch + 1 + MAX_SEED_LOOKAHEAD
    withdrawable_epoch: 18192 // epoch + EPOCHS_PER_SLASHINGS_VECTOR
  }, {
    exit_epoch: 10005,
    withdrawable_epoch: 18192
  }, {
    exit_epoch: 10005,
    withdrawable_epoch: 18192
  }, {
    exit_epoch: 10005,
    withdrawable_epoch: 18192
  },

  {
    exit_epoch: 10006, // + 1, since churn_limit for the previous epoch is reached
    withdrawable_epoch: 18192 // epoch + EPOCHS_PER_SLASHINGS_VECTOR
  },
  ...
]

Until the withdrawable_epoch calculated in slash_validator reaches the withdrawable_epoch calculated in initiate_validator_exit, we can easily calculate the slashed_epoch.

// while the queue is small
slashed_epoch = withdrawable_epoch - EPOCHS_PER_SLASHINGS_VECTOR

Large queue

A number of validators are slashed at the same time in the 10,000 epoch, the exit queue is 17,936 epochs.

[
  {
    exit_epoch: 17936, // exit_queue_epoch
    withdrawable_epoch: 18192 // exit_epoch + MIN_VALIDATOR_WITHDRAWABILITY_DELAY = epoch + EPOCHS_PER_SLASHINGS_VECTOR
  }, {
    exit_epoch: 17936,
    withdrawable_epoch: 18192
  }, {
    exit_epoch: 17936,
    withdrawable_epoch: 18192
  }, {
    exit_epoch: 17936,
    withdrawable_epoch: 18192
  },

  {
    exit_epoch: 17937, // + 1, since churn_limit for the previous epoch is reached
    withdrawable_epoch: 18193 // exit_epoch + MIN_VALIDATOR_WITHDRAWABILITY_DELAY
  },
  ...
]

If the queue exceeds MIN_VALIDATOR_WITHDRAWABILITY_DELAY - EPOCHS_PER_SLASHINGS_VECTOR, the withdrawable_epoch depends on the queue length.

In the example above, if the queue size exceeds MIN_VALIDATOR_WITHDRAWABILITY_DELAY - EPOCHS_PER_SLASHINGS_VECTOR, we cannot distinguish between a validator that slashed at epoch 10,000 and 10,001.

Comparison of slashings

Validator slashing life cycle depending on the exit queue size:

         active_ongoing      active_ongoing      active_slashed      active_slashed      exited_slashed      withdrawal_possible withdrawal_done     exited_slashed      withdrawal_possible withdrawal_done     Slasingin a smallqueueSlashingin a largequeue

Pseudo code

As a result, we can use a combined algorithm for finding the border of associated slashings: if possible, find slashed_epoch from the current state, if the queue is large, then make historical queries to the node.

"""
Spec constants. Should be defined in env to support different chain configurations.
https://github.com/ethereum/consensus-specs/blob/dev/specs/phase0/beacon-chain.md
"""
FAR_FUTURE_EPOCH = 2**64 - 1
MIN_VALIDATOR_WITHDRAWABILITY_DELAY = 2**8
EPOCHS_PER_SLASHINGS_VECTOR = 2**13
SLOTS_PER_EPOCH = 2**5


def get_associated_slashings_border_epoch(ref_epoch):
  """
  Returns the latest epoch to which the impact of the Lido validators slashing is accounted. 
  All completed slashings are ignored, in incompleted slashings it finds the earliest 
  slashed_epoch and returns the previous epoch. If there are no slashings or all are completed, 
  it returns ref_epoch.
  """

  earliest_slashed_epoch_among_incomplete_slashings = get_earliest_slashed_epoch_among_incomplete_slashings(ref_epoch)

  if earliest_slashed_epoch_among_incomplete_slashings is None:
    """
    No incompleted slashings. Requests up to and including the reference epoch take into 
    account all impacts of associated slashings

    x----->  |   completed slashing
    x------->|   completed slashing
             ^   reference epoch
    """
    return ref_epoch
  else:
    """
    There are incompleted slashings. Requests before earliest slashed epoch of incompleted 
    slashings take into account all impacts of associated slashings

    x----->  |        completed slashing
         x---|--->    incompleted slashing
          x--|---->   incompleted slashing
         ^   |        earliest slashed epoch among incompleted slashings
             ^        reference epoch
    """
    return earliest_slashed_epoch_among_incomplete_slashings - 1


def get_earliest_slashed_epoch_among_incomplete_slashings(ref_epoch):
  """
  Returns the earliest slashed epoch among all incompleted slashings. Incompleted slashing 
  is considered if the validator is slashed and withdrawable_epoch > epoch
  """

  assert ref_epoch >= 0, "Epoch should be >= 0"

  lido_validators = fetch_all_lido_validators_states_by_epoch(ref_epoch)
  lido_validators_slashed = filter_slashed_validators(lido_validators)
  lido_validators_slashed_non_withdrawable = filter_non_withdrawable_validators(lido_validators_slashed, ref_epoch)

  if len(lido_validators_slashed_non_withdrawable) == 0:
    # All slashings are complete
    return None

  validators_with_earliest_exit_epoch = get_validators_with_earliest_exit_epoch(lido_validators_slashed_non_withdrawable)

  """
  Get the earliest slashed_epoch for all incompleted slashings based on validators state 
  for reference slot. This works as long as the exit queue during the slashing is not comparable 
  to the EPOCHS_PER_SLASHINGS_VECTOR. For the same exit_epoch withdrawable_epoch must be the same, 
  so we can safely examine only one element of the array here.

  https://github.com/ethereum/consensus-specs/blob/dev/specs/phase0/beacon-chain.md#initiate_validator_exit
  https://github.com/ethereum/consensus-specs/blob/dev/specs/phase0/beacon-chain.md#slash_validator
  """
  first_validator_with_earliest_exit_epoch = validators_with_earliest_exit_epoch[0]
  earliest_slashed_epoch = calc_validator_slashed_epoch_from_state(first_validator_with_earliest_exit_epoch)

  if earliest_slashed_epoch is not None:
    return earliest_slashed_epoch

  assert ref_epoch != 0, "Should not be undetectable slashing at epoch 0"

  """
  The exit queue was too large at the moment of slashing and it's not possible to get slashed_epoch 
  from the state, so we go to search in the historical states
  """
  earliest_slashed_epoch = find_earliest_slashed_epoch(validators_with_earliest_exit_epoch, ref_epoch)
  return earliest_slashed_epoch


def get_validators_with_earliest_exit_epoch(validators):
  """
  Finds the earliest exit_epoch in the list of validators and returns all validators that match it
  """
  if len(validators) == 0:
    return []

  sorted_validators = sorted(validators, key = lambda validator: (validator["validator"]["exit_epoch"]))
  earliest_exit_epoch = sorted_validators[0]["validator"]["exit_epoch"]
  return filter_validators_by_exit_epoch(earliest_exit_epoch)


def calc_validator_slashed_epoch_from_state(validator):
  """
  Calculates slashed epoch based on current validator state
  Returns None in case it can't be calculated from the state
  """
  slashed = validator["validator"]["slashed"]
  exit_epoch = validator["validator"]["exit_epoch"]
  withdrawable_epoch = validator["validator"]["withdrawable_epoch"]

  assert slashed, "Validator is not slashed"
  assert exit_epoch != FAR_FUTURE_EPOCH, "Exit epoch is not valid"
  assert withdrawable_epoch != FAR_FUTURE_EPOCH, "Withdrawable epoch is not valid"

  exited_period = withdrawable_epoch - exit_epoch
  is_slashed_epoch_undetectable = exited_period > MIN_VALIDATOR_WITHDRAWABILITY_DELAY
  if is_slashed_epoch_undetectable:
    return None

  return withdrawable_epoch - EPOCHS_PER_SLASHINGS_VECTOR


def find_earliest_slashed_epoch(validators, ref_epoch):
  """
  Returns the earliest slashed epoch for the validator list, making historical queries 
  to the CL node and tracking slashed flag changes
  """
  pubkeys = get_validators_pubkeys(validators)
  withdrawable_epoch = min(get_validators_withdrawable_epochs(validators))

  # Search boundaries
  # it's possible to speed up the algorithm:
  # - start with the slot of the last finalized request
  # - iterate through checkpoints, so that the node doesn't waste time on state recovery
  # - replace with activation epoch
  start_search_epoch = 0
  end_search_epoch = min(ref_epoch, withdrawable_epoch - EPOCHS_PER_SLASHINGS_VECTOR)

  start_slot = get_epoch_first_slot(start_search_epoch)
  end_slot = get_epoch_last_slot(end_search_epoch)

  # Binary search
  while start_slot + 1 < end_slot:
    mid_slot = (end_slot + start_slot) // 2
    validators = fetch_validators_state_by_slot(pubkeys, mid_slot)
    slashed_validators = filter_slashed_validators(validators)

    if len(slashed_validators) > 0:
      # Ignore right half
      end_slot = mid_slot - 1
    else:
      # Ignore left half
      start_slot = mid_slot + 1

  return get_epoch_for_slot(end_slot)


def get_epoch_first_slot(epoch):
  return epoch * SLOTS_PER_EPOCH


def get_epoch_last_slot(epoch):
  return (epoch + 1) * SLOTS_PER_EPOCH - 1


def fetch_all_lido_validators_states_by_epoch(epoch):
  epoch_last_slot = get_epoch_last_slot(epoch)
  lido_validators_pubkeys = get_lido_validators_keys(epoch_last_slot)
  return fetch_validators_state_by_slot(lido_validators_pubkeys, epoch_last_slot)


def get_lido_validators_keys(slot):
  # Returns lido validators keys
  pass


def fetch_validators_state_by_slot(slot):
  # Fetches validators state for the slot
  # Jumps to the previous slot if a block in the slot is missed
  # TODO: can we proof that this state in the initial chain?
  pass


def filter_slashed_validators(validators):
  return list(filter(lambda validator: (validator["validator"]["slashed"]), validators)) 


def filter_non_withdrawable_validators(validators, epoch):
  return list(filter(lambda validator: (validator["validator"]["withdrawable_epoch"] > epoch), validators)) 


def filter_validators_by_exit_epoch(validators, exit_epoch):
  return list(filter(lambda validator: (validator["validator"]["exit_epoch"] == exit_epoch), validators)) 


def get_validators_pubkeys(validators):
  return list(map(lambda validator: (validator["validator"]["pubkey"]), validators))


def get_validators_withdrawable_epochs(validators):
  return list(map(lambda validator: (validator["validator"]["withdrawable_epoch"]), validators))
Last changed by 
 
lido
Lido Finance
0
965
Published on HackMD