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

11–20 of 63 posts

Re: Bulletproofs – Short zero-knowledge arguments of knowledge

#11

Post by SilasX »

scrollaway wrote: post #9
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…

What am I missing about the Ali Baba cave proof? Why does Victor ever need to hide which entrance she takes at first? (In fact this is brought up in the last paragraph with no reason as to why it's not the entire proof). Does Victor knowing the initial path make it non-zero-knowledge? Because if so, the example feels super contrived. I agree your Waldo example is much better.

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!”[3]

I elaborated on an earlier HN discussion: https://news.ycombinator.com/item?id=15323790

[1] The verifier, for purposes of this point, is anyone who contributed to the generation of the random bits that decided which random challenge to present.

[2] In some cases, you do want it to be convincing to everyone, but that’s not the “standard” kind of ZKP.

[3] In the jargon, a valid transcript for a ZKP must be efficiently simulable by someone who lacks the relevant knowledge.

Re: Bulletproofs – Short zero-knowledge arguments of knowledge

#13

Post by tomaha »

pas wrote: post #8
AstralStorm wrote: post #7

Earlier quoted context omitted.

By that you mean someone wake who also found Waldo can verify if the shape matched. It still slightly ruins the game as you know the shape you're looking for now. This is why one way functions are used instead.

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.

Re: Bulletproofs – Short zero-knowledge arguments of knowledge

#14

Post by infogulch »

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?

Re: Bulletproofs – Short zero-knowledge arguments of knowledge

#15

Post by dtseng123 »

darkkindness wrote: post #5
dbranes wrote: post #3

Tangent: I like that the logo for the organization 'adjoint' resembles the notation for adjoint functors.

Likewise! Looks like it was intentional: > Our name comes from advanced mathematics and represents the numerous ways in which we simplify financial processes and products using blockchain technology. ( https://www.adjoint.io/about/adjoint )

It was very intentional.

Re: Bulletproofs – Short zero-knowledge arguments of knowledge

#16

Post by askmike »

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?

I don't think this will ever be hardforked into bitcoin, but there are other ways of getting this in, such as via sidechains (see liquid[1] for example).

[1] https://blockstream.com/liquid/

Re: Bulletproofs – Short zero-knowledge arguments of knowledge

#18

Post by hackathonguy »

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.

This can easily be remedied by having the verifier ensure the prover is in an empty room, equipped with only cardboard and scissors.

Re: Bulletproofs – Short zero-knowledge arguments of knowledge

#19

Post by tromp »

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 values are in a certain range, to prevent overflow in value arithmetic.

[1] https://www.youtube.com/watch?v=BMiM0rabRjc

Re: Bulletproofs – Short zero-knowledge arguments of knowledge

#20

Post by mehrdadn »

> 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 reconstruct the secret. It doesn't sound like an algorithm that truly doesn't leak information (like OTP).

Post reply on HN