IOHKブログ:Cardanoコンセンサス層の抽象的性質

IOHKエンジニアが選択の背景を紐解くテクニカルな新シリーズ

2020年5月28日 Edsko de Vries 読了時間21分


(以下の日本語版は参照用とし、実際のコード画面は元の英語版ブログ記事をご覧ください。)

現在IOHKでは、CardanoメインネットにおけるShelley公開に向けて、最新ニュースの配信に余念がありませんが、同時に、舞台裏で絶え間なく進められている作業と担当エンジニアたちにも光を当てたいと考えます。

この不定期のテクニカルブログ「開発者を掘り下げる」では、IOHKのエンジニアたちが今後数か月にわたり、Haskell開発の現場からCardanoプラットフォームとプロトコルのコアとなる要素をありのままの姿で紹介し、エンジニアリング上の選択に至る背景を共有します。

シリーズ初回となる今回は、コンセンサス層における抽象化の使用について考察します。

はじめに

Cardanoコンセンサス層には2つの重要な役割がある。

  • ブロックチェーンのコンセンサスプロトコルを実行すること。ブロックチェーンの文脈では、コンセンサス、すなわち「多数派の意見」とは、ブロックチェーンの実行にかかわる人すべてが、どれが真のチェーンかということに同意することを意味する。したがって、コンセンサス層はブロックの適用、競合するチェーンがある場合の選択、自身のブロックを生成するタイミングの決定を担当する。
  • こうした決定を要するすべてのステータスを維持すること。ブロックを適用するか否かを判断するためには、プロトコルは台帳のステータスに照らしてブロックを検証する必要がある。別のチェーン(チェーンのフォークにおける別の選択肢)へ切り替える判断をする場合、チェーン上に台帳のステータスを再建できるに足る履歴を維持する必要がある。ブロックの生成を可能にするには、これらのブロックに挿入するトランザクションのメモリープールを維持しなくてはならない。

コンセンサス層はその下のネットワーク層上の台帳層を仲介する。ネットワーク層はコミュニケーションプロトコルやピア選定に携わり、台帳層は台帳のステータスの見え方や、各新ブロックを更新すべき方法を規定している。台帳層は完全にステートレスであり、純粋な関数のみで構成されている。そしてコンセンサス層は、台帳ステータスの正確な特性、またはブロックの中身について(コンセンサスプロトコルを実行するために必要な一部のヘッダーフィールドを除き)知る必要はない。

コンセンサス層では抽象化が活用されている。この点は多くの理由により重要である。

  • プログラマーはテストを実行する際に失敗を挿入できる。例えば、基盤とするファイルシステムを抽象化し、これをストレージ層のあらゆるディスクエラーを想定したストレステストに使用する。同様に、時間を抽象化し、これをユーザーのシステム時刻が前後にジャンプした際、ノードにどのような影響がでるかを確認することもできる。
  • コンセンサス層を多様な台帳でインスタンス化することが可能となる。現在これを使用して、コンセンサス層をByron台帳(Cardanoブロックチェーンにおける現行台帳)で実行しており、同様にShelley HaskellテストネットはShelledy台帳で実行する。さらに、コンセンサス層をテスト専用に設計した多様な台帳で実行するために使用している。こうした台帳は一般に「実際」の台帳よりもずっと単純であるため、コンセンサス層自体のテストに集中することができる。
  • 合成性が向上し、小さなコンポーネントから大きなコンポーネントを構築することが可能となる。例えば、Shelleyテストネットの台帳にはShelley台帳のみが含まれるが、Shelleyがリリースされると、実際のチェーンにはハードフォークが起こるまでByron台帳が含まれ、その後はShelley台帳となる。つまり、特定の時点で2つの台帳を切り替える台帳層が必要になる。新台帳を定義するかわりに、私たちはこの機能性それのみを、正確に実装するハードフォークコンビネーターを定義づけることができる。これにより、コードの再利用性が向上し(次回ハードフォークの際にハードフォーク機能を再実装する必要がなくなる)、関心の分離が図られる。すなわち、ハードフォークコンビネーターの開発およびテストは、切り替える台帳の特性に左右されない。
  • 最後の点に関連して、抽象化の使用によりテスタビリティが高まる。ここでコンビネーターを、特定のアスペクトに焦点を当てることを可能にするコンセンサスプロトコルのマイナーバリエーションを定義するものと定義することができる。例えば、既存のコンセンサスプロトコルを使って、ブロックを生成するべきか否かの確認のみをオーバーライドするコンビネーターが存在する。これを、所与のスロットにおいて多くのノードがブロックを生成する、またはノードがまったくいない、さらにコンセンサス層がそのような状況で正しいことをしているか検証するというテストシナリオを作成するために使用することができる。コンセンサス層のこのアスペクトをオーバーライドするコンビネーターがないと、このようなシナリオが生じるかはチャンスに賭けなければならない。こうした「チャンス」はテストでコントロールできる(疑似乱数ジェネレーターに特定の開始シードを選択することにより)が、特定のシナリオをセットアップすること、実際自動的に失敗のテストケースをミニマルテストケースに圧縮させることは不可能だろう。これらのテストコンセンサスコンビネーターを使うと、テストは文字通り、ノードがどのスロットでブロックを生成するかスケジュールされた設定のみを使用することができる。こうしたスケジュールをランダムに生成して実行し、バグがあったらバグのトリガーとなるに十分なミニマルテストケースに圧縮できる。こうしたミニマルエラースケジュールは、単に何かをどこかの時点で引き起こすランダムシードの選択よりも、デバッグ、理解、作業が大幅に楽になる。

