blockchainjapan’s blog

旬のブロックチェーンを記事を厳選して提供!

AptosのBFTコンセンサスを学ぼう!:Pontem Network学習シリーズ

 

AptosのBFTコンセンサスを学ぼう!


Pontem Network学習シリーズ

 

Pontem Network

Pontem Networkのホワイトリスト登録はこちらから!
アンバサダーも募集中です。Aptos Japanにもご参加ください。

AptosはAptos BFTという独自のコンセンサスアルゴリズムを使用していますが、これはHotStuffとpBFT(Practical Byzantine Fault Tolerance)をベースにしています。Pontem Networkによる今回の学習記事を読んで、各用語の意味をおおまかに理解していきましょう。


Aptosとは?どのようなコンセンサスを使用してるのか?

Aptosは新しいブロックチェーンで、業界で最も速く、最もスケーラブルなL1になることを目標としています。実際、160,000tpsを達成、レイテンシは1秒未満、つまり1秒以内の取引確認を公表しています。

Aptosは、Moveという新しいプログラミング言語と、その仮想マシンであるMove VMを使用しています。これらの技術は、もともとMeta(元Facebook)が出資していたブロックチェーンプロジェクト「Diem」のために開発されたものです。2022年3月にDiemプロジェクトがSilvergate Networkに売却されると、元Diemのエンジニアのグループが独自の道を歩み、Aptosを作り上げたという経緯があります。

他のブロックチェーンと同様に、Aptosにもコンセンサスアルゴリズム(ブロックやトランザクションの承認手続きの仕組み)があります。AptosのアルゴリズムはAptos BFTと呼ばれ、これはDiemのために開発されたDiem BFTと非常によく似た仕組みを持っています。

Aptosのコンセンサスは、タマネギやマトリョーシカのように、小さなものが大きなものの中に入っているような構造をしており、ひとつひとつ順番に剥がしていくイメージが近いかもしれません。

この記事の流れは以下のとおりです:

  1. BFTビザンチンフォールトトレランスについて、そしてそれがなぜブロックチェーンにとって重要なのかについて説明します
  2. BFTコンセンサスの仕組みと、それが完璧でない理由を説明します
  3. 改良された実用的なBFTコンセンサス、pBFTについて説明します
  4. 高tpsを可能にするBFTの先駆的な実装であるHotStuffについて説明します
  5. 最後に、AptosがHotStuffのコンセンサスをどのようにAptos BFTに変更し、最も安全なL1ブロックチェーンを構築するためにAptos Incentivized Testnet(AIT)を通じてどのようにストレステストを実行しているのかについて説明します

ブロックチェーンにおけるBFTとは?

BFTとは「ビザンチンフォールトトレラント(Byzantine Fault-Tolerant)」の略です。ネットワークが、メンバーの一部が悪意あるものになったり、オフラインになったとしても、正常に動作し続けることができる場合、ビザンチンフォールトトレラントであると言えます。

いわゆるビザンチン問題はブロックチェーンに限ったことではなく、ゲーム理論で有名な現象です。敵に攻撃を仕掛けるかどうかを集団で決めなければならない将軍の集団を想像してください。

この場合に、2つの問題があります:

  1. 各将軍は自陣にいて、伝令を使ってメッセージを送るなどして相互にコミュニケーションを取らなければならない
  2. 裏切り者の将軍がいる場合、彼は、最悪の作戦に投票したり、他の将軍に矛盾するメッセージを送って合意を得られないようにしたり、全く何も送らないかもしれない

軍団を救うために、善良な将軍は、裏切り者の存在の可能性があるにもかかわらず、多数決を行う方法が必要となります。ブロックチェーンでは、一部のノードが悪意を持って行動したり、クラッシュしたりしても、適切に機能するノードがブロックが有効かどうかを正しく判断できる必要があることを意味します。

