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            );
250
251            self.committed_sub_dags.push((sub_dag, commit));
252        }
253
254        self.committed_sub_dags
255            .clone()
256            .into_iter()
257            .filter(|(sub_dag, _)| leader_rounds.contains(&sub_dag.leader.round))
258            .collect()
259    }
260
261    #[cfg(test)]
262    pub(crate) fn get_sub_dag_and_certified_commits(
263        &mut self,
264        leader_rounds: RangeInclusive<Round>,
265    ) -> Vec<(CommittedSubDag, CertifiedCommit)> {
266        let commits = self.get_sub_dag_and_commits(leader_rounds);
267        commits
268            .into_iter()
269            .map(|(sub_dag, commit)| {
270                let certified_commit =
271                    CertifiedCommit::new_certified(commit, sub_dag.blocks.clone());
272                (sub_dag, certified_commit)
273            })
274            .collect()
275    }
276
277    pub fn leader_blocks(&self, rounds: RangeInclusive<Round>) -> Vec<Option<VerifiedBlock>> {
278        assert!(
279            !self.blocks.is_empty(),
280            "No blocks have been created, please make sure that you have called build method"
281        );
282        rounds
283            .into_iter()
284            .map(|round| self.leader_block(round))
285            .collect()
286    }
287
288    pub fn leader_block(&self, round: Round) -> Option<VerifiedBlock> {
289        assert!(
290            !self.blocks.is_empty(),
291            "No blocks have been created, please make sure that you have called build method"
292        );
293        self.blocks
294            .iter()
295            .find(|(block_ref, _block)| {
296                block_ref.round == round
297                    && block_ref.author == self.leader_schedule.elect_leader(round, 0)
298            })
299            .map(|(_block_ref, block)| block.clone())
300    }
301
302    pub fn layer(&mut self, round: Round) -> LayerBuilder<'_> {
303        LayerBuilder::new(self, round)
304    }
305
306    pub fn layers(&mut self, rounds: RangeInclusive<Round>) -> LayerBuilder<'_> {
307        let mut builder = LayerBuilder::new(self, *rounds.start());
308        builder.end_round = Some(*rounds.end());
309        builder
310    }
311
312    pub fn persist_all_blocks(&self, dag_state: Arc<RwLock<DagState>>) {
313        dag_state
314            .write()
315            .accept_blocks(self.blocks.values().cloned().collect());
316    }
317
318    pub fn print(&self) {
319        let mut dag_str = "DAG {\n".to_string();
320
321        let mut round = 0;
322        for block in self.blocks.values() {
323            if block.round() > round {
324                round = block.round();
325                dag_str.push_str(&format!("Round {round} : \n"));
326            }
327            dag_str.push_str(&format!("    Block {block:#?}\n"));
328        }
329        dag_str.push_str("}\n");
330
331        tracing::info!("{dag_str}");
332    }
333
334    // TODO: merge into layer builder?
335    // This method allows the user to specify specific links to ancestors. The
336    // layer is written to dag state and the blocks are cached in [`DagBuilder`]
337    // state.
338    pub fn layer_with_connections(
339        &mut self,
340        connections: Vec<(AuthorityIndex, Vec<BlockRef>)>,
341        round: Round,
342    ) {
343        let mut references = Vec::new();
344        for (authority, ancestors) in connections {
345            let author = authority.value() as u32;
346            let base_ts = round as BlockTimestampMs * 1000;
347            let block = VerifiedBlock::new_for_test(
348                TestBlock::new(round, author)
349                    .set_ancestors(ancestors)
350                    .set_timestamp_ms(base_ts + author as u64)
351                    .build(),
352            );
353            references.push(block.reference());
354            self.blocks.insert(block.reference(), block.clone());
355        }
356        self.last_ancestors = references;
357    }
358
359    /// Gets all uncommitted blocks in a slot.
360    pub fn get_uncommitted_blocks_at_slot(&self, slot: Slot) -> Vec<VerifiedBlock> {
361        let mut blocks = vec![];
362        for (_block_ref, block) in self.blocks.range((
363            Included(BlockRef::new(slot.round, slot.authority, BlockDigest::MIN)),
364            Included(BlockRef::new(slot.round, slot.authority, BlockDigest::MAX)),
365        )) {
366            blocks.push(block.clone())
367        }
368        blocks
369    }
370
371    pub fn genesis_block_refs(&self) -> Vec<BlockRef> {
372        self.genesis.keys().cloned().collect()
373    }
374}
375
376/// Refer to doc comments for [`DagBuilder`] for usage information.
377pub struct LayerBuilder<'a> {
378    dag_builder: &'a mut DagBuilder,
379
380    start_round: Round,
381    end_round: Option<Round>,
382
383    // Configuration options applied to specified authorities
384    // TODO: convert configuration options into an enum
385    specified_authorities: Option<Vec<AuthorityIndex>>,
386    // Number of transactions to include per block.
387    num_transactions: u32,
388    // Whether to include rejected transactions
389    rejected_transactions_pct: u8,
390    rejected_transactions_seed: u64,
391    // Number of equivocating blocks per specified authority
392    equivocations: usize,
393    // Skip block proposal for specified authorities
394    skip_block: bool,
395    // Skip specified ancestor links for specified authorities
396    skip_ancestor_links: Option<Vec<AuthorityIndex>>,
397    // Skip leader link for specified authorities
398    no_leader_link: bool,
399    // Use to override last ancestors in dag builder
400    override_last_ancestors: bool,
401
402    // Skip leader block proposal
403    no_leader_block: bool,
404    // Used for leader based configurations
405    specified_leader_link_offsets: Option<Vec<u32>>,
406    specified_leader_block_offsets: Option<Vec<u32>>,
407    leader_round: Option<Round>,
408
409    // All ancestors will be linked to the current layer
410    fully_linked_ancestors: bool,
411    // Only 2f+1 random ancestors will be linked to the current layer using a
412    // seed, if provided
413    min_ancestor_links: bool,
414    min_ancestor_links_random_seed: Option<u64>,
415    // Add random weak links to the current layer using a seed, if provided
416    random_weak_links: bool,
417    random_weak_links_random_seed: Option<u64>,
418
419    // Ancestors to link to the current layer
420    ancestors: Vec<BlockRef>,
421    // override last ancestors in dag_builder
422    specified_ancestors: Vec<BlockRef>,
423
424    // 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.
425    timestamps: Vec<BlockTimestampMs>,
426
427    // Accumulated blocks to write to dag state
428    blocks: Vec<VerifiedBlock>,
429}
430
431impl<'a> LayerBuilder<'a> {
432    fn new(dag_builder: &'a mut DagBuilder, start_round: Round) -> Self {
433        assert!(start_round > 0, "genesis round is created by default");
434        let ancestors = dag_builder.last_ancestors.clone();
435        Self {
436            dag_builder,
437            start_round,
438            end_round: None,
439            specified_authorities: None,
440            num_transactions: 0,
441            rejected_transactions_pct: 0,
442            rejected_transactions_seed: 0,
443            equivocations: 0,
444            skip_block: false,
445            skip_ancestor_links: None,
446            override_last_ancestors: false,
447            no_leader_link: false,
448            no_leader_block: false,
449            specified_leader_link_offsets: None,
450            specified_leader_block_offsets: None,
451            leader_round: None,
452            fully_linked_ancestors: true,
453            min_ancestor_links: false,
454            min_ancestor_links_random_seed: None,
455            random_weak_links: false,
456            random_weak_links_random_seed: None,
457            ancestors,
458            specified_ancestors: vec![],
459            timestamps: vec![],
460            blocks: vec![],
461        }
462    }
463
464    // Configuration methods
465
466    // If you try to add blocks to the same layer you will end up with the last
467    // ancestors replaced with blocks from the current layer. Use this method
468    // to override the last ancestors with the references you manually have kept.
469    pub fn override_last_ancestors(mut self, ancestors: Vec<BlockRef>) -> Self {
470        self.specified_ancestors = ancestors;
471        self.override_last_ancestors = true;
472        self.build()
473    }
474
475    // Only link 2f+1 random ancestors to the current layer round using a seed,
476    // if provided. Also provide a flag to guarantee the leader is included.
477    // note: configuration is terminal and layer will be built after this call.
478    pub fn min_ancestor_links(mut self, include_leader: bool, seed: Option<u64>) -> Self {
479        self.min_ancestor_links = true;
480        self.min_ancestor_links_random_seed = seed;
481        if include_leader {
482            self.leader_round = Some(self.ancestors.iter().max_by_key(|b| b.round).unwrap().round);
483        }
484        self.fully_linked_ancestors = false;
485        self.build()
486    }
487
488    // No links will be created between the specified ancestors and the specified
489    // authorities at the layer round.
490    // note: configuration is terminal and layer will be built after this call.
491    pub fn skip_ancestor_links(mut self, ancestors_to_skip: Vec<AuthorityIndex>) -> Self {
492        // authorities must be specified for this to apply
493        assert!(self.specified_authorities.is_some());
494        self.skip_ancestor_links = Some(ancestors_to_skip);
495        self.fully_linked_ancestors = false;
496        self.build()
497    }
498
499    // Add random weak links to the current layer round using a seed, if provided
500    pub fn random_weak_links(mut self, seed: Option<u64>) -> Self {
501        self.random_weak_links = true;
502        self.random_weak_links_random_seed = seed;
503        self
504    }
505
506    // Should be called when building a leader round. Will ensure leader block is missing.
507    // A list of specified leader offsets can be provided to skip those leaders.
508    // If none are provided all potential leaders for the round will be skipped.
509    pub fn no_leader_block(mut self, specified_leader_offsets: Vec<u32>) -> Self {
510        self.no_leader_block = true;
511        self.specified_leader_block_offsets = Some(specified_leader_offsets);
512        self
513    }
514
515    // Should be called when building a voting round. Will ensure vote is missing.
516    // A list of specified leader offsets can be provided to skip those leader links.
517    // If none are provided all potential leaders for the round will be skipped.
518    // note: configuration is terminal and layer will be built after this call.
519    pub fn no_leader_link(
520        mut self,
521        leader_round: Round,
522        specified_leader_offsets: Vec<u32>,
523    ) -> Self {
524        self.no_leader_link = true;
525        self.specified_leader_link_offsets = Some(specified_leader_offsets);
526        self.leader_round = Some(leader_round);
527        self.fully_linked_ancestors = false;
528        self.build()
529    }
530
531    pub fn authorities(mut self, authorities: Vec<AuthorityIndex>) -> Self {
532        assert!(
533            self.specified_authorities.is_none(),
534            "Specified authorities already set"
535        );
536        self.specified_authorities = Some(authorities);
537        self
538    }
539
540    // Number of transactions to include per block.
541    pub fn num_transactions(mut self, num_transactions: u32) -> Self {
542        self.num_transactions = num_transactions;
543        self
544    }
545
546    pub fn rejected_transactions_pct(mut self, pct: u8, seed: Option<u64>) -> Self {
547        self.rejected_transactions_pct = pct;
548        self.rejected_transactions_seed = if let Some(seed) = seed {
549            seed
550        } else {
551            thread_rng().r#gen()
552        };
553        self
554    }
555
556    // Multiple blocks will be created for the specified authorities at the layer round.
557    pub fn equivocate(mut self, equivocations: usize) -> Self {
558        // authorities must be specified for this to apply
559        assert!(self.specified_authorities.is_some());
560        self.equivocations = equivocations;
561        self
562    }
563
564    // No blocks will be created for the specified authorities at the layer round.
565    pub fn skip_block(mut self) -> Self {
566        // authorities must be specified for this to apply
567        assert!(self.specified_authorities.is_some());
568        self.skip_block = true;
569        self
570    }
571
572    pub fn with_timestamps(mut self, timestamps: Vec<BlockTimestampMs>) -> Self {
573        // authorities must be specified for this to apply
574        assert!(self.specified_authorities.is_some());
575        assert_eq!(
576            self.specified_authorities.as_ref().unwrap().len(),
577            timestamps.len(),
578            "Timestamps should be provided for each specified authority"
579        );
580        self.timestamps = timestamps;
581        self
582    }
583
584    // Apply the configurations & build the dag layer(s).
585    pub fn build(mut self) -> Self {
586        for round in self.start_round..=self.end_round.unwrap_or(self.start_round) {
587            tracing::debug!("BUILDING LAYER ROUND {round}...");
588
589            let authorities = if self.specified_authorities.is_some() {
590                self.specified_authorities.clone().unwrap()
591            } else {
592                self.dag_builder
593                    .context
594                    .committee
595                    .authorities()
596                    .map(|x| x.0)
597                    .collect()
598            };
599
600            // TODO: investigate if these configurations can be called in combination
601            // for the same layer
602            let mut connections = if self.override_last_ancestors {
603                self.configure_specifed_ancestors()
604            } else if self.fully_linked_ancestors {
605                self.configure_fully_linked_ancestors(round)
606            } else if self.min_ancestor_links {
607                self.configure_min_parent_links(round)
608            } else if self.no_leader_link {
609                self.configure_no_leader_links(authorities.clone(), round)
610            } else if self.skip_ancestor_links.is_some() {
611                self.configure_skipped_ancestor_links(
612                    authorities,
613                    self.skip_ancestor_links.clone().unwrap(),
614                )
615            } else {
616                vec![]
617            };
618
619            if self.random_weak_links {
620                connections.append(&mut self.configure_random_weak_links());
621            }
622
623            self.create_blocks(round, connections);
624        }
625
626        self.dag_builder.last_ancestors = self.ancestors.clone();
627        self
628    }
629
630    pub fn persist_layers(&self, dag_state: Arc<RwLock<DagState>>) {
631        assert!(
632            !self.blocks.is_empty(),
633            "Called to persist layers although no blocks have been created. Make sure you have called build before."
634        );
635        dag_state.write().accept_blocks(self.blocks.clone());
636    }
637
638    // Layer round is minimally and randomly connected with ancestors.
639    pub fn configure_min_parent_links(
640        &mut self,
641        round: Round,
642    ) -> Vec<(AuthorityIndex, Vec<BlockRef>)> {
643        let quorum_threshold = self.dag_builder.context.committee.quorum_threshold() as usize;
644        let authorities: Vec<AuthorityIndex> = self
645            .dag_builder
646            .context
647            .committee
648            .authorities()
649            .map(|authority| authority.0)
650            .collect();
651
652        let mut rng = match self.min_ancestor_links_random_seed {
653            Some(s) => StdRng::seed_from_u64(s),
654            None => StdRng::from_entropy(),
655        };
656
657        let mut authorities_to_shuffle = authorities.clone();
658
659        let mut leaders = vec![];
660        if let Some(leader_round) = self.leader_round {
661            let leader_offsets = (0..self.dag_builder.number_of_leaders).collect::<Vec<_>>();
662
663            for leader_offset in leader_offsets {
664                leaders.push(
665                    self.dag_builder
666                        .leader_schedule
667                        .elect_leader(leader_round, leader_offset),
668                );
669            }
670        }
671
672        authorities
673            .iter()
674            .map(|authority| {
675                authorities_to_shuffle.shuffle(&mut rng);
676
677                // TODO: handle quroum threshold properly with stake
678                let min_ancestors: HashSet<AuthorityIndex> = authorities_to_shuffle
679                    .iter()
680                    .take(quorum_threshold)
681                    .cloned()
682                    .collect();
683
684                (
685                    *authority,
686                    self.ancestors
687                        .iter()
688                        .filter(|a| {
689                            leaders.contains(&a.author)
690                                || min_ancestors.contains(&a.author)
691                                || a.round != round
692                        })
693                        .cloned()
694                        .collect::<Vec<BlockRef>>(),
695                )
696            })
697            .collect()
698    }
699
700    // TODO: configure layer round randomly connected with weak links.
701    fn configure_random_weak_links(&mut self) -> Vec<(AuthorityIndex, Vec<BlockRef>)> {
702        unimplemented!("configure_random_weak_links");
703    }
704
705    // Layer round misses link to leader, but other blocks are fully connected with ancestors.
706    fn configure_no_leader_links(
707        &mut self,
708        authorities: Vec<AuthorityIndex>,
709        _round: Round,
710    ) -> Vec<(AuthorityIndex, Vec<BlockRef>)> {
711        let mut missing_leaders = Vec::new();
712        let mut specified_leader_offsets = self
713            .specified_leader_link_offsets
714            .clone()
715            .expect("specified_leader_offsets should be set");
716        let leader_round = self.leader_round.expect("leader round should be set");
717
718        // When no specified leader offsets are available, all leaders are
719        // expected to be missing.
720        if specified_leader_offsets.is_empty() {
721            specified_leader_offsets.extend(0..self.dag_builder.number_of_leaders);
722        }
723
724        for leader_offset in specified_leader_offsets {
725            missing_leaders.push(
726                self.dag_builder
727                    .leader_schedule
728                    .elect_leader(leader_round, leader_offset),
729            );
730        }
731
732        self.configure_skipped_ancestor_links(authorities, missing_leaders)
733    }
734
735    fn configure_specifed_ancestors(&mut self) -> Vec<(AuthorityIndex, Vec<BlockRef>)> {
736        self.dag_builder
737            .context
738            .committee
739            .authorities()
740            .map(|authority| (authority.0, self.specified_ancestors.clone()))
741            .collect::<Vec<_>>()
742    }
743
744    fn configure_fully_linked_ancestors(
745        &mut self,
746        round: Round,
747    ) -> Vec<(AuthorityIndex, Vec<BlockRef>)> {
748        self.dag_builder
749            .context
750            .committee
751            .authorities()
752            .map(|authority| {
753                (
754                    authority.0,
755                    // don't connect to ancestors of this round
756                    self.ancestors
757                        .clone()
758                        .into_iter()
759                        .filter(|a| a.round != round)
760                        .collect::<Vec<_>>(),
761                )
762            })
763            .collect::<Vec<_>>()
764    }
765
766    fn configure_skipped_ancestor_links(
767        &mut self,
768        authorities: Vec<AuthorityIndex>,
769        ancestors_to_skip: Vec<AuthorityIndex>,
770    ) -> Vec<(AuthorityIndex, Vec<BlockRef>)> {
771        let filtered_ancestors = self
772            .ancestors
773            .clone()
774            .into_iter()
775            .filter(|ancestor| !ancestors_to_skip.contains(&ancestor.author))
776            .collect::<Vec<_>>();
777        authorities
778            .into_iter()
779            .map(|authority| (authority, filtered_ancestors.clone()))
780            .collect::<Vec<_>>()
781    }
782
783    // Creates the blocks for the new layer based on configured connections, also
784    // sets the ancestors for future layers to be linked to
785    fn create_blocks(&mut self, round: Round, connections: Vec<(AuthorityIndex, Vec<BlockRef>)>) {
786        let mut references = Vec::new();
787        let mut reject_rng =
788            StdRng::seed_from_u64(self.rejected_transactions_seed ^ (round as u64));
789        for (authority, ancestors) in connections {
790            if self.should_skip_block(round, authority) {
791                continue;
792            };
793            let transactions = (0..self.num_transactions)
794                .map(|_| Transaction::new(vec![1_u8; 16]))
795                .collect::<Vec<_>>();
796            let num_blocks = self.num_blocks_to_create(authority);
797            for num_block in 0..num_blocks {
798                let mut votes = vec![];
799                if self.rejected_transactions_pct > 0 {
800                    for ancestor in &ancestors {
801                        let mut rejects = vec![];
802                        for i in 0..self.num_transactions {
803                            if reject_rng.gen_range(1..=100) <= self.rejected_transactions_pct {
804                                rejects.push(i as TransactionIndex);
805                            }
806                        }
807                        if !rejects.is_empty() {
808                            votes.push(BlockTransactionVotes {
809                                block_ref: *ancestor,
810                                rejects,
811                            });
812                        }
813                    }
814                }
815                let timestamp = self.block_timestamp(authority, round, num_block);
816                let block = VerifiedBlock::new_for_test(
817                    TestBlock::new(round, authority.value() as u32)
818                        .set_transactions(transactions.clone())
819                        .set_transaction_votes(votes)
820                        .set_ancestors(ancestors.clone())
821                        .set_timestamp_ms(timestamp)
822                        .build(),
823                );
824                references.push(block.reference());
825                self.dag_builder
826                    .blocks
827                    .insert(block.reference(), block.clone());
828                self.blocks.push(block);
829            }
830        }
831        self.ancestors = references;
832    }
833
834    fn num_blocks_to_create(&self, authority: AuthorityIndex) -> u32 {
835        if self.specified_authorities.is_some()
836            && self
837                .specified_authorities
838                .clone()
839                .unwrap()
840                .contains(&authority)
841        {
842            // Always create 1 block and then the equivocating blocks on top of that.
843            1 + self.equivocations as u32
844        } else {
845            1
846        }
847    }
848
849    fn block_timestamp(
850        &self,
851        authority: AuthorityIndex,
852        round: Round,
853        num_block: u32,
854    ) -> BlockTimestampMs {
855        if let Some(specified_authorities) = self.specified_authorities.as_ref()
856            && !self.timestamps.is_empty()
857            && let Some(position) = specified_authorities.iter().position(|&x| x == authority)
858        {
859            return self.timestamps[position] + (round + num_block) as u64;
860        }
861        let author = authority.value() as u32;
862        let base_ts = round as BlockTimestampMs * 1000;
863        base_ts + (author + round + num_block) as u64
864    }
865
866    fn should_skip_block(&self, round: Round, authority: AuthorityIndex) -> bool {
867        // Safe to unwrap as specified authorites has to be set before skip
868        // is specified.
869        if self.skip_block
870            && self
871                .specified_authorities
872                .clone()
873                .unwrap()
874                .contains(&authority)
875        {
876            return true;
877        }
878        if self.no_leader_block {
879            let mut specified_leader_offsets = self
880                .specified_leader_block_offsets
881                .clone()
882                .expect("specified_leader_block_offsets should be set");
883
884            // When no specified leader offsets are available, all leaders are
885            // expected to be skipped.
886            if specified_leader_offsets.is_empty() {
887                specified_leader_offsets.extend(0..self.dag_builder.number_of_leaders);
888            }
889
890            for leader_offset in specified_leader_offsets {
891                let leader = self
892                    .dag_builder
893                    .leader_schedule
894                    .elect_leader(round, leader_offset);
895
896                if leader == authority {
897                    return true;
898                }
899            }
900        }
901        false
902    }
903}
consensus_core/test_dag_builder.rs

consensus_core/
test_dag_builder.rs
