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

polkadot_node_subsystem_util/
availability_chunks.rs
