[EIP2565] ModExpプリコンパイルのガスコストに関する提案について理解しよう！

はじめに

初めまして。 CryptoGamesというブロックチェーンゲーム企業でエンジニアをしている cardene（かるでね） です！スマートコントラクトを書いたり、フロントエンド・バックエンド・インフラと幅広く触れています。

CryptoGamesCryptoGamesは、ブロックチェーン技術を活用したゲーム・Web3事業を展開する企業です。トレーディングカード、NFT、RWA領域を中心に、新しいエンターテインメント体験を創出しています。cryptogames.co.jp

代表的なゲームはクリプトスペルズというブロックチェーンゲームです。

日本最大級ブロックチェーンゲーム(NFTゲーム)「CryptoSpells」日本初のブロックチェーンTCG、CryptoSpells。cryptospells.jp

今回は、Etherum上でModExpプリコンパイルを呼び出す時のガスコストを定義し、実際の運用コストを反映するための新しい計算アルゴリズムを提案しているEIP2565についてまとめていきます！

以下にまとめられているものを翻訳・要約・補足しながらまとめていきます。

EIP-2565: ModExp Gas CostEthereum Improvement Proposals

他にも様々なEIPについてまとめています。

Notion | Where teams and agents work togetherMade in Notion, the connected workspace where AI agents and teams organize docs, projects and knowledge together.Notion

概要

イーサリアムのブロックチェーン上で実行される特定の計算操作、ModExp プリコンパイルのガスコストをどのように定めるかについて説明しています。ガスはイーサリアム上での処理にかかるコストの単位であり、このEIPは特定の計算、すなわちモジュラー指数演算についてのガスコストをより正確に計算するための方法を提案しています。計算の複雑さ（この場合は乗算の複雑さ）を見積もり、それを指数演算を行うのに必要な繰り返しの回数の見積もりと掛け合わせることで、最終的なガスコストを導出します。これにより、ブロックチェーン上での計算コストがより現実の運用コストを反映したものになることが期待されます。

動機

モジュラー指数演算は、暗号学において非常に重要な役割を果たしています。この演算は、デジタル署名の生成や検証、ブロックチェーン技術で使われる様々な形式の証明（例えば、SNARKs）、暗号学的なアキュムレータ、およびVDFsのような高度なランダム性を実現するためのメカニズムに不可欠です。ただし、イーサリアムなどのブロックチェーンプラットフォームでこの演算を行うための現在のプリコンパイル（あらかじめ定義された低レベルの関数）のコストが過剰に高いため、これらの重要な暗号操作が実用性を欠き、使用が制限されています。このコストが下がれば、より多くのアプリケーションがこれらの先進的な暗号機能を利用できるようになり、それによって全体としてのセキュリティが向上し、例えばVDFを使ったより強力なランダム性の生成が可能になります。これは、ブロックチェーンの分散性とセキュリティをさらに強化することに寄与します。

モジュラー指数演算

モジュラー指数演算は、 $( a^b \mod n )$ の形で表され、ここで $( a )$ は基数、 $( b )$ は指数、 $( n )$ は割る値（モジュラス）と呼ばれます。この演算は、 $( a )$ の $( b )$ 乗を計算し、その結果を $( n )$ で割った余りを求めるというものです。モジュラー指数演算は、暗号学を含む多くの分野で広く使用されています。

具体例

例えば、 $( 4^3 \mod 5 )$ を計算する場合を考えてみましょう。

基数、指数、割る値の設定
- ここでは基数 $( a = 4 )$ 、指数 $( b = 3 )$ 、割る値 $( n = 5 )$ です。
指数乗の計算
- $( 4^3 = 64 )$ を計算します。
モジュラー演算
- 64 を 5 で割った余りを計算します。
- すなわち、 $( 64 \mod 5 = 4 )$ です。

したがって、( 4^3 \mod 5 ) の結果は 4 になります。

暗号学での使用

モジュラー指数演算は、公開鍵暗号方式の一つであるRSA暗号で中心的な役割を果たします。 RSA暗号では、大きな素数 $( p )$ と $( q )$ を選び、それらの積 $( n = p \times q )$ をモジュラスとして使用します。公開鍵は $( (e, n) )$ 、秘密鍵は $( (d, n) )$ となります。ここで $( e )$ と $( d )$ は特定の条件を満たすように選ばれます。

