blvm-consensus 0.1.82

//! Proof of Work functions from Orange Paper Section 8 Section 7

use crate::constants::*;
use crate::error::{ConsensusError, Result};
use crate::types::*;
#[cfg(feature = "spec-lock")]
use blvm_spec_lock::spec_locked;
use sha2::{Digest, Sha256};

/// GetNextWorkRequired: ℋ × ℋ* → ℕ
///
/// Calculate the next work required based on difficulty adjustment using integer arithmetic.
///
/// Difficulty adjustment algorithm (BIP adjustments, including known off-by-one in interval count):
/// 1. Use the previous block's bits (last block before adjustment)
/// 2. Calculate timespan between first and last block of adjustment period
/// 3. Clamp timespan to [expected_time/4, expected_time*4]
/// 4. Expand previous block's bits to full U256 target
/// 5. Multiply target by clamped_timespan (integer)
/// 6. Divide by expected_time (integer)
/// 7. Compress result back to compact bits format
/// 8. Clamp to MAX_TARGET
///
/// **Known Issue (Bitcoin Compatibility)**: This function measures time for (n-1) intervals
/// when given n blocks, but compares against n intervals. Standard implementation
/// behavior exactly for consensus compatibility. For corrected behavior, use
/// `get_next_work_required_corrected()`.
///
/// For block header h and previous headers prev:
/// - prev[0] is the first block of the adjustment period
/// - prev[prev.len()-1] is the last block before the adjustment (use its bits)
///
/// Note: `current_header` parameter is kept for API compatibility but not used in calculation
#[cfg_attr(feature = "spec-lock", spec_locked("7.1", "GetNextWorkRequired"))]
pub fn get_next_work_required(
    _current_header: &BlockHeader,
    prev_headers: &[BlockHeader],
) -> Result<Natural> {
    get_next_work_required_internal(_current_header, prev_headers, false)
}

/// GetNextWorkRequired (Corrected): ℋ × ℋ* → ℕ
///
/// Calculate the next work required with corrected off-by-one error fix.
///
/// This version fixes the known off-by-one error in Bitcoin's difficulty adjustment:
/// - When measuring time for n blocks (indices 0 to n-1), we measure (n-1) intervals
/// - The corrected version adjusts expected_time to account for this
/// - Use this for regtest or new protocol variants that don't need Bitcoin compatibility
///
/// **Compatibility Warning**: Do NOT use this for Bitcoin mainnet/testnet as it will
/// cause consensus divergence. This is only safe for isolated networks like regtest.
pub fn get_next_work_required_corrected(
    _current_header: &BlockHeader,
    prev_headers: &[BlockHeader],
) -> Result<Natural> {
    get_next_work_required_internal(_current_header, prev_headers, true)
}

/// Internal implementation of difficulty adjustment
///
/// `use_corrected`: If true, fixes the off-by-one error by adjusting expected_time
///                  to account for measuring (n-1) intervals when given n blocks.
fn get_next_work_required_internal(
    _current_header: &BlockHeader,
    prev_headers: &[BlockHeader],
    use_corrected: bool,
) -> Result<Natural> {
    // Need at least 2 previous headers for adjustment
    if prev_headers.len() < 2 {
        return Err(ConsensusError::InvalidProofOfWork(
            "Insufficient headers for difficulty adjustment".into(),
        ));
    }

    // Use the last block's bits (before adjustment) - this is the previous difficulty
    let last_header = &prev_headers[prev_headers.len() - 1];
    let previous_bits = last_header.bits;

    // Calculate timespan between first and last block of adjustment period
    // prev_headers[0] is the first block, last_header is the last block
    let first_timestamp = prev_headers[0].timestamp;
    let last_timestamp = last_header.timestamp;

    // Timespan should be positive (last block comes after first)
    if last_timestamp < first_timestamp {
        return Err(ConsensusError::InvalidProofOfWork(
            "Invalid timestamp order in difficulty adjustment".into(),
        ));
    }

    let time_span = last_timestamp - first_timestamp;

    // Calculate expected_time based on whether we're using corrected version
    // When we have n blocks (indices 0 to n-1), we measure (n-1) intervals
    // Bitcoin bug: compares against n intervals
    // Corrected: compares against (n-1) intervals
    let expected_time = if use_corrected {
        // Corrected: account for the fact we're measuring (n-1) intervals
        // If we have exactly DIFFICULTY_ADJUSTMENT_INTERVAL blocks, we measure
        // (DIFFICULTY_ADJUSTMENT_INTERVAL - 1) intervals
        let num_intervals = prev_headers.len() as u64;
        if num_intervals == DIFFICULTY_ADJUSTMENT_INTERVAL {
            (DIFFICULTY_ADJUSTMENT_INTERVAL - 1) * TARGET_TIME_PER_BLOCK
        } else {
            // For other cases, use the actual number of intervals measured
            (num_intervals - 1) * TARGET_TIME_PER_BLOCK
        }
    } else {
        // Bitcoin-compatible: use the buggy version
        DIFFICULTY_ADJUSTMENT_INTERVAL * TARGET_TIME_PER_BLOCK
    };

    // Clamp timespan to [expected_time/4, expected_time*4] before calculation
    // This prevents extreme difficulty adjustments (max 4x change per period)
    let clamped_timespan = time_span.max(expected_time / 4).min(expected_time * 4);

    // Runtime assertion: Clamped timespan must be within bounds
    debug_assert!(
        clamped_timespan >= expected_time / 4,
        "Clamped timespan ({}) must be >= expected_time/4 ({})",
        clamped_timespan,
        expected_time / 4
    );
    debug_assert!(
        clamped_timespan <= expected_time * 4,
        "Clamped timespan ({}) must be <= expected_time*4 ({})",
        clamped_timespan,
        expected_time * 4
    );

    // Expand previous block's bits to full U256 target
    let old_target = expand_target(previous_bits)?;

    if old_target.is_zero() {
        return Err(ConsensusError::InvalidProofOfWork(
            "Previous block target is zero (invalid compact bits)".into(),
        ));
    }

    // Multiply target by clamped_timespan (integer multiplication).
    // Regtest minimum-difficulty nBits (0x207fffff) expands to a very large U256; multiplying
    // by the clamped timespan can exceed U256::MAX. Bitcoin keeps prior difficulty in
    // pathological cases — here we preserve `previous_bits` when no exact product fits.
    let multiplied_target = match old_target.checked_mul_u64(clamped_timespan) {
        Some(t) => t,
        None => {
            return Ok(previous_bits);
        }
    };

    // Runtime assertion: Multiplied target must be >= old target (timespan >= expected_time/4)
    debug_assert!(
        multiplied_target >= old_target || clamped_timespan < expected_time,
        "Multiplied target should be >= old target when timespan >= expected_time"
    );

    // Divide by expected_time (integer division)
    let new_target = multiplied_target.div_u64(expected_time);

    if new_target.is_zero() {
        return Err(ConsensusError::InvalidProofOfWork(
            "Difficulty adjustment produced zero expanded target".into(),
        ));
    }

    // Compress back to compact bits format
    let new_bits = compress_target(&new_target)?;

    // Clamp to maximum target (minimum difficulty)
    let clamped_bits = new_bits.min(MAX_TARGET as Natural);

    // Runtime assertion: Clamped bits must be positive and <= MAX_TARGET
    debug_assert!(
        clamped_bits > 0,
        "Clamped bits ({clamped_bits}) must be positive"
    );
    debug_assert!(
        clamped_bits <= MAX_TARGET as Natural,
        "Clamped bits ({clamped_bits}) must be <= MAX_TARGET ({MAX_TARGET})"
    );

    // Ensure result is positive
    if clamped_bits == 0 {
        return Err(ConsensusError::InvalidProofOfWork(
            "Difficulty adjustment resulted in zero target".into(),
        ));
    }

    Ok(clamped_bits)
}

