use std::{
collections::hash_map::{self, Entry, HashMap},
fmt::Debug,
hash::Hash,
};
use polkadot_primitives::{
effective_minimum_backing_votes, ValidatorSignature,
ValidityAttestation as PrimitiveValidityAttestation,
};
use codec::{Decode, Encode};
const LOG_TARGET: &str = "parachain::statement-table";
pub trait Context {
type AuthorityId: Debug + Hash + Eq + Clone;
type Digest: Debug + Hash + Eq + Clone;
type GroupId: Debug + Hash + Ord + Eq + Clone;
type Signature: Debug + Eq + Clone;
type Candidate: Debug + Ord + Eq + Clone;
fn candidate_digest(candidate: &Self::Candidate) -> Self::Digest;
fn is_member_of(&self, authority: &Self::AuthorityId, group: &Self::GroupId) -> bool;
fn get_group_size(&self, group: &Self::GroupId) -> Option<usize>;
}
#[derive(PartialEq, Eq, Debug, Clone, Encode, Decode)]
pub enum Statement<Candidate, Digest> {
#[codec(index = 1)]
Seconded(Candidate),
#[codec(index = 2)]
Valid(Digest),
}
#[derive(PartialEq, Eq, Debug, Clone, Encode, Decode)]
pub struct SignedStatement<Candidate, Digest, AuthorityId, Signature> {
pub statement: Statement<Candidate, Digest>,
pub signature: Signature,
pub sender: AuthorityId,
}
#[derive(PartialEq, Eq, Debug, Clone)]
pub enum ValidityDoubleVote<Candidate, Digest, Signature> {
IssuedAndValidity((Candidate, Signature), (Digest, Signature)),
}
impl<Candidate, Digest, Signature> ValidityDoubleVote<Candidate, Digest, Signature> {
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)) =>
((Statement::Seconded(c), s1), (Statement::Valid(d), s2)),
}
}
}
#[derive(PartialEq, Eq, Debug, Clone)]
pub enum DoubleSign<Candidate, Digest, Signature> {
Seconded(Candidate, Signature, Signature),
Validity(Digest, Signature, Signature),
}
impl<Candidate, Digest, Signature> DoubleSign<Candidate, Digest, Signature> {
pub fn deconstruct(self) -> (Statement<Candidate, Digest>, Signature, Signature) {
match self {
Self::Seconded(candidate, a, b) => (Statement::Seconded(candidate), a, b),
Self::Validity(digest, a, b) => (Statement::Valid(digest), a, b),
}
}
}
#[derive(PartialEq, Eq, Debug, Clone)]
pub struct UnauthorizedStatement<Candidate, Digest, AuthorityId, Signature> {
pub statement: SignedStatement<Candidate, Digest, AuthorityId, Signature>,
}
#[derive(PartialEq, Eq, Debug, Clone)]
pub enum Misbehavior<Candidate, Digest, AuthorityId, Signature> {
ValidityDoubleVote(ValidityDoubleVote<Candidate, Digest, Signature>),
UnauthorizedStatement(UnauthorizedStatement<Candidate, Digest, AuthorityId, Signature>),
DoubleSign(DoubleSign<Candidate, Digest, Signature>),
}
pub type MisbehaviorFor<Ctx> = Misbehavior<
<Ctx as Context>::Candidate,
<Ctx as Context>::Digest,
<Ctx as Context>::AuthorityId,
<Ctx as Context>::Signature,
>;
#[derive(Clone, PartialEq, Eq)]
enum ValidityVote<Signature: Eq + Clone> {
Issued(Signature),
Valid(Signature),
}
#[derive(Clone, PartialEq, Eq, Debug)]
pub struct Summary<Digest, Group> {
pub candidate: Digest,
pub group_id: Group,
pub validity_votes: usize,
}
#[derive(Clone, PartialEq, Decode, Encode)]
pub enum ValidityAttestation<Signature> {
Implicit(Signature),
Explicit(Signature),
}
impl Into<PrimitiveValidityAttestation> for ValidityAttestation<ValidatorSignature> {
fn into(self) -> PrimitiveValidityAttestation {
match self {
Self::Implicit(s) => PrimitiveValidityAttestation::Implicit(s),
Self::Explicit(s) => PrimitiveValidityAttestation::Explicit(s),
}
}
}
#[derive(Clone, PartialEq, Decode, Encode)]
pub struct AttestedCandidate<Group, Candidate, AuthorityId, Signature> {
pub group_id: Group,
pub candidate: Candidate,
pub validity_votes: Vec<(AuthorityId, ValidityAttestation<Signature>)>,
}
pub struct CandidateData<Ctx: Context> {
group_id: Ctx::GroupId,
candidate: Ctx::Candidate,
validity_votes: HashMap<Ctx::AuthorityId, ValidityVote<Ctx::Signature>>,
}
impl<Ctx: Context> CandidateData<Ctx> {
pub fn attested(
&self,
validity_threshold: usize,
) -> Option<AttestedCandidate<Ctx::GroupId, Ctx::Candidate, Ctx::AuthorityId, Ctx::Signature>>
{
let valid_votes = self.validity_votes.len();
if valid_votes < validity_threshold {
return None
}
let validity_votes = self
.validity_votes
.iter()
.map(|(a, v)| match *v {
ValidityVote::Valid(ref s) => (a.clone(), ValidityAttestation::Explicit(s.clone())),
ValidityVote::Issued(ref s) =>
(a.clone(), ValidityAttestation::Implicit(s.clone())),
})
.collect();
Some(AttestedCandidate {
group_id: self.group_id.clone(),
candidate: self.candidate.clone(),
validity_votes,
})
}
fn summary(&self, digest: Ctx::Digest) -> Summary<Ctx::Digest, Ctx::GroupId> {
Summary {
candidate: digest,
group_id: self.group_id.clone(),
validity_votes: self.validity_votes.len(),
}
}
}
struct AuthorityData<Ctx: Context> {
proposals: Vec<(Ctx::Digest, Ctx::Signature)>,
}
impl<Ctx: Context> Default for AuthorityData<Ctx> {
fn default() -> Self {
AuthorityData { proposals: Vec::new() }
}
}
pub type ImportResult<Ctx> = Result<
Option<Summary<<Ctx as Context>::Digest, <Ctx as Context>::GroupId>>,
MisbehaviorFor<Ctx>,
>;
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>>,
}
impl<Ctx: Context> Table<Ctx> {
pub fn new() -> Self {
Table {
authority_data: HashMap::default(),
detected_misbehavior: HashMap::default(),
candidate_votes: HashMap::default(),
}
}
pub fn attested_candidate(
&self,
digest: &Ctx::Digest,
context: &Ctx,
minimum_backing_votes: u32,
) -> Option<AttestedCandidate<Ctx::GroupId, Ctx::Candidate, Ctx::AuthorityId, Ctx::Signature>>
{
self.candidate_votes.get(digest).and_then(|data| {
let v_threshold = context.get_group_size(&data.group_id).map_or(usize::MAX, |len| {
effective_minimum_backing_votes(len, minimum_backing_votes)
});
data.attested(v_threshold)
})
}
pub fn import_statement(
&mut self,
context: &Ctx,
group_id: Ctx::GroupId,
statement: SignedStatement<Ctx::Candidate, Ctx::Digest, Ctx::AuthorityId, Ctx::Signature>,
) -> Option<Summary<Ctx::Digest, Ctx::GroupId>> {
let SignedStatement { statement, signature, sender: signer } = statement;
let res = match statement {
Statement::Seconded(candidate) =>
self.import_candidate(context, signer.clone(), candidate, signature, group_id),
Statement::Valid(digest) =>
self.validity_vote(context, signer.clone(), digest, ValidityVote::Valid(signature)),
};
match res {
Ok(maybe_summary) => maybe_summary,
Err(misbehavior) => {
self.detected_misbehavior.entry(signer).or_default().push(misbehavior);
None
},
}
}
pub fn get_candidate(&self, digest: &Ctx::Digest) -> Option<&Ctx::Candidate> {
self.candidate_votes.get(digest).map(|d| &d.candidate)
}
pub fn get_misbehavior(&self) -> &HashMap<Ctx::AuthorityId, Vec<MisbehaviorFor<Ctx>>> {
&self.detected_misbehavior
}
pub fn drain_misbehaviors(&mut self) -> DrainMisbehaviors<'_, Ctx> {
self.detected_misbehavior.drain().into()
}
fn import_candidate(
&mut self,
context: &Ctx,
authority: Ctx::AuthorityId,
candidate: Ctx::Candidate,
signature: Ctx::Signature,
group: Ctx::GroupId,
) -> ImportResult<Ctx> {
if !context.is_member_of(&authority, &group) {
gum::debug!(target: LOG_TARGET, authority = ?authority, group = ?group, "New `Misbehavior::UnauthorizedStatement`, candidate backed by validator that doesn't belong to expected group" );
return Err(Misbehavior::UnauthorizedStatement(UnauthorizedStatement {
statement: SignedStatement {
signature,
statement: Statement::Seconded(candidate),
sender: authority,
},
}))
}
let digest = Ctx::candidate_digest(&candidate);
let new_proposal = match self.authority_data.entry(authority.clone()) {
Entry::Occupied(mut occ) => {
let existing = occ.get_mut();
if existing.proposals.iter().any(|(ref od, _)| od == &digest) {
false
} else {
existing.proposals.push((digest.clone(), signature.clone()));
true
}
},
Entry::Vacant(vacant) => {
vacant
.insert(AuthorityData { proposals: vec![(digest.clone(), signature.clone())] });
true
},
};
if new_proposal {
self.candidate_votes
.entry(digest.clone())
.or_insert_with(move || CandidateData {
group_id: group,
candidate,
validity_votes: HashMap::new(),
});
}
self.validity_vote(context, authority, digest, ValidityVote::Issued(signature))
}
fn validity_vote(
&mut self,
context: &Ctx,
from: Ctx::AuthorityId,
digest: Ctx::Digest,
vote: ValidityVote<Ctx::Signature>,
) -> ImportResult<Ctx> {
let votes = match self.candidate_votes.get_mut(&digest) {
None => return Ok(None),
Some(votes) => votes,
};
if !context.is_member_of(&from, &votes.group_id) {
let sig = match vote {
ValidityVote::Valid(s) => s,
ValidityVote::Issued(s) => s,
};
return Err(Misbehavior::UnauthorizedStatement(UnauthorizedStatement {
statement: SignedStatement {
signature: sig,
sender: from,
statement: Statement::Valid(digest),
},
}))
}
match votes.validity_votes.entry(from.clone()) {
Entry::Occupied(occ) => {
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) {
(ValidityVote::Issued(iss), ValidityVote::Valid(good)) |
(ValidityVote::Valid(good), ValidityVote::Issued(iss)) =>
make_vdv(ValidityDoubleVote::IssuedAndValidity(
(votes.candidate.clone(), iss),
(digest, good),
)),
(ValidityVote::Issued(a), ValidityVote::Issued(b)) =>
make_ds(DoubleSign::Seconded(votes.candidate.clone(), a, b)),
(ValidityVote::Valid(a), ValidityVote::Valid(b)) =>
make_ds(DoubleSign::Validity(digest, a, b)),
})
} else {
Ok(None)
}
},
Entry::Vacant(vacant) => {
vacant.insert(vote);
},
}
Ok(Some(votes.summary(digest)))
}
}
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 {
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> {
self.maybe_item().or_else(|| {
self.in_progress = self.drain.next().map(Into::into);
self.maybe_item()
})
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::collections::HashMap;
#[derive(Debug, Copy, Clone, Hash, PartialEq, Eq)]
struct AuthorityId(usize);
#[derive(Debug, Copy, Clone, Hash, PartialOrd, Ord, PartialEq, Eq)]
struct GroupId(usize);
#[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 {
authorities: HashMap<AuthorityId, GroupId>,
}
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 is_member_of(&self, authority: &AuthorityId, group: &GroupId) -> bool {
self.authorities.get(authority).map(|v| v == group).unwrap_or(false)
}
fn get_group_size(&self, group: &Self::GroupId) -> Option<usize> {
let count = self.authorities.values().filter(|g| *g == group).count();
if count == 0 {
None
} else {
Some(count)
}
}
}
#[test]
fn submitting_two_candidates_can_be_allowed() {
let context = TestContext {
authorities: {
let mut map = HashMap::new();
map.insert(AuthorityId(1), GroupId(2));
map
},
};
let mut table = Table::new();
let statement_a = SignedStatement {
statement: Statement::Seconded(Candidate(2, 100)),
signature: Signature(1),
sender: AuthorityId(1),
};
let statement_b = SignedStatement {
statement: Statement::Seconded(Candidate(2, 999)),
signature: Signature(1),
sender: AuthorityId(1),
};
table.import_statement(&context, GroupId(2), statement_a);
assert!(!table.detected_misbehavior.contains_key(&AuthorityId(1)));
table.import_statement(&context, GroupId(2), statement_b);
assert!(!table.detected_misbehavior.contains_key(&AuthorityId(1)));
}
#[test]
fn submitting_candidate_from_wrong_group_is_misbehavior() {
let context = TestContext {
authorities: {
let mut map = HashMap::new();
map.insert(AuthorityId(1), GroupId(3));
map
},
};
let mut table = Table::new();
let statement = SignedStatement {
statement: Statement::Seconded(Candidate(2, 100)),
signature: Signature(1),
sender: AuthorityId(1),
};
table.import_statement(&context, GroupId(2), statement);
assert_eq!(
table.detected_misbehavior[&AuthorityId(1)][0],
Misbehavior::UnauthorizedStatement(UnauthorizedStatement {
statement: SignedStatement {
statement: Statement::Seconded(Candidate(2, 100)),
signature: Signature(1),
sender: AuthorityId(1),
},
})
);
}
#[test]
fn unauthorized_votes() {
let context = TestContext {
authorities: {
let mut map = HashMap::new();
map.insert(AuthorityId(1), GroupId(2));
map.insert(AuthorityId(2), GroupId(3));
map
},
};
let mut table = Table::new();
let candidate_a = SignedStatement {
statement: Statement::Seconded(Candidate(2, 100)),
signature: Signature(1),
sender: AuthorityId(1),
};
let candidate_a_digest = Digest(100);
table.import_statement(&context, GroupId(2), candidate_a);
assert!(!table.detected_misbehavior.contains_key(&AuthorityId(1)));
assert!(!table.detected_misbehavior.contains_key(&AuthorityId(2)));
let bad_validity_vote = SignedStatement {
statement: Statement::Valid(candidate_a_digest),
signature: Signature(2),
sender: AuthorityId(2),
};
table.import_statement(&context, GroupId(3), bad_validity_vote);
assert_eq!(
table.detected_misbehavior[&AuthorityId(2)][0],
Misbehavior::UnauthorizedStatement(UnauthorizedStatement {
statement: SignedStatement {
statement: Statement::Valid(candidate_a_digest),
signature: Signature(2),
sender: AuthorityId(2),
},
})
);
}
#[test]
fn candidate_double_signature_is_misbehavior() {
let context = TestContext {
authorities: {
let mut map = HashMap::new();
map.insert(AuthorityId(1), GroupId(2));
map.insert(AuthorityId(2), GroupId(2));
map
},
};
let mut table = Table::new();
let statement = SignedStatement {
statement: Statement::Seconded(Candidate(2, 100)),
signature: Signature(1),
sender: AuthorityId(1),
};
table.import_statement(&context, GroupId(2), statement);
assert!(!table.detected_misbehavior.contains_key(&AuthorityId(1)));
let invalid_statement = SignedStatement {
statement: Statement::Seconded(Candidate(2, 100)),
signature: Signature(999),
sender: AuthorityId(1),
};
table.import_statement(&context, GroupId(2), invalid_statement);
assert!(table.detected_misbehavior.contains_key(&AuthorityId(1)));
}
#[test]
fn issue_and_vote_is_misbehavior() {
let context = TestContext {
authorities: {
let mut map = HashMap::new();
map.insert(AuthorityId(1), GroupId(2));
map
},
};
let mut table = Table::new();
let statement = SignedStatement {
statement: Statement::Seconded(Candidate(2, 100)),
signature: Signature(1),
sender: AuthorityId(1),
};
let candidate_digest = Digest(100);
table.import_statement(&context, GroupId(2), statement);
assert!(!table.detected_misbehavior.contains_key(&AuthorityId(1)));
let extra_vote = SignedStatement {
statement: Statement::Valid(candidate_digest),
signature: Signature(1),
sender: AuthorityId(1),
};
table.import_statement(&context, GroupId(2), extra_vote);
assert_eq!(
table.detected_misbehavior[&AuthorityId(1)][0],
Misbehavior::ValidityDoubleVote(ValidityDoubleVote::IssuedAndValidity(
(Candidate(2, 100), Signature(1)),
(Digest(100), Signature(1)),
))
);
}
#[test]
fn candidate_attested_works() {
let validity_threshold = 6;
let mut candidate = CandidateData::<TestContext> {
group_id: GroupId(4),
candidate: Candidate(4, 12345),
validity_votes: HashMap::new(),
};
assert!(candidate.attested(validity_threshold).is_none());
for i in 0..validity_threshold {
candidate
.validity_votes
.insert(AuthorityId(i + 100), ValidityVote::Valid(Signature(i + 100)));
}
assert!(candidate.attested(validity_threshold).is_some());
candidate.validity_votes.insert(
AuthorityId(validity_threshold + 100),
ValidityVote::Valid(Signature(validity_threshold + 100)),
);
assert!(candidate.attested(validity_threshold).is_some());
}
#[test]
fn includability_works() {
let context = TestContext {
authorities: {
let mut map = HashMap::new();
map.insert(AuthorityId(1), GroupId(2));
map.insert(AuthorityId(2), GroupId(2));
map.insert(AuthorityId(3), GroupId(2));
map
},
};
let mut table = Table::new();
let statement = SignedStatement {
statement: Statement::Seconded(Candidate(2, 100)),
signature: Signature(1),
sender: AuthorityId(1),
};
let candidate_digest = Digest(100);
table.import_statement(&context, GroupId(2), statement);
assert!(!table.detected_misbehavior.contains_key(&AuthorityId(1)));
assert!(table.attested_candidate(&candidate_digest, &context, 2).is_none());
let vote = SignedStatement {
statement: Statement::Valid(candidate_digest),
signature: Signature(2),
sender: AuthorityId(2),
};
table.import_statement(&context, GroupId(2), vote);
assert!(!table.detected_misbehavior.contains_key(&AuthorityId(2)));
assert!(table.attested_candidate(&candidate_digest, &context, 2).is_some());
}
#[test]
fn candidate_import_gives_summary() {
let context = TestContext {
authorities: {
let mut map = HashMap::new();
map.insert(AuthorityId(1), GroupId(2));
map
},
};
let mut table = Table::new();
let statement = SignedStatement {
statement: Statement::Seconded(Candidate(2, 100)),
signature: Signature(1),
sender: AuthorityId(1),
};
let summary = table
.import_statement(&context, GroupId(2), statement)
.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();
map.insert(AuthorityId(1), GroupId(2));
map.insert(AuthorityId(2), GroupId(2));
map
},
};
let mut table = Table::new();
let statement = SignedStatement {
statement: Statement::Seconded(Candidate(2, 100)),
signature: Signature(1),
sender: AuthorityId(1),
};
let candidate_digest = Digest(100);
table.import_statement(&context, GroupId(2), statement);
assert!(!table.detected_misbehavior.contains_key(&AuthorityId(1)));
let vote = SignedStatement {
statement: Statement::Valid(candidate_digest),
signature: Signature(2),
sender: AuthorityId(2),
};
let summary = table
.import_statement(&context, GroupId(2), vote)
.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);
}
}