暗号化
- メッセージ $( m )$ を暗号化するには、 $( c = m^e \mod n )$ を計算します。
- ここで $( c )$ は暗号文です。
復号化: 暗号文 $( c )$ を復号化するには、 $( m = c^d \mod n )$ を計算します。この結果 $( m )$ は元のメッセージになります。

このように、モジュラー指数演算は暗号化と復号化のプロセスの核となる部分であり、その効率性とセキュリティは暗号システム全体の性能に大きく影響します。

VDF

VDF（Verifiable Delay Function、検証可能遅延関数）は、一定の計算時間がかかる一方向関数であり、その結果を迅速に検証することができます。 VDFは、計算に要する時間を確実にすることで、ブロックチェーンや分散型システムにおけるランダムネスの生成、タイムスタンプの証明、フェアな順序付けなどに利用されます。

具体例

ランダム値の生成が重要な役割を果たすブロックチェーンのLotteryシステムを例に取ります。

初期値の設定
- システムは初期値 $( x )$ を公開します。
- この値は、例えばブロックチェーンの以前のブロックハッシュなど、公に利用可能なデータから生成されるかもしれません。
VDFの適用
- 参加者はこの初期値 $( x )$ にVDFを適用し、結果 $( y = VDF(x) )$ を計算します。
- VDFは設計により、たとえ高性能なハードウェアを使用しても、計算には予め定められた時間（例: 10分）がかかるようになっています。
結果の公開
- 計算が完了したら、参加者は結果 $( y )$ を公開します。
結果の検証
- 他の参加者は、公開された結果 $( y )$ が初期値 $( x )$ から正しいVDFの適用によって得られたものであることを迅速に検証できます。
- VDFの特性により、この検証プロセスは計算プロセスよりもずっと高速です。
ランダムネスの利用
- 検証された $( y )$ の値は、Lotteryの当選番号を決定するなど、システム内でランダムな値として利用されます。

このプロセスにより、VDFは計算の遅延を強制することで、参加者が未来の出力を予測したり、選択したりすることを防ぎます。これにより、全ての参加者にとってフェアなランダムネスが保証されます。 VDFの計算には時間がかかりますが、その結果は迅速に検証可能であるため、効率的かつ安全なランダムネスの生成手段を提供します。

仕様

def calculate_multiplication_complexity(base_length, modulus_length):
    max_length = max(base_length, modulus_length)
    words = math.ceil(max_length / 8)
    return words**2

def calculate_iteration_count(exponent_length, exponent):
    iteration_count = 0
    if exponent_length <= 32 and exponent == 0: iteration_count = 0
    elif exponent_length <= 32: iteration_count = exponent.bit_length() - 1
    elif exponent_length > 32: iteration_count = (8 * (exponent_length - 32)) + ((exponent & (2**256 - 1)).bit_length() - 1)
    return max(iteration_count, 1)

def calculate_gas_cost(base_length, modulus_length, exponent_length, exponent):
    multiplication_complexity = calculate_multiplication_complexity(base_length, modulus_length)
    iteration_count = calculate_iteration_count(exponent_length, exponent)
    return max(200, math.floor(multiplication_complexity * iteration_count / 3))

このコードは、特定のブロック番号（FORK_BLOCK_NUMBER）以降、イーサリアムの特定のアドレス（0x0000000000000000000000000000000000000005）に配置されているプリコンパイル（事前に定義された低レベルの関数）を呼び出す時のガスコストを計算する方法を定義しています。この計算は、モジュラー指数演算のガスコストをより適切に反映させるためのものです。具体的な計算手順は以下の通りです。

1. 乗算の複雑さの計算

calculate_multiplication_complexity 関数は、基数（base）と割る値（modulus）の長さを受け取り、これらの最大値を8で割った上で切り上げた値（単位は「ワード」）を計算し、その値の二乗を返します。これにより、乗算の複雑さを近似します。

2. 反復回数の計算

calculate_iteration_count 関数は、指数の長さと指数自体を受け取り、指数演算を行う時の反復回数を計算します。この計算は、指数の長さが32バイト以下の場合とそれ以上の場合で異なり、指数が0の場合は反復回数が0になります。 32バイトを超える場合、反復回数は指数の下位256ビットのビット長さを考慮して計算されます。

