inclusion.rs 87.6 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Copyright 2020 Parity Technologies (UK) Ltd.
// This file is part of Polkadot.

// Polkadot is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.

// Polkadot is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with Polkadot.  If not, see <http://www.gnu.org/licenses/>.
asynchronous rob's avatar
asynchronous rob committed
16

17
//! The inclusion pallet is responsible for inclusion and availability of scheduled parachains
asynchronous rob's avatar
asynchronous rob committed
18
19
20
21
22
//! and parathreads.
//!
//! It is responsible for carrying candidates from being backable to being backed, and then from backed
//! to included.

23
24
use crate::{
	configuration, disputes, dmp, hrmp, paras,
25
	paras_inherent::{sanitize_bitfields, DisputedBitfield},
26
27
28
	scheduler::CoreAssignment,
	shared, ump,
};
Shawn Tabrizi's avatar
Shawn Tabrizi committed
29
30
31
use bitvec::{order::Lsb0 as BitOrderLsb0, vec::BitVec};
use frame_support::pallet_prelude::*;
use parity_scale_codec::{Decode, Encode};
asynchronous rob's avatar
asynchronous rob committed
32
use primitives::v1::{
Shawn Tabrizi's avatar
Shawn Tabrizi committed
33
	AvailabilityBitfield, BackedCandidate, CandidateCommitments, CandidateDescriptor,
34
	CandidateHash, CandidateReceipt, CommittedCandidateReceipt, CoreIndex, GroupIndex, Hash,
35
36
	HeadData, Id as ParaId, SigningContext, UncheckedSignedAvailabilityBitfields, ValidatorId,
	ValidatorIndex, ValidityAttestation,
asynchronous rob's avatar
asynchronous rob committed
37
};
38
use scale_info::TypeInfo;
Shawn Tabrizi's avatar
Shawn Tabrizi committed
39
40
41
42
use sp_runtime::{
	traits::{One, Saturating},
	DispatchError,
};
43
use sp_std::{collections::btree_set::BTreeSet, prelude::*};
asynchronous rob's avatar
asynchronous rob committed
44

45
46
pub use pallet::*;

asynchronous rob's avatar
asynchronous rob committed
47
48
49
50
51
/// A bitfield signed by a validator indicating that it is keeping its piece of the erasure-coding
/// for any backed candidates referred to by a `1` bit available.
///
/// The bitfield's signature should be checked at the point of submission. Afterwards it can be
/// dropped.
52
#[derive(Encode, Decode, TypeInfo)]
asynchronous rob's avatar
asynchronous rob committed
53
54
55
#[cfg_attr(test, derive(Debug))]
pub struct AvailabilityBitfieldRecord<N> {
	bitfield: AvailabilityBitfield, // one bit per core.
Shawn Tabrizi's avatar
Shawn Tabrizi committed
56
	submitted_at: N,                // for accounting, as meaning of bits may change over time.
asynchronous rob's avatar
asynchronous rob committed
57
58
}

59
60
61
62
63
64
65
66
67
68
69
70
71
/// Determines if all checks should be applied or if a subset was already completed
/// in a code path that will be executed afterwards or was already executed before.
#[derive(Encode, Decode, PartialEq, Eq, RuntimeDebug, TypeInfo)]
pub(crate) enum FullCheck {
	/// Yes, do a full check, skip nothing.
	Yes,
	/// Skip a subset of checks that are already completed before.
	///
	/// Attention: Should only be used when absolutely sure that the required
	/// checks are completed before.
	Skip,
}

asynchronous rob's avatar
asynchronous rob committed
72
/// A backed candidate pending availability.
73
#[derive(Encode, Decode, PartialEq, TypeInfo)]
74
#[cfg_attr(test, derive(Debug, Default))]
asynchronous rob's avatar
asynchronous rob committed
75
76
77
pub struct CandidatePendingAvailability<H, N> {
	/// The availability core this is assigned to.
	core: CoreIndex,
78
79
	/// The candidate hash.
	hash: CandidateHash,
80
81
	/// The candidate descriptor.
	descriptor: CandidateDescriptor<H>,
asynchronous rob's avatar
asynchronous rob committed
82
83
	/// The received availability votes. One bit per validator.
	availability_votes: BitVec<BitOrderLsb0, u8>,
84
85
	/// The backers of the candidate pending availability.
	backers: BitVec<BitOrderLsb0, u8>,
asynchronous rob's avatar
asynchronous rob committed
86
87
88
89
	/// The block number of the relay-parent of the receipt.
	relay_parent_number: N,
	/// The block number of the relay-chain block this was backed in.
	backed_in_number: N,
90
91
	/// The group index backing this block.
	backing_group: GroupIndex,
asynchronous rob's avatar
asynchronous rob committed
92
93
}

94
95
96
97
98
99
100
101
102
103
104
105
impl<H, N> CandidatePendingAvailability<H, N> {
	/// Get the availability votes on the candidate.
	pub(crate) fn availability_votes(&self) -> &BitVec<BitOrderLsb0, u8> {
		&self.availability_votes
	}

	/// Get the relay-chain block number this was backed in.
	pub(crate) fn backed_in_number(&self) -> &N {
		&self.backed_in_number
	}

	/// Get the core index.
Shawn Tabrizi's avatar
Shawn Tabrizi committed
106
	pub(crate) fn core_occupied(&self) -> CoreIndex {
107
108
		self.core.clone()
	}
109
110
111
112
113
114

	/// Get the candidate hash.
	pub(crate) fn candidate_hash(&self) -> CandidateHash {
		self.hash
	}

Denis_P's avatar
Denis_P committed
115
	/// Get the candidate descriptor.
116
117
118
	pub(crate) fn candidate_descriptor(&self) -> &CandidateDescriptor<H> {
		&self.descriptor
	}
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