ただしこのすべてを達成するには、コンセンサス層に洗練されたHaskell型を活用する必要がある。このブログ記事では、「ミニコンセンサスプロトコル」を展開し、さまざまなアスペクトをどのように抽象化しているか、そしてこうした抽象化をさまざまなコンビネーターを定義するためにどのように利用しているかを説明する。以下は、Haskellの知識を持つ読者を想定している。

準備

Cardanoコンセンサス層は、時間をスロットに分けすことを基本前提としたOuroboros(ウロボロス)コンセンサスプロトコルファミリーをサポートするようデザインされている。ブロックチェーンはスロットごとに最大1つのブロックを持つことができる。本稿では、スロット番号をIntとする:

type SlotNo = Int

また、公開鍵暗号のミニマルモデルが必要となる。具体的には

data PrivateKey
data PublicKey
data Signature
verifySig :: Signature -> PublicKey -> Bool

本ブログ記事で唯一必要となる言語拡張はTypeFamiliesである。ただし実際の実装においては複数使用する(希望する場合はフルソースコードのダウンロードが可能)。

コンセンサスプロトコル

本稿の始めに触れたとおり、コンセンサスプロトコルには3つの役割がある。

  1. リーダーチェック(ブロックを生成すべきか)
  2. チェーン選定
  3. ブロックの検証

プロトコルは特定のブロック、特定の台帳にとらわれていないため、シングルプロトコルは異なる種類のブロックや台帳で実行することができる。したがって、これら3つの各役割の「view」は、必要とされるデータに応じて定義される。

リーダーチェック

リーダーチェックは各スロットで実行し、ノードがブロックを生成すべきか決定しなければならない。一般に、リーダーチェックは台帳ステータスから抽出された情報を必要とする場合がある。

type family LedgerView p :: *

例えば、Ouroboros PraosにおけるコンセンサスプロトコルはShelley初期の原動力となるが、ノードのリーダーに選出される(つまりブロックを生成することを許される)可能性はそのステーク次第である。ノードのステークは、もちろん台帳ステータスから抽出される。

チェーン選定

「チェーン選定」とは、2つの競合するチェーンを選択するプロセスを言う。ここで主な基準となるのはチェーンの長さだが、プロトコルによって要件が追加される場合がある。例えば、ブロックは通常サーバーに存在する「ホット」鍵により署名され、次にネットワークに接続されたデバイス上には絶対に存在しない「コールド」鍵によって生成される。ホット鍵が漏洩しても、ノードオペレーターはコールド鍵から新しく生成でき、その新しい鍵に「委任」できる。したがって、選択肢となる2つのチェーンが同じ長さで、同じコールド鍵が署名したチップを持つが、ホット鍵が異なる場合、コンセンサスプロトコルは新しいホット鍵を好む。特定のコンセンサスプロトコルにこうした要件を加えるために、ブロックにどのような情報が表示されることをプロトコルが期待しているかを明示するSelectViewが導入される。

