CCBus

# Properties of cryptographic hash functions
properties = {
    "deterministic": "Same input → Same output",
    "quick_computation": "Fast to compute",
    "preimage_resistance": "Can't find input from output",
    "collision_resistance": "Hard to find two inputs with same output",
    "avalanche_effect": "Small input change → Large output change",
    "fixed_size": "Output has constant size regardless of input"
}

# Pseudo-code for Merkle Tree construction
def construct_merkle_tree(data_blocks):
    # 1. Create leaf nodes
    leaves = [hash(block) for block in data_blocks]
    
    # 2. Handle odd number of leaves (duplicate last)
    if len(leaves) % 2 == 1:
        leaves.append(leaves[-1])
    
    # 3. Build tree bottom-up
    tree = [leaves]
    
    while len(tree[-1]) > 1:
        current_level = tree[-1]
        next_level = []
        
        for i in range(0, len(current_level), 2):
            left = current_level[i]
            right = current_level[i + 1] if i + 1 < len(current_level) else left
            parent_hash = hash(left + right)
            next_level.append(parent_hash)
        
        tree.append(next_level)
    
    return tree  # tree[-1][0] is root hash

from hashlib import sha256, sha3_256, blake2b
import mmh3  # murmurhash3

class HashFunctionBenchmark:
    """Comparison of hash functions for Merkle Trees"""
    
    FUNCTIONS = {
        'SHA-256': {
            'security': 'High (128-bit collision resistance)',
            'speed': 'Moderate',
            'output_size': 32,
            'use_case': 'Bitcoin, Blockchain'
        },
        'SHA3-256': {
            'security': 'High (sponge construction)',
            'speed': 'Slower than SHA-256',
            'output_size': 32,
            'use_case': 'Ethereum 2.0, Modern protocols'
        },
        'BLAKE2b': {
            'security': 'High (faster than SHA-3)',
            'speed': 'Very Fast',
            'output_size': 'Variable (1-64 bytes)',
            'use_case': 'Zcash, Argon2 password hashing'
        },
        'BLAKE3': {
            'security': 'High',
            'speed': 'Extremely Fast (parallel)',
            'output_size': 'Variable',
            'use_case': 'Modern applications, high throughput'
        },
        'MurmurHash3': {
            'security': 'Non-cryptographic',
            'speed': 'Very Fast',
            'output_size': 32,
            'use_case': 'Bloom filters, non-security contexts'
        }
    }

# Merkle Proof Operations Diagram
"""
Merkle Proof for Data Block 2 ("Bob"):

Data to prove: "Bob"
Leaf hash: H("Bob") = H₄

Required proof hashes: [H₃, H₂]
Verification path: [("right", H₃), ("left", H₂)]

Verification steps:
1. Start with H("Bob") = H₄
2. Compute H(H₃ + H₄) = H₁
3. Compute H(H₁ + H₂) = H₀ (root hash)
4. Compare H₀ with trusted root hash
"""

class MerkleBatchOperations:
    """Efficient batch operations for Merkle Trees"""
    
    @staticmethod
    def batch_verify(proofs, root_hash):
        """Verify multiple proofs efficiently"""
        # Can use multi-proof aggregation
        # or probabilistic verification
        
    @staticmethod
    def generate_multi_proof(leaves_indices, tree):
        """Generate a single proof for multiple leaves"""
        # More efficient than individual proofs
        # Size: O(k + log(n/k)) where k = #leaves
        
    @staticmethod
    def update_multiple_leaves(updates, tree):
        """Update multiple leaves with minimal recalculations"""
        # Identify minimal subtree covering all updates
        # Recalculate only affected nodes

# Comparison of Merkle Tree implementations in blockchains
blockchain_implementations = {
    "Bitcoin": {
        "tree_type": "Merkle Tree (Standard)",
        "hash_function": "SHA256 double-hash",
        "features": "Simple Payment Verification (SPV)",
        "optimization": "Merkle branches for light clients"
    },
    "Ethereum": {
        "tree_type": "Merkle Patricia Trie",
        "hash_function": "Keccak-256 (SHA-3)",
        "features": "State trie, Transaction trie, Receipt trie",
        "optimization": "Hexary tree with node compression"
    },
    "IPFS": {
        "tree_type": "Merkle DAG (Directed Acyclic Graph)",
        "hash_function": "SHA-256",
        "features": "Content-addressed storage",
        "optimization": "Chunking large files"
    },
    "Cassandra": {
        "tree_type": "Merkle Tree for anti-entropy",
        "hash_function": "MD5 (in older versions)",
        "features": "Data consistency across nodes",
        "optimization": "Per-range Merkle trees"
    }
}