3. ガスコストの総計算

calculate_gas_cost 関数は、基数、割る値、指数の長さ、および指数自体を受け取り、上記で計算した乗算の複雑さと反復回数を用いて最終的なガスコストを計算します。このコストは、乗算の複雑さと反復回数の積を3で割った値に基づいていますが、最低ガスコストは200とされています。

この計算方法により、モジュラー指数演算の実際の計算コストをより正確に反映したガスコストを設定することができ、結果的にこの演算を使用する暗号関数やその他のアプリケーションの効率が向上します。

補足

ModExpプリコンパイルのベンチマーク（性能評価）を行った結果、他のプリコンパイルと比較してそのコストが「過剰に高価」であることが明らかになったと述べられています。さらに、ModExpの入力変数の計算複雑性をより正確に見積もるために、現在のガス価格設定式を改善することができることも発見されました。

ModExpプリコンパイルとは、モジュラー指数演算を行うためのイーサリアムのプリコンパイルされた関数です。この関数は、暗号学的演算などで頻繁に使用されますが、その実行には計算資源が必要とされ、その使用にはガス（イーサリアムネットワークでの計算コストの単位）が必要です。

「過剰に高価」とは、ModExpプリコンパイルの実行コストが、実際の計算コストに比べて不当に高く設定されていることを意味します。これは、イーサリアム上でのModExpを用いた演算が非効率的かつコストが高くなる原因となります。

この問題を解決するためにModExpの価格設定を改善するいくつかの変更が提案されています。これらの変更は、ModExpプリコンパイルのガスコストを計算する際に、様々な入力変数の計算複雑性をより正確に反映するようにすることを目的としています。これにより、イーサリアム上でのModExp演算がより効率的かつコスト効果的になることが期待されます。

1. 計算の複雑さの公式の修正

EIP198では、ModExpの計算複雑性を近似するための関数が定義されていますが、実際の演算時間との一致度を高めるために、新たな複雑性関数の導入が提案されています。

EIP-198の複雑性関数

EIP198で定義された複雑性関数 mult_complexity は、入力 x（法または基数の長さのうち大きい方）に基づいて計算されます。この関数は、Karatsuba乗算の難易度を近似することを意図しており、xの値に応じて異なる式を使用します。

Karatsuba乗算

Karatsuba乗算は、大きな数値を効率的に掛け合わせるためのアルゴリズムです。通常の乗算が数値の桁数に対して二次的な時間複雑性（つまり、桁数が倍になると計算時間が4倍になる）を持つのに対し、Karatsubaアルゴリズムはそれよりも少し効率的です。

Karatsuba乗算は、数値をいくつかの部分に分割し、それらの部分を使って元の乗算問題をより小さな乗算問題のセットに変換することによって機能します。この方法では、元の問題よりもはるかに少ない乗算で済むため、全体としての計算時間が短縮されます。

EIP198で言及されている複雑性関数は、このKaratsuba乗算の計算コストを近似するために設計されています。具体的には、入力値 x（法または基数の長さのうち大きい方）に応じて計算コストがどのように変化するかをモデル化しています。 xが小さい場合は、通常の乗算のコストと似ているため、x ** 2として計算されます。しかし、xが大きくなると、Karatsuba乗算の効率性がより重要になり、そのため異なる式が用いられます。 xが64を超え1024以下の場合、x ** 2 // 4 + 96 * x - 3072を使用し、xが1024を超える場合はさらに効率的なx ** 2 // 16 + 480 * x - 199680を使用します。

これにより、xの値が大きくなるにつれて、Karatsuba乗算の利点をより適切に反映した計算コストが求められるようになります。この近似により、ModExpプリコンパイルのガスコストを計算する時に、実際の計算コストをより正確に反映することができます。

x が 64 以下の場合、x ** 2
x が 64 を超え 1024 以下の場合、x ** 2 // 4 + 96 * x - 3072
x が 1024 を超える場合、x ** 2 // 16 + 480 * x - 199680

新しい提案

新しい提案では、x を 8 で割ることにより、多倍長算術における「リンブ（limbs、数値を構成する部分）」の数を考慮に入れています。

