generic.rs 27.5 KB
Newer Older
Shawn Tabrizi's avatar
Shawn Tabrizi committed
1
// Copyright 2017-2020 Parity Technologies (UK) Ltd.
Gav's avatar
Gav committed
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 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/>.

17
//! The statement table: generic implementation.
Gav's avatar
Gav committed
18
19
20
21
22
//!
//! This stores messages other authorities issue about candidates.
//!
//! These messages are used to create a proposal submitted to a BFT consensus process.
//!
23
24
25
//! Each parachain is associated with a committee of authorities, who issue statements
//! indicating whether the candidate is valid or invalid. Once a threshold of the committee
//! has signed validity statements, the candidate may be marked includable.
Gav's avatar
Gav committed
26

27
use std::collections::hash_map::{self, Entry, HashMap};
Gav's avatar
Gav committed
28
29
30
use std::hash::Hash;
use std::fmt::Debug;

asynchronous rob's avatar
asynchronous rob committed
31
use primitives::v1::{ValidityAttestation as PrimitiveValidityAttestation, ValidatorSignature};
32

33
use parity_scale_codec::{Encode, Decode};
34

Gav's avatar
Gav committed
35
36
/// Context for the statement table.
pub trait Context {
37
	/// An authority ID
Gav's avatar
Gav committed
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
	type AuthorityId: Debug + Hash + Eq + Clone;
	/// The digest (hash or other unique attribute) of a candidate.
	type Digest: Debug + Hash + Eq + Clone;
	/// The group ID type
	type GroupId: Debug + Hash + Ord + Eq + Clone;
	/// A signature type.
	type Signature: Debug + Eq + Clone;
	/// Candidate type. In practice this will be a candidate receipt.
	type Candidate: Debug + Ord + Eq + Clone;

	/// get the digest of a candidate.
	fn candidate_digest(candidate: &Self::Candidate) -> Self::Digest;

	/// get the group of a candidate.
	fn candidate_group(candidate: &Self::Candidate) -> Self::GroupId;

	/// Whether a authority is a member of a group.
	/// Members are meant to submit candidates and vote on validity.
	fn is_member_of(&self, authority: &Self::AuthorityId, group: &Self::GroupId) -> bool;

58
	/// requisite number of votes for validity from a group.
59
	fn requisite_votes(&self, group: &Self::GroupId) -> usize;
Gav's avatar
Gav committed
60
61
62
}

/// Statements circulated among peers.
63
#[derive(PartialEq, Eq, Debug, Clone, Encode, Decode)]
64
65
pub enum Statement<Candidate, Digest> {
	/// Broadcast by an authority to indicate that this is its candidate for inclusion.
Gav's avatar
Gav committed
66
67
	///
	/// Broadcasting two different candidate messages per round is not allowed.
68
	#[codec(index = 1)]
69
	Seconded(Candidate),
70
	/// Broadcast by a authority to attest that the candidate with given digest is valid.
71
	#[codec(index = 2)]
72
	Valid(Digest),
73
74
}

Gav's avatar
Gav committed
75
/// A signed statement.
76
#[derive(PartialEq, Eq, Debug, Clone, Encode, Decode)]
77
pub struct SignedStatement<Candidate, Digest, AuthorityId, Signature> {
Gav's avatar
Gav committed
78
	/// The statement.
79
	pub statement: Statement<Candidate, Digest>,
Gav's avatar
Gav committed
80
	/// The signature.
81
	pub signature: Signature,
Gav's avatar
Gav committed
82
	/// The sender.
83
	pub sender: AuthorityId,
Gav's avatar
Gav committed
84
85
86
87
88
89
90
}

/// Misbehavior: voting more than one way on candidate validity.
///
/// Since there are three possible ways to vote, a double vote is possible in
/// three possible combinations (unordered)
#[derive(PartialEq, Eq, Debug, Clone)]
91
pub enum ValidityDoubleVote<Candidate, Digest, Signature> {
Black3HDF's avatar
Black3HDF committed
92
	/// Implicit vote by issuing and explicitly voting validity.
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
	IssuedAndValidity((Candidate, Signature), (Digest, Signature)),
}

impl<Candidate, Digest, Signature> ValidityDoubleVote<Candidate, Digest, Signature> {
	/// Deconstruct this misbehavior into two `(Statement, Signature)` pairs, erasing the information
	/// about precisely what the problem was.
	pub fn deconstruct<Ctx>(self) -> (
		(Statement<Candidate, Digest>, Signature),
		(Statement<Candidate, Digest>, Signature),
	)
	where
		Ctx: Context<Candidate=Candidate, Digest=Digest, Signature=Signature>,
		Candidate: Debug + Ord + Eq + Clone,
		Digest: Debug + Hash + Eq + Clone,
		Signature: Debug + Eq + Clone,
	{
		match self {
			Self::IssuedAndValidity((c, s1), (d, s2)) => {
111
				((Statement::Seconded(c), s1), (Statement::Valid(d), s2))
112
113
114
			}
		}
	}
Gav's avatar
Gav committed
115
116
}

