Proof Sketches: Verifiable In-Network Aggregation
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 the authors present a first step towards verifiable yet efficient distributed, in-network aggregation in adversarial settings. They 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.