polkadot_statement_table/
generic.rs

1// Copyright (C) Parity Technologies (UK) Ltd.
2// This file is part of Polkadot.
3
4// Polkadot is free software: you can redistribute it and/or modify
5// it under the terms of the GNU General Public License as published by
6// the Free Software Foundation, either version 3 of the License, or
7// (at your option) any later version.
8
9// Polkadot is distributed in the hope that it will be useful,
10// but WITHOUT ANY WARRANTY; without even the implied warranty of
11// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12// GNU General Public License for more details.
13
14// You should have received a copy of the GNU General Public License
15// along with Polkadot.  If not, see <http://www.gnu.org/licenses/>.
16
17//! The statement table: generic implementation.
18//!
19//! This stores messages other authorities issue about candidates.
20//!
21//! These messages are used to create a proposal submitted to a BFT consensus process.
22//!
23//! Each parachain is associated with a committee of authorities, who issue statements
24//! indicating whether the candidate is valid or invalid. Once a threshold of the committee
25//! has signed validity statements, the candidate may be marked includable.
26
27use std::{
28	collections::hash_map::{self, Entry, HashMap},
29	fmt::Debug,
30	hash::Hash,
31};
32
33use polkadot_primitives::{
34	effective_minimum_backing_votes, ValidatorSignature,
35	ValidityAttestation as PrimitiveValidityAttestation,
36};
37
38use codec::{Decode, Encode};
39const LOG_TARGET: &str = "parachain::statement-table";
40
41/// Context for the statement table.
42pub trait Context {
43	/// An authority ID
44	type AuthorityId: Debug + Hash + Eq + Clone;
45	/// The digest (hash or other unique attribute) of a candidate.
46	type Digest: Debug + Hash + Eq + Clone;
47	/// The group ID type
48	type GroupId: Debug + Hash + Ord + Eq + Clone;
49	/// A signature type.
50	type Signature: Debug + Eq + Clone;
51	/// Candidate type. In practice this will be a candidate receipt.
52	type Candidate: Debug + Ord + Eq + Clone;
53
54	/// get the digest of a candidate.
55	fn candidate_digest(candidate: &Self::Candidate) -> Self::Digest;
56
57	/// Whether a authority is a member of a group.
58	/// Members are meant to submit candidates and vote on validity.
59	fn is_member_of(&self, authority: &Self::AuthorityId, group: &Self::GroupId) -> bool;
60
61	/// Get a validator group size.
62	fn get_group_size(&self, group: &Self::GroupId) -> Option<usize>;
63}
64
65/// Statements circulated among peers.
66#[derive(PartialEq, Eq, Debug, Clone, Encode, Decode)]
67pub enum Statement<Candidate, Digest> {
68	/// Broadcast by an authority to indicate that this is its candidate for inclusion.
69	///
70	/// Broadcasting two different candidate messages per round is not allowed.
71	#[codec(index = 1)]
72	Seconded(Candidate),
73	/// Broadcast by a authority to attest that the candidate with given digest is valid.
74	#[codec(index = 2)]
75	Valid(Digest),
76}
77
78/// A signed statement.
79#[derive(PartialEq, Eq, Debug, Clone, Encode, Decode)]
80pub struct SignedStatement<Candidate, Digest, AuthorityId, Signature> {
81	/// The statement.
82	pub statement: Statement<Candidate, Digest>,
83	/// The signature.
84	pub signature: Signature,
85	/// The sender.
86	pub sender: AuthorityId,
87}
88
89/// Misbehavior: voting more than one way on candidate validity.
90///
91/// Since there are three possible ways to vote, a double vote is possible in
92/// three possible combinations (unordered)
93#[derive(PartialEq, Eq, Debug, Clone)]
94pub enum ValidityDoubleVote<Candidate, Digest, Signature> {
95	/// Implicit vote by issuing and explicitly voting validity.
96	IssuedAndValidity((Candidate, Signature), (Digest, Signature)),
97}
98
99impl<Candidate, Digest, Signature> ValidityDoubleVote<Candidate, Digest, Signature> {
100	/// Deconstruct this misbehavior into two `(Statement, Signature)` pairs, erasing the
101	/// information about precisely what the problem was.
102	pub fn deconstruct<Ctx>(
103		self,
104	) -> ((Statement<Candidate, Digest>, Signature), (Statement<Candidate, Digest>, Signature))
105	where
106		Ctx: Context<Candidate = Candidate, Digest = Digest, Signature = Signature>,
107		Candidate: Debug + Ord + Eq + Clone,
108		Digest: Debug + Hash + Eq + Clone,
109		Signature: Debug + Eq + Clone,
110	{
111		match self {
112			Self::IssuedAndValidity((c, s1), (d, s2)) =>
113				((Statement::Seconded(c), s1), (Statement::Valid(d), s2)),
114		}
115	}
116}
117
118/// Misbehavior: multiple signatures on same statement.
119#[derive(PartialEq, Eq, Debug, Clone)]
120pub enum DoubleSign<Candidate, Digest, Signature> {
121	/// On candidate.
122	Seconded(Candidate, Signature, Signature),
123	/// On validity.
124	Validity(Digest, Signature, Signature),
125}
126
127impl<Candidate, Digest, Signature> DoubleSign<Candidate, Digest, Signature> {
128	/// Deconstruct this misbehavior into a statement with two signatures, erasing the information
129	/// about precisely where in the process the issue was detected.
130	pub fn deconstruct(self) -> (Statement<Candidate, Digest>, Signature, Signature) {
131		match self {
132			Self::Seconded(candidate, a, b) => (Statement::Seconded(candidate), a, b),
133			Self::Validity(digest, a, b) => (Statement::Valid(digest), a, b),
134		}
135	}
136}
137
138/// Misbehavior: submitted statement for wrong group.
139#[derive(PartialEq, Eq, Debug, Clone)]
140pub struct UnauthorizedStatement<Candidate, Digest, AuthorityId, Signature> {
141	/// A signed statement which was submitted without proper authority.
142	pub statement: SignedStatement<Candidate, Digest, AuthorityId, Signature>,
143}
144
145/// Different kinds of misbehavior. All of these kinds of malicious misbehavior
146/// are easily provable and extremely disincentivized.
147#[derive(PartialEq, Eq, Debug, Clone)]
148pub enum Misbehavior<Candidate, Digest, AuthorityId, Signature> {
149	/// Voted invalid and valid on validity.
150	ValidityDoubleVote(ValidityDoubleVote<Candidate, Digest, Signature>),
151	/// Submitted a message that was unauthorized.
152	UnauthorizedStatement(UnauthorizedStatement<Candidate, Digest, AuthorityId, Signature>),
153	/// Submitted two valid signatures for the same message.
154	DoubleSign(DoubleSign<Candidate, Digest, Signature>),
155}
156
157/// Type alias for misbehavior corresponding to context type.
158pub type MisbehaviorFor<Ctx> = Misbehavior<
159	<Ctx as Context>::Candidate,
160	<Ctx as Context>::Digest,
161	<Ctx as Context>::AuthorityId,
162	<Ctx as Context>::Signature,
163>;
164
165// Kinds of votes for validity on a particular candidate.
166#[derive(Clone, PartialEq, Eq)]
167enum ValidityVote<Signature: Eq + Clone> {
168	// Implicit validity vote.
169	Issued(Signature),
170	// Direct validity vote.
171	Valid(Signature),
172}
173
174/// A summary of import of a statement.
175#[derive(Clone, PartialEq, Eq, Debug)]
176pub struct Summary<Digest, Group> {
177	/// The digest of the candidate referenced.
178	pub candidate: Digest,
179	/// The group that the candidate is in.
180	pub group_id: Group,
181	/// How many validity votes are currently witnessed.
182	pub validity_votes: usize,
183}
184
185/// A validity attestation.
186#[derive(Clone, PartialEq, Decode, Encode)]
187pub enum ValidityAttestation<Signature> {
188	/// implicit validity attestation by issuing.
189	/// This corresponds to issuance of a `Candidate` statement.
190	Implicit(Signature),
191	/// An explicit attestation. This corresponds to issuance of a
192	/// `Valid` statement.
193	Explicit(Signature),
194}
195
196impl Into<PrimitiveValidityAttestation> for ValidityAttestation<ValidatorSignature> {
197	fn into(self) -> PrimitiveValidityAttestation {
198		match self {
199			Self::Implicit(s) => PrimitiveValidityAttestation::Implicit(s),
200			Self::Explicit(s) => PrimitiveValidityAttestation::Explicit(s),
201		}
202	}
203}
204
205/// An attested-to candidate.
206#[derive(Clone, PartialEq, Decode, Encode)]
207pub struct AttestedCandidate<Group, Candidate, AuthorityId, Signature> {
208	/// The group ID that the candidate is in.
209	pub group_id: Group,
210	/// The candidate data.
211	pub candidate: Candidate,
212	/// Validity attestations.
213	pub validity_votes: Vec<(AuthorityId, ValidityAttestation<Signature>)>,
214}
215
216/// Stores votes and data about a candidate.
217pub struct CandidateData<Ctx: Context> {
218	group_id: Ctx::GroupId,
219	candidate: Ctx::Candidate,
220	validity_votes: HashMap<Ctx::AuthorityId, ValidityVote<Ctx::Signature>>,
221}
222
223impl<Ctx: Context> CandidateData<Ctx> {
224	/// Yield a full attestation for a candidate.
225	/// If the candidate can be included, it will return `Some`.
226	pub fn attested(
227		&self,
228		validity_threshold: usize,
229	) -> Option<AttestedCandidate<Ctx::GroupId, Ctx::Candidate, Ctx::AuthorityId, Ctx::Signature>>
230	{
231		let valid_votes = self.validity_votes.len();
232		if valid_votes < validity_threshold {
233			return None
234		}
235
236		let validity_votes = self
237			.validity_votes
238			.iter()
239			.map(|(a, v)| match *v {
240				ValidityVote::Valid(ref s) => (a.clone(), ValidityAttestation::Explicit(s.clone())),
241				ValidityVote::Issued(ref s) =>
242					(a.clone(), ValidityAttestation::Implicit(s.clone())),
243			})
244			.collect();
245
246		Some(AttestedCandidate {
247			group_id: self.group_id.clone(),
248			candidate: self.candidate.clone(),
249			validity_votes,
250		})
251	}
252
253	fn summary(&self, digest: Ctx::Digest) -> Summary<Ctx::Digest, Ctx::GroupId> {
254		Summary {
255			candidate: digest,
256			group_id: self.group_id.clone(),
257			validity_votes: self.validity_votes.len(),
258		}
259	}
260}
261
262// authority metadata
263struct AuthorityData<Ctx: Context> {
264	proposals: Vec<(Ctx::Digest, Ctx::Signature)>,
265}
266
267impl<Ctx: Context> Default for AuthorityData<Ctx> {
268	fn default() -> Self {
269		AuthorityData { proposals: Vec::new() }
270	}
271}
272
273/// Type alias for the result of a statement import.
274pub type ImportResult<Ctx> = Result<
275	Option<Summary<<Ctx as Context>::Digest, <Ctx as Context>::GroupId>>,
276	MisbehaviorFor<Ctx>,
277>;
278
279/// Stores votes
280pub struct Table<Ctx: Context> {
281	authority_data: HashMap<Ctx::AuthorityId, AuthorityData<Ctx>>,
282	detected_misbehavior: HashMap<Ctx::AuthorityId, Vec<MisbehaviorFor<Ctx>>>,
283	candidate_votes: HashMap<Ctx::Digest, CandidateData<Ctx>>,
284}
285
286impl<Ctx: Context> Table<Ctx> {
287	pub fn new() -> Self {
288		Table {
289			authority_data: HashMap::default(),
290			detected_misbehavior: HashMap::default(),
291			candidate_votes: HashMap::default(),
292		}
293	}
294
295	/// Get the attested candidate for `digest`.
296	///
297	/// Returns `Some(_)` if the candidate exists and is includable.
298	pub fn attested_candidate(
299		&self,
300		digest: &Ctx::Digest,
301		context: &Ctx,
302		minimum_backing_votes: u32,
303	) -> Option<AttestedCandidate<Ctx::GroupId, Ctx::Candidate, Ctx::AuthorityId, Ctx::Signature>>
304	{
305		self.candidate_votes.get(digest).and_then(|data| {
306			let v_threshold = context.get_group_size(&data.group_id).map_or(usize::MAX, |len| {
307				effective_minimum_backing_votes(len, minimum_backing_votes)
308			});
309			data.attested(v_threshold)
310		})
311	}
312
313	/// Import a signed statement. Signatures should be checked for validity, and the
314	/// sender should be checked to actually be an authority.
315	///
316	/// Validity and invalidity statements are only valid if the corresponding
317	/// candidate has already been imported.
318	///
319	/// If this returns `None`, the statement was either duplicate or invalid.
320	pub fn import_statement(
321		&mut self,
322		context: &Ctx,
323		group_id: Ctx::GroupId,
324		statement: SignedStatement<Ctx::Candidate, Ctx::Digest, Ctx::AuthorityId, Ctx::Signature>,
325	) -> Option<Summary<Ctx::Digest, Ctx::GroupId>> {
326		let SignedStatement { statement, signature, sender: signer } = statement;
327		let res = match statement {
328			Statement::Seconded(candidate) =>
329				self.import_candidate(context, signer.clone(), candidate, signature, group_id),
330			Statement::Valid(digest) =>
331				self.validity_vote(context, signer.clone(), digest, ValidityVote::Valid(signature)),
332		};
333
334		match res {
335			Ok(maybe_summary) => maybe_summary,
336			Err(misbehavior) => {
337				// all misbehavior in agreement is provable and actively malicious.
338				// punishments may be cumulative.
339				self.detected_misbehavior.entry(signer).or_default().push(misbehavior);
340				None
341			},
342		}
343	}
344
345	/// Get a candidate by digest.
346	pub fn get_candidate(&self, digest: &Ctx::Digest) -> Option<&Ctx::Candidate> {
347		self.candidate_votes.get(digest).map(|d| &d.candidate)
348	}
349
350	/// Access all witnessed misbehavior.
351	pub fn get_misbehavior(&self) -> &HashMap<Ctx::AuthorityId, Vec<MisbehaviorFor<Ctx>>> {
352		&self.detected_misbehavior
353	}
354
355	/// Create a draining iterator of misbehaviors.
356	///
357	/// This consumes all detected misbehaviors, even if the iterator is not completely consumed.
358	pub fn drain_misbehaviors(&mut self) -> DrainMisbehaviors<'_, Ctx> {
359		self.detected_misbehavior.drain().into()
360	}
361
362	fn import_candidate(
363		&mut self,
364		context: &Ctx,
365		authority: Ctx::AuthorityId,
366		candidate: Ctx::Candidate,
367		signature: Ctx::Signature,
368		group: Ctx::GroupId,
369	) -> ImportResult<Ctx> {
370		if !context.is_member_of(&authority, &group) {
371			gum::debug!(target: LOG_TARGET,  authority = ?authority, group = ?group, "New `Misbehavior::UnauthorizedStatement`, candidate backed by validator that doesn't belong to expected group" );
372			return Err(Misbehavior::UnauthorizedStatement(UnauthorizedStatement {
373				statement: SignedStatement {
374					signature,
375					statement: Statement::Seconded(candidate),
376					sender: authority,
377				},
378			}))
379		}
380
381		// check that authority hasn't already specified another candidate.
382		let digest = Ctx::candidate_digest(&candidate);
383
384		let new_proposal = match self.authority_data.entry(authority.clone()) {
385			Entry::Occupied(mut occ) => {
386				// if digest is different, fetch candidate and
387				// note misbehavior.
388				let existing = occ.get_mut();
389				if existing.proposals.iter().any(|(ref od, _)| od == &digest) {
390					false
391				} else {
392					existing.proposals.push((digest.clone(), signature.clone()));
393					true
394				}
395			},
396			Entry::Vacant(vacant) => {
397				vacant
398					.insert(AuthorityData { proposals: vec![(digest.clone(), signature.clone())] });
399				true
400			},
401		};
402
403		// NOTE: altering this code may affect the existence proof above. ensure it remains
404		// valid.
405		if new_proposal {
406			self.candidate_votes
407				.entry(digest.clone())
408				.or_insert_with(move || CandidateData {
409					group_id: group,
410					candidate,
411					validity_votes: HashMap::new(),
412				});
413		}
414
415		self.validity_vote(context, authority, digest, ValidityVote::Issued(signature))
416	}
417
418	fn validity_vote(
419		&mut self,
420		context: &Ctx,
421		from: Ctx::AuthorityId,
422		digest: Ctx::Digest,
423		vote: ValidityVote<Ctx::Signature>,
424	) -> ImportResult<Ctx> {
425		let votes = match self.candidate_votes.get_mut(&digest) {
426			None => return Ok(None),
427			Some(votes) => votes,
428		};
429
430		// check that this authority actually can vote in this group.
431		if !context.is_member_of(&from, &votes.group_id) {
432			let sig = match vote {
433				ValidityVote::Valid(s) => s,
434				ValidityVote::Issued(s) => s,
435			};
436
437			return Err(Misbehavior::UnauthorizedStatement(UnauthorizedStatement {
438				statement: SignedStatement {
439					signature: sig,
440					sender: from,
441					statement: Statement::Valid(digest),
442				},
443			}))
444		}
445
446		// check for double votes.
447		match votes.validity_votes.entry(from.clone()) {
448			Entry::Occupied(occ) => {
449				let make_vdv = |v| Misbehavior::ValidityDoubleVote(v);
450				let make_ds = |ds| Misbehavior::DoubleSign(ds);
451				return if occ.get() != &vote {
452					Err(match (occ.get().clone(), vote) {
453						// valid vote conflicting with candidate statement
454						(ValidityVote::Issued(iss), ValidityVote::Valid(good)) |
455						(ValidityVote::Valid(good), ValidityVote::Issued(iss)) =>
456							make_vdv(ValidityDoubleVote::IssuedAndValidity(
457								(votes.candidate.clone(), iss),
458								(digest, good),
459							)),
460
461						// two signatures on same candidate
462						(ValidityVote::Issued(a), ValidityVote::Issued(b)) =>
463							make_ds(DoubleSign::Seconded(votes.candidate.clone(), a, b)),
464
465						// two signatures on same validity vote
466						(ValidityVote::Valid(a), ValidityVote::Valid(b)) =>
467							make_ds(DoubleSign::Validity(digest, a, b)),
468					})
469				} else {
470					Ok(None)
471				}
472			},
473			Entry::Vacant(vacant) => {
474				vacant.insert(vote);
475			},
476		}
477
478		Ok(Some(votes.summary(digest)))
479	}
480}
481
482type Drain<'a, Ctx> = hash_map::Drain<'a, <Ctx as Context>::AuthorityId, Vec<MisbehaviorFor<Ctx>>>;
483
484struct MisbehaviorForAuthority<Ctx: Context> {
485	id: Ctx::AuthorityId,
486	misbehaviors: Vec<MisbehaviorFor<Ctx>>,
487}
488
489impl<Ctx: Context> From<(Ctx::AuthorityId, Vec<MisbehaviorFor<Ctx>>)>
490	for MisbehaviorForAuthority<Ctx>
491{
492	fn from((id, mut misbehaviors): (Ctx::AuthorityId, Vec<MisbehaviorFor<Ctx>>)) -> Self {
493		// we're going to be popping items off this list in the iterator, so reverse it now to
494		// preserve the original ordering.
495		misbehaviors.reverse();
496		Self { id, misbehaviors }
497	}
498}
499
500impl<Ctx: Context> Iterator for MisbehaviorForAuthority<Ctx> {
501	type Item = (Ctx::AuthorityId, MisbehaviorFor<Ctx>);
502
503	fn next(&mut self) -> Option<Self::Item> {
504		self.misbehaviors.pop().map(|misbehavior| (self.id.clone(), misbehavior))
505	}
506}
507
508pub struct DrainMisbehaviors<'a, Ctx: Context> {
509	drain: Drain<'a, Ctx>,
510	in_progress: Option<MisbehaviorForAuthority<Ctx>>,
511}
512
513impl<'a, Ctx: Context> From<Drain<'a, Ctx>> for DrainMisbehaviors<'a, Ctx> {
514	fn from(drain: Drain<'a, Ctx>) -> Self {
515		Self { drain, in_progress: None }
516	}
517}
518
519impl<'a, Ctx: Context> DrainMisbehaviors<'a, Ctx> {
520	fn maybe_item(&mut self) -> Option<(Ctx::AuthorityId, MisbehaviorFor<Ctx>)> {
521		self.in_progress.as_mut().and_then(Iterator::next)
522	}
523}
524
525impl<'a, Ctx: Context> Iterator for DrainMisbehaviors<'a, Ctx> {
526	type Item = (Ctx::AuthorityId, MisbehaviorFor<Ctx>);
527
528	fn next(&mut self) -> Option<Self::Item> {
529		// Note: this implementation will prematurely return `None` if `self.drain.next()` ever
530		// returns a tuple whose vector is empty. That will never currently happen, as the only
531		// modification to the backing map is currently via `drain` and
532		// `entry(...).or_default().push(...)`. However, future code changes might change that
533		// property.
534		self.maybe_item().or_else(|| {
535			self.in_progress = self.drain.next().map(Into::into);
536			self.maybe_item()
537		})
538	}
539}
540
541#[cfg(test)]
542mod tests {
543	use super::*;
544	use std::collections::HashMap;
545
546	#[derive(Debug, Copy, Clone, Hash, PartialEq, Eq)]
547	struct AuthorityId(usize);
548
549	#[derive(Debug, Copy, Clone, Hash, PartialOrd, Ord, PartialEq, Eq)]
550	struct GroupId(usize);
551
552	// group, body
553	#[derive(Debug, Copy, Clone, Hash, PartialOrd, Ord, PartialEq, Eq)]
554	struct Candidate(usize, usize);
555
556	#[derive(Debug, Copy, Clone, Hash, PartialEq, Eq)]
557	struct Signature(usize);
558
559	#[derive(Debug, Copy, Clone, Hash, PartialEq, Eq)]
560	struct Digest(usize);
561
562	#[derive(Debug, PartialEq, Eq)]
563	struct TestContext {
564		// v -> parachain group
565		authorities: HashMap<AuthorityId, GroupId>,
566	}
567
568	impl Context for TestContext {
569		type AuthorityId = AuthorityId;
570		type Digest = Digest;
571		type Candidate = Candidate;
572		type GroupId = GroupId;
573		type Signature = Signature;
574
575		fn candidate_digest(candidate: &Candidate) -> Digest {
576			Digest(candidate.1)
577		}
578
579		fn is_member_of(&self, authority: &AuthorityId, group: &GroupId) -> bool {
580			self.authorities.get(authority).map(|v| v == group).unwrap_or(false)
581		}
582
583		fn get_group_size(&self, group: &Self::GroupId) -> Option<usize> {
584			let count = self.authorities.values().filter(|g| *g == group).count();
585			if count == 0 {
586				None
587			} else {
588				Some(count)
589			}
590		}
591	}
592
593	#[test]
594	fn submitting_two_candidates_can_be_allowed() {
595		let context = TestContext {
596			authorities: {
597				let mut map = HashMap::new();
598				map.insert(AuthorityId(1), GroupId(2));
599				map
600			},
601		};
602
603		let mut table = Table::new();
604		let statement_a = SignedStatement {
605			statement: Statement::Seconded(Candidate(2, 100)),
606			signature: Signature(1),
607			sender: AuthorityId(1),
608		};
609
610		let statement_b = SignedStatement {
611			statement: Statement::Seconded(Candidate(2, 999)),
612			signature: Signature(1),
613			sender: AuthorityId(1),
614		};
615
616		table.import_statement(&context, GroupId(2), statement_a);
617		assert!(!table.detected_misbehavior.contains_key(&AuthorityId(1)));
618
619		table.import_statement(&context, GroupId(2), statement_b);
620		assert!(!table.detected_misbehavior.contains_key(&AuthorityId(1)));
621	}
622
623	#[test]
624	fn submitting_candidate_from_wrong_group_is_misbehavior() {
625		let context = TestContext {
626			authorities: {
627				let mut map = HashMap::new();
628				map.insert(AuthorityId(1), GroupId(3));
629				map
630			},
631		};
632
633		let mut table = Table::new();
634		let statement = SignedStatement {
635			statement: Statement::Seconded(Candidate(2, 100)),
636			signature: Signature(1),
637			sender: AuthorityId(1),
638		};
639
640		table.import_statement(&context, GroupId(2), statement);
641
642		assert_eq!(
643			table.detected_misbehavior[&AuthorityId(1)][0],
644			Misbehavior::UnauthorizedStatement(UnauthorizedStatement {
645				statement: SignedStatement {
646					statement: Statement::Seconded(Candidate(2, 100)),
647					signature: Signature(1),
648					sender: AuthorityId(1),
649				},
650			})
651		);
652	}
653
654	#[test]
655	fn unauthorized_votes() {
656		let context = TestContext {
657			authorities: {
658				let mut map = HashMap::new();
659				map.insert(AuthorityId(1), GroupId(2));
660				map.insert(AuthorityId(2), GroupId(3));
661				map
662			},
663		};
664
665		let mut table = Table::new();
666
667		let candidate_a = SignedStatement {
668			statement: Statement::Seconded(Candidate(2, 100)),
669			signature: Signature(1),
670			sender: AuthorityId(1),
671		};
672		let candidate_a_digest = Digest(100);
673
674		table.import_statement(&context, GroupId(2), candidate_a);
675		assert!(!table.detected_misbehavior.contains_key(&AuthorityId(1)));
676		assert!(!table.detected_misbehavior.contains_key(&AuthorityId(2)));
677
678		// authority 2 votes for validity on 1's candidate.
679		let bad_validity_vote = SignedStatement {
680			statement: Statement::Valid(candidate_a_digest),
681			signature: Signature(2),
682			sender: AuthorityId(2),
683		};
684		table.import_statement(&context, GroupId(3), bad_validity_vote);
685
686		assert_eq!(
687			table.detected_misbehavior[&AuthorityId(2)][0],
688			Misbehavior::UnauthorizedStatement(UnauthorizedStatement {
689				statement: SignedStatement {
690					statement: Statement::Valid(candidate_a_digest),
691					signature: Signature(2),
692					sender: AuthorityId(2),
693				},
694			})
695		);
696	}
697
698	#[test]
699	fn candidate_double_signature_is_misbehavior() {
700		let context = TestContext {
701			authorities: {
702				let mut map = HashMap::new();
703				map.insert(AuthorityId(1), GroupId(2));
704				map.insert(AuthorityId(2), GroupId(2));
705				map
706			},
707		};
708
709		let mut table = Table::new();
710		let statement = SignedStatement {
711			statement: Statement::Seconded(Candidate(2, 100)),
712			signature: Signature(1),
713			sender: AuthorityId(1),
714		};
715
716		table.import_statement(&context, GroupId(2), statement);
717		assert!(!table.detected_misbehavior.contains_key(&AuthorityId(1)));
718
719		let invalid_statement = SignedStatement {
720			statement: Statement::Seconded(Candidate(2, 100)),
721			signature: Signature(999),
722			sender: AuthorityId(1),
723		};
724
725		table.import_statement(&context, GroupId(2), invalid_statement);
726		assert!(table.detected_misbehavior.contains_key(&AuthorityId(1)));
727	}
728
729	#[test]
730	fn issue_and_vote_is_misbehavior() {
731		let context = TestContext {
732			authorities: {
733				let mut map = HashMap::new();
734				map.insert(AuthorityId(1), GroupId(2));
735				map
736			},
737		};
738
739		let mut table = Table::new();
740		let statement = SignedStatement {
741			statement: Statement::Seconded(Candidate(2, 100)),
742			signature: Signature(1),
743			sender: AuthorityId(1),
744		};
745		let candidate_digest = Digest(100);
746
747		table.import_statement(&context, GroupId(2), statement);
748		assert!(!table.detected_misbehavior.contains_key(&AuthorityId(1)));
749
750		let extra_vote = SignedStatement {
751			statement: Statement::Valid(candidate_digest),
752			signature: Signature(1),
753			sender: AuthorityId(1),
754		};
755
756		table.import_statement(&context, GroupId(2), extra_vote);
757		assert_eq!(
758			table.detected_misbehavior[&AuthorityId(1)][0],
759			Misbehavior::ValidityDoubleVote(ValidityDoubleVote::IssuedAndValidity(
760				(Candidate(2, 100), Signature(1)),
761				(Digest(100), Signature(1)),
762			))
763		);
764	}
765
766	#[test]
767	fn candidate_attested_works() {
768		let validity_threshold = 6;
769
770		let mut candidate = CandidateData::<TestContext> {
771			group_id: GroupId(4),
772			candidate: Candidate(4, 12345),
773			validity_votes: HashMap::new(),
774		};
775
776		assert!(candidate.attested(validity_threshold).is_none());
777
778		for i in 0..validity_threshold {
779			candidate
780				.validity_votes
781				.insert(AuthorityId(i + 100), ValidityVote::Valid(Signature(i + 100)));
782		}
783
784		assert!(candidate.attested(validity_threshold).is_some());
785
786		candidate.validity_votes.insert(
787			AuthorityId(validity_threshold + 100),
788			ValidityVote::Valid(Signature(validity_threshold + 100)),
789		);
790
791		assert!(candidate.attested(validity_threshold).is_some());
792	}
793
794	#[test]
795	fn includability_works() {
796		let context = TestContext {
797			authorities: {
798				let mut map = HashMap::new();
799				map.insert(AuthorityId(1), GroupId(2));
800				map.insert(AuthorityId(2), GroupId(2));
801				map.insert(AuthorityId(3), GroupId(2));
802				map
803			},
804		};
805
806		// have 2/3 validity guarantors note validity.
807		let mut table = Table::new();
808		let statement = SignedStatement {
809			statement: Statement::Seconded(Candidate(2, 100)),
810			signature: Signature(1),
811			sender: AuthorityId(1),
812		};
813		let candidate_digest = Digest(100);
814
815		table.import_statement(&context, GroupId(2), statement);
816
817		assert!(!table.detected_misbehavior.contains_key(&AuthorityId(1)));
818		assert!(table.attested_candidate(&candidate_digest, &context, 2).is_none());
819
820		let vote = SignedStatement {
821			statement: Statement::Valid(candidate_digest),
822			signature: Signature(2),
823			sender: AuthorityId(2),
824		};
825
826		table.import_statement(&context, GroupId(2), vote);
827		assert!(!table.detected_misbehavior.contains_key(&AuthorityId(2)));
828		assert!(table.attested_candidate(&candidate_digest, &context, 2).is_some());
829	}
830
831	#[test]
832	fn candidate_import_gives_summary() {
833		let context = TestContext {
834			authorities: {
835				let mut map = HashMap::new();
836				map.insert(AuthorityId(1), GroupId(2));
837				map
838			},
839		};
840
841		let mut table = Table::new();
842		let statement = SignedStatement {
843			statement: Statement::Seconded(Candidate(2, 100)),
844			signature: Signature(1),
845			sender: AuthorityId(1),
846		};
847
848		let summary = table
849			.import_statement(&context, GroupId(2), statement)
850			.expect("candidate import to give summary");
851
852		assert_eq!(summary.candidate, Digest(100));
853		assert_eq!(summary.group_id, GroupId(2));
854		assert_eq!(summary.validity_votes, 1);
855	}
856
857	#[test]
858	fn candidate_vote_gives_summary() {
859		let context = TestContext {
860			authorities: {
861				let mut map = HashMap::new();
862				map.insert(AuthorityId(1), GroupId(2));
863				map.insert(AuthorityId(2), GroupId(2));
864				map
865			},
866		};
867
868		let mut table = Table::new();
869		let statement = SignedStatement {
870			statement: Statement::Seconded(Candidate(2, 100)),
871			signature: Signature(1),
872			sender: AuthorityId(1),
873		};
874		let candidate_digest = Digest(100);
875
876		table.import_statement(&context, GroupId(2), statement);
877		assert!(!table.detected_misbehavior.contains_key(&AuthorityId(1)));
878
879		let vote = SignedStatement {
880			statement: Statement::Valid(candidate_digest),
881			signature: Signature(2),
882			sender: AuthorityId(2),
883		};
884
885		let summary = table
886			.import_statement(&context, GroupId(2), vote)
887			.expect("candidate vote to give summary");
888
889		assert!(!table.detected_misbehavior.contains_key(&AuthorityId(2)));
890
891		assert_eq!(summary.candidate, Digest(100));
892		assert_eq!(summary.group_id, GroupId(2));
893		assert_eq!(summary.validity_votes, 2);
894	}
895}
polkadot_statement_table/generic.rs

polkadot_statement_table/
generic.rs