/// Network difficulty parameters for [`next_required_bits`].
///
/// `get_next_work_required` is only the retarget formula. This struct is the
/// rest of the rule: how often retarget happens, the proof-of-work ceiling, and
/// whether a late block may use that ceiling.
struct PowParams {
    limit_bits: u64,
    interval: u64,
    timespan: u64,
    spacing: u64,
    allow_min_difficulty: bool,
    no_retargeting: bool,
    /// BIP94: retarget from the first block of the period, not the last.
    enforce_bip94: bool,
}

fn pow_params(network: Network) -> PowParams {
    let mainnet_timespan = DIFFICULTY_ADJUSTMENT_INTERVAL * TARGET_TIME_PER_BLOCK;
    match network {
        Network::Mainnet => PowParams {
            limit_bits: MAX_TARGET as u64,
            interval: DIFFICULTY_ADJUSTMENT_INTERVAL,
            timespan: mainnet_timespan,
            spacing: TARGET_TIME_PER_BLOCK,
            allow_min_difficulty: false,
            no_retargeting: false,
            enforce_bip94: false,
        },
        Network::Testnet => PowParams {
            limit_bits: MAX_TARGET as u64,
            interval: DIFFICULTY_ADJUSTMENT_INTERVAL,
            timespan: mainnet_timespan,
            spacing: TARGET_TIME_PER_BLOCK,
            allow_min_difficulty: true,
            no_retargeting: false,
            enforce_bip94: false,
        },
        Network::Testnet4 => PowParams {
            limit_bits: MAX_TARGET as u64,
            interval: DIFFICULTY_ADJUSTMENT_INTERVAL,
            timespan: mainnet_timespan,
            spacing: TARGET_TIME_PER_BLOCK,
            allow_min_difficulty: true,
            no_retargeting: false,
            enforce_bip94: true,
        },
        Network::Signet => PowParams {
            limit_bits: 0x1e0377ae,
            interval: DIFFICULTY_ADJUSTMENT_INTERVAL,
            timespan: mainnet_timespan,
            spacing: TARGET_TIME_PER_BLOCK,
            allow_min_difficulty: false,
            no_retargeting: false,
            enforce_bip94: false,
        },
        Network::Regtest => PowParams {
            limit_bits: 0x207fffff,
            interval: 144,
            timespan: 24 * 60 * 60,
            spacing: TARGET_TIME_PER_BLOCK,
            allow_min_difficulty: true,
            no_retargeting: true,
            enforce_bip94: false,
        },
    }
}

