[HN Gopher] Understanding Zero-knowledge proofs through illustra...
___________________________________________________________________
Understanding Zero-knowledge proofs through illustrated examples
Author : hongzi
Score : 145 points
Date : 2021-12-02 17:22 UTC (5 hours ago)
(HTM) web link (blog.goodaudience.com)
(TXT) w3m dump (blog.goodaudience.com)
| [deleted]
| beardyw wrote:
| 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.
| dcow wrote:
| 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?
| jtsiskin wrote:
| Alice should properly reject that proposal, and only accept
| pages with totally uniform watermarks.
| dcow wrote:
| 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?
| wutbrodo wrote:
| > 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.
| dcow wrote:
| 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.
| debbiedowner wrote:
| 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?
| cblconfederate wrote:
| Just ask them to zero-knowledge prove that they don't know it.
| c0742e9366 wrote:
| 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
| red_trumpet wrote:
| That link's dead though.
| c0742e9366 wrote:
| It seems to work for me. Though here is a snapshot just in
| case https://archive.md/MpPRL
| SilasX wrote:
| 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.
| cmehdy wrote:
| 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.
| SilasX wrote:
| 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").
| jstanley wrote:
| 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?
| aan1092j wrote:
| 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). The problem of determining whether you can
| force a checkmate in N moves is in NP, since given a candidate
| set of moves, it can be verified in polynomial time. 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.
| kevinwang wrote:
| 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.
| omegalulw wrote:
| 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.
| kevinwang wrote:
| 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?
| Kranar wrote:
| 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.
| SilasX wrote:
| 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.
| aan1092j wrote:
| 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.
| red_trumpet wrote:
| Where "winning" means "surviving for N+1 moves".
| baby wrote:
| 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.
| api wrote:
| "I am the Lord thy God!" - God
|
| "Prove it!" - Me
|
| "aec070645fe53ee3b3763059376134f058cc337247c978add178b6ccdfb001
| 9f" - God
| Kranar wrote:
| 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.
| tooltower wrote:
| > IP is currently believed to be a subset of PSPACE.
|
| IP is _known_ to be _equal_ to PSPACE
| Kranar wrote:
| 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)
| kemyke wrote:
| 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.
| wutbrodo wrote:
| 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.
| kemyke wrote:
| Oh, I missed that part, now its clear.
| Jarwain wrote:
| The machine itself would ideally not be a black box, so Bob
| could verify that the machine places 3 identical cards
| nibnalin wrote:
| 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).
| Gehinnn wrote:
| We still don't know if the universe allows us to do that. If
| P=NP ZKPs are worthless.
| 5b43d64b6f77 wrote:
| 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.
| mirekrusin wrote:
| Nice one, let's call it intentional deeper meaning saying you
| shouldn't roll your own zero-proof knowledge crypto
| implementation.
| dvt wrote:
| 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(l) and the soundness probability to
| negl(l) 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
| Dylan16807 wrote:
| > 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.
| saurik wrote:
| 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.
| c0742e9366 wrote:
| 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.
| frazbin wrote:
| 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.
| ransom1538 wrote:
| 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.
| baby wrote:
| Note that it's true for any cryptographic algorithm.
| JofArnold wrote:
| 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
___________________________________________________________________
(page generated 2021-12-02 23:00 UTC)