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
431#[allow(unused)]
432impl<'a> LayerBuilder<'a> {
433    fn new(dag_builder: &'a mut DagBuilder, start_round: Round) -> Self {
434        assert!(start_round > 0, "genesis round is created by default");
435        let ancestors = dag_builder.last_ancestors.clone();
436        Self {
437            dag_builder,
438            start_round,
439            end_round: None,
440            specified_authorities: None,
441            num_transactions: 0,
442            rejected_transactions_pct: 0,
443            rejected_transactions_seed: 0,
444            equivocations: 0,
445            skip_block: false,
446            skip_ancestor_links: None,
447            override_last_ancestors: false,
448            no_leader_link: false,
449            no_leader_block: false,
450            specified_leader_link_offsets: None,
451            specified_leader_block_offsets: None,
452            leader_round: None,
453            fully_linked_ancestors: true,
454            min_ancestor_links: false,
455            min_ancestor_links_random_seed: None,
456            random_weak_links: false,
457            random_weak_links_random_seed: None,
458            ancestors,
459            specified_ancestors: vec![],
460            timestamps: vec![],
461            blocks: vec![],
462        }
463    }
464
465    // Configuration methods
466
467    // If you try to add blocks to the same layer you will end up with the last
468    // ancestors replaced with blocks from the current layer. Use this method
469    // to override the last ancestors with the references you manually have kept.
470    pub fn override_last_ancestors(mut self, ancestors: Vec<BlockRef>) -> Self {
471        self.specified_ancestors = ancestors;
472        self.override_last_ancestors = true;
473        self.build()
474    }
475
476    // Only link 2f+1 random ancestors to the current layer round using a seed,
477    // if provided. Also provide a flag to guarantee the leader is included.
478    // note: configuration is terminal and layer will be built after this call.
479    pub fn min_ancestor_links(mut self, include_leader: bool, seed: Option<u64>) -> Self {
480        self.min_ancestor_links = true;
481        self.min_ancestor_links_random_seed = seed;
482        if include_leader {
483            self.leader_round = Some(self.ancestors.iter().max_by_key(|b| b.round).unwrap().round);
484        }
485        self.fully_linked_ancestors = false;
486        self.build()
487    }
488
489    // No links will be created between the specified ancestors and the specified
490    // authorities at the layer round.
491    // note: configuration is terminal and layer will be built after this call.
492    pub fn skip_ancestor_links(mut self, ancestors_to_skip: Vec<AuthorityIndex>) -> Self {
493        // authorities must be specified for this to apply
494        assert!(self.specified_authorities.is_some());
495        self.skip_ancestor_links = Some(ancestors_to_skip);
496        self.fully_linked_ancestors = false;
497        self.build()
498    }
499
500    // Add random weak links to the current layer round using a seed, if provided
501    pub fn random_weak_links(mut self, seed: Option<u64>) -> Self {
502        self.random_weak_links = true;
503        self.random_weak_links_random_seed = seed;
504        self
505    }
506
507    // Should be called when building a leader round. Will ensure leader block is missing.
508    // A list of specified leader offsets can be provided to skip those leaders.
509    // If none are provided all potential leaders for the round will be skipped.
510    pub fn no_leader_block(mut self, specified_leader_offsets: Vec<u32>) -> Self {
511        self.no_leader_block = true;
512        self.specified_leader_block_offsets = Some(specified_leader_offsets);
513        self
514    }
515
516    // Should be called when building a voting round. Will ensure vote is missing.
517    // A list of specified leader offsets can be provided to skip those leader links.
518    // If none are provided all potential leaders for the round will be skipped.
519    // note: configuration is terminal and layer will be built after this call.
520    pub fn no_leader_link(
521        mut self,
522        leader_round: Round,
523        specified_leader_offsets: Vec<u32>,
524    ) -> Self {
525        self.no_leader_link = true;
526        self.specified_leader_link_offsets = Some(specified_leader_offsets);
527        self.leader_round = Some(leader_round);
528        self.fully_linked_ancestors = false;
529        self.build()
530    }
531
532    pub fn authorities(mut self, authorities: Vec<AuthorityIndex>) -> Self {
533        assert!(
534            self.specified_authorities.is_none(),
535            "Specified authorities already set"
536        );
537        self.specified_authorities = Some(authorities);
538        self
539    }
540
541    // Number of transactions to include per block.
542    pub fn num_transactions(mut self, num_transactions: u32) -> Self {
543        self.num_transactions = num_transactions;
544        self
545    }
546
547    pub fn rejected_transactions_pct(mut self, pct: u8, seed: Option<u64>) -> Self {
548        self.rejected_transactions_pct = pct;
549        self.rejected_transactions_seed = if let Some(seed) = seed {
550            seed
551        } else {
552            thread_rng().r#gen()
553        };
554        self
555    }
556
557    // Multiple blocks will be created for the specified authorities at the layer round.
558    pub fn equivocate(mut self, equivocations: usize) -> Self {
559        // authorities must be specified for this to apply
560        assert!(self.specified_authorities.is_some());
561        self.equivocations = equivocations;
562        self
563    }
564
565    // No blocks will be created for the specified authorities at the layer round.
566    pub fn skip_block(mut self) -> Self {
567        // authorities must be specified for this to apply
568        assert!(self.specified_authorities.is_some());
569        self.skip_block = true;
570        self
571    }
572
573    pub fn with_timestamps(mut self, timestamps: Vec<BlockTimestampMs>) -> Self {
574        // authorities must be specified for this to apply
575        assert!(self.specified_authorities.is_some());
576        assert_eq!(
577            self.specified_authorities.as_ref().unwrap().len(),
578            timestamps.len(),
579            "Timestamps should be provided for each specified authority"
580        );
581        self.timestamps = timestamps;
582        self
583    }
584
585    // Apply the configurations & build the dag layer(s).
586    pub fn build(mut self) -> Self {
587        for round in self.start_round..=self.end_round.unwrap_or(self.start_round) {
588            tracing::debug!("BUILDING LAYER ROUND {round}...");
589
590            let authorities = if self.specified_authorities.is_some() {
591                self.specified_authorities.clone().unwrap()
592            } else {
593                self.dag_builder
594                    .context
595                    .committee
596                    .authorities()
597                    .map(|x| x.0)
598                    .collect()
599            };
600
601            // TODO: investigate if these configurations can be called in combination
602            // for the same layer
603            let mut connections = if self.override_last_ancestors {
604                self.configure_specifed_ancestors()
605            } else if self.fully_linked_ancestors {
606                self.configure_fully_linked_ancestors(round)
607            } else if self.min_ancestor_links {
608                self.configure_min_parent_links(round)
609            } else if self.no_leader_link {
610                self.configure_no_leader_links(authorities.clone(), round)
611            } else if self.skip_ancestor_links.is_some() {
612                self.configure_skipped_ancestor_links(
613                    authorities,
614                    self.skip_ancestor_links.clone().unwrap(),
615                )
616            } else {
617                vec![]
618            };
619
620            if self.random_weak_links {
621                connections.append(&mut self.configure_random_weak_links());
622            }
623
624            self.create_blocks(round, connections);
625        }
626
627        self.dag_builder.last_ancestors = self.ancestors.clone();
628        self
629    }
630
631    pub fn persist_layers(&self, dag_state: Arc<RwLock<DagState>>) {
632        assert!(
633            !self.blocks.is_empty(),
634            "Called to persist layers although no blocks have been created. Make sure you have called build before."
635        );
636        dag_state.write().accept_blocks(self.blocks.clone());
637    }
638
639    // Layer round is minimally and randomly connected with ancestors.
640    pub fn configure_min_parent_links(
641        &mut self,
642        round: Round,
643    ) -> Vec<(AuthorityIndex, Vec<BlockRef>)> {
644        let quorum_threshold = self.dag_builder.context.committee.quorum_threshold() as usize;
645        let mut authorities: Vec<AuthorityIndex> = self
646            .dag_builder
647            .context
648            .committee
649            .authorities()
650            .map(|authority| authority.0)
651            .collect();
652
653        let mut rng = match self.min_ancestor_links_random_seed {
654            Some(s) => StdRng::seed_from_u64(s),
655            None => StdRng::from_entropy(),
656        };
657
658        let mut authorities_to_shuffle = authorities.clone();
659
660        let mut leaders = vec![];
661        if let Some(leader_round) = self.leader_round {
662            let leader_offsets = (0..self.dag_builder.number_of_leaders).collect::<Vec<_>>();
663
664            for leader_offset in leader_offsets {
665                leaders.push(
666                    self.dag_builder
667                        .leader_schedule
668                        .elect_leader(leader_round, leader_offset),
669                );
670            }
671        }
672
673        authorities
674            .iter()
675            .map(|authority| {
676                authorities_to_shuffle.shuffle(&mut rng);
677
678                // TODO: handle quroum threshold properly with stake
679                let min_ancestors: HashSet<AuthorityIndex> = authorities_to_shuffle
680                    .iter()
681                    .take(quorum_threshold)
682                    .cloned()
683                    .collect();
684
685                (
686                    *authority,
687                    self.ancestors
688                        .iter()
689                        .filter(|a| {
690                            leaders.contains(&a.author)
691                                || min_ancestors.contains(&a.author)
692                                || a.round != round
693                        })
694                        .cloned()
695                        .collect::<Vec<BlockRef>>(),
696                )
697            })
698            .collect()
699    }
700
701    // TODO: configure layer round randomly connected with weak links.
702    fn configure_random_weak_links(&mut self) -> Vec<(AuthorityIndex, Vec<BlockRef>)> {
703        unimplemented!("configure_random_weak_links");
704    }
705
706    // Layer round misses link to leader, but other blocks are fully connected with ancestors.
707    fn configure_no_leader_links(
708        &mut self,
709        authorities: Vec<AuthorityIndex>,
710        round: Round,
711    ) -> Vec<(AuthorityIndex, Vec<BlockRef>)> {
712        let mut missing_leaders = Vec::new();
713        let mut specified_leader_offsets = self
714            .specified_leader_link_offsets
715            .clone()
716            .expect("specified_leader_offsets should be set");
717        let leader_round = self.leader_round.expect("leader round should be set");
718
719        // When no specified leader offsets are available, all leaders are
720        // expected to be missing.
721        if specified_leader_offsets.is_empty() {
722            specified_leader_offsets.extend(0..self.dag_builder.number_of_leaders);
723        }
724
725        for leader_offset in specified_leader_offsets {
726            missing_leaders.push(
727                self.dag_builder
728                    .leader_schedule
729                    .elect_leader(leader_round, leader_offset),
730            );
731        }
732
733        self.configure_skipped_ancestor_links(authorities, missing_leaders)
734    }
735
736    fn configure_specifed_ancestors(&mut self) -> Vec<(AuthorityIndex, Vec<BlockRef>)> {
737        self.dag_builder
738            .context
739            .committee
740            .authorities()
741            .map(|authority| (authority.0, self.specified_ancestors.clone()))
742            .collect::<Vec<_>>()
743    }
744
745    fn configure_fully_linked_ancestors(
746        &mut self,
747        round: Round,
748    ) -> Vec<(AuthorityIndex, Vec<BlockRef>)> {
749        self.dag_builder
750            .context
751            .committee
752            .authorities()
753            .map(|authority| {
754                (
755                    authority.0,
756                    // don't connect to ancestors of this round
757                    self.ancestors
758                        .clone()
759                        .into_iter()
760                        .filter(|a| a.round != round)
761                        .collect::<Vec<_>>(),
762                )
763            })
764            .collect::<Vec<_>>()
765    }
766
767    fn configure_skipped_ancestor_links(
768        &mut self,
769        authorities: Vec<AuthorityIndex>,
770        ancestors_to_skip: Vec<AuthorityIndex>,
771    ) -> Vec<(AuthorityIndex, Vec<BlockRef>)> {
772        let filtered_ancestors = self
773            .ancestors
774            .clone()
775            .into_iter()
776            .filter(|ancestor| !ancestors_to_skip.contains(&ancestor.author))
777            .collect::<Vec<_>>();
778        authorities
779            .into_iter()
780            .map(|authority| (authority, filtered_ancestors.clone()))
781            .collect::<Vec<_>>()
782    }
783
784    // Creates the blocks for the new layer based on configured connections, also
785    // sets the ancestors for future layers to be linked to
786    fn create_blocks(&mut self, round: Round, connections: Vec<(AuthorityIndex, Vec<BlockRef>)>) {
787        let mut references = Vec::new();
788        let mut reject_rng =
789            StdRng::seed_from_u64(self.rejected_transactions_seed ^ (round as u64));
790        for (authority, ancestors) in connections {
791            if self.should_skip_block(round, authority) {
792                continue;
793            };
794            let transactions = (0..self.num_transactions)
795                .map(|_| Transaction::new(vec![1_u8; 16]))
796                .collect::<Vec<_>>();
797            let num_blocks = self.num_blocks_to_create(authority);
798            for num_block in 0..num_blocks {
799                let mut votes = vec![];
800                if self.rejected_transactions_pct > 0 {
801                    for ancestor in &ancestors {
802                        let mut rejects = vec![];
803                        for i in 0..self.num_transactions {
804                            if reject_rng.gen_range(1..=100) <= self.rejected_transactions_pct {
805                                rejects.push(i as TransactionIndex);
806                            }
807                        }
808                        if !rejects.is_empty() {
809                            votes.push(BlockTransactionVotes {
810                                block_ref: *ancestor,
811                                rejects,
812                            });
813                        }
814                    }
815                }
816                let timestamp = self.block_timestamp(authority, round, num_block);
817                let block = VerifiedBlock::new_for_test(
818                    TestBlock::new(round, authority.value() as u32)
819                        .set_transactions(transactions.clone())
820                        .set_transaction_votes(votes)
821                        .set_ancestors(ancestors.clone())
822                        .set_timestamp_ms(timestamp)
823                        .build(),
824                );
825                references.push(block.reference());
826                self.dag_builder
827                    .blocks
828                    .insert(block.reference(), block.clone());
829                self.blocks.push(block);
830            }
831        }
832        self.ancestors = references;
833    }
834
835    fn num_blocks_to_create(&self, authority: AuthorityIndex) -> u32 {
836        if self.specified_authorities.is_some()
837            && self
838                .specified_authorities
839                .clone()
840                .unwrap()
841                .contains(&authority)
842        {
843            // Always create 1 block and then the equivocating blocks on top of that.
844            1 + self.equivocations as u32
845        } else {
846            1
847        }
848    }
849
850    fn block_timestamp(
851        &self,
852        authority: AuthorityIndex,
853        round: Round,
854        num_block: u32,
855    ) -> BlockTimestampMs {
856        if self.specified_authorities.is_some() && !self.timestamps.is_empty() {
857            let specified_authorities = self.specified_authorities.as_ref().unwrap();
858
859            if let Some(position) = specified_authorities.iter().position(|&x| x == authority) {
860                return self.timestamps[position] + (round + num_block) as u64;
861            }
862        }
863        let author = authority.value() as u32;
864        let base_ts = round as BlockTimestampMs * 1000;
865        base_ts + (author + round + num_block) as u64
866    }
867
868    fn should_skip_block(&self, round: Round, authority: AuthorityIndex) -> bool {
869        // Safe to unwrap as specified authorites has to be set before skip
870        // is specified.
871        if self.skip_block
872            && self
873                .specified_authorities
874                .clone()
875                .unwrap()
876                .contains(&authority)
877        {
878            return true;
879        }
880        if self.no_leader_block {
881            let mut specified_leader_offsets = self
882                .specified_leader_block_offsets
883                .clone()
884                .expect("specified_leader_block_offsets should be set");
885
886            // When no specified leader offsets are available, all leaders are
887            // expected to be skipped.
888            if specified_leader_offsets.is_empty() {
889                specified_leader_offsets.extend(0..self.dag_builder.number_of_leaders);
890            }
891
892            for leader_offset in specified_leader_offsets {
893                let leader = self
894                    .dag_builder
895                    .leader_schedule
896                    .elect_leader(round, leader_offset);
897
898                if leader == authority {
899                    return true;
900                }
901            }
902        }
903        false
904    }
905}
consensus_core/test_dag_builder.rs

consensus_core/
test_dag_builder.rs