	#[cfg(any(feature = "runtime-benchmarks", test))]
	pub(crate) fn new(
		core: CoreIndex,
		hash: CandidateHash,
		descriptor: CandidateDescriptor<H>,
		availability_votes: BitVec<BitOrderLsb0, u8>,
		backers: BitVec<BitOrderLsb0, u8>,
		relay_parent_number: N,
		backed_in_number: N,
		backing_group: GroupIndex,
	) -> Self {
		Self {
			core,
			hash,
			descriptor,
			availability_votes,
			backers,
			relay_parent_number,
			backed_in_number,
			backing_group,
		}
	}
142
143
}

144
145
146
/// A hook for applying validator rewards
pub trait RewardValidators {
	// Reward the validators with the given indices for issuing backing statements.
Shawn Tabrizi's avatar
Shawn Tabrizi committed
147
	fn reward_backing(validators: impl IntoIterator<Item = ValidatorIndex>);
148
149
150
	// Reward the validators with the given indices for issuing availability bitfields.
	// Validators are sent to this hook when they have contributed to the availability
	// of a candidate by setting a bit in their bitfield.
Shawn Tabrizi's avatar
Shawn Tabrizi committed
151
	fn reward_bitfields(validators: impl IntoIterator<Item = ValidatorIndex>);
152
153
}

154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
/// Helper return type for `process_candidates`.
#[derive(Encode, Decode, PartialEq, TypeInfo)]
#[cfg_attr(test, derive(Debug))]
pub(crate) struct ProcessedCandidates<H = Hash> {
	pub(crate) core_indices: Vec<CoreIndex>,
	pub(crate) candidate_receipt_with_backing_validator_indices:
		Vec<(CandidateReceipt<H>, Vec<(ValidatorIndex, ValidityAttestation)>)>,
}

impl<H> Default for ProcessedCandidates<H> {
	fn default() -> Self {
		Self {
			core_indices: Vec::new(),
			candidate_receipt_with_backing_validator_indices: Vec::new(),
		}
	}
}

172
173
174
#[frame_support::pallet]
pub mod pallet {
	use super::*;
asynchronous rob's avatar
asynchronous rob committed
175

176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
	#[pallet::pallet]
	#[pallet::generate_store(pub(super) trait Store)]
	pub struct Pallet<T>(_);

	#[pallet::config]
	pub trait Config:
		frame_system::Config
		+ shared::Config
		+ paras::Config
		+ dmp::Config
		+ ump::Config
		+ hrmp::Config
		+ configuration::Config
	{
		type Event: From<Event<Self>> + IsType<<Self as frame_system::Config>::Event>;
		type DisputesHandler: disputes::DisputesHandler<Self::BlockNumber>;
		type RewardValidators: RewardValidators;
	}
asynchronous rob's avatar
asynchronous rob committed
194

195
196
197
198
199
200
201
202
203
	#[pallet::event]
	#[pallet::generate_deposit(pub(super) fn deposit_event)]
	pub enum Event<T: Config> {
		/// A candidate was backed. `[candidate, head_data]`
		CandidateBacked(CandidateReceipt<T::Hash>, HeadData, CoreIndex, GroupIndex),
		/// A candidate was included. `[candidate, head_data]`
		CandidateIncluded(CandidateReceipt<T::Hash>, HeadData, CoreIndex, GroupIndex),
		/// A candidate timed out. `[candidate, head_data]`
		CandidateTimedOut(CandidateReceipt<T::Hash>, HeadData, CoreIndex),
asynchronous rob's avatar
asynchronous rob committed
204
205
	}

206
207
	#[pallet::error]
	pub enum Error<T> {
asynchronous rob's avatar
asynchronous rob committed
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
		/// Availability bitfield has unexpected size.
		WrongBitfieldSize,
		/// Multiple bitfields submitted by same validator or validators out of order by index.
		BitfieldDuplicateOrUnordered,
		/// Validator index out of bounds.
		ValidatorIndexOutOfBounds,
		/// Invalid signature
		InvalidBitfieldSignature,
		/// Candidate submitted but para not scheduled.
		UnscheduledCandidate,
		/// Candidate scheduled despite pending candidate already existing for the para.
		CandidateScheduledBeforeParaFree,
		/// Candidate included with the wrong collator.
		WrongCollator,
		/// Scheduled cores out of order.
		ScheduledOutOfOrder,
224
225
		/// Head data exceeds the configured maximum.
		HeadDataTooLarge,
asynchronous rob's avatar
asynchronous rob committed
226
227
		/// Code upgrade prematurely.
		PrematureCodeUpgrade,
228
229
		/// Output code is too large
		NewCodeTooLarge,
asynchronous rob's avatar
asynchronous rob committed
230
231
232
233
234
235
236
237
238
239
		/// Candidate not in parent context.
		CandidateNotInParentContext,
		/// Invalid group index in core assignment.
		InvalidGroupIndex,
		/// Insufficient (non-majority) backing.
		InsufficientBacking,
		/// Invalid (bad signature, unknown validator, etc.) backing.
		InvalidBacking,
		/// Collator did not sign PoV.
		NotCollatorSigned,
240
241
		/// The validation data hash does not match expected.
		ValidationDataHashMismatch,
242
243
		/// The downward message queue is not processed correctly.
		IncorrectDownwardMessageHandling,
244
245
		/// At least one upward message sent does not pass the acceptance criteria.
		InvalidUpwardMessages,
Sergey Pepyakin's avatar
Sergey Pepyakin committed
246
247
248
249
		/// The candidate didn't follow the rules of HRMP watermark advancement.
		HrmpWatermarkMishandling,
		/// The HRMP messages sent by the candidate is not valid.
		InvalidOutboundHrmp,
250
251
		/// The validation code hash of the candidate is not valid.
		InvalidValidationCodeHash,
252
253
254
		/// The `para_head` hash in the candidate descriptor doesn't match the hash of the actual para head in the
		/// commitments.
		ParaHeadMismatch,
255
256
257
258
		/// A bitfield that references a freed core,
		/// either intentionally or as part of a concluded
		/// invalid dispute.
		BitfieldReferencesFreedCore,
asynchronous rob's avatar
asynchronous rob committed
259
	}
260

261
262
	/// The latest bitfield for each validator, referred to by their index in the validator set.
	#[pallet::storage]
Shawn Tabrizi's avatar
Shawn Tabrizi committed
263
264
	pub(crate) type AvailabilityBitfields<T: Config> =
		StorageMap<_, Twox64Concat, ValidatorIndex, AvailabilityBitfieldRecord<T::BlockNumber>>;
265
266
267

