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

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

dydxをローカルに構築して遊んでみる。

今回はDefiでおなじみのdydxのv2 protocolである、soloで遊ぶためにローカルでsoloを構築する手順を説明します。
dydx.exchange

マージントレード、デリバティブトレードとして有名なdydxですが、最近プロトコルがバージョンアップされv2 soloとなりv1 expoとは大幅にコントラクトの様相が変わっております。特にマージントレードの幅広い戦略をサポートするために考案されたActionsのプロトコルは非常にメタ化された概念であり、ソースコードからその実態を掴むのは容易ではありません。
そのため、本記事ではdydx soloで追加されたActionsを実際に動かしながら体験するために、dydx soloをローカルに構築する手順を解説します。
なお、本記事ではdydx soloに関する詳しい説明やActionsを利用したマージントレード戦略の具体的な記述方法については解説しないのでご注意ください。

続きを読む

Contract Application Binary Interface(ABI)とは

今回はEthereumでDappsを開発した経験のある人は1度は目にしたことがある、「ABI」について解説します。

ABIの仕様は以下のSolidityのドキュメントにまとめられています。
solidity.readthedocs.io
ABI仕様の技術的な説明は上記ドキュメントに譲るとして、本記事では、ABIの目的やABIがどのように参照・利用されているか?に焦点を当てて解説します。

続きを読む

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

Constantinopleで導入されるEIP-1014について

今回は、いよいよ来週の2019/01/16にupdateされるConstantinopleで導入されるEIPのうちの一つである、EIP-1014について解説します。
eip-1014.mdにも書かれているとおり、これはstate channelに対して非常に重要な機能であり、個人的にConstantinopleで導入される機能の中でも一番注目しています。

では早速EIP-1014について解説していきます。

続きを読む

secp256k-1には整数解は存在しないことの証明

久しぶりのブログ投稿になります。こんにちは。今回はsecp256k-1であるy^2=x^3+7に整数解は存在しないことの証明を行いたいと思います。

元々はgemとC Libraryで書かれたsecp256k-1のライブラリが返す加算結果が違っていて、どっちのライブラリが正しい値かを手計算でも検算できそうな整数解となる点はどこかという話が発端でした。


この話題のなかで、「secp256k-1 integer」などでググったところタイトルの通り、整数解は存在しないというhomeworkを見つけました。今回ではこのhomeworkの回答をみながら自分なりに証明をしていきたいと思います。

続きを読む

ganache-cliのデータを永続化する

今回はganache-cliのデータをファイルに吐き出して永続化する方法について説明します。
ganache-cliのデータを永続化できるとDappsのサンプルを提供する時にセットアップ済みのnodeもセットで提供できるため、非常に有用ですよね。
0x protocolでもganache-cliのsnapshotを提供しており、すぐにsampleを動かせるようになっています。
https://0xproject.com/wiki#Ganache-Setup-Guide0xproject.com

それでは早速、ganache-cliでデータを永続化する方法を説明します。と言っても非常に簡単だったので、さらに応用してevm_snapshotも利用した復元ポイントを持ったdumpデータの作成方法も合わせて説明したいと思います。

続きを読む

IntelliJ Idea(Ultimate)からmochaのdebuggerを使う

今回はタイトルの通り、IntelliJ Ideaを使ったmochaのdebuggerを使う環境構築の方法を紹介します。
いい加減、mochaのtestを書くためにconsole.logで変数を追っていくのに疲れたので、重い腰をあげてdebugger環境を作ってみました。

結論としては非常に簡単に作れました。なお、Ultimate版のみ対応とのことです。

では以下で構築方法を簡単に説明します。

続きを読む