parachains.rs 60.4 KB
Newer Older
1
// Copyright 2017-2019 Parity Technologies (UK) Ltd.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 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.

use rstd::prelude::*;
20
use rstd::collections::btree_map::BTreeMap;
21
use codec::{Encode, Decode, HasCompact};
22
use srml_support::{decl_storage, decl_module, fail, ensure};
23

24
use sr_primitives::traits::{
Gavin Wood's avatar
Gavin Wood committed
25
	Hash as HashT, BlakeTwo256, Member, CheckedConversion, Saturating, One, Zero, Dispatchable,
26
};
27
use sr_primitives::weights::SimpleDispatchInfo;
28
use primitives::{Hash, Balance, parachain::{
29
	self, Id as ParaId, Chain, DutyRoster, AttestedCandidate, Statement, AccountIdConversion,
30
	ParachainDispatchOrigin, UpwardMessage, BlockIngressRoots, ValidatorId
31
}};
32
use {system, session};
33
use srml_support::{
34
	Parameter, dispatch::Result, traits::{Currency, Get, WithdrawReason, ExistenceRequirement},
35
};
36

37
38
use inherents::{ProvideInherent, InherentData, RuntimeString, MakeFatalError, InherentIdentifier};

39
40
41
#[cfg(any(feature = "std", test))]
use rstd::marker::PhantomData;

42
use system::{ensure_none, ensure_root};
43
use crate::attestations::{self, IncludedBlocks};
44

45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
// 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)
	}
}

// creates a range iterator between `low` and `high`. `low` must be <= `high`.
fn number_range<N>(low: N, high: N) -> BlockNumberRange<N> {
	BlockNumberRange { low, high }
}

Gavin Wood's avatar
Gavin Wood committed
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/// Parachain registration API.
pub trait ParachainRegistrar<AccountId> {
	/// An identifier for a parachain.
	type ParaId: Member + Parameter + Default + AccountIdConversion<AccountId> + Copy + HasCompact;

	/// Create a new unique parachain identity for later registration.
	fn new_id() -> Self::ParaId;

	/// Register a parachain with given `code` and `initial_head_data`. `id` must not yet be registered or it will
	/// result in a error.
	fn register_parachain(id: Self::ParaId, code: Vec<u8>, initial_head_data: Vec<u8>) -> Result;

	/// Deregister a parachain with given `id`. If `id` is not currently registered, an error is returned.
	fn deregister_parachain(id: Self::ParaId) -> Result;
}

impl<T: Trait> ParachainRegistrar<T::AccountId> for Module<T> {
	type ParaId = ParaId;
	fn new_id() -> ParaId {
Gavin Wood's avatar
Gavin Wood committed
90
		<NextFreeId>::mutate(|n| { let r = *n; *n = ParaId::from(u32::from(*n) + 1); r })
Gavin Wood's avatar
Gavin Wood committed
91
92
93
94
95
96
97
98
	}
	fn register_parachain(id: ParaId, code: Vec<u8>, initial_head_data: Vec<u8>) -> Result {
		let mut parachains = Self::active_parachains();
		match parachains.binary_search(&id) {
			Ok(_) => fail!("Parachain already exists"),
			Err(idx) => parachains.insert(idx, id),
		}

Gavin Wood's avatar
Gavin Wood committed
99
100
101
		<Code>::insert(id, code);
		<Parachains>::put(parachains);
		<Heads>::insert(id, initial_head_data);
Gavin Wood's avatar
Gavin Wood committed
102

103
104
105
106
107
108
		// Because there are no ordering guarantees that inherents
		// are applied before regular transactions, a parachain candidate could
		// be registered before the `UpdateHeads` inherent is processed. If so, messages
		// could be sent to a parachain in the block it is registered.
		<Watermarks<T>>::insert(id, <system::Module<T>>::block_number().saturating_sub(One::one()));

Gavin Wood's avatar
Gavin Wood committed
109
110
111
112
113
114
115
116
117
		Ok(())
	}
	fn deregister_parachain(id: ParaId) -> Result {
		let mut parachains = Self::active_parachains();
		match parachains.binary_search(&id) {
			Ok(idx) => { parachains.remove(idx); }
			Err(_) => return Ok(()),
		}

Gavin Wood's avatar
Gavin Wood committed
118
119
		<Code>::remove(id);
		<Heads>::remove(id);
Gavin Wood's avatar
Gavin Wood committed
120

121
122
123
124
125
126
127
128
129
130
131
		let watermark = <Watermarks<T>>::take(id);

		// clear all routing entries _to_. But not those _from_.
		if let Some(watermark) = watermark {
			let now = <system::Module<T>>::block_number();

			// iterate over all blocks between watermark and now + 1 (since messages might
			// have already been sent to `id` in this block.
			for unrouted_block in number_range(watermark, now).map(|n| n.saturating_add(One::one())) {
				<UnroutedIngress<T>>::remove(&(unrouted_block, id));
			}
Gavin Wood's avatar
Gavin Wood committed
132
133
		}

Gavin Wood's avatar
Gavin Wood committed
134
		<Parachains>::put(parachains);
Gavin Wood's avatar
Gavin Wood committed
135
136
137
138
139

		Ok(())
	}
}