	/// Candidates pending availability by `ParaId`.
	#[pallet::storage]
Shawn Tabrizi's avatar
Shawn Tabrizi committed
268
269
	pub(crate) type PendingAvailability<T: Config> =
		StorageMap<_, Twox64Concat, ParaId, CandidatePendingAvailability<T::Hash, T::BlockNumber>>;
270
271
272

	/// The commitments of candidates pending availability, by `ParaId`.
	#[pallet::storage]
Shawn Tabrizi's avatar
Shawn Tabrizi committed
273
274
	pub(crate) type PendingAvailabilityCommitments<T: Config> =
		StorageMap<_, Twox64Concat, ParaId, CandidateCommitments>;
275
276
277

	#[pallet::call]
	impl<T: Config> Pallet<T> {}
asynchronous rob's avatar
asynchronous rob committed
278
279
}

280
const LOG_TARGET: &str = "runtime::inclusion";
asynchronous rob's avatar
asynchronous rob committed
281

282
impl<T: Config> Pallet<T> {
asynchronous rob's avatar
asynchronous rob committed
283
	/// Block initialization logic, called by initializer.
Shawn Tabrizi's avatar
Shawn Tabrizi committed
284
285
286
	pub(crate) fn initializer_initialize(_now: T::BlockNumber) -> Weight {
		0
	}
asynchronous rob's avatar
asynchronous rob committed
287
288

	/// Block finalization logic, called by initializer.
Shawn Tabrizi's avatar
Shawn Tabrizi committed
289
	pub(crate) fn initializer_finalize() {}
asynchronous rob's avatar
asynchronous rob committed
290
291
292

	/// Handle an incoming session change.
	pub(crate) fn initializer_on_new_session(
Shawn Tabrizi's avatar
Shawn Tabrizi committed
293
		_notification: &crate::initializer::SessionChangeNotification<T::BlockNumber>,
asynchronous rob's avatar
asynchronous rob committed
294
295
296
	) {
		// unlike most drain methods, drained elements are not cleared on `Drop` of the iterator
		// and require consumption.
Shawn Tabrizi's avatar
Shawn Tabrizi committed
297
298
299
		for _ in <PendingAvailabilityCommitments<T>>::drain() {}
		for _ in <PendingAvailability<T>>::drain() {}
		for _ in <AvailabilityBitfields<T>>::drain() {}
asynchronous rob's avatar
asynchronous rob committed
300
301
	}

302
	/// Extract the freed cores based on cores that became available.
303
	///
304
305
	/// Updates storage items `PendingAvailability` and `AvailabilityBitfields`.
	pub(crate) fn update_pending_availability_and_get_freed_cores<F, const ON_CHAIN_USE: bool>(
306
		expected_bits: usize,
307
308
309
310
311
312
313
		validators: &[ValidatorId],
		signed_bitfields: UncheckedSignedAvailabilityBitfields,
		core_lookup: F,
	) -> Vec<(CoreIndex, CandidateHash)>
	where
		F: Fn(CoreIndex) -> Option<ParaId>,
	{
314
		let mut assigned_paras_record = (0..expected_bits)
asynchronous rob's avatar
asynchronous rob committed
315
			.map(|bit_index| core_lookup(CoreIndex::from(bit_index as u32)))
316
317
318
319
			.map(|opt_para_id| {
				opt_para_id.map(|para_id| (para_id, PendingAvailability::<T>::get(&para_id)))
			})
			.collect::<Vec<_>>();
asynchronous rob's avatar
asynchronous rob committed
320

321
		let now = <frame_system::Pallet<T>>::block_number();
322
323
324
325
326
327
328
329
		for (checked_bitfield, validator_index) in
			signed_bitfields.into_iter().map(|signed_bitfield| {
				// extracting unchecked data, since it's checked in `fn sanitize_bitfields` already.
				let validator_idx = signed_bitfield.unchecked_validator_index();
				let checked_bitfield = signed_bitfield.unchecked_into_payload();
				(checked_bitfield, validator_idx)
			}) {
			for (bit_idx, _) in checked_bitfield.0.iter().enumerate().filter(|(_, is_av)| **is_av) {
330
331
332
333
334
335
336
337
338
339
340
				let pending_availability = if let Some((_, pending_availability)) =
					assigned_paras_record[bit_idx].as_mut()
				{
					pending_availability
				} else {
					// For honest validators, this happens in case of unoccupied cores,
					// which in turn happens in case of a disputed candidate.
					// A malicious one might include arbitrary indices, but they are represented
					// by `None` values and will be sorted out in the next if case.
					continue
				};
asynchronous rob's avatar
asynchronous rob committed
341
342
343

				// defensive check - this is constructed by loading the availability bitfield record,
				// which is always `Some` if the core is occupied - that's why we're here.
344
				let validator_index = validator_index.0 as usize;
345
346
				if let Some(mut bit) =
					pending_availability.as_mut().and_then(|candidate_pending_availability| {
347
						candidate_pending_availability.availability_votes.get_mut(validator_index)
348
					}) {
asynchronous rob's avatar
asynchronous rob committed
349
350
351
352
					*bit = true;
				}
			}

353
354
			let record =
				AvailabilityBitfieldRecord { bitfield: checked_bitfield, submitted_at: now };
asynchronous rob's avatar
asynchronous rob committed
355

356
			<AvailabilityBitfields<T>>::insert(&validator_index, record);
asynchronous rob's avatar
asynchronous rob committed
357
358
359
360
		}

		let threshold = availability_threshold(validators.len());

361
		let mut freed_cores = Vec::with_capacity(expected_bits);
Shawn Tabrizi's avatar
Shawn Tabrizi committed
362
363
		for (para_id, pending_availability) in assigned_paras_record
			.into_iter()
asynchronous rob's avatar
asynchronous rob committed
364
365
366
367
368
			.filter_map(|x| x)
			.filter_map(|(id, p)| p.map(|p| (id, p)))
		{
			if pending_availability.availability_votes.count_ones() >= threshold {
				<PendingAvailability<T>>::remove(&para_id);
369
				let commitments = match PendingAvailabilityCommitments::<T>::take(&para_id) {
370
371
					Some(commitments) => commitments,
					None => {
372
373
374
375
376
						log::warn!(
							target: LOG_TARGET,
							"Inclusion::process_bitfields: PendingAvailability and PendingAvailabilityCommitments
							are out of sync, did someone mess with the storage?",
						);
Shawn Tabrizi's avatar
Shawn Tabrizi committed
377
378
						continue
					},
379
380
				};

381
382
383
384
385
386
387
388
389
390
391
392
393
394
				if ON_CHAIN_USE {
					let receipt = CommittedCandidateReceipt {
						descriptor: pending_availability.descriptor,
						commitments,
					};
					let _weight = Self::enact_candidate(
						pending_availability.relay_parent_number,
						receipt,
						pending_availability.backers,
						pending_availability.availability_votes,
						pending_availability.core,
						pending_availability.backing_group,
					);
				}
asynchronous rob's avatar
asynchronous rob committed
395

asynchronous rob's avatar
asynchronous rob committed
396
				freed_cores.push((pending_availability.core, pending_availability.hash));
asynchronous rob's avatar
asynchronous rob committed
397
398
399
400
401
			} else {
				<PendingAvailability<T>>::insert(&para_id, &pending_availability);
			}
		}

402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
		freed_cores
	}

