consensus_core/
test_dag_builder.rs

1// Copyright (c) Mysten Labs, Inc.
2// SPDX-License-Identifier: Apache-2.0
3
4use std::{
5    collections::{BTreeMap, HashSet},
6    ops::{Bound::Included, RangeInclusive},
7    sync::Arc,
8};
9
10use consensus_config::AuthorityIndex;
11use consensus_types::block::{BlockDigest, BlockRef, BlockTimestampMs, Round, TransactionIndex};
12use parking_lot::RwLock;
13use rand::{Rng, SeedableRng, rngs::StdRng, seq::SliceRandom, thread_rng};
14
15#[cfg(test)]
16use crate::commit::CertifiedCommit;
17use crate::{
18    CommitRef, CommittedSubDag, Transaction,
19    block::{BlockAPI, BlockTransactionVotes, Slot, TestBlock, VerifiedBlock, genesis_blocks},
20    commit::{CommitDigest, TrustedCommit},
21    context::Context,
22    dag_state::DagState,
23    leader_schedule::{LeaderSchedule, LeaderSwapTable},
24    linearizer::{BlockStoreAPI, Linearizer},
25};
26
27/// DagBuilder API
28///
29/// Usage:
30///
31/// DAG Building
32/// ```ignore
33/// let context = Arc::new(Context::new_for_test(4).0);
34/// let mut dag_builder = DagBuilder::new(context);
35/// dag_builder.layer(1).build(); // Round 1 is fully connected with parents by default.
36/// dag_builder.layers(2..=10).build(); // Rounds 2 ~ 10 are fully connected with parents by default.
37/// dag_builder.layer(11).min_parent_links().build(); // Round 11 is minimally and randomly connected with parents, without weak links.
38/// dag_builder.layer(12).no_leader_block(0).build(); // Round 12 misses leader block. Other blocks are fully connected with parents.
39/// dag_builder.layer(13).no_leader_link(12, 0).build(); // Round 13 misses votes for leader block. Other blocks are fully connected with parents.
40/// dag_builder.layer(14).authorities(vec![3,5]).skip_block().build(); // Round 14 authorities 3 and 5 will not propose any block.
41/// dag_builder.layer(15).authorities(vec![3,5]).skip_ancestor_links(vec![1,2]).build(); // Round 15 authorities 3 and 5 will not link to ancestors 1 and 2
42/// dag_builder.layer(16).authorities(vec![3,5]).equivocate(3).build(); // Round 16 authorities 3 and 5 will produce 3 equivocating blocks.
43/// ```
44///
45/// Persisting to DagState by Layer
46/// ```ignore
47/// let dag_state = Arc::new(RwLock::new(DagState::new(
48///    dag_builder.context.clone(),
49///    Arc::new(MemStore::new()),
50/// )));
51/// let context = Arc::new(Context::new_for_test(4).0);
52/// let mut dag_builder = DagBuilder::new(context);
53/// dag_builder.layer(1).build().persist_layers(dag_state.clone()); // persist the layer
54/// ```
55///
56/// Persisting entire DAG to DagState
57/// ```ignore
58/// let dag_state = Arc::new(RwLock::new(DagState::new(
59///    dag_builder.context.clone(),
60///    Arc::new(MemStore::new()),
61/// )));
62/// let context = Arc::new(Context::new_for_test(4).0);
63/// let mut dag_builder = DagBuilder::new(context);
64/// dag_builder.layer(1).build();
65/// dag_builder.layers(2..=10).build();
66/// dag_builder.persist_all_blocks(dag_state.clone()); // persist entire DAG
67/// ```
68///
69/// Printing DAG
70/// ```ignore
71/// let context = Arc::new(Context::new_for_test(4).0);
72/// let mut dag_builder = DagBuilder::new(context);
73/// dag_builder.layer(1).build();
74/// dag_builder.print(); // pretty print the entire DAG
75/// ```
76pub struct DagBuilder {
77    pub(crate) context: Arc<Context>,
78    pub(crate) leader_schedule: LeaderSchedule,
79    // The genesis blocks
80    pub(crate) genesis: BTreeMap<BlockRef, VerifiedBlock>,
81    // The current set of ancestors that any new layer will attempt to connect to.
82    pub(crate) last_ancestors: Vec<BlockRef>,
83    // All blocks created by dag builder. Will be used to pretty print or to be
84    // retrieved for testing/persiting to dag state.
85    pub(crate) blocks: BTreeMap<BlockRef, VerifiedBlock>,
86    // All the committed sub dags created by the dag builder.
87    pub(crate) committed_sub_dags: Vec<(CommittedSubDag, TrustedCommit)>,
88    pub(crate) last_committed_rounds: Vec<Round>,
89
90    number_of_leaders: u32,
91}
92
93impl DagBuilder {
94    pub fn new(context: Arc<Context>) -> Self {
95        let leader_schedule = LeaderSchedule::new(context.clone(), LeaderSwapTable::default());
96        let genesis_blocks = genesis_blocks(context.as_ref());
97        let genesis: BTreeMap<BlockRef, VerifiedBlock> = genesis_blocks
98            .into_iter()
99            .map(|block| (block.reference(), block))
100            .collect();
101        let last_ancestors = genesis.keys().cloned().collect();
102        Self {
103            last_committed_rounds: vec![0; context.committee.size()],
104            context,
105            leader_schedule,
106            number_of_leaders: 1,
107            genesis,
108            last_ancestors,
109            blocks: BTreeMap::new(),
110            committed_sub_dags: vec![],
111        }
112    }
113
114    pub fn blocks(&self, rounds: RangeInclusive<Round>) -> Vec<VerifiedBlock> {
115        assert!(
116            !self.blocks.is_empty(),
117            "No blocks have been created, please make sure that you have called build method"
118        );
119        self.blocks
120            .iter()
121            .filter_map(|(block_ref, block)| rounds.contains(&block_ref.round).then_some(block))
122            .cloned()
123            .collect::<Vec<VerifiedBlock>>()
124    }
125
126    pub fn all_blocks(&self) -> Vec<VerifiedBlock> {
127        assert!(
128            !self.blocks.is_empty(),
129            "No blocks have been created, please make sure that you have called build method"
130        );
131        self.blocks.values().cloned().collect()
132    }
133
134    pub fn get_sub_dag_and_commits(
135        &mut self,
136        leader_rounds: RangeInclusive<Round>,
137    ) -> Vec<(CommittedSubDag, TrustedCommit)> {
138        let (last_leader_round, mut last_commit_ref, mut last_timestamp_ms) =
139            if let Some((sub_dag, _)) = self.committed_sub_dags.last() {
140                (
141                    sub_dag.leader.round,
142                    sub_dag.commit_ref,
143                    sub_dag.timestamp_ms,
144                )
145            } else {
146                (0, CommitRef::new(0, CommitDigest::MIN), 0)
147            };
148
149        struct BlockStorage {
150            gc_round: Round,
151            blocks: BTreeMap<BlockRef, (VerifiedBlock, bool)>, // the tuple represends the block and whether it is committed
152            genesis: BTreeMap<BlockRef, VerifiedBlock>,
153        }
154        impl BlockStoreAPI for BlockStorage {
155            fn get_blocks(&self, refs: &[BlockRef]) -> Vec<Option<VerifiedBlock>> {
156                refs.iter()
157                    .map(|block_ref| {
158                        if block_ref.round == 0 {
159                            return self.genesis.get(block_ref).cloned();
160                        }
161                        self.blocks
162                            .get(block_ref)
163                            .map(|(block, _committed)| block.clone())
164                    })
165                    .collect()
166            }
167
168            fn gc_round(&self) -> Round {
169                self.gc_round
170            }
171
172            fn set_committed(&mut self, block_ref: &BlockRef) -> bool {
173                let Some((_block, committed)) = self.blocks.get_mut(block_ref) else {
174                    panic!("Block {:?} should be found in store", block_ref);
175                };
176                if !*committed {
177                    *committed = true;
178                    return true;
179                }
180                false
181            }
182
183            fn is_committed(&self, block_ref: &BlockRef) -> bool {
184                self.blocks
185                    .get(block_ref)
186                    .map(|(_, committed)| *committed)
187                    .expect("Block should be found in store")
188            }
189        }
190
191        let mut storage = BlockStorage {
192            blocks: self
193                .blocks
194                .clone()
195                .into_iter()
196                .map(|(k, v)| (k, (v, false)))
197                .collect(),
198            genesis: self.genesis.clone(),
199            gc_round: 0,
200        };
201
202        // Create any remaining committed sub dags
203        for leader_block in self
204            .leader_blocks(last_leader_round + 1..=*leader_rounds.end())
205            .into_iter()
206            .flatten()
207        {
208            // set the gc round to the round of the leader block
209            storage.gc_round = leader_block
210                .round()
211                .saturating_sub(1)
212                .saturating_sub(self.context.protocol_config.gc_depth());
213
214            let leader_block_ref = leader_block.reference();
215
216            let to_commit = Linearizer::linearize_sub_dag(leader_block.clone(), &mut storage);
217
218            last_timestamp_ms = Linearizer::calculate_commit_timestamp(
219                &self.context.clone(),
220                &mut storage,
221                &leader_block,
222                last_timestamp_ms,
223            );
224
225            // Update the last committed rounds
226            for block in &to_commit {
227                self.last_committed_rounds[block.author()] =
228                    self.last_committed_rounds[block.author()].max(block.round());
229            }
230
231            let commit = TrustedCommit::new_for_test(
232                last_commit_ref.index + 1,
233                last_commit_ref.digest,
234                last_timestamp_ms,
235                leader_block_ref,
236                to_commit
237                    .iter()
238                    .map(|block| block.reference())
239                    .collect::<Vec<_>>(),
240            );
241
242            last_commit_ref = commit.reference();
243
244            let sub_dag = CommittedSubDag::new(
245                leader_block_ref,
246                to_commit,
247                last_timestamp_ms,
248                commit.reference(),
249                true,
250            );
251
252            self.committed_sub_dags.push((sub_dag, commit));
253        }
254
255        self.committed_sub_dags
256            .clone()
257            .into_iter()
258            .filter(|(sub_dag, _)| leader_rounds.contains(&sub_dag.leader.round))
259            .collect()
260    }
261
262    #[cfg(test)]
263    pub(crate) fn get_sub_dag_and_certified_commits(
264        &mut self,
265        leader_rounds: RangeInclusive<Round>,
266    ) -> Vec<(CommittedSubDag, CertifiedCommit)> {
267        let commits = self.get_sub_dag_and_commits(leader_rounds);
268        commits
269            .into_iter()
270            .map(|(sub_dag, commit)| {
271                let certified_commit =
272                    CertifiedCommit::new_certified(commit, sub_dag.blocks.clone());
273                (sub_dag, certified_commit)
274            })
275            .collect()
276    }
277
278    pub fn leader_blocks(&self, rounds: RangeInclusive<Round>) -> Vec<Option<VerifiedBlock>> {
279        assert!(
280            !self.blocks.is_empty(),
281            "No blocks have been created, please make sure that you have called build method"
282        );
283        rounds
284            .into_iter()
285            .map(|round| self.leader_block(round))
286            .collect()
287    }
288
289    pub fn leader_block(&self, round: Round) -> Option<VerifiedBlock> {
290        assert!(
291            !self.blocks.is_empty(),
292            "No blocks have been created, please make sure that you have called build method"
293        );
294        self.blocks
295            .iter()
296            .find(|(block_ref, _block)| {
297                block_ref.round == round
298                    && block_ref.author == self.leader_schedule.elect_leader(round, 0)
299            })
300            .map(|(_block_ref, block)| block.clone())
301    }
302
303    pub fn layer(&mut self, round: Round) -> LayerBuilder<'_> {
304        LayerBuilder::new(self, round)
305    }
306
307    pub fn layers(&mut self, rounds: RangeInclusive<Round>) -> LayerBuilder<'_> {
308        let mut builder = LayerBuilder::new(self, *rounds.start());
309        builder.end_round = Some(*rounds.end());
310        builder
311    }
312
313    pub fn persist_all_blocks(&self, dag_state: Arc<RwLock<DagState>>) {
314        dag_state
315            .write()
316            .accept_blocks(self.blocks.values().cloned().collect());
317    }
318
319    pub fn print(&self) {
320        let mut dag_str = "DAG {\n".to_string();
321
322        let mut round = 0;
323        for block in self.blocks.values() {
324            if block.round() > round {
325                round = block.round();
326                dag_str.push_str(&format!("Round {round} : \n"));
327            }
328            dag_str.push_str(&format!("    Block {block:#?}\n"));
329        }
330        dag_str.push_str("}\n");
331
332        tracing::info!("{dag_str}");
333    }
334
335    // TODO: merge into layer builder?
336    // This method allows the user to specify specific links to ancestors. The
337    // layer is written to dag state and the blocks are cached in [`DagBuilder`]
338    // state.
339    pub fn layer_with_connections(
340        &mut self,
341        connections: Vec<(AuthorityIndex, Vec<BlockRef>)>,
342        round: Round,
343    ) {
344        let mut references = Vec::new();
345        for (authority, ancestors) in connections {
346            let author = authority.value() as u32;
347            let base_ts = round as BlockTimestampMs * 1000;
348            let block = VerifiedBlock::new_for_test(
349                TestBlock::new(round, author)
350                    .set_ancestors(ancestors)
351                    .set_timestamp_ms(base_ts + author as u64)
352                    .build(),
353            );
354            references.push(block.reference());
355            self.blocks.insert(block.reference(), block.clone());
356        }
357        self.last_ancestors = references;
358    }
359
360    /// Gets all uncommitted blocks in a slot.
361    pub fn get_uncommitted_blocks_at_slot(&self, slot: Slot) -> Vec<VerifiedBlock> {
362        let mut blocks = vec![];
363        for (_block_ref, block) in self.blocks.range((
364            Included(BlockRef::new(slot.round, slot.authority, BlockDigest::MIN)),
365            Included(BlockRef::new(slot.round, slot.authority, BlockDigest::MAX)),
366        )) {
367            blocks.push(block.clone())
368        }
369        blocks
370    }
371
372    pub fn genesis_block_refs(&self) -> Vec<BlockRef> {
373        self.genesis.keys().cloned().collect()
374    }
375}
376
377/// Refer to doc comments for [`DagBuilder`] for usage information.
378pub struct LayerBuilder<'a> {
379    dag_builder: &'a mut DagBuilder,
380
381    start_round: Round,
382    end_round: Option<Round>,
383
384    // Configuration options applied to specified authorities
385    // TODO: convert configuration options into an enum
386    specified_authorities: Option<Vec<AuthorityIndex>>,
387    // Number of transactions to include per block.
388    num_transactions: u32,
389    // Whether to include rejected transactions
390    rejected_transactions_pct: u8,
391    rejected_transactions_seed: u64,
392    // Number of equivocating blocks per specified authority
393    equivocations: usize,
394    // Skip block proposal for specified authorities
395    skip_block: bool,
396    // Skip specified ancestor links for specified authorities
397    skip_ancestor_links: Option<Vec<AuthorityIndex>>,
398    // Skip leader link for specified authorities
399    no_leader_link: bool,
400    // Use to override last ancestors in dag builder
401    override_last_ancestors: bool,
402
403    // Skip leader block proposal
404    no_leader_block: bool,
405    // Used for leader based configurations
406    specified_leader_link_offsets: Option<Vec<u32>>,
407    specified_leader_block_offsets: Option<Vec<u32>>,
408    leader_round: Option<Round>,
409
410    // All ancestors will be linked to the current layer
411    fully_linked_ancestors: bool,
412    // Only 2f+1 random ancestors will be linked to the current layer using a
413    // seed, if provided
414    min_ancestor_links: bool,
415    min_ancestor_links_random_seed: Option<u64>,
416    // Add random weak links to the current layer using a seed, if provided
417    random_weak_links: bool,
418    random_weak_links_random_seed: Option<u64>,
419
420    // Ancestors to link to the current layer
421    ancestors: Vec<BlockRef>,
422    // override last ancestors in dag_builder
423    specified_ancestors: Vec<BlockRef>,
424
425    // The block timestamps for the layer for each specified authority. This will work as base timestamp and the round will be added to make sure that timestamps do offset.
426    timestamps: Vec<BlockTimestampMs>,
427
428    // Accumulated blocks to write to dag state
429    blocks: Vec<VerifiedBlock>,
430}
431
432#[allow(unused)]
433impl<'a> LayerBuilder<'a> {
434    fn new(dag_builder: &'a mut DagBuilder, start_round: Round) -> Self {
435        assert!(start_round > 0, "genesis round is created by default");
436        let ancestors = dag_builder.last_ancestors.clone();
437        Self {
438            dag_builder,
439            start_round,
440            end_round: None,
441            specified_authorities: None,
442            num_transactions: 0,
443            rejected_transactions_pct: 0,
444            rejected_transactions_seed: 0,
445            equivocations: 0,
446            skip_block: false,
447            skip_ancestor_links: None,
448            override_last_ancestors: false,
449            no_leader_link: false,
450            no_leader_block: false,
451            specified_leader_link_offsets: None,
452            specified_leader_block_offsets: None,
453            leader_round: None,
454            fully_linked_ancestors: true,
455            min_ancestor_links: false,
456            min_ancestor_links_random_seed: None,
457            random_weak_links: false,
458            random_weak_links_random_seed: None,
459            ancestors,
460            specified_ancestors: vec![],
461            timestamps: vec![],
462            blocks: vec![],
463        }
464    }
465
466    // Configuration methods
467
468    // If you try to add blocks to the same layer you will end up with the last
469    // ancestors replaced with blocks from the current layer. Use this method
470    // to override the last ancestors with the references you manually have kept.
471    pub fn override_last_ancestors(mut self, ancestors: Vec<BlockRef>) -> Self {
472        self.specified_ancestors = ancestors;
473        self.override_last_ancestors = true;
474        self.build()
475    }
476
477    // Only link 2f+1 random ancestors to the current layer round using a seed,
478    // if provided. Also provide a flag to guarantee the leader is included.
479    // note: configuration is terminal and layer will be built after this call.
480    pub fn min_ancestor_links(mut self, include_leader: bool, seed: Option<u64>) -> Self {
481        self.min_ancestor_links = true;
482        self.min_ancestor_links_random_seed = seed;
483        if include_leader {
484            self.leader_round = Some(self.ancestors.iter().max_by_key(|b| b.round).unwrap().round);
485        }
486        self.fully_linked_ancestors = false;
487        self.build()
488    }
489
490    // No links will be created between the specified ancestors and the specified
491    // authorities at the layer round.
492    // note: configuration is terminal and layer will be built after this call.
493    pub fn skip_ancestor_links(mut self, ancestors_to_skip: Vec<AuthorityIndex>) -> Self {
494        // authorities must be specified for this to apply
495        assert!(self.specified_authorities.is_some());
496        self.skip_ancestor_links = Some(ancestors_to_skip);
497        self.fully_linked_ancestors = false;
498        self.build()
499    }
500
501    // Add random weak links to the current layer round using a seed, if provided
502    pub fn random_weak_links(mut self, seed: Option<u64>) -> Self {
503        self.random_weak_links = true;
504        self.random_weak_links_random_seed = seed;
505        self
506    }
507
508    // Should be called when building a leader round. Will ensure leader block is missing.
509    // A list of specified leader offsets can be provided to skip those leaders.
510    // If none are provided all potential leaders for the round will be skipped.
511    pub fn no_leader_block(mut self, specified_leader_offsets: Vec<u32>) -> Self {
512        self.no_leader_block = true;
513        self.specified_leader_block_offsets = Some(specified_leader_offsets);
514        self
515    }
516
517    // Should be called when building a voting round. Will ensure vote is missing.
518    // A list of specified leader offsets can be provided to skip those leader links.
519    // If none are provided all potential leaders for the round will be skipped.
520    // note: configuration is terminal and layer will be built after this call.
521    pub fn no_leader_link(
522        mut self,
523        leader_round: Round,
524        specified_leader_offsets: Vec<u32>,
525    ) -> Self {
526        self.no_leader_link = true;
527        self.specified_leader_link_offsets = Some(specified_leader_offsets);
528        self.leader_round = Some(leader_round);
529        self.fully_linked_ancestors = false;
530        self.build()
531    }
532
533    pub fn authorities(mut self, authorities: Vec<AuthorityIndex>) -> Self {
534        assert!(
535            self.specified_authorities.is_none(),
536            "Specified authorities already set"
537        );
538        self.specified_authorities = Some(authorities);
539        self
540    }
541
542    // Number of transactions to include per block.
543    pub fn num_transactions(mut self, num_transactions: u32) -> Self {
544        self.num_transactions = num_transactions;
545        self
546    }
547
548    pub fn rejected_transactions_pct(mut self, pct: u8, seed: Option<u64>) -> Self {
549        self.rejected_transactions_pct = pct;
550        self.rejected_transactions_seed = if let Some(seed) = seed {
551            seed
552        } else {
553            thread_rng().r#gen()
554        };
555        self
556    }
557
558    // Multiple blocks will be created for the specified authorities at the layer round.
559    pub fn equivocate(mut self, equivocations: usize) -> Self {
560        // authorities must be specified for this to apply
561        assert!(self.specified_authorities.is_some());
562        self.equivocations = equivocations;
563        self
564    }
565
566    // No blocks will be created for the specified authorities at the layer round.
567    pub fn skip_block(mut self) -> Self {
568        // authorities must be specified for this to apply
569        assert!(self.specified_authorities.is_some());
570        self.skip_block = true;
571        self
572    }
573
574    pub fn with_timestamps(mut self, timestamps: Vec<BlockTimestampMs>) -> Self {
575        // authorities must be specified for this to apply
576        assert!(self.specified_authorities.is_some());
577        assert_eq!(
578            self.specified_authorities.as_ref().unwrap().len(),
579            timestamps.len(),
580            "Timestamps should be provided for each specified authority"
581        );
582        self.timestamps = timestamps;
583        self
584    }
585
586    // Apply the configurations & build the dag layer(s).
587    pub fn build(mut self) -> Self {
588        for round in self.start_round..=self.end_round.unwrap_or(self.start_round) {
589            tracing::debug!("BUILDING LAYER ROUND {round}...");
590
591            let authorities = if self.specified_authorities.is_some() {
592                self.specified_authorities.clone().unwrap()
593            } else {
594                self.dag_builder
595                    .context
596                    .committee
597                    .authorities()
598                    .map(|x| x.0)
599                    .collect()
600            };
601
602            // TODO: investigate if these configurations can be called in combination
603            // for the same layer
604            let mut connections = if self.override_last_ancestors {
605                self.configure_specifed_ancestors()
606            } else if self.fully_linked_ancestors {
607                self.configure_fully_linked_ancestors(round)
608            } else if self.min_ancestor_links {
609                self.configure_min_parent_links(round)
610            } else if self.no_leader_link {
611                self.configure_no_leader_links(authorities.clone(), round)
612            } else if self.skip_ancestor_links.is_some() {
613                self.configure_skipped_ancestor_links(
614                    authorities,
615                    self.skip_ancestor_links.clone().unwrap(),
616                )
617            } else {
618                vec![]
619            };
620
621            if self.random_weak_links {
622                connections.append(&mut self.configure_random_weak_links());
623            }
624
625            self.create_blocks(round, connections);
626        }
627
628        self.dag_builder.last_ancestors = self.ancestors.clone();
629        self
630    }
631
632    pub fn persist_layers(&self, dag_state: Arc<RwLock<DagState>>) {
633        assert!(
634            !self.blocks.is_empty(),
635            "Called to persist layers although no blocks have been created. Make sure you have called build before."
636        );
637        dag_state.write().accept_blocks(self.blocks.clone());
638    }
639
640    // Layer round is minimally and randomly connected with ancestors.
641    pub fn configure_min_parent_links(
642        &mut self,
643        round: Round,
644    ) -> Vec<(AuthorityIndex, Vec<BlockRef>)> {
645        let quorum_threshold = self.dag_builder.context.committee.quorum_threshold() as usize;
646        let mut authorities: Vec<AuthorityIndex> = self
647            .dag_builder
648            .context
649            .committee
650            .authorities()
651            .map(|authority| authority.0)
652            .collect();
653
654        let mut rng = match self.min_ancestor_links_random_seed {
655            Some(s) => StdRng::seed_from_u64(s),
656            None => StdRng::from_entropy(),
657        };
658
659        let mut authorities_to_shuffle = authorities.clone();
660
661        let mut leaders = vec![];
662        if let Some(leader_round) = self.leader_round {
663            let leader_offsets = (0..self.dag_builder.number_of_leaders).collect::<Vec<_>>();
664
665            for leader_offset in leader_offsets {
666                leaders.push(
667                    self.dag_builder
668                        .leader_schedule
669                        .elect_leader(leader_round, leader_offset),
670                );
671            }
672        }
673
674        authorities
675            .iter()
676            .map(|authority| {
677                authorities_to_shuffle.shuffle(&mut rng);
678
679                // TODO: handle quroum threshold properly with stake
680                let min_ancestors: HashSet<AuthorityIndex> = authorities_to_shuffle
681                    .iter()
682                    .take(quorum_threshold)
683                    .cloned()
684                    .collect();
685
686                (
687                    *authority,
688                    self.ancestors
689                        .iter()
690                        .filter(|a| {
691                            leaders.contains(&a.author)
692                                || min_ancestors.contains(&a.author)
693                                || a.round != round
694                        })
695                        .cloned()
696                        .collect::<Vec<BlockRef>>(),
697                )
698            })
699            .collect()
700    }
701
702    // TODO: configure layer round randomly connected with weak links.
703    fn configure_random_weak_links(&mut self) -> Vec<(AuthorityIndex, Vec<BlockRef>)> {
704        unimplemented!("configure_random_weak_links");
705    }
706
707    // Layer round misses link to leader, but other blocks are fully connected with ancestors.
708    fn configure_no_leader_links(
709        &mut self,
710        authorities: Vec<AuthorityIndex>,
711        round: Round,
712    ) -> Vec<(AuthorityIndex, Vec<BlockRef>)> {
713        let mut missing_leaders = Vec::new();
714        let mut specified_leader_offsets = self
715            .specified_leader_link_offsets
716            .clone()
717            .expect("specified_leader_offsets should be set");
718        let leader_round = self.leader_round.expect("leader round should be set");
719
720        // When no specified leader offsets are available, all leaders are
721        // expected to be missing.
722        if specified_leader_offsets.is_empty() {
723            specified_leader_offsets.extend(0..self.dag_builder.number_of_leaders);
724        }
725
726        for leader_offset in specified_leader_offsets {
727            missing_leaders.push(
728                self.dag_builder
729                    .leader_schedule
730                    .elect_leader(leader_round, leader_offset),
731            );
732        }
733
734        self.configure_skipped_ancestor_links(authorities, missing_leaders)
735    }
736
737    fn configure_specifed_ancestors(&mut self) -> Vec<(AuthorityIndex, Vec<BlockRef>)> {
738        self.dag_builder
739            .context
740            .committee
741            .authorities()
742            .map(|authority| (authority.0, self.specified_ancestors.clone()))
743            .collect::<Vec<_>>()
744    }
745
746    fn configure_fully_linked_ancestors(
747        &mut self,
748        round: Round,
749    ) -> Vec<(AuthorityIndex, Vec<BlockRef>)> {
750        self.dag_builder
751            .context
752            .committee
753            .authorities()
754            .map(|authority| {
755                (
756                    authority.0,
757                    // don't connect to ancestors of this round
758                    self.ancestors
759                        .clone()
760                        .into_iter()
761                        .filter(|a| a.round != round)
762                        .collect::<Vec<_>>(),
763                )
764            })
765            .collect::<Vec<_>>()
766    }
767
768    fn configure_skipped_ancestor_links(
769        &mut self,
770        authorities: Vec<AuthorityIndex>,
771        ancestors_to_skip: Vec<AuthorityIndex>,
772    ) -> Vec<(AuthorityIndex, Vec<BlockRef>)> {
773        let filtered_ancestors = self
774            .ancestors
775            .clone()
776            .into_iter()
777            .filter(|ancestor| !ancestors_to_skip.contains(&ancestor.author))
778            .collect::<Vec<_>>();
779        authorities
780            .into_iter()
781            .map(|authority| (authority, filtered_ancestors.clone()))
782            .collect::<Vec<_>>()
783    }
784
785    // Creates the blocks for the new layer based on configured connections, also
786    // sets the ancestors for future layers to be linked to
787    fn create_blocks(&mut self, round: Round, connections: Vec<(AuthorityIndex, Vec<BlockRef>)>) {
788        let mut references = Vec::new();
789        let mut reject_rng =
790            StdRng::seed_from_u64(self.rejected_transactions_seed ^ (round as u64));
791        for (authority, ancestors) in connections {
792            if self.should_skip_block(round, authority) {
793                continue;
794            };
795            let transactions = (0..self.num_transactions)
796                .map(|_| Transaction::new(vec![1_u8; 16]))
797                .collect::<Vec<_>>();
798            let num_blocks = self.num_blocks_to_create(authority);
799            for num_block in 0..num_blocks {
800                let mut votes = vec![];
801                if self.rejected_transactions_pct > 0 {
802                    for ancestor in &ancestors {
803                        let mut rejects = vec![];
804                        for i in 0..self.num_transactions {
805                            if reject_rng.gen_range(1..=100) <= self.rejected_transactions_pct {
806                                rejects.push(i as TransactionIndex);
807                            }
808                        }
809                        if !rejects.is_empty() {
810                            votes.push(BlockTransactionVotes {
811                                block_ref: *ancestor,
812                                rejects,
813                            });
814                        }
815                    }
816                }
817                let timestamp = self.block_timestamp(authority, round, num_block);
818                let block = VerifiedBlock::new_for_test(
819                    TestBlock::new(round, authority.value() as u32)
820                        .set_transactions(transactions.clone())
821                        .set_transaction_votes(votes)
822                        .set_ancestors(ancestors.clone())
823                        .set_timestamp_ms(timestamp)
824                        .build(),
825                );
826                references.push(block.reference());
827                self.dag_builder
828                    .blocks
829                    .insert(block.reference(), block.clone());
830                self.blocks.push(block);
831            }
832        }
833        self.ancestors = references;
834    }
835
836    fn num_blocks_to_create(&self, authority: AuthorityIndex) -> u32 {
837        if self.specified_authorities.is_some()
838            && self
839                .specified_authorities
840                .clone()
841                .unwrap()
842                .contains(&authority)
843        {
844            // Always create 1 block and then the equivocating blocks on top of that.
845            1 + self.equivocations as u32
846        } else {
847            1
848        }
849    }
850
851    fn block_timestamp(
852        &self,
853        authority: AuthorityIndex,
854        round: Round,
855        num_block: u32,
856    ) -> BlockTimestampMs {
857        if self.specified_authorities.is_some() && !self.timestamps.is_empty() {
858            let specified_authorities = self.specified_authorities.as_ref().unwrap();
859
860            if let Some(position) = specified_authorities.iter().position(|&x| x == authority) {
861                return self.timestamps[position] + (round + num_block) as u64;
862            }
863        }
864        let author = authority.value() as u32;
865        let base_ts = round as BlockTimestampMs * 1000;
866        base_ts + (author + round + num_block) as u64
867    }
868
869    fn should_skip_block(&self, round: Round, authority: AuthorityIndex) -> bool {
870        // Safe to unwrap as specified authorites has to be set before skip
871        // is specified.
872        if self.skip_block
873            && self
874                .specified_authorities
875                .clone()
876                .unwrap()
877                .contains(&authority)
878        {
879            return true;
880        }
881        if self.no_leader_block {
882            let mut specified_leader_offsets = self
883                .specified_leader_block_offsets
884                .clone()
885                .expect("specified_leader_block_offsets should be set");
886
887            // When no specified leader offsets are available, all leaders are
888            // expected to be skipped.
889            if specified_leader_offsets.is_empty() {
890                specified_leader_offsets.extend(0..self.dag_builder.number_of_leaders);
891            }
892
893            for leader_offset in specified_leader_offsets {
894                let leader = self
895                    .dag_builder
896                    .leader_schedule
897                    .elect_leader(round, leader_offset);
898
899                if leader == authority {
900                    return true;
901                }
902            }
903        }
904        false
905    }
906}
consensus_core/test_dag_builder.rs

consensus_core/
test_dag_builder.rs
