newton-core 0.4.16

//! Merkle tree computation for ELIP-008 operator info verification.
//!
//! This module provides functionality for computing Merkle roots and proofs
//! for operator information, as required by ELIP-008 for cross-chain
//! certificate verification.
//!
//! The operator info tree contains leaves computed from each operator's
//! BLS public key and their corresponding weights. This allows destination
//! chains to verify non-signer exclusion proofs.

use alloy::primitives::{keccak256, FixedBytes, U256};
use serde::{Deserialize, Serialize};

/// Salt for operator info leaf hash calculation.
/// Matches `LeafCalculatorMixin.OPERATOR_INFO_LEAF_SALT` from EigenLayer contracts.
/// Value derived from keccak256("OPERATOR_INFO_LEAF_SALT") = 0x75
const OPERATOR_INFO_LEAF_SALT: u8 = 0x75;

/// Represents an operator's information for merkle tree leaf computation.
///
/// Each operator has a BLS public key (G1 point) and a vector of weights
/// representing their stake across different quorums.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct OperatorInfo {
    /// BLS public key X coordinate (G1 point)
    pub pubkey_x: U256,
    /// BLS public key Y coordinate (G1 point)
    pub pubkey_y: U256,
    /// Operator weights across quorums
    pub weights: Vec<U256>,
}

impl OperatorInfo {
    /// Creates a new OperatorInfo from BLS pubkey coordinates and weights.
    pub fn new(pubkey_x: U256, pubkey_y: U256, weights: Vec<U256>) -> Self {
        Self {
            pubkey_x,
            pubkey_y,
            weights,
        }
    }
}

/// Merkle proof for operator inclusion/exclusion verification.
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct MerkleProof {
    /// The proof elements (sibling hashes along the path)
    pub proof: Vec<FixedBytes<32>>,
    /// The index of the leaf in the tree
    pub index: usize,
    /// The leaf value being proven
    pub leaf: FixedBytes<32>,
}

/// Computes the leaf hash for an operator's information.
///
/// The leaf is computed to match the Solidity implementation:
/// `keccak256(abi.encodePacked(OPERATOR_INFO_LEAF_SALT, abi.encode(operatorInfo)))`
///
/// Where `BN254OperatorInfo` is:
/// ```solidity
/// struct BN254OperatorInfo {
///     BN254.G1Point pubkey;  // (uint256 X, uint256 Y)
///     uint256[] weights;
/// }
/// ```
///
/// The `abi.encode` for this dynamic struct produces:
/// - outer offset (32 bytes, value = 0x20 = 32) — ABI wraps dynamic types with an offset
/// - pubkey.X (32 bytes)
/// - pubkey.Y (32 bytes)
/// - offset to weights array (32 bytes, value = 0x60 = 96, relative to struct start)
/// - length of weights array (32 bytes)
/// - weights[i] (32 bytes each)
///
/// Then `abi.encodePacked(0x75, abi.encode(...))` prepends the salt byte.
pub fn compute_operator_info_leaf(operator: &OperatorInfo) -> FixedBytes<32> {
    // capacity: salt (1) + outer_offset (32) + pubkey (64) + inner_offset (32) + length (32) + weights
    let capacity = 1 + 32 + 64 + 32 + 32 + operator.weights.len() * 32;
    let mut encoded = Vec::with_capacity(capacity);

    // 1. Salt prefix (abi.encodePacked adds as single byte)
    encoded.push(OPERATOR_INFO_LEAF_SALT);

    // 2. abi.encode(BN254OperatorInfo) - dynamic struct gets outer offset wrapper
    // Outer offset to struct data (32 bytes, value = 32)
    // abi.encode wraps dynamic types (struct containing uint256[]) with a head offset
    encoded.extend_from_slice(&U256::from(32).to_be_bytes::<32>());
    // pubkey.X (32 bytes)
    encoded.extend_from_slice(&operator.pubkey_x.to_be_bytes::<32>());
    // pubkey.Y (32 bytes)
    encoded.extend_from_slice(&operator.pubkey_y.to_be_bytes::<32>());
    // offset to weights array (32 bytes, relative to struct start) - 96 = 3 * 32 (X + Y + this offset)
    encoded.extend_from_slice(&U256::from(96).to_be_bytes::<32>());
    // length of weights array (32 bytes)
    encoded.extend_from_slice(&U256::from(operator.weights.len()).to_be_bytes::<32>());
    // weights[i] (32 bytes each)
    for weight in &operator.weights {
        encoded.extend_from_slice(&weight.to_be_bytes::<32>());
    }

    keccak256(&encoded)
}