	/// Process a set of incoming bitfields.
	///
	/// Returns a `Vec` of `CandidateHash`es and their respective `AvailabilityCore`s that became available,
	/// and cores free.
	pub(crate) fn process_bitfields(
		expected_bits: usize,
		signed_bitfields: UncheckedSignedAvailabilityBitfields,
		disputed_bitfield: DisputedBitfield,
		core_lookup: impl Fn(CoreIndex) -> Option<ParaId>,
	) -> Vec<(CoreIndex, CandidateHash)> {
		let validators = shared::Pallet::<T>::active_validator_keys();
		let session_index = shared::Pallet::<T>::session_index();
		let parent_hash = frame_system::Pallet::<T>::parent_hash();

419
		let checked_bitfields = sanitize_bitfields::<T>(
420
421
422
423
424
425
			signed_bitfields,
			disputed_bitfield,
			expected_bits,
			parent_hash,
			session_index,
			&validators[..],
426
			FullCheck::Yes,
427
428
429
430
431
432
433
434
435
436
		);

		let freed_cores = Self::update_pending_availability_and_get_freed_cores::<_, true>(
			expected_bits,
			&validators[..],
			checked_bitfields,
			core_lookup,
		);

		freed_cores
asynchronous rob's avatar
asynchronous rob committed
437
438
	}

439
440
	/// Process candidates that have been backed. Provide the relay storage root, a set of candidates
	/// and scheduled cores.
asynchronous rob's avatar
asynchronous rob committed
441
442
443
	///
	/// Both should be sorted ascending by core index, and the candidates should be a subset of
	/// scheduled cores. If these conditions are not met, the execution of the function fails.
444
	pub(crate) fn process_candidates<GV>(
445
		parent_storage_root: T::Hash,
asynchronous rob's avatar
asynchronous rob committed
446
447
		candidates: Vec<BackedCandidate<T::Hash>>,
		scheduled: Vec<CoreAssignment>,
448
449
450
451
452
453
		group_validators: GV,
		full_check: FullCheck,
	) -> Result<ProcessedCandidates<T::Hash>, DispatchError>
	where
		GV: Fn(GroupIndex) -> Option<Vec<ValidatorIndex>>,
	{
asynchronous rob's avatar
asynchronous rob committed
454
455
456
		ensure!(candidates.len() <= scheduled.len(), Error::<T>::UnscheduledCandidate);

		if scheduled.is_empty() {
457
			return Ok(ProcessedCandidates::default())
asynchronous rob's avatar
asynchronous rob committed
458
459
		}

460
		let validators = shared::Pallet::<T>::active_validator_keys();
461
		let parent_hash = <frame_system::Pallet<T>>::parent_hash();
462
463
464

		// At the moment we assume (and in fact enforce, below) that the relay-parent is always one
		// before of the block where we include a candidate (i.e. this code path).
465
		let now = <frame_system::Pallet<T>>::block_number();
466
		let relay_parent_number = now - One::one();
467
		let check_ctx = CandidateCheckContext::<T>::new(now, relay_parent_number);
asynchronous rob's avatar
asynchronous rob committed
468

469
470
471
472
473
		// Collect candidate receipts with backers.
		let mut candidate_receipt_with_backing_validator_indices =
			Vec::with_capacity(candidates.len());

		// Do all checks before writing storage.
474
		let core_indices_and_backers = {
asynchronous rob's avatar
asynchronous rob committed
475
			let mut skip = 0;
476
			let mut core_indices_and_backers = Vec::with_capacity(candidates.len());
asynchronous rob's avatar
asynchronous rob committed
477
478
479
480
481
482
483
484
485
486
487
488
			let mut last_core = None;

			let mut check_assignment_in_order = |assignment: &CoreAssignment| -> DispatchResult {
				ensure!(
					last_core.map_or(true, |core| assignment.core > core),
					Error::<T>::ScheduledOutOfOrder,
				);

				last_core = Some(assignment.core);
				Ok(())
			};

Shawn Tabrizi's avatar
Shawn Tabrizi committed
489
490
			let signing_context =
				SigningContext { parent_hash, session_index: shared::Pallet::<T>::session_index() };
asynchronous rob's avatar
asynchronous rob committed
491
492
493
494
495
496
497
498
499
500
501

			// We combine an outer loop over candidates with an inner loop over the scheduled,
			// where each iteration of the outer loop picks up at the position
			// in scheduled just after the past iteration left off.
			//
			// If the candidates appear in the same order as they appear in `scheduled`,
			// then they should always be found. If the end of `scheduled` is reached,
			// then the candidate was either not scheduled or out-of-order.
			//
			// In the meantime, we do certain sanity checks on the candidates and on the scheduled
			// list.
502
503
504
505
506
507
508
509
510
511
512
			'next_backed_candidate: for (candidate_idx, backed_candidate) in
				candidates.iter().enumerate()
			{
				if let FullCheck::Yes = full_check {
					check_ctx.verify_backed_candidate(
						parent_hash,
						candidate_idx,
						backed_candidate,
					)?;
				}

513
				let para_id = backed_candidate.descriptor().para_id;
514
				let mut backers = bitvec::bitvec![BitOrderLsb0, u8; 0; validators.len()];
asynchronous rob's avatar
asynchronous rob committed
515
516
517
518

				for (i, assignment) in scheduled[skip..].iter().enumerate() {
					check_assignment_in_order(assignment)?;

519
					if para_id == assignment.para_id {
asynchronous rob's avatar
asynchronous rob committed
520
521
						if let Some(required_collator) = assignment.required_collator() {
							ensure!(
522
								required_collator == &backed_candidate.descriptor().collator,
asynchronous rob's avatar
asynchronous rob committed
523
524
525
526
								Error::<T>::WrongCollator,
							);
						}

527
528
						{
							// this should never fail because the para is registered
529
							let persisted_validation_data =
530
531
532
								match crate::util::make_persisted_validation_data::<T>(
									para_id,
									relay_parent_number,
533
									parent_storage_root,
534
								) {
535
536
537
538
539
									Some(l) => l,
									None => {
										// We don't want to error out here because it will
										// brick the relay-chain. So we return early without
										// doing anything.
540
										return Ok(ProcessedCandidates::default())
Shawn Tabrizi's avatar
Shawn Tabrizi committed
541
									},
542
								};
543

544
							let expected = persisted_validation_data.hash();
545
546

							ensure!(
547
548
								expected ==
									backed_candidate.descriptor().persisted_validation_data_hash,
549
550
551
552
								Error::<T>::ValidationDataHashMismatch,
							);
						}

asynchronous rob's avatar
asynchronous rob committed
553
						ensure!(
554
							<PendingAvailability<T>>::get(&para_id).is_none() &&
Shawn Tabrizi's avatar
Shawn Tabrizi committed
555
								<PendingAvailabilityCommitments<T>>::get(&para_id).is_none(),
asynchronous rob's avatar
asynchronous rob committed
556
557
558
559
560
561
562
563
564
565
566
							Error::<T>::CandidateScheduledBeforeParaFree,
						);

						// account for already skipped, and then skip this one.
						skip = i + skip + 1;

						let group_vals = group_validators(assignment.group_idx)
							.ok_or_else(|| Error::<T>::InvalidGroupIndex)?;

						// check the signatures in the backing and that it is a majority.
						{
Shawn Tabrizi's avatar
Shawn Tabrizi committed
567
							let maybe_amount_validated = primitives::v1::check_candidate_backing(
568
								&backed_candidate,
Shawn Tabrizi's avatar
Shawn Tabrizi committed
569
570
								&signing_context,
								group_vals.len(),
571
								|intra_group_vi| {
Shawn Tabrizi's avatar
Shawn Tabrizi committed
572
									group_vals
573
574
										.get(intra_group_vi)
										.and_then(|vi| validators.get(vi.0 as usize))
Shawn Tabrizi's avatar
Shawn Tabrizi committed
575
576
577
										.map(|v| v.clone())
								},
							);
asynchronous rob's avatar
asynchronous rob committed
578
579
580
581
582
583

							match maybe_amount_validated {
								Ok(amount_validated) => ensure!(
									amount_validated * 2 > group_vals.len(),
									Error::<T>::InsufficientBacking,
								),
Shawn Tabrizi's avatar
Shawn Tabrizi committed
584
585
586
								Err(()) => {
									Err(Error::<T>::InvalidBacking)?;
								},
asynchronous rob's avatar
asynchronous rob committed
587
							}
588

589
590
591
592
593
594
595
							let mut backer_idx_and_attestation =
								Vec::<(ValidatorIndex, ValidityAttestation)>::with_capacity(
									backed_candidate.validator_indices.count_ones(),
								);
							let candidate_receipt = backed_candidate.receipt();

							for ((bit_idx, _), attestation) in backed_candidate
Shawn Tabrizi's avatar
Shawn Tabrizi committed
596
597
598
599
								.validator_indices
								.iter()
								.enumerate()
								.filter(|(_, signed)| **signed)
600
								.zip(backed_candidate.validity_votes.iter().cloned())
601
							{
602
603
604
605
								let val_idx = group_vals
									.get(bit_idx)
									.expect("this query succeeded above; qed");
								backer_idx_and_attestation.push((*val_idx, attestation));
606

607
								backers.set(val_idx.0 as _, true);
608
							}
609
610
							candidate_receipt_with_backing_validator_indices
								.push((candidate_receipt, backer_idx_and_attestation));
asynchronous rob's avatar
asynchronous rob committed
611
612
						}

Shawn Tabrizi's avatar
Shawn Tabrizi committed
613
614
615
616
617
						core_indices_and_backers.push((
							assignment.core,
							backers,
							assignment.group_idx,
						));
618
						continue 'next_backed_candidate
asynchronous rob's avatar
asynchronous rob committed
619
620
621
622
623
624
					}
				}

				// end of loop reached means that the candidate didn't appear in the non-traversed
				// section of the `scheduled` slice. either it was not scheduled or didn't appear in
				// `candidates` in the correct order.
625
				ensure!(false, Error::<T>::UnscheduledCandidate);
626
			}
asynchronous rob's avatar
asynchronous rob committed
627
628
629
630
631
632

			// check remainder of scheduled cores, if any.
			for assignment in scheduled[skip..].iter() {
				check_assignment_in_order(assignment)?;
			}

633
			core_indices_and_backers
asynchronous rob's avatar
asynchronous rob committed
634
635
636
		};

		// one more sweep for actually writing to storage.
Shawn Tabrizi's avatar
Shawn Tabrizi committed
637
638
639
640
641
		let core_indices =
			core_indices_and_backers.iter().map(|&(ref c, _, _)| c.clone()).collect();
		for (candidate, (core, backers, group)) in
			candidates.into_iter().zip(core_indices_and_backers)
		{
asynchronous rob's avatar
asynchronous rob committed
642
			let para_id = candidate.descriptor().para_id;
asynchronous rob's avatar
asynchronous rob committed
643
644

			// initialize all availability votes to 0.
Shawn Tabrizi's avatar
Shawn Tabrizi committed
645
646
			let availability_votes: BitVec<BitOrderLsb0, u8> =
				bitvec::bitvec![BitOrderLsb0, u8; 0; validators.len()];
647
648
649
650

			Self::deposit_event(Event::<T>::CandidateBacked(
				candidate.candidate.to_plain(),
				candidate.candidate.commitments.head_data.clone(),
651
652
				core,
				group,
653
654
			));

655
656
			let candidate_hash = candidate.candidate.hash();

Shawn Tabrizi's avatar
Shawn Tabrizi committed
657
658
659
660
661
662
663
664
665
666
667
			let (descriptor, commitments) =
				(candidate.candidate.descriptor, candidate.candidate.commitments);

			<PendingAvailability<T>>::insert(
				&para_id,
				CandidatePendingAvailability {
					core,
					hash: candidate_hash,
					descriptor,
					availability_votes,
					relay_parent_number,
668
					backers: backers.to_bitvec(),
669
					backed_in_number: check_ctx.now,
Shawn Tabrizi's avatar
Shawn Tabrizi committed
670
671
					backing_group: group,
				},
672
			);
673
			<PendingAvailabilityCommitments<T>>::insert(&para_id, commitments);
asynchronous rob's avatar
asynchronous rob committed
674
675
		}

676
677
678
679
		Ok(ProcessedCandidates::<T::Hash> {
			core_indices,
			candidate_receipt_with_backing_validator_indices,
		})
asynchronous rob's avatar
asynchronous rob committed
680
681
	}

682
	/// Run the acceptance criteria checks on the given candidate commitments.
683
	pub(crate) fn check_validation_outputs_for_runtime_api(
684
		para_id: ParaId,
685
		validation_outputs: primitives::v1::CandidateCommitments,
686
	) -> bool {
687
688
		// This function is meant to be called from the runtime APIs against the relay-parent, hence
		// `relay_parent_number` is equal to `now`.
689
		let now = <frame_system::Pallet<T>>::block_number();
690
		let relay_parent_number = now;
691
		let check_ctx = CandidateCheckContext::<T>::new(now, relay_parent_number);
692

693
		if let Err(err) = check_ctx.check_validation_outputs(
694
695
696
			para_id,
			&validation_outputs.head_data,
			&validation_outputs.new_validation_code,
697
			validation_outputs.processed_downward_messages,
698
			&validation_outputs.upward_messages,
Sergey Pepyakin's avatar
Sergey Pepyakin committed
699
700
			T::BlockNumber::from(validation_outputs.hrmp_watermark),
			&validation_outputs.horizontal_messages,
701
702
703
704
705
706
707
708
709
710
711
		) {
			log::debug!(
				target: LOG_TARGET,
				"Validation outputs checking for parachain `{}` failed: {:?}",
				u32::from(para_id),
				err,
			);
			false
		} else {
			true
		}
712
713
	}

asynchronous rob's avatar
asynchronous rob committed
714
715
	fn enact_candidate(
		relay_parent_number: T::BlockNumber,
asynchronous rob's avatar
asynchronous rob committed
716
		receipt: CommittedCandidateReceipt<T::Hash>,
717
718
		backers: BitVec<BitOrderLsb0, u8>,
		availability_votes: BitVec<BitOrderLsb0, u8>,
719
720
		core_index: CoreIndex,
		backing_group: GroupIndex,
asynchronous rob's avatar
asynchronous rob committed
721
	) -> Weight {
722
		let plain = receipt.to_plain();
asynchronous rob's avatar
asynchronous rob committed
723
		let commitments = receipt.commitments;
724
		let config = <configuration::Pallet<T>>::config();
asynchronous rob's avatar
asynchronous rob committed
725

Shawn Tabrizi's avatar
Shawn Tabrizi committed
726
727
728
729
730
731
		T::RewardValidators::reward_backing(
			backers
				.iter()
				.enumerate()
				.filter(|(_, backed)| **backed)
				.map(|(i, _)| ValidatorIndex(i as _)),
732
733
		);

Shawn Tabrizi's avatar
Shawn Tabrizi committed
734
735
736
737
738
739
		T::RewardValidators::reward_bitfields(
			availability_votes
				.iter()
				.enumerate()
				.filter(|(_, voted)| **voted)
				.map(|(i, _)| ValidatorIndex(i as _)),
740
741
		);

asynchronous rob's avatar
asynchronous rob committed
742
743
744
		// initial weight is config read.
		let mut weight = T::DbWeight::get().reads_writes(1, 0);
		if let Some(new_code) = commitments.new_validation_code {
ferrell-code's avatar
ferrell-code committed
745
			weight += <paras::Pallet<T>>::schedule_code_upgrade(
asynchronous rob's avatar
asynchronous rob committed
746
				receipt.descriptor.para_id,
asynchronous rob's avatar
asynchronous rob committed
747
				new_code,
748
749
				relay_parent_number,
				&config,
asynchronous rob's avatar
asynchronous rob committed
750
751
752
			);
		}

753
		// enact the messaging facet of the candidate.
754
		weight += <dmp::Pallet<T>>::prune_dmq(
755
756
757
			receipt.descriptor.para_id,
			commitments.processed_downward_messages,
		);
758
		weight += <ump::Pallet<T>>::receive_upward_messages(
759
760
761
			receipt.descriptor.para_id,
			commitments.upward_messages,
		);
762
		weight += <hrmp::Pallet<T>>::prune_hrmp(
Sergey Pepyakin's avatar
Sergey Pepyakin committed
763
764
765
			receipt.descriptor.para_id,
			T::BlockNumber::from(commitments.hrmp_watermark),
		);
766
		weight += <hrmp::Pallet<T>>::queue_outbound_hrmp(
Sergey Pepyakin's avatar
Sergey Pepyakin committed
767
768
769
			receipt.descriptor.para_id,
			commitments.horizontal_messages,
		);
770

Shawn Tabrizi's avatar
Shawn Tabrizi committed
771
772
773
774
775
776
		Self::deposit_event(Event::<T>::CandidateIncluded(
			plain,
			commitments.head_data.clone(),
			core_index,
			backing_group,
		));
777

Shawn Tabrizi's avatar
Shawn Tabrizi committed
778
779
780
781
782
783
		weight +
			<paras::Pallet<T>>::note_new_head(
				receipt.descriptor.para_id,
				commitments.head_data,
				relay_parent_number,
			)
asynchronous rob's avatar
asynchronous rob committed
784
785
786
787
788
789
790
791
	}

