yedad_ladder 0.1.0

#![warn(missing_docs)]
//! # yedad_ladder
//!
//! Optimized core implementation of the Yedad ladder hash algorithm.
//!
//! This library provides structures and methods for generating a
//! hierarchical hash ladder from a private key, producing verifiable
//! proofs, and securely advancing through ladder steps. It is suitable
//! for deterministic key derivation, proof generation, and lightweight
//! cryptographic operations.

use sha2::{Digest, Sha256};
use subtle::ConstantTimeEq;
use thiserror::Error;

// ===== Constants =====

/// Hash size in bytes (32 bytes for SHA-256)
pub const HASH_SIZE: usize = 32;

/// Number of rounds used for Master Seed generation
pub const MASTER_SEED_ROUNDS: usize = 2048;

/// Number of rounds used for root generation
pub const ROOT_GENERATION_ROUNDS: usize = 2048;

/// Default ladder height (number of steps)
pub const DEFAULT_LADDER_HEIGHT: usize = 100_000;

/// Domain separation tag for master seed hashing
const DOMAIN_MASTER: &[u8] = b"YEDAD_MASTER";

/// Domain separation tag for root hash computation
const DOMAIN_ROOT: &[u8] = b"YEDAD_ROOT";

/// Domain separation tag for ladder step hashing
const DOMAIN_STEP: &[u8] = b"YEDAD_STEP";

/// Type alias for a 32-byte SHA-256 hash
pub type Hash = [u8; HASH_SIZE];

// ===== Errors =====

/// Errors that can occur in Yedad ladder operations.
#[derive(Error, Debug, Clone, PartialEq, Eq)]
pub enum YedadError {
    /// Input provided is invalid or has incorrect size.
    #[error("invalid input size")]
    InvalidInputSize,

    /// A provided proof does not match the expected hash.
    #[error("invalid proof")]
    InvalidProof,

    /// Attempted to advance past the end of the ladder.
    #[error("ladder exhausted")]
    LadderExhausted,

    /// Ladder index is invalid (must be greater than zero).
    #[error("invalid ladder index (must be > 0)")]
    InvalidLadderIndex,

    /// Step index is out of the allowed range.
    #[error("step out of range")]
    StepOutOfRange,

    /// Target hash not found in the ladder.
    #[error("hash not found in ladder")]
    HashNotFound,
}

// ===== Internal helper functions =====

/// Compute SHA-256 hash of the input.
#[inline]
fn sha256(data: &[u8]) -> Hash {
    let mut hasher = Sha256::new();
    hasher.update(data);
    let result = hasher.finalize();

    let mut out = [0u8; HASH_SIZE];
    out.copy_from_slice(&result);
    out
}

/// Constant-time equality comparison for hashes using `subtle`.
#[inline]
fn ct_eq(a: &Hash, b: &Hash) -> bool {
    a.ct_eq(b).into()
}

/// Double SHA-256 with domain separation.
#[inline]
fn double_hash_domain(domain: &[u8], data: &[u8]) -> Hash {
    let mut hasher = Sha256::new();
    hasher.update(domain);
    hasher.update(data);
    let first = hasher.finalize();
    sha256(&first)
}

/// Public double hash in the step domain.
#[inline]
pub fn double_hash(data: &[u8]) -> Hash {
    double_hash_domain(DOMAIN_STEP, data)
}

/// Iteratively compute double hashes for a given number of rounds.
fn iterative_double_hash(initial: &[u8], rounds: usize, domain: &[u8]) -> Hash {
    let mut current = double_hash_domain(domain, initial);
    for _ in 1..rounds {
        current = double_hash_domain(domain, &current);
    }
    current
}

/// Find the index of a target hash in a ladder starting from root.
fn find_position(root: Hash, target: &Hash, height: usize) -> Option<usize> {
    let mut current = root;
    for idx in 0..=height {
        if ct_eq(&current, target) {
            return Some(idx);
        }
        current = double_hash(&current);
    }
    None
}

// ===== Core Yedad =====

