R1CS to QAP¶
[1]:
%load_ext autoreload
%autoreload 2
Example¶
[2]:
# ref: https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649
from functools import partial
from klefki.zkp.r1cs import R1CS, mul
from klefki.zkp.qap import QAP
from klefki.curves.bns.bn128 import BN128FP as F
from klefki.algebra.rings import PolyRing
import ast
[3]:
# map int to field
ciphers = [1,2,3,4,5,6,7,8,9]
times = 5
@R1CS.r1cs(F)
def f(x, k, c):
y = x + c + k
return y ** 3
@R1CS.r1cs(F, globals())
def mimc(x, k):
for i in range(times):
c = ciphers[i]
x = f(x, k, c)
return x + k
[4]:
f.flatcode
[4]:
[['add', 'Sym::0', 'x', 'c'],
['add', 'y', 'Sym::0', 'k'],
['mul', 'Sym::1', 'y', 'y'],
['mul', '~out', 'Sym::1', 'y']]
[5]:
mimc.flatcode
[5]:
[['set', 'c', 1],
['add', 'Local<Rc(0)>Sym::0', 0, 2],
['add', 'Local<Rc(0)>y', 'Local<Rc(0)>Sym::0', 1],
['mul', 'Local<Rc(0)>Sym::1', 'Local<Rc(0)>y', 'Local<Rc(0)>y'],
['mul', 'x::0', 'Local<Rc(0)>Sym::1', 'Local<Rc(0)>y'],
['set', 'c::1', 2],
['add', 'Local<Rc(1)>Sym::0', 0, 2],
['add', 'Local<Rc(1)>y', 'Local<Rc(1)>Sym::0', 1],
['mul', 'Local<Rc(1)>Sym::1', 'Local<Rc(1)>y', 'Local<Rc(1)>y'],
['mul', 'x::2', 'Local<Rc(1)>Sym::1', 'Local<Rc(1)>y'],
['set', 'c::3', 3],
['add', 'Local<Rc(2)>Sym::0', 0, 2],
['add', 'Local<Rc(2)>y', 'Local<Rc(2)>Sym::0', 1],
['mul', 'Local<Rc(2)>Sym::1', 'Local<Rc(2)>y', 'Local<Rc(2)>y'],
['mul', 'x::4', 'Local<Rc(2)>Sym::1', 'Local<Rc(2)>y'],
['set', 'c::5', 4],
['add', 'Local<Rc(3)>Sym::0', 0, 2],
['add', 'Local<Rc(3)>y', 'Local<Rc(3)>Sym::0', 1],
['mul', 'Local<Rc(3)>Sym::1', 'Local<Rc(3)>y', 'Local<Rc(3)>y'],
['mul', 'x::6', 'Local<Rc(3)>Sym::1', 'Local<Rc(3)>y'],
['set', 'c::7', 5],
['add', 'Local<Rc(4)>Sym::0', 0, 2],
['add', 'Local<Rc(4)>y', 'Local<Rc(4)>Sym::0', 1],
['mul', 'Local<Rc(4)>Sym::1', 'Local<Rc(4)>y', 'Local<Rc(4)>y'],
['mul', 'x::8', 'Local<Rc(4)>Sym::1', 'Local<Rc(4)>y'],
['add', '~out', 'x::8', 'k']]
The format of a flatcode line is:
\[\left[Op, Out, S_a, S_b\right]\]
[24]:
mimc.var
[24]:
['~one',
'x',
'k',
'~out',
'c',
'Local<Rc(0)>Sym::0',
'Local<Rc(0)>y',
'Local<Rc(0)>Sym::1',
'x::0',
'c::1',
'Local<Rc(1)>Sym::0',
'Local<Rc(1)>y',
'Local<Rc(1)>Sym::1',
'x::2',
'c::3',
'Local<Rc(2)>Sym::0',
'Local<Rc(2)>y',
'Local<Rc(2)>Sym::1',
'x::4',
'c::5',
'Local<Rc(3)>Sym::0',
'Local<Rc(3)>y',
'Local<Rc(3)>Sym::1',
'x::6',
'c::7',
'Local<Rc(4)>Sym::0',
'Local<Rc(4)>y',
'Local<Rc(4)>Sym::1',
'x::8']
The format of variable is
\[[One, Input_0, \cdots, Input_n, Output, S_0, S_1, \cdots, S_n]\]
[25]:
assert len(mimc.A[0]) == len(mimc.var)
For each line of flatcodes, we have \(A_i.s \circ B_i.s == C_i.s\)
[26]:
s = mimc.witness(F(42))
s
[26]:
[BN128FP::0x1,
BN128FP::0x2a,
BN128FP::0x0,
BN128FP::0x1b,
BN128FP::0x1,
BN128FP::0x2,
BN128FP::0x3,
BN128FP::0x9,
BN128FP::0x1b,
BN128FP::0x2,
BN128FP::0x2,
BN128FP::0x3,
BN128FP::0x9,
BN128FP::0x1b,
BN128FP::0x3,
BN128FP::0x2,
BN128FP::0x3,
BN128FP::0x9,
BN128FP::0x1b,
BN128FP::0x4,
BN128FP::0x2,
BN128FP::0x3,
BN128FP::0x9,
BN128FP::0x1b,
BN128FP::0x5,
BN128FP::0x2,
BN128FP::0x3,
BN128FP::0x9,
BN128FP::0x1b]
[19]:
sum(mul(mimc.A[0], s)) * sum(mul(mimc.B[0], s)) == sum(mul(mimc.C[0], s))
[19]:
True
Gen QAP¶
[12]:
A, B, C = mimc.r1cs
[13]:
qap = QAP(A, B, C)
[14]:
w = mimc.witness(F(42))
w
[14]:
[BN128FP::0x1,
BN128FP::0x2a,
BN128FP::0x0,
BN128FP::0x1b,
BN128FP::0x1,
BN128FP::0x2,
BN128FP::0x3,
BN128FP::0x9,
BN128FP::0x1b,
BN128FP::0x2,
BN128FP::0x2,
BN128FP::0x3,
BN128FP::0x9,
BN128FP::0x1b,
BN128FP::0x3,
BN128FP::0x2,
BN128FP::0x3,
BN128FP::0x9,
BN128FP::0x1b,
BN128FP::0x4,
BN128FP::0x2,
BN128FP::0x3,
BN128FP::0x9,
BN128FP::0x1b,
BN128FP::0x5,
BN128FP::0x2,
BN128FP::0x3,
BN128FP::0x9,
BN128FP::0x1b]
[15]:
assert qap.verify(*qap.proof(F(112221), w))
[16]:
A, B, C, Z, H = qap.proof(F(112221), w)
PGHR13¶
[17]:
from klefki.curves.barreto_naehrig import bn128
from klefki.algebra.utils import randfield
from operator import add
from functools import reduce
A, B, C, Z = R1CS2QAP(*r1cs, F(42), field=F)
ECG = bn128.ECGBN128
G1 = bn128.ECGBN128.G1
G2 = bn128.ECGBN128.G2
e = bn128.ECGBN128.e
---------------------------------------------------------------------------
ModuleNotFoundError Traceback (most recent call last)
<ipython-input-17-90dc4368c687> in <module>
----> 1 from klefki.curves.barreto_naehrig import bn128
2 from klefki.algebra.utils import randfield
3 from operator import add
4 from functools import reduce
5
ModuleNotFoundError: No module named 'klefki.curves.barreto_naehrig'
[ ]:
class PGHR13:
def __init__(self, F, G):
"""
Setup toxic: t, k_a, k_b and k_c
"""
self.G = G
self.F = F
self.k_a = randfield(F)
self.k_b = randfield(F)
self.k_c = randfield(F)
@property
def toxic(self):
return (self.t, self.k_a, self.k_b, self.k_c)
def setup(self, A, B, C, H, Z):
self.pi_a = reduce(add, [self.G@a for a in A])
self.pi_a_ = self.pi_a @ self.k_a
self.pi_b = reduce(add, [self.G@b for b in B])
self.pi_b_ = self.pi_b @ self.k_b
self.pi_c = reduce(add, [self.G@c for c in C])
self.pi_c_ = self.pi_c @ self.k_c
self.pi_h = self.G @ H
self.pi_z = self.G @ Z
@property
def pi(self):
return (self.pi_a, self.pi_b, self.pi_c)
def check(self):
return G.e(self.pi_a, self.pi_b) / G.e(self.pi_c, self.G) == G.e(self.pi_h, self.pi_z)
[ ]:
[ ]:
[ ]:
