Contract con_verifier_opt_pairing


Contract Code

1 # con_verifier_opt_pairing
2
3 pseudo_binary_encoding = [0, 0, 0, 1, 0, 1, 0, -1, 0, 0, 1, -1, 0, 0, 1, 0,
4 0, 1, 1, 0, -1, 0, 0, 1, 0, -1, 0, 0, 0, 0, 1, 1,
5 1, 0, 0, -1, 0, 0, 1, 0, 0, 0, 0, 0, -1, 0, 0, 1,
6 1, 0, 0, -1, 0, 0, 0, 1, 1, 0, -1, 0, 0, 1, 0, 1, 1]
7 curve_order = 21888242871839275222246405745257275088548364400416034343698204186575808495617
8 p2 = 21888242871839275222246405745257275088696311157297823662689037894645226208583
9 u = 4965661367192848881
10 xiToPMinus1Over6 = [16469823323077808223889137241176536799009286646108169935659301613961712198316,
11 8376118865763821496583973867626364092589906065868298776909617916018768340080]
12 xiToPMinus1Over3 = [10307601595873709700152284273816112264069230130616436755625194854815875713954,
13 21575463638280843010398324269430826099269044274347216827212613867836435027261]
14 xiToPMinus1Over2 = [3505843767911556378687030309984248845540243509899259641013678093033130930403,
15 2821565182194536844548159561693502659359617185244120367078079554186484126554]
16 xiToPSquaredMinus1Over3 = 21888242871839275220042445260109153167277707414472061641714758635765020556616
17 xiTo2PSquaredMinus2Over3 = 2203960485148121921418603742825762020974279258880205651966
18 xiToPSquaredMinus1Over6 = 21888242871839275220042445260109153167277707414472061641714758635765020556617
19 xiTo2PMinus2Over3 = [19937756971775647987995932169929341994314640652964949448313374472400716661030,
20 2581911344467009335267311115468803099551665605076196740867805258568234346338]
21 twistB = [266929791119991161246907387137283842545076965332900288569378510910307636690,
22 19485874751759354771024239261021720505790618469301721065564631296452457478373]
23 curveB = 3
24
25
26 def FQ(n: int) -> int:
27 n = n % p2
28 if n < 0:
29 n += p2
30 return n
31
32
33 def fq_inv(a: int, n: int = p2) -> int:
34 if a == 0:
35 return 0
36 lm, hm = 1, 0
37 low, high = a % n, n
38 while low > 1:
39 r = high // low
40 nm, new = hm - lm * r, high - low * r
41 lm, low, hm, high = nm, new, lm, low
42 return lm % n
43
44
45 def fa(self: int, other: int) -> int:
46 return FQ(self + other)
47
48
49 def fm(self: int, other: int) -> int:
50 return FQ(self * other)
51
52
53 def fs(self: int, other: int) -> int:
54 return FQ(self - other)
55
56
57 def fq_eq(self: int, other: int) -> bool:
58 return self == other
59
60
61 def fq_neg(self: int) -> int:
62 self = -self
63 if self < 0:
64 self += p2
65 return self
66
67
68 def bits_of(k):
69 return [int(c) for c in "{0:b}".format(k)]
70
71
72 def FQ2(coeffs: list) -> list:
73 assert len(coeffs) == 2, f'FQ2 must have 2 coefficients but had {len(coeffs)}'
74 return coeffs
75
76
77 def FQ6(coeffs: list) -> list:
78 assert len(coeffs) == 3 and len(coeffs[0]) == 2, 'FQ6 must have 3 FQ2s'
79 return coeffs
80
81
82 def FQ12(coeffs: list) -> list:
83 assert len(coeffs) == 2 and len(coeffs[0]) == 3, 'FQ12 must have 2 FQ6s'
84 return coeffs
85
86
87 def fq2_one(n: int = 0) -> list:
88 return [0, 1]
89
90
91 def fq2_zero(n: int = 0) -> list:
92 return [0, 0]
93
94
95 def fq2_is_one(self: list) -> bool:
96 return self[0] == 0 and self[1] == 1
97
98
99 def fq2_is_zero(self: list) -> bool:
100 return self[0] == 0 and self[1] == 0
101
102
103 def fq2_conjugate(self: list) -> list:
104 return [fq_neg(self[0]), self[1]]
105
106
107 def fq2_neg(self: list) -> list:
108 return [fq_neg(self[0]), fq_neg(self[1])]
109
110
111 def f2a(self: list, other: list) -> list:
112 return [fa(self[0], other[0]), fa(self[1], other[1])]
113
114
115 def f2s(self: list, other: list) -> list:
116 return [fs(self[0], other[0]), fs(self[1], other[1])]
117
118
119 def f2m(self: list, other: list) -> list:
120 tx = fm(self[0], other[1])
121 t = fm(other[0], self[1])
122 tx = fa(tx, t)
123
124 ty = fm(self[1], other[1])
125 t = fm(self[0], other[0])
126 ty = fs(ty, t)
127 return [tx, ty]
128
129
130 def f2m_scalar(self: list, other: int) -> list:
131 x = fm(self[0], other)
132 y = fm(self[1], other)
133 return [x, y]
134
135
136 def f2m_xi(self: list) -> list:
137 tx = fa(self[0], self[0])
138 tx = fa(tx, tx)
139 tx = fa(tx, tx)
140 tx = fa(tx, self[0])
141 tx = fa(tx, self[1])
142
143 ty = fa(self[1], self[1])
144 ty = fa(ty, ty)
145 ty = fa(ty, ty)
146 ty = fa(ty, self[1])
147 ty = fs(ty, self[0])
148 return [tx, ty]
149
150
151 def fq2_eq(self: list, other: list) -> bool:
152 return self[0] == other[0] and self[1] == other[1]
153
154
155 def fq2_square(self: list) -> list:
156 tx = fs(self[1], self[0])
157 ty = fa(self[0], self[1])
158 ty = fm(tx, ty)
159
160 tx = fm(self[0], self[1])
161 tx = fa(tx, tx)
162 return [tx, ty]
163
164
165 def fq2_invert(self: list) -> list:
166 t1 = fm(self[0], self[0])
167 t2 = fm(self[1], self[1])
168 t1 = fa(t1, t2)
169 inv = fq_inv(t1)
170 t1 = fq_neg(self[0])
171 x = fm(t1, inv)
172 y = fm(self[1], inv)
173 return [x, y]
174
175
176 def fq6_one(n: int = 0) -> list:
177 return [fq2_zero(), fq2_zero(), fq2_one()]
178
179
180 def fq6_zero(n: int = 0) -> list:
181 return [fq2_zero(), fq2_zero(), fq2_zero()]
182
183
184 def fq6_is_zero(self: list) -> bool:
185 return fq2_is_zero(self[0]) and fq2_is_zero(self[1]) and fq2_is_zero(self[2])
186
187
188 def fq6_is_one(self: list) -> bool:
189 return fq2_is_zero(self[0]) and fq2_is_zero(self[1]) and fq2_is_one(self[2])
190
191
192 def fq6_neg(self: list) -> list:
193 return [fq2_neg(self[0]), fq2_neg(self[1]), fq2_neg(self[2])]
194
195
196 def fq6_frobenius(self: list) -> list:
197 x = fq2_conjugate(self[0])
198 y = fq2_conjugate(self[1])
199 z = fq2_conjugate(self[2])
200 x = f2m(x, xiTo2PMinus2Over3)
201 y = f2m(y, xiToPMinus1Over3)
202 return [x, y, z]
203
204
205 def fq6_frobenius_p2(self: list) -> list:
206 x = f2m_scalar(self[0], xiTo2PSquaredMinus2Over3)
207 y = f2m_scalar(self[1], xiToPSquaredMinus1Over3)
208 return [x, y, self[2]]
209
210
211 def f6a(self: list, other: list) -> list:
212 return [f2a(self[0], other[0]), f2a(self[1], other[1]), f2a(self[2], other[2])]
213
214
215 def f6s(self: list, other: list) -> list:
216 return [f2s(self[0], other[0]), f2s(self[1], other[1]), f2s(self[2], other[2])]
217
218
219 def f6m(self: list, other: list) -> list:
220 v0 = f2m(self[2], other[2])
221 v1 = f2m(self[1], other[1])
222 v2 = f2m(self[0], other[0])
223 t0 = f2a(self[0], self[1])
224 t1 = f2a(other[0], other[1])
225 tz = f2m(t0, t1)
226 tz = f2s(tz, v1)
227 tz = f2s(tz, v2)
228 tz = f2m_xi(tz)
229 tz = f2a(tz, v0)
230
231 t0 = f2a(self[1], self[2])
232 t1 = f2a(other[1], other[2])
233 ty = f2m(t0, t1)
234 t0 = f2m_xi(v2)
235 ty = f2s(ty, v0)
236 ty = f2s(ty, v1)
237 ty = f2a(ty, t0)
238
239 t0 = f2a(self[0], self[2])
240 t1 = f2a(other[0], other[2])
241 tx = f2m(t0, t1)
242 tx = f2s(tx, v0)
243 tx = f2a(tx, v1)
244 tx = f2s(tx, v2)
245 return [tx, ty, tz]
246
247
248 def f6m_scalar(self: list, other: list) -> list:
249 return [f2m(self[0], other), f2m(self[1], other), f2m(self[2], other)]
250
251
252 def f6m_gfp(self: list, other: int) -> list:
253 return [f2m_scalar(self[0], other), f2m_scalar(self[1], other), f2m_scalar(self[2], other)]
254
255
256 def f6m_tau(self: list) -> list:
257 tz = f2m_xi(self[0])
258 ty = self[1]
259 return [ty, self[2], tz]
260
261
262 def fq6_square(self: list) -> list:
263 v0 = fq2_square(self[2])
264 v1 = fq2_square(self[1])
265 v2 = fq2_square(self[0])
266
267 c0 = f2a(self[0], self[1])
268 c0 = fq2_square(c0)
269 c0 = f2s(c0, v1)
270 c0 = f2s(c0, v2)
271 c0 = f2m_xi(c0)
272 c0 = f2a(c0, v0)
273
274 c1 = f2a(self[1], self[2])
275 c1 = fq2_square(c1)
276 c1 = f2s(c1, v0)
277 c1 = f2s(c1, v1)
278 xiV2 = f2m_xi(v2)
279 c1 = f2a(c1, xiV2)
280
281 c2 = f2a(self[0], self[2])
282 c2 = fq2_square(c2)
283 c2 = f2s(c2, v0)
284 c2 = f2a(c2, v1)
285 c2 = f2s(c2, v2)
286 return [c2, c1, c0]
287
288
289 def fq6_invert(self: list) -> list:
290 XX = fq2_square(self[0])
291 YY = fq2_square(self[1])
292 ZZ = fq2_square(self[2])
293
294 XY = f2m(self[0], self[1])
295 XZ = f2m(self[0], self[2])
296 YZ = f2m(self[1], self[2])
297
298 A = f2s(ZZ, f2m_xi(XY))
299 B = f2s(f2m_xi(XX), YZ)
300 C = f2s(YY, XZ)
301
302 F = f2m_xi(f2m(C, self[1]))
303 F = f2a(F, f2m(A, self[2]))
304 F = f2a(F, f2m_xi(f2m(B, self[0])))
305
306 F = fq2_invert(F)
307 return [f2m(C, F), f2m(B, F), f2m(A, F)]
308
309
310 def fq12_one(n: int = 0) -> list:
311 return [fq6_zero(), fq6_one()]
312
313
314 def fq12_is_one(self: list) -> bool:
315 return fq6_is_zero(self[0]) and fq6_is_one(self[1])
316
317
318 def fq12_conjugate(self: list) -> list:
319 return [fq6_neg(self[0]), self[1]]
320
321
322 def fq12_frobenius(self: list) -> list:
323 x = fq6_frobenius(self[0])
324 x = f6m_scalar(x, xiToPMinus1Over6)
325 return [x, fq6_frobenius(self[1])]
326
327
328 def fq12_frobenius_p2(self: list) -> list:
329 x = fq6_frobenius_p2(self[0])
330 x = f6m_gfp(x, xiToPSquaredMinus1Over6)
331 return [x, fq6_frobenius_p2(self[1])]
332
333
334 def f12a(self: list, other: list) -> list:
335 return [f6a(self[0], other[0]), f6a(self[1], other[1])]
336
337
338 def f12s(self: list, other: list) -> list:
339 return [f6s(self[0], other[0]), f6s(self[1], other[1])]
340
341
342 def f12m(self: list, other: list) -> list:
343 tx = f6m(self[0], other[1])
344 t = f6m(self[1], other[0])
345 tx = f6a(tx, t)
346 ty = f6m(self[1], other[1])
347 t = f6m(self[0], other[0])
348 t = f6m_tau(t)
349 return [tx, f6a(ty, t)]
350
351
352 def f12m_scalar(self: list, other: list) -> list:
353 return [f6m(self[0], other), f6m(self[1], other)]
354
355
356 def fq12_exp(self: list, other: int) -> list:
357 sum = fq12_one()
358 for i in range(other.bit_length() - 1, -1, -1):
359 t = fq12_square(sum)
360 if other >> i & 1 != 0:
361 sum = f12m(t, self)
362 else:
363 sum = t
364 return sum
365
366
367 def fq12_square(self: list) -> list:
368 v0 = f6m(self[0], self[1])
369 t = f6m_tau(self[0])
370 t = f6a(self[1], t)
371 ty = f6a(self[0], self[1])
372 ty = f6m(ty, t)
373 ty = f6s(ty, v0)
374 t = f6m_tau(v0)
375 ty = f6s(ty, t)
376 return [f6a(v0, v0), ty]
377
378
379 def fq12_invert(self: list) -> list:
380 t1 = fq6_square(self[0])
381 t2 = fq6_square(self[1])
382 t1 = f6m_tau(t1)
383 t1 = f6s(t2, t1)
384 t2 = fq6_invert(t1)
385 return f12m_scalar([fq6_neg(self[0]), self[1]], t2)
386
387
388 def line_function_add(r: list, p: list, q: list, r2: list) -> tuple:
389 B = f2m(p[0], r[3])
390 D = f2a(p[1], r[2])
391 D = fq2_square(D)
392 D = f2s(D, r2)
393 D = f2s(D, r[3])
394 D = f2m(D, r[3])
395
396 H = f2s(B, r[0])
397 I = fq2_square(H)
398
399 E = f2a(I, I)
400 E = f2a(E, E)
401
402 J = f2m(H, E)
403
404 L1 = f2s(D, r[1])
405 L1 = f2s(L1, r[1])
406
407 V = f2m(r[0], E)
408
409 rOutX = fq2_square(L1)
410 rOutX = f2s(rOutX, J)
411 rOutX = f2s(rOutX, f2a(V, V))
412
413 rOutZ = f2a(r[2], H)
414 rOutZ = fq2_square(rOutZ)
415 rOutZ = f2s(rOutZ, r[3])
416 rOutZ = f2s(rOutZ, I)
417
418 t = f2s(V, rOutX)
419 t = f2m(t, L1)
420 t2 = f2m(r[1], J)
421 t2 = f2a(t2, t2)
422 rOutY = f2s(t, t2)
423 rOutT = fq2_square(rOutZ)
424
425 t = f2a(p[1], rOutZ)
426 t = fq2_square(t)
427 t = f2s(t, r2)
428 t = f2s(t, rOutT)
429
430 t2 = f2m(L1, p[0])
431 t2 = f2a(t2, t2)
432 a = f2s(t2, t)
433
434 c = f2m_scalar(rOutZ, q[1])
435 c = f2a(c, c)
436
437 b = fq2_neg(L1)
438 b = f2m_scalar(b, q[0])
439 b = f2a(b, b)
440
441 return a, b, c, [rOutX, rOutY, rOutZ, rOutT]
442
443
444 def line_function_double(r: list, q: list) -> tuple:
445 A = fq2_square(r[0])
446 B = fq2_square(r[1])
447 C = fq2_square(B)
448
449 D = f2a(r[0], B)
450 D = fq2_square(D)
451 D = f2s(D, A)
452 D = f2s(D, C)
453 D = f2a(D, D)
454
455 E = f2a(f2a(A, A), A)
456 F = fq2_square(E)
457
458 C8 = f2a(C, C)
459 C8 = f2a(C8, C8)
460 C8 = f2a(C8, C8)
461
462 rX = f2s(F, f2a(D, D))
463 rY = f2m(E, f2s(D, rX))
464 rY = f2s(rY, C8)
465
466 rZ = f2a(r[1], r[2])
467 rZ = fq2_square(rZ)
468 rZ = f2s(rZ, B)
469 rZ = f2s(rZ, r[3])
470
471 a = f2a(r[0], E)
472 a = fq2_square(a)
473 B4 = f2a(B, B)
474 B4 = f2a(B4, B4)
475 a = f2s(a, f2a(A, f2a(F, B4)))
476
477 t = f2m(E, r[3])
478 t = f2a(t, t)
479 b = fq2_neg(t)
480 b = f2m_scalar(b, q[0])
481
482 c = f2m(rZ, r[3])
483 c = f2a(c, c)
484 c = f2m_scalar(c, q[1])
485
486 rT = fq2_square(rZ)
487 return a, b, c, [rX, rY, rZ, rT]
488
489
490 def line_function_mul(ret: list, a: list, b: list, c: list) -> list:
491 a2 = [fq2_zero(), a, b]
492 a2 = f6m(a2, ret[0])
493 t3 = f6m_scalar(ret[1], c)
494
495 t = f2a(b, c)
496 t2 = [fq2_zero(), a, t]
497 rX = f6a(ret[0], ret[1])
498 rY = t3
499
500 rX = f6m(rX, t2)
501 rX = f6s(rX, a2)
502 rX = f6s(rX, rY)
503 a2 = f6m_tau(a2)
504 rY = f6a(rY, a2)
505 return [rX, rY]
506
507
508 def miller(q: list, p: list) -> list:
509 ret = fq12_one()
510
511 aAffine = twist_make_affine(q)
512 bAffine = curve_make_affine(p)
513
514 minusA = twist_neg(aAffine)
515
516 r = aAffine
517 r2 = fq2_square(aAffine[1])
518
519 for i in range(len(pseudo_binary_encoding) - 1, 0, -1):
520 a, b, c, r = line_function_double(r, bAffine)
521 if i != len(pseudo_binary_encoding) - 1:
522 ret = fq12_square(ret)
523
524 ret = line_function_mul(ret, a, b, c)
525
526 s = pseudo_binary_encoding[i - 1]
527 if s == 1:
528 a, b, c, r = line_function_add(r, aAffine, bAffine, r2)
529 elif s == -1:
530 a, b, c, r = line_function_add(r, minusA, bAffine, r2)
531 else:
532 continue
533
534 ret = line_function_mul(ret, a, b, c)
535
536 q1 = [
537 f2m(fq2_conjugate(aAffine[0]), xiToPMinus1Over3),
538 f2m(fq2_conjugate(aAffine[1]), xiToPMinus1Over2),
539 fq2_one(),
540 fq2_one(),
541 ]
542
543 minusQ2 = [
544 f2m_scalar(aAffine[0], xiToPSquaredMinus1Over3),
545 aAffine[1],
546 fq2_one(),
547 fq2_one(),
548 ]
549
550 r2 = fq2_square(q1[1])
551 a, b, c, r = line_function_add(r, q1, bAffine, r2)
552
553 ret = line_function_mul(ret, a, b, c)
554
555 r2 = fq2_square(minusQ2[1])
556 a, b, c, r = line_function_add(r, minusQ2, bAffine, r2)
557 ret = line_function_mul(ret, a, b, c)
558 return ret
559
560
561 def final_exponentiation(p: list) -> list:
562 t1 = fq12_conjugate(p)
563 inv = fq12_invert(p)
564
565 t1 = f12m(t1, inv)
566
567 t2 = fq12_frobenius_p2(t1)
568 t1 = f12m(t1, t2)
569
570 fp = fq12_frobenius(t1)
571 fp2 = fq12_frobenius_p2(t1)
572 fp3 = fq12_frobenius(fp2)
573
574 fu = fq12_exp(t1, u)
575 fu2 = fq12_exp(fu, u)
576 fu3 = fq12_exp(fu2, u)
577
578 y3 = fq12_frobenius(fu)
579 fu2p = fq12_frobenius(fu2)
580 fu3p = fq12_frobenius(fu3)
581 y2 = fq12_frobenius_p2(fu2)
582
583 y0 = f12m(fp, fp2)
584 y0 = f12m(y0, fp3)
585
586 y1 = fq12_conjugate(t1)
587 y5 = fq12_conjugate(fu2)
588 y3 = fq12_conjugate(y3)
589 y4 = f12m(fu, fu2p)
590 y4 = fq12_conjugate(y4)
591
592 y6 = f12m(fu3, fu3p)
593 y6 = fq12_conjugate(y6)
594
595 t0 = fq12_square(y6)
596 t0 = f12m(t0, y4)
597 t0 = f12m(t0, y5)
598
599 t1 = f12m(y3, y5)
600 t1 = f12m(t1, t0)
601 t0 = f12m(t0, y2)
602 t1 = fq12_square(t1)
603 t1 = f12m(t1, t0)
604 t1 = fq12_square(t1)
605 t0 = f12m(t1, y1)
606 t1 = f12m(t1, y0)
607 t0 = fq12_square(t0)
608 t0 = f12m(t0, t1)
609 return t0
610
611
612 def twist_make_affine(c: list) -> list:
613 if fq2_is_one(c[2]):
614 return c
615 elif fq2_is_zero(c[2]):
616 return [
617 fq2_zero(),
618 fq2_one(),
619 fq2_zero(),
620 fq2_zero()
621 ]
622 else:
623 zInv = fq2_invert(c[2])
624 zInv2 = fq2_square(zInv)
625 zInv3 = f2m(zInv2, zInv)
626 return [
627 f2m(c[0], zInv2),
628 f2m(c[1], zInv3),
629 fq2_one(),
630 fq2_one(),
631 ]
632
633
634 def twist_add(a: list, b: list) -> list:
635 if twist_is_infinity(a):
636 return b
637 if twist_is_infinity(b):
638 return a
639
640 z12 = fq2_square(a[2])
641 z22 = fq2_square(b[2])
642
643 u1 = f2m(a[0], z22)
644 u2 = f2m(b[0], z12)
645
646 t = f2m(b[2], z22)
647 s1 = f2m(a[1], t)
648
649 t = f2m(a[2], z12)
650 s2 = f2m(b[1], t)
651
652 h = f2s(u2, u1)
653 xEqual = fq2_eq(h, fq2_zero())
654
655 t = f2a(h, h)
656 i = fq2_square(t)
657 j = f2m(h, i)
658 t = f2s(s2, s1)
659
660 yEqual = fq2_eq(t, fq2_zero())
661
662 if (xEqual and yEqual):
663 return twist_double(a)
664
665 r = f2a(t, t)
666 v = f2m(u1, i)
667
668 t4 = fq2_square(r)
669 t = f2a(v, v)
670 t6 = f2s(t4, j)
671
672 cX = f2s(t6, t)
673
674 t = f2s(v, cX)
675 t4 = f2m(s1, j)
676 t6 = f2a(t4, t4)
677 t4 = f2m(r, t)
678 cY = f2s(t4, t6)
679
680 t = f2a(a[2], b[2])
681 t4 = fq2_square(t)
682 t = f2s(t4, z12)
683 t4 = f2s(t, z22)
684 cZ = f2m(t4, h)
685 return [cX, cY, cZ]
686
687
688 def twist_double(a: list) -> list:
689 A = f2m(a[0], a[0])
690 B = f2m(a[1], a[1])
691 C = f2m(B, B)
692
693 t = f2a(a[0], B)
694 t2 = f2m(t, t)
695 t = f2s(t2, A)
696 t2 = f2s(t, C)
697
698 d = f2a(t2, t2)
699 t = f2a(A, A)
700 e = f2a(t, A)
701 f = f2m(e, e)
702
703 t = f2a(d, d)
704 cX = f2s(f, t)
705
706 cZ = f2m(a[1], a[2])
707 cZ = f2a(cZ, cZ)
708
709 t = f2a(C, C)
710 t2 = f2a(t, t)
711 t = f2a(t2, t2)
712 cY = f2s(d, cX)
713 t2 = f2m(e, cY)
714 cY = f2s(t2, t)
715 return [cX, cY, cZ]
716
717
718 def twist_mul(pt: list, k: int) -> list:
719 if int(k) == 0:
720 return [fq2_one(), fq2_one(), fq2_zero()]
721
722 R = [[fq2_zero(), fq2_zero(), fq2_zero()],
723 pt]
724
725 for kb in bits_of(k):
726 R[kb ^ 1] = twist_add(R[kb], R[kb ^ 1])
727 R[kb] = twist_double(R[kb])
728 return R[0]
729
730
731 def twist_neg(c: list) -> list:
732 return [
733 c[0],
734 fq2_neg(c[1]),
735 c[2],
736 fq2_zero(),
737 ]
738
739
740 def twist_is_infinity(c: list) -> bool:
741 return fq2_is_zero(c[2])
742
743
744 def twist_is_on_curve(c: list) -> bool:
745 c = twist_make_affine(c)
746 if twist_is_infinity(c):
747 return True
748
749 y2 = fq2_square(c[1])
750 x3 = fq2_square(c[0])
751 x3 = f2m(x3, c[0])
752
753 y2 = f2s(y2, x3)
754 y2 = f2s(y2, twistB)
755 return fq2_is_zero(y2)
756
757
758 def curve_add(a: list, b: list) -> list:
759 if curve_is_infinity(a):
760 return b
761 if curve_is_infinity(b):
762 return a
763
764 z12 = fm(a[2], a[2])
765 z22 = fm(b[2], b[2])
766
767 u1 = fm(a[0], z22)
768 u2 = fm(b[0], z12)
769
770 t = fm(b[2], z22)
771 s1 = fm(a[1], t)
772
773 t = fm(a[2], z12)
774 s2 = fm(b[1], t)
775
776 h = fs(u2, u1)
777 xEqual = fq_eq(h, 0)
778
779 t = fa(h, h)
780
781 i = fm(t, t)
782
783 j = fm(h, i)
784
785 t = fs(s2, s1)
786
787 yEqual = fq_eq(t, 0)
788
789 if (xEqual and yEqual):
790 return curve_double(a)
791
792 r = fa(t, t)
793
794 v = fm(u1, i)
795
796 t4 = fm(r, r)
797 t = fa(v, v)
798 t6 = fs(t4, j)
799
800 cX = fs(t6, t)
801
802 t = fs(v, cX)
803 t4 = fm(s1, j)
804 t6 = fa(t4, t4)
805 t4 = fm(r, t)
806 cY = fs(t4, t6)
807
808 t = fa(a[2], b[2])
809 t4 = fm(t, t)
810 t = fs(t4, z12)
811 t4 = fs(t, z22)
812 cZ = fm(t4, h)
813 return [cX, cY, cZ]
814
815
816 def curve_double(a: list) -> list:
817 A = fm(a[0], a[0])
818 B = fm(a[1], a[1])
819 C = fm(B, B)
820
821 t = fa(a[0], B)
822 t2 = fm(t, t)
823 t = fs(t2, A)
824 t2 = fs(t, C)
825
826 d = fa(t2, t2)
827 t = fa(A, A)
828 e = fa(t, A)
829 f = fm(e, e)
830
831 t = fa(d, d)
832 cX = fs(f, t)
833
834 cZ = fm(a[1], a[2])
835 cZ = fa(cZ, cZ)
836
837 t = fa(C, C)
838 t2 = fa(t, t)
839 t = fa(t2, t2)
840 cY = fs(d, cX)
841 t2 = fm(e, cY)
842 cY = fs(t2, t)
843 return [cX, cY, cZ]
844
845
846 def curve_mul(pt: list, k: int) -> list:
847 if int(k) == 0:
848 return [1, 1, 0]
849
850 R = [[0, 0, 0],
851 pt]
852
853 for kb in bits_of(k):
854 R[kb ^ 1] = curve_add(R[kb], R[kb ^ 1])
855 R[kb] = curve_double(R[kb])
856 return R[0]
857
858
859 def curve_is_infinity(c: list) -> bool:
860 return c[2] == 0
861
862
863 def curve_neg(c: list) -> list:
864 return [
865 c[0],
866 fq_neg(c[1]),
867 c[2],
868 0,
869 ]
870
871
872 def curve_make_affine(c: list) -> list:
873 if fq_eq(c[2], 1):
874 return c
875 elif fq_eq(c[2], 0):
876 return [
877 0,
878 1,
879 0,
880 0
881 ]
882 else:
883 zInv = fq_inv(c[2])
884 t = fm(c[1], zInv)
885 zInv2 = fm(zInv, zInv)
886 cX = fm(c[0], zInv2)
887 cY = fm(t, zInv2)
888 return [
889 cX,
890 cY,
891 1,
892 1,
893 ]
894
895
896 def curve_is_on_curve(c: list) -> bool:
897 c = curve_make_affine(c)
898 if curve_is_infinity(c):
899 return True
900
901 y2 = fm(c[1], c[1])
902 x3 = fm(c[0], c[0])
903 x3 = fm(x3, c[0])
904 x3 = fa(x3, curveB)
905 return fq_eq(y2, x3)
906
907
908 def pairing(Q: list, P: list) -> list:
909 assert curve_is_on_curve(P), f'P is not on the curve.'
910 assert twist_is_on_curve(Q), f'Q is not on the curve.'
911 if curve_is_infinity(P) or twist_is_infinity(Q):
912 return fq12_one()
913 r = miller(Q, P)
914 return r
915
916 @export
917 def compute_vk(IC: list, inputs: list) -> list:
918 vk_x = IC[0]
919 for i in range(len(inputs)):
920 assert inputs[i] < curve_order, "verifier-gte-snark-scalar-field"
921 vk_x = curve_add(vk_x, curve_mul(IC[i + 1], inputs[i]))
922 return vk_x
923
924 @export
925 def final_result(p: list, q: list) -> int:
926 p[0] = curve_neg(p[0])
927
928 x = fq12_one()
929 for i in range(4):
930 if twist_is_infinity(q[i]) or curve_is_infinity(p[i]):
931 continue
932 x = f12m(x, pairing(q[i], p[i]))
933
934 x = final_exponentiation(x)
935 if not fq12_is_one(x):
936 return 1
937 return 0
938

