[tahoe-dev] SNARKs, constant-time proofs of computation

[Andrew Miller]

Here's a possible Tesla Coils and Corpses discussion I'd like to have
sometime a few weeks from now maybe:
   SNARKs (Succinct Non-interactive Arguments of Knowledge) are a
recent hot topic in modern cryptography. A generic SNARK scheme lets
you can take an arbitrary computation (e.g., the routine that checks a
signature and a merkle tree branch) and compile it to a *constant
size* compressed representation, called the verification key. An
untrusted server can execute the computation on behalf of the client,
and produce a *constant size* proof that it was carried out correctly.

  These techniques are currently considered "nearly practical", in the
sense that there are some proof-of-concept implementations out there
(that compile C code), they're undergoing very active optimization
work, but they have pretty poor constant-factors and absolute
performance.

   Here are the top three projects:
   - Pinocchio https://research.microsoft.com/en-us/projects/verifcomp/
(half open sourced)
   - TinyRAM http://www.scipr-lab.org/tinyram (currently vaporware)
   - Pantry https://github.com/srinathtv/pantry/ (fully open sourced)

  These have potential applications to TahoeLAFS. You could
potentially perform a check/repair, or issue updates to an MDMF file,
without having to actually transfer or compute over an entire merkle
tree branch.

   So the discussion topic would be an overview of how these work, the
available implementations, and feasibility estimates for possible
Tahoe applications.



(also, this topic is interesting to me also because I am planning to
extend my authenticated-data-structure programming language to include
SNARKs.)

-- 
Andrew Miller