【2026年7月版】

コンセンサスアルゴリズム・アンダーグラウンド【第3回】 ― 嘘をつくノード、PBFTからDAG-BFTへ

公開日: 2026/07/22
読了時間: 約 16分

データ分散システム Rust

前回までのアルゴリズムは、ノードは停止するが虚偽は送らないというクラッシュ故障モデルを前提としていた。今回はその前提を外す。

n = 3f + 1 という定数

Byzantine 故障モデルでは、ノードは次の行動を取り得る。

相手ごとに異なる値を送信する
存在しない投票を主張する
古いメッセージを再送する
特定の提案のみを選別して検閲する
意図的に進行を妨害する
秘密鍵を用いて、矛盾したメッセージへ署名する

最後の項目が本質的である。署名が存在することは、内容の正当性を意味しない。署名が保証するのは発信者の同一性のみであり、その発信者が相手ごとに異なる主張をしないことは保証しない。

一般的な BFT では、n = 3f + 1 ノードで最大 f 個の Byzantine ノードに耐える。

 4 validators → 1 Byzantine fault
 7 validators → 2 Byzantine faults
10 validators → 3 Byzantine faults

決定の証明には通常 2f+1 票を用いる。この数値には根拠がある。n = 3f+1 のとき、二つの 2f+1 集合の交差は少なくとも (2f+1) + (2f+1) − (3f+1) = f+1 ノードとなる。Byzantine ノードは高々 f 個であるため、交差部分には必ず一つ以上の正直なノードが含まれる。矛盾する二つの決定が同時に成立しないのは、この正直なノードの存在による。

クラッシュ故障の過半数クォーラムと構造は同一であり、虚偽を送るノードの分だけ交差を厚くしていると解釈できる。

PBFT：三段階の投票

PBFT の対象は、悪意あるノードを含むレプリカ集合において、同一の操作順序を決定することである。

client
  ↓
primary: PRE-PREPARE
  ↓
replicas: PREPARE
  ↓
replicas: COMMIT
  ↓
execute

簡略化すれば、各レプリカは票を集計しているにすぎない。

class PBFTReplica:
    def __init__(self, node_id, f):
        self.node_id = node_id
        self.f = f
        self.prepares = {}
        self.commits = {}

    def on_prepare(self, digest, sender):
        self.prepares.setdefault(digest, set()).add(sender)
        return len(self.prepares[digest]) >= 2 * self.f

    def on_commit(self, digest, sender):
        self.commits.setdefault(digest, set()).add(sender)
        return len(self.commits[digest]) >= 2 * self.f + 1

実際には view、シーケンス番号、チェックポイント、署名検証、watermark、view change が必要となる。

二段階ではなく三段階である理由は次のとおりである。PREPARE の段階で判明するのは、当該 view で当該順序に同意したという事実のみであり、他のレプリカが同一の結論に到達したかは判明しない。COMMIT は、その事実自体が十分に共有されたことを確認する段階である。リーダー交代をまたいでも決定が覆らない性質は、この二段目が担保する。

問題は通信量である。各レプリカが他の多数のレプリカへメッセージを送信するため、通常経路で O(n²) となりやすい。小規模な許可型ネットワークでは実用的だが、validator 数の増加に伴い通信負荷が急増する。

Tendermint：ロックがなければ、ラウンドが分裂する

Tendermint 系のコンセンサスは、ラウンドごとに proposer を選出し、二段階の投票を行う。

proposal → prevote → precommit → commit

validator はある値へ precommit した後、ロック規則により、矛盾する値への投票を制限される。

def on_proposal(block, proposal):
    if locked_block is None:
        return prevote(block)

    if block.id == locked_block.id:
        return prevote(block)

    if proposal.valid_round > locked_round:
        return prevote(block)

    return prevote_nil()

Tendermint の中核は、3分の2が投票したら決定するという単純な規則ではなく、ラウンドをまたぐロック解除の条件である。ロック規則が存在しなければ、ネットワーク遅延により、異なるラウンドで別々の値が決定され得る。

BFT の安全性は、票を集計する部分ではなく、どの条件で選好を変更してよいかを定める部分に存在する。

HotStuff：投票をQuorum Certificateへ畳む

PBFT 系の弱点は、とくにリーダー交代時の通信が複雑であり、validator 数の増加に弱い点にあった。

