arnaucube.com/blogo-input/posts/protogalaxy.md
blogo-input/posts/protogalaxy.mdRaw
1# Notes on ProtoGalaxy
2*2023-08-20*
3
4> **Note**: I'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.
5
6The idea of these notes is to provide some extra intuition on [ProtoGalaxy paper](https://eprint.iacr.org/2023/1106).
7The paper is very well written and exposes the ideas very clearly, so it's worth to check directly the paper instead of these notes.
8
9I make use of $\textcolor{blue}{c}\textcolor{magenta}{o}\textcolor{orange}{l}\textcolor{cyan}{o}\textcolor{green}{u}\textcolor{red}{r}\textcolor{pink}{s}$ to try to relate the different parameters across the scheme.
10
11ProtoGalaxy is a *folding scheme* which iterates on ideas from [ProtoStar paper](https://eprint.iacr.org/2023/620) (here you can find [Geometry's post](https://geometry.xyz/notebook/paper-speedrun-protostar) overviewing its main results and techniques).
12
13For an introduction to *folding schemes* I highly recommend [this talk (at 1:46)](https://youtu.be/IzLTpKWt-yg?t=6367) by [Carlos Perez](https://twitter.com/CPerezz19).
14
15I would like to thank [Liam Eagen](https://twitter.com/LiamEagen) and [Ariel Gabizon](https://twitter.com/rel_zeta_tech) for their kind explanations on the scheme.
16Also thanks to [Onur](https://twitter.com/kiliconu) for comments and corrections.
17
18
19<div style="margin-left:20%;" >
20
21<img src="img/posts/protogalaxy/protogalaxies-colliding.jpg"/>
22
23<br>
24(img: protogalaxies colliding, <a href="https://en.wikipedia.org/wiki/File:Stellar_Fireworks_Finale.jpg">from Wikipedia</a>)
25
26</div>
27
28
29## Preliminaries
30Before jumping into the protocol itself, let's overview some building blocks first.
31
32
33#### $pow_i$
34In the protocol we need the powers of a random value. We use the $pow_i$ function to store and operate only $log(n)$ entries instead of $n$.
35
36$pow_i$ is a $t$-variate polynomial such that
37
38$$
39% pow_i(X_1, \ldots, X_t) = \prod_{i \in [n]} ((1-b_j) + b_j \cdot X^{2^j})
40pow_i(X) = \prod_{i \in [n]} ((1-b_j) + b_j \cdot X^{2^j})
41$$
42
43where $b_j$ is the binary decomposition of $n$, such that $n = \sum 2^j$.
44
45In our case, we will have $\overrightarrow{X}$ being $\overrightarrow{\beta} = \{\beta^{2^i} \}_0^{t-1} = (\beta, \beta^2, \beta^4, \ldots, \beta^{2^{t-1}})$, thus
46
47$$
48pow_i(\overrightarrow{\beta}) = \prod_{j \in [n]} ((1-b_j) + b_j \cdot \beta_j)
49$$
50
51which, basically is a way to have $pow_i(\overrightarrow{\beta}) = \beta^i$, but storing just $t$ betas, to actually represent $2^t$ of them, so we work with $log$ of the total amount actually used.
52
53
54So, for example,
55
56$$
57 i=2_d=10_b;~
58 pow_2(\overrightarrow{\beta}) =
59 \underbrace{((1-0) + 0 \cdot \beta)}_{1}
60 \cdot \underbrace{((1-1) + 1 \cdot \beta^2)}_{\beta^2}
61 = \beta^2
62 \\
63 i=3_d=11_b;~
64 pow_3(\overrightarrow{\beta}) =
65 \underbrace{((1-1) + 1 \cdot \beta)}_{\beta}
66 \cdot \underbrace{((1-1) + 1 \cdot \beta^2)}_{\beta^2}
67 = \beta^3
68 \\
69 i=4_d=100_b;~
70 pow_4(\overrightarrow{\beta}) =
71 \underbrace{((1-0) + 0 \cdot \beta)}_{1}
72 \cdot \underbrace{((1-0) + 0 \cdot \beta^2)}_{1}
73 \cdot \underbrace{((1-1) + 1 \cdot \beta^4)}_{\beta^4}
74 = \beta^4
75 \\
76 i=5_d=101_b;~
77 pow_5(\overrightarrow{\beta}) =
78 \underbrace{((1-1) + 1 \cdot \beta)}_{\beta}
79 \cdot \underbrace{((1-0) + 0 \cdot \beta^2)}_{1}
80 \cdot \underbrace{((1-1) + 1 \cdot \beta^4)}_{\beta^4}
81 = \beta^5
82$$
83
84#### Lagrange bases
85
86Let $\omega$ denote a root of unity, such that $\omega^N=1$, and set $\mathbb{H}=\{1, \omega, \omega^2, \ldots, \omega^{N-1}\}$.
87
88Lagrange 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
89
90$$L_j(\omega^i)=
91\begin{cases}
92 &1 ~\text{if}~ i=j\\
93 &0 ~\text{otherwise}
94\end{cases}
95$$
96
97In other words, when we're evaluating the Lagrange base $j$ at $w^i$, the evaluation is going to be $1$ when $i=j$, and $0$ in all the other cases.
98
99To get a bit of more intuition here, let's represent this visually:
100
101
102<div>
103
104<img src="img/posts/protogalaxy/lagrange-basis-intuition.png" style="width:40%;display:inline-block;" />
105
106<div style="width:50%; display:inline-block;">
107The 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$.
108
109While, when we evaluate $L_2(X)$ at for example $\omega^1$, we will obtain a $0$, thus the result will be a $0$.
110
111</div>
112</div>
113
114
115Let the vanishing polynomial of $\mathbb{H}$ be $Z(X)=\prod_{i=0}^{N-1} (X - \omega^i) = X^N -1$.
116
117
118#### Function $f(X)$
119Assume we have a function $f(X)$ which when evaluated at a valid witness is equal to 0.
120
121For example, in the R1CS case, this would be (for given matrices $A, B, C \in \mathbb{F}^{m \times m}$ representing our constraints),
122
123<!--$$f(X)= \sum_{i=0}^n A(X_i) \cdot B(X_i) - C(X_i)$$-->
124
125$$f(X)= A \cdot X \circ B \cdot X - C \cdot X $$
126
127<!-- $$f(X)= \sum_{i=0}^n A(X_i) \cdot B(X_i) - C(X_i)$$ -->
128
129where $f(w)=0^n$ if satisfied for a valid witness $w \in \mathbb{F}^n$.
130
131Our goal will be to prove that we have folded various instantiations of valid witnesses and that they fulfill the check of $f(w)=0^n$.
132
133
134#### Lemma 4.2
135The following lemma is proven in the ProtoGalaxy paper, but for the current overview we will stick just to its results. The details can be found in the paper itself.
136
137> **Lemma 4.2:** Fix any polynomial $f(X) \in \mathbb{F}[X]$ and $a_0, \ldots, a_k \in \mathbb{F}$. There exists $Q(X) \in \mathbb{F}[X]$ such that
138>
139> $$
140> 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)
141> $$
142
143
144## ProtoGalaxy protocol
145The main idea of this scheme, is to be able to fold $k+1$ instances that satisfy the relation, producing a single *folded instance* which still satisfies the relation.
146
147<img src="img/posts/protogalaxy/folding-diagram.png" style="width:80%;" />
148
149#### Instances
150
151Let $(\phi; w)$ be our running instance, the witness is represented by $w$, and $\phi = cm(w)$ represents the committed witness.
152Additionally, we will have $k$ randomized instance pairs $( \{ \phi_i \}^k; \{ w_i \}^k )$.
153
154The running instance is paired with two more parameters, so the complete running instance consists of $((\phi, \overrightarrow{\beta}, e); w)$, where $e$ is the 'error' term and $\overrightarrow{\beta} \in^R \mathbb{F}^t$ (where $t=\log(n)$).
155
156As we start folding instances, the folded instance must satisfy the relation
157
158$$
159\sum_{i \in [n]} pow_i(\overrightarrow{\beta}) f_i(w) = e
160$$
161
162where $pow_i$ is the function explained in the [preliminaries section](#preliminaries), and $f_i$ is the $i$-th value from evaluating $f(w)$.
163
164For the first instance (before folding) $e=0$, which we can see that matches $\sum_{i \in [n]} pow_i(\overrightarrow{\beta}) f_i(w) = 0$, since $f(w)=0^n$ for a valid $w$.
165
166#### Protocol
167We want a way for the Prover to fold $k+1$ instances into a single one, combining them while ensuring that they satisfy the relation by showing that $f(w_i)=0$ for all $k+1$ instances.
168
169For doing so, we could just add all the instances naively, but they could cancel each other giving $0$ when evaluated at the different $w_i$, even when individually don't evaluate at $0$.
170
171One way to combine the instances is through making use of a random linear combination (as done in Nova and ProtoStar), but when combining $k$ 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 'separated' while being combined in the same expression.
172
173<br>
174*(Let P denote the Prover, and V the Verifier)*
175
176
1771. V sends a challenge $\delta \in^R \mathbb{F}$
1782. P, V compute $\overrightarrow{\delta} = \{\delta^{2^i} \}_0^{t-1} = (\delta, \delta^2, \delta^4, \ldots, \delta^{2^{t-1}}) \in \mathbb{F}^t$
1793. P computes the polynomial
180
181 $$
182 F(X) := \sum_{i \in [n]} pow_i(
183 \underbrace{
184 \textcolor{orange}{\overrightarrow{\beta}} + X \cdot
185 \textcolor{orange}{\overrightarrow{\delta} }
186 }_\text{represent it by $\textcolor{orange}{\overrightarrow{\eta}}$}
187 ) \textcolor{ForestGreen}{f_i(w)}
188 \\
189 \text{\scriptsize{where $\textcolor{orange}{\overrightarrow{\eta}}$ is just an intermediate}}
190 \\
191 \text{\scriptsize{representation of the new random vector over $X$}}
192 \\
193 \text{\scriptsize{where $\overrightarrow{\eta}=\{ \beta+X \delta, \beta^2 + X \delta^2, \beta^4 +X \delta^4, \ldots, \beta^{2^{t-1}} + X \delta^{2^{t-1}} \}$}}
194 \\
195 = \sum_{i \in [n]}
196 pow_i(\textcolor{orange}{\overrightarrow{\eta}})
197 \textcolor{ForestGreen}{f_i(w)}
198 $$
199
200 Notice that each $pow_i(\textcolor{orange}{\overrightarrow{\eta}})$ will be a polynomial of degree equal to the number of positive bits in the binary representation of $i$.
201
202 <div style="font-size:85%;">
203
204 In 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 \}$,
205 recall that
206
207 $$
208 pow_i(\overrightarrow{X}) = \prod_{j \in [n]} ((1-b_j) + b_j \cdot X_j)
209 $$
210
211 then we have
212
213 $$
214 i=2_d=10_b;~
215 pow_2(\overrightarrow{X}) = 1 \cdot X = X;~ deg=1
216 \\
217 i=3_d=11_b;~
218 pow_3(\overrightarrow{X}) = X \cdot X = X^2;~ deg=2
219 \\
220 i=4_d=100_b;~
221 pow_4(\overrightarrow{X}) = 1 \cdot 1 \cdot X = X;~ deg=1
222 \\
223 i=5_d=101_b;~
224 pow_5(\overrightarrow{X}) = X \cdot 1 \cdot X = X^2;~ deg=2
225 \\
226 i=6_d=110_b;~
227 pow_6(\overrightarrow{X}) = 1 \cdot X \cdot X = X^2;~ deg=2
228 \\
229 i=7_d=111_b;~
230 pow_7(\overrightarrow{X}) = X \cdot X \cdot X = X^3;~ deg=3
231 \\
232 i=8_d=1000_b;~
233 pow_8(\overrightarrow{X}) = 1 \cdot 1 \cdot 1 \cdot X = X;~ deg=1
234 $$
235
236 </div>
237
238 So, for example $pow_{255}$, since $i=255_d = 11111111_b$, will have degree $8$. But $pow_{256}$, since $i=256_d= 100000000_b$, will have degree $1$.
239 <br>
240
241 Notice also that when $X=0$, $\overrightarrow{\eta}=\overrightarrow{\beta}$, so we're left with the original equation $F(0)=\sum_{i\in[n]} pow_i(\textcolor{orange}{\overrightarrow{\beta}}) \textcolor{ForestGreen}{f_i(w)} = e$.
242
243
2444. P sends non constant coefficients $F_1, \ldots, F_t$ of $F(X)$ to V
2455. V sends a challenge $\textcolor{magenta}{\alpha} \in^R \mathbb{F}$
2466. P, V compute $F(\textcolor{magenta}{\alpha}) = e + \sum_{i \in [t]} \textcolor{ForestGreen}{F_i} \textcolor{magenta}{\alpha^i}$
247
2487. P, V compute $\textcolor{orange}{\overrightarrow{\beta}}\textcolor{magenta}{^*} \in \mathbb{F}^t$ where $\textcolor{orange}{\beta_i \textcolor{magenta}{^*}} := \textcolor{orange}{\beta_i} + \textcolor{magenta}{\alpha} \cdot \textcolor{orange}{\delta^{2^{i-1}}}$
249
250 Notice that $\textcolor{orange}{\overrightarrow{\beta}}\textcolor{magenta}{^*} = \textcolor{orange}{\overrightarrow{\beta}} + \textcolor{magenta}{\alpha} \cdot \textcolor{orange}{\overrightarrow{\delta}}$, is the same as $\textcolor{orange}{\overrightarrow{\eta}}$ with $X=\textcolor{magenta}{\alpha}$.
251
252 We have now a new randomized instance $(\textcolor{orange}{\overrightarrow{\beta}}\textcolor{magenta}{^*}, w, F(\alpha))$, for which the relation from the equation (1) holds:
253
254 $$F(\textcolor{magenta}{\alpha}) = \sum_{i \in [n]} pow_i(\textcolor{orange}{\overrightarrow{\beta}}\textcolor{magenta}{^*}) \textcolor{ForestGreen}{f(w)}$$
255
256 since both sides of the equality represent some $\textcolor{magenta}{re-randomized}$ (eg. $\textcolor{magenta}{\alpha}$) $\textcolor{orange}{random~value}$ (eg. $\textcolor{orange}{\overrightarrow{\beta}, ~\overrightarrow{\delta}}$) combined with the $\textcolor{ForestGreen}{evaluated~function}$ (eg. $\textcolor{ForestGreen}{f(w)}$).
257
258 The following image tries to show how the previous steps relate:
259 <img src="img/posts/protogalaxy/steps-3-7.png" style="width:80%;" />
260
2618. P computes the polynomial
262
263 $$
264 G(X) := \sum_{i \in [n]}
265 pow_i(\overrightarrow{\beta^*}) \cdot f_i(L_0(X) w + \sum_{j \in [k]} L_j(X) w_j)
266 $$
267
268 <div style="font-size:85%;">Here we make use of the <a href="#lemma-4.2">Lemma 4.2</a> to see that:</div>
269
270 $$
271 G(X) := \sum_{i \in [n]}
272 pow_i(\overrightarrow{\beta^*}) \cdot
273 \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}
274 \\
275 \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$ }}
276 \\
277 = \sum_{i \in [n]}
278 \underbrace{ pow_i(\overrightarrow{\beta^*}) \cdot f_i(w) }_{F(\alpha) ~\text{from step 6}} \cdot \textcolor{SkyBlue}{L_0(X)} \pmod{Z(X)}
279 \\
280 = F(\alpha) \cdot \textcolor{SkyBlue}{L_0(X)} \pmod{Z(X)}
281 $$
282
283 <div style="font-size:85%;">(where $Z(X)$ is the vanishing polynomial from the <a href="#lagrange-bases">preliminaries section</a>)</div>
284
285 which leads to the next step.
286
2879. P computes the polynomial $K(X)$ such that
288
289 $$G(X) = F(\alpha) L_0(X) + Z(X) K(X)$$
290
291 (Recall, $F(\alpha)$ *'contains'* the *'re-randomized'* expression comming from $\textcolor{magenta}{\alpha}$ combined with $\textcolor{orange}{\overrightarrow{\beta},~ \overrightarrow{\delta}}$, combined with $\textcolor{ForestGreen}{f(w)}$ from step 7).
292
293 <br>
294 What we'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 [Eli Ben-Sasson & Madhu Sudan in 2008](https://sci-hub.hkvisa.net/10.1137/050646445)).
295 We're using the fact that if $P(X)/Z(X)$ leads to a polynomial (and not to a rational function) means that $P(X)$ is divisible by $Z(X)$ (the *vanishing polynomial*), which means that $P(X)$ vanishes over the evaluation domain. From another perspective, there exists a polynomial $K(X)$ such that $P(X) = Z(X) \cdot K(X)$.
296 Here we're using this fact with $K(X)$, where if exists a $K(X)$ such that $G(X)- F(\alpha)L_0(X) = Z(X)K(X)$, means that $G(X)-F(\alpha)L_0(X)$ vanishes over the evaluation domain.
297
29810. P sends the coefficients $K_1, \ldots, K_t$ of $K(X)$ to V
29911. V sends a challenge $\gamma \in^R \mathbb{F}$
30012. P, V compute
301
302 $$e^* := F(\alpha) L_0(\gamma) + Z(\gamma) K(\gamma)$$
303
30413. P, V outputs the new folded committed instance
305
306 $$\Phi^* = (\phi^*, \overrightarrow{\beta^*}, e^*)$$
307
308 where
309
310 $$\phi^* = L_0(\gamma) \phi + \sum_{i \in [k]} L_i(\gamma) \cdot \phi_i$$
311
312 Recall from [*Lagrange bases* section](#lagrange-bases), that the intuition behind Lagrange bases usage is to *'select'* the different values associated to each $L_i$. The idea here is that we are combinning the different instances into a new instance, while keeping them 'separated' by the different $L_i$.
313
31414. Additionally, P outputs the folded witness
315
316 $$w^* = L_0(\gamma) w + \sum_{i \in [k]} L_i(\gamma) \cdot w_i$$
317
318
319To check that $(\Phi^*; w^*)$ satisfies the relation we check that
320
321$$\sum_{i \in [n]} pow_i(\overrightarrow{\beta^*}) \cdot f_i(w^*) = e^*$$
322
323
324As usual, this interactive protocol is converted into a non-interactive one through the Fiat-Shamir transformation.
325
326<!--
327## Wrapup
328
329#### Folding a large amount of instances
330In the previous protocol, prover's costs are $O(k \log k)$, and verifier's costs are $O(k)$.
331ProtoGalaxy paper proposes an alternative construction of the previous scheme, for When we have a larger number of instances being fold.
332
333The main idea will be to replace the vanishing check by a Sumcheck over the boolean hypercube.
334
335
336We will put the running instance $w$ from the previous section together with the other witnesses, so
337
338In step 8, we had
339
340$$
341\textcolor{gray}{
342G(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)
343}
344$$
345
346Instead of the Lagrange bases, we will use the polynomial $eq(x, y)$.
347
348TODO explain eq poly, maybe in the preliminaries section
349
350
351so we will have
352
353
354$$
355G(t) :=
356eq(t, \overrightarrow{\delta^n})
357\sum_{i \in [n]} pow_i(\overrightarrow{\beta^*})
358\cdot f_i \left( \sum_{j'=0} \textcolor{SkyBlue}{eq(t, j')} w_j' \right)
359$$
360
361P and V run the SumCheck protocol over $G$.
362-->
363
364### Conclusions
365As mentioned initially, the [ProtoGalaxy paper](https://eprint.iacr.org/2023/1106) 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.
366
367One thing to mention is that we've covered the version of the protocol presented in the section 4 of the paper, which has prover costs $O(k \log k)$ and verifier costs $O(k)$. In section 5, the protocol is modified to obtain prover costs $O(k)$ and verifier costs $O(\log k)$, at the expense of worse constant costs, which makes it more suitable for larger $k$ (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 $\textcolor{SkyBlue}{L_j(X)}$ by the equivalent over the multilinar extension world $\textcolor{SkyBlue}{eq(x, t)}$.
368
369Which for example, the equation that we had on the step 8:
370
371$$
372\textcolor{gray}{
373G(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)
374}
375$$
376
377is now replaced by
378
379$$
380G(t) :=
381eq(t, \overrightarrow{\delta^n})
382\sum_{i \in [n]} pow_i(\overrightarrow{\beta^*})
383\cdot f_i \left( \sum_{j'=0} \textcolor{SkyBlue}{eq(t, j')} w_j' \right)
384$$
385
386Further details can be found at section 5 of the paper.
387
388<br>
389
390I'm still discovering all the marvelous world of folding schemes, [trying](https://raw.githubusercontent.com/arnaucube/math/master/notes_nova.pdf) to [grasp](https://raw.githubusercontent.com/arnaucube/math/master/notes_hypernova.pdf) 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 $k$ makes sense to switch between them, and which $k$ makes sense for different use cases in the context of [parallelizing folding](https://hackmd.io/@9MPvD9czTQS18zEjAERVAg/Hy-vKK04h).
391
392In the repo https://github.com/arnaucube/protogalaxy-poc you can find a proof of concept implementation of the ProtoGalaxy scheme described in this post.