ここでいう「悪意ある行為」とは、あるノードが無効なブロックやトランザクションを有効だと宣言したり、その逆の行為を意味します。例えば、あるトランザクションが二重消費(同じアドレスで既に使われたコインを再度使うこと)である場合、それは有効ではないにもかかわらず、有効であるとしたり、偶発的にノードが不良稼働することもあります。

ネットワークが分散型である場合、どのノードが正しいメッセージを送っているのか、あるいは不正メッセージを送っているのかを知ることも、確認することもできないため、ビザンチンフォールトトレラントブロックチェーンを構築するのは非常に難しいのです。

ビットコインの解決策と現代のBFTコンセンサスとの比較

ビットコインの生みの親とされるサトシ・ナカモトはビザンチン問題についても認識しており、彼は非常に堅牢な解決策を出しましたが、高い代償を払うことになります。

ブロックを提案(ブロードキャスト)するには、ノードが複雑な暗号パズルの解法も提案する必要があり、他の全てのノードがその受け入れ/拒否を選択しなければなりません。こうして無効なブロックが迅速に特定され、他のノードを欺こうとする試み非常に困難なものとなります。

これがProof-of-Workマイニングの強みですが、裏を返せば、全てのノードが他のノードの提出物を全てチェックしなければならないということでもあります。つまり、各将軍は、他の将軍が送信したメッセージを毎秒数十億個、全て読む必要があるということです。これには膨大なエネルギーと時間がかかるため、ビットコインは、最もビザンチン的なフォールトトレラントブロックチェーンでありながら、速度が遅く、高コストで、膨大なエネルギーを消費してしまうのです。

現在、Aptosを含む大半のL1ブロックチェーンは、Proof-of-Workではなく、ビザンチン耐障害性を持つProof-of-Stakeコンセンサスを使用しています。これらのモデルに共通しているのは、3分の1までのノードが悪意を持つようになっても許容できることです。その部分を見てみましょう。


BFT Proof-of-Stakeコンセンサスの耐性

あなたが誠実なビザンチン将軍だとして、机の上に同僚からのメッセージが山積みになっており、それぞれが「攻撃」または「撤退」と言っているのを想像してください。あなたはどうしますか?

あなたは、何人かの将軍が裏切り者であると疑っていますが、具体的に誰が裏切り者なのかはわかりません。そこで、「攻撃」と「撤退」のメッセージを全て数えて、より多くの票を集めた作戦を採用するのが最善であると選択します。ここでは、誠実な将軍は全員、より良い戦略(例えば攻撃)に投票し、裏切り者は全員、負ける戦略(撤退)を選択すると仮定します。

例1:4人の将軍と1人の裏切り者がいる場合、誠実な将軍は同じく誠実な将軍から2票の「攻撃」、裏切り者の将軍から1票の「撤退」、さらに自分自身の「攻撃」票を受け取ることになります。この場合、全ての忠実な将軍(3人)が攻撃することで軍が勝利します。

しかし、4人の将軍の中に2人の裏切り者がいた場合、全ての誠実な指揮官は1つの「攻撃」メッセージと2つの「撤退」メッセージを受け取ることになります。誠実な将軍はどうしたらいいかわからず、作戦は失敗に終わるでしょう。

n(将軍の数)=4のとき、1人の裏切り者を許容することができる。

例2:7人の将軍がいる場合、1人の裏切り者は完全に許容することができます。また、裏切り者が2人いた場合、全ての誠実な将軍は4つの「攻撃」メッセージと2つの「撤退」メッセージを受け取るので、大多数の将軍(6人の誠実な将軍)は敵を攻撃して勝利します。

しかし、裏切り者が3人いた場合、全ての誠実な将軍は3つの「攻撃」と3つの「撤退」のメッセージを受け取ることになり、どうしたらいいかわからず、作戦は失敗に終わるでしょう。

n=7のとき、2人の裏切り者を許容することができる。

つまり、ネットワークが許容できる最大の裏切り者の数(t)は、

t=(n-1)/3

であることを数学的に示すことができ、t人の裏切り者がいる場合、システムにビザンチン障害耐性を持たせるためには3t+1個のノードが必要となるということが解ります。したがって、悪意のあるノードの数は全体の3分の1以下でなければならないということになります。


