アルゴリズムとかオーダーとか

仕事で勉強したことなどをまとめてます

EthereumのPending TransactionとTransaction Poolについて

今回はEthereumで発行されたTransactionがPending状態である場合にどの様にpoolに保持されているのか。また、Transaction Poolはどの程度のtransaction数を保持するのか?などのTransaction poolの動きについて調べたことをまとめていきたいと思います。

今回の説明はgo-ethereumのソースを参考にしております。
github.com
transaction poolの仕様についてはyellowpaperで特に定義されているわけではないっぽいのでnode実装ごとに若干異なる可能性があります。

Transactionを受信した時の動作概要

Ethereum nodeがTransactionを受信したときは次の様に処理されます。

  1. 有効なTransactionかチェックする。
  2. poolに空きがあればTransactionをpoolに追加する。
  3. 定期的なloop処理でpendingへの昇格や、poolのお掃除を行う。
  4. 新しいBlockを受け取った時に、pending Transactionが含まれていれば、pending queueから削除する。

nodeでは、常に新しいTransactionを受け取るたびに、1.および2.の処理が実行されます。また、定期的および新しいBlockを受け取るたびに、3.と4.の処理が実行されます。新しいTransactionはそれが問題のないものか検証してpoolに追加され、その後、定期的にpoolの状態をお掃除する。という感じの動作になります。

これらの動作についてそれぞれ詳しく見ていきます。

有効なTransactionかチェックする

