parachains.rs 59 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 parity_codec::{Encode, Decode, HasCompact};
22
use srml_support::{decl_storage, decl_module, fail, ensure};
23

24
use sr_primitives::traits::{Hash as HashT, BlakeTwo256, Member, CheckedConversion, Saturating, One};
25
use sr_primitives::weights::SimpleDispatchInfo;
26
use primitives::{Hash, Balance, ParachainPublic, parachain::{
27
	self, Id as ParaId, Chain, DutyRoster, AttestedCandidate, Statement, AccountIdConversion,
28
	ParachainDispatchOrigin, UpwardMessage, BlockIngressRoots,
29
}};
30
use {system, session};
31
use srml_support::{
32
	StorageValue, StorageMap, storage::AppendableStorageMap, Parameter, Dispatchable, dispatch::Result,
33
	traits::{Currency, Get, WithdrawReason, ExistenceRequirement}
34
};
35

Gavin Wood's avatar
Gavin Wood committed
36
37
#[cfg(feature = "std")]
use srml_support::storage::hashed::generator;
38

39
40
use inherents::{ProvideInherent, InherentData, RuntimeString, MakeFatalError, InherentIdentifier};

41
#[cfg(any(feature = "std", test))]
Gav Wood's avatar
Gav Wood committed
42
use sr_primitives::{StorageOverlay, ChildrenStorageOverlay};
43

44
45
46
#[cfg(any(feature = "std", test))]
use rstd::marker::PhantomData;

47
use system::{ensure_none, ensure_root};
48
use crate::attestations::{self, IncludedBlocks};
49

50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
// 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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
/// 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
95
		<NextFreeId>::mutate(|n| { let r = *n; *n = ParaId::from(u32::from(*n) + 1); r })
Gavin Wood's avatar
Gavin Wood committed
96
97
98
99
100
101
102
103
	}
	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
104
105
106
		<Code>::insert(id, code);
		<Parachains>::put(parachains);
		<Heads>::insert(id, initial_head_data);
Gavin Wood's avatar
Gavin Wood committed
107

108
109
110
111
112
113
		// 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
114
115
116
117
118
119
120
121
122
		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
123
124
		<Code>::remove(id);
		<Heads>::remove(id);
Gavin Wood's avatar
Gavin Wood committed
125

126
127
128
129
130
131
132
133
134
135
136
		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
137
138
		}

Gavin Wood's avatar
Gavin Wood committed
139
		<Parachains>::put(parachains);
Gavin Wood's avatar
Gavin Wood committed
140
141
142
143
144

		Ok(())
	}
}

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
171
172
173
174
175
// 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(())
	}
}

176
177
178
179
180
181
182
183
184
185
/// 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 {
186
187
188
189
190
	/// 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>;
191
192
193

	/// Some way of interacting with balances for fees.
	type ParachainCurrency: ParachainCurrency<Self::AccountId>;
194
195
196
197
198
199
200
201
}

/// 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
202
}
203

204
205
206
207
208
209
// 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
];

210
211
212
213
214
215
216
/// 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;

217
decl_storage! {
Gav's avatar
Gav committed
218
	trait Store for Module<T: Trait> as Parachains {
219
220
221
		/// All authorities' keys at the moment.
		pub Authorities get(authorities) config(authorities): Vec<ParachainPublic>;
		/// Vector of all parachain IDs.
222
		pub Parachains get(active_parachains): Vec<ParaId>;
223
		/// The parachains registered at present.
224
		pub Code get(parachain_code): map ParaId => Option<Vec<u8>>;
225
		/// The heads of the parachains registered at present.
226
		pub Heads get(parachain_head): map ParaId => Option<Vec<u8>>;
227
228
229
		/// 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.
230
231
232
233
234
235
236
		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
237

238
239
240
241
242
		/// 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
243
		///	second if the total length (in bytes) of the message payloads.
244
245
		pub RelayDispatchQueueSize: map ParaId => (u32, u32);

246
		/// Did the parachain heads get updated in this block?
247
		DidUpdate: bool;
Gavin Wood's avatar
Gavin Wood committed
248
249
250

		/// The next unused ParaId value.
		NextFreeId: ParaId;
251
252
	}
	add_extra_genesis {
253
		config(parachains): Vec<(ParaId, Vec<u8>, Vec<u8>)>;
254
		config(_phdata): PhantomData<T>;
Gav Wood's avatar
Gav Wood committed
255
		build(|storage: &mut StorageOverlay, _: &mut ChildrenStorageOverlay, config: &GenesisConfig<T>| {
256
257
			use sr_primitives::traits::Zero;

258
			let mut p = config.parachains.clone();
259
260
			p.sort_unstable_by_key(|&(ref id, _, _)| *id);
			p.dedup_by_key(|&mut (ref id, _, _)| *id);
261
262
263

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

Gavin Wood's avatar
Gavin Wood committed
264
			<Parachains as generator::StorageValue<_>>::put(&only_ids, storage);
265
266

			for (id, code, genesis) in p {
267
				// no ingress -- a chain cannot be routed to until it is live.
Gavin Wood's avatar
Gavin Wood committed
268
269
				<Code as generator::StorageMap<_, _>>::insert(&id, &code, storage);
				<Heads as generator::StorageMap<_, _>>::insert(&id, &genesis, storage);
270
				<Watermarks<T> as generator::StorageMap<_, _>>::insert(&id, &Zero::zero(), storage);
271
272
273
274
275
276
277
			}
		});
	}
}

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

			let active_parachains = Self::active_parachains();
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
314
315
316
317
			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());
					}
