Understanding Zero-knowledge proofs through illustrated examples | Hacker News Reader

Understanding Zero-knowledge proofs through illustrated examples

blog.goodaudience.com

314 pointshongzi82 comments

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.

My algo class was with Charles Rackoff who I believe was a co-author to the first paper ever written on "zero knowledge proofs" for which he won a Godel prize for in the 90's.

I honestly can't remember much about the class except that it was really difficult and I haven't really used anything I learned from that class in my day to day. Hopefully there's something stored in my brain somewhere if I ever need to recall his lectures in the future.

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 completeness in the metamathematical sense. That's a statistical boundary on what it takes to "convince" someone (or "gain knowledge"). But that's a stochastic redefinition of a pretty hard-line property of proof systems. 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).

[1] https://crypto.stanford.edu/cs355/18sp/lec3.pdf

Hence why this is a completeness "probability". In practice this is fine as alternative mechanisms to prove such things as identity involve mechanisms like signatures and hashes, which also can be guessed.

ZKP inherit this definition from the complexity class of interactive proofs (IP) that is usually defined this way. As pointed out in a comment below, IP = PSPACE. Interestingly enough, changing the definition of IP to perfect correctness (1 instead of 2/3) does not make IP any weaker. However, requiring perfect soundness (0 instead of 1/3) would result in IP = NP.

> 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 have just guessed the knowledge.

Or as an analogy, even if you had a perfect and magically irreversible hash, someone could still guess the password first try.

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.

Sure but by the same token I could guess a 256 bit key and decrypt anything I want. The placement of the statistical boundary vs a given adversary compute power is the part we care about, every time.

Yes, these proof protocols allow you to get arbitrary certainty very quickly, so there’s little practical difference.

Scott Aaronson (of quantum computing and P=NP blogging fame) likes to joke that, “okay, fine fine, so these statistical proofs are good enough for the launch codes, military encryption, and multi-billion dollar financial transactions… but what about theorem proving, where you just can’t take any chances?”

Note that it's true for any cryptographic algorithm.

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.

Right, but that astronomical probability is, as you say astronomical. In fact, it’s even better: even i have you a number of trials equal to the number of atoms in the h overs, your expected number of wins would still be astronomically small.

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

A while back I came up with a third ZK Where's Waldo protocol [1] that avoids the need to watermark the page or search Alice for contraband, and also has the (usually desirable) property that it's only convincing to Bob.

You instead have Bob randomly choose whether Alice must a) pull off the screen, revealing the original page, or b) punch a hole through to Waldo, but not both. Then you can do any number of rounds of this, with Alice putting the page in a random position each time.

It's only convincing to Bob because bystanders (or rather, anyone not part of the random number generation for which challenge to use) can't rule out the possibility that they conspired to have Bob always pick the challenge that a faker Alice could solve. (Show the original page when the uses the real one, punch a hole when she uses a fake page.)

[1] https://news.ycombinator.com/item?id=15323790

Edit: That original comment gives the "magic formula" for coming up with such ZKPs as well.

After reading your post I understand that the challenge to show the picture is to test for a fake picture (one with only Waldo for example), so that makes more sense to me. Bob is just allowed to make sure the hidden image that Alice uses is the original (and she can still cheat when Bob choses the other option but the probabilities of succeeding the tricks become vanishingly small with tries, which is the point).

And I assume the screen is meant to always cover the picture (i.e. MUST be much larger than the picture) and only Alice can know the actual coordinates of the picture behind the larger screen (otherwise Bob can infer the position of the Waldo), right? It is also possible that I have not understood something from your interesting proof there.

Thanks for sharing the discussion about the finer points of ZKP being only between Alice and Bob.

That's correct. Ideally you'd want a screen with double the dimensions so that you can designate a portion of it with uniform probability of any location having Waldo.

And my model has it so that (for the second challenge) Bob learns the position of Waldo relative to the screen, but not the position of Waldo relative to the page, which is what we mean by "finding Waldo". And, of course, on that challenge, Bob would not get to learn the position of the page relative to the screen (which would allow him to "find Waldo").

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?

The main type of zero-knowledge proofs are a subset (potentially proper subset) of interactive proofs. All problems that have an interactive proof form a complexity class called IP, and IP is currently believed to be a subset of PSPACE.

