spectral_vm 0.1.6

/*
 * ═══════════════════════════════════════════════════════════════════════════
 * TECHNICAL MANIFEST: Parallel Merkle Tree
 * SOVEREIGN SPECTRAL ROLE: Commitment Layer
 * ═══════════════════════════════════════════════════════════════════════════
 *
 * COMPLEXITY: O(n) parallel hashing | O(log n) proof generation/verification
 * HASH: SHA-256 (256-bit collision-resistant)
 * DOMAIN: Spectral vector commitment (binding)
 *
 * ARCHITECTURAL INVARIANTS:
 * - Leaf layer: H(value.to_le_bytes())
 * - Internal nodes: H(left || right)
 * - Odd leaves: Self-hashed for balance
 *
 * SECURITY PROPERTIES:
 * - Binding: Adversary cannot open to different value after commit
 * - Succinctness: O(log n) proof size
 * - Parallel: Rayon-accelerated for 64GB+ vectors
 * ═══════════════════════════════════════════════════════════════════════════
 */

use rayon::prelude::*;
use sha2::{Digest, Sha256};

/// Parallel Merkle Tree optimized for Spectral-VM.
pub struct MerkleTree {
    /// Root hash representing the entire spectral commitment.
    pub root: Vec<u8>,
    /// All layers for authentication path generation.
    pub layers: Vec<Vec<Vec<u8>>>,
}

impl MerkleTree {
    /// Commits spectral coefficients within a Merkle Tree.
    /// COMPLEXITY: O(n) parallel, O(log n) depth.
    pub fn commit(data: &[i64]) -> Self {
        // Parallel hashing of the leaf layer (L0)
        let mut current_layer: Vec<Vec<u8>> = data
            .par_iter()
            .map(|&x| {
                let mut hasher = Sha256::new();
                hasher.update(x.to_le_bytes());
                hasher.finalize().to_vec()
            })
            .collect();

        let mut layers = Vec::new();
        layers.push(current_layer.clone());

        // Parallel condensation until root.
        while current_layer.len() > 1 {
            let next_layer: Vec<Vec<u8>> = current_layer
                .par_chunks(2)
                .map(|chunk| {
                    let mut hasher = Sha256::new();
                    hasher.update(&chunk[0]);
                    if chunk.len() > 1 {
                        hasher.update(&chunk[1]);
                    } else {
                        hasher.update(&chunk[0]);
                    }
                    hasher.finalize().to_vec()
                })
                .collect();
            current_layer = next_layer;
            layers.push(current_layer.clone());
        }

        Self {
            root: layers.last().expect("Merkle tree must have at least one layer")[0].clone(),
            layers,
        }
    }

    /// Generates a Merkle Proof (authentication path).
    /// COMPLEXITY: O(log n).
    pub fn prove(&self, mut index: usize) -> Vec<Vec<u8>> {
        let mut proof = Vec::new();
        for i in 0..(self.layers.len() - 1) {
            let layer = &self.layers[i];
            let sibling_idx = if index % 2 == 0 { index + 1 } else { index - 1 };

            if sibling_idx < layer.len() {
                proof.push(layer[sibling_idx].clone());
            } else {
                proof.push(layer[index].clone());
            }
            index /= 2;
        }
        proof
    }

    /// Verifies a Merkle Proof against a root hash.
    /// COMPLEXITY: O(log n).
    pub fn verify(root: &[u8], mut index: usize, leaf_val: i64, proof: &[Vec<u8>]) -> bool {
        let mut hasher = Sha256::new();
        hasher.update(leaf_val.to_le_bytes());
        let mut current_hash = hasher.finalize().to_vec();

        for sibling_hash in proof {
            let mut hasher = Sha256::new();
            if index % 2 == 0 {
                hasher.update(&current_hash);
                hasher.update(sibling_hash);
            } else {
                hasher.update(sibling_hash);
                hasher.update(&current_hash);
            }
            current_hash = hasher.finalize().to_vec();
            index /= 2;
        }

        current_hash == root
    }
}