collation.rs 23.2 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 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/>.

//! Validator-side view of collation.
//!
//! This module contains type definitions, a trait for a batch of collators, and a trait for
//! attempting to fetch a collation repeatedly until a valid one is obtained.

use std::sync::Arc;

24
25
26
27
use polkadot_primitives::{BlakeTwo256, Block, Hash, HashT, BlockId, Balance, parachain::{
	CollatorId, ConsolidatedIngress, StructuredUnroutedIngress, CandidateReceipt, CollationInfo, ParachainHost,
	Id as ParaId, Collation, TargetedMessage, OutgoingMessages, UpwardMessage, FeeSchedule, ErasureChunk,
	HeadData, PoVBlock,
28
}};
29
use polkadot_erasure_coding::{self as erasure};
30
use runtime_primitives::traits::ProvideRuntimeApi;
31
use parachain::{wasm_executor::{self, ExternalitiesError, ExecutionMode}, MessageRef, UpwardMessageRef};
32
use trie::TrieConfiguration;
33
use futures::prelude::*;
34
use log::debug;
35
36
37
38
39
40

/// Encapsulates connections to collators and allows collation on any parachain.
///
/// This is expected to be a lightweight, shared type like an `Arc`.
pub trait Collators: Clone {
	/// Errors when producing collations.
41
	type Error: std::fmt::Debug;
42
	/// A full collation.
43
	type Collation: Future<Output=Result<Collation, Self::Error>>;
44
45

	/// Collate on a specific parachain, building on a given relay chain parent hash.
46
47
48
49
50
51
	///
	/// The returned collation should be checked for basic validity in the signature
	/// and will be checked for state-transition validity by the consumer of this trait.
	///
	/// This does not have to guarantee local availability, as a valid collation
	/// will be passed to the `TableRouter` instance.
52
53
	fn collate(&self, parachain: ParaId, relay_parent: Hash) -> Self::Collation;

54
	/// Note a bad collator. TODO: take proof (https://github.com/paritytech/polkadot/issues/217)
Gav Wood's avatar
Gav Wood committed
55
	fn note_bad_collator(&self, collator: CollatorId);
56
57
58
}

/// A future which resolves when a collation is available.
59
pub async fn collation_fetch<C: Collators, P>(
60
	parachain: ParaId,
61
62
63
	relay_parent_hash: Hash,
	collators: C,
	client: Arc<P>,
64
	max_block_data_size: Option<u64>,
65
) -> Result<(Collation, OutgoingMessages, Balance),C::Error>
66
67
68
69
70
	where
		P::Api: ParachainHost<Block, Error = sp_blockchain::Error>,
		C: Collators + Unpin,
		P: ProvideRuntimeApi,
		<C as Collators>::Collation: Unpin,
71
{
72
	let relay_parent = BlockId::hash(relay_parent_hash);
73

74
75
76
	loop {
		let collation = collators.collate(parachain, relay_parent_hash)
			.await?;
77

78
79
80
81
82
83
		let res = validate_collation(
			&*client,
			&relay_parent,
			&collation,
			max_block_data_size,
		);
84

85
86
87
88
89
90
		match res {
			Ok((messages, fees)) => {
				return Ok((collation, messages, fees))
			}
			Err(e) => {
				debug!("Failed to validate parachain due to API error: {}", e);
91

92
93
				// just continue if we got a bad collation or failed to validate
				collators.note_bad_collator(collation.info.collator)
94
95
96
97
98
99
			}
		}
	}
}

