Blockchain과 DAG

같은 자리에서 DAG라는 자료구조를 들고 출발한 두 진영이 있다. 한쪽은 그래프를 끝까지 끌고 가서 sub-second finality에 6자리 TPS를 찍었고, 다른 한쪽은 결국 그래프를 일자로 펴서 EVM 호환을 택했다.

블록체인을 처음 배울 때는 “블록이 줄줄이 이어진 자료구조”로 그림이 그려진다.

그런데 한참 공부하다 보면 Sui의 Mysticeti나 Avalanche의 X-Chain처럼 내부 구조가 그래프인 시스템들을 만나게 된다.

이들의 공통점은 DAG(Directed Acyclic Graph)다. 그런데 같은 DAG를 갖고도 도착한 곳이 다르다.

DAG

DAG는 방향성 비순환 그래프다. 풀어 쓰면 두 가지 조건을 만족하는 그래프를 말한다.

Directed: 모든 간선에 방향이 있다 (A → B는 있어도 A ← B는 따로 둬야 한다)
Acyclic: 어느 노드에서 출발해 간선을 따라가더라도 자기 자신으로 돌아올 수 없다

graph LR
    A --> B
    A --> C
    B --> D
    C --> D
    D --> E
    C --> E

소프트웨어 엔지니어링에서 DAG는 이미 익숙한 개념이다.

Git 커밋 그래프, Make나 Bazel의 빌드 의존성, Airflow와 Spark의 작업 스케줄러가 모두 DAG다.

공통점은 “여러 사건이 동시에 일어나도 좋고, 다만 시간을 거꾸로 거슬러 올라가는 것만 막자”는 발상이다.

블록체인의 linear chain은 사실 DAG의 가장 단순한 특수 케이스다.

각 노드(블록)가 정확히 하나의 부모를 가지는 일자형 그래프.

DAG 블록체인은 이 제약을 풀어서 한 블록이 여러 부모를 가질 수 있게 한다.

구분	Linear Chain	DAG
부모 블록 수	1개 (고정)	여러 개 가능
동시 블록 처리	한 번에 하나만 정당	여러 개를 동시에 흡수
경합 처리	패배한 블록은 폐기 (orphan)	모두 그래프에 포함 후 정렬
처리량 한계	block size × block time	병렬 전파로 확장 가능

블록체인이 DAG를 도입한 이유

사토시가 비트코인을 처음 설계할 때 블록 시간은 10분, 블록 크기는 1MB였다. 보수적 선택이었다. 전 세계 노드가 블록을 전파받고 검증하는 데 충분한 시간을 주기 위해서다.

문제는 이 구조가 처리량의 상한을 만든다는 점이다.

비트코인의 이론적 최대 TPS는 7 정도다. 이더리움도 PoS 전환 후 더 빨라지긴 했지만 단일 체인 위에서는 수십 TPS 수준이 한계다.

해결책은 두 갈래로 나뉘었다.

하나는 layering이다. L1은 그대로 두고 그 위에 L2(Optimistic Rollup, ZK Rollup)를 쌓아 처리량을 올린다. 이더리움 진영이 택한 길이다.

다른 하나는 합의 자체를 다시 설계하는 쪽이다. Sui나 Aptos 같은 PoS L1이 택한 길이고, 자료구조로 DAG를 들고 나왔다. 이 길을 이해하려면 먼저 BFT부터 봐야 한다.

BFT 합의의 수학적 골격

BFT(Byzantine Fault Tolerance)는 비잔틴 장군 문제에서 출발한 합의 모델이다. 노드 중 일부가 임의로 거짓말하거나 메시지를 누락해도 정직한 노드들은 같은 결정에 도달해야 한다.

전체 노드 수를 $n$ , 비잔틴 노드의 최대 수를 $f$ 라고 할 때 BFT의 안전성 조건은 다음 부등식이다.

n \geq 3f + 1

이 부등식은 정족수(quorum) 교집합 논리에서 나온다.

BFT의 안전성 목표는 단순하다. 모순되는 두 결정이 동시에 통과되어서는 안 된다. 같은 자산을 두 번 송금하는 식의 일관성 위반을 막는 게 합의의 본질이다. BFT는 이걸 보장하려고 매 결정마다 $2f + 1$ 개 노드의 동의를 정족수로 요구한다.

