referrerpolicy=no-referrer-when-downgrade

pallet_session/historical/
mod.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//! An opt-in utility for tracking historical sessions in FRAME-session.
19//!
20//! This is generally useful when implementing blockchains that require accountable
21//! safety where validators from some amount f prior sessions must remain slashable.
22//!
23//! Rather than store the full session data for any given session, we instead commit
24//! to the roots of merkle tries containing the session data.
25//!
26//! These roots and proofs of inclusion can be generated at any time during the current session.
27//! Afterwards, the proofs can be fed to a consensus module when reporting misbehavior.
28
29pub mod offchain;
30pub mod onchain;
31mod shared;
32
33use alloc::vec::Vec;
34use codec::{Decode, Encode};
35use core::fmt::Debug;
36use sp_runtime::{
37	traits::{Convert, OpaqueKeys},
38	KeyTypeId,
39};
40use sp_session::{MembershipProof, ValidatorCount};
41use sp_staking::SessionIndex;
42use sp_trie::{
43	trie_types::{TrieDBBuilder, TrieDBMutBuilderV0},
44	LayoutV0, MemoryDB, RandomState, Recorder, StorageProof, Trie, TrieMut, TrieRecorder,
45};
46
47use frame_support::{
48	print,
49	traits::{KeyOwnerProofSystem, ValidatorSet, ValidatorSetWithIdentification},
50	Parameter,
51};
52
53const LOG_TARGET: &'static str = "runtime::historical";
54
55use crate::{self as pallet_session, Pallet as Session};
56
57pub use pallet::*;
58use sp_trie::{accessed_nodes_tracker::AccessedNodesTracker, recorder_ext::RecorderExt};
59
60#[frame_support::pallet]
61pub mod pallet {
62	use super::*;
63	use frame_support::pallet_prelude::*;
64
65	/// The in-code storage version.
66	const STORAGE_VERSION: StorageVersion = StorageVersion::new(1);
67
68	#[pallet::pallet]
69	#[pallet::storage_version(STORAGE_VERSION)]
70	pub struct Pallet<T>(_);
71
72	/// Config necessary for the historical pallet.
73	#[pallet::config]
74	pub trait Config: pallet_session::Config + frame_system::Config {
75		/// The overarching event type.
76		#[allow(deprecated)]
77		type RuntimeEvent: From<Event<Self>> + IsType<<Self as frame_system::Config>::RuntimeEvent>;
78
79		/// Full identification of the validator.
80		type FullIdentification: Parameter;
81
82		/// A conversion from validator ID to full identification.
83		///
84		/// This should contain any references to economic actors associated with the
85		/// validator, since they may be outdated by the time this is queried from a
86		/// historical trie.
87		///
88		/// It must return the identification for the current session index.
89		type FullIdentificationOf: Convert<Self::ValidatorId, Option<Self::FullIdentification>>;
90	}
91
92	/// Mapping from historical session indices to session-data root hash and validator count.
93	#[pallet::storage]
94	#[pallet::getter(fn historical_root)]
95	pub type HistoricalSessions<T: Config> =
96		StorageMap<_, Twox64Concat, SessionIndex, (T::Hash, ValidatorCount), OptionQuery>;
97
98	/// The range of historical sessions we store. [first, last)
99	#[pallet::storage]
100	pub type StoredRange<T> = StorageValue<_, (SessionIndex, SessionIndex), OptionQuery>;
101
102	#[pallet::event]
103	#[pallet::generate_deposit(pub(super) fn deposit_event)]
104	pub enum Event<T> {
105		/// The merkle root of the validators of the said session were stored
106		RootStored { index: SessionIndex },
107		/// The merkle roots of up to this session index were pruned
108		RootsPruned { up_to: SessionIndex },
109	}
110}
111
112impl<T: Config> Pallet<T> {
113	/// Prune historical stored session roots up to (but not including)
114	/// `up_to`.
115	pub fn prune_up_to(up_to: SessionIndex) {
116		StoredRange::<T>::mutate(|range| {
117			let (start, end) = match *range {
118				Some(range) => range,
119				None => return, // nothing to prune.
120			};
121
122			let up_to = core::cmp::min(up_to, end);
123
124			if up_to < start {
125				return // out of bounds. harmless.
126			}
127
128			(start..up_to).for_each(HistoricalSessions::<T>::remove);
129
130			let new_start = up_to;
131			*range = if new_start == end {
132				None // nothing is stored.
133			} else {
134				Some((new_start, end))
135			}
136		});
137
138		Self::deposit_event(Event::<T>::RootsPruned { up_to });
139	}
140
141	fn full_id_validators() -> Vec<(T::ValidatorId, T::FullIdentification)> {
142		<Session<T>>::validators()
143			.into_iter()
144			.filter_map(|validator| {
145				T::FullIdentificationOf::convert(validator.clone())
146					.map(|full_id| (validator, full_id))
147			})
148			.collect::<Vec<_>>()
149	}
150}
151
152impl<T: Config> ValidatorSet<T::AccountId> for Pallet<T> {
153	type ValidatorId = T::ValidatorId;
154	type ValidatorIdOf = T::ValidatorIdOf;
155
156	fn session_index() -> sp_staking::SessionIndex {
157		super::Pallet::<T>::current_index()
158	}
159
160	fn validators() -> Vec<Self::ValidatorId> {
161		super::Pallet::<T>::validators()
162	}
163}
164
165impl<T: Config> ValidatorSetWithIdentification<T::AccountId> for Pallet<T> {
166	type Identification = T::FullIdentification;
167	type IdentificationOf = T::FullIdentificationOf;
168}
169
170/// Specialization of the crate-level `SessionManager` which returns the set of full identification
171/// when creating a new session.
172pub trait SessionManager<ValidatorId, FullIdentification>:
173	pallet_session::SessionManager<ValidatorId>
174{
175	/// If there was a validator set change, its returns the set of new validators along with their
176	/// full identifications.
177	fn new_session(new_index: SessionIndex) -> Option<Vec<(ValidatorId, FullIdentification)>>;
178	fn new_session_genesis(
179		new_index: SessionIndex,
180	) -> Option<Vec<(ValidatorId, FullIdentification)>> {
181		<Self as SessionManager<_, _>>::new_session(new_index)
182	}
183	fn start_session(start_index: SessionIndex);
184	fn end_session(end_index: SessionIndex);
185}
186
187/// An `SessionManager` implementation that wraps an inner `I` and also
188/// sets the historical trie root of the ending session.
189pub struct NoteHistoricalRoot<T, I>(core::marker::PhantomData<(T, I)>);
190
191impl<T: Config, I: SessionManager<T::ValidatorId, T::FullIdentification>> NoteHistoricalRoot<T, I> {
192	fn do_new_session(new_index: SessionIndex, is_genesis: bool) -> Option<Vec<T::ValidatorId>> {
193		<StoredRange<T>>::mutate(|range| {
194			range.get_or_insert_with(|| (new_index, new_index)).1 = new_index + 1;
195		});
196
197		let new_validators_and_id = if is_genesis {
198			<I as SessionManager<_, _>>::new_session_genesis(new_index)
199		} else {
200			<I as SessionManager<_, _>>::new_session(new_index)
201		};
202		let new_validators_opt = new_validators_and_id
203			.as_ref()
204			.map(|new_validators| new_validators.iter().map(|(v, _id)| v.clone()).collect());
205
206		if let Some(new_validators) = new_validators_and_id {
207			let count = new_validators.len() as ValidatorCount;
208			match ProvingTrie::<T>::generate_for(new_validators) {
209				Ok(trie) => {
210					<HistoricalSessions<T>>::insert(new_index, &(trie.root, count));
211					Pallet::<T>::deposit_event(Event::RootStored { index: new_index });
212				},
213				Err(reason) => {
214					print("Failed to generate historical ancestry-inclusion proof.");
215					print(reason);
216				},
217			};
218		} else {
219			let previous_index = new_index.saturating_sub(1);
220			if let Some(previous_session) = <HistoricalSessions<T>>::get(previous_index) {
221				<HistoricalSessions<T>>::insert(new_index, previous_session);
222				Pallet::<T>::deposit_event(Event::RootStored { index: new_index });
223			}
224		}
225
226		new_validators_opt
227	}
228}
229
230impl<T: Config, I> pallet_session::SessionManager<T::ValidatorId> for NoteHistoricalRoot<T, I>
231where
232	I: SessionManager<T::ValidatorId, T::FullIdentification>,
233{
234	fn new_session(new_index: SessionIndex) -> Option<Vec<T::ValidatorId>> {
235		Self::do_new_session(new_index, false)
236	}
237
238	fn new_session_genesis(new_index: SessionIndex) -> Option<Vec<T::ValidatorId>> {
239		Self::do_new_session(new_index, true)
240	}
241
242	fn start_session(start_index: SessionIndex) {
243		<I as SessionManager<_, _>>::start_session(start_index)
244	}
245
246	fn end_session(end_index: SessionIndex) {
247		onchain::store_session_validator_set_to_offchain::<T>(end_index);
248		<I as SessionManager<_, _>>::end_session(end_index)
249	}
250}
251
252/// A tuple of the validator's ID and their full identification.
253pub type IdentificationTuple<T> =
254	(<T as pallet_session::Config>::ValidatorId, <T as Config>::FullIdentification);
255
256/// A trie instance for checking and generating proofs.
257pub struct ProvingTrie<T: Config> {
258	db: MemoryDB<T::Hashing>,
259	root: T::Hash,
260}
261
262impl<T: Config> ProvingTrie<T> {
263	fn generate_for<I>(validators: I) -> Result<Self, &'static str>
264	where
265		I: IntoIterator<Item = (T::ValidatorId, T::FullIdentification)>,
266	{
267		let mut db = MemoryDB::with_hasher(RandomState::default());
268		let mut root = Default::default();
269
270		{
271			let mut trie = TrieDBMutBuilderV0::new(&mut db, &mut root).build();
272			for (i, (validator, full_id)) in validators.into_iter().enumerate() {
273				let i = i as u32;
274				let keys = match <Session<T>>::load_keys(&validator) {
275					None => continue,
276					Some(k) => k,
277				};
278
279				let id_tuple = (validator, full_id);
280
281				// map each key to the owner index.
282				for key_id in T::Keys::key_ids() {
283					let key = keys.get_raw(*key_id);
284					let res =
285						(key_id, key).using_encoded(|k| i.using_encoded(|v| trie.insert(k, v)));
286
287					res.map_err(|_| "failed to insert into trie")?;
288				}
289
290				// map each owner index to the full identification.
291				i.using_encoded(|k| id_tuple.using_encoded(|v| trie.insert(k, v)))
292					.map_err(|_| "failed to insert into trie")?;
293			}
294		}
295
296		Ok(ProvingTrie { db, root })
297	}
298
299	fn from_proof(root: T::Hash, proof: StorageProof) -> Self {
300		ProvingTrie { db: proof.into_memory_db(), root }
301	}
302
303	/// Prove the full verification data for a given key and key ID.
304	pub fn prove(&self, key_id: KeyTypeId, key_data: &[u8]) -> Option<Vec<Vec<u8>>> {
305		let mut recorder = Recorder::<LayoutV0<T::Hashing>>::new();
306		self.query(key_id, key_data, Some(&mut recorder));
307
308		Some(recorder.into_raw_storage_proof())
309	}
310
311	/// Access the underlying trie root.
312	pub fn root(&self) -> &T::Hash {
313		&self.root
314	}
315
316	/// Search for a key inside the proof.
317	fn query(
318		&self,
319		key_id: KeyTypeId,
320		key_data: &[u8],
321		recorder: Option<&mut dyn TrieRecorder<T::Hash>>,
322	) -> Option<IdentificationTuple<T>> {
323		let trie = TrieDBBuilder::new(&self.db, &self.root)
324			.with_optional_recorder(recorder)
325			.build();
326
327		let val_idx = (key_id, key_data)
328			.using_encoded(|s| trie.get(s))
329			.ok()?
330			.and_then(|raw| u32::decode(&mut &*raw).ok())?;
331
332		val_idx
333			.using_encoded(|s| trie.get(s))
334			.ok()?
335			.and_then(|raw| <IdentificationTuple<T>>::decode(&mut &*raw).ok())
336	}
337}
338
339impl<T: Config, D: AsRef<[u8]>> KeyOwnerProofSystem<(KeyTypeId, D)> for Pallet<T> {
340	type Proof = MembershipProof;
341	type IdentificationTuple = IdentificationTuple<T>;
342
343	fn prove(key: (KeyTypeId, D)) -> Option<Self::Proof> {
344		let session = <Session<T>>::current_index();
345		let validators = Self::full_id_validators();
346
347		let count = validators.len() as ValidatorCount;
348
349		let trie = ProvingTrie::<T>::generate_for(validators).ok()?;
350
351		let (id, data) = key;
352		trie.prove(id, data.as_ref()).map(|trie_nodes| MembershipProof {
353			session,
354			trie_nodes,
355			validator_count: count,
356		})
357	}
358
359	fn check_proof(key: (KeyTypeId, D), proof: Self::Proof) -> Option<IdentificationTuple<T>> {
360		fn print_error<E: Debug>(e: E) {
361			log::error!(
362				target: LOG_TARGET,
363				"Rejecting equivocation report because of key ownership proof error: {:?}", e
364			);
365		}
366
367		let (id, data) = key;
368		let (root, count) = if proof.session == <Session<T>>::current_index() {
369			let validators = Self::full_id_validators();
370			let count = validators.len() as ValidatorCount;
371			let trie = ProvingTrie::<T>::generate_for(validators).map_err(print_error).ok()?;
372			(trie.root, count)
373		} else {
374			<HistoricalSessions<T>>::get(&proof.session)?
375		};
376
377		if count != proof.validator_count {
378			print_error("InvalidCount");
379			return None
380		}
381
382		let proof = StorageProof::new_with_duplicate_nodes_check(proof.trie_nodes)
383			.map_err(print_error)
384			.ok()?;
385		let mut accessed_nodes_tracker = AccessedNodesTracker::<T::Hash>::new(proof.len());
386		let trie = ProvingTrie::<T>::from_proof(root, proof);
387		let res = trie.query(id, data.as_ref(), Some(&mut accessed_nodes_tracker))?;
388		accessed_nodes_tracker.ensure_no_unused_nodes().map_err(print_error).ok()?;
389		Some(res)
390	}
391}
392
393#[cfg(test)]
394pub(crate) mod tests {
395	use super::*;
396	use crate::mock::{
397		force_new_session, set_next_validators, NextValidators, Session, System, Test,
398	};
399	use alloc::vec;
400
401	use sp_runtime::{key_types::DUMMY, testing::UintAuthorityId, BuildStorage};
402	use sp_state_machine::BasicExternalities;
403
404	use frame_support::traits::{KeyOwnerProofSystem, OnInitialize};
405
406	type Historical = Pallet<Test>;
407
408	pub(crate) fn new_test_ext() -> sp_io::TestExternalities {
409		let mut t = frame_system::GenesisConfig::<Test>::default().build_storage().unwrap();
410		let keys: Vec<_> = NextValidators::get()
411			.iter()
412			.cloned()
413			.map(|i| (i, i, UintAuthorityId(i).into()))
414			.collect();
415		BasicExternalities::execute_with_storage(&mut t, || {
416			for (ref k, ..) in &keys {
417				frame_system::Pallet::<Test>::inc_providers(k);
418			}
419		});
420		pallet_session::GenesisConfig::<Test> { keys, ..Default::default() }
421			.assimilate_storage(&mut t)
422			.unwrap();
423		sp_io::TestExternalities::new(t)
424	}
425
426	#[test]
427	fn generated_proof_is_good() {
428		new_test_ext().execute_with(|| {
429			set_next_validators(vec![1, 2]);
430			force_new_session();
431
432			System::set_block_number(1);
433			Session::on_initialize(1);
434
435			let encoded_key_1 = UintAuthorityId(1).encode();
436			let proof = Historical::prove((DUMMY, &encoded_key_1[..])).unwrap();
437
438			// proof-checking in the same session is OK.
439			assert!(Historical::check_proof((DUMMY, &encoded_key_1[..]), proof.clone()).is_some());
440
441			set_next_validators(vec![1, 2, 4]);
442			force_new_session();
443
444			System::set_block_number(2);
445			Session::on_initialize(2);
446
447			assert!(Historical::historical_root(proof.session).is_some());
448			assert!(Session::current_index() > proof.session);
449
450			// proof-checking in the next session is also OK.
451			assert!(Historical::check_proof((DUMMY, &encoded_key_1[..]), proof.clone()).is_some());
452
453			set_next_validators(vec![1, 2, 5]);
454
455			force_new_session();
456			System::set_block_number(3);
457			Session::on_initialize(3);
458		});
459	}
460
461	#[test]
462	fn prune_up_to_works() {
463		new_test_ext().execute_with(|| {
464			for i in 1..99u64 {
465				set_next_validators(vec![i]);
466				force_new_session();
467
468				System::set_block_number(i);
469				Session::on_initialize(i);
470			}
471
472			assert_eq!(<StoredRange<Test>>::get(), Some((0, 100)));
473
474			for i in 0..100 {
475				assert!(Historical::historical_root(i).is_some())
476			}
477
478			Historical::prune_up_to(10);
479			assert_eq!(<StoredRange<Test>>::get(), Some((10, 100)));
480
481			Historical::prune_up_to(9);
482			assert_eq!(<StoredRange<Test>>::get(), Some((10, 100)));
483
484			for i in 10..100 {
485				assert!(Historical::historical_root(i).is_some())
486			}
487
488			Historical::prune_up_to(99);
489			assert_eq!(<StoredRange<Test>>::get(), Some((99, 100)));
490
491			Historical::prune_up_to(100);
492			assert_eq!(<StoredRange<Test>>::get(), None);
493
494			for i in 99..199u64 {
495				set_next_validators(vec![i]);
496				force_new_session();
497
498				System::set_block_number(i);
499				Session::on_initialize(i);
500			}
501
502			assert_eq!(<StoredRange<Test>>::get(), Some((100, 200)));
503
504			for i in 100..200 {
505				assert!(Historical::historical_root(i).is_some())
506			}
507
508			Historical::prune_up_to(9999);
509			assert_eq!(<StoredRange<Test>>::get(), None);
510
511			for i in 100..200 {
512				assert!(Historical::historical_root(i).is_none())
513			}
514		});
515	}
516}