Part 3: Annotated Specification

Beacon Chain State Transition Function

Preamble

State transitions

The state transition function is at the heart of what blockchains do. Each node on the network maintains a state that corresponds to its view of the state of the world.

Classically, the node's state is updated by applying blocks, in order, with a "state transition function". The state transition function is "pure" in that its output depends only on the input, and it has no side effects. This makes it deterministic: if every node starts with the same state (the Genesis state), and applies the same sequence of blocks, then all nodes must end up with the same resulting state. If for some reason they don't, then we have a consensus failure.

If SS is a beacon state, and BB a beacon block, then the state transition function ff can be written

Sf(S,B)S' \equiv f(S, B)

In this equation we call SS the pre-state (the state before applying the block BB), and SS' the post-state. The function ff is then iterated as we receive new blocks to constantly update the state.

That's the essence of blockchain progress in its purest form, as it existed under proof of work; under proof of work, the state transition function is driven exclusively by processing blocks.

The beacon chain, however, is not block-driven. Rather, it is slot-driven. Updates to the state depends on the progress of slots, whether or not that slot has a block associated with it.

Thus, the beacon chain's state transition function comprises three elements.

  1. A per-slot transition function, Sfs(S)S' \equiv f_s(S). (The state contains the slot number, so we do not need to supply it.)
  2. A per-block transition function Sfb(S,B)S' \equiv f_b(S, B).
  3. A per-epoch transition function Sfe(S)S' \equiv f_e(S).

Each of these state transition functions needs to be run at the appropriate point when updating the chain, and it is the role of this part of the beacon chain specification to define all of this precisely.

Validity conditions

The post-state corresponding to a pre-state state and a signed block signed_block is defined as state_transition(state, signed_block). State transitions that trigger an unhandled exception (e.g. a failed assert or an out-of-range list access) are considered invalid. State transitions that cause a uint64 overflow or underflow are also considered invalid.

This is a very important statement of how the spec deals with invalid conditions and errors. Basically, if any block is processed that would trigger any kind of exception in the Python code of the specification, then that block is invalid and must be rejected. That means having to undo any state modifications already made in the course of processing the block.

People who do formal verification of the specification don't much like this, as having assert statements in running code is an anti-pattern: it is better to ensure that your code can simply never fail.

Specification

Anyway, as discussed above, the beacon chain state transition has three elements:

  1. slot processing, which is performed for every slot regardless of what else is happening;
  2. epoch processing, which happens every SLOTS_PER_EPOCH (32) slots, again regardless of whatever else is going on; and,
  3. block processing, which happens only in slots for which a beacon block has been received.

def state_transition(state: BeaconState, signed_block: SignedBeaconBlock, validate_result: bool=True) -> None:
    block = signed_block.message
    # Process slots (including those with no blocks) since block
    process_slots(state, block.slot)
    # Verify signature
    if validate_result:
        assert verify_block_signature(state, signed_block)
    # Process block
    process_block(state, block)
    # Verify state root
    if validate_result:
        assert block.state_root == hash_tree_root(state)

Although the beacon chain's state transition is conceptually slot-driven, as the spec is written a state transition is triggered by receiving a block to process. That means that we first need to fast-forward from our current slot number in the state (which is the slot at which we last processed a block) to the slot of the block we are processing. We treat intervening slots, if any, as empty. This "fast-forward" is done by process_slots(), which also triggers epoch processing as required.

In actual client implementations, state updates will usually be time-based, triggered by moving to the next slot if a block has not been received. However, the fast-forward functionality will be used when exploring different forks in the block tree.

The validate_result parameter defaults to True, meaning that the block's signature will be checked, and that the result of applying the block to the state results in the same state root that the block claims it does (the "post-states" must match). When creating blocks, however, proposers can set validate_result to False in order to allow the state root to be calculated, else we'd have a circular dependency. The signature over the initial candidate block is omitted to avoid bad interactions with slashing protection when signing twice in a slot.

Uses process_slots(), verify_block_signature, process_block

def verify_block_signature(state: BeaconState, signed_block: SignedBeaconBlock) -> bool:
    proposer = state.validators[signed_block.message.proposer_index]
    signing_root = compute_signing_root(signed_block.message, get_domain(state, DOMAIN_BEACON_PROPOSER))
    return bls.Verify(proposer.pubkey, signing_root, signed_block.signature)

Check that the signature on the block matches the block's contents and the public key of the claimed proposer of the block. This ensures that blocks cannot be forged, or tampered with in transit. All the public keys for validators are stored in the Validators list in state.

Used by state_transition()
Uses compute_signing_root(), get_domain(), bls.Verify()
See also DOMAIN_BEACON_PROPOSER

def process_slots(state: BeaconState, slot: Slot) -> None:
    assert state.slot < slot
    while state.slot < slot:
        process_slot(state)
        # Process epoch on the start slot of the next epoch
        if (state.slot + 1) % SLOTS_PER_EPOCH == 0:
            process_epoch(state)
        state.slot = Slot(state.slot + 1)

Updates the state from its current slot up to the given slot number assuming that all the intermediate slots are empty (that they do not contain blocks). Iteratively calls process_slot() to apply the empty slot state-transition.

This is where epoch processing is triggered when required. Empty slot processing is lightweight, but any epoch transitions that need to be processed require the full rewards and penalties, and justification–finalisation apparatus.

Used by state_transition()
Uses process_slot(), process_epoch()
See also SLOTS_PER_EPOCH

def process_slot(state: BeaconState) -> None:
    # Cache state root
    previous_state_root = hash_tree_root(state)
    state.state_roots[state.slot % SLOTS_PER_HISTORICAL_ROOT] = previous_state_root
    # Cache latest block header state root
    if state.latest_block_header.state_root == Bytes32():
        state.latest_block_header.state_root = previous_state_root
    # Cache block root
    previous_block_root = hash_tree_root(state.latest_block_header)
    state.block_roots[state.slot % SLOTS_PER_HISTORICAL_ROOT] = previous_block_root

Apply a single slot state-transition (but updating the slot number, and any required epoch processing is handled by process_slots()). This is done at each slot whether or not there is a block present; if there is no block present then it is the only thing that is done.

Slot processing is almost trivial and consists only of calculating the updated state and block hash tree roots (as necessary), and storing them in the historical lists in the state. In a circular way, the state roots only change over an empty slot state transition due to updating the lists of state and block roots.

SLOTS_PER_HISTORICAL_ROOT is a multiple of SLOTS_PER_EPOCH, so there is no danger of overwriting the circular lists of state_roots and block_roots. These will be dealt with correctly during epoch processing.

The only curiosity here is the lines,

    if state.latest_block_header.state_root == Bytes32():
        state.latest_block_header.state_root = previous_state_root

This logic was introduced to avoid a circular dependency while also keeping the state transition clean. Each block that we receive contains a post-state root, but as part of state processing we store the block in the state (in state.latest_block_header), thus changing the post-state root.

Therefore, to be able to verify the state transition, we use the convention that the state root of the incoming block, and the state root that we calculate after inserting the block into the state, are both based on a temporary block header that has a stubbed state root, namely Bytes32(). This allows the block's claimed post-state root to validated without the circularity. The next time that process_slots() is called, the block's stubbed state root is updated to the actual post-state root, as above.

Used by process_slots()
Uses hash_tree_root
See also SLOTS_PER_HISTORICAL_ROOT

Created by Ben Edgington. Licensed under CC BY-SA 4.0. Published 2022-11-28 16:52 UTC. Commit 1179743.