この投稿はDMM.com #2 Advent Calendar 2017の7日目の記事です。
仮想通貨もとい、暗号通貨が世間で騒がれている昨今、様々な通貨や仕組みが生まれてきています。仮想通貨と認識されているものはおおよそブロックチェーンを土台にした作りになっているのですが、とはいえ各々のアルゴリズムや内部構造は大きく異なっています。本稿では代表的な暗号通貨のプラットフォームである、BitcoinとEthereumがどのように違うのかについて解説します。
ブロックの生成速度
1つのブロックを生成する速度はBitcoinは約10分、Ethereumは約15秒です。Ethereumは生成速度が速い分、トランザクションの承認時間が早いメリットがあります。しかしながら承認時間を早めるためにトレードオフになってしまっているデメリットがあります。
ブロックの生成速度を早めると、同時にマイニングに成功する確率が高くなるため、チェーンの分岐が起きやすくなります。分岐したところで最終的にはどれか一つのチェーンを選ばなければならないので、ネットワークの計算量を無駄にすることになってしまいます。また、マイニングしたブロックはすぐにネットワークに伝播し始めます。そしてすぐに次のブロックをマイニングする作業に取り掛かることで、マイニングに成功した人はさらにマイニングに成功する確率が上がります。これを繰り返すとマイニングの寡占化が起きやすくなってしまいます。
この問題への対処として、EthereumはGHOSTプロトコルを採用しています。これにより、分岐が起きたとしても一番計算量をかけられた（＝ブロックがマイニングされて後につけられた）チェーンを採用します。Bitcoinの場合は一番長い歴史を持つチェーンを採用するのですが、Ethereumは最も重たいチェーンを採用します。重たいチェーンとは採用されなかったブロックが一番多くぶら下がっているチェーンのことです。さらにその採用されなかったブロックに対しても報酬を与えることによって、マイニングの寡占化を防ぐ狙いもあります。
下の図はA0の後続でA1とB1のブロックが生成された後にどのようにチェーンが採用されるかを表しています。A2が生まれるとAのチェーンはブロックの重さが2です。B2が生成される前に、A1, B1と同じくA0に続くC1ブロックが、B2を生成しているノードに遅れて伝播してきました。B2のブロックがC1を採用されなかったブロックとして取り込むため、Bのチェーンは重さが3となり、一番重いチェーンとして採用されます。
マイニング方式
EthereumもBitcoinと同様にPoW(Proof of Work)を用います。Bitcoinの場合はブロック生成に必要な情報に任意の値を組み合わせ、特定の条件になるまで任意の値を変更しながら計算を続けます。ただ、この計算方式はSHA-256ハッシュ関数を使ったものなので、専用マシンを使うことでさらに効率よくマイニングが可能になりました。現実問題、すでにBitcoinは専用マシンがないとマイニングができないものになってしまいました。
EthereumはEthashと呼ばれるアルゴリズムを使います。このアルゴリズムによって、擬似的なランダムハッシュを作成し、さらにそこからとても大きな有向非巡回グラフのデータ（DAG）を作成します。この1GBを超えたデータからランダムにデータを取得したものにハッシュ関数を適用し、特定の条件になるまで任意の値を変更しながら計算を続けます。このデータは一定期間で作り直されるので、大きなメモリと作り直すための計算が必要となり、専用マシンでは容易にマイニングが出来ない、または専用マシンを作るメリットが薄いと思わせることで、マイニングの寡占化を防いでいます。
State TreeとStrage Tree
Bitcoinのブロックヘッダの内部構造は以下のようになっています。
Ethereumのブロックヘッダの内部構造は以下です。
細かいパラメータは今回説明を除外します。
現在のブロックに以前のブロックを表すhash(prev hash)が入っていてブロックが繋がっていくという仕組みは一緒です。ただし、Ethereumの場合はブロックヘッダにState Treeのrootの値が入っています。State Tree, Storage TreeこそがBitcoinにはなく、Ethereumに存在するデータ構造です。
State Tree, Storage Treeはなんのために必要なのか。EthereumはBitcoinと違って通貨をやり取りするだけではなく、様々なプログラムを動かすことができます。プログラムのことをスマートコントラクトと呼びます。そのプログラムは別の通貨アプリの実装でも、じゃんけんアプリでも、ビデオレンタルアプリでも、Suicaの残高を管理するアプリでも構わないのですが、プログラムを動かした結果として様々な情報を保持する必要があります。
ユーザーが持っているアカウントを表すデータはこのState Treeに保存されています。State TreeにはEthereumの中で利用するEtherの残高情報が入っています。Ethereumでは、ブロックサイズに制限はありませんが、Ethereumを利用する人全員の残高情報を全てブロックに入れてしまうとブロックサイズはとんでもなく肥大化してしまいます。そのため、State Treeはブロックの外に保持しておき、各ブロックにはState Treeのrootの値のみを入れておきます。
State Treeは過去のトランザクションから生成できるので、nブロックのState Treeを手に入れるためには 0 から n ブロックまでのトランザクションを順に計算していきます。その際に、各アカウントの状態をState Treeに入れる際に、アドレスをkeyとしてハッシュ化し、最後に一つになるまでハッシュを要約していきます。どこかで状態が不正に変更されてしまった場合はState Treeのrootの値が変更されてしまうので、改ざんされたことがわかります。このデータ構造はマークル木といいます。
また、木構造に対して、keyの値をハッシュ化すると、key名が長くなるため、検索や挿入のコストが増加してしまいます。EthereumのState Treeでは、分岐する際の条件を文字ではなく、文字列の並びにすることで分岐を減らし、検索挿入のコストを下げることに成功しています。このデータ構造をパトリシア木といいます。State treeはマークル木とパトリシア木を合体した構造なので、マークルパトリシア木の構造といえます。
Bitcoinで自分の残高を確認するためには今までに自分が受け取ってまだ使っていないやりとりを集める必要があります。State Treeに代表される状態を表す構造がないため、都度計算する必要があります。Ethereumで自分の残高を確認するためには、State Treeから自分が今持っている残高を取得するだけの処理で済みます。
Storage Treeはスマートコントラクトの持つ情報が入っています。スマートコントラクトもアカウントの一種です。残高管理アプリであれば、Aさんが1000でBさんが2000でCさんは20などと言った情報が入っています。
以上、主要と思われる3点を挙げてみました。
その他にも異なる点はありますが、Ethereumはそもそもが分散アプリケーションを実現するためのプラットフォームであり、Bitcoinと設計思想が異なります。興味がある方はYellow PaperやWhite Paperを読んでみるとさらに違いがわかるでしょう。
間違いがあった場合は直接メッセージを送ってください。喜びます。
明日は@Ihara-kentaさんです。
