2019-07-04

Do I need blockchain?

「それで、あなたはそのブロックチェーンやらで何がしたいの？」
当時婚約者だった彼女は自分に聞いた。世間では盛んに非中央集権だ、契約の自動化だと叫ばれるようになってきた時期だった。自分は数年ブロックチェーンの研究をしてきた中でも、耳の痛い質問だった。自分でもはっきりしてないのに、彼女にわかってもらえるはずがなかった。なぜこんな技術を研究しているのだろうか。ずっと頭の中にある問いの一つだ。

遡れば、自分は高校の頃からバンドをやっていて、将来の音楽配信、みたいなものをテーマにして大学を選択した。いわゆる学際学部で、音楽配信システムやら、音楽文化もあるし、そんなことを考えながら緩やかに学生生活を始めた。その中で情報技術ってものは面白いな。その程度の勢いで研究室に所属した。

研究室に所属してから、並行してバンド活動を始めた。バンド活動をしていると、お客さんが数人しかいないバンドでも、ライブを見たら感動するようなバンドがたくさんいた。そんな人たちと酒を飲み明かしながら、売れよう、売れるためには、みたいな話をよくしていた。友人のライブも何本も見に行った。それでも友人たちは解散していったし、その曲は忘れ去られる。自分たちも活動休止したりした。

そんな中で、ひょんなことからブロックチェーンちょっと面白そうだな、と思っていた。完全にただの興味だった。そうこうしているうちに、よく話す講師の方に「授業一コマBitcoinについて話してみないか？」と言われた。そのうち、研究室のボスから、3Dプリントとブロックチェーン、というざっくりしたネタをもらって卒論を書いていた。

バンドだって、3Dプリントだって同じだ、と気付くまで時間はそこまでかからなかった。個人が個人として作った作品の権利はどこまでどう保証したらいいのか。管理機関に預けることが最適解なのか、という問いが浮かび上がってきた。

自分は結局売れないバンドマンとしてバンドマン人生は終えた。だけども、その作品たちは、どこに向かうのだろうか。気に入ってくれてた人たちが、語り継いでくれればそれでいいのかもしれない。でも、ふと思うのは、化石みたいな形で、どこかに埋まっていて、いつの日か再発見されたりとか、そんなことがあったら面白いじゃないか。デジタルな地層、といった具合に、過去に存在したデータの上にどんどん積み重なっていくとか。まさにブロックチェーンだ。

「個人が個人として活動していた記録を残す。」
それがきっと自分がやりたいことの一つの形なんだろうな、と思う。その最適解がブロックチェーンなのか議論はあると思うが、自分は面白いと思うしやってみたい。そんなことを、数年前に問われた時の回答として、妻に話していた。

そんなある日、最近生まれた娘を抱きながら妻が言った
「ブロックチェーン上に出生記録残すサービスあるみたいじゃない。やらないの？」
ブロックチェーンが記録の一形態として、社会に受け入れられるのは、もしかしたら近いかもしれない。

*1:本稿は第2回BASEアライアンス・ユース・アワードに応募しようと思って執筆した文章の供養です。

2019-06-10

BrownieでSmart Contractのテストを書く

ブロックチェーン開発tips

概要

Ethereum上にデプロイされたSmart Contractはデプロイ後にアップデートすることができない。そのため、デプロイ前に十分な動作検証を行う必要がある。動作検証を行うにあたり、pythonでテストを書くことができるpopulusが一般的なフレームワークであったが、開発が停止している。現在pythonでテストを書くことが可能なフレームワークとしてBrownieがある。本稿ではBrownieを用いてSmart Contractのテストを実施する手順を記す。

環境

macOS mojave 10.14.5
Homebrew 2.1.4
- npm 6.9.0
pyenv 1.2.11
- Python 3.6.5
- pip 9.0.3
solc 0.5.9

Brownieのインストール

Brownieの依存ツールとしては、python3、pip、ganache-cliが挙げられている。 ganache-cliはSolidityのフレームワークtruffleのチームが開発している開発しているEthereum RPCクライアントだ。今回はCLIツールを用いる。npmでインストールするので、以下のコマンドでインストールする。

npm install -g ganache-cli

Brownie自体はpipでインストールすることが可能だ。

pip install eth-brownie

インストールされたことを確認する。

chike[~]brownie
Using solc version v0.5.9
Brownie v1.0.0b7 - Python development framework for Ethereum

Usage:  brownie <command> [<args>...] [options <args>]

また、コンパイルにsoldityコンパイラであるsolcが必要なため、brewでインストールする。

brew install solidity

Browineプロジェクトの作成とディレクトリ構成

brownie init projectnameのコマンドでプロジェクトを新規作成できる。

chike[~]brownie init test
Using solc version v0.5.9
Brownie v1.0.0b7 - Python development framework for Ethereum

Brownie environment has been initiated at /Users/chike/test

プロジェクトディレクトリ以下に新規に作成されるディレクトリは以下の構成となる。

chike[~]tree test
test
├── brownie-config.json    // brownieプロジェクトの設定ファイル
├── contracts              // solidity/viperのソースファイル
├── reports                // JSON形式のBrownie GUIでのログファイル
├── scripts                // デプロイや実行に関わるスクリプト
└── tests                  // テストコード

4 directories, 1 file

