linera_base/

ownership.rs

// Copyright (c) Zefchain Labs, Inc.
// SPDX-License-Identifier: Apache-2.0

//! Structures defining the set of owners and super owners, as well as the consensus
//! round types and timeouts for chains.

use std::{
    collections::{BTreeMap, BTreeSet},
    iter,
};

use allocative::Allocative;
use custom_debug_derive::Debug;
use linera_witty::{WitLoad, WitStore, WitType};
use serde::{Deserialize, Serialize};
use thiserror::Error;

use crate::{
    crypto::{BcsHashable, CryptoHash},
    data_types::{Round, TimeDelta},
    doc_scalar,
    identifiers::AccountOwner,
};

/// The timeout configuration: how long fast, multi-leader and single-leader rounds last.
#[derive(
    PartialEq,
    Eq,
    Clone,
    Hash,
    Debug,
    Serialize,
    Deserialize,
    WitLoad,
    WitStore,
    WitType,
    Allocative,
)]
pub struct TimeoutConfig {
    /// The duration of the fast round.
    #[debug(skip_if = Option::is_none)]
    pub fast_round_duration: Option<TimeDelta>,
    /// The duration of the first multi-leader and single-leader rounds.
    pub base_timeout: TimeDelta,
    /// The duration by which the timeout increases after each multi-leader or
    /// single-leader round.
    pub timeout_increment: TimeDelta,
    /// The age of an incoming tracked or protected message after which the validators start
    /// transitioning the chain to fallback mode.
    pub fallback_duration: TimeDelta,
}

impl Default for TimeoutConfig {
    fn default() -> Self {
        Self {
            fast_round_duration: None,
            base_timeout: TimeDelta::from_secs(10),
            timeout_increment: TimeDelta::from_secs(1),
            // This is `MAX` because the validators are not currently expected to start clients for
            // every chain with an old tracked message in the inbox.
            fallback_duration: TimeDelta::MAX,
        }
    }
}

/// Represents the owner(s) of a chain.
#[derive(
    PartialEq,
    Eq,
    Clone,
    Hash,
    Debug,
    Default,
    Serialize,
    Deserialize,
    WitLoad,
    WitStore,
    WitType,
    Allocative,
)]
pub struct ChainOwnership {
    /// Super owners can propose fast blocks in the first round, and regular blocks in any round.
    #[debug(skip_if = BTreeSet::is_empty)]
    pub super_owners: BTreeSet<AccountOwner>,
    /// The regular owners, with their weights that determine how often they are round leader.
    #[debug(skip_if = BTreeMap::is_empty)]
    pub owners: BTreeMap<AccountOwner, u64>,
    /// The leader of the first single-leader round. If not set, this is random like other rounds.
    pub first_leader: Option<AccountOwner>,
    /// The number of rounds in which all owners are allowed to propose blocks.
    pub multi_leader_rounds: u32,
    /// Whether the multi-leader rounds are unrestricted, i.e. not limited to chain owners.
    /// This should only be `true` on chains with restrictive application permissions and an
    /// application-based mechanism to select block proposers.
    pub open_multi_leader_rounds: bool,
    /// The timeout configuration: how long fast, multi-leader and single-leader rounds last.
    pub timeout_config: TimeoutConfig,
}

impl ChainOwnership {
    /// Creates a `ChainOwnership` with a single super owner.
    pub fn single_super(owner: AccountOwner) -> Self {
        ChainOwnership {
            super_owners: iter::once(owner).collect(),
            owners: BTreeMap::new(),
            first_leader: None,
            multi_leader_rounds: 5,
            open_multi_leader_rounds: false,
            timeout_config: TimeoutConfig::default(),
        }
    }

    /// Creates a `ChainOwnership` with a single regular owner.
    pub fn single(owner: AccountOwner) -> Self {
        ChainOwnership {
            super_owners: BTreeSet::new(),
            owners: iter::once((owner, 100)).collect(),
            first_leader: None,
            multi_leader_rounds: 5,
            open_multi_leader_rounds: false,
            timeout_config: TimeoutConfig::default(),
        }
    }

