arnaucube
arnaucube/arnaucube.comPublic Self-hosted repository
arnaucube.com/blog/protogalaxy.html
blog/protogalaxy.htmlRaw
  1<!DOCTYPE html>
  2<html lang="en">
  3
  4  <head>
  5    <meta name="description" content="The idea of these notes is to provide some extra intuition and explainations on ProtoGalaxy's paper. ProtoGalaxy is a folding scheme which iterates on ideas from ProtoStar paper." />
  6    <meta charset="utf-8">
  7    <title> Notes on ProtoGalaxy - arnaucube - blog</title>
  8    <meta name="title" content=" Notes on ProtoGalaxy - arnaucube - blog">
  9    <meta name="description" content="The idea of these notes is to provide some extra intuition and explainations on ProtoGalaxy's paper. ProtoGalaxy is a folding scheme which iterates on ideas from ProtoStar paper.">
 10
 11    <meta property="og:title" content=" Notes on ProtoGalaxy - arnaucube - blog" />
 12    <meta property="og:description" content="The idea of these notes is to provide some extra intuition and explainations on ProtoGalaxy's paper. ProtoGalaxy is a folding scheme which iterates on ideas from ProtoStar paper." />
 13    <meta property="og:url" content="https://arnaucube.com/blog/protogalaxy.html" />
 14    <meta property="og:type" content="article" />
 15    <meta property="og:image" content="https://arnaucube.com/blog/img/posts/protogalaxy/protogalaxies-colliding.jpg" />
 16    <meta name="twitter:title" content=" Notes on ProtoGalaxy - arnaucube - blog">
 17    <meta name="twitter:description" content="The idea of these notes is to provide some extra intuition and explainations on ProtoGalaxy's paper. ProtoGalaxy is a folding scheme which iterates on ideas from ProtoStar paper.">
 18    <meta name="twitter:image" content="https://arnaucube.com/blog/img/posts/protogalaxy/protogalaxies-colliding.jpg">
 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="/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>Notes on ProtoGalaxy</h1>
 75
 76<p><em>2023-08-20</em></p>
 77
 78<blockquote>
 79<p><strong>Note</strong>: I&rsquo;m not a mathematician, just a math enthusiast studying in my free time, and this article is just an attempt to try to sort the notes that I took while studying the ProtoGalaxy scheme.</p>
 80</blockquote>
 81
 82<p>The idea of these notes is to provide some extra intuition on <a href="https://eprint.iacr.org/2023/1106">ProtoGalaxy paper</a>.
 83The paper is very well written and exposes the ideas very clearly, so it&rsquo;s worth to check directly the paper instead of these notes.</p>
 84
 85<p>I make use of <span class="math inline">\(\textcolor{blue}{c}\textcolor{magenta}{o}\textcolor{orange}{l}\textcolor{cyan}{o}\textcolor{green}{u}\textcolor{red}{r}\textcolor{pink}{s}\)</span> to try to relate the different parameters across the scheme.</p>
 86
 87<p>ProtoGalaxy is a <em>folding scheme</em> which iterates on ideas from <a href="https://eprint.iacr.org/2023/620">ProtoStar paper</a> (here you can find <a href="https://geometry.xyz/notebook/paper-speedrun-protostar">Geometry&rsquo;s post</a> overviewing its main results and techniques).</p>
 88
 89<p>For an introduction to <em>folding schemes</em> I highly recommend <a href="https://youtu.be/IzLTpKWt-yg?t=6367">this talk (at 1:46)</a> by <a href="https://twitter.com/CPerezz19">Carlos Pérez</a>.</p>
 90
 91<p>I would like to thank <a href="https://twitter.com/LiamEagen">Liam Eagen</a> and <a href="https://twitter.com/rel_zeta_tech">Ariel Gabizon</a> for their kind explanations on the scheme.
 92Also thanks to <a href="https://twitter.com/kiliconu">Onur</a> for comments and corrections.</p>
 93
 94<div style="margin-left:20%;" >
 95
 96<img src="img/posts/protogalaxy/protogalaxies-colliding.jpg"/>
 97
 98<br>
 99(img: protogalaxies colliding, <a href="https://en.wikipedia.org/wiki/File:Stellar_Fireworks_Finale.jpg">from Wikipedia</a>)
