1// Copyright (C) Parity Technologies (UK) Ltd.
2// This file is part of Parity Bridges Common.
34// 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.
89// 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.
1314// 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/>.
1617//! Logic for checking GRANDPA Finality Proofs.
1819pub mod equivocation;
20pub mod optimizer;
21pub mod strict;
2223use crate::{justification::GrandpaJustification, AuthoritySet};
2425use 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};
4142type SignedPrecommit<Header> = finality_grandpa::SignedPrecommit<
43 <Header as HeaderT>::Hash,
44 <Header as HeaderT>::Number,
45 AuthoritySignature,
46 AuthorityId,
47>;
4849/// 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.
53base: HeaderId<Header::Hash, Header::Number>,
54/// Header hash => parent header hash mapping.
55parents: BTreeMap<Header::Hash, Header::Hash>,
56/// Hashes of headers that were not visited by `ancestry()`.
57unvisited: BTreeSet<Header::Hash>,
58}
5960impl<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.
65pub fn new(
66 justification: &GrandpaJustification<Header>,
67 ) -> (AncestryChain<Header>, Vec<usize>) {
68let mut parents = BTreeMap::new();
69let mut unvisited = BTreeSet::new();
70let mut ignored_idxs = Vec::new();
71for (idx, ancestor) in justification.votes_ancestries.iter().enumerate() {
72let hash = ancestor.hash();
73match 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 }
8586/// Returns the hash of a block's parent if the block is present in the ancestry.
87pub fn parent_hash_of(&self, hash: &Header::Hash) -> Option<&Header::Hash> {
88self.parents.get(hash)
89 }
9091/// Returns a route if the precommit target block is a descendant of the `base` block.
92pub fn ancestry(
93&self,
94 precommit_target_hash: &Header::Hash,
95 precommit_target_number: &Header::Number,
96 ) -> Option<Vec<Header::Hash>> {
97if precommit_target_number < &self.base.number() {
98return None
99}
100101let mut route = vec![];
102let mut current_hash = *precommit_target_hash;
103loop {
104if current_hash == self.base.hash() {
105break
106}
107108 current_hash = match self.parent_hash_of(¤t_hash) {
109Some(parent_hash) => {
110let is_visited_before = self.unvisited.get(¤t_hash).is_none();
111if 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).
114return Some(route)
115 }
116 route.push(current_hash);
117118*parent_hash
119 },
120None => return None,
121 };
122 }
123124Some(route)
125 }
126127fn mark_route_as_visited(&mut self, route: Vec<Header::Hash>) {
128for hash in route {
129self.unvisited.remove(&hash);
130 }
131 }
132133fn is_fully_visited(&self) -> bool {
134self.unvisited.is_empty()
135 }
136}
137138/// Justification verification error.
139#[derive(Eq, RuntimeDebug, PartialEq)]
140pub enum Error {
141/// Could not convert `AuthorityList` to `VoterSet`.
142InvalidAuthorityList,
143/// Justification is finalizing unexpected header.
144InvalidJustificationTarget,
145/// The justification contains duplicate headers in its `votes_ancestries` field.
146DuplicateVotesAncestries,
147/// Error validating a precommit
148Precommit(PrecommitError),
149/// The cumulative weight of all votes in the justification is not enough to justify commit
150 /// header finalization.
151TooLowCumulativeWeight,
152/// The justification contains extra (unused) headers in its `votes_ancestries` field.
153RedundantVotesAncestries,
154}
155156/// Justification verification error.
157#[derive(Eq, RuntimeDebug, PartialEq)]
158pub enum PrecommitError {
159/// Justification contains redundant votes.
160RedundantAuthorityVote,
161/// Justification contains unknown authority precommit.
162UnknownAuthorityVote,
163/// Justification contains duplicate authority precommit.
164DuplicateAuthorityVote,
165/// The authority has provided an invalid signature.
166InvalidAuthoritySignature,
167/// The justification contains precommit for header that is not a descendant of the commit
168 /// header.
169UnrelatedAncestryVote,
170}
171172/// The context needed for validating GRANDPA finality proofs.
173#[derive(RuntimeDebug)]
174pub struct JustificationVerificationContext {
175/// The authority set used to verify the justification.
176pub voter_set: VoterSet<AuthorityId>,
177/// The ID of the authority set used to verify the justification.
178pub authority_set_id: SetId,
179}
180181impl TryFrom<AuthoritySet> for JustificationVerificationContext {
182type Error = Error;
183184fn try_from(authority_set: AuthoritySet) -> Result<Self, Self::Error> {
185let voter_set =
186 VoterSet::new(authority_set.authorities).ok_or(Error::InvalidAuthorityList)?;
187Ok(JustificationVerificationContext { voter_set, authority_set_id: authority_set.set_id })
188 }
189}
190191enum IterationFlow {
192 Run,
193 Skip,
194}
195196/// Verification callbacks.
197trait JustificationVerifier<Header: HeaderT> {
198/// Called when there are duplicate headers in the votes ancestries.
199fn process_duplicate_votes_ancestries(
200&mut self,
201 duplicate_votes_ancestries: Vec<usize>,
202 ) -> Result<(), Error>;
203204fn process_redundant_vote(
205&mut self,
206 precommit_idx: usize,
207 ) -> Result<IterationFlow, PrecommitError>;
208209fn process_known_authority_vote(
210&mut self,
211 precommit_idx: usize,
212 signed: &SignedPrecommit<Header>,
213 ) -> Result<IterationFlow, PrecommitError>;
214215fn process_unknown_authority_vote(
216&mut self,
217 precommit_idx: usize,
218 ) -> Result<(), PrecommitError>;
219220fn process_unrelated_ancestry_vote(
221&mut self,
222 precommit_idx: usize,
223 ) -> Result<IterationFlow, PrecommitError>;
224225fn process_invalid_signature_vote(
226&mut self,
227 precommit_idx: usize,
228 ) -> Result<(), PrecommitError>;
229230fn process_valid_vote(&mut self, signed: &SignedPrecommit<Header>);
231232/// Called when there are redundant headers in the votes ancestries.
233fn process_redundant_votes_ancestries(
234&mut self,
235 redundant_votes_ancestries: BTreeSet<Header::Hash>,
236 ) -> Result<(), Error>;
237238fn 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
245if (justification.commit.target_hash, justification.commit.target_number) !=
246 finalized_target
247 {
248return Err(Error::InvalidJustificationTarget)
249 }
250251let threshold = context.voter_set.threshold().get();
252let (mut chain, ignored_idxs) = AncestryChain::new(justification);
253let mut signature_buffer = Vec::new();
254let mut cumulative_weight = 0u64;
255256if !ignored_idxs.is_empty() {
257self.process_duplicate_votes_ancestries(ignored_idxs)?;
258 }
259260for (precommit_idx, signed) in justification.commit.precommits.iter().enumerate() {
261if cumulative_weight >= threshold {
262let action =
263self.process_redundant_vote(precommit_idx).map_err(Error::Precommit)?;
264if matches!(action, IterationFlow::Skip) {
265continue
266}
267 }
268269// authority must be in the set
270let authority_info = match context.voter_set.get(&signed.id) {
271Some(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.
274let action = self
275.process_known_authority_vote(precommit_idx, signed)
276 .map_err(Error::Precommit)?;
277if matches!(action, IterationFlow::Skip) {
278continue
279}
280281 authority_info
282 },
283None => {
284self.process_unknown_authority_vote(precommit_idx).map_err(Error::Precommit)?;
285continue
286},
287 };
288289// all precommits must be descendants of the target block
290let maybe_route =
291 chain.ancestry(&signed.precommit.target_hash, &signed.precommit.target_number);
292if maybe_route.is_none() {
293let action = self
294.process_unrelated_ancestry_vote(precommit_idx)
295 .map_err(Error::Precommit)?;
296if matches!(action, IterationFlow::Skip) {
297continue
298}
299 }
300301// verify authority signature
302if !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 ) {
310self.process_invalid_signature_vote(precommit_idx).map_err(Error::Precommit)?;
311continue
312}
313314// now we can count the vote since we know that it is valid
315self.process_valid_vote(signed);
316if 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 }
321322// 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.
324if cumulative_weight < threshold {
325return Err(Error::TooLowCumulativeWeight)
326 }
327328// check that there are no extra headers in the justification
329if !chain.is_fully_visited() {
330self.process_redundant_votes_ancestries(chain.unvisited)?;
331 }
332333Ok(())
334 }
335}