[Paper] 헤링: DAG 기반 블록체인 합의에서 병렬 배치 순서 공정성

Source: arXiv - 2605.23648v1

Overview

The paper introduces Herring, a new consensus protocol for DAG‑based blockchains that delivers batch‑order‑fairness without sacrificing performance. By parallelizing the costly graph‑construction step that underlies fairness guarantees, Herring matches the raw throughput of high‑speed BFT systems while preventing the transaction‑ordering attacks (MEV) that plague DeFi platforms.

주요 기여

• γ‑배치‑순서‑공정성 on a DAG – DAG 기반 BFT 환경에서 트랜잭션 배치를 위한 조정 가능한 공정성 보장(파라미터 γ)을 제공하는 최초의 프로토콜.
• 병렬 공정성 레이어 – 단일 리더 또는 직렬 병목 현상에서 주된 그래프 구성 작업을 CPU 중심의, 커밋된 서브‑DAG 전체에 걸쳐 완전 병렬화 가능한 작업으로 이동시킴.
• 신뢰성 브로드캐스트에 기반한 누락‑엣지 해결 – 브로드캐스트 단계에서 불완전한 DAG 엣지를 해결하는 새로운 기법으로, 추가 동기화 라운드를 없앰.
• 활성도 버그 발견 및 패치 – FairDAG‑RL 및 DoD에서 공정성 레이어를 정지시킬 수 있는 이전에 알려지지 않은 공격을 식별하고, 레퍼런스 구현에 통합된 구체적인 패치를 제공함.
• 구현 및 평가 – Rust Narwhal & Tusk 스택 위에 구축; 실험 결과는 FairDAG‑RL 대비 90 % 높은 포화 처리량 및 DoD‑W 대비 100 % 높은 처리량을 보여주며, 기본 Narwhal & Tusk 처리량과 약 ~10 k tx/s 차이 내에 머무름.

방법론

1. System Model – 부분 동기식 네트워크와 f개의 비잔틴 복제본(일반적인 BFT 설정)을 가정하고, 각 복제본이 독립적으로 트랜잭션을 제안할 수 있는 DAG‑기반 데이터 구조를 사용합니다.
2. Batch‑Order‑Fairness (γ‑batch‑OF) – 엄격한 전체 순서를 강제하는 대신, 프로토콜은 크기 B인 두 배치에 대해 순서가 정직한 복제본들의 다수 의견을 완화 계수 γ까지 반영하도록 보장합니다. 이는 문제를 충분히 완화하여 병렬성을 가능하게 하면서도 체계적인 프런트‑러닝을 방지합니다.
3. Parallel Graph Construction
   • 정상적인 BFT 커밋 단계가 끝난 후, 각 복제본은 커밋된 트랜잭션의 sub‑DAG를 로컬에서 구축합니다.
   • 누락된 엣지(즉, 브로드캐스트 중 관찰되지 않은 종속성)는 신뢰할 수 있는 브로드캐스트 메타데이터를 사용해 실시간으로 추론하여 별도의 “fairness round”를 피합니다.
   • 그런 다음 sub‑DAG들은 결정론적인 방식으로 병합되며, 이는 여러 CPU 코어에서 동시에 수행될 수 있습니다.
4. Safety & Liveness Proofs – 논문에 스케치된 형식적 논증은 병렬 구축이 BFT 안전 보장을 유지하고, 비잔틴 공격 하에서도 γ‑batch‑OF 속성을 만족함을 보여줍니다.
5. Implementation – 기존 Narwhal & Tusk 코드베이스(Rust)에 통합하고, 공정한 head‑to‑head 비교를 위해 FairDAG‑RL 및 DoD‑W를 재구현했으며, 발견된 라이브니스 패치를 추가했습니다.

결과 및 발견

