[HN Gopher] Show HN: Simple Zero-Knowledge Proof Treasure Hunt Game
___________________________________________________________________
Show HN: Simple Zero-Knowledge Proof Treasure Hunt Game
Author : mattdesl
Score : 50 points
Date : 2022-01-26 17:27 UTC (5 hours ago)
(HTM) web link (zk-treasure-hunt.glitch.me)
(TXT) w3m dump (zk-treasure-hunt.glitch.me)
| can16358p wrote:
| I have the feeling someone's going to put this game on blockchain
| with token rewards.
| nicexe wrote:
| Nice demo. I found up to "harder". I assume you would need to
| bruteforce to find the "impossible".
|
| proof: {"proof":{"A":["18676004117800675141725988
| 94560508538153359060380045576693586005748057954966","216962037493
| 0453391614857867828473542574014121006630399026967709955925850380"
| ,"1"],"B":["19528498564528468902521634480986489044663227437233934
| 360035138487189177722814","70633782730309414774643216992270050398
| 2765234262612631196531687654713865722","1"],"C":["372687482535728
| 9054925101646028211344121805780590499285615367952100310015198","1
| 64137908653001459642289394892646119810792794222195838509419644546
| 19012987205","1"],"Z":["13348398295372116628737687800239385003236
| 584392082957129655537090979023752552","21858938086065692615790404
| 191021275401630119897894808135127612791495958708375","1"],"T1":["
| 14360876145883521049062480571414414707162979629186454824314165195
| 068098843755","76903832527437235373820026050375055081086945740906
| 23371839489928167967159302","1"],"T2":["1715265854373068497361718
| 20938322340084660417215376900416315101905819784325","148600734088
| 30920977059163351151904508851804307761461334115941048614121404124
| ","1"],"T3":["154512116875063988994333480245043469524120465883140
| 2130294781806168831416544","3552441256981354095031652913768122490
| 293154222496855043326406989226641931070","1"],"eval_a":"110247925
| 88659243456083103589833329966520500410691012025757085783760664829
| 419","eval_b":"81393223875192915444521967937794641858998880226762
| 12695935483571119961089263","eval_c":"275938156261786978199353988
| 3850313928775692869004537050116210023174425255732","eval_s1":"398
| 21615460823341369493345147606799251628138329879263522761283597366
| 63202279","eval_s2":"13722404104721347388598646963457682656505421
| 852782227871567200092865223175205","eval_zw":"1181861489875231432
| 1908019464035292475883958508517334670201070690246297959919","eval
| _r":"351033371214975959271810948327526637663211703371176137228232
| 410629160426468","Wxi":["2849642276594154825911327435597652863159
| 285743523681959629445273984338402763","17443880865908727420293433
| 216572018364053739032965083704472720153118177741102","1"],"Wxiw":
| ["109564743294990987233586338605191492539443805731510169160713331
| 76886419683119","107064559891489924851593923819346946264644505096
| 16938982009682610544795496695","1"],"protocol":"plonk","curve":"b
| n128"},"publicSignals":["1487088194377773772942681000284862997904
| 7457360865816386884132744016829330171","5"]}
| shhsshs wrote:
| Really interesting idea. I'm also stuck on the last proof:
| {"proof":{"A":["52879843782255400099541910637160999757520411515
| 5385613032964921571940434242","19392573634889951777626956703843
| 672538432944451899193682888548724342864529439","1"],"B":["94041
| 133329539618266698908929174929055484809231885573019256394845699
| 97434683","9355892340149400743721747317697733520039414623109138
| 623712480516150240861752","1"],"C":["17025592921218423293803353
| 276509975639327431231998740961079522035785553770278","174234984
| 217311980933065783955942271834043403590183438370625849160830185
| 36139","1"],"Z":["467920497315468622167622611730974927410804229
| 0803986293348834038552965610694","18495471997097378260571021759
| 032113343347720768624816790096532135583194497500","1"],"T1":["9
| 867739328482857556240082341319546495849614236722730250625116628
| 272791849277","286816544745713239364937013479041169659314446238
| 2351418948962174508512798119","1"],"T2":["170871999591714240645
| 64733158000941043006524389450810193258931251521734973371","2911
| 105227677439634206272144083822945188790339567179520353606559518
| 569996983","1"],"T3":["7129249599766093445028171268444907082411
| 743186316411948288132376306904700379","260603935431763826068880
| 3298171035577991543816558705808789024740126554704610","1"],"eva
| l_a":"689526022054126906396219334169892690936501574629107855612
| 3010150492168710344","eval_b":"80687250924772460530828274316106
| 12461501706876500056081310697342029389110657","eval_c":"2704512
| 929705984824776357863771653984806802643988862884038528594470902
| 574120","eval_s1":"47946955698474399007512671124181032731618292
| 62476159763959027953943371223323","eval_s2":"216349588536362666
| 8152176373764360379814151330932793558189464412748989368897","ev
| al_zw":"1880665142149130686514517533674533416334414362072524419
| 1448339490901611643578","eval_r":"17436641083417465197082211434
| 092476275687970780131379758738973376030688767532","Wxi":["44311
| 635391467731802226887323442409585617294291687251973618260985281
| 23452180","1053143132445537622723710898349304413041009840619910
| 7820103575253972171316343","1"],"Wxiw":["5408442091202782791687
| 007786548171585846105046857466808022018453657877169978","359346
| 912396501552138519103469194303344779711021617504170317457732030
| 1325259","1"],"protocol":"plonk","curve":"bn128"},"publicSignal
| s":["1487088194377773772942681000284862997904745736086581638688
| 4132744016829330171","5"]}
| dfdz wrote:
| 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 wrote:
| 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.
| chrisco255 wrote:
| 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.
| zamadatix wrote:
| 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.
| shhsshs wrote:
| 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.
| Tomuus wrote:
| Me too, as to do so you'd need to solve P == NP - we can
| split the $1million 50/50 if you like.
| sturza wrote:
| x:4 y:5789
| 2bitencryption wrote:
| could someone explain how this works?
|
| biggest question is, what information is encoded in my "proof"?
| can the proof be verified by anyone, similar to verifying a
| digital signature using a public key? or must the proof be
| verified by a central authority?
|
| if the verification is decentralized, how does the proof contain
| information that proves "I know the secret coordinates for X"
| without encoding the coords themselves?
|
| I've thought enough about "proof of work" that I can easily
| digest something like this: "testing" a coordinate is expensive,
| so finding a "treasure" in a very sparse field is really hard /
| takes many guesses (similar to finding the correct nonce for a
| blockchain block) but then confirming someone found a treasure is
| cheap, in comparison (basically just proof of work)
|
| but this seems to turn the whole thing on its head, and it's
| claiming that you can provide proof of work without actually
| exposing the solution to the work?
|
| as in, I find a nonce that "solves" a blockchain block, and I can
| prove to the system I found one without actually sharing what it
| is? or this "blockchain style" of thinking is totally not the
| same and not applicable?
| cvoss wrote:
| 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?
| skulk wrote:
| You could use [trusted timestamping](https://en.wikipedia.org/w
| iki/Trusted_timestamping) to prove that you're the one who
| first created that proof.
| pepesza wrote:
| > 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 wrote:
| 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.
| pepesza wrote:
| 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.
| [deleted]
| abalaji wrote:
| 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
| relaunched wrote:
| 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.
___________________________________________________________________
(page generated 2022-01-26 23:01 UTC)