140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
// 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;
	fn deduct(para_id: ParaId, amount: Balance) -> Result;
}

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

	fn deduct(para_id: ParaId, amount: Balance) -> Result {
		let para_account = para_id.into_account();

		// burn the fee.
		let _ = T::withdraw(
			&para_account,
			amount.into(),
			WithdrawReason::Fee,
			ExistenceRequirement::KeepAlive,
		)?;

		Ok(())
	}
}

171
172
173
174
175
176
177
178
179
180
/// Interface to the persistent (stash) identities of the current validators.
pub struct ValidatorIdentities<T>(rstd::marker::PhantomData<T>);

impl<T: session::Trait> Get<Vec<T::ValidatorId>> for ValidatorIdentities<T> {
	fn get() -> Vec<T::ValidatorId> {
		<session::Module<T>>::validators()
	}
}

pub trait Trait: attestations::Trait {
181
182
183
184
185
	/// The outer origin type.
	type Origin: From<Origin> + From<system::RawOrigin<Self::AccountId>>;

	/// The outer call dispatch type.
	type Call: Parameter + Dispatchable<Origin=<Self as Trait>::Origin>;
186
187
188

	/// Some way of interacting with balances for fees.
	type ParachainCurrency: ParachainCurrency<Self::AccountId>;
189
190
191
192
193
194
195
196
}

/// 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
197
}
198

199
200
201
202
203
204
// result of <NodeCodec<Blake2Hasher> as trie_db::NodeCodec<Blake2Hasher>>::hashed_null_node()
const EMPTY_TRIE_ROOT: [u8; 32] = [
	3, 23, 10, 46, 117, 151, 183, 183, 227, 216, 76, 5, 57, 29, 19, 154,
	98, 177, 87, 231, 135, 134, 216, 192, 130, 242, 157, 207, 76, 17, 19, 20
];

205
206
207
208
209
210
211
/// 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;

212
decl_storage! {
Gav's avatar
Gav committed
213
	trait Store for Module<T: Trait> as Parachains {
214
		/// All authorities' keys at the moment.
215
		pub Authorities get(authorities) config(authorities): Vec<ValidatorId>;
216
		/// Vector of all parachain IDs.
217
		pub Parachains get(active_parachains): Vec<ParaId>;
218
		/// The parachains registered at present.
219
		pub Code get(parachain_code): map ParaId => Option<Vec<u8>>;
220
		/// The heads of the parachains registered at present.
221
		pub Heads get(parachain_head): map ParaId => Option<Vec<u8>>;
222
223
224
		/// The watermark heights of the parachains registered at present.
		/// For every parachain, this is the block height from which all messages targeting
		/// that parachain have been processed. Can be `None` only if the parachain doesn't exist.
225
226
227
228
229
230
231
		pub Watermarks get(watermark): map ParaId => Option<T::BlockNumber>;

		/// Unrouted ingress. Maps (BlockNumber, to_chain) pairs to [(from_chain, egress_root)].
		///
		/// There may be an entry under (i, p) in this map for every i between the parachain's
		/// watermark and the current block.
		pub UnroutedIngress: map (T::BlockNumber, ParaId) => Option<Vec<(ParaId, Hash)>>;
Gav's avatar
Gav committed
232

233
234
235
236
237
		/// Messages ready to be dispatched onto the relay chain. It is subject to
		/// `MAX_MESSAGE_COUNT` and `WATERMARK_MESSAGE_SIZE`.
		pub RelayDispatchQueue: map ParaId => Vec<UpwardMessage>;
		/// 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
238
		///	second if the total length (in bytes) of the message payloads.
239
240
		pub RelayDispatchQueueSize: map ParaId => (u32, u32);

241
		/// Did the parachain heads get updated in this block?
242
		DidUpdate: bool;
Gavin Wood's avatar
Gavin Wood committed
243
244
245

		/// The next unused ParaId value.
		NextFreeId: ParaId;
246
247
	}
	add_extra_genesis {
248
		config(parachains): Vec<(ParaId, Vec<u8>, Vec<u8>)>;
249
		config(_phdata): PhantomData<T>;
250
		build(build::<T>);
251
252
253
	}
}

