Paper 2026/266

UltraFold: Efficient Distributed BaseFold from Packed Interleaved Merkle Trees

Abstract

Transparent, code-based polynomial commitment schemes (PCSs) such as BaseFold (CRYPTO’24) are a compelling building block for large-scale zero-knowledge proofs (ZKPs): they avoid trusted setup, rely on standard hash assumptions, offer post-quantum security, and achieve high performance. As ZKP workloads grow, the polynomials that PCSs must commit to and open increasingly exceed the memory and throughput of a single machine, motivating a scalable distributed version of BaseFold. However, existing distribution attempts either only support polynomials of specific structures, or their proof size grows with the number of workers, or they do not scale to arbitrarily many workers. In this paper, we present UltraFold, the first distributed BaseFold PCS that works with general polynomials, scales to any number of workers, and maintains succinct proofs whose size does not depend on the worker count. To enable efficient distributed commitment and opening, UltraFold introduces an interleaved Merkle leaf layout that is realized via a single all-to-all exchange of partially encoded values, and each worker’s computation becomes local after this exchange. To mitigate hashing overhead, UltraFold further uses packed Merkle trees, reducing both prover time in practice and the resulting proof size. We implement UltraFold and evaluate it in a distributed setting: using 256 single-core workers, we commit to and open a 134M-coefficient polynomial in under 2 seconds, with a proof size of 216 KB.