왜 하필 $2f + 1$ 인가. 두 모순된 결정 A, B가 각각 따로 정족수를 모았다고 가정해보자. A 지지자 $2f + 1$ 명, B 지지자 $2f + 1$ 명, 그런데 전체 노드는 $3f + 1$ 명뿐이다. 포함-배제 원리로 두 집합의 교집합 크기는

|A \cap B| \geq (2f + 1) + (2f + 1) - (3f + 1) = f + 1

이다. 즉 A와 B에 둘 다 동의한 노드가 최소 $f + 1$ 명 있다는 뜻이다.

비잔틴 노드는 최대 $f$ 명이므로, 그 $f + 1$ 명 중 적어도 한 명은 정직한 노드다. 정직한 노드는 모순된 두 결정에 동시에 동의할 리 없으니 모순이고, 따라서 두 모순된 결정이 동시에 정족수를 모으는 일은 일어나지 않는다.

이 quorum intersection이 BFT 안전성의 수학적 핵심이다. PBFT와 HotStuff 같은 결정적 BFT가 모두 이 구조 위에 서 있다.

문제는 처리량이다. 고전 BFT에서는 리더 노드가 트랜잭션을 담은 블록을 제안하고, 정족수의 노드가 그 블록에 서명해 합의한다.

리더 한 명이 모든 검증자에게 트랜잭션 데이터를 뿌려야 하니, 처리량은 리더의 네트워크 대역폭에 묶인다. 검증자 수가 늘면 메시지 복잡도도 커진다. PBFT는 라운드당 $O(n^2)$ 메시지를, HotStuff는 그것을 $O(n)$ 으로 줄였지만, 데이터 전파 자체의 병목은 남았다.

비트코인의 7 TPS는 PoW 블록 시간이 만든 상한이고, 고전 BFT 체인의 수천 TPS 천장은 이 리더 병목이 만든 상한이다. 둘 다 자료구조와 합의가 묶인 방식이 결정한다.

DAG-BFT가 푸는 방식

DAG-BFT의 핵심 아이디어는 한 줄로 요약된다.

BFT의 quorum 조건은 그대로 두되, 데이터 전파를 합의에서 떼어낸다.

각 노드가 자기 트랜잭션 배치를 동시에 reliable broadcast로 뿌린다. reliable broadcast는 BFT 위에서 “정직한 노드는 모두 같은 메시지를 받거나 모두 받지 못한다”를 보장하는 원시 연산이다.

각 배치는 그래프의 한 정점이 되고, 다음 라운드의 정점은 이전 라운드 정점 중 $(2f + 1)$ 개를 부모로 인용한다. 이 인용 개수가 곧 BFT의 정족수다. quorum 임계값이 자료구조에 박혀 있는 셈이다.

합의 레이어는 트랜잭션 데이터를 만질 일이 없다. DAG가 누가 무엇을 받았는지를 이미 인증해 놓았기 때문이다. 합의가 정하는 건 “이 라운드의 anchor 정점이 무엇인가” 하나뿐이고, anchor가 정해지면 그 인과적 선조 전체가 결정적으로 정렬된다.

	고전 BFT (PBFT, HotStuff)	DAG-BFT (Narwhal 계열)
데이터 전파	리더가 단독 전파	모든 노드가 reliable broadcast
정족수 위치	합의 메시지에 누적	자료구조(부모 인용)에 내장
합의의 일	블록 제안 + 정렬	anchor 선택만
메시지 복잡도	$O(n) \sim O(n^2)$	$O(n)$ (데이터 분리)

이게 DAG의 출발점이다.

DAG 합의가 겨냥한 결과는 세 가지로 정리된다.

처리량 한계: 리더 병목을 깨고 모든 노드가 동시에 데이터를 전파한다
블록 폐기로 인한 낭비: 경합 블록을 버리지 않고 그래프에 흡수한다
Finality latency: 결정적 finality를 수백 ms 안에 제공한다

“DAG는 더 빠른 블록체인”이라는 표현은 절반만 맞다. 본질은 BFT 합의에서 데이터 경로를 떼어낸 자료구조 변경이고, 빠른 건 그 결과다.

이 출발점에서 길은 두 갈래로 갈렸다. 한쪽은 reliable broadcast 위에 인증 DAG를 세운 Narwhal 계열(Sui, Aptos), 다른 한쪽은 subsampled voting을 들고 나온 Avalanche다. 둘 다 DAG에서 시작했지만 도착지가 다르다.

Narwhal

Narwhal의 핵심 발상은 한 줄로 요약된다.

