pallet_babe/randomness.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//! Provides multiple implementations of the randomness trait based on the on-chain epoch
19//! randomness collected from VRF outputs.
20
21use super::{
22 AuthorVrfRandomness, Config, EpochStart, NextRandomness, Randomness, RANDOMNESS_LENGTH,
23};
24use frame_support::traits::Randomness as RandomnessT;
25use frame_system::pallet_prelude::BlockNumberFor;
26use sp_runtime::traits::{Hash, One, Saturating};
27
28/// Randomness usable by consensus protocols that **depend** upon finality and take action
29/// based upon on-chain commitments made during the epoch before the previous epoch.
30///
31/// An off-chain consensus protocol requires randomness be finalized before usage, but one
32/// extra epoch delay beyond `RandomnessFromOneEpochAgo` suffices, under the assumption
33/// that finality never stalls for longer than one epoch.
34///
35/// All randomness is relative to commitments to any other inputs to the computation: If
36/// Alice samples randomness near perfectly using radioactive decay, but then afterwards
37/// Eve selects an arbitrary value with which to xor Alice's randomness, then Eve always
38/// wins whatever game they play.
39///
40/// All input commitments used with `RandomnessFromTwoEpochsAgo` should come from at least
41/// three epochs ago. We require BABE session keys be registered at least three epochs
42/// before being used to derive `ParentBlockRandomness` for example.
43///
44/// All users learn `RandomnessFromTwoEpochsAgo` when epoch `current_epoch - 1` starts,
45/// although some learn it a few block earlier inside epoch `current_epoch - 2`.
46///
47/// Adversaries with enough block producers could bias this randomness by choosing upon
48/// what their block producers build at the end of epoch `current_epoch - 2` or the
49/// beginning epoch `current_epoch - 1`, or skipping slots at the end of epoch
50/// `current_epoch - 2`.
51///
52/// Adversaries should not possess many block production slots towards the beginning or
53/// end of every epoch, but they possess some influence over when they possess more slots.
54pub struct RandomnessFromTwoEpochsAgo<T>(core::marker::PhantomData<T>);
55
56/// Randomness usable by on-chain code that **does not depend** upon finality and takes
57/// action based upon on-chain commitments made during the previous epoch.
58///
59/// All randomness is relative to commitments to any other inputs to the computation: If
60/// Alice samples randomness near perfectly using radioactive decay, but then afterwards
61/// Eve selects an arbitrary value with which to xor Alice's randomness, then Eve always
62/// wins whatever game they play.
63///
64/// All input commitments used with `RandomnessFromOneEpochAgo` should come from at least
65/// two epochs ago, although the previous epoch might work in special cases under
66/// additional assumption.
67///
68/// All users learn `RandomnessFromOneEpochAgo` at the end of the previous epoch, although
69/// some block producers learn it several block earlier.
70///
71/// Adversaries with enough block producers could bias this randomness by choosing upon
72/// what their block producers build at either the end of the previous epoch or the
73/// beginning of the current epoch, or electing to skipping some of their own block
74/// production slots towards the end of the previous epoch.
75///
76/// Adversaries should not possess many block production slots towards the beginning or
77/// end of every epoch, but they possess some influence over when they possess more slots.
78///
79/// As an example usage, we determine parachain auctions ending times in Polkadot using
80/// `RandomnessFromOneEpochAgo` because it reduces bias from `ParentBlockRandomness` and
81/// does not require the extra finality delay of `RandomnessFromTwoEpochsAgo`.
82pub struct RandomnessFromOneEpochAgo<T>(core::marker::PhantomData<T>);
83
84/// Randomness produced semi-freshly with each block, but inherits limitations of
85/// `RandomnessFromTwoEpochsAgo` from which it derives.
86///
87/// All randomness is relative to commitments to any other inputs to the computation: If
88/// Alice samples randomness near perfectly using radioactive decay, but then afterwards
89/// Eve selects an arbitrary value with which to xor Alice's randomness, then Eve always
90/// wins whatever game they play.
91///
92/// As with `RandomnessFromTwoEpochsAgo`, all input commitments combined with
93/// `ParentBlockRandomness` should come from at least two epoch ago, except preferably
94/// not near epoch ending, and thus ideally three epochs ago.
95///
96/// Almost all users learn this randomness for a given block by the time they receive it's
97/// parent block, which makes this randomness appear fresh enough. Yet, the block producer
98/// themselves learned this randomness at the beginning of epoch `current_epoch - 2`, at
99/// the same time as they learn `RandomnessFromTwoEpochsAgo`.
100///
101/// Aside from just biasing `RandomnessFromTwoEpochsAgo`, adversaries could also bias
102/// `ParentBlockRandomness` by never announcing their block if doing so yields an
103/// unfavorable randomness. As such, `ParentBlockRandomness` should be considered weaker
104/// than both other randomness sources provided by BABE, but `ParentBlockRandomness`
105/// remains constrained by declared staking, while a randomness source like block hash is
106/// only constrained by adversaries' unknowable computational power.
107///
108/// As an example use, parachains could assign block production slots based upon the
109/// `ParentBlockRandomness` of their relay parent or relay parent's parent, provided the
110/// parachain registers collators but avoids censorship sensitive functionality like
111/// slashing. Any parachain with slashing could operate BABE itself or perhaps better yet
112/// a BABE-like approach that derives its `ParentBlockRandomness`, and authorizes block
113/// production, based upon the relay parent's `ParentBlockRandomness` or more likely the
114/// relay parent's `RandomnessFromTwoEpochsAgo`.
115///
116/// NOTE: there is some nuance here regarding what is current and parent randomness. If
117/// you are using this trait from within the runtime (i.e. as part of block execution)
118/// then the randomness provided here will always be generated from the parent block. If
119/// instead you are using this randomness externally, i.e. after block execution, then
120/// this randomness will be provided by the "current" block (this stems from the fact that
121/// we process VRF outputs on block execution finalization, i.e. `on_finalize`).
122pub struct ParentBlockRandomness<T>(core::marker::PhantomData<T>);
123
124/// Randomness produced semi-freshly with each block, but inherits limitations of
125/// `RandomnessFromTwoEpochsAgo` from which it derives.
126///
127/// See [`ParentBlockRandomness`].
128#[deprecated(note = "Should not be relied upon for correctness, \
129 will not provide fresh randomness for the current block. \
130 Please use `ParentBlockRandomness` instead.")]
131pub struct CurrentBlockRandomness<T>(core::marker::PhantomData<T>);
132
133impl<T: Config> RandomnessT<T::Hash, BlockNumberFor<T>> for RandomnessFromTwoEpochsAgo<T> {
134 fn random(subject: &[u8]) -> (T::Hash, BlockNumberFor<T>) {
135 let mut subject = subject.to_vec();
136 subject.reserve(RANDOMNESS_LENGTH);
137 subject.extend_from_slice(&Randomness::<T>::get()[..]);
138
139 (T::Hashing::hash(&subject[..]), EpochStart::<T>::get().0)
140 }
141}
142
143impl<T: Config> RandomnessT<T::Hash, BlockNumberFor<T>> for RandomnessFromOneEpochAgo<T> {
144 fn random(subject: &[u8]) -> (T::Hash, BlockNumberFor<T>) {
145 let mut subject = subject.to_vec();
146 subject.reserve(RANDOMNESS_LENGTH);
147 subject.extend_from_slice(&NextRandomness::<T>::get()[..]);
148
149 (T::Hashing::hash(&subject[..]), EpochStart::<T>::get().1)
150 }
151}
152
153impl<T: Config> RandomnessT<Option<T::Hash>, BlockNumberFor<T>> for ParentBlockRandomness<T> {
154 fn random(subject: &[u8]) -> (Option<T::Hash>, BlockNumberFor<T>) {
155 let random = AuthorVrfRandomness::<T>::get().map(|random| {
156 let mut subject = subject.to_vec();
157 subject.reserve(RANDOMNESS_LENGTH);
158 subject.extend_from_slice(&random);
159
160 T::Hashing::hash(&subject[..])
161 });
162
163 (random, <frame_system::Pallet<T>>::block_number().saturating_sub(One::one()))
164 }
165}
166
167#[allow(deprecated)]
168impl<T: Config> RandomnessT<Option<T::Hash>, BlockNumberFor<T>> for CurrentBlockRandomness<T> {
169 fn random(subject: &[u8]) -> (Option<T::Hash>, BlockNumberFor<T>) {
170 let (random, _) = ParentBlockRandomness::<T>::random(subject);
171 (random, <frame_system::Pallet<T>>::block_number())
172 }
173}