A non-interactive zero-knowledge proof of faithful execution(people.xiph.org)
people.xiph.org
A non-interactive zero-knowledge proof of faithful execution
https://people.xiph.org/~greg/simple_verifyable_execution.txt
https://people.xiph.org/~greg/simple_verifyable_execution.txt
For starters, notice that a hash function as a commitment scheme is neither information-theoretically hiding, nor information-theoretically blinding [1], unlike e.g. a simple Pedersen commit. Another problem is that the XOR in the example table needs to be exactly one bit -- it is non-trivial to show that this actually works. Thirdly and perhaps chiefly, it is unclear why this would actually produce a zero knowledge proof, since the same inputs will produce the same circuits and the same output. Thus, I think we can build a distinguisher better than guessing to decide whether two inputs are the same given the same output (and all other inputs being equal).
Maybe these aren't a definitive end point, but they sure as hell require merit investigation.
[1] for more info on these ideas, try these: http://www.win.tue.nl/~berry/2WC13/LectureNotes.pdf (chapter 3) http://en.wikipedia.org/wiki/Commitment_scheme#Defining_the_...