8 ms·

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 me

by 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.
- pepesza 5y ago
  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.
  - zamadatix 5y ago
    But doesn't that make it no longer non-interactive?
    - pepesza 5y ago
      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.
      - zamadatix 5y ago
        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).
        pepesza 5y ago
        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 https://news.ycombinator.com/item?id=30094271
mattdesl 5y ago
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).

by cvoss 5y ago

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.

pepesza 5y ago
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.
- zamadatix 5y ago
  But doesn't that make it no longer non-interactive?
  - pepesza 5y ago
    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.
    - zamadatix 5y ago
      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).
      - pepesza 5y ago
        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 https://news.ycombinator.com/item?id=30094271

mattdesl 5y ago

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