# Bitcoin's Merkle Tree Implementation
class BitcoinMerkleTree:
    """Simplified Bitcoin Merkle Tree implementation"""
    
    def __init__(self):
        self.double_hash = True  # Bitcoin uses double SHA-256
        
    def calculate_merkle_root(self, transaction_hashes):
        """Calculate Bitcoin-style Merkle root"""
        if not transaction_hashes:
            return None
            
        level = transaction_hashes
        
        while len(level) > 1:
            next_level = []
            
            for i in range(0, len(level), 2):
                left = level[i]
                right = level[i + 1] if i + 1 < len(level) else left
                
                # Bitcoin double hash
                combined = left + right
                if self.double_hash:
                    parent = sha256(sha256(combined).digest()).digest()
                else:
                    parent = sha256(combined).digest()
                    
                next_level.append(parent)
            
            level = next_level
        
        return level[0]

class DistributedFileSystem:
    """Merkle Tree for distributed file storage"""
    
    def __init__(self, chunk_size=1024*1024):  # 1MB chunks
        self.chunk_size = chunk_size
        
    def create_file_merkle_tree(self, file_path):
        """Create Merkle Tree for a large file"""
        import os
        
        file_size = os.path.getsize(file_path)
        chunks = []
        chunk_hashes = []
        
        with open(file_path, 'rb') as f:
            chunk_index = 0
            while True:
                chunk = f.read(self.chunk_size)
                if not chunk:
                    break
                
                # Store or distribute chunk
                chunks.append({
                    'index': chunk_index,
                    'size': len(chunk),
                    'data': chunk  # In practice, store reference
                })
                
                # Calculate hash for Merkle Tree
                chunk_hash = blake3(chunk).digest()
                chunk_hashes.append(chunk_hash)
                chunk_index += 1
        
        # Build Merkle Tree from chunk hashes
        merkle_tree = MerkleTree(chunk_hashes)
        
        return {
            'file_hash': merkle_tree.root,
            'total_chunks': len(chunks),
            'chunk_size': self.chunk_size,
            'merkle_tree': merkle_tree,
            'chunks': chunks  # Metadata only
        }

from typing import List, Optional, Tuple, Dict, Any
from dataclasses import dataclass
from hashlib import sha256
import json
from functools import lru_cache

@dataclass
class MerkleNode:
    """Represents a node in the Merkle Tree"""
    hash: bytes
    left: Optional['MerkleNode'] = None
    right: Optional['MerkleNode'] = None
    is_leaf: bool = False
    data: Optional[Any] = None
    
    def to_dict(self) -> Dict:
        """Serialize node to dictionary"""
        return {
            'hash': self.hash.hex(),
            'is_leaf': self.is_leaf,
            'left': self.left.hash.hex() if self.left else None,
            'right': self.right.hash.hex() if self.right else None
        }

