Comment by pepesza | Hacker News Reader

Comment by pepesza | Hacker News Reader

Parent Full thread

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.

Reply on news.ycombinator.com