type family SelectView p :: *

ヘッダーの検証

ブロックの検証は主に台帳の領域だ。トランザクションへのすべてのインプットが二重支払いを防ぐために有効であるかの検証などは、台帳層で定義されている。コンセンサス層はブロックの中身についてほぼ無関心だ。実際、暗号通貨ですらなく、ブロックチェーン技術を使用した異なるアプリケーションであっても構わない。

ただしブロック(より正確にはブロックヘッダー)には、コンセンサス層をサポートするいくつかの情報も含まれている。ここでもPraosを例にとると、Praosはブロックチェーンからエントロピーを導出するにあたって、暗号化されたさまざまな証明を期待する。これらを検証することはコンセンサス層の責任であるため、ここでコンセンサスが検証すべきフィールドの第三および最終viewを定義する。

type family ValidateView p :: *

プロトコルの定義

ここでもう一つ、型ファミリー*が必要となる:各プロトコルは実行するために多少の静的情報を必要とする場合がある。すなわち、ブロックに署名するための鍵、リーダーチェックのための自身のアイデンティティなどである。これを「ノードコンフィグ」と呼び、以下のように定義する。

data family NodeConfig p :: *

これらすべてを、コンセンサスプロトコルの抽象化定義にまとめる。3つのclassメソッドは、前述した3つの役割に対応する。各メソッドは静的ノードコンフィグに渡されるが、そのメソッド専用のviewが必要となる。注:ここで p は単純に特定のプロトコルを同定するタイプレベルタグである。バリューレベルでは存在しない。

class ConsensusProtocol p where
-- | チェーン選定
selectChain :: NodeConfig p -> SelectView p -> SelectView p -> Ordering

-- | ヘッダーの検証
validateBlk :: NodeConfig p -> ValidateView p -> Bool

-- | リーダーチェック
--
-- 注意:実際の実装では、これは実際のリーダであることの
-- 何らかの「proof」で追加的にパラメーター化されるが、ここでは省略する
checkLeader :: NodeConfig p -> SlotNo -> LedgerView p -> Bool

例:パーミッシブBFT(PBFT)

パーミッシブBFTはシンプルなコンセンサスプロトコルであり、ノードはラウンドロビンスケジュールに従ってブロックを生成する。すなわち、始めにノードA、次にB、次にC、そしてAに戻る。このスケジュールにおけるノードのインデックスを「NodeId」とする。これはPBFTのみのコンセプトであり、残りのコンセンサス層が意識する必要はない。

type NodeId = Int

PBFTで必要なノードコンフィグはノード自身のID、そしてスケジュールに記された全ノードの公開鍵である。

data PBft -- このプロトコルを特定するタイプレベルタグ

data instance NodeConfig PBft = CfgPBft {
-- | ノードID
pbftId :: NodeId
-- | 全ノードの検証鍵
, pbftKeys :: [PublicKey]
}

PBFTはシンプルなラウンドロビンスケジュールであることから、台帳からの情報はまったく必要としない。

type instance LedgerView PBft = ()

チェーン選定はチェーンの長さのみを見る。わかりやすくするため、ここではチェーンが長いほど、そのスロット番号**は大きくなると仮定する。したがって、チェーン選定に必要なのはチップのスロット番号を知ることのみである。

type instance SelectView PBft = SlotNo

最終的にブロックを検証する際、ブロック生成を許可されたノードにより著名されているか(スケジュールに含まれ得る)を確認する必要がある。

type instance ValidateView PBft = Signature

プロトコルの定義はシンプルになる。

instance ConsensusProtocol PBft where
selectChain _cfg = compare
validateHdr cfg sig = any (verifySig sig) (pbftKeys cfg)
checkLeader cfg slot () = slot mod length (pbftKeys cfg) == pbftId cfg

チェーン選定はスロット番号を比較するだけである。検証では鍵が認定されたスロットリーダーのものであるかを確認し、リーダー選定はそのノードの順番か決定するためにモジュラー演算を行う。