そのほかにもbrownieでコンパイルを行うとbuildディレクトリが作成され、その中にバイトコードのコントラクトやテストデータが入る。

また、brownieにはテンプレートがいくつか用意されており、以下のコマンドでテンプレートを使った新規作成が行える。

brownie bake token // tokenを扱うテンプレートで新規作成

コンパイルとテストの実行

brownieを使ってコンパイルする際のsolcのバージョンをbrownie-config.jsonの中で指定している。指定されたバージョンのsolcがないとそのバージョンのsolcをインストールしようとする。¹

今回は、solcのバージョンは0.5.9を利用しているので、brownie-config.jsonの当該部分を書き換える。以下は書き換え部分の抜粋。

    "solc":{
        "optimize": true,
        "runs": 200,
        "version": "0.5.9"
    },

プロジェクトディレクトリ直下でbrownie complieのコマンドでcontractsディレクトリにあるソースコードをコンパイルする。今回はbakeしたtokenをコンパイルしてみる。

chike[token]brownie compile
Using solc version v0.5.9
Brownie v1.0.0b7 - Python development framework for Ethereum

Using solc version v0.5.9
Compiling contracts...
Optimizer: Enabled  Runs: 200
 - Token.sol...
 - SafeMath.sol...
Brownie project has been compiled at /Users/chike/Documents/workspace/brownietest/token/build/contracts

次に、brownie testでtestsディレクトリにあるテストが実行される。ひとまずtokenのそのまま実行してみる。

chike[token]brownie test
Using solc version v0.5.9
Brownie v1.0.0b7 - Python development framework for Ethereum

Using solc version v0.5.9
Running 6 tests across 2 modules.

Running /Users/chike/Documents/workspace/brownietest/token/tests/transfer.py - 1 test (1/2)
 ✓ 0 - setup (0.1654s)  
 ✓ 1 - Transfer tokens (0.1567s)  
Completed /Users/chike/Documents/workspace/brownietest/token/tests/transfer.py (0.4863s)

Running /Users/chike/Documents/workspace/brownietest/token/tests/approve_transferFrom.py - 5 tests (2/2)
 ✓ 0 - setup (0.1373s)  
 ⊝ 1 - balance (skipped)
 ✓ 2 - Set approval (0.2117s)  
 ✓ 3 - Transfer tokens with transferFrom (0.2492s)  
 ✓ 4 - transerFrom should revert (0.1418s)  
 ‼ 5 - This test is expected to fail (AttributeError)
Completed /Users/chike/Documents/workspace/brownietest/token/tests/approve_transferFrom.py (1.5656s)

Total runtime: 2.2292s
SUCCESS: All tests passed.

また、特定のテストファイルのテストのみを実行したい場合はbrownie test testfileで実行できる。

テストスクリプトの記述法

brownieはそもそもコントラクトのフレームワークなので、CLIツールとしてインタラクティブシェルがあり、デプロイやトランザクションの発行などの操作が可能になっている。具体的な各操作は公式ドキュメントのCLIの操作を見るのが一番手っ取り早い。

テストスクリプトは全てtestsディレクトリ以下に設置する。設置されたファイルはbrownieにテスト用スクリプトとして見なされるので、何か使い回しの処理をしたいときはscriptsディレクトリに設置し、importするようにする。

まずはbrownieのメソッドを利用可能にするためにfrom brownie import *する。その後、テストを開始する際はsetup関数を最初に実行する仕組みになっているので、コントラクトの初期セットアップなどはsetup関数の中に記述する。その後は各関数がそれぞれ上から順に1ユニットテストとして扱われる。

また、関数名直後にコメントを書き込むことで、テスト実行時にテストユニット名として表示される。下記サンプルと先ほどのテスト結果の項目を見比べれば理解できるだろうか。

以下はbrownieでbakeしたtokenのtestサンプルスクリプトである。ここでは、scriptsディレクトリ内にTokenコントラクトをデプロイするスクリプトが記述されており、それを用いてコントラクトデプロイを行なっている。

#!/usr/bin/python3

from brownie import *
import scripts.token


def setup():
    scripts.token.main()
    global token
    token = Token[0]


def balance(skip=True):
    check.equal(
        token.balanceOf(accounts[0], "1000 ether"),
        "Accounts 0 balance is wrong"
    )


def approve():
    '''Set approval'''
    token.approve(accounts[1], "10 ether", {'from': accounts[0]})
    check.equal(
        token.allowance(accounts[0], accounts[1]),
        "10 ether",
        "Allowance is wrong"
    )
    check.equal(
        token.allowance(accounts[0], accounts[2]),
        0,
        "Allowance is wrong"
    )
    token.approve(accounts[1], "6 ether", {'from': accounts[0]})
    check.equal(
        token.allowance(accounts[0], accounts[1]),
        "6 ether",
        "Allowance is wrong"
    )


def transfer():
    '''Transfer tokens with transferFrom'''
    token.approve(accounts[1], "6 ether", {'from': accounts[0]})
    token.transferFrom(
        accounts[0],
        accounts[2],
        "5 ether",
        {'from': accounts[1]}
    )
    check.equal(
        token.balanceOf(accounts[2]),
        "5 ether",
        "Accounts 2 balance is wrong"
    )
    check.equal(
        token.balanceOf(accounts[1]),
        0,
        "Accounts 1 balance is wrong"
    )
    check.equal(
        token.balanceOf(accounts[0]),
        "995 ether",
        "Accounts 0 balance is wrong"
    )
    check.equal(
        token.allowance(accounts[0], accounts[1]),
        "1 ether",
        "Allowance is wrong"
    )