/// Core Yedad ladder structure holding the master seed.
#[derive(Debug, Clone)]
pub struct Yedad {
    master_seed: Hash,
}

impl Yedad {
    /// Create a new Yedad instance from a private key.
    ///
    /// # Arguments
    /// * `private_key` - Secret input used to derive the master seed.
    pub fn from_private_key<T: AsRef<[u8]>>(private_key: T) -> Self {
        let master_seed =
            iterative_double_hash(private_key.as_ref(), MASTER_SEED_ROUNDS, DOMAIN_MASTER);
        Self { master_seed }
    }

    /// Compute the root hash for a given ladder ID.
    ///
    /// # Errors
    /// Returns `InvalidLadderIndex` if ladder_id is 0.
    pub fn root(&self, ladder_id: u32) -> Result<Hash, YedadError> {
        if ladder_id == 0 {
            return Err(YedadError::InvalidLadderIndex);
        }

        let mut buf = [0u8; HASH_SIZE + 4];
        buf[..HASH_SIZE].copy_from_slice(&self.master_seed);
        buf[HASH_SIZE..].copy_from_slice(&ladder_id.to_be_bytes());

        Ok(iterative_double_hash(
            &buf,
            ROOT_GENERATION_ROUNDS,
            DOMAIN_ROOT,
        ))
    }

    /// Compute the hash at a specific step index of a ladder.
    pub fn step(&self, ladder_id: u32, step_index: usize) -> Result<Hash, YedadError> {
        let mut current = self.root(ladder_id)?;
        for _ in 0..step_index {
            current = double_hash(&current);
        }
        Ok(current)
    }

    /// Compute the last hash (top of the ladder) for a given ladder.
    pub fn last_step(&self, ladder_id: u32, ladder_height: usize) -> Result<Hash, YedadError> {
        self.step(ladder_id, ladder_height)
    }

    /// Get the proof (hash) for a given position in the ladder.
    pub fn get_proof(
        &self,
        ladder_id: u32,
        position: usize,
        ladder_height: usize,
    ) -> Result<Hash, YedadError> {
        if position >= ladder_height {
            return Err(YedadError::LadderExhausted);
        }
        let step_index = ladder_height - 1 - position;
        self.step(ladder_id, step_index)
    }

    /// Find the previous proof for a given current hash.
    pub fn find_proof_by_current_hash(
        &self,
        ladder_id: u32,
        current_hash: &Hash,
        ladder_height: usize,
    ) -> Result<Hash, YedadError> {
        let root = self.root(ladder_id)?;
        if let Some(idx) = find_position(root, current_hash, ladder_height) {
            if idx == 0 {
                return Err(YedadError::StepOutOfRange);
            }
            let mut prev = root;
            let mut cur = double_hash(&prev);
            for _ in 1..idx {
                prev = cur;
                cur = double_hash(&cur);
            }
            Ok(prev)
        } else {
            Err(YedadError::HashNotFound)
        }
    }

    /// Get reference to the master seed.
    pub fn master_seed(&self) -> &Hash {
        &self.master_seed
    }
}

// ===== Slot =====

/// Represents a single ladder slot, maintaining current state.
#[derive(Debug, Clone, Copy)]
pub struct Slot {
    current_hash: Hash,
    ladder_id: u32,
    position: usize,
}

impl Slot {
    /// Create a new slot from the top of a ladder.
    pub fn new(yedad: &Yedad, ladder_id: u32, ladder_height: usize) -> Result<Self, YedadError> {
        let current_hash = yedad.last_step(ladder_id, ladder_height)?;
        Ok(Self {
            current_hash,
            ladder_id,
            position: 0,
        })
    }

    /// Restore a slot from a saved state.
    pub fn from_state(current_hash: Hash, ladder_id: u32, position: usize) -> Self {
        Self {
            current_hash,
            ladder_id,
            position,
        }
    }