117
118
/// Misbehavior: multiple signatures on same statement.
#[derive(PartialEq, Eq, Debug, Clone)]
119
pub enum DoubleSign<Candidate, Digest, Signature> {
120
	/// On candidate.
121
	Seconded(Candidate, Signature, Signature),
122
	/// On validity.
123
124
125
126
127
128
129
130
	Validity(Digest, Signature, Signature),
}

impl<Candidate, Digest, Signature> DoubleSign<Candidate, Digest, Signature> {
	/// Deconstruct this misbehavior into a statement with two signatures, erasing the information about
	/// precisely where in the process the issue was detected.
	pub fn deconstruct(self) -> (Statement<Candidate, Digest>, Signature, Signature) {
		match self {
131
			Self::Seconded(candidate, a, b) => (Statement::Seconded(candidate), a, b),
132
133
134
			Self::Validity(digest, a, b) => (Statement::Valid(digest), a, b),
		}
	}
135
136
}

Gav's avatar
Gav committed
137
138
/// Misbehavior: declaring multiple candidates.
#[derive(PartialEq, Eq, Debug, Clone)]
139
pub struct MultipleCandidates<Candidate, Signature> {
Gav's avatar
Gav committed
140
	/// The first candidate seen.
141
	pub first: (Candidate, Signature),
Gav's avatar
Gav committed
142
	/// The second candidate seen.
143
	pub second: (Candidate, Signature),
Gav's avatar
Gav committed
144
145
146
147
}

/// Misbehavior: submitted statement for wrong group.
#[derive(PartialEq, Eq, Debug, Clone)]
148
pub struct UnauthorizedStatement<Candidate, Digest, AuthorityId, Signature> {
Gav's avatar
Gav committed
149
	/// A signed statement which was submitted without proper authority.
150
	pub statement: SignedStatement<Candidate, Digest, AuthorityId, Signature>,
Gav's avatar
Gav committed
151
152
153
154
155
}

/// Different kinds of misbehavior. All of these kinds of malicious misbehavior
/// are easily provable and extremely disincentivized.
#[derive(PartialEq, Eq, Debug, Clone)]
156
pub enum Misbehavior<Candidate, Digest, AuthorityId, Signature> {
Gav's avatar
Gav committed
157
	/// Voted invalid and valid on validity.
158
	ValidityDoubleVote(ValidityDoubleVote<Candidate, Digest, Signature>),
Gav's avatar
Gav committed
159
	/// Submitted multiple candidates.
160
	MultipleCandidates(MultipleCandidates<Candidate, Signature>),
161
	/// Submitted a message that was unauthorized.
162
	UnauthorizedStatement(UnauthorizedStatement<Candidate, Digest, AuthorityId, Signature>),
163
	/// Submitted two valid signatures for the same message.
164
	DoubleSign(DoubleSign<Candidate, Digest, Signature>),
Gav's avatar
Gav committed
165
166
}

167
/// Type alias for misbehavior corresponding to context type.
168
169
170
171
172
173
pub type MisbehaviorFor<Ctx> = Misbehavior<
	<Ctx as Context>::Candidate,
	<Ctx as Context>::Digest,
	<Ctx as Context>::AuthorityId,
	<Ctx as Context>::Signature,
>;
Gav's avatar
Gav committed
174
175
176

// kinds of votes for validity
#[derive(Clone, PartialEq, Eq)]
177
enum ValidityVote<Signature: Eq + Clone> {
Gav's avatar
Gav committed
178
	// implicit validity vote by issuing
179
	Issued(Signature),
Gav's avatar
Gav committed
180
	// direct validity vote
181
	Valid(Signature),
Gav's avatar
Gav committed
182
183
184
}

/// A summary of import of a statement.
185
#[derive(Clone, PartialEq, Eq, Debug)]
186
pub struct Summary<Digest, Group> {
Gav's avatar
Gav committed
187
	/// The digest of the candidate referenced.
188
	pub candidate: Digest,
189
	/// The group that the candidate is in.
190
	pub group_id: Group,
Gav's avatar
Gav committed
191
192
193
194
	/// How many validity votes are currently witnessed.
	pub validity_votes: usize,
}

195
196
/// A validity attestation.
#[derive(Clone, PartialEq, Decode, Encode)]
197
pub enum ValidityAttestation<Signature> {
198
199
	/// implicit validity attestation by issuing.
	/// This corresponds to issuance of a `Candidate` statement.
200
	Implicit(Signature),
201
202
	/// An explicit attestation. This corresponds to issuance of a
	/// `Valid` statement.
203
	Explicit(Signature),
204
205
}

206
207
208
209
210
211
212
213
214
impl Into<PrimitiveValidityAttestation> for ValidityAttestation<ValidatorSignature> {
	fn into(self) -> PrimitiveValidityAttestation {
		match self {
			Self::Implicit(s) => PrimitiveValidityAttestation::Implicit(s),
			Self::Explicit(s) => PrimitiveValidityAttestation::Explicit(s),
		}
	}
}

