CBCification

[vbuterin]

This issue is intended as an illustration of the concrete spec changes that would be required to transition the beacon chain from its current FFG-based spec (see the mini-spec) to CBC (reading material here here here and here).

This is still a work in progress, though it is much more concrete than previous versions of this doc.

Fork choice rule changes

The fork choice rule changes from the current "favor the highest justified checkpoint then use LMD GHOST" to "use bitwise LMD GHOST", but using the balances at each epoch during each epoch.

A new helper:

def get_updated_bitfield(bitfield: bytes, position: int, bit: bool) -> bytes:
    bytepos, bitmask = position // 8, 2**(position % 8)
    if bit:
        return bitfield[:bytepos] + bytes([bitfield[bytepos] | bitmask]) + bitfield[bytepos+1:]
    else:
        return bitfield[:bytepos] + bytes([bitfield[bytepos] & (255 - bitmask)]) + bitfield[bytepos+1:]

Here is the new fork choice rule:

def lmd_ghost(store: Store, start_block: BeaconBlock) -> BeaconBlock:
    """
    Execute the LMD-GHOST algorithm to find the head ``BeaconBlock``.
    """
    head = start_block
    def get_vote_count(block: BeaconBlock) -> int:
        return sum(
            get_effective_balance(head_state.validator_balances[validator_index]) // FORK_CHOICE_BALANCE_INCREMENT
            for validator_index, target in attestation_targets
            if get_ancestor(store, target, block.slot) == block
        )

    while 1:
        head_state = get_post_state(head)
        children = get_children(store, head)
        if len(children) == 0:
            return head
        prefix_bit = 0
        while len(children) > 1:
            children_0 = [c for c in children if get_bitfield_bit(c, prefix_bit) == 0]
            children_1 = [c for c in children if get_bitfield_bit(c, prefix_bit) == 1]
            bit_0_votes = sum([get_vote_count(c) for c in children_0])
            bit_1_votes = sum([get_vote_count(c) for c in children_1])
            if bit_0_votes > bit_1_votes:
                children = children_0
            else:
                children = children_1
            prefix_bit += 1
        head = children[0]

But for CBC purposes, we need to have LMD GHOST not just be a suggestion, but rather an enforced rule; that is, a block is not valid unless its parent is the result of executing the LMD GHOST fork choice rule given all the evidence the block knows about. We need to keep track of some extra data to make it possible to verify this.

State changes

In the state, we make the following changes:

• Replace the validator_balances list with a validator_volatile_data list consisting of an object ValidatorVolatileData = {fractional_balance: uint32, last_agreement_height: uint32, last_agreement_bits: uint8, last_at_height: uint32}.
• Extend latest_block_roots to last one year (ie. ~2**22 entries).
• Add a list off_chain_block_hashes = List[HashRecord] where HashRecord = {"hash": "bytes32", "agreement_height": "uint32", "agreement_bits": "uint8"}.
• Add a list balance_agreeing_upto: List[List[int]], initialized as [[] for _ in range(LMD_GHOST_LOOKBACK)]
• Add a list balance_at: List[int], initialized as [0 for _ in range(LMD_GHOST_LOOKBACK)]
• To each ValidatorRecord, add: activation_init_epoch and exit_init_epoch (both initialized to FAR_FUTURE_EPOCH), and remove exit_initiated.

We add a new helper:

def get_agreeing_bits(hash1: bytes32, hash2: bytes32) -> int:
    i = 0
    while i < 256:
        if get_bitfield_bit(hash1, i) != get_bitfield_bit(hash2, i):
            return i
        i += 1
    return 256

We add a new method for submitting an off-chain block header:

