parachains.rs 112 KB
Newer Older
Shawn Tabrizi's avatar
Shawn Tabrizi committed
1
// Copyright 2017-2020 Parity Technologies (UK) Ltd.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 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/>.

//! Main parachains logic. For now this is just the determination of which validators do what.

19
20
use sp_std::prelude::*;
use sp_std::result;
21
use codec::{Decode, Encode};
22
23
24
use sp_runtime::{
	KeyTypeId, Perbill, RuntimeDebug,
	traits::{
25
		Hash as HashT, BlakeTwo256, Saturating, One, Zero, Dispatchable,
26
		AccountIdConversion, BadOrigin, Convert, SignedExtension, AppVerify,
27
		DispatchInfoOf,
28
29
30
31
32
33
34
35
36
	},
	transaction_validity::{TransactionValidityError, ValidTransaction, TransactionValidity},
};
use sp_staking::{
	SessionIndex,
	offence::{ReportOffence, Offence, Kind},
};
use frame_support::{
	traits::KeyOwnerProofSystem,
37
	dispatch::{IsSubType},
38
	weights::{DispatchClass, Weight},
39
};
40
use primitives::{
Ashley's avatar
Ashley committed
41
	Balance,
42
	BlockNumber,
43
	parachain::{
44
		Id as ParaId, Chain, DutyRoster, AttestedCandidate, Statement, ParachainDispatchOrigin,
45
46
		UpwardMessage, ValidatorId, ActiveParas, CollatorId, Retriable, OmittedValidationData,
		CandidateReceipt, GlobalValidationSchedule, AbridgedCandidateReceipt,
47
		LocalValidationData, Scheduling, ValidityAttestation, NEW_HEADS_IDENTIFIER, PARACHAIN_KEY_TYPE_ID,
48
		ValidatorSignature, SigningContext, HeadData, ValidationCode,
49
50
	},
};
51
use frame_support::{
52
	Parameter, dispatch::DispatchResult, decl_storage, decl_module, decl_error, ensure,
53
	traits::{Currency, Get, WithdrawReason, ExistenceRequirement, Randomness},
54
};
55
56
57
use sp_runtime::{
	transaction_validity::InvalidTransaction,
};
58

Gavin Wood's avatar
Gavin Wood committed
59
use inherents::{ProvideInherent, InherentData, MakeFatalError, InherentIdentifier};
60

61
62
use system::{
	ensure_none, ensure_signed,
63
	offchain::{CreateSignedTransaction, SendSignedTransaction, Signer},
64
};
65
use crate::attestations::{self, IncludedBlocks};
66
use crate::registrar::Registrar;
67

68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
// ranges for iteration of general block number don't work, so this
// is a utility to get around that.
struct BlockNumberRange<N> {
	low: N,
	high: N,
}

impl<N: Saturating + One + PartialOrd + PartialEq + Clone> Iterator for BlockNumberRange<N> {
	type Item = N;

	fn next(&mut self) -> Option<N> {
		if self.low >= self.high {
			return None
		}

		let item = self.low.clone();
		self.low = self.low.clone().saturating_add(One::one());
		Some(item)
	}
}

89
90
91
92
// wrapper trait because an associated type of `Currency<Self::AccountId,Balance=Balance>`
// doesn't work.`
pub trait ParachainCurrency<AccountId> {
	fn free_balance(para_id: ParaId) -> Balance;
93
	fn deduct(para_id: ParaId, amount: Balance) -> DispatchResult;
94
95
96
97
98
99
100
101
102
103
104
}

impl<AccountId, T: Currency<AccountId>> ParachainCurrency<AccountId> for T where
	T::Balance: From<Balance> + Into<Balance>,
	ParaId: AccountIdConversion<AccountId>,
{
	fn free_balance(para_id: ParaId) -> Balance {
		let para_account = para_id.into_account();
		T::free_balance(&para_account).into()
	}

105
	fn deduct(para_id: ParaId, amount: Balance) -> DispatchResult {
106
107
108
109
110
111
		let para_account = para_id.into_account();

		// burn the fee.
		let _ = T::withdraw(
			&para_account,
			amount.into(),
Gavin Wood's avatar
Gavin Wood committed
112
			WithdrawReason::Fee.into(),
113
114
115
116
117
118
119
			ExistenceRequirement::KeepAlive,
		)?;

		Ok(())
	}
}

120
/// Interface to the persistent (stash) identities of the current validators.
121
pub struct ValidatorIdentities<T>(sp_std::marker::PhantomData<T>);
122

