Hashcash

提供: tezos-wiki
移動先: 案内検索

このページでは、ハッシュカードとその使用方法について説明します。

ハッシュキャッシュ[編集]

Bitcoinは、hashcash Proof_of_work関数をマイニングコアとして使用します。 CPU、GPU、FPGA、ASICのいずれのビットコイン・マイナーも、ブロックチェインの進化における投票として機能し、ブロックチェーンのトランザクション・ログを検証するハッシュ・キャッシュ・プルーフ・オブ・ワーカーを作成しています。

多くの暗号アルゴリズムと同様に、hashcashはHMACやRSA署名がプラグイン可能なハッシュ関数(一般にアルゴリズムハッシュの命名規則:HMAC-SHA1、HMAC- hashCash-SHA1(オリジナル)、hashcash-SHA256 ^ 2(ビットコイン)、hashcash-Scrypt(iter = 1)(litecoin)などのさまざまな関数でハッシュキャッシュをインスタンス化することができます。

歴史[編集]

Hashcash [機能証明]機能は、1997年にAdam Backによって発明され、匿名のremailerとmail2newsのゲートウェイ乱用、nymserversのnym name squatting(返信可能な仮名remailer一般的な電子メールのスパム対策や一般的なネットワーク不正使用の抑制などがあります。 Bitcoinの前に、Hotmail、Exchange、OutlookなどのMicrosoftとi2pの匿名性ネットワーク、mixmasterの匿名のremailerコンポーネント、およびその他のシステムによって、MicrosoftがSpamAssasinおよび(互換性のない形式で)「hashcash」を使用しました。 Hashcashはコインを採掘する方法としてHal Finneyのビットコイン前駆体RPOWでも使われました。同様の[Bit Gold proposal]ビットコインプリカーサも、ハッシュキャッシング鉱業の文脈で提案されていた[B-money Proposal]と[Nick Szabo]

ハッシュ関数の選択[編集]

元の1997年のアルゴリズムでは、ハッシュキャッシュはSHA1を使用しました。これはその時点で、これがdefactoであり、NISTが推奨するハッシュであり、以前のdefactoハッシュMD5が最近弱点の兆候を示し始めたからです。 2008/2009で指定/リリースされたBitcoinはSHA256を使用します。実際にSHA1が動作しなかった理由はありません.Hashcashはハッシュ・パーシャル・イメージの耐性プロパティ(ハッシュ・サイズまでのセキュリティ、SHA1の160ビット・セキュリティ)と、誕生日の衝突硬度(最大80ビットのセキュリティ)したがって、SHA1ハッシュは十分に大きいです。 128ビットセキュリティを提供する256ビットECDSAが使用されているため、Bitcoinは128ビットセキュリティに構築されています。たとえSHA1でさえ、誕生日の衝突であっても第2プリイメージではなく、若干の弱さを示すようになったので、SHA256が正確でより保守的な選択であることは決してありません。

二重ハッシュ[編集]

Bitcoinは2つのハッシュ反復(SHA256 ^ 2、すなわち "SHA256 function squared"と表記)を使用しています。これは、小さいが関連するSHA1ハッシュに対する部分的な攻撃に関連しています。 SHA1の誕生日攻撃への抵抗は、O(2 ^ 64)対O(2 ^ 80)のO(2 ^ 80)で2005年に部分的に壊れており、2017年の早い段階で実用化されています。ハッシュカードは、誕生日の攻撃に対してSHA1を強化する一般的な方法は、誕生日の攻撃に対して脆弱ではないということです。これまでのSHA256に対する類似の攻撃は存在しませんが、SHA256の設計はSHA1と同様であるため、おそらく二重SHA256を使用するアプリケーションでは防御的です。これはビットコインが行うことですが、ハッシュカードがプリイメージのセキュリティに依存する必要はありませんが、将来の暗号解析の開発に対する防御的なステップです。 SHA1への攻撃、そして原則としてSHA256のような同様のデザインの他のハッシュもNIST SHA3デザインコンペのための動機となっています。

将来のハッシュ[編集]

Bitcoinは、NIST SHA3コンテストが終了したら、今後、セキュリティアップグレード(例えば、SHA3の単一呼び出しとSHA256の二重呼び出しなど)としてhashcash-SHA3を採用することを検討する可能性があります。 SHA1ブレークからは明らかですが、SHA256は似たようなデザインで、以前は誕生日の衝突に対するハッシュ関数のセキュリティに関する誤解があり、SHA3ファイナリストはその問題を解決することを目指していました。 hashcash-SHA3の関連性の1つの側面は、NISTのコメントプロセス内で、プレイメージ攻撃に対するSHA3の耐性を128ビット(以前のハッシュと同様に完全なハッシュサイズ)まで弱めるという提案に関するいくつかの議論があることです。その動機は、ハッシュプラグ可能なアルゴリズムの一部が全長のプレイメージ耐性に依存していないことを根拠にして、パフォーマンスが少し向上します。この提案は、(以前のすべてのハッシュと比較して)非標準的なセキュリティの前提を作り出しているため、重大な否定的なフィードバックを得ているため、リスクが発生し、HMAC、RSA、DSA、ハッシュカードなどのハッシュプラグ可能なアルゴリズムSHA3​​がそれらと共に使用するのが安全であるかどうかを見るためにケースバイケースで再検査されること。フィードバックのバランスから、NISTがフィードバックを受け入れ、SHA3が完全な256ビットのプレイメージ抵抗を保持する可能性が高いと思われます。

暗号解読のリスク[編集]

hashcash-SHA3に切り替えることの現実的な問題は、既存のASICマイニングハードウェアをすべて無効にすることであり、セキュリティ上のリスクを除いて変更することはほとんどありません。 SHA1またはSHA256、またはSHA256 ^ 2がプレイメージ攻撃に対して脆弱であるという兆候はないため、新たな暗号解析の開発がなければ動機付けが欠落しています。さらに、SHA256 ^ 2が暗号解読攻撃により容易になったとしても、新しいアルゴリズムアプローチが何であっても鉱夫が使用を開始したとしても、それに適応するだけでは問題はありません。しかし、可能性のある副作用の1つは、より多くのメモリまたは事前計算のトレードオフを導入し、ASICを不採算にしたり、事前計算を行うために大きなリソースを持つ人に利点を与えることです。計算前の利点はおそらく、SHA3でハッシュを置き換えるのに十分な動機であろう。とにかく、SHA256で暗号解読攻撃に影響を与えるプレイメージが見つかるまで、これはすべて推測です。

ハッシュキャッシュ関数[編集]

ハッシュキャッシュアルゴリズムは比較的簡単に理解できます。このアイデアは、暗号化ハッシュのセキュリティ特性に基づいており、逆転しにくいように設計されています(いわゆる一方向またはプレイメージ耐性)。あなたはxから安くy = H(x)を計算することができますが、yが与えられたxを見つけるのは非常に難しいです。完全なハッシュ逆転は、計算上実行不可能なブルートフォース実行時間をO(2 ^ k)とし、ここでkはハッシュサイズ、例えばSHA256、k = 256であり、プリ画像が見つかった場合、 1つのハッシュを計算するので、完全なプレイメージマイニング(計算では実行不可能)と検証(1回のハッシュ呼び出し)の間に大きな非対称性があります。

第2のハッシュ・プリ画像は、y = H(x)であるハッシュyの1プリ画像xを与えたことを意味し、タスクはy = H(x ')となるようにハッシュy:x'の別のプリ画像を見つけることである。これは、H(x)= H(x ')となるような2つの値x、x'を見つける誕生日の衝突と混同してはならない。これははるかに低い仕事O(sqrt(2 ^ k))で行うことができる。 = O(2 ^(k / 2))。これは、多くのH(x)値を計算し、一致するペアが見つかるまでそれらの値を保存することによって処理を続けることができるからです。それには多くのメモリが必要ですが、メモリと時間のトレードオフがあります。

ハッシュキャッシュプロトコル(1997)のバージョン0は部分的な第2の事前イメージを使用したが、後のバージョン1(2002)では、πまたは任意の0 ^ kの数字ではなく、かなり選択された文字列の部分イメージを使用する0文字列)は便宜上使用されるので、H(x)= 0となるようなxを見つけることです。これも同様に公平であり、第2の部分プレイメージを有する2つを検証するためにハッシュ呼び出しを1回だけ必要とする。 (この最適化はHal Finney&Thomas Boschlooが独自に提案したものです)。作業を容易にするために、部分プレ画像の定義は、H(x)/ 2 ^(nk)= 0となるようなxを見つけることであり、ここで/は除算の整数商であり、nはハッシュ出力のサイズSHA256の場合n = 256ビット)、kは作業係数です。つまり、ハッシュ出力の最初のkビットは0です。したがって、例えばk = 20の場合、平均100万回の試行が必要です。実際にはプレイメージではなく部分的に一致する出力ですので、部分的な出力マッチングでプレイメージと呼ばれる可能性がありますが、プレイメージの一部は事実上その短所となります。

目的を追加[編集]

もしy = H(x)からの部分プレ画像xがランダムであれば、それは無意味な仕事の断絶された証明であり、誰もあなたが仕事をしたのを誰も見ることができるが、異なるサービスに対して同じ作業を再利用することができます。作業証明がサービスまたは目的に結びつくようにするために、ハッシュはサービス文字列sを含まなければならないので、仕事はH(s、c)/ 2 ^(n-k)= 0を見つけるようになる。これが真になるまで、鉱夫はカウンターcを変えます。サービス文字列は、Webサーバーのドメイン名、受信者の電子メールアドレス、ビットコインブロックチェーン元帳のブロックをビットコインにすることができます。

もう1つの問題は、同じサービス文字列を使用して複数の人がマイニングしている場合、同じxで始めることはできません。同じ証拠で終わることもあります。また、同じ作品を複製した人は、それが仕事なしにコピーされている可能性があるので、それを最初に提示する人は報酬を受け、他の人は自分の仕事が拒否されることに気付くでしょう。このように無駄な作業をしないようにするためには、ランダムな開始点が必要であり、したがって、x(nは任意の整数)を見つけるためにH(s、x、c) 2人のユーザが悪意を持ってまたは偶然に同じ地点から開始することを統計的に不可能にする)cは変化するカウンタであり、sはサービスストリングである。

これは、hashcashバージョン1とbitcoinの機能です。実際にビットコインでは、サービス文字列はコインベースであり、コインベースにはレシピエントの報酬アドレスと、ブロック内で検証するトランザクションが含まれています。実際にBitcoinにはランダムな開始ポイントxは含まれていません。このランダムな開始ポイントの目的の衝突を避けるためのランダム化係数として報酬アドレスを再使用します。コインベースに16バイトのスペースが保存されます。プライバシービットコインについては、成功したブロックごとに異なる報酬アドレスを使用することを鉱夫に期待してください。

もっと精密な作業[編集]

元々提案されているHashcashは2kの整数であり、これは難易度が2の累乗でしかスケーリングできないことを意味します。これは、16進/ 2進数で0を数えるだけで、事前の使用に適しています。 (ハッシュキャッシュの選択肢の多くは、シンプルさによって動機付けられています)。

しかし、ビットコインは、より正確で動的な作業の制御(10分のブロック間隔を正確に目標とする)を必要とするため、kを分数(浮動小数点)に変更するので、作業はH <s、x、c <2 ^(nk)は、kが整数の場合に等価です。 Bitcoinは、target = 2 ^(n-k)を定義するので、H(s、x、c)<targetを見つけるより簡単に作業を書くことができます。当然のことながら、ブロック時間は実際には非常に高い分散を有するが、平均は部分kの導入によってさらに正確に目標とされる。

仕事、難易度および暗号のセキュリティ[編集]

Hashcashは、DESがk = 56ビットのセキュリティを提供し、ECDSA-256がk = 128ビットのセキュリティを提供する標準的な暗号セキュリティ用語O(2 ^ k)でセキュリティマージンを表します。仕事とセキュリティを表現することは、セキュリティの比較を行うのにも役立ちます。

Bitcoinの仕事率はGH / secで[1]と呼ばれます。ターゲットブロックの間隔は10分でlog2(ハッシュレート* 600)という暗号セキュリティに変換できるため、2013年11月のハッシュレートは4 petahash / sec、ビットコインのhashcash-256 ^ 2は62ビットです(ダブルハッシュの場合+1を含む)。

Bitcoinは、現在のネットワークハッシュレートでブロックが10分ごとに検出されることが期待されるように、(相対的な)困難という新しい概念を定義しています。これは、2 ^ 32反復の最小作業単位に相対的に表されます(ビットコム実装レベルの詳細のために、おおよそ技術的に最小限の作業は0xFFFF0000です)。 Bitcoinの難しさは、log2の暗号セキュリティに変換するのが簡単です:k = log2(難しさ)+32(または高精度log2(困難* 0xFFFF0000))。難易度は難易度=目標/ 0xFFFF0000という単純な目標に関連しています。

おそらくlog2スケール(petahash /秒は16進数の1秒あたりのハッシュ数16文字)で高い問題に対処する方が簡単で、他の暗号セキュリティステートメントに匹敵します。たとえば、EFFの "deepcrack" DES crackerプロジェクトでは、56時間で56鍵のDES鍵を破棄して56ビットDES 1998年には25万ドル(ボランティアの設計時間)を要したこともありませんでした。比較すると、ビットコインネットワークは、10分ごとに62ビット(ダブルハッシュに対して+1を含む)を行い、深いクラックよりも537,000倍強力であり、SHA256ではなくDESに焦点を当てると、9秒でDESキーがクラック56時間。

マイナープライバシー[編集]

したがって、原則として、マイナーは、プライバシーのために、各ブロックに対して異なる報酬アドレスを使用し(カウンタを0にリセットする必要があります)。なぜ聡の初期の採掘されたビットコインが潜在的にリンクされていたのか、彼は報酬アドレスを変更したが、成功した鉱山ごとにカウンタをリセットするのを忘れていた。実際にビットコインでは、カウンターも隠されていなければ、あなたの努力水準が明らかになります。また、コインの所持を示唆する鉱業力がたくさんある場合は、 Bitcoinはnonceとextra-nonceでこれを行います。ノンスは0から始まりますが、余分なノンスはランダムです。これらはともに、証明に入った努力の量を隠している無作為化カウンターを形成しているので、誰がそれが頑張ったか不運な鉱夫であるか、非常に幸運だった弱い鉱夫であるかは誰にも分かりません。

さらに、採掘プールが導入されている場合、現在の採掘プロトコルが行うすべてのユーザーに対して同じ報酬アドレスを使用する場合、ユーザーが作業をやり直すリスクがあります。ユーザーが作業をやり直すのを避けるために、鉱夫はユーザーが行うために定義された作業を引き渡します。しかし、これは不必要な通信往復をもたらし、初期のプロトコルバージョンでは、プールが実際のブロックを鉱山に送るという決定の要因となった可能性があります。つまり、鉱山者は独自のブロックを検証していません。プールオペレータに、ビットコインネットワークのセキュリティを低下させます。より最近のマイニングプロトコルバージョンでは、ユーザーが独自のブロック定義を追加することができますが、作業割り当てを引き渡すために不必要にラウンドトリップが発生します。新しいプールマイニングプロトコルには、選択されたextraNonceが選択されているため、これはランダムな開始要因として機能するため、実際にプールに作業割り当てを行う必要はなく、プールには静的に公開されたアドレスがあり、彼らが選んだどんなサイズでも、それをUDPパケットとしてプールに提出します。 (秘密が鉱山者によって要求されている場合、BIP 32のパブリック派生方法を使用して、ノードが鉱山作業で暗号化されたメッセージを介して鉱夫に伝えることを許可することができます。

仕事の証明の秘密[編集]

Scrypt証明の仕事について話すのは誤解です。 Scryptは、作業証明機能としてではなく、拡張されたキー導出機能を意図していますが、高い反復で計算するのは設計上高価ですが、公に監査可能な作業証明の作成には使用できません検証と同じように、作成と同じです。

Scryptの内部ハッシュ関数を持つHas​​hcashは、hashcash-Scrypt(1)と表示されます。 Colin PercivalによるScryptは、ユーザーが選択したパスフレーズをキーに変換するためのキー導出機能です。それは(事前計算/レインボーテーブル攻撃を防ぐために)塩漬けされ、パスフレーズ研削を遅くするためにハッシュが何度も繰り返されます。 Scryptは、デファクト標準のパスフレーズキー導出関数PBKDF2(内部でHMAC-SHA1を使用する)と目的が似ています。差別化要因とPBDF2ではなくScryptを選択する理由は、Scryptの内部ハッシュがより多くのメモリを使用するため、パスワード研磨でのGPU(または理論的なScrypt ASIC / FPGA)の利点がCPUに比べて少なくなるからです。

これはScryptのキーストレッチ機能を使用しないため、マイニングは実際にはScryptを直接使用せず、内部のScryptハッシュ(反復パラメータを1回の反復に設定することによってアクセスされます)のみを使用します。したがって、暗号化キーをユーザーのパスフレーズからビットコインウォレットを暗号化するなどのキー保護の通常の使用とは異なり、Scryptのキーストレッチ機能は硬度に寄与するためにまったく使用されていません。 Scryptのキーストレッチングをマイニングに使用できないのは、同時に同じ要因で検証するのがよりコストがかかるためです。このハッシュキャッシュの亜種は、hashcash-Scrypt(iter = 1、mem = 128KB)またはhashcash-Scrypt(1)に短縮することができます。他の主要なscryptパラメータは、使用されるメモリの量(通常128kB)を示します。

地方分権:hashcash-Scryptとhashcash-SHA256[編集]

128kB Scryptメモリフットプリントは、ユーザによるASIC機器への限定されたアクセスまたは所有権から生じるマイニングパワーの集中化に対して、litecoinがおそらく脆弱になります。 hashcash-SHA256 ^ 2は非常に単純なので、彼の個人貯蓄や小さなKickstarterプロジェクトを持つ熟練した人は、チップ製造業者と一緒に設計して注文することができるという反論があるため、議論の余地があり不明です。このシンプルさは、多くの人がそれを行い、ASICを利用できるようにすることを確実にします。逆に、ハッシュキャッシュ-Scrypt(1)ASICを作成するのは、比較するといくぶん難しいです。したがって、リコーコドンは、集中的な商業エンティティがより高速であるが所有権を持たない市場で入手可能なhashcash-Scrypt(1)litecoin GPUマイニングを不採算にするASIC。

また、hashcash-Scrypt(1)がASICの実装とGPUの速度をハッシュキャッシュ-ShA256 ^ 2よりも遅くする必要があると考えられることも考慮してください。これは、128kBのRAMで占められているダイ領域が各Scrypt(1)コア専用でなければならないと考えられているため、1チップ当たりのScryptコアの数が減少するという主張が理由で主張されています。ただし、Scrypt(1)は実際には時間メモリのトレードオフを防ぎませんので、実際には安全にメモリに固執するわけではないので、実際には内部ラウンドの計算を繰り返してメモリ要件を減らすことができます。したがって理論的には、より多くの計算では、最小限のメモリで、より多くの作業で、Scrypt(iter = 1、mem = 128kB)を実装するのに高価です。ハードウェアでは、使用するメモリの最適量を見つけるために時間メモリのトレードオフが最適化され、最適な量は128kB未満になる可能性があります。

Scrypt(mem = 128kB)の反復の検証コストが2つのSHA256ハッシュよりもはるかに高いため、Hashcash-Scrypt(1)はhashcash-SHA256 ^ 2に比べて不利になります。これにより、litecoinブロックチェーンの検証では、すべてのフルノードでより多くのCPUとメモリが使用されます。ただし、検証の主なCPU作業は、ブロック内の複数のトランザクションのトランザクションごとのECDSA署名の検証です。 1つのECDSA署名でも、ブロックごとに1回実行される1つのScrypt(1)検証よりも遅く、ブロック内で検証するために多くのトランザクション(およびECDSA署名検証)があります。