多倍長算術では、非常に大きな数値を扱うために、その数値をより小さな「部分」または「リンブ（limbs）」に分割して扱います。各リンブは、その数値の一部分を表し、全てのリンブを組み合わせることで元の大きな数値が構成されます。この方法により、コンピュータが通常扱うことのできるサイズよりも大きな数値の演算を実現しています。

新しい提案では、x（法または基数の長さのうち大きい方）を8で割ることで、実際に多倍長算術で扱われるリンブの数を考慮に入れています。通常、1リンブは8バイト（64ビット）で構成されるため、xを8で割ることで、その数値を構成するリンブの総数を求めることができます。このリンブの数は、数値の演算における計算複雑性の重要な要素です。

このアプローチにより、数値のサイズが大きくなるほど、つまりリンブの数が増えるほど、計算に必要な労力が増加することを反映できます。このため、新しい複雑性関数は、大きな数値を扱う際の実際の計算コストをより正確に近似することができるのです。これは、特に大きな指数を扱うモジュラー指数演算のような場合において、ガスコストの計算をより現実に即したものにするために重要です。

多倍長算術

多倍長算術（multiprecision arithmetic、多精度算術）は、コンピュータの標準的なデータ型で扱える範囲を超える非常に大きな数値を演算するための方法です。通常、コンピュータは固定されたサイズのデータ型（例えば、32ビットや64ビットの整数）を使用して数値を扱いますが、これらのデータ型には扱える数値の上限があります。

多倍長算術では、このような制限を超えた大きな数値を「リンブ（limbs）」と呼ばれる複数の小さな部分に分割して表現します。各リンブは、通常、コンピュータが標準的に扱えるサイズ（例えば32ビットや64ビット）であり、これらのリンブを組み合わせることで、理論上はどれだけ大きな数値でも表現することが可能になります。

多倍長算術の応用

多倍長算術は、科学計算、暗号学、高精度計算など、非常に大きな数値や非常に正確な計算が必要な分野で広く使われています。例えば、公開鍵暗号方式の一つであるRSA暗号では、1024ビット以上の非常に大きな数値が使われるため、これらの演算には多倍長算術が必要です。

多倍長算術の演算

多倍長算術での演算は、基本的に標準的な算術演算（加算、減算、乗算、除算など）の拡張ですが、各リンブ間でのキャリーやボロー（繰り上がりや繰り下がり）の管理が重要になります。乗算や除算のような複雑な演算は、特に効率的なアルゴリズムが必要とされ、Karatsuba乗算やFFT（高速フーリエ変換）を用いた方法などが使われることがあります。

実装

多倍長算術は、専用のライブラリやフレームワークを通じて実装されます。これらのライブラリは、高度な最適化や特定のアルゴリズムを実装しており、開発者が直接多倍長数値を扱う際の複雑さを抽象化します。代表的なライブラリには、GNU MP（GMP）、MPFR、MPIRなどがあります。これらのツールを使用することで、開発者は多倍長算術を容易に扱うことができ、より複雑な計算やアルゴリズムの開発に集中することができます。

これは、大きな指数に対して「bigint」ライブラリが使用する二進指数演算アルゴリズムの使用を考慮に入れるためです。

提案された新しい複雑性関数は、実行時間に対してEIP198で定義された関数よりもより良い適合性を示しています。つまり、新しい関数は実際の演算時間をより正確に反映していると言えます。また、提案された複雑性関数の回帰線がテストベクトルのデータポイントを二分しているのは、割る値が偶数か奇数かによって実行時間が変動するためです。

複雑性関数

複雑性関数は、特定の計算操作の実行に必要なリソースまたは労力を数値的に評価するための数学的モデルです。この関数は、入力サイズやその他の関連パラメータに基づいて、操作の実行に必要な計算ステップの数や時間を近似します。複雑性関数は、アルゴリズムの効率性を理解し、比較するために使用されます。

EIP198で定義された複雑性関数は、イーサリアムのModExp（モジュラー指数演算）プリコンパイルの計算複雑性を評価するために使用されていました。この関数は、ModExp演算の入力変数（特に、基数とモジュラスの長さ）に基づいて、演算のガスコストを計算するための式を提供しています。

上記のテキストでは、提案された新しい複雑性関数が、EIP198で定義された関数よりも実際の実行時間との適合性が良いと述べています。これは、新しい関数が、ModExp演算の計算コストをより正確に反映し、実際のコンピュータの計算時間とより密接に一致することを意味します。

