1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
use solana_sdk::{clock::Slot, commitment_config::CommitmentLevel};
use solana_vote_program::vote_state::MAX_LOCKOUT_HISTORY;
use std::collections::HashMap;

pub const VOTE_THRESHOLD_SIZE: f64 = 2f64 / 3f64;

pub type BlockCommitmentArray = [u64; MAX_LOCKOUT_HISTORY + 1];

#[derive(Clone, Debug, Default, Eq, PartialEq, Serialize, Deserialize)]
pub struct BlockCommitment {
    pub commitment: BlockCommitmentArray,
}

impl BlockCommitment {
    pub fn increase_confirmation_stake(&mut self, confirmation_count: usize, stake: u64) {
        assert!(confirmation_count > 0 && confirmation_count <= MAX_LOCKOUT_HISTORY);
        self.commitment[confirmation_count - 1] += stake;
    }

    pub fn get_confirmation_stake(&mut self, confirmation_count: usize) -> u64 {
        assert!(confirmation_count > 0 && confirmation_count <= MAX_LOCKOUT_HISTORY);
        self.commitment[confirmation_count - 1]
    }

    pub fn increase_rooted_stake(&mut self, stake: u64) {
        self.commitment[MAX_LOCKOUT_HISTORY] += stake;
    }

    pub fn get_rooted_stake(&self) -> u64 {
        self.commitment[MAX_LOCKOUT_HISTORY]
    }

    pub fn new(commitment: BlockCommitmentArray) -> Self {
        Self { commitment }
    }
}

/// A node's view of cluster commitment as per a particular bank
#[derive(Default)]
pub struct BlockCommitmentCache {
    /// Map of all commitment levels of current ancestor slots, aggregated from the vote account
    /// data in the bank
    block_commitment: HashMap<Slot, BlockCommitment>,
    /// Cache slot details. Cluster data is calculated from the block_commitment map, and cached in
    /// the struct to avoid the expense of recalculating on every call.
    commitment_slots: CommitmentSlots,
    /// Total stake active during the bank's epoch
    total_stake: u64,
}

impl std::fmt::Debug for BlockCommitmentCache {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("BlockCommitmentCache")
            .field("block_commitment", &self.block_commitment)
            .field("total_stake", &self.total_stake)
            .field(
                "bank",
                &format_args!("Bank({{current_slot: {:?}}})", self.commitment_slots.slot),
            )
            .field("root", &self.commitment_slots.root)
            .finish()
    }
}

impl BlockCommitmentCache {
    pub fn new(
        block_commitment: HashMap<Slot, BlockCommitment>,
        total_stake: u64,
        commitment_slots: CommitmentSlots,
    ) -> Self {
        Self {
            block_commitment,
            commitment_slots,
            total_stake,
        }
    }

    pub fn get_block_commitment(&self, slot: Slot) -> Option<&BlockCommitment> {
        self.block_commitment.get(&slot)
    }

    pub fn total_stake(&self) -> u64 {
        self.total_stake
    }

    pub fn slot(&self) -> Slot {
        self.commitment_slots.slot
    }

    pub fn root(&self) -> Slot {
        self.commitment_slots.root
    }

    pub fn highest_confirmed_slot(&self) -> Slot {
        self.commitment_slots.highest_confirmed_slot
    }

    pub fn highest_confirmed_root(&self) -> Slot {
        self.commitment_slots.highest_confirmed_root
    }

    pub fn commitment_slots(&self) -> CommitmentSlots {
        self.commitment_slots
    }

    pub fn highest_gossip_confirmed_slot(&self) -> Slot {
        // TODO: combine bank caches
        // Currently, this information is provided by OptimisticallyConfirmedBank::bank.slot()
        self.highest_confirmed_slot()
    }

    #[allow(deprecated)]
    pub fn slot_with_commitment(&self, commitment_level: CommitmentLevel) -> Slot {
        match commitment_level {
            CommitmentLevel::Recent | CommitmentLevel::Processed => self.slot(),
            CommitmentLevel::Root => self.root(),
            CommitmentLevel::Single => self.highest_confirmed_slot(),
            CommitmentLevel::SingleGossip | CommitmentLevel::Confirmed => {
                self.highest_gossip_confirmed_slot()
            }
            CommitmentLevel::Max | CommitmentLevel::Finalized => self.highest_confirmed_root(),
        }
    }

