9 ms·

Show HN: Simple Zero-Knowledge Proof Treasure Hunt Game

82 points by mattdesl 5y ago

nicexe 5y ago
Nice demo. I found up to "harder". I assume you would need to bruteforce to find the "impossible". proof: {"proof":{"A":["1867600411780067514172598894560508538153359060380045576693586005748057954966","2169620374930453391614857867828473542574014121006630399026967709955925850380","1"],"B":["19528498564528468902521634480986489044663227437233934360035138487189177722814","706337827303094147746432169922700503982765234262612631196531687654713865722","1"],"C":["3726874825357289054925101646028211344121805780590499285615367952100310015198","16413790865300145964228939489264611981079279422219583850941964454619012987205","1"],"Z":["13348398295372116628737687800239385003236584392082957129655537090979023752552","21858938086065692615790404191021275401630119897894808135127612791495958708375","1"],"T1":["14360876145883521049062480571414414707162979629186454824314165195068098843755","7690383252743723537382002605037505508108694574090623371839489928167967159302","1"],"T2":["171526585437306849736171820938322340084660417215376900416315101905819784325","14860073408830920977059163351151904508851804307761461334115941048614121404124","1"],"T3":["1545121168750639889943334802450434695241204658831402130294781806168831416544","3552441256981354095031652913768122490293154222496855043326406989226641931070","1"],"eval_a":"11024792588659243456083103589833329966520500410691012025757085783760664829419","eval_b":"8139322387519291544452196793779464185899888022676212695935483571119961089263","eval_c":"2759381562617869781993539883850313928775692869004537050116210023174425255732","eval_s1":"3982161546082334136949334514760679925162813832987926352276128359736663202279","eval_s2":"13722404104721347388598646963457682656505421852782227871567200092865223175205","eval_zw":"11818614898752314321908019464035292475883958508517334670201070690246297959919","eval_r":"351033371214975959271810948327526637663211703371176137228232410629160426468","Wxi":["2849642276594154825911327435597652863159285743523681959629445273984338402763","17443880865908727420293433216572018364053739032965083704472720153118177741102","1"],"Wxiw":["10956474329499098723358633860519149253944380573151016916071333176886419683119","10706455989148992485159392381934694626464450509616938982009682610544795496695","1"],"protocol":"plonk","curve":"bn128"},"publicSignals":["14870881943777737729426810002848629979047457360865816386884132744016829330171","5"]}
- dfdz 5y ago
  I did verify that you found the "harder" treasure, but I am not sure this is a good example of zero knowledge proof. The author claims that > you can Download the JSON Proof file, and share that publicly. It does not reveal any information of the coordinates you discovered. But it is not at all clear that the proof does not reveal any information of the coordinates you discovered. Similarly, it is also unclear that the JSON actually proves that you found the treasure. For example, there could be a specific string in the JSON that the program is checking It is a cool example of coding, but not of zero knowledge proof in my opinion
  - cvoss 5y ago
    Are you doubting that the application implements the zk-SNARK algorithm correctly? Or doubting that the application actually running on the server is the same as the one in the publicly available source code? Or something else? The first doubt could be eliminated by an expert investigating the source code. The second doubt is more interesting to me. I wonder how that one could be dispelled.
    - zamadatix 5y ago
      I don't think anything is being doubted just dumps you the numbers and tells you it is so without explaining why or how making for a weak example.
    - chrisco255 5y ago
      The entire end-to-end source code (backend and frontend) is available at: https://glitch.com/edit/#!/zk-treasure-hunt?path=README.md%3A1%3A0 https://glitch.com/edit/#!/zk-treasure-hunt?path=README.md%3... . It's a full-stack Glitch example, so you can browse all the code, and fork it and edit it.
    - mattdesl 5y ago
      Just fwiw the demo runs client side as a static site - no server is really needed for proof generation or verification. In a more ideal scenario the code and prover/verifier would all be running in a decentralized fashion (see zk-evms and StarkNet for example).
cvoss 5y ago
It's not mentioned on the website, but, empirically, at least, I see the generated proof file is different if you find the same treasure multiple times. That means if someone snoops my machine and tries to use my proof to claim that they know the answer, I can spot it as a stolen proof. However, without revealing the treasure, I wouldn't be able to prove that they stole it, because it is equally possible that I stole it from them. I wonder if there could be a mechanism for cryptographically incorporating an owner's identification into the ZKP so that I could prove that it was stolen in the above scenario? The ZKP would need to remain publicly usable so that others can verify that it's a valid proof without me, but some aspect of it would be unlockable only by my private key so that I can demonstrate that I hold said key. Does such a mechanism exist?
- deleted 5y ago
  [deleted]
