エキハッシュ

Equihash は、ルクセンブルク大学のセキュリティ、信頼性、信頼に関する学際センター (SnT)が2016 年のネットワークおよび分散システム セキュリティ シンポジウムで発表した、メモリに負担のかかるプルーフ オブ ワークアルゴリズムです。このアルゴリズムは、衝突するハッシュ値を見つける誕生日問題の一般化に基づいています。厳しい時間と空間のトレードオフがありますが、予期しない並列最適化に対する脆弱性を認めています。^{[1]このアルゴリズムは、並列実装がメモリ帯域幅によってボトルネックになるように設計されており、カスタム}ASIC実装の設計におけるコスト パフォーマンスのトレードオフを悪化させようとしています。Equihash の ASIC 耐性は、市販のハードウェアがすでにかなり高いメモリ帯域幅を持っているという仮定に基づいており、カスタム ハードウェアによる改善は開発コストに見合わない可能性があります。^[要出典]

Equihash は、ルクセンブルク大学の研究グループ CryptoLUX の一員としてAlex BiryukovとDmitry Khovratovichによって提案されました。サンディエゴで開催された Network and Distributed System Security Symposium 2016 で発表されました。ZCash、 BitcoinZ 、Horizen、Aion、Hush、Pirate Chainなどの著名なブロックチェーンベースのプロジェクトは、セキュリティ、プライバシー、 ASIC マイナー耐性などの理由から Equihash を統合しています。^{[引用が必要]}

製造元のBitmainは、ASICを使用してZcashのEquihash-200,9の処理を最適化することに成功しました。^[2]

Equihashには、、の3つのパラメータがあり 、アルゴリズムの時間とメモリ要件を決定します。時間の複雑さは に比例し、メモリの複雑さは に比例します。アルゴリズムは、（有効な難易度を制御する別の方法を使用して）で実装されることがよくあります。^[1]${\displaystyle n}$${\displaystyle k}$${\displaystyle d}$${\displaystyle 2^{{\frac {n}{k+1}}+d}}$${\displaystyle 2^{k+{\frac {n}{k+1}}}}$${\displaystyle d=0}$

Equihash の問題は、先頭にゼロが付くような、異なる- ビット値を見つけることです。ここで、は選択されたハッシュ関数です。 ^[1]さらに、基礎となる誕生日問題を解決するために開発された他のアルゴリズムが適用されるリスクを軽減することを目的とした「アルゴリズム バインディング条件」があります。メモリレス検証にはハッシュと XOR が必要です。^[1]${\displaystyle n}$${\displaystyle i_{1},i_{2},...,i_{2^{k}}}$${\displaystyle H(i_{1})\oplus H(i_{2})\,\oplus \,...\,\oplus \,H(i_{2^{k}})=0}$${\displaystyle H(i_{1}\parallel i_{2}\parallel \,...\,\parallel i_{2^{k}})}$${\displaystyle d}$${\displaystyle H}$${\displaystyle 2^{k}}$

Equihash のパズルは、一般化誕生日問題に対する Wagner のアルゴリズムのバリエーションによって解決することが提案されています。(根本的な問題は、複数のリストではなく単一のリストを使用するため、Wagner によって定義された一般化誕生日問題とまったく同じではないことに注意してください。) 提案されたアルゴリズムは、大きなリストに対して反復処理を行います。^{[1] [3]}リストあたりのエントリ数が少なくなるにつれて、アルゴリズムの計算の複雑さはメモリ効率の高い実装に対して比例して増加します。Alcock と Ren ^{[4] は、} Equihash のセキュリティの主張に反論し、Equihash にはトレードオフ耐性の境界が実際には知られていないと結論付けています。 ${\displaystyle k}$${\displaystyle {\frac {1}{q}}}$${\displaystyle q^{\frac {k}{2}}}$

暗号通貨Zcash は、およびを使用して Equihash を実装します。 ${\displaystyle n=200}$${\displaystyle k=9}$

暗号通貨BitcoinGold は、およびで Equihash を実装しています。 ${\displaystyle n=144}$${\displaystyle k=5}$

• ステーク証明