254
#[cfg(feature = "std")]
thiolliere's avatar
thiolliere committed
255
fn build<T: Trait>(config: &GenesisConfig<T>) {
256
257
258
259
260
261
	let mut p = config.parachains.clone();
	p.sort_unstable_by_key(|&(ref id, _, _)| *id);
	p.dedup_by_key(|&mut (ref id, _, _)| *id);

	let only_ids: Vec<ParaId> = p.iter().map(|&(ref id, _, _)| id).cloned().collect();

thiolliere's avatar
thiolliere committed
262
	Parachains::put(&only_ids);
263

thiolliere's avatar
thiolliere committed
264
265
266
267
	for (id, code, genesis) in p {
		// no ingress -- a chain cannot be routed to until it is live.
		Code::insert(&id, &code);
		Heads::insert(&id, &genesis);
thiolliere's avatar
thiolliere committed
268
		<Watermarks<T>>::insert(&id, &T::BlockNumber::zero());
thiolliere's avatar
thiolliere committed
269
	}
270
271
}

272
273
decl_module! {
	/// Parachains module.
274
	pub struct Module<T: Trait> for enum Call where origin: <T as system::Trait>::Origin {
275
		/// Provide candidate receipts for parachains, in ascending order by id.
276
		#[weight = SimpleDispatchInfo::FixedNormal(1_000_000)]
277
		fn set_heads(origin, heads: Vec<AttestedCandidate>) -> Result {
thiolliere's avatar
thiolliere committed
278
			ensure_none(origin)?;
Gavin Wood's avatar
Gavin Wood committed
279
			ensure!(!<DidUpdate>::exists(), "Parachain heads must be updated only once in the block");
280
281

			let active_parachains = Self::active_parachains();
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
			let parachain_count = active_parachains.len();
			ensure!(heads.len() <= parachain_count, "Too many parachain candidates");

			if !active_parachains.is_empty() {
				// perform integrity checks before writing to storage.
				{
					let mut last_id = None;
					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),
							"Parachain candidates out of order by ID"
						);

						// must be unknown since active parachains are always sorted.
						ensure!(
							iter.find(|x| x == &&id).is_some(),
							"Submitted candidate for unregistered or out-of-order parachain {}"
						);

						Self::check_upward_messages(
							id,
							&head.candidate.upward_messages,
							MAX_QUEUE_COUNT,
							WATERMARK_QUEUE_SIZE,
						)?;
						Self::check_egress_queue_roots(&head, &active_parachains)?;

						last_id = Some(head.parachain_index());
					}
314
315
				}

316
				let para_blocks = Self::check_candidates(&heads, &active_parachains)?;
317
				let current_number = <system::Module<T>>::block_number();
318

319
320
				<attestations::Module<T>>::note_included(&heads, para_blocks);

321
322
				Self::update_routing(
					current_number,
323
					&heads,
324
				);
325
326

				Self::dispatch_upward_messages(
327
					current_number,
328
329
330
331
332
					&active_parachains,
					MAX_QUEUE_COUNT,
					WATERMARK_QUEUE_SIZE,
					Self::dispatch_message,
				);
333
334
			}

Gavin Wood's avatar
Gavin Wood committed
335
			<DidUpdate>::put(true);
336
337
338
339
340
341

			Ok(())
		}

		/// Register a parachain with given code.
		/// Fails if given ID is already used.
342
		#[weight = SimpleDispatchInfo::FixedOperational(5_000_000)]
343
344
		pub fn register_parachain(origin, id: ParaId, code: Vec<u8>, initial_head_data: Vec<u8>) -> Result {
			ensure_root(origin)?;
Gavin Wood's avatar
Gavin Wood committed
345
			<Self as ParachainRegistrar<T::AccountId>>::register_parachain(id, code, initial_head_data)
346
347
348
		}

		/// Deregister a parachain with given id
349
		#[weight = SimpleDispatchInfo::FixedOperational(10_000)]
350
351
		pub fn deregister_parachain(origin, id: ParaId) -> Result {
			ensure_root(origin)?;
Gavin Wood's avatar
Gavin Wood committed
352
			<Self as ParachainRegistrar<T::AccountId>>::deregister_parachain(id)
353
354
		}

Gav Wood's avatar
Gav Wood committed
355
		fn on_finalize(_n: T::BlockNumber) {
356
357
			assert!(<Self as Store>::DidUpdate::take(), "Parachain heads must be updated once in the block");
		}
Gav's avatar
Gav committed
358
	}
359
360
}

361
362
363
364
365
366
367
368
369
370
fn majority_of(list_len: usize) -> usize {
	list_len / 2 + list_len % 2
}

