Bitcoin CoreのAmount Compression

このエントリーをはてなブックマークに追加

Bitcoin CoreのChainstateDBの’C’レコードのamount記録時に利用されている謎の圧縮方式 Amount Compressionについてのメモ。

どこで使われているのか?

このAmount Compressionは簡単に言うと、Bitcoinで通貨量の表現に利用されているSatoshi単位の数値のデータサイズを圧縮するという目的の元に作られている。具体的には0を減らして表現するということに主眼が置かれおり大半のtxoutのamount valueが1バイトか2バイトで表現できる(とのことだ)。この奇妙な方式がいつ誰によって導入されたかというと、sipaというコミッターにより2012/6/16に下記のコメントとともにコミットされている。2018/10現在の0.16.3においてはcompressor.cpp以下に存在するが、コミット当時はmain.cppの最下部に追加されている。

Compact serialization for amounts
Special serializer/deserializer for amount values. It is optimized for values which have few non-zero digits in decimal representation. Most amounts currently in the txout set take only 1 or 2 bytes to represent.

Compact serialization for amounts · bitcoin/bitcoin@0fa593d
https://github.com/bitcoin/bitcoin/commit/0fa593d0fb3a6f731a31610e98ce6bfd6a50a96c

また、さらにこの半月後には同じくsipaにより現在のBitcoin Coreにおける内部構造の原型となったUltraprune(ウルトラプルーン)と呼ばれる一連の変更がコミットされている。Ultrapruneの全容についてはまだ理解が追いついていないので改めて書きたいと思うが簡単に言うとUTXOをブロックデータを舐めまわさずとも高速に取得できるようにするための仕組みとデータ構造、実装を含んだフレームワークであり、2012/10/21にIssue:1677がメインラインに取り込まれた。余談だが、sipaさんは本名Pieter Wuilleと言い、金融機関向けサイドチェーンを開発、提供しているBlockstreamの創業者のようだ。またSegwitの時のマージも担当している。

Topic: Ultraprune merged in mainline
I’ve just merged my “ultraprune” branch into mainline (including Mike’s LevelDB work). This is a very significant change, and all testing is certainly welcome. As a result of this, many pull requests probably don’t apply cleanly anymore. If you need help rebasing them on the new structure, ask me.

Ultraprune merged in mainline
https://bitcointalk.org/index.php?topic=119525.0

そのためBitcoin CoreのUTXO管理は

  • Ultraprune前(ver < 0.08)
    この当時はブロックやUTXOの管理にBDBをつかってたらしい
  • 初代Ultraprune(0.08 <= ver < 0.15)
    ここからブロック用、UTXO用のLevelDBの利用が始まる
  • 現行のUltraprune改(0.15 <= ver)
    これまではvoutが1レコードに複数格納されていたのがTransactionHash+voutIndexをKeyとして、Valueにはブロック高とAmount、hashが格納されることになった。多分obfuscate_keyによるvalueの難読化もここから始まってる。

と変遷していることになる。なお、このUltraprune改のドキュメントはマジで驚くほど少ない。

Amount CompressionのRuby実装と振る舞い

本題に入るとAmount Compressionは下表のような可逆圧縮を行う、基本的には1桁目が0の個数、2桁目以上が0を省いた後の数値の変換値を表現している。

uint64Compressuint64Compress
001 110992
111 000 000 0009
21110 000 000 00010
98110 000 000 0019000000001
10210 000 100 000900006
1191153 000 0001377
10031 530 000 0001378
1 00041 532 100 000137886
1 100931 532 123 400137891103

直感的でなく奇妙な振る舞いをする。
基本的には9桁以下が10で割り切れる数値であれば元の数値よりバイト数を節約できる。一方でどんなに0が多くても1satoshiとかが出現すると圧縮できないどころか桁が増加してしまう。そのため将来Bitcoinがデフレ傾向が続き、マイクロペイメントが主流になった時Ultrapruneも見直しが入るかも知れない。(※まあ実際にはオフチェーンで決済させれてまとまってからオンチェーンになるだろうから心配ないかも)
実装は下記となる。基本的にはBitcoin Coreのcompressor.cppのCompressAmountとDecompressAmountをRubyへ移植しただけである。

以上がAmount CompressionのRuby実装となる。Ultraprune構造等については後日改めて触れてみたい。

ちょっとした募集

諸般の事情からこの場で詳細を書くことは出来ないが、もしこの記事を読んで、BitcoinやEthereumなどのブロックチェーンに興味があり、こいつとフルタイムで一緒に仕事するのも面白いかも知れないという奇特なソフトウェアエンジニアがいたら、aboutに書いてあるTwitterから是非私に連絡をとってみて欲しい。東京でしかるべく待遇で採用してくれるところを紹介したいと思う。