Computer-implemented systems and methods for serialisation of arithmetic circuits
Techniques described herein may be utilized to serialise and de-serialise arithmetic circuits that are utilized in the execution of computer programs. The arithmetic circuit may be utilized to build a Quadratic Arithmetic Problem (QAP) that is compiled into a set of cryptographic routines for a client and a prover. The client and prover may utilize a protocol to delegate execution of a program to the prover in a manner that allows the client to efficiently verify the prover correctly executed the program. The arithmetic circuit may comprise a set of symbols (e.g., arithmetic gates and values) that is compressed to produce a serialised circuit comprising a set of codes, wherein the set of symbols is derivable from the set of codes in a lossless manner. Serialisation and de-serialisation techniques may be utilized by nodes of a blockchain network.
1. A computer-implemented method comprising:
at a client node, compiling a computation into an arithmetic circuit comprising wires that carry values from a field and connect to addition and multiplication gates, further comprising supplying the arithmetic circuit and an input x to a worker node;
at the worker node, executing the arithmetic circuit on the input x, resulting in an output , encoding a transcript for { , x, }, and providing the output y to the client node, wherein a valid transcript for { , x, } is an assignment of values to circuit wires such that the values assigned to input wires are those of x, intermediate values correspond to a correct operation of a plurality of gates in , and values assigned to output wire(s) ; and
at a verifier node, validating a blockchain transaction.
2. The computer-implemented method of claim 1 , wherein the arithmetic circuit is a physical circuit having wires and logic gates.
3. The computer-implemented method of claim 1 , wherein the arithmetic circuit is a DAG, and the wires are edges in the DAG.
4. The computer-implemented method of claim 1 , wherein from the circuit , a quadratic program is generated that includes a set of polynomials that provide a complete description of the original circuit .
5. The computer-implemented method of claim 4 , wherein public parameters are generated to be used by the worker node and the verifier node in performing and verifying the quadratic program.
6. The computer-implemented method of claim 1 , further comprising deriving a public evaluation key EK and a public verification key VK using a secret value s selected by or from the client node.
7. The computer-implemented method of claim 6 , wherein the worker node uses the public evaluation key and the public verification key to evaluate the computation on a particular input x.
8. The computer-implemented method of claim 7 , wherein the output , values of internal circuit wires, and EK are used to produce a proof-of-correctness π.
9. The computer-implemented method of claim 8 , wherein the proof-of-correctness π is stored on a blockchain and verified by the verifier node without requiring the worker node to separately interact with the verifier node.
10. The computer-implemented method of claim 8 , wherein the verifier node validates the payment transaction using the public verification key VK and the proof-of-correctness π.
11. A system comprising:
a client node, a worker node, and a verifier node each comprising a processor and a memory including executable instructions that, as a result of execution by the processor, cause the system to:
at the client node, compile a computation into an arithmetic circuit comprising wires that carry values from a field and connect to addition and multiplication gates, supply the arithmetic circuit and an input x to the worker node;
at the worker node, execute the arithmetic circuit on the input x, outputting , encode a transcript for { , x, }, and provide the output to the client node, wherein a valid transcript for { , x, } is an assignment of values to circuit wires such that the values assigned to input wires are those of x, intermediate values correspond to a correct operation of a plurality of gates in , and values assigned to output wire(s) is ; and
at the verifier node, validate a blockchain transaction.
12. The system of claim 11 , wherein the arithmetic circuit is a physical circuit having wires and logic gates.
13. The system of claim 11 , wherein the arithmetic circuit is a DAG, and the wires are edges in the DAG.
14. The system of claim 11 , wherein from the circuit , a quadratic program is generated that includes a set of polynomials that provide a complete description of the original circuit .
15. The system of claim 14 , wherein public parameters are generated to be used by the worker node and the verifier node in performing and verifying the quadratic program.
16. The system of claim 11 , further comprising deriving a public evaluation key EK and a public verification key VK using a secret value s selected by or from the client node.
17. The system of claim 16 , wherein the worker node uses the public evaluation key and the public verification key to evaluate the computation on a particular input x.
18. The system of claim 17 , wherein the output , values of internal circuit wires, and EK are used to produce a proof-of-correctness π.