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

41–50 of 86 posts

Re: Understanding Zero-knowledge proofs through illustrated examples

#41

Post by baby »

jstanley wrote: post #7

Does anyone know if all provable things are zero-knowledge provable? As an example: given a chess position, would you be able to construct a zero-knowledge proof that you can force checkmate in N moves or less without revealing anything about the particular moves involved? If so, what would such a proof look like?

Intuitively I would encode the rules of the game, then the program would let you perform N moves (where N is hardcoded in the circuit, or is a public input but then the circuit must allow for N or more moves) and check at the end that there's a checkmate.

Re: Understanding Zero-knowledge proofs through illustrated examples

#42

Post by baby »

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…

Note that it's true for any cryptographic algorithm.

Re: Understanding Zero-knowledge proofs through illustrated examples

#44

Post by cblconfederate »

debbiedowner wrote: post #35

Is there an analogue for this to show that a person must know something even if they pretend they don't? Say I'm a middle man escrow service with an untrusted channel, and trusted A has sold a secret X to untrusted B using me, and B now wants to sell X to untrusted C on my platform. Is there a ZKP way to both make sure B doesn't scam C by sending a fake secret, and C doesn't scam B by saying they received a fake secr…

Just ask them to zero-knowledge prove that they don't know it.

Re: Understanding Zero-knowledge proofs through illustrated examples

#45

Post by ransom1538 »

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…

But isn't that how RSA works? Generate pseudoprimes - prove that they "should" be primes. That doesn't sound like "completeness" either but all modern asymmetric encryption uses public keys.

Re: Understanding Zero-knowledge proofs through illustrated examples

#46

Post by Gehinnn »

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.

Re: Understanding Zero-knowledge proofs through illustrated examples

#47

Post by aboodman »

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.

zksnarks are a generalization of this idea. They allow one to prove that they ran any arbitrary program P (in np) with some private data X, and it produced output Y, without revealing X.

It seems (slightly) less mystical for me to see it that way.

Re: Understanding Zero-knowledge proofs through illustrated examples

#48

Post by omeze »

JofArnold wrote: post #4

In addition to Nalin's great sudoku example elsewhere, here's a couple of my repos that use SNARKS: 1) Some experiments/learnings https://github.com/JofArnold/zkp-learning-in-public 2) A blockchain-based Dungeon crawler built for a hackathon that uses a SNARK (Circom, snarkjs) to validate that the user hasn't cheated when getting to the end of the maze https://github.com/Derked/FantasyCampaign

Wow, fantasy campaign is the first crypto-native game that actually looks like it could be _fun_ (as an avid gamer, it pains me to see stuff like Axie Infinity as the poster child for "web3 games"). A roguelike with re-usable /remixable items across games and players would be super fun to play!

Re: Understanding Zero-knowledge proofs through illustrated examples

#49

Post by elcomet »

jstanley wrote: post #7

Does anyone know if all provable things are zero-knowledge provable? As an example: given a chess position, would you be able to construct a zero-knowledge proof that you can force checkmate in N moves or less without revealing anything about the particular moves involved? If so, what would such a proof look like?

To write a zkp you first need to have a proof. How would your proof look like here ?

In the case where you prove existence, it's easy as just knowing the object is a proof. Here it's not really a proof of existence, it's more complex.

The only proof acceptable here would be the whole tree starting from this point. This seems too complex to use in a zero knowledge proof

Re: Understanding Zero-knowledge proofs through illustrated examples

#50

Post by bntyhntr »

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 we're at n^2! Pretty good you might think eh? After all, we were at n^4 just a few minutes ago, this is much better? But, the human mind is a wonderful thing! It is so creative and some people thought about it, and they got n log n! Amazing. I know you are thinking, n log n is always as good as it gets in this class. Well I don't want to go into the details because, it is horrifying! But actually some people, they did even better! And you know as I said, the human mind is amazing! So maybe one day, you will do even better."

Also I sat across the aisle from him when Eliezer Yudkowsky came for a talk and only realized it when he answered a question EY asked the audience.

This kind of turned into me reminiscing but my point is, the guy who put these out there and did a lot of work on them is a great undergrad professor and that makes me happy.

Post reply on HN