def revert():
    '''transerFrom should revert'''
    check.reverts(
        token.transferFrom,
        (accounts[0], accounts[3], "10 ether", {'from': accounts[1]})
    )
    check.reverts(
        token.transferFrom,
        (accounts[0], accounts[2], "1 ether", {'from': accounts[0]})
    )


def unfinished(pending=True):
    '''This test is expected to fail'''
    token.secretFunction(accounts[1], "10 ether")

skipとpending

各関数で引数skipを設定し、skipがTrueの時はそのテストはスキップされる。また、引数pendingを設定し、Trueにした場合、そのテストは実行されるが、失敗してもエラーの詳細は表示されない。

アカウント操作

テスト実行のたびに、それぞれ100Ether持ったアカウントが10個初期値として生成される。各accountオブジェクトは変数accounts内にリストとして保持されている。

accountsオブジェクトのメソッドとしては、保有Ether量を出力するbalance()、コントラクトのデプロイを行うdeploy()、送金を行うtransfer()などが用意されている。

コントラクトのデプロイ・操作

contract以下に記述された各コントラクトファイルは、テスト実行時にコンパイルされ、正常にコンパイルされればコントラクト名でコントラクトのオブジェクトを参照できる。このコントラクトオブジェクトをアカウントオブジェクトのdeploy()メソッドを用いることで、ローカルテスト環境にデプロイできる。deploy()メソッドでは第1引数にコントラクトオブジェクト、第2引数以降にコントラクトコンストラクタの引数を指定する。

t = accounts[0].deploy(Token, "Test Token", "TST", 18, "1000 ether")

また、ここでは用いていないが、最終引数には、トランザクションの付与情報をdict形式で記述することができる。ここで指定できる付与情報は、web3のeth.send.Transactionのパラメータを指定することができる。例えばコントラクトデプロイ時に一定金額デポジットを要求するような場合、ここでvalueを指定することで送金しながらのデプロイトランザクションの発行をテストできる。

デプロイされたコントラクトは、ここで指定したコントラクトオブジェクトにリスト的に格納されている。そのため、テスト中に最初にデプロイしたコントラクトはToken[0]の形でそのオブジェクトにアクセスできる。

コントラクトの各関数は、デプロイされたコントラクトオブジェクトのメソッドとしてアクセスすることができる。

まとめ

自分は普段ずっとpythonを主な使用言語にしているので、pythonでこうしたテストがかけるのは非常にありがたい。また、アップデート困難なブロックチェーン上のアプリケーションをテストするのは非常に重要である。一方で、開発者の想定外/テスト外のバグは完全に潰すことはほぼ不可能なので、そもそも根本的にブロックチェーンを改善する必要があるが、それはまた別の話だろう。

自分の環境では別バージョンsolcをmakeする際にエラーが発生したのだが、本稿の主眼ではないので追求しなかった。↩

2018-12-02

【論文メモ】A survey of DHT security techniques

修論のためにDHTのセキュリティサーベイの論文を読んだのでポイントのメモ。

A survey of DHT security techniques
- Journal ACM Computing Surveys
  - Volume 43 Issue 2, January 2011
- https://dl.acm.org/citation.cfm?id=1883615
  - Guido Urdaneta(VU University)
  - Guillaume Pierre (VU University)
  - Maarten Van Steen (VU University)

Sybil Attack

複数のidentityを攻撃者が作成する
- DHTの動作自体を妨げるものではない
- プロトコルを騙ることによって、冗長性による仕組みを覆す
DHTのセキュリティは$f$ノードが安全であることで保証する
- 攻撃者が物理的なidentityとは別に仮想的に複数identityを作成することで、$f$ノード以上のidentityをOverlay上に配置し、安全性を破壊する

対抗策

Centralized Certification
- 　前提
  - 　参加する全てのノードに信頼される認証局が必要
  - 　認証局はSybil Attackを正しく特定できる
- 　実用例
  - 　Skype
  - 　信頼できるブローカ同士のWebホスティング
- 　デメリット
  - 　認証局の運営コスト
  - 　攻撃者に対して攻撃対象が明らか
    - 　オフラインCAはそれを緩和するが、完璧ではない
  - 　証明書の失効などの運用コスト
Distributed Registration
- CAを複数配置する
- Sybil Attackを完全に特定はできないが、CCの問題を緩和する
- 分散的なアプローチは、各ノードで全体を把握しないので、攻撃の一部しか見れない
  - DHT自体と同様
Physical Network Characteristics
- ノードの物理特性は騙ることは困難であることを利用
  - Sybil Attackは単体のコンピュータまたは似た特性を持つコンピュータで行われる
- ノードを特定し、ネットワークの特徴からそれらを分類する試み
  - この手法は、参加者にとって透明性があり、採用する障壁は低い
  - しかし、信頼できるNetwork監視基盤が必要である
    - CCアプローチと同様の課題を抱える
  - また、攻撃者のノードはその位置情報を騙ることなどが可能
  - ネットワーク上の位置をノードの特定に用いる場合、本手法は困難になる
