referrerpolicy=no-referrer-when-downgrade

pallet_babe/
lib.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//! Consensus extension module for BABE consensus. Collects on-chain randomness
19//! from VRF outputs and manages epoch transitions.
20
21#![cfg_attr(not(feature = "std"), no_std)]
22#![warn(unused_must_use, unsafe_code, unused_variables, unused_must_use)]
23
24extern crate alloc;
25
26use alloc::{boxed::Box, vec, vec::Vec};
27use codec::{Decode, Encode};
28use frame_support::{
29	dispatch::{DispatchResultWithPostInfo, Pays},
30	ensure,
31	traits::{ConstU32, DisabledValidators, FindAuthor, Get, OnTimestampSet, OneSessionHandler},
32	weights::Weight,
33	BoundedVec, WeakBoundedVec,
34};
35use frame_system::pallet_prelude::{BlockNumberFor, HeaderFor};
36use sp_consensus_babe::{
37	digests::{NextConfigDescriptor, NextEpochDescriptor, PreDigest},
38	AllowedSlots, BabeAuthorityWeight, BabeEpochConfiguration, ConsensusLog, Epoch,
39	EquivocationProof, Randomness as BabeRandomness, Slot, BABE_ENGINE_ID, RANDOMNESS_LENGTH,
40	RANDOMNESS_VRF_CONTEXT,
41};
42use sp_core::crypto::Wraps;
43use sp_runtime::{
44	generic::DigestItem,
45	traits::{IsMember, One, SaturatedConversion, Saturating, Zero},
46	ConsensusEngineId, Permill,
47};
48use sp_session::{GetSessionNumber, GetValidatorCount};
49use sp_staking::{offence::OffenceReportSystem, SessionIndex};
50
51pub use sp_consensus_babe::AuthorityId;
52
53const LOG_TARGET: &str = "runtime::babe";
54
55mod default_weights;
56mod equivocation;
57mod randomness;
58
59#[cfg(any(feature = "runtime-benchmarks", test))]
60mod benchmarking;
61#[cfg(all(feature = "std", test))]
62mod mock;
63#[cfg(all(feature = "std", test))]
64mod tests;
65
66pub use equivocation::{EquivocationOffence, EquivocationReportSystem};
67#[allow(deprecated)]
68pub use randomness::CurrentBlockRandomness;
69pub use randomness::{
70	ParentBlockRandomness, RandomnessFromOneEpochAgo, RandomnessFromTwoEpochsAgo,
71};
72
73pub use pallet::*;
74
75pub trait WeightInfo {
76	fn plan_config_change() -> Weight;
77	fn report_equivocation(validator_count: u32, max_nominators_per_validator: u32) -> Weight;
78}
79
80/// Trigger an epoch change, if any should take place.
81pub trait EpochChangeTrigger {
82	/// Trigger an epoch change, if any should take place. This should be called
83	/// during every block, after initialization is done.
84	fn trigger<T: Config>(now: BlockNumberFor<T>);
85}
86
87/// A type signifying to BABE that an external trigger
88/// for epoch changes (e.g. pallet-session) is used.
89pub struct ExternalTrigger;
90
91impl EpochChangeTrigger for ExternalTrigger {
92	fn trigger<T: Config>(_: BlockNumberFor<T>) {} // nothing - trigger is external.
93}
94
95/// A type signifying to BABE that it should perform epoch changes
96/// with an internal trigger, recycling the same authorities forever.
97pub struct SameAuthoritiesForever;
98
99impl EpochChangeTrigger for SameAuthoritiesForever {
100	fn trigger<T: Config>(now: BlockNumberFor<T>) {
101		if Pallet::<T>::should_epoch_change(now) {
102			let authorities = Authorities::<T>::get();
103			let next_authorities = authorities.clone();
104
105			Pallet::<T>::enact_epoch_change(authorities, next_authorities, None);
106		}
107	}
108}
109
110const UNDER_CONSTRUCTION_SEGMENT_LENGTH: u32 = 256;
111
112#[frame_support::pallet]
113pub mod pallet {
114	use super::*;
115	use frame_support::pallet_prelude::*;
116	use frame_system::pallet_prelude::*;
117
118	/// The BABE Pallet
119	#[pallet::pallet]
120	pub struct Pallet<T>(_);
121
122	#[pallet::config]
123	#[pallet::disable_frame_system_supertrait_check]
124	pub trait Config: pallet_timestamp::Config {
125		/// The amount of time, in slots, that each epoch should last.
126		/// NOTE: Currently it is not possible to change the epoch duration after
127		/// the chain has started. Attempting to do so will brick block production.
128		#[pallet::constant]
129		type EpochDuration: Get<u64>;
130
131		/// The expected average block time at which BABE should be creating
132		/// blocks. Since BABE is probabilistic it is not trivial to figure out
133		/// what the expected average block time should be based on the slot
134		/// duration and the security parameter `c` (where `1 - c` represents
135		/// the probability of a slot being empty).
136		#[pallet::constant]
137		type ExpectedBlockTime: Get<Self::Moment>;
138
139		/// BABE requires some logic to be triggered on every block to query for whether an epoch
140		/// has ended and to perform the transition to the next epoch.
141		///
142		/// Typically, the `ExternalTrigger` type should be used. An internal trigger should only be
143		/// used when no other module is responsible for changing authority set.
144		type EpochChangeTrigger: EpochChangeTrigger;
145
146		/// A way to check whether a given validator is disabled and should not be authoring blocks.
147		/// Blocks authored by a disabled validator will lead to a panic as part of this module's
148		/// initialization.
149		type DisabledValidators: DisabledValidators;
150
151		/// Helper for weights computations
152		type WeightInfo: WeightInfo;
153
154		/// Max number of authorities allowed
155		#[pallet::constant]
156		type MaxAuthorities: Get<u32>;
157
158		/// The maximum number of nominators for each validator.
159		#[pallet::constant]
160		type MaxNominators: Get<u32>;
161
162		/// The proof of key ownership, used for validating equivocation reports.
163		/// The proof must include the session index and validator count of the
164		/// session at which the equivocation occurred.
165		type KeyOwnerProof: Parameter + GetSessionNumber + GetValidatorCount;
166
167		/// The equivocation handling subsystem, defines methods to check/report an
168		/// offence and for submitting a transaction to report an equivocation
169		/// (from an offchain context).
170		type EquivocationReportSystem: OffenceReportSystem<
171			Option<Self::AccountId>,
172			(EquivocationProof<HeaderFor<Self>>, Self::KeyOwnerProof),
173		>;
174	}
175
176	#[pallet::error]
177	pub enum Error<T> {
178		/// An equivocation proof provided as part of an equivocation report is invalid.
179		InvalidEquivocationProof,
180		/// A key ownership proof provided as part of an equivocation report is invalid.
181		InvalidKeyOwnershipProof,
182		/// A given equivocation report is valid but already previously reported.
183		DuplicateOffenceReport,
184		/// Submitted configuration is invalid.
185		InvalidConfiguration,
186	}
187
188	/// Current epoch index.
189	#[pallet::storage]
190	pub type EpochIndex<T> = StorageValue<_, u64, ValueQuery>;
191
192	/// Current epoch authorities.
193	#[pallet::storage]
194	pub type Authorities<T: Config> = StorageValue<
195		_,
196		WeakBoundedVec<(AuthorityId, BabeAuthorityWeight), T::MaxAuthorities>,
197		ValueQuery,
198	>;
199
200	/// The slot at which the first epoch actually started. This is 0
201	/// until the first block of the chain.
202	#[pallet::storage]
203	pub type GenesisSlot<T> = StorageValue<_, Slot, ValueQuery>;
204
205	/// Current slot number.
206	#[pallet::storage]
207	pub type CurrentSlot<T> = StorageValue<_, Slot, ValueQuery>;
208
209	/// The epoch randomness for the *current* epoch.
210	///
211	/// # Security
212	///
213	/// This MUST NOT be used for gambling, as it can be influenced by a
214	/// malicious validator in the short term. It MAY be used in many
215	/// cryptographic protocols, however, so long as one remembers that this
216	/// (like everything else on-chain) it is public. For example, it can be
217	/// used where a number is needed that cannot have been chosen by an
218	/// adversary, for purposes such as public-coin zero-knowledge proofs.
219	// NOTE: the following fields don't use the constants to define the
220	// array size because the metadata API currently doesn't resolve the
221	// variable to its underlying value.
222	#[pallet::storage]
223	pub type Randomness<T> = StorageValue<_, BabeRandomness, ValueQuery>;
224
225	/// Pending epoch configuration change that will be applied when the next epoch is enacted.
226	#[pallet::storage]
227	pub type PendingEpochConfigChange<T> = StorageValue<_, NextConfigDescriptor>;
228
229	/// Next epoch randomness.
230	#[pallet::storage]
231	pub type NextRandomness<T> = StorageValue<_, BabeRandomness, ValueQuery>;
232
233	/// Next epoch authorities.
234	#[pallet::storage]
235	pub type NextAuthorities<T: Config> = StorageValue<
236		_,
237		WeakBoundedVec<(AuthorityId, BabeAuthorityWeight), T::MaxAuthorities>,
238		ValueQuery,
239	>;
240
241	/// Randomness under construction.
242	///
243	/// We make a trade-off between storage accesses and list length.
244	/// We store the under-construction randomness in segments of up to
245	/// `UNDER_CONSTRUCTION_SEGMENT_LENGTH`.
246	///
247	/// Once a segment reaches this length, we begin the next one.
248	/// We reset all segments and return to `0` at the beginning of every
249	/// epoch.
250	#[pallet::storage]
251	pub type SegmentIndex<T> = StorageValue<_, u32, ValueQuery>;
252
253	/// TWOX-NOTE: `SegmentIndex` is an increasing integer, so this is okay.
254	#[pallet::storage]
255	pub type UnderConstruction<T: Config> = StorageMap<
256		_,
257		Twox64Concat,
258		u32,
259		BoundedVec<BabeRandomness, ConstU32<UNDER_CONSTRUCTION_SEGMENT_LENGTH>>,
260		ValueQuery,
261	>;
262
263	/// Temporary value (cleared at block finalization) which is `Some`
264	/// if per-block initialization has already been called for current block.
265	#[pallet::storage]
266	pub type Initialized<T> = StorageValue<_, Option<PreDigest>>;
267
268	/// This field should always be populated during block processing unless
269	/// secondary plain slots are enabled (which don't contain a VRF output).
270	///
271	/// It is set in `on_finalize`, before it will contain the value from the last block.
272	#[pallet::storage]
273	pub type AuthorVrfRandomness<T> = StorageValue<_, Option<BabeRandomness>, ValueQuery>;
274
275	/// The block numbers when the last and current epoch have started, respectively `N-1` and
276	/// `N`.
277	/// NOTE: We track this is in order to annotate the block number when a given pool of
278	/// entropy was fixed (i.e. it was known to chain observers). Since epochs are defined in
279	/// slots, which may be skipped, the block numbers may not line up with the slot numbers.
280	#[pallet::storage]
281	pub type EpochStart<T: Config> =
282		StorageValue<_, (BlockNumberFor<T>, BlockNumberFor<T>), ValueQuery>;
283
284	/// How late the current block is compared to its parent.
285	///
286	/// This entry is populated as part of block execution and is cleaned up
287	/// on block finalization. Querying this storage entry outside of block
288	/// execution context should always yield zero.
289	#[pallet::storage]
290	pub type Lateness<T: Config> = StorageValue<_, BlockNumberFor<T>, ValueQuery>;
291
292	/// The configuration for the current epoch. Should never be `None` as it is initialized in
293	/// genesis.
294	#[pallet::storage]
295	pub type EpochConfig<T> = StorageValue<_, BabeEpochConfiguration>;
296
297	/// The configuration for the next epoch, `None` if the config will not change
298	/// (you can fallback to `EpochConfig` instead in that case).
299	#[pallet::storage]
300	pub type NextEpochConfig<T> = StorageValue<_, BabeEpochConfiguration>;
301
302	/// A list of the last 100 skipped epochs and the corresponding session index
303	/// when the epoch was skipped.
304	///
305	/// This is only used for validating equivocation proofs. An equivocation proof
306	/// must contains a key-ownership proof for a given session, therefore we need a
307	/// way to tie together sessions and epoch indices, i.e. we need to validate that
308	/// a validator was the owner of a given key on a given session, and what the
309	/// active epoch index was during that session.
310	#[pallet::storage]
311	pub type SkippedEpochs<T> =
312		StorageValue<_, BoundedVec<(u64, SessionIndex), ConstU32<100>>, ValueQuery>;
313
314	#[derive(frame_support::DefaultNoBound)]
315	#[pallet::genesis_config]
316	pub struct GenesisConfig<T: Config> {
317		pub authorities: Vec<(AuthorityId, BabeAuthorityWeight)>,
318		pub epoch_config: BabeEpochConfiguration,
319		#[serde(skip)]
320		pub _config: core::marker::PhantomData<T>,
321	}
322
323	#[pallet::genesis_build]
324	impl<T: Config> BuildGenesisConfig for GenesisConfig<T> {
325		fn build(&self) {
326			SegmentIndex::<T>::put(0);
327			Pallet::<T>::initialize_genesis_authorities(&self.authorities);
328			EpochConfig::<T>::put(&self.epoch_config);
329		}
330	}
331
332	#[pallet::hooks]
333	impl<T: Config> Hooks<BlockNumberFor<T>> for Pallet<T> {
334		/// Initialization
335		fn on_initialize(now: BlockNumberFor<T>) -> Weight {
336			Self::initialize(now);
337			Weight::zero()
338		}
339
340		/// Block finalization
341		fn on_finalize(_now: BlockNumberFor<T>) {
342			// at the end of the block, we can safely include the new VRF output
343			// from this block into the under-construction randomness. If we've determined
344			// that this block was the first in a new epoch, the changeover logic has
345			// already occurred at this point, so the under-construction randomness
346			// will only contain outputs from the right epoch.
347			if let Some(pre_digest) = Initialized::<T>::take().flatten() {
348				let authority_index = pre_digest.authority_index();
349
350				if T::DisabledValidators::is_disabled(authority_index) {
351					panic!(
352						"Validator with index {:?} is disabled and should not be attempting to author blocks.",
353						authority_index,
354					);
355				}
356
357				if let Some(signature) = pre_digest.vrf_signature() {
358					let randomness: Option<BabeRandomness> = Authorities::<T>::get()
359						.get(authority_index as usize)
360						.and_then(|(authority, _)| {
361							let public = authority.as_inner_ref();
362							let transcript = sp_consensus_babe::make_vrf_transcript(
363								&Randomness::<T>::get(),
364								CurrentSlot::<T>::get(),
365								EpochIndex::<T>::get(),
366							);
367
368							// NOTE: this is verified by the client when importing the block, before
369							// execution. We don't run the verification again here to avoid slowing
370							// down the runtime.
371							debug_assert!({
372								use sp_core::crypto::VrfPublic;
373								public.vrf_verify(&transcript.clone().into_sign_data(), &signature)
374							});
375
376							public
377								.make_bytes(
378									RANDOMNESS_VRF_CONTEXT,
379									&transcript,
380									&signature.pre_output,
381								)
382								.ok()
383						});
384
385					if let Some(randomness) = pre_digest.is_primary().then(|| randomness).flatten()
386					{
387						Self::deposit_randomness(&randomness);
388					}
389
390					AuthorVrfRandomness::<T>::put(randomness);
391				}
392			}
393
394			// remove temporary "environment" entry from storage
395			Lateness::<T>::kill();
396		}
397	}
398
399	#[pallet::call]
400	impl<T: Config> Pallet<T> {
401		/// Report authority equivocation/misbehavior. This method will verify
402		/// the equivocation proof and validate the given key ownership proof
403		/// against the extracted offender. If both are valid, the offence will
404		/// be reported.
405		#[pallet::call_index(0)]
406		#[pallet::weight(<T as Config>::WeightInfo::report_equivocation(
407			key_owner_proof.validator_count(),
408			T::MaxNominators::get(),
409		))]
410		pub fn report_equivocation(
411			origin: OriginFor<T>,
412			equivocation_proof: Box<EquivocationProof<HeaderFor<T>>>,
413			key_owner_proof: T::KeyOwnerProof,
414		) -> DispatchResultWithPostInfo {
415			let reporter = ensure_signed(origin)?;
416			T::EquivocationReportSystem::process_evidence(
417				Some(reporter),
418				(*equivocation_proof, key_owner_proof),
419			)?;
420			// Waive the fee since the report is valid and beneficial
421			Ok(Pays::No.into())
422		}
423
424		/// Report authority equivocation/misbehavior. This method will verify
425		/// the equivocation proof and validate the given key ownership proof
426		/// against the extracted offender. If both are valid, the offence will
427		/// be reported.
428		/// This extrinsic must be called unsigned and it is expected that only
429		/// block authors will call it (validated in `ValidateUnsigned`), as such
430		/// if the block author is defined it will be defined as the equivocation
431		/// reporter.
432		#[pallet::call_index(1)]
433		#[pallet::weight(<T as Config>::WeightInfo::report_equivocation(
434			key_owner_proof.validator_count(),
435			T::MaxNominators::get(),
436		))]
437		pub fn report_equivocation_unsigned(
438			origin: OriginFor<T>,
439			equivocation_proof: Box<EquivocationProof<HeaderFor<T>>>,
440			key_owner_proof: T::KeyOwnerProof,
441		) -> DispatchResultWithPostInfo {
442			ensure_none(origin)?;
443			T::EquivocationReportSystem::process_evidence(
444				None,
445				(*equivocation_proof, key_owner_proof),
446			)?;
447			Ok(Pays::No.into())
448		}
449
450		/// Plan an epoch config change. The epoch config change is recorded and will be enacted on
451		/// the next call to `enact_epoch_change`. The config will be activated one epoch after.
452		/// Multiple calls to this method will replace any existing planned config change that had
453		/// not been enacted yet.
454		#[pallet::call_index(2)]
455		#[pallet::weight(<T as Config>::WeightInfo::plan_config_change())]
456		pub fn plan_config_change(
457			origin: OriginFor<T>,
458			config: NextConfigDescriptor,
459		) -> DispatchResult {
460			ensure_root(origin)?;
461			match config {
462				NextConfigDescriptor::V1 { c, allowed_slots } => {
463					ensure!(
464						(c.0 != 0 || allowed_slots != AllowedSlots::PrimarySlots) && c.1 != 0,
465						Error::<T>::InvalidConfiguration
466					);
467				},
468			}
469			PendingEpochConfigChange::<T>::put(config);
470			Ok(())
471		}
472	}
473
474	#[pallet::validate_unsigned]
475	impl<T: Config> ValidateUnsigned for Pallet<T> {
476		type Call = Call<T>;
477		fn validate_unsigned(source: TransactionSource, call: &Self::Call) -> TransactionValidity {
478			Self::validate_unsigned(source, call)
479		}
480
481		fn pre_dispatch(call: &Self::Call) -> Result<(), TransactionValidityError> {
482			Self::pre_dispatch(call)
483		}
484	}
485}
486
487impl<T: Config> FindAuthor<u32> for Pallet<T> {
488	fn find_author<'a, I>(digests: I) -> Option<u32>
489	where
490		I: 'a + IntoIterator<Item = (ConsensusEngineId, &'a [u8])>,
491	{
492		for (id, mut data) in digests.into_iter() {
493			if id == BABE_ENGINE_ID {
494				let pre_digest: PreDigest = PreDigest::decode(&mut data).ok()?;
495				return Some(pre_digest.authority_index())
496			}
497		}
498
499		None
500	}
501}
502
503impl<T: Config> IsMember<AuthorityId> for Pallet<T> {
504	fn is_member(authority_id: &AuthorityId) -> bool {
505		Authorities::<T>::get().iter().any(|id| &id.0 == authority_id)
506	}
507}
508
509impl<T: Config> pallet_session::ShouldEndSession<BlockNumberFor<T>> for Pallet<T> {
510	fn should_end_session(now: BlockNumberFor<T>) -> bool {
511		// it might be (and it is in current implementation) that session module is calling
512		// `should_end_session` from it's own `on_initialize` handler, in which case it's
513		// possible that babe's own `on_initialize` has not run yet, so let's ensure that we
514		// have initialized the pallet and updated the current slot.
515		Self::initialize(now);
516		Self::should_epoch_change(now)
517	}
518}
519
520impl<T: Config> Pallet<T> {
521	/// Public function to access epoch_index storage.
522	pub fn epoch_index() -> u64 {
523		EpochIndex::<T>::get()
524	}
525	/// Public function to access authorities storage.
526	pub fn authorities() -> WeakBoundedVec<(AuthorityId, BabeAuthorityWeight), T::MaxAuthorities> {
527		Authorities::<T>::get()
528	}
529	/// Public function to access genesis_slot storage.
530	pub fn genesis_slot() -> Slot {
531		GenesisSlot::<T>::get()
532	}
533	/// Public function to access current_slot storage.
534	pub fn current_slot() -> Slot {
535		CurrentSlot::<T>::get()
536	}
537	/// Public function to access randomness storage.
538	pub fn randomness() -> BabeRandomness {
539		Randomness::<T>::get()
540	}
541	/// Public function to access initialized storage.
542	pub fn initialized() -> Option<Option<PreDigest>> {
543		Initialized::<T>::get()
544	}
545	/// Public function to access author_vrf_randomness storage.
546	pub fn author_vrf_randomness() -> Option<BabeRandomness> {
547		AuthorVrfRandomness::<T>::get()
548	}
549	/// Public function to access lateness storage.
550	pub fn lateness() -> BlockNumberFor<T> {
551		Lateness::<T>::get()
552	}
553	/// Public function to access epoch_config storage.
554	pub fn epoch_config() -> Option<BabeEpochConfiguration> {
555		EpochConfig::<T>::get()
556	}
557	/// Public function to access skipped_epochs storage.
558	pub fn skipped_epochs() -> BoundedVec<(u64, SessionIndex), ConstU32<100>> {
559		SkippedEpochs::<T>::get()
560	}
561
562	/// Determine the BABE slot duration based on the Timestamp module configuration.
563	pub fn slot_duration() -> T::Moment {
564		// we double the minimum block-period so each author can always propose within
565		// the majority of their slot.
566		<T as pallet_timestamp::Config>::MinimumPeriod::get().saturating_mul(2u32.into())
567	}
568
569	/// Determine whether an epoch change should take place at this block.
570	/// Assumes that initialization has already taken place.
571	pub fn should_epoch_change(now: BlockNumberFor<T>) -> bool {
572		// The epoch has technically ended during the passage of time
573		// between this block and the last, but we have to "end" the epoch now,
574		// since there is no earlier possible block we could have done it.
575		//
576		// The exception is for block 1: the genesis has slot 0, so we treat
577		// epoch 0 as having started at the slot of block 1. We want to use
578		// the same randomness and validator set as signalled in the genesis,
579		// so we don't rotate the epoch.
580		now != One::one() && {
581			let diff = CurrentSlot::<T>::get().saturating_sub(Self::current_epoch_start());
582			*diff >= T::EpochDuration::get()
583		}
584	}
585
586	/// Return the _best guess_ block number, at which the next epoch change is predicted to happen.
587	///
588	/// Returns None if the prediction is in the past; This implies an error internally in the Babe
589	/// and should not happen under normal circumstances.
590	///
591	/// In other word, this is only accurate if no slots are missed. Given missed slots, the slot
592	/// number will grow while the block number will not. Hence, the result can be interpreted as an
593	/// upper bound.
594	// ## IMPORTANT NOTE
595	//
596	// This implementation is linked to how [`should_epoch_change`] is working. This might need to
597	// be updated accordingly, if the underlying mechanics of slot and epochs change.
598	//
599	// WEIGHT NOTE: This function is tied to the weight of `EstimateNextSessionRotation`. If you
600	// update this function, you must also update the corresponding weight.
601	pub fn next_expected_epoch_change(now: BlockNumberFor<T>) -> Option<BlockNumberFor<T>> {
602		let next_slot = Self::current_epoch_start().saturating_add(T::EpochDuration::get());
603		next_slot.checked_sub(*CurrentSlot::<T>::get()).map(|slots_remaining| {
604			// This is a best effort guess. Drifts in the slot/block ratio will cause errors here.
605			let blocks_remaining: BlockNumberFor<T> = slots_remaining.saturated_into();
606			now.saturating_add(blocks_remaining)
607		})
608	}
609
610	/// DANGEROUS: Enact an epoch change. Should be done on every block where `should_epoch_change`
611	/// has returned `true`, and the caller is the only caller of this function.
612	///
613	/// Typically, this is not handled directly by the user, but by higher-level validator-set
614	/// manager logic like `pallet-session`.
615	///
616	/// This doesn't do anything if `authorities` is empty.
617	pub fn enact_epoch_change(
618		authorities: WeakBoundedVec<(AuthorityId, BabeAuthorityWeight), T::MaxAuthorities>,
619		next_authorities: WeakBoundedVec<(AuthorityId, BabeAuthorityWeight), T::MaxAuthorities>,
620		session_index: Option<SessionIndex>,
621	) {
622		// PRECONDITION: caller has done initialization and is guaranteed
623		// by the session module to be called before this.
624		debug_assert!(Initialized::<T>::get().is_some());
625
626		if authorities.is_empty() {
627			log::warn!(target: LOG_TARGET, "Ignoring empty epoch change.");
628			return
629		}
630
631		// Update epoch index.
632		//
633		// NOTE: we figure out the epoch index from the slot, which may not
634		// necessarily be contiguous if the chain was offline for more than
635		// `T::EpochDuration` slots. When skipping from epoch N to e.g. N+4, we
636		// will be using the randomness and authorities for that epoch that had
637		// been previously announced for epoch N+1, and the randomness collected
638		// during the current epoch (N) will be used for epoch N+5.
639		let epoch_index = sp_consensus_babe::epoch_index(
640			CurrentSlot::<T>::get(),
641			GenesisSlot::<T>::get(),
642			T::EpochDuration::get(),
643		);
644
645		let current_epoch_index = EpochIndex::<T>::get();
646		if current_epoch_index.saturating_add(1) != epoch_index {
647			// we are skipping epochs therefore we need to update the mapping
648			// of epochs to session
649			if let Some(session_index) = session_index {
650				SkippedEpochs::<T>::mutate(|skipped_epochs| {
651					if epoch_index < session_index as u64 {
652						log::warn!(
653							target: LOG_TARGET,
654							"Current epoch index {} is lower than session index {}.",
655							epoch_index,
656							session_index,
657						);
658
659						return
660					}
661
662					if skipped_epochs.is_full() {
663						// NOTE: this is O(n) but we currently don't have a bounded `VecDeque`.
664						// this vector is bounded to a small number of elements so performance
665						// shouldn't be an issue.
666						skipped_epochs.remove(0);
667					}
668
669					skipped_epochs.force_push((epoch_index, session_index));
670				})
671			}
672		}
673
674		EpochIndex::<T>::put(epoch_index);
675		Authorities::<T>::put(authorities);
676
677		// Update epoch randomness.
678		let next_epoch_index = epoch_index
679			.checked_add(1)
680			.expect("epoch indices will never reach 2^64 before the death of the universe; qed");
681
682		// Returns randomness for the current epoch and computes the *next*
683		// epoch randomness.
684		let randomness = Self::randomness_change_epoch(next_epoch_index);
685		Randomness::<T>::put(randomness);
686
687		// Update the next epoch authorities.
688		NextAuthorities::<T>::put(&next_authorities);
689
690		// Update the start blocks of the previous and new current epoch.
691		EpochStart::<T>::mutate(|(previous_epoch_start_block, current_epoch_start_block)| {
692			*previous_epoch_start_block = core::mem::take(current_epoch_start_block);
693			*current_epoch_start_block = <frame_system::Pallet<T>>::block_number();
694		});
695
696		// After we update the current epoch, we signal the *next* epoch change
697		// so that nodes can track changes.
698		let next_randomness = NextRandomness::<T>::get();
699
700		let next_epoch = NextEpochDescriptor {
701			authorities: next_authorities.into_inner(),
702			randomness: next_randomness,
703		};
704		Self::deposit_consensus(ConsensusLog::NextEpochData(next_epoch));
705
706		if let Some(next_config) = NextEpochConfig::<T>::get() {
707			EpochConfig::<T>::put(next_config);
708		}
709
710		if let Some(pending_epoch_config_change) = PendingEpochConfigChange::<T>::take() {
711			let next_epoch_config: BabeEpochConfiguration =
712				pending_epoch_config_change.clone().into();
713			NextEpochConfig::<T>::put(next_epoch_config);
714
715			Self::deposit_consensus(ConsensusLog::NextConfigData(pending_epoch_config_change));
716		}
717	}
718
719	/// Finds the start slot of the current epoch.
720	///
721	/// Only guaranteed to give correct results after `initialize` of the first
722	/// block in the chain (as its result is based off of `GenesisSlot`).
723	pub fn current_epoch_start() -> Slot {
724		sp_consensus_babe::epoch_start_slot(
725			EpochIndex::<T>::get(),
726			GenesisSlot::<T>::get(),
727			T::EpochDuration::get(),
728		)
729	}
730
731	/// Produces information about the current epoch.
732	pub fn current_epoch() -> Epoch {
733		Epoch {
734			epoch_index: EpochIndex::<T>::get(),
735			start_slot: Self::current_epoch_start(),
736			duration: T::EpochDuration::get(),
737			authorities: Authorities::<T>::get().into_inner(),
738			randomness: Randomness::<T>::get(),
739			config: EpochConfig::<T>::get()
740				.expect("EpochConfig is initialized in genesis; we never `take` or `kill` it; qed"),
741		}
742	}
743
744	/// Produces information about the next epoch (which was already previously
745	/// announced).
746	pub fn next_epoch() -> Epoch {
747		let next_epoch_index = EpochIndex::<T>::get().checked_add(1).expect(
748			"epoch index is u64; it is always only incremented by one; \
749			 if u64 is not enough we should crash for safety; qed.",
750		);
751
752		let start_slot = sp_consensus_babe::epoch_start_slot(
753			next_epoch_index,
754			GenesisSlot::<T>::get(),
755			T::EpochDuration::get(),
756		);
757
758		Epoch {
759			epoch_index: next_epoch_index,
760			start_slot,
761			duration: T::EpochDuration::get(),
762			authorities: NextAuthorities::<T>::get().into_inner(),
763			randomness: NextRandomness::<T>::get(),
764			config: NextEpochConfig::<T>::get().unwrap_or_else(|| {
765				EpochConfig::<T>::get().expect(
766					"EpochConfig is initialized in genesis; we never `take` or `kill` it; qed",
767				)
768			}),
769		}
770	}
771
772	fn deposit_consensus<U: Encode>(new: U) {
773		let log = DigestItem::Consensus(BABE_ENGINE_ID, new.encode());
774		<frame_system::Pallet<T>>::deposit_log(log)
775	}
776
777	fn deposit_randomness(randomness: &BabeRandomness) {
778		let segment_idx = SegmentIndex::<T>::get();
779		let mut segment = UnderConstruction::<T>::get(&segment_idx);
780		if segment.try_push(*randomness).is_ok() {
781			// push onto current segment: not full.
782			UnderConstruction::<T>::insert(&segment_idx, &segment);
783		} else {
784			// move onto the next segment and update the index.
785			let segment_idx = segment_idx + 1;
786			let bounded_randomness =
787				BoundedVec::<_, ConstU32<UNDER_CONSTRUCTION_SEGMENT_LENGTH>>::try_from(vec![
788					*randomness,
789				])
790				.expect("UNDER_CONSTRUCTION_SEGMENT_LENGTH >= 1");
791			UnderConstruction::<T>::insert(&segment_idx, bounded_randomness);
792			SegmentIndex::<T>::put(&segment_idx);
793		}
794	}
795
796	fn initialize_genesis_authorities(authorities: &[(AuthorityId, BabeAuthorityWeight)]) {
797		if !authorities.is_empty() {
798			assert!(Authorities::<T>::get().is_empty(), "Authorities are already initialized!");
799			let bounded_authorities =
800				WeakBoundedVec::<_, T::MaxAuthorities>::try_from(authorities.to_vec())
801					.expect("Initial number of authorities should be lower than T::MaxAuthorities");
802			Authorities::<T>::put(&bounded_authorities);
803			NextAuthorities::<T>::put(&bounded_authorities);
804		}
805	}
806
807	fn initialize_genesis_epoch(genesis_slot: Slot) {
808		GenesisSlot::<T>::put(genesis_slot);
809		debug_assert_ne!(*GenesisSlot::<T>::get(), 0);
810
811		// deposit a log because this is the first block in epoch #0
812		// we use the same values as genesis because we haven't collected any
813		// randomness yet.
814		let next = NextEpochDescriptor {
815			authorities: Authorities::<T>::get().into_inner(),
816			randomness: Randomness::<T>::get(),
817		};
818
819		Self::deposit_consensus(ConsensusLog::NextEpochData(next));
820	}
821
822	fn initialize(now: BlockNumberFor<T>) {
823		// since `initialize` can be called twice (e.g. if session module is present)
824		// let's ensure that we only do the initialization once per block
825		let initialized = Initialized::<T>::get().is_some();
826		if initialized {
827			return
828		}
829
830		let pre_digest =
831			<frame_system::Pallet<T>>::digest()
832				.logs
833				.iter()
834				.filter_map(|s| s.as_pre_runtime())
835				.filter_map(|(id, mut data)| {
836					if id == BABE_ENGINE_ID {
837						PreDigest::decode(&mut data).ok()
838					} else {
839						None
840					}
841				})
842				.next();
843
844		if let Some(ref pre_digest) = pre_digest {
845			// the slot number of the current block being initialized
846			let current_slot = pre_digest.slot();
847
848			// on the first non-zero block (i.e. block #1)
849			// this is where the first epoch (epoch #0) actually starts.
850			// we need to adjust internal storage accordingly.
851			if *GenesisSlot::<T>::get() == 0 {
852				Self::initialize_genesis_epoch(current_slot)
853			}
854
855			// how many slots were skipped between current and last block
856			let lateness = current_slot.saturating_sub(CurrentSlot::<T>::get() + 1);
857			let lateness = BlockNumberFor::<T>::from(*lateness as u32);
858
859			Lateness::<T>::put(lateness);
860			CurrentSlot::<T>::put(current_slot);
861		}
862
863		Initialized::<T>::put(pre_digest);
864
865		// enact epoch change, if necessary.
866		T::EpochChangeTrigger::trigger::<T>(now);
867	}
868
869	/// Call this function exactly once when an epoch changes, to update the
870	/// randomness. Returns the new randomness.
871	fn randomness_change_epoch(next_epoch_index: u64) -> BabeRandomness {
872		let this_randomness = NextRandomness::<T>::get();
873		let segment_idx: u32 = SegmentIndex::<T>::mutate(|s| core::mem::replace(s, 0));
874
875		// overestimate to the segment being full.
876		let rho_size = (segment_idx.saturating_add(1) * UNDER_CONSTRUCTION_SEGMENT_LENGTH) as usize;
877
878		let next_randomness = compute_randomness(
879			this_randomness,
880			next_epoch_index,
881			(0..segment_idx).flat_map(|i| UnderConstruction::<T>::take(&i)),
882			Some(rho_size),
883		);
884		NextRandomness::<T>::put(&next_randomness);
885		this_randomness
886	}
887
888	/// Returns the session index that was live when the given epoch happened,
889	/// taking into account any skipped epochs.
890	///
891	/// This function is only well defined for epochs that actually existed,
892	/// e.g. if we skipped from epoch 10 to 20 then a call for epoch 15 (which
893	/// didn't exist) will return an incorrect session index.
894	pub(crate) fn session_index_for_epoch(epoch_index: u64) -> SessionIndex {
895		let skipped_epochs = SkippedEpochs::<T>::get();
896		match skipped_epochs.binary_search_by_key(&epoch_index, |(epoch_index, _)| *epoch_index) {
897			// we have an exact match so we just return the given session index
898			Ok(index) => skipped_epochs[index].1,
899			// we haven't found any skipped epoch before the given epoch,
900			// so the epoch index and session index should match
901			Err(0) => epoch_index.saturated_into::<u32>(),
902			// we have found a skipped epoch before the given epoch
903			Err(index) => {
904				// the element before the given index should give us the skipped epoch
905				// that's closest to the one we're trying to find the session index for
906				let closest_skipped_epoch = skipped_epochs[index - 1];
907
908				// calculate the number of skipped epochs at this point by checking the difference
909				// between the epoch and session indices. epoch index should always be greater or
910				// equal to session index, this is because epochs can be skipped whereas sessions
911				// can't (this is enforced when pushing into `SkippedEpochs`)
912				let skipped_epochs = closest_skipped_epoch.0 - closest_skipped_epoch.1 as u64;
913				epoch_index.saturating_sub(skipped_epochs).saturated_into::<u32>()
914			},
915		}
916	}
917
918	/// Submits an extrinsic to report an equivocation. This method will create
919	/// an unsigned extrinsic with a call to `report_equivocation_unsigned` and
920	/// will push the transaction to the pool. Only useful in an offchain
921	/// context.
922	pub fn submit_unsigned_equivocation_report(
923		equivocation_proof: EquivocationProof<HeaderFor<T>>,
924		key_owner_proof: T::KeyOwnerProof,
925	) -> Option<()> {
926		T::EquivocationReportSystem::publish_evidence((equivocation_proof, key_owner_proof)).ok()
927	}
928}
929
930impl<T: Config> OnTimestampSet<T::Moment> for Pallet<T> {
931	fn on_timestamp_set(moment: T::Moment) {
932		let slot_duration = Self::slot_duration();
933		assert!(!slot_duration.is_zero(), "Babe slot duration cannot be zero.");
934
935		let timestamp_slot = moment / slot_duration;
936		let timestamp_slot = Slot::from(timestamp_slot.saturated_into::<u64>());
937
938		assert_eq!(
939			CurrentSlot::<T>::get(),
940			timestamp_slot,
941			"Timestamp slot must match `CurrentSlot`"
942		);
943	}
944}
945
946impl<T: Config> frame_support::traits::EstimateNextSessionRotation<BlockNumberFor<T>>
947	for Pallet<T>
948{
949	fn average_session_length() -> BlockNumberFor<T> {
950		T::EpochDuration::get().saturated_into()
951	}
952
953	fn estimate_current_session_progress(_now: BlockNumberFor<T>) -> (Option<Permill>, Weight) {
954		let elapsed = CurrentSlot::<T>::get().saturating_sub(Self::current_epoch_start()) + 1;
955
956		(
957			Some(Permill::from_rational(*elapsed, T::EpochDuration::get())),
958			// Read: Current Slot, Epoch Index, Genesis Slot
959			T::DbWeight::get().reads(3),
960		)
961	}
962
963	fn estimate_next_session_rotation(
964		now: BlockNumberFor<T>,
965	) -> (Option<BlockNumberFor<T>>, Weight) {
966		(
967			Self::next_expected_epoch_change(now),
968			// Read: Current Slot, Epoch Index, Genesis Slot
969			T::DbWeight::get().reads(3),
970		)
971	}
972}
973
974impl<T: Config> frame_support::traits::Lateness<BlockNumberFor<T>> for Pallet<T> {
975	fn lateness(&self) -> BlockNumberFor<T> {
976		Lateness::<T>::get()
977	}
978}
979
980impl<T: Config> sp_runtime::BoundToRuntimeAppPublic for Pallet<T> {
981	type Public = AuthorityId;
982}
983
984impl<T: Config> OneSessionHandler<T::AccountId> for Pallet<T>
985where
986	T: pallet_session::Config,
987{
988	type Key = AuthorityId;
989
990	fn on_genesis_session<'a, I: 'a>(validators: I)
991	where
992		I: Iterator<Item = (&'a T::AccountId, AuthorityId)>,
993	{
994		let authorities = validators.map(|(_, k)| (k, 1)).collect::<Vec<_>>();
995		Self::initialize_genesis_authorities(&authorities);
996	}
997
998	fn on_new_session<'a, I: 'a>(_changed: bool, validators: I, queued_validators: I)
999	where
1000		I: Iterator<Item = (&'a T::AccountId, AuthorityId)>,
1001	{
1002		let authorities = validators.map(|(_account, k)| (k, 1)).collect::<Vec<_>>();
1003		let bounded_authorities = WeakBoundedVec::<_, T::MaxAuthorities>::force_from(
1004			authorities,
1005			Some(
1006				"Warning: The session has more validators than expected. \
1007				A runtime configuration adjustment may be needed.",
1008			),
1009		);
1010
1011		let next_authorities = queued_validators.map(|(_account, k)| (k, 1)).collect::<Vec<_>>();
1012		let next_bounded_authorities = WeakBoundedVec::<_, T::MaxAuthorities>::force_from(
1013			next_authorities,
1014			Some(
1015				"Warning: The session has more queued validators than expected. \
1016				A runtime configuration adjustment may be needed.",
1017			),
1018		);
1019
1020		let session_index = <pallet_session::Pallet<T>>::current_index();
1021
1022		Self::enact_epoch_change(bounded_authorities, next_bounded_authorities, Some(session_index))
1023	}
1024
1025	fn on_disabled(i: u32) {
1026		Self::deposit_consensus(ConsensusLog::OnDisabled(i))
1027	}
1028}
1029
1030// compute randomness for a new epoch. rho is the concatenation of all
1031// VRF outputs in the prior epoch.
1032//
1033// an optional size hint as to how many VRF outputs there were may be provided.
1034fn compute_randomness(
1035	last_epoch_randomness: BabeRandomness,
1036	epoch_index: u64,
1037	rho: impl Iterator<Item = BabeRandomness>,
1038	rho_size_hint: Option<usize>,
1039) -> BabeRandomness {
1040	let mut s = Vec::with_capacity(40 + rho_size_hint.unwrap_or(0) * RANDOMNESS_LENGTH);
1041	s.extend_from_slice(&last_epoch_randomness);
1042	s.extend_from_slice(&epoch_index.to_le_bytes());
1043
1044	for vrf_output in rho {
1045		s.extend_from_slice(&vrf_output[..]);
1046	}
1047
1048	sp_io::hashing::blake2_256(&s)
1049}
1050
1051pub mod migrations {
1052	use super::*;
1053	use frame_support::pallet_prelude::{StorageValue, ValueQuery};
1054
1055	/// Something that can return the storage prefix of the `Babe` pallet.
1056	pub trait BabePalletPrefix: Config {
1057		fn pallet_prefix() -> &'static str;
1058	}
1059
1060	struct __OldNextEpochConfig<T>(core::marker::PhantomData<T>);
1061	impl<T: BabePalletPrefix> frame_support::traits::StorageInstance for __OldNextEpochConfig<T> {
1062		fn pallet_prefix() -> &'static str {
1063			T::pallet_prefix()
1064		}
1065		const STORAGE_PREFIX: &'static str = "NextEpochConfig";
1066	}
1067
1068	type OldNextEpochConfig<T> =
1069		StorageValue<__OldNextEpochConfig<T>, Option<NextConfigDescriptor>, ValueQuery>;
1070
1071	/// A storage migration that adds the current epoch configuration for Babe
1072	/// to storage.
1073	pub fn add_epoch_configuration<T: BabePalletPrefix>(
1074		epoch_config: BabeEpochConfiguration,
1075	) -> Weight {
1076		let mut writes = 0;
1077		let mut reads = 0;
1078
1079		if let Some(pending_change) = OldNextEpochConfig::<T>::get() {
1080			PendingEpochConfigChange::<T>::put(pending_change);
1081
1082			writes += 1;
1083		}
1084
1085		reads += 1;
1086
1087		OldNextEpochConfig::<T>::kill();
1088
1089		EpochConfig::<T>::put(epoch_config.clone());
1090		NextEpochConfig::<T>::put(epoch_config);
1091
1092		writes += 3;
1093
1094		T::DbWeight::get().reads_writes(reads, writes)
1095	}
1096}