暗号通貨での作業証明の進化の簡単な歴史。 パート2

記事「 暗号通貨の仕事の証明：簡単な歴史 」 の翻訳に注目してください。 パート2 » Bytecoin.orgの Ray Patterson。



「暗号通貨の仕事の証明の進化の短い歴史。 パート1」はこちらです。

交配

2013年夏の半ばまでに、100以上のアルトコインがすでに使用されていましたが、ここ数か月でほぼ半分が現れました。 言うまでもなく、ほぼすべての「新人」はLitecoinのフォークであり、scryptを使用していましたか？ シーズンのもう1つのトレンドは、PPcoinの最新のProof-of-Stakeでした。そのため、scryptとPoSの組み合わせは、「初心者アルコイナーの標準セット」と呼ぶことができます。



このようなscryptの（定量的な）人気とBitcoinの複雑さの指数関数的成長の始まりは、単純な考えにつながりました：scrypt-ASICは、利益が出るとすぐに2番目に現れるでしょう。 そして、巨大な11月のバブル（ビットコインが1200ドルに達したとき）は膨らみさえしていませんでしたが、新しいPoW関数の検索が再び始まりました。



標準ハッシュ関数を多様化するにはどうすればよいですか？ たとえば... 別の標準ハッシュ関数！ Sifcoinは、 SHA3​​コンテストのファイナリストであるBlake、BMW、Groestl、JH、Keccak、Skeinの役割を引き継いだいくつかの一般的な機能を連続的にハッシュ化するというアイデアを最初に提案しました。 考え方は非常に単純です。6つの根本的に異なるアルゴリズムは、6つの異なるASICチップであり、一見すると非常に高価です。 さらに、あるアルゴリズムでバックドアが見つかった場合（必ずしもすべてを壊すわけではありませんが、「最初の多数ゼロ」問題をより早く解決する方法を学習します）、スキーム全体が多少なりとも保持されます。



先駆者は必ずしもすべての栄光を手に入れるとは限りません。結局、この6ハッシュアルゴリズムは、Sifcoinの最初の分岐点であるクォーク通貨で人気（および名前）を獲得しました。 結論：製品に接頭辞「sif」を付けないでください。 時間の経過とともに、12個または2個のアルトコインがQuarkから分離し、そのうちの1つは人気の「父」を大きく上回りました。それはダークコイン（現在はDASHと呼ばれています）です。 その中の新しいPoWはX11と呼ばれ、ご想像のとおり、使用されるハッシュ関数の数が異なりました。 彼は根本的に新しいものを提供しませんでした（ラウンドの順序を除く）、したがって、X11の普及（スクリプトの約2位）は、他の多くの変更があった（やや賢明な、ある程度の）DarkCoin自体の成功に関連付けられるべきですそうでもない）。



X11は2014年の初めに登場し、最初はCPUのみで動作していたため、誰もが非常に満足していました。 しかし、4月にDarkCoinの複雑さが倍増し、GPUマイナーの外観に合理的な疑いが生じました。 誰も認識していなかったため、このようなソフトウェアのオープンな実装をめぐる競争が発表され、お金が集められました。1か月後、新しいGPUマイナーでハッシュレートはすでに1桁大きくなりました。 CPUの約5倍の効率であることが判明しました（scrypt-10倍）。



これまで、X11とQuarkのテーマには多くのバリエーションがあります。 独自の一意の名前を持つものもあります：X14、X15 ...同時に、アルゴリズムが言葉の意味でASICにまったく耐性がないことは誰にとっても明らかです。 1つではなく11の異なるハッシュを計算することは、大まかに言って、パイプラインを11倍長くすることです。 言い換えれば、鉄片を開発することの見返りの価格閾値は数回しか動いていません。



さまざまなマーケティング手法のおかげで、個々のSHA-3ファイナリストがソロバージョンで人気を博しました。 たとえば、Keccak自身、別名SHA-3自身。 さて、ここではすべてが明確になっています：「SHA-2のように、より良いだけです！」。 つまり、開発と生産開始に少なくとも1年かかるという事実を除いて、ASICに立ち向かうという特別な考えはありませんでした。 しかし、一方で：私たちは本当に新鮮でモダンな標準を持っています！ また、Skeinアルゴリズム（おそらくBruce Schneierのファン）を使用したと思われる、特別なSkeinconコインも登場しました。

多様な種

進化が一巡し、暗号通貨の考え方は再びメモリに縛られたアルゴリズムに戻りました。 たとえば、scryptを使用します。アルゴリズムは良好で、パラメーターは不適切です。