100
101</div>
102
103<h2>Preliminaries</h2>
104
105<p>Before jumping into the protocol itself, let&rsquo;s overview some building blocks first.</p>
106
107<h4><span class="math inline">\(pow_i\)</span></h4>
108
109<p>In the protocol we need the powers of a random value. We use the <span class="math inline">\(pow_i\)</span> function to store and operate only <span class="math inline">\(log(n)\)</span> entries instead of <span class="math inline">\(n\)</span>.</p>
110
111<p><span class="math inline">\(pow_i\)</span> is a <span class="math inline">\(t\)</span>-variate polynomial such that</p>
112<p><span class="math display">\[
113% pow_i(X_1, \ldots, X_t) = \prod_{i \in [n]} ((1-b_j) + b_j \cdot X^{2^j})
114pow_i(X) = \prod_{i \in [n]} ((1-b_j) + b_j \cdot X^{2^j})
115\]</span></p><p>where <span class="math inline">\(b_j\)</span> is the binary decomposition of <span class="math inline">\(n\)</span>, such that <span class="math inline">\(n = \sum 2^j\)</span>.</p>
116
117<p>In our case, we will have <span class="math inline">\(\overrightarrow{X}\)</span> being <span class="math inline">\(\overrightarrow{\beta} = \{\beta^{2^i} \}_0^{t-1} = (\beta, \beta^2, \beta^4, \ldots, \beta^{2^{t-1}})\)</span>, thus</p>
118<p><span class="math display">\[
119pow_i(\overrightarrow{\beta}) = \prod_{j \in [n]} ((1-b_j) + b_j \cdot \beta_j)
120\]</span></p><p>which, basically is a way to have <span class="math inline">\(pow_i(\overrightarrow{\beta}) = \beta^i\)</span>, but storing just <span class="math inline">\(t\)</span> betas, to actually represent <span class="math inline">\(2^t\)</span> of them, so we work with <span class="math inline">\(log\)</span> of the total amount actually used.</p>
121
122<p>So, for example,</p>
123<p><span class="math display">\[
124    i=2_d=10_b;~
125    pow_2(\overrightarrow{\beta}) =
126    \underbrace{((1-0) + 0 \cdot \beta)}_{1}
127    \cdot \underbrace{((1-1) + 1 \cdot \beta^2)}_{\beta^2}
128    = \beta^2
129    \\
130    i=3_d=11_b;~
131    pow_3(\overrightarrow{\beta}) =
132    \underbrace{((1-1) + 1 \cdot \beta)}_{\beta}
133    \cdot \underbrace{((1-1) + 1 \cdot \beta^2)}_{\beta^2}
134    = \beta^3
135    \\
136    i=4_d=100_b;~
137    pow_4(\overrightarrow{\beta}) =
138    \underbrace{((1-0) + 0 \cdot \beta)}_{1}
139    \cdot \underbrace{((1-0) + 0 \cdot \beta^2)}_{1}
140    \cdot \underbrace{((1-1) + 1 \cdot \beta^4)}_{\beta^4}
141    = \beta^4
142    \\
143    i=5_d=101_b;~
144    pow_5(\overrightarrow{\beta}) =
145    \underbrace{((1-1) + 1 \cdot \beta)}_{\beta}
146    \cdot \underbrace{((1-0) + 0 \cdot \beta^2)}_{1}
147    \cdot \underbrace{((1-1) + 1 \cdot \beta^4)}_{\beta^4}
148    = \beta^5
149\]</span></p>
150<h4>Lagrange bases</h4>
151
152<p>Let <span class="math inline">\(\omega\)</span> denote a root of unity, such that <span class="math inline">\(\omega^N=1\)</span>, and set <span class="math inline">\(\mathbb{H}=\{1, \omega, \omega^2, \ldots, \omega^{N-1}\}\)</span>.</p>
153
154<p>Lagrange bases are a whole topic by itself, but for following the next sections, we just need to have a clear intuition on how they operate. The main idea is that</p>
155<p><span class="math display">\[L_j(\omega^i)=
156\begin{cases}
157	&amp;1 ~\text{if}~ i=j\\
158	&amp;0 ~\text{otherwise}
159\end{cases}
160\]</span></p><p>In other words, when we&rsquo;re evaluating the Lagrange base <span class="math inline">\(j\)</span> at <span class="math inline">\(w^i\)</span>, the evaluation is going to be <span class="math inline">\(1\)</span> when <span class="math inline">\(i=j\)</span>, and <span class="math inline">\(0\)</span> in all the other cases.</p>
161
162<p>To get a bit of more intuition here, let&rsquo;s represent this visually:</p>
163
164<div>
165
166<img src="img/posts/protogalaxy/lagrange-basis-intuition.png" style="width:40%;display:inline-block;" />
167
168<div style="width:50%; display:inline-block;">
169The intuition here is that when we evaluate $L_2(X)$ at $\omega_2=\omega^2$, it will give us $1$. In the blue equation of the image we're doing $L_2(w^2) \cdot v_k = 1 \cdot v_k$.
170
171While, when we evaluate $L_2(X)$ at for example $\omega^1$, we will obtain a $0$, thus the result will be a $0$.
172
173</div>
174</div>
175
176<p>Let the vanishing polynomial of <span class="math inline">\(\mathbb{H}\)</span> be <span class="math inline">\(Z(X)=\prod_{i=0}^{N-1} (X - \omega^i) = X^N -1\)</span>.</p>
177
178<h4>Function <span class="math inline">\(f(X)\)</span></h4>
179
180<p>Assume we have a function <span class="math inline">\(f(X)\)</span> which when evaluated at a valid witness is equal to 0.</p>
181
182<p>For example, in the R1CS case, this would be (for given matrices <span class="math inline">\(A, B, C \in \mathbb{F}^{m \times m}\)</span> representing our constraints),</p>
183
184<!--$$f(X)= \sum_{i=0}^n A(X_i) \cdot B(X_i) - C(X_i)$$-->
185<p><span class="math display">\[f(X)= A \cdot X \circ B \cdot X - C \cdot X \]</span></p>
186<!-- $$f(X)= \sum_{i=0}^n A(X_i) \cdot B(X_i) - C(X_i)$$ -->
187
188<p>where <span class="math inline">\(f(w)=0^n\)</span> if satisfied for a valid witness <span class="math inline">\(w \in \mathbb{F}^n\)</span>.</p>
189
190<p>Our goal will be to prove that we have folded various instantiations of valid witnesses and that they fulfill the check of <span class="math inline">\(f(w)=0^n\)</span>.</p>
191
192<h4>Lemma 4.2</h4>
193
194<p>The following lemma is from the ProtoGalaxy paper:</p>
195
196<blockquote>
197<p><strong>Lemma 4.2:</strong> Fix any polynomial <span class="math inline">\(f(X) \in \mathbb{F}[X]\)</span> and <span class="math inline">\(a_0, \ldots, a_k \in \mathbb{F}\)</span>. There exists <span class="math inline">\(Q(X) \in \mathbb{F}[X]\)</span> such that</p>
198<p><span class="math display">\[
199	f \left( \sum_{i=0}^k a_i L_i(X) \right) = \sum_{i=0}^k f(a_i) L_i(X) + Z(X) Q(X)
200\]</span></p></blockquote>
201
202<p>The way to check that the lemma is true for me was to implement it with code and check that it is satisfied. This is not a proper way, so luckily later <a href="https://hecmas.github.io">Héctor Masip</a> showed me an actual proof of this lemma, which goes as follows:</p>
203
204<p>Recall from the <a href="https://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor#Euclidean_division">Euclidean polynomial division</a>:</p>
205
206<blockquote>
207<p>For <span class="math inline">\(f(X), g(X) \in \mathbb{F}[X]\)</span> with <span class="math inline">\(\deg f \geq \deg g\)</span>, <span class="math inline">\(\exists\)</span> unique polynomials <span class="math inline">\(q(X), r(X) \in \mathbb{F}[X]\)</span> such that <span class="math inline">\(f(X) = g(X) q(X) + r(X)\)</span>, with <span class="math inline">\(0 \leq \deg r &lt; \deg g\)</span>.</p>
208</blockquote>
209
210<p>Thus,</p>
211<p><span class="math display">\[f(\sum_{i=0}^k a_i \cdot L_i(X)) = Q(X) \cdot Z(X) + r(X)\]</span></p><p>with <span class="math inline">\(0 \leq \deg r &lt; \deg Z = k+1\)</span>.</p>
212
213<p>So, when evaluating at <span class="math inline">\(a_j, ~\forall j=0, \ldots, k\)</span>,</p>
214<p><span class="math display">\[f(\sum_{i=0}^k a_i \cdot L_i(a_j)) = f(a_j) = \underbrace{Q(a_j) \cdot Z(a_j)}_{0} + r(a_j)\]</span></p><p>so <span class="math inline">\(f(a_j)=r(a_j)\)</span>, therefore</p>
215<p><span class="math display">\[r(X) = \sum_{i=0}^k r(a_i) \cdot L_i(X) = \sum_{i=0}^k f(a_i) \cdot L_i(X)\]</span></p>
216<div style="float:right;">
217
218$\square$
219
220</div>
221
222<h2>ProtoGalaxy protocol</h2>
223
224<p>The main idea of this scheme, is to be able to fold <span class="math inline">\(k+1\)</span> instances that satisfy the relation, producing a single <em>folded instance</em> which still satisfies the relation.</p>
225
226<p><img src="img/posts/protogalaxy/folding-diagram.png" style="width:80%;" /></p>
227
228<h4>Instances</h4>
229
230<p>Let <span class="math inline">\((\phi; w)\)</span> be our running instance, the witness is represented by <span class="math inline">\(w\)</span>, and <span class="math inline">\(\phi = cm(w)\)</span> represents the committed witness.
231Additionally, we will have <span class="math inline">\(k\)</span> randomized instance pairs <span class="math inline">\(( \{ \phi_i \}^k; \{ w_i \}^k )\)</span>.</p>
232
233<p>The running instance is paired with two more parameters, so the complete running instance consists of <span class="math inline">\(((\phi, \overrightarrow{\beta}, e); w)\)</span>, where <span class="math inline">\(e\)</span> is the &lsquo;error&rsquo; term and <span class="math inline">\(\overrightarrow{\beta} \in^R \mathbb{F}^t\)</span> (where <span class="math inline">\(t=\log(n)\)</span>).</p>
234
235<p>As we start folding instances, the folded instance must satisfy the relation</p>
236<p><span class="math display">\[
237\sum_{i \in [n]} pow_i(\overrightarrow{\beta}) f_i(w) = e
238\]</span></p><p>where <span class="math inline">\(pow_i\)</span> is the function explained in the <a href="#preliminaries">preliminaries section</a>, and <span class="math inline">\(f_i\)</span> is the <span class="math inline">\(i\)</span>-th value from evaluating <span class="math inline">\(f(w)\)</span>.</p>
239
240<p>For the first instance (before folding) <span class="math inline">\(e=0\)</span>, which we can see that matches <span class="math inline">\(\sum_{i \in [n]} pow_i(\overrightarrow{\beta}) f_i(w) = 0\)</span>, since <span class="math inline">\(f(w)=0^n\)</span> for a valid <span class="math inline">\(w\)</span>.</p>
241
242<h4>Protocol</h4>
243
244<p>We want a way for the Prover to fold <span class="math inline">\(k+1\)</span> instances into a single one, combining them while ensuring that they satisfy the relation by showing that <span class="math inline">\(f(w_i)=0\)</span> for all <span class="math inline">\(k+1\)</span> instances.</p>
245
246<p>For doing so, we could just add all the instances naively, but they could cancel each other giving <span class="math inline">\(0\)</span> when evaluated at the different <span class="math inline">\(w_i\)</span>, even when individually don&rsquo;t evaluate at <span class="math inline">\(0\)</span>.</p>
247
248<p>One way to combine the instances is through making use of a random linear combination (as done in Nova and ProtoStar), but when combining <span class="math inline">\(k\)</span> instances the degree of the cross-terms would grow exponentially. Thus ProtoGalaxy uses the Lagrange bases, by associating each instance to a different Lagrange coefficient, thus keeping the instances &lsquo;separated&rsquo; while being combined in the same expression.</p>
249
250<p><br>
251<em>(Let P denote the Prover, and V the Verifier)</em></p>
252
253<ol>
254<li><p>V sends a challenge <span class="math inline">\(\delta \in^R \mathbb{F}\)</span></p></li>
255
256<li><p>P, V compute <span class="math inline">\(\overrightarrow{\delta} = \{\delta^{2^i} \}_0^{t-1} = (\delta, \delta^2, \delta^4, \ldots, \delta^{2^{t-1}}) \in \mathbb{F}^t\)</span></p></li>
257
258<li><p>P computes the polynomial</p>
259<p><span class="math display">\[
260F(X) := \sum_{i \in [n]} pow_i(
261\underbrace{
262	\textcolor{orange}{\overrightarrow{\beta}} + X \cdot
263	\textcolor{orange}{\overrightarrow{\delta} }
264}_\text{represent it by $\textcolor{orange}{\overrightarrow{\eta}}$}
265) \textcolor{ForestGreen}{f_i(w)}
266\\
267\text{\scriptsize{where $\textcolor{orange}{\overrightarrow{\eta}}$ is just an intermediate}}
268\\
269\text{\scriptsize{representation of the new random vector over $X$}}
270\\
271\text{\scriptsize{where $\overrightarrow{\eta}=\{ \beta+X \delta, (\beta + X \delta)^2, (\beta +X \delta)^4, \ldots, (\beta + X \delta)^{2^{t-1}} \}$}}
272\\
273= \sum_{i \in [n]}
274	pow_i(\textcolor{orange}{\overrightarrow{\eta}})
275\textcolor{ForestGreen}{f_i(w)}
276\]</span></p><p>Notice that each <span class="math inline">\(pow_i(\textcolor{orange}{\overrightarrow{\eta}})\)</span> will be a polynomial of degree equal to the number of positive bits in the binary representation of <span class="math inline">\(i\)</span>.</p>
277
278<div style="font-size:85%;">
279
280
281In order to see this, let's simplify $\overrightarrow{\eta}$ and instead let's get take $\overrightarrow{\eta}$ getting rid of $\beta,~\delta$. Let $\overrightarrow{X} = \{X, X, X, \ldots, X \}$,
282recall that 
283
284
285$$
286pow_i(\overrightarrow{X}) = \prod_{j \in [n]} ((1-b_j) + b_j \cdot X_j)
287$$
288
289
290then we have
291
292
293$$
294i=2_d=10_b;~
295pow_2(\overrightarrow{X}) = 1 \cdot X = X;~ deg=1
296\\
297i=3_d=11_b;~
298pow_3(\overrightarrow{X}) = X \cdot X = X^2;~ deg=2
299\\
300i=4_d=100_b;~
301pow_4(\overrightarrow{X}) = 1 \cdot 1 \cdot X = X;~ deg=1
302\\
303i=5_d=101_b;~
304pow_5(\overrightarrow{X}) = X \cdot 1 \cdot X = X^2;~ deg=2
305\\
306i=6_d=110_b;~
307pow_6(\overrightarrow{X}) = 1 \cdot X \cdot X = X^2;~ deg=2
308\\
309i=7_d=111_b;~
310pow_7(\overrightarrow{X}) = X \cdot X \cdot X = X^3;~ deg=3
311\\
312i=8_d=1000_b;~
313pow_8(\overrightarrow{X}) = 1 \cdot 1 \cdot 1 \cdot X = X;~ deg=1
314$$
315
316
317</div>
318
319<p>So, for example <span class="math inline">\(pow_{255}\)</span>, since <span class="math inline">\(i=255_d = 11111111_b\)</span>, will have degree <span class="math inline">\(8\)</span>. But <span class="math inline">\(pow_{256}\)</span>, since <span class="math inline">\(i=256_d= 100000000_b\)</span>, will have degree <span class="math inline">\(1\)</span>.
320<br></p>
321
322<p>Notice also that when <span class="math inline">\(X=0\)</span>, <span class="math inline">\(\overrightarrow{\eta}=\overrightarrow{\beta}\)</span>, so we&rsquo;re left with the original equation <span class="math inline">\(F(0)=\sum_{i\in[n]} pow_i(\textcolor{orange}{\overrightarrow{\beta}}) \textcolor{ForestGreen}{f_i(w)} = e\)</span>.</p></li>
323
324<li><p>P sends non constant coefficients <span class="math inline">\(F_1, \ldots, F_t\)</span> of <span class="math inline">\(F(X)\)</span> to V</p></li>
325
326<li><p>V sends a challenge <span class="math inline">\(\textcolor{magenta}{\alpha} \in^R \mathbb{F}\)</span></p></li>
327
328<li><p>P, V compute <span class="math inline">\(F(\textcolor{magenta}{\alpha}) = e + \sum_{i \in [t]} \textcolor{ForestGreen}{F_i} \textcolor{magenta}{\alpha^i}\)</span></p></li>
329
330<li><p>P, V compute <span class="math inline">\(\textcolor{orange}{\overrightarrow{\beta}}\textcolor{magenta}{^*} \in \mathbb{F}^t\)</span> where <span class="math inline">\(\textcolor{orange}{\beta_i \textcolor{magenta}{^*}} := \textcolor{orange}{\beta_i} + \textcolor{magenta}{\alpha} \cdot \textcolor{orange}{\delta^{2^{i-1}}}\)</span></p>
331
332<p>Notice that <span class="math inline">\(\textcolor{orange}{\overrightarrow{\beta}}\textcolor{magenta}{^*} = \textcolor{orange}{\overrightarrow{\beta}} + \textcolor{magenta}{\alpha} \cdot \textcolor{orange}{\overrightarrow{\delta}}\)</span>, is the same as <span class="math inline">\(\textcolor{orange}{\overrightarrow{\eta}}\)</span> with <span class="math inline">\(X=\textcolor{magenta}{\alpha}\)</span>.</p>
333
334<p>We have now a new randomized instance <span class="math inline">\((\textcolor{orange}{\overrightarrow{\beta}}\textcolor{magenta}{^*}, w, F(\alpha))\)</span>, for which the relation from the equation (1) holds:</p>
335<p><span class="math display">\[F(\textcolor{magenta}{\alpha}) = \sum_{i \in [n]} pow_i(\textcolor{orange}{\overrightarrow{\beta}}\textcolor{magenta}{^*}) \textcolor{ForestGreen}{f(w)}\]</span></p><p>since both sides of the equality represent some <span class="math inline">\(\textcolor{magenta}{re-randomized}\)</span> (eg. <span class="math inline">\(\textcolor{magenta}{\alpha}\)</span>) <span class="math inline">\(\textcolor{orange}{random~value}\)</span> (eg. <span class="math inline">\(\textcolor{orange}{\overrightarrow{\beta}, ~\overrightarrow{\delta}}\)</span>) combined with the <span class="math inline">\(\textcolor{ForestGreen}{evaluated~function}\)</span> (eg. <span class="math inline">\(\textcolor{ForestGreen}{f(w)}\)</span>).</p>
336
337<p>The following image tries to show how the previous steps relate:
338<img src="img/posts/protogalaxy/steps-3-7.png" style="width:80%;" /></p></li>
339
340<li><p>P computes the polynomial</p>
341<p><span class="math display">\[
342G(X) := \sum_{i \in [n]}
343pow_i(\overrightarrow{\beta^*}) \cdot f_i(L_0(X) w + \sum_{j \in [k]} L_j(X) w_j)
344\]</span></p>
345<div style="font-size:85%;">Here we make use of the <a href="#lemma-4.2">Lemma 4.2</a> to see that:</div>
346<p><span class="math display">\[
347G(X) := \sum_{i \in [n]}
348pow_i(\overrightarrow{\beta^*}) \cdot
349\underbrace{ f_i(\textcolor{SkyBlue}{L_0(X)} w }_{\textcolor{SkyBlue}{L_0(X)} \cdot f_i(w)} + \underbrace{ \sum_{j \in [k]} \textcolor{SkyBlue}{L_j(X)} w_j) }_{0}
350\\
351\text{\small{ notice that $f_i(w_j)=0 ~\forall j \in [k], i \in [n]$, thus $\sum_{j \in [k]} \textcolor{SkyBlue}{L_j(X)} \cdot f_i(w_j) = 0$ }}
352\\
353= \sum_{i \in [n]}
354\underbrace{ pow_i(\overrightarrow{\beta^*}) \cdot f_i(w) }_{F(\alpha) ~\text{from step 6}} \cdot \textcolor{SkyBlue}{L_0(X)} \pmod{Z(X)}
355\\
356= F(\alpha) \cdot \textcolor{SkyBlue}{L_0(X)} \pmod{Z(X)}
357\]</span></p>
358<div style="font-size:85%;">(where $Z(X)$ is the vanishing polynomial from the <a href="#lagrange-bases">preliminaries section</a>)</div>
359
360<p>which leads to the next step.</p></li>
361
362<li><p>P computes the polynomial <span class="math inline">\(K(X)\)</span> such that</p>
363<p><span class="math display">\[G(X) = F(\alpha) L_0(X) + Z(X) K(X)\]</span></p><p>(Recall, <span class="math inline">\(F(\alpha)\)</span> <em>&lsquo;contains&rsquo;</em> the <em>&rsquo;re-randomized&rsquo;</em> expression comming from <span class="math inline">\(\textcolor{magenta}{\alpha}\)</span> combined with <span class="math inline">\(\textcolor{orange}{\overrightarrow{\beta},~ \overrightarrow{\delta}}\)</span>, combined with <span class="math inline">\(\textcolor{ForestGreen}{f(w)}\)</span> from step 7).</p>
364
365<p><br>
366What we&rsquo;re using here is the same trick that we can find in Plonk, KZG commitments, and other known protocols (which, in fact was proposed by <a href="https://sci-hub.hkvisa.net/10.1137/050646445">Eli Ben-Sasson &amp; Madhu Sudan in 2008</a>).
367We&rsquo;re using the fact that if <span class="math inline">\(P(X)/Z(X)\)</span> leads to a polynomial (and not to a rational function) means that <span class="math inline">\(P(X)\)</span> is divisible by <span class="math inline">\(Z(X)\)</span> (the <em>vanishing polynomial</em>), which means that <span class="math inline">\(P(X)\)</span> vanishes over the evaluation domain. From another perspective, there exists a polynomial <span class="math inline">\(K(X)\)</span> such that <span class="math inline">\(P(X) = Z(X) \cdot K(X)\)</span>.
368Here we&rsquo;re using this fact with <span class="math inline">\(K(X)\)</span>, where if exists a <span class="math inline">\(K(X)\)</span> such that <span class="math inline">\(G(X)- F(\alpha)L_0(X) = Z(X)K(X)\)</span>, means that <span class="math inline">\(G(X)-F(\alpha)L_0(X)\)</span> vanishes over the evaluation domain.</p></li>
369
370<li><p>P sends the coefficients <span class="math inline">\(K_1, \ldots, K_t\)</span> of <span class="math inline">\(K(X)\)</span> to V</p></li>
371
372<li><p>V sends a challenge <span class="math inline">\(\gamma \in^R \mathbb{F}\)</span></p></li>
373
374<li><p>P, V compute</p>
375<p><span class="math display">\[e^* := F(\alpha) L_0(\gamma) + Z(\gamma) K(\gamma)\]</span></p></li>
376
377<li><p>P, V outputs the new folded committed instance</p>
378<p><span class="math display">\[\Phi^* = (\phi^*, \overrightarrow{\beta^*}, e^*)\]</span></p><p>where</p>
379<p><span class="math display">\[\phi^* = L_0(\gamma) \phi + \sum_{i \in [k]} L_i(\gamma) \cdot \phi_i\]</span></p><p>Recall from <a href="#lagrange-bases"><em>Lagrange bases</em> section</a>, that the intuition behind Lagrange bases usage is to <em>&lsquo;select&rsquo;</em> the different values associated to each <span class="math inline">\(L_i\)</span>. The idea here is that we are combinning the different instances into a new instance, while keeping them &lsquo;separated&rsquo; by the different <span class="math inline">\(L_i\)</span>.</p></li>
380
381<li><p>Additionally, P outputs the folded witness</p>
382<p><span class="math display">\[w^* = L_0(\gamma) w + \sum_{i \in [k]} L_i(\gamma) \cdot w_i\]</span></p></li>
383</ol>
384
385<p>To check that <span class="math inline">\((\Phi^*; w^*)\)</span> satisfies the relation we check that</p>
386<p><span class="math display">\[\sum_{i \in [n]} pow_i(\overrightarrow{\beta^*}) \cdot f_i(w^*) = e^*\]</span></p><p>As usual, this interactive protocol is converted into a non-interactive one through the Fiat-Shamir transformation.</p>
387
388<!--
389## Wrapup
390
391#### Folding a large amount of instances
392In the previous protocol, prover's costs are $O(k \log k)$, and verifier's costs are $O(k)$.
393ProtoGalaxy paper proposes an alternative construction of the previous scheme, for When we have a larger number of instances being fold.
394
395The main idea will be to replace the vanishing check by a Sumcheck over the boolean hypercube.
396
397
398We will put the running instance $w$ from the previous section together with the other witnesses, so 
399
400In step 8, we had
401
402$$
403\textcolor{gray}{
404G(X) := \sum_{i \in [n]} pow_i(\overrightarrow{\beta^*}) \cdot f_i \left( \sum_{j=0}^k \textcolor{SkyBlue}{L_j(X)} w_j \right)
405}
406$$
407
408Instead of the Lagrange bases, we will use the polynomial $eq(x, y)$.
409
410TODO explain eq poly, maybe in the preliminaries section
411
412
413so we will have
414
415
416$$
417G(t) :=
418eq(t, \overrightarrow{\delta^n})
419\sum_{i \in [n]} pow_i(\overrightarrow{\beta^*})
420\cdot f_i \left( \sum_{j'=0} \textcolor{SkyBlue}{eq(t, j')} w_j' \right)
421$$
422
423P and V run the SumCheck protocol over $G$.
424-->
425
426<h3>Conclusions</h3>
427
428<p>As mentioned initially, the <a href="https://eprint.iacr.org/2023/1106">ProtoGalaxy paper</a> is very well written and clear, so I highly recommend reading it to get the full explaination and proofs. Hopefully these notes might have provided some intuition behind the steps helping to follow the paper descriptions.</p>
429
430<p>One thing to mention is that we&rsquo;ve covered the version of the protocol presented in the section 4 of the paper, which has prover costs <span class="math inline">\(O(k \log k)\)</span> and verifier costs <span class="math inline">\(O(k)\)</span>. In section 5, the protocol is modified to obtain prover costs <span class="math inline">\(O(k)\)</span> and verifier costs <span class="math inline">\(O(\log k)\)</span>, at the expense of worse constant costs, which makes it more suitable for larger <span class="math inline">\(k\)</span> (more instances folded in each step). The main idea is by replacing the vanishing polynomial check with the SumCheck protocol, which internally works with similar equations that we had before, but replacing the Lagrange bases <span class="math inline">\(\textcolor{SkyBlue}{L_j(X)}\)</span> by the equivalent over the multilinar extension world <span class="math inline">\(\textcolor{SkyBlue}{eq(x, t)}\)</span>.</p>
431
432<p>Which for example, the equation that we had on the step 8:</p>
433<p><span class="math display">\[
434\textcolor{gray}{
435G(X) := \sum_{i \in [n]} pow_i(\overrightarrow{\beta^*}) \cdot f_i \left( \sum_{j=0}^k \textcolor{SkyBlue}{L_j(X)} w_j \right)
436}
437\]</span></p><p>is now replaced by</p>
438<p><span class="math display">\[
439G(t) :=
440eq(t, \overrightarrow{\delta^n})
441\sum_{i \in [n]} pow_i(\overrightarrow{\beta^*})
442\cdot f_i \left( \sum_{j'=0} \textcolor{SkyBlue}{eq(t, j')} w_j' \right)
443\]</span></p><p>Further details can be found at section 5 of the paper.</p>
444
445<p><br></p>
446
447<p>I&rsquo;m still discovering all the marvelous world of folding schemes, <a href="https://raw.githubusercontent.com/arnaucube/math/master/notes_nova.pdf">trying</a> to <a href="https://raw.githubusercontent.com/arnaucube/math/master/notes_hypernova.pdf">grasp</a> intuition across the different designs. One thing that will be interesting is to be able to benchmark on the practical side all the different folding schemes to see how they work in practice, and for example depending on the use case, evaluate for which threshold of <span class="math inline">\(k\)</span> makes sense to switch between them, and which <span class="math inline">\(k\)</span> makes sense for different use cases in the context of <a href="https://hackmd.io/@9MPvD9czTQS18zEjAERVAg/Hy-vKK04h">parallelizing folding</a>.</p>
448
449<p>In the repo <a href="https://github.com/arnaucube/protogalaxy-poc">https://github.com/arnaucube/protogalaxy-poc</a> you can find a proof of concept implementation of the ProtoGalaxy scheme described in this post.</p>
450
451    </div>
452
453    <footer style="text-align:center; margin-top:100px;margin-bottom:50px;">
454      <div class="container">
455        <br>
456        <a href="/blog">Go to main</a>
457        <br><br>
458        <div class="row">
459          <ul class="list-inline">
460            <li><a href="https://twitter.com/arnaucube"
461                   style="color:gray;text-decoration:none;"
462                   target="_blank">twitter.com/arnaucube</a>
463            </li>
464            <li><a href="https://github.com/arnaucube"
465                   style="color:gray;text-decoration:none;"
466                   target="_blank">github.com/arnaucube</a>
467            </li>
468          </ul>
469        </div>
470        <div class="row" style="display:inline-block;">
471          Blog made with <a href="http://github.com/arnaucube/blogo/"
472                            target="_blank" style="color: gray;text-decoration:none;">Blogo</a>
473        </div>
474      </div>
475    </footer>
476
477    <script>
478    </script>
479    <script src="js/external-links.js"></script>
480    <script>hljs.initHighlightingOnLoad();</script>
481    <script defer src="js/katex/katex.min.js"></script>
482    <script defer src="js/katex/auto-render.min.js"></script>
483    <script>
484      document.addEventListener("DOMContentLoaded", function() {
485        renderMathInElement(document.body, {
486          displayMode: false,
487          // customised options
488          // • auto-render specific keys, e.g.:
489          delimiters: [
490            {left: '$$', right: '$$', display: true},
491            {left: '$', right: '$', display: false},
492            {left: "\\[", right: "\\]", display: true},
493            {left: "\\(", right: "\\)", display: false},
494            {left: "\\begin{equation}", right: "\\end{equation}", display: true}
495          ],
496          // • rendering keys, e.g.:
497          throwOnError : true
498        });
499      });
500
501      ///
502      let theme = localStorage.getItem("theme");
503      if ((theme === "light-theme")||(theme==null)) {
504          theme = "light-theme";
505          document.getElementById("themeSwitcher").checked = false;
506      } else if (theme === "dark-theme") {
507          theme = "dark-theme";
508          document.getElementById("themeSwitcher").checked = true;
509      }
510      document.body.className = theme;
511      localStorage.setItem("theme", theme);
512
513      function switchTheme() {
514        theme = localStorage.getItem("theme");
515        if (theme === "light-theme") {
516          theme = "dark-theme";
517          document.getElementById("themeSwitcher").checked = true;
518        } else {
519          theme = "light-theme";
520          document.getElementById("themeSwitcher").checked = false;
521        }
522        document.body.className = theme;
523        localStorage.setItem("theme", theme);
524
525        console.log(theme);
526      }
527    </script>
528    <script>
529    function tagLinks(tagName) {
530      var tags = document.getElementsByTagName(tagName);
531      for (var i=0, hElem; hElem =  tags[i]; i++) {
532        if (hElem.parentNode.className=="row postThumb") {
533          continue;
534        }
535        hElem.id = hElem.innerHTML.toLowerCase().replace(" ", "-");
536        hElem.innerHTML = "<a style='color:black!important;' href='#"+hElem.id+"'>"+hElem.innerHTML+"</a>";
537      }
538    }
539    tagLinks("h2");
540    tagLinks("h3");
541    tagLinks("h4");
542    tagLinks("h5");
543    </script>
544    <script>
545function generateTOC(tocContainerId = "toc") {
546    const tocContainer = document.getElementById(tocContainerId);
547    if (!tocContainer) return;
548
549    const headings = document.querySelectorAll("h2, h3, h4, h5, h6");
550    if (!headings.length) return;
551
552    // Generate IDs if missing
553    headings.forEach((heading, index) => {
554        if (!heading.id) {
555            heading.id =
556                heading.textContent
557                    .trim()
558                    .toLowerCase()
559                    .replace(/[^\w\s-]/g, "")
560                    .replace(/\s+/g, "-") +
561                "-" +
562                index;
563        }
564    });
565
566    const toc = document.createElement("ul");
567    let currentLevel = 1;
568    let currentList = toc;
569    const stack = [toc];
570
571    headings.forEach((heading) => {
572        const level = parseInt(heading.tagName.substring(1), 10);
573
574        const li = document.createElement("li");
575        const a = document.createElement("a");
576
577        a.href = "#" + heading.id;
578        a.textContent = heading.textContent;
579
580        li.appendChild(a);
581
582        if (level > currentLevel) {
583            for (let i = currentLevel; i < level; i++) {
584                const nestedList = document.createElement("ul");
585
586                const lastLi =
587                    currentList.lastElementChild ||
588                    currentList.appendChild(document.createElement("ul"));
589
590                lastLi.appendChild(nestedList);
591
592                stack.push(nestedList);
593                currentList = nestedList;
594            }
595        } else if (level < currentLevel) {
596            for (let i = currentLevel; i > level; i--) {
597                stack.pop();
598            }
599            currentList = stack[stack.length - 1];
600        }
601
602        currentList.appendChild(li);
603        currentLevel = level;
604    });
605
606    tocContainer.innerHTML = "";
607    tocContainer.appendChild(toc);
608}
609
610document.addEventListener("DOMContentLoaded", () => {
611    generateTOC();
612});
613    </script>
614    <script src="js/mermaid.min.js"></script>
615
616  </body>
617</html>
618