Skip to content

Heze -- Inclusion List

Note: This document is a work-in-progress for researchers and implementers.

Introduction

These are the inclusion list specifications to implement Heze.

Containers

New containers

InclusionListStore

1
2
3
4
5
6
7
8
9
@dataclass
class InclusionListStore(object):
    inclusion_lists: DefaultDict[Tuple[Slot, Root], Dict[Root, InclusionList]] = field(
        default_factory=lambda: defaultdict(dict)
    )
    inclusion_list_timeliness: Dict[Root, boolean] = field(default_factory=dict)
    equivocators: DefaultDict[Tuple[Slot, Root], Set[ValidatorIndex]] = field(
        default_factory=lambda: defaultdict(set)
    )

Helpers

New get_inclusion_list_store

1
2
3
4
5
6
7
def get_inclusion_list_store() -> InclusionListStore:
    # `cached_or_new_inclusion_list_store` is implementation and context dependent.
    # It returns the cached `InclusionListStore`; if none exists,
    # it initializes a new instance, caches it and returns it.
    inclusion_list_store = cached_or_new_inclusion_list_store()

    return inclusion_list_store

New process_inclusion_list

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def process_inclusion_list(
    store: InclusionListStore,
    inclusion_list: InclusionList,
    is_timely: bool,
) -> None:
    key = (inclusion_list.slot, inclusion_list.inclusion_list_committee_root)

    # Ignore `inclusion_list` from equivocators.
    if inclusion_list.validator_index in store.equivocators[key]:
        return

    for stored_root in store.inclusion_lists[key]:
        stored_inclusion_list = store.inclusion_lists[key][stored_root]
        if stored_inclusion_list.validator_index != inclusion_list.validator_index:
            continue

        if stored_inclusion_list != inclusion_list:
            store.equivocators[key].add(inclusion_list.validator_index)

        # Whether it was an equivocation or not, we have processed this `inclusion_list`.
        return

    # Store `inclusion_list` and its timeliness.
    inclusion_list_root = hash_tree_root(inclusion_list)
    store.inclusion_lists[key][inclusion_list_root] = inclusion_list
    store.inclusion_list_timeliness[inclusion_list_root] = is_timely

New get_inclusion_list_transactions

Note: get_inclusion_list_transactions returns a list of unique transactions from all valid and non-equivocating InclusionLists for the given slot and for which the inclusion_list_committee_root in the InclusionList matches the one calculated based on the current state. When only_timely is True, only InclusionLists received in a timely manner on the p2p network are considered; otherwise, timeliness is not considered.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
def get_inclusion_list_transactions(
    store: InclusionListStore, state: BeaconState, slot: Slot, only_timely: bool = True
) -> Sequence[Transaction]:
    committee = get_inclusion_list_committee(state, slot)
    committee_root = hash_tree_root(committee)
    key = (slot, committee_root)

    inclusion_lists = store.inclusion_lists[key]
    equivocators = store.equivocators[key]
    timeliness = store.inclusion_list_timeliness

    transactions = [
        transaction
        for inclusion_list_root in inclusion_lists
        if inclusion_lists[inclusion_list_root].validator_index not in equivocators
        if not only_timely or timeliness[inclusion_list_root]
        for transaction in inclusion_lists[inclusion_list_root].transactions
    ]

    # Deduplicate inclusion list transactions. Order does not need to be preserved.
    return list(set(transactions))

New get_inclusion_list_bits

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def get_inclusion_list_bits(
    store: InclusionListStore, state: BeaconState, slot: Slot, only_timely: bool = True
) -> Bitvector[INCLUSION_LIST_COMMITTEE_SIZE]:
    """
    Return a ``Bitvector`` over inclusion list committee indices with bits set
    for valid and non-equivocating inclusion list submissions for the given ``slot``.
    """
    committee = get_inclusion_list_committee(state, slot)
    committee_root = hash_tree_root(committee)
    key = (slot, committee_root)

    inclusion_lists = store.inclusion_lists[key]
    equivocators = store.equivocators[key]
    timeliness = store.inclusion_list_timeliness

    validator_indices = [
        inclusion_lists[inclusion_list_root].validator_index
        for inclusion_list_root in inclusion_lists
        if inclusion_lists[inclusion_list_root].validator_index not in equivocators
        if not only_timely or timeliness[inclusion_list_root]
    ]

    return Bitvector[INCLUSION_LIST_COMMITTEE_SIZE](
        validator_index in validator_indices for validator_index in committee
    )

New is_inclusion_list_bits_inclusive

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
def is_inclusion_list_bits_inclusive(
    store: InclusionListStore,
    state: BeaconState,
    slot: Slot,
    inclusion_list_bits: Bitvector[INCLUSION_LIST_COMMITTEE_SIZE],
    only_timely: bool = True,
) -> bool:
    """
    Return ``True`` if and only if ``inclusion_list_bits`` is a superset of
    the locally observed inclusion list bits for the given ``slot``.
    """
    local_inclusion_list_bits = get_inclusion_list_bits(store, state, slot, only_timely)

    return all(
        inclusion_bit or not local_inclusion_bit
        for inclusion_bit, local_inclusion_bit in zip(
            inclusion_list_bits, local_inclusion_list_bits
        )
    )