arnaucube.com/blog/ipa.html
blog/ipa.htmlRaw
1<!DOCTYPE html>
2<html lang="en">
3
4 <head>
5 <meta name="description" content="This post overviews the IPA polynomial commitment described in the Halo paper, first by providing an overview on the protocol, then by doing a step-by-step example with small values, following the style done in the 'Plonk by hand series' from Joshua Fitzgerald, and later by providing a Sage implementation of the protocol." />
6 <meta charset="utf-8">
7 <title> IPA polynomial commitment by hand - arnaucube - blog</title>
8 <meta name="title" content=" IPA polynomial commitment by hand - arnaucube - blog">
9 <meta name="description" content="This post overviews the IPA polynomial commitment described in the Halo paper, first by providing an overview on the protocol, then by doing a step-by-step example with small values, following the style done in the 'Plonk by hand series' from Joshua Fitzgerald, and later by providing a Sage implementation of the protocol.">
10
11 <meta property="og:title" content=" IPA polynomial commitment by hand - arnaucube - blog" />
12 <meta property="og:description" content="This post overviews the IPA polynomial commitment described in the Halo paper, first by providing an overview on the protocol, then by doing a step-by-step example with small values, following the style done in the 'Plonk by hand series' from Joshua Fitzgerald, and later by providing a Sage implementation of the protocol." />
13 <meta property="og:url" content="https://arnaucube.com/blog/ipa.html" />
14 <meta property="og:type" content="article" />
15 <meta property="og:image" content="https://arnaucube.com/blog/" />
16 <meta name="twitter:title" content=" IPA polynomial commitment by hand - arnaucube - blog">
17 <meta name="twitter:description" content="This post overviews the IPA polynomial commitment described in the Halo paper, first by providing an overview on the protocol, then by doing a step-by-step example with small values, following the style done in the 'Plonk by hand series' from Joshua Fitzgerald, and later by providing a Sage implementation of the protocol.">
18 <meta name="twitter:image" content="https://arnaucube.com/blog/">
19 <meta name="twitter:card" content="summary_large_image">
20 <meta name="author" content="arnaucube">
21
22 <link rel="icon" type="image/png" href="img/logoArnauCubeFavicon.png">
23
24 <meta name="viewport" content="width=device-width, initial-scale=1">
25
26 <link href="css/bootstrap.min.css" rel="stylesheet">
27 <link rel="stylesheet" href="css/style.css">
28
29 <!-- highlightjs -->
30 <!-- <link rel="stylesheet" href="js/highlightjs/atom-one-dark.css"> -->
31 <link rel="stylesheet" href="js/highlightjs/atom-one-light.css">
32 <!-- <link rel="stylesheet" href="js/highlightjs/gruvbox-dark.css"> -->
33 <script src="js/highlightjs/highlight.pack.js"></script>
34
35 <!-- katex -->
36 <link rel="stylesheet" href="js/katex/katex.min.css">
37 </head>
38
39 <body>
40
41 <!-- o_gradient_background" -->
42 <nav id="mainNav" class="navbar navbar-default navbar-fixed-top"
43 style="height:50px;font-size:100%;">
44 <div class="container">
45 <div style="float:left;">
46 <a href="/blog" style="color:#000;display:inline-block;">blog</a>
47 <span style="margin-right:20px; margin-left:20px;">|</span>
48 <a href="/blog/notes.html" style="font-size:90%;color:#000;display:inline-block;">notes</a>
49 </div>
50 <div style="float:right;">
51 <a href="/" style="color:#000;display:inline-block;margin-right:10px;">arnaucube.com</a>
52 <div class="onoffswitch" style="margin-left:0px;display:inline-block;" title="change theme">
53 <input onclick="switchTheme()" type="checkbox" name="onoffswitch" class="onoffswitch-checkbox"
54 id="themeSwitcher">
55 <label class="onoffswitch-label" for="themeSwitcher"></label>
56 </div>
57 </div>
58 </div>
59 <!-- <img style="height:5px; width:100%; margin-top:8px;" src="img/gradient-line.jpg" /> -->
60 </nav>
61
62
63
64 <div class="container" style="margin-top:0px;max-width:800px;">
65 <h1>IPA polynomial commitment by hand</h1>
66
67<p><em>2023-04-06</em></p>
68
69<p><em>This post was originally written on July 2022 during the ‘0xPARC Halo2 learning group’, posting it now as it was forgotten in a hackmd.</em></p>
70
71<h2>Context</h2>
72
73<p>During this past month (June 13 - July 8, 2022) I’ve been attending at the <a href="https://0xparc.org/blog/halo2-learning-group">Halo2 Learning Group</a> that <a href="https://0xparc.org">0xPARC</a> 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 <a href="https://eprint.iacr.org/2019/1021.pdf">Halo paper</a>.</p>
74
75<p>I’ve used this opportunity to study how IPA works, reading it from the <a href="https://eprint.iacr.org/2019/1021.pdf">Halo paper</a> but also from the <a href="https://eprint.iacr.org/2017/1066.pdf">Bulletproofs paper</a> and the good explanations from the <a href="https://doc-internal.dalek.rs/bulletproofs/notes/inner_product_proof/index.html">Dalek documentation</a> and the <a href="https://dankradfeist.de/ethereum/2021/07/27/inner-product-arguments.html">Dankrad Feist article</a>.</p>
76
77<p>Thanks to <a href="https://twitter.com/yezhang1998">Ye Zhang</a>, <a href="https://twitter.com/therealyingtong">Ying Tong</a> and <a href="https://twitter.com/shenhaichen">Haichen Shen</a> for their advise on the papers and resources to study. Also thanks to <a href="https://github.com/davidnevadoc">David Nevado</a> for the typos found in this post.</p>
78
79<h2>Intro</h2>
80
81<p>This article overviews the IPA construction described in the <a href="https://eprint.iacr.org/2019/1021.pdf">Halo paper</a>, by doing a step-by-step example with small numbers, following the style done in the <em><a href="https://research.metastate.dev/plonk-by-hand-part-1/">“PLONK by Hand series”</a></em> by <a href="https://twitter.com/lopeetall">Joshua Fitzgerald</a>. This post does not cover the amortization technique proposed in the Halo paper.</p>
82
83<p>Together with this by-hand step-by-step example, I’ve implemented it in Sage and also in Rust using arkworks:</p>
84
85<ul>
86<li>Sage: <a href="https://github.com/arnaucube/math/blob/master/ipa.sage">https://github.com/arnaucube/math/blob/master/ipa.sage</a></li>
87<li>Rust: <a href="https://github.com/arnaucube/ipa-rs">https://github.com/arnaucube/ipa-rs</a></li>
88</ul>
89
90<p>Also, if you’re looking for other Sage/Python IPA implementations, you can find one in the <a href="https://github.com/darkrenaissance/darkfi/tree/master/script/research/zk/bltprf">Darkfi/research repo</a> and another one in the <a href="https://github.com/ethereum/research/tree/master/bulletproofs">Ethereum/research repo</a>.</p>
91
92<p>This post is divided in 3 parts:</p>
93
94<ol>
95<li><a href="#ipa-overview">IPA overview</a></li>
96<li><a href="#ipa-by%20hand">IPA by hand</a></li>
97<li><a href="#now-let%E2%80%99s%20do%20a%20simple%20implementation">IPA Sage implementation</a></li>
98</ol>
99
100<h2>IPA overview</h2>
101
102<p><em>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.</em></p>
103
104<p>The scheme objective is to allow the prover to prove that the polynomial <span class="math inline">\(p(X)\)</span> from the commitment <span class="math inline">\(P\)</span>, evaluates to <span class="math inline">\(v\)</span> at <span class="math inline">\(x\)</span>, and that <span class="math inline">\(deg(p(X)) \leq d-1\)</span>.</p>
105
106<div style="font-size:80%;background:#f9f9f9;padding-left:10px;">
107
108Notation:
109<ul>
110 <li>Scalar mul: $[a]G$, where $a$ is a scalar and $G \in \mathbb{G}$</li>
111 <li>Inner product: $<\overrightarrow{a}, \overrightarrow{b}> = a_0 b_0 + a_1 b_1 + \ldots + a_{n-1} b_{n-1}$</li>
112 <li>Multiscalar mul: $<\overrightarrow{a}, \overrightarrow{G}> = [a_0] G_0 + [a_1] G_1 + \ldots + [a_{n-1}] G_{n-1}$</li>
113</ul>
114
115</div>
116
117<p>We have a transparent setup consisting of a random vector of points <span class="math inline">\(\overrightarrow{G} \in^r \mathbb{G}^d\)</span>, and a point <span class="math inline">\(H \in^r \mathbb{G}\)</span>.</p>
118
119<p>The prover commits to the polynomial <span class="math inline">\(p(X) = \sum^{d-1}_0 a_i x^i\)</span> by a Pedersen vector commitment</p>
120<p><span class="math display">\[P=<\overrightarrow{a}, \overrightarrow{G}> + [r]H\]</span></p><p>where <span class="math inline">\(\overrightarrow{a}\)</span> is the vector of the coefficients of <span class="math inline">\(p(X)\)</span>. And sets <span class="math inline">\(v\)</span> such that</p>
121<p><span class="math display">\[v=<\overrightarrow{a}, \overrightarrow{b} > = <\overrightarrow{a}, \{1, x, x^2, \ldots, x^{d-1} \} >\]</span></p><p>We can see that computing <span class="math inline">\(v\)</span> is the equivalent to evaluating <span class="math inline">\(p(X)\)</span> at <span class="math inline">\(x\)</span> (<span class="math inline">\(p(x)=v\)</span>).</p>
122
123<p>Both parties know <span class="math inline">\(P\)</span>, point <span class="math inline">\(x\)</span> and claimed evaluation <span class="math inline">\(v\)</span>. For <span class="math inline">\(U \in^r \mathbb{G}\)</span>.</p>
124
125<p>Now, for <span class="math inline">\(k\)</span> rounds (<span class="math inline">\(d=2^k\)</span>, from <span class="math inline">\(j=k\)</span> to <span class="math inline">\(j=1\)</span>):</p>
126
127<ul>
128<li><p>Prover sets random blinding factors: <span class="math inline">\(l_j, r_j \in \mathbb{F}_p\)</span></p></li>
129
130<li><p>Prover computes</p>
131<p><span class="math display">\[L_j = < \overrightarrow{a}_{lo}, \overrightarrow{G}_{hi}> + [l_j] H + [< \overrightarrow{a}_{lo}, \overrightarrow{b}_{hi}>] U\\
132R_j = < \overrightarrow{a}_{hi}, \overrightarrow{G}_{lo}> + [r_j] H + [< \overrightarrow{a}_{hi}, \overrightarrow{b}_{lo}>] U\]</span></p></li>
133
134<li><p>Verifier sends random challenge <span class="math inline">\(u_j\)</span></p></li>
135
136<li><p>Prover computes the halved vectors for next round:</p>
137<p><span class="math display">\[\overrightarrow{a} \leftarrow \overrightarrow{a}_{hi} \cdot u_j^{-1} + \overrightarrow{a}_{lo} \cdot u_j\\
138\overrightarrow{b} \leftarrow \overrightarrow{b}_{lo} \cdot u_j^{-1} + \overrightarrow{b}_{hi} \cdot u_j\\
139\overrightarrow{G} \leftarrow \overrightarrow{G}_{lo} \cdot u_j^{-1} + \overrightarrow{G}_{hi} \cdot u_j\]</span></p></li>
140</ul>
141
142<p>After final round, <span class="math inline">\(\overrightarrow{a}, \overrightarrow{b}, \overrightarrow{G}\)</span> are each of length 1.</p>
143
144<p>Verifier can compute <span class="math inline">\(G = \overrightarrow{G}_0 = < \overrightarrow{s}, \overrightarrow{G} >\)</span>, and <span class="math inline">\(b = \overrightarrow{b}_0 = < \overrightarrow{s}, \overrightarrow{b} >\)</span>,
145where <span class="math inline">\(\overrightarrow{s}\)</span> is the binary counting structure:</p>
146<p><span class="math display">\[
147s = (u_1^{-1} ~ u_2^{-1} \cdots ~u_k^{-1},\\
148~~~~~~~~~u_1 ~~~ u_2^{-1} ~\cdots ~u_k^{-1},\\
149~~~~~~~~~u_1^{-1} ~~ u_2 ~~\cdots ~u_k^{-1},\\
150~~~~~~~~~~~~~~~~~\vdots\\
151~~~~~~~~~u_1 ~~~~ u_2 ~~\cdots ~u_k)
152\]</span></p><p>Also, the verifier can computes <span class="math inline">\(P'\)</span> as</p>
153<p><span class="math display">\[P' = P + [v] U\]</span></p><p>which under the hood is equivalent to <span class="math inline">\(P'= <\overrightarrow{a}, G> + [r]H + [v] U\)</span>.</p>
154
155<p>Then, Verifier checks:</p>
156<p><span class="math display">\[[a]G + [r'] H + [ab] U == P' + \sum_{j=1}^k ( [u_j^2] L_j + [u_j^{-2}] R_j)\]</span></p><p>where the <span class="math inline">\(r' = r + \sum_{j=1}^k (l_j u_j^2 + r_j u_j^{-2})\)</span>.</p>
157
158<p>We can see how this match if we unfold it (added colors to provide a bit of intuition on the relation of values):</p>
159<p><span class="math display">\[
160\textcolor{brown}{[a]G} + \textcolor{cyan}{[r'] H} + \textcolor{magenta}{[ab] U}
161==
162\textcolor{blue}{P'} + \sum_{j=1}^k ( \textcolor{violet}{[u_j^2] L_j} + \textcolor{orange}{[u_j^{-2}] R_j})
163\]</span></p><p><span class="math display">\[
164LHS = \textcolor{brown}{[a]G} + \textcolor{cyan}{[r'] H} + \textcolor{magenta}{[ab] U}\\
165 = \textcolor{brown}{< \overrightarrow{a}, \overrightarrow{G} >}\\
166+ \textcolor{cyan}{[r + \sum_{j=1}^k (l_j \cdot u_j^2 + r_j u_j^{-2})] \cdot H}\\
167+ \textcolor{magenta}{< \overrightarrow{a}, \overrightarrow{b} > U}
168\]</span></p><p><span class="math display">\[
169RHS = \textcolor{blue}{P'} + \sum_{j=1}^k ( \textcolor{violet}{[u_j^2] L_j} + \textcolor{orange}{[u_j^{-2}] R_j})\\
170= \textcolor{blue}{< \overrightarrow{a}, \overrightarrow{G}>}\\
171+ \textcolor{blue}{[r] H}\\
172+ \sum_{j=1}^k (
173\textcolor{violet}{[u_j^2] \cdot <\overrightarrow{a}_{lo}, \overrightarrow{G}_{hi}> + [l_j] H + [<\overrightarrow{a}_{lo}, \overrightarrow{b}_{hi}>] U}\\
174\textcolor{orange}{+ [u_j^{-2}] \cdot <\overrightarrow{a}_{hi}, \overrightarrow{G}_{lo}> + [r_j] H + [<\overrightarrow{a}_{hi}, \overrightarrow{b}_{lo}>] U})\\
175 + \textcolor{blue}{[< \overrightarrow{a}, \overrightarrow{b} >] U}\\
176\]</span></p><p><br><br></p>
177
178<p>In the following diagram we can see a high level overview of the steps in the protocol:
179<img src="img/posts/ipa/sequence.png" alt="" /></p>
180
181<!--
182<pre class="mermaid" style="width:50%;background:#ffffff!important;margin-left:auto;margin-right:auto;">
183%%{init:{'theme':'neutral'}}%%
184
185sequenceDiagram
186participant P as Prover
187participant V as Verifier
188
189P->>P: knows p(X)
190P->>P: commit to p(X), P
191P->>V: P
192V->>V: rand x, U, u
193V->>P: x, U, u
194P->>P: eval v=p(x), gen proof
195P->>V: proof, a, Lⱼ, Rⱼ, v
196V->>V: verify(proof, P, a, x, v, Lⱼ, Rⱼ)
197</pre>
198-->
199
200<h2>IPA by hand</h2>
201
202<p><em>This section provides a step-by-step example of IPA with small values, following the style done in the <a href="https://research.metastate.dev/plonk-by-hand-part-1/">“PLONK by Hand series”</a> by <a href="https://twitter.com/lopeetall">Joshua Fitzgerald</a>.</em></p>
203
204<p>We will use the Elliptic curve <span class="math inline">\(E(\mathbb{F}_{19}): y^2 = x^3 + 3\)</span>.</p>
205
206<p>In the same way that was done in the <a href="https://research.metastate.dev/plonk-by-hand-part-1/"><em>Plonk by hand series</em></a>, let’s compute all the points from our generator <span class="math inline">\(G=(1,2) \in E(\mathbb{F}_{19})\)</span>. We’ll start with <span class="math inline">\(2G\)</span>:</p>
207
208<p><img src="img/posts/ipa/00.png" alt="" /></p>
209
210<p>Combining point doubling and inverses for <span class="math inline">\(4G, 6G, 8G, \ldots\)</span>, together with <a href="https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication#Point_addition">point addition</a> we obtain all the points of our curve:
211<img src="img/posts/ipa/01.png" alt="" /></p>
212
213<p>As we find out, <span class="math inline">\(14 G = G\)</span>, thus <span class="math inline">\(ord(G)_{E(\mathbb{F}_{19})} = 13\)</span>, so we will work in <span class="math inline">\(\mathbb{F}_{13}\)</span>.</p>
214
215<p>Before 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 <span class="math inline">\(d=8\)</span> to make manual computations shorter.</p>
216
217<p>We set up the vector <span class="math inline">\(\overrightarrow{G}\)</span> with random points (without known DLOG between them), and also a random point <span class="math inline">\(H\)</span>:
218<img src="img/posts/ipa/02.png" alt="" /></p>
219
220<p>We define our polynomial <span class="math inline">\(p(X)\)</span>, to which we want to commit, and let <span class="math inline">\(\overrightarrow{a}\)</span> be its coefficients:
221<img src="img/posts/ipa/03.png" alt="" /></p>
222
223<p>Verifier chooses a random challenge <span class="math inline">\(r\)</span>:
224<img src="img/posts/ipa/04.png" alt="" /></p>
225
226<p>Prover commits to <span class="math inline">\(\overrightarrow{a}\)</span>:
227<img src="img/posts/ipa/05.png" alt="" /></p>
228
229<p>We are following the Halo paper, which describes an IPA variant in which the second vector <span class="math inline">\(\overrightarrow{b}\)</span> is fixed for the given choice of <span class="math inline">\(x\)</span>, being <span class="math inline">\(\overrightarrow{b} = {1, x, x^2, x^3, \ldots, x^{d-1}}\)</span>.</p>
230
231<p>We will use <span class="math inline">\(x=3\)</span>, being <span class="math inline">\(\overrightarrow{b}\)</span>:
232<img src="img/posts/ipa/06.png" alt="" /></p>
233
234<p>Now the prover computes the <em>inner product</em> between <span class="math inline">\(\overrightarrow{a}\)</span> and <span class="math inline">\(\overrightarrow{b}\)</span>, using
235<img src="img/posts/ipa/07.png" alt="" /></p>
236
237<p>Which, since our choose of <span class="math inline">\(\overrightarrow{b}\)</span>, it is the equivalent than evaluating <span class="math inline">\(p(X)\)</span> at <span class="math inline">\(x=3\)</span>:
238<img src="img/posts/ipa/08.png" alt="" /></p>
239
240<p>Now the verifier generates the random challenges <span class="math inline">\(u_j \in \mathbb{I}\)</span> and <span class="math inline">\(U \in E\)</span>:
241<img src="img/posts/ipa/09.png" alt="" /></p>
242
243<p>In a non-interactive version of the protocol, these values would be obtained by hashing the transcript (<a href="https://en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic">Fiat-Shamir</a>).</p>
244
245<p>The prover computes P’
246<img src="img/posts/ipa/10.png" alt="" />
247Followed by <span class="math inline">\(k=log(d)\)</span> (3) rounds explained below.</p>
248
249<h4>Rounds</h4>
250
251<p>For each round, from <span class="math inline">\(k-1\)</span> to <span class="math inline">\(0\)</span>, prover will compute:</p>
252<p><span class="math display">\[
253L_j = \langle \overrightarrow{a}_{lo}, \overrightarrow{G}_{hi} \rangle + [l_j] H + [\langle \overrightarrow{a}_{lo}, \overrightarrow{b}_{hi} \rangle] U
254\]</span></p><p><span class="math display">\[
255R_j = \langle \overrightarrow{a}_{hi}, \overrightarrow{G}_{lo} \rangle + [r_j] H + [\langle \overrightarrow{a}_{hi}, \overrightarrow{b}_{lo} \rangle] U
256\]</span></p>
257<h5>Round j=2:</h5>
258
259<p>So, first we will split <span class="math inline">\(\overrightarrow{a}, \overrightarrow{b}, \overrightarrow{G}\)</span> into their respective left and right halves (<span class="math inline">\(\overrightarrow{v}_{lo}, \overrightarrow{v}_{hi}\)</span>):
260<img src="img/posts/ipa/11.png" alt="" /></p>
261
262<p>Set random blinding factors <span class="math inline">\(l_2, r_2\)</span>:
263<img src="img/posts/ipa/12.png" alt="" /></p>
264
265<p>And let’s calculate <span class="math inline">\(L_2\)</span>:
266<img src="img/posts/ipa/13.png" alt="" /></p>
267
268<p>And the same with <span class="math inline">\(R_2\)</span>:
269<img src="img/posts/ipa/14.png" alt="" /></p>
270
271<p>Now, we will compute the new <span class="math inline">\(\overrightarrow{a}, \overrightarrow{b}, \overrightarrow{G}\)</span> to be used in the next round by:</p>
272<p><span class="math display">\[
273\overrightarrow{a} \longleftarrow \overrightarrow{a}_{hi} \cdot u_j^{-1} + \overrightarrow{a}_{lo} \cdot u_j\\
274\overrightarrow{b} \longleftarrow \overrightarrow{b}_{lo} \cdot u_j^{-1} + \overrightarrow{b}_{hi} \cdot u_j
275\]</span></p><p><img src="img/posts/ipa/15.png" alt="" /></p>
276
277<p><img src="img/posts/ipa/16.png" alt="" /></p>
278
279<p>And similarly for <span class="math inline">\(\overrightarrow{G} \longleftarrow \overrightarrow{G}_{lo} \cdot u_j^{-1} + \overrightarrow{G}_{hi} \cdot u_j\)</span>
280<img src="img/posts/ipa/17.png" alt="" /></p>
281
282<p>We can see that <span class="math inline">\(\overrightarrow{a}, \overrightarrow{b}, \overrightarrow{G}\)</span> have halved.</p>
283
284<h5>Round j=1:</h5>
285
286<p>From the previous round we have:</p>
287
288<p><img src="img/posts/ipa/18.png" alt="" /></p>
289
290<p>Choose the random blinding factors:
291<img src="img/posts/ipa/19.png" alt="" /></p>
292
293<p>And now, in the same fashion that we did in the previous round, we compute the <span class="math inline">\(L_1, R_1\)</span>:
294<img src="img/posts/ipa/20.png" alt="" /></p>
295
296<p><img src="img/posts/ipa/21.png" alt="" /></p>
297
298<p>Now, we will compute the new <span class="math inline">\(\overrightarrow{a}, \overrightarrow{b}, \overrightarrow{G}\)</span> to be used in the next round:
299<img src="img/posts/ipa/22.png" alt="" /></p>
300
301<p><img src="img/posts/ipa/23.png" alt="" /></p>
302
303<p><img src="img/posts/ipa/24.png" alt="" /></p>
304
305<h5>Round j=0:</h5>
306
307<p><img src="img/posts/ipa/25.png" alt="" /></p>
308
309<p>Set the random blinding factors <span class="math inline">\(l_0, r_0\)</span>:
310<img src="img/posts/ipa/26.png" alt="" /></p>
311
312<p>Compute <span class="math inline">\(L_0, R_0\)</span>:
313<img src="img/posts/ipa/27.png" alt="" /></p>
314
315<p>we will compute the new halved <span class="math inline">\(\overrightarrow{a}, \overrightarrow{b}, \overrightarrow{G}\)</span>:
316<img src="img/posts/ipa/28.png" alt="" /></p>
317
318<p><img src="img/posts/ipa/29.png" alt="" />
319<img src="img/posts/ipa/30.png" alt="" /></p>
320
321<p>The prover ends having as outputs <span class="math inline">\(a=\overrightarrow{a}_0, ~~b=\overrightarrow{b}_0, ~~G=\overrightarrow{G}_0\)</span>, and the random blinding factors <span class="math inline">\(\overrightarrow{l}, \overrightarrow{r}\)</span>, together with <span class="math inline">\(\overrightarrow{L}, \overrightarrow{R}\)</span>:
322<img src="img/posts/ipa/31.png" alt="" /></p>
323
324<h3>Verify</h3>
325
326<p>First, verifier recomputes <span class="math inline">\(b\)</span> and <span class="math inline">\(G\)</span>. 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 <span class="math inline">\(b\)</span> and <span class="math inline">\(G\)</span> in the <em>naive way</em> (which is, doing a similar loop than what the prover did, going from the original <span class="math inline">\(\overrightarrow{b}, \overrightarrow{G}\)</span> halving each round until obtaining <span class="math inline">\(b, G\)</span>). In the Sage implementation provided in the next section, we will use the efficient approach, which was also provided in the overview section.</p>
327
328<p>Now, the verifier can compute <span class="math inline">\(P'\)</span> in the same way that the prover did (<span class="math inline">\(P'=P + [v] U\)</span>), and from here computes <span class="math inline">\(Q_0 = \sum_{j=1}^k ( [u_j^2] L_j) + P' + \sum_{j=1}^k ([u_j^{-2}] R_j)\)</span>:</p>
329
330<p><img src="img/posts/ipa/32.png" alt="" /></p>
331
332<p>As we did previously, for an easier by-hand computation, we can ‘translate’ the points to multiples of the generator <span class="math inline">\(G\)</span>, to operate with them more easily without a computer:</p>
333
334<p><img src="img/posts/ipa/33.png" alt="" /></p>
335
336<p>We need to compute also <span class="math inline">\(r' = \sum_{j=1}^k (l_j \cdot u_j^2) + r + \sum_{j=1}^k (r_j \cdot u_j^{-2})\)</span>:</p>
337
338<p><img src="img/posts/ipa/34.png" alt="" /></p>
339
340<p>And then compute <span class="math inline">\(Q_1 = [a] G + [r'] H + [ab] U\)</span>:</p>
341
342<p><img src="img/posts/ipa/35.png" alt="" /></p>
343
344<p>And by checking that <span class="math inline">\(Q_0 == Q_1\)</span>, the verifier finishes the verification.</p>
345
346<h2>Now let’s do a simple implementation</h2>
347
348<p>We will do a simple implementation in Sage of the protocol.</p>
349
350<p>First of all, we set up our curve:</p>
351
352<pre><code class="language-python">p = 19
353Fp = GF(p)
354E = EllipticCurve(Fp,[0,3])
355g = E(1, 2)
356q = g.order()
357Fq = GF(q)
358</code></pre>
359
360<p>Now let’s create the ‘IPA’ class:</p>
361
362<pre><code class="language-python">class IPA_halo(object):
363 def __init__(self, F, E, g, d):
364 self.g = g
365 self.F = F
366 self.E = E
367 self.d = d
368
369 self.h = E.random_element()
370 self.gs = random_values(E, d)
371 self.hs = random_values(E, d)
372
373
374def random_values(G, d):
375 r = [None] * d
376 for i in range(d):
377 r[i] = G.random_element()
378 return r
379</code></pre>
380
381<p>Now we can generate all the elliptic curve points in a similar way that when we computed them by-hand in the previous section:</p>
382
383<pre><code class="language-python">print("\nlet's generate all the points:")
384P = g+g
385print("P_0:", g)
386i=1
387while P!=g:
388 print("P_%d:" % i, P)
389 P = P + P
390 i += 1
391print("P_%d:" % (i+1), E(0), "(point at infinity)")
392</code></pre>
393
394<p>Alternatively we can use Sage’s methods:</p>
395
396<pre><code class="language-python"># alternatively:
397print("points", E.points())
398print("number of points", len(E.points()))
399</code></pre>
400
401<p>Now, the Prover will set the polynomial <span class="math inline">\(p(X)\)</span> and the Verifier would set <span class="math inline">\(x\)</span>:</p>
402
403<pre><code class="language-python">print("\ndefine p(X) = 1 + 2x + 3x² + 4x³ + 5x⁴ + 6x⁵ + 7x⁶ + 8x⁷")
404a = [ipa.F(1), ipa.F(2), ipa.F(3), ipa.F(4),
405 ipa.F(5), ipa.F(6), ipa.F(7), ipa.F(8)]
406x = ipa.F(3)
407x_powers = powers_of(x, ipa.d) # = b
408</code></pre>
409
410<p>Prover sets the blinding factor <span class="math inline">\(r\)</span>:</p>
411
412<pre><code class="language-python">r = int(ipa.F.random_element())
413</code></pre>
414
415<p>We will implement some utility functions that we’ll use later in the rest of the implementation:</p>
416
417<pre><code class="language-python">def inner_product_field(a, b):
418 assert len(a) == len(b)
419 c = 0
420 for i in range(len(a)):
421 c = c + a[i] * b[i]
422
423 return c
424
425def inner_product_point(a, b):
426 assert len(a) == len(b)
427 c = 0
428 for i in range(len(a)):
429 c = c + int(a[i]) * b[i]
430
431 return c
432
433def vec_add(a, b):
434 assert len(a) == len(b)
435 return [x + y for x, y in zip(a, b)]
436
437def vec_mul(a, b):
438 assert len(a) == len(b)
439 return [x * y for x, y in zip(a, b)]
440
441def vec_scalar_mul_field(a, n):
442 r = [None]*len(a)
443 for i in range(len(a)):
444 r[i] = a[i]*n
445 return r
446
447def vec_scalar_mul_point(a, n):
448 r = [None]*len(a)
449 for i in range(len(a)):
450 r[i] = a[i]*int(n)
451 return r
452</code></pre>
453
454<p>And we will implement in the <code>IPA</code> class the methods for committing and evaluating:</p>
455
456<pre><code class="language-python">class IPA_halo:
457 # [...]
458 def commit(self, a, r):
459 P = inner_product_point(a, self.gs) + r * self.h
460 return P
461
462 def evaluate(self, a, x_powers):
463 return inner_product_field(a, x_powers)
464</code></pre>
465
466<p>So now the prover can commit to <span class="math inline">\(a\)</span>:</p>
467
468<pre><code class="language-python">print("\nProver commits to a:")
469P = ipa.commit(a, r)
470print(" commit: P = <a, G> + r * H = ", P)
471print("Evaluates a at {1 + x + x² + x³ + … + xⁿ⁻¹}:")
472v = ipa.evaluate(a, x_powers)
473print(" v =", v)
474print(" (which is equivalent to evaluating p(X) at x=3)")
475</code></pre>
476
477<p>Verifier generates random challenges <span class="math inline">\(u_j \in \mathbb{I}\)</span> and <span class="math inline">\(U \in \mathbb{U}\)</span></p>
478
479<pre><code class="language-python">print("\nVerifier generate random challenges {uᵢ} ∈ 𝕀 and U ∈ 𝔾")
480U = ipa.E.random_element()
481k = int(math.log(ipa.d, 2))
482u = [None] * k
483for j in reversed(range(0, k)):
484 u[j] = ipa.F.random_element()
485 while (u[j] == 0): # prevent u[j] from being 0
486 u[j] = ipa.F.random_element()
487print(" U =", U)
488print(" u =", u)
489</code></pre>
490
491<p>Now let’s implmenet the <code>ipa</code> proof generation method in the <code>IPA</code> class:</p>
492
493<pre><code class="language-python">def ipa(self, a_, x_powers, u, U): # prove
494 G = self.gs
495 a = a_
496 b = x_powers
497
498 k = int(math.log(self.d, 2))
499 l = [None] * k
500 r = [None] * k
501 L = [None] * k
502 R = [None] * k
503
504 for j in reversed(range(0, k)):
505 m = len(a)/2
506 a_lo = a[:m]
507 a_hi = a[m:]
508 b_lo = b[:m]
509 b_hi = b[m:]
510 G_lo = G[:m]
511 G_hi = G[m:]
512
513 l[j] = self.F.random_element() # random blinding factor
514 r[j] = self.F.random_element() # random blinding factor
515
516 # Lⱼ = <a'ₗₒ, G'ₕᵢ> + [lⱼ] H + [<a'ₗₒ, b'ₕᵢ>] U
517 L[j] = inner_product_point(a_lo, G_hi) + int(l[j]) * self.h + int(inner_product_field(a_lo, b_hi)) * U
518 # Rⱼ = <a'ₕᵢ, G'ₗₒ> + [rⱼ] H + [<a'ₕᵢ, b'ₗₒ>] U
519 R[j] = inner_product_point(a_hi, G_lo) + int(r[j]) * self.h + int(inner_product_field(a_hi, b_lo)) * U
520
521 # use the random challenge uⱼ ∈ 𝕀 generated by the verifier
522 u_ = u[j] # uⱼ
523 u_inv = self.F(u[j])^(-1) # uⱼ⁻¹
524
525 a = vec_add(vec_scalar_mul_field(a_lo, u_), vec_scalar_mul_field(a_hi, u_inv))
526 b = vec_add(vec_scalar_mul_field(b_lo, u_inv), vec_scalar_mul_field(b_hi, u_))
527 G = vec_add(vec_scalar_mul_point(G_lo, u_inv), vec_scalar_mul_point(G_hi, u_))
528
529 assert len(a)==1
530 assert len(b)==1
531 assert len(G)==1
532 # a, b, G have length=1
533 # l, r are random blinding factors
534 # L, R are the "cross-terms" of the inner product
535 return a[0], l, r, L, R
536</code></pre>
537
538<p>Followed by the Inner Product Argument using the <code>ipa</code> method that we implemented in the previous step:</p>
539
540<pre><code class="language-python">print("\nProver computes the Inner Product Argument:")
541a_ipa, b_ipa, G_ipa, lj, rj, L, R = ipa.ipa(a, x_powers, u, U)
542print(" a=", a_ipa)
543print(" b=", b_ipa)
544print(" G=", G_ipa)
545print(" l_j=", lj)
546print(" r_j=", rj)
547print(" R=", R)
548print(" L=", L)
549</code></pre>
550
551<p>Now let’s implement the verification:</p>
552
553<pre><code class="language-python">def verify(self, P, a, v, x_powers, r, u, U, lj, rj, L, R):
554 # compute P' = P + [v] U
555 P = P + int(v) * U
556
557 s = build_s_from_us(u, self.d)
558 b = inner_product_field(s, x_powers)
559 G = inner_product_point(s, self.gs)
560
561 # synthetic blinding factor
562 # r' = r + ∑ ( lⱼ uⱼ² + rⱼ uⱼ⁻²)
563 r_ = r
564 # Q_0 = P' ⋅ ∑ ( [uⱼ²] Lⱼ + [uⱼ⁻²] Rⱼ)
565 Q_0 = P
566 for j in range(len(u)):
567 u_ = u[j] # uⱼ
568 u_inv = u[j]^(-1) # uⱼ⁻²
569
570 # ∑ ( [uⱼ²] Lⱼ + [uⱼ⁻²] Rⱼ)
571 Q_0 = Q_0 + int(u[j]^2) * L[j] + int(u_inv^2) * R[j]
572
573 r_ = r_ + lj[j] * (u_^2) + rj[j] * (u_inv^2)
574
575 Q_1 = int(a) * G + int(r_) * self.h + int(a * b)*U
576
577 return Q_0 == Q_1
578</code></pre>
579
580<p>Which now the verifier uses the method to verify the proof:</p>
581
582<pre><code class="language-python">verif = ipa.verify(P, a_ipa, v, x_powers, r, u, U, lj, rj, L, R)
583assert verif == True
584</code></pre>
585
586<p>Now 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.</p>
587
588<h2>Final note</h2>
589
590<p>As 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 <a href="https://github.com/arnaucube/math/blob/master/ipa.sage">complete Sage implementation here</a>. Additionally, here you can find <a href="https://github.com/arnaucube/ipa-rs">a Rust implementation using arkworks</a>.</p>
591
592<p>One thing worth to mention is that IPA proving cost is <span class="math inline">\(\mathcal{O}(n)\)</span>, proof size is <span class="math inline">\(\mathcal{O}(log(n))\)</span>, and verification cost is <span class="math inline">\(\mathcal{O}(n)\)</span>. An interesting technique not covered in this post, is the one presented in the <a href="https://eprint.iacr.org/2019/1021.pdf">Halo</a> paper, in which the cost of verification is amortized, achieving practical <span class="math inline">\(\mathcal{O}(log(n))\)</span> verification.</p>
593
594<p>IPA is used as polynomial commitment scheme in places like the already mentioned <a href="https://eprint.iacr.org/2019/1021.pdf">Halo</a> (and <a href="https://zcash.github.io/halo2/index.html">Halo2</a>), but it can be combined in other schemes such as <a href="https://iacr.org/archive/eurocrypt2020/12105185/12105185.pdf">Marlin</a>.</p>
595
596<p>I’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.</p>
597
598<style>
599p > img{
600 max-width: 70%!important;
601 display: block;
602 margin-left: auto;
603 margin-right: auto;
604}
605</style>
606
607 </div>
608
609 <footer style="text-align:center; margin-top:100px;margin-bottom:50px;">
610 <div class="container">
611 <br>
612 <a href="/blog">Go to main</a>
613 <br><br>
614 <div class="row">
615 <ul class="list-inline">
616 <li><a href="https://twitter.com/arnaucube"
617 style="color:gray;text-decoration:none;"
618 target="_blank">twitter.com/arnaucube</a>
619 </li>
620 <li><a href="https://github.com/arnaucube"
621 style="color:gray;text-decoration:none;"
622 target="_blank">github.com/arnaucube</a>
623 </li>
624 </ul>
625 </div>
626 <div class="row" style="display:inline-block;">
627 Blog made with <a href="http://github.com/arnaucube/blogo/"
628 target="_blank" style="color: gray;text-decoration:none;">Blogo</a>
629 </div>
630 </div>
631 </footer>
632
633 <script>
634 </script>
635 <script src="js/external-links.js"></script>
636 <script>hljs.initHighlightingOnLoad();</script>
637 <script defer src="js/katex/katex.min.js"></script>
638 <script defer src="js/katex/auto-render.min.js"></script>
639 <script>
640 document.addEventListener("DOMContentLoaded", function() {
641 renderMathInElement(document.body, {
642 displayMode: false,
643 // customised options
644 // • auto-render specific keys, e.g.:
645 delimiters: [
646 {left: '$$', right: '$$', display: true},
647 {left: '$', right: '$', display: false},
648 {left: "\\[", right: "\\]", display: true},
649 {left: "\\(", right: "\\)", display: false},
650 {left: "\\begin{equation}", right: "\\end{equation}", display: true}
651 ],
652 // • rendering keys, e.g.:
653 throwOnError : true
654 });
655 });
656
657 ///
658 let theme = localStorage.getItem("theme");
659 if ((theme === "light-theme")||(theme==null)) {
660 theme = "light-theme";
661 document.getElementById("themeSwitcher").checked = false;
662 } else if (theme === "dark-theme") {
663 theme = "dark-theme";
664 document.getElementById("themeSwitcher").checked = true;
665 }
666 document.body.className = theme;
667 localStorage.setItem("theme", theme);
668
669 function switchTheme() {
670 theme = localStorage.getItem("theme");
671 if (theme === "light-theme") {
672 theme = "dark-theme";
673 document.getElementById("themeSwitcher").checked = true;
674 } else {
675 theme = "light-theme";
676 document.getElementById("themeSwitcher").checked = false;
677 }
678 document.body.className = theme;
679 localStorage.setItem("theme", theme);
680
681 console.log(theme);
682 }
683 </script>
684 <script>
685 function tagLinks(tagName) {
686 var tags = document.getElementsByTagName(tagName);
687 for (var i=0, hElem; hElem = tags[i]; i++) {
688 if (hElem.parentNode.className=="row postThumb") {
689 continue;
690 }
691 hElem.id = hElem.innerHTML.toLowerCase().replace(" ", "-");
692 hElem.innerHTML = "<a style='color:black!important;' href='#"+hElem.id+"'>"+hElem.innerHTML+"</a>";
693 }
694 }
695 tagLinks("h2");
696 tagLinks("h3");
697 tagLinks("h4");
698 tagLinks("h5");
699 </script>
700 <script>
701function generateTOC(tocContainerId = "toc") {
702 const tocContainer = document.getElementById(tocContainerId);
703 if (!tocContainer) return;
704
705 const headings = document.querySelectorAll("h2, h3, h4, h5, h6");
706 if (!headings.length) return;
707
708 // Generate IDs if missing
709 headings.forEach((heading, index) => {
710 if (!heading.id) {
711 heading.id =
712 heading.textContent
713 .trim()
714 .toLowerCase()
715 .replace(/[^\w\s-]/g, "")
716 .replace(/\s+/g, "-") +
717 "-" +
718 index;
719 }
720 });
721
722 const toc = document.createElement("ul");
723 let currentLevel = 1;
724 let currentList = toc;
725 const stack = [toc];
726
727 headings.forEach((heading) => {
728 const level = parseInt(heading.tagName.substring(1), 10);
729
730 const li = document.createElement("li");
731 const a = document.createElement("a");
732
733 a.href = "#" + heading.id;
734 a.textContent = heading.textContent;
735
736 li.appendChild(a);
737
738 if (level > currentLevel) {
739 for (let i = currentLevel; i < level; i++) {
740 const nestedList = document.createElement("ul");
741
742 const lastLi =
743 currentList.lastElementChild ||
744 currentList.appendChild(document.createElement("ul"));
745
746 lastLi.appendChild(nestedList);
747
748 stack.push(nestedList);
749 currentList = nestedList;
750 }
751 } else if (level < currentLevel) {
752 for (let i = currentLevel; i > level; i--) {
753 stack.pop();
754 }
755 currentList = stack[stack.length - 1];
756 }
757
758 currentList.appendChild(li);
759 currentLevel = level;
760 });
761
762 tocContainer.innerHTML = "";
763 tocContainer.appendChild(toc);
764}
765
766document.addEventListener("DOMContentLoaded", () => {
767 generateTOC();
768});
769 </script>
770 <script src="js/mermaid.min.js"></script>
771
772 </body>
773</html>
774