318
319
				}

320
				let para_blocks = Self::check_candidates(&heads, &active_parachains)?;
321

322
				let current_number = <system::Module<T>>::block_number();
323

324
325
				<attestations::Module<T>>::note_included(&heads, para_blocks);

326
327
				Self::update_routing(
					current_number,
328
					&heads,
329
				);
330
331

				Self::dispatch_upward_messages(
332
					current_number,
333
334
335
336
337
					&active_parachains,
					MAX_QUEUE_COUNT,
					WATERMARK_QUEUE_SIZE,
					Self::dispatch_message,
				);
338
339
			}

Gavin Wood's avatar
Gavin Wood committed
340
			<DidUpdate>::put(true);
341
342
343
344
345
346

			Ok(())
		}

		/// Register a parachain with given code.
		/// Fails if given ID is already used.
347
		#[weight = SimpleDispatchInfo::FixedOperational(5_000_000)]
348
349
		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
350
			<Self as ParachainRegistrar<T::AccountId>>::register_parachain(id, code, initial_head_data)
351
352
353
		}

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

Gav Wood's avatar
Gav Wood committed
360
		fn on_finalize(_n: T::BlockNumber) {
361
362
			assert!(<Self as Store>::DidUpdate::take(), "Parachain heads must be updated once in the block");
		}
Gav's avatar
Gav committed
363
	}
364
365
}

366
367
368
369
370
371
372
373
374
375
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
}

376
impl<T: Trait> Module<T> {
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
	/// Dispatch some messages from a parachain.
	fn dispatch_message(
		id: ParaId,
		origin: ParachainDispatchOrigin,
		data: &[u8],
	) {
		if let Some(message_call) = T::Call::decode(&mut &data[..]) {
			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
405
			let (count, size) = <RelayDispatchQueueSize>::get(id);
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
			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(())
	}

427
428
429
430
431
432
433
434
435
436
437
438
439
440
	/// 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
441
			<Heads>::insert(id, &head.candidate.head_data.0);
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

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

469
470
471
	/// 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
472
			<RelayDispatchQueueSize>::mutate(id, |&mut(ref mut count, ref mut len)| {
473
474
475
476
477
478
				*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
479
			let _ = <RelayDispatchQueue>::append(id, upward_messages);
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
		}
	}

	/// 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
500
			let (count, size) = <RelayDispatchQueueSize>::get(id);
501
502
503
504
505
506
507
508
			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
509
510
					<RelayDispatchQueueSize>::remove(id);
					let messages = <RelayDispatchQueue>::take(id);
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
					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
					}
				}
			}
		}
	}

526
	/// Calculate the current block's duty roster using system's random seed.
527
528
	/// Returns the duty roster along with the random seed.
	pub fn calculate_duty_roster() -> (DutyRoster, [u8; 32]) {
529
530
		let parachains = Self::active_parachains();
		let parachain_count = parachains.len();
531
		let validator_count = Self::authorities().len();
532
		let validators_per_parachain = if parachain_count != 0 { (validator_count - 1) / parachain_count } else { 0 };
533
534

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

542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559

		let mut seed = {
			let phrase = b"validator_role_pairs";
			let seed = system::Module::<T>::random(&phrase[..]);
			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..])
		};
560

561
562
		let orig_seed = seed.clone().to_fixed_bytes();

563
564
		// shuffle
		for i in 0..(validator_count - 1) {
565
566
			// 4 bytes of entropy used per cycle, 32 bytes entropy per hash
			let offset = (i * 4 % 32) as usize;
567
568
569
570

			// number of roles remaining to select from.
			let remaining = (validator_count - i) as usize;

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

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

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

584
		(DutyRoster { validator_duty: roles_val, }, orig_seed)
585
	}
