名前だけ覚えるブロックチェーン

名前だけ覚えるブロックチェーン: BFTなコンセンサスアルゴリズム SAPPORO ENGINEER BASE #05 @MSprzk

自己紹介

自己紹介 宮本直幸 - Miyamoto Naoyuki N高等学校（北海道情報大学に進学予定） JS, TS, Java フロントエンド、バックエンド （最近 電子工作で遊ぶのにハマってます） @Msprzk とまとくん

アジェンダ 1. BFTなコンセンサスアルゴリズムとは 2. ビザンチン将軍問題 3. 具体例 4. どこで使われているの 5. 代表的なコンセンサスアルゴリズム 6. まとめ

1. PBFT 2. PoW 3. PoS といきたいところですが...

BFTなコンセンサスアルゴリズム

BFTなコンセンサスアルゴリズム BFTなコンセンサスアルゴリズム →ビザンチン故障（Byzantine Fault）に対して耐性を持つコンセンサス アルゴリズムのこと。 ビザンチン故障→ビザンチン将軍問題によって起こる故障（後ほど説明） コンセンサスアルゴリズム→分散システムやブロックチェーンにおいて、複数のノー ドが合意（コンセンサス）を形成するアルゴリズムのこと。

ビザンチン将軍問題

ビザンチン将軍問題とは ビザンチン将軍問題 偽の情報を流すものが存在するとき、分散 システムが一貫性を保つためにはどうした らいいのかという問題。 この概念は1982年にレスリー・ランポート 博士らによって提唱された。 レスリー・ランポート博士 (https://www.lamport.org/ より)

• https://www.lamport.org/

具体例

具体例 ときは14XX年、 ビザンツ帝国（東ローマ帝国）という国がありました。 ビザンツ帝国

具体例 ときは14XX年、１４YY年、 ビザンツ帝国（東ローマ帝国）という国がありました。 ビザンツ帝国

具体例 ときは14XX年、１４YY年、 ビザンツ帝国（東ローマ帝国）という国がありました。 攻め込む ビザンツ帝国 BC王国（仮）

具体例 前提 ビザンツ帝国の将軍たちはそれぞれ部隊を率いて、包囲している。各部隊 はお互いに離れた場所にいて、伝令を相互に送ることでしか連絡できな い。 →1対1通信しか行えない（Peer to Peerというやつ) 行動を提案する将軍は、各部隊に攻撃または撤退の提案を送ります。受 け取った各部隊の将軍はそれを他の将軍たちに転送します。 この中に裏切り者がいる。裏切り者の将軍は、提案を逆にして、他の将軍 たちに送る。 その状況で、攻撃か撤退かの判断を一致させることを目標にする。

具体例 B A C

具体例 3人の場合 B A C

