-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathrealization.html
308 lines (307 loc) · 23.6 KB
/
realization.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
<!DOCTYPE html>
<html>
<head>
<!-- Site made with Mobirise Website Builder v5.9.18, https://mobirise.com -->
<meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="generator" content="Mobirise v5.9.18, mobirise.com">
<meta name="twitter:card" content="summary_large_image"/>
<meta name="twitter:image:src" content="assets/images/realization-meta.jpg">
<meta property="og:image" content="assets/images/realization-meta.jpg">
<meta name="twitter:title" content="Realization">
<meta name="viewport" content="width=device-width, initial-scale=1, minimum-scale=1">
<link rel="shortcut icon" href="assets/images/ledgerloops-logo-new-144x87.jpg" type="image/x-icon">
<meta name="description" content="Ledger Loops revolutionizes invoice clearing by enabling businesses to settle transactions without cash, enhancing cash flow and efficiency in peer-to-peer networks.">
<title>Realization</title>
<link rel="stylesheet" href="assets/web/assets/mobirise-icons2/mobirise2.css">
<link rel="stylesheet" href="assets/bootstrap/css/bootstrap.min.css">
<link rel="stylesheet" href="assets/bootstrap/css/bootstrap-grid.min.css">
<link rel="stylesheet" href="assets/bootstrap/css/bootstrap-reboot.min.css">
<link rel="stylesheet" href="assets/web/assets/gdpr-plugin/gdpr-styles.css">
<link rel="stylesheet" href="assets/dropdown/css/style.css">
<link rel="stylesheet" href="assets/socicon/css/styles.css">
<link rel="stylesheet" href="assets/theme/css/style.css">
<link rel="preload" href="https://fonts.googleapis.com/css2?family=Inter+Tight:wght@400;700&display=swap&display=swap" as="style" onload="this.onload=null;this.rel='stylesheet'">
<noscript>
<link rel="stylesheet" href="https://fonts.googleapis.com/css2?family=Inter+Tight:wght@400;700&display=swap&display=swap">
</noscript>
<link rel="preload" as="style" href="assets/mobirise/css/mbr-additional.css?v=RsAAXX">
<link rel="stylesheet" href="assets/mobirise/css/mbr-additional.css?v=RsAAXX" type="text/css">
</head>
<body>
<section data-bs-version="5.1" class="menu menu2 cid-ur8H0aAPgP" once="menu" id="menu02-i">
<nav class="navbar navbar-dropdown navbar-fixed-top navbar-expand-lg">
<div class="container">
<div class="navbar-brand"><span class="navbar-logo"> <a href="/"> <img src="assets/images/ledgerloops-logo-new-144x87.jpg" alt="Mobirise Website Builder" style="height: 4.3rem;"> </a> </span>
</div>
<button class="navbar-toggler" type="button" data-toggle="collapse" data-bs-toggle="collapse" data-target="#navbarSupportedContent" data-bs-target="#navbarSupportedContent" aria-controls="navbarNavAltMarkup" aria-expanded="false" aria-label="Toggle navigation">
<div class="hamburger"><span></span><span></span><span></span><span></span>
</div>
</button>
<div class="collapse navbar-collapse" id="navbarSupportedContent">
<ul class="navbar-nav nav-dropdown nav-right" data-app-modern-menu="true">
<li class="nav-item"><a class="nav-link link text-white text-primary display-4" href="/initiation">Initiation</a>
</li>
<li class="nav-item">
<a class="nav-link link text-white text-primary display-4" href="/description">Description</a>
</li>
<li class="nav-item">
<a class="nav-link link text-white text-primary display-4" href="/realization">Realization</a>
</li>
<li class="nav-item">
<a class="nav-link link text-white text-primary display-4" href="/activation">Activation</a>
</li>
<li class="nav-item">
<a class="nav-link link text-white text-primary display-4" href="/contact">Contact</a>
</li>
</ul>
</div>
</div>
</nav>
</section>
<section data-bs-version="5.1" class="article9 cid-ur8H0bny0U mbr-fullscreen" id="article09-l">
<div class="container-fluid">
<div class="row justify-content-center">
<div class="card col-md-12 col-lg-10">
<div class="card-wrapper">
<div class="card-content-text">
<div align="center">
<h1 id="ledgerloops-using-the-sarafu-dataset">LedgerLoops using the Sarafu dataset</h1>
</div>
<p>In order to know whether our algorithm actually works and scales, we tested it on a rather large dataset: the Sarafu dataset.</p>
<h3 id="the-sarafu-dataset">The Sarafu Dataset</h3>
<p>The Sarafu Dataset is <a href="https://www.nature.com/articles/s41597-022-01539-4">openly available</a> and describes 440,000 transactions between
roughly 55,000 accounts. We use it here to see if the LedgerLoops algorithm can efficiently find loops.</p>
<h3 id="definition-of-loops">Definition of Loops</h3>
<p>Consider the following small dataset:</p>
<p><pre><code>Transaction <span class="hljs-number">1</span>: <span class="hljs-keyword">Node</span> <span class="hljs-title">1</span> sends <span class="hljs-keyword">node</span> <span class="hljs-title">2</span> a transfer of <span class="hljs-number">50</span> units
Transaction <span class="hljs-number">2</span>: <span class="hljs-keyword">Node</span> <span class="hljs-title">2</span> sends <span class="hljs-keyword">node</span> <span class="hljs-title">3</span> a transfer of <span class="hljs-number">150</span> units
Transaction <span class="hljs-number">3</span>: <span class="hljs-keyword">Node</span> <span class="hljs-title">3</span> sends <span class="hljs-keyword">node</span> <span class="hljs-title">2</span> a transfer of <span class="hljs-number">25</span> units
Transaction <span class="hljs-number">4</span>: <span class="hljs-keyword">Node</span> <span class="hljs-title">3</span> sends <span class="hljs-keyword">node</span> <span class="hljs-title">1</span> a transfer of <span class="hljs-number">25</span> units
</code></pre></p>
<p>If these transactions are administered on a single ledger, then the balances would evolve as follows:</p>
<p> <table width="100%">
<thead>
<tr>
<th>After transaction </th>
<th>Node 1 balance </th>
<th>Node 2 balance </th>
<th>Node 3 balance </th>
</tr>
</thead>
<tbody>
<tr>
<td>0</td>
<td>0</td>
<td>0</td>
<td>0</td>
</tr>
<tr>
<td>1</td>
<td>0 - 50 = -50</td>
<td>0 + 50 = 50</td>
<td>0</td>
</tr>
<tr>
<td>2</td>
<td>-50</td>
<td>50 - 150 = -100</td>
<td>0 + 150 = 150</td>
</tr>
<tr>
<td>3</td>
<td>-50</td>
<td>-100 + 25 = -75</td>
<td>150 - 25 = 125</td>
</tr>
<tr>
<td>4</td>
<td>-50 + 25 = -25</td>
<td>-75</td>
<td>125 - 25 = 100</td>
</tr>
</tbody>
</table></p>
<p>Note that in this situation, each node has only a single balance against its environment, and netting
happens explicitly as a part of each transaction. At each transaction, two of the balances on the central
ledger are updated.</p>
<p>It is, however, also possible to implement a payment network using just bilateral peer-to-peer trustlines.
In that case, the balances would evolve as follows:</p>
<p><table width="100%">
<thead>
<tr>
<th>After transaction</th>
<th>[1->2, 1->3] bilateral balances</th>
<th>[2->1, 2->3] bilateral balances</th>
<th>[3->1, 3->2] bilateral balances</th>
</tr>
</thead>
<tbody>
<tr>
<td>0</td>
<td>[ 0, 0 ]</td>
<td>[ 0, 0 ]</td>
<td>[ 0, 0 ]</td>
</tr>
<tr>
<td>1</td>
<td>[-50, 0 ]</td>
<td>[ 50 , 0 ]</td>
<td>[ 0, 0 ]</td>
</tr>
<tr>
<td>2</td>
<td>[-50, 0 ]</td>
<td>[ 50, -150 ]</td>
<td>[ 0, 150 ]</td>
</tr>
<tr>
<td>3</td>
<td>[-50, 0 ]</td>
<td>[ 50 , -125 ]</td>
<td>[ 0, 125 ]</td>
</tr>
<tr>
<td>4</td>
<td>[-50, 25 ]</td>
<td>[ 50 , -125 ]</td>
<td>[ -25, 125 ]</td>
</tr>
</tbody>
</table></p>
<p>Note that in this case bilateral netting between nodes 2 and 3 is still immediate, and transactions 2 and 3 partially
cancel each other out.</p>
<p>However, whereas the central ledger ends up with a total deployed balance of 100 units,
the system of bilateral ledgers ends up with total deployed balance of 50 + (150-25) + 25 = 200 units.</p>
<p>In order to reduce the total deployed balance in a network of bilateral ledgers, loops can be used.
They consist of a set of transactions, one per ledger, that reduce the total deployed balance in a way all participants can agree with.</p>
<p>So in this case:</p>
<pre><code>Transaction <span class="hljs-number">5</span>a: <span class="hljs-keyword">Node</span> <span class="hljs-title">2</span> sends <span class="hljs-keyword">node</span> <span class="hljs-title">1</span> a loop-transfer <span class="hljs-number">25</span> units.
Transaction <span class="hljs-number">5</span>b: <span class="hljs-keyword">Node</span> <span class="hljs-title">3</span> sends <span class="hljs-keyword">node</span> <span class="hljs-title">2</span> a loop-transfer <span class="hljs-number">25</span> units.
Transaction <span class="hljs-number">5</span>c: <span class="hljs-keyword">Node</span> <span class="hljs-title">1</span> sends <span class="hljs-keyword">node</span> <span class="hljs-title">3</span> a loop-transfer <span class="hljs-number">25</span> units.
</code></pre>
<p>And the effect:</p>
<table width="100%">
<thead>
<tr>
<th>After transaction</th>
<th>[1->2, 1->3] bilateral balances</th>
<th>[2->1, 2->3] bilateral balances</th>
<th>[3->1, 3->2] bilateral balances</th>
</tr>
</thead>
<tbody>
<tr>
<td>5a</td>
<td>[ -50 + 25 = -25, 25 ]</td>
<td>[ 50 - 25 = 25, -125 ]</td>
<td>[ -25, 125 ]</td>
</tr>
<tr>
<td>5b</td>
<td>[ -25, 25 ]</td>
<td>[ 25, -125 + 25 = -100 ]</td>
<td>[ -25, 125 - 25 = 100 ]</td>
</tr>
<tr>
<td>5c</td>
<td>[ -25, 25 - 25 = 0 ]</td>
<td>[ 25, -100 ]</td>
<td>[ -25 + 25 = 0, 100 ]</td>
</tr>
</tbody>
</table>
<p>The total deployed balance has now been reduced by 3 times 25 units, from 50 + (150-25) + 25 = 200 units to (50-25) + (150-25-25) + (25-25) = 125 units.</p>
<h3 id="performance">Performance</h3>
<h4 id="bandwidth">Snake Game Search</h4>
<p>Until recently, most loop detection algorithms were based on min-cost-flow (MCF) algorithms. However, a decentralised implementation of MCF would require nodes that are not part of the globally best solution to cooperate altruistically. We therefore explored the use of "Snake Game" search algorithms, in which forwarded messages between nodes cause a 'snake' to form through the network, similar to the Snake Game that was popular on feature phones.</p>
<p>The presence of a loop would cause the "snake" to encounter its own "tail". Our <a href="https://github.com/ledgerloops/strategy-pit?tab=readme-ov-file#sarafu-based-netting-challenge">strategy pit</a> compares such a snake-like Depth-First Search (DFS) algorithm against MCF.</p>
<h3 id="conclusion">Conclusion</h3>
<h4 id="observations">Observations</h4>
<p>The results are very encouraging. MCF does clear more debt, namely 67% instead of 60%, so snake-like DFS is underperforming by about 10%. But we believe this is an acceptable performance gap, and have plans for enhancements that will make this gap even smaller.</p>
<p>The currently tested DFS algorithm is written in 350 lines of TypeScript and finds around 1,000 loops per second in a single execution thread on a regular modern laptop.</p>
<h4 id="algorithm-open-standard">Algorithm Open Standard</h4>
<p>We are working on a messaging-based version of this algorithm that uses the messaging protocol specified by the <a href="https://datatracker.ietf.org/doc/draft-dejong-decentralized-cycle-detection/">Decentralized Cycle Detection</a> Internet Draft, and this is rather straightforward when using a central orchestrator to decide which node moves next.</p>
<h4 id="tech-preview">Tech Preview</h4>
<p>So far, it has proven more difficult than we had anticipated to make the algorithm run not only through node-to-node messaging but also without any central coordination, but we're making good progress on this goal and hope to launch an MVP of a fully peer-to-peer obligation clearing network in 2025. We published our <a href="https://github.com/ledgerloops/jerboa">Jerboa</a> prototype in October 2024 to show that peer-to-peer obligation clearing is, in principle, feasible.</p>
</section>
<section data-bs-version="5.1" class="news08 cid-ur9axhZok2" id="news08-1c">
<div class="container-fluid">
<div class="row justify-content-center mb-5">
<div class="col-12 content-head">
<div class="mbr-section-head">
<h4 class="mbr-section-title mbr-fonts-style align-center mb-0 display-2"> <strong>Take A Closer Look</strong></h4>
</div>
</div>
</div>
<div class="row">
<div class="item features-image col-12 col-md-6 col-lg-3 active">
<div class="item-wrapper">
<div class="item-img mb-3"><a href="/initiation"><img src="assets/images/ledgerloops-logo-new-tagline-128x71.png" alt="History of Ledger Loops" title=""></a>
</div>
<div class="item-content align-left">
<h5 class="item-title mbr-fonts-style mt-0 mb-3 display-7">Initiation</h5>
<h6 class="item-subtitle mbr-fonts-style mb-3 display-5"> <strong>The History of LedgerLoops</strong></h6>
<div class="mbr-section-btn item-footer">
<a href="/initiation" class="btn item-btn btn-primary display-7">Read</a>
</div>
</div>
</div>
</div>
<div class="item features-image col-12 col-md-6 col-lg-3">
<div class="item-wrapper">
<div class="item-img mb-3"><a href="/description"><img src="assets/images/whispering-merchants-by-njoku-johnston-838x471.png" alt="Ledgerloops Whispering Merchants"></a>
</div>
<div class="item-content align-left">
<h5 class="item-title mbr-fonts-style mb-3 mt-0 display-7">Description</h5>
<h6 class="item-subtitle mbr-fonts-style mb-3 display-5"> <strong>Tale of the Whispering Merchants</strong></h6>
<div class="mbr-section-btn item-footer">
<a href="/description" class="btn item-btn btn-primary display-7">Read</a>
</div>
</div>
</div>
</div>
<div class="item features-image col-12 col-md-6 col-lg-3">
<div class="item-wrapper">
<div class="item-img mb-3"><a href="/realization"><img src="assets/images/sarafu-374x377.jpg" alt="Ledger Loops Sarafu"></a>
</div>
<div class="item-content align-left">
<h5 class="item-title mbr-fonts-style mb-3 mt-0 display-7">Realization</h5>
<h6 class="item-subtitle mbr-fonts-style mt-0 mb-3 display-5"><strong>LedgerLoops using the Sarafu dataset</strong></h6>
<div class="mbr-section-btn item-footer">
<a href="/realization" class="btn item-btn btn-primary display-7">Read</a>
</div>
</div>
</div>
</div>
<div class="item features-image col-12 col-md-6 col-lg-3">
<div class="item-wrapper">
<div class="item-img mb-3"><a href="/activation"><img src="assets/images/photo-1498050108023-c5249f4df085.jpeg" alt="Ledger Loops Activation"></a>
</div>
<div class="item-content align-left">
<h5 class="item-title mbr-fonts-style mb-3 mt-0 display-7">Activation</h5>
<h6 class="item-subtitle mbr-fonts-style mt-0 mb-3 display-5"> <strong>Getting Started with LedgerLoops</strong></h6>
<div class="mbr-section-btn item-footer">
<a href="/activation" class="btn item-btn btn-primary display-7">Read</a>
</div>
</div>
</div>
</div>
</div>
</div>
</section>
<section data-bs-version="5.1" class="footer3 cid-ur8H0c3AbF" once="footers" id="footer03-n">
<div class="container">
<div class="row">
<div class="col-12 mt-4">
<p class="mbr-fonts-style copyright display-7">© 2024 LedgerLoops. All rights reserved.</p>
</div>
</div>
</div>
</section>
<script src="assets/bootstrap/js/bootstrap.bundle.min.js"></script>
<script src="assets/smoothscroll/smooth-scroll.js"></script>
<script src="assets/ytplayer/index.js"></script>
<script src="assets/dropdown/js/navbar-dropdown.js"></script>
<script src="assets/theme/js/script.js"></script>
</body>