parachains.rs 116 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, CompactStatement as 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
	Remark, DownwardMessage
51
};
52
use frame_support::{
53
	Parameter, dispatch::DispatchResult, decl_storage, decl_module, decl_error, ensure,
54
	traits::{Currency, Get, WithdrawReason, ExistenceRequirement, Randomness},
55
};
56
use sp_runtime::transaction_validity::InvalidTransaction;
57

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

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

67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
// 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)
	}
}

88
89
90
91
// 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;
92
	fn deduct(para_id: ParaId, amount: Balance) -> DispatchResult;
93
94
95
96
97
98
99
100
101
102
103
104
	fn transfer_in(
		source: &AccountId,
		dest: ParaId,
		amount: Balance,
		existence_requirement: ExistenceRequirement,
	) -> DispatchResult;
	fn transfer_out(
		source: ParaId,
		dest: &AccountId,
		amount: Balance,
		existence_requirement: ExistenceRequirement,
	) -> DispatchResult;
105
106
107
108
109
110
111
112
113
114
115
}

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()
	}

116
117
	// TODO: this should really be the same API as `withdraw`, having NegativeImbalance as an
	//   associated type.
118
	fn deduct(para_id: ParaId, amount: Balance) -> DispatchResult {
119
120
121
122
123
124
		let para_account = para_id.into_account();

		// burn the fee.
		let _ = T::withdraw(
			&para_account,
			amount.into(),
Gavin Wood's avatar
Gavin Wood committed
125
			WithdrawReason::Fee.into(),
126
127
128
129
130
			ExistenceRequirement::KeepAlive,
		)?;

		Ok(())
	}
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148

	fn transfer_in(
		source: &AccountId,
		dest: ParaId,
		amount: Balance,
		existence_requirement: ExistenceRequirement,
	) -> DispatchResult {
		T::transfer(source, &dest.into_account(), amount.into(), existence_requirement)
	}

	fn transfer_out(
		source: ParaId,
		dest: &AccountId,
		amount: Balance,
		existence_requirement: ExistenceRequirement,
	) -> DispatchResult {
		T::transfer(&source.into_account(), dest, amount.into(), existence_requirement)
	}
149
150
}

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

154
155
156
157
158
159
160
/// 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)]
161
pub struct DoubleVoteReport<Proof> {
162
163
164
165
166
167
168
169
	/// 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,
170
171
	/// A `SigningContext` with a session and a parent hash of the moment this offence was commited.
	pub signing_context: SigningContext,
172
173
}

174
impl<Proof: Parameter + GetSessionNumber> DoubleVoteReport<Proof> {
175
176
177
178
179
	fn verify<T: Trait<Proof = Proof>>(
		&self,
	) -> Result<(), DoubleVoteValidityError> {
		let first = self.first.clone();
		let second = self.second.clone();
180
		let id = self.identity.clone();
181
182
183
184

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

185
186
187
188
		if self.proof.session() != self.signing_context.session_index {
			return Err(DoubleVoteValidityError::InvalidReport);
		}

189
		// Check signatures.
190
191
192
193
194
195
196
197
198
199
		Self::verify_vote(
			&first,
			&self.signing_context,
			&self.identity,
		)?;
		Self::verify_vote(
			&second,
			&self.signing_context,
			&self.identity,
		)?;
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224

		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),
225
		signing_context: &SigningContext,
226
227
		authority: &ValidatorId,
	) -> Result<(), DoubleVoteValidityError> {
228
		let payload = localized_payload(vote.0.clone(), signing_context);
229
230
231
232
233
234
235
236
237

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

		Ok(())
	}
}

238
239
240
241
242
243
impl<T: session::Trait> Get<Vec<T::ValidatorId>> for ValidatorIdentities<T> {
	fn get() -> Vec<T::ValidatorId> {
		<session::Module<T>>::validators()
	}
}

244
/// A trait to get a session number the `MembershipProof` belongs to.
245
246
247
248
pub trait GetSessionNumber {
	fn session(&self) -> SessionIndex;
}

249
impl GetSessionNumber for sp_session::MembershipProof {
250
	fn session(&self) -> SessionIndex {
251
		self.session
252
253
254
	}
}

255
256
257
258
pub trait Trait: CreateSignedTransaction<Call<Self>> + attestations::Trait + session::historical::Trait {
	// The transaction signing authority
	type AuthorityId: system::offchain::AppCrypto<Self::Public, Self::Signature>;

259
	/// The outer origin type.
260
261
262
	type Origin: From<Origin>
		+ From<<Self as system::Trait>::Origin>
		+ Into<result::Result<Origin, <Self as Trait>::Origin>>;
263
264