// Errors that can occur when validating a parachain.
100
101
102
#[derive(Debug, derive_more::Display, derive_more::From)]
pub enum Error {
	/// Client error
Gavin Wood's avatar
Gavin Wood committed
103
	Client(sp_blockchain::Error),
104
105
	/// Wasm validation error
	WasmValidation(wasm_executor::Error),
106
107
	/// Erasure-encoding error.
	Erasure(erasure::Error),
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
	/// Collated for inactive parachain
	#[display(fmt = "Collated for inactive parachain: {:?}", _0)]
	InactiveParachain(ParaId),
	/// Unexpected egress root
	#[display(fmt = "Got unexpected egress root to {:?}. (expected: {:?}, got {:?})", id, expected, got)]
	EgressRootMismatch { id: ParaId, expected: Hash, got: Hash },
	/// Unexpected ingress root
	#[display(fmt = "Got unexpected ingress root to {:?}. (expected: {:?}, got {:?})", id, expected, got)]
	IngressRootMismatch { id: ParaId, expected: Hash, got: Hash },
	/// Ingress from wrong chain
	#[display(fmt = "Got ingress from wrong chain. (expected: {:?}, got {:?})", expected, got)]
	IngressChainMismatch { expected: ParaId, got: ParaId },
	/// Ingress canonicality mismatch
	#[display(fmt = "Got data for {} roots, expected {}", expected, got)]
	IngressCanonicalityMismatch { expected: usize, got: usize },
	/// Missing or extra egress root
	#[display(fmt = "Missing or extra egress root. (expected: {:?}, got {:?})", expected, got)]
	MissingEgressRoot { expected: Option<ParaId>, got: Option<ParaId>, },
	/// Parachain validation produced wrong head data
	#[display(fmt = "Parachain validation produced wrong head data (expected: {:?}, got {:?})", expected, got)]
	WrongHeadData { expected: Vec<u8>, got: Vec<u8> },
	/// Block data is too big
	#[display(fmt = "Block data is too big (maximum allowed size: {}, actual size: {})", size, max_size)]
	BlockDataTooBig { size: u64, max_size: u64 },
	/// Parachain validation produced wrong relay-chain messages
	#[display(fmt = "Parachain validation produced wrong relay-chain messages (expected: {:?}, got {:?})", expected, got)]
	UpwardMessagesInvalid { expected: Vec<UpwardMessage>, got: Vec<UpwardMessage> },
135
136
137
	/// Parachain validation produced wrong fees to charge to parachain.
	#[display(fmt = "Parachain validation produced wrong relay-chain fees (expected: {:?}, got {:?})", expected, got)]
	FeesChargedInvalid { expected: Balance, got: Balance },
138
139
140
141
142
143
144
	/// Candidate block has an erasure-encoded root that mismatches the actual
	/// erasure-encoded root of block data and extrinsics.
	#[display(fmt = "Got unexpected erasure root (expected: {:?}, got {:?})", expected, got)]
	ErasureRootMismatch { expected: Hash, got: Hash },
	/// Candidate block collation info doesn't match candidate receipt.
	#[display(fmt = "Got receipt mismatch for candidate {:?}", candidate)]
	CandidateReceiptMismatch { candidate: Hash },
145
}
146

147
148
149
150
151
152
impl std::error::Error for Error {
	fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
		match self {
			Error::Client(ref err) => Some(err),
			Error::WasmValidation(ref err) => Some(err),
			_ => None,
153
		}
154
	}
155
}
156

157
/// Compute a trie root for a set of messages, given the raw message data.
158
pub fn message_queue_root<A, I: IntoIterator<Item=A>>(messages: I) -> Hash
159
160
	where A: AsRef<[u8]>
{
161
	trie::trie_types::Layout::<primitives::Blake2Hasher>::ordered_trie_root(messages)
162
163
}

164
/// Compute the set of egress roots for all given outgoing messages.
165
pub fn egress_roots(outgoing: &mut [TargetedMessage]) -> Vec<(ParaId, Hash)> {
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
	// stable sort messages by parachain ID.
	outgoing.sort_by_key(|msg| ParaId::from(msg.target));

	let mut egress_roots = Vec::new();
	{
		let mut messages_iter = outgoing.iter().peekable();
		while let Some(batch_target) = messages_iter.peek().map(|o| o.target) {
 			// we borrow the iterator mutably to ensure it advances so the
			// next iteration of the loop starts with `messages_iter` pointing to
			// the next batch.
			let messages_to = messages_iter
				.clone()
				.take_while(|o| o.target == batch_target)
				.map(|o| { let _ = messages_iter.next(); &o.data[..] });

			let computed_root = message_queue_root(messages_to);
			egress_roots.push((batch_target, computed_root));
		}
	}

	egress_roots
}

