1
$\begingroup$

Let us assume I have a Program P running on remote computer generating output O. Without trusting the remote environment and not having to verify the output O, is there is a way to validate that Program P has indeed been executed and resulted in output O ?

Let me know if the question is too vague. I will clarify.

$\endgroup$
  • $\begingroup$ What exactly is your goal? Is P known to the verifier, and he wants to be convinced that the "remote environment" is in the possession of $O$, the output of $P$? $\endgroup$ – Ariel Aug 18 '17 at 9:57
  • $\begingroup$ Yes. P is know to the verifier. Verifier (V) wants to be sure that execution of P resulted in O. Trustless node T might cheat by submitting random O. V wants to ensure that what ever O might be, it is indeed generated by execution of P. $\endgroup$ – ivymike Aug 18 '17 at 12:58
  • $\begingroup$ Cross-posted: cstheory.stackexchange.com/q/38837/5038, cs.stackexchange.com/q/80169/755. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$ – D.W. Aug 23 '17 at 23:40
1
$\begingroup$

This is the problem of securely outsourcing computation. There's lots of work on this problem in the cryptographic literature; if you do a search at [Crypto.SE] and [Security.SE], you should find some references. Many of the schemes are probabilistic: if you the remote computer cheats, you have some chance of detecting that fact. I know of two general approaches: one based on cryptographic commitments, and another based on SNARKs. You should be able to turn up papers on how SNARKs work.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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