math/notes_caulk.tex
notes_caulk.texRaw
1\documentclass{article}
2\usepackage[utf8]{inputenc}
3\usepackage{amsfonts}
4\usepackage{amsthm}
5\usepackage{amsmath}
6\usepackage{enumerate}
7\usepackage{hyperref}
8% \hypersetup{
9% colorlinks,
10% citecolor=blue,
11% filecolor=blue,
12% linkcolor=black,
13% urlcolor=blue
14% }
15\usepackage{xcolor}
16
17% prevent warnings of underfull \hbox:
18\usepackage{etoolbox}
19\apptocmd{\sloppy}{\hbadness 4000\relax}{}{}
20
21\theoremstyle{definition}
22\newtheorem{definition}{Def}[section]
23\newtheorem{theorem}[definition]{Thm}
24
25% custom lemma environment to set custom numbers
26\newtheorem{innerlemma}{Lemma}
27\newenvironment{lemma}[1]
28{\renewcommand\theinnerlemma{#1}\innerlemma}
29{\endinnerlemma}
30
31
32\title{Notes on Caulk and Caulk+}
33\author{arnaucube}
34\date{February 2023}
35
36\begin{document}
37
38\maketitle
39
40\begin{abstract}
41 Notes taken while reading about Caulk \cite{cryptoeprint:2022/621} and Caulk+ \cite{cryptoeprint:2022/957}.
42
43 Usually while reading papers I take handwritten notes, this document contains some of them re-written to $LaTeX$.
44
45 The notes are not complete, don't include all the steps neither all the proofs.
46\end{abstract}
47
48\tableofcontents
49
50\section{Preliminaries}
51
52\subsection{Lagrange Polynomials and Roots of Unity}
53
54Let $\omega$ denote a root of unity, such that $\omega^N=1$. Set $\mathbb{H}=\{1, \omega, \omega^2, \ldots, \omega^{N^{-1}}\}$.
55
56Let the $i^{th}$ Lagrange polynomial be $\lambda_i(X)=\prod_{s\neq i-1} \frac{X-\omega^s}{\omega^{i-1} -\omega}$.
57
58Notice that $\lambda_i(\omega^{i-1})=1$ and $\lambda_i(w^j)=0,~\forall j\neq i-1$.
59
60Let the vanishing polynomial of $\mathbb{H}$ be $z_H(X)=\prod_{i=0}^{N-1} (X - \omega^i) = X^N -1$.
61
62\subsection{KZG Commitments}
63KZG as a Vector Commitment.
64
65We have vector $\overrightarrow{c}=\{c_i\}_1^n$, which can be interpolated into $C(X)$ through Lagrange polynomials $\{ \lambda_i(X) \}$:
66$$C(X) = \sum^n_{i=1} c_i \cdot \lambda_i(X)$$
67so, $C(\omega^{i-1})=c_i$.
68
69Commitment:
70$$C = [C(X)]_1 = \sum^n_{i=1} c_i \cdot [\lambda_i(X)]_1$$
71
72Proof of \textbf{opening for single value} $v$ at position $i$:
73
74$$Q(X) = \frac{C(X) - v}{X-\omega^{i-1}}$$
75
76$$\pi_{KZG} = Q =[Q(X)]_1$$
77
78Verification:
79$$e(C - [v]_1, [1]_2) = e(\pi_{KZG},~[X-\omega^{i-1}]_2)$$
80unfold
81$$e([C(X)]_1 - [v]_1, [1]_2) = e([Q(X)]_1,~[X-\omega^{i-1}]_2)$$
82$$C(X) - v = Q(X) \cdot (X-\omega^{i-1}) \Longrightarrow Q(X) = \frac{C(X) - v}{X-\omega^{i-1}}$$
83
84
85Proof of \textbf{opening for a subset} of positions $I \subset [N]$:
86
87$[H_I]_1$ such that for
88$$C_I(X) = \sum_{i \in I} c_i \cdot \tau_i(X)$$
89$$z_I(X) = \prod_{i \in I} (X - \omega^{i-1})$$
90
91for $\{ \tau_i(X) \}_{i \in I}$ being the Lagrange interpolation polynomials over $\mathbb{H}_I = \{\omega^{i-1}\}_{i \in I}$.
92\emph{(recall, $z_H(X)=\prod_{i=0}^{N-1} (X - \omega^i) = X^N -1$))}
93
94
95$H_I(X)$ can be computed by
96$$H_I(X) = \frac{C(X) - C_I(X)}{z_I(X)}$$
97
98So, prover commits to $C_I(X)$ with $C_I = [C_I(X)]_1$, and computes $\pi_{KZG}$:
99$$\pi_{KZG} = H_I = [H_I(X)]_1$$
100
101Then, verification checks:
102$$e(C - C_I, [1]_2) = e(\pi_{KZG}, [z_I(X)]_2)$$
103unfold
104$$e([C(X)]_1 - [C_I(X)]_1, [1]_2) = e([H_I(X)]_1, [z_I(X)]_2)$$
105$$C(X) - C_I(X) = H_I(X) \cdot z_I(X)$$
106$$C(X) - C_I(X) = \frac{C(X)-C_I(X)}{z_I(X)} \cdot z_I(X)$$
107
108
109
110\subsection{Pedersen Commitments}\label{sec:pedersen}
111Commitment
112$$cm = v [1]_1 + r [h]_1 = [v + hr]_1$$
113
114Prove knowledge of $v,~r$, Verifier sends challenge $\{s_1, s_2\}$. Prover computes:
115$$R = s_1 [1]_1 + s_2 [h]_1 = [s_1 + h s_2]_1$$
116$$c= H(cm, R)$$
117$$t_1 = s_1 + v c, ~~ t_2=s_2 + r c$$
118
119Verification:
120$$R + c \cdot cm == t_1 [1]_1 + t_2 [h]_1$$
121
122unfold:
123$$R + c \cdot cm == t_1 [1]_1 + t_2 [h]_1 = [t_1 + h t_2]$$
124$$[s_1 + h s_2]_1 + c \cdot [v + hr]_1 == [s_1 + vc + h(s_2 + rc)]_1$$
125$$[s_1 + h s_2 + cv + rch]_1 == [s_1 + vc + h s_2 + rch]_1$$
126
127
128\section{Caulk}
129\subsection{Blinded Evaluation}
130Main idea: combine KZG commitments with Pedersen commitments to prove knowledge of a value $v$ which Pedersen commitment is committed in the KZG commitment.
131
132Let $C(X) = \sum^N_{i=1} c_i \lambda_i(X)$, where $\overrightarrow{c} = \{c_i\}_{i \in I}$. In normal KZG, prover would compute $Q(X)=\frac{C(X)-v}{X-\omega^{i-1}}$, and send $[Q(X)]_1$ as proof. We will obfuscate the commitment:
133
134rand $a \in \mathbb{F}$, blind commit to $z(X)=aX - b = a(X - \omega^{i-1})$, where $\omega^{i-1}=b/a$. Denote by $[z]_2$ the commitment to $[z(X)]_2$.
135
136Prover computes:
137\begin{enumerate}[i.]
138 \item $\pi_{ped}$, Pedersen proof that $cm$ is from $v, r$ (section \ref{sec:pedersen})
139 \item $\pi_{unity}$ (see \ref{sec:pi-unity})
140 \item For random $s$ computes:
141 $$T(X)=\frac{Q(X)}{a} + hs \longrightarrow [T]_1=[T(X)]_1$$
142 $$S(X) = -r - s \cdot z(X) \longrightarrow [S]_2 = [S(X)]_2$$
143\end{enumerate}
144
145i, ii, iii defines the \emph{zk proof of membership}, which proves that $(v, r)$ is a opening of $cm$, and $v$ opens $C$ at $\omega^{i-1}$.
146
147Verifier checks proofs $\pi_{ped},~\pi_{unity}$ (i, ii), and checks
148$$e(C - cm, [1]_2) == e([T]_1, [z]_2) + e([h]_1, [S]_2)$$
149
150unfold:
151\begin{align*}
152 C(X) - cm &== T(X) \cdot z(X) + h \cdot S(X) \\
153 C(X) - v - hr &== (\frac{Q(X)}{a} + s h) \cdot z(X) + h (-r -s \cdot z(X)) \\
154 C(X) - v &== hr + (\frac{Q(X)}{a}) z(X) + sh \cdot z(X) - hr - sh \cdot z(X) \\
155 C(X) - v &== \frac{Q(X)}{a} \cdot z(X) \\
156 C(X) - v &== \frac{Q(X)}{a} \cdot a(X-\omega^{i-1}) \\
157 C(X) -v &== Q(X) \cdot (X - \omega^{i-1})
158\end{align*}
159Which matches with the definition of $Q(X) = \frac{C(X) - v}{X-\omega^{i-1}}$.
160
161\subsubsection{\texorpdfstring{Correct computation of $z(x)$, $\pi_{unity}$}%
162 {Correct computation of proof unity}}\label{sec:pi-unity}
163
164Want to prove that prover knows $a, b$ such that $[z]_2 = [a X - b]_2$, and $a^N = b^N$.
165
166To prove $\frac{a}{b}$ is inside the evaluation domain (ie. $\frac{a}{b}$ is a N$^{th}$ root of unity), proves (in $log(N)$ time) that its N$^{th}$ is one ($\frac{a}{b} = 1$).
167
168Conditions:
169\begin{enumerate}[i.]
170 \item $f_0=\frac{a}{b}$
171 \item $f_i = f_{i-1}^2,~\forall~i=1, \ldots, log(N)$
172 \item $f_{log(N)} = 1$
173\end{enumerate}
174
175
176Redefine i, and from there, redefine ii, iii:
177% \begin{minipage}[t]{0.45\textwidth}
178% \begin{enumerate}[i.]
179% \item \begin{align*}
180% f_0 &= z(1) = a - b\\
181% f_1 &= z(\sigma) a \sigma -b\\
182% f_2 &= \frac{f_0 - f_1}{1 - \sigma} = \frac{a(1-\sigma)}{1-\sigma} = a\\
183% f_3 &= \sigma f_2 - f_1 = \sigma a - a \sigma + b = b\\
184% f_4 &= \frac{f_2}{f_3} = \frac{a}{b}
185% \end{align*}
186% \end{enumerate}
187% \end{minipage}
188% \begin{enumerate}[i.]
189% \item $f_{5+i} = f_{4+i}^2,~~\forall i=0, \ldots, log(N)-1$
190% \item $f_{4+log(N)} = 1$
191% \end{enumerate}
192% \begin{minipage}[t]{0.45\textwidth}
193% \end{minipage}
194
195\begin{enumerate}[i.]
196 \item \begin{align*}
197 f_0 &= z(1) = a - b\\
198 f_1 &= z(\sigma) a \sigma -b\\
199 f_2 &= \frac{f_0 - f_1}{1 - \sigma} = \frac{a(1-\sigma)}{1-\sigma} = a\\
200 f_3 &= \sigma f_2 - f_1 = \sigma a - a \sigma + b = b\\
201 f_4 &= \frac{f_2}{f_3} = \frac{a}{b}
202 \end{align*}
203 \item $f_{5+i} = f_{4+i}^2,~~\forall i=0, \ldots, log(N)-1$
204 \item $f_{4+log(N)} = 1$
205\end{enumerate}
206
207\begin{lemma}{1}
208 Let $z(X)$ $deg=1$, $n=log(N)+6$, $\sigma$ such that $\sigma^n =1$.
209
210 If $\exists$ $f(X) \in \mathbb{F}[X]$ such that
211 \begin{enumerate}[1.]
212 \item $f(X) = z(X)$, for $1, \sigma$
213 \item $f(\sigma^2)(1-\sigma)=f(1)-f(\sigma)$
214 \item $f(\sigma^3)=\sigma f(\sigma^2)-f(\sigma)$
215 \item $f(\sigma^4)f(\sigma^3)=f(\sigma^2)$
216 \item $f(\sigma^{4+i+1})=f(\sigma^{4+i})^2,~~\forall i= 0, \ldots, log(N)-1$
217 \item $f(\sigma^{5+log(N)} \cdot \sigma^{-1})=1$
218 \end{enumerate}
219 then, $z(X)=aX-b$, where $\frac{b}{a}$ is a N$^{th}$ root of unity.
220\end{lemma}
221
222Let's see the relations between the conditions and the Lemma 1:
223\begin{scriptsize}
224\begin{align*}
225 Conditions &\longrightarrow Lemma~1\\
226 \begin{array}{l}
227 f_0 = z(1) = a - b\\ f_1 = z(\sigma) a \sigma -b
228 \end{array} &\longrightarrow 1.~f(X) = z(X), for 1, \sigma\\
229 f_2 = \frac{f_0 - f_1}{1 - \sigma} = \frac{a(1-\sigma)}{1-\sigma} = a &\longrightarrow 2.~f(\sigma^2)(1-\sigma)=f(1)-f(\sigma)\\
230 f_3 = \sigma f_2 - f_1 = \sigma a - a \sigma + b = b &\longrightarrow 3.~f(\sigma^3)=\sigma f(\sigma^2)-f(\sigma)\\
231 f_4 = \frac{f_2}{f_3} = \frac{a}{b} &\longrightarrow 4.~f(\sigma^4)f(\sigma^3)=f(\sigma^2)\\
232 f_{5+i} = f_{4+i}^2,~~\forall i=0, \ldots, log(N)-1 &\longrightarrow 5.~f(\sigma^{4+i+1})=f(\sigma^{4+i})^2,~\forall i= 0, \ldots, log(N)-1\\
233 f_{4+log(N)} = 1 &\longrightarrow 6.~f(\sigma^{5+log(N)} \cdot \sigma^{-1})=1
234\end{align*}
235\end{scriptsize}
236
237
238For succintness: aggregate $\{f_i\}$ in a polynomial $f(X)$, whose coefficients in Lagrange basis associated to $\mathbb{V}_n$ are the $f_i$ (ie. s.t. $f(\omega^i)=f_i$).
239
240\begin{small}
241\begin{align*}
242 f(X) &= (a-b) \rho_1(X) + (a \sigma - b) \rho_2(X) + a \rho_3(X) + b \rho_4(X) + \sum_{i=0}^{log(N)} (\frac{a}{b})^{2^i} \rho_{5+i}(X)\\
243 &= f_0 \rho_1(X) + f_1 \rho_2(X) + f_2 \rho_3(X) + f_3 \rho_4(X) + \sum_{i=0}^{log(N)} (f_4)^{2^i} \rho_{5+i}(X)
244\end{align*}
245\end{small}
246
247Prover shows that $f(X)$ by comparing $f(\sigma^i)$ with the corresponding constraints from Lemma 1:
248
249For rand $\alpha$ (set by Verifier), set $\alpha_1 = \sigma^{-1} \alpha,~\alpha_2= \sigma^{-2} \alpha$, and send $v_1=f(\alpha_1),~v_2=f(\alpha_2)$ with corresponding proofs of opening.
250
251Given $v_1, v_2$, shows that $p_{\alpha}(X)$, which proves the constraints from Lemma 1, evaluates to $0$ at $\alpha$ (ie. $p_{\alpha}(\alpha)=0$).
252
253\begin{align*}
254 p_{\alpha}(X) = &-h(X) z_{V_n}(\alpha) + [f(X)-z(X)]\cdot (\rho_1(\alpha) + \rho_2(\alpha))\\
255 &+ [(1-\sigma) f(X) - f(\alpha_2) + f(\alpha_1)] \rho_3(\alpha)\\
256 &+ [f(X) + f(\alpha_2) - \sigma f(\alpha_1)] \rho_4(\alpha)\\
257 &+ [f(X) f(\alpha_1) - f(\alpha_2)] \rho_5(\alpha)\\
258 &+ [f(X) - f(\alpha_1) f(\alpha_1)] \prod_{i \notin [5, \ldots, 4+log(N)]} (\alpha - \sigma^i)\\
259 &+ [f(\alpha_1)-1] \rho_n(\alpha)
260\end{align*}
261
262\subsubsection{\texorpdfstring{NIZK argument of knowledge for $R_{unity}$ and $deg(z)\leq 1$}%
263 {NIZK argument of knowledge for Runity and deg(z)<=1}}
264
265Prover:
266\begin{small}
267\begin{align*}
268 &r_0, r_1, r_2, r_3 \leftarrow^\$ \mathbb{F},~~~ r(X)=r_1+r_2 X + r_3 X^2\\
269 f(X) &= (a-b) \rho_1(X) + (a \sigma - b) \rho_2(X) + a \rho_3(X) + b \rho_4(X) + \sum_{i=0}^{log(N)} (\frac{a}{b})^{2^i} \rho_{5+i}(X)\\
270 &+ r_0 \rho_{5+log(N)}(X) + r(X) z_{V_n}(X)\\
271 \\
272p(X) &= [f(X) - (aX-b)](\rho_1(X) + \rho_2(X))\\
273 &+[(1-\sigma)f(X) - f(\sigma^{-1}X) + f(\sigma^{-1}X)] \rho_3(X)\\
274 &+ [f(X) + f(\sigma^{-2}X) - \sigma f(\sigma^{-1} X)] \rho_4(X)\\
275 &+ [f(X)f(\sigma^{-1}X)-f(\sigma^{-2}X)] \rho_5(X)\\
276 &+ [f(X)-f(\sigma^{-1}X)f(\sigma^{-1}X)] \prod_{i \notin [5, 4+log(N)]} (X-\sigma^i)\\
277 &+ [f(\sigma^{-1}X)-1] \rho_n(X)
278\end{align*}
279\end{small}
280
281Set
282$$h'(X) = \frac{p(X)}{z_{V_n}(X)},~~h(X)=h'(X) + X^{d-1} z(X)$$
283output $([F]_1=[f(X)]_1, ~ [H]_1=[h(x)]_1)$.
284
285\begin{footnotesize}
286 Note that
287 \begin{align*}
288 h(x)&=h'(X)+X^{d-1}z(X)\\
289 &=\frac{p(X)}{z_{V_n}(X)} + X^{d-1} z(X) \longrightarrow p(X)+X^{d-1} z(X) = z_{V_n}(X) h(X)
290 \end{align*}
291\end{footnotesize}
292
293Verifier sets challenge $\alpha \in^{\$} \mathbb{F}$ (hash of transcript by Fiat-Shamir).
294
295\begin{align*}
296 p_{\alpha}(X) = &-h(X) z_{V_n}(\alpha)\\
297 &+ [f(X)-z(X)]\cdot (\rho_1(\alpha) + \rho_2(\alpha))\\
298 &+ [(1-\sigma) f(X) - f(\alpha_2) + f(\alpha_1)] \rho_3(\alpha)\\
299 &+ [f(X) + f(\alpha_2) - \sigma f(\alpha_1)] \rho_4(\alpha)\\
300 &+ [f(X) f(\alpha_1) - f(\alpha_2)] \rho_5(\alpha)\\
301 &+ [f(X) - f(\alpha_1) f(\alpha_1)] \prod_{i \notin [5, \ldots, 4+log(N)]} (\alpha - \sigma^i)\\
302 &+ [f(\alpha_1)-1] \rho_n(\alpha)
303\end{align*}
304
305\begin{footnotesize}
306 Note: for the check that $[z]_1$ has degree 1, we add $-h(X) z_{V_n}(\alpha)$, to include the term $X^{d-1} z(X)$ in $h(X)$. Later the Verifier will compute $[P]_1$ without the terms including $z(X)$ (ie. without $-X^{d-1} z(X)z_{V_n}(\alpha)-z(X)[\rho_1(\alpha)+\rho_2(\alpha)]$), which the Verifier will add via the pairing:
307 \begin{align*}
308 -&X^{d-1} z(X)z_{V_n}(\alpha)-z(X)(\rho_1(\alpha)+\rho_2(\alpha))\\
309 =~ &(-X^{d-1} z_{V_n}(\alpha) - (\rho_1(\alpha)+\rho_2(\alpha))) \cdot z(X)\\
310 \longrightarrow~ &e(- (\rho_1(\alpha)+\rho_2(\alpha)) - z_{V_n}(\alpha) [X^{d-1}]_1, [z]_2)
311 \end{align*}
312\end{footnotesize}
313
314
315Prover then generates KZG proofs
316\begin{align*}
317 ((v_1, v_2), \pi_1) &\leftarrow KZG.Open(f(X), (\alpha_1, \alpha_2))\\
318 (0, \pi_2) &\leftarrow KZG.Open(p_{\alpha}(X), \alpha)
319\end{align*}
320
321prover's output: $(v_1, v_2, \pi_1, \pi_2)$.
322
323Verify:
324set $\alpha_1=\sigma^{-1}\alpha, ~\alpha_2=\sigma^{-2}\alpha$,
325
326\begin{footnotesize}(notice that $f(X)\rightarrow [F]_1$, and $f(\alpha_1)=v_1,~f(\alpha_2)=v_2$)\end{footnotesize}
327
328\begin{align*}
329 [P]_1 = &-z_{V_n}(\alpha)[H]_1 + [F]_1 (\rho_1(\alpha) + \rho_2(\alpha))\\
330 &+ [(1-\sigma) [F]_1 - v_2 + v_1] \rho_3(\alpha)\\
331 &+ [[F]_1 + v_2 - \sigma v_1] \rho_4(\alpha)\\
332 &+ [[F]_1 v_1 - v_2] \rho_5(\alpha)\\
333 &+ [[F]_1 - v_1^2] \prod_{i \notin [5, \ldots, 4+log(N)]} (\alpha - \sigma^i)\\
334 &+ [v_1-1] \rho_n(\alpha)
335\end{align*}
336
337$$KZG.Verify((\alpha_1, \alpha_2), (v_1, v_2), \pi_1)$$
338$$e([P]_1, [1]_2) + e(-(\rho_1(\alpha) + \rho_2(\alpha)) - z_{V_n}(\alpha) [x^{d-1}]_1, [z]_2) = e(\pi_2, [x-\alpha]_2)$$
339
340
341\section{Caulk+}
342Main update from original Caulk: $R_{unity}$, $\pi_{unity}$ is replaced with a pairing check constraining the evaluation points to be roots of a polynomial dividing $X^n-1$.
343
344KZG commitment $c$ to $C(X)$, with evaluation points in $\mathbb{H}$.\\
345KZG commitment $a$ to $A(X)$, with evaluation points in $\mathbb{V}$.
346
347Witness:\\
348$I \subset [n], ~~ \{ c_i \}_{i \in I} ,~~ C(X), A(X) ,~~ u: [m] \rightarrow I$
349
350Precomputed:\\
351$[W_1^i(x)]_2 ~~\forall i \in I$, where $W_1^i(X) = \frac{C(X) - c_i)}{X-\omega^i}$\\
352$[W_2^i(x)]_2 ~~\forall i \in I$, where $W_2^i(X) = \frac{Z_{\mathbb{H}}(X)}{X-\omega^i}$
353
354\paragraph{Round 1}
355\begin{enumerate}[i.]
356 \item rand blinding factors $r1, \ldots, r_6$
357 \item Lagrange basis polynomials $\{ \tau_i(X) \}_{i \in [m]}$ over $\omega^j_{j \in I}$
358 \item $Z_I'(X)= r_1 \prod_{i \in I} (X - \omega^i)$
359 \item $C_I(X)=\sum_{i \in I} c_i \tau_i(X)$ (unblinded)
360 \item blinded $C_I'(X)=C_I(X) + (r_2 + r_3 X + r_4 X^2) Z_I'(X)$
361 \item set $U(x)$, being degree $m-1$ interpolation over $\mathbb{V}$ with $U(v_i)=\omega^{u(i)},~ \forall i\in [m]$
362 \item blinded $U'(X)= U(X) + (r_5 + r_6 X) Z_{\mathbb{V}}(X)$
363 \item return $z_I=[Z_I'(x)]_1,~ c_I=[C_I'(x)]_1,~ u=[U'(X)]_1$
364\end{enumerate}
365
366Verifier sets random challenges $\chi_1, \chi_2$.
367
368\paragraph{Round 2}
369\begin{enumerate}[i.]
370 \item $[W_1(x)+ \chi_2 W_2(x)]_2 = \sum_{i \in I} \frac{[W_1^i(x)]_2 + \chi_2 [W_2^i(x)]_2}{\prod_{j \in I,~i \neq j} \omega^i - \omega^j}$
371 \item $H(X) = \frac{Z_I'(U'(X)) + \chi_1 (C_I'(U'(X)) - A(X))}{Z_{\mathbb{V}}(X)}$
372 \item return $w=r_1^{-1} [W_1(x) + \chi_2 W_2(x)]_2 - [r_2 + r_3 x + r_4 x^2]_2,~ h=[H(x)]_1$
373\end{enumerate}
374
375Verifier sets random challenge $\alpha$.
376
377\paragraph{Round 3}
378Output $v_1, v_2, \pi_1, \pi_2, \pi_3$, where
379\begin{align*}
380 P_1(X) &\leftarrow Z_I'(X) + \chi_1 C_I'(X)\\
381 P_2(X) &\leftarrow Z_I'(U'(\alpha)) + \chi_1 (C_I'(U'(\alpha)) - A(X)) - Z_{\mathbb{V}}(\alpha) H(X)\\
382 (v_1, \pi_1) &\leftarrow KZG.Open(U'(X), \alpha)\\
383 (v_2, \pi_2) &\leftarrow KZG.Open(P_1(X), v_1)\\
384 (0, \pi_3) &\leftarrow KZG.Open(P_2(X), \alpha)\\
385\end{align*}
386
387\paragraph{Verify}
388Compute $p_1 = z_I + \chi_1 c_I, ~~ p_2= [v_2]_1 - \chi_1 a - Z_{\mathbb{V}}(\alpha) h$, verify
389\begin{align*}
390 1 &\leftarrow KZG.Verify(u, \alpha, v_1, \pi_1)\\
391 1 &\leftarrow KZG.Verify(p_1, v_1, v_2, \pi_2)\\
392 1 &\leftarrow KZG.Verify(p_2, \alpha, 0, \pi_3)\\
393 e((C-c_I) &+ \chi_2[x^n -1]_1, [1]_2) = e(z_I, w)
394\end{align*}
395
396\bibliography{paper-notes.bib}
397\bibliographystyle{unsrt}
398
399\end{document}