State Tree Structure

Shielded State Tree Structure - Technical Specification

This document provides a detailed technical specification of the shielded state tree structure used in the Roru Protocol.

Tree Architecture

Binary Merkle Tree

Tree Type: Binary Merkle tree

Properties:

• Depth: 32 levels

• Capacity: 2^32 leaves (4,294,967,296 notes)

• Hash function: SHA-256

• Leaf nodes: Note commitments

• Internal nodes: Hash of children

Tree Structure:

Level 0 (Root):                    [State Root]
Level 1:                    [Node 0]        [Node 1]
Level 2:              [Node 0]    [Node 1]  [Node 2]    [Node 3]
...
Level 32 (Leaves):   [Note 0] [Note 1] ... [Note 2^32-1]

Node Structure

Leaf Node:

pub struct LeafNode {
    pub commitment: Commitment,  // Pedersen commitment to note
    pub index: u32,             // Position in tree
}

Internal Node:

pub struct InternalNode {
    pub left_hash: Hash,   // Hash of left child
    pub right_hash: Hash,  // Hash of right child
    pub hash: Hash,        // Hash of this node
}

Commitment Structure

Note Commitment

Commitment Format:

pub struct Commitment {
    pub point: Point,  // Point on BLS12-381 curve
}

Commitment Generation:

fn commit_note(note: &Note) -> Commitment {
    let value_point = note.value * G;
    let randomness_point = note.randomness * H;
    let recipient_point = hash_to_point(&note.recipient) * J;
    value_point + randomness_point + recipient_point
}

Commitment Properties:

• Hiding: Commitment doesn't reveal value

• Binding: Cannot change value without changing commitment

• Additive: Can add commitments homomorphically

Tree Operations

Insertion

Insert Process:

1. Find next available leaf position

2. Create leaf node with commitment

3. Update path to root

4. Recalculate hashes

5. Update state root

Insertion Algorithm:

fn insert_commitment(tree: &mut StateTree, commitment: Commitment) -> Result<u32> {
    let index = tree.next_index();
    let mut current = index;
    let mut path = Vec::new();
    
    // Create leaf
    let leaf = LeafNode { commitment, index };
    tree.set_leaf(index, leaf);
    
    // Update path to root
    let mut level = 32;
    while level > 0 {
        let sibling = current ^ 1;
        let sibling_hash = tree.get_node_hash(sibling, level - 1);
        path.push(sibling_hash);
        
        let left = if current % 2 == 0 { current } else { sibling };
        let right = if current % 2 == 0 { sibling } else { current };
        
        let node_hash = hash(left_hash || right_hash);
        tree.set_node(current / 2, level - 1, node_hash);
        
        current = current / 2;
        level -= 1;
    }
    
    Ok(index)
}

Deletion (Nullification)

Nullification Process:

1. Mark note as spent

2. Generate nullifier

3. Add nullifier to nullifier set

4. Note remains in tree (for history)

5. Cannot be used again

Nullification Algorithm:

fn nullify_note(tree: &mut StateTree, note_index: u32, nullifier_key: &Scalar) -> Nullifier {
    let note = tree.get_note(note_index);
    let nullifier = generate_nullifier(&note, nullifier_key);
    tree.nullifier_set.insert(nullifier);
    nullifier
}

Merkle Proofs

Proof Structure

Merkle Proof Format:

pub struct MerkleProof {
    pub leaf: Commitment,
    pub leaf_index: u32,
    pub path: Vec<ProofNode>,
    pub root: Hash,
}

pub struct ProofNode {
    pub hash: Hash,
    pub is_right: bool,  // true if sibling is right child
}

Proof Generation

Generation Algorithm:

fn generate_proof(tree: &StateTree, index: u32) -> MerkleProof {
    let leaf = tree.get_leaf(index);
    let mut path = Vec::new();
    let mut current = index;
    let mut level = 32;
    
    while level > 0 {
        let sibling = current ^ 1;
        let sibling_hash = tree.get_node_hash(sibling, level - 1);
        let is_right = current % 2 == 0;
        
        path.push(ProofNode {
            hash: sibling_hash,
            is_right,
        });
        
        current = current / 2;
        level -= 1;
    }
    
    MerkleProof {
        leaf: leaf.commitment,
        leaf_index: index,
        path,
        root: tree.get_root(),
    }
}

