polkadot_node_subsystem_util/
availability_chunks.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
17use polkadot_erasure_coding::systematic_recovery_threshold;
18use polkadot_primitives::{node_features, ChunkIndex, CoreIndex, NodeFeatures, ValidatorIndex};
19
20/// Compute the per-validator availability chunk index.
21/// WARNING: THIS FUNCTION IS CRITICAL TO PARACHAIN CONSENSUS.
22/// Any modification to the output of the function needs to be coordinated via the runtime.
23/// It's best to use minimal/no external dependencies.
24pub fn availability_chunk_index(
25	node_features: &NodeFeatures,
26	n_validators: usize,
27	core_index: CoreIndex,
28	validator_index: ValidatorIndex,
29) -> Result<ChunkIndex, polkadot_erasure_coding::Error> {
30	if node_features
31		.get(usize::from(node_features::FeatureIndex::AvailabilityChunkMapping as u8))
32		.map(|bitref| *bitref)
33		.unwrap_or_default()
34	{
35		let systematic_threshold = systematic_recovery_threshold(n_validators)? as u32;
36		let core_start_pos = core_index.0 * systematic_threshold;
37
38		return Ok(ChunkIndex((core_start_pos + validator_index.0) % n_validators as u32))
39	}
40
41	Ok(validator_index.into())
42}
43
44/// Compute the per-core availability chunk indices. Returns a Vec which maps ValidatorIndex to
45/// ChunkIndex for a given availability core index
46/// WARNING: THIS FUNCTION IS CRITICAL TO PARACHAIN CONSENSUS.
47/// Any modification to the output of the function needs to be coordinated via the
48/// runtime. It's best to use minimal/no external dependencies.
49pub fn availability_chunk_indices(
50	node_features: &NodeFeatures,
51	n_validators: usize,
52	core_index: CoreIndex,
53) -> Result<Vec<ChunkIndex>, polkadot_erasure_coding::Error> {
54	let identity = (0..n_validators).map(|index| ChunkIndex(index as u32));
55	if node_features
56		.get(usize::from(node_features::FeatureIndex::AvailabilityChunkMapping as u8))
57		.map(|bitref| *bitref)
58		.unwrap_or_default()
59	{
60		let systematic_threshold = systematic_recovery_threshold(n_validators)? as u32;
61		let core_start_pos = core_index.0 * systematic_threshold;
62
63		return Ok(identity
64			.into_iter()
65			.cycle()
66			.skip(core_start_pos as usize)
67			.take(n_validators)
68			.collect())
69	}
70
71	Ok(identity.collect())
72}
73
74#[cfg(test)]
75mod tests {
76	use super::*;
77	use std::collections::HashSet;
78
79	pub fn node_features_with_mapping_enabled() -> NodeFeatures {
80		let mut node_features = NodeFeatures::new();
81		node_features
82			.resize(node_features::FeatureIndex::AvailabilityChunkMapping as usize + 1, false);
83		node_features
84			.set(node_features::FeatureIndex::AvailabilityChunkMapping as u8 as usize, true);
85		node_features
86	}
87
88	pub fn node_features_with_other_bits_enabled() -> NodeFeatures {
89		let mut node_features = NodeFeatures::new();
90		node_features.resize(node_features::FeatureIndex::FirstUnassigned as usize + 1, true);
91		node_features
92			.set(node_features::FeatureIndex::AvailabilityChunkMapping as u8 as usize, false);
93		node_features
94	}
95
96	#[test]
97	fn test_availability_chunk_indices() {
98		let n_validators = 20u32;
99		let n_cores = 15u32;
100
101		// If the mapping feature is not enabled, it should always be the identity vector.
102		{
103			for node_features in [NodeFeatures::EMPTY, node_features_with_other_bits_enabled()] {
104				for core_index in 0..n_cores {
105					let indices = availability_chunk_indices(
106						node_features.as_ref(),
107						n_validators as usize,
108						CoreIndex(core_index),
109					)
110					.unwrap();
111
112					for validator_index in 0..n_validators {
113						assert_eq!(
114							indices[validator_index as usize],
115							availability_chunk_index(
116								node_features.as_ref(),
117								n_validators as usize,
118								CoreIndex(core_index),
119								ValidatorIndex(validator_index)
120							)
121							.unwrap()
122						)
123					}
124
125					assert_eq!(
126						indices,
127						(0..n_validators).map(|i| ChunkIndex(i)).collect::<Vec<_>>()
128					);
129				}
130			}
131		}
132
133		// Test when mapping feature is enabled.
134		{
135			let node_features = node_features_with_mapping_enabled();
136			let mut previous_indices = None;
137
138			for core_index in 0..n_cores {
139				let indices = availability_chunk_indices(
140					&node_features,
141					n_validators as usize,
142					CoreIndex(core_index),
143				)
144				.unwrap();
145
146				for validator_index in 0..n_validators {
147					assert_eq!(
148						indices[validator_index as usize],
149						availability_chunk_index(
150							&node_features,
151							n_validators as usize,
152							CoreIndex(core_index),
153							ValidatorIndex(validator_index)
154						)
155						.unwrap()
156					)
157				}
158
159				// Check that it's not equal to the previous core's indices.
160				if let Some(previous_indices) = previous_indices {
161					assert_ne!(previous_indices, indices);
162				}
163
164				previous_indices = Some(indices.clone());
165
166				// Check that it's indeed a permutation.
167				assert_eq!(
168					(0..n_validators).map(|i| ChunkIndex(i)).collect::<HashSet<_>>(),
169					indices.into_iter().collect::<HashSet<_>>()
170				);
171			}
172		}
173	}
174
175	#[test]
176	// This is just a dummy test that checks the mapping against some hardcoded outputs, to prevent
177	// accidental changes to the algorithms.
178	fn prevent_changes_to_mapping() {
179		let n_validators = 7;
180		let node_features = node_features_with_mapping_enabled();
181
182		assert_eq!(
183			availability_chunk_indices(&node_features, n_validators, CoreIndex(0))
184				.unwrap()
185				.into_iter()
186				.map(|i| i.0)
187				.collect::<Vec<u32>>(),
188			vec![0, 1, 2, 3, 4, 5, 6]
189		);
190		assert_eq!(
191			availability_chunk_indices(&node_features, n_validators, CoreIndex(1))
192				.unwrap()
193				.into_iter()
194				.map(|i| i.0)
195				.collect::<Vec<u32>>(),
196			vec![2, 3, 4, 5, 6, 0, 1]
197		);
198		assert_eq!(
199			availability_chunk_indices(&node_features, n_validators, CoreIndex(2))
200				.unwrap()
201				.into_iter()
202				.map(|i| i.0)
203				.collect::<Vec<u32>>(),
204			vec![4, 5, 6, 0, 1, 2, 3]
205		);
206		assert_eq!(
207			availability_chunk_indices(&node_features, n_validators, CoreIndex(3))
208				.unwrap()
209				.into_iter()
210				.map(|i| i.0)
211				.collect::<Vec<u32>>(),
212			vec![6, 0, 1, 2, 3, 4, 5]
213		);
214		assert_eq!(
215			availability_chunk_indices(&node_features, n_validators, CoreIndex(4))
216				.unwrap()
217				.into_iter()
218				.map(|i| i.0)
219				.collect::<Vec<u32>>(),
220			vec![1, 2, 3, 4, 5, 6, 0]
221		);
222	}
223}
polkadot_node_subsystem_util/availability_chunks.rs

polkadot_node_subsystem_util/
availability_chunks.rs
