Merkle Trees with Poseidon 2
Merkle trees are at the heart of many integrity and proof systems, including commitments and membership proofs. Building them over large datasets is compute-heavy: each level requires hashing many nodes, and doing that on a CPU can become a bottleneck. This post examines GPU-accelerated Merkle tree generation with the Poseidon 2 hash in cuPQC-Hash, covering two computation modes (Single-Block for high throughput across many trees, and Multi-Block for low latency on large individual trees) and demonstrating speedups up to 169× for large trees on NVIDIA RTX PRO 6000 GPUs.
cuPQC-Hash Library supports Poseidon 2 over two prime fields commonly used in ZK and proof systems: BabyBear and Koala Bear. You can choose the field that matches your proof system or protocol. The benchmarks in this post were run with BabyBear.
Why Poseidon 2 for Merkle Trees
Poseidon 2 is a ZK-friendly hash function designed to be efficient both in native computation and inside zero-knowledge proof circuits. Unlike traditional hash functions (SHA-2, SHA-3) that require thousands of constraints per hash in ZK systems, Poseidon 2 operates over prime fields and uses far fewer constraints, making proofs smaller and faster to generate.
This efficiency matters for validity proofs, batched commitments, and any system where you need to prove correct Merkle tree operations inside a circuit. The GPU acceleration in cuPQC-Hash makes native Poseidon 2 hash fast enough to match its circuit efficiency, eliminating Merkle tree construction as a bottleneck in proof generation pipelines.
Modes and tree configuration
The cuPQC-Hash library provides two execution modes tuned for different workloads:
| Mode | Use case | How it works |
|---|---|---|
| Single‑Block (high throughput) |
Multiple trees | One thread block computes one full Merkle tree. Many blocks run in parallel, so you maximize throughput when building lots of trees (e.g. batch commitments). |
| Multi‑Block (low latency) |
Single tree | Multiple thread blocks work together on a single tree: each builds a subtree, then subtrees are merged. This uses more of the GPU at once and cuts latency for one big tree. |
Both modes support power-of-two leaf counts. For APIs, tree sizes, subtree ranges, and how they map to Single-Block and Multi-Block usage, see Supported Merkle tree configurations in the cuPQC SDK docs. For large trees, Multi-Block builds subtrees in parallel on the GPU, then merges them into one full tree; the same documentation explains how Generate Sub Tree and related calls fit that flow.
Benchmark Configuration
Test setup
Each run builds one large tree on GPU versus CPU (Multi-Block, tuned for low latency on a single tree).
- CPU: AMD EPYC 9124 (32-core); reported CPU times use all 32 cores
- GPU: NVIDIA RTX PRO 6000 Blackwell Generation
- Library: cuPQC-Hash (cuPQC SDK)
- Hash: Poseidon 2-BabyBear
- Tree sizes: leaf-count: 2¹⁶ to 2²⁴ leaves
- Leaf input: 128 field elements per leaf
Benchmark Results
GPU runtime stays low while CPU time grows; speedup increases toward the largest trees.
VS CPU
Merkle Tree Performance
SPEEDUP · TIMES FASTER · GPU RUNTIME · MS
Poseidon 2-BabyBear, Multi-Block · 128 field elements per leaf · leaf count on the x axis.
Analysis
CPU time scales roughly linearly with leaf count; GPU time rises much more slowly, so speedup widens as trees get larger. Multi-Block can use more of the GPU on bigger trees, which helps explain why the gap is largest at the top end, which matters for large state commitments and similar workloads.
At the largest size (2²⁴ leaves), runtime is ~6.6 s on CPU versus ~39 ms on GPU. For proof pipelines, validity systems, or other workloads where Merkle construction was on the critical path, the GPU side of that gap often means tree build stops being what you optimize first.
Use Cases
Validity proofs and large Merkle commitments. STARKs and similar proof systems use Merkle trees over execution traces, polynomial data, or other large witnesses; trees on the order of 2²⁰–2²⁴ leaves often show up in demanding workloads. Pipelines that keep Merkle roots over evolving state need the same native tree work to stay fast. GPU-accelerated construction cuts the hash time that sits ahead of circuit generation and proof steps.
Membership proofs and evolving datasets. Verifiable databases, authenticated data structures, and privacy-preserving designs issue membership (and non-membership) proofs as data changes. When tree updates stay cheap, proof generation and verification stay responsive as the underlying set grows or drifts.
Many independent trees (Single-Block). When you commit to many unrelated datasets in one shot, Single-Block mode assigns one Merkle tree per thread block and runs many blocks in parallel, tuning for aggregate throughput rather than a single huge tree.
Get started
Merkle tree APIs (Generate Tree, Generate Sub Tree, Generate Proof, Verify Proof) and Poseidon 2 hash are part of cuPQC-Hash. Both BabyBear and Koala Bear fields are supported; choose the one that matches your proof system. For Multi-Block usage, tree sizes, and code samples, see the cuPQC-Hash documentation, the Merkle proof application (BabyBear) in the cuPQC repo, and the Poseidon2 operators reference for supported BabyBear and Koala Bear configurations.
For more information about cuPQC SDK and cuPQC-Hash, visit the NVIDIA Developer website.