/// Computes the merkle root for a set of operator information.
///
/// If the number of leaves is not a power of 2, the tree is padded with
/// zero hashes.
pub fn compute_operator_info_tree_root(operators: &[OperatorInfo]) -> FixedBytes<32> {
    if operators.is_empty() {
        return FixedBytes::ZERO;
    }

    let leaves: Vec<FixedBytes<32>> = operators.iter().map(compute_operator_info_leaf).collect();

    compute_merkle_root_from_leaves(&leaves)
}

/// Computes the merkle root from pre-computed leaves.
fn compute_merkle_root_from_leaves(leaves: &[FixedBytes<32>]) -> FixedBytes<32> {
    if leaves.is_empty() {
        return FixedBytes::ZERO;
    }

    if leaves.len() == 1 {
        return leaves[0];
    }

    // Pad to power of 2 if necessary
    let mut current_level = leaves.to_vec();
    let next_power_of_two = current_level.len().next_power_of_two();
    current_level.resize(next_power_of_two, FixedBytes::ZERO);

    // Build tree bottom-up
    while current_level.len() > 1 {
        let mut next_level = Vec::with_capacity(current_level.len() / 2);

        for chunk in current_level.chunks(2) {
            let left = chunk[0];
            let right = chunk.get(1).copied().unwrap_or(FixedBytes::ZERO);
            next_level.push(hash_pair(left, right));
        }

        current_level = next_level;
    }

    current_level[0]
}

/// Hashes two sibling nodes to produce their parent hash.
///
/// Uses positional hashing to match Solidity's merkleizeKeccak:
/// `keccak256(abi.encodePacked(left, right))`
///
/// This matches the EigenLayer Merkle library which uses positional (not sorted)
/// pair hashing for tree construction and proof verification.
fn hash_pair(left: FixedBytes<32>, right: FixedBytes<32>) -> FixedBytes<32> {
    let mut combined = [0u8; 64];
    combined[..32].copy_from_slice(left.as_slice());
    combined[32..].copy_from_slice(right.as_slice());

    keccak256(combined)
}

/// Generates a merkle proof for an operator at the given index.
///
/// Returns `None` if the index is out of bounds.
pub fn generate_merkle_proof(operators: &[OperatorInfo], operator_index: usize) -> Option<MerkleProof> {
    if operator_index >= operators.len() {
        return None;
    }

    let leaves: Vec<FixedBytes<32>> = operators.iter().map(compute_operator_info_leaf).collect();

    let target_leaf = *leaves.get(operator_index)?;

    let proof = generate_proof_from_leaves(&leaves, operator_index);

    Some(MerkleProof {
        proof,
        index: operator_index,
        leaf: target_leaf,
    })
}

/// Generates a merkle proof for a leaf at the given index.
fn generate_proof_from_leaves(leaves: &[FixedBytes<32>], index: usize) -> Vec<FixedBytes<32>> {
    if leaves.len() <= 1 {
        return vec![];
    }

    // Pad to power of 2
    let mut current_level = leaves.to_vec();
    let next_power_of_two = current_level.len().next_power_of_two();
    current_level.resize(next_power_of_two, FixedBytes::ZERO);

    let mut proof = Vec::new();
    let mut current_index = index;

    while current_level.len() > 1 {
        // Get sibling index
        let sibling_index = if current_index.is_multiple_of(2) {
            current_index + 1
        } else {
            current_index - 1
        };

        // Add sibling to proof
        if sibling_index < current_level.len() {
            proof.push(current_level[sibling_index]);
        } else {
            proof.push(FixedBytes::ZERO);
        }

        // Compute next level
        let mut next_level = Vec::with_capacity(current_level.len() / 2);
        for chunk in current_level.chunks(2) {
            let left = chunk[0];
            let right = chunk.get(1).copied().unwrap_or(FixedBytes::ZERO);
            next_level.push(hash_pair(left, right));
        }

        current_level = next_level;
        current_index /= 2;
    }

    proof
}

/// Verifies a merkle proof against a root.
///
/// This matches the Solidity `Merkle.verifyInclusionKeccak` which uses positional hashing:
/// - If index is even, computed hash is on the left
/// - If index is odd, computed hash is on the right
pub fn verify_merkle_proof(root: FixedBytes<32>, proof: &MerkleProof) -> bool {
    let mut computed_hash = proof.leaf;
    let mut index = proof.index;

    for sibling in &proof.proof {
        computed_hash = if index.is_multiple_of(2) {
            // index is even: computed hash is left sibling
            hash_pair(computed_hash, *sibling)
        } else {
            // index is odd: computed hash is right sibling
            hash_pair(*sibling, computed_hash)
        };
        index /= 2;
    }

    computed_hash == root
}