215
216
217
218
219
220
221
222
223
224
225
/// An attested-to candidate.
#[derive(Clone, PartialEq, Decode, Encode)]
pub struct AttestedCandidate<Group, Candidate, AuthorityId, Signature> {
	/// The group ID that the candidate is in.
	pub group_id: Group,
	/// The candidate data.
	pub candidate: Candidate,
	/// Validity attestations.
	pub validity_votes: Vec<(AuthorityId, ValidityAttestation<Signature>)>,
}

Gav's avatar
Gav committed
226
/// Stores votes and data about a candidate.
227
228
229
230
pub struct CandidateData<Ctx: Context> {
	group_id: Ctx::GroupId,
	candidate: Ctx::Candidate,
	validity_votes: HashMap<Ctx::AuthorityId, ValidityVote<Ctx::Signature>>,
Gav's avatar
Gav committed
231
232
}

233
impl<Ctx: Context> CandidateData<Ctx> {
234
235
	/// Yield a full attestation for a candidate.
	/// If the candidate can be included, it will return `Some`.
236
	pub fn attested(&self, validity_threshold: usize)
237
		-> Option<AttestedCandidate<
238
			Ctx::GroupId, Ctx::Candidate, Ctx::AuthorityId, Ctx::Signature,
239
240
		>>
	{
241
		let valid_votes = self.validity_votes.len();
242
243
		if valid_votes < validity_threshold {
			return None;
244
245
		}

246
		let validity_votes = self.validity_votes.iter()
247
			.map(|(a, v)| match *v {
248
				ValidityVote::Valid(ref s) =>
249
					(a.clone(), ValidityAttestation::Explicit(s.clone())),
250
				ValidityVote::Issued(ref s) =>
251
					(a.clone(), ValidityAttestation::Implicit(s.clone())),
252
253
254
255
256
257
258
259
			})
			.collect();

		Some(AttestedCandidate {
			group_id: self.group_id.clone(),
			candidate: self.candidate.clone(),
			validity_votes,
		})
Gav's avatar
Gav committed
260
261
	}

262
	fn summary(&self, digest: Ctx::Digest) -> Summary<Ctx::Digest, Ctx::GroupId> {
Gav's avatar
Gav committed
263
264
265
		Summary {
			candidate: digest,
			group_id: self.group_id.clone(),
asynchronous rob's avatar
asynchronous rob committed
266
			validity_votes: self.validity_votes.len(),
Gav's avatar
Gav committed
267
268
269
270
271
		}
	}
}

// authority metadata
272
273
struct AuthorityData<Ctx: Context> {
	proposal: Option<(Ctx::Digest, Ctx::Signature)>,
Gav's avatar
Gav committed
274
275
}

276
impl<Ctx: Context> Default for AuthorityData<Ctx> {
Gav's avatar
Gav committed
277
278
279
280
281
282
283
	fn default() -> Self {
		AuthorityData {
			proposal: None,
		}
	}
}

284
/// Type alias for the result of a statement import.
285
286
287
pub type ImportResult<Ctx> = Result<
	Option<Summary<<Ctx as Context>::Digest, <Ctx as Context>::GroupId>>,
	MisbehaviorFor<Ctx>
288
289
>;

Gav's avatar
Gav committed
290
/// Stores votes
291
292
293
294
pub struct Table<Ctx: Context> {
	authority_data: HashMap<Ctx::AuthorityId, AuthorityData<Ctx>>,
	detected_misbehavior: HashMap<Ctx::AuthorityId, Vec<MisbehaviorFor<Ctx>>>,
	candidate_votes: HashMap<Ctx::Digest, CandidateData<Ctx>>,
Gav's avatar
Gav committed
295
296
}

297
impl<Ctx: Context> Default for Table<Ctx> {
Gav's avatar
Gav committed
298
299
300
301
302
303
304
305
306
	fn default() -> Self {
		Table {
			authority_data: HashMap::new(),
			detected_misbehavior: HashMap::new(),
			candidate_votes: HashMap::new(),
		}
	}
}

