referrerpolicy=no-referrer-when-downgrade

bp_header_chain/justification/verification/
mod.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 checking GRANDPA Finality Proofs.
18
19pub mod equivocation;
20pub mod optimizer;
21pub mod strict;
22
23use crate::{justification::GrandpaJustification, AuthoritySet};
24
25use bp_runtime::HeaderId;
26use finality_grandpa::voter_set::VoterSet;
27use sp_consensus_grandpa::{AuthorityId, AuthoritySignature, SetId};
28use sp_runtime::{traits::Header as HeaderT, RuntimeDebug};
29use sp_std::{
30	collections::{
31		btree_map::{
32			BTreeMap,
33			Entry::{Occupied, Vacant},
34		},
35		btree_set::BTreeSet,
36	},
37	prelude::*,
38	vec,
39	vec::Vec,
40};
41
42type SignedPrecommit<Header> = finality_grandpa::SignedPrecommit<
43	<Header as HeaderT>::Hash,
44	<Header as HeaderT>::Number,
45	AuthoritySignature,
46	AuthorityId,
47>;
48
49/// Votes ancestries with useful methods.
50#[derive(RuntimeDebug)]
51pub struct AncestryChain<Header: HeaderT> {
52	/// We expect all forks in the ancestry chain to be descendants of base.
53	base: HeaderId<Header::Hash, Header::Number>,
54	/// Header hash => parent header hash mapping.
55	parents: BTreeMap<Header::Hash, Header::Hash>,
56	/// Hashes of headers that were not visited by `ancestry()`.
57	unvisited: BTreeSet<Header::Hash>,
58}
59
60impl<Header: HeaderT> AncestryChain<Header> {
61	/// Creates a new instance of `AncestryChain` starting from a `GrandpaJustification`.
62	///
63	/// Returns the `AncestryChain` and a `Vec` containing the `votes_ancestries` entries
64	/// that were ignored when creating it, because they are duplicates.
65	pub fn new(
66		justification: &GrandpaJustification<Header>,
67	) -> (AncestryChain<Header>, Vec<usize>) {
68		let mut parents = BTreeMap::new();
69		let mut unvisited = BTreeSet::new();
70		let mut ignored_idxs = Vec::new();
71		for (idx, ancestor) in justification.votes_ancestries.iter().enumerate() {
72			let hash = ancestor.hash();
73			match parents.entry(hash) {
74				Occupied(_) => {
75					ignored_idxs.push(idx);
76				},
77				Vacant(entry) => {
78					entry.insert(*ancestor.parent_hash());
79					unvisited.insert(hash);
80				},
81			}
82		}
83		(AncestryChain { base: justification.commit_target_id(), parents, unvisited }, ignored_idxs)
84	}
85
86	/// Returns the hash of a block's parent if the block is present in the ancestry.
87	pub fn parent_hash_of(&self, hash: &Header::Hash) -> Option<&Header::Hash> {
88		self.parents.get(hash)
89	}
90
91	/// Returns a route if the precommit target block is a descendant of the `base` block.
92	pub fn ancestry(
93		&self,
94		precommit_target_hash: &Header::Hash,
95		precommit_target_number: &Header::Number,
96	) -> Option<Vec<Header::Hash>> {
97		if precommit_target_number < &self.base.number() {
98			return None
99		}
100
101		let mut route = vec![];
102		let mut current_hash = *precommit_target_hash;
103		loop {
104			if current_hash == self.base.hash() {
105				break
106			}
107
108			current_hash = match self.parent_hash_of(&current_hash) {
109				Some(parent_hash) => {
110					let is_visited_before = self.unvisited.get(&current_hash).is_none();
111					if is_visited_before {
112						// If the current header has been visited in a previous call, it is a
113						// descendent of `base` (we assume that the previous call was successful).
114						return Some(route)
115					}
116					route.push(current_hash);
117
118					*parent_hash
119				},
120				None => return None,
121			};
122		}
123
124		Some(route)
125	}
126
127	fn mark_route_as_visited(&mut self, route: Vec<Header::Hash>) {
128		for hash in route {
129			self.unvisited.remove(&hash);
130		}
131	}
132
133	fn is_fully_visited(&self) -> bool {
134		self.unvisited.is_empty()
135	}
136}
137
138/// Justification verification error.
139#[derive(Eq, RuntimeDebug, PartialEq)]
140pub enum Error {
141	/// Could not convert `AuthorityList` to `VoterSet`.
142	InvalidAuthorityList,
143	/// Justification is finalizing unexpected header.
144	InvalidJustificationTarget,
145	/// The justification contains duplicate headers in its `votes_ancestries` field.
146	DuplicateVotesAncestries,
147	/// Error validating a precommit
148	Precommit(PrecommitError),
149	/// The cumulative weight of all votes in the justification is not enough to justify commit
150	/// header finalization.
151	TooLowCumulativeWeight,
152	/// The justification contains extra (unused) headers in its `votes_ancestries` field.
153	RedundantVotesAncestries,
154}
155
156/// Justification verification error.
157#[derive(Eq, RuntimeDebug, PartialEq)]
158pub enum PrecommitError {
159	/// Justification contains redundant votes.
160	RedundantAuthorityVote,
161	/// Justification contains unknown authority precommit.
162	UnknownAuthorityVote,
163	/// Justification contains duplicate authority precommit.
164	DuplicateAuthorityVote,
165	/// The authority has provided an invalid signature.
166	InvalidAuthoritySignature,
167	/// The justification contains precommit for header that is not a descendant of the commit
168	/// header.
169	UnrelatedAncestryVote,
170}
171
172/// The context needed for validating GRANDPA finality proofs.
173#[derive(RuntimeDebug)]
174pub struct JustificationVerificationContext {
175	/// The authority set used to verify the justification.
176	pub voter_set: VoterSet<AuthorityId>,
177	/// The ID of the authority set used to verify the justification.
178	pub authority_set_id: SetId,
179}
180
181impl TryFrom<AuthoritySet> for JustificationVerificationContext {
182	type Error = Error;
183
184	fn try_from(authority_set: AuthoritySet) -> Result<Self, Self::Error> {
185		let voter_set =
186			VoterSet::new(authority_set.authorities).ok_or(Error::InvalidAuthorityList)?;
187		Ok(JustificationVerificationContext { voter_set, authority_set_id: authority_set.set_id })
188	}
189}
190
191enum IterationFlow {
192	Run,
193	Skip,
194}
195
196/// Verification callbacks.
197trait JustificationVerifier<Header: HeaderT> {
198	/// Called when there are duplicate headers in the votes ancestries.
199	fn process_duplicate_votes_ancestries(
200		&mut self,
201		duplicate_votes_ancestries: Vec<usize>,
202	) -> Result<(), Error>;
203
204	fn process_redundant_vote(
205		&mut self,
206		precommit_idx: usize,
207	) -> Result<IterationFlow, PrecommitError>;
208
209	fn process_known_authority_vote(
210		&mut self,
211		precommit_idx: usize,
212		signed: &SignedPrecommit<Header>,
213	) -> Result<IterationFlow, PrecommitError>;
214
215	fn process_unknown_authority_vote(
216		&mut self,
217		precommit_idx: usize,
218	) -> Result<(), PrecommitError>;
219
220	fn process_unrelated_ancestry_vote(
221		&mut self,
222		precommit_idx: usize,
223	) -> Result<IterationFlow, PrecommitError>;
224
225	fn process_invalid_signature_vote(
226		&mut self,
227		precommit_idx: usize,
228	) -> Result<(), PrecommitError>;
229
230	fn process_valid_vote(&mut self, signed: &SignedPrecommit<Header>);
231
232	/// Called when there are redundant headers in the votes ancestries.
233	fn process_redundant_votes_ancestries(
234		&mut self,
235		redundant_votes_ancestries: BTreeSet<Header::Hash>,
236	) -> Result<(), Error>;
237
238	fn verify_justification(
239		&mut self,
240		finalized_target: (Header::Hash, Header::Number),
241		context: &JustificationVerificationContext,
242		justification: &GrandpaJustification<Header>,
243	) -> Result<(), Error> {
244		// ensure that it is justification for the expected header
245		if (justification.commit.target_hash, justification.commit.target_number) !=
246			finalized_target
247		{
248			return Err(Error::InvalidJustificationTarget)
249		}
250
251		let threshold = context.voter_set.threshold().get();
252		let (mut chain, ignored_idxs) = AncestryChain::new(justification);
253		let mut signature_buffer = Vec::new();
254		let mut cumulative_weight = 0u64;
255
256		if !ignored_idxs.is_empty() {
257			self.process_duplicate_votes_ancestries(ignored_idxs)?;
258		}
259
260		for (precommit_idx, signed) in justification.commit.precommits.iter().enumerate() {
261			if cumulative_weight >= threshold {
262				let action =
263					self.process_redundant_vote(precommit_idx).map_err(Error::Precommit)?;
264				if matches!(action, IterationFlow::Skip) {
265					continue
266				}
267			}
268
269			// authority must be in the set
270			let authority_info = match context.voter_set.get(&signed.id) {
271				Some(authority_info) => {
272					// The implementer may want to do extra checks here.
273					// For example to see if the authority has already voted in the same round.
274					let action = self
275						.process_known_authority_vote(precommit_idx, signed)
276						.map_err(Error::Precommit)?;
277					if matches!(action, IterationFlow::Skip) {
278						continue
279					}
280
281					authority_info
282				},
283				None => {
284					self.process_unknown_authority_vote(precommit_idx).map_err(Error::Precommit)?;
285					continue
286				},
287			};
288
289			// all precommits must be descendants of the target block
290			let maybe_route =
291				chain.ancestry(&signed.precommit.target_hash, &signed.precommit.target_number);
292			if maybe_route.is_none() {
293				let action = self
294					.process_unrelated_ancestry_vote(precommit_idx)
295					.map_err(Error::Precommit)?;
296				if matches!(action, IterationFlow::Skip) {
297					continue
298				}
299			}
300
301			// verify authority signature
302			if !sp_consensus_grandpa::check_message_signature_with_buffer(
303				&finality_grandpa::Message::Precommit(signed.precommit.clone()),
304				&signed.id,
305				&signed.signature,
306				justification.round,
307				context.authority_set_id,
308				&mut signature_buffer,
309			) {
310				self.process_invalid_signature_vote(precommit_idx).map_err(Error::Precommit)?;
311				continue
312			}
313
314			// now we can count the vote since we know that it is valid
315			self.process_valid_vote(signed);
316			if let Some(route) = maybe_route {
317				chain.mark_route_as_visited(route);
318				cumulative_weight = cumulative_weight.saturating_add(authority_info.weight().get());
319			}
320		}
321
322		// check that the cumulative weight of validators that voted for the justification target
323		// (or one of its descendants) is larger than the required threshold.
324		if cumulative_weight < threshold {
325			return Err(Error::TooLowCumulativeWeight)
326		}
327
328		// check that there are no extra headers in the justification
329		if !chain.is_fully_visited() {
330			self.process_redundant_votes_ancestries(chain.unvisited)?;
331		}
332
333		Ok(())
334	}
335}