Suppose Alice asks Bob to write a (python) code/function named
get_sqrt(input) that computes and returns the square root of an input number named
input. Next, Alice provides three random numbers as
input to Bob. Bob produces the three
output numbers using Bob's function
get_sqrt(input) and returns to Alice:
outputnumbers that are the square roots of the three
- The python code
- Some kind of signature/hash code. This signature/hash code can consist of any combination of information derived from the
outputand python code
- Alice only has access to Alice's world until Alice has verified the solution of Bob. Afterwards Alice gets access to both Alice's and Bob's world.
- Bob has access to both Bob's world and Alice's world (low- and high costs per operations).
- Bob can do computations cheaply in Bob's world, but Bob is not trusted in Bob's world.
- Re-doing the computation is too expensive in the world of Alice (for both Bob and Alice), because in the world of Alice, the costs per computation are too high.
- The solutions created by the function
get_sqrt(input)are reversible or easily(polynomially) verifiable. (For example, the output of Bob's function
get_sqrt(input)can be verified by Alice by checking whether the square of each
outputequals its accompanying
However, just that the answers provided by Bob are correct, does not mean that the
get_sqrt(input) function that Bob sent to Alice actually generated those answers/isn't gibberish. Therefore, I was wondering if there is some property that can be computed by Bob (and/or Alice), based on the
output, and (python) code
get_sqrt(input) that makes it possible for Alice to verify that Bob's function indeed generates those
output numbers based on the given
input numbers (without re-doing the computations).
Is there a way with which Alice can verify that the
output numbers are generated by the
get_sqrt(input) function based on the set of
input numbers, without re-doing the computation?