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

51–60 of 86 posts

Re: Understanding Zero-knowledge proofs through illustrated examples

#51

Post by betwixthewires »

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.

It's pretty convincing so far though that P != NP, all NP problems can be reduced to the four color map problem, and that means that if any one NP problem can be shown to be P, then all NP problems can be solved in polynomial time. I believe there are huge bounties and lots of researchers attempting to do this with any number of NP problems.

Of course, it could be that someone does it one day, and if so modern cryptography is useless, but I highly doubt it.

Re: Understanding Zero-knowledge proofs through illustrated examples

#52

Post by fiatjaf »

I don't understand the Sudoku example. It says it's non-interactive, but the verifier is interacting with a "machine". The machine prevents the verifier from doing whatever they want with the provided data, shuffles cards, does a bunch of things. That's interaction.

Non-interactivity to me would be if the verifier just got a blob of data and was able to do whatever they wanted with that.

Re: Understanding Zero-knowledge proofs through illustrated examples

#53

Post by dan-robertson »

fiatjaf wrote: post #52

I don't understand the Sudoku example. It says it's non-interactive, but the verifier is interacting with a "machine". The machine prevents the verifier from doing whatever they want with the provided data, shuffles cards, does a bunch of things. That's interaction. Non-interactivity to me would be if the verifier just got a blob of data and was able to do whatever they wanted with that.

The face up and face down cards would really be numbers, and the “machine” means applying some algorithm to the numbers to combine and then check them. Bob could do that by himself.

The key idea is that these numbers somehow don’t reveal which digit goes where.

Re: Understanding Zero-knowledge proofs through illustrated examples

#54

Post by johnsimer »

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).

Re: Understanding Zero-knowledge proofs through illustrated examples

#55

Post by fiatjaf »

dan-robertson wrote: post #53
fiatjaf wrote: post #52

I don't understand the Sudoku example. It says it's non-interactive, but the verifier is interacting with a "machine". The machine prevents the verifier from doing whatever they want with the provided data, shuffles cards, does a bunch of things. That's interaction. Non-interactivity to me would be if the verifier just got a blob of data and was able to do whatever they wanted with that.

The face up and face down cards would really be numbers, and the “machine” means applying some algorithm to the numbers to combine and then check them. Bob could do that by himself. The key idea is that these numbers somehow don’t reveal which digit goes where.

Why can't Bob just look at all cards as he pleases?

Re: Understanding Zero-knowledge proofs through illustrated examples

#56

Post by [deleted] »

bntyhntr wrote: post #50

I had an algorithms class (6.006 or 046?) with Silvio Micali, who I learned partway through the semester was one of the first authors about these things. Anyway, he was a great professor. When talking through algorithms, he'd always start with say, an n^4 solution. Then cut it down to n^3, call on people to help out, etc. I remember it being something like this (in an Italian accent that we really enjoyed) "And now w…

[deleted]

Re: Understanding Zero-knowledge proofs through illustrated examples

#57

Post by vikas-kumar »

> 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 me understand how it is safe. Say one can send the exact cryptographic fingerprint and impersonate me. How is this anything better than me just sending password to authenticate?

Re: Understanding Zero-knowledge proofs through illustrated examples

#58

Post by baby »

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…

Think built-in authenticators like touch ID or face ID. What they do is that they authenticate you via biometrics, and then unlock a private key stored on your device that will sign a challenge. The challenge is only relevant for some situation, so that you can't replay it. Essentially, signing is a zero-knowledge proof that you know your private key, associated with some metadata.

Re: Understanding Zero-knowledge proofs through illustrated examples

#60

Post by jjnoakes »

fiatjaf wrote: post #52

I don't understand the Sudoku example. It says it's non-interactive, but the verifier is interacting with a "machine". The machine prevents the verifier from doing whatever they want with the provided data, shuffles cards, does a bunch of things. That's interaction. Non-interactivity to me would be if the verifier just got a blob of data and was able to do whatever they wanted with that.

Non-interactive in this context, I think, means Alice does something and then Bob verifies it (perhaps with some piece in the middle that both Alice and Bob observe) but there is no back-and-forth, only that single one-directional flow of information.
Post reply on HN