Minos Garofalakis and Joseph M. Hellerstein and Petros Maniatis

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2006-20

March 1, 2006

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-20.pdf

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.

---

BibTeX citation:

@techreport{Garofalakis:EECS-2006-20,
    Author= {Garofalakis, Minos and Hellerstein, Joseph M. and Maniatis, Petros},
    Title= {Proof Sketches: Verifiable Multi-Party Aggregation},
    Year= {2006},
    Month= {Mar},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-20.html},
    Number= {UCB/EECS-2006-20},
    Abstract= {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.},
}

EndNote citation:

%0 Report
%A Garofalakis, Minos 
%A Hellerstein, Joseph M. 
%A Maniatis, Petros 
%T Proof Sketches: Verifiable Multi-Party Aggregation
%I EECS Department, University of California, Berkeley
%D 2006
%8 March 1
%@ UCB/EECS-2006-20
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-20.html
%F Garofalakis:EECS-2006-20