Protocol for certifying cloud computations integrity

We define a problem of certifying computation integrity performed by some remote party we do not necessarily trust. We present a multi-party interactive protocol that solves this problem under specified constraints. The protocol rely on a computing entity called weak reliable computing device that is able to produce certificate for a tiny computation. A complex computation of a user can be certified by relying on such weak entity if we translate the user program into an iterative form that converges to the result, a style resembling continuation-passing style programming paradigm. Each iteration of the computation can then be certified by the weak reliable computing device. To ensure the user that computation result was computed fairly and correctly, we put this mechanism into a multi-party incentivized context of several computing providers competing with each other for publishing the result and taking the reward, or finding an error in the published result of other parties. Together with computation result, the computation certificate is published. The certificate is constructed in such a way that other fair parties (auditors) are able to find divergent computation step in $O(\log n)$ steps, where $n$ is a number of computing steps taken before reaching the result. If error is found, the auditor sends proof of the error (called refutation) in the trusted weak computing device that plays the role of autonomous transparent arbiter able to check refutation by replaying a tiny fraction of the computation. Comparing to the nearest related work, our protocol reduces a proof construction complexity from $O(n\log n)$ to $O(n)$, turning a communication complexity to exactly one round using a certificate of a comparable length. We also give the formal specification for the protocol and prove some of its security properties in a specified threat-model. Experimental evaluation of the protocol in a model setting is provided.