class MerkleTree:
    """Modern Merkle Tree implementation with async support"""
    
    def __init__(self, 
                 data: List[bytes],
                 hash_func: callable = None,
                 double_hash: bool = False):
        """
        Initialize Merkle Tree
        
        Args:
            data: List of data blocks (bytes)
            hash_func: Custom hash function (default: SHA-256)
            double_hash: Whether to apply hash twice (Bitcoin style)
        """
        if not data:
            raise ValueError("Data cannot be empty")
            
        self.hash_func = hash_func or (lambda x: sha256(x).digest())
        self.double_hash = double_hash
        self.leaves = []
        self.root = None
        self.nodes = []
        
        self._build_tree(data)
    
    def _hash(self, data: bytes) -> bytes:
        """Apply hash function with optional double hashing"""
        if self.double_hash:
            return self.hash_func(self.hash_func(data))
        return self.hash_func(data)
    
    def _build_tree(self, data: List[bytes]) -> None:
        """Build Merkle Tree from data"""
        # Create leaf nodes
        self.leaves = [
            MerkleNode(
                hash=self._hash(item),
                is_leaf=True,
                data=item
            )
            for item in data
        ]
        
        # Build tree levels
        current_level = self.leaves.copy()
        self.nodes.extend(current_level)
        
        while len(current_level) > 1:
            next_level = []
            
            for i in range(0, len(current_level), 2):
                left = current_level[i]
                right = current_level[i + 1] if i + 1 < len(current_level) else left
                
                # Concatenate and hash
                combined = left.hash + right.hash
                parent_hash = self._hash(combined)
                
                parent_node = MerkleNode(
                    hash=parent_hash,
                    left=left,
                    right=right
                )
                
                next_level.append(parent_node)
                self.nodes.append(parent_node)
            
            current_level = next_level
        
        self.root = current_level[0] if current_level else None
    
    def get_proof(self, index: int) -> List[Tuple[bytes, str]]:
        """
        Generate Merkle proof for leaf at given index
        
        Returns:
            List of (hash, position) tuples where position is 'left' or 'right'
        """
        if index < 0 or index >= len(self.leaves):
            raise IndexError("Leaf index out of range")
        
        proof = []
        current_node = self.leaves[index]
        
        # Traverse up to root
        while current_node != self.root:
            parent = self._find_parent(current_node)
            if not parent:
                break
            
            # Determine if current is left or right child
            if parent.left == current_node:
                sibling = parent.right
                position = 'right'  # Sibling is on the right
            else:
                sibling = parent.left
                position = 'left'   # Sibling is on the left
            
            proof.append((sibling.hash, position))
            current_node = parent
        
        return proof
    
    def _find_parent(self, node: MerkleNode) -> Optional[MerkleNode]:
        """Find parent of a given node"""
        for n in self.nodes:
            if n.left == node or n.right == node:
                return n
        return None
    
    @staticmethod
    def verify_proof(leaf_hash: bytes, 
                    proof: List[Tuple[bytes, str]], 
                    root_hash: bytes,
                    hash_func: callable) -> bool:
        """
        Verify Merkle proof
        
        Args:
            leaf_hash: Hash of the leaf to verify
            proof: List of (hash, position) tuples
            root_hash: Expected root hash
            hash_func: Hash function used in tree construction
            
        Returns:
            bool: True if proof is valid
        """
        current_hash = leaf_hash
        
        for sibling_hash, position in proof:
            if position == 'left':
                # Sibling is on left, current on right
                combined = sibling_hash + current_hash
            else:
                # Sibling is on right, current on left
                combined = current_hash + sibling_hash
            
            current_hash = hash_func(combined)
        
        return current_hash == root_hash
    
    def update_leaf(self, index: int, new_data: bytes) -> None:
        """Update a leaf and recalculate affected nodes"""
        if index < 0 or index >= len(self.leaves):
            raise IndexError("Leaf index out of range")
        
        # Update leaf
        leaf = self.leaves[index]
        leaf.hash = self._hash(new_data)
        leaf.data = new_data
        
        # Recalculate path to root
        current = leaf
        while current != self.root:
            parent = self._find_parent(current)
            if not parent:
                break
            
            # Recalculate parent hash
            left_hash = parent.left.hash
            right_hash = parent.right.hash if parent.right else left_hash
            parent.hash = self._hash(left_hash + right_hash)
            
            current = parent
    
    def to_json(self) -> str:
        """Serialize tree to JSON"""
        tree_data = {
            'root_hash': self.root.hash.hex() if self.root else None,
            'leaf_count': len(self.leaves),
            'nodes': [node.to_dict() for node in self.nodes]
        }
        return json.dumps(tree_data, indent=2)
    
    @classmethod
    def from_json(cls, json_str: str, hash_func: callable = None) -> 'MerkleTree':
        """Reconstruct tree from JSON (partial reconstruction)"""
        data = json.loads(json_str)
        # Note: This only reconstructs structure, not data
        # Full reconstruction requires original data
        raise NotImplementedError(
            "Full reconstruction requires original data blocks. "
            "Consider storing data separately."
        )
    
    def __str__(self) -> str:
        """String representation of the tree"""
        return f"MerkleTree(root={self.root.hash.hex()[:16]}..., leaves={len(self.leaves)})"

import asyncio
from concurrent.futures import ThreadPoolExecutor
from typing import List, Optional
import aiofiles
from blake3 import blake3

class AsyncMerkleTree:
    """Asynchronous Merkle Tree for high-throughput applications"""
    
    def __init__(self, max_workers: int = 4):
        self.executor = ThreadPoolExecutor(max_workers=max_workers)
        self.hash_func = blake3  # Using BLAKE3 for speed
        
    async def hash_data(self, data: bytes) -> bytes:
        """Compute hash asynchronously"""
        loop = asyncio.get_event_loop()
        return await loop.run_in_executor(
            self.executor,
            lambda: self.hash_func(data).digest()
        )
    
    async def build_tree_async(self, data_chunks: List[bytes]) -> bytes:
        """Build Merkle Tree asynchronously"""
        # Hash all leaves in parallel
        leaf_hashes = await asyncio.gather(
            *[self.hash_data(chunk) for chunk in data_chunks]
        )
        
        # Build tree levels
        current_level = leaf_hashes
        
        while len(current_level) > 1:
            next_level = []
            tasks = []
            
            for i in range(0, len(current_level), 2):
                left = current_level[i]
                right = current_level[i + 1] if i + 1 < len(current_level) else left
                
                # Create async task for each parent hash
                task = self.hash_data(left + right)
                tasks.append(task)
            
            # Compute all parent hashes in parallel
            next_level = await asyncio.gather(*tasks)
            current_level = next_level
        
        return current_level[0] if current_level else None
    
    async def create_from_large_file(self, file_path: str, 
                                    chunk_size: int = 1024*1024) -> Dict:
        """Create Merkle Tree from large file asynchronously"""
        chunk_hashes = []
        chunk_index = 0
        
        async with aiofiles.open(file_path, 'rb') as f:
            while True:
                chunk = await f.read(chunk_size)
                if not chunk:
                    break
                
                chunk_hash = await self.hash_data(chunk)
                chunk_hashes.append((chunk_index, chunk_hash))
                chunk_index += 1
        
        # Build tree from chunk hashes
        root_hash = await self.build_tree_async([h for _, h in chunk_hashes])
        
        return {
            'file_hash': root_hash.hex(),
            'total_chunks': len(chunk_hashes),
            'chunk_size': chunk_size,
            'chunk_hashes': [(idx, h.hex()) for idx, h in chunk_hashes]
        }