Social Networks
- 限られたSybil Attackに有効
- 各ノードは小さな認証局のように動く
- 欠点
  - Social Networkに各ノードは登録されてなければならない
    - メッセージングなどで実現可能
    - ファイル共有アプリなどで用いられる
  - オフラインでの対称鍵交換を行わなければならない
Computational Puzzles
- 善良なノードは他のノードに計算コストをかけることを要求する
  - 数学的パズルを解くことを要求
  - 物理的な攻撃者のノードはidentityを複数作るために計算擦ろをかけなければならない
  - 全てのidentityが即座に検証されていればこの手法は有効
    - それはノードが自由に離脱・参加する大規模システムでは現実的には不可能
    - そのため、本手法では定期的な全ノードの検証を行う必要がある
  - 欠点
    - 善良なノードも計算コストをかけ続ける必要がある
    - またパズルの難易度も、他の作業ができるキャパシティを残して多くの善良なノードが解くことができる難易度でなければならない
      - 実際のP2Pシステムでは各ノードのCPUパワーはばらつきがある
Game Theory
- 全ノードは合理的である推測の元成り立つ
- しかし実際には各ノードは独立しておらず、攻撃者ノード軍は共謀する
  - 特定の利益を得るために合理的でない選択をすることがある
- 面白いが、現実的な対抗策になりうるかは要検討

Eclipse Attack

Routing Tableをhijackすることでネットワークを分断し、DHTの正常動作を阻害する

対抗策

Routing Tableで使われるノードのIDに制約を加える
- Chordで採用されている
- ノードIDがランダムかつ固定で、攻撃者ノードがID空間上に分散していれば有効
  - これを実現するもっとも簡単な方法は認証局を作ること
  - またはchurn状態で参加したノードにランダムなIDを割り当てる
- 一方でID割り当てのランダム化は隣接ノードの選択とパフォーマンス効率化を妨げる
  - Pastryで用いられている効率化が妨げられる
    - routing tableに対する弱い制約
    - 結果として多くのノードがIDの制約を満たし、ネットワークの計測が最適な隣接ノードの選択に使われる
- 制約を設けることで、攻撃者ノードはrouting tableにどのように配置されるかを容易に考えられる
  - Pastryでは15%の攻撃者ノードによって80%のroutingエントリが汚染される
Pastry likeなrouting tableを持つDHTに対してEclipse Attackは考慮する必要がある
- 簡単な対抗策は冗長routingを用いること
他の手法としては、冗長routingとIDへの制約を組み合わせる
- 最適化されたrouting tableは段階的に汚染される
- そこで制約を持つtableを使う
  - 汚染されたtableを用いることと、複雑な障害検知手法によるオバーヘッドが存在する
他の対策としては、ノードあたりのincomingとoutgoingリンクの数に制約をつける
- 攻撃者ノードの次数は善良なノードよりも大きいことを利用
- 分散的な手法が存在するが、攻撃が行われていなくても、lookupの時間が増加する
Eclipse　Attackの対抗策にはパフォーマンスと複雑性のトレードオフがある
- 対抗策はDHT本来のオペレーション外の作業を必要とする

Routing and Storage Attacks

正規のroutingとは異なるroutingを行ったり、異なるdataを返す攻撃

対抗策

基本的に冗長Sotageと冗長Routingで対応する
- データのレプリケーションによって実現
- 別の手法としては、消失訂正を用いる
  - レプリケーションよりストレージと帯域の点で優位
  - 様々なchurnの度合いに対応するためには、帯域は変わらない
    - 訂正の複雑性を増す、悪意のあるノードや、更新可能データについては考慮されていない
レプリケーション手法
1. ID空間上で近接するノードにレプリカを配置する
2. ID空間上に広がってレプリカを配置する
  - ランダムに再配置することで実現
3. 1と2を併用する
  - ランダムに配置して、その近接ノードにも配置する
1の優位点は有効なレプリケーションの度合いを維持し、一貫性を保持するのが容易
- しかし攻撃者ノードがID空間上で分散していることが条件
  - 特定箇所に攻撃者ノードが集中すると、特定箇所内でレプリカをコントロールすることが容易になってしまう
- その点で2は優位
  - DHTでのID空間上の配置手法はPublicなので、1では特定のkey周辺を攻撃対象にすることが可能
  - したがって冗長化のみではStorage Attackに対しての対策としては不十分
    - ノードの配置を選択することが困難であることが条件
レスポンスが正しいかどうかはあまり意識されていない
- それはアプリケーションレベルで解決できる問題
  - valueのhashをkeyにすることで、レスポンスがkeyに対するものか検証可能
- 自分の持つデータのみで検証ができることがポイント
Read-onlyで自分で検証できることがもっとも好まれるケースは、レプリカが正しいかの検証
- それにより、冗長的なroutingを用いず正しいデータが得られる可能性が増える
- レスポンスの検証失敗すれば、複数レプリカとメタデータを取得すれば、アプリレベルで解決できる
  - バージョンがもっとも高いものを選択する
  - 多数決
特定のkeyの担当への到達可能性を担保するには冗長routingを用いる
- 冗長RoutingはMultiple PathsかMultiple Wide Pathsを用いる
  - Multiple Pathsはレプリケーション手法1、Multiple Wide Pathsはレプリケーション手法2に適している

結論

