kaspa_consensus/processes/
window.rs

1use crate::{
2    model::stores::{
3        block_window_cache::{BlockWindowCacheReader, BlockWindowHeap, WindowOrigin},
4        daa::DaaStoreReader,
5        ghostdag::{GhostdagData, GhostdagStoreReader},
6        headers::HeaderStoreReader,
7    },
8    processes::ghostdag::ordering::SortableBlock,
9};
10use kaspa_consensus_core::{
11    blockhash::BlockHashExtensions,
12    config::genesis::GenesisBlock,
13    errors::{block::RuleError, difficulty::DifficultyResult},
14    BlockHashSet, BlueWorkType,
15};
16use kaspa_hashes::Hash;
17use kaspa_math::Uint256;
18use kaspa_utils::refs::Refs;
19use once_cell::unsync::Lazy;
20use std::{cmp::Reverse, iter::once, ops::Deref, sync::Arc};
21
22use super::{
23    difficulty::{FullDifficultyManager, SampledDifficultyManager},
24    past_median_time::{FullPastMedianTimeManager, SampledPastMedianTimeManager},
25};
26
27#[derive(Clone, Copy)]
28pub enum WindowType {
29    SampledDifficultyWindow,
30    FullDifficultyWindow,
31    SampledMedianTimeWindow,
32    VaryingWindow(usize),
33}
34
35pub struct DaaWindow {
36    pub window: Arc<BlockWindowHeap>,
37    pub daa_score: u64,
38    pub mergeset_non_daa: BlockHashSet,
39}
40
41impl DaaWindow {
42    pub fn new(window: Arc<BlockWindowHeap>, daa_score: u64, mergeset_non_daa: BlockHashSet) -> Self {
43        Self { window, daa_score, mergeset_non_daa }
44    }
45}
46
47pub trait WindowManager {
48    fn block_window(&self, ghostdag_data: &GhostdagData, window_type: WindowType) -> Result<Arc<BlockWindowHeap>, RuleError>;
49    fn calc_daa_window(&self, ghostdag_data: &GhostdagData, window: Arc<BlockWindowHeap>) -> DaaWindow;
50    fn block_daa_window(&self, ghostdag_data: &GhostdagData) -> Result<DaaWindow, RuleError>;
51    fn calculate_difficulty_bits(&self, ghostdag_data: &GhostdagData, daa_window: &DaaWindow) -> u32;
52    fn calc_past_median_time(&self, ghostdag_data: &GhostdagData) -> Result<(u64, Arc<BlockWindowHeap>), RuleError>;
53    fn estimate_network_hashes_per_second(&self, window: Arc<BlockWindowHeap>) -> DifficultyResult<u64>;
54    fn window_size(&self, ghostdag_data: &GhostdagData, window_type: WindowType) -> usize;
55    fn sample_rate(&self, ghostdag_data: &GhostdagData, window_type: WindowType) -> u64;
56}
57
58/// A window manager conforming (indirectly) to the legacy golang implementation
59/// based on full, hence un-sampled, windows
60#[derive(Clone)]
61pub struct FullWindowManager<T: GhostdagStoreReader, U: BlockWindowCacheReader, V: HeaderStoreReader> {
62    genesis_hash: Hash,
63    ghostdag_store: Arc<T>,
64    block_window_cache_for_difficulty: Arc<U>,
65    block_window_cache_for_past_median_time: Arc<U>,
66    difficulty_window_size: usize,
67    past_median_time_window_size: usize,
68    difficulty_manager: FullDifficultyManager<V>,
69    past_median_time_manager: FullPastMedianTimeManager<V>,
70}
71
72impl<T: GhostdagStoreReader, U: BlockWindowCacheReader, V: HeaderStoreReader> FullWindowManager<T, U, V> {
73    pub fn new(
74        genesis: &GenesisBlock,
75        ghostdag_store: Arc<T>,
76        headers_store: Arc<V>,
77        block_window_cache_for_difficulty: Arc<U>,
78        block_window_cache_for_past_median_time: Arc<U>,
79        max_difficulty_target: Uint256,
80        target_time_per_block: u64,
81        difficulty_window_size: usize,
82        min_difficulty_window_len: usize,
83        past_median_time_window_size: usize,
84    ) -> Self {
85        let difficulty_manager = FullDifficultyManager::new(
86            headers_store.clone(),
87            genesis.bits,
88            max_difficulty_target,
89            difficulty_window_size,
90            min_difficulty_window_len,
91            target_time_per_block,
92        );
93        let past_median_time_manager = FullPastMedianTimeManager::new(headers_store, genesis.timestamp);
94        Self {
95            genesis_hash: genesis.hash,
96            ghostdag_store,
97            block_window_cache_for_difficulty,
98            block_window_cache_for_past_median_time,
99            difficulty_window_size,
100            past_median_time_window_size,
101            difficulty_manager,
102            past_median_time_manager,
103        }
104    }
105
106    fn build_block_window(&self, ghostdag_data: &GhostdagData, window_type: WindowType) -> Result<Arc<BlockWindowHeap>, RuleError> {
107        let window_size = self.window_size(ghostdag_data, window_type);
108        if window_size == 0 {
109            return Ok(Arc::new(BlockWindowHeap::new(WindowOrigin::Full)));
110        }
111
112        let cache = if window_size == self.difficulty_window_size {
113            Some(&self.block_window_cache_for_difficulty)
114        } else if window_size == self.past_median_time_window_size {
115            Some(&self.block_window_cache_for_past_median_time)
116        } else {
117            None
118        };
119
120        if let Some(cache) = cache {
121            if let Some(selected_parent_binary_heap) = cache.get(&ghostdag_data.selected_parent) {
122                // Only use the cached window if it originates from here
123                if let WindowOrigin::Full = selected_parent_binary_heap.origin() {
124                    let mut window_heap = BoundedSizeBlockHeap::from_binary_heap(window_size, (*selected_parent_binary_heap).clone());
125                    if ghostdag_data.selected_parent != self.genesis_hash {
126                        self.try_push_mergeset(
127                            &mut window_heap,
128                            ghostdag_data,
129                            self.ghostdag_store.get_blue_work(ghostdag_data.selected_parent).unwrap(),
130                        );
131                    }
132
133                    return Ok(Arc::new(window_heap.binary_heap));
134                }
135            }
136        }
137
138        let mut window_heap = BoundedSizeBlockHeap::new(WindowOrigin::Full, window_size);
139        let mut current_ghostdag: Refs<GhostdagData> = ghostdag_data.into();
140
141        // Walk down the chain until we cross the window boundaries
142        loop {
143            if current_ghostdag.selected_parent.is_origin() {
144                // Reaching origin means there's no more data, so we expect the window to already be full, otherwise we err.
145                // This error can happen only during an IBD from pruning proof when processing the first headers in the pruning point's
146                // future, and means that the syncer did not provide sufficient trusted information for proper validation
147                if window_heap.reached_size_bound() {
148                    break;
149                } else {
150                    return Err(RuleError::InsufficientDaaWindowSize(window_heap.binary_heap.len()));
151                }
152            }
153
154            if current_ghostdag.selected_parent == self.genesis_hash {
155                break;
156            }
157
158            let parent_ghostdag = self.ghostdag_store.get_data(current_ghostdag.selected_parent).unwrap();
159            let selected_parent_blue_work_too_low =
160                self.try_push_mergeset(&mut window_heap, &current_ghostdag, parent_ghostdag.blue_work);
161            // No need to further iterate since past of selected parent has even lower blue work
162            if selected_parent_blue_work_too_low {
163                break;
164            }
165            current_ghostdag = parent_ghostdag.into();
166        }
167
168        Ok(Arc::new(window_heap.binary_heap))
169    }
170
171    fn try_push_mergeset(
172        &self,
173        heap: &mut BoundedSizeBlockHeap,
174        ghostdag_data: &GhostdagData,
175        selected_parent_blue_work: BlueWorkType,
176    ) -> bool {
177        // If the window is full and the selected parent is less than the minimum then we break
178        // because this means that there cannot be any more blocks in the past with higher blue work
179        if !heap.try_push(ghostdag_data.selected_parent, selected_parent_blue_work) {
180            return true;
181        }
182        for block in ghostdag_data.descending_mergeset_without_selected_parent(self.ghostdag_store.deref()) {
183            // If it's smaller than minimum then we won't be able to add the rest because we iterate in descending blue work order.
184            if !heap.try_push(block.hash, block.blue_work) {
185                break;
186            }
187        }
188        false
189    }
190}
191
192impl<T: GhostdagStoreReader, U: BlockWindowCacheReader, V: HeaderStoreReader> WindowManager for FullWindowManager<T, U, V> {
193    fn block_window(&self, ghostdag_data: &GhostdagData, window_type: WindowType) -> Result<Arc<BlockWindowHeap>, RuleError> {
194        self.build_block_window(ghostdag_data, window_type)
195    }
196
197    fn calc_daa_window(&self, ghostdag_data: &GhostdagData, window: Arc<BlockWindowHeap>) -> DaaWindow {
198        let (daa_score, mergeset_non_daa) =
199            self.difficulty_manager.calc_daa_score_and_mergeset_non_daa_blocks(&window, ghostdag_data, self.ghostdag_store.deref());
200        DaaWindow::new(window, daa_score, mergeset_non_daa)
201    }
202
203    fn block_daa_window(&self, ghostdag_data: &GhostdagData) -> Result<DaaWindow, RuleError> {
204        let window = self.block_window(ghostdag_data, WindowType::SampledDifficultyWindow)?;
205        Ok(self.calc_daa_window(ghostdag_data, window))
206    }
207
208    fn calculate_difficulty_bits(&self, _high_ghostdag_data: &GhostdagData, daa_window: &DaaWindow) -> u32 {
209        self.difficulty_manager.calculate_difficulty_bits(&daa_window.window)
210    }
211
212    fn calc_past_median_time(&self, ghostdag_data: &GhostdagData) -> Result<(u64, Arc<BlockWindowHeap>), RuleError> {
213        let window = self.block_window(ghostdag_data, WindowType::SampledMedianTimeWindow)?;
214        let past_median_time = self.past_median_time_manager.calc_past_median_time(&window)?;
215        Ok((past_median_time, window))
216    }
217
218    fn estimate_network_hashes_per_second(&self, window: Arc<BlockWindowHeap>) -> DifficultyResult<u64> {
219        self.difficulty_manager.estimate_network_hashes_per_second(&window)
220    }
221
222    fn window_size(&self, _ghostdag_data: &GhostdagData, window_type: WindowType) -> usize {
223        match window_type {
224            WindowType::SampledDifficultyWindow | WindowType::FullDifficultyWindow => self.difficulty_window_size,
225            WindowType::SampledMedianTimeWindow => self.past_median_time_window_size,
226            WindowType::VaryingWindow(size) => size,
227        }
228    }
229
230    fn sample_rate(&self, _ghostdag_data: &GhostdagData, _window_type: WindowType) -> u64 {
231        1
232    }
233}
234
235type DaaStatus = Option<(u64, BlockHashSet)>;
236
237enum SampledBlock {
238    Sampled(SortableBlock),
239    NonDaa(Hash),
240}
241
242/// A sampled window manager implementing [KIP-0004](https://github.com/kaspanet/kips/blob/master/kip-0004.md)
243#[derive(Clone)]
244pub struct SampledWindowManager<T: GhostdagStoreReader, U: BlockWindowCacheReader, V: HeaderStoreReader, W: DaaStoreReader> {
245    genesis_hash: Hash,
246    ghostdag_store: Arc<T>,
247    headers_store: Arc<V>,
248    daa_store: Arc<W>,
249    block_window_cache_for_difficulty: Arc<U>,
250    block_window_cache_for_past_median_time: Arc<U>,
251    target_time_per_block: u64,
252    sampling_activation_daa_score: u64,
253    difficulty_window_size: usize,
254    difficulty_sample_rate: u64,
255    past_median_time_window_size: usize,
256    past_median_time_sample_rate: u64,
257    difficulty_manager: SampledDifficultyManager<V>,
258    past_median_time_manager: SampledPastMedianTimeManager<V>,
259}
260
261impl<T: GhostdagStoreReader, U: BlockWindowCacheReader, V: HeaderStoreReader, W: DaaStoreReader> SampledWindowManager<T, U, V, W> {
262    #[allow(clippy::too_many_arguments)]
263    pub fn new(
264        genesis: &GenesisBlock,
265        ghostdag_store: Arc<T>,
266        headers_store: Arc<V>,
267        daa_store: Arc<W>,
268        block_window_cache_for_difficulty: Arc<U>,
269        block_window_cache_for_past_median_time: Arc<U>,
270        max_difficulty_target: Uint256,
271        target_time_per_block: u64,
272        sampling_activation_daa_score: u64,
273        difficulty_window_size: usize,
274        min_difficulty_window_len: usize,
275        difficulty_sample_rate: u64,
276        past_median_time_window_size: usize,
277        past_median_time_sample_rate: u64,
278    ) -> Self {
279        let difficulty_manager = SampledDifficultyManager::new(
280            headers_store.clone(),
281            genesis.bits,
282            max_difficulty_target,
283            difficulty_window_size,
284            min_difficulty_window_len,
285            difficulty_sample_rate,
286            target_time_per_block,
287        );
288        let past_median_time_manager = SampledPastMedianTimeManager::new(headers_store.clone(), genesis.timestamp);
289        Self {
290            genesis_hash: genesis.hash,
291            ghostdag_store,
292            headers_store,
293            daa_store,
294            block_window_cache_for_difficulty,
295            block_window_cache_for_past_median_time,
296            target_time_per_block,
297            sampling_activation_daa_score,
298            difficulty_window_size,
299            difficulty_sample_rate,
300            past_median_time_window_size,
301            past_median_time_sample_rate,
302            difficulty_manager,
303            past_median_time_manager,
304        }
305    }
306
307    fn build_block_window(
308        &self,
309        ghostdag_data: &GhostdagData,
310        window_type: WindowType,
311        mut mergeset_non_daa_inserter: impl FnMut(Hash),
312    ) -> Result<Arc<BlockWindowHeap>, RuleError> {
313        let window_size = self.window_size(ghostdag_data, window_type);
314        let sample_rate = self.sample_rate(ghostdag_data, window_type);
315
316        // First, we handle all edge cases
317        if window_size == 0 {
318            return Ok(Arc::new(BlockWindowHeap::new(WindowOrigin::Sampled)));
319        }
320        if ghostdag_data.selected_parent == self.genesis_hash {
321            // Special case: Genesis does not enter the DAA window due to having a fixed timestamp
322            mergeset_non_daa_inserter(self.genesis_hash);
323            return Ok(Arc::new(BlockWindowHeap::new(WindowOrigin::Sampled)));
324        }
325        if ghostdag_data.selected_parent.is_origin() {
326            return Err(RuleError::InsufficientDaaWindowSize(0));
327        }
328
329        let cache = match window_type {
330            WindowType::SampledDifficultyWindow => Some(&self.block_window_cache_for_difficulty),
331            WindowType::SampledMedianTimeWindow => Some(&self.block_window_cache_for_past_median_time),
332            WindowType::FullDifficultyWindow | WindowType::VaryingWindow(_) => None,
333        };
334
335        if let Some(cache) = cache {
336            if let Some(selected_parent_binary_heap) = cache.get(&ghostdag_data.selected_parent) {
337                // Only use the cached window if it originates from here
338                if let WindowOrigin::Sampled = selected_parent_binary_heap.origin() {
339                    let selected_parent_blue_work = self.ghostdag_store.get_blue_work(ghostdag_data.selected_parent).unwrap();
340
341                    let mut heap =
342                        Lazy::new(|| BoundedSizeBlockHeap::from_binary_heap(window_size, (*selected_parent_binary_heap).clone()));
343                    for block in self.sampled_mergeset_iterator(sample_rate, ghostdag_data, selected_parent_blue_work) {
344                        match block {
345                            SampledBlock::Sampled(block) => {
346                                heap.try_push(block.hash, block.blue_work);
347                            }
348                            SampledBlock::NonDaa(hash) => {
349                                mergeset_non_daa_inserter(hash);
350                            }
351                        }
352                    }
353
354                    return if let Ok(heap) = Lazy::into_value(heap) {
355                        Ok(Arc::new(heap.binary_heap))
356                    } else {
357                        Ok(selected_parent_binary_heap.clone())
358                    };
359                }
360            }
361        }
362
363        let mut window_heap = BoundedSizeBlockHeap::new(WindowOrigin::Sampled, window_size);
364        let parent_ghostdag = self.ghostdag_store.get_data(ghostdag_data.selected_parent).unwrap();
365
366        for block in self.sampled_mergeset_iterator(sample_rate, ghostdag_data, parent_ghostdag.blue_work) {
367            match block {
368                SampledBlock::Sampled(block) => {
369                    window_heap.try_push(block.hash, block.blue_work);
370                }
371                SampledBlock::NonDaa(hash) => {
372                    mergeset_non_daa_inserter(hash);
373                }
374            }
375        }
376
377        let mut current_ghostdag = parent_ghostdag;
378
379        // Walk down the chain until we cross the window boundaries
380        loop {
381            if current_ghostdag.selected_parent.is_origin() {
382                // Reaching origin means there's no more data, so we expect the window to already be full, otherwise we err.
383                // This error can happen only during an IBD from pruning proof when processing the first headers in the pruning point's
384                // future, and means that the syncer did not provide sufficient trusted information for proper validation
385                if window_heap.reached_size_bound() {
386                    break;
387                } else {
388                    return Err(RuleError::InsufficientDaaWindowSize(window_heap.binary_heap.len()));
389                }
390            }
391
392            if current_ghostdag.selected_parent == self.genesis_hash {
393                break;
394            }
395
396            let parent_ghostdag = self.ghostdag_store.get_data(current_ghostdag.selected_parent).unwrap();
397            let selected_parent_blue_work_too_low =
398                self.try_push_mergeset(&mut window_heap, sample_rate, &current_ghostdag, parent_ghostdag.blue_work);
399            // No need to further iterate since past of selected parent has even lower blue work
400            if selected_parent_blue_work_too_low {
401                break;
402            }
403
404            current_ghostdag = parent_ghostdag;
405        }
406
407        Ok(Arc::new(window_heap.binary_heap))
408    }
409
410    fn try_push_mergeset(
411        &self,
412        heap: &mut BoundedSizeBlockHeap,
413        sample_rate: u64,
414        ghostdag_data: &GhostdagData,
415        selected_parent_blue_work: BlueWorkType,
416    ) -> bool {
417        // If the window is full and the selected parent is less than the minimum then we break
418        // because this means that there cannot be any more blocks in the past with higher blue work
419        if !heap.can_push(ghostdag_data.selected_parent, selected_parent_blue_work) {
420            return true;
421        }
422
423        for block in self.sampled_mergeset_iterator(sample_rate, ghostdag_data, selected_parent_blue_work) {
424            match block {
425                SampledBlock::Sampled(block) => {
426                    if !heap.try_push(block.hash, block.blue_work) {
427                        break;
428                    }
429                }
430                SampledBlock::NonDaa(_) => {}
431            }
432        }
433        false
434    }
435
436    fn sampled_mergeset_iterator<'a>(
437        &'a self,
438        sample_rate: u64,
439        ghostdag_data: &'a GhostdagData,
440        selected_parent_blue_work: BlueWorkType,
441    ) -> impl Iterator<Item = SampledBlock> + 'a {
442        let selected_parent_block = SortableBlock::new(ghostdag_data.selected_parent, selected_parent_blue_work);
443        let selected_parent_daa_score = self.headers_store.get_daa_score(ghostdag_data.selected_parent).unwrap();
444        let blue_score_threshold = self.difficulty_manager.lowest_daa_blue_score(ghostdag_data);
445        let mut index: u64 = 0;
446
447        once(selected_parent_block)
448            .chain(ghostdag_data.descending_mergeset_without_selected_parent(self.ghostdag_store.deref()))
449            .filter_map(move |block| {
450                if self.ghostdag_store.get_blue_score(block.hash).unwrap() < blue_score_threshold {
451                    Some(SampledBlock::NonDaa(block.hash))
452                } else {
453                    index += 1;
454                    if (selected_parent_daa_score + index) % sample_rate == 0 {
455                        Some(SampledBlock::Sampled(block))
456                    } else {
457                        None
458                    }
459                }
460            })
461    }
462}
463
464impl<T: GhostdagStoreReader, U: BlockWindowCacheReader, V: HeaderStoreReader, W: DaaStoreReader> WindowManager
465    for SampledWindowManager<T, U, V, W>
466{
467    fn block_window(&self, ghostdag_data: &GhostdagData, window_type: WindowType) -> Result<Arc<BlockWindowHeap>, RuleError> {
468        self.build_block_window(ghostdag_data, window_type, |_| {})
469    }
470
471    fn calc_daa_window(&self, ghostdag_data: &GhostdagData, window: Arc<BlockWindowHeap>) -> DaaWindow {
472        let (daa_score, mergeset_non_daa) =
473            self.difficulty_manager.calc_daa_score_and_mergeset_non_daa_blocks(ghostdag_data, self.ghostdag_store.deref());
474        DaaWindow::new(window, daa_score, mergeset_non_daa)
475    }
476
477    fn block_daa_window(&self, ghostdag_data: &GhostdagData) -> Result<DaaWindow, RuleError> {
478        let mut mergeset_non_daa = BlockHashSet::default();
479        let window = self.build_block_window(ghostdag_data, WindowType::SampledDifficultyWindow, |hash| {
480            mergeset_non_daa.insert(hash);
481        })?;
482        let daa_score = self.difficulty_manager.calc_daa_score(ghostdag_data, &mergeset_non_daa);
483        Ok(DaaWindow::new(window, daa_score, mergeset_non_daa))
484    }
485
486    fn calculate_difficulty_bits(&self, _high_ghostdag_data: &GhostdagData, daa_window: &DaaWindow) -> u32 {
487        self.difficulty_manager.calculate_difficulty_bits(&daa_window.window)
488    }
489
490    fn calc_past_median_time(&self, ghostdag_data: &GhostdagData) -> Result<(u64, Arc<BlockWindowHeap>), RuleError> {
491        let window = self.block_window(ghostdag_data, WindowType::SampledMedianTimeWindow)?;
492        let past_median_time = self.past_median_time_manager.calc_past_median_time(&window)?;
493        Ok((past_median_time, window))
494    }
495
496    fn estimate_network_hashes_per_second(&self, window: Arc<BlockWindowHeap>) -> DifficultyResult<u64> {
497        self.difficulty_manager.estimate_network_hashes_per_second(&window)
498    }
499
500    fn window_size(&self, _ghostdag_data: &GhostdagData, window_type: WindowType) -> usize {
501        match window_type {
502            WindowType::SampledDifficultyWindow => self.difficulty_window_size,
503            // We aim to return a full window such that it contains what would be the sampled window. Note that the
504            // product below addresses also the worst-case scenario where the last sampled block is exactly `sample_rate`
505            // blocks from the end of the full window
506            WindowType::FullDifficultyWindow => self.difficulty_window_size * self.difficulty_sample_rate as usize,
507            WindowType::SampledMedianTimeWindow => self.past_median_time_window_size,
508            WindowType::VaryingWindow(size) => size,
509        }
510    }
511
512    fn sample_rate(&self, _ghostdag_data: &GhostdagData, window_type: WindowType) -> u64 {
513        match window_type {
514            WindowType::SampledDifficultyWindow => self.difficulty_sample_rate,
515            WindowType::SampledMedianTimeWindow => self.past_median_time_sample_rate,
516            WindowType::FullDifficultyWindow | WindowType::VaryingWindow(_) => 1,
517        }
518    }
519}
520
521/// A window manager handling either full (un-sampled) or sampled windows depending on an activation DAA score
522///
523/// See [FullWindowManager] and [SampledWindowManager]
524#[derive(Clone)]
525pub struct DualWindowManager<T: GhostdagStoreReader, U: BlockWindowCacheReader, V: HeaderStoreReader, W: DaaStoreReader> {
526    ghostdag_store: Arc<T>,
527    headers_store: Arc<V>,
528    sampling_activation_daa_score: u64,
529    full_window_manager: FullWindowManager<T, U, V>,
530    sampled_window_manager: SampledWindowManager<T, U, V, W>,
531}
532
533impl<T: GhostdagStoreReader, U: BlockWindowCacheReader, V: HeaderStoreReader, W: DaaStoreReader> DualWindowManager<T, U, V, W> {
534    #[allow(clippy::too_many_arguments)]
535    pub fn new(
536        genesis: &GenesisBlock,
537        ghostdag_store: Arc<T>,
538        headers_store: Arc<V>,
539        daa_store: Arc<W>,
540        block_window_cache_for_difficulty: Arc<U>,
541        block_window_cache_for_past_median_time: Arc<U>,
542        max_difficulty_target: Uint256,
543        target_time_per_block: u64,
544        sampling_activation_daa_score: u64,
545        full_difficulty_window_size: usize,
546        sampled_difficulty_window_size: usize,
547        min_difficulty_window_len: usize,
548        difficulty_sample_rate: u64,
549        full_past_median_time_window_size: usize,
550        sampled_past_median_time_window_size: usize,
551        past_median_time_sample_rate: u64,
552    ) -> Self {
553        let full_window_manager = FullWindowManager::new(
554            genesis,
555            ghostdag_store.clone(),
556            headers_store.clone(),
557            block_window_cache_for_difficulty.clone(),
558            block_window_cache_for_past_median_time.clone(),
559            max_difficulty_target,
560            target_time_per_block,
561            full_difficulty_window_size,
562            min_difficulty_window_len.min(full_difficulty_window_size),
563            full_past_median_time_window_size,
564        );
565        let sampled_window_manager = SampledWindowManager::new(
566            genesis,
567            ghostdag_store.clone(),
568            headers_store.clone(),
569            daa_store,
570            block_window_cache_for_difficulty,
571            block_window_cache_for_past_median_time,
572            max_difficulty_target,
573            target_time_per_block,
574            sampling_activation_daa_score,
575            sampled_difficulty_window_size,
576            min_difficulty_window_len.min(sampled_difficulty_window_size),
577            difficulty_sample_rate,
578            sampled_past_median_time_window_size,
579            past_median_time_sample_rate,
580        );
581        Self { ghostdag_store, headers_store, sampled_window_manager, full_window_manager, sampling_activation_daa_score }
582    }
583
584    fn sampling(&self, ghostdag_data: &GhostdagData) -> bool {
585        let sp_daa_score = self.headers_store.get_daa_score(ghostdag_data.selected_parent).unwrap();
586        sp_daa_score >= self.sampling_activation_daa_score
587    }
588}
589
590impl<T: GhostdagStoreReader, U: BlockWindowCacheReader, V: HeaderStoreReader, W: DaaStoreReader> WindowManager
591    for DualWindowManager<T, U, V, W>
592{
593    fn block_window(&self, ghostdag_data: &GhostdagData, window_type: WindowType) -> Result<Arc<BlockWindowHeap>, RuleError> {
594        match self.sampling(ghostdag_data) {
595            true => self.sampled_window_manager.block_window(ghostdag_data, window_type),
596            false => self.full_window_manager.block_window(ghostdag_data, window_type),
597        }
598    }
599
600    fn calc_daa_window(&self, ghostdag_data: &GhostdagData, window: Arc<BlockWindowHeap>) -> DaaWindow {
601        match self.sampling(ghostdag_data) {
602            true => self.sampled_window_manager.calc_daa_window(ghostdag_data, window),
603            false => self.full_window_manager.calc_daa_window(ghostdag_data, window),
604        }
605    }
606
607    fn block_daa_window(&self, ghostdag_data: &GhostdagData) -> Result<DaaWindow, RuleError> {
608        match self.sampling(ghostdag_data) {
609            true => self.sampled_window_manager.block_daa_window(ghostdag_data),
610            false => self.full_window_manager.block_daa_window(ghostdag_data),
611        }
612    }
613
614    fn calculate_difficulty_bits(&self, ghostdag_data: &GhostdagData, daa_window: &DaaWindow) -> u32 {
615        match self.sampling(ghostdag_data) {
616            true => self.sampled_window_manager.calculate_difficulty_bits(ghostdag_data, daa_window),
617            false => self.full_window_manager.calculate_difficulty_bits(ghostdag_data, daa_window),
618        }
619    }
620
621    fn calc_past_median_time(&self, ghostdag_data: &GhostdagData) -> Result<(u64, Arc<BlockWindowHeap>), RuleError> {
622        match self.sampling(ghostdag_data) {
623            true => self.sampled_window_manager.calc_past_median_time(ghostdag_data),
624            false => self.full_window_manager.calc_past_median_time(ghostdag_data),
625        }
626    }
627
628    fn estimate_network_hashes_per_second(&self, window: Arc<BlockWindowHeap>) -> DifficultyResult<u64> {
629        self.sampled_window_manager.estimate_network_hashes_per_second(window)
630    }
631
632    fn window_size(&self, ghostdag_data: &GhostdagData, window_type: WindowType) -> usize {
633        match self.sampling(ghostdag_data) {
634            true => self.sampled_window_manager.window_size(ghostdag_data, window_type),
635            false => self.full_window_manager.window_size(ghostdag_data, window_type),
636        }
637    }
638
639    fn sample_rate(&self, ghostdag_data: &GhostdagData, window_type: WindowType) -> u64 {
640        match self.sampling(ghostdag_data) {
641            true => self.sampled_window_manager.sample_rate(ghostdag_data, window_type),
642            false => self.full_window_manager.sample_rate(ghostdag_data, window_type),
643        }
644    }
645}
646
647struct BoundedSizeBlockHeap {
648    binary_heap: BlockWindowHeap,
649    size_bound: usize,
650}
651
652impl BoundedSizeBlockHeap {
653    fn new(contents: WindowOrigin, size_bound: usize) -> Self {
654        Self::from_binary_heap(size_bound, BlockWindowHeap::with_capacity(contents, size_bound))
655    }
656
657    fn from_binary_heap(size_bound: usize, binary_heap: BlockWindowHeap) -> Self {
658        Self { size_bound, binary_heap }
659    }
660
661    fn reached_size_bound(&self) -> bool {
662        self.binary_heap.len() == self.size_bound
663    }
664
665    fn can_push(&self, hash: Hash, blue_work: BlueWorkType) -> bool {
666        let r_sortable_block = Reverse(SortableBlock { hash, blue_work });
667        if self.reached_size_bound() {
668            let max = self.binary_heap.peek().unwrap();
669            // Returns false if heap is full and the suggested block is greater than the max. Since the heap is reversed,
670            // pushing the suggested block would involve removing a block with a higher blue work.
671            return *max >= r_sortable_block;
672        }
673        true
674    }
675
676    fn try_push(&mut self, hash: Hash, blue_work: BlueWorkType) -> bool {
677        let r_sortable_block = Reverse(SortableBlock { hash, blue_work });
678        if self.reached_size_bound() {
679            if let Some(max) = self.binary_heap.peek() {
680                if *max < r_sortable_block {
681                    return false; // Heap is full and the suggested block is greater than the max
682                }
683            }
684            self.binary_heap.pop(); // Remove the max block (because it's reverse, it'll be the block with the least blue work)
685        }
686        self.binary_heap.push(r_sortable_block);
687        true
688    }
689}
kaspa_consensus/processes/window.rs

kaspa_consensus/processes/
window.rs