より実用的なBFTコンセンサス(pBFT)

実際のネットワークでBFTコンセンサスを実現しようとすると、全てのノードが互いのメッセージをチェックすることで、行動を選択するために余分な時間とリソース、つまりオーバーヘッドが発生することになります。

このオーバーヘッドを抑えるために、コンピュータ科学者のBarbara LiskovとMiguel Castroは、1999年にPractical Byzantine Fault Tolerant algorithm(pBFT)を提案しました。

分散ネットワークのパイオニア Barbara Liskov氏

pBFTでも、「悪い」ノードの数は3分の1以下というルールは有効となります。裏切り者の可能性があるf個に対して、コンセンサスを維持するためには合計で3f+1個のノードが必要となります。異なる部分は、各ラウンドでノードが「新しいブロックの作成に責任を持つリーダーを選択する」という部分です。ノードは一次側と二次側のクライアントに分けられます。

pBFTのメッセージ交換は複数のステップを経て実行されます:

  1. クライアントがリーダーに「攻撃か、撤退か」というリクエストを送る
  2. リーダーはその要求を各将軍にブロードキャストする
  3. 各将軍とリーダーは、ネットワークに応答を返す
  4. 各将軍とリーダーは、2f+1個の一致するメッセージ(自身のものも含めて)を集めたら、コンセンサスに達したと結論づける
  5. クライアントがf+1個のマッチングメッセージを受信した段階で、クライアントもコンセンサスの成功を認める
  6. 正直なノードは、リーダーノードが静止したり悪意をもった場合に、リーダーノードを交代させるための投票手段も持っている

pBFTの最大の利点の1つは、「ファイナリティ」にあります。ノードがトランザクションやブロックが有効であると合意すると、それが確認され最終的なもの(ファイナリティ)となります。イーサリアムビットコインのように、複数のブロック確認を待つ必要はありません。

裏を返せば、ノード(バリデータ)のセットが大きくなると、各ラウンドで相互送信するメッセージ数が急速に増加し続けるということでもあります。例えば、7つのノードのセット(最大2つの「裏切り者」が存在)の場合、コンセンサスの1ラウンドは最小で71メッセージになります。これが13ノード(86%増)になると、メッセージ数は237(234%増)に達し、この指数関数的な増加が繰り返された結果、pBFTネットワークはスケーリングが困難になります。

ブロックチェーンにおけるpBFTの実装で最も有名なのは、Cosmosが採用しているTendermintがあげられます(現在Igniteに名称変更)。オリジナルと比較すると、リーダーローテーションの仕組みなど複数の調整が追加され、うまくスケールするようになっています。

他のpBFTの実装としては、ZilliqaHyperledger Fabric、そしてAptosで使われているコンセンサスであるHotStuffがあります。


HotStuff:Aptos BFTを生んだBFTコンセンサスアルゴリズム

2018年3月、VMware Researchは、pBFTを大幅に改善した新しいコンセンサスモデルとしてHotStuffを発表しました。


より明確なコミュニケーションの仕組み

各ノードは、リーダーや他の全ての「一般」にメッセージを送るのではなく、リーダーとのみ通信します。リーダーは投票対象となるメッセージ(提案ブロック)をブロードキャストし、各ノードはその投票をリーダーに送り、リーダーはそのメッセージを収集します。

リーダーはn-f票の定足数証明書(QC)を獲得する必要があります。nはノードの総数、fはシステムがnに対して許容できる悪意のあるノードの最大数を示します。QCに達すると、リーダーは結果をブロードキャストし、ノードはその決定を検証します。

これによって、システムを通過するメッセージ総数が大幅に削減され、ネットワークのスケーラビリティが非常に高くなります。実際、Aptosは最もスケーラブルなL1ブロックチェーンとなっています。

