「パイプライン方式」を通じて生成証明の効率を向上させるにはどうすればよいですか？

執筆：康水跃、Fox Tech CEO；孟铉济、Fox Tech チーフサイエンティスト

校正：林彦熹、Fox Tech CTO

前言

今日のデジタル時代において、ブロックチェーン技術の急速な発展に伴い、人々はデータのプライバシーとセキュリティに対する関心を高めています。より効率的でスケーラブルなブロックチェーンアプリケーションを実現するために、多くのソリューションが提案されており、その一つがゼロ知識証明（Zero-Knowledge Proof）技術です。ゼロ知識証明は、機密情報を漏洩することなく、ある主張の真実性を検証できる強力な暗号学的ツールです。

近年、zkRollupはブロックチェーンのスケーリング技術の重要な革新の一つとして広く注目されています。zkRollupは、多数のトランザクションをパッケージ化し、オフチェーンで実行し、ゼロ知識証明の特性を利用してこれらのトランザクションの正当性を検証することで、ブロックチェーンのスループットとスケーラビリティを大幅に向上させます。そして、zkRollupの実装において、トランザクションの配分とパッケージ化、証明の生成がzkRollupシステムの重要な構成要素となります。

Layer1システムでは、トランザクションはブロックの形式でパッケージ化され、マイナーによって計算されます。一方、Layer2システムでは、トランザクションのパッケージ化、つまりLayer2のブロックを生成する方法は別途考慮する必要があります。

FOXはzkEVMに基づくLayer2 zkRollupスケーリングプロジェクトであり、この問題に対して、FOXはパイプライン形式の処理方法を使用してトランザクションをバッチ処理することを探求しており、効率の大幅な向上が期待されています。

本稿では、zkRollupにおけるゼロ知識証明の生成におけるパイプライン方式の応用について深く探討します。まず、基本的なトランザクションのパッケージ化方法を分析します。次に、パイプライン方式によるゼロ知識証明の生成技術に焦点を当て、その原理と応用シーンを詳細に分析します。

一般的なトランザクションのパッケージ化方法

従来のブロックチェーンシステムにおいて、トランザクションの確認とパッケージ化は時間がかかり、リソースを集中的に消費するプロセスです。通常、トランザクションは一つずつ検証され、ブロックに追加され、その後、コンセンサスアルゴリズムによって合意が形成され、ブロックチェーンの状態が更新されます。しかし、この一つずつの検証とパッケージ化の方法には、スループットの低さや高い遅延などの明らかな限界があります。

一般的なトランザクションのパッケージ化プロセスでは、まず、処理待ちのトランザクションのバッチが収集されます。これらはユーザーが提出したトランザクションや他のチェーンからのトランザクションである可能性があります。次に、これらのトランザクションが検証され、その合法性と有効性が確認されます。これらの検証には、トランザクションの署名の確認、トランザクションの有効性と一貫性の検証などが含まれます。一度トランザクションが検証を通過すると、それらはバッチとしてパッケージ化され、提出待ちのブロックが形成されます。

zkRollupシステムにおいても、ユーザーが提出したトランザクションは同様にまずトランザクションプールに置かれます。FOXシステムでは、Sequencerが定期的にトランザクションプールからトランザクションを取得し、ローカルで実行およびソートしてトランザクションパッケージ、すなわちブロックを形成します。この時、トランザクションの実行結果がLayer1に提出され、同時にこの結果とトランザクションデータが証明を生成するFolderノードに提出されます。

ゼロ知識証明アルゴリズムの基本的な理解に基づくと（読者は以前のFOXのシリーズ記事を参照できます）、Folderが証明を生成するためには入力と実行結果を得る必要があります。これにより、従来の方法で行う場合、Sequencerがすべてのトランザクションを実行し終わるのを待ってからFolderに渡す必要があります。計算リソースをより効率的に利用するために、Sequencerが一部のトランザクションを実行した後、すぐにFolderに証明生成を行わせることを望んでいます。

FOXが探求しているパイプライン処理モデル

上記の目標を達成するために、Sequencerがトランザクションをバッチ処理し、一つのバッチを実行した後にすぐに中間結果をFolderに送信する必要があります。

具体的には、トランザクションパッケージのトランザクション総数が100、単一バッチのトランザクション数が10の場合、パイプライン処理方式は以下の図で表すことができます。

次に、二つの方法の時間コストを簡単に分析し、どのような場合にパイプライン方式を使用するとより高い効率が得られるかを議論します。簡略化のために、ここでの議論ではSequencerがデータをFolderに送信する時間は考慮していません。

トランザクションパッケージのトランザクション数をn、バッチ数をk、Sequencerの実行時間関数をexe()、Folderの証明生成時間関数をprove()、証明の集約時間関数をaggr()、従来の方法の総時間をSum1、パイプライン方式の総時間をSum2とします。

したがって、上記のプロセスに従い、従来の方法はSequencerが先に実行し、その後Folderが証明を生成することに依存しており、必要な総時間は

Sum1=exe(n)+prove(n)

一方、パイプライン方式の時間は、Sequencerが最初のバッチのトランザクションを実行する時間と、後続の証明生成時間および後続バッチの実行時間の大きい方、さらに最後の集約時間を含むべきです。

Sum2=exe(n/k)+max{k*prove(n/k),(k-1)*exe(n/k)}+aggr(k)

したがって、両者の総時間を比較すると、実行時間関数exe()は基本的に線形関数に近似でき、prove()については、FOXシステムの証明アルゴリズムの証明生成時間が線形関数であるため、prove()も線形関数となります。

結論として次のことが言えます：

