arnaucube.com/blog/kzg-commitments.html
blog/kzg-commitments.htmlRaw
1<!DOCTYPE html>
2<html lang="en">
3
4 <head>
5 <meta name="description" content="In the following notes I've tried to summarize the KZG Commitment scheme with the concepts that helped me to follow the reasoning." />
6 <meta charset="utf-8">
7 <title> Notes on KZG polynomial commitments - arnaucube - blog</title>
8 <meta name="title" content=" Notes on KZG polynomial commitments - arnaucube - blog">
9 <meta name="description" content="In the following notes I've tried to summarize the KZG Commitment scheme with the concepts that helped me to follow the reasoning.">
10
11 <meta property="og:title" content=" Notes on KZG polynomial commitments - arnaucube - blog" />
12 <meta property="og:description" content="In the following notes I've tried to summarize the KZG Commitment scheme with the concepts that helped me to follow the reasoning." />
13 <meta property="og:url" content="https://arnaucube.com/blog/kzg-commitments.html" />
14 <meta property="og:type" content="article" />
15 <meta property="og:image" content="https://arnaucube.com/blog/" />
16 <meta name="twitter:title" content=" Notes on KZG polynomial commitments - arnaucube - blog">
17 <meta name="twitter:description" content="In the following notes I've tried to summarize the KZG Commitment scheme with the concepts that helped me to follow the reasoning.">
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>Notes on KZG polynomial commitments</h2>
75
76<p><em>2021-08-05</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>Few weeks ago I started reading about <a href="https://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf">KZG Commitments</a> from the articles written by <a href="https://dankradfeist.de/ethereum/2020/06/16/kate-polynomial-commitments.html">Dankrad Feist</a>, by <a href="https://hackmd.io/@tompocock/Hk2A7BD6U">Tom Walton-Pocock</a> and by <a href="https://alinush.github.io/2020/05/06/kzg-polynomial-commitments.html">Alin Tomescu</a>. I want to thank them, because their articles helped me to understand a bit the concepts. I recommend spending the time reading their articles (<a href="https://dankradfeist.de/ethereum/2020/06/16/kate-polynomial-commitments.html">1</a>, <a href="https://hackmd.io/@tompocock/Hk2A7BD6U">2</a>, <a href="https://alinush.github.io/2020/05/06/kzg-polynomial-commitments.html">3</a>) instead of this current notes.</p>
83
84<div class="row">
85 <div class="col-md-7">
86 <br>
87 In the following notes I've tried to summarize the KZG Commitments scheme with the concepts that helped me to follow the reasoning.
88 </div>
89 <div class="col-md-5" style="font-size:90%; padding:10px;border:1px solid #cfcfcf;">
90 <b>Notation:</b><br>
91 $[x]_1 = x G \in \mathbb{G}_1\newline
92 [x]_2 = x H \in \mathbb{G}_2$
93 <br>Where $\mathbb{G}_1 = \langle G \rangle$ and $\mathbb{G}_2 = \langle H \rangle$.
94 <br>In other words: $G$ is the generator of $\mathbb{G}_1$, and $H$ is the generator of $\mathbb{G}_2$
95 </div>
96</div>
97
98<h4>Trusted setup</h4>
99
100<p>First of all, we need to generate a <em>Trusted Setup</em> that will be used later in the rest of steps. Here, the concept of <em>Trusted Setup</em> is quite similar to what we are familiar when dealing with other zk protocols such zkSNARKs, but with the advantage that for the <em>KZG Commitments</em> the nature of its <em>Trusted Setup</em> allows to have some kind of ‘global’ <em>Trusted Setup</em> that can be used for different polynomials.</p>
101
102<p>It should be computed in a <em>Multi-Party Computation</em> (<em>MPC</em>) fashion, and ensuring that at least one of the participants is honest, in order to ensure that the original parameter <span class="math inline">\(\tau\)</span> can not be restored.</p>
103
104<p>The parameters of the <em>Trusted Setup</em> are generated by generating a random <span class="math inline">\(\tau \in \mathbb{F}_p\)</span>, and from this parameter we can compute <span class="math inline">\([\tau^i]_1\)</span> and <span class="math inline">\([\tau^i]_2\)</span> for <span class="math inline">\(i=0,...,n-1\)</span>:</p>
105<p><span class="math display">\[
106[\tau^i]_1 = ([\tau^0]_1, [\tau^1]_1, [\tau^2]_1, ..., [\tau^{n-1}]_1)\newline
107[\tau^i]_2 = ([\tau^0]_2, [\tau^1]_2, [\tau^2]_2, ..., [\tau^{n-1}]_2)
108\]</span></p><p>Which in additive representation is:</p>
109<p><span class="math display">\[
110(G, \tau G, \tau^2 G, ..., \tau^{n-1} G) \in \mathbb{G}_1\newline
111(H, \tau H, \tau^2 H, ..., \tau^{n-1} H) \in \mathbb{G}_2
112\]</span></p><p>The ‘intuition’ about the <em>Trusted Setup</em> is that is like encrypting a secret value (<span class="math inline">\(\tau\)</span>) that later will be used in the ‘encrypted’ form to evaluate the polynomials.</p>
113
114<h4>Commitments</h4>
115
116<p>A commitment to a polynomial <span class="math inline">\(p(x) = \sum^n_{i=0} p_i x^i\)</span> is done by computing</p>
117<p><span class="math display">\[c=[p(\tau)]_1\]</span></p><p>which is computed by <span class="math inline">\(c = \sum^{deg(p(x))}_{i=0} [\tau^i] \cdot p_i\)</span>.</p>
118
119<p>The prover would send the commitment to the polynomial <span class="math inline">\(c\)</span>, and then the verifier would choose a value <span class="math inline">\(z \in \mathbb{F}_p\)</span>, where <span class="math inline">\(\mathbb{F}_p\)</span> is the finite field of the polynomial.</p>
120
121<h4>Evalutaion proofs</h4>
122
123<p>To prove an evaluation of the polynomial at the choosen value <span class="math inline">\(z\)</span> such that <span class="math inline">\(p(z)=y\)</span>, a quotient polynomial is computed: <span class="math inline">\(q(x) = \frac{p(x)-y}{x-z}\)</span>. This polynomial is the proof that <span class="math inline">\(p(z)=y\)</span>, as if <span class="math inline">\(q\)</span> exists it means that <span class="math inline">\(p(x)-y\)</span> is divisible by <span class="math inline">\(x-z\)</span>, which means that it has a root at <span class="math inline">\(z\)</span>, being <span class="math inline">\(p(z)-y=0\)</span>.</p>
124
125<p>Then, the evaluation proof is</p>
126<p><span class="math display">\[\pi = [q(\tau)]_1\]</span></p><p>which, as when computing <span class="math inline">\(c\)</span>, is computed by <span class="math inline">\(\pi=\sum^{deg(q(x))}_{i=0} [\tau^i] \cdot q_i\)</span>.</p>
127
128<p>Once computed, the prover would send this evaluation proof <span class="math inline">\(\pi\)</span> to the verifier.</p>
129
130<h4>Verifying an evaluation proof</h4>
131
132<p>In order to verify an evaluation proof, the verifier has the commitment <span class="math inline">\(c=[p(\tau)]_1\)</span>, the evaluation <span class="math inline">\(y=p(z)\)</span>, and the proof <span class="math inline">\(\pi=[q(\tau)]_1\)</span>.</p>
133
134<p>So, the verifier can check the <a href="https://en.wikipedia.org/wiki/Pairing-based_cryptography">pairing</a> evaluation:
135$<span class="math inline">\(\hat{e}(\pi, [\tau]_2 - [z]_2) == \hat{e}(c - [y]_1, H)\)</span>$</p>
136
137<p>Where <span class="math inline">\([\tau]_2\)</span> comes from the Trusted Setup, <span class="math inline">\([z]_2\)</span> is point at which the polynomial is evaluated, and <span class="math inline">\([y]_1\)</span> is the claimed value p(z). And <span class="math inline">\(\pi\)</span> and <span class="math inline">\(c\)</span> are given by the prover.</p>
138
139<p>We can unroll that last equivalence, and see that:</p>
140<p><span class="math display">\[
141\hat{e}(\pi, [\tau]_2 - [z]_2) == \hat{e}(c - [y]_1, H)\newline
142\Rightarrow \hat{e}([q(\tau)]_1, [\tau-z]_2) == \hat{e}([p(\tau)]_1 - [y]_1, H)\newline
143\Rightarrow [q(\tau) \cdot (\tau-z)]_T == [p(\tau) - y]_T
144\]</span></p><p>We can see that is the equation <span class="math inline">\(q(x)(x-z)=p(x)-y\)</span>, which can be expressed as <span class="math inline">\(q(x) = \frac{p(x) - y}{x-z}\)</span>, evaluated at <span class="math inline">\(\tau\)</span> from the <em>trusted setup</em>, which is not known: <span class="math inline">\(q(\tau) = \frac{p(\tau) - y}{\tau-z}\)</span>.</p>
145
146<h3>Conclusions</h3>
147
148<p>The content covered in this notes is just a quick overview, but allows us to see the potential of the scheme. One next iteration from what we’ve seen is the approach to do batch proofs, which allows us to evaluate at multiple points with a single evaluation proof. This scheme can be used as a <em>vector commitment</em>, using a polynomial where the <span class="math inline">\(p(i) = x_i\)</span> for all values of <span class="math inline">\(x_i\)</span> of the vector, which can be obtained from the <span class="math inline">\(x_i\)</span> values and computing the <a href="shamir-secret-sharing.html#lagrange-polynomial%20interpolation">Lagrange interpolation</a>. This is quite useful combined with the mentioned batch proofs. The <em>batch proofs</em> logic can be found at the <a href="https://arnaucube.com/blog/kzg-batch-proof.html">blog/kzg-batch-proof</a> notes (kind of the continuation of the current notes).</p>
149
150<p>As a final note, in order to try to digest the notes, I’ve did a <em>toy implementation</em> of this scheme at <a href="https://github.com/arnaucube/kzg-commitments-study">https://github.com/arnaucube/kzg-commitments-study</a>. It’s quite simple, but contains the logic overviewed in this notes.</p>
151
152<p><br>
153- <a href="https://arnaucube.com/blog/kzg-batch-proof.html">Part 2: Batch proof in KZG Commitments</a></p>
154
155 </div>
156
157 <footer style="text-align:center; margin-top:100px;margin-bottom:50px;">
158 <div class="container">
159 <br>
160 <a href="/blog">Go to main</a>
161 <br><br>
162 <div class="row">
163 <ul class="list-inline">
164 <li><a href="https://twitter.com/arnaucube"
165 style="color:gray;text-decoration:none;"
166 target="_blank">twitter.com/arnaucube</a>
167 </li>
168 <li><a href="https://github.com/arnaucube"
169 style="color:gray;text-decoration:none;"
170 target="_blank">github.com/arnaucube</a>
171 </li>
172 </ul>
173 </div>
174 <div class="row" style="display:inline-block;">
175 Blog made with <a href="http://github.com/arnaucube/blogo/"
176 target="_blank" style="color: gray;text-decoration:none;">Blogo</a>
177 </div>
178 </div>
179 </footer>
180
181 <script>
182 </script>
183 <script src="js/external-links.js"></script>
184 <script>hljs.initHighlightingOnLoad();</script>
185 <script defer src="js/katex/katex.min.js"></script>
186 <script defer src="js/katex/auto-render.min.js"></script>
187 <script>
188 document.addEventListener("DOMContentLoaded", function() {
189 renderMathInElement(document.body, {
190 displayMode: false,
191 // customised options
192 // • auto-render specific keys, e.g.:
193 delimiters: [
194 {left: '$$', right: '$$', display: true},
195 {left: '$', right: '$', display: false},
196 {left: "\\[", right: "\\]", display: true},
197 {left: "\\(", right: "\\)", display: false},
198 {left: "\\begin{equation}", right: "\\end{equation}", display: true}
199 ],
200 // • rendering keys, e.g.:
201 throwOnError : true
202 });
203 });
204
205 ///
206 let theme = localStorage.getItem("theme");
207 if ((theme === "light-theme")||(theme==null)) {
208 theme = "light-theme";
209 document.getElementById("themeSwitcher").checked = false;
210 } else if (theme === "dark-theme") {
211 theme = "dark-theme";
212 document.getElementById("themeSwitcher").checked = true;
213 }
214 document.body.className = theme;
215 localStorage.setItem("theme", theme);
216
217 function switchTheme() {
218 theme = localStorage.getItem("theme");
219 if (theme === "light-theme") {
220 theme = "dark-theme";
221 document.getElementById("themeSwitcher").checked = true;
222 } else {
223 theme = "light-theme";
224 document.getElementById("themeSwitcher").checked = false;
225 }
226 document.body.className = theme;
227 localStorage.setItem("theme", theme);
228
229 console.log(theme);
230 }
231 </script>
232 <script>
233 function tagLinks(tagName) {
234 var tags = document.getElementsByTagName(tagName);
235 for (var i=0, hElem; hElem = tags[i]; i++) {
236 if (hElem.parentNode.className=="row postThumb") {
237 continue;
238 }
239 hElem.id = hElem.innerHTML.toLowerCase().replace(" ", "-");
240 hElem.innerHTML = "<a style='color:black!important;' href='#"+hElem.id+"'>"+hElem.innerHTML+"</a>";
241 }
242 }
243 tagLinks("h2");
244 tagLinks("h3");
245 tagLinks("h4");
246 tagLinks("h5");
247 </script>
248 <script>
249function generateTOC(tocContainerId = "toc") {
250 const tocContainer = document.getElementById(tocContainerId);
251 if (!tocContainer) return;
252
253 const headings = document.querySelectorAll("h2, h3, h4, h5, h6");
254 if (!headings.length) return;
255
256 // Generate IDs if missing
257 headings.forEach((heading, index) => {
258 if (!heading.id) {
259 heading.id =
260 heading.textContent
261 .trim()
262 .toLowerCase()
263 .replace(/[^\w\s-]/g, "")
264 .replace(/\s+/g, "-") +
265 "-" +
266 index;
267 }
268 });
269
270 const toc = document.createElement("ul");
271 let currentLevel = 1;
272 let currentList = toc;
273 const stack = [toc];
274
275 headings.forEach((heading) => {
276 const level = parseInt(heading.tagName.substring(1), 10);
277
278 const li = document.createElement("li");
279 const a = document.createElement("a");
280
281 a.href = "#" + heading.id;
282 a.textContent = heading.textContent;
283
284 li.appendChild(a);
285
286 if (level > currentLevel) {
287 for (let i = currentLevel; i < level; i++) {
288 const nestedList = document.createElement("ul");
289
290 const lastLi =
291 currentList.lastElementChild ||
292 currentList.appendChild(document.createElement("ul"));
293
294 lastLi.appendChild(nestedList);
295
296 stack.push(nestedList);
297 currentList = nestedList;
298 }
299 } else if (level < currentLevel) {
300 for (let i = currentLevel; i > level; i--) {
301 stack.pop();
302 }
303 currentList = stack[stack.length - 1];
304 }
305
306 currentList.appendChild(li);
307 currentLevel = level;
308 });
309
310 tocContainer.innerHTML = "";
311 tocContainer.appendChild(toc);
312}
313
314document.addEventListener("DOMContentLoaded", () => {
315 generateTOC();
316});
317 </script>
318 <script src="js/mermaid.min.js"></script>
319
320 </body>
321</html>
322