123
124
125
126
127
128
129
/// A structure used to report conflicting votes by validators.
///
/// It is generic over two parameters:
/// `Proof` - proof of historical ownership of a key by some validator.
/// `Hash` - a type of a hash used in the runtime.
#[derive(RuntimeDebug, Encode, Decode)]
#[derive(Clone, Eq, PartialEq)]
130
pub struct DoubleVoteReport<Proof> {
131
132
133
134
135
136
137
138
	/// Identity of the double-voter.
	pub identity: ValidatorId,
	/// First vote of the double-vote.
	pub first: (Statement, ValidatorSignature),
	/// Second vote of the double-vote.
	pub second: (Statement, ValidatorSignature),
	/// Proof that the validator with `identity` id was actually a validator at `parent_hash`.
	pub proof: Proof,
139
140
	/// A `SigningContext` with a session and a parent hash of the moment this offence was commited.
	pub signing_context: SigningContext,
141
142
}

143
impl<Proof: Parameter + GetSessionNumber> DoubleVoteReport<Proof> {
144
145
146
147
148
	fn verify<T: Trait<Proof = Proof>>(
		&self,
	) -> Result<(), DoubleVoteValidityError> {
		let first = self.first.clone();
		let second = self.second.clone();
149
		let id = self.identity.clone();
150
151
152
153

		T::KeyOwnerProofSystem::check_proof((PARACHAIN_KEY_TYPE_ID, id), self.proof.clone())
			.ok_or(DoubleVoteValidityError::InvalidProof)?;

154
155
156
157
		if self.proof.session() != self.signing_context.session_index {
			return Err(DoubleVoteValidityError::InvalidReport);
		}

158
		// Check signatures.
159
160
161
162
163
164
165
166
167
168
		Self::verify_vote(
			&first,
			&self.signing_context,
			&self.identity,
		)?;
		Self::verify_vote(
			&second,
			&self.signing_context,
			&self.identity,
		)?;
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193

		match (&first.0, &second.0) {
			// If issuing a `Candidate` message on a parachain block, neither a `Valid` or
			// `Invalid` vote cannot be issued on that parachain block, as the `Candidate`
			// message is an implicit validity vote.
			(Statement::Candidate(candidate_hash), Statement::Valid(hash)) |
			(Statement::Candidate(candidate_hash), Statement::Invalid(hash)) |
			(Statement::Valid(hash), Statement::Candidate(candidate_hash)) |
			(Statement::Invalid(hash), Statement::Candidate(candidate_hash))
			if *candidate_hash == *hash => {},
			// Otherwise, it is illegal to cast both a `Valid` and
			// `Invalid` vote on a given parachain block.
			(Statement::Valid(hash_1), Statement::Invalid(hash_2)) |
			(Statement::Invalid(hash_1), Statement::Valid(hash_2))
			if *hash_1 == *hash_2 => {},
			_ => {
				return Err(DoubleVoteValidityError::NotDoubleVote);
			}
		}

		Ok(())
	}

	fn verify_vote(
		vote: &(Statement, ValidatorSignature),
194
		signing_context: &SigningContext,
195
196
		authority: &ValidatorId,
	) -> Result<(), DoubleVoteValidityError> {
197
		let payload = localized_payload(vote.0.clone(), signing_context);
198
199
200
201
202
203
204
205
206

		if !vote.1.verify(&payload[..], authority) {
			return Err(DoubleVoteValidityError::InvalidSignature);
		}

		Ok(())
	}
}

207
208
209
210
211
212
impl<T: session::Trait> Get<Vec<T::ValidatorId>> for ValidatorIdentities<T> {
	fn get() -> Vec<T::ValidatorId> {
		<session::Module<T>>::validators()
	}
}

213
/// A trait to get a session number the `MembershipProof` belongs to.
214
215
216
217
pub trait GetSessionNumber {
	fn session(&self) -> SessionIndex;
}

218
impl GetSessionNumber for sp_session::MembershipProof {
219
	fn session(&self) -> SessionIndex {
220
		self.session
221
222
223
	}
}

224
225
226
227
pub trait Trait: CreateSignedTransaction<Call<Self>> + attestations::Trait + session::historical::Trait {
	// The transaction signing authority
	type AuthorityId: system::offchain::AppCrypto<Self::Public, Self::Signature>;

228
229
230
231
	/// The outer origin type.
	type Origin: From<Origin> + From<system::RawOrigin<Self::AccountId>>;

	/// The outer call dispatch type.
232
	type Call: Parameter + Dispatchable<Origin=<Self as Trait>::Origin> + From<Call<Self>>;
233
234
235

	/// Some way of interacting with balances for fees.
	type ParachainCurrency: ParachainCurrency<Self::AccountId>;
236

237
238
239
240
241
	/// Polkadot in practice will always use the `BlockNumber` type.
	/// Substrate isn't good at giving us ways to bound the supertrait
	/// associated type, so we introduce this conversion.
	type BlockNumberConversion: Convert<Self::BlockNumber, BlockNumber>;

242
243
244
	/// Something that provides randomness in the runtime.
	type Randomness: Randomness<Self::Hash>;

245
246
247
248
249
	/// Means to determine what the current set of active parachains are.
	type ActiveParachains: ActiveParas;

	/// The way that we are able to register parachains.
	type Registrar: Registrar<Self::AccountId>;
250
251
252
253
254
255
256
257

