polkadot_node_network_protocol/
grid_topology.rs

1// Copyright (C) Parity Technologies (UK) Ltd.
2// This file is part of Polkadot.
3
4// Polkadot is free software: you can redistribute it and/or modify
5// it under the terms of the GNU General Public License as published by
6// the Free Software Foundation, either version 3 of the License, or
7// (at your option) any later version.
8
9// Polkadot is distributed in the hope that it will be useful,
10// but WITHOUT ANY WARRANTY; without even the implied warranty of
11// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12// GNU General Public License for more details.
13
14// You should have received a copy of the GNU General Public License
15// along with Polkadot.  If not, see <http://www.gnu.org/licenses/>.
16
17//! Grid topology support implementation
18//! The basic operation of the 2D grid topology is that:
19//!   * A validator producing a message sends it to its row-neighbors and its column-neighbors
20//!   * A validator receiving a message originating from one of its row-neighbors sends it to its
21//!     column-neighbors
22//!   * A validator receiving a message originating from one of its column-neighbors sends it to its
23//!     row-neighbors
24//!
25//! This grid approach defines 2 unique paths for every validator to reach every other validator in
26//! at most 2 hops.
27//!
28//! However, we also supplement this with some degree of random propagation:
29//! every validator, upon seeing a message for the first time, propagates it to 8 random peers.
30//! This inserts some redundancy in case the grid topology isn't working or is being attacked -
31//! an adversary doesn't know which peers a validator will send to.
32//! This is combined with the property that the adversary doesn't know which validators will elect
33//! to check a block.
34
35use crate::PeerId;
36use polkadot_primitives::{AuthorityDiscoveryId, SessionIndex, ValidatorIndex};
37use rand::{CryptoRng, Rng};
38use std::{
39	collections::{hash_map, HashMap, HashSet},
40	fmt::Debug,
41};
42
43const LOG_TARGET: &str = "parachain::grid-topology";
44
45/// The sample rate for randomly propagating messages. This
46/// reduces the left tail of the binomial distribution but also
47/// introduces a bias towards peers who we sample before others
48/// (i.e. those who get a block before others).
49pub const DEFAULT_RANDOM_SAMPLE_RATE: usize = crate::MIN_GOSSIP_PEERS;
50
51/// The number of peers to randomly propagate messages to.
52pub const DEFAULT_RANDOM_CIRCULATION: usize = 4;
53
54/// Information about a peer in the gossip topology for a session.
55#[derive(Debug, Clone, PartialEq)]
56pub struct TopologyPeerInfo {
57	/// The validator's known peer IDs.
58	pub peer_ids: Vec<PeerId>,
59	/// The index of the validator in the discovery keys of the corresponding
60	/// `SessionInfo`. This can extend _beyond_ the set of active parachain validators.
61	pub validator_index: ValidatorIndex,
62	/// The authority discovery public key of the validator in the corresponding
63	/// `SessionInfo`.
64	pub discovery_id: AuthorityDiscoveryId,
65}
66
67/// Topology representation for a session.
68#[derive(Default, Clone, Debug, PartialEq)]
69pub struct SessionGridTopology {
70	/// An array mapping validator indices to their indices in the
71	/// shuffling itself. This has the same size as the number of validators
72	/// in the session.
73	shuffled_indices: Vec<usize>,
74	/// The canonical shuffling of validators for the session.
75	canonical_shuffling: Vec<TopologyPeerInfo>,
76	/// The list of peer-ids in an efficient way to search.
77	peer_ids: HashSet<PeerId>,
78}
79
80impl SessionGridTopology {
81	/// Create a new session grid topology.
82	pub fn new(shuffled_indices: Vec<usize>, canonical_shuffling: Vec<TopologyPeerInfo>) -> Self {
83		let mut peer_ids = HashSet::new();
84		for peer_info in canonical_shuffling.iter() {
85			for peer_id in peer_info.peer_ids.iter() {
86				peer_ids.insert(*peer_id);
87			}
88		}
89		SessionGridTopology { shuffled_indices, canonical_shuffling, peer_ids }
90	}
91
92	/// Updates the known peer ids for the passed authorities ids.
93	pub fn update_authority_ids(
94		&mut self,
95		peer_id: PeerId,
96		ids: &HashSet<AuthorityDiscoveryId>,
97	) -> bool {
98		let mut updated = false;
99		if !self.peer_ids.contains(&peer_id) {
100			for peer in self
101				.canonical_shuffling
102				.iter_mut()
103				.filter(|peer| ids.contains(&peer.discovery_id))
104			{
105				peer.peer_ids.push(peer_id);
106				self.peer_ids.insert(peer_id);
107				updated = true;
108			}
109		}
110		updated
111	}
112	/// Produces the outgoing routing logic for a particular peer.
113	///
114	/// Returns `None` if the validator index is out of bounds.
115	pub fn compute_grid_neighbors_for(&self, v: ValidatorIndex) -> Option<GridNeighbors> {
116		if self.shuffled_indices.len() != self.canonical_shuffling.len() {
117			return None
118		}
119		let shuffled_val_index = *self.shuffled_indices.get(v.0 as usize)?;
120
121		let neighbors = matrix_neighbors(shuffled_val_index, self.shuffled_indices.len())?;
122
123		let mut grid_subset = GridNeighbors::empty();
124		for r_n in neighbors.row_neighbors {
125			let n = &self.canonical_shuffling[r_n];
126			grid_subset.validator_indices_x.insert(n.validator_index);
127			for p in &n.peer_ids {
128				grid_subset.peers_x.insert(*p);
129			}
130		}
131
132		for c_n in neighbors.column_neighbors {
133			let n = &self.canonical_shuffling[c_n];
134			grid_subset.validator_indices_y.insert(n.validator_index);
135			for p in &n.peer_ids {
136				grid_subset.peers_y.insert(*p);
137			}
138		}
139
140		Some(grid_subset)
141	}
142
143	/// Tells if a given peer id is validator in a session
144	pub fn is_validator(&self, peer: &PeerId) -> bool {
145		self.peer_ids.contains(peer)
146	}
147}
148
149struct MatrixNeighbors<R, C> {
150	row_neighbors: R,
151	column_neighbors: C,
152}
153
154/// Compute the row and column neighbors of `val_index` in a matrix
155fn matrix_neighbors(
156	val_index: usize,
157	len: usize,
158) -> Option<MatrixNeighbors<impl Iterator<Item = usize>, impl Iterator<Item = usize>>> {
159	if val_index >= len {
160		return None
161	}
162
163	// e.g. for size 11 the matrix would be
164	//
165	// 0  1  2
166	// 3  4  5
167	// 6  7  8
168	// 9 10
169	//
170	// and for index 10, the neighbors would be 1, 4, 7, 9
171
172	let sqrt = (len as f64).sqrt() as usize;
173	let our_row = val_index / sqrt;
174	let our_column = val_index % sqrt;
175	let row_neighbors = our_row * sqrt..std::cmp::min(our_row * sqrt + sqrt, len);
176	let column_neighbors = (our_column..len).step_by(sqrt);
177
178	Some(MatrixNeighbors {
179		row_neighbors: row_neighbors.filter(move |i| *i != val_index),
180		column_neighbors: column_neighbors.filter(move |i| *i != val_index),
181	})
182}
183
184/// Information about the grid neighbors for a particular node in the topology.
185#[derive(Debug, Clone, PartialEq)]
186pub struct GridNeighbors {
187	/// Represent peers in the X axis
188	pub peers_x: HashSet<PeerId>,
189	/// Represent validators in the X axis
190	pub validator_indices_x: HashSet<ValidatorIndex>,
191	/// Represent peers in the Y axis
192	pub peers_y: HashSet<PeerId>,
193	/// Represent validators in the Y axis
194	pub validator_indices_y: HashSet<ValidatorIndex>,
195}
196
197impl GridNeighbors {
198	/// Utility function for creating an empty set of grid neighbors.
199	/// Useful for testing.
200	pub fn empty() -> Self {
201		GridNeighbors {
202			peers_x: HashSet::new(),
203			validator_indices_x: HashSet::new(),
204			peers_y: HashSet::new(),
205			validator_indices_y: HashSet::new(),
206		}
207	}
208
209	/// Given the originator of a message as a validator index, indicates the part of the topology
210	/// we're meant to send the message to.
211	pub fn required_routing_by_index(
212		&self,
213		originator: ValidatorIndex,
214		local: bool,
215	) -> RequiredRouting {
216		if local {
217			return RequiredRouting::GridXY
218		}
219
220		let grid_x = self.validator_indices_x.contains(&originator);
221		let grid_y = self.validator_indices_y.contains(&originator);
222
223		match (grid_x, grid_y) {
224			(false, false) => RequiredRouting::None,
225			(true, false) => RequiredRouting::GridY, // messages from X go to Y
226			(false, true) => RequiredRouting::GridX, // messages from Y go to X
227			(true, true) => RequiredRouting::GridXY, /* if the grid works as expected, this
228			                                           * shouldn't happen. */
229		}
230	}
231
232	/// Given the originator of a message as a peer index, indicates the part of the topology
233	/// we're meant to send the message to.
234	pub fn required_routing_by_peer_id(&self, originator: PeerId, local: bool) -> RequiredRouting {
235		if local {
236			return RequiredRouting::GridXY
237		}
238
239		let grid_x = self.peers_x.contains(&originator);
240		let grid_y = self.peers_y.contains(&originator);
241
242		match (grid_x, grid_y) {
243			(false, false) => RequiredRouting::None,
244			(true, false) => RequiredRouting::GridY, // messages from X go to Y
245			(false, true) => RequiredRouting::GridX, // messages from Y go to X
246			(true, true) => {
247				gum::debug!(
248					target: LOG_TARGET,
249					?originator,
250					"Grid topology is unexpected, play it safe and send to X AND Y"
251				);
252				RequiredRouting::GridXY
253			}, /* if the grid works as expected, this
254			                                           * shouldn't happen. */
255		}
256	}
257
258	/// Get a filter function based on this topology and the required routing
259	/// which returns `true` for peers that are within the required routing set
260	/// and false otherwise.
261	pub fn route_to_peer(&self, required_routing: RequiredRouting, peer: &PeerId) -> bool {
262		match required_routing {
263			RequiredRouting::All => true,
264			RequiredRouting::GridX => self.peers_x.contains(peer),
265			RequiredRouting::GridY => self.peers_y.contains(peer),
266			RequiredRouting::GridXY => self.peers_x.contains(peer) || self.peers_y.contains(peer),
267			RequiredRouting::None | RequiredRouting::PendingTopology => false,
268		}
269	}
270
271	/// Returns the difference between this and the `other` topology as a vector of peers
272	pub fn peers_diff(&self, other: &Self) -> Vec<PeerId> {
273		self.peers_x
274			.iter()
275			.chain(self.peers_y.iter())
276			.filter(|peer_id| !(other.peers_x.contains(peer_id) || other.peers_y.contains(peer_id)))
277			.cloned()
278			.collect::<Vec<_>>()
279	}
280
281	/// A convenience method that returns total number of peers in the topology
282	pub fn len(&self) -> usize {
283		self.peers_x.len().saturating_add(self.peers_y.len())
284	}
285}
286
287/// An entry tracking a session grid topology and some cached local neighbors.
288#[derive(Debug)]
289pub struct SessionGridTopologyEntry {
290	topology: SessionGridTopology,
291	local_neighbors: GridNeighbors,
292	local_index: Option<ValidatorIndex>,
293}
294
295impl SessionGridTopologyEntry {
296	/// Access the local grid neighbors.
297	pub fn local_grid_neighbors(&self) -> &GridNeighbors {
298		&self.local_neighbors
299	}
300
301	/// Access the local grid neighbors mutably.
302	pub fn local_grid_neighbors_mut(&mut self) -> &mut GridNeighbors {
303		&mut self.local_neighbors
304	}
305
306	/// Access the underlying topology.
307	pub fn get(&self) -> &SessionGridTopology {
308		&self.topology
309	}
310
311	/// Tells if a given peer id is validator in a session
312	pub fn is_validator(&self, peer: &PeerId) -> bool {
313		self.topology.is_validator(peer)
314	}
315
316	/// Returns the list of peers to route based on the required routing.
317	pub fn peers_to_route(&self, required_routing: RequiredRouting) -> Vec<PeerId> {
318		match required_routing {
319			RequiredRouting::All => self.topology.peer_ids.iter().copied().collect(),
320			RequiredRouting::GridX => self.local_neighbors.peers_x.iter().copied().collect(),
321			RequiredRouting::GridY => self.local_neighbors.peers_y.iter().copied().collect(),
322			RequiredRouting::GridXY => self
323				.local_neighbors
324				.peers_x
325				.iter()
326				.chain(self.local_neighbors.peers_y.iter())
327				.copied()
328				.collect(),
329			RequiredRouting::None | RequiredRouting::PendingTopology => Vec::new(),
330		}
331	}
332
333	/// Updates the known peer ids for the passed authorities ids.
334	pub fn update_authority_ids(
335		&mut self,
336		peer_id: PeerId,
337		ids: &HashSet<AuthorityDiscoveryId>,
338	) -> bool {
339		let peer_id_updated = self.topology.update_authority_ids(peer_id, ids);
340		// If we added a new peer id we need to recompute the grid neighbors, so that
341		// neighbors_x and neighbors_y reflect the right peer ids.
342		if peer_id_updated {
343			if let Some(local_index) = self.local_index.as_ref() {
344				if let Some(new_grid) = self.topology.compute_grid_neighbors_for(*local_index) {
345					self.local_neighbors = new_grid;
346				}
347			}
348		}
349		peer_id_updated
350	}
351}
352
353/// A set of topologies indexed by session
354#[derive(Default)]
355pub struct SessionGridTopologies {
356	inner: HashMap<SessionIndex, (Option<SessionGridTopologyEntry>, usize)>,
357}
358
359impl SessionGridTopologies {
360	/// Returns a topology for the specific session index
361	pub fn get_topology(&self, session: SessionIndex) -> Option<&SessionGridTopologyEntry> {
362		self.inner.get(&session).and_then(|val| val.0.as_ref())
363	}
364
365	/// Updates the known peer ids for the passed authorities ids.
366	pub fn update_authority_ids(
367		&mut self,
368		peer_id: PeerId,
369		ids: &HashSet<AuthorityDiscoveryId>,
370	) -> bool {
371		self.inner
372			.iter_mut()
373			.map(|(_, topology)| {
374				topology.0.as_mut().map(|topology| topology.update_authority_ids(peer_id, ids))
375			})
376			.any(|updated| updated.unwrap_or_default())
377	}
378
379	/// Increase references counter for a specific topology
380	pub fn inc_session_refs(&mut self, session: SessionIndex) {
381		self.inner.entry(session).or_insert((None, 0)).1 += 1;
382	}
383
384	/// Decrease references counter for a specific topology
385	pub fn dec_session_refs(&mut self, session: SessionIndex) {
386		if let hash_map::Entry::Occupied(mut occupied) = self.inner.entry(session) {
387			occupied.get_mut().1 = occupied.get().1.saturating_sub(1);
388			if occupied.get().1 == 0 {
389				let _ = occupied.remove();
390			}
391		}
392	}
393
394	/// Insert a new topology, no-op if already present.
395	pub fn insert_topology(
396		&mut self,
397		session: SessionIndex,
398		topology: SessionGridTopology,
399		local_index: Option<ValidatorIndex>,
400	) {
401		let entry = self.inner.entry(session).or_insert((None, 0));
402		if entry.0.is_none() {
403			let local_neighbors = local_index
404				.and_then(|l| topology.compute_grid_neighbors_for(l))
405				.unwrap_or_else(GridNeighbors::empty);
406
407			entry.0 = Some(SessionGridTopologyEntry { topology, local_neighbors, local_index });
408		}
409	}
410}
411
412/// A simple storage for a topology and the corresponding session index
413#[derive(Debug)]
414struct GridTopologySessionBound {
415	entry: SessionGridTopologyEntry,
416	session_index: SessionIndex,
417}
418
419/// A storage for the current and maybe previous topology
420#[derive(Debug)]
421pub struct SessionBoundGridTopologyStorage {
422	current_topology: GridTopologySessionBound,
423	prev_topology: Option<GridTopologySessionBound>,
424}
425
426impl Default for SessionBoundGridTopologyStorage {
427	fn default() -> Self {
428		// having this struct be `Default` is objectively stupid
429		// but used in a few places
430		SessionBoundGridTopologyStorage {
431			current_topology: GridTopologySessionBound {
432				// session 0 is valid so we should use the upper bound
433				// as the default instead of the lower bound.
434				session_index: SessionIndex::max_value(),
435				entry: SessionGridTopologyEntry {
436					topology: SessionGridTopology {
437						shuffled_indices: Vec::new(),
438						canonical_shuffling: Vec::new(),
439						peer_ids: Default::default(),
440					},
441					local_neighbors: GridNeighbors::empty(),
442					local_index: None,
443				},
444			},
445			prev_topology: None,
446		}
447	}
448}
449
450impl SessionBoundGridTopologyStorage {
451	/// Return a grid topology based on the session index:
452	/// If we need a previous session and it is registered in the storage, then return that session.
453	/// Otherwise, return a current session to have some grid topology in any case
454	pub fn get_topology_or_fallback(&self, idx: SessionIndex) -> &SessionGridTopologyEntry {
455		self.get_topology(idx).unwrap_or(&self.current_topology.entry)
456	}
457
458	/// Return the grid topology for the specific session index, if no such a session is stored
459	/// returns `None`.
460	pub fn get_topology(&self, idx: SessionIndex) -> Option<&SessionGridTopologyEntry> {
461		if let Some(prev_topology) = &self.prev_topology {
462			if idx == prev_topology.session_index {
463				return Some(&prev_topology.entry)
464			}
465		}
466		if self.current_topology.session_index == idx {
467			return Some(&self.current_topology.entry)
468		}
469
470		None
471	}
472
473	/// Update the current topology preserving the previous one
474	pub fn update_topology(
475		&mut self,
476		session_index: SessionIndex,
477		topology: SessionGridTopology,
478		local_index: Option<ValidatorIndex>,
479	) {
480		let local_neighbors = local_index
481			.and_then(|l| topology.compute_grid_neighbors_for(l))
482			.unwrap_or_else(GridNeighbors::empty);
483
484		let old_current = std::mem::replace(
485			&mut self.current_topology,
486			GridTopologySessionBound {
487				entry: SessionGridTopologyEntry { topology, local_neighbors, local_index },
488				session_index,
489			},
490		);
491		self.prev_topology.replace(old_current);
492	}
493
494	/// Returns a current grid topology
495	pub fn get_current_topology(&self) -> &SessionGridTopologyEntry {
496		&self.current_topology.entry
497	}
498
499	/// Access the current grid topology mutably. Dangerous and intended
500	/// to be used in tests.
501	pub fn get_current_topology_mut(&mut self) -> &mut SessionGridTopologyEntry {
502		&mut self.current_topology.entry
503	}
504}
505
506/// A representation of routing based on sample
507#[derive(Debug, Clone, Copy)]
508pub struct RandomRouting {
509	/// The number of peers to target.
510	target: usize,
511	/// The number of peers this has been sent to.
512	sent: usize,
513	/// Sampling rate
514	sample_rate: usize,
515}
516
517impl Default for RandomRouting {
518	fn default() -> Self {
519		RandomRouting {
520			target: DEFAULT_RANDOM_CIRCULATION,
521			sent: 0_usize,
522			sample_rate: DEFAULT_RANDOM_SAMPLE_RATE,
523		}
524	}
525}
526
527impl RandomRouting {
528	/// Perform random sampling for a specific peer
529	/// Returns `true` for a lucky peer
530	pub fn sample(&self, n_peers_total: usize, rng: &mut (impl CryptoRng + Rng)) -> bool {
531		if n_peers_total == 0 || self.sent >= self.target {
532			false
533		} else if self.sample_rate > n_peers_total {
534			true
535		} else {
536			rng.gen_ratio(self.sample_rate as _, n_peers_total as _)
537		}
538	}
539
540	/// Increase number of messages being sent
541	pub fn inc_sent(&mut self) {
542		self.sent += 1
543	}
544
545	/// Returns `true` if we already took all the necessary samples.
546	pub fn is_complete(&self) -> bool {
547		self.sent >= self.target
548	}
549}
550
551/// Routing mode
552#[derive(Debug, Clone, Copy, PartialEq)]
553pub enum RequiredRouting {
554	/// We don't know yet, because we're waiting for topology info
555	/// (race condition between learning about the first blocks in a new session
556	/// and getting the topology for that session)
557	PendingTopology,
558	/// Propagate to all peers of any kind.
559	All,
560	/// Propagate to all peers sharing either the X or Y dimension of the grid.
561	GridXY,
562	/// Propagate to all peers sharing the X dimension of the grid.
563	GridX,
564	/// Propagate to all peers sharing the Y dimension of the grid.
565	GridY,
566	/// No required propagation.
567	None,
568}
569
570impl RequiredRouting {
571	/// Whether the required routing set is definitely empty.
572	pub fn is_empty(self) -> bool {
573		match self {
574			RequiredRouting::PendingTopology | RequiredRouting::None => true,
575			_ => false,
576		}
577	}
578
579	/// Combine two required routing sets into one that would cover both routing modes.
580	pub fn combine(self, other: Self) -> Self {
581		match (self, other) {
582			(RequiredRouting::All, _) | (_, RequiredRouting::All) => RequiredRouting::All,
583			(RequiredRouting::GridXY, _) | (_, RequiredRouting::GridXY) => RequiredRouting::GridXY,
584			(RequiredRouting::GridX, RequiredRouting::GridY) |
585			(RequiredRouting::GridY, RequiredRouting::GridX) => RequiredRouting::GridXY,
586			(RequiredRouting::GridX, RequiredRouting::GridX) => RequiredRouting::GridX,
587			(RequiredRouting::GridY, RequiredRouting::GridY) => RequiredRouting::GridY,
588			(RequiredRouting::None, RequiredRouting::PendingTopology) |
589			(RequiredRouting::PendingTopology, RequiredRouting::None) => RequiredRouting::PendingTopology,
590			(RequiredRouting::None, _) | (RequiredRouting::PendingTopology, _) => other,
591			(_, RequiredRouting::None) | (_, RequiredRouting::PendingTopology) => self,
592		}
593	}
594}
595
596#[cfg(test)]
597mod tests {
598	use super::*;
599	use rand::SeedableRng;
600	use rand_chacha::ChaCha12Rng;
601
602	fn dummy_rng() -> ChaCha12Rng {
603		rand_chacha::ChaCha12Rng::seed_from_u64(12345)
604	}
605
606	#[test]
607	fn test_required_routing_combine() {
608		assert_eq!(RequiredRouting::All.combine(RequiredRouting::None), RequiredRouting::All);
609		assert_eq!(RequiredRouting::All.combine(RequiredRouting::GridXY), RequiredRouting::All);
610		assert_eq!(RequiredRouting::GridXY.combine(RequiredRouting::All), RequiredRouting::All);
611		assert_eq!(RequiredRouting::None.combine(RequiredRouting::All), RequiredRouting::All);
612		assert_eq!(RequiredRouting::None.combine(RequiredRouting::None), RequiredRouting::None);
613		assert_eq!(
614			RequiredRouting::PendingTopology.combine(RequiredRouting::GridX),
615			RequiredRouting::GridX
616		);
617
618		assert_eq!(
619			RequiredRouting::GridX.combine(RequiredRouting::PendingTopology),
620			RequiredRouting::GridX
621		);
622		assert_eq!(RequiredRouting::GridX.combine(RequiredRouting::GridY), RequiredRouting::GridXY);
623		assert_eq!(RequiredRouting::GridY.combine(RequiredRouting::GridX), RequiredRouting::GridXY);
624		assert_eq!(
625			RequiredRouting::GridXY.combine(RequiredRouting::GridXY),
626			RequiredRouting::GridXY
627		);
628		assert_eq!(RequiredRouting::GridX.combine(RequiredRouting::GridX), RequiredRouting::GridX);
629		assert_eq!(RequiredRouting::GridY.combine(RequiredRouting::GridY), RequiredRouting::GridY);
630
631		assert_eq!(RequiredRouting::None.combine(RequiredRouting::GridY), RequiredRouting::GridY);
632		assert_eq!(RequiredRouting::None.combine(RequiredRouting::GridX), RequiredRouting::GridX);
633		assert_eq!(RequiredRouting::None.combine(RequiredRouting::GridXY), RequiredRouting::GridXY);
634
635		assert_eq!(RequiredRouting::GridY.combine(RequiredRouting::None), RequiredRouting::GridY);
636		assert_eq!(RequiredRouting::GridX.combine(RequiredRouting::None), RequiredRouting::GridX);
637		assert_eq!(RequiredRouting::GridXY.combine(RequiredRouting::None), RequiredRouting::GridXY);
638
639		assert_eq!(
640			RequiredRouting::PendingTopology.combine(RequiredRouting::None),
641			RequiredRouting::PendingTopology
642		);
643
644		assert_eq!(
645			RequiredRouting::None.combine(RequiredRouting::PendingTopology),
646			RequiredRouting::PendingTopology
647		);
648	}
649
650	#[test]
651	fn test_random_routing_sample() {
652		// This test is fragile as it relies on a specific ChaCha12Rng
653		// sequence that might be implementation defined even for a static seed
654		let mut rng = dummy_rng();
655		let mut random_routing = RandomRouting { target: 4, sent: 0, sample_rate: 8 };
656
657		assert_eq!(random_routing.sample(16, &mut rng), true);
658		random_routing.inc_sent();
659		assert_eq!(random_routing.sample(16, &mut rng), false);
660		assert_eq!(random_routing.sample(16, &mut rng), false);
661		assert_eq!(random_routing.sample(16, &mut rng), true);
662		random_routing.inc_sent();
663		assert_eq!(random_routing.sample(16, &mut rng), true);
664		random_routing.inc_sent();
665		assert_eq!(random_routing.sample(16, &mut rng), false);
666		assert_eq!(random_routing.sample(16, &mut rng), false);
667		assert_eq!(random_routing.sample(16, &mut rng), false);
668		assert_eq!(random_routing.sample(16, &mut rng), true);
669		random_routing.inc_sent();
670
671		for _ in 0..16 {
672			assert_eq!(random_routing.sample(16, &mut rng), false);
673		}
674	}
675
676	fn run_random_routing(
677		random_routing: &mut RandomRouting,
678		rng: &mut (impl CryptoRng + Rng),
679		npeers: usize,
680		iters: usize,
681	) -> usize {
682		let mut ret = 0_usize;
683
684		for _ in 0..iters {
685			if random_routing.sample(npeers, rng) {
686				random_routing.inc_sent();
687				ret += 1;
688			}
689		}
690
691		ret
692	}
693
694	#[test]
695	fn test_random_routing_distribution() {
696		let mut rng = dummy_rng();
697
698		let mut random_routing = RandomRouting { target: 4, sent: 0, sample_rate: 8 };
699		assert_eq!(run_random_routing(&mut random_routing, &mut rng, 100, 10000), 4);
700
701		let mut random_routing = RandomRouting { target: 8, sent: 0, sample_rate: 100 };
702		assert_eq!(run_random_routing(&mut random_routing, &mut rng, 100, 10000), 8);
703
704		let mut random_routing = RandomRouting { target: 0, sent: 0, sample_rate: 100 };
705		assert_eq!(run_random_routing(&mut random_routing, &mut rng, 100, 10000), 0);
706
707		let mut random_routing = RandomRouting { target: 10, sent: 0, sample_rate: 10 };
708		assert_eq!(run_random_routing(&mut random_routing, &mut rng, 10, 100), 10);
709	}
710
711	#[test]
712	fn test_matrix_neighbors() {
713		for (our_index, len, expected_row, expected_column) in vec![
714			(0usize, 1usize, vec![], vec![]),
715			(1, 2, vec![], vec![0usize]),
716			(0, 9, vec![1, 2], vec![3, 6]),
717			(9, 10, vec![], vec![0, 3, 6]),
718			(10, 11, vec![9], vec![1, 4, 7]),
719			(7, 11, vec![6, 8], vec![1, 4, 10]),
720		]
721		.into_iter()
722		{
723			let matrix = matrix_neighbors(our_index, len).unwrap();
724			let mut row_result: Vec<_> = matrix.row_neighbors.collect();
725			let mut column_result: Vec<_> = matrix.column_neighbors.collect();
726			row_result.sort();
727			column_result.sort();
728
729			assert_eq!(row_result, expected_row);
730			assert_eq!(column_result, expected_column);
731		}
732	}
733}