自己紹介

古瀨 淳 (ふるせ じゅん)

ダイラムダ株式会社代表取締役

経歴:

• 計算機科学を専攻 (プログラミング言語処理系)
• 投資金融関連企業に勤務
• Tezos ブロックチェーンのコア開発

長く「金融」にいますが、投機には興味がなく、株や FX をやったことがありません。 儲け方を聞かれても困ります。

はじめに

本講座について

ブロックチェーンの実装例の紹介を通して、数理論理学の社会インフラ実装への可能性を理解することを目標とします。

オープンソースによる国際的な共同開発についても紹介できればと思います。

ブロックチェーンとは?

• 暗号通貨
• ビットコイン、イーサリアム
• Web3
• 投機、億り人
• アナーキー
• ハッキング、詐欺💦

ブロックチェーンとは!

本講座では、私の経験を技術的な視点で紹介できればと思います。

夢のある儲け話は一切ありません。

ブロックチェーンのコア開発

ブロックチェーンシステムそのものの開発

• プロトコル設計
• ノード(サーバー)の改良
• 新機能の搭載
• コンパイラ

ブロックチェーンを使ったアプリの開発ではありません

• ウォレット/交換所ソフトウェア/ゲーム の開発とかではない

地味です

講座の流れ(予定)

あくまで予定です

1. ブロックチェーンの基本原理
2. ハッシュデータ型
3. スマートコントラクト
4. ブロックチェーンの安全性
5. ゼロ知識証明

講義資料は授業前に TACT にアップします。

簡単な演習を課題を出したいと思います。
ネットが繋がっているラップトップがあると良いです。
授業中に無理な場合は手順がスライドにあるので見てください。

数理、実装といってもさわりだけです

ブロックチェーンは

• 統計
• 暗号
• ゲーム理論
• プログラミング言語理論
• 並列分散
• コンピュータセキュリティ
• システムプログラミング
• etc.

の総合格闘技なので、全てを深く知るのは大変。ご了承ください。

ꜩ Tezos ブロックチェーン

講義での例や、演習では Tezos ブロックチェーン を使います。

マイナーですいませんが、

• 講義する人が Tezos に詳しいので。
• 多くの話は他のブロックチェーンでも同じはずです。

Tezos に特化した内容を含む場合、タイトルに ꜩ をつけます。
(Tezos を例に一般的な話をしていることも多々あります。)

おことわり

この解説はブロックチェーン技術を理解を助けるためのものです。 暗号通貨の売買を奨励するものではありません。

金銭的価値をともなう実トークン取引は、投機対象としては高リスクであることを理解し、 自己責任で行ってください。

改めて、ブロックチェーンとは?

ブロックチェーンとは

汎用分散データベース

• 台帳方式
• 分散環境
• オープン・ネットワーク、非中央集権制
• スマートコントラクト

台帳方式(ledger style)とは

変更履歴集積としてのデータベース

ブロックチェーンも台帳方式

変更履歴集積としてのデータベース

• \(S_i\) : ブロックチェーン状態。\(S_0 = \mathtt{∅}\)
• \(B_i\) : ブロック: 状態の差分
• \(S_i = B_i(S_{i-1})\)

ブロックが列をなしてチェーンとなる:

\[\mathtt{∅} \stackrel{B_{1}}→ S_{1} \stackrel{B_{2}}→ S_{2} \stackrel{B_{3}}→ S_{3} \stackrel{B_{4}}→ S_{4} \stackrel{B_{5}}→ S_{5} \stackrel{B_{6}}→ \cdots\]

分散環境

複数のデータベースノードが状態のレプリカを持つ:

• 高耐故障性
• 負荷分散

各ノードがレプリカを持つ

変更はノードを伝搬する

オープン・ネットワーク

パーミッションレスな分散データベースネットワーク:

誰もがデータベースに読み書きできる

• ただし書き込みは一定の認証が必要

誰もがデータベースノードを立ててネットワークに参加できる

• 高耐故障性、負荷分散に貢献

オープン・ネットワークの利点

中央管理者がいない

• 全参加者に中立
• 改竄が非常に難しい
• 低コスト

スマートコントラクト

汎用データベースなので、プログラムを置くこともできる

