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