189
190
fn check_egress(
	mut outgoing: Vec<TargetedMessage>,
191
	expected_egress_roots: &[(ParaId, Hash)],
192
) -> Result<OutgoingMessages, Error> {
193
194
195
196
197
198
199
200
	// stable sort messages by parachain ID.
	outgoing.sort_by_key(|msg| ParaId::from(msg.target));

	{
		let mut messages_iter = outgoing.iter().peekable();
		let mut expected_egress_roots = expected_egress_roots.iter();
		while let Some(batch_target) = messages_iter.peek().map(|o| o.target) {
			let expected_root = match expected_egress_roots.next() {
201
202
203
204
				None => return Err(Error::MissingEgressRoot {
					expected: Some(batch_target),
					got: None
				}),
205
206
207
				Some(&(id, ref root)) => if id == batch_target {
					root
				} else {
208
209
210
211
					return Err(Error::MissingEgressRoot{
						expected: Some(batch_target),
						got: Some(id)
					});
212
213
214
215
216
217
218
219
220
221
222
				}
			};

 			// we borrow the iterator mutably to ensure it advances so the
			// next iteration of the loop starts with `messages_iter` pointing to
			// the next batch.
			let messages_to = messages_iter
				.clone()
				.take_while(|o| o.target == batch_target)
				.map(|o| { let _ = messages_iter.next(); &o.data[..] });

223
			let computed_root = message_queue_root(messages_to);
224
			if &computed_root != expected_root {
225
226
227
228
229
				return Err(Error::EgressRootMismatch {
					id: batch_target,
					expected: expected_root.clone(),
					got: computed_root,
				});
230
231
232
233
234
			}
		}

		// also check that there are no more additional expected roots.
		if let Some((next_target, _)) = expected_egress_roots.next() {
235
			return Err(Error::MissingEgressRoot { expected: None, got: Some(*next_target) });
236
237
238
		}
	}

239
	Ok(OutgoingMessages { outgoing_messages: outgoing })
240
241
242
243
}

struct Externalities {
	parachain_index: ParaId,
244
	outgoing: Vec<TargetedMessage>,
245
	upward: Vec<UpwardMessage>,
246
247
248
	fees_charged: Balance,
	free_balance: Balance,
	fee_schedule: FeeSchedule,
249
250
251
252
253
254
255
256
257
}

impl wasm_executor::Externalities for Externalities {
	fn post_message(&mut self, message: MessageRef) -> Result<(), ExternalitiesError> {
		let target: ParaId = message.target.into();
		if target == self.parachain_index {
			return Err(ExternalitiesError::CannotPostMessage("posted message to self"));
		}

258
		self.apply_message_fee(message.data.len())?;
259
		self.outgoing.push(TargetedMessage {
260
261
262
263
264
265
			target,
			data: message.data.to_vec(),
		});

		Ok(())
	}
266
267
268
269

	fn post_upward_message(&mut self, message: UpwardMessageRef)
		-> Result<(), ExternalitiesError>
	{
270
271
		self.apply_message_fee(message.data.len())?;

272
273
274
275
276
277
		self.upward.push(UpwardMessage {
			origin: message.origin,
			data: message.data.to_vec(),
		});
		Ok(())
	}
278
279
280
}

impl Externalities {
281
282
283
284
285
286
287
288
289
290
291
	fn apply_message_fee(&mut self, message_len: usize) -> Result<(), ExternalitiesError> {
		let fee = self.fee_schedule.compute_fee(message_len);
		let new_fees_charged = self.fees_charged.saturating_add(fee);
		if new_fees_charged > self.free_balance {
			Err(ExternalitiesError::CannotPostMessage("could not cover fee."))
		} else {
			self.fees_charged = new_fees_charged;
			Ok(())
		}
	}

292
	// Performs final checks of validity, producing the outgoing message data.
293
294
	fn final_checks(
		self,
295
296
297
298
299
		upward_messages: &[UpwardMessage],
		egress_queue_roots: &[(ParaId, Hash)],
		fees_charged: Option<Balance>,
	) -> Result<(OutgoingMessages, Balance), Error> {
		if self.upward != upward_messages {
300
			return Err(Error::UpwardMessagesInvalid {
301
				expected: upward_messages.to_vec(),
302
303
				got: self.upward.clone(),
			});
304
305
		}

306
307
308
309
310
311
312
		if let Some(fees_charged) = fees_charged {
			if self.fees_charged != fees_charged {
				return Err(Error::FeesChargedInvalid {
					expected: fees_charged.clone(),
					got: self.fees_charged.clone(),
				});
			}
313
314
		}

315
		let messages = check_egress(
316
			self.outgoing,
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
			&egress_queue_roots[..],
		)?;

		Ok((messages, self.fees_charged))
	}
}

