-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathindex.html
More file actions
312 lines (281 loc) · 15.2 KB
/
Copy pathindex.html
File metadata and controls
312 lines (281 loc) · 15.2 KB
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
309
310
311
312
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<link rel="stylesheet" href="simple.min.css" />
<style>
body {
/* allow body to be wider */
grid-template-columns: 1fr 90% 1fr;
}
mark.comment {
background-color: #ff5555;
}
body>footer {
/* we have a section before the footer, must undo some spacing/borders */
margin-top: 0;
border-top: none;
}
cite {
/* SimpleCSS uses a smaller font */
font-size: inherit;
}
#alea-anim {
max-width: 100ch;
margin-left: auto;
margin-right: auto;
}
@media (prefers-color-scheme: dark) {
/* SimpleCSS turns the opacity down in dark mode: it's a cool idea, but it seemed too much for our video */
#alea-anim video {
opacity: 0.95;
}
}
h2 {
margin-top: 3rem;
font-size: 2rem;
}
h3 {
font-size: 1.44rem;
}
section {
margin-bottom: 2rem;
}
#logos-contrib {
display: flex;
flex-wrap: wrap;
justify-content: space-evenly;
align-items: baseline;
align-content: space-around;
gap: 10px;
margin-top: 25px;
}
#logos-contrib img {
width: 30ch;
}
#logo-fct {
text-align: center;
display: flex;
flex-wrap: wrap;
justify-content: space-evenly;
align-items: center;
align-content: space-around;
gap: 10px;
/*margin-top: 25px;*/
}
#logo-fct img {
width: 35ch;
}
/* when wide enough, show all nav items with the same width */
@media (width > 960px) {
nav {
display: inline-grid;
grid-template-columns: 1fr 1fr 1fr 1fr;
}
}
</style>
<title>Alea-BFT</title>
<meta name="author" content="Afonso Oliveira, André Breda, Diogo S. Antunes, Diogo Silva Santos, Matheus Franco, Henrique Moniz, Rodrigo Rodrigues" />
<meta name="description" content="Alea-BFT is a simple and performant asynchronous BFT consensus protocol with growing real-world adoption." />
<meta name="keywords" content="Alea-BFT,Alea,Consensus,Blockchain,Asynchronous,Randomization,BFT,Byzantine Fault Tolerance,Atomic Broadcast,Total-Order Broadcast,Distributed Systems" />
<meta name="color-scheme" content="light dark" />
</head>
<body>
<header>
<h1>Alea-BFT<br><small>Practical Asynchronous Byzantine Fault Tolerance</small></h1>
<nav>
<a href="#how-alea-works">How Alea-BFT works</a>
<a href="https://arxiv.org/abs/2407.14538">Alea-BFT Paper</a>
<a href="#code">Code</a>
<a href="#contrib">Contributors</a>
</nav>
</header>
<p>Do you need to order elements? Do you enjoy rolling the dice? Are you worried about bad/weird actors? Do you abhor fiddling with tunables? If the answer to one or more of these questions is yes, then Alea-BFT is for you!</p>
<section>
<h2>What is Alea-BFT?</h2>
<p>
Alea-BFT is a BFT (Byzantine-fault tolerant) consensus protocol designed for performance and simplicity.
Unlike partially-synchronous protocols such as <cite><a href="https://pmg.csail.mit.edu/papers/osdi99.pdf">PBFT</a></cite> or <cite><a href="https://entethalliance.org/specs/qbft/v1/">QBFT</a></cite>, which use timeouts to guarantee liveness, Alea is asynchronous, i.e., it does not use predefined timeouts to estimate when a machine might be unresponsive.
Thus, Alea-BFT closely follows network performance while requiring no tuning of timeout values. Very importantly, Alea-BFT is able to make fast progress, even when the participants or the network are not behaving or performing as expected.
</p>
<h2>What is consensus?</h2>
<p>
Consensus is an important problem in distributed systems. It consists in having a set of processes propose values and and then agree on a single proposal.
</p>
<p>
This primitive can be leveraged to build solutions to two other important (and equivalent) problems: total-order broadcast and state machine replication.
(Alea-BFT is designed as a total-order broadcast protocol, but can be easily adapted to the other, related problems.)
</p>
<p>
The focus of Alea is on BFT consensus, i.e., achieving consensus while tolerating Byzantine (arbitrary) faults.
Concretely, we require that consensus is reached among the correct processes even if some (bounded) amount of processes fail arbitrarily. BFT consensus problems is very relevant because it is the core component of important classes of systems, namely blockchains and cryptocurrencies.
</p>
<h2>Wait, I thought consensus was impossible in asynchronous networks!</h2>
<p>
Yes, consensus is impossible in an asynchronous network if we admit the existence of even a single benign fault (a simple machine crash). (This result is known as the <cite><a href="https://dl.acm.org/doi/10.1145/3149.214121">FLP impossibility</a></cite>.) However, this only holds if we restrict ourselves to deterministic protocols.
</p>
<p>
Asynchronous consensus protocols like Alea-BFT exploit <em>randomization</em> instead. Concretely, they reframe the termination property of consensus to be probabilistic: consensus terminates with a probability that approaches 1.
</p>
<p>
Randomized consensus has been studied for decades, and the initial solutions were very elegant, but incurred in a high communication cost.
Alea-BFT integrates techniques from early solutions, modern asynchronous protocols, and partially-synchronous BFT protocols, combining them into an elegant and efficient protocol.
</p>
</section>
<section>
<h2 id="how-alea-works">How Alea-BFT works</h2>
<p>
Alea-BFT brings from partially-synchronous consensus protocols the insight of centralizing work on a rotating leader node.
However, it needs to address several challenges associated with this approach, namely the reliance on a single node, which must be replaced upon failure. This is achieved by rotating the leader after each consensus attempt, and only tasking the leaders with conveying their own (locally-ordered) proposals to the remaining processes, leaving the global ordering decision to a leaderless component.
</p>
<p>
In more detail, the protocol is divided into a broadcast component and an agreement component, connected by a set of FIFO queues.
The broadcast component pushes new requests (depicted as fruits in the animation) to the queues using a consistent broadcast primitive. Then, each process appends requests to its respective queue.
In parallel, the agreement component constantly tries to pop and deliver the heads of these queues. To this end, this component uses a randomized binary agreement primitive to decide if it is safe to conclude a higher-level consensus instance.
Finally, a recovery protocol fetches missing requests in case the agreement succeeds at a node that did not receive the broadcast value.
</p>
<div id="alea-anim" class="container">
<video autoplay muted controls loop preload>
<source src="assets/alea-anim-1080p.mp4" type="video/mp4" />
</video>
</div>
</section>
<section>
<h2 id="publications">Publications and theses</h2>
<div class="notice">
<h3 style="margin-top: 0;">Main Alea-BFT paper</h3>
<a href="https://www.usenix.org/system/files/nsdi24-antunes.pdf">Alea-BFT: Practical Asynchronous Byzantine Fault Tolerance</a>
<br>
Diogo S. Antunes, Afonso N. Oliveira, André Breda, Matheus Guilherme Franco, Henrique Moniz, and Rodrigo Rodrigues
<br>
USENIX Symposium on Networked Systems Design and Implementation, 2024
<br>
An extended version complete with correctness proofs is available <a href="https://arxiv.org/abs/2407.14538">on arXiv</a>
</div>
<ul>
<li>
<a href="https://scholar.tecnico.ulisboa.pt/api/records/K4zKwORZdFJkMJKcqr_ar9UdrD-HeX5oaigD/file/eca882a647e1aaf098721d7acff8bb7490bcabb3c30d203562c9874052a0c45f.pdf">Efficient Asynchronous Byzantine State Machine Replication</a>
<br>
<small>Compares Alea-BFT's fault-free and crash performance with a state-of-the-art partially-synchronous protocol (ISS-PBFT).</small>
<br>
André Breda
<br>
Instituto Superior Técnico, 2024
</li>
<li>
<a href="https://scholar.tecnico.ulisboa.pt/api/records/tDwb4JDmOcOm7BCocf8m3r3YNG_cFbsjA8Ph/file/a18da527b8a0c0db72eeb45390471cea2c46e58b2aeeedb9ef1b1a134495b7bd.pdf">Integrating asynchronous BFT with Ethereum validator networks</a>
<br>
<small>Adapts Alea-BFT for one-shot consensus, and integrates it with a distributed Ethereum validator.</small>
<br>
Matheus Guilherme Franco
<br>
Instituto Superior Técnico, 2023
</li>
<li>
<a href="https://scholar.tecnico.ulisboa.pt/api/records/NeJvz6rI11JQ2tpjL1955QAaR0LbVneGbFY3/file/765a90ed032e06ecaf8c5398f891f1e255c619f997c42e5b81a10264b8516ed8.pdf">Using Randomized Byzantine Consensus to Improve Blockchain Resilience under Attack</a>
<br>
<small>First description of Alea-BFT.</small>
<br>
Afonso N. Oliveira
<br>
Instituto Superior Técnico, 2021
</li>
</ul>
<h2 id="articles">Real-world adoption (blog posts)</h2>
<ul>
<li><cite><a href="https://blog.obol.tech/roadmap-the-distributed-validator-protocol/">The Distributed Validator Protocol Roadmap</a></cite> - Obol presents their roadmap including exploring asynchronous consensus (Alea-BFT) for their distributed validator, published by Oisín Kyne (CTO of Obol) on February, 2024</li>
<li><cite><a href="https://ssv.network/blog/technology/ssv-into-the-future-asyncrounous-bft-protocols/">SSV Into The Future: Asynchronous BFT Protocols</a></cite> - SSV plans to explore asynchronous consensus (namely Alea-BFT) to enhance their network, published by the SSV Network Team on November, 2022</li>
</ul>
<h2>Talks</h2>
<ul>
<li>
Talk on Alea-BFT at <a href="https://www.usenix.org/conference/nsdi24">2024 USENIX Symposium on Networked Systems Design and Implementation</a> by Diogo Antunes, April 2024
<br>
Video: <a href="https://www.youtube.com/watch?v=54cDdLn2_ME">YouTube</a>
</li>
</ul>
<h2 id="code">Code</h2>
<table>
<thead>
<tr>
<th>Name</th>
<th>Description</th>
<th>Language</th>
<th>License</th>
</tr>
</thead>
<tbody>
<tr>
<td><a href="https://github.com/diogoantunes25/AleaBFT">Alea-BFT Prototype</a></td>
<td>Research prototype implementation.</td>
<td>Java</td>
<td>MIT</td>
</tr>
<tr>
<td><a href="https://github.com/MatheusFranco99/ssv">SSV + Alea-BFT</a></td>
<td>Fork of the SSV distributed Ethereum validator, incorporating Alea-BFT for consensus.</td>
<td>Go</td>
<td>GPL 3.0</td>
</tr>
<tr>
<td><a href="https://github.com/abread/mir">Mir + Alea-BFT</a></td>
<td>Fork of the Mir Framework - Mir is expected to become a consensus layer for Filecoin, and now includes support for Alea-BFT consensus (in the process of being upstreamed).</td>
<td>Go</td>
<td>Apache 2.0</td>
</tr>
</tbody>
</table>
<h2 id="contrib">Contributors</h2>
<p>Alea-BFT is the joint effort of the following students and faculty at <a href="https://tecnico.ulisboa.pt/en">IST - Lisbon</a> and its computer science research lab, <a href="https://www.inesc-id.pt">INESC-ID</a>:</p>
<ul>
<li>Afonso Oliveira</li>
<li>André Breda</li>
<li>Diogo S. Antunes</li>
<li>Diogo Silva Santos</li>
<li>Matheus Franco</li>
<li>Henrique Moniz and Rodrigo Rodrigues (faculty).</li>
</ul>
<div id="logos-contrib">
<a href="https://tecnico.ulisboa.pt/en">
<picture id="logo-ist">
<source srcset="assets/IST_A_RGB_NEG.png" media="(prefers-color-scheme: dark)" />
<img src="assets/IST_A_RGB_POS.png" alt="IST Logo" />
</picture>
</a>
<a href="https://www.inesc-id.pt/">
<picture id="logo-inesc">
<source srcset="assets/INESC-ID-new-logo_version-01B.png" media="(prefers-color-scheme: dark)" />
<img src="assets/INESC-ID-new-logo_version-01A.png" alt="INESC-ID Logo" />
</picture>
</a>
</div>
</section>
<div id="logo-fct">
<p>
This work is supported by the European Union's Horizon 2020 research and innovation programme under grant agreement No. 952226, <a href="https://bigerachair.tecnico.ulisboa.pt/">project BIG</a>, and the <a href="https://www.fct.pt/en/">Portuguese Foundation for Science and Technology (FCT)</a>.
</p>
<a href="https://bigerachair.tecnico.ulisboa.pt/">
<picture>
<source srcset="assets/logo_big_darkbg.svg" media="(prefers-color-scheme: dark)" />
<img src="assets/logo_big_lightbg.svg" alt="Project BIG Logo" />
</picture>
</a>
<a href="https://www.fct.pt/en/">
<picture>
<source srcset="assets/2022_FCT_Logo_B_horizontal_branco.png" media="(prefers-color-scheme: dark)" />
<img src="assets/2022_FCT_Logo_B_horizontal_preto.png" alt="FCT Logo" style="width: 40ch;"/>
</picture>
</a>
</div>
<footer>
<p>
Caught a typo? Want to show off your new awesome Alea-BFT usecase?
<br>
<a href="https://github.com/abread/aleabft-website/blob/main/index.html">Edit this page on GitHub</a><!-- TODO: update with final link -->
</p>
<div xmlns:cc="http://creativecommons.org/ns#" >This work is licensed under <a href="https://creativecommons.org/licenses/by/4.0/?ref=chooser-v1" target="_blank" rel="license noopener noreferrer" style="display:inline-block;">CC BY 4.0<img style="height:22px!important;margin-left:3px;vertical-align:text-bottom;" src="https://mirrors.creativecommons.org/presskit/icons/cc.svg?ref=chooser-v1" alt=""><img style="height:22px!important;margin-left:3px;vertical-align:text-bottom;" src="https://mirrors.creativecommons.org/presskit/icons/by.svg?ref=chooser-v1" alt=""></a></div>
<div>This website was inspired by the <cite><a href="https://raft.github.io/">Raft</a></cite> and <cite><a href="https://fpaxos.github.io/">Flexible Paxos</a></cite> protocol websites.</div>
</footer>
</body>
</html>