Lighthouse: Implement a sensible block-operations pool

[paulhauner]

Overview

We need to implement a sustainable block-operations pool for storage of objects that may be included in blocks.

Details

The following v0.4.0 block operations (blops, lol) are covered in the scope of this issue:

• Attestation
• Deposit
• ProposerSlashing
• AttesterSlashing
• VoluntaryExit
• Transfer

For each of these items, we need to provide a pool/queue so they can potentially be included in a future block.

Detail

This section provides the following information for each of the blops:

• Insertion: defines conditions around what should be inserted into the pool.
• Reading: defines how the pool should return a list of items for inclusion in some block.
• Deletion: defines when items should be deleted from the pool.

_Note: a pool should not contain duplicate items._

Attestation

Easily the most complex case as it involves aggregating attestations and has the most complex validation logic.

Insertion

Shall accept an Attestation and aggregate it with an existing Attestation if possible (ask for more details).

The Attestation must be valid for

Reading

Shall provide a function to return Attestations for some (beacon_block, beacon_state) pair such that each attestation passes the block inclusion validity conditions.

If the number of attestations for a block exceed MAX_ATTESTATIONS, then attestations should be included to maximize the attestation inclusion rewards for the block proposer.

Deletion

Delete if:

• Let state be the latest state.
• attestation.data.slot < state.slot - spec.slots_per_epoch: such an Attestation is too old to be included in a block.

Deposit

Insertion

No validation conditions -- deposits are provided from our own Eth1 service so we assume all are valid.

Reading

Shall provide a function to return Deposits for some (beacon_block, beacon_state) pair which:

• Are sorted by deposit.index
• Pass the block inclusion validity conditions for that block/state.

Deletion

Shall remove Deposits from the pool if:

• Let state be the latest finalised state.
• state.deposit_index > deposit.index

ProposerSlashing & AttesterSlashing

_Both objects have the same conditions._

Insertion

Must pass the following requirements:

• Validator(s) implicated must be known in the latest state.validator_registry
• Slashing must be legit (see proposer slashing validity and attester slashing validity)

Reading

Shall provide a function to return Deposits for some (beacon_block, beacon_state) pair where:

• Implicated validators are not already slashed (validator.slashed == false)

Deletion

Shall remove slashings from the pool if the implicated validators are slashed or withdrawn in the latest finalized state.

VoluntaryExit

Insertion

Must pass the following conditions:

• validator_index is in the latest state.validator_registry.
• signature is valid.
• validator is not already exited.

Reading

Shall provide a function to return VoluntaryExits for some (beacon_block, beacon_state) pair such that the exit passes the block inclusion validity conditions.

Deletion

Shall delete Exits where the specified validator is exited in the latest finalized state.

Transfer

Insertion

Must pass the following conditions:

• transfer.slot is not in the past.
• from and to validators are known in the latest state.
• transfer.signature is valid.

Reading

Shall provide a function to return Transfers for some (beacon_block, beacon_state) pair such that the transfer passes the block inclusion validity conditions.

Deletion

Shall delete all Transfers where transfer.slot is in the past.

[paulhauner]

I'm thinking it might be sensible to leave Attestation out of scope now -- it's pretty significant. Apologies for the giant text.

[paulhauner]

Note: I just updated the deletion conditions for Attestation

[michaelsproul]

To clarify, we're talking about an in-memory-only pool for now, yeah?

[paulhauner]

To clarify, we're talking about an in-memory-only pool for now, yeah?

Yep!

[paulhauner]

I'm doing a refactor of the block/state processing logic for v0.4.0 and it's producing a lot of functions that will be useful for the inclusion validator conditions here.

Hopefully I can get a WIP PR up this afternoon -- I'll point out the useful functions to you :)

[paulhauner]

Hey, related to our conversation a few minutes ago -- here's my step-by-step of how I think attestation aggregation should work.

_Note: I'm not 100% sure this is accurate. Keep an eye out for edge cases or oversights on my behalf._

1. Get an Attestation (a) from the network.
2. Validate a.aggregate_signature against some BeaconState, discard if invalid.
3. Determine if an equivalent a.data exists in the pool (lets call it b) (see "Key-ing AttestationData")
   
   
   
   1. Determine if we can aggregate a with b (see "Can two attestations be aggregated")
   
   
4. If we can aggregate, aggregate a and b into ab (see "Aggregating two attestations").
   
   
   
   1. Ditch a.
   
   
   2. Remove b from the pool.
   
   
   3. Add ab to the pool.
   
   
5. If we _cant_ aggregate, store the a as is, adding b to the pool as well.

Can two attestations be aggregated

They can be aggregated if the following two conditions are satisfied:

• If a.data == b.data
• If the set of set bits on a.aggregation_bitfield and the set of bits on b.aggregration_bitfield are disjoint (a.k.a. don't aggregate two aggregate_signatures that both have the same signature on them).

Key-ing AttestationData

I assume you're going to build a HashMap of AttestationData -> Attestation so you can ask "do I have an attestation with the same attestation data?".

The naive way to do that would be to just Impl Hash for AttestationData and let HashMap deal with it. _However_, that does not have built in protection against forks. The same AttestationData on fork A would have the same key as the one on fork B.

As such, I would use this for keying Attestation (no guarantees this compiles, just for demonstration):

let epoch = attestation_data.slot.epoch(spec.slots_per_epoch);

let mut key: Vec<u8> = ssz_encode(&attestation_data);
key.append(&mut int_to_bytes8(spec.get_domain(epoch, Domain::Attestation, &state.fork)));

key  // `HashMap` can just hash this however it wants.

Aggregating two attestations

• ab.aggregate_signature = a.aggregate_signature.add_aggregate(b.aggregate_signature)*
• ab.custody_bitfield becomes the union of the custody_bitfields on a and b.
• ab.aggregation_bitfield becomes the union of the aggregation_bitfields on a and b.

*: AggregateSignature::aggregate_signature(..) is not yet implemented, however it is present on our underlying library. I'll implement it on the v0.5.0 branch and ping you when it's done.