586

587
	/// Calculate the ingress to a specific parachain.
588
589
	/// Complexity: O(n) in the number of blocks since the parachain's watermark.
	/// invoked off-chain.
590
	///
591
592
593
594
595
596
597
598
599
600
	/// Yields a structure containing all unrouted ingress to the parachain.
	pub fn ingress(to: ParaId) -> Option<Vec<(T::BlockNumber, BlockIngressRoots)>> {
		let watermark = <Watermarks<T>>::get(to)?;
		let now = <system::Module<T>>::block_number();

		Some(number_range(watermark.saturating_add(One::one()),now)
			.filter_map(|unrouted_height| {
				<UnroutedIngress<T>>::get(&(unrouted_height, to)).map(|roots| {
					(unrouted_height, BlockIngressRoots(roots))
				})
601
602
603
604
			})
			.collect())
	}

605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
	/// 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,
			}
		})
	}

620
621
622
623
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
	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(())
	}

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

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

		impl<'a> GroupedDutyIter<'a> {
669
			fn new(inner: &'a [(usize, ParaId)]) -> Self {
670
671
672
				GroupedDutyIter { next_idx: 0, inner }
			}

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

				None
			}
		}

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

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

701
702
		let authorities = Self::authorities();
		let (duty_roster, random_seed) = Self::calculate_duty_roster();
703
704
705
706
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

		// 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[..]);

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

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

744
745
746
747
748
			ensure!(
				candidate.validity_votes.len() <= authorities.len(),
				"The number of attestations exceeds the number of authorities"
			);

749
750
751
			let fees = candidate.candidate().fees;
			T::ParachainCurrency::deduct(para_id, fees)?;

752
753
754
755
			let mut candidate_hash = None;
			let mut encoded_implicit = None;
			let mut encoded_explicit = None;

756
757
			let mut expected_votes_len = 0;
			for (vote_index, (auth_index, _)) in candidate.validator_indices
758
759
760
				.iter()
				.enumerate()
				.filter(|(_, bit)| *bit)
761
				.enumerate()
762
			{
763
764
765
766
767
768
769
				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
					}
				};
770
771
772

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

				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!(
797
					sig.verify(&payload[..], &authorities[auth_index]),
798
799
800
					"Candidate validity attestation signature is bad."
				);
			}
801

802
803
804
			para_block_hashes.push(candidate_hash.unwrap_or_else(|| candidate.candidate().hash()));

      ensure!(
805
806
807
				candidate.validity_votes.len() == expected_votes_len,
				"Extra untagged validity votes along with candidate"
			);
808
809
		}

810
811
812
813
814
815
816
		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,
		})
817
818
	}

819
/*
820
	// TODO: Consider integrating if needed. (https://github.com/paritytech/polkadot/issues/223)
821
822
823
824
825
826
	/// 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
		});
827

828
829
830
		match x {
			Some(x) => x,
			None => panic!("Invalid polkadot block asserted at {:?}", self.file_line),
831
832
		}
	}
833
*/
834
835
}

836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
impl<T: Trait> session::OneSessionHandler<T::AccountId> for Module<T> {
	type Key = ParachainPublic;