/// Validate an erasure chunk against an expected root.
pub fn validate_chunk(
	root: &Hash,
	chunk: &ErasureChunk,
) -> Result<(), Error> {
	let expected = erasure::branch_hash(root, &chunk.proof, chunk.index as usize)?;
	let got = BlakeTwo256::hash(&chunk.chunk);

	if expected != got {
		return Err(Error::ErasureRootMismatch {
			expected,
			got,
		})
337
	}
338
339

	Ok(())
340
341
}

342
343
/// Validate incoming messages against expected roots.
pub fn validate_incoming(
344
	roots: &StructuredUnroutedIngress,
345
346
	ingress: &ConsolidatedIngress,
) -> Result<(), Error> {
347
	if roots.len() != ingress.0.len() {
348
349
350
351
		return Err(Error::IngressCanonicalityMismatch {
			expected: roots.0.len(),
			got: ingress.0.len()
		});
352
353
	}

354
355
356
	let all_iter = roots.iter().zip(&ingress.0);
	for ((_, expected_from, root), (got_id, messages)) in all_iter {
		if expected_from != got_id {
357
			return Err(Error::IngressChainMismatch {
358
				expected: *expected_from,
359
360
				got: *got_id
			});
361
362
363
364
		}

		let got_root = message_queue_root(messages.iter().map(|msg| &msg.0[..]));
		if &got_root != root {
365
			return Err(Error::IngressRootMismatch{
366
				id: *expected_from,
367
368
369
				expected: *root,
				got: got_root
			});
370
371
372
373
374
375
		}
	}

	Ok(())
}

376
377
378
379
380
// A utility function that implements most of the collation validation logic.
//
// Reused by `validate_collation` and `validate_receipt`.
// Returns outgoing messages and fees charged for later reuse.
fn do_validation<P>(
381
382
	client: &P,
	relay_parent: &BlockId,
383
384
	pov_block: &PoVBlock,
	para_id: ParaId,
385
	max_block_data_size: Option<u64>,
386
387
388
389
390
	fees_charged: Option<Balance>,
	head_data: &HeadData,
	queue_roots: &Vec<(ParaId, Hash)>,
	upward_messages: &Vec<UpwardMessage>,
) -> Result<(OutgoingMessages, Balance), Error> where
391
	P: ProvideRuntimeApi,
Gavin Wood's avatar
Gavin Wood committed
392
	P::Api: ParachainHost<Block, Error = sp_blockchain::Error>,
393
{
394
	use parachain::{IncomingMessage, ValidationParams};
395

396
	if let Some(max_size) = max_block_data_size {
397
		let block_data_size = pov_block.block_data.0.len() as u64;
398
		if block_data_size > max_size {
399
			return Err(Error::BlockDataTooBig { size: block_data_size, max_size });
400
401
402
		}
	}

403
	let api = client.runtime_api();
Gav Wood's avatar
Gav Wood committed
404
	let validation_code = api.parachain_code(relay_parent, para_id)?
405
		.ok_or_else(|| Error::InactiveParachain(para_id))?;
406

407
	let chain_status = api.parachain_status(relay_parent, para_id)?
408
		.ok_or_else(|| Error::InactiveParachain(para_id))?;
409

410
	let roots = api.ingress(relay_parent, para_id, None)?
411
		.ok_or_else(|| Error::InactiveParachain(para_id))?;
412

413
	validate_incoming(&roots, &pov_block.ingress)?;
414

415
	let params = ValidationParams {
416
		parent_head: chain_status.head_data.0,
417
418
		block_data: pov_block.block_data.0.clone(),
		ingress: pov_block.ingress.0.iter()
419
			.flat_map(|&(source, ref messages)| {
420
421
422
423
424
425
				messages.iter().map(move |msg| IncomingMessage {
					source,
					data: msg.0.clone(),
				})
			})
			.collect()
426
427
	};

428
	let mut ext = Externalities {
429
		parachain_index: para_id.clone(),
430
		outgoing: Vec::new(),
431
		upward: Vec::new(),
432
433
434
		free_balance: chain_status.balance,
		fee_schedule: chain_status.fee_schedule,
		fees_charged: 0,
435
436
	};

437
	match wasm_executor::validate_candidate(&validation_code, params, &mut ext, ExecutionMode::Remote) {
438
		Ok(result) => {
439
440
441
442
443
444
445
446
			if result.head_data == head_data.0 {
				let (messages, fees) = ext.final_checks(
					upward_messages,
					queue_roots,
					fees_charged
				)?;

				Ok((messages, fees))
447
			} else {
448
				Err(Error::WrongHeadData {
449
					expected: head_data.0.clone(),
450
451
					got: result.head_data
				})
452
453
			}
		}
454
455
456
457
		Err(e) => Err(e.into())
	}
}