/// Compact `nBits` the block at `height` must carry.
///
/// Off a difficulty boundary the result is the parent’s bits. On a boundary it
/// is the retarget of that period, unless the network does not retarget.
/// Testnet and regtest may use the proof-of-work limit when the block is more
/// than two target spacings after its parent; otherwise the bits are those of
/// the last block in the period that is not itself a minimum-difficulty block.
///
/// `ancestor(height)` returns that block’s compact bits and timestamp.
/// Height 0 has no parent and returns `Ok(None)`.
///
/// This is not [`get_next_work_required`]. That function always retargets from
/// whatever headers it is given.
pub fn next_required_bits(
    network: Network,
    height: u64,
    block_timestamp: u64,
    ancestor: &dyn Fn(u64) -> Option<(u64, u64)>,
) -> Result<Option<u64>> {
    if height == 0 {
        return Ok(None);
    }
    let params = pow_params(network);
    let parent_height = height - 1;
    let (parent_bits, parent_time) = ancestor(parent_height).ok_or_else(|| {
        ConsensusError::InvalidProofOfWork(
            format!("missing ancestor header at height {parent_height} for difficulty").into(),
        )
    })?;

    if params.interval == 0 || height % params.interval != 0 {
        if params.allow_min_difficulty {
            let limit_time = parent_time.saturating_add(params.spacing.saturating_mul(2));
            if block_timestamp > limit_time {
                return Ok(Some(params.limit_bits));
            }
            let mut walk_height = parent_height;
            let mut bits = parent_bits;
            while walk_height > 0 && walk_height % params.interval != 0 && bits == params.limit_bits
            {
                walk_height -= 1;
                let (prev_bits, _) = ancestor(walk_height).ok_or_else(|| {
                    ConsensusError::InvalidProofOfWork(
                        format!("missing ancestor header at height {walk_height} for difficulty")
                            .into(),
                    )
                })?;
                bits = prev_bits;
            }
            return Ok(Some(bits));
        }
        return Ok(Some(parent_bits));
    }

    if params.no_retargeting {
        return Ok(Some(parent_bits));
    }

    // First block of the period: parent is the last block of the previous period.
    // BIP94 keeps real difficulty in that first block, because the last block of
    // the period may be a min-difficulty exception.
    let first_height = parent_height - (params.interval - 1);
    let (first_bits, first_time) = ancestor(first_height).ok_or_else(|| {
        ConsensusError::InvalidProofOfWork(
            format!("missing ancestor header at height {first_height} for difficulty").into(),
        )
    })?;
    let base_bits = if params.enforce_bip94 {
        first_bits
    } else {
        parent_bits
    };
    Ok(Some(retarget_bits(
        base_bits,
        first_time,
        parent_time,
        params.timespan,
        params.limit_bits,
    )?))
}

fn retarget_bits(
    prev_bits: u64,
    first_time: u64,
    last_time: u64,
    timespan: u64,
    limit_bits: u64,
) -> Result<u64> {
    let actual = (last_time as i64).saturating_sub(first_time as i64);
    let min_span = (timespan / 4) as i64;
    let max_span = timespan.saturating_mul(4) as i64;
    let span = if actual < min_span {
        min_span
    } else if actual > max_span {
        max_span
    } else {
        actual
    } as u64;

    let old = expand_target(prev_bits)?;
    if old.is_zero() {
        return Ok(0);
    }
    let limit = expand_target(limit_bits)?;
    let product = old.checked_mul_u64(span).ok_or_else(|| {
        ConsensusError::InvalidProofOfWork("difficulty adjustment overflow".into())
    })?;
    let new_target = product.div_u64(timespan);
    if new_target.is_zero() {
        return Ok(0);
    }
    if new_target > limit {
        return Ok(limit_bits);
    }
    compress_target(&new_target)
}

/// CheckProofOfWork: ℋ → {true, false}
///
/// Check if the block header satisfies the proof of work requirement.
/// Formula: SHA256(SHA256(header)) <= ExpandTarget(header.bits)
#[cfg_attr(feature = "spec-lock", spec_locked("7.2", "CheckProofOfWork"))]
#[cfg_attr(feature = "production", inline(always))]
#[cfg_attr(not(feature = "production"), inline)]
pub fn check_proof_of_work(header: &BlockHeader) -> Result<bool> {
    let header_bytes = serialize_header(header);
    let hash1 = Sha256::digest(header_bytes);
    let hash2 = Sha256::digest(hash1);
    let mut hash_bytes = [0u8; 32];
    hash_bytes.copy_from_slice(&hash2);
    proof_hash_meets_target(header.bits, &U256::from_bytes(&hash_bytes))
}

#[inline]
fn proof_hash_meets_target(bits: Natural, hash_value: &U256) -> Result<bool> {
    // The compact sign bit is not part of the target. A negative encoding is not work.
    if bits & 0x0080_0000 != 0 {
        return Ok(false);
    }
    let target = expand_target(bits)?;
    if target.is_zero() {
        return Ok(false);
    }
    Ok(*hash_value <= target)
}

/// Set the regtest easiest target and search a nonce until the header meets it.
///
/// Synthetic test headers are built with compact targets that a unit test cannot
/// grind. Call this after the header fields are final.
pub fn meet_regtest_proof_of_work(header: &mut BlockHeader) {
    header.bits = 0x207f_ffff;
    header.nonce = 0;
    while !check_proof_of_work(header).unwrap_or(false) {
        header.nonce = header.nonce.wrapping_add(1);
    }
}

/// Batch check proof of work for multiple headers
///
/// This function validates multiple block headers in batch, which is useful during
/// initial block download or header synchronization. Headers are serialized and
/// hashed in parallel when the production feature is enabled.
///
/// # Arguments
/// * `headers` - Slice of block headers to validate
///
/// # Returns
/// Vector of tuples (is_valid, computed_hash) for each header. Hash is None for invalid headers.
/// Order matches input headers.
#[cfg_attr(feature = "spec-lock", spec_locked("7.2", "CheckProofOfWork"))]
#[cfg(feature = "production")]
pub fn batch_check_proof_of_work(headers: &[BlockHeader]) -> Result<Vec<(bool, Option<Hash>)>> {
    use crate::optimizations::simd_vectorization;

    if headers.is_empty() {
        return Ok(Vec::new());
    }

    // Serialize all headers (stack-allocated 80-byte arrays)
    let header_bytes_vec: Vec<[u8; 80]> = {
        #[cfg(feature = "rayon")]
        {
            use rayon::prelude::*;
            headers.par_iter().map(serialize_header).collect()
        }
        #[cfg(not(feature = "rayon"))]
        {
            headers.iter().map(serialize_header).collect()
        }
    };

    // Batch hash all serialized headers using double SHA256
    let header_refs: Vec<&[u8]> = header_bytes_vec.iter().map(|v| v.as_slice()).collect();
    let aligned_hashes = simd_vectorization::batch_double_sha256_aligned(&header_refs);
    // Convert to regular hashes for compatibility
    let hashes: Vec<[u8; 32]> = aligned_hashes.iter().map(|h| *h.as_bytes()).collect();

    // Validate each hash against its target
    let mut results = Vec::with_capacity(headers.len());
    for (i, header) in headers.iter().enumerate() {
        let hash = hashes[i];

        // Convert to U256 (big-endian)
        let hash_value = U256::from_bytes(&hash);

        // Expand target from compact representation
        match proof_hash_meets_target(header.bits, &hash_value) {
            Ok(true) => results.push((true, Some(hash))),
            Ok(false) => results.push((false, None)),
            Err(_) => results.push((false, None)),
        }
    }

    Ok(results)
}

