/__w/smoldot/smoldot/repo/lib/src/verify/babe.rs
Line | Count | Source (jump to first uncovered line) |
1 | | // Smoldot |
2 | | // Copyright (C) 2019-2022 Parity Technologies (UK) Ltd. |
3 | | // SPDX-License-Identifier: GPL-3.0-or-later WITH Classpath-exception-2.0 |
4 | | |
5 | | // This program is free software: you can redistribute it and/or modify |
6 | | // it under the terms of the GNU General Public License as published by |
7 | | // the Free Software Foundation, either version 3 of the License, or |
8 | | // (at your option) any later version. |
9 | | |
10 | | // This program is distributed in the hope that it will be useful, |
11 | | // but WITHOUT ANY WARRANTY; without even the implied warranty of |
12 | | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
13 | | // GNU General Public License for more details. |
14 | | |
15 | | // You should have received a copy of the GNU General Public License |
16 | | // along with this program. If not, see <http://www.gnu.org/licenses/>. |
17 | | |
18 | | //! BABE consensus. |
19 | | //! |
20 | | //! BABE, or Blind Assignment for Blockchain Extension, is the consensus algorithm used by |
21 | | //! Polkadot in order to determine who is authorized to generate a block. |
22 | | //! |
23 | | //! Every block (with the exception of the genesis block) must contain, in its header, some data |
24 | | //! that makes it possible to verify that it has been generated by a legitimate author. |
25 | | //! |
26 | | //! References: |
27 | | //! |
28 | | //! - <https://research.web3.foundation/en/latest/polkadot/BABE/Babe.html> |
29 | | //! |
30 | | //! # Overview of BABE |
31 | | //! |
32 | | //! In the BABE algorithm, time is divided into non-overlapping **epochs**, themselves divided |
33 | | //! into **slots**. How long an epoch and a slot are is determined by calling the |
34 | | //! `BabeApi_configuration` runtime entry point. |
35 | | //! |
36 | | //! > **Note**: As example values, in the Polkadot genesis, a slot lasts for 6 seconds and an |
37 | | //! > epoch consists of 2400 slots (in other words, four hours). |
38 | | //! |
39 | | //! Every block that is produced must belong to a specific slot. This slot number can be found in |
40 | | //! the block header, with the exception of the genesis block which is considered timeless and |
41 | | //! doesn't have any slot number. |
42 | | //! |
43 | | //! At the moment, the current slot number is determined purely based on the slot duration (e.g. |
44 | | //! 6 seconds for Polkadot) and the local clock based on the UNIX EPOCH. The current slot |
45 | | //! number is `unix_timestamp / duration_per_slot`. This might change in the future. |
46 | | //! |
47 | | //! The first epoch (epoch number 0) starts at `slot_number(block #1)` and ends at |
48 | | //! `slot_number(block #1) + slots_per_epoch`. The second epoch (epoch #1) starts at slot |
49 | | //! `end_of_epoch_0 + 1`. All epochs end at `start_of_new_epoch + slots_per_epoch`. Block #0 |
50 | | //! doesn't belong to any epoch. |
51 | | //! |
52 | | //! The header of first block produced after a transition to a new epoch (including block #1) must |
53 | | //! contain a log entry indicating the public keys that are allowed to sign blocks, alongside with |
54 | | //! a weight for each of them, and a "randomness value". This information does not concern the |
55 | | //! newly-started epoch, but the one immediately after. In other words, the first block of epoch |
56 | | //! `N` contains the information about epoch `N+1`. |
57 | | //! |
58 | | //! > **Note**: The way the list of authorities and their weights is determined is at the |
59 | | //! > discretion of the runtime code and is out of scope of this module, but it normally |
60 | | //! > corresponds to the list of validators and how much stake is available to them. |
61 | | //! |
62 | | //! In order to produce a block, one must generate, using a |
63 | | //! [VRF (Verifiable Random Function)](https://en.wikipedia.org/wiki/Verifiable_random_function), |
64 | | //! and based on the slot number, genesis hash, and aforementioned "randomness value", |
65 | | //! a number whose value is lower than a certain threshold. |
66 | | //! |
67 | | //! The number that has been generated must be included in the header of the authored block, |
68 | | //! alongside with the proof of the correct generation that can be verified using one of the |
69 | | //! public keys allowed to generate blocks in that epoch. The weight associated to that public key |
70 | | //! determines the allowed threshold. |
71 | | //! |
72 | | //! The "randomness value" of an epoch `N` is calculated by combining the generated numbers of all |
73 | | //! the blocks of the epoch `N - 2`. |
74 | | //! |
75 | | //! ## Secondary slots |
76 | | //! |
77 | | //! While all slots can be claimed by generating a number below a certain threshold, each slot is |
78 | | //! additionally assigned to a specific public key amongst the ones allowed. The owner of a |
79 | | //! public key is always allowed to generate a block during the slot assigned to it. |
80 | | //! |
81 | | //! The mechanism of attributing each slot to a public key is called "secondary slot claims", |
82 | | //! while the mechanism of generating a number below a certain threshold is called a "primary |
83 | | //! slot claim". As their name indicates, primary slot claims have a higher priority over |
84 | | //! secondary slot claims. |
85 | | //! |
86 | | //! Secondary slot claims are a way to guarantee that all slots can potentially lead to a block |
87 | | //! being produced. |
88 | | //! |
89 | | //! ## Chain selection |
90 | | //! |
91 | | //! The "best" block of a chain in the BABE algorithm is the one with the highest slot number. |
92 | | //! If there exists multiple blocks on the same slot, the best block is one with the highest number |
93 | | //! of primary slot claims. In other words, if two blocks have the same parent, but one is a |
94 | | //! primary slot claim and the other is a secondary slot claim, we prefer the one with the primary |
95 | | //! slot claim. |
96 | | //! |
97 | | //! Keep in mind that there can still be draws in terms of primary slot claims count, in which |
98 | | //! case the winning block is the one upon which the next block author builds upon. |
99 | | //! |
100 | | //! ## Epochs 0 and 1 |
101 | | //! |
102 | | //! The information about an epoch `N` is provided by the first block of the epoch `N-1`. |
103 | | //! |
104 | | //! Because of this, we need to special-case epoch 0. The information about epoch 0 is contained |
105 | | //! in the chain-wide BABE configuration found in the runtime. The first block of epoch 0 is the |
106 | | //! block number #1. The information about epoch 1 is therefore contained in block #1. |
107 | | //! |
108 | | //! # Usage |
109 | | //! |
110 | | //! In order to verify a Babe block, two of the main information to pass are: |
111 | | //! |
112 | | //! - The [`chain_information::BabeEpochInformationRef`] struct corresponding to the epoch the |
113 | | //! parent block belongs to. |
114 | | //! - The [`chain_information::BabeEpochInformationRef`] struct of the epoch that follows. |
115 | | //! |
116 | | //! When verifying block number 1, [`VerifyConfig::parent_block_epoch`] must be set to `None` and |
117 | | //! [`VerifyConfig::parent_block_next_epoch`] must be set to the definition of epoch #0 as |
118 | | //! determined by performing runtime calls. |
119 | | //! |
120 | | //! Any time verifying a block produces a `Some` in [`VerifySuccess::epoch_transition_target`], |
121 | | //! which is guaranteed to be the case when verifying block number 1, an epoch transition occurs. |
122 | | //! When verifying a child of such block, the value formerly passed as |
123 | | //! [`VerifyConfig::parent_block_next_epoch`] must now be passed as |
124 | | //! [`VerifyConfig::parent_block_epoch`], and the value in |
125 | | //! [`VerifySuccess::epoch_transition_target`] becomes [`VerifyConfig::parent_block_next_epoch`]. |
126 | | //! |
127 | | //! When designing around these rules, be aware of forks: there can be multiple blocks at the same |
128 | | //! height performing epoch transitions. |
129 | | //! |
130 | | //! See also the [`crate::chain::chain_information`] module for more help. |
131 | | |
132 | | use crate::{chain::chain_information, header}; |
133 | | |
134 | | use core::{num::NonZeroU64, time::Duration}; |
135 | | |
136 | | /// Configuration for [`verify_header`]. |
137 | | pub struct VerifyConfig<'a> { |
138 | | /// Header of the block to verify. |
139 | | pub header: header::HeaderRef<'a>, |
140 | | |
141 | | /// Number of bytes used to encode the block number in the header. |
142 | | pub block_number_bytes: usize, |
143 | | |
144 | | /// Header of the parent of the block to verify. |
145 | | /// |
146 | | /// [`verify_header`] assumes that this block has been successfully verified before. |
147 | | /// |
148 | | /// The hash of this header must be the one referenced in [`VerifyConfig::header`]. |
149 | | pub parent_block_header: header::HeaderRef<'a>, |
150 | | |
151 | | /// Time elapsed since [the Unix Epoch](https://en.wikipedia.org/wiki/Unix_time) (i.e. |
152 | | /// 00:00:00 UTC on 1 January 1970), ignoring leap seconds. |
153 | | // TODO: unused, should check against a block's slot |
154 | | pub now_from_unix_epoch: Duration, |
155 | | |
156 | | /// Number of slots per epoch in the Babe configuration. |
157 | | pub slots_per_epoch: NonZeroU64, |
158 | | |
159 | | /// Epoch the parent block belongs to. Must be `None` if and only if the parent block's number |
160 | | /// is 0, as block #0 doesn't belong to any epoch. |
161 | | /// |
162 | | /// If `Some`, then the [`chain_information::BabeEpochInformationRef::start_slot_number`] |
163 | | /// must be `Some`. |
164 | | pub parent_block_epoch: Option<chain_information::BabeEpochInformationRef<'a>>, |
165 | | |
166 | | /// Epoch that follows the epoch the parent block belongs to. |
167 | | /// |
168 | | /// The [`chain_information::BabeEpochInformationRef::start_slot_number`] must be `None` if |
169 | | /// and only if the [`chain_information::BabeEpochInformationRef::epoch_index`] is `0`. |
170 | | pub parent_block_next_epoch: chain_information::BabeEpochInformationRef<'a>, |
171 | | } |
172 | | |
173 | | /// Information yielded back after successfully verifying a block. |
174 | | #[derive(Debug)] |
175 | | pub struct VerifySuccess { |
176 | | /// Slot number the block belongs to. |
177 | | /// |
178 | | /// > **Note**: This is a simple reminder. The value can also be found in the header of the |
179 | | /// > block. |
180 | | pub slot_number: u64, |
181 | | |
182 | | /// `true` if the claimed slot is a primary slot. `false` if it is a secondary slot. |
183 | | pub is_primary_slot: bool, |
184 | | |
185 | | /// If `Some`, the verified block contains an epoch transition describing the new "next epoch". |
186 | | /// When verifying blocks that are children of this one, the value in this field must be |
187 | | /// provided as [`VerifyConfig::parent_block_next_epoch`], and the value previously in |
188 | | /// [`VerifyConfig::parent_block_next_epoch`] must instead be passed as |
189 | | /// [`VerifyConfig::parent_block_epoch`]. |
190 | | /// |
191 | | /// The new epoch information is guaranteed to be valid. |
192 | | pub epoch_transition_target: Option<chain_information::BabeEpochInformation>, |
193 | | } |
194 | | |
195 | | /// Failure to verify a block. |
196 | 0 | #[derive(Debug, derive_more::Display)] Unexecuted instantiation: _RNvXs0_NtNtCsN16ciHI6Qf_7smoldot6verify4babeNtB5_11VerifyErrorNtNtCsaYZPK01V26L_4core3fmt7Display3fmt Unexecuted instantiation: _RNvXs0_NtNtCseuYC0Zibziv_7smoldot6verify4babeNtB5_11VerifyErrorNtNtCsaYZPK01V26L_4core3fmt7Display3fmt |
197 | | pub enum VerifyError { |
198 | | /// The seal (containing the signature of the authority) is missing from the header. |
199 | | MissingSeal, |
200 | | /// No pre-runtime digest in the block header. |
201 | | MissingPreRuntimeDigest, |
202 | | /// Parent block doesn't contain any Babe information. |
203 | | ParentIsntBabeConsensus, |
204 | | /// Slot number must be strictly increasing between a parent and its child. |
205 | | SlotNumberNotIncreasing, |
206 | | /// Block contains an epoch change digest log, but no epoch change is to be performed. |
207 | | UnexpectedEpochChangeLog, |
208 | | /// Block is the first block after a new epoch, but it is missing an epoch change digest log. |
209 | | MissingEpochChangeLog, |
210 | | /// The header contains an epoch change that would put the Babe configuration in an |
211 | | /// non-sensical state. |
212 | | #[display(fmt = "Invalid Babe epoch change found in header: {_0}")] |
213 | | InvalidBabeParametersChange(chain_information::BabeValidityError), |
214 | | /// Authority index stored within block is out of range. |
215 | | InvalidAuthorityIndex, |
216 | | /// Public key used to for the signature is invalid. |
217 | | BadPublicKey, |
218 | | /// Block header signature is invalid. |
219 | | BadSignature, |
220 | | /// VRF proof in the block header is invalid. |
221 | | BadVrfProof, |
222 | | /// Block is a secondary slot claim and its author is not the expected author. |
223 | | BadSecondarySlotAuthor, |
224 | | /// VRF output is over threshold required to claim the primary slot. |
225 | | OverPrimaryClaimThreshold, |
226 | | /// Type of slot claim forbidden by current configuration. |
227 | | ForbiddenSlotType, |
228 | | /// Overflow when calculating the starting slot of the next epoch. |
229 | | NextEpochStartSlotNumberOverflow, |
230 | | /// Overflow when calculating the index of the next epoch. |
231 | | EpochIndexOverflow, |
232 | | /// The configuration of the chain is invalid. It can't be determined whether the block is |
233 | | /// valid or not. |
234 | | InvalidChainConfiguration(InvalidChainConfiguration), |
235 | | } |
236 | | |
237 | | /// See [`VerifyError::InvalidChainConfiguration`] |
238 | 0 | #[derive(Debug, derive_more::Display)] Unexecuted instantiation: _RNvXs2_NtNtCsN16ciHI6Qf_7smoldot6verify4babeNtB5_25InvalidChainConfigurationNtNtCsaYZPK01V26L_4core3fmt7Display3fmt Unexecuted instantiation: _RNvXs2_NtNtCseuYC0Zibziv_7smoldot6verify4babeNtB5_25InvalidChainConfigurationNtNtCsaYZPK01V26L_4core3fmt7Display3fmt |
239 | | pub enum InvalidChainConfiguration { |
240 | | /// The start slot of the epoch the parent block belongs to is superior to the slot where the |
241 | | /// parent block was authored. |
242 | | ParentEpochStartSlotWithBlockMismatch, |
243 | | /// No current epoch was provided, but the next epoch has an index equal to 0. |
244 | | NoCurrentEpochButNextEpochNonZero, |
245 | | /// The next epoch has a non-zero epoch index, but has a start slot. |
246 | | NonZeroNextEpochYetHasStartSlot, |
247 | | /// Parent block doesn't belong to any epoch but is not the genesis block. |
248 | | NonGenesisBlockNoCurrentEpoch, |
249 | | } |
250 | | |
251 | | /// Verifies whether a block header provides a correct proof of the legitimacy of the authorship. |
252 | 4 | pub fn verify_header(config: VerifyConfig) -> Result<VerifySuccess, VerifyError> { |
253 | | // TODO: handle OnDisabled |
254 | | |
255 | | // Gather the BABE-related information from the header. |
256 | 4 | let (authority_index, slot_number, is_primary_slot, vrf_output_and_proof) = |
257 | 4 | match config.header.digest.babe_pre_runtime() { |
258 | 2 | Some(header::BabePreDigestRef::Primary(digest)) => ( |
259 | 2 | digest.authority_index, |
260 | 2 | digest.slot_number, |
261 | 2 | true, |
262 | 2 | Some((*digest.vrf_output, *digest.vrf_proof)), |
263 | 2 | ), |
264 | 2 | Some(header::BabePreDigestRef::SecondaryPlain(digest)) => { |
265 | 2 | (digest.authority_index, digest.slot_number, false, None) |
266 | | } |
267 | 0 | Some(header::BabePreDigestRef::SecondaryVRF(digest)) => ( |
268 | 0 | digest.authority_index, |
269 | 0 | digest.slot_number, |
270 | 0 | false, |
271 | 0 | Some((*digest.vrf_output, *digest.vrf_proof)), |
272 | 0 | ), |
273 | 0 | None => return Err(VerifyError::MissingPreRuntimeDigest), |
274 | | }; |
275 | | |
276 | | // Make sure that the slot of the block is increasing compared to its parent's. |
277 | 4 | let parent_slot_number = if config.parent_block_header.number != 0 { |
278 | 2 | let parent_slot_number = match config.parent_block_header.digest.babe_pre_runtime() { |
279 | 2 | Some(pr) => pr.slot_number(), |
280 | 0 | None => return Err(VerifyError::ParentIsntBabeConsensus), |
281 | | }; |
282 | | |
283 | 2 | if slot_number <= parent_slot_number { |
284 | 0 | return Err(VerifyError::SlotNumberNotIncreasing); |
285 | 2 | } |
286 | 2 | |
287 | 2 | Some(parent_slot_number) |
288 | | } else { |
289 | 2 | None |
290 | | }; |
291 | | |
292 | | // Verify consistency of the configuration. |
293 | 4 | if let Some(curr2 ) = &config.parent_block_epoch { |
294 | 2 | if curr.start_slot_number.map_or(true, |epoch_start| { |
295 | 2 | parent_slot_number.map_or(true, |parent_slot_number| epoch_start > parent_slot_number) _RNCNCNvNtNtCsN16ciHI6Qf_7smoldot6verify4babe13verify_header00B9_ Line | Count | Source | 295 | 2 | parent_slot_number.map_or(true, |parent_slot_number| epoch_start > parent_slot_number) |
Unexecuted instantiation: _RNCNCNvNtNtCseuYC0Zibziv_7smoldot6verify4babe13verify_header00B9_ |
296 | 2 | }) { _RNCNvNtNtCsN16ciHI6Qf_7smoldot6verify4babe13verify_header0B7_ Line | Count | Source | 294 | 2 | if curr.start_slot_number.map_or(true, |epoch_start| { | 295 | 2 | parent_slot_number.map_or(true, |parent_slot_number| epoch_start > parent_slot_number) | 296 | 2 | }) { |
Unexecuted instantiation: _RNCNvNtNtCseuYC0Zibziv_7smoldot6verify4babe13verify_header0B7_ |
297 | 0 | return Err(VerifyError::InvalidChainConfiguration( |
298 | 0 | InvalidChainConfiguration::ParentEpochStartSlotWithBlockMismatch, |
299 | 0 | )); |
300 | 2 | } |
301 | 2 | } else if config.parent_block_next_epoch.epoch_index != 0 { |
302 | 0 | return Err(VerifyError::InvalidChainConfiguration( |
303 | 0 | InvalidChainConfiguration::NoCurrentEpochButNextEpochNonZero, |
304 | 0 | )); |
305 | 2 | } else if config.parent_block_header.number != 0 { |
306 | 0 | return Err(VerifyError::InvalidChainConfiguration( |
307 | 0 | InvalidChainConfiguration::NonGenesisBlockNoCurrentEpoch, |
308 | 0 | )); |
309 | 2 | } |
310 | 4 | if (config.parent_block_next_epoch.epoch_index == 0) |
311 | 4 | != config.parent_block_next_epoch.start_slot_number.is_none() |
312 | | { |
313 | 0 | return Err(VerifyError::InvalidChainConfiguration( |
314 | 0 | InvalidChainConfiguration::NonZeroNextEpochYetHasStartSlot, |
315 | 0 | )); |
316 | 4 | } |
317 | | |
318 | | // Verify the epoch transition of the block. |
319 | | // `block_epoch_info` contains the epoch the block belongs to. |
320 | 4 | let block_epoch_info = match ( |
321 | 4 | &config.parent_block_epoch, |
322 | 4 | config.header.digest.babe_epoch_information().is_some(), |
323 | | ) { |
324 | 2 | (Some(parent_epoch), false) => parent_epoch, |
325 | | (None, false) => { |
326 | 0 | return Err(VerifyError::MissingEpochChangeLog); |
327 | | } |
328 | | (Some(_), true) |
329 | 0 | if config |
330 | 0 | .parent_block_next_epoch |
331 | 0 | .start_slot_number |
332 | 0 | .map_or(true, |n| n <= slot_number) => Unexecuted instantiation: _RNCNvNtNtCsN16ciHI6Qf_7smoldot6verify4babe13verify_headers_0B7_ Unexecuted instantiation: _RNCNvNtNtCseuYC0Zibziv_7smoldot6verify4babe13verify_headers_0B7_ |
333 | 0 | { |
334 | 0 | &config.parent_block_next_epoch |
335 | | } |
336 | | (Some(_), true) => { |
337 | 0 | return Err(VerifyError::UnexpectedEpochChangeLog); |
338 | | } |
339 | | (None, true) => { |
340 | | // Should only happen if the block being verified is block 1. It is, however, not the |
341 | | // responsibility of this module to check whether the block number is equal to the |
342 | | // parent's plus one. |
343 | 2 | &config.parent_block_next_epoch |
344 | | } |
345 | | }; |
346 | | |
347 | | // Check if the current slot number indicates that entire epochs have been skipped. |
348 | 4 | let skipped_epochs = if let Some(epoch_start_slot2 ) = block_epoch_info.start_slot_number { |
349 | | // We have checked that the slot number of the block is superior to its parent's, and |
350 | | // we have checked that the parent's slot number is superior or equal to the epoch |
351 | | // start slot number, and we have checked that the epoch cannot transition if the |
352 | | // slot number of the block is inferior to the next epoch start. Consequently, the |
353 | | // substraction below cannot underflow. |
354 | 2 | (slot_number - epoch_start_slot) / config.slots_per_epoch // `slots_per_epoch` is a `NonZero` type |
355 | | } else { |
356 | 2 | 0 |
357 | | }; |
358 | | |
359 | | // Calculate the epoch index of the epoch of the block. |
360 | | // This is the vast majority of the time equal to `block_epoch_info.epoch_index`. However, |
361 | | // if no block has been produced for an entire epoch, the value needs to be increased by the |
362 | | // number of skipped epochs. |
363 | | // Note that this calculation can only overflow in case where the `epoch_index` is superior |
364 | | // to its starting slot, and that `slots_per_epoch` is 1. In other words, this is expected to |
365 | | // never overflow as something else would overflow beforehand. But we prefer to return an error |
366 | | // rather than unwrap in order to avoid all possible panicking situations. |
367 | 4 | let block_epoch_index = block_epoch_info |
368 | 4 | .epoch_index |
369 | 4 | .checked_add(skipped_epochs) |
370 | 4 | .ok_or(VerifyError::EpochIndexOverflow)?0 ; |
371 | | |
372 | | // TODO: in case of epoch change, should also check the randomness value; while the runtime |
373 | | // checks that the randomness value is correct, light clients in particular do not |
374 | | // execute the runtime |
375 | | |
376 | | // Check that the claim is one of the allowed slot types. |
377 | | match ( |
378 | 4 | block_epoch_info.allowed_slots, |
379 | 4 | is_primary_slot, |
380 | 4 | vrf_output_and_proof, |
381 | | ) { |
382 | 0 | (_, true, None) => unreachable!(), |
383 | 2 | (_, true, Some(_)) => {} |
384 | 2 | (header::BabeAllowedSlots::PrimaryAndSecondaryPlainSlots, false, None) => {} |
385 | 0 | (header::BabeAllowedSlots::PrimaryAndSecondaryVrfSlots, false, Some(_)) => {} |
386 | 0 | _ => return Err(VerifyError::ForbiddenSlotType), |
387 | | } |
388 | | |
389 | | // Signature contained in the seal is copied and stored for later. |
390 | 4 | let seal_signature = match config.header.digest.babe_seal() { |
391 | 4 | Some(seal) => { |
392 | 4 | schnorrkel::Signature::from_bytes(seal).map_err(|_| VerifyError::BadSignature0 )?0 Unexecuted instantiation: _RNCNvNtNtCsN16ciHI6Qf_7smoldot6verify4babe13verify_headers0_0B7_ Unexecuted instantiation: _RNCNvNtNtCseuYC0Zibziv_7smoldot6verify4babe13verify_headers0_0B7_ |
393 | | } |
394 | 0 | None => return Err(VerifyError::MissingSeal), |
395 | | }; |
396 | | |
397 | | // If the block contains an epoch transition, build the information about the new epoch. |
398 | | // This is done now, as the header is consumed below. |
399 | 4 | let epoch_transition_target = |
400 | 4 | if let Some((info, maybe_config2 )) = config.header.digest.babe_epoch_information() { |
401 | 2 | let start_slot_number = Some( |
402 | 2 | block_epoch_info |
403 | 2 | .start_slot_number |
404 | 2 | .unwrap_or(slot_number) |
405 | 2 | .checked_add(config.slots_per_epoch.get()) |
406 | 2 | .ok_or(VerifyError::NextEpochStartSlotNumberOverflow)?0 |
407 | | // If some epochs have been skipped, we need to adjust the starting slot of |
408 | | // the next epoch. |
409 | | .checked_add( |
410 | 2 | skipped_epochs |
411 | 2 | .checked_mul(config.slots_per_epoch.get()) |
412 | 2 | .ok_or(VerifyError::NextEpochStartSlotNumberOverflow)?0 , |
413 | | ) |
414 | 2 | .ok_or(VerifyError::NextEpochStartSlotNumberOverflow)?0 , |
415 | | ); |
416 | | |
417 | | Some(chain_information::BabeEpochInformation { |
418 | 2 | epoch_index: block_epoch_index |
419 | 2 | .checked_add(1) |
420 | 2 | .ok_or(VerifyError::EpochIndexOverflow)?0 , |
421 | 2 | start_slot_number, |
422 | 2 | authorities: info.authorities.map(Into::into).collect(), |
423 | 2 | randomness: *info.randomness, |
424 | 2 | c: maybe_config.map_or(block_epoch_info.c, |config| config.c0 ), Unexecuted instantiation: _RNCNvNtNtCsN16ciHI6Qf_7smoldot6verify4babe13verify_headers1_0B7_ Unexecuted instantiation: _RNCNvNtNtCseuYC0Zibziv_7smoldot6verify4babe13verify_headers1_0B7_ |
425 | 2 | allowed_slots: maybe_config.map_or(block_epoch_info.allowed_slots, |config| { |
426 | 0 | config.allowed_slots |
427 | 2 | }), Unexecuted instantiation: _RNCNvNtNtCsN16ciHI6Qf_7smoldot6verify4babe13verify_headers2_0B7_ Unexecuted instantiation: _RNCNvNtNtCseuYC0Zibziv_7smoldot6verify4babe13verify_headers2_0B7_ |
428 | | }) |
429 | | } else { |
430 | 2 | None |
431 | | }; |
432 | | |
433 | | // Make sure that the header wouldn't put Babe in a non-sensical state. |
434 | 4 | if let Some(epoch_transition_target2 ) = &epoch_transition_target { |
435 | 2 | if let Err(err0 ) = epoch_transition_target.validate() { |
436 | 0 | return Err(VerifyError::InvalidBabeParametersChange(err)); |
437 | 2 | } |
438 | 2 | } |
439 | | |
440 | | // The signature in the seal applies to the header from where the signature isn't present. |
441 | | // Build the hash that is expected to be signed. |
442 | | // The signature cannot be verified yet, as the public key of the signer isn't known. |
443 | 4 | let pre_seal_hash = { |
444 | 4 | let mut unsealed_header = config.header; |
445 | 4 | let _popped = unsealed_header.digest.pop_seal(); |
446 | 4 | debug_assert!(matches!0 (_popped, Some(header::Seal::Babe(_)))); |
447 | 4 | unsealed_header.hash(config.block_number_bytes) |
448 | | }; |
449 | | |
450 | | // Fetch the authority that has supposedly signed the block. |
451 | 4 | let signing_authority = block_epoch_info |
452 | 4 | .authorities |
453 | 4 | .clone() |
454 | 4 | .nth(usize::try_from(authority_index).map_err(|_| VerifyError::InvalidAuthorityIndex0 )?0 ) Unexecuted instantiation: _RNCNvNtNtCsN16ciHI6Qf_7smoldot6verify4babe13verify_headers3_0B7_ Unexecuted instantiation: _RNCNvNtNtCseuYC0Zibziv_7smoldot6verify4babe13verify_headers3_0B7_ |
455 | 4 | .ok_or(VerifyError::InvalidAuthorityIndex)?0 ; |
456 | | |
457 | | // Now verifying the signature in the seal. |
458 | 4 | let signing_public_key = schnorrkel::PublicKey::from_bytes(signing_authority.public_key) |
459 | 4 | .map_err(|_| VerifyError::BadPublicKey0 )?0 ; Unexecuted instantiation: _RNCNvNtNtCsN16ciHI6Qf_7smoldot6verify4babe13verify_headers4_0B7_ Unexecuted instantiation: _RNCNvNtNtCseuYC0Zibziv_7smoldot6verify4babe13verify_headers4_0B7_ |
460 | 4 | signing_public_key |
461 | 4 | .verify_simple(b"substrate", &pre_seal_hash, &seal_signature) |
462 | 4 | .map_err(|_| VerifyError::BadSignature0 )?0 ; Unexecuted instantiation: _RNCNvNtNtCsN16ciHI6Qf_7smoldot6verify4babe13verify_headers5_0B7_ Unexecuted instantiation: _RNCNvNtNtCseuYC0Zibziv_7smoldot6verify4babe13verify_headers5_0B7_ |
463 | | |
464 | | // Now verify the VRF output and proof, if any. |
465 | | // The lack of VRF output/proof in the header is checked when we check whether the slot |
466 | | // type is allowed by the current configuration. |
467 | 4 | if let Some((vrf_output, vrf_proof2 )) = vrf_output_and_proof { |
468 | | // In order to verify the VRF output, we first need to create a transcript containing all |
469 | | // the data to verify the VRF against. |
470 | 2 | let transcript = { |
471 | 2 | let mut transcript = merlin::Transcript::new(&b"BABE"[..]); |
472 | 2 | transcript.append_u64(b"slot number", slot_number); |
473 | 2 | transcript.append_u64(b"current epoch", block_epoch_index); |
474 | 2 | transcript.append_message(b"chain randomness", &block_epoch_info.randomness[..]); |
475 | 2 | transcript |
476 | 2 | }; |
477 | 2 | |
478 | 2 | // These `unwrap()`s can only panic if `vrf_output` or `vrf_proof` are of the wrong |
479 | 2 | // length, which we know can't happen as they're of types `[u8; 32]` and `[u8; 64]`. |
480 | 2 | let vrf_output = schnorrkel::vrf::VRFPreOut::from_bytes(&vrf_output[..]).unwrap(); |
481 | 2 | let vrf_proof = schnorrkel::vrf::VRFProof::from_bytes(&vrf_proof[..]).unwrap(); |
482 | | |
483 | 2 | let (vrf_in_out, _) = signing_public_key |
484 | 2 | .vrf_verify(transcript, &vrf_output, &vrf_proof) |
485 | 2 | .map_err(|_| VerifyError::BadVrfProof0 )?0 ; Unexecuted instantiation: _RNCNvNtNtCsN16ciHI6Qf_7smoldot6verify4babe13verify_headers6_0B7_ Unexecuted instantiation: _RNCNvNtNtCseuYC0Zibziv_7smoldot6verify4babe13verify_headers6_0B7_ |
486 | | |
487 | | // If this is a primary slot claim, we need to make sure that the VRF output is below |
488 | | // a certain threshold, otherwise all the authorities could claim all the slots. |
489 | 2 | if is_primary_slot { |
490 | 2 | let threshold = calculate_primary_threshold( |
491 | 2 | block_epoch_info.c, |
492 | 12 | block_epoch_info.authorities.clone().map(|a| a.weight), _RNCNvNtNtCsN16ciHI6Qf_7smoldot6verify4babe13verify_headers7_0B7_ Line | Count | Source | 492 | 12 | block_epoch_info.authorities.clone().map(|a| a.weight), |
Unexecuted instantiation: _RNCNvNtNtCseuYC0Zibziv_7smoldot6verify4babe13verify_headers7_0B7_ |
493 | 2 | signing_authority.weight, |
494 | 2 | ); |
495 | 2 | if u128::from_le_bytes(vrf_in_out.make_bytes::<[u8; 16]>(b"substrate-babe-vrf")) |
496 | 2 | >= threshold |
497 | | { |
498 | 0 | return Err(VerifyError::OverPrimaryClaimThreshold); |
499 | 2 | } |
500 | 0 | } |
501 | | } else { |
502 | 2 | debug_assert!(!is_primary_slot); |
503 | | } |
504 | | |
505 | | // Each slot can be claimed by one specific authority in what is called a secondary slot |
506 | | // claim. If the block is a secondary slot claim, we need to make sure that the author |
507 | | // is indeed the one that is expected. |
508 | 4 | if !is_primary_slot { |
509 | | // Expected author is determined based on `blake2(randomness | slot_number)`. |
510 | 2 | let hash = { |
511 | 2 | let mut hash = blake2_rfc::blake2b::Blake2b::new(32); |
512 | 2 | hash.update(block_epoch_info.randomness); |
513 | 2 | hash.update(&slot_number.to_le_bytes()); |
514 | 2 | hash.finalize() |
515 | | }; |
516 | | |
517 | | // The expected authority index is `hash % num_authorities`. |
518 | 2 | let expected_authority_index = { |
519 | 2 | let hash = num_bigint::BigUint::from_bytes_be(hash.as_bytes()); |
520 | 2 | let authorities_len = num_bigint::BigUint::from(block_epoch_info.authorities.len()); |
521 | 2 | debug_assert_ne!(block_epoch_info.authorities.len(), 0); |
522 | 2 | hash % authorities_len |
523 | 2 | }; |
524 | 2 | |
525 | 2 | if num_traits::cast::ToPrimitive::to_u32(&expected_authority_index) |
526 | 2 | .map_or(true, |v| v != authority_index) _RNCNvNtNtCsN16ciHI6Qf_7smoldot6verify4babe13verify_headers8_0B7_ Line | Count | Source | 526 | 2 | .map_or(true, |v| v != authority_index) |
Unexecuted instantiation: _RNCNvNtNtCseuYC0Zibziv_7smoldot6verify4babe13verify_headers8_0B7_ |
527 | | { |
528 | 0 | return Err(VerifyError::BadSecondarySlotAuthor); |
529 | 2 | } |
530 | 2 | } |
531 | | |
532 | | // Success! 🚀 |
533 | 4 | Ok(VerifySuccess { |
534 | 4 | slot_number, |
535 | 4 | is_primary_slot, |
536 | 4 | epoch_transition_target, |
537 | 4 | }) |
538 | 4 | } _RNvNtNtCsN16ciHI6Qf_7smoldot6verify4babe13verify_header Line | Count | Source | 252 | 4 | pub fn verify_header(config: VerifyConfig) -> Result<VerifySuccess, VerifyError> { | 253 | | // TODO: handle OnDisabled | 254 | | | 255 | | // Gather the BABE-related information from the header. | 256 | 4 | let (authority_index, slot_number, is_primary_slot, vrf_output_and_proof) = | 257 | 4 | match config.header.digest.babe_pre_runtime() { | 258 | 2 | Some(header::BabePreDigestRef::Primary(digest)) => ( | 259 | 2 | digest.authority_index, | 260 | 2 | digest.slot_number, | 261 | 2 | true, | 262 | 2 | Some((*digest.vrf_output, *digest.vrf_proof)), | 263 | 2 | ), | 264 | 2 | Some(header::BabePreDigestRef::SecondaryPlain(digest)) => { | 265 | 2 | (digest.authority_index, digest.slot_number, false, None) | 266 | | } | 267 | 0 | Some(header::BabePreDigestRef::SecondaryVRF(digest)) => ( | 268 | 0 | digest.authority_index, | 269 | 0 | digest.slot_number, | 270 | 0 | false, | 271 | 0 | Some((*digest.vrf_output, *digest.vrf_proof)), | 272 | 0 | ), | 273 | 0 | None => return Err(VerifyError::MissingPreRuntimeDigest), | 274 | | }; | 275 | | | 276 | | // Make sure that the slot of the block is increasing compared to its parent's. | 277 | 4 | let parent_slot_number = if config.parent_block_header.number != 0 { | 278 | 2 | let parent_slot_number = match config.parent_block_header.digest.babe_pre_runtime() { | 279 | 2 | Some(pr) => pr.slot_number(), | 280 | 0 | None => return Err(VerifyError::ParentIsntBabeConsensus), | 281 | | }; | 282 | | | 283 | 2 | if slot_number <= parent_slot_number { | 284 | 0 | return Err(VerifyError::SlotNumberNotIncreasing); | 285 | 2 | } | 286 | 2 | | 287 | 2 | Some(parent_slot_number) | 288 | | } else { | 289 | 2 | None | 290 | | }; | 291 | | | 292 | | // Verify consistency of the configuration. | 293 | 4 | if let Some(curr2 ) = &config.parent_block_epoch { | 294 | 2 | if curr.start_slot_number.map_or(true, |epoch_start| { | 295 | | parent_slot_number.map_or(true, |parent_slot_number| epoch_start > parent_slot_number) | 296 | 2 | }) { | 297 | 0 | return Err(VerifyError::InvalidChainConfiguration( | 298 | 0 | InvalidChainConfiguration::ParentEpochStartSlotWithBlockMismatch, | 299 | 0 | )); | 300 | 2 | } | 301 | 2 | } else if config.parent_block_next_epoch.epoch_index != 0 { | 302 | 0 | return Err(VerifyError::InvalidChainConfiguration( | 303 | 0 | InvalidChainConfiguration::NoCurrentEpochButNextEpochNonZero, | 304 | 0 | )); | 305 | 2 | } else if config.parent_block_header.number != 0 { | 306 | 0 | return Err(VerifyError::InvalidChainConfiguration( | 307 | 0 | InvalidChainConfiguration::NonGenesisBlockNoCurrentEpoch, | 308 | 0 | )); | 309 | 2 | } | 310 | 4 | if (config.parent_block_next_epoch.epoch_index == 0) | 311 | 4 | != config.parent_block_next_epoch.start_slot_number.is_none() | 312 | | { | 313 | 0 | return Err(VerifyError::InvalidChainConfiguration( | 314 | 0 | InvalidChainConfiguration::NonZeroNextEpochYetHasStartSlot, | 315 | 0 | )); | 316 | 4 | } | 317 | | | 318 | | // Verify the epoch transition of the block. | 319 | | // `block_epoch_info` contains the epoch the block belongs to. | 320 | 4 | let block_epoch_info = match ( | 321 | 4 | &config.parent_block_epoch, | 322 | 4 | config.header.digest.babe_epoch_information().is_some(), | 323 | | ) { | 324 | 2 | (Some(parent_epoch), false) => parent_epoch, | 325 | | (None, false) => { | 326 | 0 | return Err(VerifyError::MissingEpochChangeLog); | 327 | | } | 328 | | (Some(_), true) | 329 | 0 | if config | 330 | 0 | .parent_block_next_epoch | 331 | 0 | .start_slot_number | 332 | 0 | .map_or(true, |n| n <= slot_number) => | 333 | 0 | { | 334 | 0 | &config.parent_block_next_epoch | 335 | | } | 336 | | (Some(_), true) => { | 337 | 0 | return Err(VerifyError::UnexpectedEpochChangeLog); | 338 | | } | 339 | | (None, true) => { | 340 | | // Should only happen if the block being verified is block 1. It is, however, not the | 341 | | // responsibility of this module to check whether the block number is equal to the | 342 | | // parent's plus one. | 343 | 2 | &config.parent_block_next_epoch | 344 | | } | 345 | | }; | 346 | | | 347 | | // Check if the current slot number indicates that entire epochs have been skipped. | 348 | 4 | let skipped_epochs = if let Some(epoch_start_slot2 ) = block_epoch_info.start_slot_number { | 349 | | // We have checked that the slot number of the block is superior to its parent's, and | 350 | | // we have checked that the parent's slot number is superior or equal to the epoch | 351 | | // start slot number, and we have checked that the epoch cannot transition if the | 352 | | // slot number of the block is inferior to the next epoch start. Consequently, the | 353 | | // substraction below cannot underflow. | 354 | 2 | (slot_number - epoch_start_slot) / config.slots_per_epoch // `slots_per_epoch` is a `NonZero` type | 355 | | } else { | 356 | 2 | 0 | 357 | | }; | 358 | | | 359 | | // Calculate the epoch index of the epoch of the block. | 360 | | // This is the vast majority of the time equal to `block_epoch_info.epoch_index`. However, | 361 | | // if no block has been produced for an entire epoch, the value needs to be increased by the | 362 | | // number of skipped epochs. | 363 | | // Note that this calculation can only overflow in case where the `epoch_index` is superior | 364 | | // to its starting slot, and that `slots_per_epoch` is 1. In other words, this is expected to | 365 | | // never overflow as something else would overflow beforehand. But we prefer to return an error | 366 | | // rather than unwrap in order to avoid all possible panicking situations. | 367 | 4 | let block_epoch_index = block_epoch_info | 368 | 4 | .epoch_index | 369 | 4 | .checked_add(skipped_epochs) | 370 | 4 | .ok_or(VerifyError::EpochIndexOverflow)?0 ; | 371 | | | 372 | | // TODO: in case of epoch change, should also check the randomness value; while the runtime | 373 | | // checks that the randomness value is correct, light clients in particular do not | 374 | | // execute the runtime | 375 | | | 376 | | // Check that the claim is one of the allowed slot types. | 377 | | match ( | 378 | 4 | block_epoch_info.allowed_slots, | 379 | 4 | is_primary_slot, | 380 | 4 | vrf_output_and_proof, | 381 | | ) { | 382 | 0 | (_, true, None) => unreachable!(), | 383 | 2 | (_, true, Some(_)) => {} | 384 | 2 | (header::BabeAllowedSlots::PrimaryAndSecondaryPlainSlots, false, None) => {} | 385 | 0 | (header::BabeAllowedSlots::PrimaryAndSecondaryVrfSlots, false, Some(_)) => {} | 386 | 0 | _ => return Err(VerifyError::ForbiddenSlotType), | 387 | | } | 388 | | | 389 | | // Signature contained in the seal is copied and stored for later. | 390 | 4 | let seal_signature = match config.header.digest.babe_seal() { | 391 | 4 | Some(seal) => { | 392 | 4 | schnorrkel::Signature::from_bytes(seal).map_err(|_| VerifyError::BadSignature)?0 | 393 | | } | 394 | 0 | None => return Err(VerifyError::MissingSeal), | 395 | | }; | 396 | | | 397 | | // If the block contains an epoch transition, build the information about the new epoch. | 398 | | // This is done now, as the header is consumed below. | 399 | 4 | let epoch_transition_target = | 400 | 4 | if let Some((info, maybe_config2 )) = config.header.digest.babe_epoch_information() { | 401 | 2 | let start_slot_number = Some( | 402 | 2 | block_epoch_info | 403 | 2 | .start_slot_number | 404 | 2 | .unwrap_or(slot_number) | 405 | 2 | .checked_add(config.slots_per_epoch.get()) | 406 | 2 | .ok_or(VerifyError::NextEpochStartSlotNumberOverflow)?0 | 407 | | // If some epochs have been skipped, we need to adjust the starting slot of | 408 | | // the next epoch. | 409 | | .checked_add( | 410 | 2 | skipped_epochs | 411 | 2 | .checked_mul(config.slots_per_epoch.get()) | 412 | 2 | .ok_or(VerifyError::NextEpochStartSlotNumberOverflow)?0 , | 413 | | ) | 414 | 2 | .ok_or(VerifyError::NextEpochStartSlotNumberOverflow)?0 , | 415 | | ); | 416 | | | 417 | | Some(chain_information::BabeEpochInformation { | 418 | 2 | epoch_index: block_epoch_index | 419 | 2 | .checked_add(1) | 420 | 2 | .ok_or(VerifyError::EpochIndexOverflow)?0 , | 421 | 2 | start_slot_number, | 422 | 2 | authorities: info.authorities.map(Into::into).collect(), | 423 | 2 | randomness: *info.randomness, | 424 | 2 | c: maybe_config.map_or(block_epoch_info.c, |config| config.c), | 425 | 2 | allowed_slots: maybe_config.map_or(block_epoch_info.allowed_slots, |config| { | 426 | | config.allowed_slots | 427 | 2 | }), | 428 | | }) | 429 | | } else { | 430 | 2 | None | 431 | | }; | 432 | | | 433 | | // Make sure that the header wouldn't put Babe in a non-sensical state. | 434 | 4 | if let Some(epoch_transition_target2 ) = &epoch_transition_target { | 435 | 2 | if let Err(err0 ) = epoch_transition_target.validate() { | 436 | 0 | return Err(VerifyError::InvalidBabeParametersChange(err)); | 437 | 2 | } | 438 | 2 | } | 439 | | | 440 | | // The signature in the seal applies to the header from where the signature isn't present. | 441 | | // Build the hash that is expected to be signed. | 442 | | // The signature cannot be verified yet, as the public key of the signer isn't known. | 443 | 4 | let pre_seal_hash = { | 444 | 4 | let mut unsealed_header = config.header; | 445 | 4 | let _popped = unsealed_header.digest.pop_seal(); | 446 | 4 | debug_assert!(matches!0 (_popped, Some(header::Seal::Babe(_)))); | 447 | 4 | unsealed_header.hash(config.block_number_bytes) | 448 | | }; | 449 | | | 450 | | // Fetch the authority that has supposedly signed the block. | 451 | 4 | let signing_authority = block_epoch_info | 452 | 4 | .authorities | 453 | 4 | .clone() | 454 | 4 | .nth(usize::try_from(authority_index).map_err(|_| VerifyError::InvalidAuthorityIndex)?0 ) | 455 | 4 | .ok_or(VerifyError::InvalidAuthorityIndex)?0 ; | 456 | | | 457 | | // Now verifying the signature in the seal. | 458 | 4 | let signing_public_key = schnorrkel::PublicKey::from_bytes(signing_authority.public_key) | 459 | 4 | .map_err(|_| VerifyError::BadPublicKey)?0 ; | 460 | 4 | signing_public_key | 461 | 4 | .verify_simple(b"substrate", &pre_seal_hash, &seal_signature) | 462 | 4 | .map_err(|_| VerifyError::BadSignature)?0 ; | 463 | | | 464 | | // Now verify the VRF output and proof, if any. | 465 | | // The lack of VRF output/proof in the header is checked when we check whether the slot | 466 | | // type is allowed by the current configuration. | 467 | 4 | if let Some((vrf_output, vrf_proof2 )) = vrf_output_and_proof { | 468 | | // In order to verify the VRF output, we first need to create a transcript containing all | 469 | | // the data to verify the VRF against. | 470 | 2 | let transcript = { | 471 | 2 | let mut transcript = merlin::Transcript::new(&b"BABE"[..]); | 472 | 2 | transcript.append_u64(b"slot number", slot_number); | 473 | 2 | transcript.append_u64(b"current epoch", block_epoch_index); | 474 | 2 | transcript.append_message(b"chain randomness", &block_epoch_info.randomness[..]); | 475 | 2 | transcript | 476 | 2 | }; | 477 | 2 | | 478 | 2 | // These `unwrap()`s can only panic if `vrf_output` or `vrf_proof` are of the wrong | 479 | 2 | // length, which we know can't happen as they're of types `[u8; 32]` and `[u8; 64]`. | 480 | 2 | let vrf_output = schnorrkel::vrf::VRFPreOut::from_bytes(&vrf_output[..]).unwrap(); | 481 | 2 | let vrf_proof = schnorrkel::vrf::VRFProof::from_bytes(&vrf_proof[..]).unwrap(); | 482 | | | 483 | 2 | let (vrf_in_out, _) = signing_public_key | 484 | 2 | .vrf_verify(transcript, &vrf_output, &vrf_proof) | 485 | 2 | .map_err(|_| VerifyError::BadVrfProof)?0 ; | 486 | | | 487 | | // If this is a primary slot claim, we need to make sure that the VRF output is below | 488 | | // a certain threshold, otherwise all the authorities could claim all the slots. | 489 | 2 | if is_primary_slot { | 490 | 2 | let threshold = calculate_primary_threshold( | 491 | 2 | block_epoch_info.c, | 492 | 2 | block_epoch_info.authorities.clone().map(|a| a.weight), | 493 | 2 | signing_authority.weight, | 494 | 2 | ); | 495 | 2 | if u128::from_le_bytes(vrf_in_out.make_bytes::<[u8; 16]>(b"substrate-babe-vrf")) | 496 | 2 | >= threshold | 497 | | { | 498 | 0 | return Err(VerifyError::OverPrimaryClaimThreshold); | 499 | 2 | } | 500 | 0 | } | 501 | | } else { | 502 | 2 | debug_assert!(!is_primary_slot); | 503 | | } | 504 | | | 505 | | // Each slot can be claimed by one specific authority in what is called a secondary slot | 506 | | // claim. If the block is a secondary slot claim, we need to make sure that the author | 507 | | // is indeed the one that is expected. | 508 | 4 | if !is_primary_slot { | 509 | | // Expected author is determined based on `blake2(randomness | slot_number)`. | 510 | 2 | let hash = { | 511 | 2 | let mut hash = blake2_rfc::blake2b::Blake2b::new(32); | 512 | 2 | hash.update(block_epoch_info.randomness); | 513 | 2 | hash.update(&slot_number.to_le_bytes()); | 514 | 2 | hash.finalize() | 515 | | }; | 516 | | | 517 | | // The expected authority index is `hash % num_authorities`. | 518 | 2 | let expected_authority_index = { | 519 | 2 | let hash = num_bigint::BigUint::from_bytes_be(hash.as_bytes()); | 520 | 2 | let authorities_len = num_bigint::BigUint::from(block_epoch_info.authorities.len()); | 521 | 2 | debug_assert_ne!(block_epoch_info.authorities.len(), 0); | 522 | 2 | hash % authorities_len | 523 | 2 | }; | 524 | 2 | | 525 | 2 | if num_traits::cast::ToPrimitive::to_u32(&expected_authority_index) | 526 | 2 | .map_or(true, |v| v != authority_index) | 527 | | { | 528 | 0 | return Err(VerifyError::BadSecondarySlotAuthor); | 529 | 2 | } | 530 | 2 | } | 531 | | | 532 | | // Success! 🚀 | 533 | 4 | Ok(VerifySuccess { | 534 | 4 | slot_number, | 535 | 4 | is_primary_slot, | 536 | 4 | epoch_transition_target, | 537 | 4 | }) | 538 | 4 | } |
Unexecuted instantiation: _RNvNtNtCseuYC0Zibziv_7smoldot6verify4babe13verify_header |
539 | | |
540 | | // Because `f64::powf` isn't available in no-std contexts, we generate a version of this function |
541 | | // with either `f64::powf` or `libm::pow`. Both functions are equivalent, except that `f64::powf` |
542 | | // is expected to be faster on some platforms. |
543 | | macro_rules! gen_calculate_primary_threshold { |
544 | | ($name:ident, $powf:expr) => { |
545 | | /// Calculates the primary selection threshold for a given authority, taking |
546 | | /// into account `c` (`1 - c` represents the probability of a slot being empty). |
547 | | /// |
548 | | /// The value of `c` can be found in the current Babe configuration. |
549 | | /// |
550 | | /// `authorities_weights` must be the list of all weights of all authorities. |
551 | | /// `authority_weight` must be the weight of the authority whose threshold to calculate. |
552 | | /// |
553 | | /// # Panic |
554 | | /// |
555 | | /// Panics if `authorities_weights` is empty. |
556 | | /// Panics if `authority_weight` is 0. |
557 | | /// |
558 | 8 | fn $name( |
559 | 8 | c: (u64, u64), |
560 | 8 | authorities_weights: impl Iterator<Item = u64>, |
561 | 8 | authority_weight: u64, // TODO: use a NonZeroU64 once crate::header also has weights that use NonZeroU64 |
562 | 8 | ) -> u128 { |
563 | 8 | // We import `libm` no matter what, so that there's no warning about an unused |
564 | 8 | // dependency. |
565 | 8 | use libm as _; |
566 | 8 | |
567 | 8 | let c = c.0 as f64 / c.1 as f64; |
568 | 8 | assert!(c.is_finite()); |
569 | | |
570 | 8 | let theta = authority_weight as f64 / authorities_weights.sum::<u64>() as f64; |
571 | 8 | assert!(theta > 0.0); |
572 | | |
573 | | // The calculations below has been copy-pasted from Substrate and is guaranteed to |
574 | | // not panic. |
575 | 8 | let p = num_rational::BigRational::from_float(1f64 - $powf(1f64 - c, theta)).unwrap(); |
576 | 8 | let numer = p.numer().to_biguint().unwrap(); |
577 | 8 | let denom = p.denom().to_biguint().unwrap(); |
578 | 8 | num_traits::cast::ToPrimitive::to_u128( |
579 | 8 | &((<num_bigint::BigUint as num_traits::One>::one() << 128u32) * numer / denom), |
580 | 8 | ) |
581 | 8 | .unwrap() |
582 | 8 | } _RINvNtNtCsN16ciHI6Qf_7smoldot6verify4babe27calculate_primary_thresholdINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapNtNtNtB6_6header4babe19BabeAuthoritiesIterNCNvB2_13verify_headers7_0EEB6_ Line | Count | Source | 558 | 2 | fn $name( | 559 | 2 | c: (u64, u64), | 560 | 2 | authorities_weights: impl Iterator<Item = u64>, | 561 | 2 | authority_weight: u64, // TODO: use a NonZeroU64 once crate::header also has weights that use NonZeroU64 | 562 | 2 | ) -> u128 { | 563 | 2 | // We import `libm` no matter what, so that there's no warning about an unused | 564 | 2 | // dependency. | 565 | 2 | use libm as _; | 566 | 2 | | 567 | 2 | let c = c.0 as f64 / c.1 as f64; | 568 | 2 | assert!(c.is_finite()); | 569 | | | 570 | 2 | let theta = authority_weight as f64 / authorities_weights.sum::<u64>() as f64; | 571 | 2 | assert!(theta > 0.0); | 572 | | | 573 | | // The calculations below has been copy-pasted from Substrate and is guaranteed to | 574 | | // not panic. | 575 | 2 | let p = num_rational::BigRational::from_float(1f64 - $powf(1f64 - c, theta)).unwrap(); | 576 | 2 | let numer = p.numer().to_biguint().unwrap(); | 577 | 2 | let denom = p.denom().to_biguint().unwrap(); | 578 | 2 | num_traits::cast::ToPrimitive::to_u128( | 579 | 2 | &((<num_bigint::BigUint as num_traits::One>::one() << 128u32) * numer / denom), | 580 | 2 | ) | 581 | 2 | .unwrap() | 582 | 2 | } |
_RINvNtNtNtCsN16ciHI6Qf_7smoldot6verify4babe5tests28calculate_primary_threshold1INtNtNtCsaYZPK01V26L_4core5array4iter8IntoIteryKj8_EEB8_ Line | Count | Source | 558 | 1 | fn $name( | 559 | 1 | c: (u64, u64), | 560 | 1 | authorities_weights: impl Iterator<Item = u64>, | 561 | 1 | authority_weight: u64, // TODO: use a NonZeroU64 once crate::header also has weights that use NonZeroU64 | 562 | 1 | ) -> u128 { | 563 | 1 | // We import `libm` no matter what, so that there's no warning about an unused | 564 | 1 | // dependency. | 565 | 1 | use libm as _; | 566 | 1 | | 567 | 1 | let c = c.0 as f64 / c.1 as f64; | 568 | 1 | assert!(c.is_finite()); | 569 | | | 570 | 1 | let theta = authority_weight as f64 / authorities_weights.sum::<u64>() as f64; | 571 | 1 | assert!(theta > 0.0); | 572 | | | 573 | | // The calculations below has been copy-pasted from Substrate and is guaranteed to | 574 | | // not panic. | 575 | 1 | let p = num_rational::BigRational::from_float(1f64 - $powf(1f64 - c, theta)).unwrap(); | 576 | 1 | let numer = p.numer().to_biguint().unwrap(); | 577 | 1 | let denom = p.denom().to_biguint().unwrap(); | 578 | 1 | num_traits::cast::ToPrimitive::to_u128( | 579 | 1 | &((<num_bigint::BigUint as num_traits::One>::one() << 128u32) * numer / denom), | 580 | 1 | ) | 581 | 1 | .unwrap() | 582 | 1 | } |
_RINvNtNtNtCsN16ciHI6Qf_7smoldot6verify4babe5tests28calculate_primary_threshold1INtNtNtNtCsaYZPK01V26L_4core4iter8adapters4take4TakeINtNtNtB1m_7sources10successors10SuccessorsyNCNvB2_s_33calculate_primary_threshold_tests0EEEB8_ Line | Count | Source | 558 | 1 | fn $name( | 559 | 1 | c: (u64, u64), | 560 | 1 | authorities_weights: impl Iterator<Item = u64>, | 561 | 1 | authority_weight: u64, // TODO: use a NonZeroU64 once crate::header also has weights that use NonZeroU64 | 562 | 1 | ) -> u128 { | 563 | 1 | // We import `libm` no matter what, so that there's no warning about an unused | 564 | 1 | // dependency. | 565 | 1 | use libm as _; | 566 | 1 | | 567 | 1 | let c = c.0 as f64 / c.1 as f64; | 568 | 1 | assert!(c.is_finite()); | 569 | | | 570 | 1 | let theta = authority_weight as f64 / authorities_weights.sum::<u64>() as f64; | 571 | 1 | assert!(theta > 0.0); | 572 | | | 573 | | // The calculations below has been copy-pasted from Substrate and is guaranteed to | 574 | | // not panic. | 575 | 1 | let p = num_rational::BigRational::from_float(1f64 - $powf(1f64 - c, theta)).unwrap(); | 576 | 1 | let numer = p.numer().to_biguint().unwrap(); | 577 | 1 | let denom = p.denom().to_biguint().unwrap(); | 578 | 1 | num_traits::cast::ToPrimitive::to_u128( | 579 | 1 | &((<num_bigint::BigUint as num_traits::One>::one() << 128u32) * numer / denom), | 580 | 1 | ) | 581 | 1 | .unwrap() | 582 | 1 | } |
_RINvNtNtNtCsN16ciHI6Qf_7smoldot6verify4babe5tests28calculate_primary_threshold1INtNtNtNtCsaYZPK01V26L_4core4iter8adapters4take4TakeINtNtNtB1m_7sources10successors10SuccessorsyNCNvB2_s_33calculate_primary_threshold_testss0_0EEEB8_ Line | Count | Source | 558 | 1 | fn $name( | 559 | 1 | c: (u64, u64), | 560 | 1 | authorities_weights: impl Iterator<Item = u64>, | 561 | 1 | authority_weight: u64, // TODO: use a NonZeroU64 once crate::header also has weights that use NonZeroU64 | 562 | 1 | ) -> u128 { | 563 | 1 | // We import `libm` no matter what, so that there's no warning about an unused | 564 | 1 | // dependency. | 565 | 1 | use libm as _; | 566 | 1 | | 567 | 1 | let c = c.0 as f64 / c.1 as f64; | 568 | 1 | assert!(c.is_finite()); | 569 | | | 570 | 1 | let theta = authority_weight as f64 / authorities_weights.sum::<u64>() as f64; | 571 | 1 | assert!(theta > 0.0); | 572 | | | 573 | | // The calculations below has been copy-pasted from Substrate and is guaranteed to | 574 | | // not panic. | 575 | 1 | let p = num_rational::BigRational::from_float(1f64 - $powf(1f64 - c, theta)).unwrap(); | 576 | 1 | let numer = p.numer().to_biguint().unwrap(); | 577 | 1 | let denom = p.denom().to_biguint().unwrap(); | 578 | 1 | num_traits::cast::ToPrimitive::to_u128( | 579 | 1 | &((<num_bigint::BigUint as num_traits::One>::one() << 128u32) * numer / denom), | 580 | 1 | ) | 581 | 1 | .unwrap() | 582 | 1 | } |
_RINvNtNtNtCsN16ciHI6Qf_7smoldot6verify4babe5tests28calculate_primary_threshold2INtNtNtCsaYZPK01V26L_4core5array4iter8IntoIteryKj8_EEB8_ Line | Count | Source | 558 | 1 | fn $name( | 559 | 1 | c: (u64, u64), | 560 | 1 | authorities_weights: impl Iterator<Item = u64>, | 561 | 1 | authority_weight: u64, // TODO: use a NonZeroU64 once crate::header also has weights that use NonZeroU64 | 562 | 1 | ) -> u128 { | 563 | 1 | // We import `libm` no matter what, so that there's no warning about an unused | 564 | 1 | // dependency. | 565 | 1 | use libm as _; | 566 | 1 | | 567 | 1 | let c = c.0 as f64 / c.1 as f64; | 568 | 1 | assert!(c.is_finite()); | 569 | | | 570 | 1 | let theta = authority_weight as f64 / authorities_weights.sum::<u64>() as f64; | 571 | 1 | assert!(theta > 0.0); | 572 | | | 573 | | // The calculations below has been copy-pasted from Substrate and is guaranteed to | 574 | | // not panic. | 575 | 1 | let p = num_rational::BigRational::from_float(1f64 - $powf(1f64 - c, theta)).unwrap(); | 576 | 1 | let numer = p.numer().to_biguint().unwrap(); | 577 | 1 | let denom = p.denom().to_biguint().unwrap(); | 578 | 1 | num_traits::cast::ToPrimitive::to_u128( | 579 | 1 | &((<num_bigint::BigUint as num_traits::One>::one() << 128u32) * numer / denom), | 580 | 1 | ) | 581 | 1 | .unwrap() | 582 | 1 | } |
_RINvNtNtNtCsN16ciHI6Qf_7smoldot6verify4babe5tests28calculate_primary_threshold2INtNtNtNtCsaYZPK01V26L_4core4iter8adapters4take4TakeINtNtNtB1m_7sources10successors10SuccessorsyNCNvB2_s_33calculate_primary_threshold_testss1_0EEEB8_ Line | Count | Source | 558 | 1 | fn $name( | 559 | 1 | c: (u64, u64), | 560 | 1 | authorities_weights: impl Iterator<Item = u64>, | 561 | 1 | authority_weight: u64, // TODO: use a NonZeroU64 once crate::header also has weights that use NonZeroU64 | 562 | 1 | ) -> u128 { | 563 | 1 | // We import `libm` no matter what, so that there's no warning about an unused | 564 | 1 | // dependency. | 565 | 1 | use libm as _; | 566 | 1 | | 567 | 1 | let c = c.0 as f64 / c.1 as f64; | 568 | 1 | assert!(c.is_finite()); | 569 | | | 570 | 1 | let theta = authority_weight as f64 / authorities_weights.sum::<u64>() as f64; | 571 | 1 | assert!(theta > 0.0); | 572 | | | 573 | | // The calculations below has been copy-pasted from Substrate and is guaranteed to | 574 | | // not panic. | 575 | 1 | let p = num_rational::BigRational::from_float(1f64 - $powf(1f64 - c, theta)).unwrap(); | 576 | 1 | let numer = p.numer().to_biguint().unwrap(); | 577 | 1 | let denom = p.denom().to_biguint().unwrap(); | 578 | 1 | num_traits::cast::ToPrimitive::to_u128( | 579 | 1 | &((<num_bigint::BigUint as num_traits::One>::one() << 128u32) * numer / denom), | 580 | 1 | ) | 581 | 1 | .unwrap() | 582 | 1 | } |
_RINvNtNtNtCsN16ciHI6Qf_7smoldot6verify4babe5tests28calculate_primary_threshold2INtNtNtNtCsaYZPK01V26L_4core4iter8adapters4take4TakeINtNtNtB1m_7sources10successors10SuccessorsyNCNvB2_s_33calculate_primary_threshold_testss_0EEEB8_ Line | Count | Source | 558 | 1 | fn $name( | 559 | 1 | c: (u64, u64), | 560 | 1 | authorities_weights: impl Iterator<Item = u64>, | 561 | 1 | authority_weight: u64, // TODO: use a NonZeroU64 once crate::header also has weights that use NonZeroU64 | 562 | 1 | ) -> u128 { | 563 | 1 | // We import `libm` no matter what, so that there's no warning about an unused | 564 | 1 | // dependency. | 565 | 1 | use libm as _; | 566 | 1 | | 567 | 1 | let c = c.0 as f64 / c.1 as f64; | 568 | 1 | assert!(c.is_finite()); | 569 | | | 570 | 1 | let theta = authority_weight as f64 / authorities_weights.sum::<u64>() as f64; | 571 | 1 | assert!(theta > 0.0); | 572 | | | 573 | | // The calculations below has been copy-pasted from Substrate and is guaranteed to | 574 | | // not panic. | 575 | 1 | let p = num_rational::BigRational::from_float(1f64 - $powf(1f64 - c, theta)).unwrap(); | 576 | 1 | let numer = p.numer().to_biguint().unwrap(); | 577 | 1 | let denom = p.denom().to_biguint().unwrap(); | 578 | 1 | num_traits::cast::ToPrimitive::to_u128( | 579 | 1 | &((<num_bigint::BigUint as num_traits::One>::one() << 128u32) * numer / denom), | 580 | 1 | ) | 581 | 1 | .unwrap() | 582 | 1 | } |
Unexecuted instantiation: _RINvNtNtCseuYC0Zibziv_7smoldot6verify4babe27calculate_primary_thresholdINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapNtNtNtB6_6header4babe19BabeAuthoritiesIterNCNvB2_13verify_headers7_0EEB6_ |
583 | | }; |
584 | | } |
585 | | #[cfg(feature = "std")] |
586 | | gen_calculate_primary_threshold!(calculate_primary_threshold, f64::powf); |
587 | | #[cfg(not(feature = "std"))] |
588 | | gen_calculate_primary_threshold!(calculate_primary_threshold, libm::pow); |
589 | | |
590 | | #[cfg(test)] |
591 | | mod tests { |
592 | | use core::iter; |
593 | | |
594 | | gen_calculate_primary_threshold!(calculate_primary_threshold1, f64::powf); |
595 | | gen_calculate_primary_threshold!(calculate_primary_threshold2, libm::pow); |
596 | | |
597 | | #[test] |
598 | 1 | fn calculate_primary_threshold_tests() { |
599 | 1 | // These regression tests have been generated by performing calculations using the |
600 | 1 | // Substrate implementation. The input of the calculations were chosen more or less |
601 | 1 | // arbitrarily. |
602 | 1 | |
603 | 1 | assert_eq!( |
604 | 1 | calculate_primary_threshold1((2, 9), [1, 1, 1, 1, 1, 1, 1, 1].into_iter(), 1), |
605 | 1 | 10523572781773471998586657386560225280u128 |
606 | 1 | ); |
607 | 1 | assert_eq!( |
608 | 1 | calculate_primary_threshold2((2, 9), [1, 1, 1, 1, 1, 1, 1, 1].into_iter(), 1), |
609 | 1 | 10523572781773471998586657386560225280u128 |
610 | 1 | ); |
611 | | |
612 | 1 | assert_eq!( |
613 | 1 | calculate_primary_threshold1( |
614 | 1 | (103, 971), |
615 | 900 | iter::successors(Some(2u64), |n| Some(n + 1)).take(900), |
616 | 1 | 11 |
617 | 1 | ), |
618 | 1 | 1032931305829506557190946382938112u128 |
619 | 1 | ); |
620 | 1 | assert_eq!( |
621 | 1 | calculate_primary_threshold2( |
622 | 1 | (103, 971), |
623 | 900 | iter::successors(Some(2u64), |n| Some(n + 1)).take(900), |
624 | 1 | 11 |
625 | 1 | ), |
626 | 1 | 1032931305829506557190946382938112u128 |
627 | 1 | ); |
628 | | |
629 | 1 | assert_eq!( |
630 | 1 | calculate_primary_threshold1( |
631 | 1 | (89, 91), |
632 | 50 | iter::successors(Some(2u64), |n| Some(n * 2 - 1)).take(50), |
633 | 1 | 63 |
634 | 1 | ), |
635 | 1 | 72686664904329579129208832u128 |
636 | 1 | ); |
637 | 1 | assert_eq!( |
638 | 1 | calculate_primary_threshold2( |
639 | 1 | (89, 91), |
640 | 50 | iter::successors(Some(2u64), |n| Some(n * 2 - 1)).take(50), |
641 | 1 | 63 |
642 | 1 | ), |
643 | 1 | 72686664904329579129208832u128 |
644 | 1 | ); |
645 | 1 | } |
646 | | } |