fn localized_payload(statement: Statement, parent_hash: ::primitives::Hash) -> Vec<u8> {
	let mut encoded = statement.encode();
	encoded.extend(parent_hash.as_ref());
	encoded
}

371
impl<T: Trait> Module<T> {
372
373
374
375
376
377
	/// Dispatch some messages from a parachain.
	fn dispatch_message(
		id: ParaId,
		origin: ParachainDispatchOrigin,
		data: &[u8],
	) {
378
		if let Ok(message_call) = <T as Trait>::Call::decode(&mut &data[..]) {
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
			let origin: <T as Trait>::Origin = match origin {
				ParachainDispatchOrigin::Signed =>
					system::RawOrigin::Signed(id.into_account()).into(),
				ParachainDispatchOrigin::Parachain =>
					Origin::Parachain(id).into(),
			};
			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,
	) -> Result {
		// Either there are no more messages to add...
		if !upward_messages.is_empty() {
Gavin Wood's avatar
Gavin Wood committed
400
			let (count, size) = <RelayDispatchQueueSize>::get(id);
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
			ensure!(
				// ...or we are appending one message onto an empty queue...
				upward_messages.len() + count as usize == 1
				// ...or...
				|| (
					// ...the total messages in the queue ends up being no greater than the
					// limit...
					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
				),
				"Messages added when queue full"
			);
		}
		Ok(())
	}

422
423
424
425
426
427
428
429
430
431
432
433
434
435
	/// Update routing information from the parachain heads. This queues upwards
	/// messages to the relay chain as well.
	fn update_routing(
		now: T::BlockNumber,
		heads: &[AttestedCandidate],
	) {
		// TODO: per-chain watermark
		// https://github.com/paritytech/polkadot/issues/286
		let watermark = now.saturating_sub(One::one());

		let mut ingress_update = BTreeMap::new();

		for head in heads.iter() {
			let id = head.parachain_index();
Gavin Wood's avatar
Gavin Wood committed
436
			<Heads>::insert(id, &head.candidate.head_data.0);
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

			let last_watermark = <Watermarks<T>>::mutate(id, |mark| {
				rstd::mem::replace(mark, Some(watermark))
			});

			if let Some(last_watermark) = last_watermark {
				// Discard routed ingress.
				for routed_height in number_range(last_watermark, watermark) {
					<UnroutedIngress<T>>::remove(&(routed_height, id));
				}
			}

			// place our egress root to `to` into the ingress table for (now, `to`).
			for &(to, root) in &head.candidate.egress_queue_roots {
				ingress_update.entry(to).or_insert_with(Vec::new).push((id, root));
			}

			// Queue up upwards messages (from parachains to relay chain).
			Self::queue_upward_messages(id, &head.candidate.upward_messages);
		}

		// apply the ingress update.
		for (to, ingress_roots) in ingress_update {
			<UnroutedIngress<T>>::insert((now, to), ingress_roots);
		}
	}

464
465
466
	/// Place any new upward messages into our queue for later dispatch.
	fn queue_upward_messages(id: ParaId, upward_messages: &[UpwardMessage]) {
		if !upward_messages.is_empty() {
Gavin Wood's avatar
Gavin Wood committed
467
			<RelayDispatchQueueSize>::mutate(id, |&mut(ref mut count, ref mut len)| {
468
469
470
471
472
473
				*count += upward_messages.len() as u32;
				*len += upward_messages.iter()
					.fold(0, |a, x| a + x.data.len()) as u32;
			});
			// Should never be able to fail assuming our state is uncorrupted, but best not
			// to panic, even if it does.
Gavin Wood's avatar
Gavin Wood committed
474
			let _ = <RelayDispatchQueue>::append(id, upward_messages);
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
		}
	}

	/// Simple round-robin dispatcher, using block number modulo parachain count
	/// to decide which takes precedence and proceeding from there.
	fn dispatch_upward_messages(
		now: T::BlockNumber,
		active_parachains: &[ParaId],
		max_queue_count: usize,
		watermark_queue_size: usize,
		mut dispatch_message: impl FnMut(ParaId, ParachainDispatchOrigin, &[u8]),
	) {
		let para_count = active_parachains.len();
		let offset = (now % T::BlockNumber::from(para_count as u32))
			.checked_into::<usize>()
			.expect("value is modulo a usize value; qed");

		let mut dispatched_count = 0usize;
		let mut dispatched_size = 0usize;
		for id in active_parachains.iter().cycle().skip(offset).take(para_count) {
Gavin Wood's avatar
Gavin Wood committed
495
			let (count, size) = <RelayDispatchQueueSize>::get(id);
496
497
498
499
500
501
502
503
			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...
Gavin Wood's avatar
Gavin Wood committed
504
505
					<RelayDispatchQueueSize>::remove(id);
					let messages = <RelayDispatchQueue>::take(id);
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
					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
					}
				}
			}
		}
	}