307
impl<Ctx: Context> Table<Ctx> {
asynchronous rob's avatar
asynchronous rob committed
308
309
310
	/// Get the attested candidate for `digest`.
	///
	/// Returns `Some(_)` if the candidate exists and is includable.
311
	pub fn attested_candidate(&self, digest: &Ctx::Digest, context: &Ctx)
asynchronous rob's avatar
asynchronous rob committed
312
		-> Option<AttestedCandidate<
313
			Ctx::GroupId, Ctx::Candidate, Ctx::AuthorityId, Ctx::Signature,
asynchronous rob's avatar
asynchronous rob committed
314
315
316
317
318
319
320
321
		>>
	{
		self.candidate_votes.get(digest).and_then(|data| {
			let v_threshold = context.requisite_votes(&data.group_id);
			data.attested(v_threshold)
		})
	}

Gav's avatar
Gav committed
322
	/// Import a signed statement. Signatures should be checked for validity, and the
323
	/// sender should be checked to actually be an authority.
Gav's avatar
Gav committed
324
	///
325
326
327
	/// Validity and invalidity statements are only valid if the corresponding
	/// candidate has already been imported.
	///
328
	/// If this returns `None`, the statement was either duplicate or invalid.
Gav's avatar
Gav committed
329
330
	pub fn import_statement(
		&mut self,
331
332
333
		context: &Ctx,
		statement: SignedStatement<Ctx::Candidate, Ctx::Digest, Ctx::AuthorityId, Ctx::Signature>,
	) -> Option<Summary<Ctx::Digest, Ctx::GroupId>> {
Gav's avatar
Gav committed
334
335
		let SignedStatement { statement, signature, sender: signer } = statement;

336
		let res = match statement {
337
			Statement::Seconded(candidate) => self.import_candidate(
Gav's avatar
Gav committed
338
339
340
341
342
343
344
345
346
347
348
349
350
				context,
				signer.clone(),
				candidate,
				signature
			),
			Statement::Valid(digest) => self.validity_vote(
				context,
				signer.clone(),
				digest,
				ValidityVote::Valid(signature),
			),
		};

351
352
353
354
		match res {
			Ok(maybe_summary) => maybe_summary,
			Err(misbehavior) => {
				// all misbehavior in agreement is provable and actively malicious.
355
356
				// punishments may be cumulative.
				self.detected_misbehavior.entry(signer).or_default().push(misbehavior);
357
				None
Gav's avatar
Gav committed
358
359
360
361
362
			}
		}
	}

	/// Get a candidate by digest.
363
	pub fn get_candidate(&self, digest: &Ctx::Digest) -> Option<&Ctx::Candidate> {
Gav's avatar
Gav committed
364
365
366
367
368
		self.candidate_votes.get(digest).map(|d| &d.candidate)
	}

	/// Access all witnessed misbehavior.
	pub fn get_misbehavior(&self)
369
		-> &HashMap<Ctx::AuthorityId, Vec<MisbehaviorFor<Ctx>>>
Gav's avatar
Gav committed
370
371
372
373
	{
		&self.detected_misbehavior
	}

374
375
376
377
378
379
380
381
382
	/// Create a draining iterator of misbehaviors.
	///
	/// This consumes all detected misbehaviors, even if the iterator is not completely consumed.
	pub fn drain_misbehaviors(&mut self) -> DrainMisbehaviors<'_, Ctx> {
		self.detected_misbehavior
			.drain()
			.into()
	}