해석: Herring의 병렬 공정성 레이어는 다른 프로토콜을 저하시키는 고전적인 “공정성 병목”을 제거하여, 원시 BFT 처리량 대비 몇 퍼센트 안에 머무르면서도 강력한 순서 보장을 제공합니다. 지연 시간 개선은 추가 합의 라운드가 감소한 데서 비롯됩니다.

Source: …

Practical Implications

• MEV 완화 for DeFi – DEX, 대출 플랫폼 또는 기타 스마트‑컨트랙트 시스템을 구축하는 개발자는 Herring(또는 변형)을 채택하여 채굴자/검증자에 의해 트랜잭션 순서가 체계적으로 조작되지 않도록 할 수 있으며, 이를 통해 프론트‑러닝 손실을 감소시킬 수 있습니다.
• 확장 가능한 멀티‑프로포저 블록체인 – 이미 DAG‑기반 합의를 사용하고 있는 프로젝트(Aptos, Sui 또는 맞춤형 롤‑업 등)는 핵심 BFT 엔진을 재설계하지 않고도 Herring의 공정성 레이어를 파이프라인에 쉽게 삽입할 수 있습니다.
• 더 나은 하드웨어 활용 – 공정성 작업이 CPU‑바운드이며 병렬 처리되기 때문에, 최신 클라우드 또는 엣지 환경에서는 수평 확장이 가능해집니다(코어 수 ↑ → 공정성 처리량 ↑). 별도의 네트워크 대역폭 증설이 필요하지 않습니다.
• 단순화된 검증자 소프트웨어 – 결합된 missing‑edge 해결 방식은 별도의 “공정성 라운드”를 없애 코드 복잡성을 낮추고 검증자 클라이언트의 공격 표면을 줄여줍니다.
• 기존 스택과의 상호 운용성 – Herring은 Narwhal & Tusk(오픈‑소스 Rust) 위에 구축되어 있으므로, 팀은 기존 Rust‑기반 검증자 노드에 최소한의 변경만으로 도입할 수 있습니다.

제한 사항 및 향후 연구

• γ‑파라미터 튜닝 – 공정성 보장은 선택된 γ에 의존하며, 주어진 워크로드에 최적값을 선택하려면 실험적 튜닝이 필요하고 지연 시간에 영향을 줄 수 있습니다.
• 제안자들의 정직한 다수 가정 – 대부분의 BFT 프로토콜과 마찬가지로 Herring의 안전성은 < 1/3 비잔틴 복제본에 의존합니다; 협조된 Sybil 공격과 같은 극단적인 적대적 상황은 다루어지지 않습니다.
• 평가가 합성 워크로드에 제한됨 – 실험은 생성된 트랜잭션 스트림을 사용했으며, 복잡한 계약 상호작용을 포함한 실제 DeFi 트래픽은 숨겨진 병목을 드러낼 수 있습니다.
• 네트워크 수준 공격 – 라이브니스 버그는 수정되었지만, 프로토콜은 여전히 Narwhal & Tusk의 기본 네트워크 가정을 물려받습니다; 향후 연구에서는 높은 패킷 손실이나 표적 DoS 상황에서의 견고성을 탐구할 수 있습니다.
• 크로스 샤드 공정성 확장 – 현재 설계는 단일 DAG에 초점을 맞추고 있으며, γ‑batch‑OF를 여러 샤드나 사이드체인에 적용하는 것은 아직 미해결 연구 과제입니다.

핵심 요약: Herring은 공정성이 성능 비용을 동반하지 않아도 된다는 것을 보여줍니다. 공정성 레이어를 병렬로 재구성함으로써, 블록체인 플랫폼이 MEV를 억제하면서도 트랜잭션 처리량을 경쟁력 있게 유지할 수 있는 실용적인 경로를 제공합니다.

저자

• Marko Putnik
• Jérémie Decouchant

논문 정보

• arXiv ID: 2605.23648v1
• 분류: cs.DC
• 출판일: 2026년 5월 22일
• PDF: PDF 다운로드