最も可能性が高いのは、静的な暗号化パラメーターがまったく異なる暗号通貨が出現しなかったため、何らかの思考作業が行われたためです。 しかし、動的メモリを使用したアイデアは、2つのバージョンですぐに実装されました。

1. Scrypt-n。 Tenebrixおよびその他のLitecoinで選択された3つのscryptパラメーターを思い出してください：N = 1024、r = 1、p = 1。 後者は並列化の可能性の原因であり、これは必要ありません。 Nとrは必要なメモリサイズを増やし、rはSalsa20ミキシング関数の呼び出し数も増やします。 この点に関して、NのCPU /メモリコスト係数はNよりも大きくなっています。この点に関して、Nを定期的に2倍に増やして、アルゴリズムがより多くのメモリを使用するように決定しました。 したがって、発売時には、Vertcoin [9]は512Kb（N = 4096）を必要とし、1年後には食欲が1024Kbなどに増加します。 作成者によると、GPUマイナーを書き換えることは何もありませんが、毎年新しいASICを作成する人はいません。
2. Scrypt-jane。 Nを増やすという考え方は同じですが、プロセスは特定のスケジュールに従って行われませんが、現在の時間に非線形に依存する擬似ランダム式によって規制されます。 また、Nは単調に増加していますが（大丈夫、「減少しません」）、再集計間の期間はより多様なシリーズです（6.3、3、9、3、24、12、36 ...）。 さらに、scrypt-janeは内部でいくつかのミキシング（Salsa20 / 8、ChaCha20 / 8およびSalsa6420 / 8）とハッシュ関数（SHA2、BLAKE、Skein、Keccak）を使用します。

もう1つの根本的に異なるメモリバインドPoW関数は、BitSharesに実装されたMomentumでした。 それは非常に簡単です：

1. データDに署名したいとします。まず、H = Hash（D）を取得します。Hash（）は暗号化ハッシュ関数です
2. BirthdayHash（A + H）= BirthdayHash（B + H）のようなAとBの異なる値を見つけます。ここで、BirthdayHash（）はscryptのようなメモリバウンド関数です。
3. ハッシュ（H + A + B）<TargetDifficulty（読み取り-n個のゼロで始まる）の場合、それが勝利です。 それ以外の場合は、手順2に戻ります。

ご覧のように、主な作業はステップ2で2つのハッシュの衝突を検索することです。もちろん、256個の一致するビットではなく、それより少ないビットを見つける必要がありますが、これも困難なタスクです。 たとえば、最初の64ビットの一致を見つける必要がある場合、2 ^ 64のハッシュ操作が必要になります...



スーパーヒーローが私たちの助けになります： 誕生日の逆説 。 その本質は、特定のセット間の衝突を見つける確率が要素の数とともに二次的に増加することです（セット内の一意のペアの数もそのように増加するため）。 実際には、これにより次の評価が得られます。50％の確率で64ビットの衝突を見つけるには、約2 ^ 32ハッシュ（18クインティオンではなく40億-そんな節約）を生成する必要があります。



「通常の」PoWでは動作しないのはなぜですか。なぜなら、そこにも本質的に衝突の検索があるからです。 ここでのキーワードは「任意の」競合です。 ビットコインでは、特定のパターンと一致するものを見つける必要があります。最初はN個のゼロで、モメンタムでは、最初のビットはすべてN個一致する必要があります。



時間とメモリの間には明らかな妥協点があります。 作成者によると、アルゴリズムはスレッドごとに約2GBのメモリを使用する必要があります。 通常のコンピューターでも複数の並列検索を実行できます。 同時に、ASICの運命は、その強さは記憶されていませんが、見た目とen望だけにとどまっています（まあ、またはより速く二乗する）。



