More efficient accounts hash calculation for incremental snapshots.

[jeffwashington]

Problem

Calculating the full accounts hash today requires iterating every append vec in the system. We then get the lastest hash by pubkey and sort by pubkey. We then use a merkle tree to calculate an overall accounts hash.
The amount of data to scan and the # of accounts to sort and hash in a merkle tree increases as the # of accounts increase.
The purpose of the accounts hash is to verify the entire state of every account as of a certain slot.
The accounts hash is used when loading from a snapshot to verify that all data for all accounts matches what was expected when the snapshot was created.
The accounts hash can also be checked against gossip to verify ongoing state. An optional argument allows a validator to halt if its accounts hash mismatches other trusted validators.

Incremental snapshots are created at a much shorter interval than full snapshots. Incremental snapshots work by assuming the existence of a snapshot at the base slot. The incremental snapshot only contains the account data that has changed since the full snapshot. However, today the accounts hash used to verify the contents of the full snapshot + incremental snapshot on load is the full accounts hash. At some point, as # accounts grows, if incremental snapshots are stored every 100 slots (the current default), then the validator never stops calculating the full accounts hash in the background. This results in the system churning through ALL append vecs multiple times non-stop at all times. This is a massive waste of resources.

Proposed Solution

When we compute a full snapshot, we calculate a full accounts hash. The full snapshot contains all account data as of the snapshot slot. We calculate a hash and a capitalization. On load, we can compare the capitalization to the bank's capitalization and we can compare the accounts hash to an accounts hash that was serialized with the bank on snapshot creation.

For incremental snapshot creation, we can JUST calculate an accounts hash for the append vecs SINCE the last full snapshot.
Then, we can compare the full accounts hash and the incremental accounts hash against expected to verify that the full account state up to the incremental slot is correct.

An interesting difference is that incremental accounts hash must include all accounts which have zero lamports in the hash calculation. Today's hash calculation excludes accounts where the latest version has zero lamports.

Here's the reason:
slot 1: Account A created with 1 lamport
slot 100: full snapshot created
slot 101: Account A gets drained of its 1 lamport and becomes a zero lamport account.
slot 200: incremental snapshot created based off full snapshot at slot 100

If we do not include the zero lamport account hash at slot 101, then a validator could have account A having 1 lamport as of slot 200 and that would NOT match the correct state of the system, though the incremental hash WOULD match. This would result in a failure the next time we computed a full accounts hash or the next time account A was stored since lamports would mismatch versus a validator with the correct account A.

Another possibility is:
slot 100: full snapshot created
slot 101: Account A created with 1 lamport
slot 102: Account A gets drained of its 1 lamport and becomes a zero lamport account.
slot 200: incremental snapshot created based off full snapshot at slot 100

Note that the incremental snapshot at slot 200 will have an incremental accounts hash that WILL include account A with 0 lamports. This is not necessary conceptually, but it isn't incorrect. We currently have fences that prevent removing of 0 lamport accounts until full snapshots have been taken. These existing fences will cause all validators to keep account A present with 0 lamports until the next full snapshot. So ALL validators, regardless of their cleaning and shrinking proficiency and performance must have an entry for account A with 0 lamports as of slot 200.

So, the incremental accounts hash will include both necessary 0 lamport accounts and unnecessary 0 lamport accounts.
It is expensive to determine whether, for any 0 lamport account store, that the prior non-zero lamport version of the account was present in the prior full snapshot or not. It seems more efficient to just include all zero lamport accounts that are stored in the incremental snapshot intervals.

This change will also affect gossip accounts hash checking. The incremental hash calculation will ONLY contain account changes and summed up capitalization of slots for the incremental snapshot slots. This is a deterministic hash based on the last full snapshot slot and the incremental snapshot slot.
We can't compare incremental snapshot accounts hashes for the same slot if the base full snapshot is different.

This also has ramifications for loading from snapshot. We load today by getting all append vecs from a full snapshot, then getting all append vecs from the incremental snapshot. Then, we deserialize the incremental snapshot bank and calculate the accounts hash and capitalization of ALL append vecs as of the incremental slot.

The modified procedure will have to be:

1. get all append vecs of the full snapshot
2. calculate the capitalization and accounts hash of those append vecs like we do today
3. get all append vecs of the incremental snapshot
4. calculate the capitalization and accounts hash of JUST the append vecs AFTER the full snapshot slot
5. compare the full accounts hash and capitalization against saved versions in the bank
6. compare the incremental accounts hash and capitalization against the saved versions in the bank
7. run as normal

Notes:

1. neither the incremental cap nor the full cap will match the incremental snapshot's bank cap
2. neither the incremental hash nor the full hash will match what today we are serializing in the bank as an accounts hash
3. we can hash together the full hash and the incremental hash to get a single hash which we could consider the incremental hash. This gives us a single hash which we could put as part of the snapshot file name, for example.

This means we need to add fields to the bank persistence for:

1. expected accounts hash and capitalization as of the full snapshot slot
2. expected incremental accounts hash and incremental capitalization as of the incremental snapshot slot (again: this capitalization will NOT match the bank's capitalization at the incremental slot).

Here's why the cap won't match:
slot 1: account A starts with 100 lamports, account B starts with 1 lamport, account C starts with 1,000 lamports
slot 100: full snapshot, cap is 1,101 and matches bank
slot 101: account A gets the 1 lamport (becomes 101) from account B
slot 200: incremental snapshot, cap is calculated at 101. Bank cap is 1,101. 1,101 + 101 is not correct. It is not feasible to determine the delta lamports value for every account written in the incremental snapshot slot range compared to the last full snapshot slot. This requires lookups and state that we don't want to track.
The hash of an account includes its lamports. Thus, the overall hash of the full snapshot and the incremental snapshot together already include verifying the lamports of every account across both full and incremental snapshots.
We just have to accept that the incremental capitalization is not comparable to state the bank keeps.

[jeffwashington]

@brooksprumo @HaoranYi @sakridge

[jeffwashington]

This replaces: #26799

[brooksprumo]

Closing. This have been fixed by the Incremental Accounts Hash project.