sp_consensus_beefy/
mmr.rs

1// This file is part of Substrate.
2
3// Copyright (C) Parity Technologies (UK) Ltd.
4// SPDX-License-Identifier: Apache-2.0
5
6// Licensed under the Apache License, Version 2.0 (the "License");
7// you may not use this file except in compliance with the License.
8// You may obtain a copy of the License at
9//
10// 	http://www.apache.org/licenses/LICENSE-2.0
11//
12// Unless required by applicable law or agreed to in writing, software
13// distributed under the License is distributed on an "AS IS" BASIS,
14// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15// See the License for the specific language governing permissions and
16// limitations under the License.
17
18//! BEEFY + MMR utilities.
19//!
20//! While BEEFY can be used completely independently as an additional consensus gadget,
21//! it is designed around a main use case of bridging standalone networks together.
22//! For that use case it's common to use some aggregated data structure (like MMR) to be
23//! used in conjunction with BEEFY, to be able to efficiently prove any past blockchain data.
24//!
25//! This module contains primitives used by Polkadot implementation of the BEEFY+MMR bridge,
26//! but we imagine they will be useful for other chains that either want to bridge with Polkadot
27//! or are completely standalone, but heavily inspired by Polkadot.
28
29use crate::{ecdsa_crypto::AuthorityId, ConsensusLog, MmrRootHash, BEEFY_ENGINE_ID};
30use alloc::vec::Vec;
31use codec::{Decode, Encode, MaxEncodedLen};
32use scale_info::TypeInfo;
33use sp_runtime::{
34	generic::OpaqueDigestItemId,
35	traits::{Block, Header},
36};
37
38/// A provider for extra data that gets added to the Mmr leaf
39pub trait BeefyDataProvider<ExtraData> {
40	/// Return a vector of bytes, ideally should be a merkle root hash
41	fn extra_data() -> ExtraData;
42}
43
44/// A default implementation for runtimes.
45impl BeefyDataProvider<Vec<u8>> for () {
46	fn extra_data() -> Vec<u8> {
47		Vec::new()
48	}
49}
50
51/// A standard leaf that gets added every block to the MMR constructed by Substrate's `pallet_mmr`.
52#[derive(Debug, PartialEq, Eq, Clone, Encode, Decode, TypeInfo)]
53pub struct MmrLeaf<BlockNumber, Hash, MerkleRoot, ExtraData> {
54	/// Version of the leaf format.
55	///
56	/// Can be used to enable future format migrations and compatibility.
57	/// See [`MmrLeafVersion`] documentation for details.
58	pub version: MmrLeafVersion,
59	/// Current block parent number and hash.
60	pub parent_number_and_hash: (BlockNumber, Hash),
61	/// A merkle root of the next BEEFY authority set.
62	pub beefy_next_authority_set: BeefyNextAuthoritySet<MerkleRoot>,
63	/// Arbitrary extra leaf data to be used by downstream pallets to include custom data in the
64	/// [`MmrLeaf`]
65	pub leaf_extra: ExtraData,
66}
67
68/// An MMR leaf versioning scheme.
69///
70/// Version is a single byte that consists of two components:
71/// - `major` - 3 bits
72/// - `minor` - 5 bits
73///
74/// Any change in encoding that adds new items to the structure is considered non-breaking, hence
75/// only requires an update of `minor` version. Any backward incompatible change (i.e. decoding to a
76/// previous leaf format fails) should be indicated with `major` version bump.
77///
78/// Given that adding new struct elements in SCALE is backward compatible (i.e. old format can be
79/// still decoded, the new fields will simply be ignored). We expect the major version to be bumped
80/// very rarely (hopefully never).
81#[derive(Debug, Default, PartialEq, Eq, Clone, Encode, Decode, TypeInfo)]
82pub struct MmrLeafVersion(u8);
83impl MmrLeafVersion {
84	/// Create new version object from `major` and `minor` components.
85	///
86	/// Panics if any of the component occupies more than 4 bits.
87	pub fn new(major: u8, minor: u8) -> Self {
88		if major > 0b111 || minor > 0b11111 {
89			panic!("Version components are too big.");
90		}
91		let version = (major << 5) + minor;
92		Self(version)
93	}
94
95	/// Split the version into `major` and `minor` sub-components.
96	pub fn split(&self) -> (u8, u8) {
97		let major = self.0 >> 5;
98		let minor = self.0 & 0b11111;
99		(major, minor)
100	}
101}
102
103/// Details of a BEEFY authority set.
104#[derive(Debug, Default, PartialEq, Eq, Clone, Encode, Decode, TypeInfo, MaxEncodedLen)]
105#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
106pub struct BeefyAuthoritySet<AuthoritySetCommitment> {
107	/// Id of the set.
108	///
109	/// Id is required to correlate BEEFY signed commitments with the validator set.
110	/// Light Client can easily verify that the commitment witness it is getting is
111	/// produced by the latest validator set.
112	pub id: crate::ValidatorSetId,
113	/// Number of validators in the set.
114	///
115	/// Some BEEFY Light Clients may use an interactive protocol to verify only a subset
116	/// of signatures. We put set length here, so that these clients can verify the minimal
117	/// number of required signatures.
118	pub len: u32,
119
120	/// Commitment(s) to BEEFY AuthorityIds.
121	///
122	/// This is used by Light Clients to confirm that the commitments are signed by the correct
123	/// validator set. Light Clients using interactive protocol, might verify only subset of
124	/// signatures, hence don't require the full list here (will receive inclusion proofs).
125	///
126	/// This could be Merkle Root Hash built from BEEFY ECDSA public keys and/or
127	/// polynomial commitment to the polynomial interpolating BLS public keys
128	/// which is used by APK proof based light clients to verify the validity
129	/// of aggregated BLS keys using APK proofs.
130	/// Multiple commitments can be tupled together.
131	pub keyset_commitment: AuthoritySetCommitment,
132}
133
134/// Details of the next BEEFY authority set.
135pub type BeefyNextAuthoritySet<MerkleRoot> = BeefyAuthoritySet<MerkleRoot>;
136
137/// Extract the MMR root hash from a digest in the given header, if it exists.
138pub fn find_mmr_root_digest<B: Block>(header: &B::Header) -> Option<MmrRootHash> {
139	let id = OpaqueDigestItemId::Consensus(&BEEFY_ENGINE_ID);
140
141	let filter = |log: ConsensusLog<AuthorityId>| match log {
142		ConsensusLog::MmrRoot(root) => Some(root),
143		_ => None,
144	};
145	header.digest().convert_first(|l| l.try_to(id).and_then(filter))
146}
147
148#[cfg(feature = "std")]
149pub use mmr_root_provider::MmrRootProvider;
150#[cfg(feature = "std")]
151mod mmr_root_provider {
152	use super::*;
153	use crate::{known_payloads, payload::PayloadProvider, Payload};
154	use alloc::sync::Arc;
155	use core::marker::PhantomData;
156	use sp_api::ProvideRuntimeApi;
157	use sp_mmr_primitives::MmrApi;
158	use sp_runtime::traits::NumberFor;
159
160	/// A [`crate::Payload`] provider where payload is Merkle Mountain Range root hash.
161	///
162	/// Encoded payload contains a [`crate::MmrRootHash`] type (i.e. 32-bytes hash).
163	pub struct MmrRootProvider<B, R> {
164		runtime: Arc<R>,
165		_phantom: PhantomData<B>,
166	}
167
168	impl<B, R> Clone for MmrRootProvider<B, R> {
169		fn clone(&self) -> Self {
170			Self { runtime: self.runtime.clone(), _phantom: PhantomData }
171		}
172	}
173
174	impl<B, R> MmrRootProvider<B, R>
175	where
176		B: Block,
177		R: ProvideRuntimeApi<B>,
178		R::Api: MmrApi<B, MmrRootHash, NumberFor<B>>,
179	{
180		/// Create new BEEFY Payload provider with MMR Root as payload.
181		pub fn new(runtime: Arc<R>) -> Self {
182			Self { runtime, _phantom: PhantomData }
183		}
184
185		/// Simple wrapper that gets MMR root from header digests or from client state.
186		fn mmr_root_from_digest_or_runtime(&self, header: &B::Header) -> Option<MmrRootHash> {
187			find_mmr_root_digest::<B>(header).or_else(|| {
188				self.runtime.runtime_api().mmr_root(header.hash()).ok().and_then(|r| r.ok())
189			})
190		}
191	}
192
193	impl<B: Block, R> PayloadProvider<B> for MmrRootProvider<B, R>
194	where
195		B: Block,
196		R: ProvideRuntimeApi<B>,
197		R::Api: MmrApi<B, MmrRootHash, NumberFor<B>>,
198	{
199		fn payload(&self, header: &B::Header) -> Option<Payload> {
200			self.mmr_root_from_digest_or_runtime(header).map(|mmr_root| {
201				Payload::from_single_entry(known_payloads::MMR_ROOT_ID, mmr_root.encode())
202			})
203		}
204	}
205}
206
207#[cfg(test)]
208mod tests {
209	use super::*;
210	use crate::H256;
211	use sp_runtime::{traits::BlakeTwo256, Digest, DigestItem, OpaqueExtrinsic};
212
213	#[test]
214	fn should_construct_version_correctly() {
215		let tests = vec![(0, 0, 0b00000000), (7, 2, 0b11100010), (7, 31, 0b11111111)];
216
217		for (major, minor, version) in tests {
218			let v = MmrLeafVersion::new(major, minor);
219			assert_eq!(v.encode(), vec![version], "Encoding does not match.");
220			assert_eq!(v.split(), (major, minor));
221		}
222	}
223
224	#[test]
225	#[should_panic]
226	fn should_panic_if_major_too_large() {
227		MmrLeafVersion::new(8, 0);
228	}
229
230	#[test]
231	#[should_panic]
232	fn should_panic_if_minor_too_large() {
233		MmrLeafVersion::new(0, 32);
234	}
235
236	#[test]
237	fn extract_mmr_root_digest() {
238		type Header = sp_runtime::generic::Header<u64, BlakeTwo256>;
239		type Block = sp_runtime::generic::Block<Header, OpaqueExtrinsic>;
240		let mut header = Header::new(
241			1u64,
242			Default::default(),
243			Default::default(),
244			Default::default(),
245			Digest::default(),
246		);
247
248		// verify empty digest shows nothing
249		assert!(find_mmr_root_digest::<Block>(&header).is_none());
250
251		let mmr_root_hash = H256::random();
252		header.digest_mut().push(DigestItem::Consensus(
253			BEEFY_ENGINE_ID,
254			ConsensusLog::<AuthorityId>::MmrRoot(mmr_root_hash).encode(),
255		));
256
257		// verify validator set is correctly extracted from digest
258		let extracted = find_mmr_root_digest::<Block>(&header);
259		assert_eq!(extracted, Some(mmr_root_hash));
260	}
261}
sp_consensus_beefy/mmr.rs

sp_consensus_beefy/
mmr.rs