/// 256-bit integer for Bitcoin target / chainwork calculations (256-bit limb layout).
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct U256([u64; 4]); // 4 * 64 = 256 bits

impl U256 {
    pub fn zero() -> Self {
        U256([0; 4])
    }

    fn from_u32(value: u32) -> Self {
        U256([value as u64, 0, 0, 0])
    }

    #[cfg(test)]
    fn from_u64(value: u64) -> Self {
        U256([value, 0, 0, 0])
    }

    /// Get the low 64 bits for compact target representation
    /// Returns the least significant 64 bits of the value
    fn get_low_64(&self) -> u64 {
        self.0[0]
    }

    /// Serialize as 32 little-endian bytes (Bitcoin `uint256` wire layout).
    pub fn to_le_bytes(&self) -> [u8; 32] {
        let mut bytes = [0u8; 32];
        for (i, &word) in self.0.iter().enumerate() {
            let word_bytes = word.to_le_bytes();
            bytes[i * 8..(i + 1) * 8].copy_from_slice(&word_bytes);
        }
        bytes
    }

    /// Construct from 32 little-endian bytes.
    pub fn from_le_bytes(bytes: [u8; 32]) -> Self {
        let mut words = [0u64; 4];
        for (i, word) in words.iter_mut().enumerate() {
            let mut buf = [0u8; 8];
            buf.copy_from_slice(&bytes[i * 8..(i + 1) * 8]);
            *word = u64::from_le_bytes(buf);
        }
        U256(words)
    }

    /// Bitcoin RPC `GetHex()` / getblocktemplate `target` (byte-reversed display hex).
    pub fn gbt_target_hex(&self) -> String {
        let mut bytes = self.to_le_bytes();
        bytes.reverse();
        hex::encode(bytes)
    }

    /// Low 128 bits (legacy `BlockTemplate.target` summary field).
    pub fn low_u128(&self) -> u128 {
        self.0[0] as u128 | ((self.0[1] as u128) << 64)
    }

    /// Construct from the low 128 bits (high words zero).
    pub fn from_u128(value: u128) -> Self {
        U256([value as u64, (value >> 64) as u64, 0, 0])
    }

    pub fn one() -> Self {
        U256([1, 0, 0, 0])
    }

    pub fn is_zero(&self) -> bool {
        self.0.iter().all(|&w| w == 0)
    }

    #[allow(clippy::should_implement_trait)]
    pub fn not(self) -> Self {
        U256([!self.0[0], !self.0[1], !self.0[2], !self.0[3]])
    }

    pub fn checked_add(self, other: Self) -> Option<Self> {
        let mut result = [0u64; 4];
        let mut carry = 0u128;
        for (i, word) in result.iter_mut().enumerate() {
            let sum = self.0[i] as u128 + other.0[i] as u128 + carry;
            *word = sum as u64;
            carry = sum >> 64;
        }
        if carry != 0 { None } else { Some(U256(result)) }
    }

    pub fn saturating_add(self, other: Self) -> Self {
        self.checked_add(other).unwrap_or(U256([u64::MAX; 4]))
    }

    fn sub(self, other: Self) -> Self {
        let mut result = [0u64; 4];
        let mut borrow = 0u8;
        for (i, word) in result.iter_mut().enumerate() {
            let mut minuend = self.0[i] as u128;
            if borrow != 0 {
                minuend += 1u128 << 64;
                borrow = 0;
            }
            if minuend >= other.0[i] as u128 {
                *word = (minuend - other.0[i] as u128) as u64;
            } else {
                *word = (minuend + (1u128 << 64) - other.0[i] as u128) as u64;
                borrow = 1;
            }
        }
        U256(result)
    }

    fn bit(self, bit: u32) -> bool {
        (self.0[(bit / 64) as usize] >> (bit % 64)) & 1 == 1
    }

    fn with_bit_set(self, bit: u32) -> Self {
        let mut result = self;
        result.0[(bit / 64) as usize] |= 1u64 << (bit % 64);
        result
    }

    /// Full-width unsigned division for 256-bit chainwork arithmetic.
    #[allow(clippy::should_implement_trait)]
    pub fn div(self, divisor: Self) -> Self {
        if divisor.is_zero() {
            return U256::zero();
        }
        if self < divisor {
            return U256::zero();
        }
        let mut quotient = U256::zero();
        let mut remainder = U256::zero();
        for bit in (0..256).rev() {
            remainder = remainder.shl(1);
            if self.bit(bit) {
                remainder = remainder
                    .checked_add(U256::one())
                    .unwrap_or(U256([u64::MAX; 4]));
            }
            if remainder >= divisor {
                remainder = remainder.sub(divisor);
                quotient = quotient.with_bit_set(bit);
            }
        }
        quotient
    }

    /// Serialize as 32 big-endian bytes (Bitcoin RPC `chainwork` display order).
    pub fn to_be_bytes(self) -> [u8; 32] {
        let mut bytes = self.to_le_bytes();
        bytes.reverse();
        bytes
    }

    /// Parse 32 big-endian bytes (RPC / chainstate cache layout).
    pub fn from_be_bytes(bytes: &[u8; 32]) -> Self {
        let mut le = *bytes;
        le.reverse();
        Self::from_bytes(&le)
    }

    #[cfg(test)]
    fn to_bytes(&self) -> [u8; 32] {
        self.to_le_bytes()
    }