    /// Creates a `ChainOwnership` with the specified regular owners.
    pub fn multiple(
        owners_and_weights: impl IntoIterator<Item = (AccountOwner, u64)>,
        multi_leader_rounds: u32,
        timeout_config: TimeoutConfig,
    ) -> Self {
        ChainOwnership {
            super_owners: BTreeSet::new(),
            owners: owners_and_weights.into_iter().collect(),
            first_leader: None,
            multi_leader_rounds,
            open_multi_leader_rounds: false,
            timeout_config,
        }
    }

    /// Adds a regular owner.
    #[cfg(with_testing)]
    pub fn with_regular_owner(mut self, owner: AccountOwner, weight: u64) -> Self {
        self.owners.insert(owner, weight);
        self
    }

    /// Returns whether there are any owners or super owners or it is a public chain.
    pub fn is_active(&self) -> bool {
        !self.super_owners.is_empty()
            || !self.owners.is_empty()
            || self.timeout_config.fallback_duration == TimeDelta::ZERO
    }

    /// Returns `true` if this is a regular owner or super owner or the designated first leader.
    pub fn is_owner(&self, owner: &AccountOwner) -> bool {
        self.super_owners.contains(owner)
            || self.owners.contains_key(owner)
            || self.first_leader.as_ref().is_some_and(|fl| fl == owner)
    }

    /// Returns `true` if this owner can participate in multi-leader rounds, i.e. it
    /// is a regular owner or super owner or `open_multi_leader_rounds == true`.
    pub fn can_propose_in_multi_leader_round(&self, owner: &AccountOwner) -> bool {
        self.open_multi_leader_rounds
            || self.owners.contains_key(owner)
            || self.super_owners.contains(owner)
    }

    /// Returns the duration of the given round.
    pub fn round_timeout(&self, round: Round) -> Option<TimeDelta> {
        let tc = &self.timeout_config;
        if round.is_fast() && self.owners.is_empty() {
            return None; // Fast round only times out if there are regular owners.
        }
        match round {
            Round::Fast => tc.fast_round_duration,
            Round::MultiLeader(r) | Round::SingleLeader(r) | Round::Validator(r) => {
                let increment = tc.timeout_increment.saturating_mul(u64::from(r));
                Some(tc.base_timeout.saturating_add(increment))
            }
        }
    }

    /// Returns the first consensus round for this configuration.
    pub fn first_round(&self) -> Round {
        if !self.super_owners.is_empty() {
            Round::Fast
        } else if self.owners.is_empty() {
            Round::Validator(0)
        } else if self.multi_leader_rounds > 0 {
            Round::MultiLeader(0)
        } else {
            Round::SingleLeader(0)
        }
    }

    /// Returns an iterator over all super owners, followed by all owners.
    pub fn all_owners(&self) -> impl Iterator<Item = &AccountOwner> {
        self.super_owners.iter().chain(self.owners.keys())
    }

    /// Returns whether fallback mode is enabled on this chain, i.e. the fallback duration
    /// is less than `TimeDelta::MAX`.
    pub fn has_fallback(&self) -> bool {
        self.timeout_config.fallback_duration < TimeDelta::MAX
    }

    /// Returns the round following the specified one, if any.
    pub fn next_round(&self, round: Round) -> Option<Round> {
        let next_round = match round {
            Round::Fast if self.multi_leader_rounds == 0 => Round::SingleLeader(0),
            Round::Fast => Round::MultiLeader(0),
            Round::MultiLeader(r) => r
                .checked_add(1)
                .filter(|r| *r < self.multi_leader_rounds)
                .map_or(Round::SingleLeader(0), Round::MultiLeader),
            Round::SingleLeader(r) => r
                .checked_add(1)
                .map_or(Round::Validator(0), Round::SingleLeader),
            Round::Validator(r) => Round::Validator(r.checked_add(1)?),
        };
        Some(next_round)
    }

