# EIP-7549: optimal on chain aggregation
[toc]
This proposal extends the [EIP-7549](https://eips.ethereum.org/EIPS/eip-7549) by introducing an on chain aggregate optimisation enabled by the EIP.
This proposal comes with a notion of network and on chain aggregate. Although, both type of aggregates are represented by the same `Attestation` structure, their data complexity are different which is enforced by the additional gossipsub validation rule.
## Spec changes
The changes are based on the [consensus-specs#3559](https://github.com/ethereum/consensus-specs/pull/3559).
### Modified preset
| Name | Value |
|-|-|
| `MAX_ATTESTER_SLASHINGS` | 2**0 (= 1) |
| `MAX_ATTESTATIONS` | 2**3 (= 8) |
### Modified containers
```python=
class Attestation(Container):
aggregation_bits: List[Bitlist[MAX_VALIDATORS_PER_COMMITTEE], MAX_COMMITTEES_PER_SLOT] # [Modified in EIP7549]
data: AttestationData
committee_bits: Bitvector[MAX_COMMITTEES_PER_SLOT] # [New in EIP7549]
signature: BLSSignature
class IndexedAttestation(Container):
attesting_indices: List[ValidatorIndex, MAX_VALIDATORS_PER_COMMITTEE * MAX_COMMITTEES_PER_SLOT] # [Modified in EIP7549]
data: AttestationData
signature: BLSSignature
```
### New `get_committee_indices`
```python=
def get_committee_indices(commitee_bits: Bitvector) -> List[CommitteeIndex]:
return [CommitteeIndex(index) for bit, index in enumerate(commitee_bits) if bit]
```
### Modified `get_attesting_indices`
```python=
def get_attesting_indices(state: BeaconState, attestation: Attestation) -> Set[ValidatorIndex]:
"""
Return the set of attesting indices corresponding to ``aggregation_bits`` and ``committee_bits``.
"""
def get_committee_attesters(state: BeaconState, attesting_bits: Bitlist, index: CommitteeIndex) -> Set[ValidatorIndex]:
committee = get_beacon_committee(state, data.slot, index)
return set(index for i, index in enumerate(committee) if bits[i])
output = set()
committee_indices = get_committee_indices(attestation.committee_bits)
for index in committee_indices:
attesting_bits = attestation.attesting_bits[index]
committee_attesters = get_committee_attesters(state, attesting_bits, index)
output = output.union(committee_attesters)
return output
```
### Modified `process_attestation`
```python=
def process_attestation(state: BeaconState, attestation: Attestation) -> None:
data = attestation.data
index = get_attestation_index(attestation)
assert data.target.epoch in (get_previous_epoch(state), get_current_epoch(state))
assert data.target.epoch == compute_epoch_at_slot(data.slot)
assert data.slot + MIN_ATTESTATION_INCLUSION_DELAY <= state.slot
assert index < get_committee_count_per_slot(state, data.target.epoch)
# [Modified in EIP7549]
committee_indices = get_committee_indices(attestation.committee_bits)
assert len(committee_indices) > 0
assert len(committee_indices) == len(attestation.aggregation_bits)
for index in committee_indices:
assert index < get_committee_count_per_slot(state, data.target.epoch)
committee = get_beacon_committee(state, data.slot, index)
assert len(attestation.aggregation_bits[index]) == len(committee)
# Participation flag indices
participation_flag_indices = get_attestation_participation_flag_indices(state, data, state.slot - data.slot)
# Verify signature
assert is_valid_indexed_attestation(state, get_indexed_attestation(state, attestation))
# Update epoch participation flags
if data.target.epoch == get_current_epoch(state):
epoch_participation = state.current_epoch_participation
else:
epoch_participation = state.previous_epoch_participation
proposer_reward_numerator = 0
for index in get_attesting_indices(state, attestation):
for flag_index, weight in enumerate(PARTICIPATION_FLAG_WEIGHTS):
if flag_index in participation_flag_indices and not has_flag(epoch_participation[index], flag_index):
epoch_participation[index] = add_flag(epoch_participation[index], flag_index)
proposer_reward_numerator += get_base_reward(state, index) * weight
# Reward proposer
proposer_reward_denominator = (WEIGHT_DENOMINATOR - PROPOSER_WEIGHT) * WEIGHT_DENOMINATOR // PROPOSER_WEIGHT
proposer_reward = Gwei(proposer_reward_numerator // proposer_reward_denominator)
increase_balance(state, get_beacon_proposer_index(state), proposer_reward)
```
### Honest validator
#### Block proposal
Run the following function to construct an on chain aggregate form a list of network aggregates with equal `attestation.data`:
```python=
def compute_on_chain_aggregate(network_aggregates: List[Attestation]) -> Attestation:
aggregates = sorted(network_aggregates, key=lambda a: get_committee_indices(a)[0])
data = aggregates[0].data
aggregation_bits = [a.bits[0] for a in aggregates]
signature = bls.Aggregate([a.signature for a in aggregates])
committee_indices = [get_committee_indices(a)[0] for a in aggregates]
committee_flags = [(i in committee_indices) for i in range(0, MAX_COMMITTEES_PER_SLOT)]
committee_bits = Bitvector[MAX_COMMITTEES_PER_SLOT](committee_flags)
return Attestation(aggregation_bits=aggregation_bits,
data=data,
committee_bits=committee_bits,
signature=signature)
```
### `beacon_aggregate_and_proof` topic
The list of `beacon_aggregate_and_proof` validations is extended with the following:
* [REJECT] `len(committee_indices) == len(aggregate.attestation_bits) == 1`, where `committee_indices = get_committee_indices(aggregate)`.
## Complexity analysis
### Network aggregates
Data complexity of the network aggregtes does not increase as the new validity condition for the `beacon_aggregate_and_proof` gossipsub topic ensures that every network aggregate comprises a single committee.
### On chain aggregates
![image](https://hackmd.io/_uploads/HywxrsV2T.png)
The above plot shows potential optimisation effect of the proposed change. Namely, it is roughly 18KB to 4KB reduction in the size of a 64-committee aggregate for a 1 million validator set. Note that these numbers assumes perfect aggregation.
#### `MAX_ATTESTATIONS`
`MAX_ATTESTATIONS` parameter should be adjusted respectively to avoid increase of the block size.
![image](https://hackmd.io/_uploads/SkdjviEn6.png)
The above plot suggests `MAX_ATTESTATIONS = 8` as a reasonable limitation. Which means that assuming perfect aggregation the attestation capacity of the block increases from `128` committees to `8*64 = 512` committees, i.e. from `2` slots worth of attestations to `8`.
### Attester slashing
The plot below shows different variations of attester slashing data complexity. Numbers e.g. 64 vs 64 mean a number of committees which validator indices are respresented by the corresponding `IndexedAttestation` structure. For instance, today every on chain aggregate comprises a single committee thus the worst case attester slashing produced from on chain aggregates will have two indexed attestations with `1_000_000 / 32 / 64 = 488` validator indices each, which is roughly `8 KB` of uncompressed data. With the proposed change an attester slashing obtained in the same way could require `488 KB` of uncompressed data because it could contain indices from up to 64 committees instead of just 1.
![image](https://hackmd.io/_uploads/ryE7KjE3T.png)
Note that in the case of attack entailing mass slashing the overall complexity of attester slashing data with the proposed change remains the same as it is with the status quo. However, the proposed changed increases the size of the beacon block as each slashing will contain up to 64 times more indices than with the status quo. The positive outcome here is that all slashable attestations can be processed during roughly one epoch (EIP-7549 makes this already possible).
The red line on the plot represents the case when one of the indexed attestations is obtained from an on chain aggregate and the other one from a network aggregate. Moreover, with the proposed change it is still possible to create a slashing from two network aggregates. Therefore, complexity of attester slashing data in case of a single slashing event depends on the _slasher database schema, i.e. whether or not a slasher has access to network aggregates_.
`MAX_ATTESTER_SLASHINGS = 1` is suggested to alleviate the increase of the attester slashing complexity.
#### Compressed validator indices
Intuitively validator indices should compress well as there is just `20` bits of useful information per each validator index in the case of `1_000_000` validator set size. So `488 KB` of attester slashing data (the worst case) can be reduced to `153 KB` by employing a trivial compression algorithm.
_AttesterSlashing with 64x64 committees (1_000_000 validators) takes 320KB if compressed by Snappy (checked with PySpec SSZ test suite)._
### Imperfect aggregation
The proposed change reduces maximum number of aggregates per block from 128 to 8. This reduction can have adverse effects in the following cases:
1. There are network aggregates attesting to different fork choice views.
2. There are many network aggregates with overlapping indices.
Considering attesting committees shuffling, let's assume that validators of every attesting committee have roughly the same number of different views. With this assumption the proposed change is an improvement on the status quo as it can accommodate `8` different views vs `128 / 64 = 2` with the status quo.
In reality the distribution of a number of fork choice views can be more complicated. In the case of network asynchrony, a number of views per committee will highly depend on the network topology, i.e. how committee members are connected with each other and to members of other committees. Regardless of that, with the proposed change one block will be capable of accommodating `6` different aggregates more which should alleviate the complexity in the case of (1).
In the second case a proposer can opt in to include two on chain aggregates for the same slot, where the second aggregate will contain aggregates overlapping with the first one. The problem with that is every on chain aggregate can contain only one network aggregate from each committee. To overcome this limitation we can do the following changes:
```python=
class Attestation(Container):
aggregation_bits: List[Bitlist[MAX_VALIDATORS_PER_COMMITTEE], MAX_COMMITTEES_PER_SLOT] # [Modified in EIP7549]
data: AttestationData
committee_indexes: List[uint8, MAX_COMMITTEES_PER_SLOT] # [New in EIP7549]
signature: BLSSignature
def get_committee_indices(commitee_indices: List[uint8]) -> List[CommitteeIndex]:
return [CommitteeIndex(index) for index in committee_indices]
def get_attesting_indices_list(state: BeaconState, attestation: Attestation) -> Set[ValidatorIndex]:
"""
Return the set of attesting indices corresponding to ``aggregation_bits`` and ``committee_bits``.
"""
def get_committee_attesters(state: BeaconState, attesting_bits: Bitlist, index: CommitteeIndex) -> List[ValidatorIndex]:
committee = get_beacon_committee(state, data.slot, index)
return [index for i, index in enumerate(committee) if bits[i]]
output = []
committee_indices = get_committee_indices(attestation.committee_bits)
for index in committee_indices:
attesting_bits = attestation.attesting_bits[index]
committee_attesters = get_committee_attesters(state, attesting_bits, index)
output = output + committee_attesters
return output
def get_attesting_indices(state: BeaconState, attestation: Attestation) -> Set[ValidatorIndex]:
return set(get_attesting_indices_list(state, attestation))
def get_indexed_attestation(state: BeaconState, attestation: Attestation) -> IndexedAttestation:
"""
Return the indexed attestation corresponding to ``attestation``.
"""
attesting_indices = get_attesting_indices_list(state, attestation)
return IndexedAttestation(
attesting_indices=sorted(attesting_indices),
data=attestation.data,
signature=attestation.signature,
)
```
This change allows to pack overlapping network aggregates into a single on chain aggregate with high flexibility. Note that `List[uint8]` can be replaced with `List[CommitteeIndex]` if we assume that the latter is compressed to the size of the former.