So no, not all provable statements are zero-knowledge provable if by zero-knowledge proof you mean an interactive proof where no information is transferred.

Of course it's possible that in the future, other types of zero knowledge proofs will be formulated that are not interactive proofs. For example there are zk-SNARKs that are non-interactive and zero knowledge, but they form a subset of IP and in fact are a subset of NP problems.

> IP is currently believed to be a subset of PSPACE.

IP is _known_ to be _equal_ to PSPACE

Well there you go, Wikipedia confirms that IP = PSPACE, and furthermore that if some assumptions hold about one-way functions, then zero knowledge IP = IP = PSPACE.

Thanks for your correction.

https://en.wikipedia.org/wiki/IP_(complexity)

For problems in NP (i.e. for which a solution can be verified in polynomial time), we can construct a Zero Knowledge Proof by reducing it to 3SAT, then constructing a PCP (Probabilistically checkable proof). T̶h̶e̶ ̶p̶r̶o̶b̶l̶e̶m̶ ̶o̶f̶ ̶d̶e̶t̶e̶r̶m̶i̶n̶i̶n̶g̶ ̶w̶h̶e̶t̶h̶e̶r̶ ̶y̶o̶u̶ ̶c̶a̶n̶ ̶f̶o̶r̶c̶e̶ ̶a̶ ̶c̶h̶e̶c̶k̶m̶a̶t̶e̶ ̶i̶n̶ ̶N̶ ̶m̶o̶v̶e̶s̶ ̶i̶s̶ ̶i̶n̶ ̶N̶P̶,̶ ̶s̶i̶n̶c̶e̶ ̶g̶i̶v̶e̶n̶ ̶a̶ ̶c̶a̶n̶d̶i̶d̶a̶t̶e̶ ̶s̶e̶t̶ ̶o̶f̶ ̶m̶o̶v̶e̶s̶,̶ ̶i̶t̶ ̶c̶a̶n̶ ̶b̶e̶ ̶v̶e̶r̶i̶f̶i̶e̶d̶ ̶i̶n̶ ̶p̶o̶l̶y̶n̶o̶m̶i̶a̶l̶ ̶t̶i̶m̶e̶.̶ The main challenge is the time taken to construct the proof

https://en.wikipedia.org/wiki/PCP_theorem

This is where zkSNARKS help since they generate a non-interactive + succinct proof.

A simple answer to OPs question should be "Yes". Given a finite number of moves, the state space is finite and thus, e.g. using naive min-max, you can verify if you can force a checkmate. In practice this is infeasible for any large N as this is NP as you noted.

Isn't this just an ordinary proof, not a zero knowledge proof? And why would you say this is infeasible for large n? NP doesn't mean that verification is hard, it means that verification is easy, no?

How do you verify a checkmate in polytime? I'd think a candidate sequence of p1,p2 moves isn't a certificate, since it says nothing about whether the losing player still gets checkmated if they make some different moves.

Giving a candidate set of moves that results in a checkmate does not prove that said checkmate was forced. I can provide a candidate set of moves that results in a checkmate after 3 moves (the classic Blitzkrieg), and certainly you can verify that in polynomial time, but that does not mean that it's possible to force a checkmate in 3 moves.

To the best that anyone knows, for a generalized chess board of size WxW, to demonstrate that a checkmate can be forced in at most N moves, you'd need a candidate set of almost every possible sequence of N moves. You can prune some sequences, but not enough to bring the size of the candidate set down to something that can be verified in polynomial time.

Chess, depending on how you generalize it, belongs to EXPTIME.

Ah my bad. I wrote hastily and did not consider the full implication of the word `forced`, i.e. it would involve proving the opponent has no winning options.

Where "winning" means "surviving for N+1 moves".

Mate can be forced in N moves. This generally requires involvement of the king (e.g., check, no other pieces, guarding of the king) such that the only legal moves remaining are dictated by the positioning of the attacker.

Good catch, I was scratching my head at the parent comment since I was pretty sure chess isn't in NP, so thanks for confirming and explaining why it's not.

"I am the Lord thy God!" - God

"Prove it!" - Me

