sp_domains/
extrinsics.rs

1#[cfg(not(feature = "std"))]
2extern crate alloc;
3
4#[cfg(not(feature = "std"))]
5use alloc::vec::Vec;
6use domain_runtime_primitives::opaque::AccountId;
7use rand_chacha::ChaCha8Rng;
8use rand_core::{Rng, SeedableRng};
9use sp_state_machine::trace;
10use sp_std::collections::btree_map::BTreeMap;
11use sp_std::collections::vec_deque::VecDeque;
12use sp_std::fmt::Debug;
13use subspace_core_primitives::Randomness;
14
15pub fn deduplicate_and_shuffle_extrinsics<Extrinsic>(
16    mut extrinsics: Vec<(Option<AccountId>, Extrinsic)>,
17    shuffling_seed: Randomness,
18) -> VecDeque<Extrinsic>
19where
20    Extrinsic: Debug + PartialEq + Clone,
21{
22    let mut seen = Vec::new();
23    extrinsics.retain(|(_, uxt)| match seen.contains(uxt) {
24        true => {
25            trace!(extrinsic = ?uxt, "Duplicated extrinsic");
26            false
27        }
28        false => {
29            seen.push(uxt.clone());
30            true
31        }
32    });
33    drop(seen);
34    trace!(?extrinsics, "Origin deduplicated extrinsics");
35    shuffle_extrinsics::<Extrinsic, AccountId>(extrinsics, shuffling_seed)
36}
37
38/// Shuffles the extrinsics in a deterministic way.
39///
40/// The extrinsics are grouped by the signer. The extrinsics without a signer, i.e., unsigned
41/// extrinsics, are considered as a special group. The items in different groups are cross shuffled,
42/// while the order of items inside the same group is still maintained.
43pub fn shuffle_extrinsics<Extrinsic: Debug, AccountId: Ord + Clone>(
44    extrinsics: Vec<(Option<AccountId>, Extrinsic)>,
45    shuffling_seed: Randomness,
46) -> VecDeque<Extrinsic> {
47    let mut rng = ChaCha8Rng::from_seed(*shuffling_seed);
48
49    let mut positions = extrinsics
50        .iter()
51        .map(|(maybe_signer, _)| maybe_signer)
52        .cloned()
53        .collect::<Vec<_>>();
54
55    shuffle(&mut positions, &mut rng);
56
57    let mut grouped_extrinsics: BTreeMap<Option<AccountId>, VecDeque<_>> = extrinsics
58        .into_iter()
59        .fold(BTreeMap::new(), |mut groups, (maybe_signer, tx)| {
60            groups.entry(maybe_signer).or_default().push_back(tx);
61            groups
62        });
63
64    // The relative ordering for the items in the same group does not change.
65    let shuffled_extrinsics = positions
66        .into_iter()
67        .map(|maybe_signer| {
68            grouped_extrinsics
69                .get_mut(&maybe_signer)
70                .expect("Extrinsics are grouped correctly; qed")
71                .pop_front()
72                .expect("Extrinsic definitely exists as it's correctly grouped above; qed")
73        })
74        .collect::<VecDeque<_>>();
75
76    trace!(?shuffled_extrinsics, "Shuffled extrinsics");
77
78    shuffled_extrinsics
79}
80
81/// Shuffles the slice using Fisher–Yates algorithm.
82///
83/// This is a consensus-critical function that must produce exactly the same output as
84/// `SliceRandom::shuffle()` from `rand` 0.8 did, independently of the `rand` version in use.
85fn shuffle<T>(slice: &mut [T], rng: &mut ChaCha8Rng) {
86    for i in (1..slice.len()).rev() {
87        // Invariant: elements with index > i have been locked in place
88        slice.swap(i, gen_index(rng, i + 1));
89    }
90}
91
92/// Uniformly samples an index in `0..ubound` using widening multiplication with rejection.
93fn gen_index(rng: &mut ChaCha8Rng, ubound: usize) -> usize {
94    if let Ok(ubound) = u32::try_from(ubound) {
95        let zone = (ubound << ubound.leading_zeros()).wrapping_sub(1);
96        loop {
97            let product = u64::from(rng.next_u32()) * u64::from(ubound);
98            if product as u32 <= zone {
99                return (product >> u32::BITS) as usize;
100            }
101        }
102    } else {
103        let ubound = ubound as u64;
104        let zone = (ubound << ubound.leading_zeros()).wrapping_sub(1);
105        loop {
106            let product = u128::from(rng.next_u64()) * u128::from(ubound);
107            if product as u64 <= zone {
108                return (product >> u64::BITS) as usize;
109            }
110        }
111    }
112}
sp_domains/extrinsics.rs

sp_domains/
extrinsics.rs
