# Verifiable execution of a program

I would like to know what cryptographic primitives could be used for Alice to prove to Bob that she actually executed a program. The goal is to make a Proof-of-useful work, where Alice proves she verified a transaction, but where this proof is tied to Alice's public key. Creating the proof needs to be only possible by executing the program. Verifying the proof should be much faster using the public key of Alice.

Input (known to Everybody):

• Alice's identity (including public key and other needed material)
• Input of the program
• The program itself
• Output of the program

Output (created by Alice):

• A proof of execution

Verification (done by Bob):

• Take all the input plus the proof of execution, and verify it's correct

Restrictions:

• Even if Eve knows all the Inputs and Outputs, it shouldn't give her an advantage in creating her own proof of execution
• Verification should be much faster than re-creating the proof

I'm currently looking into Verifiable Delay Functions and Verifiable Random Function, but this doesn't seem to quite hit the target. Perhaps some kind of ZKP could be used, but to prove a generic execution of a program seems very heavy.

• Would verifiable computation help e.g., eprint.iacr.org/2013/279.pdf? The key feature of VC is that verifying the computation should be much more efficient than doing the computation itself. These are ZKP by the way because the verifier needs to know the input, but it seems to fit your requirement. Aug 13 at 14:40
• Sorry, typo, it should be are not ZKP. I can't edit for some reason. Aug 13 at 16:29
• In the paper they show how it can be used as a ZKP, too. However, if Eve wants to prove that she did verify the program, she'll have to call KeyGen again, which seems to be quite expensive. I looked a bit at papers that cite Pinocchio, but couldn't find any that can remove the multiple calls to KeyGen. Aug 13 at 19:30
• By definition any information Alice has that Bob doesn't have is an output of the program. We could make all the intermediate results outputs, to prove that Alice actually knows the intermediate results, but then Eve would know them too. Aug 24 at 14:39