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="/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>Notes on KZG polynomial commitments</h2>
71
72<p><em>2021-08-05</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>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>
79
80<div class="row">
81 <div class="col-md-7">
82 <br>
83 In the following notes I've tried to summarize the KZG Commitments scheme with the concepts that helped me to follow the reasoning.
84 </div>
85 <div class="col-md-5" style="font-size:90%; padding:10px;border:1px solid #cfcfcf;">
86 <b>Notation:</b><br>
87 $[x]_1 = x G \in \mathbb{G}_1\newline
88 [x]_2 = x H \in \mathbb{G}_2$
89 <br>Where $\mathbb{G}_1 = \langle G \rangle$ and $\mathbb{G}_2 = \langle H \rangle$.
90 <br>In other words: $G$ is the generator of $\mathbb{G}_1$, and $H$ is the generator of $\mathbb{G}_2$
91 </div>
92</div>
93
94<h4>Trusted setup</h4>
95
96<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>
97
98<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>
99
100<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>
101<p><span class="math display">\[
102[\tau^i]_1 = ([\tau^0]_1, [\tau^1]_1, [\tau^2]_1, ..., [\tau^{n-1}]_1)\newline
103[\tau^i]_2 = ([\tau^0]_2, [\tau^1]_2, [\tau^2]_2, ..., [\tau^{n-1}]_2)
104\]</span></p><p>Which in additive representation is:</p>
105<p><span class="math display">\[
106(G, \tau G, \tau^2 G, ..., \tau^{n-1} G) \in \mathbb{G}_1\newline
107(H, \tau H, \tau^2 H, ..., \tau^{n-1} H) \in \mathbb{G}_2
108\]</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>
109
110<h4>Commitments</h4>
111
112<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>
113<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>
114
115<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>
116
117<h4>Evalutaion proofs</h4>
118
119<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>
120
121<p>Then, the evaluation proof is</p>
122<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>
123
124<p>Once computed, the prover would send this evaluation proof <span class="math inline">\(\pi\)</span> to the verifier.</p>
125
126<h4>Verifying an evaluation proof</h4>
127
128<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>
129
130<p>So, the verifier can check the <a href="https://en.wikipedia.org/wiki/Pairing-based_cryptography">pairing</a> evaluation:
131$<span class="math inline">\(\hat{e}(\pi, [\tau]_2 - [z]_2) == \hat{e}(c - [y]_1, H)\)</span>$</p>
132
133<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>
134
135<p>We can unroll that last equivalence, and see that:</p>
136<p><span class="math display">\[
137\hat{e}(\pi, [\tau]_2 - [z]_2) == \hat{e}(c - [y]_1, H)\newline
138\Rightarrow \hat{e}([q(\tau)]_1, [\tau-z]_2) == \hat{e}([p(\tau)]_1 - [y]_1, H)\newline
139\Rightarrow [q(\tau) \cdot (\tau-z)]_T == [p(\tau) - y]_T
140\]</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>
141
142<h3>Conclusions</h3>
143
144<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>
145
146<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>
147
148<p><br>
149- <a href="https://arnaucube.com/blog/kzg-batch-proof.html">Part 2: Batch proof in KZG Commitments</a></p>
150
151 </div>
152
153 <footer style="text-align:center; margin-top:100px;margin-bottom:50px;">
154 <div class="container">
155 <br>
156 <a href="/blog">Go to main</a>
157 <br><br>
158 <div class="row">
159 <ul class="list-inline">
160 <li><a href="https://twitter.com/arnaucube"
161 style="color:gray;text-decoration:none;"
162 target="_blank">twitter.com/arnaucube</a>
163 </li>
164 <li><a href="https://github.com/arnaucube"
165 style="color:gray;text-decoration:none;"
166 target="_blank">github.com/arnaucube</a>
167 </li>
168 </ul>
169 </div>
170 <div class="row" style="display:inline-block;">
171 Blog made with <a href="http://github.com/arnaucube/blogo/"
172 target="_blank" style="color: gray;text-decoration:none;">Blogo</a>
173 </div>
174 </div>
175 </footer>
176
177 <script>
178 </script>
179 <script src="js/external-links.js"></script>
180 <script>hljs.initHighlightingOnLoad();</script>
181 <script defer src="js/katex/katex.min.js"></script>
182 <script defer src="js/katex/auto-render.min.js"></script>
183 <script>
184 document.addEventListener("DOMContentLoaded", function() {
185 renderMathInElement(document.body, {
186 displayMode: false,
187 // customised options
188 // • auto-render specific keys, e.g.:
189 delimiters: [
190 {left: '$$', right: '$$', display: true},
191 {left: '$', right: '$', display: false},
192 {left: "\\[", right: "\\]", display: true},
193 {left: "\\(", right: "\\)", display: false},
194 {left: "\\begin{equation}", right: "\\end{equation}", display: true}
195 ],
196 // • rendering keys, e.g.:
197 throwOnError : true
198 });
199 });
200
201 ///
202 let theme = localStorage.getItem("theme");
203 if ((theme === "light-theme")||(theme==null)) {
204 theme = "light-theme";
205 document.getElementById("themeSwitcher").checked = false;
206 } else if (theme === "dark-theme") {
207 theme = "dark-theme";
208 document.getElementById("themeSwitcher").checked = true;
209 }
210 document.body.className = theme;
211 localStorage.setItem("theme", theme);
212
213 function switchTheme() {
214 theme = localStorage.getItem("theme");
215 if (theme === "light-theme") {
216 theme = "dark-theme";
217 document.getElementById("themeSwitcher").checked = true;
218 } else {
219 theme = "light-theme";
220 document.getElementById("themeSwitcher").checked = false;
221 }
222 document.body.className = theme;
223 localStorage.setItem("theme", theme);
224
225 console.log(theme);
226 }
227 </script>
228 <script>
229 function tagLinks(tagName) {
230 var tags = document.getElementsByTagName(tagName);
231 for (var i=0, hElem; hElem = tags[i]; i++) {
232 if (hElem.parentNode.className=="row postThumb") {
233 continue;
234 }
235 hElem.id = hElem.innerHTML.toLowerCase().replace(" ", "-");
236 hElem.innerHTML = "<a style='color:black!important;' href='#"+hElem.id+"'>"+hElem.innerHTML+"</a>";
237 }
238 }
239 tagLinks("h2");
240 tagLinks("h3");
241 tagLinks("h4");
242 tagLinks("h5");
243 </script>
244 <script>
245function generateTOC(tocContainerId = "toc") {
246 const tocContainer = document.getElementById(tocContainerId);
247 if (!tocContainer) return;
248
249 const headings = document.querySelectorAll("h2, h3, h4, h5, h6");
250 if (!headings.length) return;
251
252 // Generate IDs if missing
253 headings.forEach((heading, index) => {
254 if (!heading.id) {
255 heading.id =
256 heading.textContent
257 .trim()
258 .toLowerCase()
259 .replace(/[^\w\s-]/g, "")
260 .replace(/\s+/g, "-") +
261 "-" +
262 index;
263 }
264 });
265
266 const toc = document.createElement("ul");
267 let currentLevel = 1;
268 let currentList = toc;
269 const stack = [toc];
270
271 headings.forEach((heading) => {
272 const level = parseInt(heading.tagName.substring(1), 10);
273
274 const li = document.createElement("li");
275 const a = document.createElement("a");
276
277 a.href = "#" + heading.id;
278 a.textContent = heading.textContent;
279
280 li.appendChild(a);
281
282 if (level > currentLevel) {
283 for (let i = currentLevel; i < level; i++) {
284 const nestedList = document.createElement("ul");
285
286 const lastLi =
287 currentList.lastElementChild ||
288 currentList.appendChild(document.createElement("ul"));
289
290 lastLi.appendChild(nestedList);
291
292 stack.push(nestedList);
293 currentList = nestedList;
294 }
295 } else if (level < currentLevel) {
296 for (let i = currentLevel; i > level; i--) {
297 stack.pop();
298 }
299 currentList = stack[stack.length - 1];
300 }
301
302 currentList.appendChild(li);
303 currentLevel = level;
304 });
305
306 tocContainer.innerHTML = "";
307 tocContainer.appendChild(toc);
308}
309
310document.addEventListener("DOMContentLoaded", () => {
311 generateTOC();
312});
313 </script>
314 <script src="js/mermaid.min.js"></script>
315
316 </body>
317</html>
318