Add support for JSnark / Pinocchio intermediate format

[HarryR]

It would be really good to support the common opcode format used by JSnark/xJSnark and make it Ethereum compatible, the source code looks fairly simple and would be trivial to include in ethsnarks.

This would allow any circuit written using XJSnark and JSnark to be proven on Ethereum.

Relevant papers:

• Pinocchio: Nearly Practical Verifiable Computation - https://eprint.iacr.org/2013/279.pdf
• Pinocchio-Based Adaptive zk-SNARKs and Secure/Correct Adaptive Function Evaluation - https://eprint.iacr.org/2017/013.pdf
• xJsnark: A Framework for Efficient Verifiable Computation - http://www.cs.umd.edu/~akosba/papers/xjsnark.pdf

Relevant source:

• https://github.com/corda/msr-vc/tree/master/pinocchio
• https://github.com/akosba/libsnark/blob/fde8599fc047e9d681ee8f8325913c76de389b55/src/interface/CircuitReader.cpp
• https://github.com/bbuenz/BulletProofLib/blob/master/pinocchioconversion/arithparser3.py
• https://github.com/corda/msr-vc/tree/master/geppetto/code
• https://git.drwx.org/bsc/parity/src/branch/master/ethvc/src/lib.rs
• https://github.com/meilof/geppetri

It would be good to get some static examples of opcodes + inputs, and a way of verifying the circuit and generating witnesses etc.

The Pinocchio compiler and JSnark seem to be generally compatible with each other, and thus I think this is a good direction to go in.

There are also other compilers, but they are more difficult to directly support due to requiring JavaScript or WebAssembly blocks for witness computation, so the circuit cannot be simulated easily...

• https://github.com/iden3/circom/
• https://github.com/JacobEberhardt/ZoKrates
• https://github.com/o1-labs/snarky
• https://github.com/pepper-project/pequin
• Others - https://zkp.science/#general-purpose-compilers-from-high-level-languages

[HarryR]

I have a branch of the pinocchio compiler and the circuit reader from jsnark, am importing circuit reader into the ethsnarks code base (porting to gadgetlib1/ethsnarks etc) and hopefully should have something interesting working soon.

[HarryR]

Making good progress in this branch: https://github.com/HarryR/ethsnarks/tree/pinocchio

However, need to put together some more thorough and verifiable tests for all of the opcodes.

[HarryR]

So, I'm going to be taking the following approach to Pinocchio support:

• Create a circuit_operation class which takes input and output wires, has auxiliary variables, functions to generate a witness, and to generate the constraints
• Split the existing opcodes into instances of circuit_operation class
• Make CircuitReader use these new classes
• Split circuit creation and evaluation, so circuit can be created without inputs
• Separate stage for witnessing from circuit inputs

So, the generic circuit_operaiton class forms the basis. Then there needs to be a circuit_reader class, which parses the input file format into properties and operations. Then construct the circuit from the properties and operations.

Essentially I want to abstract the underlying operations from the input file format, and the circuit as a whole from the operations, so each component can be tested independently.

The downside to this is that every circuit operation will be a virtual class with method dispatch, and the memory overhead will be many times greater compared to what it is now.

I think a more immediately viable interim measure would be to split the existing CircuitReader into two phases for circuit and witness generation, where it operates on lines of text directly.