具体例 3人の場合 B(裏切り） A ？？？？？ C

具体例 4人の場合 B(裏切り） A C D

具体例 4人の場合 B(裏切り） A C D

具体例 4人の場合 B(裏切り） A C D

具体例 4人の場合 A ここでクイズ C B(裏切り） D

Q. 裏切り者が2人のときは、誠実な将軍は最低 何人いたらいいでしょうか？ A, 4人 B, 5人 C, 7人

Q. 裏切り者が2人のときは、誠実な将軍は最低 何人いたらいいでしょうか？ A, 4人 B, 5人 C, 7人

クイズ 裏切り者が n人 のとき、誠実な将軍が 2n + 1人 以上ならば ↓ 誠実な将軍は高確率で判断を一致させ られる！

具体例 4人の場合 B(裏切り） A C D

具体例 4人の場合 n=1 2n + 1 に代入すると... 2×2+1=5 A. 5人 A C B(裏切り） D

どこで使われているの？

どこで使われているの？ ビザンチン将軍問題 分散システムにおける同意問題 ※ここにおける同意とは、複数のコンピュータで同じ 値を持つこと。

どこで使われているの？ 課題 コンピュータは壊れる。間違った通信や処理を始めることもある。 →分散システムやブロックチェーンにビザンチン将軍問題の考 え方を取り入れ、壊れたコンピュータを裏切り者に見立てて、 正常なコンピュータの合意を形成できるようにするといった活用 がされている。

どこで使われているの？ ブロックチェーン BFT(Byzantine Fault Tolerance)という考え方があり、ブロック チェーン分野でとても重要なものになっている。 Bitcoinなど暗号資産が存在するために不可欠。 ノード上のトランザクションの

代表的なコンセンサスアルゴリズム

復習 コンセンサスアルゴリズム 分散システムやブロックチェーンにおいて、複数のノードが 合意（コンセンサス）を形成するアルゴリズムのこと。

代表的なコンセンサスアルゴリズム 1. PBFT 2. PoW 3. PoS

代表的なコンセンサスアルゴリズム 1. PBFT 2. PoW 3. PoS

PBFT (Practical Byzantine Fault Tolerance) Practical Byzantine Fault Tolerance 主な使用: エンタープライズ向けのブロックチェーン 仕組み: Practical Byzantine Fault Tolerance https://hazm.at/mox/distributed-system/algorithm /transaction/pbft/index.html

• https://hazm.at/mox/distributed-system/algorithm/transaction/pbft/index.html

PBFT (Practical Byzantine Fault Tolerance) Practical Byzantine Fault Tolerance メリット:ブロックの確定が即時で行える。 PoW で必須となるハッシュ計算が必要ないため commit までの時間が短く、高いスループットを得ることができる。 電力消費が少ない。 課題: グループを大規模にするとスループットが大きく低下する。 Sybil Attack を受けやすい。 プライベート型やコンソーシアム型のネットワークでしか利用 することができない。（他のコンセンサスアルゴリズムと組み 合わせる or PBFTを最適化する必要あり）

代表的なコンセンサスアルゴリズム 1. PBFT 2. PoW 3. PoS

PoW (Proof of Work) Proof of Work 主な使用: ビットコインなど 仕組み: ハッシュ値を計算し、ある値になるようなブロックを見つける ことで、ブロックを追加する権利を得る。 メリット: 過去のブロックを改ざんしようとすると、そのブロック以降の ブロックのハッシュ値を計算し直す必要があるため、改ざんは 実質不可能。 課題: 計算量が膨大であるため、エネルギー消費が大きい。 チェーンが伸びるほど改ざんの難易度が上がるため、初期の 改ざん耐性はBFTなものより低い。 51%以上の計算能力を持つものが現れるとコントロールさ れてしまう

代表的なコンセンサスアルゴリズム 1. PBFT 2. PoW 3. PoS

PoS (Proof of Stake) Proof of Stake 主な使用: Ethereumなど 仕組み: 保有している暗号資産の量に応じて、承認権を持つ人を選ぶ。 保有期間も考慮するタイプのPoSも存在する。 メリット: 計算量がPoWより少なく、環境負荷が低い。 課題: 保有期間が長い方が有利な性質のため、取引があまり行われ ない。 中央集権化のリスクがPoWより高い。

まとめ

まとめ ● 偽の情報を流すものがいるとき、誠実に情 報を伝えるものが 2n + 1人以上いれば高確率で合意でき る。 ● PBFT, Pow, PoS をというアルゴリズム の名前だけ覚えた

参考 画像引用 https://www.lamport.org/ 参考 佐藤一郎. (2015). ‘「「ビザンチン将軍問題」とは何か」第69号 NII Today’, NII Today / 国立情報学研究所, 2015-09, https://www.nii.ac.jp/today/69/4.html (Accessed: 2025-02-26) Leslie Lamport, Robert Shostak, Marshall Pease: "The Byzantine Generals Problem", ACM Transactions on Programming Languages and Systems, Vol.4, No.3, pp. 382-401, 1982. https://bitcoin.dmm.com/column/0171 https://bitcoin.dmm.com/glossary/proof_of_stake https://www.jstage.jst.go.jp/article/bplus/14/1/14_19/_pdf https://gaiax-blockchain.com/poi https://coincheck.com/ja/article/213 https://hazm.at/mox/distributed-system/algorithm/transaction/pbft/index.html

• https://www.lamport.org/
• https://www.nii.ac.jp/today/69/4.html
• https://bitcoin.dmm.com/column/0171