referrerpolicy=no-referrer-when-downgrade

bp_header_chain/
lib.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//! Defines traits which represent a common interface for Substrate pallets which want to
18//! incorporate bridge functionality.
19
20#![warn(missing_docs)]
21#![cfg_attr(not(feature = "std"), no_std)]
22
23use crate::justification::{
24	GrandpaJustification, JustificationVerificationContext, JustificationVerificationError,
25};
26use bp_runtime::{
27	BasicOperatingMode, BlockNumberOf, Chain, HashOf, HasherOf, HeaderOf, RawStorageProof,
28	StorageProofChecker, StorageProofError, UnderlyingChainProvider,
29};
30use codec::{Codec, Decode, DecodeWithMemTracking, Encode, EncodeLike, MaxEncodedLen};
31use core::{clone::Clone, cmp::Eq, default::Default, fmt::Debug};
32use frame_support::PalletError;
33use scale_info::TypeInfo;
34use serde::{Deserialize, Serialize};
35use sp_consensus_grandpa::{
36	AuthorityList, ConsensusLog, ScheduledChange, SetId, GRANDPA_ENGINE_ID,
37};
38use sp_runtime::{traits::Header as HeaderT, Digest, RuntimeDebug, SaturatedConversion};
39use sp_std::{boxed::Box, vec::Vec};
40
41pub use call_info::{BridgeGrandpaCall, BridgeGrandpaCallOf, SubmitFinalityProofInfo};
42
43mod call_info;
44
45pub mod justification;
46pub mod storage_keys;
47
48/// Header chain error.
49#[derive(
50	Clone, Decode, DecodeWithMemTracking, Encode, Eq, PartialEq, PalletError, Debug, TypeInfo,
51)]
52pub enum HeaderChainError {
53	/// Header with given hash is missing from the chain.
54	UnknownHeader,
55	/// Error generated by the `storage_proof` module.
56	StorageProof(StorageProofError),
57}
58
59/// Header data that we're storing on-chain.
60///
61/// Even though we may store full header, our applications (XCM) only use couple of header
62/// fields. Extracting those values makes on-chain storage and PoV smaller, which is good.
63#[derive(Clone, Decode, Encode, Eq, MaxEncodedLen, PartialEq, RuntimeDebug, TypeInfo)]
64pub struct StoredHeaderData<Number, Hash> {
65	/// Header number.
66	pub number: Number,
67	/// Header state root.
68	pub state_root: Hash,
69}
70
71/// Stored header data builder.
72pub trait StoredHeaderDataBuilder<Number, Hash> {
73	/// Build header data from self.
74	fn build(&self) -> StoredHeaderData<Number, Hash>;
75}
76
77impl<H: HeaderT> StoredHeaderDataBuilder<H::Number, H::Hash> for H {
78	fn build(&self) -> StoredHeaderData<H::Number, H::Hash> {
79		StoredHeaderData { number: *self.number(), state_root: *self.state_root() }
80	}
81}
82
83/// Substrate header chain, abstracted from the way it is stored.
84pub trait HeaderChain<C: Chain> {
85	/// Returns state (storage) root of given finalized header.
86	fn finalized_header_state_root(header_hash: HashOf<C>) -> Option<HashOf<C>>;
87
88	/// Get storage proof checker using finalized header.
89	fn verify_storage_proof(
90		header_hash: HashOf<C>,
91		storage_proof: RawStorageProof,
92	) -> Result<StorageProofChecker<HasherOf<C>>, HeaderChainError> {
93		let state_root = Self::finalized_header_state_root(header_hash)
94			.ok_or(HeaderChainError::UnknownHeader)?;
95		StorageProofChecker::new(state_root, storage_proof).map_err(HeaderChainError::StorageProof)
96	}
97}
98
99/// A type that can be used as a parameter in a dispatchable function.
100///
101/// When using `decl_module` all arguments for call functions must implement this trait.
102pub trait Parameter: Codec + EncodeLike + Clone + Eq + Debug + TypeInfo {}
103impl<T> Parameter for T where T: Codec + EncodeLike + Clone + Eq + Debug + TypeInfo {}
104
105/// A GRANDPA Authority List and ID.
106#[derive(
107	Default, Encode, Eq, Decode, DecodeWithMemTracking, RuntimeDebug, PartialEq, Clone, TypeInfo,
108)]
109#[cfg_attr(feature = "std", derive(Serialize, Deserialize))]
110pub struct AuthoritySet {
111	/// List of GRANDPA authorities for the current round.
112	pub authorities: AuthorityList,
113	/// Monotonic identifier of the current GRANDPA authority set.
114	pub set_id: SetId,
115}
116
117impl AuthoritySet {
118	/// Create a new GRANDPA Authority Set.
119	pub fn new(authorities: AuthorityList, set_id: SetId) -> Self {
120		Self { authorities, set_id }
121	}
122}
123
124/// Data required for initializing the GRANDPA bridge pallet.
125///
126/// The bridge needs to know where to start its sync from, and this provides that initial context.
127#[derive(
128	Default,
129	Encode,
130	Decode,
131	DecodeWithMemTracking,
132	RuntimeDebug,
133	PartialEq,
134	Eq,
135	Clone,
136	TypeInfo,
137	Serialize,
138	Deserialize,
139)]
140pub struct InitializationData<H: HeaderT> {
141	/// The header from which we should start syncing.
142	pub header: Box<H>,
143	/// The initial authorities of the pallet.
144	pub authority_list: AuthorityList,
145	/// The ID of the initial authority set.
146	pub set_id: SetId,
147	/// Pallet operating mode.
148	pub operating_mode: BasicOperatingMode,
149}
150
151/// Abstract finality proof that is justifying block finality.
152pub trait FinalityProof<Hash, Number>: Clone + Send + Sync + Debug {
153	/// Return hash of header that this proof is generated for.
154	fn target_header_hash(&self) -> Hash;
155
156	/// Return number of header that this proof is generated for.
157	fn target_header_number(&self) -> Number;
158}
159
160/// A trait that provides helper methods for querying the consensus log.
161pub trait ConsensusLogReader {
162	/// Returns true if digest contains item that schedules authorities set change.
163	fn schedules_authorities_change(digest: &Digest) -> bool;
164}
165
166/// A struct that provides helper methods for querying the GRANDPA consensus log.
167pub struct GrandpaConsensusLogReader<Number>(sp_std::marker::PhantomData<Number>);
168
169impl<Number: Codec> GrandpaConsensusLogReader<Number> {
170	/// Find and return scheduled (regular) change digest item.
171	pub fn find_scheduled_change(digest: &Digest) -> Option<ScheduledChange<Number>> {
172		use sp_runtime::generic::OpaqueDigestItemId;
173		let id = OpaqueDigestItemId::Consensus(&GRANDPA_ENGINE_ID);
174
175		let filter_log = |log: ConsensusLog<Number>| match log {
176			ConsensusLog::ScheduledChange(change) => Some(change),
177			_ => None,
178		};
179
180		// find the first consensus digest with the right ID which converts to
181		// the right kind of consensus log.
182		digest.convert_first(|l| l.try_to(id).and_then(filter_log))
183	}
184
185	/// Find and return forced change digest item. Or light client can't do anything
186	/// with forced changes, so we can't accept header with the forced change digest.
187	pub fn find_forced_change(digest: &Digest) -> Option<(Number, ScheduledChange<Number>)> {
188		// find the first consensus digest with the right ID which converts to
189		// the right kind of consensus log.
190		digest
191			.convert_first(|log| log.consensus_try_to(&GRANDPA_ENGINE_ID))
192			.and_then(|log| match log {
193				ConsensusLog::ForcedChange(delay, change) => Some((delay, change)),
194				_ => None,
195			})
196	}
197}
198
199impl<Number: Codec> ConsensusLogReader for GrandpaConsensusLogReader<Number> {
200	fn schedules_authorities_change(digest: &Digest) -> bool {
201		GrandpaConsensusLogReader::<Number>::find_scheduled_change(digest).is_some()
202	}
203}
204
205/// The finality-related info associated to a header.
206#[derive(Encode, Decode, DecodeWithMemTracking, Debug, PartialEq, Clone, TypeInfo)]
207pub struct HeaderFinalityInfo<FinalityProof, FinalityVerificationContext> {
208	/// The header finality proof.
209	pub finality_proof: FinalityProof,
210	/// The new verification context introduced by the header.
211	pub new_verification_context: Option<FinalityVerificationContext>,
212}
213
214/// Grandpa-related info associated to a header. This info can be saved to events.
215pub type StoredHeaderGrandpaInfo<Header> =
216	HeaderFinalityInfo<GrandpaJustification<Header>, AuthoritySet>;
217
218/// Processed Grandpa-related info associated to a header.
219pub type HeaderGrandpaInfo<Header> =
220	HeaderFinalityInfo<GrandpaJustification<Header>, JustificationVerificationContext>;
221
222impl<Header: HeaderT> TryFrom<StoredHeaderGrandpaInfo<Header>> for HeaderGrandpaInfo<Header> {
223	type Error = JustificationVerificationError;
224
225	fn try_from(grandpa_info: StoredHeaderGrandpaInfo<Header>) -> Result<Self, Self::Error> {
226		Ok(Self {
227			finality_proof: grandpa_info.finality_proof,
228			new_verification_context: match grandpa_info.new_verification_context {
229				Some(authority_set) => Some(authority_set.try_into()?),
230				None => None,
231			},
232		})
233	}
234}
235
236/// Helper trait for finding equivocations in finality proofs.
237pub trait FindEquivocations<FinalityProof, FinalityVerificationContext, EquivocationProof> {
238	/// The type returned when encountering an error while looking for equivocations.
239	type Error: Debug;
240
241	/// Find equivocations.
242	fn find_equivocations(
243		verification_context: &FinalityVerificationContext,
244		synced_proof: &FinalityProof,
245		source_proofs: &[FinalityProof],
246	) -> Result<Vec<EquivocationProof>, Self::Error>;
247}
248
249/// Substrate-based chain that is using direct GRANDPA finality.
250///
251/// Keep in mind that parachains are relying on relay chain GRANDPA, so they should not implement
252/// this trait.
253pub trait ChainWithGrandpa: Chain {
254	/// Name of the bridge GRANDPA pallet (used in `construct_runtime` macro call) that is deployed
255	/// at some other chain to bridge with this `ChainWithGrandpa`.
256	///
257	/// We assume that all chains that are bridging with this `ChainWithGrandpa` are using
258	/// the same name.
259	const WITH_CHAIN_GRANDPA_PALLET_NAME: &'static str;
260
261	/// Max number of GRANDPA authorities at the chain.
262	///
263	/// This is a strict constant. If bridged chain will have more authorities than that,
264	/// the GRANDPA bridge pallet may halt.
265	const MAX_AUTHORITIES_COUNT: u32;
266
267	/// Max reasonable number of headers in `votes_ancestries` vector of the GRANDPA justification.
268	///
269	/// This isn't a strict limit. The relay may submit justifications with more headers in its
270	/// ancestry and the pallet will accept such justification. The limit is only used to compute
271	/// maximal refund amount and submitting justifications which exceed the limit, may be costly
272	/// to submitter.
273	const REASONABLE_HEADERS_IN_JUSTIFICATION_ANCESTRY: u32;
274
275	/// Maximal size of the mandatory chain header. Mandatory header is the header that enacts new
276	/// GRANDPA authorities set (so it has large digest inside).
277	///
278	/// This isn't a strict limit. The relay may submit larger headers and the pallet will accept
279	/// the call. The limit is only used to compute maximal refund amount and doing calls which
280	/// exceed the limit, may be costly to submitter.
281	const MAX_MANDATORY_HEADER_SIZE: u32;
282
283	/// Average size of the chain header. We don't expect to see there headers that change GRANDPA
284	/// authorities set (GRANDPA will probably be able to finalize at least one additional header
285	/// per session on non test chains), so this is average size of headers that aren't changing the
286	/// set.
287	///
288	/// This isn't a strict limit. The relay may submit justifications with larger headers and the
289	/// pallet will accept the call. However, if the total size of all `submit_finality_proof`
290	/// arguments exceeds the maximal size, computed using this average size, relayer will only get
291	/// partial refund.
292	///
293	/// We expect some headers on production chains that are above this size. But they are rare and
294	/// if rellayer cares about its profitability, we expect it'll select other headers for
295	/// submission.
296	const AVERAGE_HEADER_SIZE: u32;
297}
298
299impl<T> ChainWithGrandpa for T
300where
301	T: Chain + UnderlyingChainProvider,
302	T::Chain: ChainWithGrandpa,
303{
304	const WITH_CHAIN_GRANDPA_PALLET_NAME: &'static str =
305		<T::Chain as ChainWithGrandpa>::WITH_CHAIN_GRANDPA_PALLET_NAME;
306	const MAX_AUTHORITIES_COUNT: u32 = <T::Chain as ChainWithGrandpa>::MAX_AUTHORITIES_COUNT;
307	const REASONABLE_HEADERS_IN_JUSTIFICATION_ANCESTRY: u32 =
308		<T::Chain as ChainWithGrandpa>::REASONABLE_HEADERS_IN_JUSTIFICATION_ANCESTRY;
309	const MAX_MANDATORY_HEADER_SIZE: u32 =
310		<T::Chain as ChainWithGrandpa>::MAX_MANDATORY_HEADER_SIZE;
311	const AVERAGE_HEADER_SIZE: u32 = <T::Chain as ChainWithGrandpa>::AVERAGE_HEADER_SIZE;
312}
313
314/// Result of checking maximal expected submit finality proof call weight and size.
315#[derive(Debug)]
316pub struct SubmitFinalityProofCallExtras {
317	/// If true, the call weight is larger than what we have assumed.
318	///
319	/// We have some assumptions about headers and justifications of the bridged chain.
320	/// We know that if our assumptions are correct, then the call must not have the
321	/// weight above some limit. The fee paid for weight above that limit, is never refunded.
322	pub is_weight_limit_exceeded: bool,
323	/// Extra size (in bytes) that we assume are included in the call.
324	///
325	/// We have some assumptions about headers and justifications of the bridged chain.
326	/// We know that if our assumptions are correct, then the call must not have the
327	/// weight above some limit. The fee paid for bytes above that limit, is never refunded.
328	pub extra_size: u32,
329	/// A flag that is true if the header is the mandatory header that enacts new
330	/// authorities set.
331	pub is_mandatory_finality_target: bool,
332}
333
334/// Checks whether the given `header` and its finality `proof` fit the maximal expected
335/// call limits (size and weight). The submission may be refunded sometimes (see pallet
336/// configuration for details), but it should fit some limits. If the call has some extra
337/// weight and/or size included, though, we won't refund it or refund will be partial.
338pub fn submit_finality_proof_limits_extras<C: ChainWithGrandpa>(
339	header: &C::Header,
340	proof: &justification::GrandpaJustification<C::Header>,
341) -> SubmitFinalityProofCallExtras {
342	// the `submit_finality_proof` call will reject justifications with invalid, duplicate,
343	// unknown and extra signatures. It'll also reject justifications with less than necessary
344	// signatures. So we do not care about extra weight because of additional signatures here.
345	let precommits_len = proof.commit.precommits.len().saturated_into();
346	let required_precommits = precommits_len;
347
348	// the weight check is simple - we assume that there are no more than the `limit`
349	// headers in the ancestry proof
350	let votes_ancestries_len: u32 = proof.votes_ancestries.len().saturated_into();
351	let is_weight_limit_exceeded =
352		votes_ancestries_len > C::REASONABLE_HEADERS_IN_JUSTIFICATION_ANCESTRY;
353
354	// check if the `finality_target` is a mandatory header. If so, we are ready to refund larger
355	// size
356	let is_mandatory_finality_target =
357		GrandpaConsensusLogReader::<BlockNumberOf<C>>::find_scheduled_change(header.digest())
358			.is_some();
359
360	// we can estimate extra call size easily, without any additional significant overhead
361	let actual_call_size: u32 =
362		header.encoded_size().saturating_add(proof.encoded_size()).saturated_into();
363	let max_expected_call_size = max_expected_submit_finality_proof_arguments_size::<C>(
364		is_mandatory_finality_target,
365		required_precommits,
366	);
367	let extra_size = actual_call_size.saturating_sub(max_expected_call_size);
368
369	SubmitFinalityProofCallExtras {
370		is_weight_limit_exceeded,
371		extra_size,
372		is_mandatory_finality_target,
373	}
374}
375
376/// Returns maximal expected size of `submit_finality_proof` call arguments.
377pub fn max_expected_submit_finality_proof_arguments_size<C: ChainWithGrandpa>(
378	is_mandatory_finality_target: bool,
379	precommits: u32,
380) -> u32 {
381	let max_expected_justification_size =
382		GrandpaJustification::<HeaderOf<C>>::max_reasonable_size::<C>(precommits);
383
384	// call arguments are header and justification
385	let max_expected_finality_target_size = if is_mandatory_finality_target {
386		C::MAX_MANDATORY_HEADER_SIZE
387	} else {
388		C::AVERAGE_HEADER_SIZE
389	};
390	max_expected_finality_target_size.saturating_add(max_expected_justification_size)
391}
392
393#[cfg(test)]
394mod tests {
395	use super::*;
396	use bp_runtime::ChainId;
397	use frame_support::weights::Weight;
398	use sp_runtime::{
399		testing::H256, traits::BlakeTwo256, DigestItem, MultiSignature, StateVersion,
400	};
401
402	struct TestChain;
403
404	impl Chain for TestChain {
405		const ID: ChainId = *b"test";
406
407		type BlockNumber = u32;
408		type Hash = H256;
409		type Hasher = BlakeTwo256;
410		type Header = sp_runtime::generic::Header<u32, BlakeTwo256>;
411		type AccountId = u64;
412		type Balance = u64;
413		type Nonce = u64;
414		type Signature = MultiSignature;
415
416		const STATE_VERSION: StateVersion = StateVersion::V1;
417
418		fn max_extrinsic_size() -> u32 {
419			0
420		}
421		fn max_extrinsic_weight() -> Weight {
422			Weight::zero()
423		}
424	}
425
426	impl ChainWithGrandpa for TestChain {
427		const WITH_CHAIN_GRANDPA_PALLET_NAME: &'static str = "Test";
428		const MAX_AUTHORITIES_COUNT: u32 = 128;
429		const REASONABLE_HEADERS_IN_JUSTIFICATION_ANCESTRY: u32 = 2;
430		const MAX_MANDATORY_HEADER_SIZE: u32 = 100_000;
431		const AVERAGE_HEADER_SIZE: u32 = 1_024;
432	}
433
434	#[test]
435	fn max_expected_submit_finality_proof_arguments_size_respects_mandatory_argument() {
436		assert!(
437			max_expected_submit_finality_proof_arguments_size::<TestChain>(true, 100) >
438				max_expected_submit_finality_proof_arguments_size::<TestChain>(false, 100),
439		);
440	}
441
442	#[test]
443	fn find_scheduled_change_works() {
444		let scheduled_change = ScheduledChange { next_authorities: vec![], delay: 0 };
445
446		// first
447		let mut digest = Digest::default();
448		digest.push(DigestItem::Consensus(
449			GRANDPA_ENGINE_ID,
450			ConsensusLog::ScheduledChange(scheduled_change.clone()).encode(),
451		));
452		assert_eq!(
453			GrandpaConsensusLogReader::find_scheduled_change(&digest),
454			Some(scheduled_change.clone())
455		);
456
457		// not first
458		let mut digest = Digest::default();
459		digest.push(DigestItem::Consensus(
460			GRANDPA_ENGINE_ID,
461			ConsensusLog::<u64>::OnDisabled(0).encode(),
462		));
463		digest.push(DigestItem::Consensus(
464			GRANDPA_ENGINE_ID,
465			ConsensusLog::ScheduledChange(scheduled_change.clone()).encode(),
466		));
467		assert_eq!(
468			GrandpaConsensusLogReader::find_scheduled_change(&digest),
469			Some(scheduled_change.clone())
470		);
471	}
472}