Investigate new SlotHashes syscall

[buffalojoec]

Problem

SlotHashes is not available to BPF programs, but it's required by Address Lookup Table and Vote. These programs both need to lookup a slot and determine if it corresponds to a valid block-producing slot (hash), as well as evaluate that slot's position in the list of SlotHash entries.

Solution

Evaluate a new syscall for performing this lookup, without deserializing all of the data.

[buffalojoec]

Usage of SlotHashes in Address Lookup Table

[1] SlotHash::get(&self, slot: Slot)
Used to determine if a slot is a valid block-producing slot when deriving a lookup table address.

This can probably be replaced with position if we wanted to combine them into one syscall.

let derivation_slot = {
    let slot_hashes = invoke_context.get_sysvar_cache().get_slot_hashes()?;
    if slot_hashes.get(&untrusted_recent_slot).is_some() {
        Ok(untrusted_recent_slot)
    } else {
        ic_msg!(
            invoke_context,
            "{} is not a recent slot",
            untrusted_recent_slot
        );
        Err(InstructionError::InvalidInstructionData)
    }
}?;

[2] SlotHash::position(&self, slot: Slot)
Used to check the cooldown status of a deactivated lookup table.

Technically, this check only cares about whether or not the slot is in the SlotHashes sysvar. In other words: "have 512 (MAX_ENTRIES) passed since this lookup table was deactivated?". However,position allows the state function status to return the remaining_blocks, which is part of the program's state. It's not used elsewhere in the monorepo, but would break downstream compatibility.

/// Return the current status of the lookup table
pub fn status(&self, current_slot: Slot, slot_hashes: &SlotHashes) -> LookupTableStatus {
    if self.deactivation_slot == Slot::MAX {
        LookupTableStatus::Activated
    } else if self.deactivation_slot == current_slot {
        LookupTableStatus::Deactivating {
            remaining_blocks: MAX_ENTRIES.saturating_add(1),
        }
    } else if let Some(slot_hash_position) = slot_hashes.position(&self.deactivation_slot) {
        // Deactivation requires a cool-down period to give in-flight transactions
        // enough time to land and to remove indeterminism caused by transactions loading
        // addresses in the same slot when a table is closed. The cool-down period is
        // equivalent to the amount of time it takes for a slot to be removed from the
        // slot hash list.
        //
        // By using the slot hash to enforce the cool-down, there is a side effect
        // of not allowing lookup tables to be recreated at the same derived address
        // because tables must be created at an address derived from a recent slot.
        LookupTableStatus::Deactivating {
            remaining_blocks: MAX_ENTRIES.saturating_sub(slot_hash_position),
        }
    } else {
        LookupTableStatus::Deactivated
    }
}

[Conclusion]: Address Lookup Table requires:

• SlotHashes::position(&self, slot: Slot).

[buffalojoec]

Usage of SlotHashes in Vote

SlotHashes::slot_hashes(&self)
Vote directly asks for the whole slot hashes list. It makes a few standalone calls:

• slot_hashes.is_empty()
• slot_hashes.len()
• slot_hashes.last()

However, the functions check_update_vote_state_slots_are_valid and check_slots_are_valid actually use up the entire SlotHashes sysvar (as an upper bound). They both iterate over the whole list, starting at the bottom, and compare slots to vote slots.

It's worth noting that only one check of the actual hash is required in both functions. See the bottom section in the below snippet (pasted from check_slots_are_valid) under /* more conditional checks... */. The usage of a hash lookup in both functions is almost identical.

https://github.com/anza-xyz/agave/blob/8887cd19a1a86f61cfa44fb41a6e528e8857bc59/programs/vote/src/vote_state/mod.rs#L379-L392

https://github.com/anza-xyz/agave/blob/8887cd19a1a86f61cfa44fb41a6e528e8857bc59/programs/vote/src/vote_state/mod.rs#L491-L501

// index into the vote's slots, starting at the oldest
// slot
let mut i = 0;

// index into the slot_hashes, starting at the oldest known
// slot hash
let mut j = slot_hashes.len();

// Note:
//
// 1) `vote_slots` is sorted from oldest/smallest vote to newest/largest
// vote, due to the way votes are applied to the vote state (newest votes
// pushed to the back).
//
// 2) Conversely, `slot_hashes` is sorted from newest/largest vote to
// the oldest/smallest vote
while i < vote_slots.len() && j > 0 {
    // 1) increment `i` to find the smallest slot `s` in `vote_slots`
    // where `s` >= `last_voted_slot`
    if vote_state
        .last_voted_slot()
        .map_or(false, |last_voted_slot| vote_slots[i] <= last_voted_slot)
    {
        i = i
            .checked_add(1)
            .expect("`i` is bounded by `MAX_LOCKOUT_HISTORY` when finding larger slots");
        continue;
    }

    // 2) Find the hash for this slot `s`.
    if vote_slots[i] != slot_hashes[j.checked_sub(1).expect("`j` is positive")].0 {
        // Decrement `j` to find newer slots
        j = j
            .checked_sub(1)
            .expect("`j` is positive when finding newer slots");
        continue;
    }

    // 3) Once the hash for `s` is found, bump `s` to the next slot
    // in `vote_slots` and continue.
    i = i
        .checked_add(1)
        .expect("`i` is bounded by `MAX_LOCKOUT_HISTORY` when hash is found");
    j = j
        .checked_sub(1)
        .expect("`j` is positive when hash is found");
}

/ ** more conditional checks... **/

if &slot_hashes[j].1 != vote_hash {
    // This means the newest slot in the `vote_slots` has a match that
    // doesn't match the expected hash for that slot on this
    // fork
    warn!(
        "{} dropped vote slots {:?} failed to match hash {} {}",
        vote_state.node_pubkey, vote_slots, vote_hash, slot_hashes[j].1
    );
    inc_new_counter_info!("dropped-vote-hash", 1);
    return Err(VoteError::SlotHashMismatch);
}

Vote could maybe use a new syscall like SlotHashes::slots(&self) -> &[Slot], which would save 512 x 32 bytes on load, to iterate over slots and check against vote slots. Then, when the function(s) is ready to check the hash at the resulting j index, it could call another new syscall SlotHashes::lookup_slot_hash(&self, slot: &Slot) -> Option<Hash>.

[Conclusion]: Vote requires:

• SlotHashes::slots(&self) -> &[Slot] (new proposed function)
• SlotHashes::lookup_slot_hash(&self, slot: &Slot) -> Option<Hash> (new proposed function)

[buffalojoec]

If we decide to roll SlotHashes::lookup_slot_hash(&self, slot: &Slot) -> Option<Hash> for Vote, then Address Lookup Table could use this new syscall or SlotHashes::position(&self, slot: Slot) when validating derived lookup table addresses. It doesn't matter.

[buffalojoec]

Proof-of-Concept for SlotHashes::lookup_slot_hash(slot: &Slot) -> Option<Hash> syscall:
buffalojoec/solana#13

Proof-of-Concept for SlotHashes::lookup_slot_hash_position(slot: &Slot) -> Option<usize> syscall:
buffalojoec/solana#14