458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
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
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
/// Produce a `CandidateReceipt` and erasure encoding chunks with a given collation.
///
/// To produce a `CandidateReceipt` among other things the root of erasure encoding of
/// the block data and messages needs to be known. To avoid redundant re-computations
/// of erasure encoding this method creates an encoding and produces a candidate with
/// encoding's root returning both for re-use.
pub fn produce_receipt_and_chunks(
	n_validators: usize,
	pov: &PoVBlock,
	messages: &OutgoingMessages,
	fees: Balance,
	info: &CollationInfo,
) -> Result<(CandidateReceipt, Vec<ErasureChunk>), Error>
{
	let erasure_chunks = erasure::obtain_chunks(
		n_validators,
		&pov.block_data,
		Some(&messages.clone().into())
	)?;

	let branches = erasure::branches(erasure_chunks.as_ref());
	let erasure_root = branches.root();

	let chunks: Vec<_> = erasure_chunks
			.iter()
			.zip(branches.map(|(proof, _)| proof))
			.enumerate()
			.map(|(index, (chunk, proof))| ErasureChunk {
				// branches borrows the original chunks, but this clone could probably be dodged.
				chunk: chunk.clone(),
				index: index as u32,
				proof,
			})
			.collect();

	let receipt = CandidateReceipt {
		parachain_index: info.parachain_index,
		collator: info.collator.clone(),
		signature: info.signature.clone(),
		head_data: info.head_data.clone(),
		egress_queue_roots: info.egress_queue_roots.clone(),
		fees,
		block_data_hash: info.block_data_hash.clone(),
		upward_messages: info.upward_messages.clone(),
		erasure_root,
	};

	Ok((receipt, chunks))
}

/// Check if a given candidate receipt is valid with a given collation.
///
/// This assumes that basic validity checks have been done:
///   - Block data hash is the same as linked in collation info and a receipt.
pub fn validate_receipt<P>(
	client: &P,
	relay_parent: &BlockId,
	pov_block: &PoVBlock,
	receipt: &CandidateReceipt,
	max_block_data_size: Option<u64>,
) -> Result<(OutgoingMessages, Vec<ErasureChunk>), Error> where
	P: ProvideRuntimeApi,
	P::Api: ParachainHost<Block, Error = sp_blockchain::Error>,
{
	let (messages, _fees) = do_validation(
		client,
		relay_parent,
		pov_block,
		receipt.parachain_index,
		max_block_data_size,
		Some(receipt.fees),
		&receipt.head_data,
		&receipt.egress_queue_roots,
		&receipt.upward_messages,
	)?;

	let api = client.runtime_api();
	let validators = api.validators(&relay_parent)?;
	let n_validators = validators.len();

	let (validated_receipt, chunks) = produce_receipt_and_chunks(
		n_validators,
		pov_block,
		&messages,
		receipt.fees,
		&receipt.clone().into(),
	)?;

	if validated_receipt.erasure_root != receipt.erasure_root {
		return Err(Error::ErasureRootMismatch {
			expected: validated_receipt.erasure_root,
			got: receipt.erasure_root,
		});
	}

	Ok((messages, chunks))
}

