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
//! `V7` Primitives.
18

            
19
use alloc::{
20
	vec,
21
	vec::{IntoIter, Vec},
22
};
23
use bitvec::{field::BitField, slice::BitSlice, vec::BitVec};
24
use codec::{Decode, Encode};
25
use core::{
26
	marker::PhantomData,
27
	slice::{Iter, IterMut},
28
};
29
use scale_info::TypeInfo;
30

            
31
use sp_application_crypto::KeyTypeId;
32
use sp_arithmetic::traits::{BaseArithmetic, Saturating};
33
use sp_core::RuntimeDebug;
34
use sp_inherents::InherentIdentifier;
35
use sp_runtime::traits::{AppVerify, Header as HeaderT};
36

            
37
pub use sp_runtime::traits::{BlakeTwo256, Hash as HashT};
38

            
39
// Export some core primitives.
40
pub use polkadot_core_primitives::v2::{
41
	AccountId, AccountIndex, AccountPublic, Balance, Block, BlockId, BlockNumber, CandidateHash,
42
	ChainId, DownwardMessage, Hash, Header, InboundDownwardMessage, InboundHrmpMessage, Moment,
43
	Nonce, OutboundHrmpMessage, Remark, Signature, UncheckedExtrinsic,
44
};
45

            
46
// Export some polkadot-parachain primitives
47
pub use polkadot_parachain_primitives::primitives::{
48
	HeadData, HorizontalMessages, HrmpChannelId, Id, UpwardMessage, UpwardMessages, ValidationCode,
49
	ValidationCodeHash, LOWEST_PUBLIC_ID,
50
};
51

            
52
use serde::{Deserialize, Serialize};
53

            
54
pub use sp_authority_discovery::AuthorityId as AuthorityDiscoveryId;
55
pub use sp_consensus_slots::Slot;
56
pub use sp_staking::SessionIndex;
57

            
58
/// Signed data.
59
mod signed;
60
pub use signed::{EncodeAs, Signed, UncheckedSigned};
61

            
62
pub mod async_backing;
63
pub mod executor_params;
64
pub mod slashing;
65

            
66
pub use async_backing::AsyncBackingParams;
67
pub use executor_params::{
68
	ExecutorParam, ExecutorParamError, ExecutorParams, ExecutorParamsHash, ExecutorParamsPrepHash,
69
};
70

            
71
mod metrics;
72
pub use metrics::{
73
	metric_definitions, RuntimeMetricLabel, RuntimeMetricLabelValue, RuntimeMetricLabelValues,
74
	RuntimeMetricLabels, RuntimeMetricOp, RuntimeMetricUpdate,
75
};
76

            
77
/// The key type ID for a collator key.
78
pub const COLLATOR_KEY_TYPE_ID: KeyTypeId = KeyTypeId(*b"coll");
79
const LOG_TARGET: &str = "runtime::primitives";
80

            
81
mod collator_app {
82
	use sp_application_crypto::{app_crypto, sr25519};
83
	app_crypto!(sr25519, super::COLLATOR_KEY_TYPE_ID);
84
}
85

            
86
/// Identity that collators use.
87
pub type CollatorId = collator_app::Public;
88

            
89
/// A Parachain collator keypair.
90
#[cfg(feature = "std")]
91
pub type CollatorPair = collator_app::Pair;
92

            
93
/// Signature on candidate's block data by a collator.
94
pub type CollatorSignature = collator_app::Signature;
95

            
96
/// The key type ID for a parachain validator key.
97
pub const PARACHAIN_KEY_TYPE_ID: KeyTypeId = KeyTypeId(*b"para");
98

            
99
mod validator_app {
100
	use sp_application_crypto::{app_crypto, sr25519};
101
	app_crypto!(sr25519, super::PARACHAIN_KEY_TYPE_ID);
102
}
103

            
104
/// Identity that parachain validators use when signing validation messages.
105
///
106
/// For now we assert that parachain validator set is exactly equivalent to the authority set, and
107
/// so we define it to be the same type as `SessionKey`. In the future it may have different crypto.
108
pub type ValidatorId = validator_app::Public;
109

            
110
/// Trait required for type specific indices e.g. `ValidatorIndex` and `GroupIndex`
111
pub trait TypeIndex {
112
	/// Returns the index associated to this value.
113
	fn type_index(&self) -> usize;
114
}
115

            
116
/// Index of the validator is used as a lightweight replacement of the `ValidatorId` when
117
/// appropriate.
118
#[derive(Eq, Ord, PartialEq, PartialOrd, Copy, Clone, Encode, Decode, TypeInfo, RuntimeDebug)]
119
#[cfg_attr(feature = "std", derive(Serialize, Deserialize, Hash))]
120
pub struct ValidatorIndex(pub u32);
121

            
122
/// Index of an availability chunk.
123
///
124
/// The underlying type is identical to `ValidatorIndex`, because
125
/// the number of chunks will always be equal to the number of validators.
126
/// However, the chunk index held by a validator may not always be equal to its `ValidatorIndex`, so
127
/// we use a separate type to make code easier to read.
128
#[derive(Eq, Ord, PartialEq, PartialOrd, Copy, Clone, Encode, Decode, TypeInfo, RuntimeDebug)]
129
#[cfg_attr(feature = "std", derive(Serialize, Deserialize, Hash))]
130
pub struct ChunkIndex(pub u32);
131

            
132
impl From<ChunkIndex> for ValidatorIndex {
133
	fn from(c_index: ChunkIndex) -> Self {
134
		ValidatorIndex(c_index.0)
135
	}
136
}
137

            
138
impl From<ValidatorIndex> for ChunkIndex {
139
	fn from(v_index: ValidatorIndex) -> Self {
140
		ChunkIndex(v_index.0)
141
	}
142
}
143

            
144
impl From<u32> for ChunkIndex {
145
	fn from(n: u32) -> Self {
146
		ChunkIndex(n)
147
	}
148
}
149

            
150
// We should really get https://github.com/paritytech/polkadot/issues/2403 going ..
151
impl From<u32> for ValidatorIndex {
152
	fn from(n: u32) -> Self {
153
		ValidatorIndex(n)
154
	}
155
}
156

            
157
impl TypeIndex for ValidatorIndex {
158
	fn type_index(&self) -> usize {
159
		self.0 as usize
160
	}
161
}
162

            
163
sp_application_crypto::with_pair! {
164
	/// A Parachain validator keypair.
165
	pub type ValidatorPair = validator_app::Pair;
166
}
167

            
168
/// Signature with which parachain validators sign blocks.
169
///
170
/// For now we assert that parachain validator set is exactly equivalent to the authority set, and
171
/// so we define it to be the same type as `SessionKey`. In the future it may have different crypto.
172
pub type ValidatorSignature = validator_app::Signature;
173

            
174
/// A declarations of storage keys where an external observer can find some interesting data.
175
pub mod well_known_keys {
176
	use super::{HrmpChannelId, Id, WellKnownKey};
177
	use alloc::vec::Vec;
178
	use codec::Encode as _;
179
	use hex_literal::hex;
180
	use sp_io::hashing::twox_64;
181

            
182
	// A note on generating these magic values below:
183
	//
184
	// The `StorageValue`, such as `ACTIVE_CONFIG` was obtained by calling:
185
	//
186
	//     ActiveConfig::<T>::hashed_key()
187
	//
188
	// The `StorageMap` values require `prefix`, and for example for `hrmp_egress_channel_index`,
189
	// it could be obtained like:
190
	//
191
	//     HrmpEgressChannelsIndex::<T>::prefix_hash();
192
	//
193

            
194
	/// The current epoch index.
195
	///
196
	/// The storage item should be access as a `u64` encoded value.
197
	pub const EPOCH_INDEX: &[u8] =
198
		&hex!["1cb6f36e027abb2091cfb5110ab5087f38316cbf8fa0da822a20ac1c55bf1be3"];
199

            
200
	/// The current relay chain block randomness
201
	///
202
	/// The storage item should be accessed as a `schnorrkel::Randomness` encoded value.
203
	pub const CURRENT_BLOCK_RANDOMNESS: &[u8] =
204
		&hex!["1cb6f36e027abb2091cfb5110ab5087fd077dfdb8adb10f78f10a5df8742c545"];
205

            
206
	/// The randomness for one epoch ago
207
	///
208
	/// The storage item should be accessed as a `schnorrkel::Randomness` encoded value.
209
	pub const ONE_EPOCH_AGO_RANDOMNESS: &[u8] =
210
		&hex!["1cb6f36e027abb2091cfb5110ab5087f7ce678799d3eff024253b90e84927cc6"];
211

            
212
	/// The randomness for two epochs ago
213
	///
214
	/// The storage item should be accessed as a `schnorrkel::Randomness` encoded value.
215
	pub const TWO_EPOCHS_AGO_RANDOMNESS: &[u8] =
216
		&hex!["1cb6f36e027abb2091cfb5110ab5087f7a414cb008e0e61e46722aa60abdd672"];
217

            
218
	/// The current slot number.
219
	///
220
	/// The storage entry should be accessed as a `Slot` encoded value.
221
	pub const CURRENT_SLOT: &[u8] =
222
		&hex!["1cb6f36e027abb2091cfb5110ab5087f06155b3cd9a8c9e5e9a23fd5dc13a5ed"];
223

            
224
	/// The currently active host configuration.
225
	///
226
	/// The storage entry should be accessed as an `AbridgedHostConfiguration` encoded value.
227
	pub const ACTIVE_CONFIG: &[u8] =
228
		&hex!["06de3d8a54d27e44a9d5ce189618f22db4b49d95320d9021994c850f25b8e385"];
229

            
230
	/// Hash of the committed head data for a given registered para.
231
	///
232
	/// The storage entry stores wrapped `HeadData(Vec<u8>)`.
233
	pub fn para_head(para_id: Id) -> Vec<u8> {
234
		let prefix = hex!["cd710b30bd2eab0352ddcc26417aa1941b3c252fcb29d88eff4f3de5de4476c3"];
235

            
236
		para_id.using_encoded(|para_id: &[u8]| {
237
			prefix
238
				.as_ref()
239
				.iter()
240
				.chain(twox_64(para_id).iter())
241
				.chain(para_id.iter())
242
				.cloned()
243
				.collect()
244
		})
245
	}
246

            
247
	/// The upward message dispatch queue for the given para id.
248
	///
249
	/// The storage entry stores a tuple of two values:
250
	///
251
	/// - `count: u32`, the number of messages currently in the queue for given para,
252
	/// - `total_size: u32`, the total size of all messages in the queue.
253
	#[deprecated = "Use `relay_dispatch_queue_remaining_capacity` instead"]
254
	pub fn relay_dispatch_queue_size(para_id: Id) -> Vec<u8> {
255
		let prefix = hex!["f5207f03cfdce586301014700e2c2593fad157e461d71fd4c1f936839a5f1f3e"];
256

            
257
		para_id.using_encoded(|para_id: &[u8]| {
258
			prefix
259
				.as_ref()
260
				.iter()
261
				.chain(twox_64(para_id).iter())
262
				.chain(para_id.iter())
263
				.cloned()
264
				.collect()
265
		})
266
	}
267

            
268
	/// Type safe version of `relay_dispatch_queue_size`.
269
	#[deprecated = "Use `relay_dispatch_queue_remaining_capacity` instead"]
270
	pub fn relay_dispatch_queue_size_typed(para: Id) -> WellKnownKey<(u32, u32)> {
271
		#[allow(deprecated)]
272
		relay_dispatch_queue_size(para).into()
273
	}
274

            
275
	/// The upward message dispatch queue remaining capacity for the given para id.
276
	///
277
	/// The storage entry stores a tuple of two values:
278
	///
279
	/// - `count: u32`, the number of additional messages which may be enqueued for the given para,
280
	/// - `total_size: u32`, the total size of additional messages which may be enqueued for the
281
	/// given para.
282
	pub fn relay_dispatch_queue_remaining_capacity(para_id: Id) -> WellKnownKey<(u32, u32)> {
283
		(b":relay_dispatch_queue_remaining_capacity", para_id).encode().into()
284
	}
285

            
286
	/// The HRMP channel for the given identifier.
287
	///
288
	/// The storage entry should be accessed as an `AbridgedHrmpChannel` encoded value.
289
	pub fn hrmp_channels(channel: HrmpChannelId) -> Vec<u8> {
290
		let prefix = hex!["6a0da05ca59913bc38a8630590f2627cb6604cff828a6e3f579ca6c59ace013d"];
291

            
292
		channel.using_encoded(|channel: &[u8]| {
293
			prefix
294
				.as_ref()
295
				.iter()
296
				.chain(twox_64(channel).iter())
297
				.chain(channel.iter())
298
				.cloned()
299
				.collect()
300
		})
301
	}
302

            
303
	/// The list of inbound channels for the given para.
304
	///
305
	/// The storage entry stores a `Vec<ParaId>`
306
	pub fn hrmp_ingress_channel_index(para_id: Id) -> Vec<u8> {
307
		let prefix = hex!["6a0da05ca59913bc38a8630590f2627c1d3719f5b0b12c7105c073c507445948"];
308

            
309
		para_id.using_encoded(|para_id: &[u8]| {
310
			prefix
311
				.as_ref()
312
				.iter()
313
				.chain(twox_64(para_id).iter())
314
				.chain(para_id.iter())
315
				.cloned()
316
				.collect()
317
		})
318
	}
319

            
320
	/// The list of outbound channels for the given para.
321
	///
322
	/// The storage entry stores a `Vec<ParaId>`
323
	pub fn hrmp_egress_channel_index(para_id: Id) -> Vec<u8> {
324
		let prefix = hex!["6a0da05ca59913bc38a8630590f2627cf12b746dcf32e843354583c9702cc020"];
325

            
326
		para_id.using_encoded(|para_id: &[u8]| {
327
			prefix
328
				.as_ref()
329
				.iter()
330
				.chain(twox_64(para_id).iter())
331
				.chain(para_id.iter())
332
				.cloned()
333
				.collect()
334
		})
335
	}
336

            
337
	/// The MQC head for the downward message queue of the given para. See more in the `Dmp` module.
338
	///
339
	/// The storage entry stores a `Hash`. This is polkadot hash which is at the moment
340
	/// `blake2b-256`.
341
	pub fn dmq_mqc_head(para_id: Id) -> Vec<u8> {
342
		let prefix = hex!["63f78c98723ddc9073523ef3beefda0c4d7fefc408aac59dbfe80a72ac8e3ce5"];
343

            
344
		para_id.using_encoded(|para_id: &[u8]| {
345
			prefix
346
				.as_ref()
347
				.iter()
348
				.chain(twox_64(para_id).iter())
349
				.chain(para_id.iter())
350
				.cloned()
351
				.collect()
352
		})
353
	}
354

            
355
	/// The signal that indicates whether the parachain should go-ahead with the proposed validation
356
	/// code upgrade.
357
	///
358
	/// The storage entry stores a value of `UpgradeGoAhead` type.
359
	pub fn upgrade_go_ahead_signal(para_id: Id) -> Vec<u8> {
360
		let prefix = hex!["cd710b30bd2eab0352ddcc26417aa1949e94c040f5e73d9b7addd6cb603d15d3"];
361

            
362
		para_id.using_encoded(|para_id: &[u8]| {
363
			prefix
364
				.as_ref()
365
				.iter()
366
				.chain(twox_64(para_id).iter())
367
				.chain(para_id.iter())
368
				.cloned()
369
				.collect()
370
		})
371
	}
372

            
373
	/// The signal that indicates whether the parachain is disallowed to signal an upgrade at this
374
	/// relay-parent.
375
	///
376
	/// The storage entry stores a value of `UpgradeRestriction` type.
377
	pub fn upgrade_restriction_signal(para_id: Id) -> Vec<u8> {
378
		let prefix = hex!["cd710b30bd2eab0352ddcc26417aa194f27bbb460270642b5bcaf032ea04d56a"];
379

            
380
		para_id.using_encoded(|para_id: &[u8]| {
381
			prefix
382
				.as_ref()
383
				.iter()
384
				.chain(twox_64(para_id).iter())
385
				.chain(para_id.iter())
386
				.cloned()
387
				.collect()
388
		})
389
	}
390
}
391

            
392
/// Unique identifier for the Parachains Inherent
393
pub const PARACHAINS_INHERENT_IDENTIFIER: InherentIdentifier = *b"parachn0";
394

            
395
/// The key type ID for parachain assignment key.
396
pub const ASSIGNMENT_KEY_TYPE_ID: KeyTypeId = KeyTypeId(*b"asgn");
397

            
398
/// Compressed or not the wasm blob can never be less than 9 bytes.
399
pub const MIN_CODE_SIZE: u32 = 9;
400

            
401
/// Maximum compressed code size we support right now.
402
/// At the moment we have runtime upgrade on chain, which restricts scalability severely. If we want
403
/// to have bigger values, we should fix that first.
404
///
405
/// Used for:
406
/// * initial genesis for the Parachains configuration
407
/// * checking updates to this stored runtime configuration do not exceed this limit
408
/// * when detecting a code decompression bomb in the client
409
// NOTE: This value is used in the runtime so be careful when changing it.
410
pub const MAX_CODE_SIZE: u32 = 3 * 1024 * 1024;
411

            
412
/// Maximum head data size we support right now.
413
///
414
/// Used for:
415
/// * initial genesis for the Parachains configuration
416
/// * checking updates to this stored runtime configuration do not exceed this limit
417
// NOTE: This value is used in the runtime so be careful when changing it.
418
pub const MAX_HEAD_DATA_SIZE: u32 = 1 * 1024 * 1024;
419

            
420
/// Maximum PoV size we support right now.
421
///
422
/// Used for:
423
/// * initial genesis for the Parachains configuration
424
/// * checking updates to this stored runtime configuration do not exceed this limit
425
/// * when detecting a PoV decompression bomb in the client
426
// NOTE: This value is used in the runtime so be careful when changing it.
427
pub const MAX_POV_SIZE: u32 = 5 * 1024 * 1024;
428

            
429
/// Default queue size we use for the on-demand order book.
430
///
431
/// Can be adjusted in configuration.
432
pub const ON_DEMAND_DEFAULT_QUEUE_MAX_SIZE: u32 = 10_000;
433

            
434
/// Maximum for maximum queue size.
435
///
436
/// Setting `on_demand_queue_max_size` to a value higher than this is unsound. This is more a
437
/// theoretical limit, just below enough what the target type supports, so comparisons are possible
438
/// even with indices that are overflowing the underyling type.
439
pub const ON_DEMAND_MAX_QUEUE_MAX_SIZE: u32 = 1_000_000_000;
440

            
441
/// Backing votes threshold used from the host prior to runtime API version 6 and from the runtime
442
/// prior to v9 configuration migration.
443
pub const LEGACY_MIN_BACKING_VOTES: u32 = 2;
444

            
445
// The public key of a keypair used by a validator for determining assignments
446
/// to approve included parachain candidates.
447
mod assignment_app {
448
	use sp_application_crypto::{app_crypto, sr25519};
449
	app_crypto!(sr25519, super::ASSIGNMENT_KEY_TYPE_ID);
450
}
451

            
452
/// The public key of a keypair used by a validator for determining assignments
453
/// to approve included parachain candidates.
454
pub type AssignmentId = assignment_app::Public;
455

            
456
sp_application_crypto::with_pair! {
457
	/// The full keypair used by a validator for determining assignments to approve included
458
	/// parachain candidates.
459
	pub type AssignmentPair = assignment_app::Pair;
460
}
461

            
462
/// The index of the candidate in the list of candidates fully included as-of the block.
463
pub type CandidateIndex = u32;
464

            
465
/// Get a collator signature payload on a relay-parent, block-data combo.
466
pub fn collator_signature_payload<H: AsRef<[u8]>>(
467
	relay_parent: &H,
468
	para_id: &Id,
469
	persisted_validation_data_hash: &Hash,
470
	pov_hash: &Hash,
471
	validation_code_hash: &ValidationCodeHash,
472
) -> [u8; 132] {
473
	// 32-byte hash length is protected in a test below.
474
	let mut payload = [0u8; 132];
475

            
476
	payload[0..32].copy_from_slice(relay_parent.as_ref());
477
	u32::from(*para_id).using_encoded(|s| payload[32..32 + s.len()].copy_from_slice(s));
478
	payload[36..68].copy_from_slice(persisted_validation_data_hash.as_ref());
479
	payload[68..100].copy_from_slice(pov_hash.as_ref());
480
	payload[100..132].copy_from_slice(validation_code_hash.as_ref());
481

            
482
	payload
483
}
484

            
485
fn check_collator_signature<H: AsRef<[u8]>>(
486
	relay_parent: &H,
487
	para_id: &Id,
488
	persisted_validation_data_hash: &Hash,
489
	pov_hash: &Hash,
490
	validation_code_hash: &ValidationCodeHash,
491
	collator: &CollatorId,
492
	signature: &CollatorSignature,
493
) -> Result<(), ()> {
494
	let payload = collator_signature_payload(
495
		relay_parent,
496
		para_id,
497
		persisted_validation_data_hash,
498
		pov_hash,
499
		validation_code_hash,
500
	);
501

            
502
	if signature.verify(&payload[..], collator) {
503
		Ok(())
504
	} else {
505
		Err(())
506
	}
507
}
508

            
509
/// A unique descriptor of the candidate receipt.
510
#[derive(PartialEq, Eq, Clone, Encode, Decode, TypeInfo, RuntimeDebug)]
511
#[cfg_attr(feature = "std", derive(Hash))]
512
pub struct CandidateDescriptor<H = Hash> {
513
	/// The ID of the para this is a candidate for.
514
	pub para_id: Id,
515
	/// The hash of the relay-chain block this is executed in the context of.
516
	pub relay_parent: H,
517
	/// The collator's sr25519 public key.
518
	pub collator: CollatorId,
519
	/// The blake2-256 hash of the persisted validation data. This is extra data derived from
520
	/// relay-chain state which may vary based on bitfields included before the candidate.
521
	/// Thus it cannot be derived entirely from the relay-parent.
522
	pub persisted_validation_data_hash: Hash,
523
	/// The blake2-256 hash of the PoV.
524
	pub pov_hash: Hash,
525
	/// The root of a block's erasure encoding Merkle tree.
526
	pub erasure_root: Hash,
527
	/// Signature on blake2-256 of components of this receipt:
528
	/// The parachain index, the relay parent, the validation data hash, and the `pov_hash`.
529
	pub signature: CollatorSignature,
530
	/// Hash of the para header that is being generated by this candidate.
531
	pub para_head: Hash,
532
	/// The blake2-256 hash of the validation code bytes.
533
	pub validation_code_hash: ValidationCodeHash,
534
}
535

            
536
impl<H: AsRef<[u8]>> CandidateDescriptor<H> {
537
	/// Check the signature of the collator within this descriptor.
538
	pub fn check_collator_signature(&self) -> Result<(), ()> {
539
		check_collator_signature(
540
			&self.relay_parent,
541
			&self.para_id,
542
			&self.persisted_validation_data_hash,
543
			&self.pov_hash,
544
			&self.validation_code_hash,
545
			&self.collator,
546
			&self.signature,
547
		)
548
	}
549
}
550

            
551
/// A candidate-receipt.
552
#[derive(PartialEq, Eq, Clone, Encode, Decode, TypeInfo, RuntimeDebug)]
553
pub struct CandidateReceipt<H = Hash> {
554
	/// The descriptor of the candidate.
555
	pub descriptor: CandidateDescriptor<H>,
556
	/// The hash of the encoded commitments made as a result of candidate execution.
557
	pub commitments_hash: Hash,
558
}
559

            
560
impl<H> CandidateReceipt<H> {
561
	/// Get a reference to the candidate descriptor.
562
	pub fn descriptor(&self) -> &CandidateDescriptor<H> {
563
		&self.descriptor
564
	}
565

            
566
	/// Computes the blake2-256 hash of the receipt.
567
	pub fn hash(&self) -> CandidateHash
568
	where
569
		H: Encode,
570
	{
571
		CandidateHash(BlakeTwo256::hash_of(self))
572
	}
573
}
574

            
575
/// A candidate-receipt with commitments directly included.
576
#[derive(PartialEq, Eq, Clone, Encode, Decode, TypeInfo, RuntimeDebug)]
577
#[cfg_attr(feature = "std", derive(Hash))]
578
pub struct CommittedCandidateReceipt<H = Hash> {
579
	/// The descriptor of the candidate.
580
	pub descriptor: CandidateDescriptor<H>,
581
	/// The commitments of the candidate receipt.
582
	pub commitments: CandidateCommitments,
583
}
584

            
585
impl<H> CommittedCandidateReceipt<H> {
586
	/// Get a reference to the candidate descriptor.
587
	pub fn descriptor(&self) -> &CandidateDescriptor<H> {
588
		&self.descriptor
589
	}
590
}
591

            
592
impl<H: Clone> CommittedCandidateReceipt<H> {
593
	/// Transforms this into a plain `CandidateReceipt`.
594
	pub fn to_plain(&self) -> CandidateReceipt<H> {
595
		CandidateReceipt {
596
			descriptor: self.descriptor.clone(),
597
			commitments_hash: self.commitments.hash(),
598
		}
599
	}
600

            
601
	/// Computes the hash of the committed candidate receipt.
602
	///
603
	/// This computes the canonical hash, not the hash of the directly encoded data.
604
	/// Thus this is a shortcut for `candidate.to_plain().hash()`.
605
	pub fn hash(&self) -> CandidateHash
606
	where
607
		H: Encode,
608
	{
609
		self.to_plain().hash()
610
	}
611

            
612
	/// Does this committed candidate receipt corresponds to the given [`CandidateReceipt`]?
613
	pub fn corresponds_to(&self, receipt: &CandidateReceipt<H>) -> bool
614
	where
615
		H: PartialEq,
616
	{
617
		receipt.descriptor == self.descriptor && receipt.commitments_hash == self.commitments.hash()
618
	}
619
}
620

            
621
impl PartialOrd for CommittedCandidateReceipt {
622
	fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
623
		Some(self.cmp(other))
624
	}
