Bulletproofs – Short zero-knowledge arguments of knowledge • Hacker News Board

Re: Bulletproofs – Short zero-knowledge arguments of knowledge

#51

Post by phyzome » Thu, Jul 12, 2018, 4:13 PM UTC

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.

I was stumped at first, but then I changed my approach:

Vs fbzrbar unf guvf novyvgl, gura gurl'er abg whfg rfgvzngvat -- gurl xabj gur rknpg ahzore. Gung zrnaf gurl pna gryy gur qvssrerapr orgjrra n gerr jvgu gubhfnaq yrnirf if. n gubhfnaq naq bar...

...naq gung'f jura vg uvg zr. :-)

Re: Bulletproofs – Short zero-knowledge arguments of knowledge

#52

Post by SilasX » Thu, Jul 12, 2018, 4:26 PM UTC

jasode wrote: post #23

SilasX wrote: post #11

Earlier quoted context omitted.

One quirk about ZKPs is that they must be convincing only to the verifier[1]. If you know which entrance they used, it’s convincing to everyone , not just the verifier.[2] If you don’t know which entrance they used, than anyone besides the verifier can remain a Doubting Thomas: “okay, cool, your verifier came out B, then B, then A. So? You could just as well have conspired with them to start out at B, then B, then A!…

>One quirk about ZKPs is that they must be convincing only to the verifier[1]. I think the parent's question is about what the "zero-knowledge" actually refers to. (scrollaway asked, "Does Victor knowing the initial path make it non-zero-knowledge?" ) The Wikipedia writing in 2 different places makes it confusing. For Peggy's secret password X, the "zero knowledge" might mean: (1) Victor has zero knowledge of what _X…

The definition of ZKP is (1), but that implies (2), as explained in this paragraph from the Wikipedia article:

>For zero-knowledge proofs of knowledge, the protocol must necessarily require interactive input from the verifier, usually in the form of a challenge or challenges such that the responses from the prover will convince the verifier if and only if the statement is true (i.e., if the prover does have the claimed knowledge). This is clearly the case, since otherwise the verifier could record the execution of the protocol and replay it to someone else: if this were accepted by the new party as proof that the replaying party knows the secret information, then the new party's acceptance is either justified—the replayer does know the secret information—which means that the protocol leaks knowledge and is not zero-knowledge, or it is spurious—i.e. leads to a party accepting someone's proof of knowledge who does not actually possess it.

That is, if the proof were convincing to the entire world, then non-possessors of the knowledge could just replay they proof without having the knowledge.

Re: Bulletproofs – Short zero-knowledge arguments of knowledge

#53

Post by SilasX » Thu, Jul 12, 2018, 4:29 PM UTC

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.

The idea is that a prover puts the original page at some random position behind the screen. The verifier randomly decides to force you to punch the hole or remove the screen, but not both. The possibility of doing the latter is what weeds out frauds who try to cheat by not using the original page (or inserting fake Waldos).

Re: Bulletproofs – Short zero-knowledge arguments of knowledge

#54

Post by SilasX » Thu, Jul 12, 2018, 4:33 PM UTC

gnarcoregrizz wrote: post #50

edanm wrote: post #34

Earlier quoted context omitted.

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…

The model of the WW problem assumes you know what Waldo looks like (but not where he is), so that part is taken care of.

Under the protocol I gave, you can’t cheat by using a fake Waldo, because each time there’s a fifty percent chance the prover will ask you to remove the screen, which would reveal you’re not using (only) the original page.

(Keep in mind you do the protocol many times with a new position in each one.)

Re: Bulletproofs – Short zero-knowledge arguments of knowledge

#55

Post by gnarcoregrizz » Thu, Jul 12, 2018, 4:43 PM UTC

SilasX wrote: post #54

gnarcoregrizz wrote: post #50

Earlier quoted context omitted.

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…

The model of the WW problem assumes you know what Waldo looks like (but not where he is), so that part is taken care of. Under the protocol I gave, you can’t cheat by using a fake Waldo, because each time there’s a fifty percent chance the prover will ask you to remove the screen, which would reveal you’re not using (only) the original page. (Keep in mind you do the protocol many times with a new position in each one…

I see, that makes more sense

Re: Bulletproofs – Short zero-knowledge arguments of knowledge

#56

Post by SilasX » Thu, Jul 12, 2018, 6:47 PM UTC

SilasX wrote: post #10

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…

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

Late follow-up: I didn't read carefully; I actually came up with a different protocol that improves upon it and makes it actually zero-knowlege, by only being convincing to the verifier, and which prevents you from cheating with a fake Waldo.

Re: Bulletproofs – Short zero-knowledge arguments of knowledge

#57

Post by jlrubin » Thu, Jul 12, 2018, 7:59 PM UTC

infogulch wrote: post #14

jlrubin wrote: post #4

Bulletproofs are significant because they allows you to check that the amount being input and output in a Bitcoin transaction is correct without revealing the amounts to non-parties to the transaction. The size of a bulletproof is small enough (and they grow with O(c + log n)) that for transactions with a couple inputs and outputs, there is minimal overhead compared to a unblinded transaction. The link provided is to…

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?

These are publicly verifiable, they are just not plaintext values anymore. This isn't so weird -- think about what a signature is, it's a proof that I know a private key without plaintext revealing the key.

Re: Bulletproofs – Short zero-knowledge arguments of knowledge

#58

Post by jlrubin » Thu, Jul 12, 2018, 8:00 PM UTC

infogulch wrote: post #48

zodiac wrote: post #26

Earlier quoted context omitted.

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 sla…

You take the commitments from the outputs and use them in the next proof.

It is possible to soft fork confidentiality into Bitcoin, see https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016... for example

Re: Bulletproofs – Short zero-knowledge arguments of knowledge

#59

Post by jlrubin » Thu, Jul 12, 2018, 8:03 PM UTC

tromp wrote: post #19

jlrubin wrote: post #4

Bulletproofs are significant because they allows you to check that the amount being input and output in a Bitcoin transaction is correct without revealing the amounts to non-parties to the transaction. The size of a bulletproof is small enough (and they grow with O(c + log n)) that for transactions with a couple inputs and outputs, there is minimal overhead compared to a unblinded transaction. The link provided is to…

In a Mimblewimble [1] blockchain, values are hidden inside Pedersen commitments, blind * G + value * H, and inputs can be seen to match outputs of a transaction if the latter minus the former is of the form blind*G (the difference in value is 0). But this form is a public key that the transactors can produce a signature for! This is way simpler than a bulletproof. BUT, bulletproofs are needed to show that the output…

Correct -- the bulletproofs are only for the range proofs, but thought that was a bit too involved for my tldr :)

Re: Bulletproofs – Short zero-knowledge arguments of knowledge

#60

Post by antpls » Fri, Jul 13, 2018, 7:52 AM UTC

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

> I'm not sure anyone is philosophically attached to "all balances are visible".

I don't know either about others, but to me it looks like hiding balances is a regression. Why would you hide your balance, unless you want to lie about it?

I can't think of a reason hiding balances would be better, but I don't have a degree about economy so I'm open to explanation.

Same argument than personal privacy I guess, but here we are talking about currency, not personal political opinions or personal identifyable information.