from typing import Set, Dict
from collections import defaultdict

class AdvancedMerkleTree(MerkleTree):
    """Enhanced Merkle Tree with advanced features"""
    
    def generate_multiproof(self, indices: Set[int]) -> Dict:
        """
        Generate a multi-proof for multiple leaves
        
        Args:
            indices: Set of leaf indices to prove
            
        Returns:
            Dictionary containing proof data
        """
        if not indices:
            return {}
        
        # Sort indices for consistent proof generation
        indices = sorted(indices)
        proof_hashes = []
        proof_positions = defaultdict(list)
        
        # Track which nodes are needed for proof
        needed_nodes = set()
        
        # Mark leaves as needed
        for idx in indices:
            needed_nodes.add(id(self.leaves[idx]))
        
        # Mark required internal nodes
        for idx in indices:
            node = self.leaves[idx]
            while node != self.root:
                parent = self._find_parent(node)
                if not parent:
                    break
                
                # Mark sibling as needed if not already marked
                sibling = parent.right if parent.left == node else parent.left
                if sibling and id(sibling) not in needed_nodes:
                    proof_hashes.append(sibling.hash)
                    # Record position relative to node being proven
                    position = 'left' if parent.left == node else 'right'
                    proof_positions[id(node)].append({
                        'sibling_hash': sibling.hash,
                        'position': position
                    })
                    needed_nodes.add(id(sibling))
                
                node = parent
        
        return {
            'proof_hashes': proof_hashes,
            'proof_structure': proof_positions,
            'root_hash': self.root.hash,
            'leaf_indices': indices
        }
    
    @staticmethod
    def verify_multiproof(leaf_hashes: List[Tuple[int, bytes]],
                         multiproof: Dict,
                         root_hash: bytes,
                         hash_func: callable) -> bool:
        """
        Verify multi-proof for multiple leaves
        
        Args:
            leaf_hashes: List of (index, hash) tuples
            multiproof: Multi-proof dictionary
            root_hash: Expected root hash
            hash_func: Hash function used
            
        Returns:
            bool: True if all leaves are verified
        """
        # This is a simplified implementation
        # In practice, you'd reconstruct partial tree
        
        # For now, verify each leaf individually
        for idx, leaf_hash in leaf_hashes:
            # Extract proof for this leaf from multiproof
            # This depends on the multiproof structure
            pass
        
        return True  # Placeholder

class SparseMerkleTree:
    """
    Sparse Merkle Tree for key-value stores
    
    Useful for:
    - Blockchain state trees
    - Database indices
    - Membership proofs
    """
    
    def __init__(self, depth: int = 256):
        self.depth = depth  # Typically 256 for 256-bit keys
        self.default_hash = self._compute_default_hashes(depth)
        self.root = self.default_hash[-1]  # Root is last default hash
        self.leaves = {}  # key: path, value: leaf hash
    
    def _compute_default_hashes(self, depth: int) -> List[bytes]:
        """Precompute default hashes for empty subtrees"""
        default_hashes = [b'\x00' * 32]  # Leaf default
        
        for i in range(depth):
            parent = sha256(default_hashes[-1] + default_hashes[-1]).digest()
            default_hashes.append(parent)
        
        return default_hashes
    
    def insert(self, key: bytes, value: bytes) -> None:
        """Insert key-value pair"""
        # Convert key to binary path
        path = ''.join(f'{byte:08b}' for byte in key)[:self.depth]
        
        # Update leaf
        leaf_hash = sha256(value).digest()
        self.leaves[path] = leaf_hash
        
        # Update path to root
        self._update_path(path, leaf_hash)
    
    def _update_path(self, path: str, leaf_hash: bytes) -> None:
        """Update hashes along the path from leaf to root"""
        current_hash = leaf_hash
        
        for i in range(self.depth - 1, -1, -1):
            # Get sibling
            sibling_path = self._get_sibling_path(path, i)
            sibling_hash = self.leaves.get(sibling_path, self.default_hash[i])
            
            # Determine left/right order
            if path[i] == '0':
                # Current is left child
                combined = current_hash + sibling_hash
            else:
                # Current is right child
                combined = sibling_hash + current_hash
            
            current_hash = sha256(combined).digest()
            
            # Update path for parent
            parent_path = path[:i]
            self.leaves[parent_path] = current_hash
    
    def _get_sibling_path(self, path: str, level: int) -> str:
        """Get sibling path at given level"""
        if level >= len(path):
            return path
        
        # Flip the bit at the specified level
        path_list = list(path)
        path_list[level] = '1' if path[level] == '0' else '0'
        return ''.join(path_list)
    
    def get_proof(self, key: bytes) -> List[bytes]:
        """Generate inclusion proof for key"""
        path = ''.join(f'{byte:08b}' for byte in key)[:self.depth]
        proof = []
        
        for i in range(self.depth - 1, -1, -1):
            sibling_path = self._get_sibling_path(path, i)
            sibling_hash = self.leaves.get(sibling_path, self.default_hash[i])
            proof.append(sibling_hash)
        
        return proof

