동현 유
척척석사
동현 유
전체 방문자
오늘
어제
  • 분류 전체보기 (181)
    • BlockChain (48)
      • [paper] Consensus (13)
      • [paper] Execution (19)
      • [paper] Storage (5)
      • [paper] ZKP (1)
      • [paper] Oracle (1)
      • Blockchains (9)
    • Java (19)
      • Java의 정석 (13)
      • Java 파헤치기 (5)
    • Python (20)
      • Python 뜯어보기 (6)
      • 데이터 분석 기초 (5)
      • Python 기초 강의 (6)
      • Python 기초 강의 부록 (3)
    • Golang (0)
    • MySQL (3)
      • programmers (2)
      • 기본 문법 (0)
    • 웹 프로젝트 (IBAS) (36)
      • Django 레거시 (14)
      • SpringBoot api 개편 (14)
      • Infra (3)
      • 서버 장애 기록 (4)
      • 신입팀원 교육 자료 (1)
    • CS (30)
      • Operating System (22)
      • Computer Security (3)
      • Network (4)
      • DBMS (1)
    • 책 (10)
      • 도메인 주도 설계 철저 입문 (9)
      • Real MySQL 8.0 (1)
    • BOJ 문제 풀이 (3)
    • 이러쿵저러쿵 (10)
    • 회고 (1)

인기 글

최근 댓글

최근 글

hELLO · Designed By 정상우.
동현 유

척척석사

[논문 세미나] Bullshark: DAG BFT Protocols Made Practical
BlockChain/[paper] Consensus

[논문 세미나] Bullshark: DAG BFT Protocols Made Practical

2023. 7. 5. 16:04

Authors:

Alexander Spiegelman, Neil Giridharan, Alberto Sonnino, Lefteris Kokoris-Kogias

 

Journal/Conference:

ACM CCS '22

 

Source:

https://arxiv.org/abs/2201.05677

 

Presentation material:

2023-07-05 Bullshark DAG BFT Protocols Made Practical.pdf
1.00MB

 


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, 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 mechanisms. Bullshark achieves this while maintaining all the desired properties of its predecessor DAG-Rider. 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 (Narwhal & Tusk). It is highly efficient, achieving for example, 125,000 transaction 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.



Introduction

  • Two problems of DAG-Rider based protocols
    1. optimize for the worst case asynchornous network assumption. do not take advantages of synchronous cases.
    2. assumming unbounded memory in order to preserve fairness.
  • Provide fast path(partial synchronous) / slow path(asynchronous) by improving Tusk.

Recap


Challenges

 

(Theoretical)

  • Asynchronous DAG-base BFT protocols annot guarantee derterministic liveness during synchronous periods.
    => adopt timeout during DAG contruction to get message from leader.
  • take advantage of a common-case synchronous network without sacrificing latency in the asynchronous worst case.
    •   Two types of votes: (1) 'steady-state' for the predefined leader in 1st and 3rd round, (2) 'fallback' for the random leader in 1st round
    •  To reduce latency in synchronous periods, the 3rd round of a wave has a predefined leader as well and it takes two rounds to commit a steady-state leader.
    •   A vertex's voting type is determined bywheter or not its source(the party that broadcasted it) commited a leader in the previous wave)

(Practical)

  • Bounded memory implementation of Bullshark guarantees timely fairness only during synchornous. This means that after GST all messages by honest parties make it into the DAG in finite time and before garbage collection. For all the other mesages, use Tusks's approach of retransmission.

DAG construction


Bullshark


GC

 

'BlockChain > [paper] Consensus' 카테고리의 다른 글

[논문 세미나] Themis: Fast, Strong Order-Fairness in Byzantine Consensus  (0) 2025.03.06
[논문 세미나] Shoal: Improving DAG-BFT Latency And Robustness  (0) 2023.08.04
[KCC 2023] Survey on Asynchronous BFT consensus Algorithms for Scalable and Robust Blockchain  (2) 2023.06.21
[논문 리뷰] Narwhal and Tusk: A DAG-based Mempool and Efficient BFT Consensus  (0) 2023.04.23
[논문 세미나] HotStuff: BFT Consensus with Linearity and Responsiveness  (0) 2023.04.22
    동현 유
    동현 유
    Fault Tolerant System Researcher for more Trustful World and Better Lives. (LinkedIn: https://www.linkedin.com/in/donghyeon-ryu-526b8a276/)

    티스토리툴바