Inclusion List Committee Selection in FOCIL

IL Committee Selection Desiderata

Committee members: Composed of a small size (e.g., 16 members per slot), with no duplicates within a slot or across the epoch
Secrecy: It will be nice that no one can calculate who the inclusion list committee members are until they broadcast their inclusion list. This helps mitigate DOS attacks.
Verifiability: It should be easy to verify that a particular validator was selected as part of the inclusion list committee. Additionally, it should be straightforward to pre-compute if a validator will be part of the inclusion committee for a given slot with some lookahead.
Simplicity: The design should prioritize simplicity for the beacon chain spec and client implementations. For example, a validator client should only need to retrieve the inclusion message, sign and return the signature.

We probably care less about optimizing selection based on the following properties:

Inclusion list message aggregation
Rewarding and penalty scheme for the inclusion list committee
Bias in selection outcomes based on a validator's effective balance

Potential Approaches

1: Beacon committee aproach

Select the inclusion list committee similarly to the beacon committee. Using the beacon state, epoch, and seed, we obtain the shuffled indices and divide them into slots. Subsets of these slot indices form the inclusion list committee.

def get_inclusion_list_committee(state: BeaconState, slot: Slot) -> Vector[ValidatorIndex, IL_COMMITTEE_SIZE]:
    epoch = compute_epoch_at_slot(slot)
    seed = get_seed(state, epoch, DOMAIN_IL_COMMITTEE)
    indices = get_active_validator_indices(state, epoch)
    start = (slot % SLOTS_PER_EPOCH) * IL_COMMITTEE_SIZE
    end = start + IL_COMMITTEE_SIZE
    return [indices[compute_shuffled_index(uint64(i), uint64(len(indices)), seed)] for i in range(start, end)]

Remarks:

Easy verifiability
Does not satisfy secrecy, as anyone can pre-compute who the IL committee members are
Simple to extend for reward and penalty schemes
Validator effective balance does not influence selection, meaning a consolidated validator has the same chance of being selected for the IL committee as a non-consolidated validator
Adds some complication for spec tests in edge case where IL committee size is greater than total validator / 32

Here’s an improved version for readability and clarity:

2: Sync committee approach

Select the inclusion list committee similarly to how the proposer and sync committees are sampled. Shuffled indices are processed one by one, with effective balance influencing the selection outcome.

def get_inclusion_list_committee(state: BeaconState) -> Sequence[ValidatorIndex]:
    epoch = Epoch(get_current_epoch(state) + 1)

    MAX_RANDOM_BYTE = 2**8 - 1
    active_validator_indices = get_active_validator_indices(state, epoch)
    active_validator_count = uint64(len(active_validator_indices))
    seed = get_seed(state, epoch, DOMAIN_IL_COMMITTEE)
    i = 0
    inclusion_list_committee_indices: List[ValidatorIndex] = []

    while len(inclusion_list_committee_indices) < IL_COMMITTEE_SIZE:
        shuffled_index = compute_shuffled_index(uint64(i % active_validator_count), active_validator_count, seed)
        candidate_index = active_validator_indices[shuffled_index]
        random_byte = hash(seed + uint_to_bytes(uint64(i // 32)))[i % 32]
        effective_balance = state.validators[candidate_index].effective_balance

        if effective_balance * MAX_RANDOM_BYTE >= MAX_EFFECTIVE_BALANCE * random_byte:
            inclusion_list_committee_indices.append(candidate_index)
        i += 1

    return inclusion_list_committee_indices

Remarks:

Provides easy verifiability but is computationally more expensive than (1)
There can be duplications across members in a committee
Does not satisfy secrecy, as IL committee members can still be pre-computed
Validator effective balance influences selection, giving higher balance validators a greater chance of being selected

3: Aggregator approach

Select the inclusion list committee similarly to how the aggregator in the beacon committee is selected. First, a validator computes a slot signature using the inclusion list selection proof domain:

def get_slot_signature(state: BeaconState, slot: Slot, privkey: int) -> BLSSignature:
    domain = get_domain(state, DOMAIN_IL_PROOF, compute_epoch_at_slot(slot))
    signing_root = compute_signing_root(slot, domain)
    return bls.Sign(privkey, signing_root)

Based on the slot signature, we determine whether the slot signature qualifies as part of the inclusion list committee. This reuses logic from the beacon committee:

def is_inclusion_list_member(state: BeaconState, slot: Slot, index: CommitteeIndex, slot_signature: BLSSignature) -> bool:
    committee = get_beacon_committee(state, slot, index)
    modulo = max(1, len(committee) // TARGET_INCLUSION_LIST_PER_COMMITTEE)
    return bytes_to_uint64(hash(slot_signature)[0:8]) % modulo == 0

Additionally, we add a selection proof to the inclusion list container and define another message to sign over it:

class InclusionListAndProof(Container):
    validator_index: ValidatorIndex
    message: InclusionList
    selection_proof: BLSSignature

Remarks:

Verification remains straightforward, but implementation complexity increases. Beacon node and validator client interactions require multiple round trips since the selection proof is part of the signed inclusion list, adding more verification steps.
Satisfies secrecy, as no validator can determine who else is in the inclusion list committee except for themselves.
Validator effective balance does not influence selection.

Closing thought

Final note, FOCIL currently implements (1) as it is the simplest approach and achieves most of the desired properties. However, if there is any critical property we are missing or a feature needed for future compatibility, we should identify it soon.