// Smoldot

// Copyright (C) 2019-2022  Parity Technologies (UK) Ltd.

// SPDX-License-Identifier: GPL-3.0-or-later WITH Classpath-exception-2.0

// This program is free software: you can redistribute it and/or modify

// it under the terms of the GNU General Public License as published by

// the Free Software Foundation, either version 3 of the License, or

// (at your option) any later version.

// This program is distributed in the hope that it will be useful,

// but WITHOUT ANY WARRANTY; without even the implied warranty of

// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License

// along with this program.  If not, see <http://www.gnu.org/licenses/>.

//! AURA consensus.

//!

//! AURA, for Authority Round, is one of the consensus algorithm available to Substrate-based

//! chains in order to determine who is authorized to generate a block.

//!

//! Every block (with the exception of the genesis block) must contain, in its header, some data

//! that makes it possible to verify that it has been generated by a legitimate author.

//!

//! # Overview of AURA

//!

//! In the AURA algorithm, time is divided into non-overlapping **slots**. How long a slot is

//! never changes, and is determined by calling the `AuraApi_slot_duration` runtime entry point,

//! typically at initialization. The current slot number is equal to `unix_time / slot_duration`.

//! The slot number of a block can be found in its header.

//!

//! > **Note**: Slot durations values are usually around 3 to 20 seconds.

//!

//! A list of authorities (each authority being represented as a public key) is maintained by the

//! chain. The current authorities of a block can be found by calling the `AuraApi_authorities`

//! runtime entry point.

//! When this list is modified, a consensus log item is added to the header of the block, meaning

//! that this runtime entry point doesn't have to be called every single time.

//!

//! During a slot, only the authority whose public key is found at

//! `authorities[slot_number % authorities.len()]` is allowed to produce a block.

//!

//! Each block being produced must include an Aura seal in its header containing a signature of

//! the block header (with the exclusion of the seal itself) made using the public key in question.

//!

use crate::header;

use alloc::vec::Vec;

use core::{num::NonZeroU64, time::Duration};

/// Configuration for [`verify_header`].

pub struct VerifyConfig<'a, TAuthList> {

    /// Header of the block to verify.

    pub header: header::HeaderRef<'a>,

    /// Number of bytes used to encode the block number in the header.

    pub block_number_bytes: usize,

    /// Header of the parent of the block to verify.

    ///

    /// [`verify_header`] assumes that this block has been successfully verified before.

    ///

    /// The hash of this header must be the one referenced in [`VerifyConfig::header`].

    pub parent_block_header: header::HeaderRef<'a>,

    /// Time elapsed since [the Unix Epoch](https://en.wikipedia.org/wiki/Unix_time) (i.e.

    /// 00:00:00 UTC on 1 January 1970), ignoring leap seconds.

    pub now_from_unix_epoch: Duration,

    /// Aura authorities that must validate the block.

    ///

    /// This list is either equal to the parent's list, or, if the parent changes the list of

    /// authorities, equal to that new modified list.

    pub current_authorities: TAuthList,

    /// Duration of a slot in milliseconds.

    /// Can be found by calling the `AuraApi_slot_duration` runtime function.

    pub slot_duration: NonZeroU64,

}

/// Information yielded back after successfully verifying a block.

#[derive(Debug)]

pub struct VerifySuccess {

    /// `Some` if the list of authorities is modified by this block. Contains the new list of

    /// authorities.

    pub authorities_change: Option<Vec<header::AuraAuthority>>,

}

/// Failure to verify a block.

#[derive(Debug, derive_more::Display)]

Unexecuted instantiation: _RNvXs0_NtNtCsN16ciHI6Qf_7smoldot6verify4auraNtB5_11VerifyErrorNtNtCsaYZPK01V26L_4core3fmt7Display3fmt

Unexecuted instantiation: _RNvXs0_NtNtCseuYC0Zibziv_7smoldot6verify4auraNtB5_11VerifyErrorNtNtCsaYZPK01V26L_4core3fmt7Display3fmt

pub enum VerifyError {

    /// The seal (containing the signature of the authority) is missing from the header.

    MissingSeal,

    /// No pre-runtime digest in the block header.

    MissingPreRuntimeDigest,

    /// Parent block doesn't contain any Aura information.

    ParentIsntAuraConsensus,

    /// Slot number must be strictly increasing between a parent and its child.

    SlotNumberNotIncreasing,

    /// Slot number starts too far in the future.

    TooFarInFuture,

    /// Block header signature is invalid.

    BadSignature,

    /// Failed to parse Ed25519 public key.

    BadPublicKey,

    /// List of authorities is empty.

    EmptyAuthorities,

    /// Header contains more than one new list of authorities.

    MultipleAuthoritiesChangeDigestItems,

}

/// Verifies whether a block header provides a correct proof of the legitimacy of the authorship.

