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

Bulletproofs – Short zero-knowledge arguments of knowledge

github.com

Post reply on HN
Print view View original

41–50 of 63 posts

Re: Bulletproofs – Short zero-knowledge arguments of knowledge

#41

Post by edanm »

lccarrasco wrote: post #40
edanm wrote: post #35

Earlier quoted context omitted.

I also really love the Waldo example, and give it often. Just FYI (as noted by SilasX in other comments), this is not officially a Zero Knowledge proof, since you're "proving too much" (people who are not the verifier will "know that you know", which is not allowed in ZKPs). Btw, another favorite of mine which I often give as a riddle (not a ZKP, but an interactive proof): Assume I claim to have the superpower of kno…

rot13'd to avoid spoilers Vf vg ol erzbivat n pregnva ahzore bs yrnirf naq nfxvat sbe gur gbgny pbhag ntnva, gura fhogenpgvat obgu naq pbzcnevat gur qvssrerapr?

Yep.

Also rot13'd:

Lbh erzbir n xabja (gb lbh) ahzore bs yrnirf juvyr zl onpx vf ghearq, gura nfx zr ntnva. Gura lbh pna frr vs guvf ahzore vf pbeerpg. Lbh pna ercrng guvf nf znal gvzrf nf lbh yvxr.

Lbh pna "fvzcyvsl" guvf ol whfg pubbfvat rnpu gvzr jurgure gb erzbir n yrns be abg, gura nfxvat zr vs lbh qvq be abg. Gura vg'f rnfl gb frr gung gur cebonoyl bs trggvat guvf evtug a gvzrf vf 1/2^a.

Re: Bulletproofs – Short zero-knowledge arguments of knowledge

#44

Post by lccarrasco »

edanm wrote: post #41
lccarrasco wrote: post #40

Earlier quoted context omitted.

rot13'd to avoid spoilers Vf vg ol erzbivat n pregnva ahzore bs yrnirf naq nfxvat sbe gur gbgny pbhag ntnva, gura fhogenpgvat obgu naq pbzcnevat gur qvssrerapr?

Yep. Also rot13'd: Lbh erzbir n xabja (gb lbh) ahzore bs yrnirf juvyr zl onpx vf ghearq, gura nfx zr ntnva. Gura lbh pna frr vs guvf ahzore vf pbeerpg. Lbh pna ercrng guvf nf znal gvzrf nf lbh yvxr. Lbh pna "fvzcyvsl" guvf ol whfg pubbfvat rnpu gvzr jurgure gb erzbir n yrns be abg, gura nfxvat zr vs lbh qvq be abg. Gura vg'f rnfl gb frr gung gur cebonoyl bs trggvat guvf evtug a gvzrf vf 1/2^a.

Ohhh, that's cool, thanks for sharing!

Re: Bulletproofs – Short zero-knowledge arguments of knowledge

#45

Post by mehrdadn »

zodiac wrote: post #27
mehrdadn wrote: post #20

> They rely on the discrete logarithmic assumption > Range proofs do not leak any information about the secret value Could someone explain this? I can't say I followed the proof algorithm (don't have background on blinded Pederson commitments etc.), but to me these sound contradictory. If you're relying on a discrete log assumption then it means you are leaking information, but you hope it's not enough information to…

The does-not-leak-information property doesn't depend on the discrete log assumption, but the binding property does. I.e., if you have an oracle that solves the discrete log problem you can now open commitments in different ways, but if someone else generates a commitment you still can't tell what their secret input was. One thing I found useful is section 2.2 of https://crypto.stanford.edu/~dabo/papers/RSA-survey.pd…

Interesting, thanks!

Re: Bulletproofs – Short zero-knowledge arguments of knowledge

#46

Post by throwawaymath »

hackathonguy wrote: post #37
hackathonguy wrote: post #6

Zero knowledge proofs are fascinating - as a non-mathematician, I particularly enjoy real-world examples. Two famous examples ("The Ali Baba Cave" and the "Two Balls and the Color Blind Friend") appear in the Wikipedia article on zero knowledge proofs [1]. My favorite, however, is this paper [2] on convincing another person you've found Waldo, without revealing his location and therefore ruining the game. It's extrao…

