💻 computer science

FairDAG: Consensus Fairness over Multi-Proposer Causal Design

이 논문은 기존 리더 기반 시스템의 처리량 및 조작 한계를 극복하기 위해 공정성 프로토콜을 DAG 기반 합의와 통합하여, 블록체인 네트워크에서 우수한 트랜잭션 순서 공정성과 성능을 달성하는 새로운 프레임워크인 FairDAG를 소개한다.

원저자: Dakai Kang, Junchao Chen, Tien Tuan Anh Dinh, Mohammad Sadoghi

게시일 2026-01-30

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Dakai Kang, Junchao Chen, Tien Tuan Anh Dinh, Mohammad Sadoghi

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

수천 명의 사람들이 동시에 물건을 사고팔려고 노력하는 분주한 디지털 시장을 상상해 보십시오. 이 시장에서는 거래가 발생하는 순서가 매우 중요합니다. 만약 당신이 다른 사람보다 먼저 희귀 아이템을 구매한다면 당신이 그것을 얻게 되지만, 만약 당신이 나중에 구매한다면 기회를 놓치거나 더 많은 비용을 지불해야 할 수도 있습니다.

블록체인(암호화폐의 기반 기술)의 세계에는 한 가지 문제가 있습니다. 바로 거래 순서를 결정하는 책임자(블록 제안자)가 사기꾼이 될 수 있다는 점입니다. 그들은 목록을 살펴보고, 자신에게 이득이 되는 움직임을 포착하면, 정직한 사람들을 뒤로 밀어내고 자신들이 돈을 벌 수 있도록 줄의 순서를 재배치할 수 있습니다. 이는 마치 VIP 고객이 오는 것을 보고 줄을 새치기하게 해주거나, 심지어는 친구에게 마지막 남은 물건을 먼저 팔기 위해 줄의 순서를 조작하는 점원과 같습니다.

기존의 솔루션들은 모든 사람의 선호도를 수집하여 순서를 결정하는 단 한 명의 "수석 점원"(리더)을 두는 방식으로 이 문제를 해결하려 했습니다. 하지만 이는 두 가지 새로운 문제를 야기했습니다.

병목 현상: 만약 수석 점원이 느리거나 과부하가 걸리면, 상점 전체의 속도가 느려집니다.
사기: 만약 그 수석 점원이 사기꾼이라면, 그는 목록을 독점하고 있기 때문에 여전히 줄을 조작할 수 있습니다.

FairDAG의 등장: "그룹 라인" 솔루션

이 논문은 이 시장을 조직하는 새로운 방법인 FairDAG를 소개합니다. 단 한 명의 수석 점원에 의존하는 대신, FairDAG는 멀티 프로포저(Multi-Proposer) 시스템을 사용합니다. 이것은 마치 거대하고 서로 연결된 캐셔(복제본)들의 네트워크와 같아서, 그들이 각자의 거래 목록을 동시에 외치는 것과 같습니다.

작동 방식은 다음과 같습니다.

1. 신뢰의 웹 (DAG)

단일한 줄 대신, 거미줄(Directed Acyclic Graph, DAG)을 상상해 보십시오. 캐셔가 거래 목록을 작성할 때마다, 그들은 단순히 한 사람에게 목록을 보내는 것이 아니라, 최근에 접했던 여러 다른 캐셔들의 목록에 자신의 목록을 부착합니다.

이것이 도움이 되는 이유: 만약 한 명의 캐셔가 거래를 숨기거나 속임수를 쓰려고 해도, 이 웹 구조 덕분에 다른 모든 사람의 목록이 결국 서로 연결되어 실제로 어떤 일이 일민지를 확인하게 됩니다. 전체 구조를 감지하지 못한 채 웹에서 하나의 실을 쉽게 삭제하는 것은 불가능합니다.

2. 두 가지 공정함의 방식

논문은 원하는 엄격함의 정도에 따라 줄을 세우는 두 가지 특정 "규칙"을 제안합니다.

