Equihashについて

This is the Japanese translation of “Speaking of Equihash”, prepared for Beam Japan. The original Beam Japan Medium post is here.

一般化された誕生日のパラドックス

1つの部屋に2人だけが居合わせた場合、その2人の誕生日が同じになる確率は、1年における365日と2月29日（閏年）を合わせた366日、すなわち366分の1です。1つの部屋に367人が居合わせた場合、100%の確率で同じ誕生日の人が2人いるでしょう。なぜなら、想定しうる誕生日の日数より多くの人が集まっているからです。しかし、50%の確率で同じ誕生日の人が2人いるようにするためには何人必要なのでしょうか。驚くべきことに、たった23人しか必要ありません。というのも、1年のうち、どの日に生まれるかの確率は等しいにもかかわらず、30人の生徒が在籍する平均的な規模のクラスでは、その確率は70%に上がり、70人が居合わせた場合には、99.9%の確率で2人が同じ誕生日となるのです。

このパラドックスは、可変長である年数によって一般化することができます。1年が $d$ 日だとすると、ランダムに選ばれた $n$ 人の、$n$ がいくつなら、最低でも50％の確率で誕生日が重なるでしょうか。問題は、2つの側面（あるいは2つの分類）にも拡張され得る、2つのグループの人々、例えば、$m$ 人の男性と $n$ 人の女性がいるとき、少なくとも1人の男性と1人の女性が同じ誕生日になる確率（2人の男性または2人の女性が同じ誕生日となる確率は考慮しない。）はどのくらいでしょうか。David Wagner は $k$ 個の側面[1]を一般化し、複数の側面を持つタイプを加えました。「$n$ ビットの $k$ つのリストが価値を持つとすれば、ビット演算の結果が0となるように、それぞれの要素から何らかの方法で1つずつ選びなさい。」といった問いを設定したのです。彼はその複雑さを証明し、そのためのアルゴリズムを考案しました。そこには多大な時間と労力が費やされたでしょう。

最初の誕生日の問題では、組み合わせの矛盾が生じますが、後者の一般化された問題は、暗号化とハッシュの衝突の研究にとって重要となります。

以下で述べられている通り、この問題の要旨はPoWに援用でき、それはASICの収益に限界点を与えるトレードオフに繋がっています。

PoWにおける課題

Biryukov and Khovratovich

Equihashを発展させたBiryukovとKhovratovichは、調整可能なパラメーターによる非対称的なPoWに様々な課題が生じていることを示しました。こうした課題は計算複雑性理論のもとで形式化されます。それらは解決困難であり、理論上では解決できても、いずれの解決策もリソースを費やしすぎてしまうため、現実では有用性に欠けます。実現可能性は、多項式時間解として定義されます。つまり、問題が大きいほど、$k$ が正の定数の場合、$n^k$ のような多項式として計算が大きくなります。しかし、手に負えない問題は指数関数的に大きくなります。十分に大きな問題は、計算するために永久とも言える時間を要するでしょう。

ソース: BIGOCHEATSHEET.COM

これらの難しい問題の1つは、巡回セールスマン問題です。「都市のリストと各都市間の距離が与えられた時に、各都市を訪問して出発地の都市に戻る最短の経路はどれですか？」というものです。もう1つは、試験のスケジュール設定の問題です。「生徒が多くのクラスに登録している場合に、同じ時間に複数の試験が重ならない最短の試験スケジュールを見つけなさい。」という問題です。まだそのようなありふれた問題を解くための優れた方程式はありません。それでも、問いが小さなサイズであれば、力ずくのアプローチはまだ実行可能です。

これらの問題のサブセットであるNP完全問題は、Proof of Workの為の最良の候補です。なぜなら、それらにとって最良なアルゴリズムとは、指数時間で実行され、多項式時間で検証され、それが容易であることだからです。

Super Mario Coin — Nintendo

数独コインはN by Nの数独グリッドで作ることができます。または、特別なスーパーマリオレベルを持つスーパーマリオコイン、あるいは、パックマンでも、プロセスや削減によってNP-Hard[2]であることがすべて証明されています（1つの問題を別の問題に変える）。難しい問題とNP問題は、沢山の例を含むリストがあります。一般化された誕生日のパラドックスはそのうちの1つであり、それを計算するための拡張されたワーグナーのアルゴリズムと共に、Equihashに用いられてきました。

