A Hybrid Architecture for Interactive Verifiable Computation

We consider
interactive, proof-based verifiable computa-
tion
: how can a client machine specify a computation to a server,
receive an answer, and then engage the server in an interactive
protocol that convinces the client that the answer is correct, with
less work for the client than executing the computation in the first
place? Complexity theory and cryptography offer solutions in prin-
ciple, but if implemented naively, they are ludicrously expensive.
Recently, however, several strands of work have refined this the-
ory and implemented the resulting protocols in actual systems. This
work is promising but suffers from one of two problems: either it
relies on expensive cryptography, or else it applies to a restricted
class of computations. Worse, it is not always clear which protocol
will perform better for a given problem.
We describe a system that (a) extends optimized refinements of
the non-cryptographic protocols to a much broader class of compu-
tations, (b) uses static analysis to fail over to the cryptographic ones
when the non-cryptographic ones would be more expensive, and (c)
incorporates this core into a built system that includes a compiler
for a high-level language, a distributed server, and GPU accelera-
tion. Experimental results indicate that our system performs better
and applies more widely than the best in the literature.