Recent work on distributed, in-network aggregation assumes
a benign population of participants. Unfortunately,
modern distributed systems are plagued by malicious participants.
In this paper we present a first step towards
verifiable yet efficient distributed, in-network aggregation
in adversarial settings. We describe a general framework
and threat model for the problem and then present proof
sketches, a compact verification mechanism that combines
cryptographic signatures and Flajolet-Martin sketches to
guarantee acceptable aggregation error bounds with high
probability. We derive proof sketches for count aggregates
and extend them for random sampling, which can be used to
provide verifiable approximations for a broad class of dataanalysis
queries, e.g., quantiles and heavy hitters. Finally,
we evaluate 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.
(EN)
