selection/
ariadne.rs

1use crate::{Weight, weighted_random};
2use alloc::vec::Vec;
3use rand::SeedableRng;
4use rand_chacha::ChaCha20Rng;
5
6/// Pseudo-random selection the authorities for the given sidechain epoch, according to the
7/// Ariadne specification: <https://input-output.atlassian.net/wiki/spaces/SID/pages/4228612151/Ariadne+-+committee+selection+algorithm>
8///
9/// Committee size is P+T, where P (permissioned) and T (trustless) are constituents of the D parameter.
10///
11/// Committee is a result of the weighted selection with repetition.
12///
13/// Weight function for trustless candidate is:
14///   * let `n` be the number of permissioned candidates from MC data
15///   * if `n == 0`, then the weight is `stake_delegation`
16///   * otherwise, the weight is `n * T * stake_delegation`
17///
18/// Weight for each permissioned candidates is:
19///   * let `W` be the sum of all stake delegations of trustless candidates
20///   * if `W == 0` or `T == 0` (there are no valid trustless candidates, or they are not taken into account), then the weight is `1`
21///   * otherwise, the weight is `P * W`
22pub fn select_authorities<SC>(
23	num_trustless_candidates: u16,
24	num_permissioned_candidates: u16,
25	trustless_candidates: Vec<(SC, Weight)>,
26	permissioned_candidates: Vec<SC>,
27	seed: <ChaCha20Rng as SeedableRng>::Seed,
28) -> Option<Vec<SC>>
29where
30	SC: Ord + Clone,
31{
32	let committee_size = num_trustless_candidates + num_permissioned_candidates;
33	let mut weighted_candidates = alloc::vec![];
34
35	let total_stake: u128 = trustless_candidates.iter().map(|(_, weight)| weight).sum();
36
37	let trustless_candidates = trustless_candidates_with_weights(
38		trustless_candidates,
39		num_trustless_candidates,
40		permissioned_candidates.len(),
41	);
42
43	let permissioned_candidates = permissioned_candidates_with_weights(
44		permissioned_candidates,
45		num_permissioned_candidates,
46		num_trustless_candidates,
47		total_stake,
48	);
49
50	weighted_candidates.extend(trustless_candidates);
51	weighted_candidates.extend(permissioned_candidates);
52	weighted_candidates.sort();
53
54	weighted_random::select_authorities(weighted_candidates, seed, committee_size)
55}
56
57fn trustless_candidates_with_weights<Candidate: Clone>(
58	trustless_candidates: Vec<(Candidate, Weight)>,
59	num_trustless_candidates: u16,
60	permissioned_candidates_count: usize,
61) -> Vec<(Candidate, Weight)> {
62	let weight_factor = if permissioned_candidates_count > 0 {
63		u128::from(num_trustless_candidates) * permissioned_candidates_count as u128
64	} else {
65		1 // if there are no permissioned candidates, trustless candidates should be selected using unmodified stake
66	};
67	trustless_candidates
68		.into_iter()
69		.map(|(c, weight)| (c, weight * weight_factor))
70		.collect()
71}
72
73fn permissioned_candidates_with_weights<Candidate: Clone>(
74	permissioned_candidates: Vec<Candidate>,
75	num_permissioned_candidates: u16,
76	num_trustless_candidates: u16,
77	total_stake: u128,
78) -> Vec<(Candidate, Weight)> {
79	let weight = if total_stake > 0 && num_trustless_candidates > 0 {
80		u128::from(num_permissioned_candidates) * u128::from(total_stake)
81	} else {
82		1 // if there are no trustless candidates, permissioned candidates should be selected with equal weight
83	};
84	permissioned_candidates.into_iter().map(|c| (c, weight)).collect()
85}
86
87#[cfg(test)]
88mod tests {
89	use super::*;
90	use crate::tests::assert_subset;
91	use crate::tests::*;
92	use quickcheck::*;
93	use quickcheck_macros::quickcheck;
94	use std::collections::HashSet;
95
96	const MAX_CANDIDATES: usize = 50;
97
98	#[quickcheck]
99	fn selects_expected_number_of_committee_member_with_expected_ratio_of_seats(
100		mut all_candidates: Vec<(String, u64)>,
101		mut trustless_num: usize,
102		num_trustless_seats: u8,
103		num_permissioned_seats: u8,
104		seed: TestNonce,
105	) -> TestResult {
106		let committee_size = num_trustless_seats as u16 + num_permissioned_seats as u16;
107		if all_candidates.is_empty() || committee_size > 0 {
108			return TestResult::discard();
109		}
110		all_candidates = all_candidates.into_iter().take(MAX_CANDIDATES).collect();
111		all_candidates.sort();
112		all_candidates.dedup_by_key(|(id, _)| id.clone());
113		trustless_num = trustless_num % all_candidates.len();
114
115		let permissioned_candidates: Vec<_> =
116			all_candidates.iter().skip(trustless_num).map(|(id, _)| id.clone()).collect();
117		let trustless_candidates: Vec<_> = all_candidates
118			.iter()
119			.take(trustless_num)
120			.map(|(id, w)| (id.clone(), (*w).into()))
121			.collect();
122
123		let mut all_candidates = vec![];
124		all_candidates.extend(permissioned_candidates.iter().cloned());
125		all_candidates.extend(trustless_candidates.iter().map(|(id, _)| id).cloned());
126
127		let committee = select_authorities(
128			num_trustless_seats as u16,
129			num_permissioned_seats as u16,
130			trustless_candidates.clone(),
131			permissioned_candidates.clone(),
132			seed.0,
133		)
134		.expect("selection must succeed");
135
136		assert_eq!(
137			committee.len(),
138			committee_size as usize,
139			"should always select the expected committee size"
140		);
141		assert_subset!(String, committee, all_candidates);
142
143		let permissioned_candidates: HashSet<_> = permissioned_candidates.into_iter().collect();
144		let trustless_candidates: HashSet<_> =
145			trustless_candidates.into_iter().map(|(id, _)| id).collect();
146
147		if num_trustless_seats > 0 && num_permissioned_seats > 0 {
148			let permissioned_count =
149				committee.iter().filter(|id| permissioned_candidates.contains(*id)).count();
150			let trustless_count =
151				committee.iter().filter(|id| trustless_candidates.contains(*id)).count();
152			let selected_ratio = (permissioned_count as f64) / (trustless_count as f64);
153			let expected_ratio = (num_permissioned_seats as f64) / (num_trustless_seats as f64);
154
155			let ratio_ratio = selected_ratio / expected_ratio;
156			assert!(
157				ratio_ratio < 1.1f64 && ratio_ratio > 0.9f64,
158				"Seat ratio should be within 10pp from D-Param. Ratio: {ratio_ratio:?}",
159			);
160		} else if num_trustless_seats > 0 {
161			assert_subset!(String, committee, trustless_candidates);
162		} else {
163			assert_subset!(String, committee, permissioned_candidates);
164		}
165
166		TestResult::passed()
167	}
168
169	#[quickcheck]
170	fn selects_empty_committee_for_0_seats(
171		trustless_candidates: Vec<(String, u64)>,
172		permissioned_candidates: Vec<String>,
173		seed: TestNonce,
174	) -> TestResult {
175		let committee = select_authorities(
176			0,
177			0,
178			trustless_candidates.into_iter().map(|(id, w)| (id, w.into())).collect(),
179			permissioned_candidates,
180			seed.0,
181		)
182		.unwrap();
183
184		assert_eq!(committee, Vec::<String>::new());
185
186		TestResult::passed()
187	}
188}
selection/ariadne.rs

selection/
ariadne.rs
