LEB128とBitcoin CoreのBase128の違い

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

前回の記事でLEB128(正しくはUnsignedなのでULEB128)について書いたのだが、そもそも論としてBitcoinCoreで利用されているBase128とは微妙に結果が異なっておりこれはおかしいとBitcoin Core 0.16.3のコードを良く確認するとやはり別物であったので、各表現の整理とBitcoin CoreのBase128のRuby実装を再掲載したいと思う。

Bitcoin Core界隈での奇妙な表現の数々について

Bitcoin界隈では整数の表現について幾つかの特徴的な方法がある。まずコードを全て確認しているわけではないので(マサカリ対策として)全てを網羅していない事を断っておく、その上で現時点で私が認識しているBitcoin界隈での整数表現には下記の3つがある。

  1. BitcoinのプロトコルのVariable Length Integer
    BitcoinでVarIntと言ったら通常はこれを指し、Protocol Documentationで定義されている。トランザクションやブロック上のIntのByte表現に利用され符号なし64bit整数まで表現できる。簡単に言うと253未満の数値は1byteで表現し、それ以上は1byte目をtype表現(FD=uint16,FE=uint32,FF=uint64)として利用しlength(1,3,4,9)を決定する。つまり1byte目が0xFCなら252として扱い、0xFDなら更に後続2byte取得して16bit整数として扱い、0xFFなら更に後続8byte取得して64bit整数として扱うということだ。
  2. BitcoinCoreで利用しているVarInt
    BitcoinCoreの内部で利用されているByte表現で、ULEB128類似の方式であるが、こちらはMSBから並ぶのでBigEndianである。あえて言うならUBEB128類似(後述)と言ったところだろうか。基本的には無限のサイズの整数を表現できる方式で整数を7bit毎に分割し最下位の7bitには先頭に0付与し8bit=1byte、それ以外は先頭に1を付与し8bitにした後、8bit目から1を減算(ここが類似という理由)し1byteとしたものを配列として構成した後に結合する。
  3. BitcoinCoreで利用しているAmount Compression
    これは内部的には全てSatoshiなどで表現されるbtcの数量(uint64)を圧縮して表現するための整数変換方式であり0が多いほど返還後の桁数が小さくなる一方で0の存在しない数値は桁が大きくなる。2のVarIntと合わせて利用されることが多い。

1、2は整数をByte表現に変換する方法で3は整数を圧縮する方法である。1についてはWiki自体も分かりやすい上に、プロトコルなので結構色んな所で実装され解説されている。一方で2や3についてはBitcoinCoreの実装の話なので情報が極端に少ないのである。なお3のAmount Compressionについては別な機会に記述したいと思う。

BitcoinCoreのVarIntとULEB128について

さて前回の記事ではULEB128を稚拙なRubyで実装してドヤってしまい大変恥ずかしいのだが、よくよく実行してみると下記の様にBitcoinCoreのVarInt(Base128風)とULEB128の数値が異なっていた。

整数HexULEB128BC版VarInt
1270x7f7f7f
1280x8080018000
46600x1234b424a334
655350xffffffff0382fe7f
6242450x98765e58e26a58d65

この時ULEB128では下記のような処理を行っている

624485                      変換対象整数
10011000011101100101 2進数表現

MSB ------------------ LSB 10011000011101100101 2進数表記 010011000011101100101 7bitで割り切れるようにMSB側に0埋め処理 0100110 0001110 1100101 7bit単位で分割 00100110 10001110 11100101 MSB側の最初の7bitの最上位bitには0を付与
それ以外のグループの最上位bitには1を付与
11100101 10001110 00100110 バイトオーダーの反転(Little Endianへ変換) 0xE5 0x8E 0x26 16進数表記 → 0xE5 0x8E 0x26 結合

一方でBC版のVarIntでは下記の様に処理を行っている

MSB ------------------ LSB
      10011000011101100101  2進数表記
     010011000011101100101  7bitで割り切れるようにMSB側に0埋め処理
 0100110  0001110  1100101  7bit単位で分割
10100110 10001110 01100101  7bit単位でMSB側から順に最上位8bit目に
1を付与し、最後には0を付与する
10100101 10001101 01100101 LSBの最終グループ以外から1を引く 0xA5 0x8D 0x65 16進数表記 → 0xA5 0x8D 0x65 結合

いずれの方式もデコード時はMSB側から1byte毎に読み込み、最上位bitが0になるまで次の読み込みを行う。それぞれ特有の処理(LEB128ではバイトオーダーを反転、BC版VarIntでは最終byte以外に1を加算)を行う。その後双方とも各byteから下位7bitを取得し結合すれば元の値が得られるという仕組みである。
それぞれの実装は下記になる。

ULEB128のRubyによる実装

下記実装だが前回とは異なり、BitcoinCoreのコードを参考にビットシフトで実装してみた。具体的にはエンコード時は対象数値から下位7bitを取得、最上位に1bit付与(0x80をOR)して配列に追加、その後対象数値を7bit下げ最初から処理を繰り返す。なお、配列に追加後に対象数値が0x7F以下であれば(つまり最もMSB側であれば)0x80をXORして最上位bitを0にする。

Bitcoin CoreのVarIntのRubyによる実装

これはもう、BitcoinCoreのC++実装を移植しただけである。ただし7bitずつ取ってくるという処理を論理積とシフトダウンで実装しており非常にシンプルである。C++とかの本物プログラマって凄いんだね。

本当はAmount Compressionについても書きたかったんだけど疲れてしまったので今回はここまでとしたい。

ちょっとした募集

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