月別アーカイブ: 2018年4月

貧民的DAppsプログラミング

ビットマップによる注文情報保持

前回の続きです。Gasを節約しつつ、オーダーブックをオンチェーンで保持する方法の解決編です。

アセンブラやC言語でプログラムを書いていた(る)人は、ビット操作というものに馴染みがあると思います。ブロックチェーンで、Gasを節約しながらできるだけ大きめのデータを扱おうとするとき、ビットマップで何とかできないかと考えると、けっこう解決できることがあります。大きめのデータを圧縮した形にしたり、複数回の操作を1回にまとめられたりします。

このやり方は、オーダーブックで扱う価格に制限をかけることで実現できます。

  • 価格の範囲を 0.000001 ~ 1000000(106~10-6)に制限する
  • 有効数字3桁とする

株のことはよく知らないんですが、こういう制限をしても問題にはならないようです。

この制限によって、とりえる価格が 10800 種類に制限されます。これを、10800ビットのビットマップで表現します。”1″のビットはその価格で注文があり、”0″のビットは注文がない価格です。

オーダーブックのビットマップ

とりえる価格を制限したオーダーブックを、ビットマップで表現した図(出典:https://ubitok.io/2017-08-24-maintain-order-book-blockchain-bitmap/

最小の価格が一番左の0.000000100、最大の価格が一番右の999000、中間付近に1.23があるということですね。有効数字3桁に制限されているので、997000、998000、999000という並びになるんだと思います。有効数字とか懐かしい・・・。最小価格も同じでしょう。

Solidityで実装するなら、uint256の43要素の配列を使えばよいわけです(10800 / 256 = 42.1875)

ヤック・デカルチャー・・・(最近マクロスFにハマっています)

ビットマップを使うことまでは、いつも最初に思い浮かびはしますが、株の価格をこんな形で保持する発想は、Web屋の脳のままでは難しいでしょう。作ろうとしているシステムで受け入れられる制限を考えて、ビットマップに落とし込む方法を考えるのは、なんだか楽しそうです。(雑誌のアセンブラコードを読んで悦に入っていただけの)昔を思い出します(笑)。

ビットマップオーダーブックから注文を検索するSolidityコードについては、次の上のURL下部にアイディア部分だけ示したものが、下のURLに全体が掲載されています。

https://ubitok.io/2017-08-24-maintain-order-book-blockchain-bitmap/

https://github.com/bonnag/ubitok-contracts/blob/master/contracts/BookERC20EthV1.sol

富豪的プログラミングがどうこうと、2000年代にいわれてました。ブロックチェーンプログラミングでは、けっこうチマチマと節約しながらプログラムするシーンが戻ってきたようです。

Web以前を思い出させるEthereumのDApp開発

90年代以前のプログラミングを思い出させるDApps開発

パブリックチェーンに放流するDAppを書いていますと、ちょっとしたことに割りと多目のGasを必要とすることがわかり、驚いた次第です。これまで、Erisやなんかのプライベートチェーン向けの開発が中心だったので、実感として分かりませんでした。ちょっと大きめの2次元配列を作るだけで何百円(Gas PriceをGas Stdと同じとして)とかかり、PHPとRDBで適当に組んでいた間、データ量や計算量を軽視する悪癖を身に付けたような気がします(笑)

パブリックチェーン向けのDAppの開発は、計算量やデータ量を割りと細かく気にしながら書くという意味で、C言語全盛の90年代に活躍していたプログラマーは、懐かしい気持ちになるかもしれませんね。あるいはゲームを開発しているような方は、現在進行形でこの手の問題と格闘されているかも。

Web系しかやったことがない人は馴染みが薄い、純粋アルゴリズム系やデータ構造系の知識、ビット演算の知識などがあると、節約がしやすくなります。DBが気づかないところでいろいろやってくれていたことに、気づくかもしれません。

オンチェーンでオーダーブックマッチングを行う解説記事

https://ubitok.io/2017-08-24-maintain-order-book-blockchain-bitmap/

オーダーブックをオンチェーンで保存・実行する方法の記事

ブロックチェーンへのうまいデータ格納方法を調べていて見つけたのが、この記事です。株などのオーダーブックを、Ethereumブロックチェーン上にすべて保持してマッチングを処理する方法について、解説しています。データの更新があるトランザクションの場合、Gasを必要としますので、その量をいかに少なく済ませる実装にするかというものです。この記事から、要点を解説します。

オーダーブックですので、買い注文と売り注文をマッチングさせることになります。Web+DB環境など非分散システム上で普通に組むと、データを次のように価格から注文数へのマップとして持たせることになります。

そして、プログラム言語がJavaならTreeMap(よく知らないですけど)、PHPなら配列を使って実装することになります(というかDBに入れますけどね、普通)。

このマッピングに使うデータ構造は、一般的にTree(木)、とりわけ順序木というものになります。木・・・どうなんすかね、こういう名前付けの世界。自然にあるものをこういう抽象的な世界に持ってきて使う文化は、私は好きですけど。

オーダーブックのデータをTreeに格納した状態(出典:https://ubitok.io/2017-08-24-maintain-order-book-blockchain-bitmap/

各ノードの数字が価格です。マッチする売り注文を探すのは、木からある価格を持つノードを探す処理です。これは順序木といって、あるノードの左はそのノードの数より小さい数を持つノードだけ、右は逆に大きい数を持つノードだけを、子ノードとして持つ、そういう木構造です。

で、引用もとの記事のいうように、木構造がソリューションとして理想的なのは、平均的なケースでしかないと。オーダーブックの仕様に注文の削除があるので、そのとき最悪の場合木全体を書き換えないといけなくなってしまいます(木というのは、そういうデータ構造です。興味がある方は、データ構造の解説書などを見てみてください)。大量のWriteが発生するので、Gasも高額になってしまいます。

じゃあ、他にいい方法はないか?次に例として出ているのが、連結リストです。

オーダーブックのデータを連結リストに格納した状態(出典:https://ubitok.io/2017-08-24-maintain-order-book-blockchain-bitmap/

連結リストなら、更新のとき書き換える箇所は一定です(挿入・削除する要素と、その前後の繋ぎ直しだけ)。

しかし、やっぱり連結リストにも問題があります。注文をたくさん出すユーザーがいると、その人が原因で、ほかのユーザーがGasを多く支払わないといけない状態になってしまうのです。これは、連結リストは走査するとき、リストの一方の端から順にたどるしかないことが理由です。上の図で ”1.23 ” の価格のところへ行くには、 “1.20” から2つ移動する必要があります。その分のコストが請求されるのです。

こういったGas消費量節約の問題を、ビットマップを用いてうまく解決する方法が紹介されているので、次回解説します。