	/// Cleans up all paras pending availability that the predicate returns true for.
	///
	/// The predicate accepts the index of the core and the block number the core has been occupied
	/// since (i.e. the block number the candidate was backed at in this fork of the relay chain).
	///
	/// Returns a vector of cleaned-up core IDs.
Shawn Tabrizi's avatar
Shawn Tabrizi committed
792
793
794
	pub(crate) fn collect_pending(
		pred: impl Fn(CoreIndex, T::BlockNumber) -> bool,
	) -> Vec<CoreIndex> {
asynchronous rob's avatar
asynchronous rob committed
795
796
797
798
799
800
801
802
803
804
805
		let mut cleaned_up_ids = Vec::new();
		let mut cleaned_up_cores = Vec::new();

		for (para_id, pending_record) in <PendingAvailability<T>>::iter() {
			if pred(pending_record.core, pending_record.backed_in_number) {
				cleaned_up_ids.push(para_id);
				cleaned_up_cores.push(pending_record.core);
			}
		}

		for para_id in cleaned_up_ids {
806
			let pending = <PendingAvailability<T>>::take(&para_id);
807
			let commitments = <PendingAvailabilityCommitments<T>>::take(&para_id);
808
809
810
811
812
813
814
815
816
817
818

			if let (Some(pending), Some(commitments)) = (pending, commitments) {
				// defensive: this should always be true.
				let candidate = CandidateReceipt {
					descriptor: pending.descriptor,
					commitments_hash: commitments.hash(),
				};

				Self::deposit_event(Event::<T>::CandidateTimedOut(
					candidate,
					commitments.head_data,
819
					pending.core,
820
821
				));
			}
asynchronous rob's avatar
asynchronous rob committed
822
823
824
825
		}

		cleaned_up_cores
	}
826

asynchronous rob's avatar
asynchronous rob committed
827
828
829
	/// Cleans up all paras pending availability that are in the given list of disputed candidates.
	///
	/// Returns a vector of cleaned-up core IDs.
830
	pub(crate) fn collect_disputed(disputed: &BTreeSet<CandidateHash>) -> Vec<CoreIndex> {
asynchronous rob's avatar
asynchronous rob committed
831
832
833
834
835
836
837
838
839
840
841
842
		let mut cleaned_up_ids = Vec::new();
		let mut cleaned_up_cores = Vec::new();

		for (para_id, pending_record) in <PendingAvailability<T>>::iter() {
			if disputed.contains(&pending_record.hash) {
				cleaned_up_ids.push(para_id);
				cleaned_up_cores.push(pending_record.core);
			}
		}

		for para_id in cleaned_up_ids {
			let _ = <PendingAvailability<T>>::take(&para_id);
843
			let _ = <PendingAvailabilityCommitments<T>>::take(&para_id);
asynchronous rob's avatar
asynchronous rob committed
844
845
846
847
848
		}

		cleaned_up_cores
	}

849
850
851
852
853
854
855
856
	/// Forcibly enact the candidate with the given ID as though it had been deemed available
	/// by bitfields.
	///
	/// Is a no-op if there is no candidate pending availability for this para-id.
	/// This should generally not be used but it is useful during execution of Runtime APIs,
	/// where the changes to the state are expected to be discarded directly after.
	pub(crate) fn force_enact(para: ParaId) {
		let pending = <PendingAvailability<T>>::take(&para);
857
		let commitments = <PendingAvailabilityCommitments<T>>::take(&para);
858
859

		if let (Some(pending), Some(commitments)) = (pending, commitments) {
Shawn Tabrizi's avatar
Shawn Tabrizi committed
860
861
			let candidate =
				CommittedCandidateReceipt { descriptor: pending.descriptor, commitments };
862
863
864
865

			Self::enact_candidate(
				pending.relay_parent_number,
				candidate,
866
867
				pending.backers,
				pending.availability_votes,
868
869
				pending.core,
				pending.backing_group,
870
871
872
873
			);
		}
	}

Denis_P's avatar
Denis_P committed
874
	/// Returns the `CommittedCandidateReceipt` pending availability for the para provided, if any.
Shawn Tabrizi's avatar
Shawn Tabrizi committed
875
876
877
	pub(crate) fn candidate_pending_availability(
		para: ParaId,
	) -> Option<CommittedCandidateReceipt<T::Hash>> {
878
879
		<PendingAvailability<T>>::get(&para)
			.map(|p| p.descriptor)
880
			.and_then(|d| <PendingAvailabilityCommitments<T>>::get(&para).map(move |c| (d, c)))
881
882
883
884
885
			.map(|(d, c)| CommittedCandidateReceipt { descriptor: d, commitments: c })
	}