	/// The outer call dispatch type.
265
	type Call: Parameter + Dispatchable<Origin=<Self as Trait>::Origin> + From<Call<Self>>;
266

267
	/// Some way of interacting with balances for fees and transfers.
268
	type ParachainCurrency: ParachainCurrency<Self::AccountId>;
269

270
271
272
273
274
	/// 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>;

275
276
277
	/// Something that provides randomness in the runtime.
	type Randomness: Randomness<Self::Hash>;

278
279
280
281
282
	/// 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>;
283
284
285
286
287
288
289
290

	/// 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>;
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
	/// 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>;
306
307
308
309
310
311
312
313
314
315

	/// 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<
316
		(KeyTypeId, ValidatorId),
317
318
319
320
321
322
323
324
325
326
327
		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,
328
		DoubleVoteOffence<Self::IdentificationTuple>,
329
	>;
330
331
332

	/// A type that converts the opaque hash type to exact one.
	type BlockHashConversion: Convert<Self::Hash, primitives::Hash>;
333
334
335
}

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

343
344
345
346
347
348
349
350
351
352
353
354
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
/// 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)
	}
}

381
382
/// Total number of individual messages allowed in the relay-chain -> parachain message queue.
const MAX_DOWNWARD_QUEUE_COUNT: usize = 10;
383
384
385
386
387
388
389
/// 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;

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
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
/// 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()
			}
		}
	}
}

482
decl_storage! {
483
	trait Store for Module<T: Trait> as Parachains {
484
		/// All authorities' keys at the moment.
485
		pub Authorities get(fn authorities): Vec<ValidatorId>;
486
		/// The active code of a currently-registered parachain.
487
		pub Code get(fn parachain_code): map hasher(twox_64_concat) ParaId => Option<ValidationCode>;
488
489
490
491
492
493
		/// 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.
494
		PastCode: map hasher(twox_64_concat) (ParaId, T::BlockNumber) => Option<ValidationCode>;
495
496
497
498
499
500
501
		/// 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.
502
		FutureCode: map hasher(twox_64_concat) ParaId => ValidationCode;
503

504
		/// The heads of the parachains registered at present.
505
		pub Heads get(fn parachain_head): map hasher(twox_64_concat) ParaId => Option<HeadData>;
506
507
		/// Messages ready to be dispatched onto the relay chain. It is subject to
		/// `MAX_MESSAGE_COUNT` and `WATERMARK_MESSAGE_SIZE`.
508
		pub RelayDispatchQueue: map hasher(twox_64_concat) ParaId => Vec<UpwardMessage>;
509
510
		/// 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
511
		/// second if the total length (in bytes) of the message payloads.
512
		pub RelayDispatchQueueSize: map hasher(twox_64_concat) ParaId => (u32, u32);
513
514
		/// The ordered list of ParaIds that have a `RelayDispatchQueue` entry.
		NeedsDispatch: Vec<ParaId>;
515

516
517
		/// `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).
518
		///
519
		/// `None` if not yet updated.
520
		pub DidUpdate: Option<Vec<ParaId>>;
521
522
523

		/// Messages waiting to be delivered from the Relay chain into the parachain.
		pub DownwardMessageQueue: map hasher(twox_64_concat) ParaId => Vec<DownwardMessage<T::AccountId>>;
thiolliere's avatar
thiolliere committed
524
	}
525
526
527
528
	add_extra_genesis {
		config(authorities): Vec<ValidatorId>;
		build(|config| Module::<T>::initialize_authorities(&config.authorities))
	}
529
530
}

531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
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,
559
560
		/// Wrong parent head for parachain receipt.
		ParentMismatch,
561
562
		/// Head data was too large.
		HeadDataTooLarge,
563
564
565
566
		/// New validation code was too large.
		ValidationCodeTooLarge,
		/// Disallowed code upgrade.
		DisallowedCodeUpgrade,
567
568
569
570
		/// Para does not have enough balance to pay fees.
		CannotPayFees,
		/// Unexpected relay-parent for a candidate receipt.
		UnexpectedRelayParent,
571
572
		/// Downward message queue is full for the Parachain.
		DownwardMessageQueueFull,
573
574
575
	}
}

