referrerpolicy=no-referrer-when-downgrade

bp_header_chain/justification/verification/
optimizer.rs

1// Copyright (C) Parity Technologies (UK) Ltd.
2// This file is part of Parity Bridges Common.
3
4// Parity Bridges Common 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// Parity Bridges Common 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 Parity Bridges Common.  If not, see <http://www.gnu.org/licenses/>.
16
17//! Logic for optimizing GRANDPA Finality Proofs.
18
19use crate::justification::{
20	verification::{Error, JustificationVerifier, PrecommitError},
21	GrandpaJustification,
22};
23
24use crate::justification::verification::{
25	IterationFlow, JustificationVerificationContext, SignedPrecommit,
26};
27use sp_consensus_grandpa::AuthorityId;
28use sp_runtime::traits::Header as HeaderT;
29use sp_std::{collections::btree_set::BTreeSet, prelude::*, vec, vec::Vec};
30
31// Verification callbacks for justification optimization.
32struct JustificationOptimizer<Header: HeaderT> {
33	votes: BTreeSet<AuthorityId>,
34
35	extra_precommits: Vec<usize>,
36	duplicate_votes_ancestries_idxs: Vec<usize>,
37	redundant_votes_ancestries: BTreeSet<Header::Hash>,
38}
39
40impl<Header: HeaderT> JustificationOptimizer<Header> {
41	fn optimize(self, justification: &mut GrandpaJustification<Header>) {
42		for invalid_precommit_idx in self.extra_precommits.into_iter().rev() {
43			justification.commit.precommits.remove(invalid_precommit_idx);
44		}
45		if !self.duplicate_votes_ancestries_idxs.is_empty() {
46			for idx in self.duplicate_votes_ancestries_idxs.iter().rev() {
47				justification.votes_ancestries.swap_remove(*idx);
48			}
49		}
50		if !self.redundant_votes_ancestries.is_empty() {
51			justification
52				.votes_ancestries
53				.retain(|header| !self.redundant_votes_ancestries.contains(&header.hash()))
54		}
55	}
56}
57
58impl<Header: HeaderT> JustificationVerifier<Header> for JustificationOptimizer<Header> {
59	fn process_duplicate_votes_ancestries(
60		&mut self,
61		duplicate_votes_ancestries: Vec<usize>,
62	) -> Result<(), Error> {
63		self.duplicate_votes_ancestries_idxs = duplicate_votes_ancestries.to_vec();
64		Ok(())
65	}
66
67	fn process_redundant_vote(
68		&mut self,
69		precommit_idx: usize,
70	) -> Result<IterationFlow, PrecommitError> {
71		self.extra_precommits.push(precommit_idx);
72		Ok(IterationFlow::Skip)
73	}
74
75	fn process_known_authority_vote(
76		&mut self,
77		precommit_idx: usize,
78		signed: &SignedPrecommit<Header>,
79	) -> Result<IterationFlow, PrecommitError> {
80		// Skip duplicate votes
81		if self.votes.contains(&signed.id) {
82			self.extra_precommits.push(precommit_idx);
83			return Ok(IterationFlow::Skip)
84		}
85
86		Ok(IterationFlow::Run)
87	}
88
89	fn process_unknown_authority_vote(
90		&mut self,
91		precommit_idx: usize,
92	) -> Result<(), PrecommitError> {
93		self.extra_precommits.push(precommit_idx);
94		Ok(())
95	}
96
97	fn process_unrelated_ancestry_vote(
98		&mut self,
99		precommit_idx: usize,
100	) -> Result<IterationFlow, PrecommitError> {
101		self.extra_precommits.push(precommit_idx);
102		Ok(IterationFlow::Skip)
103	}
104
105	fn process_invalid_signature_vote(
106		&mut self,
107		precommit_idx: usize,
108	) -> Result<(), PrecommitError> {
109		self.extra_precommits.push(precommit_idx);
110		Ok(())
111	}
112
113	fn process_valid_vote(&mut self, signed: &SignedPrecommit<Header>) {
114		self.votes.insert(signed.id.clone());
115	}
116
117	fn process_redundant_votes_ancestries(
118		&mut self,
119		redundant_votes_ancestries: BTreeSet<Header::Hash>,
120	) -> Result<(), Error> {
121		self.redundant_votes_ancestries = redundant_votes_ancestries;
122		Ok(())
123	}
124}
125
126/// Verify and optimize given justification by removing unknown and duplicate votes.
127pub fn verify_and_optimize_justification<Header: HeaderT>(
128	finalized_target: (Header::Hash, Header::Number),
129	context: &JustificationVerificationContext,
130	justification: &mut GrandpaJustification<Header>,
131) -> Result<(), Error> {
132	let mut optimizer = JustificationOptimizer {
133		votes: BTreeSet::new(),
134		extra_precommits: vec![],
135		duplicate_votes_ancestries_idxs: vec![],
136		redundant_votes_ancestries: Default::default(),
137	};
138	optimizer.verify_justification(finalized_target, context, justification)?;
139	optimizer.optimize(justification);
140
141	Ok(())
142}