    fn shl(&self, shift: u32) -> Self {
        if shift >= 256 {
            return U256::zero();
        }

        let mut result = U256::zero();
        let word_shift = (shift / 64) as usize;
        let bit_shift = shift % 64;

        for i in 0..4 {
            if i + word_shift < 4 {
                result.0[i + word_shift] |= self.0[i] << bit_shift;
                if bit_shift > 0 && i + word_shift + 1 < 4 {
                    result.0[i + word_shift + 1] |= self.0[i] >> (64 - bit_shift);
                }
            }
        }

        result
    }

    fn shr(&self, shift: u32) -> Self {
        if shift >= 256 {
            return U256::zero();
        }

        let mut result = U256::zero();
        let word_shift = (shift / 64) as usize;
        let bit_shift = shift % 64;

        // Runtime assertion: word_shift must be < 4 (since shift < 256)
        debug_assert!(
            word_shift < 4,
            "Word shift ({word_shift}) must be < 4 (shift: {shift})"
        );

        // Runtime assertion: bit_shift must be < 64
        debug_assert!(
            bit_shift < 64,
            "Bit shift ({bit_shift}) must be < 64 (shift: {shift})"
        );

        if bit_shift == 0 {
            for i in word_shift..4 {
                result.0[i - word_shift] = self.0[i];
            }
        } else {
            // Limb pairing for 256-bit shift: each output word combines the low bits of
            // self[i] and the high bits of self[i+1].
            for i in word_shift..4 {
                let mut word = self.0[i] >> bit_shift;
                if i + 1 < 4 {
                    word |= self.0[i + 1] << (64 - bit_shift);
                }
                result.0[i - word_shift] = word;
            }
        }

        result
    }

    fn from_bytes(bytes: &[u8; 32]) -> Self {
        let mut words = [0u64; 4];
        for (i, word) in words.iter_mut().enumerate() {
            let start = i * 8;
            let _end = start + 8;
            *word = u64::from_le_bytes([
                bytes[start],
                bytes[start + 1],
                bytes[start + 2],
                bytes[start + 3],
                bytes[start + 4],
                bytes[start + 5],
                bytes[start + 6],
                bytes[start + 7],
            ]);
        }
        U256(words)
    }

    /// Multiply U256 by u64 with overflow checking
    /// Returns None if overflow occurs
    fn checked_mul_u64(&self, rhs: u64) -> Option<Self> {
        // Use u128 for intermediate calculations to avoid overflow
        let mut carry = 0u128;
        let mut result = U256::zero();

        // Optimization: Unroll 4-iteration loop for better performance
        // Loop unrolling reduces loop overhead and improves instruction-level parallelism
        #[cfg(feature = "production")]
        {
            // Unrolled: i = 0, 1, 2, 3
            // i = 0
            let product = (self.0[0] as u128) * (rhs as u128) + carry;
            result.0[0] = product as u64;
            carry = product >> 64;

            // i = 1
            let product = (self.0[1] as u128) * (rhs as u128) + carry;
            result.0[1] = product as u64;
            carry = product >> 64;

            // i = 2
            let product = (self.0[2] as u128) * (rhs as u128) + carry;
            result.0[2] = product as u64;
            carry = product >> 64;

            // i = 3
            let product = (self.0[3] as u128) * (rhs as u128) + carry;
            result.0[3] = product as u64;
            carry = product >> 64;

            // Check for overflow in the final word
            if carry > 0 {
                return None; // Overflow
            }
        }

        #[cfg(not(feature = "production"))]
        {
            for i in 0..4 {
                let product = (self.0[i] as u128) * (rhs as u128) + carry;
                result.0[i] = product as u64;
                carry = product >> 64;

                // Check for overflow in the final word
                if i == 3 && carry > 0 {
                    return None; // Overflow
                }
            }
        }

        Some(result)
    }

    /// Divide U256 by u64 (integer division)
    ///
    /// Mathematical invariants:
    /// - Result <= self (division never increases value)
    /// - If rhs > 0, then result * rhs + remainder = self
    /// - Division by zero returns max value (error indicator)
    fn div_u64(&self, rhs: u64) -> Self {
        if rhs == 0 {
            // Division by zero - return max value as error indicator
            // In practice, this should never happen for difficulty adjustment
            return U256([u64::MAX; 4]);
        }

        let mut remainder = 0u128;
        let mut result = U256::zero();

        // Divide from most significant word to least significant
        // Optimization: Unroll 4-iteration loop for better performance
        // Loop unrolling reduces loop overhead and improves instruction-level parallelism
        #[cfg(feature = "production")]
        {
            // Unrolled: i = 3, 2, 1, 0
            // i = 3
            let dividend = (remainder << 64) | (self.0[3] as u128);
            let quotient = dividend / (rhs as u128);
            remainder = dividend % (rhs as u128);
            debug_assert!(quotient <= u64::MAX as u128, "Quotient must fit in u64");
            result.0[3] = quotient as u64;

            // i = 2
            let dividend = (remainder << 64) | (self.0[2] as u128);
            let quotient = dividend / (rhs as u128);
            remainder = dividend % (rhs as u128);
            debug_assert!(quotient <= u64::MAX as u128, "Quotient must fit in u64");
            result.0[2] = quotient as u64;

            // i = 1
            let dividend = (remainder << 64) | (self.0[1] as u128);
            let quotient = dividend / (rhs as u128);
            remainder = dividend % (rhs as u128);
            debug_assert!(quotient <= u64::MAX as u128, "Quotient must fit in u64");
            result.0[1] = quotient as u64;

            // i = 0
            let dividend = (remainder << 64) | (self.0[0] as u128);
            let quotient = dividend / (rhs as u128);
            remainder = dividend % (rhs as u128);
            debug_assert!(quotient <= u64::MAX as u128, "Quotient must fit in u64");
            result.0[0] = quotient as u64;
        }

        #[cfg(not(feature = "production"))]
        {
            // Non-production: use loop for readability
            for i in (0..4).rev() {
                let dividend = (remainder << 64) | (self.0[i] as u128);
                let quotient = dividend / (rhs as u128);
                remainder = dividend % (rhs as u128);
                debug_assert!(
                    quotient <= u64::MAX as u128,
                    "Quotient ({quotient}) must fit in u64"
                );
                result.0[i] = quotient as u64;
            }
        }

        // Runtime assertion: Result must be <= self (division never increases)
        debug_assert!(
            result <= *self,
            "Division result ({result:?}) must be <= dividend ({self:?})"
        );

        // Runtime assertion: Remainder must be < rhs
        debug_assert!(
            remainder < rhs as u128,
            "Remainder ({remainder}) must be < divisor ({rhs})"
        );

        result
    }