521
	/// Calculate the current block's duty roster using system's random seed.
522
523
	/// Returns the duty roster along with the random seed.
	pub fn calculate_duty_roster() -> (DutyRoster, [u8; 32]) {
524
525
		let parachains = Self::active_parachains();
		let parachain_count = parachains.len();
526
		// TODO: use decode length. substrate #2794
527
		let validator_count = Self::authorities().len();
528
		let validators_per_parachain = if parachain_count != 0 { (validator_count - 1) / parachain_count } else { 0 };
529
530

		let mut roles_val = (0..validator_count).map(|i| match i {
531
532
533
534
			i if i < parachain_count * validators_per_parachain => {
				let idx = i / validators_per_parachain;
				Chain::Parachain(parachains[idx].clone())
			}
535
536
			_ => Chain::Relay,
		}).collect::<Vec<_>>();
537

538
539
540

		let mut seed = {
			let phrase = b"validator_role_pairs";
Ashley's avatar
Ashley committed
541
			let seed = randomness_collective_flip::Module::<T>::random(&phrase[..]);
542
543
544
545
546
547
548
549
550
551
552
553
554
555
			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..])
		};
556

557
558
		let orig_seed = seed.clone().to_fixed_bytes();

559
		// shuffle
560
		for i in 0..(validator_count.saturating_sub(1)) {
561
562
			// 4 bytes of entropy used per cycle, 32 bytes entropy per hash
			let offset = (i * 4 % 32) as usize;
563
564

			// number of roles remaining to select from.
565
			let remaining = rstd::cmp::max(1, (validator_count - i) as usize);
566

567
			// 8 32-bit ints per 256-bit seed.
568
569
			let val_index = u32::decode(&mut &seed[offset..offset + 4])
				.expect("using 4 bytes for a 32-bit quantity") as usize % remaining;
570

571
572
			if offset == 28 {
				// into the last 4 bytes - rehash to gather new entropy
573
				seed = BlakeTwo256::hash(seed.as_ref());
574
575
576
577
578
579
			}

			// exchange last item with randomly chosen first.
			roles_val.swap(remaining - 1, val_index);
		}

580
		(DutyRoster { validator_duty: roles_val, }, orig_seed)
581
	}
582

583
	/// Calculate the ingress to a specific parachain.
584
585
586
	/// If `since` is provided, only messages since (including those in) that block
	/// will be included.
	/// Complexity: O(n) in the number of blocks since the supplied block.
587
	/// invoked off-chain.
588
	///
589
	/// Yields a structure containing all unrouted ingress to the parachain.
590
	pub fn ingress(to: ParaId, since: Option<T::BlockNumber>) -> Option<Vec<(T::BlockNumber, BlockIngressRoots)>> {
591
592
593
		let watermark = <Watermarks<T>>::get(to)?;
		let now = <system::Module<T>>::block_number();

594
595
596
597
598
599
600
		let watermark_since = watermark.saturating_add(One::one());
		let since = rstd::cmp::max(since.unwrap_or(Zero::zero()), watermark_since);
		if since > now {
			return Some(Vec::new());
		}

		Some(number_range(since, now)
601
602
603
604
			.filter_map(|unrouted_height| {
				<UnroutedIngress<T>>::get(&(unrouted_height, to)).map(|roots| {
					(unrouted_height, BlockIngressRoots(roots))
				})
605
606
607
608
			})
			.collect())
	}

609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
	/// Get the parachain status necessary for validation.
	pub fn parachain_status(id: &parachain::Id) -> Option<parachain::Status> {
		let balance = T::ParachainCurrency::free_balance(*id);
		Self::parachain_head(id).map(|head_data| parachain::Status {
			head_data: parachain::HeadData(head_data),
			balance,
			// TODO: https://github.com/paritytech/polkadot/issues/92
			// plug in some real values here. most likely governable.
			fee_schedule: parachain::FeeSchedule {
				base: 0,
				per_byte: 0,
			}
		})
	}

624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
	fn check_egress_queue_roots(head: &AttestedCandidate, active_parachains: &[ParaId]) -> Result {
		let mut last_egress_id = None;
		let mut iter = active_parachains.iter();
		for (egress_para_id, root) in &head.candidate.egress_queue_roots {
			// egress routes should be ascending order by parachain ID without duplicate.
			ensure!(
				last_egress_id.as_ref().map_or(true, |x| x < &egress_para_id),
				"Egress routes out of order by ID"
			);

			// a parachain can't route to self
			ensure!(
				*egress_para_id != head.candidate.parachain_index,
				"Parachain routing to self"
			);

			// no empty trie roots
			ensure!(
				*root != EMPTY_TRIE_ROOT.into(),
				"Empty trie root included"
			);

			// can't route to a parachain which doesn't exist
			ensure!(
				iter.find(|x| x == &egress_para_id).is_some(),
				"Routing to non-existent parachain"
			);

			last_egress_id = Some(egress_para_id)
		}
		Ok(())
	}