Gav's avatar
Gav committed
383
384
	fn import_candidate(
		&mut self,
385
386
387
388
389
390
391
		context: &Ctx,
		authority: Ctx::AuthorityId,
		candidate: Ctx::Candidate,
		signature: Ctx::Signature,
	) -> ImportResult<Ctx> {
		let group = Ctx::candidate_group(&candidate);
		if !context.is_member_of(&authority, &group) {
392
393
394
			return Err(Misbehavior::UnauthorizedStatement(UnauthorizedStatement {
				statement: SignedStatement {
					signature,
395
					statement: Statement::Seconded(candidate),
396
					sender: authority,
397
398
				},
			}));
Gav's avatar
Gav committed
399
400
401
		}

		// check that authority hasn't already specified another candidate.
402
		let digest = Ctx::candidate_digest(&candidate);
Gav's avatar
Gav committed
403

404
		let new_proposal = match self.authority_data.entry(authority.clone()) {
Gav's avatar
Gav committed
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
			Entry::Occupied(mut occ) => {
				// if digest is different, fetch candidate and
				// note misbehavior.
				let existing = occ.get_mut();

				if let Some((ref old_digest, ref old_sig)) = existing.proposal {
					if old_digest != &digest {
						const EXISTENCE_PROOF: &str =
							"when proposal first received from authority, candidate \
							votes entry is created. proposal here is `Some`, therefore \
							candidate votes entry exists; qed";

						let old_candidate = self.candidate_votes.get(old_digest)
							.expect(EXISTENCE_PROOF)
							.candidate
							.clone();

422
423
424
425
						return Err(Misbehavior::MultipleCandidates(MultipleCandidates {
							first: (old_candidate, old_sig.clone()),
							second: (candidate, signature.clone()),
						}));
Gav's avatar
Gav committed
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
					}

					false
				} else {
					existing.proposal = Some((digest.clone(), signature.clone()));
					true
				}
			}
			Entry::Vacant(vacant) => {
				vacant.insert(AuthorityData {
					proposal: Some((digest.clone(), signature.clone())),
				});
				true
			}
		};

		// NOTE: altering this code may affect the existence proof above. ensure it remains
		// valid.
		if new_proposal {
			self.candidate_votes.entry(digest.clone()).or_insert_with(move || CandidateData {
				group_id: group,
asynchronous rob's avatar
asynchronous rob committed
447
				candidate,
Gav's avatar
Gav committed
448
449
450
451
452
453
				validity_votes: HashMap::new(),
			});
		}

		self.validity_vote(
			context,
454
			authority,
Gav's avatar
Gav committed
455
456
457
458
459
460
461
			digest,
			ValidityVote::Issued(signature),
		)
	}

	fn validity_vote(
		&mut self,
462
463
464
465
466
		context: &Ctx,
		from: Ctx::AuthorityId,
		digest: Ctx::Digest,
		vote: ValidityVote<Ctx::Signature>,
	) -> ImportResult<Ctx> {
Gav's avatar
Gav committed
467
		let votes = match self.candidate_votes.get_mut(&digest) {
468
			None => return Ok(None),
Gav's avatar
Gav committed
469
470
471
472
473
			Some(votes) => votes,
		};

		// check that this authority actually can vote in this group.
		if !context.is_member_of(&from, &votes.group_id) {
474
475
			let sig = match vote {
				ValidityVote::Valid(s) => s,
Gav's avatar
Gav committed
476
477
478
479
480
				ValidityVote::Issued(_) =>
					panic!("implicit issuance vote only cast from `import_candidate` after \
							checking group membership of issuer; qed"),
			};

481
482
483
484
			return Err(Misbehavior::UnauthorizedStatement(UnauthorizedStatement {
				statement: SignedStatement {
					signature: sig,
					sender: from,
485
					statement: Statement::Valid(digest),
486
487
				}
			}));
Gav's avatar
Gav committed
488
489
490
491
492
		}

		// check for double votes.
		match votes.validity_votes.entry(from.clone()) {
			Entry::Occupied(occ) => {
493
494
495
496
497
				let make_vdv = |v| Misbehavior::ValidityDoubleVote(v);
				let make_ds = |ds| Misbehavior::DoubleSign(ds);
				return if occ.get() != &vote {
					Err(match (occ.get().clone(), vote) {
						// valid vote conflicting with candidate statement
Gav's avatar
Gav committed
498
499
						(ValidityVote::Issued(iss), ValidityVote::Valid(good)) |
						(ValidityVote::Valid(good), ValidityVote::Issued(iss)) =>
500
501
502
503
							make_vdv(ValidityDoubleVote::IssuedAndValidity((votes.candidate.clone(), iss), (digest, good))),

						// two signatures on same candidate
						(ValidityVote::Issued(a), ValidityVote::Issued(b)) =>
504
							make_ds(DoubleSign::Seconded(votes.candidate.clone(), a, b)),
505
506
507
508
509
510
511
512

						// two signatures on same validity vote
						(ValidityVote::Valid(a), ValidityVote::Valid(b)) =>
							make_ds(DoubleSign::Validity(digest, a, b)),
					})
				} else {
					Ok(None)
				}
Gav's avatar
Gav committed
513
514
515
516
517
518
			}
			Entry::Vacant(vacant) => {
				vacant.insert(vote);
			}
		}

519
		Ok(Some(votes.summary(digest)))
Gav's avatar
Gav committed
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
type Drain<'a, Ctx> = hash_map::Drain<'a, <Ctx as Context>::AuthorityId, Vec<MisbehaviorFor<Ctx>>>;

struct MisbehaviorForAuthority<Ctx: Context> {
	id: Ctx::AuthorityId,
	misbehaviors: Vec<MisbehaviorFor<Ctx>>,
}

impl<Ctx: Context> From<(Ctx::AuthorityId, Vec<MisbehaviorFor<Ctx>>)> for MisbehaviorForAuthority<Ctx> {
	fn from((id, mut misbehaviors): (Ctx::AuthorityId, Vec<MisbehaviorFor<Ctx>>)) -> Self {
		// we're going to be popping items off this list in the iterator, so reverse it now to
		// preserve the original ordering.
		misbehaviors.reverse();
		Self { id, misbehaviors }
	}
}

impl<Ctx: Context> Iterator for MisbehaviorForAuthority<Ctx> {
	type Item = (Ctx::AuthorityId, MisbehaviorFor<Ctx>);

	fn next(&mut self) -> Option<Self::Item> {
		self.misbehaviors.pop().map(|misbehavior| (self.id.clone(), misbehavior))
	}
}

pub struct DrainMisbehaviors<'a, Ctx: Context> {
	drain: Drain<'a, Ctx>,
	in_progress: Option<MisbehaviorForAuthority<Ctx>>,
}

impl<'a, Ctx: Context> From<Drain<'a, Ctx>> for DrainMisbehaviors<'a, Ctx> {
	fn from(drain: Drain<'a, Ctx>) -> Self {
		Self {
			drain,
			in_progress: None,
		}
	}
}