"aec070645fe53ee3b3763059376134f058cc337247c978add178b6ccdfb0019f" - God

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.

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

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.

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.

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

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

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

No. You could have access to the hash.

For the private/public key signing, of course; the signature guarantees that you have access to the private key. But if the ‘private secret data’ is not the private key?

> But if the ‘private secret data’ is not the private key?

It is in the example you were replying to. That’s my point.

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.

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 SNARK based proof is the same (just using the more general circom circuit library to compile the constraints into a ZK-SNARK).

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.

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

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!

Thanks. It was a very fast last-minute hack and the frontend code's a bit buggy! Plus, we need to make some major changes to how it works since at present some of the decisions were made to promote the Chainlink integration make it much more cumbersome than it needs to be.

We briefly considered making this a completely open-source, decentralized thing completely controlled by the community. Your comment has definitely made us a bit more motivated to do that!

I'm completely onboard with the Axie thing. It's an interesting start but I think these kinds of play-to-earn models are fairly toxic.

This is great.

Have to say, after reading several tutorials on different languages that allow you to build zk proof circuits, it still seems very difficult to encode the problem a priori into them such that the result is useful. For example, using them in cryptocurrency seems tricky because you often have to encode the actors involved (by way of their addresses) in advance when you put the zkSNARK on the chain, which makes that less useful.

I really enjoyed Cairo tutorials which have similar concepts.

https://www.cairo-lang.org/docs/hello_cairo/puzzle.html

> 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?

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.

> Say one can send the exact cryptographic fingerprint and impersonate me. How is this anything better than me just sending password to authenticate?

If you're genuinely interested in this topic, you will, I think, really enjoy what I'm about to tell you.

You can setup a system where: 1- you never tell the server your plaintext password at any time, ever; 2- the server does not know your actual password and cannot determine it; 3- you can prove to the server that you know the password, and they have strong proof that you do know it; 4- nobody that eavesdrops on you can do likewise.

Cryptography is magic. And it mostly has to do with the authentication protocol being multi-step. IE: you don't just send your password or fingerprint, you send X and the server sends back Y, and you send Z, and so on and so on, but after a few steps, you have proven yourself. And since it's all being done on GHZ speed computers and gbps networks, it's fast enough for human use.

There are better algorithms than this one, evolutions on the idea, but the most common one discussed is Secure Remote Password Protocol: https://en.wikipedia.org/wiki/Secure_Remote_Password_protoco...

And honestly, I'm not even doing justice to how cool these protocols are. It's an incredible topic.

> Say one can send the exact cryptographic fingerprint and impersonate me. How is this anything better than me just sending password to authenticate?

The message can be signed with a private key to ensure you are not being impersonated. In cases where you'd also like anonymity, it is possible to add some salt as an input to the 'cryptographic fingerprint,' obfuscating the unsalted proof.

This video is good material for learning to reason about ZK proofs: https://www.youtube.com/watch?v=J3UlqJk3Kl0

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

I first heard of ZKPs in the context of mathematical theorems rather than cryptographic protocols, probably sometime in the late '80s I think and probably from an article in the MAA's "Focus" magazine.

If I remember correctly the article said that it is possible for any given mathematical theorem and proof it is possible to produce a graph such that (1) the proof is correct if and only if the graph has a Hamiltonian circuit, and (2) you can show people the graph and prove to them that it is such a graph for that theorem.

The article then gave a ZKP scheme for showing that you know a Hamiltonian circuit on a given graph.

Putting it all together then someone who claimed to have a proof of the Riemann Hypothesis or Goldbach's Conjecture or any other famous unsolved mathematical problem could produce the corresponding graph, and produce a ZKP that they know a Hamiltonian circuit for that graph, and we'd have to accept that they have in fact solved the problem.

I wonder what would happen if someone actually did that for one of the Millennium Prize Problems [1] or some other high profile problem that has a substantial reward behind it? When offering prizes for proofs nowadays should you include a clause in the rules that states to win the prize you have to publish a conventional proof?

[1] https://en.wikipedia.org/wiki/Millennium_Prize_Problems

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://starkware.co/starknet/

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.

I don't have stats on that, but I'm sure the StarkWare community would love to help

- a recent tweet by StarkWare President Eli on some performance stats https://twitter.com/EliBenSasson/status/1467161132569931784