    /// Returns whether the given owner a super owner and there are no regular owners.
    pub fn is_super_owner_no_regular_owners(&self, owner: &AccountOwner) -> bool {
        self.owners.is_empty() && self.super_owners.contains(owner)
    }

    /// Returns whether `owner` has the lowest `hash(owner, round)` among the eligible
    /// multi-leader proposers, and should therefore propose immediately rather than wait
    /// out a jitter delay. Returns `false` for `open_multi_leader_rounds`, where the set
    /// of proposers is unbounded.
    ///
    /// This is a gentle-clients convention; it is not enforced by the protocol.
    fn is_preferred_multi_leader_proposer(&self, owner: &AccountOwner, round_index: u32) -> bool {
        if self.open_multi_leader_rounds || !self.can_propose_in_multi_leader_round(owner) {
            return false;
        }
        let our_priority = multi_leader_priority(owner, round_index);
        self.all_owners().all(|other| {
            other == owner || multi_leader_priority(other, round_index) >= our_priority
        })
    }

    /// Returns the deterministic delay this owner should wait before proposing in `round`,
    /// to spread out concurrent proposals from honest clients. The preferred owner returns
    /// `TimeDelta::ZERO`; others return `hash(owner, round) mod round_duration`. Returns
    /// `None` outside of multi-leader rounds, in the first multi-leader round (where
    /// honest clients all attempt to propose immediately), and `Some(ZERO)` if the round
    /// has no configured timeout.
    pub fn multi_leader_proposal_delay(
        &self,
        owner: &AccountOwner,
        round: Round,
    ) -> Option<TimeDelta> {
        let Round::MultiLeader(round_index) = round else {
            return None;
        };
        if round_index == 0 {
            return None;
        }
        let round_duration = self.round_timeout(round).unwrap_or(TimeDelta::ZERO);
        if round_duration == TimeDelta::ZERO
            || self.is_preferred_multi_leader_proposer(owner, round_index)
        {
            return Some(TimeDelta::ZERO);
        }
        let priority = multi_leader_priority(owner, round_index);
        let prefix = <[u8; 8]>::try_from(&priority.as_bytes().as_slice()[..8])
            .expect("hash is at least 8 bytes long");
        let hash_u64 = u64::from_le_bytes(prefix);
        Some(TimeDelta::from_micros(
            hash_u64 % round_duration.as_micros(),
        ))
    }
}

/// Returns the deterministic priority of `owner` in the multi-leader round with the
/// given index. The owner with the lowest priority is preferred to propose first.
fn multi_leader_priority(owner: &AccountOwner, round_index: u32) -> CryptoHash {
    CryptoHash::new(&MultiLeaderPriorityInput {
        round: round_index,
        owner: *owner,
    })
}

#[derive(Serialize, Deserialize)]
struct MultiLeaderPriorityInput {
    round: u32,
    owner: AccountOwner,
}

impl BcsHashable<'_> for MultiLeaderPriorityInput {}

/// Errors that can happen when attempting to manage a chain (close it, change ownership, or
/// change application permissions).
#[derive(Clone, Copy, Debug, Error, WitStore, WitType)]
pub enum ManageChainError {
    /// The application wasn't allowed to perform this chain management operation.
    #[error("Unauthorized chain management operation")]
    NotPermitted,
}

/// Errors that can happen when verifying the authentication of an operation over an
/// account.
#[derive(Clone, Copy, Debug, Error, WitStore, WitType)]
pub enum AccountPermissionError {
    /// Operations on this account are not permitted in the current execution context.
    #[error("Unauthorized attempt to access account owned by {0}")]
    NotPermitted(AccountOwner),
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::crypto::{Ed25519SecretKey, Secp256k1SecretKey};