데이터 전파(mempool)와 트랜잭션 순서 결정(consensus)을 분리하자.

기존 BFT 합의는 리더가 트랜잭션 데이터를 합의 메시지에 실어 날랐다. 처리량은 리더의 네트워크 대역폭에 묶이고, 리더가 자주 바뀌면 같은 데이터를 다시 전송해야 했다.

Narwhal은 이 둘을 분리한다. 워커들이 트랜잭션 배치를 reliable broadcast로 뿌려 인증 DAG를 먼저 만들고, 합의 레이어는 그 DAG 위에서 anchor 블록을 골라 정렬만 한다. 합의 메시지는 트랜잭션 데이터 대신 DAG 정점만 가리키는 참조를 들고 다닌다.

graph LR
    subgraph "Mempool DAG (Narwhal)"
        N1[Worker batch] --> N2[Worker batch]
        N1 --> N3[Worker batch]
        N2 --> N4[Worker batch]
        N3 --> N4
    end
    subgraph Consensus
        N4 --> C1[Anchor commit]
    end

DAG의 각 정점은 라운드 $r$ 의 블록이고, 라운드 $r-1$ 의 블록 중 $(2f+1)$ 개를 부모로 인용한다. 이 인용 자체가 reliable broadcast의 인증서가 된다.

합의 메시지가 가벼워져서 처리량이 폭발했다. 데이터는 이미 DAG에 있고, 합의는 어느 anchor를 commit point로 삼을지만 결정한다.

Tusk, Mysticeti

Narwhal 위에 올라가는 합의 알고리즘은 시간이 가면서 진화했다.

처음 Tusk는 비동기 환경에서 동작하는 무리더 합의였다. 안전했지만 빠르지 않았다.

Bullshark는 leader 기반의 부분 동기 합의를 얹어 latency를 낮췄다. 평시에는 정해진 anchor를 빠르게 commit하고, 장애 시에만 fallback 경로로 빠진다. Sui가 처음 메인넷에 올린 합의가 이것이다.

Mysticeti는 한 걸음 더 나갔다. Bullshark까지는 각 블록이 별도의 certification 라운드를 거쳐 인증되어야 했다. Mysticeti는 이 라운드를 없앤 uncertified DAG다.

각 블록은 $(2f+1)$ 개의 부모 인용만으로 암묵적으로 인증되고, commit latency가 이론적 하한인 3 message delay에 근접한다. 동시에 multi-leader를 도입해 한 라운드에서 여러 anchor를 동시에 commit할 수 있게 했다.

합의	DAG 형태	Anchor	메인 도입
Tusk	certified, async	random	-
Bullshark	certified, partial-sync	leader-based	Sui (초기)
Mysticeti	uncertified	multi-leader	Sui (현재)

Sui와 Aptos의 채택 경로

Sui는 처음부터 Narwhal 계열로 시작해 한 갈래로 진화했다. Bullshark에서 출발해 현재는 Mysticeti가 메인넷 합의다.

Sui와 Narwhal이 잘 맞은 이유는 실행 모델에 있다. Sui의 object model은 트랜잭션을 두 부류로 나눈다.

Owned object 트랜잭션: 단일 소유자만 접근하므로 합의 없이 fast path로 처리
Shared object 트랜잭션: 합의를 거쳐 순서 결정

대부분의 송금이나 NFT 전송이 owned object에 해당해 합의 자체를 우회한다. 합의가 필요한 경우에만 Mysticeti DAG에 들어간다. partial ordering이 자연스럽게 맞는 구조다.

Aptos는 좀 다른 길로 들어왔다. AptosBFT(HotStuff/Jolteon 계열)로 출발한 linear-chain 합의에 Narwhal의 아이디어를 단계적으로 흡수했다.

Quorum Store: Narwhal-style로 mempool을 합의에서 분리
Shoal, Shoal++: DAG-BFT 위에서 leader rotation을 파이프라이닝
Raptr: DAG와 fast path를 결합한 최신 합의

같은 Narwhal 계보지만 Sui는 처음부터 DAG, Aptos는 linear에서 DAG로 점진 흡수라는 차이가 있다. 두 메인넷 모두 sub-second finality에 100k~250k TPS를 처리한다. 단일 linear chain이 도달하기 거의 불가능한 영역이다.

Avalanche

Avalanche는 다른 가족이다. Narwhal이 reliable broadcast 기반의 결정적 합의라면, Avalanche는 subsampled voting을 핵심으로 하는 확률적 합의다.

