コンセンサスアルゴリズム・アンダーグラウンド【第4回】 ― 身元を数えられない世界、PoWとPoS

ここまでは、参加者の集合が既知であることを前提としてきた。validator が判明しているからこそ、過半数や 2f+1 を数えられる。最終回ではその前提を外す。

1ノード1票が使えない世界

参加者の身元も人数も不明な permissionless ネットワークでは、単純な1ノード1票は成立しない。攻撃者がノードを無制限に生成できるためである。

Nakamoto Consensus は、投票権を計算資源へ結び付けることでこれを解決した。

one CPU / hash power ≈ voting weight

各 miner は nonce を探索し、条件を満たすハッシュを持つブロックを生成する。

import hashlib

def mine(header: bytes, difficulty_prefix: bytes):
    nonce = 0
    while True:
        digest = hashlib.sha256(
            header + nonce.to_bytes(8, "big")
        ).digest()
        if digest.startswith(difficulty_prefix):
            return nonce, digest
        nonce += 1

身元を数えられないため、代わりに計測可能な量、すなわち消費された計算量を数える。これが本設計の核心である。

確率的ファイナリティ

Raft や PBFT では、コミット済みの値は規則上覆らない。Nakamoto Consensus では、累積作業量が最大のチェーンを選択するため、直近のブロックは再編成され得る。

canonical = max(candidate_chains, key=lambda c: c.total_work)

確認数が増加するほど覆る確率は低下するが、ゼロにはならない。決定的ファイナリティと確率的ファイナリティの差は、上位のアプリケーション設計へ直接影響する。何確認で入金確定とするかという運用判断が必要となるのは、この性質による。

PoW は単なるブロック生成方式ではない。Sybil 耐性、リーダーくじ、フォーク選択、履歴改ざんコスト、新規参加者による履歴検証を、一つの経済的機構へ統合している。代償は、エネルギー消費、低スループット、確率的な確定、採掘資本の集中である。

Proof of Stake：不可能にせず、割に合わなくする

PoS では、計算量の代わりに stake を投票権とする。Ethereum は2022年に PoW から PoS へ移行した。公式資料は、エネルギー消費の低減と、その後のスケーリング施策との親和性を移行理由として挙げている。

ただし、残高比例でリーダーを選出するだけでは不十分である。二重投票、長距離攻撃、Nothing at Stake、stake の集中、validator の離脱、弱い主観性、検閲、MEV、時刻と slot の同期といった固有の問題が伴う。

中心にあるのが slashing である。矛盾する履歴へ署名した validator に対して、経済的な罰を与える。

def slashable(vote_a, vote_b):
    same_validator = vote_a.validator == vote_b.validator
    double_vote = (
        vote_a.target_epoch == vote_b.target_epoch
        and vote_a.target_hash != vote_b.target_hash
    )
    surround_vote = (
        vote_a.source_epoch < vote_b.source_epoch
        and vote_b.target_epoch < vote_a.target_epoch
    )
    return same_validator and (double_vote or surround_vote)

PoS-BFT は、暗号学的な安全性に加えて経済的な安全性を用いる。二重署名を技術的に不可能とするのではなく、二重署名は可能だが証拠が残り、担保を失うという設計である。第3回までのアルゴリズムが不可能性によって安全性を構成していたのに対し、ここでは損失によって構成している。

Solana：時計とロックアウト

Solana では、Proof of History が検証可能な時間順序を提供し、その上で Tower BFT が stake 加重の投票を行う。Ethereum と Solana はいずれも PoS を用いるが、ブロック生成とコンセンサスの構成は異なる。

Proof of History はコンセンサスそのものではなく、validator が共通の時間順序を効率的に扱うための暗号学的な時計である。順序を事後に合意するのではなく、順序の証拠を事前に生成する構成といえる。

Tower BFT では、validator が同一フォークへ継続して投票するほど lockout 期間が延長される。

class TowerVote:
    def __init__(self, slot):
        self.slot = slot
        self.confirmations = 1

    @property
    def lockout(self):
        return 2 ** self.confirmations

投票を積み重ねるほど、過去の投票を覆すための待機コストが指数的に増加する。決定を一度で確定させるのではなく、覆すコストを累積させる方式である。

Avalanche / Snowman：全員には聞かない

Avalanche 系は、全 validator から明示的に大規模クォーラムを一度収集する代わりに、ランダムに選択した少数の validator へ反復的に問い合わせる。

def poll(sample, preference):
    votes = [peer.query() for peer in sample]
    winner, count = most_common(votes)

    if count >= alpha:
        if winner == preference:
            confidence += 1
        else:
            preference = winner
            confidence = 1
    else:
        confidence = 0

    return confidence >= beta

局所的な多数派の選好が、反復サンプリングによってネットワーク全体へ増幅される。古典 BFT の全対全通信や固定リーダーへの依存を削減し、大規模な validator 集合でも高速に選好を収束させることが目的である。

Snowman は、元の Avalanche DAG をスマートコントラクト向けの線形チェーンへ適用したものである。Avalanche の Primary Network は Snowman を用い、低いブロック遅延と高スループットを目指す構造となっている。

