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

[Jonathan Dill]

If I'm reading this right, if someone is trying to crack the system, it
might allow you to quickly discard a lot of the malicious data and reduce
the impact on performance and the cracker learns nothing about the system
in the process--something they really need with bitcoin / altcoin. When you
exchange hashes, a third party could in theory use that information to
learn about the system, I think mainly hashes would benefit crackers with
large amounts of resources at their disposal, so I'd say it really depends
on the use case (who would want your data?) and the design goals of the
system.

http://stackoverflow.com/questions/6776050/how-long-to-brute-force-a-salted-sha-512-hash-salt-provided

"Zero-knowledge proofs introduced by Goldwasser, Micali and Racko [GMR89]
are interactive
protocols that enable a prover to convince a veri er about the truth of a
statement without
leaking any information but the fact that the statement is true. Blum,
Feldman and Micali
[BFM88] followed up by introducing non-interactive zero-knowledge (NIZK)
proofs where the
prover outputs just one message called a proof, which convinces the veri er
of the truth of the
statement. The central properties of zero-knowledge proofs and
non-interactive zero-knowledge
proofs are completeness, soundness and zero-knowledge."

"Completeness: If the statement is true, the prover should be able to
convince the veri er.
Soundness: A malicious prover should not be able to convince the veri er if
the statement is
false.
Zero-knowledge: A malicious veri er learns nothing except that the
statement is true"

http://www0.cs.ucl.ac.uk/staff/J.Groth/PCPNIZK.pdf

"Non-interactive zero-knowledge proofs are a variant of zero-knowledge
proofs in which no interaction is necessary between prover and verifier.
Blum, Feldman, and Micali [1] showed that a common reference string shared
between the prover and the verifier is enough to achieve computational
zero-knowledge without requiring interaction."

http://en.wikipedia.org/wiki/Non-interactive_zero-knowledge_proof

A more simplified explanation and example:

http://www.cse.scu.edu/~tschwarz/coen350/zkp.html


On Thu, Nov 7, 2013 at 3:11 PM, Natanael <natanael.l at gmail.com> wrote:

> Resending since it bounced the last time.
>
> > 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" <steveweis at 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 <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.
> >>
> >>
> >> _______________________________________________
> >> cryptography mailing list
> >> cryptography at randombit.net
> >> http://lists.randombit.net/mailman/listinfo/cryptography
> >>
>
> _______________________________________________
> 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/687552a6/attachment.html>