Verifiable graph processing

Yupeng Zhang, Charalampos Papamanthou, Jonathan Katz

Research output: Contribution to journalArticlepeer-review


We consider a scenario in which a data owner outsources storage of a large graph to an untrusted server; the server performs computations on this graph in response to queries from a client (whether the data owner or others), and the goal is to ensure verifiability of the returned results. Applying generic verifiable computation (VC) would involve compiling each graph computation to a circuit or a RAM program and would incur large overhead, especially in the proof-computation time. In this work, we address the above by designing, building, and evaluating Alitheia, a VC system tailored for graph queries such as computing shortest paths, longest paths, and maximum flows. The underlying principle of Alitheia is to minimize the use of generic VC techniques by leveraging various algorithmic approaches specific for graphs. This leads to both theoretical and practical improvements. Asymptotically, it improves the complexity of proof computation by at least a logarithmic factor. On the practical side, our system achieves significant performance improvements over current state-of-the-art VC systems (up to a 10-orders-of-magnitude improvement in proof-computation time, and a 99.9% reduction in server storage), while scaling to 200,000-node graphs.

Original languageEnglish (US)
Article number20
JournalACM Transactions on Privacy and Security
Issue number4
StatePublished - Jul 2018
Externally publishedYes


  • Cloud computing
  • Graph processing
  • Verifiable computation

ASJC Scopus subject areas

  • General Computer Science
  • Safety, Risk, Reliability and Quality


Dive into the research topics of 'Verifiable graph processing'. Together they form a unique fingerprint.

Cite this