Show HN: Simple Zero-Knowledge Proof Treasure Hunt Game | Hacker News Reader

Show HN: Simple Zero-Knowledge Proof Treasure Hunt Game

zk-treasure-hunt.glitch.me

82 pointsmattdesl45 comments

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

[2] https://github.com/weijiekoh/perpetualpowersoftau

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.

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.

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.

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!

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?

You could use [trusted timestamping](https://en.wikipedia.org/wiki/Trusted_timestamping) to prove that you're the one who first created that proof.

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

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.

There are multiple ways of pulling this off. Signatures are zk-proof systems, just a very specialized ones. So you do it every time you sign a message.

See my other comment on how it can be done.

But doesn't that make it no longer non-interactive?

Why would it? Both signatures and snarks are non-interactive. And since you prove any(*) computation with a snark, you can prove that computation that verifies something (signature or snark proof) went well.

Without the interactive check imagine the real finder crewtes a self signed version of "42" for 2020. Shortly after an fake finder creates a new document with the exact same contents "42" dated 2019 and self signed. There is no interactive way of verifying which was truly the original here, you'd need to bring in a trusted 3rd party (or have already trusted one of the signers over the other in the first place) which is an interactive verification step (and actually measures when it was validated with 3rd party not truly when it was discovered).

I think we are talking about three different scenarios.

You are describing attribution problem. "Solution to the puzzle is no longer a secret, it is a public knowledge. Who was the original finder?". This problem is not really concerned with the proof - there is nothing more to hide, milk has been spilled.

GP is speaking about a different problem. Thief is not stealing the secret - they are stealing the proof that secret exists. In GP's scenario thief hacks GP's machine - which is not necessary, since GP is likely to show the proof to the world himself.

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

And I was specifically addressing the situation when GP has made proof public. In such scenario thief can point the finger at the proof and claim that they have produced it. Solution described by me prevents thief from doing it, since proof will contain a public key from a keypair thief does not possess.

Here is other poster, presenting the solution I spoke of in a clearer way: https://news.ycombinator.com/item?id=30094271

> You are describing attribution problem. "Solution to the puzzle is no longer a secret, it is a public knowledge. Who was the original finder?".

Not at all, though perhaps my choice of "42" was poor as that seems to be an actual answer to one of the examples used here. "42" was meant as a dummy proof of knowledge value, not the secret value. My bad, should have picked something more obvious.

> GP is speaking about a different problem. Thief is not stealing the secret - they are stealing the proof that secret exists. In GP's scenario thief hacks GP's machine - which is not necessary, since GP is likely to show the proof to the world himself.

Yes, this is the scenario I'm exclusively referring to.

> And I was specifically addressing the situation when GP has made proof public. In such scenario thief can point the finger at the proof and claim that they have produced it. Solution described by me prevents thief from doing it, since proof will contain a public key from a keypair thief does not possess.

Your solution gives proof the person claiming to have found the proof signed their copy of the proof before the time it was shared, it doesn't prevent a 2nd person from taking the ZKP that was signed, making a new copy of it's value (not signature history), and signing it as an original signed ZK proof and claiming to have found it even earlier. The only ways I know of to detect such forgery of an original signed document occurred all involve interactivity (which makes the problem trivial).

> Here is other poster, presenting the solution I spoke of in a clearer way: https://news.ycombinator.com/item?id=30094271

Embedding the user's public key in the ZKP process is also an interactive ZKP method, as above interactive verifications are trivial and there are many ways. The example site here uses non-interactive zero-knowledge proofs via zk-SNARK and that's where the open question left in my original comment lay.

The trick is to sign the secret, not the proof. And than to prove inside the circuit following claims:

1) secret (provided as a hidden input) is correct a solution to the puzzle

2) signature that signs the secret is correct (signature is provided as a hidden input)

3) signature corresponds to a public key (which is provided as a public input)

You don't need blockchain or interaction for that. You just provide the proof and you are done. As long as other people are not able to steal the secret and your private key - world knows that you are the only holder of the secret.

To run through an actual example:

1) pepesza signs the ZKP "42424242" as the correct solution to the problem in 2022

2) pepesza's signature is correct

3) pepesza's signature corresponds to a public key

4) zamadatix see's pepesza's signed ZKP value and creates a signs it as a "new" ZKP value "42424242" as the correct solution to the problem and dates it as 2021

5) zamadatix's signature is correct

6) zamadatix's signature corresponds to a public key

7) nobody can tell whether pepesza's or zamadatix's signed version of the solution actually came first without interaction, just that each claims to have signed it at the specified times.

How do you work around 7)? Alternatively if the signature instead hides the actual value of the ZKP:

1) pepesza signs the ZKP "424242" in a way that hides what that value is or otherwise prevents it from being read without further interaction.

2) pepesza's signature is correct

3) pepesza's signature corresponds to a public key

4) nobody can verify what pepesza has signed is actually a valid ZKP as they can't read the value to check and they can't interact with pepesza or they are back to an interactive ZKP

In the first scenario you haven't proven you generated it first without interaction you've just proven you signed that you claimed to have generated it first. In the second scenario you have broken the ability for anyone to validate you have an answer as they can't read your ZKP value. If you wait for someone to challenge you and then show them that's an interaction.

Is there a way I'm missing that avoids 7) in scenario 1 or 4) in scenario 2 or an alternative scenario completely?

