5
$\begingroup$

Is there any cryptographic method for Proof Of Computation ?
If i am running my program on untrusted hardware (remote server), after some time i want to verify the remote machine hasn't tampered with my program and successfully ran it for required time (and the result/output is correct), how can i verify ?
Is there any Zero knowledge proof for it?

Also i want to check if the remote server was active (online) for the certain time, this can be done by proof of computation ? (like the server need to keep running my custom program for certain time, and when i come back to check it will give me require mathematical proofs using which i can verify the server was active for that period of time)

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Are you looking for A) Cryptographic proof that a certain amount of work/computation was performed ? B) Cryptographic proof that a certain computation was performed ? C) Cryptographic proof that a program on a remote server runs unmodified ? There are practical solutions of A. As stated by Daniel S in his answer, there are solutions for B), and they can be practical for some kinds of computation. I think there is no solution for C). $\endgroup$
    – fgrieu ♦
    Jul 12, 2022 at 14:18
  • $\begingroup$ @fgrieu is this relevant for my use: Miden is a zero-knowledge virtual machine. For any program executed on Miden VM, a STARK-based proof of execution is automatically generated. This proof can then be used by anyone to verify that a program was executed correctly without the need for re-executing the program or even knowing what the program was. $\endgroup$
    – fin
    Jul 12, 2022 at 15:16
  • 1
    $\begingroup$ Yes I think it is relevant, and of the B) kind. However that "zero-knowledge virtual machine" has some serious limitations, and I don't think it qualifies as C) [update: this is not a recommendation, and I do not fully grasp the Miden VM] $\endgroup$
    – fgrieu ♦
    Jul 12, 2022 at 16:02

2 Answers 2

Reset to default
2
$\begingroup$

Yes this is possible using methods such as zk-SNARKS and zk-STARKS. Vitalik Buterin has written a good series of blogs giving an overview of the ideas. The linked blog gives verifiable computation of Fibonacci recurrences as an example; the blog on PLONK gives a description of how to encode more general computations.

The ZoKrates toolkit gives a workable way to create proofs of computation using zk-SNARKS.

Improve this answer
$\endgroup$
2
  • $\begingroup$ can you link some specific topics which is related to it? $\endgroup$
    – fin
    Jul 12, 2022 at 13:34
  • $\begingroup$ Added another link on some theory and also to an implementation of the ideas that can be experimented with. $\endgroup$
    – Daniel S
    Jul 12, 2022 at 13:40
0
$\begingroup$

Instead of asking for a proof, you could use a slightly different approach. You could send a homomorphically encrypted payload and ask the server to homomorphically run it as agreed in advance. After the server has computed the answer, you get it back and you can decypher it.

If you don't want to verify the whole server solution yourself you can randomly insert some dummy fields into the payload (for instance some integers to be added) and quickly verify that the server is computing it correctly. The server never sees the plaintext, so it cannot cheat by performing a different computation, otherwise you would quickly find out by looking at the dummy payload results.

The limitation of this technique are pretty much the limitations of homomorphic encryption.

Improve this answer
$\endgroup$
3
  • $\begingroup$ can you tell me more about ask the server to homomorphically run it as agreed in advance? also how is that related to my problem? $\endgroup$
    – fin
    Jul 13, 2022 at 20:35
  • $\begingroup$ The server cannot decypher the payload you send him. So you have to tell the server in advance what operations it should perform on the the payload. $\endgroup$
    – Rexcirus
    Jul 13, 2022 at 20:44
  • $\begingroup$ My suggestion allows you to have the server do the work and you can verify quickly that the work has been done properly. It's not a proof of computation, but it's another way to get a similar result. $\endgroup$
    – Rexcirus
    Jul 13, 2022 at 20:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.