ラウンドロビンスケジュールは現行のリーダーか否かの確認のみに使用される。既存のブロック(検証時)に関しては、単にブロックの署名が認定されたリーダーのいずれか1人によるものかのみを確認するだけで、順序は問わない。これが、PBFTのパーミッシブ、すなわち「許容」の部分である。実際の実装ではもう1点追加の確認(1人のリーダーがシェアを超える署名を行っていないか)を行うが、本稿では省略する。

プロトコルコンビネーター例:明確なリーダースケジュール

イントロダクションで触れた通り、ブロックに署名するノードの順番を明確に決めることができるとテストに役立つ。このためのプロトコルコンビネーターを定義することができる。ここではプロトコルを取り、代わりに固定スケジュールをチェックするためにis-leaderを確認するようオーバーライドするだけである。

data OverrideSchedule p -- As before, just a type-level tag

このようなプロトコルを実行するためには、プロトコルpが必要とする基本コンフィグに加えて、スケジュールとこのスケジュールに含まれるノードIDが設定上必要となる。

data instance NodeConfig (OverrideSchedule p) = CfgOverride {
-- | ブロックに署名するノードの明確なスケジュール
schedule :: Map SlotNo [NodeId]

-- | スケジュールにおける独自の識別子
-- (PBFTはこのような識別子を有するが、多くのプロトコルは有していない)
, scheduleId :: NodeId

-- | プロトコルのコンフィグ
, scheduleP :: NodeConfig p
}

チェーン選定は変化なし、したがってチェーン選定が必要なブロックのviewも変わらず。

type instance SelectView (OverrideSchedule p) = SelectView p

しかし、ヘッダー検証をオーバーライドする必要がある—実際には無効化も行う—なぜなら、ブロックが正しいノードに署名されているとプロトコルが検証してしまうと、明らかにこのオーバーライドと両立しないからだ。したがって、ブロックから検証用として必要となるものはない(検証を行わないため)。

type instance LedgerView (OverrideSchedule p) = ()

プロトコルの定義は自明となる。

instance ConsensusProtocol p => ConsensusProtocol (OverrideSchedule p) where
selectChain cfg = selectChain (scheduleP cfg)
validateHdr _cfg () = True
checkLeader cfg s () = scheduleId cfg elem (schedule cfg) Map.! s

チェーン選定はプロトコルpのチェーン選定のみを使用し、ブロック検証はなにも行わず、is-leaderチェックは静的スケジュールを参照する。

ブロックからプロトコルへ

コンセンサスプロトコルと同様に、特定のブロック選定も必要とされるコンフィグデータに入れられる。

data family BlockConfig b :: *

多くのブロックが同じプロトコルを使用できるが、特定のブロックタイプは特定のプロトコル用に設計される。したがって、ブロックタイプを関連するプロトコルにマッピングする型ファミリーを導入する。

type family BlockProtocol b :: *

それから、特定のプロトコルが必要とするブロック上にviewを構築できた場合に、ブロックがそのプロトコルをサポートすることにする。

class BlockSupportsProtocol b where
selectView :: BlockConfig b -> b -> SelectView (BlockProtocol b)
validateView :: BlockConfig b -> b -> ValidateView (BlockProtocol b)

例:(簡略化した)Byronブロック

必要最小限まで簡略化すると、Byronブロックチェーン上のブロックは以下のようになる。

type Epoch = Int
type RelSlot = Int

data ByronBlock = ByronBlock {
bbSignature :: Signature
, bbEpoch :: Epoch
, bbRelSlot :: RelSlot
}

Ouroborosコンセンサスプロトコルファミリーは、時間をスロットに分けることを前提とすることは前述したが、これに加えて、スロットはエポックにグループ分けされる。Byronブロックに絶対番号は含まれないが、代わりにエポック番号とそのエポックに関連するスロット番号が含まれる。Byronチェーン上のエポックごとのスロット数は10,000強に固定されているが、テストのためには、セキュリティパラメーターkを変更し、設定可能にすると便利だ。これは、Byronブロックで作業するとに必要な設定(の一部)である。