Byte Code

e3000000000000000000000000410000004000000073ca050000640064006400640164006401640064ba64006400640164bb6400640064016400640064016401640064bc640064006401640064bd64006400640064006401640164016400640064be6400640064016400640064006400640064bf64006400640164016400640064c064006400640064016401640064c164006400640164006401640167415a0064025a0164035a0264045a036405640667025a046407640867025a056409640a67025a06640b5a07640c5a08640d5a09640e640f67025a0a6410641167025a0b64125a0c650d650d64139c026414641584045a0e65026601650d650d650d64169c036417641884055a0f650d650d650d64199c03641a641b84045a10650d650d650d64199c03641c641d84045a11650d650d650d64199c03641e641f84045a12650d650d651364199c036420642184045a14650d650d64229c026423642484045a156425642684005a166517651764279c026428642984045a186517651764279c02642a642b84045a196517651764279c02642c642d84045a1a64c2650d651764139c02642e642f84055a1b64c3650d651764139c026430643184055a1c6517651364229c026432643384045a1d6517651364229c026434643584045a1e6517651764229c026436643784045a1f6517651764229c026438643984045a2065176517651764199c03643a643b84045a2165176517651764199c03643c643d84045a2265176517651764199c03643e643f84045a236517650d651764199c036440644184045a246517651764229c026442644384045a2565176517651364199c036444644584045a266517651764229c026446644784045a276517651764229c026448644984045a2864c4650d651764139c02644a644b84055a2964c5650d651764139c02644c644d84055a2a6517651364229c02644e644f84045a2b6517651364229c026450645184045a2c6517651764229c026452645384045a2d6517651764229c026454645584045a2e6517651764229c026456645784045a2f65176517651764199c036458645984045a3065176517651764199c03645a645b84045a3165176517651764199c03645c645d84045a3265176517651764199c03645e645f84045a336517650d651764199c036460646184045a346517651764229c026462646384045a356517651764229c026464646584045a366517651764229c026466646784045a3764c6650d651764139c026468646984055a386517651364229c02646a646b84045a396517651764229c02646c646d84045a3a6517651764229c02646e646f84045a3b6517651764229c026470647184045a3c65176517651764199c036472647384045a3d65176517651764199c036474647584045a3e65176517651764199c036476647784045a3f65176517651764199c036478647984045a406517650d651764199c03647a647b84045a416517651764229c02647c647d84045a426517651764229c02647e647f84045a436517651765176517654464809c056481648284045a4565176517654464839c036484648584045a466517651765176517651764869c056487648884045a4765176517651764899c03648a648b84045a4865176517648c9c02648d648e84045a4965176517648f9c026490649184045a4a65176517651764929c036493649484045a4b6517651764959c026496649784045a4c6517650d651764989c036499649a84045a4d65176517648f9c02649b649c84045a4e65176513648f9c02649d649e84045a4f65176513648f9c02649f64a084045a5065176517651764929c0364a164a284045a516517651764959c0264a364a484045a526517650d651764989c0364a564a684045a5365176513648f9c0264a764a884045a5465176517648f9c0264a964aa84045a5565176517648f9c0264ab64ac84045a5665176513648f9c0264ad64ae84045a5765176517651764af9c0364b064b184045a58655964b2830165176517651764b39c0364b464b5840483015a5a655964b2830165176517650d64b69c0364b764b8840483015a5b64b9530029c7e900000000e9010000006c11000000010000604f560f1f14092e371e12f419285db002065a2d02851b05344c38392764306c11000000477df9305b300461d328390e5a24b540975db002065a2d02851b05344c38392764306c05000000f109d214d14a4c2704006c11000000ac62e6017e41e7525c7ed85de31dc93c740e172a4878e713636afc5c3e6d794b69246c11000000706493396b5759306d17e4250a020f295c60164ddb75fe4c8b7efb34190a8e5b84126c11000000a24b1f4871542e33e15c936f4207155732140f345d2f6426ba04c4757a18a872c9166c110000003d55de2e5c551c4fc930665830446146b7436233d573615fc0743e22de13cc23b32f6c11000000e330474c8c7d9b16283d4b7463723e40212bde72b11fad2570209320102b5e1ec0076c110000005a1340631905a0628d192b396a3b7055db39f345db623476c54dbb5e265282793c066c11000000487df9409513ea25de63cd72ee278347c2309959821fcf6ee61505344c38392764306c0d000000fe7fff6fc51c1a3bf5446b1b6b7c3179d42c1729833a5e139e056c11000000497df9409513ea25de63cd72ee278347c2309959821fcf6ee61505344c38392764306c110000002601571a471cda093c76d87b863ae94236123916ec400554f3695d31ff796d2f142c6c1100000062273d24567d502428479d52ef7db219d3043d30685d051e0f1800553b19af27b5056c11000000d215860b1a7415252e05a3253921d027a774fb31bb377d65d24cda1fbc0ed80997006c11000000e5384249701b3f13337a7d3b5679625ab543d5406f64c4701b685515ae33a04e142be9030000002902da016eda0672657475726e630100000000000000010000000200000043000000731c0000007c00740016007d007c0064016b0072187c00740037007d007c00530029024e72010000002901da02703229017204000000a9007207000000da00da045f5f4651300000007308000000000108010801080172090000002903da016172040000007205000000630200000000000000090000000400000043000000736e0000007c0064016b02720c6401530064035c027d027d037c007c0116007c0102007d047d0578427c0464026b0472647c057c041a007d067c037c027c06140018007c057c047c061400180002007d077d087c077c087c027c0466045c047d027d047d037d05712457007c027c011600530029044e7201000000720200000029027202000000720100000072070000002909720a0000007204000000da026c6dda02686dda036c6f77da0468696768da0172da026e6dda036e6577720700000072070000007208000000da085f5f66715f696e7637000000731200000000010801040108010e010a0108011a01180172120000002903da0473656c66da056f746865727205000000630200000000000000020000000300000043000000730c00000074007c007c0117008301530029014e29017209000000290272130000007214000000720700000072070000007208000000da045f5f666143000000730200000000017215000000630200000000000000020000000300000043000000730c00000074007c007c0114008301530029014e29017209000000290272130000007214000000720700000072070000007208000000da045f5f666d47000000730200000000017216000000630200000000000000020000000300000043000000730c00000074007c007c0118008301530029014e29017209000000290272130000007214000000720700000072070000007208000000da045f5f66734b00000073020000000001721700000063020000000000000002000000020000004300000073080000007c007c016b02530029014e7207000000290272130000007214000000720700000072070000007208000000da075f5f66715f65714f000000730200000000017218000000290272130000007205000000630100000000000000010000000200000043000000731a0000007c000b007d007c0064016b0072167c00740037007d007c00530029024e72010000002901720600000029017213000000720700000072070000007208000000da085f5f66715f6e656753000000730800000000010601080108017219000000630100000000000000010000000300000043000000731400000064016402840064036a007c00830144008301530029044e630100000000000000020000000400000053000000731400000067007c005d0c7d0174007c01830191027104530072070000002901da03696e742902da022e30da0163720700000072070000007208000000fa0a3c6c697374636f6d703e5b000000730200000006007a1d5f5f626974735f6f662e3c6c6f63616c733e2e3c6c697374636f6d703e7a057b303a627d2901da06666f726d61742901da016b720700000072070000007208000000da095f5f626974735f6f665a0000007302000000000172200000002902da06636f656666737205000000630100000000000000010000000400000043000000732200000074007c00830164016b02731e7401640274007c0083019b009d02830182017c00530029034ee9020000007a25465132206d7573742068617665203220636f656666696369656e74732062757420686164202902da036c656eda0e417373657274696f6e4572726f7229017221000000720700000072070000007208000000da055f5f4651325e00000073060000000001060118017225000000630100000000000000010000000300000043000000732800000074007c00830164016b02721c74007c0064021900830164036b02732474016404830182017c00530029054e7203000000720100000072220000007a14465136206d75737420686176652033204651327329027223000000722400000029017221000000720700000072070000007208000000da055f5f465136640000007304000000000124017226000000630100000000000000010000000300000043000000732800000074007c00830164016b02721c74007c0064021900830164036b02732474016404830182017c00530029054e7222000000720100000072030000007a1546513132206d75737420686176652032204651367329027223000000722400000029017221000000720700000072070000007208000000da065f5f465131326900000073040000000001240172270000006301000000000000000100000002000000430000007308000000640164026702530029034e72010000007202000000720700000029017204000000720700000072070000007208000000da095f5f6671325f6f6e656e0000007302000000000172280000006301000000000000000100000002000000430000007308000000640164016702530029024e7201000000720700000029017204000000720700000072070000007208000000da0a5f5f6671325f7a65726f7200000073020000000001722900000063010000000000000001000000020000004300000073180000007c006401190064016b026f167c006402190064026b02530029034e72010000007202000000720700000029017213000000720700000072070000007208000000da0c5f5f6671325f69735f6f6e657600000073020000000001722a00000063010000000000000001000000020000004300000073180000007c006401190064016b026f167c006402190064016b02530029034e72010000007202000000720700000029017213000000720700000072070000007208000000da0d5f5f6671325f69735f7a65726f7a00000073020000000001722b000000630100000000000000010000000300000043000000731400000074007c006401190083017c00640219006702530029034e720100000072020000002901721900000029017213000000720700000072070000007208000000da0f5f5f6671325f636f6e6a75676174657e00000073020000000001722c000000630100000000000000010000000400000043000000731800000074007c0064011900830174007c006402190083016702530029034e720100000072020000002901721900000029017213000000720700000072070000007208000000da095f5f6671325f6e65678200000073020000000001722d000000630200000000000000020000000500000043000000732400000074007c00640119007c0164011900830274007c00640219007c016402190083026702530029034e7201000000720200000029017215000000290272130000007214000000720700000072070000007208000000da055f5f6632618600000073020000000001722e000000630200000000000000020000000500000043000000732400000074007c00640119007c0164011900830274007c00640219007c016402190083026702530029034e7201000000720200000029017217000000290272130000007214000000720700000072070000007208000000da055f5f6632738a00000073020000000001722f000000630200000000000000050000000400000043000000736400000074007c00640119007c016402190083027d0274007c01640119007c006402190083027d0374017c027c0383027d0274007c00640219007c016402190083027d0474007c00640119007c016401190083027d0374027c047c0383027d047c027c046702530029034e720100000072020000002903721600000072150000007217000000290572130000007214000000da027478da0174da027479720700000072070000007208000000da055f5f66326d8e000000730e0000000001120112010a01120112010a017233000000630200000000000000040000000300000043000000732400000074007c00640119007c0183027d0274007c00640219007c0183027d037c027c036702530029034e7201000000720200000029017216000000290472130000007214000000da0178da0179720700000072070000007208000000da0c5f5f66326d5f7363616c617298000000730600000000010e010e017236000000630100000000000000030000000400000043000000738c00000074007c00640119007c006401190083027d0174007c017c0183027d0174007c017c0183027d0174007c017c006401190083027d0174007c017c006402190083027d0174007c00640219007c006402190083027d0274007c027c0283027d0274007c027c0283027d0274007c027c006402190083027d0274017c027c006401190083027d027c017c026702530029034e720100000072020000002902721500000072170000002903721300000072300000007232000000720700000072070000007208000000da085f5f66326d5f78699e0000007316000000000112010a010a010e010e0112010a010a010e010e01723700000063020000000000000002000000030000004300000073200000007c00640119007c01640119006b026f1e7c00640219007c01640219006b02530029034e720100000072020000007207000000290272130000007214000000720700000072070000007208000000da085f5f6671325f6571ac000000730200000000017238000000630100000000000000030000000400000043000000735200000074007c00640119007c006402190083027d0174017c00640219007c006401190083027d0274027c017c0283027d0274027c00640219007c006401190083027d0174017c017c0183027d017c017c026702530029034e7202000000720100000029037217000000721500000072160000002903721300000072300000007232000000720700000072070000007208000000da0c5f5f6671325f737175617265b0000000730c0000000001120112010a0112010a017239000000630100000000000000060000000400000043000000736200000074007c00640119007c006401190083027d0174007c00640219007c006402190083027d0274017c017c0283027d0174027c0183017d0374037c006401190083017d0174007c017c0383027d0474007c00640219007c0383027d057c047c056702530029034e720100000072020000002904721600000072150000007212000000721900000029067213000000da027431da027432da03696e7672340000007235000000720700000072070000007208000000da0c5f5f6671325f696e76657274b900000073100000000001120112010a0108010c010a010e01723d00000063010000000000000001000000030000004300000073100000007400830074008300740183006703530029014e29027229000000722800000029017204000000720700000072070000007208000000da095f5f6671365f6f6e65c400000073020000000001723e00000063010000000000000001000000030000004300000073100000007400830074008300740083006703530029014e2901722900000029017204000000720700000072070000007208000000da0a5f5f6671365f7a65726fc800000073020000000001723f000000630100000000000000010000000300000043000000732400000074007c006401190083016f2274007c006402190083016f2274007c00640319008301530029044e7201000000720200000072220000002901722b00000029017213000000720700000072070000007208000000da0d5f5f6671365f69735f7a65726fcc000000730400000000011a017240000000630100000000000000010000000300000043000000732400000074007c006401190083016f2274007c006402190083016f2274017c00640319008301530029044e7201000000720200000072220000002902722b000000722a00000029017213000000720700000072070000007208000000da0c5f5f6671365f69735f6f6e65d1000000730400000000011a017241000000630100000000000000010000000500000043000000732200000074007c0064011900830174007c0064021900830174007c006403190083016703530029044e7201000000720200000072220000002901722d00000029017213000000720700000072070000007208000000da095f5f6671365f6e6567d6000000730200000000017242000000630100000000000000040000000300000043000000734200000074007c006401190083017d0174007c006402190083017d0274007c006403190083017d0374017c01740283027d0174017c02740383027d027c017c027c036703530029044e7201000000720200000072220000002904722c0000007233000000da117869546f32504d696e7573324f76657233da107869546f504d696e7573314f766572332904721300000072340000007235000000da017a720700000072070000007208000000da0f5f5f6671365f66726f62656e697573da000000730c00000000010c010c010c010a010a017246000000630100000000000000030000000400000043000000732a00000074007c0064011900740183027d0174007c0064021900740283027d027c017c027c00640319006703530029044e72010000007202000000722200000029037236000000da187869546f3250537175617265644d696e7573324f76657233da177869546f50537175617265644d696e7573314f766572332903721300000072340000007235000000720700000072070000007208000000da125f5f6671365f66726f62656e6975735f7032e3000000730600000000010e010e017249000000630200000000000000020000000600000043000000733400000074007c00640119007c0164011900830274007c00640219007c0164021900830274007c00640319007c016403190083026703530029044e7201000000720200000072220000002901722e000000290272130000007214000000720700000072070000007208000000da055f5f663661e9000000730400000000012401724a000000630200000000000000020000000600000043000000733400000074007c00640119007c0164011900830274007c00640219007c0164021900830274007c00640319007c016403190083026703530029044e7201000000720200000072220000002901722f000000290272130000007214000000720700000072070000007208000000da055f5f663673ee000000730400000000012401724b0000006302000000000000000a0000000400000043000000733401000074007c00640119007c016401190083027d0274007c00640219007c016402190083027d0374007c00640319007c016403190083027d0474017c00640319007c006402190083027d0574017c01640319007c016402190083027d0674007c057c0683027d0774027c077c0383027d0774027c077c0483027d0774037c0783017d0774017c077c0283027d0774017c00640219007c006401190083027d0574017c01640219007c016401190083027d0674007c057c0683027d0874037c0483017d0574027c087c0283027d0874027c087c0383027d0874017c087c0583027d0874017c00640319007c006401190083027d0574017c01640319007c016401190083027d0674007c057c0683027d0974027c097c0283027d0974017c097c0383027d0974027c097c0483027d097c097c087c076703530029044e72220000007202000000720100000029047233000000722e000000722f0000007237000000290a72130000007214000000da027630da027631da027632da027430723a000000da02747a72320000007230000000720700000072070000007208000000da055f5f66366df300000073300000000001120112011201120112010a010a010a0108010a01120112010a0108010a010a010a01120112010a010a010a010a017251000000630200000000000000020000000500000043000000732800000074007c00640119007c01830274007c00640219007c01830274007c00640319007c0183026703530029044e72010000007202000000722200000029017233000000290272130000007214000000720700000072070000007208000000da0c5f5f66366d5f7363616c61720e010000730200000000017252000000630200000000000000020000000500000043000000732800000074007c00640119007c01830274007c00640219007c01830274007c00640319007c0183026703530029044e72010000007202000000722200000029017236000000290272130000007214000000720700000072070000007208000000da095f5f66366d5f676670130100007304000000000118017253000000630100000000000000030000000300000043000000732200000074007c006401190083017d017c00640219007d027c027c00640319007c016703530029044e720100000072020000007222000000290172370000002903721300000072500000007232000000720700000072070000007208000000da095f5f66366d5f74617518010000730600000000010c010801725400000063010000000000000008000000040000004300000073e600000074007c006401190083017d0174007c006402190083017d0274007c006403190083017d0374017c00640319007c006402190083027d0474007c0483017d0474027c047c0283027d0474027c047c0383027d0474037c0483017d0474017c047c0183027d0474017c00640219007c006401190083027d0574007c0583017d0574027c057c0183027d0574027c057c0283027d0574037c0383017d0674017c057c0683027d0574017c00640319007c006401190083027d0774007c0783017d0774027c077c0183027d0774017c077c0283027d0774027c077c0383027d077c077c057c046703530029044e72220000007202000000720100000029047239000000722e000000722f000000723700000029087213000000724c000000724d000000724e000000da026330da026331da0478695632da026332720700000072070000007208000000da0c5f5f6671365f7371756172651e010000732a00000000010c010c010c01120108010a010a0108010a01120108010a010a0108010a01120108010a010a010a0172590000006301000000000000000b000000070000004300000073e200000074007c006401190083017d0174007c006402190083017d0274007c006403190083017d0374017c00640119007c006402190083027d0474017c00640119007c006403190083027d0574017c00640219007c006403190083027d0674027c0374037c04830183027d07740274037c0183017c0683027d0874027c027c0583027d09740374017c097c0064021900830283017d0a74047c0a74017c077c0064031900830283027d0a74047c0a740374017c087c00640119008302830183027d0a74057c0a83017d0a74017c097c0a830274017c087c0a830274017c077c0a83026703530029044e720100000072020000007222000000290672390000007233000000722f0000007237000000722e000000723d000000290b7213000000da025858da025959da025a5ada025859da02585ada02595ada0141da0142da0143da0146720700000072070000007208000000da0c5f5f6671365f696e7665727436010000731c00000000010c010c010c011201120112010e010e010a0112011401180108017264000000630100000000000000010000000200000043000000730c00000074008300740183006702530029014e2902723f000000723e00000029017204000000720700000072070000007208000000da0a5f5f667131325f6f6e6547010000730200000000017265000000630100000000000000010000000300000043000000731800000074007c006401190083016f1674017c00640219008301530029034e7201000000720200000029027240000000724100000029017213000000720700000072070000007208000000da0d5f5f667131325f69735f6f6e654b010000730200000000017266000000630100000000000000010000000300000043000000731400000074007c006401190083017c00640219006702530029034e720100000072020000002901724200000029017213000000720700000072070000007208000000da105f5f667131325f636f6e6a75676174654f010000730200000000017267000000630100000000000000020000000400000043000000732600000074007c006401190083017d0174017c01740283027d017c0174007c006402190083016702530029034e72010000007202000000290372460000007252000000da107869546f504d696e7573314f76657236290272130000007234000000720700000072070000007208000000da105f5f667131325f66726f62656e69757353010000730600000000010c010a017269000000630100000000000000020000000400000043000000732600000074007c006401190083017d0174017c01740283027d017c0174007c006402190083016702530029034e72010000007202000000290372490000007253000000da177869546f50537175617265644d696e7573314f76657236290272130000007234000000720700000072070000007208000000da135f5f667131325f66726f62656e6975735f703259010000730600000000010c010a01726b000000630200000000000000020000000500000043000000732400000074007c00640119007c0164011900830274007c00640219007c016402190083026702530029034e720100000072020000002901724a000000290272130000007214000000720700000072070000007208000000da065f5f663132615f01000073020000000001726c000000630200000000000000020000000500000043000000732400000074007c00640119007c0164011900830274007c00640219007c016402190083026702530029034e720100000072020000002901724b000000290272130000007214000000720700000072070000007208000000da065f5f663132736301000073020000000001726d000000630200000000000000050000000400000043000000736800000074007c00640119007c016402190083027d0274007c00640219007c016401190083027d0374017c027c0383027d0274007c00640219007c016402190083027d0474007c00640119007c016401190083027d0374027c0383017d037c0274017c047c0383026702530029034e7201000000720200000029037251000000724a0000007254000000290572130000007214000000723000000072310000007232000000720700000072070000007208000000da065f5f6631326d67010000730e0000000001120112010a01120112010801726e000000630200000000000000020000000400000043000000731c00000074007c00640119007c01830274007c00640219007c0183026702530029034e7201000000720200000029017251000000290272130000007214000000720700000072070000007208000000da0d5f5f6631326d5f7363616c61727101000073020000000001726f0000006302000000000000000500000004000000430000007350000000740083007d02784474017c016a0283006401180064036404830344005d2c7d0374037c0283017d047c017c033f006401400064026b03724474047c047c0083027d02711c7c047d02711c57007c02530029054e72020000007201000000e9ffffffff727000000029057265000000da0572616e6765da0a6269745f6c656e677468da0d5f5f667131325f737175617265726e000000290572130000007214000000da0373756dda01697231000000720700000072070000007208000000da0a5f5f667131325f65787075010000730e000000000106011a01080110010c0208017276000000630100000000000000040000000400000043000000737200000074007c00640119007c006402190083027d0174017c006401190083017d0274027c00640219007c0283027d0274027c00640119007c006402190083027d0374007c037c0283027d0374037c037c0183027d0374017c0183017d0274037c037c0283027d0374027c017c0183027c036702530029034e72010000007202000000290472510000007254000000724a000000724b00000029047213000000724c000000723100000072320000007207000000720700000072080000007273000000800100007312000000000112010c010e0112010a010a0108010a017273000000630100000000000000030000000400000043000000734c00000074007c006401190083017d0174007c006402190083017d0274017c0183017d0174027c027c0183027d0174037c0183017d02740474057c006401190083017c006402190067027c028302530029034e72010000007202000000290672590000007254000000724b0000007264000000726f000000724200000029037213000000723a000000723b000000720700000072070000007208000000da0d5f5f667131325f696e766572748c010000730c00000000010c010c0108010a01080172770000002905720f000000da0170da0171da027232720500000063040000000000000015000000070000004300000073d601000074007c01640119007c006402190083027d0474017c01640319007c006404190083027d0574027c0583017d0574037c057c0383027d0574037c057c006402190083027d0574007c057c006402190083027d0574037c047c006401190083027d0674027c0683017d0774017c077c0783027d0874017c087c0883027d0874007c067c0883027d0974037c057c006403190083027d0a74037c0a7c006403190083027d0a74007c00640119007c0883027d0b74027c0a83017d0c74037c0c7c0983027d0c74037c0c74017c0b7c0b830283027d0c74017c00640419007c0683027d0d74027c0d83017d0d74037c0d7c006402190083027d0d74037c0d7c0783027d0d74037c0b7c0c83027d0e74007c0e7c0a83027d0e74007c00640319007c0983027d0f74017c0f7c0f83027d0f74037c0e7c0f83027d1074027c0d83017d1174017c01640319007c0d83027d0e74027c0e83017d0e74037c0e7c0383027d0e74037c0e7c1183027d0e74007c0a7c016401190083027d0f74017c0f7c0f83027d0f74037c0f7c0e83027d1274047c0d7c026403190083027d1374017c137c1383027d1374057c0a83017d1474047c147c026401190083027d1474017c147c1483027d147c127c147c137c0c7c107c0d7c1167046604530029054e720100000072030000007202000000722200000029067233000000722e0000007239000000722f0000007236000000722d0000002915720f00000072780000007279000000727a0000007261000000da0144da0148da0149da0145da014ada024c31da0156da05724f757458da05724f75745a7231000000723b000000da05724f757459da05724f757454720a000000721c000000da0162720700000072070000007208000000da135f5f6c696e655f66756e6374696f6e5f61646495010000735000000000011201120108010a010e010e010e0108010a010a010a010e010e010e0108010a0110010e0108010e010a010a010a010e010a010a0108010e0108010a010a010e010a010a010e010a0108010e010a0172870000002903720f00000072790000007205000000630200000000000000120000000700000043000000739601000074007c006401190083017d0274007c006402190083017d0374007c0383017d0474017c00640119007c0383027d0574007c0583017d0574027c057c0283027d0574027c057c0483027d0574017c057c0583027d05740174017c027c0283027c0283027d0674007c0683017d0774017c047c0483027d0874017c087c0883027d0874017c087c0883027d0874027c0774017c057c05830283027d0974037c0674027c057c09830283027d0a74027c0a7c0883027d0a74017c00640219007c006403190083027d0b74007c0b83017d0b74027c0b7c0383027d0b74027c0b7c006404190083027d0b74017c00640119007c0683027d0c74007c0c83017d0c74017c037c0383027d0d74017c0d7c0d83027d0d74027c0c74017c0274017c077c0d8302830283027d0c74037c067c006404190083027d0e74017c0e7c0e83027d0e74047c0e83017d0f74057c0f7c016401190083027d0f74037c0b7c006404190083027d1074017c107c1083027d1074057c107c016402190083027d1074007c0b83017d117c0c7c0f7c107c097c0a7c0b7c1167046604530029054e720100000072020000007222000000720300000029067239000000722e000000722f0000007233000000722d00000072360000002912720f0000007279000000726000000072610000007262000000727b000000727e0000007263000000da024338da027258da027259da02725a720a000000da02423472310000007286000000721c000000da027254720700000072070000007208000000da165f5f6c696e655f66756e6374696f6e5f646f75626c65c0010000734400000000010c010c0108010e0108010a010a010a01100108010a010a010a01100110010a01120108010a010e010e0108010a010a0116010e010a0108010e010e010a010e010801728e0000002905da03726574720a0000007286000000721c00000072050000006304000000000000000a0000000400000043000000738c000000740083007c017c0267037d0474017c047c006401190083027d0474027c00640219007c0383027d0574037c027c0383027d06740083007c017c0667037d0774047c00640119007c006402190083027d087c057d0974017c087c0783027d0874057c087c0483027d0874057c087c0983027d0874067c0483017d0474047c097c0483027d097c087c096702530029034e720100000072020000002907722900000072510000007252000000722e000000724a000000724b0000007254000000290a728f000000720a0000007286000000721c000000da026132da0274337231000000723b0000007289000000728a000000720700000072070000007208000000da135f5f6c696e655f66756e6374696f6e5f6d756ce5010000731a00000000010c010e010e010a010c01120104010a010a010a0108010a01729200000029037279000000727800000072050000006302000000000000000f0000000600000043000000738e010000740083007d0274017c0083017d0374027c0183017d0474037c0383017d057c037d0674047c036401190083017d0778b074057406740783016401180064026403830344005d987d0874087c067c0483025c047d097d0a7d0b7d067c08740674078301640118006b03727274097c0283017d02740a7c027c097c0a7c0b83047d0274077c086401180019007d0c7c0c64016b0272ac740b7c067c037c047c0783045c047d097d0a7d0b7d066e227c0c64046b027244740b7c067c057c047c0783045c047d097d0a7d0b7d066e027144740a7c027c097c0a7c0b83047d0271445700740c740d7c03640219008301740e8302740c740d7c03640119008301740f8302741083007410830067047d0d74117c0364021900741283027c0364011900741083007410830067047d0e74047c0d6401190083017d07740b7c067c0d7c047c0783045c047d097d0a7d0b7d06740a7c027c097c0a7c0b83047d0274047c0e6401190083017d07740b7c067c0e7c047c0783045c047d097d0a7d0b7d06740a7c027c097c0a7c0b83047d027c02530029054e720200000072010000007270000000727000000029137265000000da135f5f74776973745f6d616b655f616666696e65da135f5f63757276655f6d616b655f616666696e65da0b5f5f74776973745f6e6567723900000072710000007223000000da1670736575646f5f62696e6172795f656e636f64696e67728e0000007273000000729200000072870000007233000000722c0000007244000000da107869546f504d696e7573314f76657232722800000072360000007248000000290f72790000007278000000728f000000da0761416666696e65da0762416666696e65da066d696e757341720f000000727a0000007275000000720a0000007286000000721c000000da0173da027131da076d696e75735132720700000072070000007208000000da085f5f6d696c6c6572f5010000733c0000000001060108010801080104010c011a011201100108010e010c0108011801080118020201120112011201080112010c010c0116010e010c0116010e01729e000000290272780000007205000000630100000000000000140000000300000043000000735001000074007c0083017d0174017c0083017d0274027c017c0283027d0174037c0183017d0374027c017c0383027d0174047c0183017d0474037c0183017d0574047c0583017d0674057c01740683027d0774057c07740683027d0874057c08740683027d0974047c0783017d0a74047c0883017d0b74047c0983017d0c74037c0883017d0d74027c047c0583027d0e74027c0e7c0683027d0e74007c0183017d0f74007c0883017d1074007c0a83017d0a74027c077c0b83027d1174007c1183017d1174027c097c0c83027d1274007c1283017d1274077c1283017d1374027c137c1183027d1374027c137c1083027d1374027c0a7c1083027d0174027c017c1383027d0174027c137c0d83027d1374077c0183017d0174027c017c1383027d0174077c0183017d0174027c017c0f83027d1374027c017c0e83027d0174077c1383017d1374027c137c0183027d137c13530029014e290872670000007277000000726e000000726b00000072690000007276000000da0175727300000029147278000000723a000000723c000000723b000000da026670da03667032da03667033da026675da03667532da03667533da027933da0466753270da0466753370da027932da027930da027931da027935da027934da027936724f000000720700000072070000007208000000da165f5f66696e616c5f6578706f6e656e74696174696f6e17020000734c0000000001080108010a0108010a010801080108010a010a010a0108010801080108010a010a010801080108010a0108010a01080108010a010a010a010a010a0108010a0108010a010a0108010a0172af0000002902721c0000007205000000630100000000000000040000000400000043000000737600000074007c0064011900830172107c00530074017c006401190083017230740283007403830074028300740283006704530074047c006401190083017d0174057c0183017d0274067c027c0183027d0374067c00640219007c02830274067c00640319007c0383027403830074038300670453006400530029044e7222000000720100000072020000002907722a000000722b00000072290000007228000000723d000000723900000072330000002904721c000000da047a496e76da057a496e7632da057a496e7633720700000072070000007208000000729300000040020000731200000000010c0104010c0114020c0108010a011c0172930000002903720a00000072860000007205000000630200000000000000150000000400000043000000738a01000074007c008301720c7c01530074007c01830172187c00530074017c006401190083017d0274017c016401190083017d0374027c00640219007c0383027d0474027c01640219007c0283027d0574027c01640119007c0383027d0674027c00640319007c0683027d0774027c00640119007c0283027d0674027c01640319007c0683027d0874037c057c0483027d0974047c097405830083027d0a74067c097c0983027d0674017c0683017d0b74027c097c0b83027d0c74037c087c0783027d0674047c067405830083027d0d7c0a72dc7c0d72dc74077c008301530074067c067c0683027d0e74027c047c0b83027d0f74017c0e83017d1074067c0f7c0f83027d0674037c107c0c83027d1174037c117c0683027d1274037c0f7c1283027d0674027c077c0c83027d1074067c107c1083027d1174027c0e7c0683027d1074037c107c1183027d1374067c00640119007c016401190083027d0674017c0683017d1074037c107c0283027d0674037c067c0383027d1074027c107c0983027d147c127c137c146703530029044e7222000000720100000072020000002908da135f5f74776973745f69735f696e66696e69747972390000007233000000722f00000072380000007229000000722e000000da0e5f5f74776973745f646f75626c652915720a0000007286000000da037a3132da037a3232da027531da0275327231000000da027331da027332da0168da0678457175616c7275000000da016ada0679457175616c720f000000da0176da027434da027436da026358da026359da02635a720700000072070000007208000000da0b5f5f74776973745f6164644d020000734c000000000108010401080104010c010c010e010e010e010e010e010e010a010c010a0108010a010a010c01080108010a010a0108010a010a010a010a010a010a010a010a01120108010a010a010a0172c50000002902720a00000072050000006301000000000000000c000000040000004300000073f800000074007c00640119007c006401190083027d0174007c00640219007c006402190083027d0274007c027c0283027d0374017c00640119007c0283027d0474007c047c0483027d0574027c057c0183027d0474027c047c0383027d0574017c057c0583027d0674017c017c0183027d0474017c047c0183027d0774007c077c0783027d0874017c067c0683027d0474027c087c0483027d0974007c00640219007c006403190083027d0a74017c0a7c0a83027d0a74017c037c0383027d0474017c047c0483027d0574017c057c0583027d0474027c067c0983027d0b74007c077c0b83027d0574027c057c0483027d0b7c097c0b7c0a6703530029044e72010000007202000000722200000029037233000000722e000000722f000000290c720a0000007260000000726100000072620000007231000000723b000000da0164da0165da016672c200000072c400000072c300000072070000007207000000720800000072b400000076020000732c0000000001120112010a010e010a010a010a010a010a010a010a010a010a0112010a010a010a010a010a010a010a0172b40000002903da027074721f0000007205000000630200000000000000040000000600000043000000737800000074007c01830164016b02721c7401830074018300740283006703530074028300740283007402830067037c0067027d02783e74037c01830144005d327d0374047c027c0319007c027c0364024100190083027c027c03640241003c0074057c027c03190083017c027c033c00713a57007c0264011900530029034e720100000072020000002906721a00000072280000007229000000722000000072c500000072b4000000290472c9000000721f000000da0152da026b62720700000072070000007208000000da0b5f5f74776973745f6d756c8f020000730e00000000010c01100114010e011e01140172cc000000630100000000000000010000000400000043000000731e0000007c006401190074007c006402190083017c0064031900740183006704530029044e7201000000720200000072220000002902722d00000072290000002901721c000000720700000072070000007208000000729500000099020000730200000000017295000000630100000000000000010000000300000043000000730c00000074007c00640119008301530029024e72220000002901722b0000002901721c00000072070000007207000000720800000072b30000009d0200007302000000000172b3000000630100000000000000030000000400000043000000735600000074007c0083017d0074017c00830172146401530074027c006402190083017d0174027c006403190083017d0274037c027c006403190083027d0274047c017c0283027d0174047c01740583027d0174067c018301530029044e54720200000072010000002907729300000072b300000072390000007233000000722f000000da06747769737442722b0000002903721c00000072a9000000da027833720700000072070000007208000000da135f5f74776973745f69735f6f6e5f6375727665a1020000731200000000010801080104010c010c010e010a010a0172cf000000630200000000000000150000000400000043000000739801000074007c008301720c7c01530074007c01830172187c00530074017c00640119007c006401190083027d0274017c01640119007c016401190083027d0374017c00640219007c0383027d0474017c01640219007c0283027d0574017c01640119007c0383027d0674017c00640319007c0683027d0774017c00640119007c0283027d0674017c01640319007c0683027d0874027c057c0483027d0974037c09640283027d0a74047c097c0983027d0674017c067c0683027d0b74017c097c0b83027d0c74027c087c0783027d0674037c06640283027d0d7c0a72e67c0d72e674057c008301530074047c067c0683027d0e74017c047c0b83027d0f74017c0e7c0e83027d1074047c0f7c0f83027d0674027c107c0c83027d1174027c117c0683027d1274027c0f7c1283027d0674017c077c0c83027d1074047c107c1083027d1174017c0e7c0683027d1074027c107c1183027d1374047c00640119007c016401190083027d0674017c067c0683027d1074027c107c0283027d0674027c067c0383027d1074017c107c0983027d147c127c137c146703530029044e7222000000720100000072020000002906da135f5f63757276655f69735f696e66696e6974797216000000721700000072180000007215000000da0e5f5f63757276655f646f75626c652915720a000000728600000072b500000072b600000072b700000072b8000000723100000072b900000072ba00000072bb00000072bc000000727500000072bd00000072be000000720f00000072bf00000072c000000072c100000072c200000072c300000072c4000000720700000072070000007208000000da0b5f5f63757276655f616464ad020000734c00000000010801040108010401120112010e010e010e010e010e010e010a010a010a010a010a010a010a01080108010a010a010a010a010a010a010a010a010a010a010a0112010a010a010a010a0172d20000006301000000000000000c000000040000004300000073f800000074007c00640119007c006401190083027d0174007c00640219007c006402190083027d0274007c027c0283027d0374017c00640119007c0283027d0474007c047c0483027d0574027c057c0183027d0474027c047c0383027d0574017c057c0583027d0674017c017c0183027d0474017c047c0183027d0774007c077c0783027d0874017c067c0683027d0474027c087c0483027d0974007c00640219007c006403190083027d0a74017c0a7c0a83027d0a74017c037c0383027d0474017c047c0483027d0574017c057c0583027d0474027c067c0983027d0b74007c077c0b83027d0574027c057c0483027d0b7c097c0b7c0a6703530029044e7201000000720200000072220000002903721600000072150000007217000000290c720a0000007260000000726100000072620000007231000000723b00000072c600000072c700000072c800000072c200000072c400000072c300000072070000007207000000720800000072d1000000d6020000732c0000000001120112010a010e010a010a010a010a010a010a010a010a010a0112010a010a010a010a010a010a010a0172d1000000630200000000000000040000000600000043000000736c00000074007c01830164016b0272166402640264016703530064016401640167037c0067027d02783e74017c01830144005d327d0374027c027c0319007c027c0364024100190083027c027c03640241003c0074037c027c03190083017c027c033c00712e57007c0264011900530029034e720100000072020000002904721a000000722000000072d200000072d1000000290472c9000000721f00000072ca00000072cb000000720700000072070000007208000000da0b5f5f63757276655f6d756cef020000730e00000000010c010a010e010e011e01140172d3000000630100000000000000010000000200000043000000730c0000007c006401190064026b02530029034e7222000000720100000072070000002901721c00000072070000007207000000720800000072d0000000f90200007302000000000172d0000000630100000000000000010000000400000043000000731c0000007c006401190074007c006402190083017c006403190064016704530029044e720100000072020000007222000000290172190000002901721c000000720700000072070000007208000000da0b5f5f63757276655f6e6567fd0200007302000000000172d4000000630100000000000000060000000400000043000000737800000074007c00640119006402830272127c00530074007c006401190064038302722c64036402640364036704530074017c006401190083017d0174027c00640219007c0183027d0274027c017c0183027d0374027c00640319007c0383027d0474027c027c0383027d057c047c0564026402670453006400530029044e72220000007202000000720100000029037218000000721200000072160000002906721c00000072b0000000723100000072b100000072c200000072c3000000720700000072070000007208000000729400000001030000731400000000010e0104010e010c020c010e010a010e010a017294000000630100000000000000030000000400000043000000735a00000074007c0083017d0074017c00830172146401530074027c00640219007c006402190083027d0174027c00640319007c006403190083027d0274027c027c006403190083027d0274037c02740483027d0274057c017c028302530029044e54720200000072010000002906729400000072d000000072160000007215000000da0663757276654272180000002903721c00000072a900000072ce000000720700000072070000007208000000da135f5f63757276655f69735f6f6e5f63757276650f03000073100000000001080108010401120112010e010a0172d60000002903da0151da01507205000000630200000000000000030000000300000043000000734400000074007c0183017310740164018301820174027c0083017320740164028301820174037c018301733074047c008301723674058300530074067c007c0183027d027c02530029034e7a1650206973206e6f74206f6e207468652063757276652e7a1651206973206e6f74206f6e207468652063757276652e290772d6000000722400000072cf00000072d000000072b30000007265000000729e000000290372d700000072d8000000720f000000720700000072070000007208000000da095f5f70616972696e671a030000730c000000000110011001100106010a0172d9000000da18636f6e5f76657269666965725f6f70745f70616972696e672903da024943da06696e70757473720500000063020000000000000004000000070000004300000073520000007c00640119007d027844740074017c018301830144005d347d037c017c03190074026b00732e740364028301820174047c0274057c007c036403170019007c017c031900830283027d02711657007c02530029044e72010000007a1f76657269666965722d6774652d736e61726b2d7363616c61722d6669656c647202000000290672710000007223000000da0b63757276655f6f72646572722400000072d200000072d3000000290472db00000072dc000000da04766b5f787275000000720700000072070000007208000000da0a636f6d707574655f766b23030000730a0000000002080112011401200172df0000002903727800000072790000007205000000630200000000000000040000000700000043000000737200000074007c006401190083017c0064013c00740183007d02784274026402830144005d367d0374037c017c0319008301732074047c007c0319008301723e712074057c0274067c017c0319007c007c031900830283027d027120570074077c0283017d0274087c028301736e640353006401530029044e7201000000e9040000007202000000290972d40000007265000000727100000072b300000072d0000000726e00000072d900000072af000000726600000029047278000000727900000072340000007275000000720700000072070000007208000000da0c66696e616c5f726573756c742c03000073140000000002100106010e01180102011c0108010801040172e10000004e727000000072700000007270000000727000000072700000007270000000727000000072700000002901720100000029017201000000290172010000002901720100000029017201000000295c729600000072dd0000007206000000729f00000072680000007244000000729700000072480000007247000000726a000000724300000072cd00000072d5000000721a00000072090000007212000000721500000072160000007217000000da04626f6f6c721800000072190000007220000000da046c69737472250000007226000000722700000072280000007229000000722a000000722b000000722c000000722d000000722e000000722f00000072330000007236000000723700000072380000007239000000723d000000723e000000723f00000072400000007241000000724200000072460000007249000000724a000000724b0000007251000000725200000072530000007254000000725900000072640000007265000000726600000072670000007269000000726b000000726c000000726d000000726e000000726f000000727600000072730000007277000000da057475706c657287000000728e0000007292000000729e00000072af000000729300000072c500000072b400000072cc000000729500000072b300000072cf00000072d200000072d100000072d300000072d000000072d4000000729400000072d600000072d9000000da085f5f6578706f727472df00000072e10000007207000000720700000072070000007208000000da083c6d6f64756c653e0100000073c000000020012e012e010a02040304020402020206030202060302020603040304020403020206030202060204031007160c12041204120412041007080410061005100512041204100410041004100412041204120a1206100e12041009100b120412041005100510041009100612051205121b120512051006101810111204100410041006100612041204120a1204120b100c1009162b1225161012221029100d12291019120a10041004100c12291019120a10041004100e100b1209060114080601