まず、poolに以下の全てのチェックに合格したものが有効なTransactionと見なされます。

  1. まだqueue(pending含む)に格納されていないこと。(重複チェック
  2. 全体のサイズが32KB以下なこと(geth特有のDoS対策コードっぽい)。
  3. value値がマイナスではないこと。
  4. 指定されたgas limitがblock gas limitを超えていないこと。
  5. 署名が正しいこと。
  6. 指定されたgasPriceが最低値以上であること。
  7. nonceが最後にblockに格納されたTransactionのnonceより大きいこと。
  8. senderが指定された gas limit * gasPriceを支払えるだけのETHを保有していること。
  9. 指定されたgas limitがTransaction発行に必要な最低gas量以上であること。

これら、9つの検証に全て合格したTransactionがpoolに追加されます。
次は、これらの検証に合格し、正当と見なされたTransactionがpoolにどの様に格納されていくかを説明します。

poolに空きがあればTransactionをpoolに追加する

検証に合格したTransactionであれば、poolに空きがある場合はpoolに追加されます。poolに空きがない場合は、ある条件を満たしたTransactionのみがpoolに追加されます。
上記の動作を詳しく説明するために、まずはTransaction Poolの容量について説明します。

Transaction Poolの容量

Transaction Poolの容量としては4つの種類が設定されています。

  1. AccountSlots: アカウントごとのpending transactionの容量。default値は16
  2. GlobalSlots: 全てのpending transactionの容量。default値は4096
  3. AccountQueue: アカウントごとのnon-executable transactionの容量。default値は64
  4. GlobalQueue: 全てのnon-executable transactionの容量。default値は1024

となっています。non-executable transactionについては後述します。上記の容量区分からもわかる通り、poolにはまず大きく2つの箱が用意されています。1つ目はpending transactionが入る箱(これを以降はpending listと呼ぶ)。そして、もう一つはnon-executable transactionの入る箱(これを以降はqueueと呼ぶ)です。

受信したTransactionは全てまず、queueに入れられます。その後すぐに定期loop処理でnonceがチェックされて、nonceの条件を満たすものがqueueからpending listに移されます。
受信したTransactionを他のnodeに伝搬するのはこのタイミングになります。つまりqueueからpending listに移すと同時にそのtransactionが他のnodeへ伝搬されます。

これらの容量の定義とdefault値の設定が書いてあるソースの箇所は以下になります。

次は上記で説明を割愛したnon-executable transactionについて説明します。

non-executable transaction

non-executable transactionとは、現在のblockに格納されているTransactionのnonceに+1した値よりもより大きなnonceを持ったTransactionのことです。とあるアカウントを A 、あるアカウントAが発行したTransactionを Tx(A)、現在のblockに格納されているアカウントAのTransactionを Tx_c(A)、Transactionのnonceを Tx(A).Nonceとした場合、次の式を満たすものがnon-executable transactionです。

 Tx(A).Nonce > Tx_c(A).Nonce

また、pending transactionは上記の定義を用いると下記の式を満たすものになります。

 Tx(A).Nonce = Tx_c(A).Nonce + 1

nonceはあるアカウントから発行されたTransactionの数であり、blockに格納する順番を示すものです。Ethereumでは現在blockに格納されているtransactionが持つnonceの+1したnonceを持つtransaction(つまりpending transaction)が次のブロックに格納されます。nonceの値は常に1つずつインクリメントされるため、より大きな値を指定した場合は、間の値を埋めるnonceを持つtransactionが発行されるまで、それらのtransactionはblockに格納されません*1。つまり、すぐには実行ができないtransactionであるため、non-executable transactionと呼ばれます。

poolが一杯の場合に、Transactionがpoolに格納される条件

漸く、poolが一杯の場合にTransactionがpoolに格納される条件についての説明に入ります。
poolで指定されている前述した4つの容量制限のどれかに引っかかった場合は、Transactionは以下の条件を満たす場合にのみ、poolに格納されます。

  • poolに入っているTransactionの中で最小のgasPriceよりも大きなgasPriceが指定されている場合。

受信したTransactionが上記条件を満たしていた場合、poolの中にある最小のgasPriceを持つTransactionと受信したTransactionが入れ替えられることになります。上記条件を満たさない場合は、エラーとなり受信したTransactionは捨てられます。
nonceに関するより詳しい説明は次の記事を参照ください。
kb.myetherwallet.com

ちなみに、localなアカウント(多分geth node自体が管理しているaddress)から発行されたTransactionについては上記の条件は無視され、優先的にpoolに格納されます。

定期的なloop処理でpendingへの昇格や、poolのお掃除を行う。

これまでは、受信した、もしくはlocalで発行されたTransactionがどの様にpoolの中のqueueの領域に格納されるのかを見てきました。ここからは、queueに格納されたTransactionがpending listに昇格する処理、および、定期的に行われるpoolの整理の処理を説明します。

Ethereumのnodeでは定期的にpoolの中身であるpending listとqueueの状況を監視・管理しています。定期的に実行される処理は以下の3つになります。

  1. queueからpending transactionの条件を満たすものをpending listに昇格*2させる。
  2. queueおよび、pending listの容量が超えていた場合は、gasPriceの低いTransactionを削除*3する。
  3. queueに長時間格納されているTransactionを削除する。

1.と2.の処理はそのままなので特に詳しくは説明しません。ここでは3.の処理について詳しく見ていきたいと思います。

長時間格納されているTransactionを削除

pending transactionはある意味、いつかはblockに格納されることがわかっているので特に時間制限は設けられていません。逆に、non-executable transactionについては、間のnonceを埋めるTransactionが発行されるまで絶対にblockには格納されません。そのため、アタックベクターとなり得るので、queueに格納されたTransactionは時間制限によって削除される様になっています。

queueからは以下の条件に合致する古いTransactionを削除します。

  • アカウントごとに最後に投げられたTransactionの時間を取得する
  • 上記の時間が現在より3時間以上立っている場合は、そのアカウントが発行したTransactionをqueueから全て削除する

該当ソースは以下を参照ください。
queueから古いtxを削除する処理(tx_pool.go#L344-L348)

古いTransactionを削除する場合は、Transactionごとに個別の発行時間を見るのではなく、アカウントごとに、最後にTransactionを発行した時間を元に判断されます。

新しいBlockを受け取った時のpoolの整理

最後に、新しいBlockを受け取った時のpoolの整理の処理について説明します。基本的には定期的なloop処理と同じ処理が行われますが、新しいBlockを受け取った場合は追加として以下の処理も行われます。

  1. 新しいBlock情報を元にStateDBを更新する
  2. 新しいStateDBを元に、Blockに格納済みのTransactionをpending listから削除する。
  3. 新しいStateDBから、各アカウントの残高を参照し、queueの中から、支払いが不可能になったTransactionを削除する。
  4. 新しいStateDBを参照し、Blockに格納済みのTransactionのnonceより小さいnonceを持つTransactionをqueueから削除する。

となります。ここも特に複雑な処理はしていないため詳細な説明は割愛します。簡単にまとめると、新しいBlockのデータを適用させることで、無効となったTransactionを削除するという処理が行われます。
該当ソースは以下を参照ください。
demoteUnexecutablesの処理(tx_pool.go#L1115-L1158)

まとめ

nonceの扱いによって、すぐにblockに格納されないTransaction(non-executable transaction)が生成できることは知っていましたが、non-executable transactionがどの様に扱われるのかがよく分かっていなかったので今回調べてみました。
また、transaction poolの処理を調べたことで以下のことも新たに知ることができました。

  • 1つのアカウントで一度にnodeに送信できるTransactionは64個まで。
  • 1つのブロックには1つアカウントから発行されたTransactionが16個までしか含まれない。(別のmining appを使っている場合はこの限りではないかも?)
  • non-executable transactionは伝搬されない。
  • 多分、pending transactionは理論上いつまでも残り続ける。


そのほかにも、poolを埋め尽くす様な攻撃を仕掛けてきたアカウントをblacklistに入れたり、64block以上のreorgが起きた時に同期を諦めるwなども実装されていることがわかりました。

この辺りの基本的なことは興味のある人は少ないかもしれませんが、特に詳しく説明しているブログなども見当たらないので、何かの助けになればと思いまとめてみました。
自分もまだ完全に理解できてはいないので、何かしら疑問点などありましたらぜひ質問してください。

*1:Ganacheを使っているのに、MetaMaskでsignしたTransactionがなかなかblockに入らないという経験をしたことがある人はそこそこいるはず。。。

*2:該当ソース:https://github.com/ethereum/go-ethereum/blob/master/core/tx_pool.go#L752-L789

*3:該当ソース:https://github.com/ethereum/go-ethereum/blob/master/core/tx_pool.go#L653-L667