import time
import random
import string
from statistics import mean, median
import matplotlib.pyplot as plt

class MerkleTreeBenchmark:
    """Benchmark different Merkle Tree implementations"""
    
    @staticmethod
    def generate_random_data(num_items: int, item_size: int = 1024) -> List[bytes]:
        """Generate random test data"""
        return [
            ''.join(random.choices(string.ascii_letters + string.digits, k=item_size))
            .encode('utf-8')
            for _ in range(num_items)
        ]
    
    @staticmethod
    def benchmark_construction(data_sizes: List[int]) -> Dict:
        """Benchmark tree construction time"""
        results = {
            'standard': [],
            'async': [],
            'sparse': []
        }
        
        for size in data_sizes:
            data = MerkleTreeBenchmark.generate_random_data(size)
            
            # Standard Merkle Tree
            start = time.time()
            tree = MerkleTree(data)
            results['standard'].append(time.time() - start)
            
            # Async (simulated - run in event loop)
            async_tree = AsyncMerkleTree()
            
            async def run_async():
                return await async_tree.build_tree_async(data)
            
            start = time.time()
            asyncio.run(run_async())
            results['async'].append(time.time() - start)
            
            # Sparse Merkle Tree (different use case, but for comparison)
            sparse_tree = SparseMerkleTree()
            start = time.time()
            for i, item in enumerate(data[:1000]):  # Limit for sparse tree
                sparse_tree.insert(i.to_bytes(32, 'big'), item)
            results['sparse'].append(time.time() - start)
        
        return results
    
    @staticmethod
    def plot_results(results: Dict, data_sizes: List[int]):
        """Plot benchmark results"""
        fig, axes = plt.subplots(2, 2, figsize=(12, 10))
        
        # Construction time
        ax = axes[0, 0]
        for label, times in results.items():
            ax.plot(data_sizes[:len(times)], times, label=label, marker='o')
        ax.set_xlabel('Number of Items')
        ax.set_ylabel('Time (seconds)')
        ax.set_title('Tree Construction Time')
        ax.legend()
        ax.grid(True)
        
        # Proof generation time
        ax = axes[0, 1]
        proof_times = []
        for size in data_sizes[:5]:  # Limit for clarity
            data = MerkleTreeBenchmark.generate_random_data(size)
            tree = MerkleTree(data)
            
            start = time.time()
            for i in range(min(100, size)):  # Generate 100 proofs
                tree.get_proof(i % size)
            proof_times.append(time.time() - start)
        
        ax.plot(data_sizes[:len(proof_times)], proof_times, marker='s', color='red')
        ax.set_xlabel('Number of Items')
        ax.set_ylabel('Time for 100 proofs (seconds)')
        ax.set_title('Proof Generation Time')
        ax.grid(True)
        
        # Proof size vs tree size
        ax = axes[1, 0]
        proof_sizes = []
        for size in data_sizes:
            data = MerkleTreeBenchmark.generate_random_data(size)
            tree = MerkleTree(data)
            proof = tree.get_proof(0)
            proof_sizes.append(len(proof) * 32)  # 32 bytes per hash
        
        ax.plot(data_sizes, proof_sizes, marker='^', color='green')
        ax.set_xlabel('Number of Items')
        ax.set_ylabel('Proof Size (bytes)')
        ax.set_title('Proof Size vs Tree Size')
        ax.grid(True)
        ax.set_yscale('log')
        
        # Memory usage comparison
        ax = axes[1, 1]
        memory_usage = []
        for size in data_sizes[:10]:  # Limit sizes for memory test
            data = MerkleTreeBenchmark.generate_random_data(size, 256)  # Smaller items
            tree = MerkleTree(data)
            
            # Approximate memory: nodes * node_size
            # Each node: hash (32) + pointers (16) + overhead
            approx_memory = len(tree.nodes) * 100  # ~100 bytes per node
            memory_usage.append(approx_memory / 1024)  # Convert to KB
        
        ax.plot(data_sizes[:len(memory_usage)], memory_usage, marker='d', color='purple')
        ax.set_xlabel('Number of Items')
        ax.set_ylabel('Memory Usage (KB)')
        ax.set_title('Approximate Memory Usage')
        ax.grid(True)
        
        plt.tight_layout()
        plt.savefig('merkle_tree_benchmark.png', dpi=300, bbox_inches='tight')
        plt.show()