新しい複雑性関数は、多倍長算術や二進指数演算アルゴリズムなど、ModExp演算において実際に使用される数学的・計算的手法をより詳細に考慮に入れています。これにより、ガスコストの計算が実際の計算負荷とより一致し、イーサリアム上でのModExp演算の利用がより効率的かつ公正になることが期待されます。

提案された新しい複雑性関数は、実際のModExp演算の計算時間をより正確に反映することにより、EIP198の関数よりも改善された適合性を示しています。これは、イーサリアムネットワークの効率性と公平性を向上させるための重要なステップです。

この提案により、ModExpのガスコスト計算がより現実に即したものとなり、イーサリアム上でのModExp演算の効率性とコスト効果が向上することが期待されます。

引用: https://eips.ethereum.org/EIPS/eip-2565

2.GQUADDIVISORの値を変更する

EIP198で定義された「計算複雑性」の式を変更した後、ModExpプリコンパイルのガスコストを実行時間と一致させるために、GQUADDIVISORの値を変更する必要があると述べています。具体的には、GQUADDIVISORを3に設定することにより、ModExpプリコンパイルのコスト（ガス/秒）を他のプリコンパイル、例えばECRecoverと比較して高く設定することを意味します。

GQUADDIVISORとは GQUADDIVISORは、イーサリアムのガスコスト計算式において、計算複雑性の結果を割るための定数です。この値によって、特定の操作のガスコストが調整され、実際の計算資源の消費とより密接に一致するようになります。

変更の理由

計算複雑性の再定義
- ModExpプリコンパイルの計算複雑性をより正確に反映する新しい式に変更したため、その変更に合わせてGQUADDIVISORも調整する必要があります。
ガスコストの整合性
- 新しい計算複雑性の式とGQUADDIVISORの調整により、ModExpプリコンパイルのガスコストが実際の実行時間と一致するようになり、他のプリコンパイルとのバランスが取れた状態を維持することができます。

影響

コストの増加
- GQUADDIVISORを3に設定することにより、ModExpプリコンパイルのガスコストが増加し、結果として、これを使用するアプリケーションの運用コストも高くなります。
ECRecoverとの比較
- ECRecoverはイーサリアム上での公開鍵からアドレスを復元するために使用されるプリコンパイルであり、ModExpプリコンパイルのガスコストがこれよりも高くなることを意味します。
- これは、ModExpのような計算複雑性が高い操作に対して適切なコストを反映させるためです。

この変更は、イーサリアムネットワーク上でのリソース使用とコスト割り当てをより公平かつ効率的にするためのものです。

引用: https://eips.ethereum.org/EIPS/eip-2565

3. 乱用を防ぐため、最低ガス料金を設定

プリコンパイル（特にイーサリアムのネットワーク上で予め定義された特定の計算を行うための関数）を利用する時のガスコストに最低限のコストを設定する提案について述べています。これは、小さな入力値に対してプリコンパイルが過小評価されることを防ぐためです。

イーサリアムでは、トランザクションを実行するために「ガス」と呼ばれる単位が使用されます。ガスは計算リソースの使用量を表し、異なる操作には異なるガスコストが割り当てられます。プリコンパイルは、特定の計算を効率的に実行するために最適化された関数であり、それぞれ固有のガスコストが設定されています。

小さな入力値の場合、計算コストが比較的低いため、プリコンパイルのガスコストも低くなる傾向があります。しかし、あまりにも低いガスコストは、ネットワークのリソースを不必要に消費する攻撃や悪用の余地を提供する可能性があります。たとえば、攻撃者が非常に低いガスコストで大量のトランザクションを送信することで、ネットワークを過負荷にすることができます。

最低ガスコストの設定は、このような悪用を防ぐための対策です。すなわち、どんなに小さな入力値であっても、プリコンパイルの実行には一定量のガスが必要とされ、それによってネットワークのリソース使用が一定の基準以上に保たれることが保証されます。これにより、プリコンパイルが不適切に低価格になることを防ぎ、イーサリアムネットワークの健全な運用を支援します。

テスト