#[cfg(test)]
mod tests {
    use std::slice;

    use super::*;

    /// Verify that our manual ABI encoding matches alloy's abi_encode for BN254OperatorInfo.
    ///
    /// abi.encode for a dynamic struct (containing uint256[]) wraps with a 32-byte outer offset.
    #[test]
    fn test_encoding_matches_alloy_abi_encode() {
        use crate::bn254_table_calculator::{IOperatorTableCalculatorTypes::BN254OperatorInfo, BN254::G1Point};
        use alloy::sol_types::SolValue;

        let op = OperatorInfo::new(U256::from(0x1234), U256::from(0x5678), vec![U256::from(1000)]);

        // Our manual encoding (what compute_operator_info_leaf uses, minus the salt byte)
        let mut manual_encoded = Vec::new();
        // Outer offset (32 bytes, value = 32) — ABI wraps dynamic struct
        manual_encoded.extend_from_slice(&U256::from(32).to_be_bytes::<32>());
        manual_encoded.extend_from_slice(&op.pubkey_x.to_be_bytes::<32>());
        manual_encoded.extend_from_slice(&op.pubkey_y.to_be_bytes::<32>());
        manual_encoded.extend_from_slice(&U256::from(96).to_be_bytes::<32>());
        manual_encoded.extend_from_slice(&U256::from(op.weights.len()).to_be_bytes::<32>());
        for w in &op.weights {
            manual_encoded.extend_from_slice(&w.to_be_bytes::<32>());
        }

        // Alloy's abi_encode (matches Solidity's abi.encode(operatorInfo))
        let contract_op = BN254OperatorInfo {
            pubkey: G1Point {
                X: U256::from(0x1234),
                Y: U256::from(0x5678),
            },
            weights: vec![U256::from(1000)],
        };
        let alloy_encoded = contract_op.abi_encode();

        assert_eq!(
            alloy_encoded,
            manual_encoded,
            "Manual encoding doesn't match alloy's abi_encode (alloy={}, manual={})",
            alloy_encoded.len(),
            manual_encoded.len()
        );
    }

    #[test]
    fn test_empty_operators_returns_zero_root() {
        let root = compute_operator_info_tree_root(&[]);
        assert_eq!(root, FixedBytes::ZERO);
    }

    #[test]
    fn test_single_operator_leaf_is_root() {
        let operator = OperatorInfo::new(
            U256::from(123),
            U256::from(456),
            vec![U256::from(1_000_000_000_000_000_000u128)],
        );

        let root = compute_operator_info_tree_root(slice::from_ref(&operator));
        let leaf = compute_operator_info_leaf(&operator);

        assert_eq!(root, leaf);
    }

    #[test]
    fn test_deterministic_root_computation() {
        let operators = vec![
            OperatorInfo::new(U256::from(1), U256::from(2), vec![U256::from(100)]),
            OperatorInfo::new(U256::from(3), U256::from(4), vec![U256::from(200)]),
        ];

        let root1 = compute_operator_info_tree_root(&operators);
        let root2 = compute_operator_info_tree_root(&operators);

        assert_eq!(root1, root2);
    }

    #[test]
    fn test_different_order_different_root() {
        let op1 = OperatorInfo::new(U256::from(1), U256::from(2), vec![U256::from(100)]);
        let op2 = OperatorInfo::new(U256::from(3), U256::from(4), vec![U256::from(200)]);

        let root1 = compute_operator_info_tree_root(&[op1.clone(), op2.clone()]);
        let root2 = compute_operator_info_tree_root(&[op2, op1]);

        // Roots should differ because order matters. This distinction matches onchain behavior
        assert_ne!(root1, root2);
    }

    #[test]
    fn test_merkle_proof_generation_and_verification() {
        let operators = vec![
            OperatorInfo::new(U256::from(1), U256::from(2), vec![U256::from(100)]),
            OperatorInfo::new(U256::from(3), U256::from(4), vec![U256::from(200)]),
            OperatorInfo::new(U256::from(5), U256::from(6), vec![U256::from(300)]),
        ];

        let root = compute_operator_info_tree_root(&operators);

        // Generate and verify proof for each operator
        for i in 0..operators.len() {
            let proof = generate_merkle_proof(&operators, i).unwrap();
            assert!(
                verify_merkle_proof(root, &proof),
                "Proof verification failed for operator {}",
                i
            );
        }
    }