	/// Returns the metadata around the candidate pending availability for the
	/// para provided, if any.
Shawn Tabrizi's avatar
Shawn Tabrizi committed
886
887
888
	pub(crate) fn pending_availability(
		para: ParaId,
	) -> Option<CandidatePendingAvailability<T::Hash, T::BlockNumber>> {
889
890
		<PendingAvailability<T>>::get(&para)
	}
asynchronous rob's avatar
asynchronous rob committed
891
892
893
894
895
896
897
898
}

const fn availability_threshold(n_validators: usize) -> usize {
	let mut threshold = (n_validators * 2) / 3;
	threshold += (n_validators * 2) % 3;
	threshold
}

899
900
901
902
903
#[derive(derive_more::From, Debug)]
enum AcceptanceCheckErr<BlockNumber> {
	HeadDataTooLarge,
	PrematureCodeUpgrade,
	NewCodeTooLarge,
904
905
906
907
	ProcessedDownwardMessages(dmp::ProcessedDownwardMessagesAcceptanceErr),
	UpwardMessages(ump::AcceptanceCheckErr),
	HrmpWatermark(hrmp::HrmpWatermarkAcceptanceErr<BlockNumber>),
	OutboundHrmp(hrmp::OutboundHrmpAcceptanceErr),
908
909
910
911
912
}

