parachains.rs 11.5 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// Copyright 2017 Parity Technologies (UK) Ltd.
// This file is part of Polkadot.

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

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

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

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

Gav Wood's avatar
Gav Wood committed
19
use primitives;
20
21
use rstd::prelude::*;
use codec::{Slicable, Joiner};
22
23

use runtime_primitives::traits::{Executable, RefInto, MaybeEmpty};
Gav Wood's avatar
Gav Wood committed
24
use primitives::parachain::{Id, Chain, DutyRoster, CandidateReceipt};
25
26
use {system, session};

Gav Wood's avatar
Gav Wood committed
27
28
use substrate_runtime_support::{Hashable, StorageValue, StorageMap};
use substrate_runtime_support::dispatch::Result;
29
30
31
32
33
34
35

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

#[cfg(any(feature = "std", test))]
use {runtime_io, runtime_primitives};

36
pub trait Trait: session::Trait<Hash = primitives::Hash> {
37
38
39
40
41
	/// The position of the set_heads call in the block.
	const SET_POSITION: u32;

	type PublicAux: RefInto<Self::AccountId> + MaybeEmpty;
}
42
43

decl_module! {
Gav Wood's avatar
Gav Wood committed
44
	/// Parachains module.
45
	pub struct Module<T: Trait>;
Gav Wood's avatar
Gav Wood committed
46
47
48

	/// Call type for parachains.
	#[cfg_attr(feature = "std", derive(Serialize, Deserialize))]
49
50
	pub enum Call where aux: <T as Trait>::PublicAux {
		// provide candidate receipts for parachains, in ascending order by id.
51
		fn set_heads(aux, heads: Vec<CandidateReceipt>) -> Result = 0;
52
	}
53
54
55
}

decl_storage! {
56
57
58
59
60
61
62
63
64
65
	trait Store for Module<T: Trait>;
	// Vector of all parachain IDs.
	pub Parachains get(active_parachains): b"para:chains" => default Vec<Id>;
	// The parachains registered at present.
	pub Code get(parachain_code): b"para:code" => map [ Id => Vec<u8> ];
	// The heads of the parachains registered at present. these are kept sorted.
	pub Heads get(parachain_head): b"para:head" => map [ Id => Vec<u8> ];

	// Did the parachain heads get updated in this block?
	DidUpdate: b"para:did" => default bool;
66
67
68
}