- skulk 5y ago
  You could use [trusted timestamping](https://en.wikipedia.org/wiki/Trusted_timestamping https://en.wikipedia.org/wiki/Trusted_timestamping) to prove that you're the one who first created that proof.
- pepesza 5y ago
  > Does such a mechanism exist? Sign the puzzle solution with your private key. Check signature inside the circuit. This obviously can't be applied to this particular game since it has a circuit that does not employ such measures. Alternatively, if used snark is recursive - create a new circuit that will both validate original proof and check the signature.
- zamadatix 5y ago
  In a pure sense don't think so in this case since it's a non-interactive zero-knowledge proof, would love to be wrong about that though. For a more practical approach though get your copy of the unique zero-knowledge proof signed by a trusted source first and that should do. Could be a trusted 3rd party or even a large blockchain. Or just switch to interactive zero-knowledge proofs in the first place.
can16358p 5y ago
I have the feeling someone's going to put this game on blockchain with token rewards.
- mattdesl 5y ago
  (author here) totally - and unironically. there is a lot to explore within the space of using zk proofs to mitigate sybil attacks, vote buying and botting in terms of governance tokens, NFT auctions and the like. also the benefit of decentralization and true verifiability which this demo does not offer.
  - can16358p 5y ago
    Interesting. Genuine question: how does zk proofs mitigate against Sybil attacks especially in crypto space? Regardless of that, great work!
    - mattdesl 5y ago
      I'm not sure ZK proof alone solves this, but seems integral to Sybil resistant systems that operate on personhood/identity, as it allows you to prove your identity (or that your personhood meets some criteria, like an age limit) without revealing any additional information about yourself. See [1][2]. A contrived example is an NFT drop that only allows you to claim 1 token per identity proof. [1] - https://blog.cloudflare.com/introducing-zero-knowledge-proofs-for-private-web-attestation-with-cross-multi-vendor-hardware/ https://blog.cloudflare.com/introducing-zero-knowledge-proof... [2] - https://eprint.iacr.org/2019/546 https://eprint.iacr.org/2019/546
abalaji 5y ago
The project mentions that it uses snarkjs and I thought I'd link it directy here. [1] What's interesting in the setup of these systems is the "Powers of Tau" ceremony which, in a decentralized manner (using secure multi-party computation), avoids the "trusted setup" problem in non-interactive variants of zero knowledge proof systems like this one. [2] [1] https://github.com/iden3/snarkjs https://github.com/iden3/snarkjs [2] https://github.com/weijiekoh/perpetualpowersoftau https://github.com/weijiekoh/perpetualpowersoftau
deleted 5y ago
[deleted]
relaunched 5y ago
This doesn't seem like a zero knowledge proof to me. It seems like, for this to work, you have to have a prover, a validator and a 3rd party. By revealing the authentication to the validator, you are providing them information. I know where something is on the grid, check these coordinates, and if it's there, give me a yellow hat...that is easy. If I see you have a yellow hat, I know that you know where the thing is. If I could prove that without disclosing the actual coordinates, that seems more zero knowledge to me. An example might be if you overlay a layer on the infinite plane, blacked out all, on the transparent layer, save a one by one square, and aligned it to the spot that had the easy emoji. Thereby, I prove to you I know where the easy emoji is, without giving any info regarding where it sits in the plane. However, this isn't my field - just my thoughts.
- mattdesl 5y ago
  The demo does not disclose any coordinates—only verifies a proof that you know the coordinates. Not even the demo knows the coordinates of a valid proof that you submit (check the source - there are no coordinates present).
  - relaunched 5y ago
    I'm not sure why that matters. By inputting coordinates, you have giving extra information. There is a difference between verifying that someone knows the coordinates and sharing the actual coordinates. This particular system seems to function like an IDP. Where, upon authentication and token is issued, and the 3rd party checks the token's validity. I'm not sure that is the same as zero-knowledge.
    - mattdesl 5y ago
      The project can be downloaded and run locally (it is a static client side website, no server) and the proof generation and verification can be run offline, without the coordinates ever being sent over the network. Only the proof file needs to be sent between the two parties. I suppose the system itself acts as a “third party” but at no stage does it require you to share the coordinates with one another, hence zero knowledge. :) Does that make sense?
