Proof Sketches: Verifiable Multi-Party Aggregation

Recent work on distributed aggregation has assumed a benign population of participants. In modern distributed systems, it is now necessary to account for adversarial behavior. In this paper we consider the problem of ensuring verifiable yet efficient results to typical aggregation queries in a distributed, multi-party setting. We describe a general framework for the problem, including the threat model for adversaries that we consider. We then present a mechanism called a Proof Sketch, which uses a compact combination of cryptographic signatures and Flajolet-Martin sketches to verify that a query answer is within acceptable error bounds with high probability. When verification fails, we provide efficient mechanisms to identify any participants responsible for the perturbed result. We derive Proof Sketches for count aggregates, and extend them to Proof Sketches for verifiable random samples, which, in turn, can be used to provide verifiable approximations for a broad class of data-analysis queries, including quantiles and heavy hitters. In addition to our specific Proof Sketches developed here, we sketch a general framework for developing new Proof Sketches. Finally, we examine the practical use of Proof Sketches, and observe that adversaries can often be reduced to much smaller violations in practice than our worst-case bounds suggest