def submit_offchain_block_header(header: Proposal, state: BeaconState):
    if header.parent_root in state.latest_block_roots:
        state.off_chain_block_hashes.append(HashRecord(
            hash=tree_hash_root(header),
            agreement_height=header.slot - 1,
            agreement_bits=get_agreeing_bits(get_block_root(parent_slot + 1),
                                             tree_hash_root(header))
        ))
    else:
        for rec in state.off_chain_block_hashes:
            if rec.hash == header.parent_root:
                state.off_chain_block_hashes.append(HashRecord(
                    hash=tree_hash_root(header),
                    agreement_height=rec.agreement_height
                    agreement_bits=rec.agreement_bits
                ))
                return
        raise Exception("Could not find parent")

off_chain_block_hashes are removed if their agreement height // 256 is < current slot - 2**22 (ie. after ~1 year).

We add three helpers:

def two_d_array_get(array, x, y):
    return array[x][y] if y < len(array[x]) else 0

def two_d_array_set(array, x, y, value):
    if value != 0 and y >= len(array[x]):
        array[x] += [0] * (y - len(array[x]) + 1)
    if y < len(array[x]):
        array[x] = y
    while len(array[x]) > 0 and array[x][-1] == 0:
        array[x].pop()

def adjust_deltas(state: BeaconState, agreement_balance_deltas: Dict[Int -> Int], at_balance_deltas: Dict[Int -> Int]):
    for (slot, bits), delta_balance in agreement_balance_deltas.items():
        existing_balance = two_d_array_get(state.balance_agreeing_upto,
                                           slot % LMD_GHOST_LOOKBACK,
                                           bits)
        two_d_array_set(state.balance_agreeing_upto,
                        slot % LMD_GHOST_LOOKBACK,
                        bits,
                        delta_balance + existing_balance)
    for slot, delta_balance in at_balance_deltas.items():
        state.balance_at[slot % LMD_GHOST_LOOKBACK] += delta_balance

Here is the function for processing a set of attestations:

def process_attestations(state: BeaconState, attestations: List[Attestation]):
    # Map of virtual agreement height -> balance delta (validators that will newly have that VAH
    # minus validators that will no longer have that VAH)
    agreement_balance_deltas = {}
    # Map of virtual at height -> balance delta (same logic)
    at_balance_deltas = {}
    # For each attestation...
    for attestation in attestations:
        verify_attestation(state, attestation)
        # For each participant in the attestation....
        for validator_index in get_attestation_participants(state, attestation.data, attestation.aggregation_bitfield):
            validator = state.validator_registry[validator_index]
            # Previous agreement height and implied at height
            previous_agreement_height = validator.last_agreement_height
            previous_agreement_bits = validator.last_agreement_bits
            previous_at_height = validator.last_at_height
            # New attestation is on this chain
            if attestation.data.beacon_block_root in state.latest_block_roots:
                next_agreement_height = next_at_height
                next_agreement_bits = 0
                next_at_height = attestation.data.slot * 256
            # New attestation is not on this chain
            else:
                found = False
                for rec in state.off_chain_block_hashes:
                    if attestation.data.beacon_block_root == rec.hash:
                        next_agreement_height = rec.virtual_agreement_height
                        next_agreement_bits = rec.virtual_agreement_bits
                        next_at_height = attestation.slot
                        found = True
                if not found:
                    raise Exception("Attestation on an unknown hash")
            # Adjust the validator data
            validator.last_agreement_height = next_agreement_height
            validator.last_agreement_bits = next_agreement_bits
            validator.last_at_height = next_at_height
            # Use rounded balance for fork choice rule (as it adjusts infrequently)
            balance = validator.rounded_balance
            # Adjust the delta maps
            prev_key = (previous_agreement_height, previous_agreement_bits)
            next_key = (next_agreement_height, next_agreement_bits)
            agreement_balance_deltas[prev_key] = agreement_balance_deltas.get(prev_key, 0) - balance
            agreement_balance_deltas[next_key] = agreement_balance_deltas.get(next_key, 0) + balance
            at_balance_deltas[previous_at_height] = at_balance_deltas.get(previous_at_height, 0) - balance
            at_balance_deltas[next_at_height] = at_balance_deltas.get(next_at_height, 0) + balance
    adjust_deltas(state, agreement_balance_deltas, at_balance_deltas)

