1from hashlib import sha256
  2
  3# Implementation of Sigma protocol & OR proofs
  4
  5
  6def hash_two_points(a, b):
  7    h = sha256((str(a)+str(b)).encode('utf-8'))
  8    return int(h.hexdigest(), 16)
  9
 10def generic_verify(g, X, A, c, z):
 11    return g * int(z) == X * int(c) + A
 12
 13###
 14# Sigma protocol interactive
 15###
 16
 17class Prover_interactive(object):
 18    def __init__(self, F, g):
 19        self.F = F # Z_p
 20        self.g = g # elliptic curve generator
 21
 22    def new_key(self):
 23        self.w = self.F.random_element()
 24        X = self.g * int(self.w)
 25        return X
 26
 27    def new_commitment(self):
 28        self.a = self.F.random_element()
 29        A = self.g * int(self.a)
 30        return A
 31
 32    def gen_proof(self, c):
 33        return int(self.a) + int(c) * int(self.w)
 34
 35class Verifier_interactive(object):
 36    def __init__(self, F, g):
 37        self.F = F
 38        self.g = g
 39
 40    def new_challenge(self, A):
 41        self.A = A
 42        self.c = self.F.random_element()
 43        return self.c
 44    
 45    def verify(self, X, z):
 46        return self.g * int(z) == X * int(self.c) + self.A
 47
 48
 49###
 50# Sigma protocol non-interactive
 51###
 52class Prover(object):
 53    def __init__(self, F, g):
 54        self.F = F # Z_p
 55        self.g = g # elliptic curve generator
 56
 57    def new_key(self):
 58        self.w = self.F.random_element()
 59        X = self.g * int(self.w)
 60        return X
 61
 62    def gen_proof(self, X):
 63        a = self.F.random_element()
 64        A = self.g * int(a)
 65        c = hash_two_points(A, X)
 66        z = int(a) + c * int(self.w)
 67        return A, z
 68
 69
 70class Verifier(object):
 71    def __init__(self, F, g):
 72        self.F = F
 73        self.g = g
 74
 75    def verify(self, X, A, z):
 76        c = hash_two_points(A, X)
 77        return self.g * int(z) == X * c + A
 78
 79class Simulator(object):
 80    def __init__(self, F, g):
 81        self.F = F
 82        self.g = g
 83
 84    def simulate(self, X):
 85        c = self.F.random_element()
 86        z = self.F.random_element()
 87        #  A = g * int(z) + X*(-int(c))
 88        A = g * int(z) - X * int(c)
 89        return A, c, z
 90
 91###
 92# OR proof (with 2 parties)
 93###
 94
 95class ORProver_2parties(object):
 96    def __init__(self, F, g):
 97        self.F = F # Z_p
 98        self.g = g # elliptic curve generator
 99
100    def new_key(self):
101        self.w = self.F.random_element()
102        X = self.g * int(self.w)
103        return X
104
105    def gen_commitments(self, xs):
106        # gen commitment A
107        self.a = self.F.random_element()
108        A = self.g * int(self.a)
109
110        # run the simulator for 1-b
111        sim = Simulator(self.F, self.g)
112        A_1, c_1, z_1 = sim.simulate(xs[1])
113
114        self.A_1 = A_1
115        self.c_1 = c_1
116        self.z_1 = z_1
117
118        return [A, A_1]
119
120    def gen_proof(self, s):
121        # split the challenge s = c xor c_1
122        c = int(s) ^^ int(self.c_1)
123        # compute z
124        z = int(self.a) + int(c) * int(self.w)
125        # note, here the order of the returned elements is always the same, in
126        # a real-world implementation would be shuffled
127        return [c, self.c_1], [z, self.z_1]
128
129class ORVerifier_2parties(object):
130    def __init__(self, F, g):
131        self.F = F
132        self.g = g
133
134    def new_challenge(self, As):
135        self.As = As
136        self.s = self.F.random_element()
137        return self.s
138
139    def verify(self, Xs, cs, zs):
140        assert self.s == int(cs[0]) ^^ int(cs[1])
141        assert self.g * int(zs[0]) == Xs[0] * int(cs[0]) + self.As[0]
142        assert self.g * int(zs[1]) == Xs[1] * int(cs[1]) + self.As[1]
143
144###
145# OR proof (with n parties)
146###
147
148class ORProver(object):
149    def __init__(self, F, g):
150        self.F = F # Z_p
151        self.g = g # elliptic curve generator
152
153    def new_key(self):
154        self.w = self.F.random_element()
155        X = self.g * int(self.w)
156        return X
157
158    def gen_commitments(self, xs):
159        # gen commitment A
160        self.a = self.F.random_element()
161        A = self.g * int(self.a)
162        self.As = [A]
163
164
165        # run the simulator for the rest of Xs
166        sim = Simulator(self.F, self.g)
167        self.cs = []
168        self.zs = []
169        for i in range(1, len(xs)):
170            A_1, c_1, z_1 = sim.simulate(xs[i])
171            self.As.append(A_1)
172            self.cs.append(c_1)
173            self.zs.append(z_1)
174
175        return self.As
176
177    def gen_proof(self, s):
178        # split the challenge s = c xor c_1 xor c_2 xor ... xor c_n
179        c = int(s)
180        for i in range(len(self.cs)):
181            c = c ^^ int(self.cs[i])
182
183        self.cs.insert(0, c) # add c at the beginning of cs array
184
185        # compute z
186        z = int(self.a) + int(c) * int(self.w)
187        self.zs.insert(0, z) # add z at the beginning of zs array
188
189        # note, here the order of the returned elements is always the same, in
190        # a real-world implementation would be shuffled
191        return self.cs, self.zs
192
193class ORVerifier(object):
194    def __init__(self, F, g):
195        self.F = F
196        self.g = g
197
198    def new_challenge(self, As):
199        self.As = As
200        self.s = self.F.random_element()
201        return self.s
202
203    def verify(self, Xs, cs, zs):
204        # check s == c_0 xor c_1 xor c_2 xor ... xor c_n
205        computed_s = int(cs[0])
206        for i in range(1, len(cs)):
207            computed_s = computed_s ^^ int(cs[i])
208
209        assert self.s == computed_s
210
211        # check g*z == X*c + A (in multiplicative notation would g^z ==X^c * A)
212        for i in range(len(Xs)):
213            assert self.g * int(zs[i]) == Xs[i] * int(cs[i]) + self.As[i]