4
$\begingroup$

Assuming an algorithm $A$ known to both Alice and Bob.

Alice runs the algorithm and gets a result $R$. How can Alice prove to Bob that $R$ is the result of the execution of $A$ and not some random value (without having Bob run the algorithm himself)?

The goal is for Bob to perform less calculations checking Alice proof than running the algorithm itself. A probabilistic scheme for the proof is fine.

Please note that Alice does not have to prove correctness of $R$, just that she ran $A$ to obtain $R$.

The algorithm and its inputs can be modified to build the proof if necessary

Note: from the discussions below. I am happy with heuristics or techniques to obtain the proof. This is not a rhetorical question on algorithms.

Note2: @DavidRicherby suggests providing an execution trace, which seems perfectly reasonable. This leads to two sub-questions

  1. How does Alice practically build a trace which proves to Bob with high probability that the trace is the one linked to the result ? (Bob should run less calculations checking the trace, than running the calculation himself)

  2. Could such a mechanism be generic i.e. work with any algorithm ? For instance by confining execution inside a Virtual Machine which could record all operations.

$\endgroup$
  • $\begingroup$ The answer might depend on the program $P$. $\endgroup$ – Yuval Filmus Nov 16 '18 at 6:51
  • $\begingroup$ Are you familiar with interactive proofs? $\endgroup$ – Yuval Filmus Nov 16 '18 at 6:51
  • $\begingroup$ @YuvalFilmus Hello. Are you referring to Sigma protocols used in zero knowledge proofs for instance? $\endgroup$ – BGR Nov 16 '18 at 6:55
  • $\begingroup$ I have never heard of Sigma protocols. Zero-knowledge proofs are just one type of interactive proofs. $\endgroup$ – Yuval Filmus Nov 16 '18 at 7:05
  • 1
    $\begingroup$ @DavidRicherby if Bob needs to check every step, it is as good as saying that Bob must run the algorithm himself, which is what we want to avoid. Maybe we could have Bob check some "checkpoints" only, which would reduce the amount of computation for Bob but then becomes probabilistic (which is fine) $\endgroup$ – BGR Nov 16 '18 at 10:15
5
+100
$\begingroup$

This is known as verifiable computing or verified computation. There are many protocols for verified computation, with different properties. Some of them rely upon special hardware (e.g., SGX). Many of them don't rely on special hardware and use cryptography. Among the cryptographic solutions, there are some protocols that can be used with any program (but are potentially inefficient), and some that can only be used for specific programs or types of computations (but are much more efficient).

There's an entire line of research papers on the subject, and it is too broad to summarize in a single paragraph or two. I suggest reading about interactive proofs, and about the Pepper, Ginger, Zaatar, Pinocchio, Pantry, and Truebit systems, among others. I also recommend reading the following survey paper for an overview of cryptographic solutions that can handle general computation:

In practice, I suspect that the SGX-based schemes or Truebit are likely to be the most practical for general computation at the moment, though the research literature is progressing rapidly and this could change in the future. For specific computations, it is sometimes possible to design a custom protocol that does much better, but that depends on the particular computation.

$\endgroup$
  • $\begingroup$ Thank you for the pointers. I have started reviewing the literature which is usually targeting correctness as well. I was hoping that by relaxing requirements I could get a more practical implementation: I am only trying to distinguish random values from a value - correct or not - outputted by the algorithm; a sort of "proof of work" $\endgroup$ – BGR Nov 22 '18 at 6:56
1
$\begingroup$

Assuming that the algorithm results in an output $R$ that is a deterministic function of its input(s).

Bob asks Alice to run the algorithm on a given input $I$, obtain an output $R_1$, use that as an input to the algorithm and produce $R_2$, and to re-run the algorithm $n$ number of times where $n$ is an even number. Bob also asks Alice to send $R_{n/2}$ and $R_n$

Now Bob runs the algorithm $\frac{n}{2}$ times on the initial input $I$ (with $p=0.5$) and checks if $A(A(A(..I))) = R_{n/2}$ or runs it on $R_{n/2}$ (with $p=0.5$) and sees if $A(A(A(..R_{n/2}))) = R_n$.

As suggested by @Draconis, we can also extend this to any $k$ instead of looking at just 2 results. This will allow Bob to potentially do much lesser work.

We can use a probability bound to see what the value of $n$ should be to obtain a given confidence. This way, Bob can be certain that Alice is running algorithm $A$ by using fewer computations that Alice.

Note: This relies on Bob asking Alice to do possibly meaningless extra computations but do let me know if there are specific points in your question that this answer does not address.

$\endgroup$
  • 1
    $\begingroup$ You can also replace the 2 with some arbitrary $k$ to make Bob do potentially much less work, though no matter what $k$ is (even for 2) you should use this algorithm several times to get a solid p-value. $\endgroup$ – Draconis Nov 20 '18 at 5:54
  • $\begingroup$ Yep that sounds good! Thank you @Draconis $\endgroup$ – doodhwala Nov 20 '18 at 6:09
  • $\begingroup$ I'm having trouble understanding why it would ever be beneficial to choose $n>2$ -- could you elaborate please? (I can see why running the entire procedure multiple times is useful to reduce the probability of a false positive.) $\endgroup$ – j_random_hacker Nov 20 '18 at 8:57
  • $\begingroup$ Unfortunately this method works poorly. Alice can cheat, in a way that causes her to be detected with low probability. With your initial example, Alice can pick a single step and replace the internal state with some other state (cheating); this will be detected only if Bob happens to pick the same half that Alice cheated on to recompute. So with that example, Alice's cheating is detected with probability only $1/2$. That's usually not good enough in practice -- if Alice can fool you half of the time, you've got a serious problem. $\endgroup$ – D.W. Nov 22 '18 at 1:01
  • $\begingroup$ If you split into $k$ pieces (instead of 2) and you recompute $r$ of them, then the probability that Alice's cheating is discovered is only $r/k$. Meanwhile, the work that Bob has to do is a $r/k$ fraction of the work that Bob would have to do of the entire task. If you want the probability of detecting cheating to be very close to 1 (which you typically will, in practice), you need $r/k$ to be close to 1, which means that Bob has to do essentially as much work as if he just computed the answer himself without Alice's help. For that reason, this method is a poor solution to the problem. $\endgroup$ – D.W. Nov 22 '18 at 1:02

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.