impl<'a, Ctx: Context> DrainMisbehaviors<'a, Ctx> {
	fn maybe_item(&mut self) -> Option<(Ctx::AuthorityId, MisbehaviorFor<Ctx>)> {
		self.in_progress.as_mut().and_then(Iterator::next)
	}
}

impl<'a, Ctx: Context> Iterator for DrainMisbehaviors<'a, Ctx> {
	type Item = (Ctx::AuthorityId, MisbehaviorFor<Ctx>);

	fn next(&mut self) -> Option<Self::Item> {
		// Note: this implementation will prematurely return `None` if `self.drain.next()` ever returns a
		// tuple whose vector is empty. That will never currently happen, as the only modification
		// to the backing map is currently via `drain` and `entry(...).or_default().push(...)`.
		// However, future code changes might change that property.
		self.maybe_item().or_else(|| {
			self.in_progress = self.drain.next().map(Into::into);
			self.maybe_item()
		})
	}
}

Gav's avatar
Gav committed
582
583
584
585
586
#[cfg(test)]
mod tests {
	use super::*;
	use std::collections::HashMap;

587
	fn create<Candidate: Context>() -> Table<Candidate> {
588
		Table::default()
Gav's avatar
Gav committed
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
	}

	#[derive(Debug, Copy, Clone, Hash, PartialEq, Eq)]
	struct AuthorityId(usize);

	#[derive(Debug, Copy, Clone, Hash, PartialOrd, Ord, PartialEq, Eq)]
	struct GroupId(usize);

	// group, body
	#[derive(Debug, Copy, Clone, Hash, PartialOrd, Ord, PartialEq, Eq)]
	struct Candidate(usize, usize);

	#[derive(Debug, Copy, Clone, Hash, PartialEq, Eq)]
	struct Signature(usize);

	#[derive(Debug, Copy, Clone, Hash, PartialEq, Eq)]
	struct Digest(usize);

	#[derive(Debug, PartialEq, Eq)]
	struct TestContext {
609
610
		// v -> parachain group
		authorities: HashMap<AuthorityId, GroupId>
Gav's avatar
Gav committed
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
	}

	impl Context for TestContext {
		type AuthorityId = AuthorityId;
		type Digest = Digest;
		type Candidate = Candidate;
		type GroupId = GroupId;
		type Signature = Signature;

		fn candidate_digest(candidate: &Candidate) -> Digest {
			Digest(candidate.1)
		}

		fn candidate_group(candidate: &Candidate) -> GroupId {
			GroupId(candidate.0)
		}

		fn is_member_of(
			&self,
			authority: &AuthorityId,
			group: &GroupId
		) -> bool {
633
			self.authorities.get(authority).map(|v| v == group).unwrap_or(false)
Gav's avatar
Gav committed
634
635
		}

636
		fn requisite_votes(&self, id: &GroupId) -> usize {
637
638
			let mut total_validity = 0;

639
			for validity in self.authorities.values() {
640
641
642
				if validity == id { total_validity += 1 }
			}

643
			total_validity / 2 + 1
Gav's avatar
Gav committed
644
645
646
647
648
649
650
651
		}
	}

	#[test]
	fn submitting_two_candidates_is_misbehavior() {
		let context = TestContext {
			authorities: {
				let mut map = HashMap::new();
652
				map.insert(AuthorityId(1), GroupId(2));
Gav's avatar
Gav committed
653
654
655
656
657
658
				map
			}
		};

		let mut table = create();
		let statement_a = SignedStatement {
659
			statement: Statement::Seconded(Candidate(2, 100)),
Gav's avatar
Gav committed
660
661
662
663
664
			signature: Signature(1),
			sender: AuthorityId(1),
		};

		let statement_b = SignedStatement {
665
			statement: Statement::Seconded(Candidate(2, 999)),
Gav's avatar
Gav committed
666
667
668
669
			signature: Signature(1),
			sender: AuthorityId(1),
		};

670
		table.import_statement(&context, statement_a);
Gav's avatar
Gav committed
671
672
		assert!(!table.detected_misbehavior.contains_key(&AuthorityId(1)));

673
		table.import_statement(&context, statement_b);
Gav's avatar
Gav committed
674
		assert_eq!(
675
676
			table.detected_misbehavior[&AuthorityId(1)][0],
			Misbehavior::MultipleCandidates(MultipleCandidates {
Gav's avatar
Gav committed
677
678
679
680
681
682
683
684
685
686
687
				first: (Candidate(2, 100), Signature(1)),
				second: (Candidate(2, 999), Signature(1)),
			})
		);
	}

