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
- 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.