arnaucube.com/blog/ringsig.html
blog/ringsig.htmlRaw
1<!DOCTYPE html>
2<html lang="en">
3
4 <head>
5 <meta name="description" content="Notes on ring signatures" />
6 <meta charset="utf-8">
7 <title> bLSAG ring signatures overview - arnaucube - blog</title>
8 <meta name="title" content=" bLSAG ring signatures overview - arnaucube - blog">
9 <meta name="description" content="Notes on ring signatures">
10
11 <meta property="og:title" content=" bLSAG ring signatures overview - arnaucube - blog" />
12 <meta property="og:description" content="Notes on ring signatures" />
13 <meta property="og:url" content="https://arnaucube.com/blog/ringsig.html" />
14 <meta property="og:type" content="article" />
15 <meta property="og:image" content="https://arnaucube.com/blog/" />
16 <meta name="twitter:title" content=" bLSAG ring signatures overview - arnaucube - blog">
17 <meta name="twitter:description" content="Notes on ring signatures">
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 <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 <h1>bLSAG ring signatures overview</h1>
75
76<p><em>2022-07-20</em></p>
77
78<blockquote>
79<p>Note: I’m not a mathematician, I’m just an amateur on math. These notes are just an attempt to try to sort the notes that I took while learning abut bLSAG.</p>
80</blockquote>
81
82<p><br>
83bLSAG: Back’s Linkable Spontaneous Anonymous Group signatures</p>
84
85<ul>
86<li>signer ambiguity</li>
87<li>linkability</li>
88<li>unforgeability</li>
89</ul>
90
91<h3>Setup</h3>
92
93<p>Let <span class="math inline">\(G\)</span> be the generator of an EC group.
94We use a hash function <span class="math inline">\(\mathcal{H}_p\)</span>, which maps to curve points in EC, and a normal hash <span class="math inline">\(\mathcal{H}_n\)</span>, which maps to <span class="math inline">\(\mathbb{Z}_p\)</span>.
95Signer’s key pair: <span class="math inline">\(k_{\pi}\)</span>, s.t. <span class="math inline">\(K_{\pi} = k_{\pi} \cdot G \in \mathcal{R}\)</span>, with secret index <span class="math inline">\(\pi\)</span>.
96Set of Public Keys: <span class="math inline">\(\mathcal{R} = \{ K_1, K_2, \ldots, K_n \}\)</span></p>
97
98<pre><code class="language-python">def new_key():
99 k = F.random_element()
100 K = g * k # g is the generator of the EC group
101 return K
102</code></pre>
103
104<h3>Signature</h3>
105
106<ol>
107<li><p>compute key image: <span class="math inline">\(\tilde{K} = k_{\pi} \mathcal{H_p} ( K_{\pi}) \in G\)</span></p>
108
109<pre><code class="language-python">key_image = k * hashToPoint(K)
110</code></pre></li>
111
112<li><p>Generate <span class="math inline">\(\alpha \in^R \mathbb{Z}_p\)</span>, and <span class="math inline">\(r_i \in^R \mathbb{Z}_p\)</span>, for <span class="math inline">\(i \in \{1, 2, \ldots, n \}\)</span>, with <span class="math inline">\(i \neq \pi\)</span></p>
113
114<ul>
115<li><p><span class="math inline">\(r_i\)</span> is used for the fake responses</p>
116
117<pre><code class="language-python">a = F.random_element()
118r = [None] * len(R)
119for i in range(0, len(R)):
120 if i==pi:
121 continue
122
123
124 r[i] = mod(F.random_element(), p)
125</code></pre></li>
126</ul></li>
127
128<li><p>Compute <span class="math inline">\(c_{\pi + 1} = \mathcal{H}_n ( m, [\alpha G], [\alpha \mathcal{H}_p(K_{\pi})])\)</span></p>
129
130<pre><code class="language-python">c[pi1] = hash(R, m, a * g, hashToPoint(R[pi]) * a, p)
131</code></pre></li>
132
133<li><p>for <span class="math inline">\(i=\pi + 1, \pi +2, \ldots, n, 1, 2, \ldots, \pi -1\)</span>, calculate, replacing <span class="math inline">\(n+1 \rightarrow 1\)</span>
134$<span class="math inline">\(
135c_{i+1} = \mathcal{H}_n (m, [r_i G + c_i K_i], [r_i \mathcal{H}_p (K_i) + c_i \tilde{K}])
136\)</span>$</p>
137
138<ul>
139<li>Notice that (from step 3 & 4):<br>
140<span class="math inline">\(\alpha \mathcal{H}_p (K_{\pi}) = r_{\pi} \mathcal{H}_p (K_{\pi}) + c_{\pi} \cdot (\tilde{K})\)</span>,<br>
141where <span class="math inline">\(\tilde{K}= k_{\pi} \mathcal{H_p} ( K_{\pi})\)</span>, so:<br>
142<span class="math inline">\(\alpha \mathcal{H}_p (K_{\pi}) = r_{\pi} \mathcal{H}_p (K_{\pi}) + c_{\pi} \cdot (k_{\pi} \mathcal{H}_p(K_{\pi}))\)</span><br>
143which is equal to,<br>
144<span class="math inline">\(\alpha \cdot \mathcal{H}_p (K_{\pi}) = (r_{\pi} + c_{\pi} \cdot k_{\pi}) \cdot \mathcal{H}_p(K_{\pi})\)</span><br>
145From where we can see: <span class="math inline">\(\alpha = r_{\pi} + c_{\pi} \cdot k_{\pi}\)</span><br>
146which we can rearrange to
147<span class="math inline">\(r_{\pi} = \alpha - c_{\pi} \cdot k_{\pi}\)</span>.<br><br></li>
148</ul>
149
150<pre><code class="language-python">for j in range(0, len(R)-1):
151 i = mod(pi1+j, len(R))
152 i1 = mod(pi1+j +1, len(R))
153
154
155 c[i1] = hash(R, m, r[i] * g + c[i] * R[i],
156 r[i] * hashToPoint(R[i]) + c[i] * key_image, p)
157</code></pre></li>
158
159<li><p>Define <span class="math inline">\(r_{\pi} = \alpha - c_{\pi} k_{\pi} \mod{p}\)</span></p></li>
160</ol>
161
162<pre><code class="language-python">r[pi] = mod(a - c[pi] * k, p)
163</code></pre>
164
165<p>Signature: <span class="math inline">\(\sigma(m) = (c_1, r_1, \ldots, r_n)\)</span>, with key image <span class="math inline">\(\tilde{K}\)</span> and ring <span class="math inline">\(\mathcal{R}\)</span>.
166- <span class="math inline">\(len(\sigma(m)) = 1+n\)</span></p>
167
168<pre><code class="language-python">return [c[0], r]
169</code></pre>
170
171<p><br><br><br></p>
172
173<h4>Step by step (simplified):</h4>
174
175<div style="overflow:auto;">
176<div style="width: 60%; float:left; height: 360px; overflow-y:scroll;">
177
178<img src="img/posts/ring-sig/step00.png" style="width:100%;" />
179<img src="img/posts/ring-sig/step00.png" style="width:100%;" />
180<img src="img/posts/ring-sig/step01.png" style="width:100%;" />
181<img src="img/posts/ring-sig/step02.png" style="width:100%;" />
182<img src="img/posts/ring-sig/step03.png" style="width:100%;" />
183<img src="img/posts/ring-sig/step04.png" style="width:100%;" />
184<img src="img/posts/ring-sig/step05.png" style="width:100%;" />
185<img src="img/posts/ring-sig/step06.png" style="width:100%;" />
186
187</div>
188
189<div style="width: 40%; float:right; margin-top:80px;">
190
191 <ul>
192<li>Generate $r_i \in^R \mathbb{Z_p}$</li>
193<li>Compute $c_{i+1}$ from $r_i$</li>
194<li>Link $r_{\pi}$ with $c_{\pi}$</li>
195</ul>
196
197</div>
198</div>
199
200<p><em>You can scroll down the images through the step-by-step diagrams.</em></p>
201
202<p><br></p>
203
204<p>It reminds in some way to the approach to close a box like the one in the picture:
205<img src="img/posts/ring-sig/box-closed.png" alt="" /></p>
206
207<p><br><br><br></p>
208
209<h3>Verification</h3>
210
211<ol>
212<li><p>check <span class="math inline">\(p \tilde{K} \stackrel{?}{=} 0\)</span></p>
213
214<ul>
215<li>to ensure that <span class="math inline">\(\tilde{K} \in G\)</span> (and not in a cofactor group of <span class="math inline">\(G\)</span>)</li>
216</ul></li>
217
218<li><p>for <span class="math inline">\(i = 1, 2, \ldots, n\)</span>, replacing <span class="math inline">\(n+1 \rightarrow 1\)</span>
219$<span class="math inline">\(
220c'_{i+1} = \mathcal{H}_n (m, [r_i G + c_i K_i], [r_i \mathcal{H}_p (K_i) + c_i \tilde{K}])
221\)</span>$</p></li>
222
223<li><p>check <span class="math inline">\(c_1 \stackrel{?}{=} c'_i\)</span></p>
224
225<pre><code class="language-python">c[0] = c1
226for j in range(0, len(R)):
227 i = mod(j, len(R))
228 i1 = mod(j+1, len(R))
229 c[i1] = hash(R, m, r[i] * g + c[i] * R[i],
230 r[i] * hashToPoint(R[i]) + c[i] * key_image, p)
231
232
233assert c1 == c[0]
234</code></pre></li>
235</ol>
236
237<p><br><br></p>
238
239<h2>Links</h2>
240
241<p>Toy implementation:</p>
242
243<ul>
244<li>Sage: <a href="https://github.com/arnaucube/math/blob/master/ring-signatures.sage">https://github.com/arnaucube/math/blob/master/ring-signatures.sage</a></li>
245<li>Rust: <a href="https://github.com/arnaucube/ring-signatures-rs">https://github.com/arnaucube/ring-signatures-rs</a></li>
246</ul>
247
248<p>Resources:</p>
249
250<ul>
251<li><em>“Zero to Monero”</em> - <a href="https://web.getmonero.org/library/Zero-to-Monero-2-0-0.pdf">https://web.getmonero.org/library/Zero-to-Monero-2-0-0.pdf</a>
252(section <em>“3.4 Back’s Linkable Spontaneous Anonymous Group (bLSAG) signatures”</em>)</li>
253</ul>
254
255 </div>
256
257 <footer style="text-align:center; margin-top:100px;margin-bottom:50px;">
258 <div class="container">
259 <br>
260 <a href="/blog">Go to main</a>
261 <br><br>
262 <div class="row">
263 <ul class="list-inline">
264 <li><a href="https://twitter.com/arnaucube"
265 style="color:gray;text-decoration:none;"
266 target="_blank">twitter.com/arnaucube</a>
267 </li>
268 <li><a href="https://github.com/arnaucube"
269 style="color:gray;text-decoration:none;"
270 target="_blank">github.com/arnaucube</a>
271 </li>
272 </ul>
273 </div>
274 <div class="row" style="display:inline-block;">
275 Blog made with <a href="http://github.com/arnaucube/blogo/"
276 target="_blank" style="color: gray;text-decoration:none;">Blogo</a>
277 </div>
278 </div>
279 </footer>
280
281 <script>
282 </script>
283 <script src="js/external-links.js"></script>
284 <script>hljs.initHighlightingOnLoad();</script>
285 <script defer src="js/katex/katex.min.js"></script>
286 <script defer src="js/katex/auto-render.min.js"></script>
287 <script>
288 document.addEventListener("DOMContentLoaded", function() {
289 renderMathInElement(document.body, {
290 displayMode: false,
291 // customised options
292 // • auto-render specific keys, e.g.:
293 delimiters: [
294 {left: '$$', right: '$$', display: true},
295 {left: '$', right: '$', display: false},
296 {left: "\\[", right: "\\]", display: true},
297 {left: "\\(", right: "\\)", display: false},
298 {left: "\\begin{equation}", right: "\\end{equation}", display: true}
299 ],
300 // • rendering keys, e.g.:
301 throwOnError : true
302 });
303 });
304
305 ///
306 let theme = localStorage.getItem("theme");
307 if ((theme === "light-theme")||(theme==null)) {
308 theme = "light-theme";
309 document.getElementById("themeSwitcher").checked = false;
310 } else if (theme === "dark-theme") {
311 theme = "dark-theme";
312 document.getElementById("themeSwitcher").checked = true;
313 }
314 document.body.className = theme;
315 localStorage.setItem("theme", theme);
316
317 function switchTheme() {
318 theme = localStorage.getItem("theme");
319 if (theme === "light-theme") {
320 theme = "dark-theme";
321 document.getElementById("themeSwitcher").checked = true;
322 } else {
323 theme = "light-theme";
324 document.getElementById("themeSwitcher").checked = false;
325 }
326 document.body.className = theme;
327 localStorage.setItem("theme", theme);
328
329 console.log(theme);
330 }
331 </script>
332 <script>
333 function tagLinks(tagName) {
334 var tags = document.getElementsByTagName(tagName);
335 for (var i=0, hElem; hElem = tags[i]; i++) {
336 if (hElem.parentNode.className=="row postThumb") {
337 continue;
338 }
339 hElem.id = hElem.innerHTML.toLowerCase().replace(" ", "-");
340 hElem.innerHTML = "<a style='color:black!important;' href='#"+hElem.id+"'>"+hElem.innerHTML+"</a>";
341 }
342 }
343 tagLinks("h2");
344 tagLinks("h3");
345 tagLinks("h4");
346 tagLinks("h5");
347 </script>
348 <script>
349function generateTOC(tocContainerId = "toc") {
350 const tocContainer = document.getElementById(tocContainerId);
351 if (!tocContainer) return;
352
353 const headings = document.querySelectorAll("h2, h3, h4, h5, h6");
354 if (!headings.length) return;
355
356 // Generate IDs if missing
357 headings.forEach((heading, index) => {
358 if (!heading.id) {
359 heading.id =
360 heading.textContent
361 .trim()
362 .toLowerCase()
363 .replace(/[^\w\s-]/g, "")
364 .replace(/\s+/g, "-") +
365 "-" +
366 index;
367 }
368 });
369
370 const toc = document.createElement("ul");
371 let currentLevel = 1;
372 let currentList = toc;
373 const stack = [toc];
374
375 headings.forEach((heading) => {
376 const level = parseInt(heading.tagName.substring(1), 10);
377
378 const li = document.createElement("li");
379 const a = document.createElement("a");
380
381 a.href = "#" + heading.id;
382 a.textContent = heading.textContent;
383
384 li.appendChild(a);
385
386 if (level > currentLevel) {
387 for (let i = currentLevel; i < level; i++) {
388 const nestedList = document.createElement("ul");
389
390 const lastLi =
391 currentList.lastElementChild ||
392 currentList.appendChild(document.createElement("ul"));
393
394 lastLi.appendChild(nestedList);
395
396 stack.push(nestedList);
397 currentList = nestedList;
398 }
399 } else if (level < currentLevel) {
400 for (let i = currentLevel; i > level; i--) {
401 stack.pop();
402 }
403 currentList = stack[stack.length - 1];
404 }
405
406 currentList.appendChild(li);
407 currentLevel = level;
408 });
409
410 tocContainer.innerHTML = "";
411 tocContainer.appendChild(toc);
412}
413
414document.addEventListener("DOMContentLoaded", () => {
415 generateTOC();
416});
417 </script>
418 <script src="js/mermaid.min.js"></script>
419
420 </body>
421</html>
422