SP1 Merkle Tree Verification

This repository demonstrates how to implement and verify Merkle tree proofs using SP1 zero-knowledge proofs.

Overview

The project showcases:

1. A guest program that verifies Merkle proofs inside the SP1 zkVM
2. A host program that sets up inputs, generates proofs, and verifies them

Project Structure

sp1-merkle-proof/
├── guest-merkle-verifier/    # Guest program that runs in zkVM
│   ├── Cargo.toml
│   └── src/
│       └── main.rs           # Merkle verification logic
├── host/                     # Host program
│   ├── Cargo.toml
│   └── src/
│       └── main.rs           # Proof generation and verification
└── Cargo.toml                # Workspace configuration

Prerequisites

• Install Rust (https://rustup.rs/)
• Install SP1: curl -sSL https://sp1.succinct.xyz/install | bash
• Add SP1 to your PATH: export PATH="$HOME/.sp1/bin:$PATH"

Build and Run

1. Build the Guest Program

cargo prove build --release -p guest-merkle-verifier

This will compile the guest program and generate the ELF file required by the zkVM.

2. Run the Host Program

cargo run --release -p host

This will:

• Read the guest program ELF
• Set up the example Merkle proof inputs
• Generate a zero-knowledge proof
• Verify the proof

How It Works

Guest Program

The guest program:

1. Reads the Merkle root, leaf, and proof from the host
2. Verifies the proof by recalculating the root hash
3. Commits the result (true/false) back to the host

Host Program

The host program:

1. Sets up inputs (root, leaf, and proof)
2. Passes them to the guest program
3. Generates a zero-knowledge proof that the guest executed correctly
4. Verifies the proof
5. Extracts the result from the public values

Customizing

To use your own Merkle tree:

1. Modify the host program to use your own Merkle root, leaf, and proof
2. The guest program should work with any valid Merkle proof using Keccak-256

Advanced Usage

• For larger Merkle trees, you may need to optimize the guest program
• SP1 provides precompiles for common cryptographic operations that can accelerate proof generation
• For production use, consider using the SP1 Prover Network instead of generating proofs locally

Resources

• SP1 Documentation
• Merkle Tree Implementation Guide