[cryptography] [tahoe-dev] SNARKs, constant-time proofs of computation
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-...@tahoe-lafs.org https://tahoe-lafs.org/cgi-bin/mailman/listinfo/tahoe-dev ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] [tahoe-dev] SNARKs, constant-time proofs of computation
Hi Andrew. You may be interested in contacting an early-phase startup called Tegos: http://www.tegostech.com/ They're in stealth mode and haven't posted any info online, but they are legitimate and relevant to this work. On Thu, Nov 7, 2013 at 8:39 AM, Andrew Miller amil...@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. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] [tahoe-dev] SNARKs, constant-time proofs of computation
SCIPR is another one. http://www.scipr-lab.org/ If it became efficient it could be useful for mining in a Bitcoin fork (commonly called altcoins). Don't know what kind of computations you'd actually would want it to do, though. Most meaningful computations could easily be deprecated by better algorithms, forcing you to switch algorithms often. You also have the problem of achieving consensus for what to compute. What exactly would it be used for in Tahoe-LAFS? - Sent from my phone Den 7 nov 2013 18:54 skrev Steve Weis stevew...@gmail.com: Hi Andrew. You may be interested in contacting an early-phase startup called Tegos: http://www.tegostech.com/ They're in stealth mode and haven't posted any info online, but they are legitimate and relevant to this work. On Thu, Nov 7, 2013 at 8:39 AM, Andrew Miller amil...@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. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography