Verifying Computations without Reexecuting Them. - WALFISH, MICHAEL; BLUMBERG, ANDREW J. (Communications of the ACM, 2015)
The authors discuss potential problems with the reliability of computations performed by remote computers and consider different methods of verification that do not entail replicating the results. The authors describe a framework for addressing the problem in theory, then examine solutions posited by various researchers in published papers. They conclude with a discussion of performance that covers the verifying party's variable costs, the size and amortization of the verifier's setup costs, and overhead costs. INSETS: Encoding a Circuit¿s Execution in a Polynomial;Probabilistically Checking a Transcript¿s Validity;Probabilistically Checkable Proofs (simplified).