impl<BlockNumber> AcceptanceCheckErr<BlockNumber> {
	/// Returns the same error so that it can be threaded through a needle of `DispatchError` and
	/// ultimately returned from a `Dispatchable`.
913
	fn strip_into_dispatch_err<T: Config>(self) -> Error<T> {
914
915
916
917
918
919
920
921
922
923
924
925
926
		use AcceptanceCheckErr::*;
		match self {
			HeadDataTooLarge => Error::<T>::HeadDataTooLarge,
			PrematureCodeUpgrade => Error::<T>::PrematureCodeUpgrade,
			NewCodeTooLarge => Error::<T>::NewCodeTooLarge,
			ProcessedDownwardMessages(_) => Error::<T>::IncorrectDownwardMessageHandling,
			UpwardMessages(_) => Error::<T>::InvalidUpwardMessages,
			HrmpWatermark(_) => Error::<T>::HrmpWatermarkMishandling,
			OutboundHrmp(_) => Error::<T>::InvalidOutboundHrmp,
		}
	}
}

927
/// A collection of data required for checking a candidate.
928
pub(crate) struct CandidateCheckContext<T: Config> {
929
930
931
932
933
	config: configuration::HostConfiguration<T::BlockNumber>,
	now: T::BlockNumber,
	relay_parent_number: T::BlockNumber,
}