data instance BlockConfig ByronBlock = ByronConfig {
bcEpochLen :: Int
}

Byronコンフィグの次に、エポック番号と関連するスロットのペアを、単純に絶対的なスロット番号に変換する。

bbSlotNo :: BlockConfig ByronBlock -> ByronBlock -> SlotNo
bbSlotNo cfg blk = bbEpoch blk * bcEpochLen cfg + bbRelSlot blk

プロトコルはどうするか。ByronチェーンはPBFTを実行するため、そのように定義できる。

type instance BlockProtocol ByronBlock = PBft

Byronブロックがこのプロトコルをサポートすることは簡単に証明できる。

instance BlockSupportsProtocol ByronBlock where
selectView = bbSlotNo
validateView = const bbSignature

台帳ステータス

コンセンサス層はコンセンサスプロトコルを実行するだけでなく、台帳ステータスの管理も行う。ただし、台帳ステータスが特にどのような状態であるかには頓着せず、単にある種の台帳ステータスがブロックタイプに関連していると仮定するのみである。

data family LedgerState b :: *

ファミリーを1タイプ追加する必要がでてくる。台帳ステータスにブロックを適用させるとき、ブロックが無効であるというエラーを生じさせる可能性がある。この特定の台帳エラーは台帳層に定義され、もちろん極めて台帳特有のものである。例えば、Shelley台帳にはステーキング関連のエラーが生じるが、Byronにはありえない。ステーキングをサポートしていないためだ。そして、暗号通貨でない台帳は、極めて異なるタイプのエラーを生じさせるだろう。

data family LedgerError b :: *

ここで、2つの型クラスを定義する。まず、単にインターフェイスを台帳層に以下のように説明する。ブロックを台帳ステータスに適用可能にする必要があり、エラーとする(ブロックが無効の場合)か、台帳ステータスを更新する。

class UpdateLedger b where
applyBlk :: b -> LedgerState b -> Either (LedgerError b) (LedgerState b)

次に、あるブロックに関連する台帳をそのブロックに関連するコンセンサスプロトコルに接続する型クラスを定義する。BlockSupportsProtocolがコンセンサスプロトコルが必要とするブロックからviewを導出する機能性を提供するように、LedgerSupportsProtocolはコンセンサスプロトコルが要求する台帳ステータスからviewを導出する機能性を提供する。

class LedgerSupportsProtocol b where
-- |レジャーステータスから関連する情報を抽出
ledgerView :: LedgerState b -> LedgerView (BlockProtocol b)

次のセクションでは、台帳との統合(UpdateLedger)とコンセンサスプロトコルへの接続(LedgerSupportsProtocol)を分けることが有効である理由を説明する。

ブロックコンビネーター

コンビネーターの威力を示す最後の例として、ここではブロック上のコンビネーターとその関連する台帳を定義できることを示す。これが便利な場合の例として、実装実行可能な仕様記述を搭載したByronブロックチェーンがある。コンセンサス層をこの両台帳でインスタンス化すると便利である。実装が仕様とすべての点で合致することを検証できるからだ。これは、この「二重台帳」セットアップにおけるブロックが、実際には1組のブロックであることを意味する***。

data DualBlock main aux = DualBlock {
dbMain :: main
, dbAux :: aux
}

二重台帳ステータスと二重台帳エラーの定義は類似している。

data instance LedgerState (DualBlock main aux) = DualLedger {
dlMain :: LedgerState main
, dlAux :: LedgerState aux
}

data instance LedgerError (DualBlock main aux) = DualError {
deMain :: LedgerError main
, deAux :: LedgerError aux
}

二重ブロックを二重台帳ステータスに適用するためには、単純に関連するステータスに各ブロックを適用させる。この専用コンビネーターは、特定のブロックが有効であるか否かについて2つの台帳が常に合致すると仮定する。これは実装と仕様の比較に適しているのであり、他の選択(他のコンビネーター)も可能である。

instance ( UpdateLedger main
, UpdateLedger aux
) => UpdateLedger (DualBlock main aux) where
applyBlk (DualBlock dbMain dbAux)
(DualLedger dlMain dlAux) =
case (applyBlk dbMain dlMain, applyBlk dbAux dlAux) of
(Left deMain , Left deAux ) -> Left $ DualError deMain deAux
(Right dlMain' , Right dlAux') -> Right $ DualLedger dlMain' dlAux'
_otherwise -> error "ledgers disagree"