このアプローチには1つの欠点があります。 以前のすべての作業証明アルゴリズムは「即座に」機能しました。 実際には、彼らは破産していたという意味で、それぞれの試みには一定の時間がかかり、彼らはすべて成功のチャンスが同じでした。 検証済みの各ハッシュは、2ˆ256の面を持つキューブを投げるようなもので、いつでも「別のサイコロを取り」（別のブロックで作業を開始）、チャンスは変わりません。 これは鉱夫にとって何を意味するのでしょうか？ これは、ブロックに含める新しいトランザクションを受け取った場合、ハッシュ構造を更新する必要があることを意味します（「別のキューブを取得」）。 これには一瞬かかりますので、損失は無視できると言えます。 Momentumの場合、すべてがそれほど単純ではありません。 次のハッシュ処理と新しいハッシュのグローバル2GBテーブルへの追加は、以前のものよりも成功する可能性が高くなります！ その後、ブロックヘッダーを更新し、最初からテーブルの構築を開始することは非常に不利であることは明らかです。 ダイスを振るたびに解決策を見つける機会が増えている場合は、新しいダイスを取らないほうが有利です。 つまり、最終的に、Momentumマイナーが新しいトランザクションを受け入れて進捗を「ダンプ」することは有益ではありません。最終的に、このブロックで作業を開始する前に送信されたトランザクションはブロックに分類されます。 Bitokinの場合、これは平均トランザクション確認時間が10分から20に増加することを意味します。

鉱物

Apartは2013年夏に登場した唯一のPoW機能です。 それに移る前に、一般的に1つの問題を作業の証明で実現しましょう。 これは誰にとっても問題にならないように（またはその逆も）行われないように、すぐに予約します。 多くの人が問題と考えるものについてです。



この作業はすべて無駄です！ どこにも、暗号通貨の内部を除いて、誰もこれらのハッシュを必要としません。 もちろん、 見つかった最小のハッシュを印刷して壁に掛けることができますが、実用的ではありません。 この作業が有用であるかどうかについての哲学的な議論は行いませんが、有益なPoW関数を思い付くのは簡単な作業ではないことに注意してください。



しかし、1つが見つかりました。 SunnyKingの開発者（彼がProof-of-stakeスキームを発明した（または少なくとも最初に実装した））は、次のスキームを公開しました：行われた作業の証拠は、いくつかの特性を満たす素数のチェーンが見つかりました。 より正確には、第1種または第2種のカニンガムシーケンス、またはそれらの組み合わせ（いわゆる双双素数 ）でなければなりません。



1つ目は、これが便利な理由です。 もちろん、これらの素数は小さくありません（さもなければ、それらを見つけるのは非常に簡単です）：10進表記で数百桁のオーダーです。 ただし、RSA暗号化ではこれで十分ではありませんが、そこで乱数を使用する必要があります。 カニンガムチェーンは、（理論的には）数論の次の幕を開くことができる奇妙な数学的構造です。 最終的に、公開鍵暗号方式が出現するまで、この領域全体は「美しく、役に立たない科学」とみなされていたため、そのような「オリンピアード」の性質であっても、努力する価値はないと考えられます。



次に、プライムと暗号通貨ブロックを正確に関連付ける方法について説明します。 チェーンが数字Pで始まると仮定します。（nonceフィールドが列挙される）ブロックヘッダーのハッシュは、整数として解釈されます。 そして、その数はP-1またはP + 1の約数でなければなりません。 ネットワークの複雑さは、必要な素数のチェーンの長さです（7〜11の範囲）。 それは、一般に、全体のアイデアです。 したがって、ランダムに見つかったチェーン（または他のブロックの誰かのチェーンでさえ）を使用して、独自のヘッダーでの作業を証明することは不可能です（つまり、非常に困難です）。



2つの欠点があります。まず、プライムコインの問題を解決する簡単な方法があるかどうかわかりません（この暗号通貨は呼ばれています）。 ハッシュでは、すべてが多かれ少なかれ明確です：暗号化ハッシュ関数のプロトタイプを見つける攻撃はほとんど絶望的です（少なくとも、すべての暗号化の柱はこの仮定に基づいています-そして神はそれを崩壊させません！）、既存のハッシュのブロックを拾う可能性はありません。 しかし、Primecoinブロック（すべてのP-1またはP + 1因子が私たちに適している）について同じことを言うことは、すでに困難です。



第二に、マイニングの複雑さ。 すでに述べたように、それはチェーンの長さに比例します。 ただし、長さは整数であり、小数部の変化を考慮していません。 したがって、9.0から9.99への複雑さの変化は完全に目に見えませんが、9.99から10への変化は、全体のハッシュレートと新しいブロックの出現速度にすでに大きな影響を与えます。



さらに、この機能は明らかに、コンピューターのCPUパワーのみを使用し、メモリーは使用しません。 長い間、彼女はGPUマイナーを持っていませんでしたが、彼が現れたとき、プライムコインはアンチASICの聖杯ではないことが明らかになりました。 おそらくそれが彼が二、三のフォークで自分のニッチにとどまり、彼のPoW機能がポピュラーにならなかった理由です。