	/// Maximum code size for parachains, in bytes. Note that this is not
	/// the entire storage burden of the parachain, as old code is stored for
	/// `SlashPeriod` blocks.
	type MaxCodeSize: Get<u32>;

	/// Max head data size.
	type MaxHeadDataSize: Get<u32>;
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
	/// The frequency at which paras can upgrade their validation function.
	/// This is an integer number of relay-chain blocks that must pass between
	/// code upgrades.
	type ValidationUpgradeFrequency: Get<Self::BlockNumber>;

	/// The delay before a validation function upgrade is applied.
	type ValidationUpgradeDelay: Get<Self::BlockNumber>;

	/// The period (in blocks) that slash reports are permitted against an
	/// included candidate.
	///
	/// After validation function upgrades, the old code is persisted on-chain
	/// for this period, to ensure that candidates validated under old functions
	/// can be re-checked.
	type SlashPeriod: Get<Self::BlockNumber>;
273
274
275
276
277
278
279
280
281
282

	/// Proof type.
	///
	/// We need this type to bind the `KeyOwnerProofSystem::Proof` to necessary bounds.
	/// As soon as https://rust-lang.github.io/rfcs/2289-associated-type-bounds.html
	/// gets in this can be simplified.
	type Proof: Parameter + GetSessionNumber;

	/// Compute and check proofs of historical key owners.
	type KeyOwnerProofSystem: KeyOwnerProofSystem<
283
		(KeyTypeId, ValidatorId),
284
285
286
287
288
289
290
291
292
293
294
		Proof = Self::Proof,
		IdentificationTuple = Self::IdentificationTuple,
	>;

	/// An identification tuple type bound to `Parameter`.
	type IdentificationTuple: Parameter;

	/// Report an offence.
	type ReportOffence: ReportOffence<
		Self::AccountId,
		Self::IdentificationTuple,
295
		DoubleVoteOffence<Self::IdentificationTuple>,
296
	>;
297
298
299

	/// A type that converts the opaque hash type to exact one.
	type BlockHashConversion: Convert<Self::Hash, primitives::Hash>;
300
301
302
303
304
305
306
307
}

/// Origin for the parachains module.
#[derive(PartialEq, Eq, Clone)]
#[cfg_attr(feature = "std", derive(Debug))]
pub enum Origin {
	/// It comes from a parachain.
	Parachain(ParaId),
Gavin Wood's avatar
Gavin Wood committed
308
}
309

310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
/// An offence that is filed if the validator has submitted a double vote.
#[derive(RuntimeDebug)]
#[cfg_attr(feature = "std", derive(Clone, PartialEq, Eq))]
pub struct DoubleVoteOffence<Offender> {
	/// The current session index in which we report a validator.
	session_index: SessionIndex,
	/// The size of the validator set in current session/era.
	validator_set_count: u32,
	/// An offender that has submitted two conflicting votes.
	offender: Offender,
}

impl<Offender: Clone> Offence<Offender> for DoubleVoteOffence<Offender> {
	const ID: Kind = *b"para:double-vote";
	type TimeSlot = SessionIndex;

	fn offenders(&self) -> Vec<Offender> {
		vec![self.offender.clone()]
	}

	fn session_index(&self) -> SessionIndex {
		self.session_index
	}

	fn validator_set_count(&self) -> u32 {
		self.validator_set_count
	}

	fn time_slot(&self) -> Self::TimeSlot {
		self.session_index
	}

	fn slash_fraction(_offenders_count: u32, _validator_set_count: u32) -> Perbill {
		// Slash 100%.
		Perbill::from_percent(100)
	}
}

348
349
350
351
352
353
354
/// Total number of individual messages allowed in the parachain -> relay-chain message queue.
const MAX_QUEUE_COUNT: usize = 100;
/// 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.
const WATERMARK_QUEUE_SIZE: usize = 20000;

355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
/// Metadata used to track previous parachain validation code that we keep in
/// the state.
#[derive(Default, Encode, Decode)]
#[cfg_attr(test, derive(Debug, Clone, PartialEq))]
pub struct ParaPastCodeMeta<N> {
	// Block numbers where the code was replaced. These can be used as indices
	// into the `PastCode` map along with the `ParaId` to fetch the code itself.
	upgrade_times: Vec<N>,
	// This tracks the highest pruned code-replacement, if any.
	last_pruned: Option<N>,
}

#[cfg_attr(test, derive(Debug, PartialEq))]
enum UseCodeAt<N> {
	// Use the current code.
	Current,
	// Use the code that was replaced at the given block number.
	ReplacedAt(N),
}

impl<N: Ord + Copy> ParaPastCodeMeta<N> {
	// note a replacement has occurred at a given block number.
	fn note_replacement(&mut self, at: N) {
		self.upgrade_times.insert(0, at)
	}