pub fn verify_header<'a>(

    mut config: VerifyConfig<'a, impl ExactSizeIterator<Item = header::AuraAuthorityRef<'a>>>,

) -> Result<VerifySuccess, VerifyError> {

    // TODO: handle OnDisabled

    // Gather the slot number from the header.

    let slot_number = config

        .header

        .digest

        .aura_pre_runtime()

        .ok_or(VerifyError::MissingPreRuntimeDigest)?

        .slot_number;

    // Make sure that the slot number is strictly increasing between a parent and its children.

    if config.parent_block_header.number != 0 {

        let parent_slot_number = match config.parent_block_header.digest.aura_pre_runtime() {

            Some(pr) => pr.slot_number,

            None => return Err(VerifyError::ParentIsntAuraConsensus),

        };

        if slot_number <= parent_slot_number {

            return Err(VerifyError::SlotNumberNotIncreasing);

        }

    }

    // Check that the slot number isn't a slot in the future.

    // Since there might be a clock drift (either locally or on the authority that created the

    // block), a tolerance period is added.

    // If the local node is an authority itself, and the best block uses a slot number `N` seconds

    // in the future, then for the next `N` seconds the local node won't produce any block. As

    // such, a high tolerance level constitutes an attack vector.

    {

        const TOLERANCE: Duration = Duration::from_secs(30);

        let current_slot =

            (config.now_from_unix_epoch + TOLERANCE).as_secs() * 1000 / config.slot_duration.get();

        if slot_number > current_slot {

            return Err(VerifyError::TooFarInFuture);

        }

    };

    // Check whether there is an authority change in the block.

    // This information is used in case of success.

    let mut authorities_change = None;

    for digest_item in config.header.digest.logs() {

        if let header::DigestItemRef::AuraConsensus(

            header::AuraConsensusLogRef::AuthoritiesChange(new_list),

        ) = digest_item

        {

            if authorities_change.is_some() {

                return Err(VerifyError::MultipleAuthoritiesChangeDigestItems);

            }

            authorities_change = Some(new_list.map(Into::into).collect());

            // We continue looping even after finding a list, to make sure there is only one list.

        }

    }

    // The signature in the seal applies to the header from where the signature isn't present.

    // Extract the signature and build the hash that is expected to be signed.

    let (seal_signature, pre_seal_hash) = {

        let mut unsealed_header = config.header;

        let seal_signature = match unsealed_header.digest.pop_seal() {

            Some(header::Seal::Aura(seal)) => {

                schnorrkel::Signature::from_bytes(seal).map_err(|_| VerifyError::BadSignature)?

Unexecuted instantiation: _RNCINvNtNtCsN16ciHI6Qf_7smoldot6verify4aura13verify_headerNtNtNtB8_6header4aura19AuraAuthoritiesIterE0B8_

Unexecuted instantiation: _RNCINvNtNtCseuYC0Zibziv_7smoldot6verify4aura13verify_headerNtNtNtB8_6header4aura19AuraAuthoritiesIterE0B8_

            }

            _ => return Err(VerifyError::MissingSeal),

        };

        (

            seal_signature,

            unsealed_header.hash(config.block_number_bytes),

        )

    };

    // Fetch the authority that has supposedly signed the block.

    if config.current_authorities.len() == 0 {

        // Checked beforehand in order to not do a modulo 0 operation.

        return Err(VerifyError::EmptyAuthorities);

    }

    // About overflows:

    // If `config.current_authorities.len()` doesn't fit in a `u64`, then

    // `slot_number % config.current_authorities.len()` is necessarily equal to `slot_number`.

    // Since we're using a modulo operation, `signing_authority` is always inferior to

    // `current_authorities.len()`, meaning that it always fits in a `usize`.

    let signing_authority = usize::try_from(

        slot_number % u64::try_from(config.current_authorities.len()).unwrap_or(u64::MAX),

    )

    .unwrap_or_else(|_| unreachable!());

Unexecuted instantiation: _RNCINvNtNtCsN16ciHI6Qf_7smoldot6verify4aura13verify_headerpEs_0B8_

Unexecuted instantiation: _RNCINvNtNtCseuYC0Zibziv_7smoldot6verify4aura13verify_headerpEs_0B8_

    // This `unwrap()` can only panic if `public_key` is the wrong length, which we know can't

    // happen as it's of type `[u8; 32]`.

    let authority_public_key = schnorrkel::PublicKey::from_bytes(

        config

            .current_authorities

            .nth(signing_authority)

            .unwrap()

            .public_key,

    )

    .unwrap();

    // Now verifying the signature in the seal.

    authority_public_key

        .verify_simple(b"substrate", &pre_seal_hash, &seal_signature)

        .map_err(|_| VerifyError::BadSignature)?;

Unexecuted instantiation: _RNCINvNtNtCsN16ciHI6Qf_7smoldot6verify4aura13verify_headerNtNtNtB8_6header4aura19AuraAuthoritiesIterEs0_0B8_

Unexecuted instantiation: _RNCINvNtNtCseuYC0Zibziv_7smoldot6verify4aura13verify_headerNtNtNtB8_6header4aura19AuraAuthoritiesIterEs0_0B8_

    // Success! 🚀

    Ok(VerifySuccess { authorities_change })

}

Unexecuted instantiation: _RINvNtNtCsN16ciHI6Qf_7smoldot6verify4aura13verify_headerNtNtNtB6_6header4aura19AuraAuthoritiesIterEB6_

Unexecuted instantiation: _RINvNtNtCseuYC0Zibziv_7smoldot6verify4aura13verify_headerNtNtNtB6_6header4aura19AuraAuthoritiesIterEB6_