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="/blog/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
69 <div class="container" style="margin-top:0px;max-width:800px;">
70 <h2>Batch proof in KZG Commitments</h2>
71
72<p><em>2021-08-14</em></p>
73
74<blockquote>
75<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>
76</blockquote>
77
78<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>
79
80<h4>Batch proof</h4>
81
82<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.
83Let <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.
84The <em>commitment</em> to the polynomial stands the same than for single proofs: <span class="math inline">\(c=[p(\tau)]_1\)</span>.</p>
85
86<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.
87The 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>
88<p><span class="math display">\[
89I(x) = \sum_{j=0}^k y_j l_j(x)\newline
90where \space\space\space l_j(x) = \prod_{0\leq m \leq k} \frac{x-x_m}{x_j - x_m}
91\]</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>
92<p><span class="math display">\[
93Z(x) = \prod_{i=0}^{k} x-z_i =\newline
94=(x-z_0)(x-z_1)...(x-z_k)
95\]</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>
96
97<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>
98
99<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>
100<p><span class="math display">\[
101\hat{e}(\pi, [Z(\tau)]_2) == \hat{e}(c - [I(\tau)]_1, H)
102\]</span></p><p>Which, as we did with the single proofs in the previous post, we can unroll it and see that:</p>
103<p><span class="math display">\[
104\hat{e}(\pi, [Z(\tau)]_2) == \hat{e}(c - [I(\tau)]_1, H)\newline
105\Rightarrow \hat{e}([q(\tau)]_1, [Z(\tau)]_2) == \hat{e}([p(\tau)]_1 - [I(\tau)]_1, H)\newline
106\Rightarrow [q(\tau) \cdot Z(\tau)]_T == [p(\tau) - I(\tau)]_T
107\]</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>
108
109<h4>Vector commitments</h4>
110
111<p>As mentioned earlier, this scheme can be used as a <em>vector commitment</em> scheme.</p>
112
113<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.
114The 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>
115
116<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>
117
118<h4>Final note</h4>
119
120<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>
121
122<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>
123
124 </div>
125
126 <footer style="text-align:center; margin-top:100px;margin-bottom:50px;">
127 <div class="container">
128 <br>
129 <a href="/blog">Go to main</a>
130 <br><br>
131 <div class="row">
132 <ul class="list-inline">
133 <li><a href="https://twitter.com/arnaucube"
134 style="color:gray;text-decoration:none;"
135 target="_blank">twitter.com/arnaucube</a>
136 </li>
137 <li><a href="https://github.com/arnaucube"
138 style="color:gray;text-decoration:none;"
139 target="_blank">github.com/arnaucube</a>
140 </li>
141 </ul>
142 </div>
143 <div class="row" style="display:inline-block;">
144 Blog made with <a href="http://github.com/arnaucube/blogo/"
145 target="_blank" style="color: gray;text-decoration:none;">Blogo</a>
146 </div>
147 </div>
148 </footer>
149
150 <script>
151 </script>
152 <script src="js/external-links.js"></script>
153 <script>hljs.initHighlightingOnLoad();</script>
154 <script defer src="js/katex/katex.min.js"></script>
155 <script defer src="js/katex/auto-render.min.js"></script>
156 <script>
157 document.addEventListener("DOMContentLoaded", function() {
158 renderMathInElement(document.body, {
159 displayMode: false,
160 // customised options
161 // • auto-render specific keys, e.g.:
162 delimiters: [
163 {left: '$$', right: '$$', display: true},
164 {left: '$', right: '$', display: false},
165 {left: "\\[", right: "\\]", display: true},
166 {left: "\\(", right: "\\)", display: false},
167 {left: "\\begin{equation}", right: "\\end{equation}", display: true}
168 ],
169 // • rendering keys, e.g.:
170 throwOnError : true
171 });
172 });
173
174 ///
175 let theme = localStorage.getItem("theme");
176 if ((theme === "light-theme")||(theme==null)) {
177 theme = "light-theme";
178 document.getElementById("themeSwitcher").checked = false;
179 } else if (theme === "dark-theme") {
180 theme = "dark-theme";
181 document.getElementById("themeSwitcher").checked = true;
182 }
183 document.body.className = theme;
184 localStorage.setItem("theme", theme);
185
186 function switchTheme() {
187 theme = localStorage.getItem("theme");
188 if (theme === "light-theme") {
189 theme = "dark-theme";
190 document.getElementById("themeSwitcher").checked = true;
191 } else {
192 theme = "light-theme";
193 document.getElementById("themeSwitcher").checked = false;
194 }
195 document.body.className = theme;
196 localStorage.setItem("theme", theme);
197
198 console.log(theme);
199 }
200 </script>
201 <script>
202 function tagLinks(tagName) {
203 var tags = document.getElementsByTagName(tagName);
204 for (var i=0, hElem; hElem = tags[i]; i++) {
205 if (hElem.parentNode.className=="row postThumb") {
206 continue;
207 }
208 hElem.id = hElem.innerHTML.toLowerCase().replace(" ", "-");
209 hElem.innerHTML = "<a style='color:black!important;' href='#"+hElem.id+"'>"+hElem.innerHTML+"</a>";
210 }
211 }
212 tagLinks("h2");
213 tagLinks("h3");
214 tagLinks("h4");
215 tagLinks("h5");
216 </script>
217 <script>
218function generateTOC(tocContainerId = "toc") {
219 const tocContainer = document.getElementById(tocContainerId);
220 if (!tocContainer) return;
221
222 const headings = document.querySelectorAll("h2, h3, h4, h5, h6");
223 if (!headings.length) return;
224
225 // Generate IDs if missing
226 headings.forEach((heading, index) => {
227 if (!heading.id) {
228 heading.id =
229 heading.textContent
230 .trim()
231 .toLowerCase()
232 .replace(/[^\w\s-]/g, "")
233 .replace(/\s+/g, "-") +
234 "-" +
235 index;
236 }
237 });
238
239 const toc = document.createElement("ul");
240 let currentLevel = 1;
241 let currentList = toc;
242 const stack = [toc];
243
244 headings.forEach((heading) => {
245 const level = parseInt(heading.tagName.substring(1), 10);
246
247 const li = document.createElement("li");
248 const a = document.createElement("a");
249
250 a.href = "#" + heading.id;
251 a.textContent = heading.textContent;
252
253 li.appendChild(a);
254
255 if (level > currentLevel) {
256 for (let i = currentLevel; i < level; i++) {
257 const nestedList = document.createElement("ul");
258
259 const lastLi =
260 currentList.lastElementChild ||
261 currentList.appendChild(document.createElement("ul"));
262
263 lastLi.appendChild(nestedList);
264
265 stack.push(nestedList);
266 currentList = nestedList;
267 }
268 } else if (level < currentLevel) {
269 for (let i = currentLevel; i > level; i--) {
270 stack.pop();
271 }
272 currentList = stack[stack.length - 1];
273 }
274
275 currentList.appendChild(li);
276 currentLevel = level;
277 });
278
279 tocContainer.innerHTML = "";
280 tocContainer.appendChild(toc);
281}
282
283document.addEventListener("DOMContentLoaded", () => {
284 generateTOC();
285});
286 </script>
287 <script src="js/mermaid.min.js"></script>
288
289 </body>
290</html>
291