	// Yields the block number of the code that should be used for validating at
	// the given block number.
	//
	// a return value of `None` means that there is no code we are aware of that
	// should be used to validate at the given height.
	fn code_at(&self, at: N) -> Option<UseCodeAt<N>> {
		// The `PastCode` map stores the code which was replaced at `t`.
		let end_position = self.upgrade_times.iter().position(|&t| t < at);
		if let Some(end_position) = end_position {
			Some(if end_position != 0 {
				// `end_position` gives us the replacement time where the code used at `at`
				// was set. But that code has been replaced: `end_position - 1` yields
				// that index.
				UseCodeAt::ReplacedAt(self.upgrade_times[end_position - 1])
			} else {
				// the most recent tracked replacement is before `at`.
				// this means that the code put in place then (i.e. the current code)
				// is correct for validating at `at`.
				UseCodeAt::Current
			})
		} else {
			if self.last_pruned.as_ref().map_or(true, |&n| n < at) {
				// Our `last_pruned` is before `at`, so we still have the code!
				// but no code upgrade entries found before the `at` parameter.
				//
				// this means one of two things is true:
				// 1. there are no non-pruned upgrade logs. in this case use `Current`
				// 2. there are non-pruned upgrade logs all after `at`.
				//    in this case use the oldest upgrade log.
				Some(self.upgrade_times.last()
					.map(|n| UseCodeAt::ReplacedAt(*n))
					.unwrap_or(UseCodeAt::Current)
				)
			} else {
				// We don't have the code anymore.
				None
			}
		}
	}

	// The block at which the most recently tracked code change occurred.
	fn most_recent_change(&self) -> Option<N> {
		self.upgrade_times.first().map(|x| x.clone())
	}