impl<T: Trait> Module<T> {
69
	/// Calculate the current block's duty roster using system's random seed.
70
	pub fn calculate_duty_roster() -> DutyRoster {
71
72
73
		let parachains = Self::active_parachains();
		let parachain_count = parachains.len();
		let validator_count = <session::Module<T>>::validator_count() as usize;
74
		let validators_per_parachain = if parachain_count != 0 { (validator_count - 1) / parachain_count } else { 0 };
75
76

		let mut roles_val = (0..validator_count).map(|i| match i {
77
78
79
80
			i if i < parachain_count * validators_per_parachain => {
				let idx = i / validators_per_parachain;
				Chain::Parachain(parachains[idx].clone())
			}
81
82
			_ => Chain::Relay,
		}).collect::<Vec<_>>();
83

84
85
		let mut roles_gua = roles_val.clone();

86
87
		let random_seed = system::Module::<T>::random_seed();
		let mut seed = random_seed.to_vec().and(b"validator_role_pairs").blake2_256();
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

		// shuffle
		for i in 0..(validator_count - 1) {
			// 8 bytes of entropy used per cycle, 32 bytes entropy per hash
			let offset = (i * 8 % 32) as usize;

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

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

			if offset == 24 {
				// into the last 8 bytes - rehash to gather new entropy
				seed = seed.blake2_256();
			}

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

		DutyRoster {
			validator_duty: roles_val,
			guarantor_duty: roles_gua,
		}
	}
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143

	/// Register a parachain with given code.
	/// Fails if given ID is already used.
	pub fn register_parachain(id: Id, code: Vec<u8>, initial_head_data: Vec<u8>) {
		let mut parachains = Self::active_parachains();
		match parachains.binary_search(&id) {
			Ok(_) => panic!("Parachain with id {} already exists", id.into_inner()),
			Err(idx) => parachains.insert(idx, id),
		}

		<Code<T>>::insert(id, code);
		<Parachains<T>>::put(parachains);
		<Heads<T>>::insert(id, initial_head_data);
	}

	/// Deregister a parachain with given id
	pub fn deregister_parachain(id: Id) {
		let mut parachains = Self::active_parachains();
		match parachains.binary_search(&id) {
			Ok(idx) => { parachains.remove(idx); }
			Err(_) => {}
		}

		<Code<T>>::remove(id);
		<Heads<T>>::remove(id);
		<Parachains<T>>::put(parachains);
	}

144
145
146
147
	fn set_heads(aux: &<T as Trait>::PublicAux, heads: Vec<CandidateReceipt>) -> Result {
		ensure!(aux.is_empty(), "set_heads must not be signed");
		ensure!(!<DidUpdate<T>>::exists(), "Parachain heads must be updated only once in the block");
		ensure!(
148
			<system::Module<T>>::extrinsic_index() == T::SET_POSITION,
149
150
			"Parachain heads update extrinsic must be at position {} in the block"
//			, T::SET_POSITION
151
152
153
154
155
156
157
		);

		let active_parachains = Self::active_parachains();
		let mut iter = active_parachains.iter();

		// perform this check before writing to storage.
		for head in &heads {
158
			ensure!(
159
				iter.find(|&p| p == &head.parachain_index).is_some(),
160
161
				"Submitted candidate for unregistered or out-of-order parachain {}"
//				, head.parachain_index.into_inner()
162
163
164
165
166
167
168
169
170
			);
		}

		for head in heads {
			let id = head.parachain_index.clone();
			<Heads<T>>::insert(id, head.head_data.0);
		}

		<DidUpdate<T>>::put(true);
171
172

		Ok(())
173
	}
174
175
176
177
}

impl<T: Trait> Executable for Module<T> {
	fn execute() {
178
		assert!(<Self as Store>::DidUpdate::take(), "Parachain heads must be updated once in the block");
179
180
181
	}
}

182
/// Parachains module genesis configuration.
183
#[cfg(any(feature = "std", test))]
184
185
186
#[derive(Serialize, Deserialize)]
#[serde(rename_all = "camelCase")]
#[serde(deny_unknown_fields)]
187
pub struct GenesisConfig<T: Trait> {
188
189
190
	/// The initial parachains, mapped to code.
	pub parachains: Vec<(Id, Vec<u8>)>,
	/// Phantom data.
191
	#[serde(skip)]
192
193
194
195
196
197
198
	pub phantom: PhantomData<T>,
}

#[cfg(any(feature = "std", test))]
impl<T: Trait> Default for GenesisConfig<T> {
	fn default() -> Self {
		GenesisConfig {
199
			parachains: Vec::new(),
200
201
202
203
204
205
			phantom: PhantomData,
		}
	}
}

#[cfg(any(feature = "std", test))]
Gav Wood's avatar
Gav Wood committed
206
impl<T: Trait> runtime_primitives::BuildStorage for GenesisConfig<T>
207
{
208
	fn build_storage(mut self) -> ::std::result::Result<runtime_io::TestExternalities, String> {
209
		use std::collections::HashMap;
210
211
		use runtime_io::twox_128;
		use codec::Slicable;
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226

		self.parachains.sort_unstable_by_key(|&(ref id, _)| id.clone());
		self.parachains.dedup_by_key(|&mut (ref id, _)| id.clone());

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

		let mut map: HashMap<_, _> = map![
			twox_128(<Parachains<T>>::key()).to_vec() => only_ids.encode()
		];

		for (id, code) in self.parachains {
			let key = twox_128(&<Code<T>>::key_for(&id)).to_vec();
			map.insert(key, code.encode());
		}

227
		Ok(map.into())
228
229
230
231
232
233
234
235
	}
}

#[cfg(test)]
mod tests {
	use super::*;
	use runtime_io::with_externalities;
	use substrate_primitives::H256;
Gav Wood's avatar
Gav Wood committed
236
	use runtime_primitives::BuildStorage;
Gav Wood's avatar
Gav Wood committed
237
	use runtime_primitives::traits::{HasPublicAux, Identity, BlakeTwo256};
238
	use runtime_primitives::testing::{Digest, Header};
239
	use {consensus, timestamp};
240

Gav Wood's avatar
Gav Wood committed
241
	#[derive(Clone, Eq, PartialEq)]
242
243
244
245
246
247
248
249
250
251
252
253
	pub struct Test;
	impl HasPublicAux for Test {
		type PublicAux = u64;
	}
	impl consensus::Trait for Test {
		type PublicAux = <Self as HasPublicAux>::PublicAux;
		type SessionKey = u64;
	}
	impl system::Trait for Test {
		type Index = u64;
		type BlockNumber = u64;
		type Hash = H256;
Gav Wood's avatar
Gav Wood committed
254
		type Hashing = BlakeTwo256;
255
256
257
258
259
260
		type Digest = Digest;
		type AccountId = u64;
		type Header = Header;
	}
	impl session::Trait for Test {
		type ConvertAccountIdToSessionKey = Identity;
261
262
263
264
265
		type OnSessionChange = ();
	}
	impl timestamp::Trait for Test {
		const TIMESTAMP_SET_POSITION: u32 = 0;
		type Moment = u64;
266
	}
267
268
269
270
271
	impl Trait for Test {
		const SET_POSITION: u32 = 0;