	fn on_new_session<'a, I: 'a>(changed: bool, validators: I, _queued: I)
		where I: Iterator<Item=(&'a T::AccountId, Self::Key)>
	{
		if changed {
			<Self as Store>::Authorities::put(&validators.map(|(_, key)| key).collect::<Vec<_>>())
		}
	}

	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";
853

854
pub type InherentType = Vec<AttestedCandidate>;
855

856
857
858
impl<T: Trait> ProvideInherent for Module<T> {
	type Call = Call<T>;
	type Error = MakeFatalError<RuntimeString>;
859
	const INHERENT_IDENTIFIER: InherentIdentifier = NEW_HEADS_IDENTIFIER;
860

861
	fn create_inherent(data: &InherentData) -> Option<Self::Call> {
862
		let data = data.get_data::<InherentType>(&NEW_HEADS_IDENTIFIER)
863
864
			.expect("Parachain heads could not be decoded.")
			.expect("No parachain heads found in inherent data.");
865

866
		Some(Call::set_heads(data))
867
868
869
870
871
872
	}
}

#[cfg(test)]
mod tests {
	use super::*;
873
	use super::Call as ParachainsCall;
874
	use bitvec::{bitvec, vec::BitVec};
875
	use sr_io::{TestExternalities, with_externalities};
876
	use substrate_primitives::{H256, Blake2Hasher};
877
	use substrate_trie::NodeCodec;
878
	use sr_primitives::{
879
880
		Perbill,
		traits::{BlakeTwo256, IdentityLookup, ConvertInto},
881
		testing::{UintAuthorityId, Header},
882
	};
883
	use primitives::{
884
		parachain::{CandidateReceipt, HeadData, ValidityAttestation}, SessionKey,
885
		BlockNumber, AuraId,
886
	};
887
	use keyring::Ed25519Keyring;
888
889
890
	use srml_support::{
		impl_outer_origin, impl_outer_dispatch, assert_ok, assert_err, parameter_types,
	};
891
	use crate::parachains;
892

893
	impl_outer_origin! {
894
895
896
897
898
899
900
901
902
		pub enum Origin for Test {
			parachains
		}
	}

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

Gav Wood's avatar
Gav Wood committed
905
	#[derive(Clone, Eq, PartialEq)]
906
	pub struct Test;
907
908
	parameter_types! {
		pub const BlockHashCount: u64 = 250;
909
910
911
		pub const MaximumBlockWeight: u32 = 4 * 1024 * 1024;
		pub const MaximumBlockLength: u32 = 4 * 1024 * 1024;
		pub const AvailableBlockRatio: Perbill = Perbill::from_percent(75);
912
	}
913
	impl system::Trait for Test {
914
		type Origin = Origin;
915
		type Index = u64;
916
917
		type BlockNumber = u64;
		type Hash = H256;
Gav Wood's avatar
Gav Wood committed
918
		type Hashing = BlakeTwo256;
919
920
921
		type AccountId = u64;
		type Lookup = IdentityLookup<u64>;
		type Header = Header;
922
		type WeightMultiplierUpdate = ();
Gav's avatar
Gav committed
923
		type Event = ();
924
		type BlockHashCount = BlockHashCount;
925
926
927
		type MaximumBlockWeight = MaximumBlockWeight;
		type MaximumBlockLength = MaximumBlockLength;
		type AvailableBlockRatio = AvailableBlockRatio;
928
	}
929
930
931
932
933
934

	parameter_types! {
		pub const Period: BlockNumber = 1;
		pub const Offset: BlockNumber = 0;
	}

935
	impl session::Trait for Test {
936
937
938
939
		type OnSessionEnding = ();
		type Keys = UintAuthorityId;
		type ShouldEndSession = session::PeriodicSessions<Period, Offset>;
		type SessionHandler = ();
Gav's avatar
Gav committed
940
		type Event = ();
941
		type SelectInitialValidators = staking::Module<Self>;
942
		type ValidatorId = u64;
943
944
945
946
		type ValidatorIdOf = staking::StashOf<Self>;
	}

	impl session::historical::Trait for Test {
947
		type FullIdentification = staking::Exposure<u64, Balance>;
948
		type FullIdentificationOf = staking::ExposureOf<Self>;
949
	}
950

951
952
953
	parameter_types! {
		pub const MinimumPeriod: u64 = 3;
	}
954
955
	impl timestamp::Trait for Test {
		type Moment = u64;
956
		type OnTimestampSet = ();
957
		type MinimumPeriod = MinimumPeriod;
958
	}
959
960
961
962
963
964

	impl aura::Trait for Test {
		type HandleReport = aura::StakingSlasher<Test>;
		type AuthorityId = AuraId;
	}

Gavin Wood's avatar
Gavin Wood committed
965
966
967
968
969
970
971
972
	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;
	}

973
	impl balances::Trait for Test {
974
		type Balance = Balance;
975
976
977
978
979
980
		type OnFreeBalanceZero = ();
		type OnNewAccount = ();
		type Event = ();
		type TransactionPayment = ();
		type DustRemoval = ();
		type TransferPayment = ();
Gavin Wood's avatar
Gavin Wood committed
981
982
983
984
985
		type ExistentialDeposit = ExistentialDeposit;
		type TransferFee = TransferFee;
		type CreationFee = CreationFee;
		type TransactionBaseFee = TransactionBaseFee;
		type TransactionByteFee = TransactionByteFee;
986
		type WeightToFee = ConvertInto;
987
988
989
990
991
	}

	parameter_types! {
		pub const SessionsPerEra: session::SessionIndex = 6;
		pub const BondingDuration: staking::EraIndex = 24 * 28;
992
		pub const AttestationPeriod: u64 = 100;
993
994
995
996
997
998
999
1000
	}

	impl staking::Trait for Test {
		type OnRewardMinted = ();
		type CurrencyToVote = ();
		type Event = ();
		type Currency = balances::Module<Test>;
		type Slash = ();
For faster browsing, not all history is shown. View entire blame