再帰とは何ですか?

再帰は、数学、統計、コンピューター サイエンスの分野で最も一般的に使用されていますが、言語学や論理学、人工知能やゲームの実世界のアプリケーションなど、他の幅広い分野でも広く使用されています。

再帰とは、関数が循環ループ内で直接的または間接的にそれ自体を呼び出すことを指します。

再帰を使用すると、計算の精度を向上させ、必要な全体的な計算負荷を軽減できます。 「分割統治」とも呼ばれる、より大きく複雑な問題を小さな部分に分割することにより、再帰によりタスクの解決がより迅速かつ実現可能になります。重要な特徴は、基本ケースと再帰ステップの観点から定義される再帰を達成するために、関数がそれ自体を連続して繰り返し呼び出すことです。

基本ケースは、出力を計算するすべての入力に関する問題の最も単純なインスタンスを指します。再帰的なステップは同じ関数を呼び出しますが、入力のサイズや複雑さは減少します。

反復アルゴリズムと再帰アルゴリズムはどちらも問題を小さな問題に分割しますが、前者ではアルゴリズムの順序を管理するために明示的な制御ロジックが必要です。再帰関数の順序は、ベクトル データと再帰関数の相互作用によって決まります。これにより、事前に明示的に定義できないデータ構造をより柔軟に処理できるようになります。

再帰はブロックチェーン技術にどのように適用されますか?

再帰はブロックチェーン上で証明を生成する方法です。現在、イーサリアムメインネット上で複数の実稼働システムを提供しています。たとえば、Arbitrum は紛争解決プロセスに再帰的二分アルゴリズムを使用していますが、StarkWare と zkSync は両方とも再帰を使用して拡張スケーリング機能を実現しています。

再帰的テクノロジがなければ、証明に適合できるトランザクションの上限があり、これは単一ブロックの計算能力によって決まります。再帰を使用すると、数十万の基礎となるトランザクションを含む複数の検証済みプルーフから 1 つのプルーフを生成できます。言い換えれば、単一のプルーフでより多くのトランザクションを処理できるようになりました (再帰的スケーリングとも呼ばれます)。

ゼロ知識証明に適用されている再帰的テクノロジーは、ブロックチェーンのスケーラビリティを解決するソリューションの重要な部分とみなされているため、特に重要です。イーサリアム上の主要な zk-rollup スケーリング ソリューションの 1 つである StarkWare の StarkNet を例にとると、SHARP (SHARed Prover) は、StarkNet 上の個別のアプリケーションからトランザクションをバッチ処理し、1 つの ZK-STARK 証明 (または単に STARK 証明) に圧縮します。次に証明者は証明を検証者に渡し、層 1 で状態変化を検証して登録するのが検証者の仕事です。必要な計算リソースに基づいて証明者になれる人には制限があります。

次に、画像に再帰を追加しましょう。複数のトランザクション (またはステートメント) が SHARP に送信され、並行して証明されます。次に、各証明は STARK 検証者によって検証されます。検証されると、それらは Recursive Verifier ステートメントによって再度マージされます。このプロセスは、最後の証明がレイヤー 1 で Solidity 検証者のスマート コントラクトに送信されるまで繰り返されます。したがって、この証明はすべての元のステートメントを証明し、複数のオンチェーントランザクションを 1 つの証明で処理できるようになります。理論的には、再帰ループは無限に繰り返すことができ、「ハイパースケーリング」機能の可能性が可能になります。

したがって、再帰はロールアップ テクノロジーとレイヤー 2 スケーリングの可能性をさらに解き放ちます。

再帰の利点

有効性証明のための再帰の利点には、複数の証明を 1 つに「圧縮」することでトランザクションあたりのコストが削減され、ガスコストが削減されることが含まれます。これにより、L1 に送信された単一プルーフ内でより多くのトランザクションを分割できるようになり、トランザクションごとのガスコストが償却されます。非常に大きなステートメントを一度に証明する必要がないため、証明サイズを制限していた計算リソースの障壁もなくなりました。

また、レイテンシの短縮にもつながります。ステートメント (小規模なトランザクションを含む) は並行して証明でき、他のトランザクションが入ってくるのを待つ必要がありません。証明者はオフチェーンで大規模な計算を実行する必要がなくなり、証明者になるための障壁が低くなり、分散型の証明者になることが奨励されています。ネットワークの処理能力を高めるための証明者のネットワーク。

さらに、ユーザーは STARK による「対数圧縮」の恩恵を受ける可能性があります。この場合、ステートメントの証明には T 時間がかかり、証明の検証にはおよそ log(T) 時間がかかります。正しい実行の 2 つの証明を含む証明を検証するには log(2log(T)) ステップが必要となるため、対数圧縮は重要です。言い換えれば、再帰的な証明を生成して検証するための待ち時間が対数スケールで減少します。

再帰を通じて、プラットフォームとアプリケーションはコストとパフォーマンスをさらに拡張する機会が得られます。

レイヤ 2 を超えた再帰の使用

再帰は、レイヤー 3 のユースケースの準備を整えます。これまでのところ、再帰を使用して、最終的にレイヤー 1 に落ち着くレイヤー 2 でプルーフを生成することに重点が置かれてきました。しかし、新しいレイヤーでは、最上位レイヤーで実行が行われるレイヤー 3 からレイヤー 2 にトランザクションプルーフを送信する可能性も開かれます。 、そしてその証明は最終的にレイヤー 2 で検証され、これによりパフォーマンスの最適化とコストの利点をさらに引き出すことができます。レイヤ 3 とレイヤ 2 間の対話はレイヤ 2 とレイヤ 1 に似ていますが、すべてのトランザクションの整合性とセキュリティは維持されます。

具体的には、プライベート レイヤ 3 ネットワークは高度にカスタマイズ可能であるため、プロトコルはトランザクション バッチ サイズを設定してトランザクション コストと速度のバランスをとったり、プライバシー保護機能を実装したりするなど、独自の動作パラメータを設定できます。さまざまなユースケースに対応するレイヤー 3 の特注品質と、再帰による処理機能の向上により、パフォーマンスとコストの最適化のためのツールをすぐに利用できるようにしながら、カスタマイズされたチェーン エクスペリエンスの両方が可能になります。レイヤ 3 の利点は、再帰的証明、プライバシー、レイヤ 2 とレイヤ 3 間の相互運用性の向上の相乗効果を活用した結果としてのハイパー スケーラビリティです。

時間の経過とともに、ブロックチェーン開発における再帰の使用例と利点がさらに多くなるでしょう。並列化プロセスのロックを解除することで、ハイパースケーリングが可能になり、レイテンシーの改善とガス料金の削減が同時に可能になります。

著者

Jane Ma 氏、zkLend の共同創設者兼共同プロジェクト リーダー。StarkNet 上に構築された L2 マネー マーケット プロトコルで、zk ロールアップのスケーラビリティ、優れたトランザクション速度、コスト削減とイーサリアムのセキュリティを組み合わせています。このプロトコルは、機関顧客向けのコンプライアンス重視のパーミッション型ソリューションと、DeFi ユーザー向けのパーミッションレス サービスの 2 つのソリューションを、すべて分散化を犠牲にすることなく提供します。