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