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:
reducing data footprint of an arithmetic circuit by at least:
removing a first subset of data fields of a set of data fields associated with the arithmetic circuit, wherein the first subset of the data fields is obtainable from a second subset of the data fields of the set of the data fields, the first subset and the second subset being disjoint sets; and
applying an entropy coding scheme to the second subset to produce a compressed arithmetic circuit;
causing the compressed arithmetic circuit to be stored; and
generating a serialised circuit comprising:
a result based at least in part on applying the entropy coding scheme on the second subset; and
a header data structure, the header data structure comprising:
a version number; and
a total number of wires.
2. The computer-implemented method claimed in claim 1 , wherein the first subset of the data fields comprises identifiers of a set of inputs to the arithmetic circuit and the second subset comprises a cardinality of the set of inputs.
3. The computer-implemented method claimed in claim 1 , wherein the first subset of the data fields comprises identifiers of a set of gate outputs of the arithmetic circuit.
4. The computer-implemented method claimed in claim 1 , wherein:
the second subset comprises a set of gates; and
the first subset comprises a first input of a first gate of the set of gates.
5. The computer-implemented method claimed in claim 1 , wherein:
the second subset comprises a set of gates; and
the first subset comprises a last output of a last gate of the set of gates.
6. The computer-implemented method claimed in claim 1 , wherein applying the entropy coding scheme to the second subset comprises:
determining a set of symbols from the second subset; and
assigning, to each symbol of the set of symbols, a corresponding code.
7. The computer-implemented method claimed in claim 6 , wherein a symbol of the set of symbols is repeated at least twice in the second subset.
8. The computer-implemented method claimed in claim 6 , wherein a length of a code is inversely proportional to a frequency of the symbol that corresponds to the code.
9. The computer-implemented method claimed in claim 6 , wherein codes corresponding to symbols of the set of symbols are generated according to a Huffman code.
10. The computer-implemented method claimed in claim 1 , wherein the header data structure further comprises a bit-width usable to enable execution optimisations based at least in part on a target architecture.
11. The computer-implemented method claimed in claim 1 , herein the version number indicates a coding scheme usable to determine symbols from codes.
12. The computer-implemented method claimed in claim 1 , wherein the arithmetic circuit is architecture independent.
13. A system, comprising:
a processor; and
memory including executable instructions that, as a result of execution by the processor, cause the system to:
reduce data footprint of an arithmetic circuit by at least:
removing a first subset of data fields of a set of data fields associated with the arithmetic circuit, wherein the first subset of the data fields is obtainable from a second subset of the data fields of the set of the data fields, the first subset and the second subset being disjoint sets; and
applying an entropy coding scheme to the second subset to produce a compressed arithmetic circuit;
cause the compressed arithmetic circuit to be stored; and
generate a serialised circuit comprising:
a result based at least in part on applying the entropy coding scheme on the second subset; and
a header data structure, the header data structure comprising:
a version number; and
a total number of wires.
14. A non-transitory computer-readable storage medium having stored thereon executable instructions that, as a result of being executed by a processor of a computer system, cause the computer system to at least perform the computer-implemented method of claim 1 .
15. The system of claim 13 wherein the first subset of the data fields comprises identifiers of a set of inputs to the arithmetic circuit and the second subset comprises a cardinality of the set of inputs.
16. The system of claim 13 wherein the first subset of the data fields comprises identifiers of a set of gate outputs of the arithmetic circuit.
17. The system of claim 13 wherein:
the second subset comprises a set of gates; and
the first subset comprises a first input of a first gate of the set of gates.
18. A non-transitory computer-readable storage medium having stored thereon executable instructions that, as a result of being executed by a processor of a computer system, cause the computer system to at least perform the computer-implemented method of claim 2 .
19. A non-transitory computer-readable storage medium having stored thereon executable instructions that, as a result of being executed by a processor of a computer system, cause the computer system to at least perform the computer-implemented method of claim 3 .