/// Check whether a given collation is valid. Returns `Ok` on success, error otherwise.
///
/// This assumes that basic validity checks have been done:
///   - Block data hash is the same as linked in collation info.
pub fn validate_collation<P>(
	client: &P,
	relay_parent: &BlockId,
	collation: &Collation,
	max_block_data_size: Option<u64>,
) -> Result<(OutgoingMessages, Balance), Error> where
	P: ProvideRuntimeApi,
	P::Api: ParachainHost<Block, Error = sp_blockchain::Error>,
{
	let para_id = collation.info.parachain_index;

	do_validation(
		client,
		relay_parent,
		&collation.pov,
		para_id,
		max_block_data_size,
		None,
		&collation.info.head_data,
		&collation.info.egress_queue_roots,
		&collation.info.upward_messages,
	)
}

584
585
586
587
#[cfg(test)]
mod tests {
	use super::*;
	use parachain::wasm_executor::Externalities as ExternalitiesTrait;
588
	use parachain::ParachainDispatchOrigin;
589
	use polkadot_primitives::parachain::{CandidateReceipt, HeadData};
590
591

	#[test]
592
	fn compute_and_check_egress() {
593
		let messages = vec![
594
595
596
597
			TargetedMessage { target: 3.into(), data: vec![1, 1, 1] },
			TargetedMessage { target: 1.into(), data: vec![1, 2, 3] },
			TargetedMessage { target: 2.into(), data: vec![4, 5, 6] },
			TargetedMessage { target: 1.into(), data: vec![7, 8, 9] },
598
599
		];

600
601
602
		let root_1 = message_queue_root(&[vec![1, 2, 3], vec![7, 8, 9]]);
		let root_2 = message_queue_root(&[vec![4, 5, 6]]);
		let root_3 = message_queue_root(&[vec![1, 1, 1]]);
603

604
		assert!(check_egress(
605
606
607
608
			messages.clone(),
			&[(1.into(), root_1), (2.into(), root_2), (3.into(), root_3)],
		).is_ok());

609
		let egress_roots = egress_roots(&mut messages.clone()[..]);
610

611
		assert!(check_egress(
612
613
614
615
			messages.clone(),
			&egress_roots[..],
		).is_ok());

616
		// missing root.
617
		assert!(check_egress(
618
619
620
621
622
			messages.clone(),
			&[(1.into(), root_1), (3.into(), root_3)],
		).is_err());

		// extra root.
623
		assert!(check_egress(
624
625
626
627
628
			messages.clone(),
			&[(1.into(), root_1), (2.into(), root_2), (3.into(), root_3), (4.into(), Default::default())],
		).is_err());

		// root mismatch.
629
		assert!(check_egress(
630
631
632
633
634
635
636
637
638
639
			messages.clone(),
			&[(1.into(), root_2), (2.into(), root_1), (3.into(), root_3)],
		).is_err());
	}

	#[test]
	fn ext_rejects_local_message() {
		let mut ext = Externalities {
			parachain_index: 5.into(),
			outgoing: Vec::new(),
640
			upward: Vec::new(),
641
642
643
644
645
646
			fees_charged: 0,
			free_balance: 1_000_000,
			fee_schedule: FeeSchedule {
				base: 1000,
				per_byte: 10,
			},
647
648
		};

649
650
		assert!(ext.post_message(MessageRef { target: 1.into(), data: &[] }).is_ok());
		assert!(ext.post_message(MessageRef { target: 5.into(), data: &[] }).is_err());
651
	}
652
653
654
655
656
657
658
659
660