DHTへ攻撃としては、主にSybil Attack、Eclipse Attack、Routing and Storage Attacksが挙げられる
対抗策として、ノードIDの安全な割り当て、全体参加者に対して攻撃者ノードの割合を低くする、攻撃者ノードがID空間上で分散するようにする、正しいレプリカへの到達可能性を確保するroutingメカニズムが挙げられる。
- こうした対抗策の提案はそれぞれ異なる前提に基づいている
- アプリにとって最適な対抗策は、その前提を何を持つかによって組み合わせ、考える必要がある

感想

結構昔からこういった分散システムで計算コストを掛けさせることで守るというモデルがあることは、新たな発見だった*1。またそのモデルと、ゲーム理論的モデルでは、攻撃者は攻撃をして利益を挙げるために行動するので、合理的でない攻撃をするということが起こりうる、というのは先述出した論文に近いところがあるので、その辺は精査してみたい。

*1:まぁPoWとか別にBlockchain特有のものではないので当然といえば当然だが

2018-08-30

それ、Googleにやらせる？

雑記

先日テレビを眺めていたらGoogleアシスタントのCMが流れてきた。

www.youtube.com

いろんなことがAI*1とかで自動化できるようになってきたし、人間がやる必要のないことはどんどんこういうエージェントに任せたらいいと思う。

そこで、「宿題は自分でやろう」と出てきたとき、本当にそうか？と思った。

自分でやることに意味がある、確かにそうだ。自分で頑張って論文とかレポート書くから、文章力も上がるし、頭の中の整理もされていく。プログラムも自分で組むから、その詳細な仕組みもわかるし、本当にどう動作して、何ができるかわかる。宿題ってなんなんだろうか、夏休みの宿題、自分も昔夏休み終盤になって必死こいてやったり、やらずに未提出のまま教師に怒られたこともある。

その一方でGoogleにできる宿題なんてやる必要あるのか、とも思う。漢字ドリルや、計算ドリルをガリガリやった思い出はあるが、この歳になって文章を書くときはほとんどパソコンで書くし*2、ちょっとした計算もすぐに電卓を開く、英語の文法チェックはGramally様様だ。本質はきっと宿題をやること、ではなくその解法や、漢字の意味を理解することだし、それを学ぶための反復練習としての漢字ドリルや計算ドリルなんだろうな、とは思う。

効率よく学ぶことなんてできないし、結局最後はプログラムだってなんだって自分で考えて書く、ということに意味がある。Googleにできる宿題は淘汰されろ、頭を使うことをしっかりやれ、砂浜でどうやったら崩れない山を作れるか、それに精を出したほうが楽しいし、学びじゃないだろうか？

なんて思ってはいるが、こう応用やらやりたいことベースで学問をつまみ食いをする大学*3にいると、そういう反復練習みたいなものを課せられて基礎ができていることへの羨ましさもある。砂山を崩さないために円錐のバランスやら、そういうことがわかっていた方が結局最後応用を積み上げていくときにも崩れないことが裏打ちされた状態で組み上げることができるんじゃないだろうか？

学びを押し付けるような真似はしたくないし、自分のやりたいことベースでなんでもやればいいけど、基礎は大事、そんなことは言われなくてもわかっていることが前提なのだ。宿題はGoogleにやらせたって構わない、だけどそれがなぜその結果になるか、抽象化された概念ぐらいはわかっていないと、足元を掬われる。結局基礎もおろそかにして応用ばっか走る、そんなことをしているとそもそも根底がぐちゃぐちゃなことに気づかないままになるんじゃなかろうか。どこかの分散台帳界隈でただひたすらに夢見た応用を叫ぶみたいに。

*1:バズワードだがあえて使う

*2:手で何か書こうとして全然漢字が出てこないことはしばしば

*3:SFCの理念は大好きだ

2018-08-20

【論文】Information Propagation in the Bitcoin Network

論文ブロックチェーン

読んだ論文をまとめる。

論文は

Information propagation in the Bitcoin network - IEEE Conference Publication

発表スライドは以下

https://www.tik.ee.ethz.ch/file/0bc1493ba049fe69dbafccef4220c666/presentation.pdf

Information propagation in the Bitcoin network
- IEEE P2P 2013
著者
- Christian Decke ETH Zurich
- Roger Wattenhofer Microsoft Research/ETH Zurich

概要

Bitcoinにおけるブロック・トランザクション伝播の分析・モデル化
電波遅延におけるブロックチェーンフォークへの影響分析
伝播を早めるプロトコルの改善提案

Bitcoinネットワークでの情報伝播

BItcoinネットワークは均一なノードによるネットワーク
- それぞれのノードは協働することはなく、TXの検証に必要な完全な複製を持つ*1
- それぞれのノードは独立しているので、ノード間の信頼は最小となる
ネットワークトポロジはランダムグラフ
- ノードが参加すると、幾つかのDNSに問い合わせを行う
- DNSは現在ネットワークに参加する幾つかのbootstrapノードを返す
- ネットワークに参加すると、ノードは他ノードに隣接ノードを尋ねる
- ネットワークからの離脱の表明手段はない
  - ノードの隣接アドレスセットから数時間で削除される
- ノードはそれぞれのコネクションを持つ
  - 内向きのコネクションは閉じないので、実際にはコネクションの数は $p$ より多くなる
  - Bitcoindではデフォルトは $p = 8$ で、平均して32のコネクション
