Topic: VerSum: Verifiable Computations over Large Public Logs (Read 1652 times)

Amusing paper on blockchain-based data verification/authentication.

From MIT CSAIL (pdf): 
VERSUM allows lightweight clients to outsource expensive compu- tations 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 over- head for both incremental re-computation and conflict resolution, using three key ideas: (1) representing the computation as a func- tional program, which allows memorization of previous results; (2) recording the evaluation trace of the functional program in a care- fully 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.