# Run benchmarks
if __name__ == "__main__":
    benchmark = MerkleTreeBenchmark()
    data_sizes = [10, 100, 1000, 5000, 10000, 50000]
    results = benchmark.benchmark_construction(data_sizes)
    benchmark.plot_results(results, data_sizes)

class MerkleMountainRange:
    """
    Merkle Mountain Range - Append-only Merkle structure
    
    Properties:
    - Efficient append operations
    - No rebalancing needed
    - Perfect for blockchain headers
    """
    
    def __init__(self):
        self.peaks = []  # List of peak hashes
        self.leaves = []  # All leaf hashes
        self.nodes = []   # All node hashes
        
    def append(self, leaf_hash: bytes) -> None:
        """Append new leaf to MMR"""
        self.leaves.append(leaf_hash)
        self.nodes.append(leaf_hash)
        
        # Merge peaks while possible
        node_index = len(self.nodes) - 1
        
        while self._is_left_sibling(node_index):
            left_sibling = self.nodes[node_index - 1]
            parent_hash = sha256(left_sibling + leaf_hash).digest()
            
            # Replace left sibling and current with parent
            self.nodes = self.nodes[:-2] + [parent_hash]
            node_index = len(self.nodes) - 1
            leaf_hash = parent_hash
        
        # Update peaks
        self._update_peaks()
    
    def _is_left_sibling(self, index: int) -> bool:
        """Check if node at index has a left sibling to merge with"""
        if index == 0:
            return False
        
        # Check if we're at a position where two subtrees can merge
        # This depends on the binary representation
        height = self._get_height(index)
        return height == self._get_height(index - 1)
    
    def _get_height(self, index: int) -> int:
        """Get height of node at given position"""
        # Height is number of trailing 1s in (index + 1)
        pos = index + 1
        height = 0
        while pos % 2 == 1:
            height += 1
            pos //= 2
        return height
    
    def _update_peaks(self) -> None:
        """Update list of peak hashes"""
        self.peaks = []
        n = len(self.nodes)
        
        # Find peaks by traversing from right
        while n > 0:
            # Find the largest power of 2 <= n
            peak_size = 1 << (n.bit_length() - 1)
            peak_index = n - 1
            
            # The root of this peak is the last node of this subtree
            self.peaks.append(self.nodes[peak_index])
            n -= peak_size
    
    def get_root(self) -> bytes:
        """Calculate bagged root from peaks"""
        if not self.peaks:
            return b'\x00' * 32
        
        # Bag peaks: hash peaks from right to left
        root = self.peaks[-1]
        for peak in reversed(self.peaks[:-1]):
            root = sha256(peak + root).digest()
        
        return root

from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives import serialization
import hashlib

class VerkleNode:
    """
    Verkle Tree Node using vector commitments
    
    Advantages over Merkle Trees:
    - Smaller proof sizes (O(1) vs O(log n))
    - Faster verification
    - Better for stateless clients
    """
    
    def __init__(self, width: int = 256):
        self.width = width
        self.children = [None] * width
        self.commitment = None
        
    def insert(self, index: int, value: bytes) -> None:
        """Insert value at specific index"""
        if 0 <= index < self.width:
            self.children[index] = value
            self._update_commitment()
    
    def _update_commitment(self) -> None:
        """Update Pedersen commitment for this node"""
        # Simplified version - real implementation uses elliptic curves
        # This is a conceptual implementation
        
        combined = b''.join(
            child if child else b'\x00' * 32 
            for child in self.children
        )
        self.commitment = hashlib.sha256(combined).digest()
    
    def generate_proof(self, indices: List[int]) -> Dict:
        """
        Generate proof for multiple indices
        
        In real Verkle Trees, this uses:
        - KZG polynomial commitments
        - Elliptic curve pairings
        """
        proof = {
            'node_commitment': self.commitment,
            'values': {},
            'sibling_hashes': []
        }
        
        for idx in indices:
            if 0 <= idx < self.width:
                proof['values'][idx] = self.children[idx]
                
                # For other indices, we'd normally provide hashes
                # In KZG, we provide evaluation proofs
        
        return proof