1) pepesza finds "42424242" <- that is the solution that needs to be hidden from the world

2) Signature = sign("42424242", privk_pepesza)

3) Witness = Circuit("42424242", Signature, pubk_pepesza). `Circuit` program will validate things I've mentioned. a) is 42424242 a correct solution to the puzzle? b) is signature correct for "42424242" as msg and pubk_pepesza as signer? It will return a computation trace - the Witness.

4) Proof = Prove(Witness). This `Prove` program is specific to a zksnark flavor that is being used. Some flavors will produce Proof of constant size.

Now pepesza sends the Proof and pubk_pepesza to zamadatix. Zamadatix runs:

Result = Validate(Proof, pubk_pepesza). If Result is true, both a) and b) are correct. This allows zamadatix to learn if pepesza actually has a solution to the puzzle. Note that Validate(Proof, pubk_zamadatix) will return false.

`Validate` is the program which can be automatically compiled from the Circuit (and things that are dependent on the flavor of zksnarks used).

The whole thing revolves around two properties of zksnarks. First - they allow to prove any(*) computation. Second - they allow to use so-called hidden inputs. In example above `pubk_pepesza` is the only public input. "42424242" and Signature are both hidden inputs and don't have to be revealed. Thus Zamadatix can create a Proof' that will result in true = Validate(Proof', pukb_zamadatix), but that would require an independent discovery of "42424242" string. Or a hack of pepesza's machine.

It is possible to embed a users public key (from a private/public key pair) in the zk circuit, so that the proof would be tied to it. In a blockchain setting this could tie each proof to a user; only releasing a reward if they both can prove knowledge of coordinates, and also initiate the transaction from the associated address in the circuit (thus proving they know the private key).

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!

The website is stuck on “searching” for me? Is this expected?

It doesn't seem to work on mobile (maybe a limitation of snarkjs)—I've been testing only on macOS Chrome.

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.

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.

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

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.

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?

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

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

Interesting. Genuine question: how does zk proofs mitigate against Sybil attacks especially in crypto space?

Regardless of that, great work!

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

[2] - https://eprint.iacr.org/2019/546

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"]}

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

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.

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.

The entire end-to-end source code (backend and frontend) is available at: 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.

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

If you can show how to go from a proof JSON generated by this app to any piece of information that points even slightly in the direction of the inputs used to generate that proof, I'd love to see it.

Me too, as to do so you'd need to solve P == NP - we can split the $1million 50/50 if you like.

Would you? Are you saying that an oracle which gets some statistical information from such zk-proofs could be used to solve NP-complete problems in (randomized?) polynomial time?

The demo assumes that zkSNARK, circom, snarkjs and my usage of them all works as expected. At some point in the future I can reveal the Proof to demonstrate that I indeed know the hash associated with the Impossible location (the hashes are known: see the source code).

You could also remix the demo and choose your own hashes for each emoji (see console when searching for coordinates to get its hash), and I could then be the one guessing your secret coordinates.

The demo runs locally by the way (no server needed).

x:4 y:5789

Really interesting idea. I'm also stuck on the last proof:

    {"proof":{"A":["528798437822554000995419106371609997575204115155385613032964921571940434242","19392573634889951777626956703843672538432944451899193682888548724342864529439","1"],"B":["9404113332953961826669890892917492905548480923188557301925639484569997434683","9355892340149400743721747317697733520039414623109138623712480516150240861752","1"],"C":["17025592921218423293803353276509975639327431231998740961079522035785553770278","17423498421731198093306578395594227183404340359018343837062584916083018536139","1"],"Z":["4679204973154686221676226117309749274108042290803986293348834038552965610694","18495471997097378260571021759032113343347720768624816790096532135583194497500","1"],"T1":["9867739328482857556240082341319546495849614236722730250625116628272791849277","2868165447457132393649370134790411696593144462382351418948962174508512798119","1"],"T2":["17087199959171424064564733158000941043006524389450810193258931251521734973371","2911105227677439634206272144083822945188790339567179520353606559518569996983","1"],"T3":["7129249599766093445028171268444907082411743186316411948288132376306904700379","2606039354317638260688803298171035577991543816558705808789024740126554704610","1"],"eval_a":"6895260220541269063962193341698926909365015746291078556123010150492168710344","eval_b":"8068725092477246053082827431610612461501706876500056081310697342029389110657","eval_c":"2704512929705984824776357863771653984806802643988862884038528594470902574120","eval_s1":"4794695569847439900751267112418103273161829262476159763959027953943371223323","eval_s2":"2163495885363626668152176373764360379814151330932793558189464412748989368897","eval_zw":"18806651421491306865145175336745334163344143620725244191448339490901611643578","eval_r":"17436641083417465197082211434092476275687970780131379758738973376030688767532","Wxi":["4431163539146773180222688732344240958561729429168725197361826098528123452180","10531431324455376227237108983493044130410098406199107820103575253972171316343","1"],"Wxiw":["5408442091202782791687007786548171585846105046857466808022018453657877169978","3593469123965015521385191034691943033447797110216175041703174577320301325259","1"],"protocol":"plonk","curve":"bn128"},"publicSignals":["14870881943777737729426810002848629979047457360865816386884132744016829330171","5"]}

Reply on news.ycombinator.com