Scaling Semaphore – PIR Merkle-Path Retrieval

Private Information Retrieval lets Semaphore users fetch their Merkle path from a server without revealing which identity they own, enabling truly private proofs for groups with millions of members.

discord

Scaling Semaphore – PIR Merkle-Path Retrieval

Scaling Semaphore – Private Merkle-Path Retrieval with PIR

Project Overview

The project tackles the privacy bottleneck that appears when Semaphore groups grow to millions of members. In large groups, a user must obtain their Merkle-path (all sibling hashes from leaf to root) from a remote database before they can create a zero-knowledge membership proof. Asking for that path naïvely reveals which identity they own.

This project solves the problem by letting users query the server with Private Information Retrieval (PIR). PIR lets a client fetch database records without the server learning which records were requested, preserving full anonymity at Internet scale.

Why PIR matters

Traditional PIR protocols were too heavy for on-chain use. Recent schemes—e.g. Respire and Frodo-PIR—support 2²⁰ elements (≈ 1 million) with sub-second online latency and no trusted setup. By storing Merkle leaves/hashes in PIR-friendly chunks (32 B records) we can keep group trees on a server while users privately retrieve only the ~64 kB they need for a proof.

Technical Approach

Component	Role
Lean Incremental Merkle Tree (LeanIMT)	Append-only tree used by Semaphore; gives deterministic indices so the client knows exactly which nodes to fetch.
PIR Layer (Respire)	Batched, lattice-based PIR with no offline phase; ideal for many small records.
`lean-imt` integration	Rust implementation and benchmarks with Respire

Data flow

Client computes the indices of its Merkle path.
Client sends a PIR query for those indices to the server.
Server responds with encrypted buckets; client decrypts to obtain hashes/leaves.
Client generates the standard Semaphore ZK proof locally; nothing is leaked to the server.