patternMinor
Proving a value is the result of the execution of an algorithm
Viewed 0 times
provingresultthevaluealgorithmexecution
Problem
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
-
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)
-
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.
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
-
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)
-
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.
Solution
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.
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:
- Verifying computations without reexecuting them, Michael Walfish, Andrew J. Blumberg, CACM 58(2), February 2015.
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.
Context
StackExchange Computer Science Q#100158, answer score: 5
Revisions (0)
No revisions yet.