class PostQuantumMerkleTree:
    """
    Merkle Tree with post-quantum cryptographic hash functions
    
    Uses:
    - SHA-3 (already quantum-resistant to some extent)
    - BLAKE3
    - Future: SHAKE, cSHAKE for XOF functionality
    """
    
    def __init__(self, pq_hash_func: str = 'SHA3-512'):
        self.pq_hash_func = pq_hash_func
        
        if pq_hash_func == 'SHA3-512':
            self.hash_func = lambda x: hashlib.sha3_512(x).digest()
        elif pq_hash_func == 'BLAKE2b':
            self.hash_func = lambda x: hashlib.blake2b(x, digest_size=64).digest()
        elif pq_hash_func == 'SHAKE256':
            self.hash_func = lambda x: hashlib.shake_256(x).digest(64)
        else:
            raise ValueError(f"Unsupported hash function: {pq_hash_func}")
    
    def build_tree(self, data: List[bytes]) -> bytes:
        """Build tree with post-quantum hash function"""
        # Similar to standard Merkle Tree but with larger hash outputs
        leaves = [self.hash_func(item) for item in data]
        
        while len(leaves) > 1:
            next_level = []
            
            for i in range(0, len(leaves), 2):
                left = leaves[i]
                right = leaves[i + 1] if i + 1 < len(leaves) else left
                parent = self.hash_func(left + right)
                next_level.append(parent)
            
            leaves = next_level
        
        return leaves[0] if leaves else None

class ResearchMerkleTree:
    """Cutting-edge research topics in Merkle Trees"""
    
    RESEARCH_AREAS = {
        'succinct_arguments': {
            'description': 'Ultra-compact proofs (log log n size)',
            'techniques': ['Bulletproofs', 'Halo', 'SuperSpartan'],
            'applications': 'Light clients, IoT devices'
        },
        'incremental_verification': {
            'description': 'Verify updates without recomputing entire tree',
            'techniques': ['Authenticated data structures', 'CRDTs'],
            'applications': 'Real-time collaboration, live streaming'
        },
        'cross_chain_interop': {
            'description': 'Merkle proofs across different blockchains',
            'techniques': ['Bridge protocols', 'Light client relays'],
            'applications': 'Cross-chain DeFi, asset transfers'
        },
        'storage_optimization': {
            'description': 'Minimize storage while maintaining provability',
            'techniques': ['Erasure coding', 'Data availability proofs'],
            'applications': 'Decentralized storage, archival systems'
        },
        'hardware_acceleration': {
            'description': 'FPGA/ASIC optimized hash computations',
            'techniques': ['Custom hash circuits', 'GPU parallelization'],
            'applications': 'High-frequency trading, real-time analytics'
        }
    }
    
    @staticmethod
    def future_roadmap():
        """Projected timeline for Merkle Tree evolution"""
        return {
            '2024-2025': {
                'focus': 'Verkle Tree adoption in Ethereum',
                'milestones': ['EIP-6800 implementation', 'Stateless client testnets']
            },
            '2026-2027': {
                'focus': 'Quantum-resistant deployments',
                'milestones': ['NIST standardized hashes', 'Hybrid schemes']
            },
            '2028-2030': {
                'focus': 'AI-integrated optimizations',
                'milestones': ['Self-optimizing trees', 'Predictive caching']
            }
        }

from typing import Protocol, runtime_checkable
from abc import ABC, abstractmethod
import pickle
from pathlib import Path

@runtime_checkable
class MerkleProtocol(Protocol):
    """Protocol defining Merkle Tree interface"""
    
    @abstractmethod
    def root(self) -> bytes:
        """Get root hash"""
        pass
    
    @abstractmethod
    def insert(self, data: bytes) -> int:
        """Insert data and return index"""
        pass
    
    @abstractmethod
    def get_proof(self, index: int) -> List[bytes]:
        """Get inclusion proof for index"""
        pass
    
    @abstractmethod
    def verify(self, data: bytes, proof: List[bytes]) -> bool:
        """Verify data with proof"""
        pass

