{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T16:14:02Z","timestamp":1783008842296,"version":"3.54.5"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2011,9]]},"abstract":"<jats:p>When computation is outsourced, the data owner would like to be assured that the desired computation has been performed correctly by the service provider. In theory, proof systems can give the necessary assurance, but prior work is not sufficiently scalable or practical. In this paper, we develop new proof protocols for verifying computations which are streaming in nature: the verifier (data owner) needs only logarithmic space and a single pass over the input, and after observing the input follows a simple protocol with a prover (service provider) that takes logarithmic communication spread over a logarithmic number of rounds. These ensure that the computation is performed correctly: that the service provider has not made any errors or missed out some data. The guarantee is very strong: even if the service provider deliberately tries to cheat, there is only vanishingly small probability of doing so undetected, while a correct computation is always accepted.<\/jats:p>\n          <jats:p>We first observe that some theoretical results can be modified to work with streaming verifiers, showing that there are efficient protocols for problems in the complexity classes NP and NC. Our main results then seek to bridge the gap between theory and practice by developing usable protocols for a variety of problems of central importance in streaming and database processing. All these problems require linear space in the traditional streaming model, and therefore our protocols demonstrate that adding a prover can exponentially reduce the effort needed by the verifier. Our experimental results show that our protocols are practical and scalable.<\/jats:p>","DOI":"10.14778\/2047485.2047488","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"25-36","source":"Crossref","is-referenced-by-count":33,"title":["Verifying computations with streaming interactive proofs"],"prefix":"10.14778","volume":"5","author":[{"given":"Graham","family":"Cormode","sequence":"first","affiliation":[{"name":"AT&amp;T Labs---Research"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Justin","family":"Thaler","sequence":"additional","affiliation":[{"name":"SEAS, Harvard University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ke","family":"Yi","sequence":"additional","affiliation":[{"name":"HKUST, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2011,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity: A Modern Approach","author":"Arora S.","year":"2009","unstructured":"S. Arora and B. Barak . Computational Complexity: A Modern Approach . Cambridge University Press . 2009 . S. Arora and B. Barak. Computational Complexity: A Modern Approach. Cambridge University Press. 2009."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90028-1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2005.27"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_20"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1881412.1881446"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1294261.1294281"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90041-8"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90210-K"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1881412.1881445"},{"key":"e_1_2_1_13_1","unstructured":"S. Garfinkel. Sub-Linear Drive Analysis. http:\/\/simson.net\/page\/Sub-Linear_Drive_Analysis  S. Garfinkel. Sub-Linear Drive Analysis. http:\/\/simson.net\/page\/Sub-Linear_Drive_Analysis"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374396"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12137"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1315245.1315317"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129782"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/264772"},{"key":"e_1_2_1_19_1","first-page":"147","volume-title":"VLDB","author":"Li F.","year":"2007","unstructured":"F. Li , K. Yi , M. Hadjieleftheriou , and G. Kollios . Proof-infused streams: Enabling authentication of sliding window queries on streams . In VLDB , pages 147 -- 158 , 2007 . F. Li, K. Yi, M. Hadjieleftheriou, and G. Kollios. Proof-infused streams: Enabling authentication of sliding window queries on streams. In VLDB, pages 147--158, 2007."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000002"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0145-2"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02017-9_21"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146609"},{"key":"e_1_2_1_26_1","first-page":"1","volume-title":"Proc. of HotOS Workshop","author":"Setty S.","year":"2011","unstructured":"S. Setty , A. J. Blumberg , and M. Walfish . Toward practical and unconditional verification of remote computations . In Proc. of HotOS Workshop , pages 1 -- 5 , 2011 . S. Setty, A. J. Blumberg, and M. Walfish. Toward practical and unconditional verification of remote computations. In Proc. of HotOS Workshop, pages 1--5, 2011."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-008-0113-2"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1567274.1567277"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2047485.2047488","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:03:24Z","timestamp":1672221804000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2047485.2047488"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,9]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,9]]}},"alternative-id":["10.14778\/2047485.2047488"],"URL":"https:\/\/doi.org\/10.14778\/2047485.2047488","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2011,9]]}}}