Proof Sketches: Verifiable In-Network Aggregation Export

@inproceedings{garofalakis-etal-icde07, abstract = {A 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 data-analysis 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.}, author = {Garofalakis, M. and Hellerstein, J. M. and Maniatis, P.}, booktitle = {Data Engineering, 2007. ICDE 2007. IEEE 23rd International Conference on}, citeulike-article-id = {3195781}, citeulike-linkout-0 = {http://dx.doi.org/10.1109/ICDE.2007.368958}, citeulike-linkout-1 = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4221748}, doi = {10.1109/ICDE.2007.368958}, journal = {Data Engineering, 2007. ICDE 2007. IEEE 23rd International Conference on}, keywords = {aggregation, networks, sensor, sketches}, pages = {996--1005}, posted-at = {2008-09-04 19:11:56}, priority = {2}, title = {Proof Sketches: Verifiable In-Network Aggregation}, url = {http://dx.doi.org/10.1109/ICDE.2007.368958}, year = {2007} }

TY - CONF ID - garofalakis-etal-icde07 L3 - citeulike-article-id:3195781 N2 - A 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 data-analysis 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. JF - Data Engineering, 2007. ICDE 2007. IEEE 23rd International Conference on EP - 1005 TI - Proof Sketches: Verifiable In-Network Aggregation T2 - Data Engineering, 2007. ICDE 2007. IEEE 23rd International Conference on SP - 996 KW - aggregation KW - networks KW - sensor KW - sketches AU - Garofalakis, M AU - Hellerstein, JM AU - Maniatis, P PY - 2007/// UR - http://dx.doi.org/10.1109/ICDE.2007.368958 ER -