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

[Arthur Breitman]

This reminds me, I've joined this list to ask a question / make a
suggestion and never got to it.

It's very easy for to generate, for large data file a list of challenges to
prove knowledge of the file. For instance the hash of the file after
encryption with a given key indicates knowledge of the for content. If a
user retains a long precomputed list of challenge-response pairs (which
uses only a tiny amount of storage), it can periodically check that a
storage service indeed hosts the data, at a trivial bandwidth cost. The CPU
cost for the host can be alleviated too, by considering a small, random
subset of the data for each challenge.

In an pseudonymous hosting market for long term storage, it would be a
simple way to keep participants honest.

Is there anything of the sort planned or available in Tahoe?
On Nov 7, 2013 11:39 AM, "Andrew Miller" <amiller at cs.ucf.edu> wrote:

> 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
> _______________________________________________
> tahoe-dev mailing list
> tahoe-dev at tahoe-lafs.org
> https://tahoe-lafs.org/cgi-bin/mailman/listinfo/tahoe-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://tahoe-lafs.org/pipermail/tahoe-dev/attachments/20131107/458541d9/attachment.html>