Proof Verification

Verification Algorithm:

fn verify_proof(proof: &MerkleProof) -> bool {
    let mut current_hash = hash_commitment(&proof.leaf);
    let mut current_index = proof.leaf_index;
    
    for node in &proof.path {
        let (left, right) = if node.is_right {
            (current_hash, node.hash)
        } else {
            (node.hash, current_hash)
        };
        
        current_hash = hash(left || right);
        current_index = current_index / 2;
    }
    
    current_hash == proof.root
}

State Root

Root Calculation

Root Properties:

• Commits to entire tree

• Single hash value

• Updated with each transaction

• Verifiable by anyone

Root Format:

pub struct StateRoot {
    pub hash: Hash,
    pub height: u32,
    pub timestamp: u64,
    pub epoch: u64,
}

Root Updates

Update Process:

1. Transaction processed

2. Tree updated

3. New root calculated

4. Root signed

5. Root published

Update Algorithm:

fn update_root(tree: &mut StateTree) -> StateRoot {
    let root_hash = tree.calculate_root();
    let root = StateRoot {
        hash: root_hash,
        height: tree.height(),
        timestamp: current_timestamp(),
        epoch: current_epoch(),
    };
    tree.set_root(root.clone());
    root
}

Incremental Updates

Efficient Updates

Update Strategy:

• Only update changed paths

• Cache intermediate hashes

• Batch updates when possible

• Incremental root calculation

Update Algorithm:

fn incremental_update(tree: &mut StateTree, updates: Vec<Update>) -> StateRoot {
    let mut changed_paths = HashSet::new();
    
    for update in updates {
        let path = get_path_to_root(update.index);
        changed_paths.extend(path);
    }
    
    for path_index in changed_paths {
        recalculate_node_hash(tree, path_index);
    }
    
    update_root(tree)
}

Sparse Tree Representation

Efficient Storage

Sparse Tree:

• Only store non-empty nodes

• Use hash map for nodes

• Efficient memory usage

• Fast lookups

Storage Format:

pub struct SparseTree {
    pub nodes: HashMap<u64, Hash>,  // (index, hash)
    pub leaves: HashMap<u32, Commitment>,  // (index, commitment)
    pub root: Hash,
}

Sparse Tree Operations

Lookup:

fn get_node_hash(tree: &SparseTree, index: u64) -> Hash {
    tree.nodes.get(&index)
        .copied()
        .unwrap_or_else(|| default_hash(index))
}

Update:

fn update_node(tree: &mut SparseTree, index: u64, hash: Hash) {
    tree.nodes.insert(index, hash);
}

Batch Operations

Batch Updates

Batch Processing:

• Process multiple updates together

• Optimize tree traversal

• Reduce hash computations

• Faster overall processing

Batch Algorithm:

fn batch_update(tree: &mut StateTree, updates: Vec<Update>) -> StateRoot {
    // Group updates by path
    let mut path_groups = group_by_path(updates);
    
    // Process each path group
    for (path, group_updates) in path_groups {
        process_path_group(tree, path, group_updates);
    }
    
    update_root(tree)
}

Performance Characteristics

Complexity

Operations:

• Insert: O(log n)

• Proof generation: O(log n)

• Proof verification: O(log n)

• Root update: O(log n)

• Lookup: O(log n)

Space:

• Full tree: O(n)

• Sparse tree: O(k log n) where k is number of notes

• Proof size: O(log n)

Optimization

Optimization Techniques:

• Caching intermediate hashes

• Batch processing

• Parallel computation

• Efficient data structures

Security Properties

Security Guarantees

Tree Security:

• Collision resistance (SHA-256)

• Binding commitments

• Tamper resistance

• Integrity verification

Privacy:

• Commitments hide values

• Proofs don't reveal paths

• No information leakage

• Complete privacy

Conclusion

The state tree provides:

• Efficiency: Logarithmic operations

• Scalability: Supports billions of notes

• Security: Cryptographic guarantees

• Privacy: Hidden state

• Performance: Optimized operations

Understanding the tree structure is essential for protocol development and optimization.