Mercari Advent Calendar 2017の8日目はブロックチェーンについてです。
7日目は、@keita0qさんの
でした。
「ブロックチェーン x 分散ファイルシステム」に興味がある方は、@stanakaさんの
をご覧ください。
今日は、@zaq1tomoがサンフランシスコからお送りします。
はじめに
今回は、ブロックチェーンにおける主要技術のひとつ
コンセンサスアルゴリズム（合意形成アルゴリズム）についての投稿です。
- Proof of Work
- Proof of Stake
- Proof of Importance
他にも多くのアルゴリズムが提案されていますが、今回は最も代表的なBitcoinの
- Proof of Work（PoW）
についてまとめたいと思います。
Proof of Work（PoW）
White paper
まずはWhite paper、ということでSatoshi Nakamotoによって書かれた論文
Bitcoin: A Peer-to-Peer Electronic Cash System
を実際に読んでみましょう。
Proof of Workについて書かれているのは、以下の部分です。
To implement a distributed timestamp server on a peer-to-peer basis, we will need to use a proofof-work system similar to Adam Back’s Hashcash [6], rather than newspaper or Usenet posts. The proof-of-work involves scanning for a value that when hashed, such as with SHA-256, the hash begins with a number of zero bits. The average work required is exponential in the number of zero bits required and can be verified by executing a single hash. For our timestamp network, we implement the proof-of-work by incrementing a nonce in the block until a value is found that gives the block’s hash the required zero bits. Once the CPU effort has been expended to make it satisfy the proof-of-work, the block cannot be changed without redoing the work. As later blocks are chained after it, the work to change the block would include redoing all the blocks after it. The proof-of-work also solves the problem of determining representation in majority decision making. If the majority were based on one-IP-address-one-vote, it could be subverted by anyone able to allocate many IPs. Proof-of-work is essentially one-CPU-one-vote. The majority decision is represented by the longest chain, which has the greatest proof-of-work effort invested in it. If a majority of CPU power is controlled by honest nodes, the honest chain will grow the fastest and outpace any competing chains. To modify a past block, an attacker would have to redo the proof-of-work of the block and all blocks after it and then catch up with and surpass the work of the honest nodes. We will show later that the probability of a slower attacker catching up diminishes exponentially as subsequent blocks are added. To compensate for increasing hardware speed and varying interest in running nodes over time, the proof-of-work difficulty is determined by a moving average targeting an average number of blocks per hour. If they’re generated too fast, the difficulty increases.
簡単に翻訳してみます。
P2Pで分散型タイムスタンプサーバーを実行するためには、新聞やUsenetポストというより、アダム・バックのHashcashのようなProof of Workのシステムを使う必要があります。Proof of Workには、SHA-256のようなハッシュ化をしたとき0ビットではじまる値が含まれます。通常のブロック生成作業で要求されるのは、必要とされる個数の0ビットをもった指数で、ハッシュ化を一度行うことで検証できます。Bitcoinの分散型タイムスタンプサーバーでは、ハッシュ化したときに要求された個数の0ビットで始まる値が見つかるまでの間、ブロックにnonceを足していくことでProof of Workを実現しています。一度、このProof of Workの制約を満たすためにCPUパワーを使ってブロックが生成されると、そのブロックはもう一度この作業を繰り返さない限り変更することはできません。その後のブロックも、チェーン化されて連なっていくため、過去のある地点のブロックを変更しようとすると、それ以降のブロック全てで同様の作業を繰り返さなければなりません。また、Proof of Workは、多数決における意思決定で代表をどう決定するかという問題を解決しています。一つのIPアドレスで一回の投票とすると、多くのIPアドレスを手に入れることのできるものはネットワークを乗っ取ることが出来てしまうでしょう。Proof of workは、原則一つのCPUで一回の投票です。多数決における意思決定の代表は、最もProof of Workの労力が費やされた、最も長いチェーンです。CPUパワーの過半数が良心的なノードによってもたらされるとき、その良心的なチェーンはどの競合のチェーンよりも早く成長していきます。攻撃者は過去のブロックを変更するために、その後に続く全てのブロックにおいてProof of workを再実行して良心的なチェーンに追いつき、追い越さなければなりません。後で、低速な攻撃者が良心的なチェーンに追いつく可能性は、後続のブロックが追加されるごとに指数関数的に減少していくことを示します。ハードウェアスピードの加速とマイナーの心理の長期的な変化に対応するために、Proof of Workの難易度は一時間ごとのブロック数を一定に保つことを目的とする移動平均によって決定されます。ブロックの生成が速ければ、難易度は増加します。
以上が、Proof of Workの概要です。
「よくわからない、何がどう動くんだ？？？」
そんな方のために、実際にソースコードを使っていくつかのトピックを深掘りしていきましょう。
ハッシュ関数
一つ目のトピックは、ハッシュ関数です。
Proof of Workを理解するためには、このハッシュ関数について理解する必要があるでしょう。
BitcoinのProof of Workでは、
- SHA-256
というハッシュ関数使われています。
ハッシュ関数を直感的に理解するために、「SHA-256がどのような挙動を示すか」スクリプトを書いて検証してみます。
// example of SHA-256 package main import ( "crypto/sha256" "fmt" ) func main() { // input data data := "Mercari" // calculate SHA-256 hash of the input hash := sha256.Sum256([]byte(data)) // show the input and SHA-256 has result fmt.Printf("Mercari =>\n %x\n", hash) }
Mercari => b37e1c8a0583db3e2e8d5f09df92c02344d3f4c281a84422ce695f5ae0bb7fc9
入力「Mercari」に対して、SHA-256によって生成した出力
b37e1c8a0583db3e2e8d5f09df92c02344d3f4c281a84422ce695f5ae0bb7fc9
がハッシュ値です。ハッシュ値は予想出来ず、実際に計算してみないとどのような値になるかわかりません。
もう一度スクリプトを書いて「入力を変化させると出力が異なること」を検証してみます。
// example of SHA-256 package main import ( "crypto/sha256" "fmt" ) func main() { text := "Mercari" for i := 0; i < 5; i++ { nonce := fmt.Sprint(i) // add the nonth to the end of text data := text + nonce // calculate SHA-256 hash of the input hash := sha256.Sum256([]byte(data)) // show the input and SHA-256 has result fmt.Printf("%s =>\n %x\n", data, hash) } }
Mercari0 => 137402fad777dce4c55d7cb0ad770daecd847a24a61f72a4d683ed26a4d91993 Mercari1 => 87febb4a8045297e457ddb5d25cc3047eb97ad4f8ebb57f471fe2a76a7c14ea7 Mercari2 => 96d82f5f3f4e3239ca3b70e317c1c88bcfe1c184ce424d0bd24a4d7bb93910e3 Mercari3 => 2570e3259e49959b62032f543f248a8ee8ddc24f45748dfcd72565ad42741c68 Mercari4 => 0bcb3020ba81bbdf23ad226dfcfe00ea32415638fd8e3b12d8fb725e28c9c6d2
5回目の試行をしたところで先頭が0から始まるハッシュ値が見つかりました。
この結果は、「target=0x10000…よりも小さいハッシュ値を生成するnonce=4を発見した」ということが出来るでしょう。
targetを小さくすると、解となるハッシュ値を見つけるまでにかかる時間は指数関数的に大きくなります。
求めたハッシュ値が、あるtarget以下のnonceを探すという仕事をしたという証明になるのです。
BitcoinのProof of Workは、これと同じ仕組みを用いています。
Difficulty
二つ目のトピックは、Difficultyです。
Bitcoinのブロックは、平均10分ごとに生成されています。
技術の発展ともにコンピューターの処理速度は急激に加速してくため、
ブロックの生成時間を一定に保つためには、適切な難易度(Difficulty)のtargetが設定され続けなければなりません。
ではどのように調整が行われているのか、Bitcoinのソースコード
を実際に見てみましょう。
unsigned int CalculateNextWorkRequired(const CBlockIndex* pindexLast, int64_t nFirstBlockTime, const Consensus::Params& params) { if (params.fPowNoRetargeting) return pindexLast->nBits; // Limit adjustment step int64_t nActualTimespan = pindexLast->GetBlockTime() - nFirstBlockTime; if (nActualTimespan < params.nPowTargetTimespan/4) nActualTimespan = params.nPowTargetTimespan/4; if (nActualTimespan > params.nPowTargetTimespan*4) nActualTimespan = params.nPowTargetTimespan*4; // Retarget const arith_uint256 bnPowLimit = UintToArith256(params.powLimit); arith_uint256 bnNew; bnNew.SetCompact(pindexLast->nBits); bnNew *= nActualTimespan; bnNew /= params.nPowTargetTimespan; if (bnNew > bnPowLimit) bnNew = bnPowLimit; return bnNew.GetCompact(); }
調整が行われているのは、以下の部分です。
// Retarget const arith_uint256 bnPowLimit = UintToArith256(params.powLimit); arith_uint256 bnNew; bnNew.SetCompact(pindexLast->nBits); bnNew *= nActualTimespan; bnNew /= params.nPowTargetTimespan;
簡単にまとめると、Difficultyの調整は以下の式で表せます。
new difficulty = old difficulty * (generation time of 2016 blocks / two weeks)
Bitcoinでは、2016ブロックごとに実際の生成時間と目標となる生成時間の比が計算され、
適切なDifficultyとなるように、次の2016ブロックでのtargetの調整が行われているのです。
参考: https://blockchain.info/charts/difficulty
まとめ
Proof of Workは - 膨大な計算量を使って発見困難な値を見つけるとブロックを作ることができる というアルゴリズムである。 Bitcoinでは、適切な間隔で適切にブロックが生成されるために - ハッシュ関数 - Difficulty といったアイデアを使っている。
Proof of X
Proof of Workについての理解は深まったでしょうか。
このアルゴリズムは、
- デジタル価値を保存する
という観点においてとても優れた画期的な技術です。
しかし実際の運用においては完璧とはいえず、いくつかのデメリットを抱えています。
- 消費電力
- 51%攻撃
このようなデメリットを解決するために、多くのアルゴリズムが提案されています。
Proof of Stake（PoS）
PoSは、Ethereumでの採用が予定されているアルゴリズムで
- コインを保有量や保有期間に応じてtargetを調整する
というのが基本的なアイデアです。
参考: https://github.com/ethereum/wiki/wiki/Proof-of-Stake-FAQ
Proof of Stake Velocity（PoSV）
PoSVは、ReddCoinなどで採用されているアルゴリズムで
- PoSと似ているが古いコインの保有は評価を下げる
というのが基本的なアイデアです。
参考: https://bravenewcoin.com/assets/Whitepapers/Reddcoin-PoSV.pdf
Proof of Importance（PoI）
PoIは、NENなどで採用されているアルゴリズムで
- ネットワークにおける重要度に応じてtargetを調整する
というのが基本的なアイデアです。
参考: https://nem.io/wp-content/themes/nem/files/NEM_techRef.pdf
Proof of Consensus（PoC）
PoCは、Rippleなどで採用されているアルゴリズムで
- 一部のノードの合意によってブロックが承認される
というのが基本的なアイデアです。
参考: https://ripple.com/files/ripple_consensus_whitepaper.pdf
Proof of Burn（PoB）
PoBは、Counterpartyなどで採用されているアルゴリズムです。
- 誰も使えないアドレスにコインを送ることで無効化させる
というのが基本的なアイデアです。
参考: https://counterparty.io/news/why-proof-of-burn/
他にも数多くの面白いアイデアやアルゴリズムが提案されていますが、
今回はこのあたりで。
最後に
Proof of Workなどのコンセンサスアルゴリズムを含め、ブロックチェーンのテクノロジーは未完成です。
暗号通貨のあるべきガバナンス、誰もが使えるアプリケーションの姿は今後も模索され続けるでしょう。
メルカリではブロックチェーン関連の開発を検討しており、
- 「ブロックチェーン」それ自体の技術
- 「ブロックチェーン x 分散ファイルシステム」のような応用技術
- 「ブロックチェーン」を利用したアプリケーション
様々なレイヤーに興味のあるエンジニアを募集しています。
採用情報はこちらから
また、定期的に「blockchain.tokyo」というコミニュティの運営も行っており、
来週の12/15(金)DMM.comラボさんで、来月ではメルカリでの開催を予定しています。
ブロックチェーンや暗号通貨の技術に興味のある方はぜひご参加ください！
9日目は、@syu_creamさんです。引き続きMercari Advent Calendar 2017をお楽しみに。