	// prunes all code upgrade logs occurring at or before `max`.
	// note that code replaced at `x` is the code used to validate all blocks before
	// `x`. Thus, `max` should be outside of the slashing window when this is invoked.
	//
	// returns an iterator of block numbers at which code was replaced, where the replaced
	// code should be now pruned, in ascending order.
	fn prune_up_to(&'_ mut self, max: N) -> impl Iterator<Item=N> + '_ {
		match self.upgrade_times.iter().position(|&t| t <= max) {
			None => {
				// this is a no-op `drain` - desired because all
				// logged code upgrades occurred after `max`.
				self.upgrade_times.drain(self.upgrade_times.len()..).rev()
			}
			Some(pos) => {
				self.last_pruned = Some(self.upgrade_times[pos]);
				self.upgrade_times.drain(pos..).rev()
			}
		}
	}
}

447
decl_storage! {
448
449
	trait Store for Module<T: Trait> as Parachains
	{
450
		/// All authorities' keys at the moment.
451
		pub Authorities get(fn authorities): Vec<ValidatorId>;
452
		/// The active code of a currently-registered parachain.
453
		pub Code get(fn parachain_code): map hasher(twox_64_concat) ParaId => Option<ValidationCode>;
454
455
456
457
458
459
		/// Past code of parachains. The parachains themselves may not be registered anymore,
		/// but we also keep their code on-chain for the same amount of time as outdated code
		/// to assist with availability.
		PastCodeMeta get(fn past_code_meta): map hasher(twox_64_concat) ParaId => ParaPastCodeMeta<T::BlockNumber>;
		/// Actual past code, indicated by the parachain and the block number at which it
		/// became outdated.
460
		PastCode: map hasher(twox_64_concat) (ParaId, T::BlockNumber) => Option<ValidationCode>;
461
462
463
464
465
466
467
		/// Past code pruning, in order of priority.
		PastCodePruning get(fn past_code_pruning_tasks): Vec<(ParaId, T::BlockNumber)>;
		// The block number at which the planned code change is expected for a para.
		// The change will be applied after the first parablock for this ID included which executes
		// in the context of a relay chain block with a number >= `expected_at`.
		FutureCodeUpgrades get(fn code_upgrade_schedule): map hasher(twox_64_concat) ParaId => Option<T::BlockNumber>;
		// The actual future code of a para.
468
		FutureCode: map hasher(twox_64_concat) ParaId => ValidationCode;
469

470
		/// The heads of the parachains registered at present.
471
		pub Heads get(fn parachain_head): map hasher(twox_64_concat) ParaId => Option<HeadData>;
472
473
		/// Messages ready to be dispatched onto the relay chain. It is subject to
		/// `MAX_MESSAGE_COUNT` and `WATERMARK_MESSAGE_SIZE`.
474
		pub RelayDispatchQueue: map hasher(twox_64_concat) ParaId => Vec<UpwardMessage>;
475
476
		/// Size of the dispatch queues. Separated from actual data in order to avoid costly
		/// decoding when checking receipt validity. First item in tuple is the count of messages
477
		/// second if the total length (in bytes) of the message payloads.
478
		pub RelayDispatchQueueSize: map hasher(twox_64_concat) ParaId => (u32, u32);
479
480
		/// The ordered list of ParaIds that have a `RelayDispatchQueue` entry.
		NeedsDispatch: Vec<ParaId>;
481

482
483
		/// `Some` if the parachain heads get updated in this block, along with the parachain IDs
		/// that did update. Ordered in the same way as `registrar::Active` (i.e. by ParaId).
484
		///
485
		/// `None` if not yet updated.
486
		pub DidUpdate: Option<Vec<ParaId>>;
thiolliere's avatar
thiolliere committed
487
	}
488
489
490
491
	add_extra_genesis {
		config(authorities): Vec<ValidatorId>;
		build(|config| Module::<T>::initialize_authorities(&config.authorities))
	}
492
493
}

494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
decl_error! {
	pub enum Error for Module<T: Trait> {
		/// Parachain heads must be updated only once in the block.
		TooManyHeadUpdates,
		/// Too many parachain candidates.
		TooManyParaCandidates,
		/// Proposed heads must be ascending order by parachain ID without duplicate.
		HeadsOutOfOrder,
		/// Candidate is for an unregistered parachain.
		UnregisteredPara,
		/// Invalid collator.
		InvalidCollator,
		/// The message queue is full. Messages will be added when there is space.
		QueueFull,
		/// The message origin is invalid.
		InvalidMessageOrigin,
		/// No validator group for parachain.
		NoValidatorGroup,
		/// Not enough validity votes for candidate.
		NotEnoughValidityVotes,
		/// The number of attestations exceeds the number of authorities.
		VotesExceedsAuthorities,
		/// Attesting validator not on this chain's validation duty.
		WrongValidatorAttesting,
		/// Invalid signature from attester.
		InvalidSignature,
		/// Extra untagged validity votes along with candidate.
		UntaggedVotes,
522
523
		/// Wrong parent head for parachain receipt.
		ParentMismatch,
524
525
		/// Head data was too large.
		HeadDataTooLarge,
526
527
528
529
		/// New validation code was too large.
		ValidationCodeTooLarge,
		/// Disallowed code upgrade.
		DisallowedCodeUpgrade,
530
531
532
533
		/// Para does not have enough balance to pay fees.
		CannotPayFees,
		/// Unexpected relay-parent for a candidate receipt.
		UnexpectedRelayParent,
534
535
536
	}
}

537
538
decl_module! {
	/// Parachains module.
539
	pub struct Module<T: Trait> for enum Call where origin: <T as system::Trait>::Origin {
540
541
		type Error = Error<T>;

542
543
544
545
546
547
		fn on_initialize(now: T::BlockNumber) -> Weight {
			<Self as Store>::DidUpdate::kill();

			Self::do_old_code_pruning(now);

			// TODO https://github.com/paritytech/polkadot/issues/977: set correctly
548
			0
549
550
551
552
553
554
		}

		fn on_finalize() {
			assert!(<Self as Store>::DidUpdate::exists(), "Parachain heads must be updated once in the block");
		}

555
		/// Provide candidate receipts for parachains, in ascending order by id.
556
		#[weight = (1_000_000_000, DispatchClass::Mandatory)]
557
		pub fn set_heads(origin, heads: Vec<AttestedCandidate>) -> DispatchResult {
thiolliere's avatar
thiolliere committed
558
			ensure_none(origin)?;
559
			ensure!(!<DidUpdate>::exists(), Error::<T>::TooManyHeadUpdates);
560
561

			let active_parachains = Self::active_parachains();
562

563
			let parachain_count = active_parachains.len();
564
			ensure!(heads.len() <= parachain_count, Error::<T>::TooManyParaCandidates);
565

566
567
			let mut proceeded = Vec::with_capacity(heads.len());

568
			let schedule = Self::global_validation_schedule();
569

570
571
572
573
			if !active_parachains.is_empty() {
				// perform integrity checks before writing to storage.
				{
					let mut last_id = None;
574

575
576
577
578
579
580
					let mut iter = active_parachains.iter();
					for head in &heads {
						let id = head.parachain_index();
						// proposed heads must be ascending order by parachain ID without duplicate.
						ensure!(
							last_id.as_ref().map_or(true, |x| x < &id),
581
							Error::<T>::HeadsOutOfOrder
582
583
584
						);

						// must be unknown since active parachains are always sorted.
585
						let (_, maybe_required_collator) = iter.find(|para| para.0 == id)
586
							.ok_or(Error::<T>::UnregisteredPara)?;
587
588

						if let Some((required_collator, _)) = maybe_required_collator {
589
							ensure!(required_collator == &head.candidate.collator, Error::<T>::InvalidCollator);
590
						}
591
592
593

						Self::check_upward_messages(
							id,
594
							&head.candidate.commitments.upward_messages,
595
596
597
598
							MAX_QUEUE_COUNT,
							WATERMARK_QUEUE_SIZE,
						)?;

599
600
601
						let id = head.parachain_index();
						proceeded.push(id);
						last_id = Some(id);
602
					}
603
604
				}

605
606
607
608
609
				let para_blocks = Self::check_candidates(
					&schedule,
					&heads,
					&active_parachains,
				)?;
610

611
612
				<attestations::Module<T>>::note_included(&heads, para_blocks);

613
				Self::update_routing(
614
					&heads,
615
				);
616

617
618
619
				// note: we dispatch new messages _after_ the call to `check_candidates`
				// which deducts any fees. if that were not the case, an upward message
				// could be dispatched and spend money that invalidated a candidate.
620
621
622
623
624
				Self::dispatch_upward_messages(
					MAX_QUEUE_COUNT,
					WATERMARK_QUEUE_SIZE,
					Self::dispatch_message,
				);
625
626
			}

627
			DidUpdate::put(proceeded);
628
629
630
631

			Ok(())
		}

632
633
634
635
		/// Provide a proof that some validator has commited a double-vote.
		///
		/// The weight is 0; in order to avoid DoS a `SignedExtension` validation
		/// is implemented.
636
		#[weight = 0]
637
638
639
		pub fn report_double_vote(
			origin,
			report: DoubleVoteReport<
640
				<T::KeyOwnerProofSystem as KeyOwnerProofSystem<(KeyTypeId, ValidatorId)>>::Proof,
641
642
643
644
645
646
647
648
649
650
651
652
653
			>,
		) -> DispatchResult {
			let reporter = ensure_signed(origin)?;

			let validators = <session::Module<T>>::validators();
			let validator_set_count = validators.len() as u32;

			let session_index = report.proof.session();
			let DoubleVoteReport { identity, proof, .. } = report;

			// We have already checked this proof in `SignedExtension`, but we need
			// this here to get the full identification of the offender.
			let offender = T::KeyOwnerProofSystem::check_proof(
654
					(PARACHAIN_KEY_TYPE_ID, identity),
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
					proof,
				).ok_or("Invalid/outdated key ownership proof.")?;

			let offence = DoubleVoteOffence {
				session_index,
				validator_set_count,
				offender,
			};

			// Checks if this is actually a double vote are
			// implemented in `ValidateDoubleVoteReports::validete`.
			T::ReportOffence::report_offence(vec![reporter], offence)
				.map_err(|_| "Failed to report offence")?;

			Ok(())
		}
Gav's avatar
Gav committed
671
	}
672
673
}

674
675
676
677
fn majority_of(list_len: usize) -> usize {
	list_len / 2 + list_len % 2
}

678
679
680
681
fn localized_payload(
	statement: Statement,
	signing_context: &SigningContext,
) -> Vec<u8> {
682
	let mut encoded = statement.encode();
683
	signing_context.using_encoded(|s| encoded.extend(s));
684
685
686
	encoded
}

687
impl<T: Trait> Module<T> {
688
689
690
	/// Initialize the state of a new parachain/parathread.
	pub fn initialize_para(
		id: ParaId,
691
692
		code: ValidationCode,
		initial_head_data: HeadData,
693
694
695
696
697
	) {
		<Code>::insert(id, code);
		<Heads>::insert(id, initial_head_data);
	}

698
699
	/// Cleanup all storage related to a para. Some pieces of data may remain
	/// available in the on-chain state.
700
701
702
	pub fn cleanup_para(
		id: ParaId,
	) {
703
		let code = <Code>::take(id);
704
		<Heads>::remove(id);
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723

		// clean up from all code-upgrade maps.
		// we don't clean up the meta or planned-code maps as that's handled
		// by the pruning process.
		if let Some(_planned_future_at) = <Self as Store>::FutureCodeUpgrades::take(&id) {
			<Self as Store>::FutureCode::remove(&id);
		}

		if let Some(code) = code {
			Self::note_past_code(id, <system::Module<T>>::block_number(), code);
		}
	}