class ProductionMerkleSystem:
    """
    Production-ready Merkle Tree system with:
    - Persistence
    - Cache
    - Monitoring
    - Fault tolerance
    """
    
    def __init__(self, 
                 storage_path: Path,
                 cache_size: int = 10000,
                 backup_interval: int = 3600):
        self.storage_path = storage_path
        self.cache = LRUCache(cache_size)
        self.backup_interval = backup_interval
        self.metrics = {
            'inserts': 0,
            'proofs_generated': 0,
            'verifications': 0,
            'cache_hits': 0,
            'cache_misses': 0
        }
        
        # Create storage directory
        storage_path.mkdir(parents=True, exist_ok=True)
        
        # Load existing tree if available
        self.tree = self._load_or_create_tree()
        
        # Start backup scheduler
        self._start_backup_scheduler()
    
    def _load_or_create_tree(self) -> MerkleTree:
        """Load existing tree or create new one"""
        tree_file = self.storage_path / 'tree_state.pkl'
        
        if tree_file.exists():
            try:
                with open(tree_file, 'rb') as f:
                    return pickle.load(f)
            except Exception as e:
                print(f"Failed to load tree: {e}. Creating new tree.")
        
        return MerkleTree([b'initial'])
    
    def _start_backup_scheduler(self):
        """Start periodic backup"""
        import threading
        
        def backup_task():
            while True:
                time.sleep(self.backup_interval)
                self._backup_tree()
        
        thread = threading.Thread(target=backup_task, daemon=True)
        thread.start()
    
    def _backup_tree(self):
        """Backup tree state"""
        backup_file = self.storage_path / f'backup_{int(time.time())}.pkl'
        
        try:
            with open(backup_file, 'wb') as f:
                pickle.dump(self.tree, f)
            
            # Keep only last 10 backups
            backups = sorted(self.storage_path.glob('backup_*.pkl'))
            for old_backup in backups[:-10]:
                old_backup.unlink()
                
        except Exception as e:
            print(f"Backup failed: {e}")
    
    def insert_data(self, data: bytes) -> Dict[str, Any]:
        """Insert data with monitoring and caching"""
        start_time = time.time()
        
        # Insert into tree
        # In our implementation, we need to rebuild or use appendable tree
        # For simplicity, we'll create a new leaf (in practice, use appendable structure)
        
        # Get current state
        current_leaves = self.tree.leaves.copy()
        current_leaves.append(data)
        
        # Rebuild tree (in production, use incremental update)
        new_tree = MerkleTree([leaf.data for leaf in current_leaves if leaf.data])
        
        # Update
        old_root = self.tree.root.hash
        self.tree = new_tree
        new_index = len(current_leaves) - 1
        
        # Cache the proof
        proof = self.tree.get_proof(new_index)
        self.cache[new_index] = {
            'data': data,
            'proof': proof,
            'timestamp': time.time()
        }
        
        # Update metrics
        self.metrics['inserts'] += 1
        
        return {
            'index': new_index,
            'root': self.tree.root.hash.hex(),
            'old_root': old_root.hex(),
            'proof': proof,
            'processing_time': time.time() - start_time
        }
    
    def get_proof_cached(self, index: int) -> Optional[Dict]:
        """Get proof with cache lookup"""
        self.metrics['proofs_generated'] += 1
        
        if index in self.cache:
            self.metrics['cache_hits'] += 1
            return self.cache[index]
        
        self.metrics['cache_misses'] += 1
        
        if 0 <= index < len(self.tree.leaves):
            proof = self.tree.get_proof(index)
            result = {
                'data': self.tree.leaves[index].data,
                'proof': proof,
                'timestamp': time.time()
            }
            self.cache[index] = result
            return result
        
        return None
    
    def get_metrics(self) -> Dict:
        """Get system metrics"""
        return {
            **self.metrics,
            'tree_size': len(self.tree.leaves),
            'cache_size': len(self.cache),
            'storage_path': str(self.storage_path)
        }
    
    def verify_data(self, data: bytes, proof: List[bytes], 
                   expected_root: bytes = None) -> bool:
        """Verify data with proof"""
        self.metrics['verifications'] += 1
        
        if expected_root is None:
            expected_root = self.tree.root.hash
        
        leaf_hash = sha256(data).digest()
        return MerkleTree.verify_proof(
            leaf_hash, 
            [(h, 'right') for h in proof],  # Simplified position
            expected_root,
            sha256
        )

# Usage example
if __name__ == "__main__":
    # Initialize production system
    system = ProductionMerkleSystem(Path('./merkle_storage'))
    
    # Insert some data
    for i in range(100):
        data = f"Transaction {i}: {random.randint(1, 1000)}".encode()
        result = system.insert_data(data)
        print(f"Inserted: {result['index']}, Root: {result['root'][:16]}...")
    
    # Get proof for item 42
    proof_data = system.get_proof_cached(42)
    if proof_data:
        print(f"Data: {proof_data['data'][:50]}...")
        print(f"Proof length: {len(proof_data['proof'])} hashes")
    
    # Verify item
    is_valid = system.verify_data(
        proof_data['data'],
        proof_data['proof']
    )
    print(f"Verification: {'PASS' if is_valid else 'FAIL'}")
    
    # Show metrics
    metrics = system.get_metrics()
    print(f"\nSystem Metrics:")
    for key, value in metrics.items():
        print(f"  {key}: {value}")