Paper 2017/901

Stateful Multi-Client Verifiable Computation

Christian Cachin, Esha Ghosh, Dimitrios Papadopoulos, and Björn Tackmann


This paper develops a cryptographic protocol for outsourcing arbitrary stateful computation among multiple clients to an untrusted server, while guaranteeing integrity of the data. The clients communicate only with the server and store only a short authenticator to ensure that the server does not cheat. Our contribution is two-fold. First, we extend the recent hash&prove scheme of Fiore et al. (CCS 2016) to stateful computations that support arbitrary updates by the untrusted server, in a way that can be verified by the clients. We use this scheme to generically instantiate authenticated data types. Second, we describe a protocol for multi-client verifiable computation based on an authenticated data type, and prove that it achieves a computational version of fork linearizability. This is the strongest guarantee that can be achieved in the setting where clients do not communicate directly; it ensures correctness and consistency of outputs seen by the clients individually.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Byzantine emulationverifiable computationauthenticated data types
Contact author(s)
bta @ zurich ibm com
2018-08-23: last of 2 revisions
2017-09-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Christian Cachin and Esha Ghosh and Dimitrios Papadopoulos and Björn Tackmann},
      title = {Stateful Multi-Client Verifiable Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2017/901},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.