625
}
626

            
627
impl Ord for CommittedCandidateReceipt {
628
	fn cmp(&self, other: &Self) -> core::cmp::Ordering {
629
		// TODO: compare signatures or something more sane
630
		// https://github.com/paritytech/polkadot/issues/222
631
		self.descriptor()
632
			.para_id
633
			.cmp(&other.descriptor().para_id)
634
			.then_with(|| self.commitments.head_data.cmp(&other.commitments.head_data))
635
	}
636
}
637

            
638
/// The validation data provides information about how to create the inputs for validation of a
639
/// candidate. This information is derived from the chain state and will vary from para to para,
640
/// although some fields may be the same for every para.
641
///
642
/// Since this data is used to form inputs to the validation function, it needs to be persisted by
643
/// the availability system to avoid dependence on availability of the relay-chain state.
644
///
645
/// Furthermore, the validation data acts as a way to authorize the additional data the collator
646
/// needs to pass to the validation function. For example, the validation function can check whether
647
/// the incoming messages (e.g. downward messages) were actually sent by using the data provided in
648
/// the validation data using so called MQC heads.
649
///
650
/// Since the commitments of the validation function are checked by the relay-chain, secondary
651
/// checkers can rely on the invariant that the relay-chain only includes para-blocks for which
652
/// these checks have already been done. As such, there is no need for the validation data used to
653
/// inform validators and collators about the checks the relay-chain will perform to be persisted by
654
/// the availability system.
655
///
656
/// The `PersistedValidationData` should be relatively lightweight primarily because it is
657
/// constructed during inclusion for each candidate and therefore lies on the critical path of
658
/// inclusion.
659
#[derive(PartialEq, Eq, Clone, Encode, Decode, TypeInfo, RuntimeDebug)]
660
#[cfg_attr(feature = "std", derive(Default))]
661
pub struct PersistedValidationData<H = Hash, N = BlockNumber> {
662
	/// The parent head-data.
663
	pub parent_head: HeadData,
664
	/// The relay-chain block number this is in the context of.
665
	pub relay_parent_number: N,
666
	/// The relay-chain block storage root this is in the context of.
667
	pub relay_parent_storage_root: H,
668
	/// The maximum legal size of a POV block, in bytes.
669
	pub max_pov_size: u32,
670
}
671

            
672
impl<H: Encode, N: Encode> PersistedValidationData<H, N> {
673
	/// Compute the blake2-256 hash of the persisted validation data.
674
	pub fn hash(&self) -> Hash {
675
		BlakeTwo256::hash_of(self)
676
	}
677
}
678

            
679
/// Commitments made in a `CandidateReceipt`. Many of these are outputs of validation.
680
#[derive(PartialEq, Eq, Clone, Encode, Decode, TypeInfo, RuntimeDebug)]
681
#[cfg_attr(feature = "std", derive(Default, Hash))]
682
pub struct CandidateCommitments<N = BlockNumber> {
683
	/// Messages destined to be interpreted by the Relay chain itself.
684
	pub upward_messages: UpwardMessages,
685
	/// Horizontal messages sent by the parachain.
686
	pub horizontal_messages: HorizontalMessages,
687
	/// New validation code.
688
	pub new_validation_code: Option<ValidationCode>,
689
	/// The head-data produced as a result of execution.
690
	pub head_data: HeadData,
691
	/// The number of messages processed from the DMQ.
692
	pub processed_downward_messages: u32,
693
	/// The mark which specifies the block number up to which all inbound HRMP messages are
694
	/// processed.
695
	pub hrmp_watermark: N,
696
}
697

            
698
impl CandidateCommitments {
699
	/// Compute the blake2-256 hash of the commitments.
700
	pub fn hash(&self) -> Hash {
701
		BlakeTwo256::hash_of(self)
702
	}
703
}
704

            
705
/// A bitfield concerning availability of backed candidates.
706
///
707
/// Every bit refers to an availability core index.
708
#[derive(PartialEq, Eq, Clone, Encode, Decode, RuntimeDebug, TypeInfo)]
709
pub struct AvailabilityBitfield(pub BitVec<u8, bitvec::order::Lsb0>);
710

            
711
impl From<BitVec<u8, bitvec::order::Lsb0>> for AvailabilityBitfield {
712
	fn from(inner: BitVec<u8, bitvec::order::Lsb0>) -> Self {
713
		AvailabilityBitfield(inner)
714
	}
715
}
716

            
717
/// A signed compact statement, suitable to be sent to the chain.
718
pub type SignedStatement = Signed<CompactStatement>;
719
/// A signed compact statement, with signature not yet checked.
720
pub type UncheckedSignedStatement = UncheckedSigned<CompactStatement>;
721

            
722
/// A bitfield signed by a particular validator about the availability of pending candidates.
723
pub type SignedAvailabilityBitfield = Signed<AvailabilityBitfield>;
724
/// A signed bitfield with signature not yet checked.
725
pub type UncheckedSignedAvailabilityBitfield = UncheckedSigned<AvailabilityBitfield>;
726

            
727
/// A set of signed availability bitfields. Should be sorted by validator index, ascending.
728
pub type SignedAvailabilityBitfields = Vec<SignedAvailabilityBitfield>;
729
/// A set of unchecked signed availability bitfields. Should be sorted by validator index,
730
/// ascending.
731
pub type UncheckedSignedAvailabilityBitfields = Vec<UncheckedSignedAvailabilityBitfield>;
732

            
733
/// A backed (or backable, depending on context) candidate.
734
#[derive(Encode, Decode, Clone, PartialEq, Eq, RuntimeDebug, TypeInfo)]
735
pub struct BackedCandidate<H = Hash> {
736
	/// The candidate referred to.
737
	candidate: CommittedCandidateReceipt<H>,
738
	/// The validity votes themselves, expressed as signatures.
739
	validity_votes: Vec<ValidityAttestation>,
740
	/// The indices of the validators within the group, expressed as a bitfield. May be extended
741
	/// beyond the backing group size to contain the assigned core index, if ElasticScalingMVP is
742
	/// enabled.
743
	validator_indices: BitVec<u8, bitvec::order::Lsb0>,
744
}
745

            
746
impl<H> BackedCandidate<H> {
747
	/// Constructor
748
	pub fn new(
749
		candidate: CommittedCandidateReceipt<H>,
750
		validity_votes: Vec<ValidityAttestation>,
751
		validator_indices: BitVec<u8, bitvec::order::Lsb0>,
752
		core_index: Option<CoreIndex>,
753
	) -> Self {
754
		let mut instance = Self { candidate, validity_votes, validator_indices };
755
		if let Some(core_index) = core_index {
756
			instance.inject_core_index(core_index);
757
		}
758
		instance
759
	}
760

            
761
	/// Get a reference to the descriptor of the candidate.
762
	pub fn descriptor(&self) -> &CandidateDescriptor<H> {
763
		&self.candidate.descriptor
764
	}
765

            
766
	/// Get a reference to the committed candidate receipt of the candidate.
767
396
	pub fn candidate(&self) -> &CommittedCandidateReceipt<H> {
768
396
		&self.candidate
769
396
	}
770

            
771
	/// Get a reference to the validity votes of the candidate.
772
372
	pub fn validity_votes(&self) -> &[ValidityAttestation] {
773
372
		&self.validity_votes
774
372
	}
775

            
776
	/// Get a mutable reference to validity votes of the para.
777
	pub fn validity_votes_mut(&mut self) -> &mut Vec<ValidityAttestation> {
778
		&mut self.validity_votes
779
	}
780

            
781
	/// Compute this candidate's hash.
782
	pub fn hash(&self) -> CandidateHash
783
	where
784
		H: Clone + Encode,
785
	{
786
		self.candidate.hash()
787
	}
788

            
789
	/// Get this candidate's receipt.
790
	pub fn receipt(&self) -> CandidateReceipt<H>
791
	where
792
		H: Clone,
793
	{
794
		self.candidate.to_plain()
795
	}
796

            
797
	/// Get a copy of the validator indices and the assumed core index, if any.
798
	pub fn validator_indices_and_core_index(
799
		&self,
800
		core_index_enabled: bool,
801
	) -> (&BitSlice<u8, bitvec::order::Lsb0>, Option<CoreIndex>) {
802
		// This flag tells us if the block producers must enable Elastic Scaling MVP hack.
803
		// It extends `BackedCandidate::validity_indices` to store a 8 bit core index.
804
		if core_index_enabled {
805
			let core_idx_offset = self.validator_indices.len().saturating_sub(8);
806
			if core_idx_offset > 0 {
807
				let (validator_indices_slice, core_idx_slice) =
808
					self.validator_indices.split_at(core_idx_offset);
809
				return (
810
					validator_indices_slice,
811
					Some(CoreIndex(core_idx_slice.load::<u8>() as u32)),
812
				);
813
			}
814
		}
815

            
816
		(&self.validator_indices, None)
817
	}
818

            
819
	/// Inject a core index in the validator_indices bitvec.
820
	fn inject_core_index(&mut self, core_index: CoreIndex) {
821
		let core_index_to_inject: BitVec<u8, bitvec::order::Lsb0> =
822
			BitVec::from_vec(vec![core_index.0 as u8]);
823
		self.validator_indices.extend(core_index_to_inject);
824
	}
825

            
826
	/// Update the validator indices and core index in the candidate.
827
	pub fn set_validator_indices_and_core_index(
828
		&mut self,
829
		new_indices: BitVec<u8, bitvec::order::Lsb0>,
830
		maybe_core_index: Option<CoreIndex>,
831
	) {
832
		self.validator_indices = new_indices;
833

            
834
		if let Some(core_index) = maybe_core_index {
835
			self.inject_core_index(core_index);
836
		}
837
	}
838
}
839

            
840
/// Verify the backing of the given candidate.
841
///
842
/// Provide a lookup from the index of a validator within the group assigned to this para,
843
/// as opposed to the index of the validator within the overall validator set, as well as
844
/// the number of validators in the group.
845
///
846
/// Also provide the signing context.
847
///
848
/// Returns either an error, indicating that one of the signatures was invalid or that the index
849
/// was out-of-bounds, or the number of signatures checked.
850
pub fn check_candidate_backing<H: AsRef<[u8]> + Clone + Encode + core::fmt::Debug>(
851
	candidate_hash: CandidateHash,
852
	validity_votes: &[ValidityAttestation],
853
	validator_indices: &BitSlice<u8, bitvec::order::Lsb0>,
854
	signing_context: &SigningContext<H>,
855
	group_len: usize,
856
	validator_lookup: impl Fn(usize) -> Option<ValidatorId>,
857
) -> Result<usize, ()> {
858
	if validator_indices.len() != group_len {
859
		log::debug!(
860
			target: LOG_TARGET,
861
			"Check candidate backing: indices mismatch: group_len = {} , indices_len = {}",
862
			group_len,
863
			validator_indices.len(),
864
		);
865
		return Err(())
866
	}
867

            
868
	if validity_votes.len() > group_len {
869
		log::debug!(
870
			target: LOG_TARGET,
871
			"Check candidate backing: Too many votes, expected: {}, found: {}",
872
			group_len,
873
			validity_votes.len(),
874
		);
875
		return Err(())
876
	}
877

            
878
	let mut signed = 0;
879
	for ((val_in_group_idx, _), attestation) in validator_indices
880
		.iter()
881
		.enumerate()
882
		.filter(|(_, signed)| **signed)
883
		.zip(validity_votes.iter())
884
	{
885
		let validator_id = validator_lookup(val_in_group_idx).ok_or(())?;
886
		let payload = attestation.signed_payload(candidate_hash, signing_context);
887
		let sig = attestation.signature();
888

            
889
		if sig.verify(&payload[..], &validator_id) {
890
			signed += 1;
891
		} else {
892
			log::debug!(
893
				target: LOG_TARGET,
894
				"Check candidate backing: Invalid signature. validator_id = {:?}, validator_index = {} ",
895
				validator_id,
896
				val_in_group_idx,
897
			);
898
			return Err(())
899
		}
900
	}
901

            
902
	if signed != validity_votes.len() {
903
		log::error!(
904
			target: LOG_TARGET,
905
			"Check candidate backing: Too many signatures, expected = {}, found = {}",
906
			validity_votes.len(),
907
			signed,
908
		);
909
		return Err(())
910
	}
911

            
912
	Ok(signed)
913
}
914

            
915
/// The unique (during session) index of a core.
916
#[derive(
917
	Encode, Decode, Default, PartialOrd, Ord, Eq, PartialEq, Clone, Copy, TypeInfo, RuntimeDebug,
