math/ipa.sage
ipa.sageRaw
1# This file contains two Inner Product Argument implementations:
2# - Bulletproofs version: https://eprint.iacr.org/2017/1066.pdf
3# - Halo version: https://eprint.iacr.org/2019/1021.pdf
4
5
6
7# IPA_bulletproofs implements the IPA version from the Bulletproofs paper: https://eprint.iacr.org/2017/1066.pdf
8# https://doc-internal.dalek.rs/bulletproofs/notes/inner_product_proof/index.html
9class IPA_bulletproofs:
10 def __init__(self, F, E, g, d):
11 self.g = g
12 self.F = F
13 self.E = E
14 self.d = d
15 # TODO:
16 # Setup:
17 self.h = E.random_element() # TMP
18 self.gs = random_values(E, d)
19 self.hs = random_values(E, d)
20
21 # a: aᵢ ∈ 𝔽 coefficients of p(X)
22 # r: blinding factor
23 def commit(self, a, b):
24 P = inner_product_point(a, self.gs) + inner_product_point(b, self.hs)
25 return P
26
27 def evaluate(self, a, x_powers):
28 return inner_product_field(a, x_powers)
29
30 def ipa(self, a_, b_, u, U):
31 G = self.gs
32 H = self.hs
33 a = a_
34 b = b_
35
36 k = int(math.log(self.d, 2))
37 L = [None] * k
38 R = [None] * k
39
40 for j in reversed(range(0, k)):
41 m = len(a)/2
42 a_lo = a[:m]
43 a_hi = a[m:]
44 b_lo = b[:m]
45 b_hi = b[m:]
46 H_lo = H[:m]
47 H_hi = H[m:]
48 G_lo = G[:m]
49 G_hi = G[m:]
50
51 # Lⱼ = <a'ₗₒ, G'ₕᵢ> + [lⱼ] H + [<a'ₗₒ, b'ₕᵢ>] U
52 L[j] = inner_product_point(a_lo, G_hi) + inner_product_point(b_hi, H_lo) + int(inner_product_field(a_lo, b_hi)) * U
53 # Rⱼ = <a'ₕᵢ, G'ₗₒ> + [rⱼ] H + [<a'ₕᵢ, b'ₗₒ>] U
54 R[j] = inner_product_point(a_hi, G_lo) + inner_product_point(b_lo, H_hi) + int(inner_product_field(a_hi, b_lo)) * U
55
56 # use the random challenge uⱼ ∈ 𝕀 generated by the verifier
57 u_ = u[j] # uⱼ
58 u_inv = u[j]^(-1) # uⱼ⁻¹
59
60 a = vec_add(vec_scalar_mul_field(a_lo, u_), vec_scalar_mul_field(a_hi, u_inv))
61 b = vec_add(vec_scalar_mul_field(b_lo, u_inv), vec_scalar_mul_field(b_hi, u_))
62 G = vec_add(vec_scalar_mul_point(G_lo, u_inv), vec_scalar_mul_point(G_hi, u_))
63 H = vec_add(vec_scalar_mul_point(H_lo, u_), vec_scalar_mul_point(H_hi, u_inv))
64
65 assert len(a)==1
66 assert len(b)==1
67 assert len(G)==1
68 assert len(H)==1
69 # a, b, G have length=1
70 # L, R are the "cross-terms" of the inner product
71 return a[0], b[0], G[0], H[0], L, R
72
73 def verify(self, P, a, v, x_powers, u, U, L, R, b_ipa, G_ipa, H_ipa):
74 b = b_ipa
75 G = G_ipa
76 H = H_ipa
77
78 # Q_0 = P' ⋅ ∑ ( [uⱼ²] Lⱼ + [uⱼ⁻²] Rⱼ)
79 C = P
80 for j in range(len(L)):
81 u_ = u[j] # uⱼ
82 u_inv = u[j]^(-1) # uⱼ⁻²
83
84 # ∑ ( [uⱼ²] Lⱼ + [uⱼ⁻²] Rⱼ)
85 C = C + int(u_^2) * L[j] + int(u_inv^2) * R[j]
86
87 D = int(a) * G + int(b) * H + int(a * b)*U
88
89 return C == D
90
91# IPA_halo implements the modified IPA from the Halo paper: https://eprint.iacr.org/2019/1021.pdf
92class IPA_halo:
93 def __init__(self, F, E, g, d):
94 self.g = g
95 self.F = F
96 self.E = E
97 self.d = d
98
99 self.h = E.random_element() # TMP
100 self.gs = random_values(E, d)
101 self.hs = random_values(E, d)
102 # print(" h=", self.h)
103 # print(" G=", self.gs)
104 # print(" H=", self.hs)
105
106 def commit(self, a, r):
107 P = inner_product_point(a, self.gs) + r * self.h
108 return P
109
110 def evaluate(self, a, x_powers):
111 return inner_product_field(a, x_powers)
112
113 def ipa(self, a_, x_powers, u, U): # prove
114 print(" method ipa():")
115 G = self.gs
116 a = a_
117 b = x_powers
118
119 k = int(math.log(self.d, 2))
120 l = [None] * k
121 r = [None] * k
122 L = [None] * k
123 R = [None] * k
124
125 for j in reversed(range(0, k)):
126 print(" j =", j)
127 print(" len(a) = n =", len(a))
128 print(" m = n/2 =", len(a)/2)
129 m = len(a)/2
130 a_lo = a[:m]
131 a_hi = a[m:]
132 b_lo = b[:m]
133 b_hi = b[m:]
134 G_lo = G[:m]
135 G_hi = G[m:]
136
137 print(" Split into a_lo,hi b_lo,hi, G_lo,hi:")
138 print(" a", a)
139 print(" a_lo", a_lo)
140 print(" a_hi", a_hi)
141 print(" b", b)
142 print(" b_lo", b_lo)
143 print(" b_hi", b_hi)
144 print(" G", G)
145 print(" G_lo", G_lo)
146 print(" G_hi", G_hi)
147
148 l[j] = self.F.random_element() # random blinding factor
149 r[j] = self.F.random_element() # random blinding factor
150 print(" random blinding factors:")
151 print(" l[j]", l[j])
152 print(" r[j]", r[j])
153
154 # Lⱼ = <a'ₗₒ, G'ₕᵢ> + [lⱼ] H + [<a'ₗₒ, b'ₕᵢ>] U
155 L[j] = inner_product_point(a_lo, G_hi) + int(l[j]) * self.h + int(inner_product_field(a_lo, b_hi)) * U
156 # Rⱼ = <a'ₕᵢ, G'ₗₒ> + [rⱼ] H + [<a'ₕᵢ, b'ₗₒ>] U
157 R[j] = inner_product_point(a_hi, G_lo) + int(r[j]) * self.h + int(inner_product_field(a_hi, b_lo)) * U
158
159 print(" Compute Lⱼ = <a'ₗₒ, G'ₕᵢ> + [lⱼ] H + [<a'ₗₒ, b'ₕᵢ>] U")
160 print(" L[j]", L[j])
161 print(" Compute Rⱼ = <a'ₕᵢ, G'ₗₒ> + [rⱼ] H + [<a'ₕᵢ, b'ₗₒ>] U")
162 print(" R[j]", R[j])
163
164 # use the random challenge uⱼ ∈ 𝕀 generated by the verifier
165 u_ = u[j] # uⱼ
166 u_inv = self.F(u[j])^(-1) # uⱼ⁻¹
167 print(" u_j", u_)
168 print(" u_j^-1", u_inv)
169
170 a = vec_add(vec_scalar_mul_field(a_lo, u_), vec_scalar_mul_field(a_hi, u_inv))
171 b = vec_add(vec_scalar_mul_field(b_lo, u_inv), vec_scalar_mul_field(b_hi, u_))
172 G = vec_add(vec_scalar_mul_point(G_lo, u_inv), vec_scalar_mul_point(G_hi, u_))
173 print(" new a, b, G")
174 print(" a =", a)
175 print(" b =", b)
176 print(" G =", G)
177
178 assert len(a)==1
179 assert len(b)==1
180 assert len(G)==1
181 # a, b, G have length=1
182 # l, r are random blinding factors
183 # L, R are the "cross-terms" of the inner product
184 return a[0], l, r, L, R
185
186 def verify(self, P, a, v, x_powers, r, u, U, lj, rj, L, R):
187 print("method verify()")
188
189 # compute P' = P + [v] U
190 P = P + int(v) * U
191
192 s = build_s_from_us(u, self.d)
193 b = inner_product_field(s, x_powers)
194 G = inner_product_point(s, self.gs)
195
196 # synthetic blinding factor
197 # r' = r + ∑ ( lⱼ uⱼ² + rⱼ uⱼ⁻²)
198 print(" synthetic blinding factor r' = r + ∑ ( lⱼ uⱼ² + rⱼ uⱼ⁻²)")
199 r_ = r
200 print(" r_ =", r_)
201 # Q_0 = P' ⋅ ∑ ( [uⱼ²] Lⱼ + [uⱼ⁻²] Rⱼ)
202 print(" Q_0 = P' ⋅ ∑ ( [uⱼ²] Lⱼ + [uⱼ⁻²] Rⱼ)")
203 Q_0 = P
204 print(" Q_0 =", Q_0)
205 for j in range(len(u)):
206 print(" j =", j)
207 u_ = u[j] # uⱼ
208 u_inv = u[j]^(-1) # uⱼ⁻²
209
210 # ∑ ( [uⱼ²] Lⱼ + [uⱼ⁻²] Rⱼ)
211 Q_0 = Q_0 + int(u[j]^2) * L[j] + int(u_inv^2) * R[j]
212 print(" Q_0 =", Q_0)
213
214 r_ = r_ + lj[j] * (u_^2) + rj[j] * (u_inv^2)
215 print(" r_ =", r_)
216
217 Q_1 = int(a) * G + int(r_) * self.h + int(a * b)*U
218 print(" Q_1", Q_1)
219 # Q_1_ = int(a) * (G + int(b)*U) + int(r_) * self.h
220
221 return Q_0 == Q_1
222
223
224# s = (
225# u₁⁻¹ u₂⁻¹ … uₖ⁻¹,
226# u₁ u₂⁻¹ … uₖ⁻¹,
227# u₁⁻¹ u₂ … uₖ⁻¹,
228# u₁ u₂ … uₖ⁻¹,
229# ⋮ ⋮ ⋮
230# u₁ u₂ … uₖ
231# )
232def build_s_from_us(u, d):
233 k = int(math.log(d, 2))
234 s = [1]*d
235 t = d
236 for j in reversed(range(k)):
237 t = t/2
238 c = 0
239 for i in range(d):
240 if c<t:
241 s[i] = s[i] * u[j]^(-1)
242 else:
243 s[i] = s[i] * u[j]
244 c = c+1
245 if c>=t*2:
246 c=0
247
248 return s
249
250
251
252
253def powers_of(g, d):
254 r = [None] * d
255 for i in range(d):
256 r[i] = g^i
257 return r
258
259
260def multiples_of(g, d):
261 r = [None] * d
262 for i in range(d):
263 r[i] = g*i
264 return r
265
266def random_values(G, d):
267 r = [None] * d
268 for i in range(d):
269 r[i] = G.random_element()
270 return r
271
272def inner_product_field(a, b):
273 assert len(a) == len(b)
274 c = 0
275 for i in range(len(a)):
276 c = c + a[i] * b[i]
277
278 return c
279
280def inner_product_point(a, b):
281 assert len(a) == len(b)
282 c = 0
283 for i in range(len(a)):
284 c = c + int(a[i]) * b[i]
285
286 return c
287
288def vec_add(a, b):
289 assert len(a) == len(b)
290 return [x + y for x, y in zip(a, b)]
291
292def vec_mul(a, b):
293 assert len(a) == len(b)
294 return [x * y for x, y in zip(a, b)]
295
296def vec_scalar_mul_field(a, n):
297 r = [None]*len(a)
298 for i in range(len(a)):
299 r[i] = a[i]*n
300 return r
301
302def vec_scalar_mul_point(a, n):
303 r = [None]*len(a)
304 for i in range(len(a)):
305 r[i] = a[i]*int(n)
306 return r
307
308
309# Tests
310import unittest, operator
311
312# Ethereum elliptic curve
313p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
314a = 0
315b = 7
316Fp = GF(p)
317E = EllipticCurve(Fp, [a,b])
318GX = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
319GY = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
320g = E(GX,GY)
321n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
322h = 1
323q = g.order()
324Fq = GF(q)
325
326# simpler curve values
327# p = 19
328# Fp = GF(p)
329# E = EllipticCurve(Fp,[0,3])
330# g = E(1, 2)
331# q = g.order()
332# Fq = GF(q)
333
334print(E)
335print(Fq)
336assert is_prime(p)
337assert is_prime(q)
338assert g * q == 0
339
340class TestUtils(unittest.TestCase):
341 def test_vecs(self):
342 a = [1, 2, 3, 4, 5]
343 b = [1, 2, 3, 4, 5]
344
345 c = vec_scalar_mul_field(a, 10)
346 assert c == [10, 20, 30, 40, 50]
347
348 c = inner_product_field(a, b)
349 assert c == 55
350
351 # check that <a, b> with b = (1, x, x^2, ..., x^{d-1}) is the same
352 # than evaluating p(x) with coefficients a_i, at x
353 a = [Fq(1), Fq(2), Fq(3), Fq(4), Fq(5), Fq(6), Fq(7), Fq(8)]
354 z = Fq(3)
355 b = powers_of(z, 8)
356 c = inner_product_field(a, b)
357
358 x = PolynomialRing(Fq, 'x').gen()
359 px = 1 + 2*x + 3*x^2 + 4*x^3 + 5*x^4 + 6*x^5 + 7*x^6 + 8*x^7
360 assert c == px(x=z)
361
362
363class TestIPA_bulletproofs(unittest.TestCase):
364 def test_inner_product_argument(self):
365 d = 8
366 ipa = IPA_bulletproofs(Fq, E, g, d)
367
368 # prover
369 # p(x) = 1 + 2x + 3x² + 4x³ + 5x⁴ + 6x⁵ + 7x⁶ + 8x⁷
370 a = [ipa.F(1), ipa.F(2), ipa.F(3), ipa.F(4), ipa.F(5), ipa.F(6), ipa.F(7), ipa.F(8)]
371 x = ipa.F(3)
372 b = powers_of(x, ipa.d) # = b
373
374 # prover
375 P = ipa.commit(a, b)
376 print("commit", P)
377 v = ipa.evaluate(a, b)
378 print("v", v)
379
380 # verifier generate random challenges {uᵢ} ∈ 𝕀 and U ∈ 𝔾
381 U = ipa.E.random_element()
382 k = int(math.log(d, 2))
383 u = [None] * k
384 for j in reversed(range(0, k)):
385 u[j] = ipa.F.random_element()
386 while (u[j] == 0): # prevent u[j] from being 0
387 u[j] = ipa.F.random_element()
388
389 P = P + int(inner_product_field(a, b)) * U
390
391 # prover
392 a_ipa, b_ipa, G_ipa, H_ipa, L, R = ipa.ipa(a, b, u, U)
393
394 # verifier
395 print("P", P)
396 print("a_ipa", a_ipa)
397 verif = ipa.verify(P, a_ipa, v, b, u, U, L, R, b_ipa, G_ipa, H_ipa)
398 print("Verification:", verif)
399 assert verif == True
400
401
402class TestIPA_halo(unittest.TestCase):
403 def test_homomorphic_property(self):
404 ipa = IPA_halo(Fq, E, g, 5)
405
406 a = [1, 2, 3, 4, 5]
407 b = [1, 2, 3, 4, 5]
408 c = vec_add(a, b)
409 assert c == [2,4,6,8,10]
410
411 r = int(ipa.F.random_element())
412 s = int(ipa.F.random_element())
413 vc_a = ipa.commit(a, r)
414 vc_b = ipa.commit(b, s)
415
416 # com(a, r) + com(b, s) == com(a+b, r+s)
417 expected_vc_c = ipa.commit(vec_add(a, b), r+s)
418 vc_c = vc_a + vc_b
419 assert vc_c == expected_vc_c
420
421 def test_inner_product_argument(self):
422 d = 8
423 ipa = IPA_halo(Fq, E, g, d)
424
425 # prover
426 # p(x) = 1 + 2x + 3x² + 4x³ + 5x⁴ + 6x⁵ + 7x⁶ + 8x⁷
427 a = [ipa.F(1), ipa.F(2), ipa.F(3), ipa.F(4), ipa.F(5), ipa.F(6), ipa.F(7), ipa.F(8)]
428 x = ipa.F(3)
429 x_powers = powers_of(x, ipa.d) # = b
430
431 # blinding factor
432 r = int(ipa.F.random_element())
433
434 # prover
435 P = ipa.commit(a, r)
436 print("commit", P)
437 v = ipa.evaluate(a, x_powers)
438 print("v", v)
439
440 # verifier generate random challenges {uᵢ} ∈ 𝕀 and U ∈ 𝔾
441 # This might be obtained from the hash of the transcript
442 # (Fiat-Shamir heuristic for non-interactive version)
443 U = ipa.E.random_element()
444 k = int(math.log(ipa.d, 2))
445 u = [None] * k
446 for j in reversed(range(0, k)):
447 u[j] = ipa.F.random_element()
448 while (u[j] == 0): # prevent u[j] from being 0
449 u[j] = ipa.F.random_element()
450
451 # prover
452 a_ipa, lj, rj, L, R = ipa.ipa(a, x_powers, u, U)
453
454 # verifier
455 print("P", P)
456 print("a_ipa", a_ipa)
457 print("\n Verify:")
458 verif = ipa.verify(P, a_ipa, v, x_powers, r, u, U, lj, rj, L, R)
459 assert verif == True
460
461
462if __name__ == '__main__':
463 unittest.main()