657
658
	// check the attestations on these candidates. The candidates should have been checked
	// that each candidates' chain ID is valid.
659
660
661
	fn check_candidates(attested_candidates: &[AttestedCandidate], active_parachains: &[ParaId])
		-> rstd::result::Result<IncludedBlocks<T>, &'static str>
	{
662
		use primitives::parachain::ValidityAttestation;
663
		use sr_primitives::traits::AppVerify;
664
665
666
667
668

		// returns groups of slices that have the same chain ID.
		// assumes the inner slice is sorted by id.
		struct GroupedDutyIter<'a> {
			next_idx: usize,
669
			inner: &'a [(usize, ParaId)],
670
671
672
		}

		impl<'a> GroupedDutyIter<'a> {
673
			fn new(inner: &'a [(usize, ParaId)]) -> Self {
674
675
676
				GroupedDutyIter { next_idx: 0, inner }
			}

677
			fn group_for(&mut self, wanted_id: ParaId) -> Option<&'a [(usize, ParaId)]> {
678
679
680
681
682
683
684
685
686
687
688
				while let Some((id, keys)) = self.next() {
					if wanted_id == id {
						return Some(keys)
					}
				}

				None
			}
		}

		impl<'a> Iterator for GroupedDutyIter<'a> {
689
			type Item = (ParaId, &'a [(usize, ParaId)]);
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704

			fn next(&mut self) -> Option<Self::Item> {
				if self.next_idx == self.inner.len() { return None }
				let start_idx = self.next_idx;
				self.next_idx += 1;
				let start_id = self.inner[start_idx].1;

				while self.inner.get(self.next_idx).map_or(false, |&(_, ref id)| id == &start_id) {
					self.next_idx += 1;
				}

				Some((start_id, &self.inner[start_idx..self.next_idx]))
			}
		}

705
706
		let authorities = Self::authorities();
		let (duty_roster, random_seed) = Self::calculate_duty_roster();
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736

		// convert a duty roster, which is originally a Vec<Chain>, where each
		// item corresponds to the same position in the session keys, into
		// a list containing (index, parachain duty) where indices are into the session keys.
		// this list is sorted ascending by parachain duty, just like the
		// parachain candidates are.
		let make_sorted_duties = |duty: &[Chain]| {
			let mut sorted_duties = Vec::with_capacity(duty.len());
			for (val_idx, duty) in duty.iter().enumerate() {
				let id = match duty {
					Chain::Relay => continue,
					Chain::Parachain(id) => id,
				};

				let idx = sorted_duties.binary_search_by_key(&id, |&(_, ref id)| id)
					.unwrap_or_else(|idx| idx);

				sorted_duties.insert(idx, (val_idx, *id));
			}

			sorted_duties
		};

		let sorted_validators = make_sorted_duties(&duty_roster.validator_duty);

		let parent_hash = super::System::parent_hash();
		let localized_payload = |statement: Statement| localized_payload(statement, parent_hash);

		let mut validator_groups = GroupedDutyIter::new(&sorted_validators[..]);

737
		let mut para_block_hashes = Vec::new();
738
		for candidate in attested_candidates {
739
740
			let para_id = candidate.parachain_index();
			let validator_group = validator_groups.group_for(para_id)
741
742
743
744
745
746
747
				.ok_or("no validator group for parachain")?;

			ensure!(
				candidate.validity_votes.len() >= majority_of(validator_group.len()),
				"Not enough validity attestations"
			);

748
749
750
751
752
			ensure!(
				candidate.validity_votes.len() <= authorities.len(),
				"The number of attestations exceeds the number of authorities"
			);

753
754
755
			let fees = candidate.candidate().fees;
			T::ParachainCurrency::deduct(para_id, fees)?;

756
757
758
759
			let mut candidate_hash = None;
			let mut encoded_implicit = None;
			let mut encoded_explicit = None;

760
761
			let mut expected_votes_len = 0;
			for (vote_index, (auth_index, _)) in candidate.validator_indices
762
763
764
				.iter()
				.enumerate()
				.filter(|(_, bit)| *bit)
765
				.enumerate()
766
			{
767
768
769
770
771
772
773
				let validity_attestation = match candidate.validity_votes.get(vote_index) {
					None => return Err("Not enough validity votes"),
					Some(v) => {
						expected_votes_len = vote_index + 1;
						v
					}
				};
774
775
776

				if validator_group.iter().find(|&(idx, _)| *idx == auth_index).is_none() {
					return Err("Attesting validator not on this chain's validation duty.");
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
				}

				let (payload, sig) = match validity_attestation {
					ValidityAttestation::Implicit(sig) => {
						let payload = encoded_implicit.get_or_insert_with(|| localized_payload(
							Statement::Candidate(candidate.candidate.clone()),
						));

						(payload, sig)
					}
					ValidityAttestation::Explicit(sig) => {
						let hash = candidate_hash
							.get_or_insert_with(|| candidate.candidate.hash())
							.clone();

						let payload = encoded_explicit.get_or_insert_with(|| localized_payload(
							Statement::Valid(hash),
						));

						(payload, sig)
					}
				};

				ensure!(
801
					sig.verify(&payload[..], &authorities[auth_index]),
802
803
804
					"Candidate validity attestation signature is bad."
				);
			}
805

806
807
			para_block_hashes.push(candidate_hash.unwrap_or_else(|| candidate.candidate().hash()));

808
		ensure!(
809
810
811
				candidate.validity_votes.len() == expected_votes_len,
				"Extra untagged validity votes along with candidate"
			);
812
813
		}

814
815
816
817
818
819
820
		Ok(IncludedBlocks {
			actual_number: <system::Module<T>>::block_number(),
			session: <session::Module<T>>::current_index(),
			random_seed,
			active_parachains: active_parachains.to_vec(),
			para_blocks: para_block_hashes,
		})
821
822
	}

