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

polkadot_statement_table/
generic.rs