• データベースエントリにプログラムコードを紐づけ
• コードが紐づいたエントリに書き込みがあると、コードが起動される
• コードによるデータベース書き込み
• コードによる書き込み先にさらにコードが紐づいていると実行が連鎖

複雑な自動データベース操作が可能 (dApps、Web3 など)

ブロックチェーン、いいことばっかりだ!!

• 汎用
• 分散: 高耐故障性・負荷分散
• パーミッションレス
• 非中央集権: 改竄が難しい、低コスト
• スマートコントラクトによる自動操作

そんなうまい話はない…

分散は難しい

複数のノードに互いに矛盾する書き込みがあったら、
衝突が起こる。

衝突をどう解消するか?

ブロックチェーンでの衝突

チェーンが分岐してしまう。どちらを選ぶか?

　　　　　　　　　\(︎↗︎\stackrel{B_{n+1}}→ S_{n+1} \stackrel{B_{n+2}}→ S_{n+2} \stackrel{B_{n+3}}→ S_{n+3}\)

\(.. \stackrel{B_{n-1}}→ S_{n-1} \stackrel{B_{n}}→ S_{n}\)

　　　　　　　　　\(↘︎\underset{B'_{n+1}}→ S'_{n+1} \underset{B'_{n+2}}→ S'_{n+2} \underset{B'_{n+3}}→ S'_{n+3}\)

(バージョン管理システムならブランチがあっても良いが…)

分散合意アルゴリズム

分散ノード間の衝突を解決するアルゴリズム。

完璧なアルゴリズムは存在しない[FLP85]が、
Paxos や Raft など実用上問題ないものがある。

基本的にはノード間の多数決を取ることで衝突を解消する

オープンネットワークでの多数決

オープンネットワークでの多数決💦

「Botで票水増したんかも」

オープンネットワークでの多数決問題

クローズドネットワークでの合意形成

参加者が固定されているの多数決は簡単。

オープンネットワークでの合意形成

誰でも参加できるため、成りすましによる 票数水増しにより合意形成の操作と妨害ができてしまう。(Sybil攻撃)

オープンネットワークを諦めれば？

クローズドネットワークなら、普通の分散データベースでよい。

(コンソーシアムブロックチェーンなどもあるが)

Proof of XXX

有限にしか存在しないリソースを投票に要求することで
票数水増しを 不可能にする 難しくする。

Proof of Work

投票するために一定の計算量を要求。

計算リソースを多く持つものには有利だが、地球上の計算能力の総和は有限なので、「成りすまし」にも限界がある。

動的な必要計算量調整

参加するリソース量は時間により変化するので、定期的に必要計算量を調整する

インセンティブ設計

リソース提供者: マイナー、バリデータ

タダでは誰もコストのかかるバリデータになってくれない

正直なバリデータに換金性のあるポイント(トークン)を与える。

• 正直な=データベースに都合の良い行動をした
• トークンはデータベース上で管理

暗号通貨の誕生!![サトシナカモトとBitcoin (2008)]

暗号通貨は非中央集権分散データベースのSybil攻撃への解

Proof of Work ブロックチェーンの動作

Proof of Work ブロックチェーンの動作(概略)

• 送金命令の送り出し (by ユーザー)
• Mempool
• チェーン選択 (by バリデータ)
• ブロック生成 (送金命令+報酬情報) (by バリデータ)
• Proof of Work 計算 (by バリデータ)
• ブロック投稿 (by バリデータ)
• ブロックの承認

送金命令の送り出し (by ユーザー)

ユーザーによる送金命令 \(O\) の作成:

• 送金: 自アカウント \(a\) からトークン量 \(x\) をアカウント \(b\) に送る
• 手数料宣言: \(a\) から \(O\) をブロックに取り込むバリデータへ \(f_O\) 送る
• 偽造対策: アカウント \(a\) のデジタル署名

\(O\) は P2P ノードネットワークに送られ、伝播していく:

Mempool

各ノードに届いた送金命令 \(O\) は Mempool と呼ばれる
データストアにブロックに取り込まれるまで待機する。

オンメモリデータストアなので “MEMory POOL”

チェーン選択(投票) (by バリデータ)

Nakamoto consensus

より長い枝の方が「正当」。他のバリデータもそう行動する。

ブロック生成報酬は、そのブロックが適用された枝でのみ有効。

自分の利益のために、長い枝に新ブロックを作成(=投票)すべき。

　　　　　　　　　\(︎↗︎\stackrel{B_{n+1}}→ S_{n+1} \stackrel{B_{n+2}}→ S_{n+2}\) 　勝ち馬はこちら

\(.. \stackrel{B_{n-1}}→ S_{n-1} \stackrel{B_{n}}→ S_{n}\)

　　　　　　　　　\(↘︎\underset{B'_{n+1}}→ S'_{n+1}\) 　こっちに賭けても損する

ブロックの生成 (by バリデータ)

Mempool にある送金命令集合からリスト \([ O_1, .., O_m ]\) を作る:

条件

• \(O_i\) は過去のブロック \(B_1, .., B_n\) に含まれていない。
• 新しい状態 \[S_{n+1} = [O_i](S_n) = O_m(O_{m-1}(..(O_1(S_n))))\] が不正になってはいけない:
  • 残高が負になってはいけない
  • 規定通りのブロック作成報酬が支払われている

ブロックサイズ

追加条件

ブロックにはサイズ上限がある (Bitcoin では上限 1MB、 \(O\) の平均サイズは 500~600B。)

バリデータは手数料収入 \(\sum_i f_{O_i}\) が最大になるように \([ O_i ]\) を選ぶ (0-1 Knapsack 問題)

• 手数料が低い \(O\) は無視されがち

Proof of Work 計算 (by バリデータ)

入力:

• 前状態 \(S_n\)
• 送金操作のリスト \([O_i]\)
• 現在の Proof of Work 難易度パラメータ

から決まる計算問題を解く:

\[\mathit{Hash_{難易度}}(S_nのハッシュ ~\mathtt{++}~ [O_i] ~\mathtt{++}~ 答) = 0 ~~~~{\small (\mathtt{++}): 文字列連結}\]

答を探すのは総当たり。それなりの時間(=リソース)が必要。
ある値が答かどうかの確認は簡単。

ブロック投稿 (by バリデータ)

\(B_{n+1}\) として

• 前状態 \(S_n\) のハッシュ
• 送金命令列 \([O_i]\)
• Proof of Work 計算の答
• 上記のデータに対するバリデータの電子署名

を作り、ノードネットワークに流す

ネットワークによるブロックの承認

各ノードは受け取った \(B_{n+1}\) が \(S_n\) に続く正当なブロックか検査し、 不正であれば無視し、正当であればチェーンに付け足す:

\[.. → S_{n-2} \stackrel{B_{n-1}}→ S_{n-1} \stackrel{B_{n}}→ S_{n} {\color{red} \stackrel{B_{n+1}}→ S_{n+1}}\]

Nakamoto consensus の安全性

ブロックチェーンへの攻撃

Nakamoto consensus を守った上で、悪意のあるバリデータが悪さをすることができるか

• ノードのバグや送金命令への署名の偽造はないものとする
• 悪さ: 記録の改竄。 \(S_i\) で \(x=A\) だったものを \(x=B\) にする

Double Spending 攻撃

悪意あるバリデータが秘密裏に分岐 \(S'_i\) を作り公表しない:

\(\small　　　　　　　　　\mbox{💎⇨💰😈}\)
\(\small　　　　　　　↗︎\)
\(\small .. \stackrel{B_{n-4}}→ S_{n-4}^💎 \stackrel{B_{n-3}}→ S_{n-3} \stackrel{B_{n-2}}→ S_{n-2} \stackrel{B_{n-1}}→ S_{n-1} \stackrel{B_{n}}→ S_{n}\)
\(\color{gray}\small　　　　↘︎︎\)
\(\color{gray}\small　　　　　️😈 \stackrel{B'_{n-3}}→ S'^💎_{n-3} \stackrel{B'_{n-2}}→ S'^💎_{n-2} \stackrel{B'_{n-1}}→ S'^💎_{n-1}\)

公式チェーン \(B_{n-3}\) で😈が所有するトークン💎を
チェーン外資産💰と交換

Double Spending 攻撃

秘密分岐が公式チェーンより長くなったら分岐を公開する:

\(\small　　　　　　　　　\mbox{💎⇨💰😈}\)
\(\small　　　　　　　↗︎\)
\(\small .. \stackrel{B_{n-4}}→ S_{n-4}^💎 \color{gray} \stackrel{B_{n-3}}→ S_{n-3} \stackrel{B_{n-2}}→ S_{n-2} \stackrel{B_{n-1}}→ S_{n-1} \stackrel{B_{n}}→ S_{n} → ⛔️\)
\(\small　　　　↘︎︎\)
\(\small　　　　　️😈 \stackrel{B'_{n-3}}→ S'^💎_{n-3} \stackrel{B'_{n-2}}→ S'^💎_{n-2} \stackrel{B'_{n-1}}→ S'^💎_{n-1} \stackrel{B'_{n}}→ S'^💎_{n} \stackrel{B'_{n+1}}→ S'^💎_{n+1}→..\)

• 公式の枝はもう育たない。
• \(S_{n-3},..,S_{n}\) は \(S'^💎_{n-3},..,S'^💎_{n}\) に置き換わってしまう
• \(B_{n-3}\)でのトークン使用はなかったことになる
• チェーン外資産💰を盗むことができた

Double Spending の難易度

51%攻撃

ネットワークに参加しているリソースの過半があれば容易(事例): \[悪意ある平均ブロック生成速度 > 正直者の平均生成速度\] 参加リソースが少ないマイナーなブロックチェーンが狙われやすい

改竄されてしまうリスク

リソースの過半を持っていなくても、運が良ければ短期的にブロック生成数を上回ることは可能

が、その確率は追い抜くべき枝の長さが長くなると指数関数的に小さくなっていく:

• Hashパズルの解を見つけるのはポアソン過程と見なし
• 悪意あるバリデータの生成数が正直者の生成数を超える確率を求める

Probablistic finality

状態変更が厳密には確定せず、覆される確率が時間(ブロック)とともに減っていく (⇄ Deterministic finality)

防御方法

投票数の過半数が正直に行動していれば、十分に古い状態は覆されることはない

\[\small .. \stackrel{B_{n-6}}→ S_{n-6} \stackrel{B_{n-5}}→ S_{n-5} \stackrel{B_{n-4}}→ S_{n-4} \stackrel{B_{n-3}}→ S_{n-3} \stackrel{B_{n-2}}→ S_{n-2} \stackrel{B_{n-1}}→ S_{n-1} \stackrel{B_{n}}→ S_{n}\] \[\small　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 ↘︎\stackrel{B'_{n}}→ S'_{n}\]

• 悪意がなくても \(S'_{n}\) のような浅い分岐 は発生しうる。\(S_{n}\)はなかった事になるかもしれない。
• Bitcoin の場合 \(S_{n-6}\) くらいになればまず信用して良いとされている
• 暗号通貨の売却依頼を受けた交換業者は、暗号通貨の自アカウントへの振り込みを確認後、 しばらく待ってブロックが十分古くなってから支払いを行う

Proof of Work と 環境問題、SDGs

オープン・ネットワークの利点❓

中央管理者がいない

• 全参加者に中立
• 改竄が非常に難しい
• 低コスト❓❓❓

Proof of Work (Bitcoin) はエネルギーを喰う

と言ってよく叩かれる。例: ホワイトハウスのレポート

Bitcoin価格の上昇
→ 報酬の換金額も上がる
→ 競争が激しくなる

現在の推定総電気使用量: 140.42 TWh / year

比較サイト

Proof of Stake

Proof of Stake

Sybil攻撃に対する別の投票制限: データベース上の有限の値を使う

所有トークン量(Stake)に比例した投票権

• ブロックチェーン上のデータなので水増し(改竄)できない
• 大きな Stakeholder ほど所有する暗号通貨の価値を毀損する行動はしない
• 所有トークンの一部を保証金として担保に取ることができる
  • 害をなす行為をした場合は没収
• 計算競争がないので、合意形成にエネルギーをほとんど必要としない

Proof of Stake はエネルギーを消費しない

注意: Ethereum は PoS に移行後 0.0026 TWh に減少。

Proof of Stake はエネルギーを消費しない

Proof of Stake はネットワーク維持費をカバーする送金手数料も低くなる:

Bitcoin: 1 ~ 3 USD/Tx

Ethereum: 0.5 ~ 1 USD/Tx

Tezos: 0.008 USD/Tx

(プロトコルのデザインによります。 Ethereum は PoS 移行後も高いままですね…💦)

ꜩ Tezos での Nakamoto PoS consensus

Tezos で過去に使われていた分散合意アルゴリズム: Emmy

• 計算競争はない
• ブロック生成を担当するバリデータの優先度付き集合を事前に決める

(現在 Tezos は deterministic finality アルゴリズムを使用)

ꜩ 優先度付きバリデータによるブロック生成

バリデータの優先度付きリストを作る。
選ばれる確率は保有トークン量に比例:

• 前ブロック生成から \(t\) 秒後、第1位バリデータがブロックを生成できる
• 第1位バリデータが生成しない場合、さらに \(t'\) 秒後に第2位が生成できる
• 第2位バリデータが生成しない場合、さらに \(t'\) 秒後に第3位が生成できる
• …

Proof of Stake での攻撃手法

PoS でも Double spending が可能:

Nothing at stake 攻撃、long range 攻撃

  　　　　　　　　　💰🫲😈 ステークを外部資産に交換
　　　　　　　　　⤴︎
\(→ B^💎_{n-1} → B^💎_{n} → B_{n+1} → ⛔️\)
　　　　　↘︎ 過去のステークを利用して分岐
　　　　😈　\(B'^💎_{n} → B'^💎_{n+1} → B'^💎_{n+2} → ..\) こちらを主流にしてしまう

Proof of Work と異なり、ブロック作成に計算リソースを必要としないので、枝をどんどん作れてしまう。

ꜩ Tezos の攻撃への対処: 裏書き投票

作成したブロックに対し、バリデータが裏書き投票を行う

投票できるバリデータも保有トークン量に比例した確率で選ばれる

枝の長さではなく、総投票数の多い枝が選ばれる:

　　　　　　　　\(︎↗ B_{n+1}^{👍👍👍👍👍} → ..\) こちらが選ばれる

\(.. B_{n-1} → B_{n}\)

　　　　　　👿　\(↘ B'^{👍^👿}_{n+1} → B'^{👍^👿}_{n+2} → ⛔️\) 長いだけではダメ

ꜩ Tezos の攻撃への対処: 保証金

PoW と異なり、ブロック作成に計算リソースは必要ない。

枝の濫造を禁止するため各バリデータは各チェーンレベルで一つのブロックしか提案できないようにする。

違反した場合は罰金を取る:

• バリデータリストに乗るためには保証金を預ける必要がある
• 同じレベルで2度ブロックを作成した場合、保証金を奪われる

ꜩ 報酬

ブロック作成と裏書き投票にインセンティブ報酬を与える

• ほとんどの場合、報酬を求めて、優先度1位のバリデータがブロックを作成
• 投票に揺らぎがあれば、すぐに多い方に票が集中する
  (負けた枝では報酬をもらえない)

ꜩ Probablistic finality

Emmy は Nakamoto consensus の変種: probablistic finality

送金がブロックに取り込まれてから、さらに6ブロックほど待てば、覆される確率はほぼ 0 になる。

ꜩ 51% 攻撃

Proof of Stake ももちろん 51% 攻撃には無力

ブロックチェーン上のトークンの半数以上が悪意あるユーザーに支配されると終了。

• トークン所持の分散具合を監視
• 大口所有者は信頼できるものにする企業バリデータ

ꜩ バリデータ委託

トークンを所有しているが、バリデータになりたくない場合、
トークン保有料を他のバリデータに委託できる

• バリデータ報酬の一部を分けてもらえる
• 委託された分の保証金も預けなければいけないので、バリデータは自己資金に比例した委託しか受けられない
• 大投票力(≧51%)のあるバリデータを作らないように気をつける必要がある

まとめ: ブロックチェーンの基本原理

汎用分散データベース

• 台帳方式、分散環境、オープン・ネットワーク、非中央集権制
• (スマートコントラクト)

オープンネットワークにおける分散合意

• 有限のリソースによる投票数制限
  • Proof of Work: 計算リソース
  • Proof of Stake: 過去のトークン所持量
• ネットワーク維持のためのインセンティブ設計 → 暗号通貨