EIP-1559のトランザクションプールの動向
TL;DR
EIP-1559はトランザクションに手数料に影響を与える新たなフィールドを追加するため、トランザクションプールを管理するアルゴリズムも変更する必要がある。
EIP-1559ではトランザクションの評価が毎ブロックごとに動的に変化するため、ナイーブな手法では毎ブロックごとにトランザクションプールを再構築する必要がある。
先月minaminao.iconが見つけたEIP-1559トランザクションプールのアルゴリズムは、3つの平衡二分探索木を組み合わせることで、プールの再構築が必要無く、収益を最大化でき、需要が安定しているほど高速に動作可能である。
cipepser.icon かっこいい
前提: Ethereumのトランザクション手数料メカニズム
Ethereumのトランザクション手数料は、トランザクションの実行で消費したgasgas_usedとユーザーが指定するgasの価格gas_priceをかけ合わせた値gas used * gas priceである。そのため、マイナーは基本的にnonceを考慮した上でgas_priceが高い順にトランザクションを採用すれば最適な収益を得られる。この手数料メカニズムはファーストプライスオークションと呼ばれる。
現状Ethereumは毎ブロックが満杯になるほど利用されているため、ファーストプライスオークションだと適切なgas_priceの予測が難しく、手数料の過払いやトランザクションの再送が発生してしまう問題を抱えている。
上記課題を解決するために、EIP-1559はEthereumの手数料メカニズムに次の変更を加える。
ステートにbase_feeと呼ばれるgasあたりの手数料の基準値を導入する。
トランザクションのgas_priceを無くし、代わりにmax_miner_bribe_per_gasとfee_cap_per_gasを導入する。これらはgas_price同様ユーザーが指定できる。
トランザクション手数料として最低でもbase_fee * gas_usedを支払わなければならない。
fee_cap_per_gas * gas_usedを超える手数料は支払われない。
マイナーは最大max_miner_bribe_per_gas * gas_usedの収益を得る。
マイナーに支払われないbase_fee * gas_usedはバーンされる（燃やされる、二度と使えない）。
つまりユーザーの支払う手数料は、min(max_miner_bribe_per_gas + base_fee, fee_cap_per_gas) * gas_used。
cipepser.icon fee_cap_per_gasだとバーンなしです？
nrryuya.icon > いえ、base fee分はburnです
cipepser.icon なるほど。主語は「ユーザの支払う手数料」でしたね。あざます。
https://gyazo.com/de3c59e2f73fcdc68af663bb10c4d62c
base_feeはブロックサイズごとに調整される。EIP-1559は、ブロックのサイズを倍、つまりブロックガスリミットを倍にする。さらに、ブロックサイズにターゲットサイズblock.gas_targetが定められる。ターゲットサイズは最大のブロックサイズの1/2である。平均的にブロックのガス消費量block.gas_usedがターゲットblock.gas_targetになるように、base_feeはブロックごとに調整され、ターゲットサイズよりもブロックサイズのほうが大きければbase_feeは増額、小さければ減額される。
https://gyazo.com/74f264e89747f724991e8c9d6dff1705
これにより、需要と供給のバランスが調整され、基本的にはあるブロックに取り込まれるトランザクション全てがgasに同じ額を払えば良くなり過払いが緩和する。また、block.gas_targetはブロックガスリミットよりも小さいため、需要が安定していればトランザクションは次のブロックに必ず取り込まれるため、再送する必要がなくなる。ただし、需要が急増した際には、一時的にmax_miner_bribe_per_gasのファーストプライスオークションになり、従来と同じく過払いと再送の問題が発生する。
EIP-1559トランザクションプール
EIP-1559はトランザクションの構造を変えるため、トランザクションプールを管理するアルゴリズムも変更する必要がある。マイナーが手数料を最適化したい際、従来はgas_priceとnonceさえ考えれば良かった。EIP-1559ではgas_priceが無くなり、トランザクションのmax_miner_bribe_per_gasとfee_cap_per_gas、さらにステートのbase_feeを考慮する必要があり、パラメータの個数が2つ増えて複雑性が増している。
従来のトランザクションプールでは、nonceを考慮してgas_priceが高い順にトランザクションをブロックに取り込むのが最適な戦略である（ただし、トランザクションごとにgas_usedは異なるため、厳密にはgas_priceが高い順に取り込むよりも収益を向上できるケースが存在する）。各クライアントの実装は、この戦略を実現するアルゴリズムが実装されているが、アルゴリズムの中身は異なる。トランザクションプールのトランザクション数を$ nとする。
cipepser.icon そぼぎ：nonceを考慮というのは、どういう？
minaminao.icon 単なるgas_priceが高い順だとnonceの条件上、先に採用できないトランザクションが存在することがあり、その対処ですね。例えば、あるユーザーのnonceがkのトランザクションとk+1のトランザクションがあればkのトランザクションの方を優先します。
cipepser.icon 完全理解
cipepser.icon $ nってどれくらいなんですか？平均とか中央値など目安を知りたく。
minaminao.icon Gethのトランザクションプールの最大トランザクション数はデフォルト値は8,000です（後述）。
cipepser.icon 後述されてました :bow_tateburu:
Geth (Go)は、max-heapを用いてトランザクションの追加を$ O(\log n)、最大gas_priceのトランザクションの取得及び削除を$ O(\log n)で行っている。ただし、max-heapは任意のトランザクションの削除は効率的に行えないため、1~3秒ごとにトランザクションプールのトランザクションを全てチェックし不必要なトランザクションをまとめて削除及びmax-heapの再構築（再ソート）を$ O(n\log n)で行っている。 cipepser.icon 取得はheapの先頭を持ってくればいい（arrayで構築すればarray[0]）ので$ O(1)でできそうですね。
minaminao.icon 取得は$ O(1)ですね！「取得/削除」 => 「取得及び削除」に修正
cipepser.icon add/removeはheapの再構築に掛かる時間は無視してそうですね。$ n個の要素をadd/removeすると合計で$ O(n)掛かると思うので。
minaminao.icon リサイズは$ O(n)で、償却$ O(1)ですね。再構築 is ゼロから$ n個のトランザクションを追加してheapを構築し直すことを意味しており$ O(n \log n)です。
cipepser.icon 1~3秒でバッチ的に削除するの頭いい
OpenEthereum (Rust)は、B-treeを用いてトランザクションの追加を$ O(\log n)、最大gas_priceのトランザクションの取得及び削除を$ O(\log n)、任意のトランザクション削除を$ O(\log n)で行っている。Gethと異なり、任意のトランザクションの削除を効率的に行えるため、再構築は必要ない。 理論的には、OpenEthereumのようにB-treeを用いるほうmax-heapを用いるより計算量は良いが、Gethの手法でも現状機能しているため現実的には問題ないと思われる。
EIP-1559の場合を考えてみる。あるEIP-1559トランザクションのgasあたりのマイナー収益は、min(fee_cap_per_gas - base_fee, max_miner_bribe_per_gas)である。従来のトランザクションはどんな状況でもgasあたりのマイナー収益は一定のgas_priceであったのに対し、EIP-1559におけるgasあたりのマイナー収益はbase_feeによって変動する。この変動は次の図のようになる。
https://gyazo.com/58a448498f9fd0793668722ebc24cdc9
base_feeが上がりfee_cap_per_gas - max_miner_per_gasを超えると、gasあたりのマイナー収益が減少し始める。このように、EIP-1559ではトランザクションの評価が毎ブロックごとに変わるため、マイナーが最適な収益を獲得するために用いていた単一のmax-heapやB-treeを持つアプローチを見直す必要がある。
EIP-1559が特徴的なのは前述した通りblock.gas_usedがblock.gas_targetに近づくように調整されるため、トランザクションプールで管理するトランザクション数が大幅に減ることである。従来はGethであればデフォルトで8,000のトランザクションを保持していたが、EIP-1559であれば需要が安定している時は数百程度になると言われている。つまり、計算量で用いていた$ nが小さくなるため、需要が安定していればナイーブな手法を用いても問題ないと言われている。よって現段階では、Gethのような一定期間ごと及びブロックごとにトランザクションプールを再構築するアプローチが採用予定であり、議論されている。
最適収益を高速に実現するEIP-1559トランザクションプール
EIP-1559のトランザクションは、base_feeによってトランザクションの評価が動的に変化するものの、「評価が変化しているトランザクション集合$ D」のトランザクション同士の相対的な評価順序は変わらない。また同様に「評価が変化しないトランザクション集合$ S」のトランザクション同士の相対的な評価順序も変わらない。この2つの集合をそれぞれ平衡二分探索木で管理し、集合$ Dと集合$ S間のトランザクション移動をもう1つの平衡二分探索木で管理することで上述の高速化が可能になった。先程の$ kはこの移動するトランザクション数である。
今後のコミュニティのトランザクションプール関連の動きとしては、引き続きトランザクションプールのクライアントレベルの厳密な実装が進められ、各種トランザクションプールのパフォーマンスをローカルあるいはEIP-1559の大規模テストネットを用いて検証するフェーズに入る。