Byzantine Quorums (3f+1) and the PBFT → HotStuff → Tendermint Lineage TODO

Algorithms · Day 56 / 100 · D. Distributed Systems & Consensus (Day 52-68)

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.

Where it lands in Jayverse

• Devnet: when moving from forked Anvil to an OP-Stack L2, write down which finality model it inherits. Probabilistic like L1, or BFT-style instant finality from the sequencer — that decides every downstream confirmation-depth policy.
• Verex: set settlement confirmation-depth policy explicitly per chain. Don't reuse an Ethereum-style probabilistic-finality wait time on a chain with instant finality, and don't assume instant finality where it doesn't hold.
• Bridge: justify the lock-and-mint relayer's "safe to mint" threshold by the source chain's actual quorum/finality assumptions. Not a fixed block-confirmation constant copied from elsewhere.

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

한국어

비잔틴 정족수(3f+1)와 PBFT TODO

Algorithms · Day 56 / 100 · D. 분산시스템·합의 (Day 52–68)

개념

부분 동기 환경에서 f개의 비잔틴 노드를 견디려면 전체 노드 수가 3f+1 이상이어야 하고, 정족수를 2f+1로 잡으면 임의의 두 정족수가 최소 f+1개 노드에서 겹친다. 그 교집합에는 정직한 노드가 반드시 하나 이상 포함되므로, 서로 상충하는 두 값이 동시에 확정될 수 없다는 안전성이 나온다. PBFT는 pre-prepare, prepare, commit 3단계로 합의를 이루지만 뷰 체인지 비용이 노드 수에 대해 크게 증가한다. HotStuff는 투표를 임계 서명으로 집계하고 리더를 통해 중계해 통신량을 선형으로 줄이고, 연속된 체인 규칙으로 뷰 체인지를 단순화했다. Tendermint는 propose, prevote, precommit 구조에 잠금(lock) 규칙을 두어 한 번 커밋된 블록이 뒤집히지 않는 즉시 완결성을 제공한다.

지분증명 체인, 롤업 시퀀서, 사이드 인프라가 모두 이 계열이라 완결성이 어떤 가정 위에서 보장되는지, 리더가 죽었을 때 진행성이 어떻게 회복되는지를 알아야 장애를 해석할 수 있다.

코드 · 수식

# 비잔틴 정족수(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

연습

n=4, f=1로 두고 정직 노드 두 개가 서로 다른 값을 커밋하는 시나리오를 종이에 그려 정족수 교집합 때문에 왜 불가능한지 직접 따라가 보라.

실무 · Verex 연결

즉시 완결성 체인에서는 재구성(reorg) 위험이 사실상 사라져 Verex 같은 정산 시스템의 확정 대기 블록 수 정책이 달라지므로, 이더리움의 확률적 완결성과의 차이를 정확히 구분해야 한다.

Jayverse에서의 위치

• Devnet: 포크된 Anvil에서 OP-Stack L2로 옮길 때 어떤 파이널리티 모델을 물려받는지 명시한다. L1처럼 확률적인지, 시퀀서의 BFT식 즉시 파이널리티인지가 이후의 모든 컨펌 깊이 정책을 결정한다.
• Verex: 정산 컨펌 깊이 정책을 체인별로 명시적으로 정한다. 즉시 파이널리티를 가진 체인에 이더리움식 확률적 파이널리티 대기 시간을 재사용하지 않고, 즉시 파이널리티가 없는 체인에서 있다고 가정하지도 않는다.
• Bridge: lock-and-mint 릴레이어의 "민팅해도 안전함" 임계값을 소스 체인의 실제 쿼럼/파이널리티 가정으로 정당화한다. 다른 곳에서 복사한 고정 블록 컨펌 상수가 아니다.

공부한 날 원본 커리큘럼(docs/knowledge/dev-100-curriculum.md)의 이 줄에 노트 링크와 ✅ 를 붙이면, 이 자리는 노트 본문으로 바로 이어집니다. 노트 없이 이 페이지에 바로 적어도 됩니다 — 다만 다시 생성하면 덮어쓰이므로, 남길 글은 docs/algorithms/ 의 마크다운으로 쓰는 편이 안전합니다.