4 ms·

zksnarks are one of the most wonderful results in computer science and mathematics. On first learning of them, I had the common reaction of "I can't believe th

zksnarks are one of the most wonderful results in computer science and mathematics. On first learning of them, I had the common reaction of "I can't believe this is even possible to do". The way that I came to intuitively understand them is by analogy to public key cryptography. Digital signatures allow someone to run the RSA algorithm on some piece of private data X and prove the output is Y, without revealing X. zksnarks are a generalization of this idea. They allow one to prove that they ran any arbitrary program P (in np) with some private data X, and it produced output Y, without revealing X. It seems (slightly) less mystical for me to see it that way.

johnsimer 5y ago
Would there be a way to make a Proof of Infra algorithm using zk proofs? e.g. to prove that some blockchain nodes ran a set of data through a particular infra setup (e.g. a bunch of language arbitrary Lambdas, SQS queues etc. defined in cloudformation or terraform).
- aboodman 5y ago
  No it has to be a pure function with no reference to outside systems, and the function has to be in the complexity class np.
alanfranz 5y ago
Why would you leverage signatures? An hash would be enough for showing knowledge. Maybe you meant you needed to show proof that only you (not somebody else) knows some data? Even for such scenario I would not be sure it’s correct. Many signature implementations hash the data, then sign the hash; if I happen to know the hash but not the data, I could just sign it without owning it. (I should verify a few things, this was written off the top of my head).
- runeks 5y ago
  > Why would you leverage signatures? Because in order to verify that a hash over some secret data is correct you need access to the secret data, which makes it pointless. Only using a signature can the signer prove that they have knowledge of a secret number (their private key) by providing information that does not reveal the secret (public key, message hash, signature).
  - alanfranz 5y ago
    > Because in order to verify that a hash over some secret data is correct you need access to the secret data, which makes it pointless. No. You could have access to the hash. For the private/public key signing, of course; the signature guarantees that you have access to the private key. But if the ‘private secret data’ is not the private key?
    - runeks 5y ago
      > But if the ‘private secret data’ is not the private key? It is in the example you were replying to. That’s my point.
- aboodman 5y ago
  The key is the "any arbitrary program". With zk-snarks, I can, theoretically, run some complex analysis of some data -- imagine something that requires millions of compute hours -- and provide a receiver (a) the answer, and (b) a compact hash-like proof that (a) is correct *without* receiver having to re-run the calculation to trust the answer.

johnsimer 5y ago

Would there be a way to make a Proof of Infra algorithm using zk proofs? e.g. to prove that some blockchain nodes ran a set of data through a particular infra setup (e.g. a bunch of language arbitrary Lambdas, SQS queues etc. defined in cloudformation or terraform).

aboodman 5y ago
No it has to be a pure function with no reference to outside systems, and the function has to be in the complexity class np.

alanfranz 5y ago

Why would you leverage signatures? An hash would be enough for showing knowledge. Maybe you meant you needed to show proof that only you (not somebody else) knows some data? Even for such scenario I would not be sure it’s correct. Many signature implementations hash the data, then sign the hash; if I happen to know the hash but not the data, I could just sign it without owning it. (I should verify a few things, this was written off the top of my head).

runeks 5y ago
> Why would you leverage signatures? Because in order to verify that a hash over some secret data is correct you need access to the secret data, which makes it pointless. Only using a signature can the signer prove that they have knowledge of a secret number (their private key) by providing information that does not reveal the secret (public key, message hash, signature).
- alanfranz 5y ago
  > Because in order to verify that a hash over some secret data is correct you need access to the secret data, which makes it pointless. No. You could have access to the hash. For the private/public key signing, of course; the signature guarantees that you have access to the private key. But if the ‘private secret data’ is not the private key?
  - runeks 5y ago
    > But if the ‘private secret data’ is not the private key? It is in the example you were replying to. That’s my point.
aboodman 5y ago
The key is the "any arbitrary program". With zk-snarks, I can, theoretically, run some complex analysis of some data -- imagine something that requires millions of compute hours -- and provide a receiver (a) the answer, and (b) a compact hash-like proof that (a) is correct *without* receiver having to re-run the calculation to trust the answer.