- ネットワークの分断の積極的検知はない
  - マイニングパワー総量の監視によって推測は可能
台帳の同期にはtxメッセージとblockメッセージを用いる
- ブロック/TXをBlock/txメッセージによって受け取ると、検証を行ってから隣接ノードにinvメッセージを送る
- invメッセージを受け、当該ブロック/TXを持っていなければgetdataメッセージを返す

メッセージのやりとり論文本文より

それぞれのメッセージングで伝播遅延が発生する
- 遅延はメッセージの転送と、ブロック/TXの検証の組み合わせである
  - TXの検証はディスクへのランダムアクセスが必要*2
$i_{i,j}$ をブロック/TX $i$ が生成され、広告されてからノード $j$ が受信するまでの時間とする
伝播は2つのフェーズに分かれる
- 多くのノードがinvメッセージを受け取り、持っていないデータを収集するフェーズ
- 多くのノードが持っているデータのinvメッセージを受け取り、集束するフェーズ
180000〜190000ブロックの受信した時間とブロックのタイムスタンプを収集
- 中央値は6.5秒で、平均して12.6秒で受信する
- ロングテールになり、40秒後には5%のノードがまだ受信していない

論文本文より

送信するデータサイズは、20kBまでは遅延に深く影響する
- 96%のTXは1kB未満
- ブロックのほとんどは20kB以上で過半数が知るまでに80msかかる
ネットワークへの侵食
- ネットワーク上のノードを $V$ 、エッジを $E$ とし、ネットワークを $G = (V,E)$ で表す
- ブロック高 $h$ を持つネットワークの一部のノード群を $P_h \subset V$ とする
- のブロックを見つけ、それを持つノード群はとなる
  - $b$ が見つかり、他のブロックが見つからなければ、ノードは $P_h$ を離脱し、 $P_h$ が空になるまで $P_{h+1,b}$ に参加する
- が見つかった時、が発生する
  - それぞれ $b'$ と $b$ を受信することで、ブロックチェーンのフォークを検知する
- ノードはどちらかを選択し、もう一方の伝播を止める
  - これはTXでも同様の動作をする
- トランザクションの場合、伝播を止めることはネットワーク上での検証コストとフォークさせる攻撃とのトレードオフとなる
- ブロックの場合、任意の値を持つブロックを生成することは困難なため、攻撃になり得ない

ブロックチェーンのフォーク

フォークはネットワークの一部によって観測される
- NATやFirewallの中などのノードへは到達できない可能性が高いので、全てのフォークは観測できない
180000〜190000ブロックまでを観測した結果、169回のフォークが発生し、発生頻度は1.69%となった
フォークのモデル化*3
- PoWはブロックの発見をランダムな独立事象にする
- 伝播によるブロックチェーンのフォークの２要素
  1. ブロックの発見確率
    - 10分に一回ブロックが発見されるので、1秒間にブロックが発見される確率は以下
    - $P_b = Pr[X_b \lt t+ 1 \mid X_b \geq t] \approx 1/600$
  2. ネットワークの一部による競合ブロックの発見
    - ブロックチェーンのフォークはが伝播している時にが見つかることで発生する
      - $b'$ は $b$ を知らないノードによってのみ発見される
    - $t_j$ を $b$ が発見されてからノード $j$ が存在を知るまでの時間とする
    - $I_j(t)$ を $j$ が $t$ に $b$ を知っているかどうかの判定関数とする
    - をまでに全てのノードが知るとすると
      - $I_j(t) = \begin{cases} 0\ t_j \gt t \\ 1\ t_j \le t \end{cases}$
      - $I(t) = \sum_{j \in V} I_j(t)$
    - 知っているノードの割合は
      - $f(t) = \mathbb{E}[I(t)] \cdot n^{-1}$
    - 以上よりフォークの確率は
      - $Pr[F \le 1] = 1 - (1 - P_b)^{\int_\bullet^ \infty(1-f(t))dt}$
- $P_b$ と $I_j$ はネットワーク上の計算パワーとネットワークのトポロジに影響を受ける
- 180000〜190000ブロックの計測を元にした分析
  - ブロックの発見確率はPoWによってポアゾン事象となる
  - 確率分布を元にすると程度
    - $1/\lambda = 633.68$ であり、おおよそ600に近似されている
    - 計算パワーが平均10分に1回見つかる調整よりも少し多く投入されているためのズレ
    - これを元に先の式を計算すると平均11.37秒でブロックが伝播する
  - 11.37秒で伝播するということは、伝播する間に費やされる計算パワーは無駄となる
  - $1 - 11.37 / 633.68 = 98.20%$ なので、実質49.1%の有効な計算パワーを費やすことで攻撃が可能となる

伝播を速める施作

伝播を速める手法として提案するのは3つ
1. 検証の最小化
  - ブロックの検証作業は以下の二つに分割できる
    - difficultyの検証
    - トランザクションの検証
  - difficultyの検証が終わったら即座に隣接ノードにinvメッセージを出す
  - 同じdifficultyを持つブロックの生成は困難なため、DoSのリスクを高めることはない
2. ブロック伝播のパイプライン化
  - invメッセージを受け取ったらすぐに転送する
3. 接続性の増加
  - 一つのノードのコネクション数を増やす

論文本文より