FairDAG-AB (절대적 규칙): 이것은 엄격한 "선착순" 규칙과 같습니다. 만약 모두가 A가 B보다 먼저 도착했다는 것에 동의한다면, A가 반드시 먼저 가야 합니다. 시스템은 정직한 캐셔들이 해당 거래를 목격한 시점을 기준으로 모든 거래에 대해 특정 "티켓 번호"를 계산합니다. 설령 사기꾼이 덱을 섞으려고 시도하더라도, 수학적 계산을 통해 정직한 티켓 번호가 승리하도록 보장합니다.
FairDAG-RL (상대적 규칙): 이것은 조금 더 유연한 "그룹화" 규칙입니다. 때로는 누가 먼저 도착했는지 정확히 알 수 없는 경우가 있습니다(마치 두 사람이 동시에 문을 통과하는 경우처럼). 정확히 누가 먼저인지 다투는 대신, 이 규칙은 그들을 함께 묶습니다. 만약 90%의 정직한 캐셔들이 A가 B보다 먼저라고 보았다면, A를 B보다 먼저 배치합니다. 만약 의견이 팽팽하다면, 그들을 같은 "배치(batch)"에 넣습니다. 이 방식은 더 빠르고 복잡한 상황을 더 잘 처리합니다.

3. 사기꾼을 물리치기

논문은 FairDAG가 단일 리더 대신 다수의 캐셔를 사용하는 웹 구조를 사용하기 때문에 다음과 같은 효과가 있음을 보여줍니다.

사기꾼은 숨을 수 없다: 사기꾼은 정직한 사람들의 목록을 무시할 수 없습니다. 왜냐하면 웹 구조가 그들의 목록이 결국 포함되도록 강제하기 때문입니다.
속도: 모든 사람이 동시에 자신의 목록을 외치고 있기 때문에, 시스템은 한 명의 느린 사람을 기다리느라 멈춰 서지 않습니다. 이 시스템은 기존의 "단일 리더" 시스템보다 훨씬 빠르게 거래를 처리합니다.

결과

저자들은 자신들의 시스템을 기존 방식(Pompe 및 Themis와 같은)과 비교 테스트했습니다. 그 결과는 다음과 같습니다.

더 빠릅니다: FairDAG는 단일 병목 현상이 없기 때문에 더 많은 초당 거래량(throughput)을 처리합니다.
더 공정합니다: 사기꾼들이 순서를 조작하려고 시도하더라도(목록을 역전시키거나 특정 거래를 지연시키는 등), FairDAG는 기존 시스템보다 훨씬 더 정확하게 순서를 유지합니다.
더 견고합니다: 인터넷이 느리거나 일부 캐셔의 응답이 늦더라도, 시스템은 멈추지 않고 계속 진행됩니다.

요약하자면

FairDAG는 쉽게 매수될 수 있는 단 한 명의 관리자를 민주적이고 상호 연결된 팀으로 교체하는 것과 같습니다. 모든 사람이 자신의 목록을 동시에 외치고 그 목록들을 웹으로 엮음으로써, 단 한 명의 사기꾼이 순서를 조작하는 것을 거의 불가능하게 만듭니다. 또한 줄이 빠르게 움직이도록 유지합니다. 이는 시스템을 너무 크고 긴밀하게 연결하여 단 한 명의 사기꾼이 통제할 수 없게 만듦으로써 "순서 조작 위기"를 해결합니다.

기술 요약: FairDAG: 다중 제안자 인과적 설계를 통한 합의 공정성

1. 문제 정의

탈중앙화 금융(DeFi)의 부상은 블록체인 트랜잭션 순서 지정의 치명적인 취약점인 **최대 추출 가능 가치(Maximal Extractable Value, MEV)**를 부각시켰다. 적대적인 블록 제안자는 트랜잭션 순서를 조작하여 프런트 러닝(front-running), 샌드위치 공격(sandwich attacks), 또는 청산 조작을 실행함으로써 다른 참여자들의 희생을 바탕으로 이익을 추출할 수 있다.

Pompe 및 Themis와 같은 기존의 공정성 프로토콜은 쿼럼(quorum)의 로컬 트랜잭션 순서들을 집계하여 전역 순서를 도출함으로써 이를 완화하려고 시도한다. 그러나 이러한 프로토콜들은 리더 기반 합의(예: PBFT, Hot Stuff)에 의존한다. 이러한 아키텍처는 다음과 같은 두 가지 주요 한계를 초래한다:

단일 장애점 병목 현상(Single-Point-of-Failure Bottleneck): 단일 리더가 로컬 순서들을 수집한다. 만약 리더가 비잔틴(Byzantine) 노드라면, 최종 시퀀스를 조작하기 위해 특정 순서들을 선택적으로 수집하거나 트랜잭션을 검열할 수 있다. 또한, 리더가 정직하더라도 참여자 수가 증가함에 따라 메시지 복잡도가 이차 함수적으로 증가하므로 단일 리더는 성능 병목 지점이 된다.
조작에 대한 취약성: 비잔틴 리더는 특정 정당한 복제본(replica)의 로컬 순서들을 제외함으로써 유효 쿼럼 크기를 줄이고, 트랜잭션 의존성을 조작하거나 특정 트랜잭션을 지연시키는 것을 용이하게 할 수 있다.