	// note replacement of the code of para with given `id`, which occured in the
	// context of the given relay-chain block number. provide the replaced code.
	//
	// `at` for para-triggered replacement is the block number of the relay-chain
	// block in whose context the parablock was executed
	// (i.e. number of `relay_parent` in the receipt)
724
	fn note_past_code(id: ParaId, at: T::BlockNumber, old_code: ValidationCode) {
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
		<Self as Store>::PastCodeMeta::mutate(&id, |past_meta| {
			past_meta.note_replacement(at);
		});

		<Self as Store>::PastCode::insert(&(id, at), old_code);

		// Schedule pruning for this past-code to be removed as soon as it
		// exits the slashing window.
		<Self as Store>::PastCodePruning::mutate(|pruning| {
			let insert_idx = pruning.binary_search_by_key(&at, |&(_, b)| b)
				.unwrap_or_else(|idx| idx);
			pruning.insert(insert_idx, (id, at));
		})
	}

	// does old code pruning.
	fn do_old_code_pruning(now: T::BlockNumber) {
		let slash_period = T::SlashPeriod::get();
		if now <= slash_period { return }

		// The height of any changes we no longer should keep around.
		let pruning_height = now - (slash_period + One::one());

		<Self as Store>::PastCodePruning::mutate(|pruning_tasks: &mut Vec<(_, T::BlockNumber)>| {
			let pruning_tasks_to_do = {
				// find all past code that has just exited the pruning window.
				let up_to_idx = pruning_tasks.iter()
					.take_while(|&(_, at)| at <= &pruning_height)
					.count();
				pruning_tasks.drain(..up_to_idx)
			};

			for (para_id, _) in pruning_tasks_to_do {
				let full_deactivate = <Self as Store>::PastCodeMeta::mutate(&para_id, |meta| {
					for pruned_repl_at in meta.prune_up_to(pruning_height) {
						<Self as Store>::PastCode::remove(&(para_id, pruned_repl_at));
					}

					meta.most_recent_change().is_none() && Self::parachain_head(&para_id).is_none()
				});

				// This parachain has been removed and now the vestigial code
				// has been removed from the state. clean up meta as well.
				if full_deactivate {
					<Self as Store>::PastCodeMeta::remove(&para_id);
				}
			}
		});
	}