計測結果
- 200000〜210000ブロックで改善を行った上で計測を行った
- フォークの頻度は0.78%となった
- 最も影響したのは接続性の増加　 * 帯域はおおよそ100MB/s必要となった

結論

ネットワーク上での伝播の分析を行った
モデル化と計測を行い、モデルの検証を行った
ネットワーク上でフォークを解決することは台帳の複製の非一貫性の解決に重要
しかしイクリプスされると多くのノードは検知できない
幾つかの伝播を促進する施作を提案し、計測した
それぞれは短期的な対策であり、スケーラブルな長期的な解決策を見つける必要がある

感想

結構早めの段階(2013年)に出た論文でネットワークの分析を行ったということで、かなり引用されている論文。やはり、先日の記事でも触れたようにネットワークへの前提を持たないことで伝播がフォークへ影響しており、興味深かった。伝播中に費やされたコンピューティングパワーは浪費になる、というのも面白く、例えば攻撃者としては伝播をわざと遅らせるなどする攻撃もできそうだ。この論文を根っことしてネットワークへの攻撃や分析の論文が多数出ているので、その辺を追っていく。

*1:全てフルノードであることを想定している

*2:おそらくUTXOの探索のことを言っている

*3:ここはうまく読めていないので数式などは暫定で記述する

2018-08-18

進化のガバナンスとレイヤー構造

ブロックチェーン

先日*1大学の授業のTAをしてGinocoの森川さんの話を聞く機会があった。その時に以下のレイヤー構造を見せられたのだが、なんだか違和感があったその原因が最近つかめてきたのでその話。

magazine.ginco.io

ブロックチェーンとはなんだろうか

という定義をまずはっきりさせないといけない。自分としては少なくとも

ハッシュのチェーン構造を持ったブロックというデータ構造
そのブロックのフォークを解決するための分散コンセンサスプロトコル

というものが、ブロックチェーンを構成する要素だと思っている*2。

なので森川さんの言うLayer 1.0まで、ということになるだろうか。ブロックの中にトランザクションとして何が入るか、というのはブロックチェーンを用いたどんなアプリケーションを構築するか、に依存する。Bitcoinでは通貨の所有権利の移転だし、Ethereumであればアプリケーション(DApps)だ。

一番違和感を感じるところ

機能拡張・汎用性向上領域、というところに一番違和感を感じた。これはおそらくEthereumをベースに考案されたレイヤー構造であることに原因がある気がする。

EthereumではProof-of-Stakeや、スループット向上のための分散処理ShardingをEthereum上のコントラクトとして実装を進めている。ちょっと待ってくれ、ブロックチェーン上でアプリケーションを実装できるプラットフォームのアップデートをそのプラットフォーム上で動くアプロケーションとして実装する、というのはなんだが倒錯しているような気がする。セルフホスティングみたいな文脈としてはあるのかもしれない。

ここで森川さんはそうした状況を受けてか、こう述べている。

Layer1.0〜1.5の階層で定義された基幹システムを大きく変えてしまっては、別のシステム体系になってしまいます。2017年に起きたビットコインのハードフォークも、スケーラビリティ問題をLayer1.0まで遡ってブロックサイズを変更することで発生したものです。

ここが一番の問題だ。Ethereumもまだまだ実験的なシステムであり、その下層のプロトコルは完全に決められたものではない。そこでハードフォークを起こしてアップデートするのが問題だ、というのは、Ethereumなどの既存のブロックチェーン上でアプリケーションを作ろうとする人の意見だなぁ、と思う。

進化のガバナンス

ブロックチェーンは、ネットワーク全体で同期していることを前提として動作する。つまり、全世界が同じルールに則っていることを前提としているため、一部で新たなプロトコル、データ構造の変更などを行うと、ブロックチェーンのハードフォークをおこなさなければならない、という状況に陥る。このブロックチェーンの課題が自分が感じた違和感の根本原因であるということに最近気づいた。

ブロックチェーンをレイヤー構造化し、整理を行おうという試みはいくつかある。だが、未だブロックチェーンは黎明期で、根本的に成し遂げようとしていることも成し遂げられていないのではないか、ということは前回の記事で言及した。BitcoinやEthereumは現状そこそこのサイズへネットワークがスケールしたため運用されているものの、実験システムの域は出ることはない。そこで、現状の下層を壊しに行き、アップデートを試みなければ、いつまでも下層のパフォーマンスに引きずられ実用への道は遠いのではないだろうか。

自分はブロックチェーン技術自体のアップデートを志向して研究をしているが、森川さんはおそらくその上に乗るアプリケーションを志向している。そうなると現状の(Ethereum)の整理としては非常によくまとまっているとは思うのだが、そこはなぜそのレイヤーで基盤の部分のテコ入れをやるのか、というのがしっくりこなくなる。どちらが正義、ということではなくて、どちらもこの技術のアップデートには必要なものだと思う。勝手ながら、同い年であることもあり、お互い頑張ろう、という気分にさせてくれた気づきだった。

*1:とは言ってもだいぶ前だが

*2:ここが違和感の根本的原因のかもしれない。

2018-08-16

改ざん困難な台帳とは

ブロックチェーン

研究を進めるうちに少し見失ってきたので、雑記的にちょっとまとめてみる。

ブロックチェーンは改ざん困難な台帳

