Hacker News new | past | comments | ask | show | jobs | submit login
Zero Knowledge Proofs applied to Auctions (2019) [pdf] (csail.mit.edu)
122 points by kkm 36 days ago | hide | past | favorite | 15 comments

This is not a peer-reviewed research paper. It seems to be a project report likely done by undergraduates. The paper is full of typos and it is not clear what the specific novelty of the proposal is (if there is any).

> This is not a peer-reviewed research paper. It seems to be a project report likely done by undergraduates. The paper is full of typos and it is not clear what the specific novelty of the proposal is (if there is any).

This is not a constructive comment.

The URL suggests this is a final(?) project paper for MIT's 6.857: Computer and Network Security course. The paper seems appropriate in style and length for this kind of setting.

When I clicked the link, I figured this would be a research paper from MIT. It took me a bit of reading to figure out it was just a student project report. That's why I posted the GP.

I stand by my comment that there doesn't appear to be anything particularly novel about this work. Especially with crypto it is important to stick with well-studied and well-understood primitives. There's a danger that someone looks at this and assumes it is being endorsed by MIT and implements it in their system.

This is a misapplication of that principle and runs the risk of turning into the toxic gatekeeping that I know first hand has kept many talented people out of the academic cryptography community. The authors of this work implement their system using existing proof of concept zkSNARK libraries that have been developed by researchers studying this area for roughly a decade or more. They are not rolling their own crypto and are guided by top notch cryptography researchers at MIT (albeit in a course setting).

Even supposing that there is a dangerous time to experiment with application with proof of concept work, this really isn't the case for zero-knowledge proof (or more specifically, zk-SNARK) systems right now. I have been in this field for many years and the chief complaint that I have heard many researchers have is that the tooling exists, yet people are not making heavy usage of it outside of ZCash. This, thankfully, has become less true within the last year or two. This work, even if it is written by students, is nice to see given this reality and can give researchers trying to optimize these development tools necessary feedback to improve them.

To put this into a larger research context, keep in mind that various funding agencies have probably spent at least $1 billion on FHE, ZKP, and similar novel crypto research in the last decade. Off the top of my head, this includes DARPA, ONR, NSF, and many more. The biggest barrier this area currently faces is fine tuning these tools to be performant and accessible to non-research level security engineers and developers. This includes determining which applications this technology may be useful for and where, if applied, it is surprisingly not useful. This is why there are continuing (multi-million $) programs to directly target these problems (DARPA SIEVE and IARPA HECTOR for example). This work by MIT students is, at least on the surface, a potentially useful datapoint that we can use to inform our decisions going forward (I personally would like to know more about their development experience using the tools).

Your point about the need to "popularize" zk-snarks etc. is well-taken and I upvoted you for it.

But that said, we seem to be talking past each other at this point. I don't see why my criticism of the OP was unconstructive. This is not actually a research paper, it has not undergone any sort of academic peer review, and if the goal is to present it as one example of the kinds of things that are possible to build with zkSNARKs, then it ought to be presented in that context.

I do want to note that it is possible to compose zkSNARKs in an application in ways that result in the composition not being zero-knowledge. Not saying that has happened here, but implying there's no danger with incorrect usage of zkSNARKs seems sketchy to me.

Has anyone figured out how to play simple games with ZKPs? I’ve seen the sudoku paper but looking for other ones

There's lots of stuff in the literature about playing games with ZKPs. Shameless plug: I've been writing a framework for writing card games (or any game that could potentially be emulated with cards, e.g. flipping coins or rolling dice): https://github.com/rmartinho/pbmx

What do you mean by 'play'?

ZKP's let you prove some fact without disclosing the details. "I know an input that makes this program return true".

While you could construct an unusual game that made use of them, they don't generally map into the framework of "play".

Try one night ultimate werewolf... except that kind of breaks the game

It was not clear to me why they are doing a zk-proof for each losing bid and not just to the winning bid. Probably it could save a lot of resources.

Because there's no proof that can be made for the winning bid on its own. The property that needs to be proven (with ZK) is that "all losing bids were strictly worse than the winning bid". That can't be shown (or even stated) without referring to the losing bids. The one-proof-per-losing-bid itself is probably just an implementation detail, but ultimately all the losing bids must be considered.

Isn't a losing bid simply a winning bid of 0 items?

I understand the system can create proofs for all participants, but that's the point: a losing bid does not receive the reward (or it is 0).

Then I think it could be easier to spend resources to prove just the winner (who got something).

It is an implementation detail and performance tuning. The whole thing is very interesting overall.

I don't think you understood. You need a proof for all participants, because otherwise the statement you are trying to prove is meaningless.

There is no statement involving just the winner that verifies the authenticity of the auction. You cannot say "the winner won", because "the winner" is a term that only makes sense in terms of all the auction losers. There must be proofs involving all the participants, because you at the very least need to show that all the losing bids were strictly worse than the winning bid.

"prov[ing] just the winner" doesn't make any sense, or really mean anything.

Yes, I got the point. The approach is every bidder doing the zkproof to create a receipt of their bid because the auction will end at some point in the future. I understand it works very well, and it is the most used approach.

I was wondering about the possibility of another approach and my point was creating just the winner zkproof on the auction side (not bidder side), at the end of the auction. If all the bidders used some stealth method plus homomorphic encryption, the bids could be hidden and maybe they could receive the 'winner zkproof bid receipt' and check it against their very own bid. Then the winner could be able to prove it being the owner of the keys who delivered the stealth bid which won the auction.

I read the paper again and understood their approach. It is clear why they are doing the zkproof for every participant in that context.

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact