1/11/2022, 9:22:52 PM

0

58

89f67bb871351a1629d66676e4bd92bbacb23bd0649b890542ef98f1b664a497

6 ( 0.462 dTAU )

submission

submit_contract

e72985de9f292fa2f131e9ed495f7eff9f9c9e39ae32dd718fac53fc3ccaa12f1adb7572648f8ca0478fcd0123d014313b624a2b3d8fa0ed8ecc942f08377d0c

def FQ(n:int)->int: n=n%p2 if n<0:n+=p2 return n def fq_inv(a:int,n:int=p2)->int: if a==0:return 0 B,D=1,0;A,C=a%n,n while A>1:E=C//A;F,G=D-B*E,C-A*E;B,A,D,C=F,G,B,A return B%n def fq_add(self:int,other:int)->int:return FQ(self+other) def fq_mul(self:int,other:int)->int:return FQ(self*other) def fq_sub(self:int,other:int)->int:return FQ(self-other) def fq_eq(self:int,other:int)->bool:return self==other def fq_neg(self:int)->int: A=self;A=-A if A<0:A+=p2 return A def bits_of(k):return[int(A)for A in '{0:b}'.format(k)] def FQ2(coeffs:list)->list:A=coeffs;assert len(A)==2,f"FQ2 must have 2 coefficients but had {len(A)}";return A def FQ6(coeffs:list)->list:A=coeffs;assert len(A)==3 and len(A[0])==2,'FQ6 must have 3 FQ2s';return A def FQ12(coeffs:list)->list:A=coeffs;assert len(A)==2 and len(A[0])==3,'FQ12 must have 2 FQ6s';return A def fq2_one(n:int=0)->list:return[0,1] def fq2_zero(n:int=0)->list:return[0,0] def fq2_is_one(self:list)->bool:return self[0]==0 and self[1]==1 def fq2_is_zero(self:list)->bool:return self[0]==0 and self[1]==0 def fq2_conjugate(self:list)->list:return[fq_neg(self[0]),self[1]] def fq2_neg(self:list)->list:return[fq_neg(self[0]),fq_neg(self[1])] def fq2_add(self:list,other:list)->list:A=other;return[fq_add(self[0],A[0]),fq_add(self[1],A[1])] def fq2_sub(self:list,other:list)->list:A=other;return[fq_sub(self[0],A[0]),fq_sub(self[1],A[1])] def fq2_mul(self:list,other:list)->list:B=other;A=self;C=fq_mul(A[0],B[1]);D=fq_mul(B[0],A[1]);C=fq_add(C,D);E=fq_mul(A[1],B[1]);D=fq_mul(A[0],B[0]);E=fq_sub(E,D);return[C,E] def fq2_mul_scalar(self:list,other:int)->list:A=other;B=fq_mul(self[0],A);C=fq_mul(self[1],A);return[B,C] def fq2_mul_xi(self:list)->list:C=self;A=fq_add(C[0],C[0]);A=fq_add(A,A);A=fq_add(A,A);A=fq_add(A,C[0]);A=fq_add(A,C[1]);B=fq_add(C[1],C[1]);B=fq_add(B,B);B=fq_add(B,B);B=fq_add(B,C[1]);B=fq_sub(B,C[0]);return[A,B] def fq2_eq(self:list,other:list)->bool:A=other;return self[0]==A[0]and self[1]==A[1] def fq2_square(self:list)->list:A=self;B=fq_sub(A[1],A[0]);C=fq_add(A[0],A[1]);C=fq_mul(B,C);B=fq_mul(A[0],A[1]);B=fq_add(B,B);return[B,C] def fq2_invert(self:list)->list:A=self;B=fq_mul(A[0],A[0]);D=fq_mul(A[1],A[1]);B=fq_add(B,D);C=fq_inv(B);B=fq_neg(A[0]);E=fq_mul(B,C);F=fq_mul(A[1],C);return[E,F] def fq6_one(n:int=0)->list:return[fq2_zero(),fq2_zero(),fq2_one()] def fq6_zero(n:int=0)->list:return[fq2_zero(),fq2_zero(),fq2_zero()] def fq6_is_zero(self:list)->bool:A=self;return fq2_is_zero(A[0])and fq2_is_zero(A[1])and fq2_is_zero(A[2]) def fq6_is_one(self:list)->bool:A=self;return fq2_is_zero(A[0])and fq2_is_zero(A[1])and fq2_is_one(A[2]) def fq6_neg(self:list)->list:A=self;return[fq2_neg(A[0]),fq2_neg(A[1]),fq2_neg(A[2])] def fq6_frobenius(self:list)->list:A=self;B=fq2_conjugate(A[0]);C=fq2_conjugate(A[1]);D=fq2_conjugate(A[2]);B=fq2_mul(B,xiTo2PMinus2Over3);C=fq2_mul(C,xiToPMinus1Over3);return[B,C,D] def fq6_frobenius_p2(self:list)->list:A=self;B=fq2_mul_scalar(A[0],xiTo2PSquaredMinus2Over3);C=fq2_mul_scalar(A[1],xiToPSquaredMinus1Over3);return[B,C,A[2]] def fq6_add(self:list,other:list)->list:B=other;A=self;return[fq2_add(A[0],B[0]),fq2_add(A[1],B[1]),fq2_add(A[2],B[2])] def fq6_sub(self:list,other:list)->list:B=other;A=self;return[fq2_sub(A[0],B[0]),fq2_sub(A[1],B[1]),fq2_sub(A[2],B[2])] def fq6_mul(self:list,other:list)->list:B=other;A=self;H=fq2_mul(A[2],B[2]);I=fq2_mul(A[1],B[1]);J=fq2_mul(A[0],B[0]);D=fq2_add(A[0],A[1]);G=fq2_add(B[0],B[1]);C=fq2_mul(D,G);C=fq2_sub(C,I);C=fq2_sub(C,J);C=fq2_mul_xi(C);C=fq2_add(C,H);D=fq2_add(A[1],A[2]);G=fq2_add(B[1],B[2]);E=fq2_mul(D,G);D=fq2_mul_xi(J);E=fq2_sub(E,H);E=fq2_sub(E,I);E=fq2_add(E,D);D=fq2_add(A[0],A[2]);G=fq2_add(B[0],B[2]);F=fq2_mul(D,G);F=fq2_sub(F,H);F=fq2_add(F,I);F=fq2_sub(F,J);return[F,E,C] def fq6_mul_scalar(self:list,other:list)->list:B=other;A=self;return[fq2_mul(A[0],B),fq2_mul(A[1],B),fq2_mul(A[2],B)] def fq6_mul_gfp(self:list,other:int)->list:B=other;A=self;return[fq2_mul_scalar(A[0],B),fq2_mul_scalar(A[1],B),fq2_mul_scalar(A[2],B)] def fq6_mul_tau(self:list)->list:A=self;B=fq2_mul_xi(A[0]);C=A[1];return[C,A[2],B] def fq6_square(self:list)->list:B=self;E=fq2_square(B[2]);F=fq2_square(B[1]);G=fq2_square(B[0]);A=fq2_add(B[0],B[1]);A=fq2_square(A);A=fq2_sub(A,F);A=fq2_sub(A,G);A=fq2_mul_xi(A);A=fq2_add(A,E);C=fq2_add(B[1],B[2]);C=fq2_square(C);C=fq2_sub(C,E);C=fq2_sub(C,F);H=fq2_mul_xi(G);C=fq2_add(C,H);D=fq2_add(B[0],B[2]);D=fq2_square(D);D=fq2_sub(D,E);D=fq2_add(D,F);D=fq2_sub(D,G);return[D,C,A] def fq6_invert(self:list)->list:A=self;F=fq2_square(A[0]);G=fq2_square(A[1]);H=fq2_square(A[2]);I=fq2_mul(A[0],A[1]);J=fq2_mul(A[0],A[2]);K=fq2_mul(A[1],A[2]);C=fq2_sub(H,fq2_mul_xi(I));D=fq2_sub(fq2_mul_xi(F),K);E=fq2_sub(G,J);B=fq2_mul_xi(fq2_mul(E,A[1]));B=fq2_add(B,fq2_mul(C,A[2]));B=fq2_add(B,fq2_mul_xi(fq2_mul(D,A[0])));B=fq2_invert(B);return[fq2_mul(E,B),fq2_mul(D,B),fq2_mul(C,B)] def fq12_one(n:int=0)->list:return[fq6_zero(),fq6_one()] def fq12_zero(n:int=0)->list:return[fq6_zero(),fq6_zero()] def fq12_is_zero(self:list)->bool:return fq6_is_zero(self[0])and fq6_is_zero(self[1]) def fq12_is_one(self:list)->bool:return fq6_is_zero(self[0])and fq6_is_one(self[1]) def fq12_conjugate(self:list)->list:return[fq6_neg(self[0]),self[1]] def fq12_neg(self:list)->list:return[fq6_neg(self[0]),fq6_neg(self[1])] def fq12_frobenius(self:list)->list:A=fq6_frobenius(self[0]);A=fq6_mul_scalar(A,xiToPMinus1Over6);return[A,fq6_frobenius(self[1])] def fq12_frobenius_p2(self:list)->list:A=fq6_frobenius_p2(self[0]);A=fq6_mul_gfp(A,xiToPSquaredMinus1Over6);return[A,fq6_frobenius_p2(self[1])] def fq12_add(self:list,other:list)->list:A=other;return[fq6_add(self[0],A[0]),fq6_add(self[1],A[1])] def fq12_sub(self:list,other:list)->list:A=other;return[fq6_sub(self[0],A[0]),fq6_sub(self[1],A[1])] def fq12_mul(self:list,other:list)->list:C=other;B=self;D=fq6_mul(B[0],C[1]);A=fq6_mul(B[1],C[0]);D=fq6_add(D,A);E=fq6_mul(B[1],C[1]);A=fq6_mul(B[0],C[0]);A=fq6_mul_tau(A);return[D,fq6_add(E,A)] def fq12_mul_scalar(self:list,other:list)->list:A=other;return[fq6_mul(self[0],A),fq6_mul(self[1],A)] def fq12_exp(self:list,other:int)->list: A=other;sum=fq12_one() for C in range(A.bit_length()-1,-1,-1): B=fq12_square(sum) if A>>C&1!=0:sum=fq12_mul(B,self) else:sum=B return sum def fq12_square(self:list)->list:B=self;D=fq6_mul(B[0],B[1]);C=fq6_mul_tau(B[0]);C=fq6_add(B[1],C);A=fq6_add(B[0],B[1]);A=fq6_mul(A,C);A=fq6_sub(A,D);C=fq6_mul_tau(D);A=fq6_sub(A,C);return[fq6_add(D,D),A] def fq12_invert(self:list)->list:B=self;A=fq6_square(B[0]);C=fq6_square(B[1]);A=fq6_mul_tau(A);A=fq6_sub(C,A);C=fq6_invert(A);return fq12_mul_scalar([fq6_neg(B[0]),B[1]],C) def line_function_add(r:list,p:list,q:list,r2:list)->tuple:O=fq2_mul(p[0],r[3]);C=fq2_add(p[1],r[2]);C=fq2_square(C);C=fq2_sub(C,r2);C=fq2_sub(C,r[3]);C=fq2_mul(C,r[3]);J=fq2_sub(O,r[0]);K=fq2_square(J);H=fq2_add(K,K);H=fq2_add(H,H);M=fq2_mul(J,H);E=fq2_sub(C,r[1]);E=fq2_sub(E,r[1]);L=fq2_mul(r[0],H);F=fq2_square(E);F=fq2_sub(F,M);F=fq2_sub(F,fq2_add(L,L));B=fq2_add(r[2],J);B=fq2_square(B);B=fq2_sub(B,r[3]);B=fq2_sub(B,K);A=fq2_sub(L,F);A=fq2_mul(A,E);D=fq2_mul(r[1],M);D=fq2_add(D,D);P=fq2_sub(A,D);N=fq2_square(B);A=fq2_add(p[1],B);A=fq2_square(A);A=fq2_sub(A,r2);A=fq2_sub(A,N);D=fq2_mul(E,p[0]);D=fq2_add(D,D);Q=fq2_sub(D,A);I=fq2_mul_scalar(B,q[1]);I=fq2_add(I,I);G=fq2_neg(E);G=fq2_mul_scalar(G,q[0]);G=fq2_add(G,G);return Q,G,I,[F,P,B,N] def line_function_double(r:list,q:list)->tuple:E=fq2_square(r[0]);F=fq2_square(r[1]);K=fq2_square(F);A=fq2_add(r[0],F);A=fq2_square(A);A=fq2_sub(A,E);A=fq2_sub(A,K);A=fq2_add(A,A);H=fq2_add(fq2_add(E,E),E);N=fq2_square(H);C=fq2_add(K,K);C=fq2_add(C,C);C=fq2_add(C,C);O=fq2_sub(N,fq2_add(A,A));L=fq2_mul(H,fq2_sub(A,O));L=fq2_sub(L,C);B=fq2_add(r[1],r[2]);B=fq2_square(B);B=fq2_sub(B,F);B=fq2_sub(B,r[3]);G=fq2_add(r[0],H);G=fq2_square(G);I=fq2_add(F,F);I=fq2_add(I,I);G=fq2_sub(G,fq2_add(E,fq2_add(N,I)));J=fq2_mul(H,r[3]);J=fq2_add(J,J);M=fq2_neg(J);M=fq2_mul_scalar(M,q[0]);D=fq2_mul(B,r[3]);D=fq2_add(D,D);D=fq2_mul_scalar(D,q[1]);P=fq2_square(B);return G,M,D,[O,L,B,P] def line_function_mul(ret:list,a:list,b:list,c:list)->list:C=ret;B=[fq2_zero(),a,b];B=fq6_mul(B,C[0]);E=fq6_mul_scalar(C[1],c);F=fq2_add(b,c);G=[fq2_zero(),a,F];A=fq6_add(C[0],C[1]);D=E;A=fq6_mul(A,G);A=fq6_sub(A,B);A=fq6_sub(A,D);B=fq6_mul_tau(B);D=fq6_add(D,B);return[A,D] def miller(q:list,p:list)->list: A=fq12_one();C=twist_make_affine(q);H=curve_make_affine(p);M=twist_neg(C);B=C;G=fq2_square(C[1]) for I in range(len(pseudo_binary_encoding)-1,0,-1): D,E,F,B=line_function_double(B,H) if I!=len(pseudo_binary_encoding)-1:A=fq12_square(A) A=line_function_mul(A,D,E,F);J=pseudo_binary_encoding[I-1] if J==1:D,E,F,B=line_function_add(B,C,H,G) elif J==-1:D,E,F,B=line_function_add(B,M,H,G) else:continue A=line_function_mul(A,D,E,F) K=[fq2_mul(fq2_conjugate(C[0]),xiToPMinus1Over3),fq2_mul(fq2_conjugate(C[1]),xiToPMinus1Over2),fq2_one(),fq2_one()];L=[fq2_mul_scalar(C[0],xiToPSquaredMinus1Over3),C[1],fq2_one(),fq2_one()];G=fq2_square(K[1]);D,E,F,B=line_function_add(B,K,H,G);A=line_function_mul(A,D,E,F);G=fq2_square(L[1]);D,E,F,B=line_function_add(B,L,H,G);A=line_function_mul(A,D,E,F);return A def final_exponentiation(p:list)->list:A=fq12_conjugate(p);L=fq12_invert(p);A=fq12_mul(A,L);M=fq12_frobenius_p2(A);A=fq12_mul(A,M);N=fq12_frobenius(A);I=fq12_frobenius_p2(A);O=fq12_frobenius(I);D=fq12_exp(A,u);C=fq12_exp(D,u);J=fq12_exp(C,u);E=fq12_frobenius(D);P=fq12_frobenius(C);Q=fq12_frobenius(J);R=fq12_frobenius_p2(C);F=fq12_mul(N,I);F=fq12_mul(F,O);S=fq12_conjugate(A);K=fq12_conjugate(C);E=fq12_conjugate(E);G=fq12_mul(D,P);G=fq12_conjugate(G);H=fq12_mul(J,Q);H=fq12_conjugate(H);B=fq12_square(H);B=fq12_mul(B,G);B=fq12_mul(B,K);A=fq12_mul(E,K);A=fq12_mul(A,B);B=fq12_mul(B,R);A=fq12_square(A);A=fq12_mul(A,B);A=fq12_square(A);B=fq12_mul(A,S);A=fq12_mul(A,F);B=fq12_square(B);B=fq12_mul(B,A);return B def twist_make_affine(c:list)->list: if fq2_is_one(c[2]):return c elif fq2_is_zero(c[2]):return[fq2_zero(),fq2_one(),fq2_zero(),fq2_zero()] else:A=fq2_invert(c[2]);B=fq2_square(A);C=fq2_mul(B,A);return[fq2_mul(c[0],B),fq2_mul(c[1],C),fq2_one(),fq2_one()] def twist_add(a:list,b:list)->list: if twist_is_infinity(a):return b if twist_is_infinity(b):return a D=fq2_square(a[2]);E=fq2_square(b[2]);H=fq2_mul(a[0],E);N=fq2_mul(b[0],D);A=fq2_mul(b[2],E);I=fq2_mul(a[1],A);A=fq2_mul(a[2],D);O=fq2_mul(b[1],A);C=fq2_sub(N,H);P=fq2_eq(C,fq2_zero());A=fq2_add(C,C);J=fq2_square(A);K=fq2_mul(C,J);A=fq2_sub(O,I);Q=fq2_eq(A,fq2_zero()) if P and Q:return twist_double(a) L=fq2_add(A,A);F=fq2_mul(H,J);B=fq2_square(L);A=fq2_add(F,F);G=fq2_sub(B,K);M=fq2_sub(G,A);A=fq2_sub(F,M);B=fq2_mul(I,K);G=fq2_add(B,B);B=fq2_mul(L,A);R=fq2_sub(B,G);A=fq2_add(a[2],b[2]);B=fq2_square(A);A=fq2_sub(B,D);B=fq2_sub(A,E);S=fq2_mul(B,C);return[M,R,S] def twist_double(a:list)->list:C=fq2_mul(a[0],a[0]);E=fq2_mul(a[1],a[1]);F=fq2_mul(E,E);A=fq2_add(a[0],E);B=fq2_mul(A,A);A=fq2_sub(B,C);B=fq2_sub(A,F);G=fq2_add(B,B);A=fq2_add(C,C);H=fq2_add(A,C);K=fq2_mul(H,H);A=fq2_add(G,G);J=fq2_sub(K,A);D=fq2_mul(a[1],a[2]);D=fq2_add(D,D);A=fq2_add(F,F);B=fq2_add(A,A);A=fq2_add(B,B);I=fq2_sub(G,J);B=fq2_mul(H,I);I=fq2_sub(B,A);return[J,I,D] def twist_mul(pt:list,k:int)->list: if int(k)==0:return[fq2_one(),fq2_one(),fq2_zero()] A=[[fq2_zero(),fq2_zero(),fq2_zero()],pt] for B in bits_of(k):A[B^1]=twist_add(A[B],A[B^1]);A[B]=twist_double(A[B]) return A[0] def twist_neg(c:list)->list:return[c[0],fq2_neg(c[1]),c[2],fq2_zero()] def twist_is_infinity(c:list)->bool:return fq2_is_zero(c[2]) def twist_is_on_curve(c:list)->bool: c=twist_make_affine(c) if twist_is_infinity(c):return True A=fq2_square(c[1]);B=fq2_square(c[0]);B=fq2_mul(B,c[0]);A=fq2_sub(A,B);A=fq2_sub(A,twistB);return fq2_is_zero(A) def curve_add(a:list,b:list)->list: if curve_is_infinity(a):return b if curve_is_infinity(b):return a D=fq_mul(a[2],a[2]);E=fq_mul(b[2],b[2]);I=fq_mul(a[0],E);N=fq_mul(b[0],D);A=fq_mul(b[2],E);J=fq_mul(a[1],A);A=fq_mul(a[2],D);O=fq_mul(b[1],A);C=fq_sub(N,I);P=fq_eq(C,0);A=fq_add(C,C);K=fq_mul(A,A);L=fq_mul(C,K);A=fq_sub(O,J);Q=fq_eq(A,0) if P and Q:return curve_double(a) F=fq_add(A,A);G=fq_mul(I,K);B=fq_mul(F,F);A=fq_add(G,G);H=fq_sub(B,L);M=fq_sub(H,A);A=fq_sub(G,M);B=fq_mul(J,L);H=fq_add(B,B);B=fq_mul(F,A);R=fq_sub(B,H);A=fq_add(a[2],b[2]);B=fq_mul(A,A);A=fq_sub(B,D);B=fq_sub(A,E);S=fq_mul(B,C);return[M,R,S] def curve_double(a:list)->list:C=fq_mul(a[0],a[0]);E=fq_mul(a[1],a[1]);F=fq_mul(E,E);A=fq_add(a[0],E);B=fq_mul(A,A);A=fq_sub(B,C);B=fq_sub(A,F);G=fq_add(B,B);A=fq_add(C,C);H=fq_add(A,C);K=fq_mul(H,H);A=fq_add(G,G);J=fq_sub(K,A);D=fq_mul(a[1],a[2]);D=fq_add(D,D);A=fq_add(F,F);B=fq_add(A,A);A=fq_add(B,B);I=fq_sub(G,J);B=fq_mul(H,I);I=fq_sub(B,A);return[J,I,D] def curve_mul(pt:list,k:int)->list: if int(k)==0:return[1,1,0] A=[[0,0,0],pt] for B in bits_of(k):A[B^1]=curve_add(A[B],A[B^1]);A[B]=curve_double(A[B]) return A[0] def curve_is_infinity(c:list)->bool:return c[2]==0 def curve_neg(c:list)->list:return[c[0],fq_neg(c[1]),c[2],0] def curve_make_affine(c:list)->list: if fq_eq(c[2],1):return c elif fq_eq(c[2],0):return[0,1,0,0] else:A=fq_inv(c[2]);C=fq_mul(c[1],A);B=fq_mul(A,A);D=fq_mul(c[0],B);E=fq_mul(C,B);return[D,E,1,1] def curve_is_on_curve(c:list)->bool: c=curve_make_affine(c) if curve_is_infinity(c):return True B=fq_mul(c[1],c[1]);A=fq_mul(c[0],c[0]);A=fq_mul(A,c[0]);A=fq_add(A,curveB);return fq_eq(B,A) def pairing(Q:list,P:list)->list: assert curve_is_on_curve(P),f"P is not on the curve.";assert twist_is_on_curve(Q),f"Q is not on the curve." if curve_is_infinity(P)or twist_is_infinity(Q):return fq12_one() A=miller(Q,P);return A def verify(inputs:list,proof:dict)->int: D=inputs;B=proof;E=vk['IC'];assert len(D)+1==len(E),'verifier-bad-input';F=E[0] for A in range(len(D)):assert D[A]<curve_order,'verifier-gte-snark-scalar-field';F=curve_add(F,curve_mul(E[A+1],D[A])) G=[curve_neg(B['A']),vk['vk_alfa_1'],F,B['C']];H=[(B['B'][0],B['B'][1],B['B'][2],B['B'][3]),vk['vk_beta_2'],vk['vk_gamma_2'],vk['vk_delta_2']];C=fq12_one() for A in range(4): if twist_is_infinity(H[A])or curve_is_infinity(G[A]):continue C=fq12_mul(C,pairing(H[A],G[A])) C=final_exponentiation(C) if not fq12_is_one(C):return 1 return 0 @export def verify_proof(a:list,b:list,c:list,inputs:list)->bool: B=inputs;A={};A['A']=int(a[0]),int(a[1]),int(a[2]),1;A['B']=FQ2([int(b[0][1]),int(b[0][0])]),FQ2([int(b[1][1]),int(b[1][0])]),FQ2([int(b[2][1]),int(b[2][0])]),fq2_one();A['C']=int(c[0]),int(c[1]),int(c[2]),1;B=[int(A)for A in B] if verify(B,A)==0:return True else:return False

con_test_contract_length