    /// Verify a proof and advance the slot.
    pub fn verify_and_advance(
        &mut self,
        proof: &Hash,
        ladder_height: usize,
    ) -> Result<(), YedadError> {
        if self.position >= ladder_height {
            return Err(YedadError::LadderExhausted);
        }

        let check = double_hash(proof);
        if !ct_eq(&check, &self.current_hash) {
            return Err(YedadError::InvalidProof);
        }

        self.current_hash = *proof;
        self.position += 1;
        Ok(())
    }

    /// Check if the ladder slot is exhausted.
    pub fn is_exhausted(&self, ladder_height: usize) -> bool {
        self.position >= ladder_height
    }

    /// Remaining steps in the ladder.
    pub fn remaining(&self, ladder_height: usize) -> usize {
        ladder_height.saturating_sub(self.position)
    }

    /// Get the full state of the slot.
    pub fn state(&self) -> (Hash, u32, usize) {
        (self.current_hash, self.ladder_id, self.position)
    }

    /// Get current hash.
    pub fn current_hash(&self) -> &Hash {
        &self.current_hash
    }

    /// Ladder ID.
    pub fn ladder_id(&self) -> u32 {
        self.ladder_id
    }

    /// Current position in the ladder.
    pub fn position(&self) -> usize {
        self.position
    }
}

// ===== Account =====

/// Represents an account with ladder state derived from a private key.
#[derive(Debug, Clone)]
pub struct Account {
    yedad: Yedad,
    ladder_id: u32,
    position: usize,
    current_hash: Hash,
}

impl Account {
    /// Create a new account from a private key.
    pub fn new_private(
        private_key: &[u8],
        ladder_height: usize,
    ) -> Result<(Self, Hash), YedadError> {
        let yedad = Yedad::from_private_key(private_key);
        let ladder_id = 1;
        let current_hash = yedad.last_step(ladder_id, ladder_height)?;

        let account = Self {
            yedad,
            ladder_id,
            position: 0,
            current_hash,
        };

        Ok((account, current_hash))
    }

    /// Load an account from a previous state.
    pub fn load(
        private_key: &[u8],
        ladder_id: u32,
        current_hash: &Hash,
        ladder_height: usize,
    ) -> Result<Self, YedadError> {
        let yedad = Yedad::from_private_key(private_key);
        let root = yedad.root(ladder_id)?;

        if let Some(idx) = find_position(root, current_hash, ladder_height) {
            let position = ladder_height - idx;
            Ok(Self {
                yedad,
                ladder_id,
                position,
                current_hash: *current_hash,
            })
        } else {
            Err(YedadError::HashNotFound)
        }
    }

    /// Get the next proof without advancing.
    pub fn next_proof(&self, ladder_height: usize) -> Result<Hash, YedadError> {
        if self.position >= ladder_height {
            return Err(YedadError::LadderExhausted);
        }
        let proof_index = ladder_height - 1 - self.position;
        self.yedad.step(self.ladder_id, proof_index)
    }

    /// Advance the account by verifying a proof.
    pub fn advance(&mut self, proof: &Hash, ladder_height: usize) -> Result<(), YedadError> {
        if self.position >= ladder_height {
            return Err(YedadError::LadderExhausted);
        }

        let check = double_hash(proof);
        if !ct_eq(&check, &self.current_hash) {
            return Err(YedadError::InvalidProof);
        }

        self.current_hash = *proof;
        self.position += 1;
        Ok(())
    }

    /// Get current ladder state (ID and hash).
    pub fn state(&self) -> (u32, Hash) {
        (self.ladder_id, self.current_hash)
    }

    /// Remaining steps in the ladder.
    pub fn remaining(&self, ladder_height: usize) -> usize {
        ladder_height.saturating_sub(self.position)
    }

    /// Access underlying Yedad instance.
    pub fn yedad(&self) -> &Yedad {
        &self.yedad
    }

    /// Ladder ID.
    pub fn ladder_id(&self) -> u32 {
        self.ladder_id
    }

    /// Current position in the ladder.
    pub fn position(&self) -> usize {
        self.position
    }

    /// Current hash.
    pub fn current_hash(&self) -> &Hash {
        &self.current_hash
    }
}