• もしexe(n)>prove(n)であれば、prove(n)>aggr(k)のとき、Sum1>Sum2。
• もしexe(n)aggr(k)のとき、Sum1>Sum2。

したがって、集約時間aggr(k)が十分に小さく、証明生成時間が線形関数であれば、パイプライン方式を採用することはシステムの効率を向上させ、総証明生成時間を減少させるのに非常に役立ちます。

上記の分析は線形時間証明アルゴリズムに対してのみ成立し、この点からもFOXが線形時間証明アルゴリズムを採用する重要性がわかります。

パイプライン方式が現在探求中である理由は、このモデルの分析を通じて、各トランザクションパッケージが分割されるバッチが多くなるほど、SequencerがFolderに記録し送信するデータが増え、オーバーヘッドが大きくなることがわかるからです。しかし、Folderにとっては、一度の処理の計算量が減少し、集約プロセスがより複雑になります。したがって、具体的にどのように分割するかは、トレードオフの問題であり、SequencerとFolderの計算性能に具体的に依存します。

トランザクションを効率的に配分しパッケージ化して逐次証明を生成することが重要な最適化ポイント

zkRollupの実装において、トランザクションを効率的に配分しパッケージ化して証明を生成することは重要な最適化ポイントです。FOXはこのモデルを継続的に最適化し、より効率的なソリューションを探求しています。以下はFOXが採用している基本的なプロセスです：

1. トランザクション収集：処理待ちのトランザクションを収集し、トランザクションプールに保存します。これらのトランザクションは、ユーザーが提出したものであったり、他のシステムやコントラクトから生成されたものである可能性があります。
2. トランザクションソート：トランザクションプール内のトランザクションをソートし、パッケージ化の順序を決定します。通常、優先度、タイムスタンプ、その他の要因に基づくソートアルゴリズムを使用できます。ソートの目標は、トランザクションの全体的なスループットと効率を最大化することです。
3. トランザクション配分：ソートされたトランザクションを適切なブロックに配分します。zkRollupでは、通常、一定数のトランザクションを収容する新しいブロックが作成されます。配分プロセスには、貪欲アルゴリズムやその他の配分戦略を使用して、各ブロックの容量利用率を最大化します。
4. ブロックパッケージ化：配分されたトランザクションをパッケージ化し、完全なブロックを形成します。FOXのLayer2アーキテクチャにおいて、このブロックは実際にはトランザクションの要約情報のみを含みます。この要約情報はトランザクションのハッシュやその他の形式のコンパクトな表現であり、トランザクションの詳細な内容ではありません。詳細なトランザクション情報はFOXのRingerに保存され、データの可用性（DA）を実現します。
5. 証明生成：パッケージ化されたブロックに対して相応の証明を生成します。この証明は、ブロック内の各トランザクションの有効性と全体のブロックの一貫性を証明できるものである必要があります。FOXのパイプラインモデルは主にこの段階で適用され、Folderの計算力をより効率的に利用し、ブロック内のトランザクションを逐次Folderに送信して証明生成を行います。Folderは各バッチのトランザクションの正当性証明を計算し、最後にそれを集約します。通常、この証明はFOAKSという迅速かつターゲットを絞ったゼロ知識証明アルゴリズムに基づいており、ブロック内のトランザクションと状態遷移ルールを比較して、それらがシステムのルールと制約に従っているかを検証します。
6. 証明検証：受信者は証明を使用してブロックの有効性を検証できます。これにより、全体のブロックを再計算する必要がありません。この検証プロセスは非常に効率的であり、証明のチェックのみを含むため、トランザクションに対する複雑な計算は必要ありません。

FOXの「パイプラインモデル」は主に証明生成のこの段階で発生します。トランザクションの収集とソートの中で、Sequencerは処理待ちのトランザクションを収集し、何らかのルールに従ってそれらをソートし、実行の順序を決定します。その後のトランザクションのバッチ実行において、Sequencerはソートされたトランザクションをバッチごとに実行します。各バッチ内の一組のトランザクションが実行エンジンに送信され、処理されます。実行エンジンはこれらのトランザクションをシミュレーション実行し、状態遷移の中間結果を記録します。各バッチのトランザクションが実行された後、Sequencerは中間結果をFolderに送信します。

これは、中間結果を状態更新、トランザクションハッシュなどの形式で逐次Folderに送信する通信チャネルを介して実現できます。Folderは各バッチの中間結果を受け取った後、これらの結果を使用して逐次的に相応の証明を生成します。これらの証明の生成は、FOXが独自に開発したFOAKSゼロ知識証明アルゴリズムに基づいており、中間結果を入力として使用してトランザクションの有効性と全体のブロックの一貫性を証明します。

最後のステップは証明の検証です。生成された証明は、EthereumにデプロイされたスマートコントラクトVerifierに送信され、ブロックの有効性を検証します。Verifierは検証アルゴリズムを使用して証明をチェックし、その正確性と合法性を確認します。

このようなパイプライン方式により、Sequencerはトランザクションを実行しながら、中間結果をFolderに逐次送信し、証明の生成を行うことができます。これにより、システム全体の効率とスループットが向上し、証明生成の遅延が減少します。

結語

本稿では、zkRollupにおけるトランザクションのバッチ処理による証明生成の新しいアプローチ、パイプライン方式を紹介し、この方式の時間コストを詳細に分析しました。線形証明アルゴリズムに対して、合理的にパイプライン方式を使用することで、総証明生成時間を減少させるのに役立ちます。FOXが採用している証明システムは線形証明時間を実現しており、迅速な証明生成とユーザー体験の向上に大いに貢献しています。FOXチームはこのソリューションを引き続き探求し、最適化を進めていく予定です。