Bulletproofs – Short zero-knowledge arguments of knowledge | Hacker News Reader

Bulletproofs – Short zero-knowledge arguments of knowledge

github.com

185 pointsrwosync60 comments

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 extraordinarily simple: take a piece of cardboard larger than the Where's Waldo book, make a small, Waldo-sized cutout, and position the cardboard in a way that only Waldo himself is visible. As long as you don't give away the position of the book underneath the cardboard, you can prove you've found Waldo without providing _any_ information as to where he is! It's pretty great.

Would love to know of other real world examples. :-)

[1] https://en.wikipedia.org/wiki/Zero-knowledge_proof#The_Ali_B... [2] http://www.wisdom.weizmann.ac.il/%7Enaor/PAPERS/waldo.pdf

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.

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

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.

No that's not the thing about it. The thing is you put the cardboard over the book then show it to the other person.

The other person won't know where Waldo is, because the cardboard is much bigger than the book, so Waldo could be anywhere on the page.

The cardboard would need to be at least twice the dimensions. Otherwise it's possible that the book could be seen past the edges.

That’s not what OP was referring to. OP was saying the hole still reveals a little information (Waldo’s Size/shape/posture) to the opponent.

Twist the example in the paper a bit, to create a shape of Waldo's face and show only Waldo's face.

Do note, the information we are concealing is where Waldo is, and not how he looks.

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.

>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_ actually is even after Peggy proves she knows it: the first Wiki paragraph seems to emphasize this with "(the prover Peggy) can prove to another party (the verifier Victor) that she knows a value x, without conveying any information apart from the fact that she knows the value x."

(2) outside world (other than Victor) has zero knowledge that _Peggy_ knows what X is: the later Wiki paragraph is "Further notice that if Victor chooses his A's and B's by flipping a coin on-camera, this protocol loses its zero-knowledge property; the on-camera coin flip would probably be convincing to any person watching the recording later. Thus, although this does not reveal the secret word to Victor, it does make it possible for Victor to convince the world in general that Peggy has that knowledge—counter to Peggy's stated wishes."

Is the "zero knowledge" referring to keeping _X_ a secret , or is it keeping the fact that _Peggy_knows_X_ a secret, or are both secrets together required? The wikipedia article isn't clear on that so the article probably needs some revision to be more explicit.

(For some, an example of a ZKP would be email address verification for new user accounts: Vimeo(verifier) sends an email with a generated numeric code and Peggy(prover) has to enter that number in the webform to activate the account. This proves that Peggy "knows the secret password of that email account" but Vimeo still has "zero knowledge" of her email password. For this particular example, it doesn't matter that that the whole world knows that Peggy knows the password to her peggy@gmail.com so condition (2) is not a strong requirement.)

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 the "zero knowledge" refers to. Whether Peggy's account is compromised or wiretapped by man-in-the-middle attacks, Vimeo/verifier still has zero knowledge of her email account's password.

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

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.

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.

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

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

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.

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 knowing exactly how many leaves are on a tree just by looking at it. How can you verify this without actually having to count an entire tree's worth of leaves?

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!

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

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.

How does she do that?!

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.

Isn’t this very similar to the classical magic word door example, assuming the password is stored as some hashed value?

E; not really

Thank you for this

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 a relatively new library for doing bullet proofs written in Haskell -- the README might benefit from more disclaimer about the verification steps taken and analysis of side channels for the library (probably not ready for production)

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/

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.

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

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

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.

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

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

There is also an implementation by Andrew Poelstra (one of the Bulletproof authors) in a PR to the secp256k1-zkp repository: https://github.com/ElementsProject/secp256k1-zkp/pull/23

See also original Blockstream paper (pdf): https://eprint.iacr.org/2017/1066.pdf

The primary innovations are not really from the Blockstream folks, but from the graduate students involved: Benedikt and Jonathan

More UCL and Stanford but okay

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.

Just out of curiosity, do you actually use adjunctions? If so I would be really happy to know more about it.

Ugh, I'm cringing a little that they consider adjunctions 'advanced mathematics'. Adjunctions are ubiquitous even in elementary math. For example, in linear algebra whenever one writes down a matrix to represent a operator in some basis, this is using the tensor-hom adjunctions for modules.

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

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.pdf, on blinding in RSA.

Interesting, thanks!

More about bulletproof in context of Uplink. https://www.adjoint.io/docs/privacy.html#upperlink

for those who don't know, Monero is using bulletproofs.

Not yet.

A hard fork later this fall is expected to bring Bulletproofs to main net. Right now the code is being vetted by 3 external auditors, hired by the community through fund-raising.

The benefit to Monero, once this is implemented, is transactions that are almost an order of magnitude smaller. This is a huge win, for many reasons, and it doesn't even come at the cost of CPU time.

What is difference between Bulletproof and zk-SNARK (of ZCash)? Any advantage?

Reply on news.ycombinator.com