arnaucube.com/public/kzg-batch-proof.html
public/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 <meta name="viewport" content="width=device-width, initial-scale=1">
23
24 <link href="https://cdn.jsdelivr.net/npm/bootstrap@5.0.2/dist/css/bootstrap.min.css" rel="stylesheet" integrity="sha384-EVSTQN3/azprG1Anm3QDgpJLIm9Nao0Yz1ztcQTwFspd3yD65VohhpuuCOmLASjC" crossorigin="anonymous">
25 <link rel="stylesheet" href="css/style.css">
26
27 <!-- highlightjs -->
28 <!-- <link rel="stylesheet" href="js/highlightjs/atom-one-dark.css"> -->
29 <link rel="stylesheet" href="js/highlightjs/gruvbox-dark.css">
30 <script src="js/highlightjs/highlight.pack.js"></script>
31
32 <!-- katex -->
33 <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/katex@0.13.11/dist/katex.min.css" integrity="sha384-Um5gpz1odJg5Z4HAmzPtgZKdTBHZdw8S29IecapCSB31ligYPhHQZMIlWLYQGVoc" crossorigin="anonymous">
34 </head>
35
36 <body>
37
38 <!-- o_gradient_background" -->
39 <nav id="mainNav" class="navbar navbar-default navbar-fixed-top"
40 style="height:50px;font-size:130%;">
41 <div class="container">
42 <a href="/blog" style="color:#000;">Blog index</a>
43 <div style="float:right;">
44 <a href="/" style="color:#000;display:inline-block;">arnaucube.com</a>
45 <div class="onoffswitch" style="margin:10px;display:inline-block;" title="change theme">
46 <input onclick="switchTheme()" type="checkbox" name="onoffswitch" class="onoffswitch-checkbox"
47 id="themeSwitcher">
48 <label class="onoffswitch-label" for="themeSwitcher"></label>
49 </div>
50 </div>
51 </div>
52 <img style="height:5px; width:100%; margin-top:8px;" src="img/gradient-line.jpg" />
53 </nav>
54
55
56
57 <div class="container" style="margin-top:40px;max-width:800px;">
58 <h2>Batch proof in KZG Commitments</h2>
59
60<p><em>2021-08-14</em></p>
61
62<blockquote>
63<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>
64</blockquote>
65
66<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 reading their articles instead of this current notes.</p>
67
68<h4>Batch proof</h4>
69
70<p>The benefit of <em>batch proof</em> is that allows us to proof multiple points while the proof size remains constant to one $\mathbb{G}_1$ point.
71Let $(z_0, y_0), (z_1, y_1), …, (z_k, y_k)$ be the points that we want to proof, and that we have a polynomial $p(x)$ that goes through the points.
72The <em>commitment</em> to the polynomial stands the same than for single proofs: $c=[p(\tau)]_1$.</p>
73
74<p>For the evaluation proof, while in the single proofs we compute $q(x) = \frac{p(x)-y}{x-z}$, we will replace $y$ and $x-z$ by the following two polynomials.
75The constant $y$ 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="https://en.wikipedia.org/wiki/Lagrange_polynomial">Lagrange interpolation</a> for the given set of points:</p>
76
77<p>$$
78I(x) = \sum_{j=0}^k y_j l_j(x)\newline
79where \space\space\space l_j(x) = \prod_{0\leq m \leq k} \frac{x-x_m}{x_j - x_m}
80$$</p>
81
82<p>And the $x-z$, which was to ensure that $q(x)$ had a root at $z$, now, as we want to ensure that $q(x)$ has roots at all the points of the commitment, we will use the <em>zero polynomial</em>:
83$$
84Z(x) = \prod_{i=0}^{k} x-z_i =\newline
85=(x-z_0)(x-z_1)…(x-z_k)
86$$</p>
87
88<p>This polynomial ensures that when $x=z_i$ ($z_i$ being one of our points), the polynomial evaluation will be zero.</p>
89
90<p>Now we can put $I(x)$ and $Z(x)$ in place, obtaining $q(x)=\frac{p(x)-I(x)}{Z(x)}$. And the batch proof evaluation is obtained by $\pi=[q(\tau)]_1$.</p>
91
92<p>The verification is quite similar than what we did for single proofs, but using the mentioned $z(x)$ and $I(x)$:
93$$
94\hat{e}(\pi, [Z(\tau)]_2) == \hat{e}(c - [I(\tau)]_1, H)
95$$</p>
96
97<p>Which, as we did with the single proofs in the previous post, we can unroll it and see that:
98$$
99\hat{e}(\pi, [Z(\tau)]_2) == \hat{e}(c - [I(\tau)]_1, H)\newline
100\Rightarrow \hat{e}([q(\tau)]_1, [Z(\tau)]_2) == \hat{e}([p(\tau)]_1 - [I(\tau)]_1, H)\newline
101\Rightarrow [q(\tau) \cdot Z(\tau)]_T == [p(\tau) - I(\tau)]_T
102$$
103From where we see that is the equation $q(x)\cdot Z(x)=p(x)-I(x)$, which can be expressed as $q(x) = \frac{p(x) - I(x)}{Z(x)}$, evaluated at $\tau$ from the trusted setup, which is not known: $q(\tau) = \frac{p(\tau) - I(\tau)}{Z(\tau)}$.</p>
104
105<h4>Vector commitments</h4>
106
107<p>As mentioned earlier, this scheme can be used as a <em>vector commitment</em> scheme.</p>
108
109<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.
110The 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 $\mathbb{G}_1$ point, no matter of how many points we are batching.</p>
111
112<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>
113
114<h4>Final note</h4>
115
116<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>
117
118<p>As in the previous notes, in order to try to put in practice the concepts, I’ve added the <em>batch proof</em> logic at <a href="https://github.com/arnaucube/kzg-commitments-study">https://github.com/arnaucube/kzg-commitments-study</a>.</p>
119
120 </div>
121
122 <footer style="text-align:center; margin-top:100px;margin-bottom:50px;">
123 <div class="container">
124 <div class="row">
125 <ul class="list-inline">
126 <li><a href="https://twitter.com/arnaucube"
127 style="color:gray;text-decoration:none;"
128 target="_blank">twitter.com/arnaucube</a>
129 </li>
130 <li><a href="https://github.com/arnaucube"
131 style="color:gray;text-decoration:none;"
132 target="_blank">github.com/arnaucube</a>
133 </li>
134 </ul>
135 </div>
136 <div class="row" style="display:inline-block;">
137 Blog made with <a href="http://github.com/arnaucube/blogo/"
138 target="_blank" style="color: gray;text-decoration:none;">Blogo</a>
139 </div>
140 </div>
141 </footer>
142
143 <script>
144 </script>
145 <script src="js/external-links.js"></script>
146 <script>hljs.initHighlightingOnLoad();</script>
147 <script defer src="https://cdn.jsdelivr.net/npm/katex@0.13.11/dist/katex.min.js" integrity="sha384-YNHdsYkH6gMx9y3mRkmcJ2mFUjTd0qNQQvY9VYZgQd7DcN7env35GzlmFaZ23JGp" crossorigin="anonymous"></script>
148 <script defer src="https://cdn.jsdelivr.net/npm/katex@0.13.11/dist/contrib/auto-render.min.js" integrity="sha384-vZTG03m+2yp6N6BNi5iM4rW4oIwk5DfcNdFfxkk9ZWpDriOkXX8voJBFrAO7MpVl" crossorigin="anonymous"></script>
149 <script>
150 document.addEventListener("DOMContentLoaded", function() {
151 renderMathInElement(document.body, {
152 displayMode: false,
153 // customised options
154 // • auto-render specific keys, e.g.:
155 delimiters: [
156 {left: '$$', right: '$$', display: true},
157 {left: '$', right: '$', display: false},
158 ],
159 // • rendering keys, e.g.:
160 throwOnError : true
161 });
162 });
163
164 ///
165 let theme = localStorage.getItem("theme");
166 if ((theme === "light-theme")||(theme==null)) {
167 theme = "light-theme";
168 document.getElementById("themeSwitcher").checked = false;
169 } else if (theme === "dark-theme") {
170 theme = "dark-theme";
171 document.getElementById("themeSwitcher").checked = true;
172 }
173 document.body.className = theme;
174 localStorage.setItem("theme", theme);
175
176 function switchTheme() {
177 theme = localStorage.getItem("theme");
178 if (theme === "light-theme") {
179 theme = "dark-theme";
180 document.getElementById("themeSwitcher").checked = true;
181 } else {
182 theme = "light-theme";
183 document.getElementById("themeSwitcher").checked = false;
184 }
185 document.body.className = theme;
186 localStorage.setItem("theme", theme);
187
188 console.log(theme);
189 }
190 </script>
191 <script src="https://cdn.jsdelivr.net/npm/mermaid/dist/mermaid.min.js"></script>
192
193
194 </body>
195</html>
196