918
)]
919
#[cfg_attr(feature = "std", derive(Hash))]
920
pub struct CoreIndex(pub u32);
921

            
922
impl From<u32> for CoreIndex {
923
	fn from(i: u32) -> CoreIndex {
924
		CoreIndex(i)
925
	}
926
}
927

            
928
impl TypeIndex for CoreIndex {
929
	fn type_index(&self) -> usize {
930
		self.0 as usize
931
	}
932
}
933

            
934
/// The unique (during session) index of a validator group.
935
#[derive(Encode, Decode, Default, Clone, Copy, Debug, PartialEq, Eq, TypeInfo, PartialOrd, Ord)]
936
#[cfg_attr(feature = "std", derive(Hash))]
937
pub struct GroupIndex(pub u32);
938

            
939
impl From<u32> for GroupIndex {
940
	fn from(i: u32) -> GroupIndex {
941
		GroupIndex(i)
942
	}
943
}
944

            
945
impl TypeIndex for GroupIndex {
946
	fn type_index(&self) -> usize {
947
		self.0 as usize
948
	}
949
}
950

            
951
/// A claim on authoring the next block for a given parathread (on-demand parachain).
952
#[derive(Clone, Encode, Decode, TypeInfo, PartialEq, RuntimeDebug)]
953
pub struct ParathreadClaim(pub Id, pub Option<CollatorId>);
954

            
955
/// An entry tracking a claim to ensure it does not pass the maximum number of retries.
956
#[derive(Clone, Encode, Decode, TypeInfo, PartialEq, RuntimeDebug)]
957
pub struct ParathreadEntry {
958
	/// The claim.
959
	pub claim: ParathreadClaim,
960
	/// Number of retries
961
	pub retries: u32,
962
}
963

            
964
/// A helper data-type for tracking validator-group rotations.
965
#[derive(Clone, Encode, Decode, TypeInfo, RuntimeDebug)]
966
#[cfg_attr(feature = "std", derive(PartialEq))]
967
pub struct GroupRotationInfo<N = BlockNumber> {
968
	/// The block number where the session started.
969
	pub session_start_block: N,
970
	/// How often groups rotate. 0 means never.
971
	pub group_rotation_frequency: N,
972
	/// The current block number.
973
	pub now: N,
974
}
975

            
976
impl GroupRotationInfo {
977
	/// Returns the index of the group needed to validate the core at the given index, assuming
978
	/// the given number of cores.
979
	///
980
	/// `core_index` should be less than `cores`, which is capped at `u32::max()`.
981
	pub fn group_for_core(&self, core_index: CoreIndex, cores: usize) -> GroupIndex {
982
		if self.group_rotation_frequency == 0 {
983
			return GroupIndex(core_index.0)
984
		}
985
		if cores == 0 {
986
			return GroupIndex(0)
987
		}
988

            
989
		let cores = core::cmp::min(cores, u32::MAX as usize);
990
		let blocks_since_start = self.now.saturating_sub(self.session_start_block);
991
		let rotations = blocks_since_start / self.group_rotation_frequency;
992

            
993
		// g = c + r mod cores
994

            
995
		let idx = (core_index.0 as usize + rotations as usize) % cores;
996
		GroupIndex(idx as u32)
997
	}
998

            
999
	/// Returns the index of the group assigned to the given core. This does no checking or
	/// whether the group index is in-bounds.
	///
	/// `core_index` should be less than `cores`, which is capped at `u32::max()`.
	pub fn core_for_group(&self, group_index: GroupIndex, cores: usize) -> CoreIndex {
		if self.group_rotation_frequency == 0 {
			return CoreIndex(group_index.0)
		}
		if cores == 0 {
			return CoreIndex(0)
		}
		let cores = core::cmp::min(cores, u32::MAX as usize);
		let blocks_since_start = self.now.saturating_sub(self.session_start_block);
		let rotations = blocks_since_start / self.group_rotation_frequency;
		let rotations = rotations % cores as u32;
		// g = c + r mod cores
		// c = g - r mod cores
		// x = x + cores mod cores
		// c = (g + cores) - r mod cores
		let idx = (group_index.0 as usize + cores - rotations as usize) % cores;
		CoreIndex(idx as u32)
	}
	/// Create a new `GroupRotationInfo` with one further rotation applied.
	pub fn bump_rotation(&self) -> Self {
		GroupRotationInfo {
			session_start_block: self.session_start_block,
			group_rotation_frequency: self.group_rotation_frequency,
			now: self.next_rotation_at(),
		}
	}
}
impl<N: Saturating + BaseArithmetic + Copy> GroupRotationInfo<N> {
	/// Returns the block number of the next rotation after the current block. If the current block
	/// is 10 and the rotation frequency is 5, this should return 15.
86415
	pub fn next_rotation_at(&self) -> N {
86415
		let cycle_once = self.now + self.group_rotation_frequency;
86415
		cycle_once -
86415
			(cycle_once.saturating_sub(self.session_start_block) % self.group_rotation_frequency)
86415
	}
	/// Returns the block number of the last rotation before or including the current block. If the
	/// current block is 10 and the rotation frequency is 5, this should return 10.
281178
	pub fn last_rotation_at(&self) -> N {
281178
		self.now -
281178
			(self.now.saturating_sub(self.session_start_block) % self.group_rotation_frequency)
281178
	}
}
/// Information about a core which is currently occupied.
#[derive(Clone, Encode, Decode, TypeInfo, RuntimeDebug)]
#[cfg_attr(feature = "std", derive(PartialEq))]
pub struct OccupiedCore<H = Hash, N = BlockNumber> {
	// NOTE: this has no ParaId as it can be deduced from the candidate descriptor.
	/// If this core is freed by availability, this is the assignment that is next up on this
	/// core, if any. None if there is nothing queued for this core.
	pub next_up_on_available: Option<ScheduledCore>,
	/// The relay-chain block number this began occupying the core at.
	pub occupied_since: N,
	/// The relay-chain block this will time-out at, if any.
	pub time_out_at: N,
	/// If this core is freed by being timed-out, this is the assignment that is next up on this
	/// core. None if there is nothing queued for this core or there is no possibility of timing
	/// out.
	pub next_up_on_time_out: Option<ScheduledCore>,
	/// A bitfield with 1 bit for each validator in the set. `1` bits mean that the corresponding
	/// validators has attested to availability on-chain. A 2/3+ majority of `1` bits means that
	/// this will be available.
	pub availability: BitVec<u8, bitvec::order::Lsb0>,
	/// The group assigned to distribute availability pieces of this candidate.
	pub group_responsible: GroupIndex,
	/// The hash of the candidate occupying the core.
	pub candidate_hash: CandidateHash,
	/// The descriptor of the candidate occupying the core.
	pub candidate_descriptor: CandidateDescriptor<H>,
}
impl<H, N> OccupiedCore<H, N> {
	/// Get the Para currently occupying this core.
	pub fn para_id(&self) -> Id {
		self.candidate_descriptor.para_id
	}
}
/// Information about a core which is currently occupied.
#[derive(Clone, Encode, Decode, TypeInfo, RuntimeDebug)]
#[cfg_attr(feature = "std", derive(PartialEq))]
pub struct ScheduledCore {
	/// The ID of a para scheduled.
	pub para_id: Id,
	/// DEPRECATED: see: <https://github.com/paritytech/polkadot/issues/7575>
	///
	/// Will be removed in a future version.
	pub collator: Option<CollatorId>,
}
/// The state of a particular availability core.
#[derive(Clone, Encode, Decode, TypeInfo, RuntimeDebug)]
#[cfg_attr(feature = "std", derive(PartialEq))]
pub enum CoreState<H = Hash, N = BlockNumber> {
	/// The core is currently occupied.
	#[codec(index = 0)]
	Occupied(OccupiedCore<H, N>),
	/// The core is currently free, with a para scheduled and given the opportunity
	/// to occupy.
	///
	/// If a particular Collator is required to author this block, that is also present in this
	/// variant.
	#[codec(index = 1)]
	Scheduled(ScheduledCore),
	/// The core is currently free and there is nothing scheduled. This can be the case for
	/// parathread cores when there are no parathread blocks queued. Parachain cores will never be
	/// left idle.
	#[codec(index = 2)]
	Free,
}
impl<N> CoreState<N> {
	/// Returns the scheduled `ParaId` for the core or `None` if nothing is scheduled.
	///
	/// This function is deprecated. `ClaimQueue` should be used to obtain the scheduled `ParaId`s
	/// for each core.
	#[deprecated(
		note = "`para_id` will be removed. Use `ClaimQueue` to query the scheduled `para_id` instead."
	)]
	pub fn para_id(&self) -> Option<Id> {
		match self {
			Self::Occupied(ref core) => core.next_up_on_available.as_ref().map(|n| n.para_id),
			Self::Scheduled(core) => Some(core.para_id),
			Self::Free => None,
		}
	}
	/// Is this core state `Self::Occupied`?
	pub fn is_occupied(&self) -> bool {
		matches!(self, Self::Occupied(_))
	}
}
/// An assumption being made about the state of an occupied core.
#[derive(Clone, Copy, Encode, Decode, TypeInfo, RuntimeDebug)]
#[cfg_attr(feature = "std", derive(PartialEq, Eq, Hash))]
pub enum OccupiedCoreAssumption {
	/// The candidate occupying the core was made available and included to free the core.
	#[codec(index = 0)]
	Included,
	/// The candidate occupying the core timed out and freed the core without advancing the para.
	#[codec(index = 1)]
	TimedOut,
	/// The core was not occupied to begin with.
	#[codec(index = 2)]
	Free,
}
/// An even concerning a candidate.
#[derive(Clone, Encode, Decode, TypeInfo, RuntimeDebug)]
#[cfg_attr(feature = "std", derive(PartialEq))]
pub enum CandidateEvent<H = Hash> {
	/// This candidate receipt was backed in the most recent block.
	/// This includes the core index the candidate is now occupying.
	#[codec(index = 0)]
	CandidateBacked(CandidateReceipt<H>, HeadData, CoreIndex, GroupIndex),
	/// This candidate receipt was included and became a parablock at the most recent block.
	/// This includes the core index the candidate was occupying as well as the group responsible
	/// for backing the candidate.
	#[codec(index = 1)]
	CandidateIncluded(CandidateReceipt<H>, HeadData, CoreIndex, GroupIndex),
	/// This candidate receipt was not made available in time and timed out.
	/// This includes the core index the candidate was occupying.
	#[codec(index = 2)]
	CandidateTimedOut(CandidateReceipt<H>, HeadData, CoreIndex),
}
/// Scraped runtime backing votes and resolved disputes.
#[derive(Clone, Encode, Decode, RuntimeDebug, TypeInfo)]
#[cfg_attr(feature = "std", derive(PartialEq))]
pub struct ScrapedOnChainVotes<H: Encode + Decode = Hash> {
	/// The session in which the block was included.
	pub session: SessionIndex,
	/// Set of backing validators for each candidate, represented by its candidate
	/// receipt.
	pub backing_validators_per_candidate:
		Vec<(CandidateReceipt<H>, Vec<(ValidatorIndex, ValidityAttestation)>)>,
	/// On-chain-recorded set of disputes.
	/// Note that the above `backing_validators` are
	/// unrelated to the backers of the disputes candidates.
	pub disputes: MultiDisputeStatementSet,
}
/// A vote of approval on a candidate.
#[derive(Clone, RuntimeDebug)]
pub struct ApprovalVote(pub CandidateHash);
impl ApprovalVote {
	/// Yields the signing payload for this approval vote.
	pub fn signing_payload(&self, session_index: SessionIndex) -> Vec<u8> {
		const MAGIC: [u8; 4] = *b"APPR";
		(MAGIC, &self.0, session_index).encode()
	}
}
/// A vote of approval for multiple candidates.
#[derive(Clone, RuntimeDebug)]
pub struct ApprovalVoteMultipleCandidates<'a>(pub &'a [CandidateHash]);
impl<'a> ApprovalVoteMultipleCandidates<'a> {
	/// Yields the signing payload for this approval vote.
	pub fn signing_payload(&self, session_index: SessionIndex) -> Vec<u8> {
		const MAGIC: [u8; 4] = *b"APPR";
		// Make this backwards compatible with `ApprovalVote` so if we have just on candidate the
		// signature will look the same.
		// This gives us the nice benefit that old nodes can still check signatures when len is 1
		// and the new node can check the signature coming from old nodes.
		if self.0.len() == 1 {
			(MAGIC, self.0.first().expect("QED: we just checked"), session_index).encode()
		} else {
			(MAGIC, &self.0, session_index).encode()
		}
	}
}
/// Approval voting configuration parameters
#[derive(
	RuntimeDebug,
	Copy,
	Clone,
	PartialEq,
	Encode,
	Decode,
	TypeInfo,
	serde::Serialize,
	serde::Deserialize,
)]
pub struct ApprovalVotingParams {
	/// The maximum number of candidates `approval-voting` can vote for with
	/// a single signatures.
	///
	/// Setting it to 1, means we send the approval as soon as we have it available.
	pub max_approval_coalesce_count: u32,
}
impl Default for ApprovalVotingParams {
	fn default() -> Self {
		Self { max_approval_coalesce_count: 1 }
	}
}
/// Custom validity errors used in Polkadot while validating transactions.
#[repr(u8)]
pub enum ValidityError {
	/// The Ethereum signature is invalid.
	InvalidEthereumSignature = 0,
	/// The signer has no claim.
	SignerHasNoClaim = 1,
	/// No permission to execute the call.
	NoPermission = 2,
	/// An invalid statement was made for a claim.
	InvalidStatement = 3,
}
impl From<ValidityError> for u8 {
	fn from(err: ValidityError) -> Self {
		err as u8
	}
}
/// Abridged version of `HostConfiguration` (from the `Configuration` parachains host runtime
/// module) meant to be used by a parachain or PDK such as cumulus.
#[derive(Clone, Encode, Decode, RuntimeDebug, TypeInfo)]
#[cfg_attr(feature = "std", derive(PartialEq))]
pub struct AbridgedHostConfiguration {
	/// The maximum validation code size, in bytes.
	pub max_code_size: u32,
	/// The maximum head-data size, in bytes.
	pub max_head_data_size: u32,
	/// Total number of individual messages allowed in the parachain -> relay-chain message queue.
	pub max_upward_queue_count: u32,
	/// Total size of messages allowed in the parachain -> relay-chain message queue before which
	/// no further messages may be added to it. If it exceeds this then the queue may contain only
	/// a single message.
	pub max_upward_queue_size: u32,
	/// The maximum size of an upward message that can be sent by a candidate.
	///
	/// This parameter affects the size upper bound of the `CandidateCommitments`.
	pub max_upward_message_size: u32,
	/// The maximum number of messages that a candidate can contain.
	///
	/// This parameter affects the size upper bound of the `CandidateCommitments`.
	pub max_upward_message_num_per_candidate: u32,
	/// The maximum number of outbound HRMP messages can be sent by a candidate.
	///
	/// This parameter affects the upper bound of size of `CandidateCommitments`.
	pub hrmp_max_message_num_per_candidate: u32,
	/// The minimum period, in blocks, between which parachains can update their validation code.
	pub validation_upgrade_cooldown: BlockNumber,
	/// The delay, in blocks, before a validation upgrade is applied.
	pub validation_upgrade_delay: BlockNumber,
	/// Asynchronous backing parameters.
	pub async_backing_params: AsyncBackingParams,
}
/// Abridged version of `HrmpChannel` (from the `Hrmp` parachains host runtime module) meant to be
/// used by a parachain or PDK such as cumulus.
#[derive(Clone, Encode, Decode, RuntimeDebug, TypeInfo)]
#[cfg_attr(feature = "std", derive(PartialEq))]
pub struct AbridgedHrmpChannel {
	/// The maximum number of messages that can be pending in the channel at once.
	pub max_capacity: u32,
	/// The maximum total size of the messages that can be pending in the channel at once.
	pub max_total_size: u32,
	/// The maximum message size that could be put into the channel.
	pub max_message_size: u32,
	/// The current number of messages pending in the channel.
	/// Invariant: should be less or equal to `max_capacity`.s`.
	pub msg_count: u32,
	/// The total size in bytes of all message payloads in the channel.
	/// Invariant: should be less or equal to `max_total_size`.
	pub total_size: u32,
	/// A head of the Message Queue Chain for this channel. Each link in this chain has a form:
	/// `(prev_head, B, H(M))`, where
	/// - `prev_head`: is the previous value of `mqc_head` or zero if none.
	/// - `B`: is the [relay-chain] block number in which a message was appended
	/// - `H(M)`: is the hash of the message being appended.
	/// This value is initialized to a special value that consists of all zeroes which indicates
	/// that no messages were previously added.
	pub mqc_head: Option<Hash>,
}
/// A possible upgrade restriction that prevents a parachain from performing an upgrade.
#[derive(Copy, Clone, Encode, Decode, PartialEq, RuntimeDebug, TypeInfo)]
pub enum UpgradeRestriction {
	/// There is an upgrade restriction and there are no details about its specifics nor how long
	/// it could last.
	#[codec(index = 0)]
	Present,
}
/// A struct that the relay-chain communicates to a parachain indicating what course of action the
/// parachain should take in the coordinated parachain validation code upgrade process.
///
/// This data type appears in the last step of the upgrade process. After the parachain observes it
/// and reacts to it the upgrade process concludes.
#[derive(Copy, Clone, Encode, Decode, PartialEq, RuntimeDebug, TypeInfo)]
pub enum UpgradeGoAhead {
	/// Abort the upgrade process. There is something wrong with the validation code previously
	/// submitted by the parachain. This variant can also be used to prevent upgrades by the
	/// governance should an emergency emerge.
	///
	/// The expected reaction on this variant is that the parachain will admit this message and
	/// remove all the data about the pending upgrade. Depending on the nature of the problem (to
	/// be examined offchain for now), it can try to send another validation code or just retry
	/// later.
	#[codec(index = 0)]
	Abort,
	/// Apply the pending code change. The parablock that is built on a relay-parent that is
	/// descendant of the relay-parent where the parachain observed this signal must use the
	/// upgraded validation code.
	#[codec(index = 1)]
	GoAhead,
}
/// Consensus engine id for polkadot v1 consensus engine.
pub const POLKADOT_ENGINE_ID: sp_runtime::ConsensusEngineId = *b"POL1";
/// A consensus log item for polkadot validation. To be used with [`POLKADOT_ENGINE_ID`].
#[derive(Decode, Encode, Clone, PartialEq, Eq)]
pub enum ConsensusLog {
	/// A parachain upgraded its code.
	#[codec(index = 1)]
	ParaUpgradeCode(Id, ValidationCodeHash),
	/// A parachain scheduled a code upgrade.
	#[codec(index = 2)]
	ParaScheduleUpgradeCode(Id, ValidationCodeHash, BlockNumber),
	/// Governance requests to auto-approve every candidate included up to the given block
	/// number in the current chain, inclusive.
	#[codec(index = 3)]
	ForceApprove(BlockNumber),
	/// A signal to revert the block number in the same chain as the
	/// header this digest is part of and all of its descendants.
	///
	/// It is a no-op for a block to contain a revert digest targeting
	/// its own number or a higher number.
	///
	/// In practice, these are issued when on-chain logic has detected an
	/// invalid parachain block within its own chain, due to a dispute.
	#[codec(index = 4)]
	Revert(BlockNumber),
}
impl ConsensusLog {
	/// Attempt to convert a reference to a generic digest item into a consensus log.
	pub fn from_digest_item(
		digest_item: &sp_runtime::DigestItem,
	) -> Result<Option<Self>, codec::Error> {
		match digest_item {
			sp_runtime::DigestItem::Consensus(id, encoded) if id == &POLKADOT_ENGINE_ID =>
				Ok(Some(Self::decode(&mut &encoded[..])?)),
			_ => Ok(None),
		}
	}
}
impl From<ConsensusLog> for sp_runtime::DigestItem {
	fn from(c: ConsensusLog) -> sp_runtime::DigestItem {
		Self::Consensus(POLKADOT_ENGINE_ID, c.encode())
	}
}
/// A statement about a candidate, to be used within the dispute resolution process.
///
/// Statements are either in favor of the candidate's validity or against it.
48
#[derive(Encode, Decode, Clone, PartialEq, RuntimeDebug, TypeInfo)]
pub enum DisputeStatement {
1629
	/// A valid statement, of the given kind.
	#[codec(index = 0)]
1629
	Valid(ValidDisputeStatementKind),
96
	/// An invalid statement, of the given kind.
	#[codec(index = 1)]
96
	Invalid(InvalidDisputeStatementKind),
}
impl DisputeStatement {
	/// Get the payload data for this type of dispute statement.
	///
	/// Returns Error if the candidate_hash is not included in the list of signed
	/// candidate from ApprovalCheckingMultipleCandidate.
	pub fn payload_data(
		&self,
		candidate_hash: CandidateHash,
		session: SessionIndex,
	) -> Result<Vec<u8>, ()> {
		match self {
			DisputeStatement::Valid(ValidDisputeStatementKind::Explicit) =>
				Ok(ExplicitDisputeStatement { valid: true, candidate_hash, session }
					.signing_payload()),
			DisputeStatement::Valid(ValidDisputeStatementKind::BackingSeconded(
				inclusion_parent,
			)) => Ok(CompactStatement::Seconded(candidate_hash).signing_payload(&SigningContext {
				session_index: session,
				parent_hash: *inclusion_parent,
			})),
			DisputeStatement::Valid(ValidDisputeStatementKind::BackingValid(inclusion_parent)) =>
				Ok(CompactStatement::Valid(candidate_hash).signing_payload(&SigningContext {
					session_index: session,
					parent_hash: *inclusion_parent,
				})),
			DisputeStatement::Valid(ValidDisputeStatementKind::ApprovalChecking) =>
				Ok(ApprovalVote(candidate_hash).signing_payload(session)),
			DisputeStatement::Valid(
				ValidDisputeStatementKind::ApprovalCheckingMultipleCandidates(candidate_hashes),
			) =>
				if candidate_hashes.contains(&candidate_hash) {
					Ok(ApprovalVoteMultipleCandidates(candidate_hashes).signing_payload(session))
				} else {
					Err(())
				},
			DisputeStatement::Invalid(InvalidDisputeStatementKind::Explicit) =>
				Ok(ExplicitDisputeStatement { valid: false, candidate_hash, session }
					.signing_payload()),
		}
	}
	/// Check the signature on a dispute statement.
	pub fn check_signature(
		&self,
		validator_public: &ValidatorId,
		candidate_hash: CandidateHash,
		session: SessionIndex,
		validator_signature: &ValidatorSignature,
	) -> Result<(), ()> {
		let payload = self.payload_data(candidate_hash, session)?;
		if validator_signature.verify(&payload[..], &validator_public) {
			Ok(())
		} else {
			Err(())
		}
	}
	/// Whether the statement indicates validity.
	pub fn indicates_validity(&self) -> bool {
		match *self {
			DisputeStatement::Valid(_) => true,
			DisputeStatement::Invalid(_) => false,
		}
	}
	/// Whether the statement indicates invalidity.
	pub fn indicates_invalidity(&self) -> bool {
		match *self {
			DisputeStatement::Valid(_) => false,
			DisputeStatement::Invalid(_) => true,
		}
	}
	/// Statement is backing statement.
	pub fn is_backing(&self) -> bool {
		match self {
			Self::Valid(s) => s.is_backing(),
			Self::Invalid(_) => false,
		}
	}
}
/// Different kinds of statements of validity on  a candidate.
24
#[derive(Encode, Decode, Clone, PartialEq, RuntimeDebug, TypeInfo)]
pub enum ValidDisputeStatementKind {
1347
	/// An explicit statement issued as part of a dispute.
1347
	#[codec(index = 0)]
1347
	Explicit,
60
	/// A seconded statement on a candidate from the backing phase.
	#[codec(index = 1)]
60
	BackingSeconded(Hash),
24
	/// A valid statement on a candidate from the backing phase.
	#[codec(index = 2)]
24
	BackingValid(Hash),
27
	/// An approval vote from the approval checking phase.
27
	#[codec(index = 3)]
27
	ApprovalChecking,
147
	/// An approval vote from the new version.
	/// We can't create this version until all nodes
	/// have been updated to support it and max_approval_coalesce_count
	/// is set to more than 1.
	#[codec(index = 4)]
147
	ApprovalCheckingMultipleCandidates(Vec<CandidateHash>),
}
impl ValidDisputeStatementKind {
	/// Whether the statement is from the backing phase.
	pub fn is_backing(&self) -> bool {
		match self {
			ValidDisputeStatementKind::BackingSeconded(_) |
			ValidDisputeStatementKind::BackingValid(_) => true,
			ValidDisputeStatementKind::Explicit |
			ValidDisputeStatementKind::ApprovalChecking |
			ValidDisputeStatementKind::ApprovalCheckingMultipleCandidates(_) => false,
		}
	}
}
/// Different kinds of statements of invalidity on a candidate.
21
#[derive(Encode, Decode, Copy, Clone, PartialEq, RuntimeDebug, TypeInfo)]
pub enum InvalidDisputeStatementKind {
75
	/// An explicit statement issued as part of a dispute.
75
	#[codec(index = 0)]
75
	Explicit,
}
/// An explicit statement on a candidate issued as part of a dispute.
#[derive(Clone, PartialEq, RuntimeDebug)]
pub struct ExplicitDisputeStatement {
	/// Whether the candidate is valid
	pub valid: bool,
	/// The candidate hash.
	pub candidate_hash: CandidateHash,
	/// The session index of the candidate.
	pub session: SessionIndex,
}
impl ExplicitDisputeStatement {
	/// Produce the payload used for signing this type of statement.
	pub fn signing_payload(&self) -> Vec<u8> {
		const MAGIC: [u8; 4] = *b"DISP";
		(MAGIC, self.valid, self.candidate_hash, self.session).encode()
	}
}
/// A set of statements about a specific candidate.
#[derive(Encode, Decode, Clone, PartialEq, RuntimeDebug, TypeInfo)]
pub struct DisputeStatementSet {
	/// The candidate referenced by this set.
	pub candidate_hash: CandidateHash,
	/// The session index of the candidate.
	pub session: SessionIndex,
	/// Statements about the candidate.
	pub statements: Vec<(DisputeStatement, ValidatorIndex, ValidatorSignature)>,
}
impl From<CheckedDisputeStatementSet> for DisputeStatementSet {
	fn from(other: CheckedDisputeStatementSet) -> Self {
		other.0
	}
}
impl AsRef<DisputeStatementSet> for DisputeStatementSet {
840
	fn as_ref(&self) -> &DisputeStatementSet {
840
		&self
840
	}
}
/// A set of dispute statements.
pub type MultiDisputeStatementSet = Vec<DisputeStatementSet>;
/// A _checked_ set of dispute statements.
#[derive(Clone, PartialEq, RuntimeDebug, Encode)]
pub struct CheckedDisputeStatementSet(DisputeStatementSet);
impl AsRef<DisputeStatementSet> for CheckedDisputeStatementSet {
	fn as_ref(&self) -> &DisputeStatementSet {
		&self.0
	}
}
impl core::cmp::PartialEq<DisputeStatementSet> for CheckedDisputeStatementSet {
	fn eq(&self, other: &DisputeStatementSet) -> bool {
		self.0.eq(other)
	}
}
impl CheckedDisputeStatementSet {
	/// Convert from an unchecked, the verification of correctness of the `unchecked` statement set
	/// _must_ be done before calling this function!
	pub fn unchecked_from_unchecked(unchecked: DisputeStatementSet) -> Self {
		Self(unchecked)
	}
}
/// A set of _checked_ dispute statements.
pub type CheckedMultiDisputeStatementSet = Vec<CheckedDisputeStatementSet>;
/// The entire state of a dispute.
#[derive(Encode, Decode, Clone, RuntimeDebug, PartialEq, TypeInfo)]
pub struct DisputeState<N = BlockNumber> {
	/// A bitfield indicating all validators for the candidate.
	pub validators_for: BitVec<u8, bitvec::order::Lsb0>, // one bit per validator.
	/// A bitfield indicating all validators against the candidate.
	pub validators_against: BitVec<u8, bitvec::order::Lsb0>, // one bit per validator.
	/// The block number at which the dispute started on-chain.
	pub start: N,
	/// The block number at which the dispute concluded on-chain.
	pub concluded_at: Option<N>,
}
/// Parachains inherent-data passed into the runtime by a block author
#[derive(Encode, Decode, Clone, PartialEq, RuntimeDebug, TypeInfo)]
pub struct InherentData<HDR: HeaderT = Header> {
	/// Signed bitfields by validators about availability.
	pub bitfields: UncheckedSignedAvailabilityBitfields,
	/// Backed candidates for inclusion in the block.
	pub backed_candidates: Vec<BackedCandidate<HDR::Hash>>,
	/// Sets of dispute votes for inclusion,
	pub disputes: MultiDisputeStatementSet,
	/// The parent block header. Used for checking state proofs.
	pub parent_header: HDR,
}
/// An either implicit or explicit attestation to the validity of a parachain
/// candidate.
57
#[derive(Clone, Eq, PartialEq, Decode, Encode, RuntimeDebug, TypeInfo)]
pub enum ValidityAttestation {
171
	/// Implicit validity attestation by issuing.
	/// This corresponds to issuance of a `Candidate` statement.
	#[codec(index = 1)]
171
	Implicit(ValidatorSignature),
33
	/// An explicit attestation. This corresponds to issuance of a
	/// `Valid` statement.
	#[codec(index = 2)]
33
	Explicit(ValidatorSignature),
}
impl ValidityAttestation {
	/// Produce the underlying signed payload of the attestation, given the hash of the candidate,
	/// which should be known in context.
	pub fn to_compact_statement(&self, candidate_hash: CandidateHash) -> CompactStatement {
		// Explicit and implicit map directly from
		// `ValidityVote::Valid` and `ValidityVote::Issued`, and hence there is a
		// `1:1` relationship which enables the conversion.
		match *self {
			ValidityAttestation::Implicit(_) => CompactStatement::Seconded(candidate_hash),
			ValidityAttestation::Explicit(_) => CompactStatement::Valid(candidate_hash),
		}
	}
	/// Get a reference to the signature.
	pub fn signature(&self) -> &ValidatorSignature {
		match *self {
			ValidityAttestation::Implicit(ref sig) => sig,
			ValidityAttestation::Explicit(ref sig) => sig,
		}
	}
	/// Produce the underlying signed payload of the attestation, given the hash of the candidate,
	/// which should be known in context.
	pub fn signed_payload<H: Encode>(
		&self,
		candidate_hash: CandidateHash,
		signing_context: &SigningContext<H>,
	) -> Vec<u8> {
		match *self {
			ValidityAttestation::Implicit(_) =>
				(CompactStatement::Seconded(candidate_hash), signing_context).encode(),
			ValidityAttestation::Explicit(_) =>
				(CompactStatement::Valid(candidate_hash), signing_context).encode(),
		}
	}
}
/// A type returned by runtime with current session index and a parent hash.
#[derive(Clone, Eq, PartialEq, Default, Decode, Encode, RuntimeDebug)]
pub struct SigningContext<H = Hash> {
	/// Current session index.
	pub session_index: sp_staking::SessionIndex,
	/// Hash of the parent.
	pub parent_hash: H,
}
const BACKING_STATEMENT_MAGIC: [u8; 4] = *b"BKNG";
/// Statements that can be made about parachain candidates. These are the
/// actual values that are signed.
#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, RuntimeDebug)]
#[cfg_attr(feature = "std", derive(Hash))]
pub enum CompactStatement {
	/// Proposal of a parachain candidate.
	Seconded(CandidateHash),
	/// State that a parachain candidate is valid.
	Valid(CandidateHash),
}
impl CompactStatement {
	/// Yields the payload used for validator signatures on this kind
	/// of statement.
	pub fn signing_payload(&self, context: &SigningContext) -> Vec<u8> {
		(self, context).encode()
	}
	/// Get the underlying candidate hash this references.
	pub fn candidate_hash(&self) -> &CandidateHash {
		match *self {
			CompactStatement::Seconded(ref h) | CompactStatement::Valid(ref h) => h,
		}
	}
}
// Inner helper for codec on `CompactStatement`.
#[derive(Encode, Decode, TypeInfo)]
enum CompactStatementInner {
	#[codec(index = 1)]
	Seconded(CandidateHash),
	#[codec(index = 2)]
	Valid(CandidateHash),
}
impl From<CompactStatement> for CompactStatementInner {
	fn from(s: CompactStatement) -> Self {
		match s {
			CompactStatement::Seconded(h) => CompactStatementInner::Seconded(h),
			CompactStatement::Valid(h) => CompactStatementInner::Valid(h),
		}
	}
}
impl codec::Encode for CompactStatement {
	fn size_hint(&self) -> usize {
		// magic + discriminant + payload
		4 + 1 + 32
	}
	fn encode_to<T: codec::Output + ?Sized>(&self, dest: &mut T) {
		dest.write(&BACKING_STATEMENT_MAGIC);
		CompactStatementInner::from(self.clone()).encode_to(dest)
	}
}
impl codec::Decode for CompactStatement {
	fn decode<I: codec::Input>(input: &mut I) -> Result<Self, codec::Error> {
		let maybe_magic = <[u8; 4]>::decode(input)?;
		if maybe_magic != BACKING_STATEMENT_MAGIC {
			return Err(codec::Error::from("invalid magic string"))
		}
		Ok(match CompactStatementInner::decode(input)? {
			CompactStatementInner::Seconded(h) => CompactStatement::Seconded(h),
			CompactStatementInner::Valid(h) => CompactStatement::Valid(h),
		})
	}
}
/// `IndexedVec` struct indexed by type specific indices.
#[derive(Clone, Encode, Decode, RuntimeDebug, TypeInfo)]
#[cfg_attr(feature = "std", derive(PartialEq))]
pub struct IndexedVec<K, V>(Vec<V>, PhantomData<fn(K) -> K>);
impl<K, V> Default for IndexedVec<K, V> {
	fn default() -> Self {
		Self(vec![], PhantomData)
	}
}
impl<K, V> From<Vec<V>> for IndexedVec<K, V> {
270468
	fn from(validators: Vec<V>) -> Self {
270468
		Self(validators, PhantomData)
270468
	}
}
impl<K, V> FromIterator<V> for IndexedVec<K, V> {
	fn from_iter<T: IntoIterator<Item = V>>(iter: T) -> Self {
		Self(Vec::from_iter(iter), PhantomData)
	}
}
impl<K, V> IndexedVec<K, V>
where
	V: Clone,
{
	/// Returns a reference to an element indexed using `K`.
	pub fn get(&self, index: K) -> Option<&V>
	where
		K: TypeIndex,
	{
		self.0.get(index.type_index())
	}
	/// Returns a mutable reference to an element indexed using `K`.
	pub fn get_mut(&mut self, index: K) -> Option<&mut V>
	where
		K: TypeIndex,
	{
		self.0.get_mut(index.type_index())
	}
	/// Returns number of elements in vector.
	pub fn len(&self) -> usize {
		self.0.len()
	}
	/// Returns contained vector.
	pub fn to_vec(&self) -> Vec<V> {
		self.0.clone()
	}
	/// Returns an iterator over the underlying vector.
	pub fn iter(&self) -> Iter<'_, V> {
		self.0.iter()
	}
	/// Returns a mutable iterator over the underlying vector.
	pub fn iter_mut(&mut self) -> IterMut<'_, V> {
		self.0.iter_mut()
	}
	/// Creates a consuming iterator.
	pub fn into_iter(self) -> IntoIter<V> {
		self.0.into_iter()
	}
	/// Returns true if the underlying container is empty.
	pub fn is_empty(&self) -> bool {
		self.0.is_empty()
	}
}
/// The maximum number of validators `f` which may safely be faulty.
///
/// The total number of validators is `n = 3f + e` where `e in { 1, 2, 3 }`.
129842
pub const fn byzantine_threshold(n: usize) -> usize {
129842
	n.saturating_sub(1) / 3
129842
}
/// The supermajority threshold of validators which represents a subset
/// guaranteed to have at least f+1 honest validators.
129842
pub const fn supermajority_threshold(n: usize) -> usize {
129842
	n - byzantine_threshold(n)
129842
}
/// Adjust the configured needed backing votes with the size of the backing group.
pub fn effective_minimum_backing_votes(
	group_len: usize,
	configured_minimum_backing_votes: u32,
) -> usize {
	core::cmp::min(group_len, configured_minimum_backing_votes as usize)
}
/// Information about validator sets of a session.
///
/// NOTE: `SessionInfo` is frozen. Do not include new fields, consider creating a separate runtime
/// API. Reasoning and further outlook [here](https://github.com/paritytech/polkadot/issues/6586).
#[derive(Clone, Encode, Decode, RuntimeDebug, TypeInfo)]
#[cfg_attr(feature = "std", derive(PartialEq))]
pub struct SessionInfo {
	/****** New in v2 ****** */
	/// All the validators actively participating in parachain consensus.
	/// Indices are into the broader validator set.
	pub active_validator_indices: Vec<ValidatorIndex>,
	/// A secure random seed for the session, gathered from BABE.
	pub random_seed: [u8; 32],
	/// The amount of sessions to keep for disputes.
	pub dispute_period: SessionIndex,
	/****** Old fields ***** */
	/// Validators in canonical ordering.
	///
	/// NOTE: There might be more authorities in the current session, than `validators`
	/// participating in parachain consensus. See
	/// [`max_validators`](https://github.com/paritytech/polkadot/blob/a52dca2be7840b23c19c153cf7e110b1e3e475f8/runtime/parachains/src/configuration.rs#L148).
	///
	/// `SessionInfo::validators` will be limited to to `max_validators` when set.
	pub validators: IndexedVec<ValidatorIndex, ValidatorId>,
	/// Validators' authority discovery keys for the session in canonical ordering.
	///
	/// NOTE: The first `validators.len()` entries will match the corresponding validators in
	/// `validators`, afterwards any remaining authorities can be found. This is any authorities
	/// not participating in parachain consensus - see
	/// [`max_validators`](https://github.com/paritytech/polkadot/blob/a52dca2be7840b23c19c153cf7e110b1e3e475f8/runtime/parachains/src/configuration.rs#L148)
	pub discovery_keys: Vec<AuthorityDiscoveryId>,
	/// The assignment keys for validators.
	///
	/// NOTE: There might be more authorities in the current session, than validators participating
	/// in parachain consensus. See
	/// [`max_validators`](https://github.com/paritytech/polkadot/blob/a52dca2be7840b23c19c153cf7e110b1e3e475f8/runtime/parachains/src/configuration.rs#L148).
	///
	/// Therefore:
	/// ```ignore
	/// 	assignment_keys.len() == validators.len() && validators.len() <= discovery_keys.len()
	/// ```
	pub assignment_keys: Vec<AssignmentId>,
	/// Validators in shuffled ordering - these are the validator groups as produced
	/// by the `Scheduler` module for the session and are typically referred to by
	/// `GroupIndex`.
	pub validator_groups: IndexedVec<GroupIndex, Vec<ValidatorIndex>>,
	/// The number of availability cores used by the protocol during this session.
	pub n_cores: u32,
	/// The zeroth delay tranche width.
	pub zeroth_delay_tranche_width: u32,
	/// The number of samples we do of `relay_vrf_modulo`.
	pub relay_vrf_modulo_samples: u32,
	/// The number of delay tranches in total.
	pub n_delay_tranches: u32,
	/// How many slots (BABE / SASSAFRAS) must pass before an assignment is considered a
	/// no-show.
	pub no_show_slots: u32,
	/// The number of validators needed to approve a block.
	pub needed_approvals: u32,
}
/// A statement from the specified validator whether the given validation code passes PVF
/// pre-checking or not anchored to the given session index.
#[derive(Encode, Decode, Clone, PartialEq, RuntimeDebug, TypeInfo)]
pub struct PvfCheckStatement {
	/// `true` if the subject passed pre-checking and `false` otherwise.
	pub accept: bool,
	/// The validation code hash that was checked.
	pub subject: ValidationCodeHash,
	/// The index of a session during which this statement is considered valid.
	pub session_index: SessionIndex,
	/// The index of the validator from which this statement originates.
	pub validator_index: ValidatorIndex,
}
impl PvfCheckStatement {
	/// Produce the payload used for signing this type of statement.
	///
	/// It is expected that it will be signed by the validator at `validator_index` in the
	/// `session_index`.
	pub fn signing_payload(&self) -> Vec<u8> {
		const MAGIC: [u8; 4] = *b"VCPC"; // for "validation code pre-checking"
		(MAGIC, self.accept, self.subject, self.session_index, self.validator_index).encode()
	}
}
/// A well-known and typed storage key.
///
/// Allows for type-safe access to raw well-known storage keys.
pub struct WellKnownKey<T> {
	/// The raw storage key.
	pub key: Vec<u8>,
	_p: core::marker::PhantomData<T>,
}
impl<T> From<Vec<u8>> for WellKnownKey<T> {
	fn from(key: Vec<u8>) -> Self {
		Self { key, _p: Default::default() }
	}
}
impl<T> AsRef<[u8]> for WellKnownKey<T> {
	fn as_ref(&self) -> &[u8] {
		self.key.as_ref()
	}
}
impl<T: Decode> WellKnownKey<T> {
	/// Gets the value or `None` if it does not exist or decoding failed.
	pub fn get(&self) -> Option<T> {
		sp_io::storage::get(&self.key)
			.and_then(|raw| codec::DecodeAll::decode_all(&mut raw.as_ref()).ok())
	}
}
impl<T: Encode> WellKnownKey<T> {
	/// Sets the value.
	pub fn set(&self, value: T) {
		sp_io::storage::set(&self.key, &value.encode());
	}
}
/// Type discriminator for PVF preparation.
6
#[derive(Encode, Decode, TypeInfo, Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub enum PvfPrepKind {
42
	/// For prechecking requests.