HotStuffのリーダー中心の通信システムは、Aptosを比類のないレベルで高速化します。具体的には、秒未満のファイナリティで秒間100,000 ~ 160,000のトランザクションを処理することができ、これはブロックチェーン上でトランザクションの確認までに1秒かからずに済むことを意味します。ちなみに、Solanaではトランザクションの確定に約6秒、Binance Smart Chainでは約30秒かかります。


新たなリーダーの選出プロセスの改善

新たなバリデータをリーダーに選出するプロセスは、コンセンサスメカニズムの他の部分とスムーズに統合されています。一方、pBFTでは、新たなリーダーを提案しようとするノードは、まず他のノードからリーダーを選ぶことに同意するという確認を集める必要があります。

HotStuffでは、新たなリーダーを選ぶための方法として、ペースメーカーという方法を採用しています。リーダーを常に交代させることは、リーダーノードに問題がある場合のみに交代が可能になるpBFTとは対照的に、余分なオーバーヘッドを発生させてしまいます。しかし一方で、常にローテーションを行うことで、リーダーが悪意を持ち、他のノードに気づかれないような方法でシステムを弱体化させるという事態を回避することが可能となるのです。


パイプライン

これはpBFTの基本モデルを改良したもので、リーダーは準備段階の異なるブロックに対して複数の「スロット」を持ち、同時に複数のブロックに対応できるようにします。これによって、1つのブロックの検証には数ラウンドのメッセージ(Prepare、Pre-commit、Commit、Decide)が必要ですが、ネットワークは同じラウンド内で、ブロックXのDecideステージ、ブロックX-1のCommitステージ、ブロックX-2のPre-commitオペレーション、ブロックX-3のPrepareステージを完了させることが可能となります。

これは、HotStuffの論文の図にも反映されています‍:

 

Aptos BFT:Aptosで使用されるコンセンサス

Facebookが独自のブロックチェーンLibraの構築に着手した際、HotStuffは高速でスケーラブルかつ堅牢なコンセンサスアルゴリズムを生成するために採用されました。これはLibra BFTと名付けられましたが、LibraがDiemに改名した段階でDiem BFTとなり、現在はAptos BFTとして知られています。

Diemは2022年3月にSilvergateに売却されましたが、Diem BFTのコンセンサスアルゴリズムオープンソースであったため、AptosチームはそれをMove言語とMove VMと共に使うことができました。

HotStuffとAptos BFTの違いについて、ここでは技術的な詳細説明はしませんが、Aptosの重要な特徴をいくつか紹介します。


パーミッションレスとパーミッション

まず、Diemはパーミッションド・ブロックチェーンとして開発されているため、Diemは企業によって選ばれたバリデーターを持つことになります。これは、Binance Smart Chainが意図的な21人のバリデーターを持っているのと同様です。

対照的に、Aptosは数千のノードを持つことができます。ハードウェア要件を満たせば、誰でもノードを作成することができ、どのノードもリーダーになることが可能です。


ペースメーカー

HotStuffのセクションでペースメーカーを紹介しましたが、その詳細な仕様については触れていません。ペースメーカーは各バリデータノードに組み込まれた機能で、投票ラウンドを破綻なく進めることを保証する機能を持ちます。これにより、次の場合に新たなリーダーを選出することが可能になります:

  • 現在のリーダーがブロックのブロードキャストに成功した場合
  • 現在のリーダーが一定時間静止した場合 (最大許容遅延時間をペースメーカーで設定)
  • リーダーが証明に必要な数の有効票を集められなかった場合


VRFによるリーダー選択

ペースメーカーは、同じバリデータが連続してリーダーに選出されないように、また誰もがプロセスを操作できないようにすることで、選出の予測可能性を排除しています。これは、VRF(Verifiably Random Function)を使用することで実現されています。


少ないメッセージ数=少ないオーバーヘッド

AptosBFTでは、悪意のあるノードが存在しない場合、各ノードが1ラウンドに送信するメッセージは1つのみとなります。


コンセンサスキーのローテーション

暗号ウォレットがトランザクションに署名するために必要な秘密鍵を持っているように、ノードも秘密鍵としてコンセンサスキーを持っています。バリデータはこの鍵を使ってブロックに投票する仕組みです。