	// Performs a code upgrade of a parachain.
776
	fn do_code_upgrade(id: ParaId, at: T::BlockNumber, new_code: &ValidationCode) {
777
778
779
780
		let old_code = Self::parachain_code(&id).unwrap_or_default();
		Code::insert(&id, new_code);

		Self::note_past_code(id, at, old_code);
781
782
	}

783
784
785
786
787
788
789
790
791
792
793
	/// Get a `SigningContext` with a current `SessionIndex` and parent hash.
	pub fn signing_context() -> SigningContext {
		let session_index = <session::Module<T>>::current_index();
		let parent_hash = <system::Module<T>>::parent_hash();

		SigningContext {
			session_index,
			parent_hash: T::BlockHashConversion::convert(parent_hash),
		}
	}

794
795
796
797
	/// Submit a double vote report.
	pub fn submit_double_vote_report(
		report: DoubleVoteReport<T::Proof>,
	) -> Option<()> {
798
799
800
801
802
		Signer::<T, T::AuthorityId>::all_accounts()
			.send_signed_transaction(
				move |_account| {
					Call::report_double_vote(report.clone())
				}
803
804
805
			)
			.iter()
			.find_map(|(_, res)| res.ok().map(|_| ()))
806
807
	}

808
809
810
811
812
813
	/// Dispatch some messages from a parachain.
	fn dispatch_message(
		id: ParaId,
		origin: ParachainDispatchOrigin,
		data: &[u8],
	) {
814
		if let Ok(message_call) = <T as Trait>::Call::decode(&mut &data[..]) {
815
816
817
818
819
			let origin: <T as Trait>::Origin = match origin {
				ParachainDispatchOrigin::Signed =>
					system::RawOrigin::Signed(id.into_account()).into(),
				ParachainDispatchOrigin::Parachain =>
					Origin::Parachain(id).into(),
820
821
				ParachainDispatchOrigin::Root =>
					system::RawOrigin::Root.into(),
822
823
824
825
826
827
828
829
830
831
832
833
834
			};
			let _ok = message_call.dispatch(origin).is_ok();
			// Not much to do with the result as it is. It's up to the parachain to ensure that the
			// message makes sense.
		}
	}

