DAG-Based Consensus — The Mempool/Consensus Split in Narwhal and Bullshark TODO
Concept
DAG-based consensus separates "spreading the data" from "deciding the order." Narwhal is the mempool layer: each validator builds transaction batches, collects other validators' signatures (a proof of availability) for them, and creates a vertex referencing the previous round's batches — the result is that all validators end up holding nearly the same DAG. Because this DAG already guarantees the data has been propagated and stored, the consensus layer only has to handle the DAG's metadata, not the actual transactions. An ordering protocol like Bullshark exchanges almost no extra messages: each validator interprets its own local DAG by a fixed deterministic rule and derives the same total order as everyone else. With this split, throughput scales with network bandwidth, and consensus latency becomes nearly independent of data size.
In classic BFT, where a single leader broadcasts every transaction, that leader's bandwidth becomes the system's throughput ceiling — this split is the core idea behind how modern high-throughput chain designs solve that bottleneck.
Code & Formula
# DAG 합의 — Narwhal(데이터 전파)과 Bullshark(순서화)처럼, 전파와 순서 결정을 분리한다.
# 각 정점은 이전 라운드의 과반 정점을 참조하고, 모든 노드가 같은 규칙으로 같은 전체 순서를 뽑는다.
import random
random.seed(9)
N_VALIDATORS = 4
QUORUM = N_VALIDATORS // 2 + 1 # 3
class Vertex:
def __init__(self, round_no, validator, refs):
self.round_no = round_no
self.validator = validator
self.refs = refs # 참조하는 이전 라운드 정점들의 (round, validator) 목록
self.id = (round_no, validator)
def build_dag(n_rounds):
dag = {0: [Vertex(0, v, refs=[]) for v in range(N_VALIDATORS)]}
for r in range(1, n_rounds):
prev_vertices = dag[r - 1]
dag[r] = []
for v in range(N_VALIDATORS):
# 이전 라운드 중 과반(QUORUM)개를 무작위로 참조 (가용성 증명을 흉내)
refs = random.sample([pv.id for pv in prev_vertices], QUORUM)
dag[r].append(Vertex(r, v, refs))
return dag
def deterministic_order(dag, n_rounds):
"""각 라운드의 validator 0을 anchor로 삼아, anchor가 참조하는 조상들을 순서대로 나열 (Bullshark 축약판)"""
order = []
seen = set()
for r in range(n_rounds - 1, -1, -1):
anchor = next(v for v in dag[r] if v.validator == 0)
stack = [anchor.id]
local_order = []
while stack:
vid = stack.pop()
if vid in seen:
continue
seen.add(vid)
local_order.append(vid)
rr, vv = vid
vertex = next(v for v in dag[rr] if v.validator == vv)
stack.extend(vertex.refs)
order.extend(reversed(local_order))
return order
dag = build_dag(n_rounds=3)
for r in sorted(dag):
print(f"round {r}: {[v.id for v in dag[r]]}, 참조 예시(v0)={dag[r][0].refs}")
order_node_a = deterministic_order(dag, n_rounds=3)
order_node_b = deterministic_order(dag, n_rounds=3) # 다른 노드가 같은 DAG로 동일하게 계산했다고 가정
print(f"\n전체 순서 (노드 A 계산): {order_node_a}")
print(f"전체 순서 (노드 B 계산): {order_node_b}")
print(f"두 노드의 순서 동일: {order_node_a == order_node_b} "
f"(같은 DAG에 같은 규칙 -> 추가 통신 없이 결정적으로 동일한 전체 순서)")
docs/code/algorithms/algorithms-57.py
Exercise
Build a simple round-based DAG in code where each vertex references a quorum's worth of the previous round's vertices, write a function that picks anchors by a fixed rule to derive a total order, and verify that different nodes produce identical results.
Practical Connection
This is directly relevant to understanding what determines the throughput and confirmation latency of the execution layer carrying Verex's orders and settlements, and what kind of ordering guarantee to expect when posting an off-chain matching result on-chain.
Where it lands in Jayverse
- Devnet: check whether the OP-Stack L2 plan separates availability from ordering. As devnet moves toward an OP-Stack L2, note whether the sequencer follows the Narwhal/Bullshark split, since that split is what determines the confirmation latency Verex can promise on order settlement.
- Verex: benchmark peak order rate against actual devnet/Sepolia block bandwidth. Don't assume a single-leader chain's throughput ceiling; a DAG-based L2 changes it, a single-leader L1 fork doesn't.
- OFA: note whether the chosen L2 exposes pre-finality DAG state. If propagated-but-uncommitted data is visible before ordering finishes, that's a surface a solver could exploit, and the intent/solver design should account for it.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| proof of availability | 가용성 증명 · 데이터가 실제로 배포·저장되었음을 검증자 서명으로 보증하는 것 · "collects other validators' signatures (a proof of availability)" |
| becomes independent of | ~와 거의 무관해지다 · 지연시간이 데이터 크기에 더 이상 영향받지 않게 된다는 뜻 · "consensus latency becomes nearly independent of data size" |
| throughput ceiling | 처리량 상한선 · 시스템 전체 성능이 한 지점(리더)에 의해 막히는 한계 · "that leader's bandwidth becomes the system's throughput ceiling" |
| bottleneck | 병목(현상) · 전체 흐름을 느리게 만드는 좁은 지점 · "solve that bottleneck" |
| deterministic rule | 결정론적 규칙 · 같은 입력이면 항상 같은 결과가 나오는 고정된 규칙 · "by a fixed deterministic rule and derives" |
| derive the same total order | (각자) 동일한 전체 순서를 도출해내다 · 별도 통신 없이도 모두가 같은 결론에 도달한다는 뜻 · "derives the same total order as everyone else" |
| BFT | 비잔틴장애허용(Byzantine Fault Tolerance) · 악의적 노드가 있어도 합의가 성립하는 고전적 합의 방식, DAG 기반 설계와 대비됨. "In classic BFT, where a single leader broadcasts" |
| DAG | 방향성 비순환 그래프(Directed Acyclic Graph) · 데이터 전파와 순서 결정을 분리하는 이 글의 핵심 구조. "DAG-based consensus separates" |
| Narwhal | 멤풀(데이터 전파) 계층을 맡는 프로토콜 · 검증자들이 배치를 만들고 가용성 증명을 모으는 계층. "Narwhal is the mempool layer" |
| Bullshark | Narwhal 위에서 순서를 정하는 합의 프로토콜 · 추가 메시지 교환 없이 로컬 DAG만으로 전체 순서를 도출함. "An ordering protocol like Bullshark exchanges almost no extra messages" |
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.