The Efficient Server Audit Problem, Deduplicated Re-execution, and the Web
This addresses the problem of ensuring trust in server computations for scenarios like web applications on untrusted providers, representing a novel method for a known bottleneck.
The paper tackles the Efficient Server Audit Problem, which involves verifying that a server's responses were correctly derived from a program given untrusted logs, by proposing a solution based on simultaneous replay and efficient verification of concurrent executions. The implementation for PHP web applications achieves a 5.6–10.9x speedup in verification compared to simple re-execution, with less than 10% server overhead.
You put a program on a concurrent server, but you don't trust the server; later, you get a trace of the actual requests that the server received from its clients and the responses that it delivered. You separately get logs from the server; these are untrusted. How can you use the logs to efficiently _verify_ that the responses were derived from running the program on the requests? This is the _Efficient Server Audit Problem_, and it abstracts real-world scenarios, including running a web application on an untrusted provider. We give a solution based on several new techniques, including simultaneous replay and efficient verification of concurrent executions. We implement the solution for PHP web applications. For several applications, our verifier achieves 5.6--10.9x speedup versus simply re-executing, with less than 10 percent overhead for the server.