STARKアルゴリズムの解析

• パート 0: はじめに

• パート 1: STARK を見てみる

• その2：便利な「ツール」

• パート 3: 金曜日

• パート 4: STARK 多項式 IOP

• パート 5: レスキュープライムスターク

• パート 6: プロセス全体のスピードアップ

1. スタークとは何ですか?

最近、暗号証明システムの分野で最もエキサイティングな開発の 1 つは STARK の開発です。急成長を遂げるブロックチェーン業界の後に来るものだ。全体として、証明システムはそれらに合わせて作られているようです。ブロックチェーン ネットワークは、多くの場合、秘密情報を使用して取引を行ったり、状態進化のルールに従って集団状態を更新したりすることを望む、相互に不信感を抱いている当事者で構成されています。参加者は相互に不信感を抱いているため、参加者が提案したトランザクション (または状態の更新) の有効性を検証する方法が必要です。

zk-SNARK の次の特性により、当然のことながら、この環境での計算整合性の保証を提供できます。

• zk-SNARK は一般に汎用的であり、あらゆる計算の整合性を証明できることを意味します。

• zk-SNARK は非対話型です。つまり、完全性証明全体が 1 つのメッセージで構成されます。

• zk-SNARK の検証は効率的です。つまり、検証者の作業負荷は、単純に計算を再実行する場合よりも 1 桁少なくなります (翻訳者注: 数桁の作業負荷も可能です)。

• zk-SNARK はゼロ知識であり、秘密入力の計算に関する情報をまったく明らかにしません。

"私は、zk-SNARK が今後 10 ～ 20 年で主流の世界に浸透し、大きな革命を起こすことを期待しています。"——『V神』2021.9.2

zk-SNARK はしばらく前から存在していますが、STARK プルーフ システムは比較的新しいものです。これはいくつかの理由から際立っています。

• 従来の zk-SNARK は高度な暗号パズルと仮定に依存していますが、STARK 証明システムの唯一の暗号コンポーネントは衝突耐性のあるハッシュ関数です。したがって、理想化されたハッシュ関数モデルの下では、証明システムの反量子安全性を証明できます (文献では、この理想化は「量子ランダム オラクル モデル」量子ランダム オラクル モデルと呼ばれています)。これは、双線形マップを使用し、反証不可能な仮定の下でのみ安全であることが証明された第一世代の SNARK とはまったく対照的です。

• STARK の算術化は暗号学的に難しい問題とは独立しているため、このドメインはパフォーマンスを最適化するために特別に選択できます。したがって、STARK は真の高速証明 (Prover) を可能にします。

• 従来の zk-SNARK は、信頼されたセットアップ セレモニーに依存してパブリック パラメーターを生成します。式典の後は、使用したランダムパラメータは安全に忘れてください。参加者がこの暗号化された「有害なゴミ」を削除することを拒否したり忘れたりした場合、証拠を偽造する能力が保持されるため、式典自体は信頼できないものではありません。対照的に、STARK には信頼できるセットアップがないため、暗号化はありません。"有害廃棄物"。



「私は概ね同意しますが、次の 2 つの点で留保します。

1) SNARKではなくSTARKが支配する

2) 3 ～ 5 年で主流の世界に浸透する

カレンダーにリマインダーを入れて、4 年後にその言葉をテストしてみます。 ——エリ・ベン・サッソン 2021.9.2

このチュートリアルでは、これらの部分がどれだけ連携して機能するかを説明します。この文字通りの説明は、Rescue-Prime ハッシュ関数に基づく単純な計算を証明および検証する Python 実装によってサポートされています。このチュートリアルを読むか従った後は、選択した計算のための独自のゼロ知識 STARK 証明器と検証器を作成できるようになります。

2. この記事を書く理由は何ですか?

STARK の学習には複数の情報源があることを早い段階で指摘しておく必要があります。以下は不完全なリストです。

• FRI、STARK、DEEP-FRI、およびFRIの最新の信頼性解析に関する論文

• Vitalik Buterin による複数部構成のチュートリアル (パート 1/2/3)。

• StarkWare の一連のブログ投稿 (パート 1、2、3、4、5)。

• Starkware の STARK@Home ウェブキャスト

• Starkware の STARK 101 オンライン コース

• StarkWare による EthStark ドキュメント

• 一般的に、Starkware がリリースするものはすべて、

これほど多くの学習リソースがあるのに、なぜ別のチュートリアルを書く必要があるのでしょうか?