		type PublicAux = <Self as HasPublicAux>::PublicAux;
	}
272
273
274

	type Parachains = Module<Test>;

275
	fn new_test_ext(parachains: Vec<(Id, Vec<u8>)>) -> runtime_io::TestExternalities {
276
		let mut t = system::GenesisConfig::<Test>::default().build_storage().unwrap();
277
278
279
		t.extend(consensus::GenesisConfig::<Test>{
			code: vec![],
			authorities: vec![1, 2, 3],
280
		}.build_storage().unwrap());
281
282
283
		t.extend(session::GenesisConfig::<Test>{
			session_length: 1000,
			validators: vec![1, 2, 3, 4, 5, 6, 7, 8],
284
			broken_percent_late: 100,
285
		}.build_storage().unwrap());
286
		t.extend(GenesisConfig::<Test>{
287
			parachains: parachains,
288
			phantom: PhantomData,
289
		}.build_storage().unwrap());
290
291
292
293
		t
	}

	#[test]
294
295
296
297
298
299
300
301
302
303
	fn active_parachains_should_work() {
		let parachains = vec![
			(5u32.into(), vec![1,2,3]),
			(100u32.into(), vec![4,5,6]),
		];

		with_externalities(&mut new_test_ext(parachains), || {
			assert_eq!(Parachains::active_parachains(), vec![5u32.into(), 100u32.into()]);
			assert_eq!(Parachains::parachain_code(&5u32.into()), Some(vec![1,2,3]));
			assert_eq!(Parachains::parachain_code(&100u32.into()), Some(vec![4,5,6]));
304
305
306
307
		});
	}

	#[test]
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
	fn register_deregister() {
		let parachains = vec![
			(5u32.into(), vec![1,2,3]),
			(100u32.into(), vec![4,5,6]),
		];

		with_externalities(&mut new_test_ext(parachains), || {
			assert_eq!(Parachains::active_parachains(), vec![5u32.into(), 100u32.into()]);

			assert_eq!(Parachains::parachain_code(&5u32.into()), Some(vec![1,2,3]));
			assert_eq!(Parachains::parachain_code(&100u32.into()), Some(vec![4,5,6]));

			Parachains::register_parachain(99u32.into(), vec![7,8,9], vec![1, 1, 1]);

			assert_eq!(Parachains::active_parachains(), vec![5u32.into(), 99u32.into(), 100u32.into()]);
			assert_eq!(Parachains::parachain_code(&99u32.into()), Some(vec![7,8,9]));

			Parachains::deregister_parachain(5u32.into());

			assert_eq!(Parachains::active_parachains(), vec![99u32.into(), 100u32.into()]);
			assert_eq!(Parachains::parachain_code(&5u32.into()), None);
		});
	}

	#[test]
	fn duty_roster_works() {
		let parachains = vec![
			(0u32.into(), vec![]),
			(1u32.into(), vec![]),
		];

		with_externalities(&mut new_test_ext(parachains), || {
340
341
342
343
344
345
346
347
348
349
350
			let check_roster = |duty_roster: &DutyRoster| {
				assert_eq!(duty_roster.validator_duty.len(), 8);
				assert_eq!(duty_roster.guarantor_duty.len(), 8);
				for i in (0..2).map(Id::from) {
					assert_eq!(duty_roster.validator_duty.iter().filter(|&&j| j == Chain::Parachain(i)).count(), 3);
					assert_eq!(duty_roster.guarantor_duty.iter().filter(|&&j| j == Chain::Parachain(i)).count(), 3);
				}
				assert_eq!(duty_roster.validator_duty.iter().filter(|&&j| j == Chain::Relay).count(), 2);
				assert_eq!(duty_roster.guarantor_duty.iter().filter(|&&j| j == Chain::Relay).count(), 2);
			};

351
			system::Module::<Test>::set_random_seed([0u8; 32].into());
352
353
354
			let duty_roster_0 = Parachains::calculate_duty_roster();
			check_roster(&duty_roster_0);

355
			system::Module::<Test>::set_random_seed([1u8; 32].into());
356
357
358
359
			let duty_roster_1 = Parachains::calculate_duty_roster();
			check_roster(&duty_roster_1);
			assert!(duty_roster_0 != duty_roster_1);

360
361

			system::Module::<Test>::set_random_seed([2u8; 32].into());
362
363
364
365
366
367
368
			let duty_roster_2 = Parachains::calculate_duty_roster();
			check_roster(&duty_roster_2);
			assert!(duty_roster_0 != duty_roster_2);
			assert!(duty_roster_1 != duty_roster_2);
		});
	}
}