二重台帳の目的は2つの台帳実装の比較であることから、初めの(メイン)ブロックによるすべてのコンセンサス関連事項があれば十分であり、補助ブロックのProtocolLedgerViewのインスタンスは不要であり、実際これを得ることは一般に不可能である。つまり、二重ブロックのブロックプロトコルは、メインブロックのブロックプロトコルということになる。

type instance BlockProtocol (DualBlock main aux) = BlockProtocol main

instance LedgerSupportsProtocol main
=> LedgerSupportsProtocol (DualBlock main aux) where
ledgerView = ledgerView . dlMain

必要となるブロックのコンフィグは、両ブロックのブロックコンフィグである。

data instance BlockConfig (DualBlock main aux) = DualConfig {
dcMain :: BlockConfig main
, dcAix :: BlockConfig aux
}

これで、二重ブロックがプロトコルもサポートすることを簡単に示すことができる。

instance BlockSupportsProtocol main => BlockSupportsProtocol (DualBlock main aux) where
selectView cfg = selectView (dcMain cfg) . dbMain
validateView cfg = validateView (dcMain cfg) . dbMain

結論

Cardanoコンセンサス層はもともとCardanoブロックチェーンのためにデザインされ、現在Byronを、まもなくShelleyを実行する。IOHKのエンジニアは当初特定のブロックチェーンのためにデザインするべきであり、のちにコンセンサス層を他のブロックチェーンに使用するときに一般化すればよいという議論も成り立つ。しかし、これには重大な欠陥がある。

  • テスタビリティが下がる。どのノードがいつブロックを生成するか、スケジュールをオーバーライドしたり、二重台帳を実行することなどができなくなる。
  • 論理的に独立しているものをもつれさせることになる。抽象化アプローチにおいて、Shelley台帳は3つのパートから構成される。Byronチェーン、Shelleyチェーン、そしてこれら2つを仲介するハードフォークコンビネーターである。抽象化なしには、このような分離は達成困難である。コードの理解と維持の難度が上がる。
  • 抽象化コードではバグの生じやすさが減少する。単純な例を示すと、二重台帳コンビネーターはそれが繋ぐ2つの台帳のポリモーフィックであり、各台帳は異なる型を持つことから、正しい型コードを書くことができなくても、いずれにせよ例えばメインブロックを補助台帳に適用させようとする。
  • 新しいブロックチェーン用にコンセンサス層をインスタンス化したい(必然的にすることになる)時期が来たら、最初から抽象化して書いておくことで、否が応でもデザインが注意深くなり、組み合わせるべきでないものを組み合わせることや、熟考の結果実際のブロックチェーン上ではたまたま正当化できるが一般には当てはまらないかもしれないような仮定を立てることを避けるようになる。デザインが実行に移されてからこうした問題を修正するのは難しい。

もちろん、このすべては優秀な抽象化能力を持つプログラミング言語を必要とする。幸運なことに、Haskellはこれに完璧に当てはまる。

-「開発者を掘り下げる」シリーズ第1回 -

*さまざまなviewと異なり、NodeConfigはデータファミリーである。ノードコンフィグはすべての関数を通過するため、データファミリーとしてNodeConfigを持つことによりpが決定されるため型推論に役立つ。残りを型ファミリーのままにしておくと便利であり、不必要なラップ、アンラップを回避できる。

**スロット番号はすべてのスロットがブロックを1つ持つ場合のみチェーン長のプロキシとなる。これは、一時的なネットワークパーティションのないPBFTのみに当てはまり、Praosなどの確率的コンセンサスアルゴリズムにはまったく当てはまらない。言い換えると、密度の低いチェーンは、短いが密度の高いチェーンより、チップに大きなスロット番号が含まれる場合がある。

*** 実際のDualBlockコンビネーターには2つのブロックに関連する3番目の情報が含まれる(トランザクションIDなど)。本稿では煩雑さを避けるために省略した。

1 Like