Add accounts hash from prior epoch into a bank hash when we eliminate rewrites.

[jeffwashington]

Problem

We will stop doing rewrites of rent-exempt accounts during rent-collection in Bank::freeze.
Rewrites involve loading an account based on its pubkey range (rent collection range) and storing it as-is in the current slot. This has the effect of causing the previously written version of the account to become dead. Once dead, entire slots and appendvecs of dead accounts can be dropped/recycled.
A side effect of rewriting accounts is that each account is written at least once per epoch.
Every account that is written is included in a slot's bank hash.
Bank hash is used for consensus. Validators must vote on this.
Thus, every account was verified during each epoch by the consensus mechanism when we do rewrites.
If we get rid of rewrites, then an account will only be verified when it is written (bank hash in the slot it was last written will include the account's value) and then perhaps never again on chain.

Proposed Solution

The solution is to calculate a full accounts hash once per epoch. The resulting accounts hash can then be included in the bank hash of a slot 1 epoch later. This gives the validator an entire epoch of time to calculate the full accounts hash. This also causes all account data to be included in consensus once per epoch as before. So, any validator with any missing, corrupt, or extra accounts would identify this within 1-2 epochs.

Note that it is not feasible to calculate the full accounts hash of some arbitrary slot in the past. Allowing this would require the validator to keep too much old state available in its working set. The validator constantly works to clean up old state to enable efficiency and reduce resource consumption (memory, disk, i/o). This means that the full accounts hash calculation will have to occur somewhere close to when the end of the epoch occurs.

We could consider moving the hash calculation point to the epoch midpoint as opposed to the end of the epoch. The beginning of a new epoch can be a time of contention and stress. We could choose to calculate it based on the first root created >= 432,000/2 slots into the epoch, for example. We could include the resulting hash value at the first slot in the new epoch or the first slot >= 432,000/2 slots in the next epoch, giving us the full epoch to calculate it. It practically isn't helpful to allow the full accounts hash an entire epoch in which to calculate it. This would require the validator to keep around 2 epochs worth of state, which is inefficient. So, practically, the validator will want to begin calculating the required hash asap after the target slot becomes a root.

[brooksprumo]

Idea sounds good. Some things we'll likely figure out along the way:

• Setting the "start" and "stop" slots for the accounts hash computation; we may want to change these values in the future. Instead of a module-constant, functions on the bank would allow updating these values more easily (via feature gates).
• Should the "start" and "stop" slots be blocks instead? Can't guarantee how many blocks will be within one epoch. With slots, do we need to handle forks though? Need to ensure everyone's epoch accounts hash is computed from the same view of all the accounts.
• Where should this "epoch accounts hash" be stored? Probably in AccountsDb. If we have forks, may need a HashMap<Slot, EpochAccountsHash> data structure to ensure the "stop bank" can pick the epoch accounts hash from the correct starting bank.
  • Who should clear this data structure? If the "stop bank" is in charge, what happens when there's forking and we're stopping based on slots, not blocks? Maybe this data structure gets cleared when crossing the epoch. Should be trivially to clear a HashMap with only a few entries.

[brooksprumo]

Completed!