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.
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/.