circom/doc/r1cs_bin_format.md
doc/r1cs_bin_format.mdRaw
1# Binary format for R1CS
2
3---
4eip:
5title: r1cs binary format
6author: Jordi Baylina <jordi@baylina.cat>
7discussions-to:
8status: draft
9type: Standards Track
10category: ERC
11created: 2019-09-24
12requires:
13---
14
15## Simple Summary
16
17This standard defines a standard format for a binery representation of a r1cs constraint system.
18
19## Abstract
20
21
22## Motivation
23
24The zero knowledge primitives, requires the definition of a statment that wants to be proved. This statment can be expressed as a deterministric program or an algebraic circuit. Lots of primitives like zkSnarks, bulletProofs or aurora, requires to convert this statment to a rank-one constraint system.
25
26This standard specifies a format for a r1cs and allows the to connect a set of tools that compiles a program or a circuit to r1cs that can be used for the zksnarks or bulletproofs primitives.
27
28## Specification
29
30### General considerations
31
32The standard extension is `.r1cs`
33
34
35A deterministic program (or circuit) is a program that generates a set of deterministic values given an input. All those values are labeled from l_{0} to l_{n_labels}
36
37This file defines a map beween l_{i} -> w_{j} and defines a series a R1CS of the form
38
39$$
40\left\{ \begin{array}{rclclcl}
41(a_{0,0}w_0 + a_{0,1}w_1 + ... + a_{0,n}w_{n}) &\cdot& (b_{0,0} w_0 + b_{0,1} w_1 + ... + b_{0,n} w_{n}) &-& (c_{0,0} w_0 + c_{0,1} w_1 + ... + c_{0,n}w_{n}) &=& 0 \\
42(a_{1,0}w_0 + a_{1,1}w_1 + ... + a_{1,n}w_{n}) &\cdot& (b_{1,0} w_0 + b_{1,1} w_1 + ... + b_{1,n} w_{n}) &-& (c_{1,0} w_0 + c_{1,1}w_1 + ... + c_{1,n}w_{n}) &=& 0 \\
43...\\
44(a_{m-1,0}w_0 + a_{m-1,1}w_1 + ... + a_{m-1,n}w_{n}) &\cdot& (b_{m-1,0} w_0 + b_{m-1,1} w_1 + ... + b_{m-1,n} w_{n}) &-& (c_{m-1,0} w_0 + c_{m-1,1}w_1 + ... + c_{m-1,n}w_{n}) &=& 0
45 \end{array} \right.
46$$
47
48Wire 0 must be always mapped to label 0 and it's an input forced to value "1" implicitly
49
50
51### Format of the file
52
53````
54
55 ┏━━━━┳━━━━━━━━━━━━━━━━━┓
56 ┃ 4 │ 72 31 63 73 ┃ Magic "r1cs"
57 ┗━━━━┻━━━━━━━━━━━━━━━━━┛
58 ┏━━━━┳━━━━━━━━━━━━━━━━━┓
59 ┃ 4 │ 01 00 00 00 ┃ Version 1
60 ┗━━━━┻━━━━━━━━━━━━━━━━━┛
61 ┏━━━━┳━━━━━━━━━━━━━━━━━┓
62 ┃ 4 │ 03 00 00 00 ┃ Number of Sections
63 ┗━━━━┻━━━━━━━━━━━━━━━━━┛
64 ┏━━━━┳━━━━━━━━━━━━━━━━━┳━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━┓
65 ┃ 4 │ sectionType ┃ 8 │ SectionSize ┃
66 ┗━━━━┻━━━━━━━━━━━━━━━━━┻━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━┛
67 ┏━━━━━━━━━━━━━━━━━━━━━┓
68 ┃ ┃
69 ┃ ┃
70 ┃ ┃
71 ┃ Section Content ┃
72 ┃ ┃
73 ┃ ┃
74 ┃ ┃
75 ┗━━━━━━━━━━━━━━━━━━━━━┛
76
77 ┏━━━━┳━━━━━━━━━━━━━━━━━┳━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━┓
78 ┃ 4 │ sectionType ┃ 8 │ SectionSize ┃
79 ┗━━━━┻━━━━━━━━━━━━━━━━━┻━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━┛
80 ┏━━━━━━━━━━━━━━━━━━━━━┓
81 ┃ ┃
82 ┃ ┃
83 ┃ ┃
84 ┃ Section Content ┃
85 ┃ ┃
86 ┃ ┃
87 ┃ ┃
88 ┗━━━━━━━━━━━━━━━━━━━━━┛
89
90 ...
91 ...
92 ...
93````
94
95#### Magic Number
96
97Size: 4 bytes
98The file start with a constant 4 bytes (magic number) "r1cs"
99
100```
1010x72 0x31 0x63 0x73
102```
103
104#### Version
105
106Size: 4 bytes
107Format: Little-Endian
108
109For this standard it's fixed to
110
111```
1120x01 0x00 0x00 0x00
113```
114
115#### Number of Sections
116
117Size: 4 bytes
118Format: Little-Endian
119
120Number of sections contained in the file
121
122#### SectionType
123
124Size: 4 bytes
125Format: Little-Endian
126
127Type of the section.
128
129Currently there are 3 types of sections defined:
130
131* 0x00000001 : Header Section
132* 0x00000002 : Constraint Section
133* 0x00000003 : Wire2LabelId Map Section
134
135If the file contain other types, the format is valid, but they MUST be ignored.
136
137Any order of the section must be accepted.
138
139Example:
140```
1410x01 0x00 0x00 0x00
142```
143
144#### SectionSize
145
146Size: `ws` bytes
147Format: Little-Endian
148
149Size in bytes of the section
150
151### Header Section
152
153Section Type: 0x01
154````
155 ┏━━━━┳━━━━━━━━━━━━━━━━━┓
156 ┃ 4 │ 20 00 00 00 ┃ Field Size in bytes (fs)
157 ┗━━━━┻━━━━━━━━━━━━━━━━━┛
158 ┏━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
159 ┃ fs │ 010000f0 93f5e143 9170b979 48e83328 5d588181 b64550b8 29a031e1 724e6430 ┃ Prime size
160 ┗━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
161 ┏━━━━┳━━━━━━━━━━━━━━━━━┓
162 ┃ 32 │ 01 00 00 00 ┃ nWires
163 ┗━━━━┻━━━━━━━━━━━━━━━━━┛
164 ┏━━━━┳━━━━━━━━━━━━━━━━━┓
165 ┃ 32 │ 01 00 00 00 ┃ nPubOut
166 ┗━━━━┻━━━━━━━━━━━━━━━━━┛
167 ┏━━━━┳━━━━━━━━━━━━━━━━━┓
168 ┃ 32 │ 01 00 00 00 ┃ nPubIn
169 ┗━━━━┻━━━━━━━━━━━━━━━━━┛
170 ┏━━━━┳━━━━━━━━━━━━━━━━━┓
171 ┃ 32 │ 01 00 00 00 ┃ nPrvIn
172 ┗━━━━┻━━━━━━━━━━━━━━━━━┛
173 ┏━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
174 ┃ 64 │ 01 00 00 00 00 00 00 00 ┃ nLabels
175 ┗━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
176 ┏━━━━┳━━━━━━━━━━━━━━━━━┓
177 ┃ 32 │ 01 00 00 00 ┃ mConstraints
178 ┗━━━━┻━━━━━━━━━━━━━━━━━┛
179
180
181````
182
183#### field Size (fs)
184
185Size: 4 bytes
186Format: Little-Endian
187
188Size in bytes of a field element. Mast be a multiple of 8.
189
190Example:
191```
1920x00 0x0 0x00 0x00
193```
194
195#### Prime
196
197Prime Number of the field
198
199Example:
200```
2010x010000f0_93f5e143_9170b979_48e83328_5d588181_b64550b8_29a031e1_724e6430
202```
203
204#### Number of wires
205
206Size: 4 bytes
207Format: Little-Endian
208
209Total Number of wires including ONE signal (Index 0).
210
211#### Number of public outputs
212
213Size: 4 bytes
214Format: Little-Endian
215
216Total Number of wires public output wires. They should be starting at idx 1
217
218#### Number of public inputs
219
220Size: 4 bytes
221Format: Little-Endian
222
223Total Number of wires public input wires. They should be starting just after the public output
224
225#### Number of private inputs
226
227Size: 4 bytes
228Format: Little-Endian
229
230Total Number of wires private input wires. They should be starting just after the public inputs
231
232#### Number of Labels
233
234Size: 8 bytes
235Format: Little-Endian
236
237Total Number of wires private input wires. They should be starting just after the public inputs
238
239#### Number of constraints (m)
240
241Size: 4 bytes
242Format: Little-Endian
243
244Total Number of constraints
245
246### Constraints section
247
248Section Type: 0x02
249
250````
251 ┏━━━━┳━━━━━━━━━━━━━━━━━┓ ╲
252 ┃ 32 │ nA ┃ ╲
253 ┣━━━━╋━━━━━━━━━━━━━━━━━╋━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━┓ ╲
254 ┃ 32 │ wireId_1 ┃ fs │ a_{0,wireId_1} ┃ │
255 ┣━━━━╋━━━━━━━━━━━━━━━━━╋━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━┫ │
256 ┃ 32 │ wireId_2 ┃ fs │ a_{0,wireId_2} ┃ │
257 ┗━━━━┻━━━━━━━━━━━━━━━━━┻━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━┛ │
258 ... ... │
259 ┏━━━━┳━━━━━━━━━━━━━━━━━┳━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━┓ │
260 ┃ 32 │ wireId_nA ┃ fs │ a_{0,wireId_nA} ┃ │
261 ┗━━━━┻━━━━━━━━━━━━━━━━━┻━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━┛ │
262 ┏━━━━┳━━━━━━━━━━━━━━━━━┓ │
263 ┃ 32 │ nB ┃ │
264 ┣━━━━╋━━━━━━━━━━━━━━━━━╋━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━┓ │
265 ┃ 32 │ wireId_1 ┃ fs │ b_{0,wireId_1} ┃ │
266 ┣━━━━╋━━━━━━━━━━━━━━━━━╋━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━┫ ╲
267 ┃ 32 │ wireId_2 ┃ fs │ b_{0,wireId_2} ┃ ╲
268 ┗━━━━┻━━━━━━━━━━━━━━━━━┻━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━┛ ╱ Constraint_0
269 ... ... ╱
270 ┏━━━━┳━━━━━━━━━━━━━━━━━┳━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━┓ │
271 ┃ 32 │ wireId_nB ┃ fs │ b_{0,wireId_nB} ┃ │
272 ┗━━━━┻━━━━━━━━━━━━━━━━━┻━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━┛ │
273 ┏━━━━┳━━━━━━━━━━━━━━━━━┓ │
274 ┃ 32 │ nC ┃ │
275 ┣━━━━╋━━━━━━━━━━━━━━━━━╋━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━┓ │
276 ┃ 32 │ wireId_1 ┃ fs │ c_{0,wireId_1} ┃ │
277 ┣━━━━╋━━━━━━━━━━━━━━━━━╋━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━┫ │
278 ┃ 32 │ wireId_2 ┃ fs │ c_{0,wireId_2} ┃ │
279 ┗━━━━┻━━━━━━━━━━━━━━━━━┻━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━┛ │
280 ... ... │
281 ┏━━━━┳━━━━━━━━━━━━━━━━━┳━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━┓ │
282 ┃ 32 │ wireId_nC ┃ fs │ c_{0,wireId_nC} ┃ ╱
283 ┗━━━━┻━━━━━━━━━━━━━━━━━┻━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━┛ ╱
284 ╱
285
286
287 ┏━━━━┳━━━━━━━━━━━━━━━━━┓ ╲
288 ┃ 32 │ nA ┃ ╲
289 ┣━━━━╋━━━━━━━━━━━━━━━━━╋━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━┓ ╲
290 ┃ 32 │ wireId_1 ┃ fs │ a_{1,wireId_1} ┃ │
291 ┣━━━━╋━━━━━━━━━━━━━━━━━╋━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━┫ │
292 ┃ 32 │ wireId_2 ┃ fs │ a_{1,wireId_2} ┃ │
293 ┗━━━━┻━━━━━━━━━━━━━━━━━┻━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━┛ │
294 ... ... │
295 ┏━━━━┳━━━━━━━━━━━━━━━━━┳━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━┓ │
296 ┃ 32 │ wireId_nA ┃ fs │ a_{1,wireId_nA} ┃ │
297 ┗━━━━┻━━━━━━━━━━━━━━━━━┻━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━┛ │
298 ┏━━━━┳━━━━━━━━━━━━━━━━━┓ │
299 ┃ 32 │ nB ┃ │
300 ┣━━━━╋━━━━━━━━━━━━━━━━━╋━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━┓ │
301 ┃ 32 │ wireId_1 ┃ fs │ b_{1,wireId_1} ┃ │
302 ┣━━━━╋━━━━━━━━━━━━━━━━━╋━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━┫ ╲
303 ┃ 32 │ wireId_2 ┃ fs │ b_{1,wireId_2} ┃ ╲
304 ┗━━━━┻━━━━━━━━━━━━━━━━━┻━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━┛ ╱ Constraint_1
305 ... ... ╱
306 ┏━━━━┳━━━━━━━━━━━━━━━━━┳━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━┓ │
307 ┃ 32 │ wireId_nB ┃ fs │ b_{1,wireId_nB} ┃ │
308 ┗━━━━┻━━━━━━━━━━━━━━━━━┻━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━┛ │
309 ┏━━━━┳━━━━━━━━━━━━━━━━━┓ │
310 ┃ 32 │ nC ┃ │
311 ┣━━━━╋━━━━━━━━━━━━━━━━━╋━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━┓ │
312 ┃ 32 │ wireId_1 ┃ fs │ c_{1,wireId_1} ┃ │
313 ┣━━━━╋━━━━━━━━━━━━━━━━━╋━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━┫ │
314 ┃ 32 │ wireId_2 ┃ fs │ c_{1,wireId_2} ┃ │
315 ┗━━━━┻━━━━━━━━━━━━━━━━━┻━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━┛ │
316 ... ... │
317 ┏━━━━┳━━━━━━━━━━━━━━━━━┳━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━┓ │
318 ┃ 32 │ wireId_nC ┃ fs │ c_{1,wireId_nC} ┃ ╱
319 ┗━━━━┻━━━━━━━━━━━━━━━━━┻━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━┛ ╱
320 ╱
321
322 ...
323 ...
324 ...
325
326 ┏━━━━┳━━━━━━━━━━━━━━━━━┓ ╲
327 ┃ 32 │ nA ┃ ╲
328 ┣━━━━╋━━━━━━━━━━━━━━━━━╋━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━┓ ╲
329 ┃ 32 │ wireId_1 ┃ fs │ a_{m-1,wireId_1} ┃ │
330 ┣━━━━╋━━━━━━━━━━━━━━━━━╋━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━┫ │
331 ┃ 32 │ wireId_2 ┃ fs │ a_{m-1,wireId_2} ┃ │
332 ┗━━━━┻━━━━━━━━━━━━━━━━━┻━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━┛ │
333 ... ... │
334 ┏━━━━┳━━━━━━━━━━━━━━━━━┳━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━┓ │
335 ┃ 32 │ wireId_nA ┃ fs │ a_{m-1,wireId_nA} ┃ │
336 ┗━━━━┻━━━━━━━━━━━━━━━━━┻━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━┛ │
337 ┏━━━━┳━━━━━━━━━━━━━━━━━┓ │
338 ┃ 32 │ nB ┃ │
339 ┣━━━━╋━━━━━━━━━━━━━━━━━╋━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━┓ │
340 ┃ 32 │ wireId_1 ┃ fs │ b_{m-1,wireId_1} ┃ │
341 ┣━━━━╋━━━━━━━━━━━━━━━━━╋━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━┫ ╲
342 ┃ 32 │ wireId_2 ┃ fs │ b_{m-1,wireId_2} ┃ ╲
343 ┗━━━━┻━━━━━━━━━━━━━━━━━┻━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━┛ ╱ Constraint_{m-1}
344 ... ... ╱
345 ┏━━━━┳━━━━━━━━━━━━━━━━━┳━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━┓ │
346 ┃ 32 │ wireId_nB ┃ fs │ b_{m-1,wireId_nB} ┃ │
347 ┗━━━━┻━━━━━━━━━━━━━━━━━┻━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━┛ │
348 ┏━━━━┳━━━━━━━━━━━━━━━━━┓ │
349 ┃ 32 │ nC ┃ │
350 ┣━━━━╋━━━━━━━━━━━━━━━━━╋━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━┓ │
351 ┃ 32 │ wireId_1 ┃ fs │ c_{m-1,wireId_1} ┃ │
352 ┣━━━━╋━━━━━━━━━━━━━━━━━╋━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━┫ │
353 ┃ 32 │ wireId_2 ┃ fs │ c_{m-1,wireId_2} ┃ │
354 ┗━━━━┻━━━━━━━━━━━━━━━━━┻━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━┛ │
355 ... ... │
356 ┏━━━━┳━━━━━━━━━━━━━━━━━┳━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━┓ │
357 ┃ 32 │ wireId_nC ┃ fs │ c_{m-1,wireId_nC} ┃ ╱
358 ┗━━━━┻━━━━━━━━━━━━━━━━━┻━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━┛ ╱
359 ╱
360````
361
362
363
364#### Constraints
365
366Each constraint contains 3 linear combinations A, B, C.
367
368The constraint is such that:
369```
370A*B-C = 0
371```
372
373#### Linear combination
374
375Each linear combination is of the form:
376
377$$
378a_{j,0}w_0 + a_{j,1}w_1 + ... + a_{j,n}w_{n}
379$$
380
381#### Number of nonZero Factors
382
383Size: 4 bytes
384Format: Little-Endian
385
386Total number of non Zero factors in the linear compination.
387
388The factors MUST be sorted in ascending order.
389
390#### Factor
391
392For each factor we have the index of the factor and the value of the factor.
393
394#### WireId of the factor
395
396Size: 4 bytes
397Format: Little-Endian
398
399WireId of the nonZero Factor
400
401#### Value of the factor
402
403This is the factor that multiplies the associated wire in the linear convination.
404
405For example, to represent the linear combination:
406
407$$
4085w_4 +8w_5 + 260w_{886}
409$$
410
411The linear combination would be represented as:
412
413````
414 ┏━━━━━━━━━━━━━━━━━┓
415 ┃ 03 00 00 00 ┃
416 ┣━━━━━━━━━━━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
417 ┃ 04 00 00 00 ┃ 05000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 ┃
418 ┣━━━━━━━━━━━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫
419 ┃ 05 00 00 00 ┃ 08000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 ┃
420 ┣━━━━━━━━━━━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫
421 ┃ 76 03 00 00 ┃ 04010000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 ┃
422 ┗━━━━━━━━━━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
423````
424
425
426### WireId2LabelId Map Section
427
428Section Type: 0x03
429
430````
431┏━━┳━━━━━━━━━━━━━━━━━━━┳━━┳━━━━━━━━━━━━━━━━━━━┓ ┏━━┳━━━━━━━━━━━━━━━━━━━┓
432┃64│ labelId of Wire_0 ┃64│ labelId of Wire_1 ┃ ... ┃64│ labelId of Wire_n ┃
433┗━━┻━━━━━━━━━━━━━━━━━━━┻━━┻━━━━━━━━━━━━━━━━━━━┛ ┗━━┻━━━━━━━━━━━━━━━━━━━┛
434````
435
436## Rationale
437
438Variable size for field elements allows to shrink the size of the file and allows to work with any field.
439
440Version allows to update the format.
441
442Have a very good comprasion ratio for sparse r1cs as it's the normal case.
443
444The motivation of having a map between l and w is that this allows optimizers to calculate equivalent r1cs systems but keeping the original values geneated by the circuit.
445
446
447## Backward Compatibility
448
449N.A.
450
451## Test Cases
452### Example
453
454Given this r1cs in a 256 bit Field:
455
456
457$$
458\left\{ \begin{array}{rclclcl}
459(3w_5 + 8w_6) &\cdot& (2w_0 + 20w_2 + 12w_3) &-& (5w_0 + 7w_2) &=& 0 \\
460(4w_1 + 8w_4 + 3w_5) &\cdot& (6w_6 + 44w_3) && &=& 0 \\
461(4w_6) &\cdot& (6w_0 + 5w_3 + 11s_2) &-& (600w_6) &=& 0
462\end{array} \right.
463$$
464
465And a Wire to label map.
466
467$$
468w_0 := l_0 \\
469w_1 := l_3 \\
470w_2 := l_{10} \\
471w_3 := l_{11} \\
472w_4 := l_{12} \\
473w_5 := l_{15} \\
474w_6 := l_{324} \\
475$$
476
477The format will be:
478
479````
480 ┏━━━━━━━━━━┓
481 ┃ 72316377 ┃ Magic
482 ┣━━━━━━━━━━┫
483 ┃ 01000000 ┃ Version
484 ┣━━━━━━━━━━┫
485 ┃ 03000000 ┃ nSections
486 ┗━━━━━━━━━━┛
487 ┏━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━┓
488 ┃ 01000000 ┃ 40000000 00000000 ┃ SectionType: Header
489 ┗━━━━━━━━━━┻━━━━━━━━━━━━━━━━━━━┛
490 ┏━━━━━━━━━━┓
491 ┃ 20000000 ┃ Field Size
492 ┣━━━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
493 ┃ 010000f0 93f5e143 9170b979 48e83328 5d588181 b64550b8 29a031e1 724e6430 ┃
494 ┣━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
495 ┃ 07000000 ┃ # of wires
496 ┣━━━━━━━━━━┫
497 ┃ 01000000 ┃ # Public Outs
498 ┣━━━━━━━━━━┫
499 ┃ 02000000 ┃ # Public Ins
500 ┣━━━━━━━━━━┫
501 ┃ 03000000 ┃ # Private Ins
502 ┣━━━━━━━━━━┻━━━━━━━━┓
503 ┃ e8030000 00000000 ┃ # Labels
504 ┣━━━━━━━━━━┳━━━━━━━━┛
505 ┃ 03000000 ┃ # Constraints
506 ┗━━━━━━━━━━┛
507 ┏━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━┓
508 ┃ 02000000 ┃ 88200000 00000000 ┃ SectionType: Constraints
509 ┗━━━━━━━━━━┻━━━━━━━━━━━━━━━━━━━┛
510 ┏━━━━━━━━━━┓ Constraint 0: (3w_5 + 8w_6) * (2w_0 + 20w_2 + 12w_3) - (5w_0 + 7w_2) = 0
511 ┃ 02000000 ┃
512 ┣━━━━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
513 ┃ 05000000 ┃ 03000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 ┃
514 ┣━━━━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫
515 ┃ 06000000 ┃ 01000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 ┃
516 ┗━━━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
517 ┏━━━━━━━━━━┓
518 ┃ 03000000 ┃
519 ┣━━━━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
520 ┃ 00000000 ┃ 02000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 ┃
521 ┣━━━━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫
522 ┃ 02000000 ┃ 01140000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 ┃
523 ┣━━━━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫
524 ┃ 03000000 ┃ 0C000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 ┃
525 ┗━━━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
526 ┏━━━━━━━━━━┓
527 ┃ 02000000 ┃
528 ┣━━━━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
529 ┃ 00000000 ┃ 05000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 ┃
530 ┣━━━━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫
531 ┃ 02000000 ┃ 07000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 ┃
532 ┗━━━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
533
534 ┏━━━━━━━━━━┓ Constraint 1: (4w_1 + 8w_4 + 3w_5) * (6w_6 + 44w_3) = 0
535 ┃ 03000000 ┃
536 ┣━━━━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
537 ┃ 01000000 ┃ 04000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 ┃
538 ┣━━━━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫
539 ┃ 04000000 ┃ 08000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 ┃
540 ┣━━━━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫
541 ┃ 05000000 ┃ 03000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 ┃
542 ┗━━━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
543 ┏━━━━━━━━━━┓
544 ┃ 02000000 ┃
545 ┣━━━━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
546 ┃ 03000000 ┃ 2C000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 ┃
547 ┣━━━━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫
548 ┃ 06000000 ┃ 06000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 ┃
549 ┗━━━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
550 ┏━━━━━━━━━━┓
551 ┃ 00000000 ┃
552 ┗━━━━━━━━━━┛
553
554 ┏━━━━━━━━━━┓ Constraint 2: (4w_6) * (6w_0 + 5w_3 + 11w_2) - (600w_6) = 0
555 ┃ 01000000 ┃
556 ┣━━━━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
557 ┃ 06000000 ┃ 04000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 ┃
558 ┗━━━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
559 ┏━━━━━━━━━━┓
560 ┃ 03000000 ┃
561 ┣━━━━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
562 ┃ 00000000 ┃ 06000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 ┃
563 ┣━━━━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫
564 ┃ 02000000 ┃ 0B000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 ┃
565 ┣━━━━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫
566 ┃ 03000000 ┃ 05000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 ┃
567 ┗━━━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
568 ┏━━━━━━━━━━┓
569 ┃ 01000000 ┃
570 ┣━━━━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
571 ┃ 06000000 ┃ 58020000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 ┃
572 ┗━━━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
573
574 ┏━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━┓
575 ┃ 03000000 ┃ 38000000 00000000 ┃ Wire to Label Map
576 ┗━━━━━━━━━━┻━━━━━━━━━━━━━━━━━━━┛
577 ┏━━━━━━━━━━━━━━━━━━━┓
578 ┃ 00000000 00000000 ┃
579 ┣━━━━━━━━━━━━━━━━━━━┫
580 ┃ 03000000 00000000 ┃
581 ┣━━━━━━━━━━━━━━━━━━━┫
582 ┃ 0a000000 00000000 ┃
583 ┣━━━━━━━━━━━━━━━━━━━┫
584 ┃ 0b000000 00000000 ┃
585 ┣━━━━━━━━━━━━━━━━━━━┫
586 ┃ 0c000000 00000000 ┃
587 ┣━━━━━━━━━━━━━━━━━━━┫
588 ┃ 0f000000 00000000 ┃
589 ┣━━━━━━━━━━━━━━━━━━━┫
590 ┃ 44010000 00000000 ┃
591 ┗━━━━━━━━━━━━━━━━━━━┛
592````
593
594And the binary representation in Hex:
595
596````
59772316377
59801000000
59903000000
60001000000 40000000 00000000
60120000000
602010000f0 93f5e143 9170b979 48e83328 5d588181 b64550b8 29a031e1 724e6430
60307000000
60401000000
60502000000
60603000000
607e8030000 00000000
60803000000
60902000000 88200000 00000000
61002000000
61105000000 03000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
61206000000 01000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
61303000000
61400000000 02000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
61502000000 01140000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
61603000000 0C000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
61702000000
61800000000 05000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
61902000000 07000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
62003000000
62101000000 04000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
62204000000 08000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
62305000000 03000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
62402000000
62503000000 2C000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
62606000000 06000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
62700000000
62801000000
62906000000 04000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
63003000000
63100000000 06000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
63202000000 0B000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
63303000000 05000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
63401000000
63506000000 58020000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
63603000000 38000000 00000000
63700000000 00000000
63803000000 00000000
6390a000000 00000000
6400b000000 00000000
6410c000000 00000000
6420f000000 00000000
64344010000 00000000
644
645````
646
647## Implementation
648
649circom will output this format.
650
651## Copyright
652
653Copyright and related rights waived via [CC0](https://creativecommons.org/publicdomain/zero/1.0/).
654