Idea: zkSNARKs for Neural Networks

It might be possible to use zkSNARKs for verifying computations of neural networks quite efficiently. The reason is that a single multiplication gate might suffice to model a neuron if the activation function of the neuron is a rational function. This means that the number of gates will be quite small. We still have the problem that the number of wires is extremely large. The scheme by Groth (On the Size of Pairing-based Non-interactive Arguments) trades complexity in the number of multiplication gates for the number of wires, so that might be feasible (and the Groth scheme can be implemented with the planned precompiles).

If the weights of a neural network are public, it is quite easy to fool it (you analyze the network like you do in backpropagation). On the other hand, there are also use-cases where the weights are private. In this use-case, there would be a fixed SNARK for a universal neural network of a fixed size and topology (all of them sharing the trusted setup). The weights would be part of the private input. If you do not do anything else, the prover can prove anything about the input. Because of that, the universal neural network also has a component that computes a hash of the weights which is part of the input. That way, the input selects a neural network by the hash of its weights. The prover can now evaluate the neural network and create a zkSNARK showing that it computes a certain result.

There are not too many rational activation functions and in the general circuit model of zkSNARKs, a polynomial would not be a good fit as e.g. `y = x^3` does not have a large slope at `x=0`. Here, we have to think of zkSNARKs less in the circuit model but rather in the "set of polynomial equations" model: The function `y^3 = x` is already quite close to the arc targent or some other step function and can be realized with only two constraints or "gates". Another activation function is the "bent identity": `y = (sqrt(x^2 + 1) - 1) / 2 + x` - this one can be realized with just a single gate.

The issue names no files, tests, or entry points. Start by reviewing the proposed zkSNARK model, Groth's pairing-based argument scheme, and the neural-network constraints described here. There is no concrete implementation target or testable definition of done in the issue.

Written by the indexing model from the issue text.