2
$\begingroup$

Let's say there's a cloud computing service that allows people to run arbitrary programs and get the results. The idea being that your machine is too slow, and you don't want to overwhelm it. If your program is something like "factorize 15672965357291016", then it's a perfect candidate for this service, because you can very quickly verify that a result handed back to you is correct. But if your program is long and complicated, and you can't think of a quick way to verify that a given input/output pair is correct, then you're stuck with running the program on your own machine to verify the results, which defeats the purpose.

One solution would be to use the blockchain and have a lot of people verify that some given input/output pair is correct--then you only accept the result as true when whatever block it's on has enough confirmations. The problem with this is that it could really slow down the network if your program is resource-intensive.

What would be nice to have is a programming language where a given program P, an input to it I, and a supposed output O, can be verified quickly (i.e. P(I) == O). That way, making confirmations would be fast, and the whole network would speed up.

I don't think this can be done in general because you could use it to solve the halting problem. If you have some function V(P, I, O), which verifies that P(I) == O, then running V(P, I, halts) would check that P halts on input I.

However, the fact that V does exist for every problem in NP makes me think that there has got to be some middleground, where you could make a really restricted language for which V always exists, and it can easily be determined from the structure of P (a trivial implementation is just V(P, I, O) = P(I) == O). I'm not really sure what my question is, but is this an existing problem? What search terms should I use to learn more about this?

$\endgroup$
  • $\begingroup$ I'm pretty sure there are people in cloud computing researching things like this. There are multiple trust issues such a "How do I know that my cloud provider is keeping my data secure?" and your proposal of "How do I know my cloud provider really ran my computation instead of just making up an answer?" seems somewhat related. The recent Oxford Strachey Lecture by Jon Crowcroft might give you some pointers; I think the video will be uploaded to podcasts.ox.ac.uk before too long. $\endgroup$ – David Richerby Mar 13 '18 at 12:40
  • $\begingroup$ (But I don't think Prof. Crowcroft's lecture will answer your question.) $\endgroup$ – David Richerby Mar 13 '18 at 12:41
  • 1
    $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Mar 13 '18 at 12:45
  • $\begingroup$ You are proposing a distributed brute-force algorithm. What a waste of resources! $\endgroup$ – Raphael Mar 13 '18 at 12:46
  • $\begingroup$ "That way, making confirmations would be fast, and the whole network would speed up." -- No, as long as the space of possible solutions is huge, you gain little. See also the theory around NP-completeness: verification is "simple", but solving the actual problem isprobably not. $\endgroup$ – Raphael Mar 13 '18 at 12:47
1
$\begingroup$

I found out that this is called Verifiable computing:

Verifiable computing (or verified computation or verified computing) is enabling a computer to offload the computation of some function, to other perhaps untrusted clients, while maintaining verifiable results.

| cite | improve this answer | |
$\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.