    #[test]
    fn test_ownership_round_timeouts() {
        let super_pub_key = Ed25519SecretKey::generate().public();
        let super_owner = AccountOwner::from(super_pub_key);
        let pub_key = Secp256k1SecretKey::generate().public();
        let owner = AccountOwner::from(pub_key);

        let ownership = ChainOwnership {
            super_owners: BTreeSet::from_iter([super_owner]),
            owners: BTreeMap::from_iter([(owner, 100)]),
            first_leader: Some(owner),
            multi_leader_rounds: 10,
            open_multi_leader_rounds: false,
            timeout_config: TimeoutConfig {
                fast_round_duration: Some(TimeDelta::from_secs(5)),
                base_timeout: TimeDelta::from_secs(10),
                timeout_increment: TimeDelta::from_secs(1),
                fallback_duration: TimeDelta::from_secs(60 * 60),
            },
        };

        assert_eq!(
            ownership.round_timeout(Round::Fast),
            Some(TimeDelta::from_secs(5))
        );
        assert_eq!(
            ownership.round_timeout(Round::MultiLeader(0)),
            Some(TimeDelta::from_secs(10))
        );
        assert_eq!(
            ownership.round_timeout(Round::MultiLeader(8)),
            Some(TimeDelta::from_secs(18))
        );
        assert_eq!(
            ownership.round_timeout(Round::SingleLeader(0)),
            Some(TimeDelta::from_secs(10))
        );
        assert_eq!(
            ownership.round_timeout(Round::SingleLeader(1)),
            Some(TimeDelta::from_secs(11))
        );
        assert_eq!(
            ownership.round_timeout(Round::SingleLeader(8)),
            Some(TimeDelta::from_secs(18))
        );
    }

    #[test]
    fn test_multi_leader_proposal_delay() {
        let owner_a = AccountOwner::from(Ed25519SecretKey::generate().public());
        let owner_b = AccountOwner::from(Ed25519SecretKey::generate().public());
        let owner_c = AccountOwner::from(Ed25519SecretKey::generate().public());
        let mut ownership = ChainOwnership::multiple(
            [(owner_a, 100), (owner_b, 100), (owner_c, 100)],
            10,
            TimeoutConfig {
                fast_round_duration: None,
                base_timeout: TimeDelta::from_secs(10),
                timeout_increment: TimeDelta::ZERO,
                fallback_duration: TimeDelta::MAX,
            },
        );

        // No jitter in MultiLeader(0): all clients race; lowest-hash recovery kicks in
        // only from MultiLeader(1) onwards.
        for owner in [owner_a, owner_b, owner_c] {
            assert_eq!(
                ownership.multi_leader_proposal_delay(&owner, Round::MultiLeader(0)),
                None
            );
        }

        // Outside multi-leader rounds, no delay is computed.
        assert_eq!(
            ownership.multi_leader_proposal_delay(&owner_a, Round::SingleLeader(1)),
            None
        );

        // In MultiLeader(1) exactly one owner is preferred (delay = 0); the others
        // get a deterministic, bounded delay.
        let delays = [owner_a, owner_b, owner_c].map(|owner| {
            ownership
                .multi_leader_proposal_delay(&owner, Round::MultiLeader(1))
                .expect("delay should be defined in a multi-leader round")
        });
        let zero_count = delays.iter().filter(|d| **d == TimeDelta::ZERO).count();
        assert_eq!(
            zero_count, 1,
            "exactly one owner should be the preferred proposer"
        );
        for delay in delays {
            assert!(delay < TimeDelta::from_secs(10));
        }

        // Open multi-leader rounds have no fixed proposer set; nobody is preferred,
        // so every owner waits its own deterministic jitter.
        ownership.open_multi_leader_rounds = true;
        for owner in [owner_a, owner_b, owner_c] {
            let delay = ownership
                .multi_leader_proposal_delay(&owner, Round::MultiLeader(1))
                .expect("delay should be defined in a multi-leader round");
            assert!(delay > TimeDelta::ZERO && delay < TimeDelta::from_secs(10));
        }
    }
}

doc_scalar!(ChainOwnership, "Represents the owner(s) of a chain");