    /// Find the highest set bit position (0-indexed from MSB)
    /// Returns None if the value is zero
    fn highest_set_bit(&self) -> Option<u32> {
        for (i, &word) in self.0.iter().rev().enumerate() {
            if word != 0 {
                let word_index = (3 - i) as u32;
                let bit_pos = word_index * 64 + (63 - word.leading_zeros());
                return Some(bit_pos);
            }
        }
        None
    }

    /// Convert U256 to f64 for difficulty display.
    /// Precision loss for very large values; sufficient for RPC difficulty (4-8 significant digits).
    fn to_f64(self) -> f64 {
        if self.is_zero() {
            return 0.0;
        }
        let mut result = 0.0_f64;
        result += self.0[0] as f64;
        result += (self.0[1] as f64) * 2.0_f64.powi(64);
        result += (self.0[2] as f64) * 2.0_f64.powi(128);
        result += (self.0[3] as f64) * 2.0_f64.powi(192);
        result
    }
}

impl serde::Serialize for U256 {
    fn serialize<S: serde::Serializer>(
        &self,
        serializer: S,
    ) -> std::result::Result<S::Ok, S::Error> {
        serializer.serialize_str(&self.gbt_target_hex())
    }
}

impl<'de> serde::Deserialize<'de> for U256 {
    fn deserialize<D: serde::Deserializer<'de>>(
        deserializer: D,
    ) -> std::result::Result<Self, D::Error> {
        let hex_str = <String as serde::Deserialize>::deserialize(deserializer)?;
        if hex_str.len() != 64 {
            return Err(serde::de::Error::custom("target hex must be 64 characters"));
        }
        let mut bytes = [0u8; 32];
        for i in 0..32 {
            bytes[i] = u8::from_str_radix(&hex_str[i * 2..i * 2 + 2], 16)
                .map_err(serde::de::Error::custom)?;
        }
        bytes.reverse();
        Ok(U256::from_le_bytes(bytes))
    }
}

impl PartialOrd for U256 {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for U256 {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        for (a, b) in self.0.iter().rev().zip(other.0.iter().rev()) {
            match a.cmp(b) {
                std::cmp::Ordering::Equal => continue,
                other => return other,
            }
        }
        std::cmp::Ordering::Equal
    }
}

/// Convert compact target bits to human-readable difficulty (MAX_TARGET / target).
///
/// Used by getblockchaininfo, getmininginfo RPC for display. Formula: difficulty = MAX_TARGET / target
/// where MAX_TARGET = 0x00000000FFFF0000000000000000000000000000000000000000000000000000 (genesis).
pub fn difficulty_from_bits(bits: Natural) -> Result<f64> {
    let target = expand_target(bits)?;
    if target.is_zero() {
        return Ok(1.0);
    }
    // MAX_TARGET = 0x00000000FFFF0000... (genesis target, compact 0x1d00ffff)
    let max_target = U256::from_bytes(&[
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0x00, 0x00, 0xFF,
        0xFF, 0x00, 0x00, 0x00, 0x00,
    ]);
    let max_f64 = max_target.to_f64();
    let target_f64 = target.to_f64();
    if target_f64 == 0.0 {
        return Ok(1.0);
    }
    Ok((max_f64 / target_f64).max(1.0))
}

/// Expand target from compact representation
///
/// Expand compact target representation to full U256 target
///
/// Bitcoin uses a compact representation for difficulty targets.
/// The format is: 0x1d00ffff where:
/// - 0x1d is the exponent (29)
/// - 0x00ffff is the mantissa (65535)
///
/// The actual target is: mantissa * 2^(8 * (exponent - 3))
///
/// # Mathematical Specification (compact target format)
///
/// Implements SetCompact() algorithm for nBits.
/// The inverse operation is `compress_target()` which implements GetCompact().
///
/// **Round-trip Property (Formally Verified):**
/// ∀ bits ∈ [0x03000000, 0x1d00ffff]:
/// - Let expanded = expand_target(bits)
/// - Let compressed = compress_target(expanded)
/// - Let re_expanded = expand_target(compressed)
/// - Then: re_expanded ≤ expanded (compression truncates lower bits)
/// - And: re_expanded.0[2] = expanded.0[2] ∧ re_expanded.0[3] = expanded.0[3]
///   (significant bits preserved exactly)
///
/// # Verified by formally verified
///
/// The round-trip property is formally verified by `_target_expand_compress_round_trip()`
/// which proves the mathematical specification holds for all valid target values.
#[cfg_attr(feature = "spec-lock", spec_locked("7.1", "ExpandTarget"))]
pub fn expand_target(bits: Natural) -> Result<U256> {
    // SetCompact implementation:
    // int nSize = nCompact >> 24;
    // uint32_t nWord = nCompact & 0x007fffff;  // 23-bit mantissa (not 24-bit!)
    // if (nSize <= 3) {
    //     nWord >>= 8 * (3 - nSize);
    //     *this = nWord;
    // } else {
    //     *this = nWord;
    //     *this <<= 8 * (nSize - 3);
    // }

    let exponent = (bits >> 24) as u8;
    // SetCompact uses a 23-bit mantissa (Orange Paper §11.3).
    let mantissa = bits & 0x007fffff;

    // Exponent in [3, 32] covers mainnet-style compact targets and regtest minimum-difficulty
    // (e.g. nBits 0x207fffff, exponent 32).
    if !(3..=32).contains(&exponent) {
        return Err(ConsensusError::InvalidProofOfWork(
            "Invalid target exponent".into(),
        ));
    }

    if mantissa == 0 {
        return Ok(U256::zero());
    }

    // If exponent <= 3, right shift; else left shift
    if exponent <= 3 {
        // Target is mantissa >> (8 * (3 - exponent))
        // When exponent = 3: no shift (mantissa as-is)
        // When exponent = 2: shift right by 8 bits (shouldn't happen, but handle it)
        // When exponent = 1: shift right by 16 bits (shouldn't happen, but handle it)
        let shift = 8 * (3 - exponent);
        let mantissa_u256 = U256::from_u32(mantissa as u32);
        Ok(mantissa_u256.shr(shift as u32))
    } else {
        // Target is mantissa << (8 * (exponent - 3))
        // When exponent = 4: shift left by 8 bits
        // When exponent = 29: shift left by 208 bits
        let shift = 8u32 * (exponent as u32 - 3);
        if shift >= 256 {
            return Err(crate::error::ConsensusError::InvalidProofOfWork(
                "Target too large".into(),
            ));
        }
        let mantissa_u256 = U256::from_u32(mantissa as u32);
        Ok(mantissa_u256.shl(shift))
    }
}