발상은 단순하다. 각 노드는 매 라운드마다 무작위로 $k$ 개의 검증자를 샘플링해 의견을 묻고, 같은 답이 임계값 $\alpha$ 이상 나오면 자기 의견을 그쪽으로 바꾼다.

처음에는 의견이 50:50으로 갈려 있어도, 노드들이 서로 다수를 빌려오는 과정에서 시스템이 한쪽으로 살짝 기울어지면, 그 다음 라운드부터는 그 다수가 더 자주 샘플링돼 다수가 더 커진다. 작은 편향이 양의 피드백으로 증폭되어 합의가 한쪽으로 빠르게 쏠리는 이 동역학을 메타스테이블이라 부른다.

대신 BFT처럼 결정론적이지 않다. 안전성이 “ $2f + 1$ 의 동의로 항상 안전”이 아니라 “ $k$ 와 라운드 수를 키우면 잘못 합의될 확률이 무시할 수준이 된다”는 형태로 정의된다. 확률적 합의의 본질이다.

이 메커니즘은 두 가지 변종으로 갈라졌다.

Avalanche: UTXO 트랜잭션 그래프 위에서 동작. 트랜잭션 간 conflict set만 충돌 처리하고 나머지는 병렬로 확정된다. 본래의 DAG 합의다.
Snowman: 같은 subsampled voting을 linear chain에 적용. 블록을 순서대로 commit한다.

Avalanche 메인넷은 세 개의 빌트인 체인을 두는데, 출발 시점에는 X-Chain이 본래의 DAG-Avalanche, C-Chain(EVM)과 P-Chain은 Snowman을 썼다.

Cortina와 X-Chain의 linearize

Cortina 업그레이드로 X-Chain까지 linear chain이 됐다. 이후 Avalanche의 모든 빌트인 체인은 사실상 Snowman이다. 학술적 출발점이었던 DAG-Avalanche는 메인넷에서 사라졌다.

왜 DAG를 포기했나. 본질은 실행 모델의 충돌이다.

Avalanche의 DAG 합의는 트랜잭션이 disjoint한 UTXO를 건드릴 때 빛난다. 충돌이 없으면 병렬로 확정된다. 그런데 EVM 같은 account-based shared state 위에서는 트랜잭션이 같은 컨트랙트, 같은 storage slot을 자주 건드린다. 이러면 거의 모든 트랜잭션이 conflict set에 묶이고, DAG의 병렬성이 무너진다.

도구도 문제였다. EVM 인덱서, RPC, JSON-RPC 표준은 모두 block.number 기반의 total ordering을 전제한다. partial ordering 위에서 EVM 호환을 유지하려면 결국 어딘가에서 totally order된 view를 만들어야 한다. 그럴 거면 처음부터 linear가 깔끔하다.

Avalanche는 “DAG 합의를 안 쓴 게 아니라 지속적으로 쓸 도메인을 잃었다”에 가깝다. UTXO 기반 자산 전송에 특화된 자료구조가 EVM 생태계에 자리 잡지 못했다.

Sui / Aptos vs Avalanche

같은 DAG에서 출발한 두 진영이 갈린 지점은 실행 모델이다.

구분	Sui / Aptos (Narwhal 계열)	Avalanche (Snowman)
합의 메커니즘	Reliable broadcast + DAG ordering	Subsampled voting
자료구조	DAG (uncertified, Mysticeti)	Linear chain
실행 모델	Object model (Sui), Move (Aptos)	EVM (account-based)
병렬성의 원천	Disjoint object access	단일 world state 직렬 실행
Finality	Sub-second	~1초
처리량	100k~250k TPS	EVM L1 수준 (수천 TPS)

DAG는 “여러 사건이 동시에 일어나도 좋다”는 자료구조다. 그러려면 트랜잭션도 정말로 동시에 처리될 수 있어야 한다.

Sui의 object model과 Aptos의 Move는 이 동시성을 언어와 런타임 차원에서 표현한다. 같은 객체를 만지지 않는 한 트랜잭션은 서로 모르고 처리된다.

EVM은 그렇지 않다. 모든 트랜잭션이 단일 world state를 순차적으로 갱신한다. DAG가 아무리 멋져도 실행 단계에서 직렬화되면 그래프의 의미가 없다.

DAG는 자료구조의 선택이 아니라 실행 모델의 선택이다. 그래프를 살리려면 그래프적인 상태 모델이 필요하다.

DAG