既存のチュートリアルは比較的浅いものです。これらのチュートリアルは、これらのテクニックがどのように機能するかを高レベルで説明し、STARK が機能する理由についての直観を伝えるのに適しています。ただし、これらは完全な展開可能なシステムについては説明していません。たとえば、ゼロ知識を実装する方法、さまざまな低レベル証明をバッチ処理する方法、または結果のセキュリティ レベルを決定する方法については、どのチュートリアルでも説明されていません。 EthSTARK のドキュメントは、これらの質問のほとんどに答えるための完全なリファレンスを提供していますが、特定の計算に特化しており、知識がゼロではなく、アクセスしやすく直感的な説明も提供していません。

これらの論文は理解するのが難しいです。悲しいことに、科学出版におけるインセンティブは、科学論文を一般読者にとって読みにくくするように設定されています。したがって、これらの論文をより多くの人が理解できるようにするには、この記事のようなチュートリアルが必要です。

情報が古いです。さまざまなチュートリアルで説明されているテクニックの多くは、その後改良されました。たとえば、EthSTARK ドキュメント (上で引用した最新のもの) では、有界次数の多項式に対する正しい評価の要件を軽減するための DEEP 補間技術が説明されています。これらの情報源はこの手法よりも古いものであるため、この手法についてはこれらの情報源では言及されていません。

私は自分のスタイルの方が好きです。私は多くの記号や名前に同意しません。人々が正しいものを使用することを願っています。特に、私は証明システムの最も基本的な対象である多項式に焦点を当てるのが好きです。対照的に、他のすべての情報源は、リードソロモン符号語の操作の観点から証明システムのメカニズムを説明しています。

このチュートリアルは、STARK をより深く理解するのに役立ちました。このチュートリアルを書くことで、自分の知識を体系化し、どこが浅いのか、あるいはまったく欠けているのかを見つけることができました。

3. 必要な予備知識

このチュートリアルでは、必要に応じて背景知識をブラッシュアップします。ただし、読者が以下のトピックに精通していない場合、ここでの紹介は内容が濃すぎる可能性があるため、すべての読者が以下のトピックを理解して研究することをお勧めします。

• 有限体とその拡張体

• 単変量多項式および多変量多項式を含む、有限体上の多項式

• ハッシュ関数

• ハッシュ関数

4.シリーズウィザード

• パート 1: STARK の概要では、コンセプトとワークフローを高レベルで説明します。

• パート 2: 便利な「ツール」では、証明システムを構築するための基本的な数学ツールと暗号ツールを紹介します。

• パート 3: FRI は、証明システムの暗号化の中核となる低レベルのテストをカバーします。

• Part 4: STARK Polynomial IOP（IOP,インタラクティブオラクル証明) は、任意の計算要件から抽象証明システムを生成するための情報理論を説明します。

• パート 5: Rescue-Prime STARK は、これらのツールを組み合わせて、単純な計算のための透過的なゼロ知識証明システムを構築します。

• パート 6: プロセス全体を高速化する プロセス全体をより高速かつ効果的に行うためのアルゴリズムとテクノロジを導入します。"S "(簡潔、簡潔) STARK に入れる

  5. 謝辞

著者らは、有益なフィードバックとコメントをくれた Bobbin Threadbare 氏、Thorkil Værge 氏、Eli Ben-Sasson 氏、そして経済的支援をくれた Nervos Foundation に感謝したいと思います。 alan@nervos.org に電子メールを送信するか、twitter または Github で aszepieniec をフォローしてください。

訳者注：原文には公式アカウントの制限により添付できない資料リンクが多数ありますので、原文の資料リンクをご参照ください。

About zCloak Network

zCloak Network は、Polkadot エコシステムに基づくプライベート コンピューティング サービス プラットフォームで、zk-STARK 仮想マシンを使用して一般的なコンピューティングのゼロ知識証明を生成および検証します。独自の自律データと自己認証コンピューティング技術に基づいて、ユーザーはデータを外部に送信することなくデータを分析および計算できます。 Polkadot クロスチェーン メッセージング メカニズムを通じて、Polkadot エコシステム内の他のパラレル チェーンや他のパブリック チェーンにデータ プライバシー保護のサポートを提供できます。このプロジェクトでは、「ゼロ知識証明サービスとしてのゼロ知識証明」ビジネス モデルを採用し、ワンストップのマルチチェーン プライバシー コンピューティング インフラストラクチャを構築します。