はじめに
こんにちは、新規事業開発室インターンの高橋(@KT1539164348)です。
最近ビットコインマイニング界隈でASICBoostと呼ばれるマイニングアルゴリズムが再び注目を集めています。ASICBoostとはマイニングを効率的に行うためのアルゴリズムであり、20〜30%効率がアップすると言われていました。ところが2017年8月、ビットコインにsegwitと呼ばれる仕様が追加されたため使用することができなくなっていました。そのASICBoostが復活したとの情報から、ASICBoostは再び注目を集め始めているのです。
2018年3月、Halong社がsegwitアクティベート環境でも使用可能なASICBoostの実装に成功したことを発表し、その後大手マイニングプールSlush PoolがこのASICBoostをサポートしマイニングに成功したことを発表しました。 本記事では2種類のASICBoostの違いに注目し、マイニングの仕組み、なぜASICBoostは効率がよいのか、なぜsegwitによって使えなくなったのか、なぜ再び使えるようになったのかといったことを説明していきます。
ASICBoostに関して簡単にまとめられています。ASICBoostって何？って方はこちらに目を通してみてください。
- はじめに
- マイニングとは
- マイニングの仕組み
- nonce使い切り問題
- covert ASICBoostとは
- covert ASICBoostのアルゴリズム
- segwitとは
- Overt ASICBoostとは
- まとめ
- 最後に
- 宣伝
マイニングとは
マイニングとはトランザクションを検証し、過去のブロックとの整合性を取りながら新しいブロックを生成することです。具体的にはブロックヘッダーのハッシュ値(ブロックハッシュ)が一定以下になるようなnonceを求める作業を行います。
ハッシュ値は一方向性を持つため目的のハッシュ値からnonceを求めることはできず、nonceを変更しブロックハッシュを計算する作業を総当たり的に繰り返す必要があります。よってこの作業を早く行なうことができるほどブロックの生成に成功しやすいということになります。この計算を行ったという証拠がnonceであり、この計算量がブロックチェーンのセキュリティを担保しています。
こちらの記事にマイニングについて更に詳しく紹介されています。この記事を読んでから先に進んでいただいた方が理解しやすいかもしれないです。
マイニングの仕組み
マイニングにおいて前述のようにハッシュ値の計算を繰り返すのですが、ビットコインにおいてはハッシュ値の計算にDouble SHA-256というアルゴリズムが用いられています。このアルゴリズムは文字どおりSHA-256というハッシュアルゴリズムを2回用いてハッシュ値を計算します。アルゴリズムの詳細を以下で説明します。
まず80bytesのブロックヘッダーに対して48bytesのpadding(データサイズを合わせるために追加する意味のないデータ)を追加し、64bytesずつ２つのchunk(かたまり)に分割します。この操作はSHA-256が64bytesの内部状態(state)を持ち、その内部状態とchunkのサイズが同じである必要があるためです。ここでマークルルートが前半部分head(28bytes)と後半部分tail(4bytes)に分かれていることに注意しましょう。このマークルルートとは図２のようにトランザクションのハッシュ木のルートのことを指します。
続いて図3のように様々な関数をinit state(初期状態)とchunkに対して作用させます。init stateとはSHA-256が最初から保持している64bytesのデータのことです。
Expanderはchunkを1byteずつに区切り、それぞれをそれぞれに対応した単語に置き換えることでmessage scheduleを作成します。Compressorはこのmessage scheduleと一つ前のstateを入力として次のstateを計算します(ぐちゃぐちゃに混ぜて復元不可能にするイメージ)。つまりchunkを使って次々にstateを変更していくイメージです。そして一連の計算を全てのchunkを用いて行い、得られた最終stateから出力を計算します。
これがSHA-256であり、Double SHA-256は1回目のSHA-256の出力を(図3:Single SHA Digest)２回目のSHA-256の入力とし、ブロックハッシュ(図3:Double SHA Digest)を得ます。通常のマイニングではこの作業を、ブロックハッシュが一定以下になるnonceを発見するまで次々にnonceを変更して行います。
ハッシュ関数に関してはこちらの中村さんのスライドがわかりやすいです。
nonce使い切り問題
マイニングはブロックハッシュを求める計算速度が速いほど有利であるため熾烈なハッシュレート(1秒間に計算できるブロックハッシュの数)の上昇競争が行われました。そのためビットコインではブロックの生成間隔が約10分になるようにマイニング難易度(ディフィカルティ)が調整されているのですが、１つのブロックを生成するために必要な計算量は増大していきました。その結果4bytesのnonceをすぐに(1秒以内に)使い切ってしまい、使い切ってもブロックハッシュを一定以下にすることができない(マイニングできない)ということが起こり始めました。これがnonce使い切り問題です。
この問題の対応策としてマークルツリーに含まれるトランザクションを入れ替えることでマークルルートを変更するというものが提案されました。ブロック内のトランザクションは順不同なので入れ替えを行なっても内容は変化しません。これによってnonce使い切り問題は解決されました。
以上を踏まえると通常のマイニングは図４のように行われます。低頻度なOuter Loop(上図緑色)と高頻度なInnerLoop(上図赤色)が存在しており、Inner Loopにおいてはnonceを変化させてハッシュ値を計算し、nonceを使い切るとOuter Loopにおいてマークルルートが変更され(それに伴ってMid stateとMessageが変化して)、再びInner Loopに戻ることを繰り返します。なお図4のMessageとはマークルルートのtail、Timestamp、Bits(図1)を合わせたものを指します。
このマイニングアルゴリズムはOuter Loop にてMerkle rootを変更するとchunk1、chunk2(すなわちMid state、Message)ともに変化するため再度Message schedule1の計算が必要なことから効率が悪いと考えられます。
covert ASICBoostとは
segwitの導入によって使えなくなってしまった方のASICBoostはCovert ASICBoostと呼ばれています。Covertとは非公開という意味でありその名の通りアルゴリズムの実装や用いられる集積回路の設計は公開されておらず、特許に守られていました。そのため一部のマイナーのみが効率的な方法でマイニングを行うことによってブロックの生成成功率に偏りが生じ分散性が毀損されるのではないかという批判を浴びていました。
またsegwitが導入されると使用不能になることから、その導入に反対していたためビットコインコミュニティの発展を阻害している、ASICBoostを使用しているマイナーはデータサイズが小さいブロックを作るインセンティブがあるといった批判も浴びていました。
ASICBoostについてはこちらのメルカリの高橋さんのスライドがわかりやすいです。
covert ASICBoostのアルゴリズム
図1を振り返ってみるとわかるのですがマークルルートのtail、つまり後半4bytesを固定することができればMessageを固定することが可能です。そのためCovert ASICBoostでは事前に後半4bytesが同じ(衝突している）マークルルートを大量に計算しておきます(マークルルートの計算はブランチ(マークルツリーに含まれるトランザクション)を入れ替えるだけなので再利用できる計算が多く、Message Scheduleの計算と比較して容易です)。まとめるとこれらのマークルルートを総当たりで使用してブロックハッシュを求める高頻度なinner Loop、そしてマークルルートを使い切る度にnonceを変化させる低頻度なouter Loopが存在しています。
segwitとは
segwitとはビットコインの仕様を変更する提案の一種です。segwitが実装されることによってトランザクションやブロックの仕様が変更されます。ビットコインのトランザクションについてはこちらの記事で詳しく説明しています。
この変更によってビットコインのMalleability問題を解決し、スケーリング問題に対しても有効とされています。ライトニングなど多くの新技術の前提となっている大変重要な技術です。
図8のように通常のTXIDから構成されるマークルツリーのcoinbase transactionの中にwitness commitmentという領域が追加されました。ここには先述のWTXIDから構成されるセカンドマークルツリーのマークルルートが置かれなければなりません。つまりブロックヘッダに含めるマークルルートを計算するために２つのマークルツリーを構成しなければならなくなりました。
ここで前述したCovert ASICBoostの話を思い出して欲しいのですが「マークルルートの計算はブランチを入れ替えるだけなので再利用できる計算が多く、Message Scheduleの計算と比較して容易です」と述べました。しかしsegwitの適用によってマークルルートを求めるために必要な計算量が大幅に増大してしまうのです。そのためマークルルートを衝突させるための計算量がマークルルートを衝突させることによって得られる計算の削減量を上回ってしまいCovert ASICBoostの効率が低下し事実上無効化されると考えられます。
Overt ASICBoostとは
overt ASICBoostはマークルルートもnonceと同様に固定することでMessage Schedule1を固定します。そしてVersionを変更すること(version rolling)でchunk1(すなわちMid state)を変化させマイニングを行います。マークルルートを固定するためsegwitの影響は受けません。
2018年３月にHalongs社のDragonmintで実装されました。ただしこのDragonmintを使用してマイニングを行うにはDragonmintに対応したマイニングプールに参加する必要があります。現在のところマイニングプールとマイナーとのやりとりのルールを定めたMining Pool Protocolはstratum mining protocolと呼ばれるプロトコルが主流なのですが、このプロトコルで規定されているマイナーが変更可能なブロックヘッダーの領域の中にVersionが含まれていないからです。そのためマイナーとマイニングプールの間でVersionのどのビットを変更していいか交渉する手順が定められたStratum protocol extentions(図9)に対応したマイニングプールに参加する必要があります。
Slush poolはstratum mining protocolに対応しており、2018年3月24日、overt ASICBoostを用いてマイニングに成功したことを発表しました。
Our block #514882 is the first-ever block mined using the active version-rolling aka overt AsicBoost. According to the available evidence, it was mined by @HalongMining hardware. Congrats to lucky miner from Guangdong, China 🇨🇳https://t.co/4XtmSN6yo1
— Slush Pool ⚡️ (@slush_pool) 2018年3月24日
まとめ
ASICBoostはブロックハッシュの計算に必要なインプットの一部を固定することで計算効率を向上させている
この固定の仕方によってcovertとovertの2種類のASICBoostが存在する
covertはsegwitの適用によって無効化されたがovertは使用可能
ただしovertは特定のマイニングプールにしか対応していない
最後に
今回は普段意識することが少ないであろうマイニングアルゴリズムについて紹介しました。自分もマイニングアルゴリズムについて調べるのは初めてだったのですが、非常に面白い分野だと思いました。この記事を読んで興味を持っていただけたら以下の参考文献も読んでみてください！
ビットコインホワイトペーパー
ASICBoostについて
ASICBoostのホワイトペーパー
slush poolで用いられているStratum protocol extentionsです
segwitについて
日本語スライド、わかりやすいです
CovertとOvertの違いが簡潔にまとめられています
宣伝
Gunosyではブロックチェーンを始めとしてスマートスピーカー、VR/ARと言った新規領域での研究・開発を進めており、メンバーを募集しています。
少し話を聞いてみたい！という方も歓迎していますので、下記のリンクからの応募お待ちしております。
また弊社Gunosyでは、blockchain.tokyo を主催するなど、ブロックチェーンや仮想通貨に関する研究開発を進めています。
イベントグループへメンバー登録をしていただくとイベント参加者募集の通知が来るので、こちらもぜひ登録してみてください。