576
577
decl_module! {
	/// Parachains module.
578
	pub struct Module<T: Trait> for enum Call where origin: <T as system::Trait>::Origin {
579
580
		type Error = Error<T>;

581
582
583
584
585
586
		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
587
			0
588
589
590
591
592
593
		}

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

594
		/// Provide candidate receipts for parachains, in ascending order by id.
595
		#[weight = (1_000_000_000, DispatchClass::Mandatory)]
596
		pub fn set_heads(origin, heads: Vec<AttestedCandidate>) -> DispatchResult {
thiolliere's avatar
thiolliere committed
597
			ensure_none(origin)?;
598
			ensure!(!<DidUpdate>::exists(), Error::<T>::TooManyHeadUpdates);
599
600

			let active_parachains = Self::active_parachains();
601

602
			let parachain_count = active_parachains.len();
603
			ensure!(heads.len() <= parachain_count, Error::<T>::TooManyParaCandidates);
604

605
606
			let mut proceeded = Vec::with_capacity(heads.len());

607
			let schedule = Self::global_validation_schedule();
608

609
610
611
612
			if !active_parachains.is_empty() {
				// perform integrity checks before writing to storage.
				{
					let mut last_id = None;
613

614
615
616
617
618
619
					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),
620
							Error::<T>::HeadsOutOfOrder
621
622
623
						);

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

						if let Some((required_collator, _)) = maybe_required_collator {
628
							ensure!(required_collator == &head.candidate.collator, Error::<T>::InvalidCollator);
629
						}
630
631
632

						Self::check_upward_messages(
							id,
633
							&head.candidate.commitments.upward_messages,
634
635
636
637
							MAX_QUEUE_COUNT,
							WATERMARK_QUEUE_SIZE,
						)?;

638
639
640
641
642
						Self::remove_processed_downward_messages(
							id,
							head.candidate.commitments.processed_downward_messages as usize,
						);

643
644
645
						let id = head.parachain_index();
						proceeded.push(id);
						last_id = Some(id);
646
					}
647
648
				}

649
650
651
652
653
				let para_blocks = Self::check_candidates(
					&schedule,
					&heads,
					&active_parachains,
				)?;
654

655
656
				<attestations::Module<T>>::note_included(&heads, para_blocks);

657
				Self::update_routing(
658
					&heads,
659
				);
660

661
662
663
				// 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.
664
665
666
667
668
				Self::dispatch_upward_messages(
					MAX_QUEUE_COUNT,
					WATERMARK_QUEUE_SIZE,
					Self::dispatch_message,
				);
669
670
			}

671
			DidUpdate::put(proceeded);
672
673
674
675

			Ok(())
		}

676
677
678
679
		/// 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.
680
		#[weight = 0]
681
682
683
		pub fn report_double_vote(
			origin,
			report: DoubleVoteReport<
684
				<T::KeyOwnerProofSystem as KeyOwnerProofSystem<(KeyTypeId, ValidatorId)>>::Proof,
685
686
687
688
689
690
691
692
693
694
695
696
697
			>,
		) -> 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(
698
					(PARACHAIN_KEY_TYPE_ID, identity),
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
					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(())
		}
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744

		/// Transfer some tokens into a parachain and leave a message in the downward queue for it.
		#[weight = 100_000]
		pub fn transfer_to_parachain(
			origin,
			to: ParaId,
			amount: Balance,
			remark: Remark,
		) {
			let who = ensure_signed(origin)?;
			let downward_queue_count = DownwardMessageQueue::<T>::decode_len(to).unwrap_or(0);
			ensure!(downward_queue_count < MAX_DOWNWARD_QUEUE_COUNT, Error::<T>::DownwardMessageQueueFull);
			T::ParachainCurrency::transfer_in(&who, to, amount, ExistenceRequirement::AllowDeath)?;
			DownwardMessageQueue::<T>::append(to, DownwardMessage::TransferInto(who, amount, remark));
		}

		/// Send a XCMP message to the given parachain.
		///
		/// The origin must be another parachain.
		#[weight = 100_000]
		pub fn send_xcmp_message(
			origin,
			to: ParaId,
			msg: Vec<u8>,
		) {
			ensure_parachain(<T as Trait>::Origin::from(origin))?;
			let downward_queue_count = DownwardMessageQueue::<T>::decode_len(to).unwrap_or(0);
			ensure!(downward_queue_count < MAX_DOWNWARD_QUEUE_COUNT, Error::<T>::DownwardMessageQueueFull);
			DownwardMessageQueue::<T>::append(to, DownwardMessage::XCMPMessage(msg));
		}
Gav's avatar
Gav committed
745
	}
746
747
}

748
749
750
751
fn majority_of(list_len: usize) -> usize {
	list_len / 2 + list_len % 2
}

752
753
754
755
fn localized_payload(
	statement: Statement,
	signing_context: &SigningContext,
) -> Vec<u8> {
756
	let mut encoded = statement.encode();
757
	signing_context.using_encoded(|s| encoded.extend(s));
758
759
760
	encoded
}