42
	Precheck,
111
	/// For execution and heads-up requests.
111
	Prepare,
}
/// Type discriminator for PVF execution.
6
#[derive(Encode, Decode, TypeInfo, Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub enum PvfExecKind {
39
	/// For backing requests.
39
	Backing,
141
	/// For approval and dispute request.
141
	Approval,
}
/// Bit indices in the `HostConfiguration.node_features` that correspond to different node features.
pub type NodeFeatures = BitVec<u8, bitvec::order::Lsb0>;
/// Module containing feature-specific bit indices into the `NodeFeatures` bitvec.
pub mod node_features {
	/// A feature index used to identify a bit into the node_features array stored
	/// in the HostConfiguration.
	#[repr(u8)]
	#[derive(Clone, Copy)]
	pub enum FeatureIndex {
		/// Tells if tranch0 assignments could be sent in a single certificate.
		/// Reserved for: `<https://github.com/paritytech/polkadot-sdk/issues/628>`
		EnableAssignmentsV2 = 0,
		/// This feature enables the extension of `BackedCandidate::validator_indices` by 8 bits.
		/// The value stored there represents the assumed core index where the candidates
		/// are backed. This is needed for the elastic scaling MVP.
		ElasticScalingMVP = 1,
		/// Tells if the chunk mapping feature is enabled.
		/// Enables the implementation of
		/// [RFC-47](https://github.com/polkadot-fellows/RFCs/blob/main/text/0047-assignment-of-availability-chunks.md).
		/// Must not be enabled unless all validators and collators have stopped using `req_chunk`
		/// protocol version 1. If it is enabled, validators can start systematic chunk recovery.
		AvailabilityChunkMapping = 2,
		/// First unassigned feature bit.
		/// Every time a new feature flag is assigned it should take this value.
		/// and this should be incremented.
		FirstUnassigned = 3,
	}
}
#[cfg(test)]
mod tests {
	use super::*;
	use bitvec::bitvec;
	use sp_core::sr25519;
	pub fn dummy_committed_candidate_receipt() -> CommittedCandidateReceipt {
		let zeros = Hash::zero();
		CommittedCandidateReceipt {
			descriptor: CandidateDescriptor {
				para_id: 0.into(),
				relay_parent: zeros,
				collator: CollatorId::from(sr25519::Public::default()),
				persisted_validation_data_hash: zeros,
				pov_hash: zeros,
				erasure_root: zeros,
				signature: CollatorSignature::from(sr25519::Signature::default()),
				para_head: zeros,
				validation_code_hash: ValidationCode(vec![1, 2, 3, 4, 5, 6, 7, 8, 9]).hash(),
			},
			commitments: CandidateCommitments {
				head_data: HeadData(vec![]),
				upward_messages: vec![].try_into().expect("empty vec fits within bounds"),
				new_validation_code: None,
				horizontal_messages: vec![].try_into().expect("empty vec fits within bounds"),
				processed_downward_messages: 0,
				hrmp_watermark: 0_u32,
			},
		}
	}
	#[test]
	fn group_rotation_info_calculations() {
		let info =
			GroupRotationInfo { session_start_block: 10u32, now: 15, group_rotation_frequency: 5 };
		assert_eq!(info.next_rotation_at(), 20);
		assert_eq!(info.last_rotation_at(), 15);
	}
	#[test]
	fn group_for_core_is_core_for_group() {
		for cores in 1..=256 {
			for rotations in 0..(cores * 2) {
				let info = GroupRotationInfo {
					session_start_block: 0u32,
					now: rotations,
					group_rotation_frequency: 1,
				};
				for core in 0..cores {
					let group = info.group_for_core(CoreIndex(core), cores as usize);
					assert_eq!(info.core_for_group(group, cores as usize).0, core);
				}
			}
		}
	}
	#[test]
	fn collator_signature_payload_is_valid() {
		// if this fails, collator signature verification code has to be updated.
		let h = Hash::default();
		assert_eq!(h.as_ref().len(), 32);
		let _payload = collator_signature_payload(
			&Hash::repeat_byte(1),
			&5u32.into(),
			&Hash::repeat_byte(2),
			&Hash::repeat_byte(3),
			&Hash::repeat_byte(4).into(),
		);
	}
	#[test]
	fn test_byzantine_threshold() {
		assert_eq!(byzantine_threshold(0), 0);
		assert_eq!(byzantine_threshold(1), 0);
		assert_eq!(byzantine_threshold(2), 0);
		assert_eq!(byzantine_threshold(3), 0);
		assert_eq!(byzantine_threshold(4), 1);
		assert_eq!(byzantine_threshold(5), 1);
		assert_eq!(byzantine_threshold(6), 1);
		assert_eq!(byzantine_threshold(7), 2);
	}
	#[test]
	fn test_supermajority_threshold() {
		assert_eq!(supermajority_threshold(0), 0);
		assert_eq!(supermajority_threshold(1), 1);
		assert_eq!(supermajority_threshold(2), 2);
		assert_eq!(supermajority_threshold(3), 3);
		assert_eq!(supermajority_threshold(4), 3);
		assert_eq!(supermajority_threshold(5), 4);
		assert_eq!(supermajority_threshold(6), 5);
		assert_eq!(supermajority_threshold(7), 5);
	}
	#[test]
	fn balance_bigger_than_usize() {
		let zero_b: Balance = 0;
		let zero_u: usize = 0;
		assert!(zero_b.leading_zeros() >= zero_u.leading_zeros());
	}
	#[test]
	fn test_backed_candidate_injected_core_index() {
		let initial_validator_indices = bitvec![u8, bitvec::order::Lsb0; 0, 1, 0, 1];
		let mut candidate = BackedCandidate::new(
			dummy_committed_candidate_receipt(),
			vec![],
			initial_validator_indices.clone(),
			None,
		);
		// No core index supplied, ElasticScalingMVP is off.
		let (validator_indices, core_index) = candidate.validator_indices_and_core_index(false);
		assert_eq!(validator_indices, initial_validator_indices.as_bitslice());
		assert!(core_index.is_none());
		// No core index supplied, ElasticScalingMVP is on. Still, decoding will be ok if backing
		// group size is <= 8, to give a chance to parachains that don't have multiple cores
		// assigned.
		let (validator_indices, core_index) = candidate.validator_indices_and_core_index(true);
		assert_eq!(validator_indices, initial_validator_indices.as_bitslice());
		assert!(core_index.is_none());
		let encoded_validator_indices = candidate.validator_indices.clone();
		candidate.set_validator_indices_and_core_index(validator_indices.into(), core_index);
		assert_eq!(candidate.validator_indices, encoded_validator_indices);
		// No core index supplied, ElasticScalingMVP is on. Decoding is corrupted if backing group
		// size larger than 8.
		let candidate = BackedCandidate::new(
			dummy_committed_candidate_receipt(),
			vec![],
			bitvec![u8, bitvec::order::Lsb0; 0, 1, 0, 1, 0, 1, 0, 1, 0],
			None,
		);
		let (validator_indices, core_index) = candidate.validator_indices_and_core_index(true);
		assert_eq!(validator_indices, bitvec![u8, bitvec::order::Lsb0; 0].as_bitslice());
		assert!(core_index.is_some());
		// Core index supplied, ElasticScalingMVP is off. Core index will be treated as normal
		// validator indices. Runtime will check against this.
		let candidate = BackedCandidate::new(
			dummy_committed_candidate_receipt(),
			vec![],
			bitvec![u8, bitvec::order::Lsb0; 0, 1, 0, 1],
			Some(CoreIndex(10)),
		);
		let (validator_indices, core_index) = candidate.validator_indices_and_core_index(false);
		assert_eq!(
			validator_indices,
			bitvec![u8, bitvec::order::Lsb0; 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0]
		);
		assert!(core_index.is_none());
		// Core index supplied, ElasticScalingMVP is on.
		let mut candidate = BackedCandidate::new(
			dummy_committed_candidate_receipt(),
			vec![],
			bitvec![u8, bitvec::order::Lsb0; 0, 1, 0, 1],
			Some(CoreIndex(10)),
		);
		let (validator_indices, core_index) = candidate.validator_indices_and_core_index(true);
		assert_eq!(validator_indices, bitvec![u8, bitvec::order::Lsb0; 0, 1, 0, 1]);
		assert_eq!(core_index, Some(CoreIndex(10)));
		let encoded_validator_indices = candidate.validator_indices.clone();
		candidate.set_validator_indices_and_core_index(validator_indices.into(), core_index);
		assert_eq!(candidate.validator_indices, encoded_validator_indices);
	}
}