	#[test]
	fn submitting_candidate_from_wrong_group_is_misbehavior() {
		let context = TestContext {
			authorities: {
				let mut map = HashMap::new();
688
				map.insert(AuthorityId(1), GroupId(3));
Gav's avatar
Gav committed
689
690
691
692
693
694
				map
			}
		};

		let mut table = create();
		let statement = SignedStatement {
695
			statement: Statement::Seconded(Candidate(2, 100)),
Gav's avatar
Gav committed
696
697
698
699
			signature: Signature(1),
			sender: AuthorityId(1),
		};

700
		table.import_statement(&context, statement);
Gav's avatar
Gav committed
701
702

		assert_eq!(
703
704
			table.detected_misbehavior[&AuthorityId(1)][0],
			Misbehavior::UnauthorizedStatement(UnauthorizedStatement {
Gav's avatar
Gav committed
705
				statement: SignedStatement {
706
					statement: Statement::Seconded(Candidate(2, 100)),
Gav's avatar
Gav committed
707
708
709
710
711
712
713
714
715
716
717
718
					signature: Signature(1),
					sender: AuthorityId(1),
				},
			})
		);
	}

	#[test]
	fn unauthorized_votes() {
		let context = TestContext {
			authorities: {
				let mut map = HashMap::new();
719
720
				map.insert(AuthorityId(1), GroupId(2));
				map.insert(AuthorityId(2), GroupId(3));
Gav's avatar
Gav committed
721
722
723
724
725
726
727
				map
			}
		};

		let mut table = create();

		let candidate_a = SignedStatement {
728
			statement: Statement::Seconded(Candidate(2, 100)),
Gav's avatar
Gav committed
729
730
731
732
733
			signature: Signature(1),
			sender: AuthorityId(1),
		};
		let candidate_a_digest = Digest(100);

734
		table.import_statement(&context, candidate_a);
Gav's avatar
Gav committed
735
736
737
738
739
740
741
742
743
		assert!(!table.detected_misbehavior.contains_key(&AuthorityId(1)));
		assert!(!table.detected_misbehavior.contains_key(&AuthorityId(2)));

		// authority 2 votes for validity on 1's candidate.
		let bad_validity_vote = SignedStatement {
			statement: Statement::Valid(candidate_a_digest.clone()),
			signature: Signature(2),
			sender: AuthorityId(2),
		};
744
		table.import_statement(&context, bad_validity_vote);
Gav's avatar
Gav committed
745
746

		assert_eq!(
747
748
			table.detected_misbehavior[&AuthorityId(2)][0],
			Misbehavior::UnauthorizedStatement(UnauthorizedStatement {
Gav's avatar
Gav committed
749
750
751
752
753
754
755
756
757
				statement: SignedStatement {
					statement: Statement::Valid(candidate_a_digest),
					signature: Signature(2),
					sender: AuthorityId(2),
				},
			})
		);
	}

758
759
760
761
762
	#[test]
	fn candidate_double_signature_is_misbehavior() {
		let context = TestContext {
			authorities: {
				let mut map = HashMap::new();
763
764
				map.insert(AuthorityId(1), GroupId(2));
				map.insert(AuthorityId(2), GroupId(2));
765
766
767
768
769
770
				map
			}
		};

		let mut table = create();
		let statement = SignedStatement {
771
			statement: Statement::Seconded(Candidate(2, 100)),
772
773
774
775
776
777
778
779
			signature: Signature(1),
			sender: AuthorityId(1),
		};

		table.import_statement(&context, statement);
		assert!(!table.detected_misbehavior.contains_key(&AuthorityId(1)));

		let invalid_statement = SignedStatement {
780
			statement: Statement::Seconded(Candidate(2, 100)),
781
782
783
784
785
786
787
788
			signature: Signature(999),
			sender: AuthorityId(1),
		};

		table.import_statement(&context, invalid_statement);
		assert!(table.detected_misbehavior.contains_key(&AuthorityId(1)));
	}

Gav's avatar
Gav committed
789
790
791
792
793
	#[test]
	fn issue_and_vote_is_misbehavior() {
		let context = TestContext {
			authorities: {
				let mut map = HashMap::new();
794
				map.insert(AuthorityId(1), GroupId(2));
Gav's avatar
Gav committed
795
796
797
798
799
800
				map
			}
		};

		let mut table = create();
		let statement = SignedStatement {
801
			statement: Statement::Seconded(Candidate(2, 100)),
Gav's avatar
Gav committed
802
803
804
805
806
			signature: Signature(1),
			sender: AuthorityId(1),
		};
		let candidate_digest = Digest(100);

807
		table.import_statement(&context, statement);
Gav's avatar
Gav committed
808
809
810
811
812
813
814
815
		assert!(!table.detected_misbehavior.contains_key(&AuthorityId(1)));

		let extra_vote = SignedStatement {
			statement: Statement::Valid(candidate_digest.clone()),
			signature: Signature(1),
			sender: AuthorityId(1),
		};

816
		table.import_statement(&context, extra_vote);
Gav's avatar
Gav committed
817
		assert_eq!(
818
819
			table.detected_misbehavior[&AuthorityId(1)][0],
			Misbehavior::ValidityDoubleVote(ValidityDoubleVote::IssuedAndValidity(
Gav's avatar
Gav committed
820
821
822
823
824
825
826
				(Candidate(2, 100), Signature(1)),
				(Digest(100), Signature(1)),
			))
		);
	}

