Byzantine Quorums (3f+1) and the PBFT → HotStuff → Tendermint Lineage TODO
Concept
In a partially synchronous setting, tolerating f Byzantine nodes requires a total node count of at least 3f+1; setting the quorum size to 2f+1 makes any two quorums overlap in at least f+1 nodes. That intersection is guaranteed to contain at least one honest node, which is where the safety property — that two conflicting values can never both be finalized — comes from. PBFT reaches agreement in three phases, pre-prepare, prepare, and commit, but its view-change cost grows sharply with the number of nodes. HotStuff aggregates votes with threshold signatures and relays them through the leader, cutting communication to linear cost, and simplifies view changes with a chained-block rule. Tendermint's propose/prevote/precommit structure adds a locking rule that guarantees instant finality — once a block is committed, it is never reverted.
Proof-of-stake chains, rollup sequencers, and side infrastructure are all in this family, so interpreting a failure requires knowing exactly what assumptions finality rests on and how liveness recovers when a leader dies.
Code & Formula
# 비잔틴 정족수(3f+1)와 PBFT 계보 — n=3f+1, 정족수=2f+1일 때
# 서로 다른 두 정족수는 항상 최소 f+1개 노드에서 겹치고, 그 교집합엔 정직한 노드가 반드시 있다.
from itertools import combinations
def check_byzantine_safety(f):
n = 3 * f + 1
quorum_size = 2 * f + 1
nodes = set(range(n))
min_intersection = n # 최소 교집합 크기 추적
for q1 in combinations(nodes, quorum_size):
for q2 in combinations(nodes, quorum_size):
overlap = len(set(q1) & set(q2))
min_intersection = min(min_intersection, overlap)
# 비잔틴 노드가 최대 f개이므로, 교집합이 f+1개 이상이면 정직한 노드가 반드시 하나 이상 포함
guaranteed_honest = min_intersection - f
return n, quorum_size, min_intersection, guaranteed_honest
for f in [1, 2]:
n, q, min_overlap, honest = check_byzantine_safety(f)
print(f"f={f}: n={n}, quorum={q} -> 임의의 두 정족수 최소 교집합={min_overlap} "
f"(이론값 f+1={f+1})")
print(f" 교집합 중 정직 노드 최소 보장 = {min_overlap} - f = {honest} "
f"({'안전' if honest >= 1 else '위험'})")
print("\n-> 두 정족수의 교집합에 정직한 노드가 항상 1개 이상 있으므로,")
print(" 그 노드가 서로 모순되는 두 값에 동시에 서명할 수 없어 안전성이 성립한다.")
print(" (PBFT: 3단계 통신, HotStuff: 서명 집계로 선형 통신량, Tendermint: lock 규칙으로 즉시 완결성)")
docs/code/algorithms/algorithms-56.py
Exercise
With n=4, f=1, sketch on paper a scenario where two honest nodes commit different values, and walk through why the quorum-intersection property makes that impossible.
Practical Connection
Under instant finality, reorganization risk effectively disappears, changing what confirmation-depth policy makes sense for a settlement system like Verex — so you need to be precise about how this differs from Ethereum's probabilistic finality.
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/.