arnaucube.com/blogo-input/posts/ipa.md
blogo-input/posts/ipa.mdRaw
1# IPA polynomial commitment by hand
2*2023-04-06*
3
4*This post was originally written on July 2022 during the '0xPARC Halo2 learning group', posting it now as it was forgotten in a hackmd.*
5
6## Context
7During this past month (June 13 - July 8, 2022) I've been attending at the [Halo2 Learning Group](https://0xparc.org/blog/halo2-learning-group) that [0xPARC](https://0xparc.org) organized. It has been an amazing experience and I've learned a lot from aweseome people. For the past two weeks, the participants were encouraged to do a project related to the contents of the sessions, after a bit of doubts, I've chosen to do it about the Inner Product Argument used in Halo2 for the polynomial commitments, which is described in the [Halo paper](https://eprint.iacr.org/2019/1021.pdf).
8
9I've used this opportunity to study how IPA works, reading it from the [Halo paper](https://eprint.iacr.org/2019/1021.pdf) but also from the [Bulletproofs paper](https://eprint.iacr.org/2017/1066.pdf) and the good explanations from the [Dalek documentation](https://doc-internal.dalek.rs/bulletproofs/notes/inner_product_proof/index.html) and the [Dankrad Feist article](https://dankradfeist.de/ethereum/2021/07/27/inner-product-arguments.html).
10
11Thanks to [Ye Zhang](https://twitter.com/yezhang1998), [Ying Tong](https://twitter.com/therealyingtong) and [Haichen Shen](https://twitter.com/shenhaichen) for their advise on the papers and resources to study. Also thanks to [David Nevado](https://github.com/davidnevadoc) for the typos found in this post.
12
13## Intro
14
15This article overviews the IPA construction described in the [Halo paper](https://eprint.iacr.org/2019/1021.pdf), by doing a step-by-step example with small numbers, following the style done in the *["PLONK by Hand series"](https://research.metastate.dev/plonk-by-hand-part-1/)* by [Joshua Fitzgerald](https://twitter.com/lopeetall). This post does not cover the amortization technique proposed in the Halo paper.
16
17Together with this by-hand step-by-step example, I've implemented it in Sage and also in Rust using arkworks:
18
19- Sage: https://github.com/arnaucube/math/blob/master/ipa.sage
20- Rust: https://github.com/arnaucube/ipa-rs
21
22Also, if you're looking for other Sage/Python IPA implementations, you can find one in the [Darkfi/research repo](https://github.com/darkrenaissance/darkfi/tree/master/script/research/zk/bltprf) and another one in the [Ethereum/research repo](https://github.com/ethereum/research/tree/master/bulletproofs).
23
24
25This post is divided in 3 parts:
26
271. [IPA overview](#ipa-overview)
282. [IPA by hand](#ipa-by%20hand)
293. [IPA Sage implementation](#now-let%E2%80%99s%20do%20a%20simple%20implementation)
30
31
32## IPA overview
33*This section provides an overview on the IPA scheme, for more details it is recommended to go directly to the earlier mentioned papers and articles.*
34
35The scheme objective is to allow the prover to prove that the polynomial $p(X)$ from the commitment $P$, evaluates to $v$ at $x$, and that $deg(p(X)) \leq d-1$.
36
37<div style="font-size:80%;background:#f9f9f9;padding-left:10px;">
38
39Notation:
40<ul>
41 <li>Scalar mul: $[a]G$, where $a$ is a scalar and $G \in \mathbb{G}$</li>
42 <li>Inner product: $<\overrightarrow{a}, \overrightarrow{b}> = a_0 b_0 + a_1 b_1 + \ldots + a_{n-1} b_{n-1}$</li>
43 <li>Multiscalar mul: $<\overrightarrow{a}, \overrightarrow{G}> = [a_0] G_0 + [a_1] G_1 + \ldots + [a_{n-1}] G_{n-1}$</li>
44</ul>
45
46</div>
47
48We have a transparent setup consisting of a random vector of points $\overrightarrow{G} \in^r \mathbb{G}^d$, and a point $H \in^r \mathbb{G}$.
49
50The prover commits to the polynomial $p(X) = \sum^{d-1}_0 a_i x^i$ by a Pedersen vector commitment
51
52$$P=<\overrightarrow{a}, \overrightarrow{G}> + [r]H$$
53
54where $\overrightarrow{a}$ is the vector of the coefficients of $p(X)$. And sets $v$ such that
55
56$$v=<\overrightarrow{a}, \overrightarrow{b} > = <\overrightarrow{a}, \{1, x, x^2, \ldots, x^{d-1} \} >$$
57We can see that computing $v$ is the equivalent to evaluating $p(X)$ at $x$ ($p(x)=v$).
58
59Both parties know $P$, point $x$ and claimed evaluation $v$. For $U \in^r \mathbb{G}$.
60
61
62Now, for $k$ rounds ($d=2^k$, from $j=k$ to $j=1$):
63
64- Prover sets random blinding factors: $l_j, r_j \in \mathbb{F}_p$
65- Prover computes
66
67 $$L_j = < \overrightarrow{a}_{lo}, \overrightarrow{G}_{hi}> + [l_j] H + [< \overrightarrow{a}_{lo}, \overrightarrow{b}_{hi}>] U\\
68 R_j = < \overrightarrow{a}_{hi}, \overrightarrow{G}_{lo}> + [r_j] H + [< \overrightarrow{a}_{hi}, \overrightarrow{b}_{lo}>] U$$
69- Verifier sends random challenge $u_j$
70- Prover computes the halved vectors for next round:
71
72 $$\overrightarrow{a} \leftarrow \overrightarrow{a}_{hi} \cdot u_j^{-1} + \overrightarrow{a}_{lo} \cdot u_j\\
73 \overrightarrow{b} \leftarrow \overrightarrow{b}_{lo} \cdot u_j^{-1} + \overrightarrow{b}_{hi} \cdot u_j\\
74 \overrightarrow{G} \leftarrow \overrightarrow{G}_{lo} \cdot u_j^{-1} + \overrightarrow{G}_{hi} \cdot u_j$$
75
76After final round, $\overrightarrow{a}, \overrightarrow{b}, \overrightarrow{G}$ are each of length 1.
77
78
79Verifier can compute $G = \overrightarrow{G}_0 = < \overrightarrow{s}, \overrightarrow{G} >$, and $b = \overrightarrow{b}_0 = < \overrightarrow{s}, \overrightarrow{b} >$,
80where $\overrightarrow{s}$ is the binary counting structure:
81
82$$
83s = (u_1^{-1} ~ u_2^{-1} \cdots ~u_k^{-1},\\
84~~~~~~~~~u_1 ~~~ u_2^{-1} ~\cdots ~u_k^{-1},\\
85~~~~~~~~~u_1^{-1} ~~ u_2 ~~\cdots ~u_k^{-1},\\
86~~~~~~~~~~~~~~~~~\vdots\\
87~~~~~~~~~u_1 ~~~~ u_2 ~~\cdots ~u_k)
88$$
89
90Also, the verifier can computes $P'$ as
91
92$$P' = P + [v] U$$
93
94which under the hood is equivalent to $P'= <\overrightarrow{a}, G> + [r]H + [v] U$.
95
96
97Then, Verifier checks:
98
99$$[a]G + [r'] H + [ab] U == P' + \sum_{j=1}^k ( [u_j^2] L_j + [u_j^{-2}] R_j)$$
100
101where the $r' = r + \sum_{j=1}^k (l_j u_j^2 + r_j u_j^{-2})$.
102
103We can see how this match if we unfold it (added colors to provide a bit of intuition on the relation of values):
104
105$$
106\textcolor{brown}{[a]G} + \textcolor{cyan}{[r'] H} + \textcolor{magenta}{[ab] U}
107==
108\textcolor{blue}{P'} + \sum_{j=1}^k ( \textcolor{violet}{[u_j^2] L_j} + \textcolor{orange}{[u_j^{-2}] R_j})
109$$
110
111$$
112LHS = \textcolor{brown}{[a]G} + \textcolor{cyan}{[r'] H} + \textcolor{magenta}{[ab] U}\\
113 = \textcolor{brown}{< \overrightarrow{a}, \overrightarrow{G} >}\\
114+ \textcolor{cyan}{[r + \sum_{j=1}^k (l_j \cdot u_j^2 + r_j u_j^{-2})] \cdot H}\\
115+ \textcolor{magenta}{< \overrightarrow{a}, \overrightarrow{b} > U}
116$$
117
118
119$$
120RHS = \textcolor{blue}{P'} + \sum_{j=1}^k ( \textcolor{violet}{[u_j^2] L_j} + \textcolor{orange}{[u_j^{-2}] R_j})\\
121= \textcolor{blue}{< \overrightarrow{a}, \overrightarrow{G}>}\\
122+ \textcolor{blue}{[r] H}\\
123+ \sum_{j=1}^k (
124\textcolor{violet}{[u_j^2] \cdot <\overrightarrow{a}_{lo}, \overrightarrow{G}_{hi}> + [l_j] H + [<\overrightarrow{a}_{lo}, \overrightarrow{b}_{hi}>] U}\\
125\textcolor{orange}{+ [u_j^{-2}] \cdot <\overrightarrow{a}_{hi}, \overrightarrow{G}_{lo}> + [r_j] H + [<\overrightarrow{a}_{hi}, \overrightarrow{b}_{lo}>] U})\\
126 + \textcolor{blue}{[< \overrightarrow{a}, \overrightarrow{b} >] U}\\
127$$
128
129
130<br><br>
131
132In the following diagram we can see a high level overview of the steps in the protocol:
133
134
135<!--
136<pre class="mermaid" style="width:50%;background:#ffffff!important;margin-left:auto;margin-right:auto;">
137%%{init:{'theme':'neutral'}}%%
138
139sequenceDiagram
140participant P as Prover
141participant V as Verifier
142
143P->>P: knows p(X)
144P->>P: commit to p(X), P
145P->>V: P
146V->>V: rand x, U, u
147V->>P: x, U, u
148P->>P: eval v=p(x), gen proof
149P->>V: proof, a, Lⱼ, Rⱼ, v
150V->>V: verify(proof, P, a, x, v, Lⱼ, Rⱼ)
151</pre>
152-->
153
154
155## IPA by hand
156*This section provides a step-by-step example of IPA with small values, following the style done in the ["PLONK by Hand series"](https://research.metastate.dev/plonk-by-hand-part-1/) by [Joshua Fitzgerald](https://twitter.com/lopeetall).*
157
158We will use the Elliptic curve $E(\mathbb{F}_{19}): y^2 = x^3 + 3$.
159
160In the same way that was done in the [_Plonk by hand series_](https://research.metastate.dev/plonk-by-hand-part-1/), let's compute all the points from our generator $G=(1,2) \in E(\mathbb{F}_{19})$. We'll start with $2G$:
161
162
163
164Combining point doubling and inverses for $4G, 6G, 8G, \ldots$, together with [point addition](https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication#Point_addition) we obtain all the points of our curve:
165
166
167As we find out, $14 G = G$, thus $ord(G)_{E(\mathbb{F}_{19})} = 13$, so we will work in $\mathbb{F}_{13}$.
168
169
170Before we start the interaction of the protocol, we need to setup some values. First of all, we need to define the degree of the polynomial with which we want to work, we will use the degree $d=8$ to make manual computations shorter.
171
172We set up the vector $\overrightarrow{G}$ with random points (without known DLOG between them), and also a random point $H$:
173
174
175
176We define our polynomial $p(X)$, to which we want to commit, and let $\overrightarrow{a}$ be its coefficients:
177
178
179Verifier chooses a random challenge $r$:
180
181
182
183Prover commits to $\overrightarrow{a}$:
184
185
186
187We are following the Halo paper, which describes an IPA variant in which the second vector $\overrightarrow{b}$ is fixed for the given choice of $x$, being $\overrightarrow{b} = {1, x, x^2, x^3, \ldots, x^{d-1}}$.
188
189We will use $x=3$, being $\overrightarrow{b}$:
190
191
192Now the prover computes the *inner product* between $\overrightarrow{a}$ and $\overrightarrow{b}$, using
193
194
195Which, since our choose of $\overrightarrow{b}$, it is the equivalent than evaluating $p(X)$ at $x=3$:
196
197
198
199Now the verifier generates the random challenges $u_j \in \mathbb{I}$ and $U \in E$:
200
201
202
203In a non-interactive version of the protocol, these values would be obtained by hashing the transcript ([Fiat-Shamir](https://en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic)).
204
205The prover computes P'
206
207Followed by $k=log(d)$ (3) rounds explained below.
208
209
210#### Rounds
211
212For each round, from $k-1$ to $0$, prover will compute:
213
214$$
215L_j = \langle \overrightarrow{a}_{lo}, \overrightarrow{G}_{hi} \rangle + [l_j] H + [\langle \overrightarrow{a}_{lo}, \overrightarrow{b}_{hi} \rangle] U
216$$
217
218$$
219R_j = \langle \overrightarrow{a}_{hi}, \overrightarrow{G}_{lo} \rangle + [r_j] H + [\langle \overrightarrow{a}_{hi}, \overrightarrow{b}_{lo} \rangle] U
220$$
221
222##### Round j=2:
223So, first we will split $\overrightarrow{a}, \overrightarrow{b}, \overrightarrow{G}$ into their respective left and right halves ($\overrightarrow{v}_{lo}, \overrightarrow{v}_{hi}$):
224
225
226
227Set random blinding factors $l_2, r_2$:
228
229
230And let's calculate $L_2$:
231
232
233And the same with $R_2$:
234
235
236Now, we will compute the new $\overrightarrow{a}, \overrightarrow{b}, \overrightarrow{G}$ to be used in the next round by:
237
238$$
239\overrightarrow{a} \longleftarrow \overrightarrow{a}_{hi} \cdot u_j^{-1} + \overrightarrow{a}_{lo} \cdot u_j\\
240\overrightarrow{b} \longleftarrow \overrightarrow{b}_{lo} \cdot u_j^{-1} + \overrightarrow{b}_{hi} \cdot u_j
241$$
242
243
244
245
246
247
248And similarly for $\overrightarrow{G} \longleftarrow \overrightarrow{G}_{lo} \cdot u_j^{-1} + \overrightarrow{G}_{hi} \cdot u_j$
249
250
251We can see that $\overrightarrow{a}, \overrightarrow{b}, \overrightarrow{G}$ have halved.
252
253##### Round j=1:
254
255From the previous round we have:
256
257
258
259Choose the random blinding factors:
260
261
262
263And now, in the same fashion that we did in the previous round, we compute the $L_1, R_1$:
264
265
266
267
268
269Now, we will compute the new $\overrightarrow{a}, \overrightarrow{b}, \overrightarrow{G}$ to be used in the next round:
270
271
272
273
274
275
276
277##### Round j=0:
278
279
280Set the random blinding factors $l_0, r_0$:
281
282
283Compute $L_0, R_0$:
284
285
286we will compute the new halved $\overrightarrow{a}, \overrightarrow{b}, \overrightarrow{G}$:
287
288
289
290
291
292
293The prover ends having as outputs $a=\overrightarrow{a}_0, ~~b=\overrightarrow{b}_0, ~~G=\overrightarrow{G}_0$, and the random blinding factors $\overrightarrow{l}, \overrightarrow{r}$, together with $\overrightarrow{L}, \overrightarrow{R}$:
294
295
296
297### Verify
298
299
300First, verifier recomputes $b$ and $G$. This can be done in more efficient ways described in the Halo paper, but for the sake of simplicity we will assume that the verifier computes $b$ and $G$ in the *naive way* (which is, doing a similar loop than what the prover did, going from the original $\overrightarrow{b}, \overrightarrow{G}$ halving each round until obtaining $b, G$). In the Sage implementation provided in the next section, we will use the efficient approach, which was also provided in the overview section.
301
302Now, the verifier can compute $P'$ in the same way that the prover did ($P'=P + [v] U$), and from here computes $Q_0 = \sum_{j=1}^k ( [u_j^2] L_j) + P' + \sum_{j=1}^k ([u_j^{-2}] R_j)$:
303
304
305
306As we did previously, for an easier by-hand computation, we can 'translate' the points to multiples of the generator $G$, to operate with them more easily without a computer:
307
308
309
310We need to compute also $r' = \sum_{j=1}^k (l_j \cdot u_j^2) + r + \sum_{j=1}^k (r_j \cdot u_j^{-2})$:
311
312
313
314
315And then compute $Q_1 = [a] G + [r'] H + [ab] U$:
316
317
318
319And by checking that $Q_0 == Q_1$, the verifier finishes the verification.
320
321
322## Now let's do a simple implementation
323We will do a simple implementation in Sage of the protocol.
324
325First of all, we set up our curve:
326```python
327p = 19
328Fp = GF(p)
329E = EllipticCurve(Fp,[0,3])
330g = E(1, 2)
331q = g.order()
332Fq = GF(q)
333```
334
335Now let's create the 'IPA' class:
336```python
337class IPA_halo(object):
338 def __init__(self, F, E, g, d):
339 self.g = g
340 self.F = F
341 self.E = E
342 self.d = d
343
344 self.h = E.random_element()
345 self.gs = random_values(E, d)
346 self.hs = random_values(E, d)
347
348
349def random_values(G, d):
350 r = [None] * d
351 for i in range(d):
352 r[i] = G.random_element()
353 return r
354```
355
356Now we can generate all the elliptic curve points in a similar way that when we computed them by-hand in the previous section:
357```python
358print("\nlet's generate all the points:")
359P = g+g
360print("P_0:", g)
361i=1
362while P!=g:
363 print("P_%d:" % i, P)
364 P = P + P
365 i += 1
366print("P_%d:" % (i+1), E(0), "(point at infinity)")
367```
368
369Alternatively we can use Sage's methods:
370```python
371# alternatively:
372print("points", E.points())
373print("number of points", len(E.points()))
374```
375
376Now, the Prover will set the polynomial $p(X)$ and the Verifier would set $x$:
377
378```python
379print("\ndefine p(X) = 1 + 2x + 3x² + 4x³ + 5x⁴ + 6x⁵ + 7x⁶ + 8x⁷")
380a = [ipa.F(1), ipa.F(2), ipa.F(3), ipa.F(4),
381 ipa.F(5), ipa.F(6), ipa.F(7), ipa.F(8)]
382x = ipa.F(3)
383x_powers = powers_of(x, ipa.d) # = b
384```
385
386Prover sets the blinding factor $r$:
387```python
388r = int(ipa.F.random_element())
389```
390
391We will implement some utility functions that we'll use later in the rest of the implementation:
392```python
393def inner_product_field(a, b):
394 assert len(a) == len(b)
395 c = 0
396 for i in range(len(a)):
397 c = c + a[i] * b[i]
398
399 return c
400
401def inner_product_point(a, b):
402 assert len(a) == len(b)
403 c = 0
404 for i in range(len(a)):
405 c = c + int(a[i]) * b[i]
406
407 return c
408
409def vec_add(a, b):
410 assert len(a) == len(b)
411 return [x + y for x, y in zip(a, b)]
412
413def vec_mul(a, b):
414 assert len(a) == len(b)
415 return [x * y for x, y in zip(a, b)]
416
417def vec_scalar_mul_field(a, n):
418 r = [None]*len(a)
419 for i in range(len(a)):
420 r[i] = a[i]*n
421 return r
422
423def vec_scalar_mul_point(a, n):
424 r = [None]*len(a)
425 for i in range(len(a)):
426 r[i] = a[i]*int(n)
427 return r
428```
429
430And we will implement in the `IPA` class the methods for committing and evaluating:
431
432```python
433class IPA_halo:
434 # [...]
435 def commit(self, a, r):
436 P = inner_product_point(a, self.gs) + r * self.h
437 return P
438
439 def evaluate(self, a, x_powers):
440 return inner_product_field(a, x_powers)
441```
442
443So now the prover can commit to $a$:
444
445```python
446print("\nProver commits to a:")
447P = ipa.commit(a, r)
448print(" commit: P = <a, G> + r * H = ", P)
449print("Evaluates a at {1 + x + x² + x³ + … + xⁿ⁻¹}:")
450v = ipa.evaluate(a, x_powers)
451print(" v =", v)
452print(" (which is equivalent to evaluating p(X) at x=3)")
453```
454
455Verifier generates random challenges $u_j \in \mathbb{I}$ and $U \in \mathbb{U}$
456```python
457print("\nVerifier generate random challenges {uᵢ} ∈ 𝕀 and U ∈ 𝔾")
458U = ipa.E.random_element()
459k = int(math.log(ipa.d, 2))
460u = [None] * k
461for j in reversed(range(0, k)):
462 u[j] = ipa.F.random_element()
463 while (u[j] == 0): # prevent u[j] from being 0
464 u[j] = ipa.F.random_element()
465print(" U =", U)
466print(" u =", u)
467```
468
469
470Now let's implmenet the `ipa` proof generation method in the `IPA` class:
471
472```python
473def ipa(self, a_, x_powers, u, U): # prove
474 G = self.gs
475 a = a_
476 b = x_powers
477
478 k = int(math.log(self.d, 2))
479 l = [None] * k
480 r = [None] * k
481 L = [None] * k
482 R = [None] * k
483
484 for j in reversed(range(0, k)):
485 m = len(a)/2
486 a_lo = a[:m]
487 a_hi = a[m:]
488 b_lo = b[:m]
489 b_hi = b[m:]
490 G_lo = G[:m]
491 G_hi = G[m:]
492
493 l[j] = self.F.random_element() # random blinding factor
494 r[j] = self.F.random_element() # random blinding factor
495
496 # Lⱼ = <a'ₗₒ, G'ₕᵢ> + [lⱼ] H + [<a'ₗₒ, b'ₕᵢ>] U
497 L[j] = inner_product_point(a_lo, G_hi) + int(l[j]) * self.h + int(inner_product_field(a_lo, b_hi)) * U
498 # Rⱼ = <a'ₕᵢ, G'ₗₒ> + [rⱼ] H + [<a'ₕᵢ, b'ₗₒ>] U
499 R[j] = inner_product_point(a_hi, G_lo) + int(r[j]) * self.h + int(inner_product_field(a_hi, b_lo)) * U
500
501 # use the random challenge uⱼ ∈ 𝕀 generated by the verifier
502 u_ = u[j] # uⱼ
503 u_inv = self.F(u[j])^(-1) # uⱼ⁻¹
504
505 a = vec_add(vec_scalar_mul_field(a_lo, u_), vec_scalar_mul_field(a_hi, u_inv))
506 b = vec_add(vec_scalar_mul_field(b_lo, u_inv), vec_scalar_mul_field(b_hi, u_))
507 G = vec_add(vec_scalar_mul_point(G_lo, u_inv), vec_scalar_mul_point(G_hi, u_))
508
509 assert len(a)==1
510 assert len(b)==1
511 assert len(G)==1
512 # a, b, G have length=1
513 # l, r are random blinding factors
514 # L, R are the "cross-terms" of the inner product
515 return a[0], l, r, L, R
516```
517
518
519Followed by the Inner Product Argument using the `ipa` method that we implemented in the previous step:
520```python
521print("\nProver computes the Inner Product Argument:")
522a_ipa, b_ipa, G_ipa, lj, rj, L, R = ipa.ipa(a, x_powers, u, U)
523print(" a=", a_ipa)
524print(" b=", b_ipa)
525print(" G=", G_ipa)
526print(" l_j=", lj)
527print(" r_j=", rj)
528print(" R=", R)
529print(" L=", L)
530```
531
532
533Now let's implement the verification:
534```python
535def verify(self, P, a, v, x_powers, r, u, U, lj, rj, L, R):
536 # compute P' = P + [v] U
537 P = P + int(v) * U
538
539 s = build_s_from_us(u, self.d)
540 b = inner_product_field(s, x_powers)
541 G = inner_product_point(s, self.gs)
542
543 # synthetic blinding factor
544 # r' = r + ∑ ( lⱼ uⱼ² + rⱼ uⱼ⁻²)
545 r_ = r
546 # Q_0 = P' ⋅ ∑ ( [uⱼ²] Lⱼ + [uⱼ⁻²] Rⱼ)
547 Q_0 = P
548 for j in range(len(u)):
549 u_ = u[j] # uⱼ
550 u_inv = u[j]^(-1) # uⱼ⁻²
551
552 # ∑ ( [uⱼ²] Lⱼ + [uⱼ⁻²] Rⱼ)
553 Q_0 = Q_0 + int(u[j]^2) * L[j] + int(u_inv^2) * R[j]
554
555 r_ = r_ + lj[j] * (u_^2) + rj[j] * (u_inv^2)
556
557 Q_1 = int(a) * G + int(r_) * self.h + int(a * b)*U
558
559 return Q_0 == Q_1
560```
561
562Which now the verifier uses the method to verify the proof:
563```python
564verif = ipa.verify(P, a_ipa, v, x_powers, r, u, U, lj, rj, L, R)
565assert verif == True
566```
567
568Now that we have the implementation of the protocol in Sage, we could replace the elliptic curve by some more 'real' curve to see it work with more realistic values.
569
570## Final note
571As mentioned in the beginning, this post is not intended to provide the full description of the scheme and its proofs, but to provide an overview with a by-hand step-by-step example and a later simple Sage implementation. You can find the [complete Sage implementation here](https://github.com/arnaucube/math/blob/master/ipa.sage). Additionally, here you can find [a Rust implementation using arkworks](https://github.com/arnaucube/ipa-rs).
572
573One thing worth to mention is that IPA proving cost is $\mathcal{O}(n)$, proof size is $\mathcal{O}(log(n))$, and verification cost is $\mathcal{O}(n)$. An interesting technique not covered in this post, is the one presented in the [Halo](https://eprint.iacr.org/2019/1021.pdf) paper, in which the cost of verification is amortized, achieving practical $\mathcal{O}(log(n))$ verification.
574
575IPA is used as polynomial commitment scheme in places like the already mentioned [Halo](https://eprint.iacr.org/2019/1021.pdf) (and [Halo2](https://zcash.github.io/halo2/index.html)), but it can be combined in other schemes such as [Marlin](https://iacr.org/archive/eurocrypt2020/12105185/12105185.pdf).
576
577I'm still amazed by the existence of all the 'magic' of the polynomial commitments, and how they can be combined with polyomial IOPs to achieve practical SNARKs.
578
579
580<style>
581p > img{
582 max-width: 70%!important;
583 display: block;
584 margin-left: auto;
585 margin-right: auto;
586}
587</style>