    fn highest_slot_with_confirmation_count(&self, confirmation_count: usize) -> Slot {
        assert!(confirmation_count > 0 && confirmation_count <= MAX_LOCKOUT_HISTORY);
        for slot in (self.root()..self.slot()).rev() {
            if let Some(count) = self.get_confirmation_count(slot) {
                if count >= confirmation_count {
                    return slot;
                }
            }
        }
        self.commitment_slots.root
    }

    pub fn calculate_highest_confirmed_slot(&self) -> Slot {
        self.highest_slot_with_confirmation_count(1)
    }

    pub fn get_confirmation_count(&self, slot: Slot) -> Option<usize> {
        self.get_lockout_count(slot, VOTE_THRESHOLD_SIZE)
    }

    // Returns the lowest level at which at least `minimum_stake_percentage` of the total epoch
    // stake is locked out
    fn get_lockout_count(&self, slot: Slot, minimum_stake_percentage: f64) -> Option<usize> {
        self.get_block_commitment(slot).map(|block_commitment| {
            let iterator = block_commitment.commitment.iter().enumerate().rev();
            let mut sum = 0;
            for (i, stake) in iterator {
                sum += stake;
                if (sum as f64 / self.total_stake as f64) > minimum_stake_percentage {
                    return i + 1;
                }
            }
            0
        })
    }

    pub fn new_for_tests() -> Self {
        let mut block_commitment: HashMap<Slot, BlockCommitment> = HashMap::new();
        block_commitment.insert(0, BlockCommitment::default());
        Self {
            block_commitment,
            total_stake: 42,
            ..Self::default()
        }
    }

    pub fn new_for_tests_with_slots(slot: Slot, root: Slot) -> Self {
        let mut block_commitment: HashMap<Slot, BlockCommitment> = HashMap::new();
        block_commitment.insert(0, BlockCommitment::default());
        Self {
            block_commitment,
            total_stake: 42,
            commitment_slots: CommitmentSlots {
                slot,
                root,
                highest_confirmed_slot: root,
                highest_confirmed_root: root,
            },
        }
    }

    pub fn set_highest_confirmed_slot(&mut self, slot: Slot) {
        self.commitment_slots.highest_confirmed_slot = slot;
    }

    pub fn set_highest_confirmed_root(&mut self, root: Slot) {
        self.commitment_slots.highest_confirmed_root = root;
    }

    pub fn initialize_slots(&mut self, slot: Slot) {
        self.commitment_slots.slot = slot;
        self.commitment_slots.root = slot;
    }

    pub fn set_all_slots(&mut self, slot: Slot, root: Slot) {
        self.commitment_slots.slot = slot;
        self.commitment_slots.highest_confirmed_slot = slot;
        self.commitment_slots.root = root;
        self.commitment_slots.highest_confirmed_root = root;
    }
}

#[derive(Default, Clone, Copy)]
pub struct CommitmentSlots {
    /// The slot of the bank from which all other slots were calculated.
    pub slot: Slot,
    /// The current node root
    pub root: Slot,
    /// Highest cluster-confirmed slot
    pub highest_confirmed_slot: Slot,
    /// Highest cluster-confirmed root
    pub highest_confirmed_root: Slot,
}