    #[test]
    fn test_invalid_proof_fails_verification() {
        let operators = vec![
            OperatorInfo::new(U256::from(1), U256::from(2), vec![U256::from(100)]),
            OperatorInfo::new(U256::from(3), U256::from(4), vec![U256::from(200)]),
        ];

        let root = compute_operator_info_tree_root(&operators);
        let mut proof = generate_merkle_proof(&operators, 0).unwrap();

        // Tamper with the proof
        proof.leaf = FixedBytes::ZERO;

        assert!(!verify_merkle_proof(root, &proof));
    }

    #[test]
    fn test_out_of_bounds_index_returns_none() {
        let operators = vec![OperatorInfo::new(U256::from(1), U256::from(2), vec![U256::from(100)])];

        let proof = generate_merkle_proof(&operators, 5);
        assert!(proof.is_none());
    }

    #[test]
    fn test_leaf_computation_matches_solidity_encoding() {
        // Test that leaf computation matches Solidity:
        // keccak256(abi.encodePacked(OPERATOR_INFO_LEAF_SALT, abi.encode(operatorInfo)))
        let operator = OperatorInfo::new(U256::from(0x1234), U256::from(0x5678), vec![U256::from(1000)]);

        let leaf = compute_operator_info_leaf(&operator);

        // Manually compute expected hash matching Solidity encoding
        let mut expected_encoded = Vec::new();
        // Salt (single byte from abi.encodePacked)
        expected_encoded.push(OPERATOR_INFO_LEAF_SALT);
        // abi.encode(BN254OperatorInfo):
        // - outer offset (32 bytes, value = 32) — ABI wraps dynamic struct with offset
        expected_encoded.extend_from_slice(&U256::from(32).to_be_bytes::<32>());
        // - pubkey.X (32 bytes)
        expected_encoded.extend_from_slice(&U256::from(0x1234).to_be_bytes::<32>());
        // - pubkey.Y (32 bytes)
        expected_encoded.extend_from_slice(&U256::from(0x5678).to_be_bytes::<32>());
        // - offset to weights array (32 bytes, value = 96)
        expected_encoded.extend_from_slice(&U256::from(96).to_be_bytes::<32>());
        // - length of weights array (32 bytes)
        expected_encoded.extend_from_slice(&U256::from(1).to_be_bytes::<32>());
        // - weights[0] (32 bytes)
        expected_encoded.extend_from_slice(&U256::from(1000).to_be_bytes::<32>());

        let expected_leaf = keccak256(&expected_encoded);

        assert_eq!(leaf, expected_leaf);
    }

    #[test]
    fn test_multiple_weights() {
        let operator = OperatorInfo::new(
            U256::from(1),
            U256::from(2),
            vec![U256::from(100), U256::from(200), U256::from(300)],
        );

        let leaf = compute_operator_info_leaf(&operator);
        assert_ne!(leaf, FixedBytes::ZERO);

        // Verify different weights produce different leaf
        let operator2 = OperatorInfo::new(
            U256::from(1),
            U256::from(2),
            vec![U256::from(100), U256::from(200), U256::from(400)],
        );

        let leaf2 = compute_operator_info_leaf(&operator2);
        assert_ne!(leaf, leaf2);
    }

    #[test]
    fn test_power_of_two_padding() {
        // Test with 3 operators (not a power of 2)
        let operators = vec![
            OperatorInfo::new(U256::from(1), U256::from(2), vec![U256::from(100)]),
            OperatorInfo::new(U256::from(3), U256::from(4), vec![U256::from(200)]),
            OperatorInfo::new(U256::from(5), U256::from(6), vec![U256::from(300)]),
        ];

        let root = compute_operator_info_tree_root(&operators);
        assert_ne!(root, FixedBytes::ZERO);

        // All proofs should still verify
        for i in 0..operators.len() {
            let proof = generate_merkle_proof(&operators, i).unwrap();
            assert!(verify_merkle_proof(root, &proof));
        }
    }

    #[test]
    fn test_operator_index_uses_iteration_order() {
        let op0 = OperatorInfo::new(
            U256::from_be_slice(&[0xff; 32]),
            U256::from_be_slice(&[0xff; 32]),
            vec![U256::from(20)],
        );
        let op1 = OperatorInfo::new(
            U256::from_be_slice(&[0x00; 32]),
            U256::from_be_slice(&[0x01; 32]),
            vec![U256::from(40)],
        );

        let operators = vec![op0, op1];
        let root = compute_operator_info_tree_root(&operators);

        // verify proofs for each operator at its iteration index
        for i in 0..operators.len() {
            let proof = generate_merkle_proof(&operators, i).unwrap();
            assert!(verify_merkle_proof(root, &proof));
        }
    }
}