commonware_consensus/simplex/
elector.rs

1//! Leader election strategies for simplex consensus.
2//!
3//! This module provides the [`Config`] and [`Elector`] traits for customizing
4//! how leaders are selected for each consensus round, along with built-in implementations.
5//!
6//! # Built-in Electors
7//!
8//! - [`RoundRobin`]/[`RoundRobinElector`]: Deterministic rotation through participants
9//!   based on view number. Optionally shuffled using a seed. Works with any signing scheme.
10//!
11//! - [`Random`]/[`RandomElector`]: Uses randomness derived from BLS threshold signatures
12//!   for unpredictable leader selection. Falls back to round-robin for the first view
13//!   (no certificate available). Only works with [`bls12381_threshold`].
14//!
15//! # Custom Electors
16//!
17//! Applications can implement [`Config`] and [`Elector`] for custom leader
18//! selection logic such as stake-weighted selection or other application-specific strategies.
19//!
20//! # Usage
21//!
22//! This module uses a type-state pattern to ensure correct usage:
23//! 1. Users create an elector [`Config`] (e.g., [`RoundRobin`])
24//! 2. The config is passed to the consensus configuration
25//! 3. Consensus calls [`Config::build`] internally with the correct participants
26//! 4. The resulting [`Elector`] can only be created by consensus, preventing misuse
27
28use crate::{
29    simplex::scheme::bls12381_threshold,
30    types::{Round, View},
31};
32use commonware_codec::Encode;
33use commonware_cryptography::{
34    bls12381::primitives::variant::Variant, certificate::Scheme, Hasher, PublicKey, Sha256,
35};
36use commonware_utils::{modulo, ordered::Set};
37use std::marker::PhantomData;
38
39/// Configuration for creating an [`Elector`].
40///
41/// Users create and configure this type, then pass it to the consensus configuration.
42/// Consensus will call [`build`](Config::build) internally with the correct
43/// participant set to create the initialized [`Elector`].
44///
45/// # Determinism Requirement
46///
47/// Implementations **must** be deterministic: given the same construction parameters
48/// and the same inputs to [`Elector::elect`], the method must always return
49/// the same leader index. This is critical for consensus correctness - all honest
50/// participants must agree on the leader for each round.
51pub trait Config<S: Scheme>: Clone + Default + Send + 'static {
52    /// The initialized elector type.
53    type Elector: Elector<S>;
54
55    /// Builds the elector with the given participants.
56    ///
57    /// Called internally by consensus with the correct participant set.
58    ///
59    /// # Panics
60    ///
61    /// Implementations should panic if `participants` is empty.
62    fn build(self, participants: &Set<S::PublicKey>) -> Self::Elector;
63}
64
65/// An initialized elector that can select leaders for consensus rounds.
66///
67/// This type can only be created via [`Config::build`], which is called
68/// internally by consensus. This ensures the elector is always initialized with
69/// the correct participant set.
70///
71/// # Certificate Handling
72///
73/// The `certificate` parameter to [`elect`](Elector::elect) is `None` only for
74/// view 1 (the first view after genesis). For all subsequent views, a certificate
75/// from the previous view is provided. Implementations can use the certificate to
76/// derive randomness (like [`RandomElector`]) or ignore it entirely (like [`RoundRobinElector`]).
77pub trait Elector<S: Scheme>: Clone + Send + 'static {
78    /// Selects the leader for the given round.
79    ///
80    /// This method **must** be a pure function given the elector's initialization state.
81    ///
82    /// The `certificate` is expected to be `None` only for view 1.
83    ///
84    /// Returns the index of the selected leader in the participants list.
85    fn elect(&self, round: Round, certificate: Option<&S::Certificate>) -> u32;
86}
87
88/// Configuration for round-robin leader election.
89///
90/// Rotates through participants based on `(epoch + view) % num_participants`.
91/// The rotation order can be shuffled at construction using a seed.
92///
93/// Works with any signing scheme.
94#[derive(Clone, Debug, Default)]
95pub struct RoundRobin<H: Hasher = Sha256> {
96    seed: Option<Vec<u8>>,
97    _phantom: PhantomData<H>,
98}
99
100impl<H: Hasher> RoundRobin<H> {
101    /// Creates a round-robin config that will shuffle the rotation order based on seed.
102    ///
103    /// The seed is used during [`Config::build`] to deterministically
104    /// shuffle the permutation.
105    pub fn shuffled(seed: &[u8]) -> Self {
106        Self {
107            seed: Some(seed.to_vec()),
108            _phantom: PhantomData,
109        }
110    }
111}
112
113impl<S: Scheme, H: Hasher> Config<S> for RoundRobin<H> {
114    type Elector = RoundRobinElector<S>;
115
116    fn build(self, participants: &Set<S::PublicKey>) -> RoundRobinElector<S> {
117        assert!(!participants.is_empty(), "no participants");
118
119        let mut permutation: Vec<u32> = (0..participants.len() as u32).collect();
120
121        if let Some(seed) = &self.seed {
122            let mut hasher = H::new();
123            permutation.sort_by_key(|&index| {
124                hasher.update(seed);
125                hasher.update(&index.encode());
126                hasher.finalize()
127            });
128        }
129
130        RoundRobinElector {
131            permutation,
132            _phantom: PhantomData,
133        }
134    }
135}
136
137/// Initialized round-robin leader elector.
138///
139/// Created via [`RoundRobin::build`].
140#[derive(Clone, Debug)]
141pub struct RoundRobinElector<S: Scheme> {
142    permutation: Vec<u32>,
143    _phantom: PhantomData<S>,
144}
145
146impl<S: Scheme> Elector<S> for RoundRobinElector<S> {
147    fn elect(&self, round: Round, _certificate: Option<&S::Certificate>) -> u32 {
148        let n = self.permutation.len();
149        let idx = (round.epoch().get().wrapping_add(round.view().get())) as usize % n;
150        self.permutation[idx]
151    }
152}
153
154/// Configuration for leader election using threshold signature randomness.
155///
156/// Uses the seed signature from BLS threshold certificates to derive unpredictable
157/// leader selection. Falls back to standard round-robin for view 1 when no
158/// certificate is available.
159///
160/// Only works with [`bls12381_threshold`] signing scheme.
161#[derive(Clone, Debug, Default)]
162pub struct Random;
163
164impl Random {
165    /// Returns the selected leader index for the given round and seed signature.
166    pub fn select_leader<V: Variant>(
167        round: Round,
168        n: usize,
169        seed_signature: Option<V::Signature>,
170    ) -> u32 {
171        assert!(seed_signature.is_some() || round.view() == View::new(1));
172
173        let Some(seed_signature) = seed_signature else {
174            // Standard round-robin for view 1
175            return (round.epoch().get().wrapping_add(round.view().get()) as usize % n) as u32;
176        };
177
178        // Use the seed signature as a source of randomness
179        modulo(seed_signature.encode().as_ref(), n as u64) as u32
180    }
181}
182
183impl<P, V> Config<bls12381_threshold::Scheme<P, V>> for Random
184where
185    P: PublicKey,
186    V: Variant + Send + Sync + 'static,
187{
188    type Elector = RandomElector<bls12381_threshold::Scheme<P, V>>;
189
190    fn build(self, participants: &Set<P>) -> RandomElector<bls12381_threshold::Scheme<P, V>> {
191        assert!(!participants.is_empty(), "no participants");
192        RandomElector {
193            n: participants.len(),
194            _phantom: PhantomData,
195        }
196    }
197}
198
199/// Initialized random leader elector using threshold signature randomness.
200///
201/// Created via [`Random::build`].
202#[derive(Clone, Debug)]
203pub struct RandomElector<S: Scheme> {
204    n: usize,
205    _phantom: PhantomData<S>,
206}
207
208impl<P, V> Elector<bls12381_threshold::Scheme<P, V>>
209    for RandomElector<bls12381_threshold::Scheme<P, V>>
210where
211    P: PublicKey,
212    V: Variant + Send + Sync + 'static,
213{
214    fn elect(&self, round: Round, certificate: Option<&bls12381_threshold::Signature<V>>) -> u32 {
215        Random::select_leader::<V>(round, self.n, certificate.map(|c| c.seed_signature))
216    }
217}
218
219#[cfg(test)]
220mod tests {
221    use super::*;
222    use crate::{
223        simplex::{
224            scheme::{bls12381_threshold, ed25519},
225            types::Subject,
226        },
227        types::{Epoch, View},
228    };
229    use commonware_cryptography::{
230        bls12381::primitives::variant::MinPk, certificate::mocks::Fixture,
231        sha256::Digest as Sha256Digest, Sha256,
232    };
233    use commonware_utils::{quorum_from_slice, TryFromIterator};
234    use rand::{rngs::StdRng, SeedableRng};
235
236    type ThresholdScheme =
237        bls12381_threshold::Scheme<commonware_cryptography::ed25519::PublicKey, MinPk>;
238
239    #[test]
240    fn round_robin_rotates_through_participants() {
241        let mut rng = StdRng::seed_from_u64(42);
242        let Fixture { participants, .. } = ed25519::fixture(&mut rng, 4);
243        let participants = Set::try_from_iter(participants).unwrap();
244        let n = participants.len();
245        let elector: RoundRobinElector<ed25519::Scheme> =
246            RoundRobin::<Sha256>::default().build(&participants);
247        let epoch = Epoch::new(0);
248
249        // Run through 3 * n views, record the sequence of leaders
250        let mut leaders = Vec::new();
251        for view in 1..=(3 * n as u64) {
252            let round = Round::new(epoch, View::new(view));
253            leaders.push(elector.elect(round, None));
254        }
255
256        // Verify leaders cycle: consecutive leaders differ by 1 (mod n)
257        for i in 0..leaders.len() - 1 {
258            assert_eq!((leaders[i] + 1) % n as u32, leaders[i + 1]);
259        }
260    }
261
262    #[test]
263    fn round_robin_cycles_through_epochs() {
264        let mut rng = StdRng::seed_from_u64(42);
265        let Fixture { participants, .. } = ed25519::fixture(&mut rng, 5);
266        let participants = Set::try_from_iter(participants).unwrap();
267        let n = participants.len();
268        let elector: RoundRobinElector<ed25519::Scheme> =
269            RoundRobin::<Sha256>::default().build(&participants);
270
271        // Record leader for view 1 of epochs 0..n
272        let leaders: Vec<_> = (0..n as u64)
273            .map(|e| {
274                let round = Round::new(Epoch::new(e), View::new(1));
275                elector.elect(round, None)
276            })
277            .collect();
278
279        // Each participant should be selected exactly once
280        let mut seen = vec![false; n];
281        for &leader in &leaders {
282            assert!(!seen[leader as usize]);
283            seen[leader as usize] = true;
284        }
285        assert!(seen.iter().all(|x| *x));
286    }
287
288    #[test]
289    fn round_robin_shuffled_changes_order() {
290        let mut rng = StdRng::seed_from_u64(42);
291        let Fixture { participants, .. } = ed25519::fixture(&mut rng, 5);
292        let participants = Set::try_from_iter(participants).unwrap();
293
294        let elector_no_seed: RoundRobinElector<ed25519::Scheme> =
295            RoundRobin::<Sha256>::default().build(&participants);
296        let elector_seed_1: RoundRobinElector<ed25519::Scheme> =
297            RoundRobin::<Sha256>::shuffled(b"seed1").build(&participants);
298        let elector_seed_2: RoundRobinElector<ed25519::Scheme> =
299            RoundRobin::<Sha256>::shuffled(b"seed2").build(&participants);
300
301        // Collect first 5 leaders from each
302        let epoch = Epoch::new(0);
303        let leaders_no_seed: Vec<_> = (1..=5)
304            .map(|v| elector_no_seed.elect(Round::new(epoch, View::new(v)), None))
305            .collect();
306        let leaders_seed_1: Vec<_> = (1..=5)
307            .map(|v| elector_seed_1.elect(Round::new(epoch, View::new(v)), None))
308            .collect();
309        let leaders_seed_2: Vec<_> = (1..=5)
310            .map(|v| elector_seed_2.elect(Round::new(epoch, View::new(v)), None))
311            .collect();
312
313        // No seed should be identity permutation
314        assert_eq!(leaders_no_seed, vec![1, 2, 3, 4, 0]);
315
316        // Different seeds should produce different permutations
317        assert_ne!(leaders_seed_1, leaders_no_seed);
318        assert_ne!(leaders_seed_2, leaders_no_seed);
319        assert_ne!(leaders_seed_1, leaders_seed_2);
320
321        // Each permutation should still cover all participants
322        for leaders in [&leaders_seed_1, &leaders_seed_2] {
323            let mut sorted = leaders.clone();
324            sorted.sort();
325            assert_eq!(sorted, vec![0, 1, 2, 3, 4]);
326        }
327    }
328
329    #[test]
330    fn round_robin_same_seed_is_deterministic() {
331        let mut rng = StdRng::seed_from_u64(42);
332        let Fixture { participants, .. } = ed25519::fixture(&mut rng, 5);
333        let participants = Set::try_from_iter(participants).unwrap();
334
335        let elector1: RoundRobinElector<ed25519::Scheme> =
336            RoundRobin::<Sha256>::shuffled(b"same_seed").build(&participants);
337        let elector2: RoundRobinElector<ed25519::Scheme> =
338            RoundRobin::<Sha256>::shuffled(b"same_seed").build(&participants);
339
340        let epoch = Epoch::new(0);
341        for view in 1..=10 {
342            let round = Round::new(epoch, View::new(view));
343            assert_eq!(elector1.elect(round, None), elector2.elect(round, None));
344        }
345    }
346
347    #[test]
348    #[should_panic(expected = "no participants")]
349    fn round_robin_build_panics_on_empty_participants() {
350        let participants: Set<commonware_cryptography::ed25519::PublicKey> = Set::default();
351        let _: RoundRobinElector<ed25519::Scheme> =
352            RoundRobin::<Sha256>::default().build(&participants);
353    }
354
355    #[test]
356    fn random_falls_back_to_round_robin_for_view_1() {
357        let mut rng = StdRng::seed_from_u64(42);
358        let Fixture { participants, .. } = bls12381_threshold::fixture::<MinPk, _>(&mut rng, 5);
359        let participants = Set::try_from_iter(participants).unwrap();
360        let n = participants.len();
361        let elector: RandomElector<ThresholdScheme> = Random.build(&participants);
362
363        // For view 1 (no certificate), Random should behave like RoundRobin
364        let leaders: Vec<_> = (0..n as u64)
365            .map(|e| {
366                let round = Round::new(Epoch::new(e), View::new(1));
367                elector.elect(round, None)
368            })
369            .collect();
370
371        // Each participant should be selected exactly once (same as RoundRobin)
372        let mut seen = vec![false; n];
373        for &leader in &leaders {
374            assert!(!seen[leader as usize]);
375            seen[leader as usize] = true;
376        }
377        assert!(seen.iter().all(|x| *x));
378    }
379
380    #[test]
381    fn random_uses_certificate_randomness() {
382        let mut rng = StdRng::seed_from_u64(42);
383        let Fixture {
384            participants,
385            schemes,
386            ..
387        } = bls12381_threshold::fixture::<MinPk, _>(&mut rng, 5);
388        let participants = Set::try_from_iter(participants).unwrap();
389        let elector: RandomElector<ThresholdScheme> = Random.build(&participants);
390        let quorum = quorum_from_slice(&schemes) as usize;
391
392        // Create certificate for round (1, 2)
393        let round1 = Round::new(Epoch::new(1), View::new(2));
394        let attestations1: Vec<_> = schemes
395            .iter()
396            .take(quorum)
397            .map(|s| {
398                s.sign::<Sha256Digest>(b"test", Subject::Nullify { round: round1 })
399                    .unwrap()
400            })
401            .collect();
402        let cert1 = schemes[0].assemble(attestations1).unwrap();
403
404        // Create certificate for round (1, 3) (different round -> different seed signature)
405        let round2 = Round::new(Epoch::new(1), View::new(3));
406        let attestations2: Vec<_> = schemes
407            .iter()
408            .take(quorum)
409            .map(|s| {
410                s.sign::<Sha256Digest>(b"test", Subject::Nullify { round: round2 })
411                    .unwrap()
412            })
413            .collect();
414        let cert2 = schemes[0].assemble(attestations2).unwrap();
415
416        // Same certificate always gives same leader
417        let leader1a = elector.elect(round1, Some(&cert1));
418        let leader1b = elector.elect(round1, Some(&cert1));
419        assert_eq!(leader1a, leader1b);
420
421        // Different certificates produce different leaders
422        //
423        // NOTE: In general, different certificates could produce the same leader by chance.
424        // However, for our specific test inputs (rng seed 42, 5 participants), we've
425        // verified these produce different results.
426        let leader2 = elector.elect(round1, Some(&cert2));
427        assert_ne!(leader1a, leader2);
428    }
429
430    #[test]
431    #[should_panic(expected = "no participants")]
432    fn random_build_panics_on_empty_participants() {
433        let participants: Set<commonware_cryptography::ed25519::PublicKey> = Set::default();
434        let _: RandomElector<ThresholdScheme> = Random.build(&participants);
435    }
436
437    #[test]
438    #[should_panic]
439    fn random_panics_on_none_certificate_after_view_1() {
440        let mut rng = StdRng::seed_from_u64(42);
441        let Fixture { participants, .. } = bls12381_threshold::fixture::<MinPk, _>(&mut rng, 5);
442        let participants = Set::try_from_iter(participants).unwrap();
443        let elector: RandomElector<ThresholdScheme> = Random.build(&participants);
444
445        // View 2 requires a certificate
446        let round = Round::new(Epoch::new(1), View::new(2));
447        elector.elect(round, None);
448    }
449}
commonware_consensus/simplex/elector.rs

commonware_consensus/simplex/
elector.rs