Just thought of another ZKP - my niece can prove to me that she knows the password to a device by logging in, without me ever knowing the password myself.

Technically speaking that's not a zero knowledge proof, because it requires what would be considered a trusted third party (the service being logged into). Ostensibly that service "knows" the password (or a functional substitute), and the prover is only proving password possession insofar as the third party service can be trusted.

In your Where's Waldo example, this would be like having a non-playing third participant whose trusted by both players. When one player wishes to prove they've found Waldo without ending the game for the other play, they'd demonstrate this in full transparency to the third party verifier, whose word would then be trusted by the second player.

Re: Bulletproofs – Short zero-knowledge arguments of knowledge

#47

Post by throwawaymath »

tomaha wrote: post #13
pas wrote: post #8

Earlier quoted context omitted.

Maybe you can show only Waldo's face?

The Waldo zk proof isn't a good example. You can easily fake knowing where Waldo is by gluing a Waldo to the board you use to hide the book. That way you can even proof you know a solution for a picture that doesn't even have Waldo in it.

It's a perfectly fine example! It doesn't have to be academically rigorous, it just has to demonstrate the basic idea of proving a thing without exposing the thing. Yes, obviously it's not actually a formal ZKP, but analogies are imperfect.

Re: Bulletproofs – Short zero-knowledge arguments of knowledge

#48

Post by infogulch »

zodiac wrote: post #26
infogulch wrote: post #14

Earlier quoted context omitted.

How is that possible? Bitcoin's whole premise is a globally verifiable balance of each address after each block (aka public ledger). I could see this being very helpful for new crypto currencies, but Bitcoin is pretty set in stone on this matter, no?

Well, the verification guarantees you want out of a public ledger for currency are weaker than that (no money is created out of thin air, the person you're receiving money from actually has enough money to send to you, etc). I'm not sure anyone is philosophically attached to "all balances are visible".

Ok yes, in a single transaction you can prove to everyone else that the net exchange is zero, but how do you prove that you have enough money to send to them? That's global state that depends on all past transactions, even if they're hidden. Include more ZKPs for every transaction ever associated with that address? You have to prove that 1. you received enough to cover it and 2. you haven't spent it already.

Just slapping some ZKP on top of bitcoin is not enough to make it magically private. It needs deeper integration to the model than that.

Re: Bulletproofs – Short zero-knowledge arguments of knowledge

#49

Post by windows_tips »

jasode wrote: post #36
windows_tips wrote: post #31

Earlier quoted context omitted.

Email is a plaintext protocol, so having a number in an email really just means that you saw the email, not that you know Peggy's password.

Right. It's not irrefutable proof beyond all standards of doubt but it's "enough proof" to Vimeo/verifier that Peggy controls that email account. Whatever arbitrary threshold of proof it is, it's in in the eye of the beholder (the verifier). It's up to Vimeo to arbitrarily decide that getting a matching number is "verifying" Peggy's email account. Instead of the "proof" aspect, the email example is highlighting what…

If Peggy has to use the password since recieving the email, vimeo could put bounds on the password length, at least.

Re: Bulletproofs – Short zero-knowledge arguments of knowledge

#50

Post by gnarcoregrizz »

edanm wrote: post #34
SilasX wrote: post #10

Earlier quoted context omitted.

Hey! I independently came up with the Where’s Waldo protocol right here on Hacker News! https://news.ycombinator.com/item?id=15323790

Oh wow! It looks like you attempted to avoid the problem with the original Waldo solution (namely, that's it not completely zero-knowledge since you can't fool outsiders.) I'm not 100% sure I understand your protocol though. You're putting a fake picture that has Waldo in it beneath the cardboard? So that you can always punch a hole to reveal Waldo? How does that prove anything? I'm not sure what I'm missing here.

Well his example does break down since it is supposed to have a protocol, and the prover could fake it by showing him a fake waldo. To make it a ZKP, The person requesting the proof would need to know exactly what waldo looks like (possibly reconfiguring/redrawing him himself), but doesn't know where he is. He hands the prover the new picture, and he proves it by showing the cutout with the exact rendition of the new waldo. Repeat n times with new waldos to reduce the likelihood of getting a lucky guess. I'm not sure but I think this sounds closer.
Post reply on HN