	#[test]
	fn ext_checks_upward_messages() {
		let ext = || Externalities {
			parachain_index: 5.into(),
			outgoing: Vec::new(),
			upward: vec![
				UpwardMessage{ data: vec![42], origin: ParachainDispatchOrigin::Parachain },
			],
661
662
663
664
665
666
			fees_charged: 0,
			free_balance: 1_000_000,
			fee_schedule: FeeSchedule {
				base: 1000,
				per_byte: 10,
			},
667
668
669
670
671
672
673
674
675
676
677
678
679
		};
		let receipt = CandidateReceipt {
			parachain_index: 5.into(),
			collator: Default::default(),
			signature: Default::default(),
			head_data: HeadData(Vec::new()),
			egress_queue_roots: Vec::new(),
			fees: 0,
			block_data_hash: Default::default(),
			upward_messages: vec![
				UpwardMessage{ data: vec![42], origin: ParachainDispatchOrigin::Signed },
				UpwardMessage{ data: vec![69], origin: ParachainDispatchOrigin::Parachain },
			],
680
			erasure_root: [1u8; 32].into(),
681
		};
682
683
684
685
686
		assert!(ext().final_checks(
			&receipt.upward_messages,
			&receipt.egress_queue_roots,
			Some(receipt.fees),
		).is_err());
687
688
689
690
691
692
693
694
695
696
697
		let receipt = CandidateReceipt {
			parachain_index: 5.into(),
			collator: Default::default(),
			signature: Default::default(),
			head_data: HeadData(Vec::new()),
			egress_queue_roots: Vec::new(),
			fees: 0,
			block_data_hash: Default::default(),
			upward_messages: vec![
				UpwardMessage{ data: vec![42], origin: ParachainDispatchOrigin::Signed },
			],
698
			erasure_root: [1u8; 32].into(),
699
		};
700
701
702
703
704
		assert!(ext().final_checks(
			&receipt.upward_messages,
			&receipt.egress_queue_roots,
			Some(receipt.fees),
		).is_err());
705
706
707
708
709
710
711
712
713
714
715
		let receipt = CandidateReceipt {
			parachain_index: 5.into(),
			collator: Default::default(),
			signature: Default::default(),
			head_data: HeadData(Vec::new()),
			egress_queue_roots: Vec::new(),
			fees: 0,
			block_data_hash: Default::default(),
			upward_messages: vec![
				UpwardMessage{ data: vec![69], origin: ParachainDispatchOrigin::Parachain },
			],
716
			erasure_root: [1u8; 32].into(),
717
		};
718
719
720
721
722
		assert!(ext().final_checks(
			&receipt.upward_messages,
			&receipt.egress_queue_roots,
			Some(receipt.fees),
		).is_err());
723
724
725
726
727
728
729
730
731
732
733
		let receipt = CandidateReceipt {
			parachain_index: 5.into(),
			collator: Default::default(),
			signature: Default::default(),
			head_data: HeadData(Vec::new()),
			egress_queue_roots: Vec::new(),
			fees: 0,
			block_data_hash: Default::default(),
			upward_messages: vec![
				UpwardMessage{ data: vec![42], origin: ParachainDispatchOrigin::Parachain },
			],
734
			erasure_root: [1u8; 32].into(),
735
		};
736
737
738
739
740
		assert!(ext().final_checks(
			&receipt.upward_messages,
			&receipt.egress_queue_roots,
			Some(receipt.fees),
		).is_ok());
741
	}
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780

	#[test]
	fn ext_checks_fees_and_updates_correctly() {
		let mut ext = Externalities {
			parachain_index: 5.into(),
			outgoing: Vec::new(),
			upward: vec![
				UpwardMessage{ data: vec![42], origin: ParachainDispatchOrigin::Parachain },
			],
			fees_charged: 0,
			free_balance: 1_000_000,
			fee_schedule: FeeSchedule {
				base: 1000,
				per_byte: 10,
			},
		};

		ext.apply_message_fee(100).unwrap();
		assert_eq!(ext.fees_charged, 2000);

		ext.post_message(MessageRef {
			target: 1.into(),
			data: &[0u8; 100],
		}).unwrap();
		assert_eq!(ext.fees_charged, 4000);

		ext.post_upward_message(UpwardMessageRef {
			origin: ParachainDispatchOrigin::Signed,
			data: &[0u8; 100],
		}).unwrap();
		assert_eq!(ext.fees_charged, 6000);


		ext.apply_message_fee((1_000_000 - 6000 - 1000) / 10).unwrap();
		assert_eq!(ext.fees_charged, 1_000_000);

		// cannot pay fee.
		assert!(ext.apply_message_fee(1).is_err());
	}
781
}