Join Log in
Score:2
avatar Crypto

Verifiable execution of a program

si flag
ineiti

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.

74
0 + 4
cn flag
lamba
Would verifiable computation help e.g., https://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.
1
Reply
cn flag
lamba
Sorry, typo, it should be *are not ZKP*. I can't edit for some reason.
0
Reply
si flag
ineiti
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`.
0
Reply
jp flag
user253751
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.
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.