Optimise calculation of proposer indices

[michaelsproul]

Description

In v0.9 of the spec, proposer selection was changed so that it depends on a per slot shuffling of the active validators. This invalidates any attempt to use the existing committee cache to compute the proposer, but doesn't rule out doing something else clever.

The relevant functions in the spec are get_beacon_proposer_index and compute_proposer_index.

Present Behaviour

With #597, I've taken the simplest approach of recomputing the (ordered) active validators and their shuffling each time the beacon proposer for a slot is requested.

Proposed Behaviour

We could construct a cache of proposer indices at the start of each epoch. This would look like a Vec<u64> of length SLOTS_PER_EPOCH, that contains the Beacon proposer index for each slot of the epoch at vec index slot % SLOTS_PER_EPOCH.

We are able to compute this cache because the selection of proposers depends upon:

• The list of active validators, which is fixed for the duration of the epoch
• The seed, which we know a whole epoch in advance, and the slot number (which is predictable), i.e. we can easily calculate: hash(get_seed(state, epoch, DOMAIN_BEACON_PROPOSER) + int_to_bytes(slot, length=8)) for all slots in the epoch.
• The effective balances of the active validators, which are only updated in the process_final_updates function as part of an epoch transition, and are therefore stable for the entirety of the epoch. Unlike the committee cache which we can compute a full epoch in advance, the dependence on the effective balances (which change right up to the end of the previous epoch), prevents us from computing the proposer index cache until we transition into the current epoch.

[michaelsproul]

Blocked on merging of v0.9 into master: #597

[paulhauner]

Hey @michaelsproul is this still relevant?

[michaelsproul]

I'd concluded that it wasn't really worth doing, because the calculation of a single proposer index doesn't seem to take that long. But I will confirm this suspicion with a benchmark on 100k validators (I think last I looked was with 16k validators)

[michaelsproul]

I did some benchmarks

• 16k validators: get_beacon_proposer_index takes 0.26ms, compare:
  • block processing with signature verification: 183ms (0.14%)
  • block processing without sigs: 2.83ms (9.18%)
• 300k validators: get_beacon_proposer_index takes 3.26ms, compare:
  • block processing with signature verification: 186ms (1.75%)
  • block processing without sigs: 7.51ms (43.4%)

Noting that we currently do two proposer calculations per block processed, the calls to get_beacon_proposer_index potentially represent ~85% of no-sig block processing! Given that we use these sorts of block replays for states fetched from disk, cutting this time down could be a potentially fruitful area for further optimisation (but one I don't feel like pursuing right now).

(all benchmarks run using mainnet spec, average_block)

[paulhauner]

Noting that we currently do two proposer calculations per block processed, the calls to get_beacon_proposer_index potentially represent ~85% of no-sig block processing!

Great find! Good to know we have this up our sleeve!