暗号通貨 ハッシュ関数を学ぶ その1 SHA Ethash

hash2
たくさんのハッシュ関数がありますね。
こんにちは、ノリヒロです。いまさら感はありますがハッシュ関数についてです。数が多いので、複数回に分けてご紹介します。第一回目は、よく耳にする「SHA型」「Ethash」です。

ハッシュ関数その1

①ハッシュ関数とは

②SHA型

③Ethash

①ハッシュ関数とは

英語では「hash function」。
あるデータ(key)に対して、適当な値(特定のルールに従って出した値)を作って返してくれる関数です。返した値を「ハッシュ値」といいます。

特徴としては
ルールに従って適当な値が返ってくる
同じKeyでは同じ値が返ってくる
不可逆的で一方向であり、復元不可能である

となります。

ブロックチェーンでは、トランザクションや直前のブロックデータをハッシュ化するなど、ハッシュ関数がとても重要な役割を果たしています。通貨によって、使用するハッシュ関数が異なります。

①SHA型 BTC BCH

haash3

SHA型は、Bitcoin(BTC)やBitcoincash(BCH)で用いられているハッシュ関数です。
正式名はSecure Hash Algorithm(セキュアハッシュアルゴリズム)で、アメリカ国立標準技術研究所(NIST)によって標準のハッシュ関数に指定されています。

元はMD5から始まり、攻撃法が発見されてはその都度改良が加えられました。

MD5⇒SHA-0(1993)⇒SHA-1(1995)⇒SHA-2(2001),SHA-3(2015)となります。
特に2017年に発表されたSHA-1の衝突攻撃
は「異なるkeyからハッシュ化するとほぼ同じハッシュ値が作成される」というものです。
hash5

この図のようにkeyは「john Smith」と「SandraDee」で違いますが、ハッシュ値は同じ「hash02」となって衝突
が起こっていますね。これでは、偽のデータに改ざんされる可能性がゼロではないということですね。
先ほどの研究ではハッシュ計算に(110台のGPUで1年かかる計算)が必要であるとしています。そこで、SHA-1からSHA-2への改良が行われました。

SHA-2ではハッシュ長を変えられるようになりました。SHA-224,SHA-256,SHA-384,SHA-512,SHA–512/224,SHA-512/256の6つのバリエーションがあります。現在では、フルバージョンのSHA-2に対する攻撃は成功していないようです。

それとは方向性を別にSHAの代替えを求める動きがありました。それがSHA-3です。代替えですので、SHA-2までとは全く違う構造となります。元Keccak として知られたアルゴリズムがベースとなります。スポンジ構造に基づく関数です。構造は難しいので…詳細が知りたい方はこちらを参照ください。実際にはまだSHA-2が多く使われています。
参照:wiki SHA-3


SHA-256はBTCで使用されていますが、PoWのマイニングに参加する人が増えてCPU⇒GPU⇒ASICと専用のツールが開発され、大規模なマイニングが行われています。マイニングの寡占状態は、ブロックチェーンの安全性を損なう危険性がありますので、危惧されています。ブロック生成は、10分/ブロックです。

③Ethash Ethereum

Ethereumも同じPoWを採用していますが、ハッシュ関数としてEthashを使用しています。Etereumは言います。

PoWが本来備えているべき性質は
1:特殊な機械を使用して有利になるべきではない
2:マイナーの資本力に応じて、ハッシュパワーを与えるべきではない

である。ところが、ASICの出現のせいでこの2つが実現されていない。だからこの問題を解決するために、独自のアルゴリズムを作成した。

Ethereumの最初は、Dagger Hashimotoというアルゴリズムを使用していました。PoWのアルゴリズムで、適度にDAGに接続する計算をされていたようです。
dag
DAGとは、Directed Acyclic Graph(有向非巡回グラフ)のことです。Bitcoinのような1本の鎖ではなく、木のように複数の鎖が網目状につながっています。PoWアルゴリズムでDAGに適度に接続する計算をさせることでメモリー消費を激しくさせます。もともとASICは単純な計算に対して特化したものであったため、ASIC耐性を持つことが可能となります。

2015年のEthreumのホームステッドへの修正を経て、Dagger Hashimotoも Ethashへと改良されています。

Ethashも、メモリー消費が激しく、ASICやFPGA(両方とも特定の設定ができる集積回路、要するにマイニング専用機械)抵抗をもち、もしASICを作成してもGPUマイニングよりも効率が圧倒的に落ちるようしむける事で、マイニングの寡占化を防いでいます。ブロック生成時間は15秒/ブロックです。
参照:イーサリアムジャパン

いかがでしたでしょうか。Ethashは理解がまだまだですね…難しい。間違っていたところがありましたらコメントいただければ幸いです。助かります。次回は scrypt と zerocoin を予定しています。
ありがとうございました。

コメント

  1. tk84gf より:

    こんにちは。
    この記事とても面白かったです。
    他の記事も是非いろいろと読んでみます。
    これからも頑張って下さい。

  2. ノリヒロ より:

    ブログを閲覧いただきまして感謝いたします。ブロックチェーンだけの技術ではありませんが、ハッシュ関数は非常に面白いものが多いです。まだまだ勉強中ですが、できる限りわかりやすく記事にしていきますのでよろしくお願いいたします。

  3. けいた より:

    こんにちは。
    記事とても勉強になりました。
    「PoWアルゴリズムでDAGに適度に接続する計算をさせることでメモリー消費を激しくさせます。」という箇所らへんがよく理解できませんでした…もう少し詳しくお願いできますでしょうか…?

  4. ノリヒロ より:

    けいたさん、コメントありがとうございます!
    BTCとETHについて、PoW(proof of work)の合意形成(マイニング)を対比してお伝えします。
    BTCはSHA256というハッシュを使っているのはお伝えしました。このハッシュは、一定の法則に従ってただひたすら計算して総当たりで答えを見つけるだけなので、直線的です。図で示すなら〇→〇→〇→〇→答え(成功!)です。ASIC(特定集積回路)は単純計算を数多くこなすには優れた機械なのでこのハッシュには適しています。
    一方ETHはEThashというアルゴリズム、その中の機能がDAGです。ブログでDAGのところで説明している、〇と矢印の樹状の図があります。先ほどのBTCの【〇→〇→〇→答え】といったように、直線的・連続的ではありませんよね。いろんなところに進みますが、全体でみると1つの→で繋がっています。この【いろんな方面に分岐するが最終的には1つに結合しなければならない】という機能は複雑で、メモリーをものすごく使います。単純作業が好きなASICには向かないのです。(専用のASICを作ったとしてもGPUよりも効率が悪い)。
    このDAGのおかげで、ASIC耐性があるといわれ、一部のマイナーによるハッシュパワーの独占を防いでいたわけです。
    なお、このEthashに関しても、2018年4月にBitmainが専用のASICを開発しています。
    あまりうまく説明できずにスミマセン。わからないところがありましたらまたコメントください!!
    > こんにちは。
    >
    > 記事とても勉強になりました。
    > 「PoWアルゴリズムでDAGに適度に接続する計算をさせることでメモリー消費を激しくさせます。」という箇所らへんがよく理解できませんでした…もう少し詳しくお願いできますでしょうか…?