- StarkWare discord server https://t.co/klHVDhQokP

- StarkWare research forum https://community.starknet.io/

Alice and Bob used to be such a fun couple. Now he's watermarking the back of Where's Wally. I think we all know where this is going.

If you're wondering how the state of the art schemes work, here's my series of explanation of PLONK: https://www.youtube.com/watch?v=RUZcam_jrz0&

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 secret? Obviously while me and snoopers never knowing what X is?

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

In the Waldo example, if Bob has watermarked the back of the puzzle and Alice shows him the cutout Waldo, what prevents Bob from comparing the portion of the watermark on the back of the cutout Waldo (provided by Alice) with the original watermark (say Bob chose the watermark to be a grid of cells where each cell is trivially identifiable and small enough to be contained on the back of the cutout), thus deriving Waldo’s location?

Alice should properly reject that proposal, and only accept pages with totally uniform watermarks.

So in essence, Alice must also verify that, for any given puzzle, it has been constructed in a way such that Bob cannot discern the information that is intended to be private? That sounds problematic for general public Alice and clever trickster Bob scenarios, which I suspect would be a common use case. What’s the solution, an oligopoly of Proof Authorities?

> That sounds problematic for general public Alice and clever trickster Bob scenarios, which I suspect would be a common use case.

The general public isn't involved in constructing the proofs, just as they don't manually engage in cryptographic exchanges of any kind. Absent cryptographic expertise, the general public is forced to delegate their trust to cryptographic experts, whose code they execute when making exchanges with tricksters.

Sounds like you are saying ZKPs won’t be generally applicable and instead that these proofs have to be specifically crafted for a given application use case much like how you choose an acceptable cipher suite today?

Like I go to website A and they want me to authenticate that I have access to a unique email address without revealing which one and they offer a zkp-email-ident challenge, I’d have to use OpenZKP which supports zkp-email-ident because the cryptography community vetted it and thus it’s included as a supported auth challenge? So the implication here would be that the protocol specifies the exact nature of the (back to the cutout example) image such that it’s impossible for Bob to apply an adversarial watermark?

So generally ZKPs are more like a cryptography primitive and protocols must be developed that apply them in ways that mitigate adversaries.

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?

Typically the “mixing of the cards” is done via a one-way function (e.g., modular arithmetic), making it impractical to fake and impractical to reverse.

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.

I like the Ali Baba's cave [1] explanation for ZKP. Especially since it gives intuition for how one can prove that a protocol is in fact zero-knowledge.

[1] http://pages.cs.wisc.edu/~mkowalcz/628.pdf

That link's dead though.

It seems to work for me. Though here is a snapshot just in case https://archive.md/MpPRL

In the sudoku exapmle how can Bob be sure that the three face down cards in a cell are three identcal card? Without this knowledge, it is easy to pass the final validations without a correct solution.

Each pile has three solutions in it, and you're asking how we know that all three solutions align to the same number, as required by Sudoku.

> Starting with each row, Bob randomly chooses one card in each cell, from the top, the middle, or the bottom

The random assignment of solutions from each pile to each of the three problems means that the only way to consistently pass the test is to have the three solutions in each pile be identical.

Oh, I missed that part, now its clear.

The machine itself would ideally not be a black box, so Bob could verify that the machine places 3 identical cards

The Sudoku example is great.

This is partially tangential, but they have misidentified Wanda as Waldo in the original image. In some of the books, there are multiple Waldo characters to be found on the pages. In this image, Waldo is elsewhere.

Doesn't detract from the main ideas and shouldn't be too hard to fix.

Nice one, let's call it intentional deeper meaning saying you shouldn't roll your own zero-proof knowledge crypto implementation.

This is a sect and abuse of a language in which words supposed to be associated with particular non-imaginary aspects of reality.

Logic "works" not because its rules are absolute, but because Universe has its structure and laws. Ignoring validity and non-contradiction of premises renders any conclusions meaningless (merely abstract Hegelian bullshit).

Causes (and premises) are not arbitrary so the assumption that everything can be deduced (proved) from anything is bullshit.

Applied math require a type discipline and abstract math is just a set of rules, like abstract logic. And this is my contribution to science.

Reply on news.ycombinator.com