留意すべきは、これが数回問い合わせて多数決を取るだけの方式ではない点である。加重サンプリング、metastability、confidence 閾値、敵対的サンプリング、ネットワークの参加離脱、競合トランザクションの扱いを、一体として解析する必要がある。

そもそも合意しない、という選択

最後に、コンセンサスと混同されやすいが別種の方式を整理する。設計上もっとも効果が大きいのは、多くの場合この区別である。

CRDT

CRDT は、同一の操作順序へ合意せずとも、更新をすべて交換すれば同一状態へ収束できるデータ型である。

class GCounter:
    def __init__(self, node_id):
        self.node_id = node_id
        self.counts = {}

    def increment(self):
        self.counts[self.node_id] = self.counts.get(self.node_id, 0) + 1

    def merge(self, other):
        for node, value in other.counts.items():
            self.counts[node] = max(self.counts.get(node, 0), value)

    def value(self):
        return sum(self.counts.values())

これは操作順序を高速に合意しているのではない。コンセンサスを要した問題を、可換なデータ構造へ変形して回避している。対象はカウンタ、集合、共同編集、観測データなどである。

一方、在庫を一つだけ減算する、口座残高を超える出金を禁止する、唯一のリーダーを決定するといった不変条件には、そのままでは適用できない。ここを誤ると、収束はするが業務要件を満たさないシステムとなる。

Gossip

Gossip は情報の拡散方式である。

def gossip(node, peers):
    peer = random.choice(peers)
    delta = node.state.diff(peer.version)
    peer.merge(delta)

全ノードへ効率的に状態を伝播できるが、正しい値を一つに決定するわけではない。

SWIM

SWIM は障害検知とメンバーシップ拡散の方式である。

PING B
  ↓ no response
PING-REQ B through C, D
  ↓ no response
mark B suspected
  ↓ timeout
mark B failed

ノードがクラスタへ参加しているかを推定するが、トランザクション順序を決定するコンセンサスではない。第1回で確認したとおり、停止と遅延は区別できないため、SWIM が返すのはあくまで推定である。

何を選ぶか

選定基準は新しさではない。確認すべきは次の条件である。

failure model         どこまでの故障を想定するか
network model         同期・部分同期・非同期のどれか
membership model      参加者は固定か、可変か、不特定か
finality requirement  決定的か、確率的で足りるか
write locality        書き込みはどこで発生するか
conflict rate         操作同士はどれくらい競合するか
validator count       ノード数はいくつまで増えるか
trust model           虚偽を送るノードを想定するか
storage durability    ディスクをどこまで信頼するか
operational complexity 運用と障害対応に割ける人数

最後の項目は付随的な条件ではない。第2回で確認したとおり、本番の Raft 実装の大半は論文の外側にあり、それを保守できるかどうかが選定の実質的な制約となる。

地下で起きていること

表層的には、コンセンサスアルゴリズムは投票方式の差異に見える。

Raft      = 過半数
PBFT      = 3分の2
PoS       = stake投票
Avalanche = サンプリング

しかし、その下で扱われている問題はそれぞれ異なる。

Raft が扱うのは、信頼されたノードの停止と再起動である。PBFT が扱うのは、署名付きの虚偽と矛盾である。Nakamoto Consensus が扱うのは、参加者の身元を数えられない環境である。DAG-BFT が扱うのは、順序決定より先にデータ配布が飽和するという帯域の問題である。CRDT が行っているのは、合意を高速化することではなく、合意を要しない形へ問題を変形することである。

最大の変化は、コンセンサスが単一の機構ではなくなったことである。

identity / Sybil resistance
data availability
transaction dissemination
ordering
finality
execution
storage durability
economic incentives

これらを分離し、異なる仕組みを組み合わせる方向へ進んでいる。Narwhal は配布と順序を分離した。HotStuff は投票を QC へ圧縮した。Mysticeti は certificate 形成を通常経路から除去した。Multi-Raft は合意の単位を細分化した。CRDT は一部の問題から順序合意そのものを除去した。

したがって、今後のコンセンサス設計で問うべきは、採用するアルゴリズムの選択だけではない。より正確には、システムのどの境界で、何について、どの故障モデルの下で合意が必要なのかである。

コンセンサスはシステム全体を駆動する機構ではない。必要最小限の不変条件のみを保護する、基盤層の施錠機構である。

まとめ

• permissionless では1ノード1票が成立しない。PoW は計測できない身元の代わりに、計測可能な計算量を数える。
• PoW のファイナリティは確率的である。何確認で確定とするかという運用判断が、上位設計に必ず生じる。
• PoS の安全性は不可能性ではなく、損失によって構成される。中心は slashing と、その証拠が残る構造である。
• Solana は順序の証拠（PoH）を事前に生成し、Tower BFT は覆すコストを指数的に累積させる。Avalanche は全員に問い合わせず、反復サンプリングで選好を収束させる。
• CRDT・Gossip・SWIM はコンセンサスではない。とくに CRDT は、合意を高速化する手段ではなく、合意を要しない形へ問題を変形する手段である。
• 問うべきはアルゴリズムの選択ではなく、システムのどの境界で、何について、どの故障モデルの下で合意が必要かである。