/// Per-block chainwork contribution (Orange Paper §11.3 / `GetBlockProof`).
///
/// For compact `bits`, let `target = expand_target(bits)`. When `target == 0`, returns zero;
/// otherwise `(~target / (target + 1)) + 1` in 256-bit arithmetic.
#[cfg_attr(feature = "spec-lock", spec_locked("11.3", "GetBlockProof"))]
pub fn get_block_proof(bits: Natural) -> Result<U256> {
    let target = expand_target(bits)?;
    if target.is_zero() {
        return Ok(U256::zero());
    }
    let target_plus_one = target
        .checked_add(U256::one())
        .ok_or_else(|| ConsensusError::InvalidProofOfWork("Target overflow".into()))?;
    let quotient = target.not().div(target_plus_one);
    Ok(quotient
        .checked_add(U256::one())
        .unwrap_or(U256([u64::MAX; 4])))
}

/// Compress target to compact representation
///
/// Reverse of expand_target: converts U256 target back to compact bits format.
/// Implements GetCompact() algorithm for nBits.
///
/// Format: bits = (exponent << 24) | mantissa
/// - exponent (1 byte): number of bytes needed to represent the target
/// - mantissa (23 bits): the significant digits, with bit 24 (0x00800000) reserved for sign
///
/// The target is normalized to the form: mantissa * 256^(exponent - 3)
/// where mantissa is 23 bits (0x000000 to 0x7fffff) and exponent is in range [3, 34].
///
/// # Mathematical Specification (GetCompact/SetCompact)
///
/// ∀ target ∈ U256, bits = compress_target(target):
/// - Let expanded = expand_target(bits)
/// - Then: expanded ≤ target (compression truncates lower bits, never increases)
/// - And: expanded.0[2] = target.0[2] ∧ expanded.0[3] = target.0[3]
///   (significant bits in words 2, 3 are preserved exactly)
/// - Precision loss in words 0, 1 is acceptable (compact format limitation)
///
/// Compact format may lose precision for very large targets
/// in lower-order bits but preserves the significant bits required for difficulty validation.
///
/// # Verified by formally verified
///
/// The round-trip property is formally verified by `_target_expand_compress_round_trip()`
/// which proves the mathematical specification holds for all valid target values.
#[cfg_attr(feature = "spec-lock", spec_locked("7.1", "CompressTarget"))]
pub(crate) fn compress_target(target: &U256) -> Result<Natural> {
    // Handle zero target
    if target.is_zero() {
        return Ok(0x1d000000); // Zero target with exponent 29 (0x1d)
    }

    // Find the highest set bit to determine size in bytes
    let highest_bit = target
        .highest_set_bit()
        .ok_or_else(|| ConsensusError::InvalidProofOfWork("Cannot compress zero target".into()))?;

    // Calculate size in bytes: nSize = ceil((bits + 1) / 8)
    // This is the number of bytes needed to represent the target
    let n_size = (highest_bit + 1).div_ceil(8);

    // Calculate compact representation
    // nCompact is computed as uint64 first, then converted to uint32
    let mut n_compact: u64;

    if n_size <= 3 {
        // If size <= 3 bytes, shift left to fill 3 bytes
        // Get low 64 bits and shift left by 8 * (3 - nSize) bytes
        let low_64 = target.get_low_64();
        let shift_bytes = 3 - n_size;
        n_compact = low_64 << (8 * shift_bytes);
    } else {
        // If size > 3 bytes, shift right by 8 * (nSize - 3) bytes
        // then get the low 64 bits (which contains the mantissa)
        let shift_bytes = n_size - 3;
        let shifted = target.shr(shift_bytes * 8);
        n_compact = shifted.get_low_64();
    }

    // If the mantissa has bit 0x00800000 set (the sign bit),
    // divide the mantissa by 256 and increase the exponent.
    // This ensures the mantissa fits in 23 bits (0x007fffff).
    let mut n_size_final = n_size;
    while (n_compact & 0x00800000) != 0 {
        n_compact >>= 8;
        n_size_final += 1;
    }

    // Convert to u32 mantissa (taking lower 32 bits)
    // nCompact = GetLow64() which returns uint64, then uses as uint32
    let mantissa = (n_compact & 0x007fffff) as u32;

    // Validate exponent is reasonable (clamp to 29 for safety)
    // Exponent 32 is the regtest minimum-difficulty compact form (0x207fffff).
    if n_size_final > 32 {
        return Err(ConsensusError::InvalidProofOfWork(
            format!("Target too large: exponent {n_size_final} exceeds maximum 32").into(),
        ));
    }

    // Combine exponent and mantissa: (nSize << 24) | mantissa
    let bits = (n_size_final << 24) | mantissa;

    Ok(bits as Natural)
}