761
impl<T: Trait> Module<T> {
762
763
764
	/// Initialize the state of a new parachain/parathread.
	pub fn initialize_para(
		id: ParaId,
765
766
		code: ValidationCode,
		initial_head_data: HeadData,
767
768
769
770
771
	) {
		<Code>::insert(id, code);
		<Heads>::insert(id, initial_head_data);
	}

772
773
	/// Cleanup all storage related to a para. Some pieces of data may remain
	/// available in the on-chain state.
774
775
776
	pub fn cleanup_para(
		id: ParaId,
	) {
777
		let code = <Code>::take(id);
778
		<Heads>::remove(id);
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797

		// 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)
798
	fn note_past_code(id: ParaId, at: T::BlockNumber, old_code: ValidationCode) {
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
		<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.
850
	fn do_code_upgrade(id: ParaId, at: T::BlockNumber, new_code: &ValidationCode) {
851
852
853
854
		let old_code = Self::parachain_code(&id).unwrap_or_default();
		Code::insert(&id, new_code);

		Self::note_past_code(id, at, old_code);
855
856
	}

857
858
859
860
861
862
863
864
865
866
867
	/// 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),
		}
	}

868
869
870
871
	/// Submit a double vote report.
	pub fn submit_double_vote_report(
		report: DoubleVoteReport<T::Proof>,
	) -> Option<()> {
872
873
874
875
876
		Signer::<T, T::AuthorityId>::all_accounts()
			.send_signed_transaction(
				move |_account| {
					Call::report_double_vote(report.clone())
				}
877
878
879
			)
			.iter()
			.find_map(|(_, res)| res.ok().map(|_| ()))
880
881
	}

882
883
884
885
886
887
	/// Dispatch some messages from a parachain.
	fn dispatch_message(
		id: ParaId,
		origin: ParachainDispatchOrigin,
		data: &[u8],
	) {
888
		if let Ok(message_call) = <T as Trait>::Call::decode(&mut &data[..]) {
889
890
			let origin: <T as Trait>::Origin = match origin {
				ParachainDispatchOrigin::Signed =>
891
					<T as Trait>::Origin::from(<T as system::Trait>::Origin::from(system::RawOrigin::Signed(id.into_account()))),
892
893
				ParachainDispatchOrigin::Parachain =>
					Origin::Parachain(id).into(),
894
				ParachainDispatchOrigin::Root =>
895
					<T as Trait>::Origin::from(<T as system::Trait>::Origin::from(system::RawOrigin::Root)),
896
897
898
899
900
901
902
903
904
905
906
907
908
			};
			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,
909
	) -> DispatchResult {
910
911
		// Either there are no more messages to add...
		if !upward_messages.is_empty() {
Gavin Wood's avatar
Gavin Wood committed
912
			let (count, size) = <RelayDispatchQueueSize>::get(id);
913
914
915
916
917
			ensure!(
				// ...or we are appending one message onto an empty queue...
				upward_messages.len() + count as usize == 1
				// ...or...
				|| (
Ashley's avatar
Ashley committed
918
919
				// ...the total messages in the queue ends up being no greater than the
				// limit...
920
921
922
923
924
925
926
927
					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
				),
928
				Error::<T>::QueueFull
929
			);
930
931
			if !id.is_system() {
				for m in upward_messages.iter() {
932
					ensure!(m.origin != ParachainDispatchOrigin::Root, Error::<T>::InvalidMessageOrigin);
933
934
				}
			}
935
936
937
938
		}
		Ok(())
	}

939
940
941
942
943
944
945
946
947
948
949
	/// Remove processed downward messages from the `DownwardMessageQueue`.
	fn remove_processed_downward_messages(id: ParaId, processed: usize) {
		DownwardMessageQueue::<T>::mutate(id, |v| {
			if processed > v.len() {
				v.clear();
			} else {
				*v = v.split_off(processed);
			}
		});
	}

950
951
952
953
954
	/// Update routing information from the parachain heads. This queues upwards
	/// messages to the relay chain as well.
	fn update_routing(
		heads: &[AttestedCandidate],
	) {
955
956
957
958
		// 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();

959
960
		for head in heads.iter() {
			let id = head.parachain_index();
961
			Heads::insert(id, &head.candidate.head_data);
962
963

			// Queue up upwards messages (from parachains to relay chain).
964
965
			Self::queue_upward_messages(
				id,
966
				&head.candidate.commitments.upward_messages,
967
968
				&mut ordered_needs_dispatch,
			);
969
970
		}

971
		NeedsDispatch::put(ordered_needs_dispatch);
972
973
	}

974
	/// Place any new upward messages into our queue for later dispatch.
975
976
977
978
979
980
981
982
983
	///
	/// `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>,
	) {
984
		if !upward_messages.is_empty() {
985
			RelayDispatchQueueSize::mutate(id, |&mut(ref mut count, ref mut len)| {
986
987
988
989
				*count += upward_messages.len() as u32;
				*len += upward_messages.iter()
					.fold(0, |a, x| a + x.data.len()) as u32;
			});
990
991
992

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

993
994
995
996
			if let Err(i) = ordered_needs_dispatch.binary_search(&id) {
				// same.
				ordered_needs_dispatch.insert(i, id);
			} else {
997
				sp_runtime::print("ordered_needs_dispatch contains id?!");
998
			}
999
1000
		}
	}
For faster browsing, not all history is shown. View entire blame