みたいな言説をよく目にしますよね。改ざん不可能ってなんでしょうか。雰囲気でブロックチェーンをやっているのでわからなくなってきたので、ざっとよくわからないということを説明してみる。

ブロックチェーンの動作

まずブロックチェーンの動作を考えてみる。ここではPoWベースのものを想定してみる。正直PoWベースでないブロックチェーンにはあまり新しさを感じないのだが、その話はまた別途。

基本的な動作は以下だと考えている*1。

誰でも検証可能なトランザクション
検証済みトランザクションをまとめたものをブロックとする *ブロックには直前のブロックのハッシュ値が含まれる
- それゆえ過去のブロック(に含まれるトランザクション)を書き換えると、最新のものまで全てつじつまが合うように書き換える必要がある
- ブロックのハッシュ値はネットワーク上で共有された目標値以下になる必要がある
  - それゆえ一つのブロックを作るにはブロックのハッシュ値が目標値以下になるノンスを見つける必要がある
    - この作業はノンスを変えながらハッシュ値を全探索する以外の方法はないので計算パワーが必要となる
ネットワーク上で最も累積difficultyが高くなる（＝計算パワーを投入された)ブロックが正しいとみなす
- 善良なノード*2たちは、典型的には累積difficultyが現在最も高いブロックに続くようにブロックを作る
- 改ざんを試みる攻撃者は、善良なノードの計算パワー < 攻撃者の計算パワーでなければ、累積difficultyを自分のフォークしたチェーンの方が大きくすることは困難
- つまり改ざんを他のノードたちに認めさせることは困難 = 改ざん困難

なるほどネットワークの全ての善良なノードたちより大きな計算パワーを持つのは難しそうだ、そんな攻撃してもペイしないだろう。というのがブロックチェーンの安全性として語られているように思う。

どこに正しいチェーンってあるんですか？

さてここで考えてみよう。改ざん困難、書き換えるのが難しい、ということだが、そうだろうか。例えば、あるノードへ攻撃者が侵入して、ノードの持つDBを書き換えたとする。改ざんできていないだろうか。いやいやネットワークからブロックが流れてきてすぐ正規のチェーンへと修正できるはずですよ、と言うだろう。

ではネットワークってそんなに単純なものなのだろうか。Eclipse攻撃へ脆弱だ、という話は前から議論されている。ネットワークを分断することで、正しいチェーンへの同期を阻害することは理論上可能だ。繋がったPeerのDBが改ざんされていないかどうかなんて自分からは知りようがない。パブリックな非構造Peer-to-Peerネットワークにおいて、ネットワークに前提を置かずに同期すればいいなんていい加減だなぁ、と個人的には思う。

さらに言えば、最も計算パワーが費やされたブロックを正しいとする、という仕組みだが、計算パワーに（理論上は）上限はないので、新たに計算パワーが大量に費やされたブロックを受信する可能性はいつまでも無くならない。いやいや十二分に大きいネットワークであれば現実的ではない計算パワーを投入しなければならないんですよ、と言うかもしれない。過去のネットワーク全体の計算パワーの2倍以上に計算パワーが短期間で投入されている事実を鑑みれば*3、過去の時点においてより強大な計算パワーを投入することは可能であったということだ。しかも、こういったことを考えているとネットワークが十分に拡大しなければ改ざん耐性を持ってるとは言えない。

もっと言おう。過去の時点において計算パワーの50%に支持されていたブロックに対して、現在の計算パワーの何%がそれに当たるだろうか。また、過去の時点以上の計算パワーを投入して新規にその時点のブロックを作ることは容易なのではないだろうか。いやいやタイムスタンプというものがありまして、それで一定時間以内のものしか受け付けないんですよ、と言うかもしれない。P2Pで時刻ほど信頼できないものはない。ブロックのタイムスタンプなんて書き換えてからブロードキャストすればいい話だ。

そう思うと、ネットワーク上に合意された正しいチェーンというのはどこに存在するのだろうか。いつでもひっくり返る可能性があり、自らのDBや、ネットワークへの前提条件もなく、改ざん困難、と言うのはどういうことだろうか。正しい台帳、というものがどこにあるのか、自分の中でいまいちしっくりこなくなってきてしまった今日この頃。

推測する前提条件

ということでかなりいきなり

ネットワーク上の計算パワーの50%以上が善良なノードに維持されていれば改ざんが困難

というのは結構いろんな条件を無視している気がする。

少なくとも

有限時間内にネットワークを通じて善良なノードに全てのブロック/トランザクションは到達する
ネットワーク上の計算パワーは常にその攻撃にかかるコストがペイしない程度に投入されている

という条件があると自分は考えている*4。

しかしこの二つの条件は、パブリックな非構造P2Pネットワークで常に実現可能なことだろうか。答えはおそらくNOではないだろうか。この辺の話をしっかり整理して改ざん困難、ということを説明してくれる人がいたら泣いて喜びます。

こうP2Pでの改ざん困難性や同期、といったことを考えてるとState Machine Replicationとかそういう話な気がしてきた。そういった方面から分析した論文をしっかり漁ってみようと思う。

*1:ここに対するツッコミを歓迎します

*2:正確には善良なマイナー

*3:統計をみると2倍なんてものではないことがわかる https://www.blockchain.com/ja/charts/hash-rate?timespan=all

*4:精査していないので今度精査して記事を書いてみたい。

chike0905の日記

何者かになりたい