BiryukovとKhovratovichは、Equihashの論文[3]の中で、これらの条件が良好な作業証明メカニズムを構築するために必要であると公式化しました。

• 非対称性： マイナーは、証明することは困難を伴いますが、その証明を検証することは簡単です。もし、その証明の検証が困難である場合、それがネットワーク上でDoS攻撃のキッカケになり得ます。これは数独のような問題に似ています。グリッドを解くのは難しいですが、幾つかの最適化プログラムを除いて、バックトラックを使ったブルートフォースよりも優れた戦略はありません。しかし、解決されたグリッドはすぐに検証することができます。RSAなどの暗号化方式で使用される素因数分解についても同じことが言えます。数を考えれば、掛け算したときにその数を得る2つの素数は何ですか？ 15の場合は3と5ですし、77の時は7と11です。それでは、54063013の場合はどうですか？ RSAは数百桁の長さの数字を使用します。繰り返しますが、計算が難しく、検証は簡単です。
• 最適化が出来ない： 賢いマイニング会社は、はるかに効率的にマイニングすることができる、賢いアルゴリズムを考案するかもしれません。効率的なアルゴリズムは、ムーアの法則によるマイクロチップの技術的進歩よりも桁違いに優れています。一般化された誕生日のパラドックスは、コンピュータ科学者や暗号技術者によって広く研究されてきており、将来の最適化を実現するのは困難ではありますが、不可能ではありません。
• 償却できない： 償却は規模の経済によるもので、クラスター化と集中化によって、マイニングははるかに効率的になります。Amortization（償却）では、全体が部分の合計よりはるかに大きいので、2 + 2は4になり得ません。どのコンピュータでも、10億個の計算機を掛け合わせるよりはるかに良いです。現在、マイニングプールは利益を均等に分け合うようになっており、利益は非常に細分化されています。単独のマイナーは、宝くじに当たるよりも低い確率でマイニングに成功するのを待つ必要があります。マイニングプールは、はるかに大きなチャンスがあり、プールの参加者間で報酬を共有します。確率論的に、最大のプールが大きな優位性を持つようになり、事態は悪化します。結果的に、最大のプールに回復不可能な集中化が生じます。
• 独立的に修正可能なパラメーター： さらなるアルゴリズムの改善および構造の変更を可能にするために、作業証明の時間、メモリ、およびPoWの傾斜は独立して調整可能でなければいけません。Equihashは、Wagnerの問題にBitcoinの難易度フィルタ（Hashcash[4]）を導入しました。そこでは、暗号ハッシュ関数の出力値の先頭d桁はゼロでなければいけないという性質を持っています。PoWは、時間の経過とともに一定の採掘率を維持するために、技術的な改善によってより高い効率性を得たマイナーを報いるために、その難易度設定を調整する必要があります。私たちは○×クイズの遊び方を習得し、毎回勝利するようになると、完全に遊ぶのをやめました。これは、ゲームの難易度を調整することができなくなったためです。
• 並列処理の制限： もしコアが互いに通信しあう必要がある場合、並列処理はバンド幅によって制限されます。また、ネットワークおよびメモリにボトルネックがあると、問題解決の困難性をバンド幅に依拠させるようにすることができます。並列処理を完全に回避できるかどうかはまだ証明されていません。依然として、本質的にシーケンシャルである問題を見つける必要もあります。Equihashは、並列処理による解決策が、チップを極端に大きくしたり、膨大なバンド幅を必要とするという課題を利用しようとしています。Equihashの一部は並列処理することができますが、いくつかのステップは順列処理のままです。並列処理は、1回の証明ごとにメモリを保持する必要がある時間も短縮します。Equihashはメモリのバンド幅に束縛されます。つまり、RAM GBとGB/sどちらにも依ります。

Equihashはさらに一歩進めて、コモディティ化されたハードウェアとカスタムされたハードウェアとの間の不均衡を是正するために、解決策（メモリーハード）を見つけようとしています。これを、Equihashは、証明の生成に大量のメモリを必要とする問題と合わせて行います。それでも依然として検証は簡単です。よく知られているように、アルゴリズムは時間計算量と空間計算量によって計られます。時間計算量は入力のサイズが大きくなるにつれて必要とされる計算ステップの増加を計ります。