본 논문은 잘 설계된 공정성 프로토콜이 순서 조작에 대한 회복력을 갖추고, 정당한 참여자의 요구 사항을 최소화하며, 높은 성능(처리량 및 낮은 지연 시간)을 유지해야 한다고 주장한다.

2. 방법론: FairDAG 프레임워크

저자들은 DAG 기반 합의 프로토콜(예: Tusk, DAG-Rider, Bullshark) 상에서 공정성 프로토콜을 실행하는, 합의 계층과 공정성 계층을 분리한 FairDAG 프레임워크를 제안한다.

핵심 아키텍처

FairDAG는 두 개의 뚜렷한 계층으로 작동한다:

DAG 계층 (합의): 모든 복제본이 라운드별로 블록(정점, vertex)을 동시 제안하는 다중 제안자 설계를 활용하여 DAG를 형성한다.
- 다중 제안자 설계: 단일 리더 병목 현상을 제거하여 병렬적인 블록 제안을 가능하게 하고 더 높은 처리량을 제공한다.
- 유효성 속성(Validity Property): DAG의 인과적 구조는 정당한 복제본이 정점을 브로드캐스트하면 모든 정당한 복제본이 결국 이를 커밋함을 보장한다. 이는 비잔틴 리더가 정당한 복제본의 순서들을 선택적으로 무시하는 것을 방지한다.
공정성 계층 (Fairness Layer): DAG 계층으로부터 커밋된 로컬 순서들(sub-DAGs)을 처리하여 최종적이고 공정한 트랜잭션 순서를 생성한다.

프로토콜 변형

본 논문은 서로 다른 공정성 속성을 보장하는 두 가지 FairDAG 변형을 소개한다.

A. FairDAG-AB (절대적 공정성, Absolute Fairness)

목표: **순서 선형성(Ordering Linearizability)**을 보장한다. 만약 모든 정당한 복제본이 $T_1$ 을 $T_2$ 보다 먼저 받는다면, $T_1$ 은 반드시 $T_2$ 보다 앞서 순서가 지정되어야 한다.
메커니즘:
- 각 트랜잭션에는 **할당된 순서 지표(Assigned Ordering Indicator, AOI)**가 부여된다.
- 프로토콜은 관찰되고 커밋된 순서 지표를 추적하기 위해 **순서 지표 관리자(Ordering Indicator Manager, OIM)**를 사용한다.
- DAG 커밋의 지연 시간을 처리하기 위해, 미커밋 트랜잭션에 대한 **최저 가능 AOI(Lowest Possible AOI, LPAOI)**를 계산한다. 트랜잭션은 그 AOI가 다른 대기 중인 트랜잭션들의 LPAOI보다 엄격히 낮을 때만 최종 확정된다.
- 최종 순서는 AOI를 기준으로 트랜잭션을 정렬하여 결정된다.

B. FairDAG-RL (상대적 공정성, Relative Fairness)

목표: ** $\gamma$ -배치 순서 공정성( $\gamma$ -Batch-Order-Fairness)**을 보장한다. 만약 $\gamma$ 비율의 정당한 복제본이 $T_1$ 을 $T_2$ 보다 먼저 받는다면, $T_1$ 은 $T_2$ 보다 늦지 않게 순서가 지정된다.
메커니즘:
- 노드가 트랜잭션이고 에지가 로컬 순서로부터 파생된 순서 선호도를 나타내는 **의존성 그래프(Dependency Graph)**를 구축한다.
- 임계값 최적화: 리더 제외 가능성으로 인해 $n-2f$ 개의 커밋된 순서에 의존하는 리더 기반 프로토콜(Themis)과 달리, FairDAG-RL은 DAG의 유효성 속성을 활용하여 최소 $n-f$ 개의 순서가 커밋됨을 보장한다. 결과적으로 에지 생성 임계값을 $\frac{n-2f}{2}$ 에서 $\frac{n-f}{2}$ 로 높인다.
- 그래프 응축(Graph Condensation): 프로토콜은 의존성 그래프에서 강결합 컴포넌트(Strongly Connected Components, SCC)를 식별한다. 프로토콜은 "견고한(solid)" 노드(충분한 커밋된 순서를 가진 노드)의 순서를 확정하고, "그늘진(shaded)" 노드들을 그들이 견고해질 때까지 후속 그래프에 다시 추가한다.
- 이 접근 방식은 공정성을 보장하기 위해 필요한 정당한 복제본의 최소 수를 줄인다 (예: $\gamma=1$ 일 때 $n > 4f$ 대신 $n > 3f$ 요구).

