Merkle Tree Proof Generation and Verification

A Rust implementation of Merkle Trees with complete proof generation and verification capabilities. This library provides both a structured tree-based approach and standalone functions for flexibility in different use cases.

Table of Contents

• Overview
• How It Works
• Architecture
• Usage
• API Reference
• Building and Running

---

Overview

Merkle Trees are a fundamental data structure in cryptography and distributed systems. They allow efficient and secure verification of data integrity without requiring access to the entire dataset. This implementation uses SHA-256 for hashing and supports arbitrary data types.

Key Features

• Tree construction from arbitrary data
• Merkle root calculation
• Proof generation for any leaf node
• Proof verification against a known root
• Both object-oriented and functional approaches

---

How It Works

Finding the Merkle Root

The Merkle root is calculated by recursively hashing pairs of nodes from the leaves up to a single root hash. If the number of nodes at any level is odd, the last node is duplicated.

Generating a Proof

To prove that a specific piece of data exists in the tree, we collect the sibling hashes along the path from the leaf to the root. These sibling hashes, combined with the original data, allow anyone to reconstruct the path and verify the root.

Verifying the Proof

Verification takes the leaf data, the proof (list of sibling hashes), and the expected root. By rehashing along the path using the proof elements, we can confirm whether the reconstructed root matches the expected one.

Sample Output

---

Architecture

Data Structures

MerkleNode: Represents a single node in the tree with a hash value and optional left/right children.

struct MerkleNode {
    hash: String,
    left: Option<Box<MerkleNode>>,
    right: Option<Box<MerkleNode>>,
}

MerkleTree: The main tree structure holding the root node and a vector of leaf hashes for efficient proof generation.

struct MerkleTree {
    root: Option<Box<MerkleNode>>,
    leaves: Vec<String>,
}

Core Functions

Function	Purpose
hash<T>	Computes SHA-256 hash of input data
merkle_root	Calculates root from a vector of hashes
generate_proof	Creates proof for a leaf at a given index
verify_proof	Validates a proof against an expected root

---

Usage

Basic Example

use merkle_verify::MerkleTree;

fn main() {
    let data = vec!["A", "B", "C", "D"];
    
    let mut tree = MerkleTree::new();
    tree.build(data);
    
    // Get the root hash
    let root = tree.find_root();
    println!("Root: {:?}", root);
    
    // Generate proof for leaf "A"
    let proof = tree.find_proof("A".to_string());
    println!("Proof: {:?}", proof);
    
    // Verify the proof
    let is_valid = tree.verify("A".to_string(), proof);
    println!("Valid: {}", is_valid);
}

Using Standalone Functions

For scenarios where you only need specific functionality without maintaining a tree structure:

// Calculate root from pre-hashed leaves
let leaf_hashes: Vec<String> = data.iter().map(|x| hash(x)).collect();
let root = merkle_root(leaf_hashes);

// Generate and verify proof
let proof = generate_proof(hashes.clone(), leaf_index);
let is_valid = verify_proof(root, leaf_data, proof, leaf_index);

---

API Reference

MerkleTree Methods

new() -> Self
Creates an empty Merkle tree.

build<T>(&mut self, data: Vec<T>)
Builds the tree from a vector of data elements. Each element is hashed to form the leaves.

find_root(&self) -> Option<String>
Returns the root hash of the tree, or None if the tree is empty.

find_proof(&self, leaf_data: String) -> Vec<String>
Generates a proof for the specified leaf. Panics if the leaf is not found.

verify(&self, leaf_data: String, proof: Vec<String>) -> bool
Verifies that a leaf is part of the tree using the provided proof.

Standalone Functions

hash<T: AsRef<[u8]>>(data: T) -> String
Returns the SHA-256 hash of the input as a hexadecimal string.

merkle_root(hs: Vec<String>) -> String
Calculates the Merkle root from a vector of hash strings.

generate_proof(hs: Vec<String>, idx: usize) -> Vec<String>
Generates a proof for the leaf at the specified index.

verify_proof(root: String, leaf: String, proof: Vec<String>, idx: usize) -> bool
Verifies a proof against the expected root.

---

Building and Running

Prerequisites

• Rust 1.75 or later
• Cargo

Build

cargo build --release

Run

cargo run

Run Tests

cargo test

---

Dependencies

Crate	Version	Purpose
sha2	0.10.9	SHA-256 hashing

---

License

This project is open source. Feel free to use, modify, and distribute as needed.