HotStuff は、投票をリーダーへ集約し、Quorum Certificate（QC）としてまとめる。

validators
   \  |  /
    leader
      |
      QC

QC は、あるブロックに 2f+1 の投票が集まったことの証明である。

struct Vote {
    validator: ValidatorId,
    block_hash: Hash,
    view: u64,
    signature: Signature,
}

struct QuorumCertificate {
    block_hash: Hash,
    view: u64,
    signatures: AggregateSignature,
}

全対全でメッセージを配布する代わりに、リーダーが集約した一つの証明書を配布すればよい。HotStuff は部分同期モデルのリーダーベース BFT であり、正常なリーダーの下では実際のネットワーク遅延に応じて進行する responsiveness と、線形の通信量を両立させた。

Chained HotStuff

各ブロックは親ブロックの QC を含む。

B1 ← B2 ← B3 ← B4
   QC1  QC2  QC3

複数段の認証済みチェーンが形成された時点で、祖先ブロックをコミットする。概念的な 3-chain ルールは次のとおりである。

def try_commit(block):
    parent = block.parent
    grandparent = parent.parent if parent else None

    if block.qc.certifies(parent) and parent.qc.certifies(grandparent):
        commit(grandparent)

本質は、PBFT が独立したメッセージ往復として保持していた PREPARE、PRE-COMMIT、COMMIT を、ブロックチェーン上の連続した QC へパイプライン化した点にある。段数自体は減少しておらず、段が重畳して流れる構造へ変換されている。

HotStuff の設計は Libra/Diem 系、およびその後の Aptos や Sui 周辺の BFT 研究へ大きな影響を与えた。ただし現在の Sui や Aptos は、素の HotStuff ではなく DAG 型コンセンサスへ移行している。

Narwhal：データ配布と順序決定を分ける

従来の BFT では、リーダーが大規模なトランザクションバッチを配布し、その内容について投票を集める。ここでは二つの別問題が混在している。提案されたデータを全員が取得できているかという可用性の問題と、順序をどう決定するかという問題である。

Narwhal はこれを分離した。

transaction dissemination
        ↓
    DAG store
        ↓
consensus ordering protocol

Narwhal は、高スループットなデータ配布と因果履歴の保存を担当する DAG ベースの mempool である。順序決定は Tusk、Bullshark、HotStuff といった別のコンセンサス層が担当する。

validator はバッチを配布し、十分な署名を得た時点で certificate を形成する。

struct Header {
    author: AuthorityId,
    round: u64,
    payload: Vec<BatchDigest>,
    parents: Vec<CertificateDigest>,
}

struct Certificate {
    header: Header,
    votes: Vec<SignedVote>,
}

この certificate は、当該ヘッダーへ賛成したという意味ではない。十分な数の正直なノードがデータを受信済みであり、後から取得可能であるという可用性の証明として機能する。順序を決定する前に、データの所在を先に確定させる構成である。

Bullshark：DAGから決定的な順序を取り出す

Bullshark は、Narwhal が構築するラウンドベースの DAG 上で、決定的な順序を導出する。

 round 1      round 2      round 3

  A1 ────────▶ A2 ────────▶ A3
  │ ╲          ▲ ╲          ▲
  │  ╲         │  ╲         │
  B1 ────────▶ B2 ────────▶ B3
  │            ▲            ▲
  C1 ────────▶ C2 ────────▶ C3

各ノードは前ラウンドの複数 certificate を参照する。十分な強参照を受けたリーダー certificate を anchor としてコミットし、その祖先 DAG を決定的な順序で出力する。

def strongly_supported(anchor, next_round, f):
    supporters = {
        cert.author
        for cert in next_round
        if anchor.digest in cert.parents
    }
    return len(supporters) >= 2 * f + 1

HotStuff ではリーダーが順序決定と提案配布の中心であった。Bullshark では各 validator が並列に DAG へデータを追加し、リーダーはデータ配布の独占者ではなく、DAG 内の順序決定基準に近い役割となる。全 validator が常時帯域を使用し、投票に相当するメッセージも DAG の一部として運搬されるため、追加の投票往復をほとんど必要としない。

実装レベルの分析（arXiv:2507.04956、2025年）では、Bullshark on Narwhal について29.7万TPS、約2秒のレイテンシという評価が報告されている。ただしこれは特定の実験条件における値であり、本番性能を保証する数値ではない。

