ALITHEIA: Towards practical verifiable graph processing

We consider a scenario in which a data owner outsources storage of a large graph to an untrusted server; the server performs compu-tations 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. Existing work on verifiable computation (VC) would compile each graph computation to a circuit or a RAM pro-gram and then use generic techniques to produce a cryptographic proof of correctness for the result. Such an approach will incur large overhead, especially in the proof-computation time. In this work we address the above by designing, building, and evaluating ALITHEIA, a nearly practical VC system tailored for graph queries such as computing shortest paths, longest paths, and maximum flow. The underlying principle of ALITHEIA is to min-imize the use of generic VC systems by leveraging various algo-rithmic techniques specific for graphs. This leads to both theoret-ical and practical improvements. Asymptotically, it improves the complexity of proof computation by at least a logarithmic factor. On the practical side, we show that ALITHEIA achieves signifi-cant performance improvements over current state-of-the-art (up to a 108 × improvement in proof-computation time, and a 99.9 % re-duction in server storage), while scaling to 200,000-node graphs