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 from the ProtoGalaxy paper:
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
143The 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 [Héctor Masip](https://hecmas.github.io) showed me an actual proof of this lemma, which goes as follows:
144
145Recall from the [euclidean polynomial division](https://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor#Euclidean_division):
146
147> For $f(X), g(X) \in \mathbb{F}[X]$ with $\deg f \geq \deg g$, $\exists$ unique polynomials $q(X), r(X) \in \mathbb{F}[X]$ such that $f(X) = g(X) q(X) + r(X)$, with $0 \leq \deg r < \deg g$.
148
149Thus,
150
151$$f(\sum_{i=0}^k a_i \cdot L_i(X)) = Q(X) \cdot Z(X) + r(X)$$
152
153with $0 \leq \deg r < \deg z = k+1$.
154
155So, when evaluating at $a_j, ~\forall j=0, \ldots, k$,
156
157$$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)$$
158
159so $f(a_j)=r(a_j)$, therefore
160
161$$r(X) = \sum_{i=0}^k r(a_i) \cdot L_i(X) = \sum_{i=0}^k f(a_i) \cdot L_i(X)$$
162
163<div style="float:right;">
164
165$\square$
166
167</div>
168
169
170
171## ProtoGalaxy protocol
172The 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.
173
174<img src="img/posts/protogalaxy/folding-diagram.png" style="width:80%;" />
175
176#### Instances
177
178Let $(\phi; w)$ be our running instance, the witness is represented by $w$, and $\phi = cm(w)$ represents the committed witness.
179Additionally, we will have $k$ randomized instance pairs $( \{ \phi_i \}^k; \{ w_i \}^k )$.
180
181The 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)$).
182
183As we start folding instances, the folded instance must satisfy the relation
184
185$$
186\sum_{i \in [n]} pow_i(\overrightarrow{\beta}) f_i(w) = e
187$$
188
189where $pow_i$ is the function explained in the [preliminaries section](#preliminaries), and $f_i$ is the $i$-th value from evaluating $f(w)$.
190
191For 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$.
192
193#### Protocol
194We 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.
195
196For 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$.
197
198One 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.
199
200<br>
201*(Let P denote the Prover, and V the Verifier)*
202
203
2041. V sends a challenge $\delta \in^R \mathbb{F}$
2052. 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$
2063. P computes the polynomial
207
208 $$
209 F(X) := \sum_{i \in [n]} pow_i(
210 \underbrace{
211 \textcolor{orange}{\overrightarrow{\beta}} + X \cdot
212 \textcolor{orange}{\overrightarrow{\delta} }
213 }_\text{represent it by $\textcolor{orange}{\overrightarrow{\eta}}$}
214 ) \textcolor{ForestGreen}{f_i(w)}
215 \\
216 \text{\scriptsize{where $\textcolor{orange}{\overrightarrow{\eta}}$ is just an intermediate}}
217 \\
218 \text{\scriptsize{representation of the new random vector over $X$}}
219 \\
220 \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}} \}$}}
221 \\
222 = \sum_{i \in [n]}
223 pow_i(\textcolor{orange}{\overrightarrow{\eta}})
224 \textcolor{ForestGreen}{f_i(w)}
225 $$
226
227 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$.
228
229 <div style="font-size:85%;">
230
231 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 \}$,
232 recall that
233
234 $$
235 pow_i(\overrightarrow{X}) = \prod_{j \in [n]} ((1-b_j) + b_j \cdot X_j)
236 $$
237
238 then we have
239
240 $$
241 i=2_d=10_b;~
242 pow_2(\overrightarrow{X}) = 1 \cdot X = X;~ deg=1
243 \\
244 i=3_d=11_b;~
245 pow_3(\overrightarrow{X}) = X \cdot X = X^2;~ deg=2
246 \\
247 i=4_d=100_b;~
248 pow_4(\overrightarrow{X}) = 1 \cdot 1 \cdot X = X;~ deg=1
249 \\
250 i=5_d=101_b;~
251 pow_5(\overrightarrow{X}) = X \cdot 1 \cdot X = X^2;~ deg=2
252 \\
253 i=6_d=110_b;~
254 pow_6(\overrightarrow{X}) = 1 \cdot X \cdot X = X^2;~ deg=2
255 \\
256 i=7_d=111_b;~
257 pow_7(\overrightarrow{X}) = X \cdot X \cdot X = X^3;~ deg=3
258 \\
259 i=8_d=1000_b;~
260 pow_8(\overrightarrow{X}) = 1 \cdot 1 \cdot 1 \cdot X = X;~ deg=1
261 $$
262
263 </div>
264
265 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$.
266 <br>
267
268 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$.
269
270
2714. P sends non constant coefficients $F_1, \ldots, F_t$ of $F(X)$ to V
2725. V sends a challenge $\textcolor{magenta}{\alpha} \in^R \mathbb{F}$
2736. P, V compute $F(\textcolor{magenta}{\alpha}) = e + \sum_{i \in [t]} \textcolor{ForestGreen}{F_i} \textcolor{magenta}{\alpha^i}$
274
2757. 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}}}$
276
277 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}$.
278
279 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:
280
281 $$F(\textcolor{magenta}{\alpha}) = \sum_{i \in [n]} pow_i(\textcolor{orange}{\overrightarrow{\beta}}\textcolor{magenta}{^*}) \textcolor{ForestGreen}{f(w)}$$
282
283 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)}$).
284
285 The following image tries to show how the previous steps relate:
286 <img src="img/posts/protogalaxy/steps-3-7.png" style="width:80%;" />
287
2888. P computes the polynomial
289
290 $$
291 G(X) := \sum_{i \in [n]}
292 pow_i(\overrightarrow{\beta^*}) \cdot f_i(L_0(X) w + \sum_{j \in [k]} L_j(X) w_j)
293 $$
294
295 <div style="font-size:85%;">Here we make use of the <a href="#lemma-4.2">Lemma 4.2</a> to see that:</div>
296
297 $$
298 G(X) := \sum_{i \in [n]}
299 pow_i(\overrightarrow{\beta^*}) \cdot
300 \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}
301 \\
302 \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$ }}
303 \\
304 = \sum_{i \in [n]}
305 \underbrace{ pow_i(\overrightarrow{\beta^*}) \cdot f_i(w) }_{F(\alpha) ~\text{from step 6}} \cdot \textcolor{SkyBlue}{L_0(X)} \pmod{Z(X)}
306 \\
307 = F(\alpha) \cdot \textcolor{SkyBlue}{L_0(X)} \pmod{Z(X)}
308 $$
309
310 <div style="font-size:85%;">(where $Z(X)$ is the vanishing polynomial from the <a href="#lagrange-bases">preliminaries section</a>)</div>
311
312 which leads to the next step.
313
3149. P computes the polynomial $K(X)$ such that
315
316 $$G(X) = F(\alpha) L_0(X) + Z(X) K(X)$$
317
318 (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).
319
320 <br>
321 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)).
322 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)$.
323 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.
324
32510. P sends the coefficients $K_1, \ldots, K_t$ of $K(X)$ to V
32611. V sends a challenge $\gamma \in^R \mathbb{F}$
32712. P, V compute
328
329 $$e^* := F(\alpha) L_0(\gamma) + Z(\gamma) K(\gamma)$$
330
33113. P, V outputs the new folded committed instance
332
333 $$\Phi^* = (\phi^*, \overrightarrow{\beta^*}, e^*)$$
334
335 where
336
337 $$\phi^* = L_0(\gamma) \phi + \sum_{i \in [k]} L_i(\gamma) \cdot \phi_i$$
338
339 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$.
340
34114. Additionally, P outputs the folded witness
342
343 $$w^* = L_0(\gamma) w + \sum_{i \in [k]} L_i(\gamma) \cdot w_i$$
344
345
346To check that $(\Phi^*; w^*)$ satisfies the relation we check that
347
348$$\sum_{i \in [n]} pow_i(\overrightarrow{\beta^*}) \cdot f_i(w^*) = e^*$$
349
350
351As usual, this interactive protocol is converted into a non-interactive one through the Fiat-Shamir transformation.
352
353<!--
354## Wrapup
355
356#### Folding a large amount of instances
357In the previous protocol, prover's costs are $O(k \log k)$, and verifier's costs are $O(k)$.
358ProtoGalaxy paper proposes an alternative construction of the previous scheme, for When we have a larger number of instances being fold.
359
360The main idea will be to replace the vanishing check by a Sumcheck over the boolean hypercube.
361
362
363We will put the running instance $w$ from the previous section together with the other witnesses, so
364
365In step 8, we had
366
367$$
368\textcolor{gray}{
369G(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)
370}
371$$
372
373Instead of the Lagrange bases, we will use the polynomial $eq(x, y)$.
374
375TODO explain eq poly, maybe in the preliminaries section
376
377
378so we will have
379
380
381$$
382G(t) :=
383eq(t, \overrightarrow{\delta^n})
384\sum_{i \in [n]} pow_i(\overrightarrow{\beta^*})
385\cdot f_i \left( \sum_{j'=0} \textcolor{SkyBlue}{eq(t, j')} w_j' \right)
386$$
387
388P and V run the SumCheck protocol over $G$.
389-->
390
391### Conclusions
392As 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.
393
394One 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)}$.
395
396Which for example, the equation that we had on the step 8:
397
398$$
399\textcolor{gray}{
400G(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)
401}
402$$
403
404is now replaced by
405
406$$
407G(t) :=
408eq(t, \overrightarrow{\delta^n})
409\sum_{i \in [n]} pow_i(\overrightarrow{\beta^*})
410\cdot f_i \left( \sum_{j'=0} \textcolor{SkyBlue}{eq(t, j')} w_j' \right)
411$$
412
413Further details can be found at section 5 of the paper.
414
415<br>
416
417I'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).
418
419In the repo https://github.com/arnaucube/protogalaxy-poc you can find a proof of concept implementation of the ProtoGalaxy scheme described in this post.