823
/*
824
	// TODO: Consider integrating if needed. (https://github.com/paritytech/polkadot/issues/223)
825
826
827
828
829
830
	/// Extract the parachain heads from the block.
	pub fn parachain_heads(&self) -> &[CandidateReceipt] {
		let x = self.inner.extrinsics.get(PARACHAINS_SET_POSITION as usize).and_then(|xt| match xt.function {
			Call::Parachains(ParachainsCall::set_heads(ref x)) => Some(&x[..]),
			_ => None
		});
831

832
833
834
		match x {
			Some(x) => x,
			None => panic!("Invalid polkadot block asserted at {:?}", self.file_line),
835
836
		}
	}
837
*/
838
839
}

840
impl<T: Trait> session::OneSessionHandler<T::AccountId> for Module<T> {
841
	type Key = ValidatorId;
842

Gavin Wood's avatar
Gavin Wood committed
843
844
845
846
847
848
	fn on_genesis_session<'a, I: 'a>(validators: I)
		where I: Iterator<Item=(&'a T::AccountId, Self::Key)>
	{
		<Self as Store>::Authorities::put(&validators.map(|(_, key)| key).collect::<Vec<_>>())
	}

849
850
851
852
	fn on_new_session<'a, I: 'a>(changed: bool, validators: I, _queued: I)
		where I: Iterator<Item=(&'a T::AccountId, Self::Key)>
	{
		if changed {
Gavin Wood's avatar
Gavin Wood committed
853
			Self::on_genesis_session(validators)
854
855
856
857
858
859
860
861
862
		}
	}

	fn on_disabled(_i: usize) { }
}

/// An identifier for inherent data that provides new minimally-attested
/// parachain heads.
pub const NEW_HEADS_IDENTIFIER: InherentIdentifier = *b"newheads";
863

864
pub type InherentType = Vec<AttestedCandidate>;
865

866
867
868
impl<T: Trait> ProvideInherent for Module<T> {
	type Call = Call<T>;
	type Error = MakeFatalError<RuntimeString>;
869
	const INHERENT_IDENTIFIER: InherentIdentifier = NEW_HEADS_IDENTIFIER;
870

871
	fn create_inherent(data: &InherentData) -> Option<Self::Call> {
872
		let data = data.get_data::<InherentType>(&NEW_HEADS_IDENTIFIER)
873
874
			.expect("Parachain heads could not be decoded.")
			.expect("No parachain heads found in inherent data.");
875

876
		Some(Call::set_heads(data))
877
878
879
880
881
882
	}
}

#[cfg(test)]
mod tests {
	use super::*;
883
	use super::Call as ParachainsCall;
884
	use bitvec::{bitvec, vec::BitVec};
885
	use sr_io::{TestExternalities, with_externalities};
886
	use substrate_primitives::{H256, Blake2Hasher};
887
	use substrate_trie::NodeCodec;
888
	use sr_primitives::{
889
		Perbill,
Ashley's avatar
Ashley committed
890
		traits::{BlakeTwo256, IdentityLookup, ConvertInto, OnInitialize},
891
		testing::{UintAuthorityId, Header},
thiolliere's avatar
thiolliere committed
892
		curve::PiecewiseLinear,
893
	};
894
	use primitives::{
895
896
		parachain::{CandidateReceipt, HeadData, ValidityAttestation, ValidatorId},
		BlockNumber,
897
	};
898
899
	use crate::constants::time::*;
	use keyring::Sr25519Keyring;
900
901
902
	use srml_support::{
		impl_outer_origin, impl_outer_dispatch, assert_ok, assert_err, parameter_types,
	};
903
	use crate::parachains;
904

905
	impl_outer_origin! {
906
907
908
909
910
911
912
913
914
		pub enum Origin for Test {
			parachains
		}
	}

	impl_outer_dispatch! {
		pub enum Call for Test where origin: Origin {
			parachains::Parachains,
		}
915
916
	}

Gav Wood's avatar
Gav Wood committed
917
	#[derive(Clone, Eq, PartialEq)]
918
	pub struct Test;
919
	parameter_types! {
920
		pub const BlockHashCount: u32 = 250;
921
922
923
		pub const MaximumBlockWeight: u32 = 4 * 1024 * 1024;
		pub const MaximumBlockLength: u32 = 4 * 1024 * 1024;
		pub const AvailableBlockRatio: Perbill = Perbill::from_percent(75);
924
	}
925
	impl system::Trait for Test {
926
		type Origin = Origin;
927
		type Call = Call;
928
		type Index = u64;
929
930
		type BlockNumber = u64;
		type Hash = H256;
Gav Wood's avatar
Gav Wood committed
931
		type Hashing = BlakeTwo256;
932
933
934
		type AccountId = u64;
		type Lookup = IdentityLookup<u64>;
		type Header = Header;
935
		type WeightMultiplierUpdate = ();
Gav's avatar
Gav committed
936
		type Event = ();
937
		type BlockHashCount = BlockHashCount;
938
939
940
		type MaximumBlockWeight = MaximumBlockWeight;
		type MaximumBlockLength = MaximumBlockLength;
		type AvailableBlockRatio = AvailableBlockRatio;
941
		type Version = ();
942
	}
943
944
945
946

	parameter_types! {
		pub const Period: BlockNumber = 1;
		pub const Offset: BlockNumber = 0;
thiolliere's avatar
thiolliere committed
947
		pub const DisabledValidatorsThreshold: Perbill = Perbill::from_percent(17);
948
949
	}

950
	impl session::Trait for Test {
951
952
953
954
		type OnSessionEnding = ();
		type Keys = UintAuthorityId;
		type ShouldEndSession = session::PeriodicSessions<Period, Offset>;
		type SessionHandler = ();
Gav's avatar
Gav committed
955
		type Event = ();
956
		type SelectInitialValidators = staking::Module<Self>;
957
		type ValidatorId = u64;
958
		type ValidatorIdOf = staking::StashOf<Self>;
thiolliere's avatar
thiolliere committed
959
		type DisabledValidatorsThreshold = DisabledValidatorsThreshold;
960
961
962
	}

	impl session::historical::Trait for Test {
963
		type FullIdentification = staking::Exposure<u64, Balance>;
964
		type FullIdentificationOf = staking::ExposureOf<Self>;
965
	}
966

967
968
969
	parameter_types! {
		pub const MinimumPeriod: u64 = 3;
	}
970
971
	impl timestamp::Trait for Test {
		type Moment = u64;
972
		type OnTimestampSet = ();
973
		type MinimumPeriod = MinimumPeriod;
974
	}
975

976
	parameter_types! {
977
		pub const EpochDuration: u64 = EPOCH_DURATION_IN_BLOCKS as u64;
978
979
980
981
982
983
		pub const ExpectedBlockTime: u64 = MILLISECS_PER_BLOCK;
	}

	impl babe::Trait for Test {
		type EpochDuration = EpochDuration;
		type ExpectedBlockTime = ExpectedBlockTime;
984
985
986

		// session module is the trigger
		type EpochChangeTrigger = babe::ExternalTrigger;
987
988
	}

Gavin Wood's avatar
Gavin Wood committed
989
990
991
992
993
994
995
996
	parameter_types! {
		pub const ExistentialDeposit: Balance = 0;
		pub const TransferFee: Balance = 0;
		pub const CreationFee: Balance = 0;
		pub const TransactionBaseFee: Balance = 0;
		pub const TransactionByteFee: Balance = 0;
	}

997
	impl balances::Trait for Test {
998
		type Balance = Balance;
999
1000
		type OnFreeBalanceZero = ();
		type OnNewAccount = ();
For faster browsing, not all history is shown. View entire blame