空間計算量は入力が増えるにつれて必要となる追加のメモリー量を測定します。時間を犠牲にした場合、適度な入力値であっても天文学的な数字の計算が必要であり、また、空間を犠牲にした場合、現存するハードウェアの中で、この計算に必要なデータを全て保存できるものはありません。アルゴリズムでは時間と空間のトレードオフを考慮します。一般化された誕生日の問題では、kを変更することで時間/空間計算量のトレードオフを設定できます。

広いバンド幅を得るために、擬似ランダムな方法でアクセスされた適度なサイズのランダムな配列によって、多くのメモリハード方式が提案されてきました。後に、彼らは、このメモリをメモリーハード機能で満たすことを提案しました。もともと、メモリは領域と償却チップのコストから、とても高いリソースであると想定されていました。ASICは、メモリに関して通常のx86ベースのマシンよりわずかに効率的ですが、バンド幅の観点では当てはまりません。ASICは、すでにCPUよりも効率的なメモリバンド幅を持っているGPUよりもさらに最適化できます。

最初に提案された方式は、メモリ使用に関して対称的でした（検証は証明と同じ量のエネルギーを使用する必要があります）。また、この方式では、最適化や償却の可能性について分析されていません。この方式では、最適化アルゴリズムを許可しないようにする必要があります。また、計算コストを複数の呼び出しで償却することもできません。

その他の試み

Equihashとは別に、これらの問題[5]に対して、いくつかの注目に値するメモリハードで非対称なPoWの解決策がありました。

1. Primecoin は、マイニングがHashcashと等しいという概念を壊した、科学的な計算を作業とする最初のマイニングアルゴリズムです。マイナーは、Cunninghamチェーン[6]やbi-twinチェーン[7]として知られる特別な素数のチェーンを探します。ここで、素数はステップごとにほぼ倍増するか、特定のシーケンスに従います。
2. Daniel Larimerによる Momentum[8]（BitShares、Steemit、EOS）は一般化された誕生日問題に基づき、26ビットのインプットとハッシュ関数によって得られる、50ビットのアウトプットの衝突を探します。簡単に言えば、マイナーは併せてハッシュすることによって、0になる2つのアイテムを見つけなければなりません。ただし、時間と空間のトレードオフが非常に悪く、PoWとしては失敗しました。トレードオフは、良いPoWのために、直接的な関係を持つべきです。パズルは、Equihashに似ていますが、1次元のみです（k = 1）。
3. Ethash[9]（EthereumのPoW）では、シードはブロックごとに計算され、そこから数メガバイトの疑似乱数キャッシュを計算できます。そのキャッシュから数ギガバイトのデータセットが生成されます（30000ブロックの"epoch"ごとに、または約125時間で更新されます）。マイニングは、そのデータセットのランダムな一面を一緒にハッシュすることを含みます。検証は個々の証明よりも時間がかかるため、ここでは非対称性が逆になっています。これは、フルクライアントを持つマイナーが使用する大規模なデータセットではなく、検証者（多くの場合軽量クライアントです）がキャッシュからの再計算のためにスペースを使用するためです。
4. Dziembowski・他による Proof of Space[10]（proof of capacityとも呼ばれる）はBurstcoin、SpaceMint、およびChiaによって実装され、証明者はメモリハード関数を計算し、次に検証者はそれらが適切な関数によって埋められたかどうかをチェックするためにメモリロケーションのサブセットを要求します。
5. Tromp・他による Cuckoo Cycle[11] は、非常に簡潔な42行の完全な仕様を備えた、最初のグラフ理論的PoWです。証明者は、2部構成のCuckoo Hashtableグラフで42個のエッジのサイクルを見つける必要がありますが、これは非常に検証が簡単です。2015年1月のCuckoo Cycleの投稿によると、デイブ・アンデルセン（Dave Andersen）によって認識されたエッジをトリミングするスペースの最適化が含まれています。

