pallet_session/historical/
mod.rs1pub 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 const STORAGE_VERSION: StorageVersion = StorageVersion::new(1);
67
68 #[pallet::pallet]
69 #[pallet::storage_version(STORAGE_VERSION)]
70 pub struct Pallet<T>(_);
71
72 #[pallet::config]
74 pub trait Config: pallet_session::Config + frame_system::Config {
75 #[allow(deprecated)]
77 type RuntimeEvent: From<Event<Self>> + IsType<<Self as frame_system::Config>::RuntimeEvent>;
78
79 type FullIdentification: Parameter;
81
82 type FullIdentificationOf: Convert<Self::ValidatorId, Option<Self::FullIdentification>>;
90 }
91
92 #[pallet::storage]
94 #[pallet::getter(fn historical_root)]
95 pub type HistoricalSessions<T: Config> =
96 StorageMap<_, Twox64Concat, SessionIndex, (T::Hash, ValidatorCount), OptionQuery>;
97
98 #[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 RootStored { index: SessionIndex },
107 RootsPruned { up_to: SessionIndex },
109 }
110}
111
112impl<T: Config> Pallet<T> {
113 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, };
121
122 let up_to = core::cmp::min(up_to, end);
123
124 if up_to < start {
125 return }
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 } 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
170pub trait SessionManager<ValidatorId, FullIdentification>:
173 pallet_session::SessionManager<ValidatorId>
174{
175 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
187pub 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
252pub type IdentificationTuple<T> =
254 (<T as pallet_session::Config>::ValidatorId, <T as Config>::FullIdentification);
255
256pub 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 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 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 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 pub fn root(&self) -> &T::Hash {
313 &self.root
314 }
315
316 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 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 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}