この記事はZK-SNARKs - Create Verifiable Trust, even against Quantum Computersを和訳したものです。
注：ゼロ知識証明またはZK-SNARKについてよく知らない場合は、このブログのパート1（https://cryptodigestnews.com/digital-identity-privacy-and-zero-knowledge-proofs-zk-snarks-3d092b509990）およびパート2（https://medium.com/coinmonks/zk-snarks-a-realistic-zero-knowledge-example-and-deep-dive-c5e6eaa7131c）を読むことをおすすめします。
ZK-SNARKについてはカバー出来たとして、これからZK-SNARKのいくつかの問題を解説し、ゼロ知識暗号（zero-knowledge cryptography)における最近の革新について議論していきましょう。：ZK-STARK(Zero-Knowledge Scalable Transparent ARguments of Knowledge)
ZK-SNARKにはいくつかの根本的な問題があり、ブロックチェーンやその他の実装可能な領域でのゼロ知識暗号の活用が減少しかねません。
- Trusted Setupがきちんと行われてない可能性があります（ZK-SNARKシステムを使用する場合、Trusted Setupの段階においてきちんと情報が破棄されており、安全であるという大前提があります。）
- ZK-SNARKのスケーラビリティを向上させることは可能です。しかし実行時間が長くなるとそれだけ、プルーフを生成・検証するために必要な時間が増えることになります。
- ZK-SNARKは量子コンピュータからの攻撃に対して脆弱です。
これらの問題を噛み砕いて、ZK-STARKと比較してみましょう。
Trusted Setup
もし、政府や力を持つ企業がZK-SNARKシステムの設定に関わる関係者にインセンティブを与えて設定パラメータを共有しようとした場合、どうなるでしょうか？彼らが共有に成功した場合、信頼できると広く知られているシステム内で虚偽のプルーフを生成することができます。例えば、ZK-SNARKを使用しているブロックチェーンで国の大統領投票が行われた場合、彼らにとって設定パラメータを見つけることは大きなインセンティブになり得えますし、選挙結果自体も改ざんしかねません。彼らは偽のプルーフを作成することにより、選挙を意図した方向に傾けることができるでしょう。ZK-SNARKアプローチの最大の問題は、ユーザーが設定フェーズそのものとシステムを設定する人らに関して、暗黙のうちに信頼する必要があることです。システムのユーザーは、セットアップ段階でセットアップフェーズが妥協されたかどうか、または将来のある時点で実際には実際にはわかりません。したがって、このような場合は、ユーザーが暗黙のうちにシステムの設定に関係する当事者を信頼する必要がないシステムの場合、ドアは開いたままです。システムを迂回するためにインセンティブが高いシステムが使用される場合、それを回避する方法を見つけようとする人が存在します。
ZK-STARKでは、外部の信頼できる設定フェーズはなく、使用されるランダム性はパブリックなものです。パブリックなランダム性を利用することは、人々がゼロ知識証明システムを信頼する上で非常に重要です。そうしないと、強力な企業や政府が設定パラメータを取得して嘘のプルーフを生成する可能性があります。第三者の信頼できるセットアップフェーズがなく、パブリックで検証可能なランダム性が使用される場合、ZK-STARKシステムは信頼できるものになります。
スケーラビリティ
ブロックチェーン界隈の技術的課題に注意を払う人々の中で議論の中心になっているのはスケーラビリティです。このブログの記事の範囲外ですが、ブロックチェーンをスケールする方法は沢山あり、それらはすべてトレードオフを伴います。 ZK（zero-knowledge）プルーフシステムの場合、システムのスケーラビリティは、広く普及し続けていく上で最も重要です。 ZK-STARKは、ZK-SNARKよりもはるかに高いスケーラビリティを見せてくれます。 ZK-STARKとZK-SNARKの計算との複雑さを、スケーラビリティに関連する4つの異なるカテゴリ（ZK-STARKのホワイトペーパーを活用した結果）に分けて考えてみましょう。
- 演算回路の複雑さ（演算回路とは加算と乗算を含む多項式を計算するためのスタンダードな手段です。）：ZK-SNARKとZK-STARKシステムにおいて、ZKプログラムを作成するコードは、まずいくつかの回路に分割しそれから計算されるように構築されます。実際、回路のシンプルさは、その計算効率に比例します。以下のチャートにおいて、計算の複雑さは基本的にプルーフを生成するための計算量とその複雑さに等しい。 （以下のチャートは、乗算を中心としたシステム全体の複雑さに基づいています;パラメータ設定については、ZK-STARKホワイトペーパーの11ページを参照してください）。
- 通信の複雑さ（2つ以上のパーティーに分散された問題を解決するために必要な通信の量として定義されることが多い）：計算量が大きくなると、ZK-SNARKの通信の複雑性も線形に増加する計算量が増えるにつれてわずかにしか成長しないZK-STARKは、ZK-STARKとZK-SNARKの大きな利点です。設定フェーズの後、SNARKは現在、を検証する際に、STARKよりも通信の複雑さが少ない。
- 複雑さの証明：計算量が大きくなるにつれて、ZK-STARKはZK-SNARKの10倍近くまで高速になります。
- 検証者の複雑性：ZK-SNARKSは、計算量が増えるにつれて線形に増えていく傾向があるのに対して、ZK-STARKS は初期設定でもわずかにしか増えません。設定フェーズの後、証明を検証するために必要な時間に関しては、STARKよりもSNARKの方が少なく済みます。（ STARKは検証に50〜100msかかりますが、SNARKは〜10msで済みます。）
以下は、ZK-STARKホワイトペーパーにおける、ZK-STARKS・ZK-SNARK間のベンチマーク分析の簡単な図です。
Communication Complexity の図が入ります
上記の簡略化されたベンチマークは、ZK-STARKに必要な通信がZK-SNARKよりもはるかに遅くなることを示しています。レベル1〜レベル6は、演算回路の複雑さ（乗算のレベルを指しており、それぞれのレベルは前のレベルの約55倍です）を指します。通信のサイズが100GBを超えるとレベル5と6は表示されません。 ZK-SNARK処理後確認時刻とは、SNARKが検証された時刻のことです。
上記の簡略化されたベンチマークは、プルーフを生成するZK-STARKの時間が、基礎となる証明が複雑さを増すので、ZK-SNARKよりもはるかに遅く上昇することを示しています。レベル1〜レベル6は、演算回路の複雑さ（乗算のレベルを指しており、それぞれのレベルは前のレベルの約55倍です）を指します。レベル6は10時間を超えると表示されません。）
上記の簡略化されたベンチマークは、重要なプルーフの複雑性が増すとZK-SNARKに比べてZK-STARKの所要時間の方が非常にゆっくりと上昇することを示しています。レベル1〜6は、演算回路の複雑さ（乗算のレベルを指しており、それぞれのレベルは前のレベルの約55倍です）を指します。レベル6は10時間を超えると表示されません）。 ZK-STARKおよびZK-SNARK処理後検証時間は、STARK / SNARKが検証された時点を示します。
チャートデータソース：ZK-STARKホワイトペーパーチャートはホワイトペーパーから再現されています。ZK-SNARKとZK-STARKの比較のために簡略化されています。
プルーフシステムでは、証明者がその声明を検証したいと思う人に真実であると主張したいという声明があります。例えば：
証明者のステートメント：アリスは自分がAcme Bankの銀行口座の所有者であることを証明したい。
（ポスト＃2のコードロジックで分割されたステートメント）をゼロ知識回路が計算してプルーフを生成しようとするとき、検証者はそのプルーフを検証者キーとともに数学的にチェックすることになります。このプロセス（特に検証プロセス）は、Fast Reed-Solomon Interactive Oracle Proof of Proximityと呼ばれる新しいアルゴリズムを使用することで大幅にスピードアップしました。 ZK-STARKのスケーラビリティを向上させるために利用される新しいアルゴリズムの詳細については、Vitalik Buterinのブログ記事を読んで、詳細な分析を行うことをお勧めします。
量子コンピュータ
最近では、量子コンピュータが注目されており、ブロックチェーンの世界でもある程度関心が集まっています。（Qubitプロトコルは興味深いブロックチェーンのスタートアップです） IBMとIntelはどちらも量子コンピュータの開発に取り組んでいますが、広く普及するにはまだまだ時間が必要であると言われています。量子コンピューティングはシステムをブロックする危険性があります。量子コンピュータがブロックチェーンが利用している暗号のいくつかの側面にリスクをもたらす理由を探ることにしましょう。
従来型のコンピュータ（現在使用されているコンピュータ）は、0または1の2つの状態のうちの1つを記憶するビットで動作します。量子コンピュータは、0または1の状態を格納する量子ビット（ビットに似ています）であり、測定されていないときには0と1、どちらも存在します。（光子、核、または電子がキュビットの例になり得る）。キュビットのユニークな特性のため、それらは古典的なコンピュータやビットでは達成できないものに活用することができます。
量子コンピュータは、量子ビット間の全ての相関関係、すなわち、その計算量が2 ^ n（各システムにおける量子ビットごとの相関）だけ効果的に指数関数的に増加します。2量子ビット= 4ビット、3量子ビット= 8ビット、および20量子ビット= 1,048,576ビットとなります。量子コンピュータは、特定の操作のために（古典的なコンピュータのように）並行してデータを処理できるので、データベース検索や公開鍵から秘密鍵を見つけるなどの計算を大幅に高速化できます。
量子コンピューティングがもたらすブロックチェーンへの影響
量子コンピュータはすべての点で優れているわけではなく、特定のアルゴリズムが扱える特定の計算に対して優れているだけです。たとえば、量子コンピュータで実行可能なShorのアルゴリズムと呼ばれるアルゴリズムがあり、非常に高速な整数分解計算を並列に実行する能力があります（整数分解は、合成数を小さな整数の積に分解するプロセスですが、公開鍵から秘密鍵を見つけるために使用することができます。秘密鍵と公開鍵は基本的に非常に大きな数です）、任意の整数の素因数を見つけることができます。
現在の暗号化方式の多くは、RSAやECDSA（Elliptic Curve Cryptography）などは量子コンピューティング攻撃に耐性がありません。 BitcoinとEthereumは、秘密鍵と公開鍵の生成にECDSAを使用します。たとえば、Bitcoinが秘密鍵、公開鍵、およびパブリックアドレスを生成するために使用するプロセスの基本的な図はこのようなものになります。
秘密鍵は、エントロピー（ランダム性）のレベルが追加された番号から生成され、公開鍵は秘密鍵から生成され、公開鍵は公開鍵のハッシュから生成されます。 量子コンピュータはShorのアルゴリズムを利用して公開鍵から秘密鍵を導出し、秘密鍵を利用してトランザクションを捏造したり、ユーザーの残高を盗んだりすることができます（Bitcoin / Ethereum）。
Shorのアルゴリズムは、主に再利用されるアドレスの問題です。使用されていないアドレスの場合、量子コンピュータはグローバーのアルゴリズムを利用してSHA-256またはSHA3-256が公開鍵ハッシュから公開鍵を見つけられるようになりますし、今日の従来型のコンピュータの半分の時間で公開鍵を見つけることが可能です。半分の時間であっても、地球上の誰の生涯でも鍵は見つからないであろう。さらに、ハッシュツリーは現在の量子コンピューティング攻撃の影響を受けにくいのです。
現在、BitcoinやEthereumなどのブロックチェーンでECDSAを将来置き換える候補となるラティスベースの暗号や多変量暗号など、量子コンピュータでは解読しにくいアルゴリズムが開発されています。
ZK-STARKは、ECDSAなどのプライベート・パブリック・キー・ペアリングに依存しませんが、グローバーのアルゴリズムは意味をなさないような対話型ソリューション（通常は代わりに使用されるモデル）に耐衝突性ハッシュを使用する非インタラクティブプルーフ（zk-nSTARK、n =非インタラクティブ）のために強力なランダム性の仮定が必要な一般的な暗号ハッシュ関数を使用しているため、ZK-STARKは量子コンピュータ攻撃に耐性があります。
量子コンピュータが完成するまでまだまだ何年もかかると言われていますから（推定では2026〜2035年あたり）、今日の能力について心配する必要はほとんどありません。また、量子耐性と量子プルーフが反映する2つの用語であるので、私はこの投稿で量子耐性という用語を使用します。量子コンピュータの真の能力がわかるまでは防水時計のように、今日の量子耐性暗号アルゴリズムを回避するために量子コンピュータを活用するアルゴリズムが見つかるかどうかは言い難いです。主流の量子コンピューティングが現実味を帯びてくるまで、BitcoinまたはEthereumで使用される暗号化アルゴリズムの変更は見られないでしょう。
従来型のコンピュータと量子コンピュータの違いを理解するのに役立つビデオ：
現状と最後の考察
現在、ZK-SNARKは暗号通貨であるZcashと、ライブラリのlibSNARKで利用可能であり、ブロックチェーンで利用できるZK-SNARKプログラムを構築しています。 ZK-STARKはより新しい技術であり、現在の生産能力で展開されていません。 StarkWare Industriesと呼ばれる新しい会社があり、ZK-STARKを活用して課題のいくつかを解決し、ブロックチェーン実装を含む複数の業界で活用できる技術を実用化しようとしています。
ZK-STARKはスケーラブルで、透明性があり、普遍的な応用が可能で、現在は量子耐性です。これは、検証可能なので、技術に対する信頼性の創造を可能にします。 ZK-STARKなどの信頼を必要とするテクノロジーや、不正行為を誘発する大きなインセンティブがあるなどの技術を使用することによって強化できる領域は数多くあります。
- 投票システム
- ブロックチェーンの過去のトランザクションなどの計算を実行してその結果を検証
- 身元確認や資格証明などの情報のセキュリティ確認
私の現在の考えは、ZcashがZK-nSTARK（非対話型）技術を将来的にそのブロックチェーンに採用することです。さらに、Ethereumは、ベーシックアテンショントークンを活用するBraveのWebブラウザなど、プライバシーが重要なDappsと同様に、検証可能な計算や潜在的に安全な/匿名のトランザクションでZK-STARKSを活用することができます。
ZK-STARKは、創造された信頼性が検証可能で公開されているため、これまで達成されていないコンピューティングシステムでも信頼性を実現するテクノロジーです。この考え方は、ZK-STARK証明システムを使用する際に、情報を改ざんする大きなインセンティブを持つものが改ざんしないようにする上で、特に重要です。このタイプのテクノロジーが採用されるには時間がかかりますが、利益をもたらし、非常に大きく本当にユニークなものを作ることが可能になります。システムによって処理される情報を改ざんする高いインセンティブが存在する世界における検証可能な信頼性などもその一つです。