934
impl<T: Config> CandidateCheckContext<T> {
935
	pub(crate) fn new(now: T::BlockNumber, relay_parent_number: T::BlockNumber) -> Self {
Shawn Tabrizi's avatar
Shawn Tabrizi committed
936
		Self { config: <configuration::Pallet<T>>::config(), now, relay_parent_number }
937
938
	}

939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
	/// Execute verification of the candidate.
	///
	/// Assures:
	///  * correct expected relay parent reference
	///  * collator signature check passes
	///  * code hash of commitments matches current code hash
	///  * para head in the descriptor and commitments match
	pub(crate) fn verify_backed_candidate(
		&self,
		parent_hash: <T as frame_system::Config>::Hash,
		candidate_idx: usize,
		backed_candidate: &BackedCandidate<<T as frame_system::Config>::Hash>,
	) -> Result<(), Error<T>> {
		let para_id = backed_candidate.descriptor().para_id;
		let now = self.now;

		// we require that the candidate is in the context of the parent block.
		ensure!(
			backed_candidate.descriptor().relay_parent == parent_hash,
			Error::<T>::CandidateNotInParentContext,
		);
		ensure!(
			backed_candidate.descriptor().check_collator_signature().is_ok(),
			Error::<T>::NotCollatorSigned,
		);

		let validation_code_hash = <paras::Pallet<T>>::validation_code_hash_at(para_id, now, None)
			// A candidate for a parachain without current validation code is not scheduled.
			.ok_or_else(|| Error::<T>::UnscheduledCandidate)?;
		ensure!(
			backed_candidate.descriptor().validation_code_hash == validation_code_hash,
			Error::<T>::InvalidValidationCodeHash,
		);

		ensure!(
			backed_candidate.descriptor().para_head ==
				backed_candidate.candidate.commitments.head_data.hash(),
			Error::<T>::ParaHeadMismatch,
		);

		if let Err(err) = self.check_validation_outputs(
			para_id,
			&backed_candidate.candidate.commitments.head_data,
			&backed_candidate.candidate.commitments.new_validation_code,
			backed_candidate.candidate.commitments.processed_downward_messages,
			&backed_candidate.candidate.commitments.upward_messages,
			T::BlockNumber::from(backed_candidate.candidate.commitments.hrmp_watermark),
			&backed_candidate.candidate.commitments.horizontal_messages,
		) {
			log::debug!(
				target: LOG_TARGET,
				"Validation outputs checking during inclusion of a candidate {} for parachain `{}` failed: {:?}",
				candidate_idx,
				u32::from(para_id),
				err,
			);
			Err(err.strip_into_dispatch_err::<T>())?;
		};
		Ok(())
	}

1000
	/// Check the given outputs after candidate validation on whether it passes the acceptance
For faster browsing, not all history is shown. View entire blame