EIP198とEIP2565のプライシングモデルに基づいたModExpプリコンパイルのテストケースとその結果について述べています。これらのテストケースは、プリコンパイルのガスコスト計算の変更が実際にどのような影響を与えるかを示すものです。

表には、異なるテストケースにおけるEIP198とEIP2565によるガスコストの比較が記載されています。 EIP2565の新しいプライシングモデルにより、多くのケースでガスコストが大幅に削減されていることがわかります。これは、新しいプライシングモデルが実際の計算コストをより正確に反映しているためです。

Test Case	EIP-198 Pricing	EIP-2565 Pricing
modexp_nagydani_1_square	204	200
modexp_nagydani_1_qube	204	200
modexp_nagydani_1_pow0x10001	3276	341
modexp_nagydani_2_square	665	200
modexp_nagydani_2_qube	665	200
modexp_nagydani_2_pow0x10001	10649	1365
modexp_nagydani_3_square	1894	341
modexp_nagydani_3_qube	1894	341
modexp_nagydani_3_pow0x10001	30310	5461
modexp_nagydani_4_square	5580	1365
modexp_nagydani_4_qube	5580	1365
modexp_nagydani_4_pow0x10001	89292	21845
modexp_nagydani_5_square	17868	5461
modexp_nagydani_5_qube	17868	5461
modexp_nagydani_5_pow0x10001	285900	87381

この表から、特に大きな数値を扱うテストケース（例えば、pow0x10001）で、EIP2565によるガスコストの削減が顕著であることが分かります。これにより、イーサリアムネットワーク上でのModExpプリコンパイルの使用がより効率的かつコスト効果的になることが期待されます。

セキュリティ

このEIP（Ethereum Improvement Proposal、イーサリアム改善提案）に関する最大のセキュリティ上の懸念は、ModExp（モジュラー指数演算）操作のコストを計算時間に対して過度に安く設定することにより、潜在的なDoS（Denial of Service、サービス拒否）攻撃のベクトルを作り出す可能性があることです。

DoS攻撃とは、システムのリソースを意図的に圧倒し、正当なユーザーがそのサービスを利用できなくする攻撃のことです。イーサリアムのコンテキストでは、攻撃者が非常に低いガスコストで大量の計算集約型のトランザクションをネットワークに送信することにより、ブロックチェーン上のノード（コンピュータ）が過負荷になり、正規のトランザクション処理が妨げられる可能性があります。

ModExp操作は計算集約型であり、特に大きな数値を扱う場合にはかなりの計算リソースを必要とします。このEIPではModExpプリコンパイルのガスコストを再評価し、より正確に計算コストを反映させることを提案していますが、ガスコストを計算時間と比較して過小評価すると、攻撃者が低コストで大量のModExp操作を利用したトランザクションをネットワークに送信することが可能になり、結果的にDoS攻撃に悪用されるリスクが生じます。

したがって、このEIPを実装する時には、ガスコストの設定を慎重に検討し、計算コストとのバランスを適切に取ることが重要です。これにより、ModExpプリコンパイルの利便性と効率性を向上させつつ、イーサリアムネットワークのセキュリティと安定性を保持することが目指されます。

参考

EIP-198: Big integer modular exponentiationEthereum Improvement Proposals

引用

Kelly Olson (@ineffectualproperty), Sean Gulley (@sean-sn), Simon Peffers (@simonatsn), Justin Drake (@justindrake), Dankrad Feist (@dankrad), "EIP-2565: ModExp Gas Cost," Ethereum Improvement Proposals, no. 2565, March 2020. [Online serial]. Available: https://eips.ethereum.org/EIPS/eip-2565.

最後に

今回は「Etherum上でModExpプリコンパイルを呼び出す時のガスコストを定義し、実際の運用コストを反映するための新しい計算アルゴリズムを提案しているEIP2565」についてまとめてきました！いかがだったでしょうか？

質問などがある方は以下のTwitterのDMなどからお気軽に質問してください！

Twitter @cardene777

他の媒体でも情報発信しているのでぜひ他も見ていってください！

https://chaldene.net/

https://zenn.dev/heku

https://mirror.xyz/0xcE77b9fCd390847627c84359fC1Bc02fC78f0e58

Notion | Where teams and agents work togetherMade in Notion, the connected workspace where AI agents and teams organize docs, projects and knowledge together.Notion