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.

Improve this question
$\endgroup$
3
  • $\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
    Commented Aug 18, 2017 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
    Commented Aug 18, 2017 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. ♦
    Commented Aug 23, 2017 at 23:40

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

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

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