# Better Aggregation Inclusion - 1 Pager Design Author: Preston Van Loon, Terence Tsao Date: 2019/10/12 ## Objective In this design, we aim to achieve 100% attestation inclusion with BLS aggregation. ## Background Ethereum 2.0 signature scheme, BLS, does not allow for two aggregated signatures to be aggregated if any public key exists in both signatures. The specific use case in ETH2 is aggregation of beacon attestations. Examples as bitfields: ``` OK - Two single attestations can be aggregated. attestation_0: b00001000 attestation_1: b01000000 result: b01001000 OK - Two aggregated attestations with distinct bits (no overlap). attestation_0: b00011010 attestation_1: b01000001 result: b01011011 NOT OK - Two aggregated attestations with same signature in both. attestation_0: b00000101 attestation_1: b00000011 result: error! ``` ## Overview The problem above can be addressed in three initial steps. 1. Do not aggregate attestations with overlapping signatures. 2. Change the database schema for storing attestations such that multiple aggregated attestations may exist in the database for a given data root. 3. Update the attestation pool to track multiple aggregated attestations for a given attestation root; choose attestations where the aggregation bitfield contains bits which have not already been included in a block. A future step would be to choose the most profitable attestations in the scenario where there exists more than MAX_ATTESTATIONS eligible attestations in the attestation pool. This is a NP-hard problem and does not exist at the current scale of the test network so we will not address the entirety of that problem in this document. ## Detailed Design Reference objects from spec: ```python MAX_VALIDATORS_PER_COMMITTEE = 2**12 # 4,096 class Attestation(Container): aggregation_bits: Bitlist[MAX_VALIDATORS_PER_COMMITTEE] data: AttestationData custody_bits: Bitlist[MAX_VALIDATORS_PER_COMMITTEE] signature: BLSSignature class AttestationData(Container): # LMD GHOST vote beacon_block_root: Hash # FFG vote source: Checkpoint target: Checkpoint # Crosslink vote crosslink: Crosslink ``` ### 1 - Do not aggregate with overlap The solution here is to check that `aggregation_bits` bits have no overlap before attempting to aggregate the BLS signatures. If overlap exists, return a known error. On occurrence of said known error, treat both attestation as unique and eligible for processing / inclusion. Work in progress [PR 3747](https://github.com/prysmaticlabs/prysm/pull/3747). ### 2 - New attestation database schema The current schema looks as follows: ```go // Map key is SSZ hash of the attestation.Data type attestationDataHash [32]byte // Existing storage type. map[attestationDataHash]*pb.Attestation ``` This schema works until you receive an attestation with overlap for the same attestation root. The corrent implementation rejects the new attestation entirely and does not store it in the database. The obvious issue is that both attestations have unique bits that, if not included in a block, will affect justification. A new schema is proposed which will contain a map with the same key, but a container object for the map value type. ```go type attestationContainer struct { Data *pb.AttestationData SignaturePairs []struct{ AggregationBits bitfield.Bitlist Signature [48]byte // Aggregated signature } } // New storage type. map[attestationDataHash]attestationContainer ``` When fetching attestations from the database, the aggregated attestations can be reconstructed with the attestationContainer information. ```go var atts := make(*pb.Attestation, len(container.SignaturePairs)) for _, sp := range container.SignaturePairs { atts = append(atts, &pb.Attestation{ Data: container.Data, CustodyBits: EMPTY_BITLIST, // not used until phase 1. AggregationBits: sp.AggregationBits, Signature: sp.Signature, }) } return atts ``` **This design does not account for storage of custody bits as they are not used until phase 1.** When inserting attestations into the DB, we handle attestations that fully contain each other such that we do not add unnecessary attestations. Example bitfields in database: ``` b11000000, b00010000, b00001111 ``` If we attempt to insert an attestation with `b00001000`, we can simply ignore this insertion as that attestation is fully contained within `b00001111`. In the case that we receive an attestation that fully contains one or more attestations in the database, we would replace/remove those in favor of the new attestation. For example, if we received `b11111111` then we would remove all of the existing attestations in favor of the new one as it fully contains all others. ### 3 - Attestation pool updates The attestation pool is nearly identical to the database storage, except that these attestations are those kept in memory for quick access and maintained as attestations are included in blocks or become ineligible for inclusion. As such, we will use the same data structures with an additional map for tracking bits that have already been included. ```go type recentAttestationBits map[attestationDataHash]bitfield.Bitlist ``` With the attestation pool, we have two primary operations: insertion of newly seen attestations, removing included or expired attestations. #### Insertion of new attestations First, the new attestation must be checked that there exists one or more bits in the aggregation_bitfield which have not been included in a beacon block for that data root. Second, the attestation must check if it has any bits in the aggregation_bitlist for the data root which are not already in the pool. Likewise, it we must check if this new attestation completely overlaps an existing attestations in the pool. #### Removal of attestations from pool Upon successful processed block, remove the attestations from the pool which are fully contained within attestations in the block. Additionally, insert the aggregation_bits into the recently included aggregation bits tracking map. #### Pruning included aggregation bits tracking Attestations in the tracking map can be safely removed after those attestations are ineligible for inclusion. Relevant spec code ```python attestation_slot = get_attestation_data_slot(state, data) assert attestation_slot + MIN_ATTESTATION_INCLUSION_DELAY <= state.slot <= attestation_slot + SLOTS_PER_EPOCH ``` Given that the attestation data slot is the key indicator for eligibility, the recentAttestationBits must be a multimap or otherwise retain information about its data slot and, on block processing (the routine above in removal of attestations from pool), remove any attestation data slot which is older than one epoch as required from the spec. Note: get_attestation_data_slot is going away ([upstream PR #1428](https://github.com/ethereum/eth2.0-specs/pull/1428)) and will be replaced with attestation.Slot on the attestation itself. Until then, we will use the target epoch start slot as the attestation slot for cache referencing. We know that the attestation slot was definitely within the target epoch so it can be safe to use the start slot as reference. The side effect is that we may keep bitlists in memory for a bit longer than necessary but should be marginal impact. ### Runtime testing & rollout We can expect a more consistent flow of justification with these changes implemented correctly. A second step of validation would be to inspect the beacon chain database to ensure attestations with overlap are included in blocks as expected. These changes are considered to be a breaking change with regards to the database schema. As such, we will restart the test network which is already in a bad state after finalizing improper blocks due to a (probably) unrelated issue. Sanity check local testing should be conducted with a multiple node setup before merging and restarting the network.