パワーサピエンス

最後に、暗号通貨用の系統発生PoWツリーのまったく異なるブランチであるCryptoNightとCuckooCycleを検討します 。これらは、CPUのみのアルゴリズムとして、scryptの失敗直後に他のブランチと並行して開発を開始しました。









CryptoNightは、CryptoNoteコードのハッシュ関数の名前です（混乱しないでください！）。これには、Bitcoinとのその他の多くの違いが含まれています（これはまったくフォークではないという事実から始まります。 CryptoNoteの暗号通貨自体はありませんが、このテクノロジーに基づいて構築されたものがいくつかあります。Bytecoin、Monero、DigitalNoteなど。それぞれ独自の違いがあれば、PoW機能はすべての人に共通です。



CryptoNightは、「ランダムクエリが行われる大きなデータテーブル」に関するscryptの一般的な考え方を使用します。 ただし、作成者は、線形妥協「時間」-「メモリ」に関連する欠点に注意しました。 scryptでは、メイン（2番目）レイヤーは、前のブロックに基づいて新しいデータブロックをそれぞれ作成します。 したがって、たとえば、Nの2つおきのブロックのみを保存する場合、50％の場合、再度再カウントする必要があります。 配列へのこのようなランダムアクセスはN個あるため、メモリの半分を節約して、ブロックのN + 1 / 2N = 150％、つまり1.5倍だけを計算することがわかります。 同様に、ブロックを3つおきに保持する場合、33％の場合、33％でこれに気付くことはありません-33％で1つの余分なブロック、2つの余分なブロックを再計算します。 つまり、作業全体：N + 1 / 3N + 1/3 * 2N = 2N = 200％。 合計すると、すべてのデータの1 / sのみを保存すると、作業の合計量が（s-1）/ 2倍だけ増加することが計算されました（おそらく、それがscrypt-ASICの仕組みです）。



この点で、CryptoNightには3つの基本的な違いがあります。

1. 次のブロックは、以前のすべてのブロックに基づいて計算されます。 したがって、たとえば、1つおきのブロックを削除すると、パスを復元するために、1つのブロックではなく、以前のすべてのブロックを一度に再カウントする必要があります。
2. データ配列へのアクセスは、読み取りだけでなく書き込みでもあります。 したがって、各要素には「2番目の次元」が表示されます-時間。 再カウントはさらに時間がかかります。
3. 最後に、配列の呼び出しの総数は、配列内の要素の数よりもはるかに多く（2 ^ 20対2 ^ 15）、つまり、結果の配列は、サイクルの終わりまでに認識できないほど変換されます。

さらに、64ビット操作（乗算、加算）および混合機能としてのAES暗号化が内部的に使用されます。 これは、組み込みの関連命令（およびGPUガーデンの石）を備えた最新のプロセッサの方向に向いています。 CryptoNightが必要とする合計メモリは2 MBです。 およそコアあたりのL3キャッシュのサイズ。 これがASICの到達不可能な高さであるとは言いませんが、それでもコストバーは非常に高いです。



一般的に、CryptoNightは非常に効果的な実用的なアルゴリズムとして特徴付けられます。もちろん、GPUマイナーがありますが、古いプロセッサ（32ビットまたは小さなキャッシュ）と比較した場合のみ深刻な利点があります。 判断できる限り、そのすべての詳細は、従来のコンピューター（その数十億）の実際的な有効性を正確に目指しています。



CuckooCycleは、正反対です。 まず、理論的な情報ベースがあります。 理論だけで開発されたという意味ではなく（現時点ではそのような暗号通貨はありません）、その信頼性は情報理論的な問題を解決する複雑さに基づいているという事実にあります：二部グラフでのサイクルの検索。 基本的に、すべての最新の公開鍵暗号は同じ方法で設計されています。

主なアイデア（グラフ理論自体に入らない場合）はMomentumと同じです-一定量のメモリを使用することで、この問題を解決するための最適なアルゴリズムが得られます。 計算操作は最小限に抑えられるため、このメモリへのアクセスにはメイン時間がかかります。 さらに、ソリューションの検証はもちろん、はるかに高速です。



質問できる主な質問は次のとおりです。説明されているアルゴリズムは本当に最適ですか？ 明日、メモリをあまり使用しない、より効率的な別のソリューションを提供するトリッキーなCS記事はありますか？ 基本的に、これはCuckooCycleとCryptoNightを区別する主なものです。