VerSum: Verifiable Computations over Large Public Logs
VerSum allows lightweight clients to outsource expensive computations over large and frequently changing data structures, such as the Bitcoin or Namecoin blockchains, or a Certificate Transparency log. VerSum clients ensure that the output is correct by comparing the outputs from multiple servers. V...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery (ACM)
2015
|
| Online Access: | http://hdl.handle.net/1721.1/100450 https://orcid.org/0000-0003-0238-2703 https://orcid.org/0000-0001-7098-586X https://orcid.org/0000-0003-3438-4711 |
| _version_ | 1826215575936827392 |
|---|---|
| author | van den Hooff, Jelle Kaashoek, M. Frans Zeldovich, Nickolai |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory van den Hooff, Jelle Kaashoek, M. Frans Zeldovich, Nickolai |
| author_sort | van den Hooff, Jelle |
| collection | MIT |
| description | VerSum allows lightweight clients to outsource expensive computations over large and frequently changing data structures, such as the Bitcoin or Namecoin blockchains, or a Certificate Transparency log. VerSum clients ensure that the output is correct by comparing the outputs from multiple servers. VerSum assumes that at least one server is honest, and crucially, when servers disagree, VerSum uses an efficient conflict resolution protocol to determine which server(s) made a mistake and thus obtain the correct output.
VerSum's contribution lies in achieving low server-side overhead for both incremental re-computation and conflict resolution, using three key ideas: (1) representing the computation as a functional program, which allows memoization of previous results; (2) recording the evaluation trace of the functional program in a carefully designed computation history to help clients determine which server made a mistake; and (3) introducing a new authenticated data structure for sequences, called SeqHash, that makes it efficient for servers to construct summaries of computation histories in the presence of incremental re-computation. Experimental results with an implementation of VerSum show that VerSum can be used for a variety of computations, that it can support many clients, and that it can easily keep up with Bitcoin's rate of new blocks with transactions. |
| first_indexed | 2024-09-23T16:35:50Z |
| format | Article |
| id | mit-1721.1/100450 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T16:35:50Z |
| publishDate | 2015 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/1004502022-10-02T08:22:15Z VerSum: Verifiable Computations over Large Public Logs van den Hooff, Jelle Kaashoek, M. Frans Zeldovich, Nickolai Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science van den Hooff, Jelle Kaashoek, M. Frans Zeldovich, Nickolai VerSum allows lightweight clients to outsource expensive computations over large and frequently changing data structures, such as the Bitcoin or Namecoin blockchains, or a Certificate Transparency log. VerSum clients ensure that the output is correct by comparing the outputs from multiple servers. VerSum assumes that at least one server is honest, and crucially, when servers disagree, VerSum uses an efficient conflict resolution protocol to determine which server(s) made a mistake and thus obtain the correct output. VerSum's contribution lies in achieving low server-side overhead for both incremental re-computation and conflict resolution, using three key ideas: (1) representing the computation as a functional program, which allows memoization of previous results; (2) recording the evaluation trace of the functional program in a carefully designed computation history to help clients determine which server made a mistake; and (3) introducing a new authenticated data structure for sequences, called SeqHash, that makes it efficient for servers to construct summaries of computation histories in the presence of incremental re-computation. Experimental results with an implementation of VerSum show that VerSum can be used for a variety of computations, that it can support many clients, and that it can easily keep up with Bitcoin's rate of new blocks with transactions. United States. Defense Advanced Research Projects Agency. Clean-slate design of Resilient, Adaptive, Secure Hosts (CRASH) Program (Contract N66001-10-2-4089) National Science Foundation (U.S.) (Award CNS-1053143) National Science Foundation (U.S.) (Award CNS-1413920) 2015-12-21T14:44:58Z 2015-12-21T14:44:58Z 2014-11 Article http://purl.org/eprint/type/ConferencePaper 9781450329576 http://hdl.handle.net/1721.1/100450 Jelle van den Hooff, M. Frans Kaashoek, and Nickolai Zeldovich. 2014. VerSum: Verifiable Computations over Large Public Logs. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security (CCS '14). ACM, New York, NY, USA, 1304-1316. https://orcid.org/0000-0003-0238-2703 https://orcid.org/0000-0001-7098-586X https://orcid.org/0000-0003-3438-4711 en_US http://dx.doi.org/10.1145/2660267.2660327 Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security (CCS '14) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) MIT web domain |
| spellingShingle | van den Hooff, Jelle Kaashoek, M. Frans Zeldovich, Nickolai VerSum: Verifiable Computations over Large Public Logs |
| title | VerSum: Verifiable Computations over Large Public Logs |
| title_full | VerSum: Verifiable Computations over Large Public Logs |
| title_fullStr | VerSum: Verifiable Computations over Large Public Logs |
| title_full_unstemmed | VerSum: Verifiable Computations over Large Public Logs |
| title_short | VerSum: Verifiable Computations over Large Public Logs |
| title_sort | versum verifiable computations over large public logs |
| url | http://hdl.handle.net/1721.1/100450 https://orcid.org/0000-0003-0238-2703 https://orcid.org/0000-0001-7098-586X https://orcid.org/0000-0003-3438-4711 |
| work_keys_str_mv | AT vandenhooffjelle versumverifiablecomputationsoverlargepubliclogs AT kaashoekmfrans versumverifiablecomputationsoverlargepubliclogs AT zeldovichnickolai versumverifiablecomputationsoverlargepubliclogs |