mattdesl 5y ago
Hi HN! Author here, this is my first experiment with circom and snarkjs, I wanted to do something basic that shows a small sample of their potential. :) Comments & questions welcome!
- eruleman 5y ago
  The website is stuck on “searching” for me? Is this expected?
  - mattdesl 5y ago
    It doesn't seem to work on mobile (maybe a limitation of snarkjs)—I've been testing only on macOS Chrome.
  - amflare 5y ago
    If you try to input a number longer than 10 digits in either field it'll break and you have to refresh. You can see the error in the console. Its not stuck on searching, it just never reactiviated the button since it broke prior to that in the flow.
aib 5y ago
I think there is an impedance mismatch in how easy the game is to understand versus how the ZK proof part has required reading. Some (if not most) of the questions or comments here must sound silly to someone knowledged in the field. Anyway, here is mine: How is the proof different than a signed message saying "This person has found the treasure"? With the private key derived from the coordinates? Anyway, I'm off to read more about ZK proofs in hopes of making the above sound silly to me.
- minism 5y ago
  I haven't looked at the game implementation in detail yet, but in order to verify "This person has found the treasure" is signed with the key for coordinates (X,Y), we need to know the cooresponding public key for coordinates (X,Y), which means that youre revealing the coordinates themselves in your message. The idea in ZKP is to prove you know a value without revealing the value itself.
  - aib 5y ago
    I don't know how actual asymmetric KDFs work, but I was thinking more along the lines of secret -> private key -> public key, i.e. the public key doesn't contain information about the secret.
- mattdesl 5y ago
  Thanks! You may be correct in that this application could be better achieved with a simple signed message—this is my first time playing with ZK proofs. The main issue is that the circuit is simply hashing the coordinates and the resulting hash is being used to identify the treasures. So it is already fairly similar to the scenario you describe, but in an ideal ZK system it would not even reveal a hash of the coordinates, only verifiable knowledge of them. For example, I _think_ it might be closer to true ZK if I had hardcoded an equality check with exactly (5, 10) coordinates into the ZK circuit, rather than using hashes to support a variety of coordinates (but then it wouldn’t be as general purpose). Perhaps there’s another better way though!

82 points by mattdesl 5y ago

Nice demo. I found up to "harder". I assume you would need to bruteforce to find the "impossible". proof: {"proof":{"A":["1867600411780067514172598894560508538153359060380045576693586005748057954966","2169620374930453391614857867828473542574014121006630399026967709955925850380","1"],"B":["19528498564528468902521634480986489044663227437233934360035138487189177722814","706337827303094147746432169922700503982765234262612631196531687654713865722","1"],"C":["3726874825357289054925101646028211344121805780590499285615367952100310015198","16413790865300145964228939489264611981079279422219583850941964454619012987205","1"],"Z":["13348398295372116628737687800239385003236584392082957129655537090979023752552","21858938086065692615790404191021275401630119897894808135127612791495958708375","1"],"T1":["14360876145883521049062480571414414707162979629186454824314165195068098843755","7690383252743723537382002605037505508108694574090623371839489928167967159302","1"],"T2":["171526585437306849736171820938322340084660417215376900416315101905819784325","14860073408830920977059163351151904508851804307761461334115941048614121404124","1"],"T3":["1545121168750639889943334802450434695241204658831402130294781806168831416544","3552441256981354095031652913768122490293154222496855043326406989226641931070","1"],"eval_a":"11024792588659243456083103589833329966520500410691012025757085783760664829419","eval_b":"8139322387519291544452196793779464185899888022676212695935483571119961089263","eval_c":"2759381562617869781993539883850313928775692869004537050116210023174425255732","eval_s1":"3982161546082334136949334514760679925162813832987926352276128359736663202279","eval_s2":"13722404104721347388598646963457682656505421852782227871567200092865223175205","eval_zw":"11818614898752314321908019464035292475883958508517334670201070690246297959919","eval_r":"351033371214975959271810948327526637663211703371176137228232410629160426468","Wxi":["2849642276594154825911327435597652863159285743523681959629445273984338402763","17443880865908727420293433216572018364053739032965083704472720153118177741102","1"],"Wxiw":["10956474329499098723358633860519149253944380573151016916071333176886419683119","10706455989148992485159392381934694626464450509616938982009682610544795496695","1"],"protocol":"plonk","curve":"bn128"},"publicSignals":["14870881943777737729426810002848629979047457360865816386884132744016829330171","5"]}