Here is the function to call every slot for every validator whose rounded balance gets adjusted:

def process_balance_updates(state: BeaconState, prev_balances: List[int]):
    # New validator rounded balances
    new_balances = [v.rounded_balance for v in state.validator_registry]
    # Map of agreement/at height -> balance delta
    agreement_deltas = {}
    at_deltas = {}
    for i in range(len(prev_balances)):
        # If the rounded balance changed....
        if prev_balances[i] != new_balances[i]:
            # Agreement height and implied at height
            agreement_key = (validator.last_agreement_height, validator.last_agreement_bits)
            at_height = validator.last_at_height
            # Round balance delta
            balance_delta = new_balances[i] - prev_balances[i]
            # Adjust the delta maps
            agreement_deltas[agreement_key] = agreement_deltas.get(agreement_key, 0) + balance_delta
            at_deltas[at_height] = at_deltas.get(at_height, 0) + balance_delta
    adjust_deltas(state, agreement_deltas, at_deltas)

Here is the function to check if a block is valid under the CBC validity condition; this should be run after processing attestations:

def verify_cbc(state: BeaconState) -> bool:
    pivot = state.slot % LMD_GHOST_LOOKBACK
    balance_agreeing = state.balance_agreeing_upto[pivot:] + state.balance_agreeing_upto[:pivot]
    balance_at = state.balance_at[pivot:] + state.balance_at[:pivot]
    flattened_balance_agreeing = [
        two_d_array_get(balance_agreeing, i // 256, i % 256) for i in range(LMD_GHOST_LOOKBACK * 256)
    ]
    for i in range(LMD_GHOST_LOOKBACK * 256):
        balance_at_this_point = balance_at[i // 256] if i % 256 == 0 else 0
        assert (
            sum(flattened_balance_agreeing[i+1:]) >=
             (flattened_balance_agreeing[i] - balance_at_this_point) * (i / (LMD_GHOST_LOOKBACK * 256)) // 2
        )

For example, suppose LMD_GHOST_LOOKBACK = 4 and block.slot % LMD_GHOST_LOOKBACK = 1 and agreement_height = [[10, 20], [30, 80, 50], [], [40]], where instead of 256 bits every hash has three bits.

Then, agreement_height rotated would be [[30, 80, 50], [], [40], [10, 20], the flattened version is [30, 80, 50, 0, 0, 0, 40, 0, 0, 10, 20, 0] and the partial sums are [230, 200, 120, 70, 70, 70, 70, 30, 30, 30, 20, 0] - which may be invalid unless at least there are >= 10 votes at the same position as the 40.

Note that as a matter of efficient implementation, the sums need not be recalculated each time; nodes can maintain a sum tree locally (see description of sum trees in https://ethresear.ch/t/bitwise-lmd-ghost/4749) and use the binary search algorithm to verify correctness. One can compute a rotated sumtree from an unrotated sumtree in real time as follows: for a rotation by r of a list of length L, rotated_sum[i] = sum[i] - sum[r] if i <= r else sum[i] + sum[0] -sum[r]. One can also generally avoid storing most of the zeroes in high-order bits of each set of 256, and one can avoid a linear pass to verify compliance by doing a repeated binary search to find each position where the remaining sum drops below half of the previous remaining sum.

Slashing condition enforcement

We only need two slashing conditions, for these two cases:

• A validator signs two different blocks in the same epoch
• A validator signs a block with a slot number of C, in which their last_at_height is A, and they also sign a block with a slot number B, with A < B < C

For the first slashing condition, we can reuse code from the FFG beacon chain as is. For the second, we need to create a SlashingProof object which contains the parameters:

{
    index: uint64,
    data1: SlashableAttestationData,
    data2: SlashableAttestationData,
    merkle_branch_bottom: ValidatorVolatileData,
    merkle_branch_in_volatile_data_tree: [hash32],
    block_header_1: BlockHeader,
    block_header_2: BlockHeader,
}

See here for the definition of SlashableVoteData. Verifying this would entail verifying:

• Both SlashableVoteData objects pass a verify_slashable_vote_data check
• index is part of intersection(union(data1.custody_bit_0_indices, data1.custody_bit_1_indices), union(data2.custody_bit_0_indices, data2.custody_bit_1_indices))
• verify_merkle_branch(leaf=proof.merkle_branch_bottom, branch=proof.merkle_branch_in_volatile_data_tree, index=proof.index, root=proof.block_header_1.validator_volatile_data_root)`
• hash(block_header_1) == data1.data and hash(block_header_2) == data2.data
• block_header_1.slot // EPOCH_LENGTH > block_header_2.slot // EPOCH_LENGTH > merkle_branch_bottom.last_at_height // EPOCH_LENGTH

Note that this is almost but not quite sufficient. The reason is that an attacker could make a signature on the main chain at height H1, then sign on a fake off-chain block that only has a header at height H2, include that signature in the main chain and sign at height H3, then keep signing on the main chain, and then sign a message on another chain at a height between H2 and H3. The fact that the Merkle branch for height H2 is absent means that there is no way to catch and penalize the validator. We can solve this in two ways:

1. Add an additional challenge-response game where anyone can require any validator to publish the Merkle root for their own index for any signature that they participated in
2. Require clients to actually verify the off-chain blocks before they accept any chain that references them, and make this a validity rule for the chain

(1) could be extended into a general "proof of custody of beacon chain state" mechanism, which may also be useful for other reasons.

Changes to deposit/withdraw logic

We remove the exit queue and replace it with a (deposit+withdrawal) queue. That is, we set MAX_BALANCE_CHURN_QUOTIENT to equal LMD_GHOST_LOOKBACK, and instead of running through validators in order, we pre-sort the indices:

    # Sort validators by time they've been waiting for a transition
    def get_time_waiting(index):
        if state.validator_registry[index].activation_epoch == FAR_FUTURE_EPOCH:
            return get_current_epoch(state) - state.validator_registry[index].activation_init_epoch
        elif state.exit_epoch == FAR_FUTURE_EPOCH:
            return get_current_epoch(state) - state.validator_registry[index].exit_init_epoch
        else:
            return -1
    # Admit and exit validators within the allowable balance churn
    balance_churn = 0
    sorted_indices = sorted(list(range(len(state.validator_registry))), key=lambda index: -get_time_waiting(index))
    for index in sorted_indices:
        validator = state.validator_registry[index]
        if validator.activation_epoch == FAR_FUTURE_EPOCH and state.activation_init_epoch < FAR_FUTURE_EPOCH:
            # Check the balance churn would be within the allowance
            balance_churn += get_effective_balance(state, index)
            if balance_churn > max_balance_churn:
                break
            # Activate validator
            activate_validator(state, index, is_genesis=False)
        elif validator.activation_epoch == FAR_FUTURE_EPOCH and state.exit_init_epoch < FAR_FUTURE_EPOCH:
            # Check the balance churn would be within the allowance
            balance_churn += get_effective_balance(state, index)
            if balance_churn > max_balance_churn:
                break
            # Exit validator
            exit_validator(state, index)

Replace exit_initiated = True with exit_init_epoch = get_current_epoch(state).

Sections to remove

• The exit mechanism (instead, process_exit_queue simply runs prepare_validator_for_withdrawal on all validators that pass the eligible check)
• Justification
• Finalization

[nrryuya]

Thank you for writing this! This is a really beautiful proposal.
I'd like to ask a few questions.

(1) About LMD_GHOST_LOOKBACK, these are correct?

• Execute the fork-choice from the block at LMD_GHOST_LOOKBACK-th slot from the current slot
  • This basically corresponds to the weakly subjective checkpointing which is usual for chain-based PoS
  • Hence, LMD_GHOST_LOOKBACK is 2**22, which is equal to the lifespan of latest_block_roots and off_chain_block_hashes
• About validator rotation, allow exits up to 1/LMD_GHOST_LOOKBACK (in balance) for every slot
  • Therefore, it takes 1/LMD_GHOST_LOOKBACK slot at least for a validator set to change completely

(2) About bitwise LMD GHOST under validator rotation, what is the rationale of the (i / (LMD_GHOST_LOOKBACK * 256)) slacking (which seems to be modified from your previous proposal) and how it affects safety argument?
Also, how do you think the approach where exits are allowed only at every N block-heights and bitwise LMD GHOST is executed several times without slacking?

(3) About slashing,

Note that this is almost but not quite sufficient

I don't understand the problem here. The last_virtual_at_height of the attacker is H2 in the block which he attests to at H3 so we can create the slashing proof with the attestation at the slot between H2 and H3?

Also, In verify_cbc, I guess these are typos:

• two_d_array_get(agreement_balance_deltas -> two_d_array_get(balance_agreeing
• flattened_balance_agreeing[i] -> sum(flattened_balance_agreeing[i:])

Thank you in advance 🙏

[vbuterin]

This basically corresponds to the weakly subjective checkpointing which is usual for chain-based PoS

Yes.

Hence, LMD_GHOST_LOOKBACK is 2**22, which is equal to the lifespan of latest_block_roots and off_chain_block_hashes

Yes.

About validator rotation, allow exits up to 1/LMD_GHOST_LOOKBACK (in balance) for every slot . Therefore, it takes 1/LMD_GHOST_LOOKBACK slot at least for a validator set to change completely

I think you mean LMD_GHOST_LOOKBACK slots, not 1/LMD_GHOST_LOOKBACK slots. But yes.

(2) About bitwise LMD GHOST under validator rotation, what is the rationale of the (i / (LMD_GHOST_LOOKBACK * 256)) slacking (which seems to be modified from your previous proposal) and how it affects safety argument?

The rationale for having the slacking is the same as it was before: to account for the possibility that the ancestor of a block is actually valid even if it does not look valid from the point of view of the current validator set, because the validator set changed in the meantime. The // 256 is there to account for the fact that the data structure above uses 256 items per block height.

Also, how do you think the approach where exits are allowed only at every N block-heights and bitwise LMD GHOST is executed several times without slacking?

Definitely an interesting idea! Though the "several" would be big; eg. if N = 1 day (probably the best we can do for usability reasons) and LMD_GHOST_LOOKBACK = 8 months that's still ~240 times.

The last_virtual_at_height of the attacker is H2 in the block which he attests to at H3 so we can create the slashing proof with the attestation at the slot between H2 and H3?

The problem is that it's not guaranteed that the block at H2 is fully available. The body of that particular block could be missing, making the slashing unprovable, as the information of the last_virtual_at_height in the block would not be there to be put into the slashing proof.

two_d_array_get(agreement_balance_deltas -> two_d_array_get(balance_agreeing

Yep! Typo

flattened_balance_agreeing[i] -> sum(flattened_balance_agreeing[i:])

I think that actually does need to be [i]. The idea is that we are checking that the balance that forks off from the chain at exactly height i does not exceed the balance that stays in the chain at height i+1.

[nrryuya]

Thank you for replying!

I think you mean LMD_GHOST_LOOKBACK slots, not 1/LMD_GHOST_LOOKBACK slots. But yes.

Yeah, thanks.

The problem is that it's not guaranteed that the block at H2 is fully available. The body of that particular block could be missing, making the slashing unprovable, as the information of the last_virtual_at_height in the block would not be there to be put into the slashing proof.

Ah, so I assumed the second approach you described: a block is not valid at the moment unless the referenced ("justified") blocks are fully available. Is there any advantage to the challenge-response scheme?

In the first place, I'm also assuming that every block includes attestations for off-chain blocks or points to off-chain blocks themselves as CBC's "justification" so that receivers can verify validator_volatile_data_root. Is it correct?

I think that actually does need to be [i]. The idea is that we are checking that the balance that forks off from the chain at exactly height i does not exceed the balance that stays in the chain at height i+1.

Hmm, so I assumed that sum(flattened_balance_agreeing[i:]) is Agreeing[h], balance_at_this_pointisat[h] and i is h in your post so the validity condition Agreeing[h + 1] >= (Agreeing[h] - at[h]) * 1/2 is sum(flattened_balance_agreeing[h + 1:]) >= (sum(flattened_balance_agreeing[h:]) - balance_at_this_point) / 2 but it's not correct? (From process_attestations, balance_at[i] seems to be the weight of validators whose latest attestation is at i regardless of whether the validator is agreeing or not.)

Other minor corrections:

• In adjust_deltas, the names of variables agreement_delta_map and at_delta_map should be agreement_balance_deltas and at_balance_deltas respectively.
• Since ValidatorVolatileData only has last_at_height instead of last_virtual_at_height, the second slashing condition should be "A validator signs a block with a slot number of C, in which their last_at_height is A, and..."
• Also, the last validity condition of SlashingProof should be block_header_2.slot // EPOCH_LENGTH > merkle_branch_bottom.last_at_height // EPOCH_LENGTH (I'm not sure why there are // EPOCH_LENGTH)

[vbuterin]

Ah, so I assumed the second approach you described: a block is not valid at the moment unless the referenced ("justified") blocks are fully available. Is there any advantage to the challenge-response scheme?

The challenge response scheme approach allows us to keep the changes to purely within block validation rules, not changing the block acceptance rules at all. Not sure how valuable this is though.

In the first place, I'm also assuming that every block includes attestations for off-chain blocks or points to off-chain blocks themselves as CBC's "justification" so that receivers can verify validator_volatile_data_root

Even in the current ethereum, every block includes attestations for off-chain blocks.

Hmm, so I assumed that sum(flattened_balance_agreeing[i:]) is Agreeing[h], balance_at_this_pointisat[h] and i is h in your post so the validity condition Agreeing[h + 1] >= (Agreeing[h] - at[h]) * 1/2 is sum(flattened_balance_agreeing[h + 1:]) >= (sum(flattened_balance_agreeing[h:]) - balance_at_this_point) / 2 but it's not correct? (From process_attestations, balance_at[i] seems to be the weight of validators whose latest attestation is at i regardless of whether the validator is agreeing or not.)

flattened_balance_agreeing is derived from balance_agreeing_upto, which is an array that stores the total ETH of validators whose latest message forked off from the current chain at a given slot. Updating balance_agreeing_upto is done by process_attestations and adjust_deltas.

Another way to look at the problem is, suppose balance_at_this_point and the slack are both zero. Then, the desired goal is to check the total agreeing balance after the current point (ie. attestations that don't fork off at the current point) exceeds the balance that does fork off at the current point. Hence sum(flattened_balance_agreeing[i+1:]) >= flattened_balance_agreeing[i] in the case where those other two terms are zero.

[nrryuya]

@vbuterin
In the ETH2.0 spec, every block can only include attestations within 1 epoch.

Source: in process_attestation

assert attestation_slot + MIN_ATTESTATION_INCLUSION_DELAY <= state.slot <= attestation_slot + SLOTS_PER_EPOCH

Without modifying this, liveness will be lost in a case when some protocol-following validators end up in a situation where their previous attestations are not included in the main chain for 1 epoch (due to adaptive corruption on block proposer or temporal network failure) and hence they can not justify their previous attestations.

In the first place, the rationale of the limit of attestation inclusion is to set the upper bound of the cost of block verification, right?

[JustinDrake]

Closing this issue because the details are becoming increasingly stale—the discussion can continue on ethresear.ch or hackmd. CBCfication is still part of the 5-10 year roadmap likely after we've nailed the execution model in phase 2.