Equihashは、一般化された誕生日のパラドックスに基づいて、高速でメモリ非対称で最適化と償却性を伴わないPoWを提案しました。償却性を排除するために、彼らはアルゴリズム結合と呼ばれる別の制約を導入し、それぞれの解決策をユニークにしました。また、BitcoinのHashcashアルゴリズム（Adam Backが提唱）の要素を組み合わせ、マイナーはd個の先行ゼロを持つダイジェストを見つけるまでハッシュします。上で概説したように、ワーグナーの一般化された誕生日のパラドックスはnとkパラメーターを承認します。そして、それは修正することが簡単ではない時間の空間の問題をもたらします。解あたりの計算時間は、nを増やすことで短縮できます。これにより、メモリを犠牲にして解の数を増やします。Hashcashでは、dによる難易度の調整は簡単で、Zcashの実装では、この難易度パラメーターは2.5分を目安にするようにネットワークによって調整されています。

Zcashの実装

Zcash Foundationは、n = 200、k = 9のパラメーターを指定したEquihash PoW[12]を実装しました。これは、解を見つけるために必要なメモリースペース/バンド幅の量を示します。それを、賞金30,000ドルのオープンソースマイナーチャレンジ[13]で試しました。このアルゴリズムは、Bitcoin GoldとBitcoin Privateによって採用されています。

Solar Designer[14]（Alexander Peslyak）は、2016年にZcashによるEquihashの選択と、そのパラメーターを分析し、Zcashのパラメーター（n = 200、k = 9）は最適ではないため、変更が必要な可能性があると結論付けました。Zcashのオープンソースマイナーチャレンジへの提出において、設定されたZcashのパラメーターでは、ほとんど全ての解を効率的に見つけるために少なくとも144 MiBのRAMが必要であったからです（現在、一般的で最大のCPUには64 MiBを超えるSRAMが含まれています）。1チップあたりのSRAMの量を最大化するという特別な目標を掲げた時に、ASICは非常に速く追いつくことができ、エネルギー効率とハードウェアコストが最も適した一般的なハードウェアよりも、効率性において10から100倍優れます。他の解決策の候補は、Epiphany V（1024個のCPUコアを搭載）などの多数のコアを備えるCPUやeDRAMです。Solarは2016年に、最終的にASICマイニングについて、Zcashへの注目度がLitecoin（Bitcoinではなく）と同等になる可能性があると結論付けました。

さらにSolarは、現在最適化されているEquihashソルバー（解法）には、Zcash社の立ち上げ時にEquihashで一般に知られていないような最適化がいくつか含まれていると述べました。Equihashの論文が示唆していたもの（インデックスペアの成長リスト）よりもずっとコンパクトな方法（インデックスペアのバイナリツリー）で中間結果を格納します。big-O空間の複雑さは $(2^k) / k$ 倍にも減っています。その上、衝突と完全にソートされたリストを出力しない不完全なバケットソートとを同一視しますが、その一方でWagnerのアルゴリズムは完全なリストの整列操作によって通常表現されます。

Tromp、そしてxenoncat[16]はそれぞれ、公開版Equihashの空間最適化を確認しました。AlcockとRen[17]は、セキュリティが一般化された誕生日のパラドックスに対するWagnerのアルゴリズムに基づいているというEquihashの主張に反論しました。また、それに対するトレードオフ耐性の制約は一切知られておらず、解の予想数に関する分析は不正確であるとも言及しました。Equihashは正式に証明されたセキュリティ保証のない発見的方法であると結論づけました。

ASICの時代

2018年6月、BitmainはASIC Antminer Z9 mini（5月のASICminerに続く）を発表しました。このマイニングマシンは、低コストでSRAMチップでインターフェイスを設けることで、Equihashを一般的なCPUやGPUよりはるかに効率的にマイニングできるようにするものです。この発表はBitmainによるEthereumマイナー発表の1ヵ月後に行われました。EthashアルゴリズムもASIC耐性を持つように考案されていました。ルクセンブルク大学の研究者たちは、2018年5月現在、Equihashの20〜30%がASICによってマイニングされていると報告しています。

Antminer Z9 mini announcement