dfdz 5y ago
I did verify that you found the "harder" treasure, but I am not sure this is a good example of zero knowledge proof. The author claims that > you can Download the JSON Proof file, and share that publicly. It does not reveal any information of the coordinates you discovered. But it is not at all clear that the proof does not reveal any information of the coordinates you discovered. Similarly, it is also unclear that the JSON actually proves that you found the treasure. For example, there could be a specific string in the JSON that the program is checking It is a cool example of coding, but not of zero knowledge proof in my opinion
- cvoss 5y ago
  Are you doubting that the application implements the zk-SNARK algorithm correctly? Or doubting that the application actually running on the server is the same as the one in the publicly available source code? Or something else? The first doubt could be eliminated by an expert investigating the source code. The second doubt is more interesting to me. I wonder how that one could be dispelled.
  - zamadatix 5y ago
    I don't think anything is being doubted just dumps you the numbers and tells you it is so without explaining why or how making for a weak example.
  - chrisco255 5y ago
    The entire end-to-end source code (backend and frontend) is available at: https://glitch.com/edit/#!/zk-treasure-hunt?path=README.md%3A1%3A0 https://glitch.com/edit/#!/zk-treasure-hunt?path=README.md%3... . It's a full-stack Glitch example, so you can browse all the code, and fork it and edit it.
  - mattdesl 5y ago
    Just fwiw the demo runs client side as a static site - no server is really needed for proof generation or verification. In a more ideal scenario the code and prover/verifier would all be running in a decentralized fashion (see zk-evms and StarkNet for example).

cvoss 5y ago

It's not mentioned on the website, but, empirically, at least, I see the generated proof file is different if you find the same treasure multiple times. That means if someone snoops my machine and tries to use my proof to claim that they know the answer, I can spot it as a stolen proof. However, without revealing the treasure, I wouldn't be able to prove that they stole it, because it is equally possible that I stole it from them. I wonder if there could be a mechanism for cryptographically incorporating an owner's identification into the ZKP so that I could prove that it was stolen in the above scenario? The ZKP would need to remain publicly usable so that others can verify that it's a valid proof without me, but some aspect of it would be unlockable only by my private key so that I can demonstrate that I hold said key. Does such a mechanism exist?

