Paper 2026/662

Verifiable Divide-and-Conquer

Rafael Pass, Cornell University, Technion – Israel Institute of Technology

Abstract

Succinct non-interactive arguments (SNARGs) for P are a powerful tool for verifiably outsourcing a computation to a single entity. In this work, we study verifiable outsourcing in a distributed divide-and-conquer setting: a party tasked with solving a large computational problem divides it into smaller subproblems, delegates each subproblem to a different party, and then combines their solutions. Moreover, each party may recursively apply the same strategy, further delegating its computation. Verifying such recursive outsourcing requires SNARGs that are \emph{mergeable}, so that proofs for subproblems can be efficiently combined into a single proof for the original problem. While mergeable proofs have been known for nearly two decades (either based on heuristic assumptions such at SNARKs or, more recently, on standard hardness assumptions), in all existing approaches security degrades exponentially with the number of recursive merges. In this work, we overcome this barrier. Assuming the Learning with Errors (LWE) assumption, we construct a mergeable SNARG for P that supports an unbounded polynomial number of recursive merges. The proof size grows only linearly with the depth of the merge tree, and is independent of its total size.