Zcashの創設者Zooko Wilcoxはフォーラムでの投稿で、ASIC耐性をコミットすることは、長期的に見て不可能であり、考えていなかった事を明かしました。さらに、一方では、コインの配布において根源的なトレードオフが存在します。また、コインへの投資として、大きな埋没コストを抱えるマイナー達がいます。後者は、最終的には、攻撃耐性の確保において、ネットワークの安定性に寄与し、価値があることが証明する可能性があります。彼は、Equihash採用の動機は、初期のコインの配布とマイニングにおいて広範性を確保することであることを明かし、これが一時的な戦略ではなく長期的な原則であると人々に認識させました。Zcash社は、依然としてASIC耐性の道を探求していると述べました。

結論

私たちBeamはMimblewimbleとEquihashが最も有望で、最先端技術であると考えています。Equihashは安定したGPUフレンドリーなアルゴリズムであり、ローンチ時に公平なコインの配布を可能にします。BeamはCPUとGPUのマイナーたちに、ASICに比べ大幅に有利にスタートが切れるようにパラメーターを設定します。しかし、Beamは長期的には、ASIC耐性を確保しようとするポリシーは持っておらず、長期的に見れば、ASICが追い付いてくると考えています。このポリシーによって、Beamのネットワークに、強力なハッシュレートと、暗号化による防御壁が構築されつつ、マイニングコミュニティとインセンティブの調整も上手く行くと考えています。

このようにして広範囲で公平なコインの配布と、ASICマイナーたちとの不可避ではあるが相乗的な攻撃耐性の獲得という、トレードオフの間でのバランスを実現していきます。

著者： Ronen Lahat. @ronenl

参考

[1] Wagner D. 2002. A Generalized Birthday Problem. In: Yung M. (eds) Advances in Cryptology — CRYPTO 2002. Lecture Notes in Computer Science, vol 2442. Springer, Berlin, Heidelberg. https://link.springer.com/chapter/10.1007%2F3-540-45708-9_19

[2] Viglietta G. 2012 Gaming is a hard job, but someone has to do it! https://arxiv.org/abs/1201.4995

[3] Biryukov, A., & Khovratovich, D. 2017. Equihash: Asymmetric Proof-of-Work Based on the Generalized Birthday Problem. Ledger, 2, 1–30. https://doi.org/10.5195/ledger.2017.48

[4] Black, Adam. 2002. Hashcash — A Denial of Service Counter-Measure. http://www.hashcash.org/papers/hashcash.pdf

[5] @tromp: Cuck(at)oo Cycle POW https://youtu.be/CLiKX0nOsHE

[6] Cunningham chain https://en.wikipedia.org/wiki/Cunningham_chain

[7] Bi-twin chain https://en.wikipedia.org/wiki/Bi-twin_chain

[8] Larimer, Daniel. Momentum — A Memory-Hard Proof-of-Work Via Finding Birthday Collisions. http://www.hashcash.org/papers/momentum.pdf

[9] ethereum/wiki https://github.com/ethereum/wiki/wiki/Ethash

[10] Dziembowski, Faust, Kolmogorov, Pietrzak. 2013. Proofs of Space. https://eprint.iacr.org/2013/796.pdf

[11] tromp/cuckoo https://github.com/tromp/cuckoo/

[12] Why Equihash? — Zcash https://z.cash/blog/why-equihash/

[13] Zcash Open Source Miners https://zcashminers.org/

[14] Solar Designer. 2016. An analysis of Zcash’s use of the Equihash proof-of-work scheme. http://www.openwall.com/articles/Zcash-Equihash-Analysis

[15] Breaking equihash in Solutions per GB second https://forum.zcashcommunity.com/t/breaking-equihash-in-solutions-per-gb-second/1995

[16] xenoncat/equihash-xenon https://github.com/xenoncat/equihash-xenon

[17] Alcock, Leo & Ren, Ling. 2017. A Note on the Security of Equihash. 51–55. 10.1145/3140649.3140652. https://dl.acm.org/citation.cfm?id=3140652

[18] Biryukov, Alex & Feher, Daniel. 2018. Detecting ASIC Miners in Zcash (draft v1.1) https://cryptolux.org/images/e/ef/Zcash_Mining.pdf

Japanese translation prepared for Beam Japan. Original English article: Speaking of Equihash. Beam Japan Medium version: Equihashについて.