3. 주요 기여

새로운 프레임워크: 리더 기반 시스템의 처리량 및 조작 취약성을 해결하기 위해 공정성 프로토콜을 다중 제안자 DAG 기반 합의와 통합한 최초의 프레임워크인 FairDAG를 제안하였다.
FairDAG-AB: DAG 커밋 규칙과 호환되는 적응형 LPAOI 메커니즘을 사용하여 순서 선형성을 보장하는 절대적 공정성 프로토콜을 제시하였다.
FairDAG-RL: DAG의 유효성을 활용하여 의존성 그래프 구축을 위한 임계값을 낮춤으로써, Themis와 같은 최신 리더 기반 프로토콜보다 더 적은 정당한 참여자를 요구하고 성능을 개선하였다.
새로운 DAG 구축 규칙: 공정성 속성이 적대적 참여자에 의해 보존되도록 하는 특정 규칙(예: 느린 복제본을 위한 약한 에지 포함, 이전 로컬 정점에 대한 강한 에지 유지)을 도입하였다.
포괄적 평가: 안전성, 활성(liveness) 및 공정성에 대한 광범한 분석적 증명과 실험적 검증을 수행하였다.

4. 실험 결과

저자들은 Apache ResilientDB에 FairDAG를 구현하여 PBFT, Pompe, Themi, RCC, Tusk와 같은 베이스라인 모델들과 비교하였다.

처리량 (Throughput):
- FairDAG는 리더 기반 공정성 프로토콜(Pompe 및 Themis)보다 성능이 크게 우수하다.
- FairDAG-AB는 Pompe보다 30.2%에서 52.6% 더 높은 처리량을 달성했다.
- FairDAG-RL은 단일 지역 설정에서 Themis보다 5.1% ~ 7.5% 높은 처리량을 달성했으며, 기반이 되는 DAG 합의의 견고성 덕분에 지리적 분산 환경에서는 이 격차가 **42.1%**까지 증가했다.
지연 시간 (Latency):
- FairDAG-AB는 (Tusk의 기반 커밋 지연 시간으로 인해) Pompe보다 약간 높은 지연 시간을 보이지만 여전히 경쟁력 있는 수준이다.
- FairDAG-RL은 결함이 있는 복제본의 수( $f$ )가 증가함에 따라 Themis보다 낮은 지연 시간을 보여준다. 이는 Themis가 공정성을 보장하기 위해 더 많은 정당한 복제본을 필요로 하여 오버헤드가 증가하기 때문이다.
적대적 행동에 대한 회복력:
- 리더 실패: 리더를 결함 상태로 만든 실험에서, Pompe와 Themis는 뷰 체인지(view-change) 동안 처리량 저하를 겪었다. 반면 FairDAG 변형들은 다중 제안자 설계 덕분에 성능 저하를 보이지 않았다.
- 순서 조작: 비잔틴 복제본의 "순서 역전(Reversing Order)" 및 "표적 지연(Targeted Delay)" 공격 하에서도, FairDAG-AB와 FairDAG-RL은 Pompe 및 Themis에 비해 일관되게 더 높은 비율의 올바르게 정렬된 트랜잭션 쌍을 유지했다. DAG 계층의 유효성 속성이 비잔틴 행위자가 순서들을 선택적으로 제외하는 능력을 효과적으로 억제했다.

5. 의의 및 주장

본 논문은 FairDAG가 리더 기반 시스템에 내재된 성능과 공정성 사이의 트레이드오프를 해결함으로써 블록체인 공정성의 중요한 진전을 이루었다고 주장한다.

회복력: 단일 리더를 제거함으로써, 적대자가 로컬 순서들을 선택적으로 수집하여 최종 순서를 조작하는 것을 방지한다.
효율성: 다중 제안자 설계는 처리량 병목 현상을 완화하여 공정성 프로토콜이 네트워크 규모와 워크로드에 따라 더 잘 확장될 수 있도록 한다.
요구 사항 감소: DAG의 유효성 속성은 FairDAG-RL이 Themis와 같은 최신 리더 기반 프로토콜보다 더 적은 정당한 참여자로도 공정성 보장을 달성할 수 있게 한다.

저자들은 FairDAG가 정상 및 적대적 조건 모두에서 우수한 성능을 달면서도 트랜잭션 순서에 대한 적대적 조작을 효과적으로 제한하며, 따라서 탈중앙화 금융 및 기타 중요한 블록체인 애플리케이션을 위한 실행 가능한 솔루션이 된다고 결론짓는다.