**Cluster Computing in Zero Knowledge**

*Alessandro Chiesa and Eran Tromer and Madars Virza*

**Abstract: **Large computations, when amenable to distributed parallel execution, are often executed on computer clusters, for scalability and cost reasons. Such computations are used in many applications, including, to name but a few, machine learning, webgraph mining, and statistical machine translation. Oftentimes, though, the input data is private and only the result of the computation can be published. Zero-knowledge proofs would allow, in such settings, to verify correctness of the output without leaking (additional) information about the input.

In this work, we investigate theoretical and practical aspects of *zero-knowledge proofs for cluster computations*. We design, build, and evaluate zero-knowledge proof systems for which: (i) a proof attests to the correct execution of a cluster computation; and (ii) generating the proof is itself a cluster computation that is similar in structure and complexity to the original one. Concretely, we focus on MapReduce, an elegant and popular form of cluster computing.

Previous zero-knowledge proof systems can in principle prove a MapReduce computation's correctness, via a monolithic NP statement that reasons about all mappers, all reducers, and shuffling. However, it is not clear how to generate the proof for such monolithic statements via parallel execution by a distributed system. Our work demonstrates, by theory and implementation, that proof generation can be similar in structure and complexity to the original cluster computation.

Our main technique is a bootstrapping theorem for succinct non-interactive arguments of knowledge (SNARKs) that shows how, via recursive proof composition and Proof-Carrying Data, it is possible to transform any SNARK into a *distributed SNARK for MapReduce* which proves, piecewise and in a distributed way, the correctness of every step in the original MapReduce computation as well as their global consistency.

**Category / Keywords: **cryptographic protocols / zero knowledge, cluster computing, MapReduce, proof-carrying data, succinct arguments

**Original Publication**** (with major differences): **IACR-EUROCRYPT-2015

**Date: **received 26 Apr 2015, last revised 28 Apr 2015

**Contact author: **alexch at berkeley edu

**Available format(s): **PDF | BibTeX Citation

**Version: **20150428:110109 (All versions of this report)

**Short URL: **ia.cr/2015/377

[ Cryptology ePrint archive ]