deleted 5y ago
[deleted]
skulk 5y ago
You could use [trusted timestamping](https://en.wikipedia.org/wiki/Trusted_timestamping https://en.wikipedia.org/wiki/Trusted_timestamping) to prove that you're the one who first created that proof.
pepesza 5y ago
> Does such a mechanism exist? Sign the puzzle solution with your private key. Check signature inside the circuit. This obviously can't be applied to this particular game since it has a circuit that does not employ such measures. Alternatively, if used snark is recursive - create a new circuit that will both validate original proof and check the signature.
zamadatix 5y ago
In a pure sense don't think so in this case since it's a non-interactive zero-knowledge proof, would love to be wrong about that though. For a more practical approach though get your copy of the unique zero-knowledge proof signed by a trusted source first and that should do. Could be a trusted 3rd party or even a large blockchain. Or just switch to interactive zero-knowledge proofs in the first place.

can16358p 5y ago

I have the feeling someone's going to put this game on blockchain with token rewards.

mattdesl 5y ago
(author here) totally - and unironically. there is a lot to explore within the space of using zk proofs to mitigate sybil attacks, vote buying and botting in terms of governance tokens, NFT auctions and the like. also the benefit of decentralization and true verifiability which this demo does not offer.
- can16358p 5y ago
  Interesting. Genuine question: how does zk proofs mitigate against Sybil attacks especially in crypto space? Regardless of that, great work!
  - mattdesl 5y ago
    I'm not sure ZK proof alone solves this, but seems integral to Sybil resistant systems that operate on personhood/identity, as it allows you to prove your identity (or that your personhood meets some criteria, like an age limit) without revealing any additional information about yourself. See [1][2]. A contrived example is an NFT drop that only allows you to claim 1 token per identity proof. [1] - https://blog.cloudflare.com/introducing-zero-knowledge-proofs-for-private-web-attestation-with-cross-multi-vendor-hardware/ https://blog.cloudflare.com/introducing-zero-knowledge-proof... [2] - https://eprint.iacr.org/2019/546 https://eprint.iacr.org/2019/546

abalaji 5y ago

The project mentions that it uses snarkjs and I thought I'd link it directy here. [1] What's interesting in the setup of these systems is the "Powers of Tau" ceremony which, in a decentralized manner (using secure multi-party computation), avoids the "trusted setup" problem in non-interactive variants of zero knowledge proof systems like this one. [2] [1] https://github.com/iden3/snarkjs https://github.com/iden3/snarkjs [2] https://github.com/weijiekoh/perpetualpowersoftau https://github.com/weijiekoh/perpetualpowersoftau

deleted 5y ago

[deleted]

relaunched 5y ago

This doesn't seem like a zero knowledge proof to me. It seems like, for this to work, you have to have a prover, a validator and a 3rd party. By revealing the authentication to the validator, you are providing them information. I know where something is on the grid, check these coordinates, and if it's there, give me a yellow hat...that is easy. If I see you have a yellow hat, I know that you know where the thing is. If I could prove that without disclosing the actual coordinates, that seems more zero knowledge to me. An example might be if you overlay a layer on the infinite plane, blacked out all, on the transparent layer, save a one by one square, and aligned it to the spot that had the easy emoji. Thereby, I prove to you I know where the easy emoji is, without giving any info regarding where it sits in the plane. However, this isn't my field - just my thoughts.

mattdesl 5y ago
The demo does not disclose any coordinates—only verifies a proof that you know the coordinates. Not even the demo knows the coordinates of a valid proof that you submit (check the source - there are no coordinates present).
- relaunched 5y ago
  I'm not sure why that matters. By inputting coordinates, you have giving extra information. There is a difference between verifying that someone knows the coordinates and sharing the actual coordinates. This particular system seems to function like an IDP. Where, upon authentication and token is issued, and the 3rd party checks the token's validity. I'm not sure that is the same as zero-knowledge.
  - mattdesl 5y ago
    The project can be downloaded and run locally (it is a static client side website, no server) and the proof generation and verification can be run offline, without the coordinates ever being sent over the network. Only the proof file needs to be sent between the two parties. I suppose the system itself acts as a “third party” but at no stage does it require you to share the coordinates with one another, hence zero knowledge. :) Does that make sense?

mattdesl 5y ago

Hi HN! Author here, this is my first experiment with circom and snarkjs, I wanted to do something basic that shows a small sample of their potential. :) Comments & questions welcome!

eruleman 5y ago
The website is stuck on “searching” for me? Is this expected?
- mattdesl 5y ago
  It doesn't seem to work on mobile (maybe a limitation of snarkjs)—I've been testing only on macOS Chrome.
- amflare 5y ago
  If you try to input a number longer than 10 digits in either field it'll break and you have to refresh. You can see the error in the console. Its not stuck on searching, it just never reactiviated the button since it broke prior to that in the flow.

aib 5y ago

I think there is an impedance mismatch in how easy the game is to understand versus how the ZK proof part has required reading. Some (if not most) of the questions or comments here must sound silly to someone knowledged in the field. Anyway, here is mine: How is the proof different than a signed message saying "This person has found the treasure"? With the private key derived from the coordinates? Anyway, I'm off to read more about ZK proofs in hopes of making the above sound silly to me.

minism 5y ago
I haven't looked at the game implementation in detail yet, but in order to verify "This person has found the treasure" is signed with the key for coordinates (X,Y), we need to know the cooresponding public key for coordinates (X,Y), which means that youre revealing the coordinates themselves in your message. The idea in ZKP is to prove you know a value without revealing the value itself.
- aib 5y ago
  I don't know how actual asymmetric KDFs work, but I was thinking more along the lines of secret -> private key -> public key, i.e. the public key doesn't contain information about the secret.
mattdesl 5y ago
Thanks! You may be correct in that this application could be better achieved with a simple signed message—this is my first time playing with ZK proofs. The main issue is that the circuit is simply hashing the coordinates and the resulting hash is being used to identify the treasures. So it is already fairly similar to the scenario you describe, but in an ideal ZK system it would not even reveal a hash of the coordinates, only verifiable knowledge of them. For example, I _think_ it might be closer to true ZK if I had hardcoded an equality check with exactly (5, 10) coordinates into the ZK circuit, rather than using hashes to support a variety of coordinates (but then it wouldn’t be as general purpose). Perhaps there’s another better way though!