impl CommitmentSlots {
    pub fn new_from_slot(slot: Slot) -> Self {
        Self {
            slot,
            ..Self::default()
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_block_commitment() {
        let mut cache = BlockCommitment::default();
        assert_eq!(cache.get_confirmation_stake(1), 0);
        cache.increase_confirmation_stake(1, 10);
        assert_eq!(cache.get_confirmation_stake(1), 10);
        cache.increase_confirmation_stake(1, 20);
        assert_eq!(cache.get_confirmation_stake(1), 30);
    }

    #[test]
    fn test_get_confirmations() {
        // Build BlockCommitmentCache with votes at depths 0 and 1 for 2 slots
        let mut cache0 = BlockCommitment::default();
        cache0.increase_confirmation_stake(1, 5);
        cache0.increase_confirmation_stake(2, 40);

        let mut cache1 = BlockCommitment::default();
        cache1.increase_confirmation_stake(1, 40);
        cache1.increase_confirmation_stake(2, 5);

        let mut cache2 = BlockCommitment::default();
        cache2.increase_confirmation_stake(1, 20);
        cache2.increase_confirmation_stake(2, 5);

        let mut block_commitment = HashMap::new();
        block_commitment.entry(0).or_insert(cache0);
        block_commitment.entry(1).or_insert(cache1);
        block_commitment.entry(2).or_insert(cache2);
        let block_commitment_cache = BlockCommitmentCache {
            block_commitment,
            total_stake: 50,
            ..BlockCommitmentCache::default()
        };

        assert_eq!(block_commitment_cache.get_confirmation_count(0), Some(2));
        assert_eq!(block_commitment_cache.get_confirmation_count(1), Some(1));
        assert_eq!(block_commitment_cache.get_confirmation_count(2), Some(0),);
        assert_eq!(block_commitment_cache.get_confirmation_count(3), None,);
    }

    #[test]
    fn test_highest_confirmed_slot() {
        let bank_slot_5 = 5;
        let total_stake = 50;

        // Build cache with confirmation_count 2 given total_stake
        let mut cache0 = BlockCommitment::default();
        cache0.increase_confirmation_stake(1, 5);
        cache0.increase_confirmation_stake(2, 40);

        // Build cache with confirmation_count 1 given total_stake
        let mut cache1 = BlockCommitment::default();
        cache1.increase_confirmation_stake(1, 40);
        cache1.increase_confirmation_stake(2, 5);

        // Build cache with confirmation_count 0 given total_stake
        let mut cache2 = BlockCommitment::default();
        cache2.increase_confirmation_stake(1, 20);
        cache2.increase_confirmation_stake(2, 5);

        let mut block_commitment = HashMap::new();
        block_commitment.entry(1).or_insert_with(|| cache0.clone()); // Slot 1, conf 2
        block_commitment.entry(2).or_insert_with(|| cache1.clone()); // Slot 2, conf 1
        block_commitment.entry(3).or_insert_with(|| cache2.clone()); // Slot 3, conf 0
        let commitment_slots = CommitmentSlots::new_from_slot(bank_slot_5);
        let block_commitment_cache =
            BlockCommitmentCache::new(block_commitment, total_stake, commitment_slots);

        assert_eq!(block_commitment_cache.calculate_highest_confirmed_slot(), 2);

        // Build map with multiple slots at conf 1
        let mut block_commitment = HashMap::new();
        block_commitment.entry(1).or_insert_with(|| cache1.clone()); // Slot 1, conf 1
        block_commitment.entry(2).or_insert_with(|| cache1.clone()); // Slot 2, conf 1
        block_commitment.entry(3).or_insert_with(|| cache2.clone()); // Slot 3, conf 0
        let block_commitment_cache =
            BlockCommitmentCache::new(block_commitment, total_stake, commitment_slots);

        assert_eq!(block_commitment_cache.calculate_highest_confirmed_slot(), 2);

        // Build map with slot gaps
        let mut block_commitment = HashMap::new();
        block_commitment.entry(1).or_insert_with(|| cache1.clone()); // Slot 1, conf 1
        block_commitment.entry(3).or_insert(cache1); // Slot 3, conf 1
        block_commitment.entry(5).or_insert_with(|| cache2.clone()); // Slot 5, conf 0
        let block_commitment_cache =
            BlockCommitmentCache::new(block_commitment, total_stake, commitment_slots);

        assert_eq!(block_commitment_cache.calculate_highest_confirmed_slot(), 3);

        // Build map with no conf 1 slots, but one higher
        let mut block_commitment = HashMap::new();
        block_commitment.entry(1).or_insert(cache0); // Slot 1, conf 2
        block_commitment.entry(2).or_insert_with(|| cache2.clone()); // Slot 2, conf 0
        block_commitment.entry(3).or_insert_with(|| cache2.clone()); // Slot 3, conf 0
        let block_commitment_cache =
            BlockCommitmentCache::new(block_commitment, total_stake, commitment_slots);

        assert_eq!(block_commitment_cache.calculate_highest_confirmed_slot(), 1);

        // Build map with no conf 1 or higher slots
        let mut block_commitment = HashMap::new();
        block_commitment.entry(1).or_insert_with(|| cache2.clone()); // Slot 1, conf 0
        block_commitment.entry(2).or_insert_with(|| cache2.clone()); // Slot 2, conf 0
        block_commitment.entry(3).or_insert(cache2); // Slot 3, conf 0
        let block_commitment_cache =
            BlockCommitmentCache::new(block_commitment, total_stake, commitment_slots);

        assert_eq!(block_commitment_cache.calculate_highest_confirmed_slot(), 0);
    }
}