	/// Ensure all is well with the upward messages.
	fn check_upward_messages(
		id: ParaId,
		upward_messages: &[UpwardMessage],
		max_queue_count: usize,
		watermark_queue_size: usize,
835
	) -> DispatchResult {
836
837
		// Either there are no more messages to add...
		if !upward_messages.is_empty() {
Gavin Wood's avatar
Gavin Wood committed
838
			let (count, size) = <RelayDispatchQueueSize>::get(id);
839
840
841
842
843
			ensure!(
				// ...or we are appending one message onto an empty queue...
				upward_messages.len() + count as usize == 1
				// ...or...
				|| (
Ashley's avatar
Ashley committed
844
845
				// ...the total messages in the queue ends up being no greater than the
				// limit...
846
847
848
849
850
851
852
853
					upward_messages.len() + count as usize <= max_queue_count
				&&
					// ...and the total size of the payloads in the queue ends up being no
					// greater than the limit.
					upward_messages.iter()
						.fold(size as usize, |a, x| a + x.data.len())
					<= watermark_queue_size
				),
854
				Error::<T>::QueueFull
855
			);
856
857
			if !id.is_system() {
				for m in upward_messages.iter() {
858
					ensure!(m.origin != ParachainDispatchOrigin::Root, Error::<T>::InvalidMessageOrigin);
859
860
				}
			}
861
862
863
864
		}
		Ok(())
	}

865
866
867
868
869
	/// Update routing information from the parachain heads. This queues upwards
	/// messages to the relay chain as well.
	fn update_routing(
		heads: &[AttestedCandidate],
	) {
870
871
872
873
		// we sort them in order to provide a fast lookup to ensure we can avoid duplicates in the
		// needs_dispatch queue.
		let mut ordered_needs_dispatch = NeedsDispatch::get();

874
875
		for head in heads.iter() {
			let id = head.parachain_index();
876
			Heads::insert(id, &head.candidate.head_data);
877
878

			// Queue up upwards messages (from parachains to relay chain).
879
880
			Self::queue_upward_messages(
				id,
881
				&head.candidate.commitments.upward_messages,
882
883
				&mut ordered_needs_dispatch,
			);
884
885
		}

886
		NeedsDispatch::put(ordered_needs_dispatch);
887
888
	}

889
	/// Place any new upward messages into our queue for later dispatch.
890
891
892
893
894
895
896
897
898
	///
	/// `ordered_needs_dispatch` is mutated to ensure it reflects the new value of
	/// `RelayDispatchQueueSize`. It is up to the caller to guarantee that it gets written into
	/// storage after this call.
	fn queue_upward_messages(
		id: ParaId,
		upward_messages: &[UpwardMessage],
		ordered_needs_dispatch: &mut Vec<ParaId>,
	) {
899
		if !upward_messages.is_empty() {
900
			RelayDispatchQueueSize::mutate(id, |&mut(ref mut count, ref mut len)| {
901
902
903
904
				*count += upward_messages.len() as u32;
				*len += upward_messages.iter()
					.fold(0, |a, x| a + x.data.len()) as u32;
			});
905
906
907

			upward_messages.iter().for_each(|m| RelayDispatchQueue::append(id, m));

908
909
910
911
			if let Err(i) = ordered_needs_dispatch.binary_search(&id) {
				// same.
				ordered_needs_dispatch.insert(i, id);
			} else {
912
				sp_runtime::print("ordered_needs_dispatch contains id?!");
913
			}
914
915
916
		}
	}

917
918
	/// Simple FIFO dispatcher. This must be called after parachain fees are checked,
	/// as dispatched messages may spend parachain funds.
919
920
921
922
923
	fn dispatch_upward_messages(
		max_queue_count: usize,
		watermark_queue_size: usize,
		mut dispatch_message: impl FnMut(ParaId, ParachainDispatchOrigin, &[u8]),
	) {
924
925
		let queueds = NeedsDispatch::get();
		let mut drained_count = 0usize;
926
927
		let mut dispatched_count = 0usize;
		let mut dispatched_size = 0usize;
928
929
930
		for id in queueds.iter() {
			drained_count += 1;

Gavin Wood's avatar
Gavin Wood committed
931
			let (count, size) = <RelayDispatchQueueSize>::get(id);
932
933
934
935
936
937
938
939
			let count = count as usize;
			let size = size as usize;
			if dispatched_count == 0 || (
				dispatched_count + count <= max_queue_count
					&& dispatched_size + size <= watermark_queue_size
			) {
				if count > 0 {
					// still dispatching messages...
940
941
					RelayDispatchQueueSize::remove(id);
					let messages = RelayDispatchQueue::take(id);
942
943
944
945
946
947
948
949
950
951
952
953
954
					for UpwardMessage { origin, data } in messages.into_iter() {
						dispatch_message(*id, origin, &data);
					}
					dispatched_count += count;
					dispatched_size += size;
					if dispatched_count >= max_queue_count
						|| dispatched_size >= watermark_queue_size
					{
						break
					}
				}
			}
		}
955
		NeedsDispatch::put(&queueds[drained_count..]);
956
957
	}

958
	/// Calculate the current block's duty roster using system's random seed.
959
960
	/// Returns the duty roster along with the random seed.
	pub fn calculate_duty_roster() -> (DutyRoster, [u8; 32]) {
961
962
		let parachains = Self::active_parachains();
		let parachain_count = parachains.len();
963

964
		// TODO: use decode length. substrate #2794
965
		let validator_count = Self::authorities().len();
966
967
968
969
970
971
		let validators_per_parachain =
			if parachain_count == 0 {
				0
			} else {
				(validator_count - 1) / parachain_count
			};
972
973

		let mut roles_val = (0..validator_count).map(|i| match i {
974
975
			i if i < parachain_count * validators_per_parachain => {
				let idx = i / validators_per_parachain;
976
				Chain::Parachain(parachains[idx].0.clone())
977
			}
978
979
			_ => Chain::Relay,
		}).collect::<Vec<_>>();
980

981
982
		let mut seed = {
			let phrase = b"validator_role_pairs";
983
			let seed = T::Randomness::random(&phrase[..]);
984
985
986
987
988
989
990
991
992
993
994
995
996
997
			let seed_len = seed.as_ref().len();
			let needed_bytes = validator_count * 4;

			// hash only the needed bits of the random seed.
			// if earlier bits are influencable, they will not factor into
			// the seed used here.
			let seed_off = if needed_bytes >= seed_len {
				0
			} else {
				seed_len - needed_bytes
			};

			BlakeTwo256::hash(&seed.as_ref()[seed_off..])
		};
998

999
1000
		let orig_seed = seed.clone().to_fixed_bytes();

For faster browsing, not all history is shown. View entire blame