Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Understanding Zero-knowledge proofs through illustrated examples

blog.goodaudience.com

Post reply on HN
Print view View original

71–80 of 86 posts

Re: Understanding Zero-knowledge proofs through illustrated examples

#71

Post by aboodman »

johnsimer wrote: post #54
aboodman wrote: post #47

zksnarks are one of the most wonderful results in computer science and mathematics. On first learning of them, I had the common reaction of "I can't believe this is even possible to do". The way that I came to intuitively understand them is by analogy to public key cryptography. Digital signatures allow someone to run the RSA algorithm on some piece of private data X and prove the output is Y, without revealing X. zk…

Would there be a way to make a Proof of Infra algorithm using zk proofs? e.g. to prove that some blockchain nodes ran a set of data through a particular infra setup (e.g. a bunch of language arbitrary Lambdas, SQS queues etc. defined in cloudformation or terraform).

No it has to be a pure function with no reference to outside systems, and the function has to be in the complexity class np.

Re: Understanding Zero-knowledge proofs through illustrated examples

#72

Post by alanfranz »

aboodman wrote: post #47

zksnarks are one of the most wonderful results in computer science and mathematics. On first learning of them, I had the common reaction of "I can't believe this is even possible to do". The way that I came to intuitively understand them is by analogy to public key cryptography. Digital signatures allow someone to run the RSA algorithm on some piece of private data X and prove the output is Y, without revealing X. zk…

Why would you leverage signatures? An hash would be enough for showing knowledge.

Maybe you meant you needed to show proof that only you (not somebody else) knows some data?

Even for such scenario I would not be sure it’s correct. Many signature implementations hash the data, then sign the hash; if I happen to know the hash but not the data, I could just sign it without owning it.

(I should verify a few things, this was written off the top of my head).

Re: Understanding Zero-knowledge proofs through illustrated examples

#73

Post by hanniabu »

vikas-kumar wrote: post #57

> Logging into a website: rather than typing your password into a potentially unsafe website, you can simply send a proof that you “know your password”. Authenticating your identity: rather than giving your mother’s maiden name over the phone to a random, bank call center agent, you can simply send a proof (a cryptographic fingerprint), that you are who you say you are. These examples tipped me off. Can someone help…

> you can simply send a proof

My bank doesn't even support OTP 2FA for login. There's no way they'll support this stuff.

Re: Understanding Zero-knowledge proofs through illustrated examples

#74

Post by runeks »

alanfranz wrote: post #72
aboodman wrote: post #47

zksnarks are one of the most wonderful results in computer science and mathematics. On first learning of them, I had the common reaction of "I can't believe this is even possible to do". The way that I came to intuitively understand them is by analogy to public key cryptography. Digital signatures allow someone to run the RSA algorithm on some piece of private data X and prove the output is Y, without revealing X. zk…

Why would you leverage signatures? An hash would be enough for showing knowledge. Maybe you meant you needed to show proof that only you (not somebody else) knows some data? Even for such scenario I would not be sure it’s correct. Many signature implementations hash the data, then sign the hash; if I happen to know the hash but not the data, I could just sign it without owning it. (I should verify a few things, this…

> Why would you leverage signatures?

Because in order to verify that a hash over some secret data is correct you need access to the secret data, which makes it pointless.

Only using a signature can the signer prove that they have knowledge of a secret number (their private key) by providing information that does not reveal the secret (public key, message hash, signature).

Re: Understanding Zero-knowledge proofs through illustrated examples

#75

Post by runeks »

spir wrote: post #67

StarkNet is a turing complete virtual machine built on top of zero-knowledge proofs. The output of any StarkNet program can be transformed into an extremely succinct zero-knowledge proof. This proof generation process is quite costly. But then, the proof itself is extremely tiny and may be verified extremely inexpensively. Coincidentally with this post, StarkNet launched this week after seven years of R&D. https://st…

Interesting!

> This proof generation process is quite costly.

Where can I find some benchmarks for creating various proofs?

This technology can be groundbreaking or useless solely depending on how long it takes to create a given proof.

Re: Understanding Zero-knowledge proofs through illustrated examples

#77

Post by aboodman »

alanfranz wrote: post #72
aboodman wrote: post #47

zksnarks are one of the most wonderful results in computer science and mathematics. On first learning of them, I had the common reaction of "I can't believe this is even possible to do". The way that I came to intuitively understand them is by analogy to public key cryptography. Digital signatures allow someone to run the RSA algorithm on some piece of private data X and prove the output is Y, without revealing X. zk…

Why would you leverage signatures? An hash would be enough for showing knowledge. Maybe you meant you needed to show proof that only you (not somebody else) knows some data? Even for such scenario I would not be sure it’s correct. Many signature implementations hash the data, then sign the hash; if I happen to know the hash but not the data, I could just sign it without owning it. (I should verify a few things, this…

The key is the "any arbitrary program".

With zk-snarks, I can, theoretically, run some complex analysis of some data -- imagine something that requires millions of compute hours -- and provide a receiver (a) the answer, and (b) a compact hash-like proof that (a) is correct *without* receiver having to re-run the calculation to trust the answer.

Re: Understanding Zero-knowledge proofs through illustrated examples

#78

Post by Ar-Curunir »

Gehinnn wrote: post #46
nibnalin wrote: post #2

It's kind of mind-blowing that the universe allows us to do this at all: Convincingly prove that you have a solution to a puzzle without revealing anything about the solution itself. On the sudoku example, I built out a playable version of zero-knowledge sudoku a few months ago: https://github.com/nalinbhardwaj/snarky-sudoku It doesn't use the same strategy as the article, but the underlying idea of non-interactive S…

We still don't know if the universe allows us to do that. If P=NP ZKPs are worthless.

For some settings we have unconditional zero-knowledge; we don’t need to make any assumptions. This is called perfect ZK or statistical ZK

Re: Understanding Zero-knowledge proofs through illustrated examples

#79

Post by tromp »

Dylan16807 wrote: post #38
dvt wrote: post #20

I'm not an expert, but coming from a logic background, I always think that ZK proofs are fudging the idea of "completeness" (and "soundness," for that matter). For example, in [1] (Definition 1.1): > We note that the constants 2/3 and 1/3 are arbitrarily chosen for simplicity. We can always amplify the completeness probability to 1 − negl(λ) and the soundness probability to negl(λ) with repetition. But that's not com…

> In other words, you could theoretically have no knowledge and just get astronomically lucky to an arbitrary degree (whatever degree it would take to cross that proof threshold). Even if you remove all the statistical nature from the system: They're trying to prove they have a piece of knowledge of finite size. If astronomical luck is a real concern, then you have to worry that even a non-probabilistic prover could…

In many applications of zero knowledge proofs, you prove knowledge of solution to a puzzle that need not have a solution. E.g. graph isomorphism, a 3-coloring, a Sudoko puzzle. So the probability of guessing the solution can be 0, while there's a nonzero probability of convincing a verifier.

Re: Understanding Zero-knowledge proofs through illustrated examples

#80

Post by mirekrusin »

dvt wrote: post #20

I'm not an expert, but coming from a logic background, I always think that ZK proofs are fudging the idea of "completeness" (and "soundness," for that matter). For example, in [1] (Definition 1.1): > We note that the constants 2/3 and 1/3 are arbitrarily chosen for simplicity. We can always amplify the completeness probability to 1 − negl(λ) and the soundness probability to negl(λ) with repetition. But that's not com…

With that way of thinking nothing is secure because random byte generator can reveal it.
Post reply on HN