arnaucube.com/blog/kzg-batch-proof.html
blog/kzg-batch-proof.htmlRaw
1<!DOCTYPE html>
2<html lang="en">
3
4 <head>
5 <meta name="description" content="The benefit of batch proof is that allows us to proof multiple points while the proof size remains constant to one G1 point." />
6 <meta charset="utf-8">
7 <title> Batch proof in KZG Commitments - arnaucube - blog</title>
8 <meta name="title" content=" Batch proof in KZG Commitments - arnaucube - blog">
9 <meta name="description" content="The benefit of batch proof is that allows us to proof multiple points while the proof size remains constant to one G1 point.">
10
11 <meta property="og:title" content=" Batch proof in KZG Commitments - arnaucube - blog" />
12 <meta property="og:description" content="The benefit of batch proof is that allows us to proof multiple points while the proof size remains constant to one G1 point." />
13 <meta property="og:url" content="https://arnaucube.com/blog/kzg-batch-proof.html" />
14 <meta property="og:type" content="article" />
15 <meta property="og:image" content="https://arnaucube.com/blog/" />
16 <meta name="twitter:title" content=" Batch proof in KZG Commitments - arnaucube - blog">
17 <meta name="twitter:description" content="The benefit of batch proof is that allows us to proof multiple points while the proof size remains constant to one G1 point.">
18 <meta name="twitter:image" content="https://arnaucube.com/blog/">
19 <meta name="twitter:card" content="summary_large_image">
20 <meta name="author" content="arnaucube">
21
22 <link rel="icon" type="image/png" href="img/logoArnauCubeFavicon.png">
23
24 <meta name="viewport" content="width=device-width, initial-scale=1">
25
26 <link href="css/bootstrap.min.css" rel="stylesheet">
27 <link rel="stylesheet" href="css/style.css">
28
29 <!-- highlightjs -->
30 <!-- <link rel="stylesheet" href="js/highlightjs/atom-one-dark.css"> -->
31 <link rel="stylesheet" href="js/highlightjs/atom-one-light.css">
32 <!-- <link rel="stylesheet" href="js/highlightjs/gruvbox-dark.css"> -->
33 <script src="js/highlightjs/highlight.pack.js"></script>
34
35 <!-- katex -->
36 <link rel="stylesheet" href="js/katex/katex.min.css">
37 <link rel="alternate" type="application/rss+xml" title="arnaucube - blog RSS" href="https://arnaucube.com/blog/rss.xml">
38</head>
39
40 <body>
41
42 <!-- o_gradient_background" -->
43 <nav id="mainNav" class="navbar navbar-default navbar-fixed-top"
44 style="height:50px;font-size:100%;">
45 <div class="container">
46 <div style="float:left;">
47 <a href="/blog" style="color:#000;display:inline-block;">blog</a>
48 <span style="margin-right:20px; margin-left:20px;">|</span>
49 <a href="/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 <h2>Batch proof in KZG Commitments</h2>
75
76<p><em>2021-08-14</em></p>
77
78<blockquote>
79<p><strong>Warning</strong>: I want to state clearly that I’m not a mathematician, I’m just an amateur on math studying in my free time, and this article is just an attempt to try to sort the notes that I took while reading about the KZG Commitments.</p>
80</blockquote>
81
82<p>Last week I posted some <em><a href="https://arnaucube.com/blog/kzg-commitments.html">notes on KZG Commitmens</a></em>, which overviews the scheme for single proofs. The current notes, try to overview the <em>batch proof</em> iteraton on KZG Commitments, and the <em>vector commitment</em> usage of it. Again (as in the previous post), big thanks to <a href="https://dankradfeist.de/ethereum/2020/06/16/kate-polynomial-commitments.html">Dankrad Feist</a> and <a href="https://alinush.github.io/2020/05/06/kzg-polynomial-commitments.html">Alin Tomescu</a> for their articles which helped me to follow a bit the reasoing behind this, and again, I recommend spending the time <strong>reading their articles (<a href="https://dankradfeist.de/ethereum/2020/06/16/kate-polynomial-commitments.html">1</a>, <a href="https://alinush.github.io/2020/05/06/kzg-polynomial-commitments.html">2</a>) instead of this current notes</strong>.</p>
83
84<h4>Batch proof</h4>
85
86<p>The benefit of <em>batch proof</em> is that allows us to proof multiple points while the proof size remains constant to one <span class="math inline">\(\mathbb{G}_1\)</span> point.
87Let <span class="math inline">\((z_0, y_0), (z_1, y_1), ..., (z_k, y_k)\)</span> be the points that we want to proof, and that we have a polynomial <span class="math inline">\(p(x)\)</span> that goes through the points.
88The <em>commitment</em> to the polynomial stands the same than for single proofs: <span class="math inline">\(c=[p(\tau)]_1\)</span>.</p>
89
90<p>For the evaluation proof, while in the single proofs we compute <span class="math inline">\(q(x) = \frac{p(x)-y}{x-z}\)</span>, we will replace <span class="math inline">\(y\)</span> and <span class="math inline">\(x-z\)</span> by the following two polynomials.
91The constant <span class="math inline">\(y\)</span> is replaced by a polynomial that has roots at all the points that we want to prove. This is achieved by computing the <a href="shamir-secret-sharing.html#lagrange-polynomial%20interpolation">Lagrange interpolation</a> for the given set of points:</p>
92<p><span class="math display">\[
93I(x) = \sum_{j=0}^k y_j l_j(x)\newline
94where \space\space\space l_j(x) = \prod_{0\leq m \leq k} \frac{x-x_m}{x_j - x_m}
95\]</span></p><p>And the <span class="math inline">\(x-z\)</span>, which was to ensure that <span class="math inline">\(q(x)\)</span> had a root at <span class="math inline">\(z\)</span>, now, as we want to ensure that <span class="math inline">\(q(x)\)</span> has roots at all the points of the commitment, we will use the <em>zero polynomial</em>:</p>
96<p><span class="math display">\[
97Z(x) = \prod_{i=0}^{k} x-z_i =\newline
98=(x-z_0)(x-z_1)...(x-z_k)
99\]</span></p><p>This polynomial ensures that when <span class="math inline">\(x=z_i\)</span> (<span class="math inline">\(z_i\)</span> being one of our points), the polynomial evaluation will be zero.</p>
100
101<p>Now we can put <span class="math inline">\(I(x)\)</span> and <span class="math inline">\(Z(x)\)</span> in place, obtaining <span class="math inline">\(q(x)=\frac{p(x)-I(x)}{Z(x)}\)</span>. And the batch proof evaluation is obtained by <span class="math inline">\(\pi=[q(\tau)]_1\)</span>.</p>
102
103<p>The verification is quite similar than what we did for single proofs, but using the mentioned <span class="math inline">\(z(x)\)</span> and <span class="math inline">\(I(x)\)</span>:</p>
104<p><span class="math display">\[
105\hat{e}(\pi, [Z(\tau)]_2) == \hat{e}(c - [I(\tau)]_1, H)
106\]</span></p><p>Which, as we did with the single proofs in the previous post, we can unroll it and see that:</p>
107<p><span class="math display">\[
108\hat{e}(\pi, [Z(\tau)]_2) == \hat{e}(c - [I(\tau)]_1, H)\newline
109\Rightarrow \hat{e}([q(\tau)]_1, [Z(\tau)]_2) == \hat{e}([p(\tau)]_1 - [I(\tau)]_1, H)\newline
110\Rightarrow [q(\tau) \cdot Z(\tau)]_T == [p(\tau) - I(\tau)]_T
111\]</span></p><p>From where we see that is the equation <span class="math inline">\(q(x)\cdot Z(x)=p(x)-I(x)\)</span>, which can be expressed as <span class="math inline">\(q(x) = \frac{p(x) - I(x)}{Z(x)}\)</span>, evaluated at <span class="math inline">\(\tau\)</span> from the trusted setup, which is not known: <span class="math inline">\(q(\tau) = \frac{p(\tau) - I(\tau)}{Z(\tau)}\)</span>.</p>
112
113<h4>Vector commitments</h4>
114
115<p>As mentioned earlier, this scheme can be used as a <em>vector commitment</em> scheme.</p>
116
117<p>A vector commitment allows a prover to commit to a vector and later proof that a certain value belongs to that vector. As a traditional example, we can think of <em>Merkle Trees</em>, where we can commit to a vector of values, which are placed in the tree leafs. Then we compute the <em>root</em> which acts as the commitment. Then we can provide a proof that a certain leaf belongs to the vector for the commitment (<em>root</em>) that we showed earlier.
118The problem with Merkle Trees is that the proof size grows linearly with the size of the tree, as it contains the siblings from the leaf to the root. Here is where <em>KZG Commitments</em> can be benefitial, as the proof always stands with the same size, one <span class="math inline">\(\mathbb{G}_1\)</span> point, no matter of how many points we are batching.</p>
119
120<p>We can use KZG Commitments as a vector commitment scheme by mapping the <em>vector</em> as a batch of points that build the polynomial, so when commiting to the polynomial we are commiting to the vector. Then, it’s a matter of using the <em>batch proof</em> approach explained above in order to proof multiple elements of the vector in a single proof that can be verified later.</p>
121
122<h4>Final note</h4>
123
124<p>I’m fascinated by this scheme and its potential. One next rabbit hole (related to KZG Commitments) to look at, would be the <a href="https://vitalik.ca/general/2019/09/22/plonk.html">Plonk</a> and other similar constructions. Also, another use case that is getting attention in the Ethereum community is the <a href="https://vitalik.ca/general/2021/06/18/verkle.html"><em>Verkle Trees</em></a>.</p>
125
126<p>As in the previous notes, in order to try to put in practice the concepts, I’ve added the implementation of the <em>batch proof</em> logic at the Go KZG implementation <a href="https://github.com/arnaucube/kzg-commitments-study">https://github.com/arnaucube/kzg-commitments-study</a>.</p>
127
128 </div>
129
130 <footer style="text-align:center; margin-top:100px;margin-bottom:50px;">
131 <div class="container">
132 <br>
133 <a href="/blog">Go to main</a>
134 <br><br>
135 <div class="row">
136 <ul class="list-inline">
137 <li><a href="https://twitter.com/arnaucube"
138 style="color:gray;text-decoration:none;"
139 target="_blank">twitter.com/arnaucube</a>
140 </li>
141 <li><a href="https://github.com/arnaucube"
142 style="color:gray;text-decoration:none;"
143 target="_blank">github.com/arnaucube</a>
144 </li>
145 </ul>
146 </div>
147 <div class="row" style="display:inline-block;">
148 Blog made with <a href="http://github.com/arnaucube/blogo/"
149 target="_blank" style="color: gray;text-decoration:none;">Blogo</a>
150 </div>
151 </div>
152 </footer>
153
154 <script>
155 </script>
156 <script src="js/external-links.js"></script>
157 <script>hljs.initHighlightingOnLoad();</script>
158 <script defer src="js/katex/katex.min.js"></script>
159 <script defer src="js/katex/auto-render.min.js"></script>
160 <script>
161 document.addEventListener("DOMContentLoaded", function() {
162 renderMathInElement(document.body, {
163 displayMode: false,
164 // customised options
165 // • auto-render specific keys, e.g.:
166 delimiters: [
167 {left: '$$', right: '$$', display: true},
168 {left: '$', right: '$', display: false},
169 {left: "\\[", right: "\\]", display: true},
170 {left: "\\(", right: "\\)", display: false},
171 {left: "\\begin{equation}", right: "\\end{equation}", display: true}
172 ],
173 // • rendering keys, e.g.:
174 throwOnError : true
175 });
176 });
177
178 ///
179 let theme = localStorage.getItem("theme");
180 if ((theme === "light-theme")||(theme==null)) {
181 theme = "light-theme";
182 document.getElementById("themeSwitcher").checked = false;
183 } else if (theme === "dark-theme") {
184 theme = "dark-theme";
185 document.getElementById("themeSwitcher").checked = true;
186 }
187 document.body.className = theme;
188 localStorage.setItem("theme", theme);
189
190 function switchTheme() {
191 theme = localStorage.getItem("theme");
192 if (theme === "light-theme") {
193 theme = "dark-theme";
194 document.getElementById("themeSwitcher").checked = true;
195 } else {
196 theme = "light-theme";
197 document.getElementById("themeSwitcher").checked = false;
198 }
199 document.body.className = theme;
200 localStorage.setItem("theme", theme);
201
202 console.log(theme);
203 }
204 </script>
205 <script>
206 function tagLinks(tagName) {
207 var tags = document.getElementsByTagName(tagName);
208 for (var i=0, hElem; hElem = tags[i]; i++) {
209 if (hElem.parentNode.className=="row postThumb") {
210 continue;
211 }
212 hElem.id = hElem.innerHTML.toLowerCase().replace(" ", "-");
213 hElem.innerHTML = "<a style='color:black!important;' href='#"+hElem.id+"'>"+hElem.innerHTML+"</a>";
214 }
215 }
216 tagLinks("h2");
217 tagLinks("h3");
218 tagLinks("h4");
219 tagLinks("h5");
220 </script>
221 <script>
222function generateTOC(tocContainerId = "toc") {
223 const tocContainer = document.getElementById(tocContainerId);
224 if (!tocContainer) return;
225
226 const headings = document.querySelectorAll("h2, h3, h4, h5, h6");
227 if (!headings.length) return;
228
229 // Generate IDs if missing
230 headings.forEach((heading, index) => {
231 if (!heading.id) {
232 heading.id =
233 heading.textContent
234 .trim()
235 .toLowerCase()
236 .replace(/[^\w\s-]/g, "")
237 .replace(/\s+/g, "-") +
238 "-" +
239 index;
240 }
241 });
242
243 const toc = document.createElement("ul");
244 let currentLevel = 1;
245 let currentList = toc;
246 const stack = [toc];
247
248 headings.forEach((heading) => {
249 const level = parseInt(heading.tagName.substring(1), 10);
250
251 const li = document.createElement("li");
252 const a = document.createElement("a");
253
254 a.href = "#" + heading.id;
255 a.textContent = heading.textContent;
256
257 li.appendChild(a);
258
259 if (level > currentLevel) {
260 for (let i = currentLevel; i < level; i++) {
261 const nestedList = document.createElement("ul");
262
263 const lastLi =
264 currentList.lastElementChild ||
265 currentList.appendChild(document.createElement("ul"));
266
267 lastLi.appendChild(nestedList);
268
269 stack.push(nestedList);
270 currentList = nestedList;
271 }
272 } else if (level < currentLevel) {
273 for (let i = currentLevel; i > level; i--) {
274 stack.pop();
275 }
276 currentList = stack[stack.length - 1];
277 }
278
279 currentList.appendChild(li);
280 currentLevel = level;
281 });
282
283 tocContainer.innerHTML = "";
284 tocContainer.appendChild(toc);
285}
286
287document.addEventListener("DOMContentLoaded", () => {
288 generateTOC();
289});
290 </script>
291 <script src="js/mermaid.min.js"></script>
292
293 </body>
294</html>
295