Bullshark: DAG BFT protocols made practical

Spiegelman A, Giridharan N, Sonnino A, Kokoris Kogias E. 2022. Bullshark: DAG BFT protocols made practical. Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. CCS: CConference on Computer and Communications Security, 2705–2718.

Download (ext.)

Conference Paper | Published | English

Scopus indexed
Author
Spiegelman, Alexander; Giridharan, Neil; Sonnino, Alberto; Kokoris Kogias, LefterisISTA
Department
Abstract
We present Bullshark, the first directed acyclic graph (DAG) based asynchronous Byzantine Atomic Broadcast protocol that is optimized for the common synchronous case. Like previous DAG-based BFT protocols [19, 25], Bullshark requires no extra communication to achieve consensus on top of building the DAG. That is, parties can totally order the vertices of the DAG by interpreting their local view of the DAG edges. Unlike other asynchronous DAG-based protocols, Bullshark provides a practical low latency fast-path that exploits synchronous periods and deprecates the need for notoriously complex view-change and view-synchronization mechanisms. Bullshark achieves this while maintaining all the desired properties of its predecessor DAG-Rider [25]. Namely, it has optimal amortized communication complexity, it provides fairness and asynchronous liveness, and safety is guaranteed even under a quantum adversary. In order to show the practicality and simplicity of our approach, we also introduce a standalone partially synchronous version of Bullshark, which we evaluate against the state of the art. The implemented protocol is embarrassingly simple (200 LOC on top of an existing DAG-based mempool implementation). It is highly efficient, achieving for example, 125,000 transactions per second with a 2 seconds latency for a deployment of 50 parties. In the same setting, the state of the art pays a steep 50% latency increase as it optimizes for asynchrony.
Publishing Year
Date Published
2022-11-01
Proceedings Title
Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security
Page
2705–2718
Conference
CCS: CConference on Computer and Communications Security
Conference Location
Los Angeles, CA, United States
Conference Date
2022-11-07 – 2022-11-11
IST-REx-ID

Cite this

Spiegelman A, Giridharan N, Sonnino A, Kokoris Kogias E. Bullshark: DAG BFT protocols made practical. In: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. Association for Computing Machinery; 2022:2705–2718. doi:10.1145/3548606.3559361
Spiegelman, A., Giridharan, N., Sonnino, A., & Kokoris Kogias, E. (2022). Bullshark: DAG BFT protocols made practical. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security (pp. 2705–2718). Los Angeles, CA, United States: Association for Computing Machinery. https://doi.org/10.1145/3548606.3559361
Spiegelman, Alexander, Neil Giridharan, Alberto Sonnino, and Eleftherios Kokoris Kogias. “Bullshark: DAG BFT Protocols Made Practical.” In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, 2705–2718. Association for Computing Machinery, 2022. https://doi.org/10.1145/3548606.3559361.
A. Spiegelman, N. Giridharan, A. Sonnino, and E. Kokoris Kogias, “Bullshark: DAG BFT protocols made practical,” in Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, Los Angeles, CA, United States, 2022, pp. 2705–2718.
Spiegelman A, Giridharan N, Sonnino A, Kokoris Kogias E. 2022. Bullshark: DAG BFT protocols made practical. Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. CCS: CConference on Computer and Communications Security, 2705–2718.
Spiegelman, Alexander, et al. “Bullshark: DAG BFT Protocols Made Practical.” Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, Association for Computing Machinery, 2022, pp. 2705–2718, doi:10.1145/3548606.3559361.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Sources

arXiv 2201.05677

Search this title in

Google Scholar
ISBN Search