秘密鍵の盗難はブロックチェーンにとって深刻なリスクですが、Aptosはエレガントな解決策を導入しています:ユーザーとバリデーターの両方に対してキーローテーションを実行します。これは、メールのパスワードを定期的に変更するようなものです。コンセンサスキーのローテーションに加えて、Aptosのバリデータはいくつかの新しいキーリカバリ技術にアクセスすることができます。

 

ノードへのインセンティブ

Aptos BFT(DiemBFT)はProof-of-Stakeを採用していますが、HotStuffはPoSと組み合わせる必要がないのが本来の姿であると言えます。Aptosでは、バリデータはコンセンサスに参加するためにステークする必要があります。また、ルールを守って稼働している限り、報酬を獲得することができます。逆に、バリデータがコンセンサスのルールを破った場合、そのステークはスラッシュ(没収)される可能性があります。

繰り返しになりますが、AptosとDiemには大きな違いがあります。Aptosでは、誰でもトークンをステークして自身のノードを立ち上げたり、既存のバリデータにトークンを委任したりすることができます。元々のDiemの計画では、ローンチから5年以内にこのようなパーミッションレスモデルに切り替える予定でした。


Aptos BFTコンセンサスは機能するのか?

Aptosのような新しく誕生するL1ブロックチェーンでは、メインネットのローンチ前にコンセンサスのストレステストを行うことが不可欠です。

投票は意図したとおりに実行されるか?秒以下のブロックの確定が可能か?また、悪意のあるバリデータ集団が組織的に攻撃した場合の耐性は?

このようなAptos BFTのテストは、Aptosのインセンティブ付きテストネット・プログラム(AIT)の目標の1つです。AITは、数百のテストネットノードのバリデーターを集め、バグを探したり、アップグレードを実施したり、その他のタスクを実行することで報酬を獲得するというものです。AIT1、AIT2、AIT3の各ステージには、何千人ものバリデーターが応募しています。

Aptosミームチャンネルより 出典: @SvyatoyRen

AITは、2021年に「Game of Stake」でインセンティブ付きテストネットの先駆者となったCosmosのネットワークの成功例を踏襲しています。このキャンペーンでは、バリデーターはコンセンサスを破るというタスクがあり、それを全力で実行しました。これは、事前にコンセンサスの耐性をテストすることの重要性を示すものでもあります。

Pontem Networkは、Aptosの基盤となるdAppsとプリミティブのセットを構築していることから、同様にセキュリティファーストのアプローチをとっています。Pontemは現在、複数のコード監査を受けており、今後数ヶ月で、開発者がPontemのツールをテストするための、独自のカナリアネットワークを立ち上げる計画もあります。

Aptosは、100–130k tpsという業界最速かつ量産可能なL1を目指しており、これはAptosBFTのような最先端のコンセンサスアルゴリズムがあればこそ実現可能となるものです。Aptosは2022年秋にメインネットをローンチする予定であり、間もなく本番環境でその姿を見ることができるはずです。

Pontem Networkの記事をお読みいただきありがとうございます。今後もチェーンやプロジェクトの枠を超えて、暗号/ブロックチェーン分野全体の発展に向けた情報材料の共有に取り組んでいきます。


Pontem Network

Pontem Networkは、最も高い生産性と安全性を持ち、スケーラブルなブロックチェーンであるAptosの基盤となるdAppsと開発ツールを構築している製品スタジオです。私たちはAptosチームと共に、私たちは世界中の最初の10億人のブロックチェーンユーザーを参加させることのできるエコシステムを構築しています。Pontem Networkの製品は、Move言語とMove VMを使用しています。これらは、元々Metaが支援するブロックチェーンであるDiemのために開発された技術です。

Pontem Networkの将来的なトークンリリースに向けたホワイトリスト登録はこちらから!また、アンバサダーも募集中です。

Webサイト| Twitter | Telegram | Discord | ドキュメント| GitHub