Mysticeti：認証をやめる

Narwhal/Bullshark では、各 DAG 頂点について certificate を形成してから次へ進む。安全である一方、頂点ごとに署名を収集する追加ラウンドを要する。

Mysticeti 系の特徴は、すべての DAG ブロックを事前に certificate 化しない uncertified DAG へ移行した点にある。各 validator は受信した DAG ブロックを、次に自身が発行するブロックから直接参照する。

broadcast block
      ↓
 receive blocks
      ↓
reference them directly
      ↓
implicit support accumulates

参照そのものが支持を意味するため、証明書を形成する往復が消える。論文（NDSS 2025）では、DAG ベース BFT として3メッセージラウンドという下限に到達し、WAN で0.5秒のコンセンサスコミットと20万TPS超のスループットを同時に達成したと報告されている。Sui へ統合した結果、レイテンシは4分の1以下になったとされる。

代償も存在する。認証済み DAG が明示的に提供していたデータ可用性の境界が弱まり、Byzantine validator による equivocation や選択的配布への防御が、DAG の解釈規則の内部へ移動する。2024年の Adelie（arXiv:2408.02000）も、uncertified DAG が低遅延を可能にする一方で、認証済み DAG には存在しなかった攻撃面を生じさせると指摘し、その検出と防止を扱っている。

高速化によって削減されたコストは消滅したのではなく、防御の複雑さとして別の層へ移動している。

Shoal系：遅いリーダーを待たない

DAG-BFT においても、選出された anchor leader が遅延、あるいは悪意を持つ場合、ラウンドの進行が停滞する。

Shoal / Shoal++ 系の方針は、DAG 内の情報から leader reputation を更新し、成功見込みの高いリーダーを選出し、失敗した anchor を早期にスキップすることである。

def choose_leader(authorities, reputation):
    return max(
        authorities,
        key=lambda a: (
            reputation[a].recent_success,
            -reputation[a].latency,
            reputation[a].availability,
        ),
    )

これは単なる性能最適化ではない。固定的なラウンドロビンでは Byzantine leader が定期的に順番を迎え、そのたびにタイムアウトを待機することになる。DAG から観測可能な過去の振る舞いを用いることで、悪意あるリーダーによる停滞コストを削減できる。評価の材料が既に手元の DAG に含まれている点が、この方式の利点である。Aptos Core には DAG ベースの order rule を含むコンセンサス実装が公開されている。

次に来るのは公平性の問題

性能が改善すると、次に問題となるのは stake の集中、報酬の集中、validator 選択の公平性である。

2026年の FairWave（arXiv:2606.10982）は、Sybil 耐性・報酬の公平性・金権化のトリレンマを扱い、DAG-BFT における anchor 選択と報酬配分を別チャネルとして分離することを提案している。選択チャネルは stake に対して超線形とし Sybil 分割の利得を消去する一方、報酬チャネルは平方根で正規化して集中を緩和する構成である。ただし現時点では新しい研究提案であり、本番実績を持つ確立済みの方式として扱うべきではない。

まとめ

n = 3f+1 と 2f+1 という数値は、二つのクォーラムの交差に必ず正直なノードが一つ残ることに由来する。
PBFT が三段階である理由は、順序に同意したことと、その同意が共有されたことが別の事実だからである。代償は O(n²) の通信量である。
Tendermint の中核はロック規則である。どの条件で選好を変更してよいかを定める部分に安全性が存在する。
HotStuff は投票を Quorum Certificate へ畳み、PBFT の三往復をチェーン上のパイプラインへ変換して通信量を線形化した。
Narwhal はデータ配布と順序決定を分離し、certificate をデータ可用性の証明として用いる。Bullshark はその DAG から決定的順序を導出する（29.7万TPS／約2秒の報告がある）。
Mysticeti は certificate 形成を通常経路から除去し、3メッセージラウンドに到達した（WAN 0.5秒、20万TPS超）。その代わり equivocation と可用性の防御が DAG の解釈規則へ移行し、Adelie のような後続研究が生じた。

次回は最後の前提を外す。参加者の身元も人数も不明な環境を扱い、PoW と PoS、Solana の時間順序、Avalanche の反復サンプリング、および合意を回避する選択肢までを整理してシリーズを終える。