/// Serialize block header to the canonical 80-byte wire layout.
fn serialize_header(header: &BlockHeader) -> [u8; 80] {
    // Stack-allocated: headers are always exactly 80 bytes, no heap allocation needed
    let mut bytes = [0u8; 80];

    bytes[0..4].copy_from_slice(&(header.version as u32).to_le_bytes());
    bytes[4..36].copy_from_slice(&header.prev_block_hash);
    bytes[36..68].copy_from_slice(&header.merkle_root);
    bytes[68..72].copy_from_slice(&(header.timestamp as u32).to_le_bytes());
    bytes[72..76].copy_from_slice(&(header.bits as u32).to_le_bytes());
    bytes[76..80].copy_from_slice(&(header.nonce as u32).to_le_bytes());

    bytes
}

#[cfg(test)]
/// Convert bytes to u256 (simplified to u128)
fn u256_from_bytes(bytes: &[u8]) -> u128 {
    let mut value = 0u128;
    for (i, &byte) in bytes.iter().enumerate() {
        if i < 16 {
            // Only use first 16 bytes for u128
            value |= (byte as u128) << (8 * (15 - i));
        }
    }
    value
}

// ============================================================================
// FORMAL VERIFICATION
// ============================================================================

/// Mathematical Specification for Proof of Work:
/// ∀ header H: CheckProofOfWork(H) = SHA256(SHA256(H)) < ExpandTarget(H.bits)
///
/// Invariants:
/// - Hash must be less than target for valid proof of work
/// - Target expansion handles edge cases correctly
/// - Difficulty adjustment respects bounds [0.25, 4.0]
/// - Work calculation is deterministic

#[cfg(test)]
mod property_tests {
    use super::*;
    use proptest::prelude::*;

    fn compact_target_bytes(exponent: u8, mantissa: u32) -> [u8; 32] {
        let mut out = [0u8; 32];
        if mantissa == 0 || !(3..=32).contains(&exponent) {
            return out;
        }
        let shift = (exponent as usize).saturating_sub(3);
        for (i, byte) in mantissa.to_le_bytes().iter().enumerate() {
            let pos = shift + i;
            if pos < 32 {
                out[pos] = *byte;
            }
        }
        out
    }

    fn arb_block_header() -> impl Strategy<Value = BlockHeader> {
        (
            any::<i64>(),
            any::<[u8; 32]>(),
            any::<[u8; 32]>(),
            any::<u64>(),
            0x03000000u32..0x1d00ffffu32,
            any::<u64>(),
        )
            .prop_map(
                |(version, prev_block_hash, merkle_root, timestamp, bits, nonce)| BlockHeader {
                    version,
                    prev_block_hash,
                    merkle_root,
                    timestamp,
                    bits: bits as u64,
                    nonce,
                },
            )
    }

    /// Property test: expand_target handles valid ranges
    proptest! {
        #[test]
        fn prop_expand_target_valid_range(
            exponent in 0u8..=40,
            mantissa in 0u32..=0x007f_ffff
        ) {
            let bits = ((exponent as u64) << 24) | (mantissa as u64);
            let result = expand_target(bits);
            if !(3..=32).contains(&exponent) {
                prop_assert!(result.is_err());
            } else {
                let expected = compact_target_bytes(exponent, mantissa);
                prop_assert_eq!(result.unwrap().to_le_bytes(), expected);
                let signed = bits | 0x0080_0000;
                prop_assert_eq!(expand_target(signed).unwrap().to_le_bytes(), expected);
            }
        }
    }

    /// Property test: check_proof_of_work is deterministic
    proptest! {
        #[test]
        fn prop_check_proof_of_work_deterministic(
            header in arb_block_header()
        ) {
            let result1 = check_proof_of_work(&header);
            let result2 = check_proof_of_work(&header);
            prop_assert_eq!(result1, result2);
        }
    }

    /// Property test: get_next_work_required respects bounds
    proptest! {
        #[test]
        fn prop_get_next_work_required_bounds(
            n in 0usize..6,
            span in 0u64..5_000_000,
            ordered in any::<bool>()
        ) {
            let start = 1_700_000_000u64;
            let mut headers: Vec<BlockHeader> = (0..n)
                .map(|i| BlockHeader {
                    version: 1,
                    prev_block_hash: [0; 32],
                    merkle_root: [1; 32],
                    timestamp: start + (i as u64) * span,
                    bits: 0x1d00ffff,
                    nonce: 0,
                })
                .collect();
            if n >= 2 && !ordered {
                headers[n - 1].timestamp = start.saturating_sub(1);
            }
            let current = headers.first().cloned().unwrap_or(BlockHeader {
                version: 1,
                prev_block_hash: [0; 32],
                merkle_root: [1; 32],
                timestamp: start,
                bits: 0x1d00ffff,
                nonce: 0,
            });
            let result = get_next_work_required(&current, &headers);
            if n < 2 || !ordered {
                prop_assert!(result.is_err());
            } else {
                let bits = result.unwrap();
                prop_assert!(bits > 0);
                prop_assert!(bits <= MAX_TARGET as Natural);
                let next = expand_target(bits).unwrap();
                let previous = expand_target(0x1d00ffff).unwrap();
                prop_assert!(next <= previous);
            }
        }
    }
}

#[cfg(test)]
#[path = "pow_tests.rs"]
mod tests;