	#[test]
827
	fn candidate_attested_works() {
Gav's avatar
Gav committed
828
829
830
831
832
833
834
835
		let validity_threshold = 6;

		let mut candidate = CandidateData::<TestContext> {
			group_id: GroupId(4),
			candidate: Candidate(4, 12345),
			validity_votes: HashMap::new(),
		};

836
		assert!(candidate.attested(validity_threshold).is_none());
Gav's avatar
Gav committed
837
838
839
840
841

		for i in 0..validity_threshold {
			candidate.validity_votes.insert(AuthorityId(i + 100), ValidityVote::Valid(Signature(i + 100)));
		}

842
		assert!(candidate.attested(validity_threshold).is_some());
Gav's avatar
Gav committed
843

844
845
846
847
		candidate.validity_votes.insert(
			AuthorityId(validity_threshold + 100),
			ValidityVote::Valid(Signature(validity_threshold + 100)),
		);
Gav's avatar
Gav committed
848

849
		assert!(candidate.attested(validity_threshold).is_some());
Gav's avatar
Gav committed
850
851
	}

852
	#[test]
853
	fn includability_works() {
854
855
856
		let context = TestContext {
			authorities: {
				let mut map = HashMap::new();
857
858
859
				map.insert(AuthorityId(1), GroupId(2));
				map.insert(AuthorityId(2), GroupId(2));
				map.insert(AuthorityId(3), GroupId(2));
860
861
862
863
864
865
866
				map
			}
		};

		// have 2/3 validity guarantors note validity.
		let mut table = create();
		let statement = SignedStatement {
867
			statement: Statement::Seconded(Candidate(2, 100)),
868
869
870
871
872
			signature: Signature(1),
			sender: AuthorityId(1),
		};
		let candidate_digest = Digest(100);

873
		table.import_statement(&context, statement);
874

875
		assert!(!table.detected_misbehavior.contains_key(&AuthorityId(1)));
876
		assert!(table.attested_candidate(&candidate_digest, &context).is_none());
877
878
879
880
881
882
883

		let vote = SignedStatement {
			statement: Statement::Valid(candidate_digest.clone()),
			signature: Signature(2),
			sender: AuthorityId(2),
		};

884
		table.import_statement(&context, vote);
885
		assert!(!table.detected_misbehavior.contains_key(&AuthorityId(2)));
886
		assert!(table.attested_candidate(&candidate_digest, &context).is_some());
887
888
	}

Gav's avatar
Gav committed
889
890
891
892
893
	#[test]
	fn candidate_import_gives_summary() {
		let context = TestContext {
			authorities: {
				let mut map = HashMap::new();
894
				map.insert(AuthorityId(1), GroupId(2));
Gav's avatar
Gav committed
895
896
897
898
899
900
				map
			}
		};

		let mut table = create();
		let statement = SignedStatement {
901
			statement: Statement::Seconded(Candidate(2, 100)),
Gav's avatar
Gav committed
902
903
904
905
			signature: Signature(1),
			sender: AuthorityId(1),
		};

906
		let summary = table.import_statement(&context, statement)
Gav's avatar
Gav committed
907
908
909
910
911
912
913
914
915
916
917
918
			.expect("candidate import to give summary");

		assert_eq!(summary.candidate, Digest(100));
		assert_eq!(summary.group_id, GroupId(2));
		assert_eq!(summary.validity_votes, 1);
	}

	#[test]
	fn candidate_vote_gives_summary() {
		let context = TestContext {
			authorities: {
				let mut map = HashMap::new();
919
920
				map.insert(AuthorityId(1), GroupId(2));
				map.insert(AuthorityId(2), GroupId(2));
Gav's avatar
Gav committed
921
922
923
924
925
926
				map
			}
		};

		let mut table = create();
		let statement = SignedStatement {
927
			statement: Statement::Seconded(Candidate(2, 100)),
Gav's avatar
Gav committed
928
929
930
931
932
			signature: Signature(1),
			sender: AuthorityId(1),
		};
		let candidate_digest = Digest(100);

933
		table.import_statement(&context, statement);
Gav's avatar
Gav committed
934
935
936
937
938
939
940
941
		assert!(!table.detected_misbehavior.contains_key(&AuthorityId(1)));

		let vote = SignedStatement {
			statement: Statement::Valid(candidate_digest.clone()),
			signature: Signature(2),
			sender: AuthorityId(2),
		};

942
		let summary = table.import_statement(&context, vote)
Gav's avatar
Gav committed
943
944
945
946
947
948
949
950
951
			.expect("candidate vote to give summary");

		assert!(!table.detected_misbehavior.contains_key(&AuthorityId(2)));

		assert_eq!(summary.candidate, Digest(100));
		assert_eq!(summary.group_id, GroupId(2));
		assert_eq!(summary.validity_votes, 2);
	}
}