A moon-math-free (purely symmetric crypto, understandable to
joe-programmer) non-interactive zero-knowledge (NIZK) proof of faithful
execution.

I want to compute a function with some of its inputs kept secret
and (optionally) some inputs which are known to both of us. Then I
want to show you the output and convince you via a proof that the
output was the result of me faithfully executing the agreed function.

And I want to do it without any math fancier than boolean logic and
a cryptographic hash function.

NIZK proofs have many applications, including many interesting ones
in connection with Bitcoin. E.g. Using a ZK proof you can pay someone
who gives you the solution to any problem which verifiable by computer
in a manner where neither party can cheat the other.
(https://en.bitcoin.it/wiki/Zero_Knowledge_Contingent_Payment)

Most current research in this space is mostly focused on efficient
versions where the proofs whos size and validation complexity are
_sub-linear_, or even O(1), in the number of operations the program
performs. These systems require very complex math and complex
cryptographic assumptions.

Even ignoring efficiency, the fact that general program execution can
be proven in zero-knowledge is really surprising to people. As a result
I think it would be useful to have a description of this which is
maximally simple, even if it is less efficient.

The simpler cryptographic assumptions make it more likely that the 
scheme is secure against breakthrough mathematics or quantum computers.
These simplifications, however, mean that it has O(N^2) proof size
and validation time. [Explain why]

Core to this is the idea that you can use a strong cryptographic hash
function H() to commit to a value without revealing what that value is.
E.g. I tell you the Y in H(X)=Y and then later I tell you X and you're
confident that the X I tell you later was the original X.

We first assume that you can convert your program to a fixed binary
circuit consisting of regular logic gates. There are compilers to
translate from C into logic, so this is fully general. 

Lets defined an logic gate as a truth table, e.g. an AND gate:
 in0, in1, out
--------------
   1,   1,   1
   0,   1,   0
   1,   0,   0
   0,   0,   0

We can create an encrypted version of the gate by picking an encryption
key for each wire in/out (e1,e2,e3) and a random permutation

It has a truth table of:  (^ is xor)
  in0,  in1,  out
-----------------
 e1^0, e2^0, e3^0
 e1^1, e2^1, e3^1
 e1^1, e2^0, e3^0
 e1^0, e2^1, e3^0
(the rows are randomly permuted)

In such a scheme you can get a XOR or a NOT gate applied to any wire
in or out "for free": you don't need a separate table, you can also get
constant shifts and rotations and bit permutations for free... because
NOT and XOR commute across the XOR encryption, and all operations are
bit-level.

The gates AND and NOT alone are enough to construct any circuit. So
we'll assume that everything done here is done using our encrypted
AND gates and the XORs and NOTs that we get for free.

Now lets define an adaptation key for two wires. If I have two encrypted
gates, G1 and G2, and I want to re-encrypt the G1's output to make it
compatible with G2's second input, I need to xor it with a key which
decrypts with one key and re-encrypts with another. Because our encryption
is just xor the xor of the two encryption keys (G1.e3 ^ G2.e2) is the key
we need to adapt from one encryption to another because (A^X)^Y == A^(X^Y).
[add concrete example]

Now say we want to prove the execution of a circuit with N gates.

H() is some cryptographic hash function, like SHA256.

I generate 4 * N encrypted gates, all with unique keys.

I generate 4 * N commitments to the encrypted gates:
H(H(H(entry_0)||H(entry_1))||H(H(entry_2)||H(entry_3)))
e.g. each is a hashtree over the truth table.

[A tree structured commitment makes it somewhat more efficient to reveal
single entries at a time because I can reveal three values inseat of four:
e.g. entry_0,H(entry_1),H(H(entry_2)||H(entry_3))]

Then I generate 4 * N commitments to the gate encryption keys as H(H(e1||e2)||e3).

Then I generate 32 * N^2 commitments for the 32 * N^2 adaptation keys between
all possible output and input wires in the set of gates. H(adapt_Gx.e3_Gy.e[1,2])

I also commit to the encrypted original inputs and the decrypted final
answers, as well as adaptation keys to wire any up any of the inputs/outputs
to any of the gates.

I send the commitments to you.

I then compute the hash of all the commitments.

I use the resulting super-commitment to select a random permutation of the encrypted
gates. E.g. I use that hash to initialize a random shuffle on the gates.

Then I reveal the gates and their encryption keys for the first half of the gates
in the shuffled list.

With this data you can validate that the gates were valid (e.g. were actually
AND gates), that they matched their commitments, that the encryption keys
match the commitments, and that all the implicitly revealed adaptation keys
match their commitments.

I take the original circuit and replace every AND gate with two AND gates
in parallel, and a check that they produce the same answer.

Now I take the other half of the encrypted gates that weren't revealed
and drop them into the circuit, in order.

I reveal the relevant adaption keys for the resulting topology.

I reveal the single truth table entry used for each gate in the execution,
and the additional hashes to prove it is the correct entry in the committed
gate.

I reveal the encryption keys for the final output wires.

You can be confident that my execution is faithful because if I inserted a
bad gate or adaptation key in the set it would have been likely to be detected
in either the half that I revealed, or by a disagreement between duplicated gates in the circuit.

Security can be adjusted by increasing the gate duplication or adjusting the
number of unused extra gates which are revealed. With a sutiable choice in
parameters the probablity of cheating detection can be made overwhemingly large.

The N^2 blowup could be eliminated if the gate encryption keys were
committed with a strong hash function which was commutative for XOR, but
this appears to require fancy crypto or interaction[1]. With this you
don't need the N^2 adaption key commitments because you can just
compose the encryption key commitments.

([1] https://eprint.iacr.org/2013/155.pdf )