2026-09-13T04:32:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24882 2026-09-05T18:59:34Z ddc:004 open_access

Brief Announcement: Incrementally Verifiable Distributed Computation Aldema Tshuva, Eden Oshman, Rotem Incrementally verifiable computation massively parallel computation streaming parallel RAM batch arguments SNARG Incrementally verifiable computation (IVC) is a cryptographic scheme that allows a prover to certify the correctness of a long or ongoing computation in an incremental manner, by repeatedly updating a proof certifying the computation so far. Updating the proof does not require access to the entire trace of the computation, which makes the IVC prover memory efficient. In this work we construct incrementally verifiable distributed computation, which allows a distributed algorithm to efficiently certify its own execution using low memory and communication overhead. Our primary motivation is massively-parallel computation (MPC), where memory efficiency is make-or-break: the machines participating in an MPC algorithm usually cannot store the entire trace of their computation. Thus, certifying MPC algorithms essentially requires distributed IVC. At the heart of this work is a new abstraction, updatable batch arguments for {NP} (UpBARGs), which we define and construct. Standard BARGs allow one to prove a batch of k {NP}-statements using a proof whose length barely grows with k; however, the statements and their witnesses must all be known in advance. In contrast, UpBARGs support adding statements and witnesses on the fly, making them a flexible tool for constructing IVC across different computational models. We use UpBARGs to construct IVC for streaming algorithms, for MPC algorithms, and for PRAM algorithms in the exclusive-read exclusive-write (EREW) model. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eden Aldema Tshuva and Rotem Oshman 2025 Is Part Of LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2025.44 urn:nbn:de:0030-drops-248829 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.44 eng https://creativecommons.org/licenses/by/4.0/legalcode