math/sigma.sage
sigma.sageRaw
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:
18 def __init__(self, F, g):
19 self.F = F # Z_q
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:
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:
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:
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:
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:
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:
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:
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:
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]
214
215
216
217# Tests
218import unittest, operator
219
220# ethereum elliptic curve
221p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
222a = 0
223b = 7
224F = GF(p)
225E = EllipticCurve(F, [a,b])
226GX = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
227GY = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
228g = E(GX,GY)
229n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
230h = 1
231q = g.order()
232assert is_prime(p)
233assert is_prime(q)
234
235class TestSigmaProtocol(unittest.TestCase):
236 def test_interactive(self):
237 alice = Prover_interactive(F, g)
238
239 # Alice generates witness w & statement X
240 X = alice.new_key()
241 assert X == alice.g * int(alice.w)
242
243 # Alice generates the commitment A
244 A = alice.new_commitment()
245 assert A == alice.g * int(alice.a)
246
247 # Bob generates the challenge (and stores A)
248 bob = Verifier_interactive(F, g)
249 c = bob.new_challenge(A)
250
251 # Alice generates the proof
252 z = alice.gen_proof(c)
253
254 # Bob verifies the proof
255 assert bob.verify(X, z)
256
257 # check with the generic_verify function
258 assert generic_verify(g, X, A, c, z)
259
260 def test_non_interactive(self):
261 alice = Prover(F, g)
262
263 # Alice generates witness w & statement X
264 X = alice.new_key()
265 assert X == alice.g * int(alice.w)
266
267 # Alice generates the proof
268 A, z = alice.gen_proof(X)
269
270 # Bob generates the challenge
271 bob = Verifier(F, g)
272
273 # Bob verifies the proof
274 assert bob.verify(X, A, z)
275
276 # check with the generic_verify function
277 c = hash_two_points(A, X)
278 assert generic_verify(g, X, A, c, z)
279
280 def test_simulator(self):
281 sim = Simulator(F, g)
282
283 # set a public key X, for which we don't know w
284 unknown_w = 3
285 X = g * unknown_w
286
287 # simulate for X
288 A, c, z = sim.simulate(X)
289
290 # verify the simulated proof
291 assert generic_verify(g, X, A, c, z)
292
293class TestORProof(unittest.TestCase):
294 def test_2_parties(self):
295 # set a public key X, for which we don't know w
296 unknown_w = 3
297 X_1 = g * unknown_w
298
299 alice = ORProver_2parties(F, g)
300
301 # Alice generates key pair
302 X = alice.new_key()
303 Xs = [X, X_1]
304 # Alice generates commitments (internally running the simulator)
305 As = alice.gen_commitments(Xs)
306
307 # Bob generates the challenge (and stores As)
308 bob = ORVerifier_2parties(F, g)
309 s = bob.new_challenge(As)
310
311 # Alice generates the ORproof
312 cs, zs = alice.gen_proof(s)
313
314 # Bob verifies the proofs
315 bob.verify(Xs, cs, zs)
316
317 def test_n_parties(self):
318 # set n public keys X, for which we don't know w
319 Xs = []
320 for i in range(10):
321 X_i = g * i
322 Xs.append(X_i)
323
324 alice = ORProver(F, g)
325
326 # Alice generates key pair
327 X = alice.new_key()
328 Xs.insert(0, X) # add X at the beginning of Xs array
329
330 # Alice generates commitments (internally running the simulator)
331 As = alice.gen_commitments(Xs)
332
333 # Bob generates the challenge (and stores As)
334 bob = ORVerifier(F, g)
335 s = bob.new_challenge(As)
336
337 # Alice generates the ORproof
338 cs, zs = alice.gen_proof(s)
339
340 # Bob verifies the proofs
341 bob.verify(Xs, cs, zs)
342
343if __name__ == '__main__':
344 unittest.main()