はじめに
かなり説明がつらいです。
今回は、モザイクを２つ定義して、MosaicCacheのPatricia Treeを理解していこうと思います。
（前回は１つだったので、とてもシンプルでした。）
モザイク情報
以下の２つを設定しました。
2AECBFD76AE7411B
config-network.propertiesでは、以下のように設定されます。
harvestingMosaicId = 0x2AEC'BFD7'6AE7'411B
119E15661E9B2758
config-network.propertiesでは、以下のように設定されます。
currencyMosaicId = 0x119E'1566'1E9B'2758
subCacheMerkleRoot
モザイクは３番目なので
1CA8F8AB2C2513B1ADFE050AB85C91D648837A52B82A19A69A9DBFCC78405B51
です。
Height: 1
Generation Hash: C6871CB9FA666FF20B93DCE6D7E25196EFBAFDFF3989AC00C76BD8E1DCEE9AEE
Transactions Hash: 814C8164E99927A30BD6D06212EB10D1A5C3F6A4458045B40E0AD7FDF702117F
Receipts Hash: 6419DD8BAA202763D1B5946F877C9B728F344D7A5365FBC3622CB049EB7B88A5
State Hash: E20FE3D20B709572558E21C13A99BF7CFE66D3BED9C4BF082AAE0E6FC1A95612
--- Components (7) ---
+ 13067B2FEB08F5C99547B4A5C30D9581D1D8E22F817A542AEF8E02684CADA2DC
+ 7EA827EB9A862C95EED988E3D5757C7B0F23BC99757FF6925F6FCC4447C6B864
+ 1CA8F8AB2C2513B1ADFE050AB85C91D648837A52B82A19A69A9DBFCC78405B51
+ 0000000000000000000000000000000000000000000000000000000000000000
+ 0000000000000000000000000000000000000000000000000000000000000000
+ 0000000000000000000000000000000000000000000000000000000000000000
+ 0000000000000000000000000000000000000000000000000000000000000000
全体像
まずは全体像です。
RocksDB
MosaicCacheのRocksDBを見てみます。
defaultには、keyがモザイクIDでvalueが発行数とかのモザイクエントリーであるレコードがあります。
モザイクは2つ作ったので、モザイクIDがkeyとなっているレコードが2つあります。
patricia_treeには、ツリーのmerkle rootとtree nodeに対応するレコードがあります。
keyがtree nodeのハッシュで、valueがシリアライズされたものになります。
単純化
Patricia Treeに挿入するデータは、ハッシュ化したデータになります。
key: sha3(mosaic id)
value: sha3(mosaic entry)
これはRocksDBのdefaultのレコードからとれる情報ですね。
なので、実際には以下のようになります。
2AECBFD76AE7411B
key: f66127864c906993852d957db4001a0e95108a92e7f9dbe194ac3971933ad9d7
value: 8bf2854520124aec81e224f4047043ea08ffe7f9e31e592a6d0cdfa2b83811c6
119E15661E9B2758
key: eca198418d698a7205e10957385ff4a9a29f68cbfa2e489abd3b090f382e565f
value: 290ec8c44899e1aa719a9552ba3118bb3cf184e43a2a3a1d732831068c4a3b97
これをPatricia Treeに挿入し、さらにものすごく単純化して表示するとこんな感じ。
それぞれのleaf nodeのkeyは、先頭の1文字が欠けています。これは、branch nodeがその情報を持っているので、必要ないというわけです。
では、それぞれのnodeを見ていきます。
Leaf Node
ひとつ抜き出してみます。
まず、これがbranch nodeなのかleaf nodeなのかを判別するために、prefixがつきます。branch nodeならば00、leaf nodeならffです。
そしてKeyのサイズは可変なのでサイズを加えます。またKeyの名前をAligned Pathに変えます。
そして、aligned pathが奇数ニブルの場合、バイトに合わせるために0を最後に加えます。
というのが、このあたりに書いてあります。
https://github.com/nemtech/catapult-server/blob/v0.4.0.1/src/catapult/tree/PatriciaTreeSerializer.cpp#L49
これをつなぎ合わせたものが、RocksDBのpatricia_treeのレコードのvalueに相当します。
では、RocksDBのpatricia_treeのレコードのkeyはどうなるでしょうか。
これは、leaf nodeのハッシュが入っています。
計算方法はここらへんに書いてありますので、やってみます。
https://github.com/nemtech/catapult-server/blob/v0.4.0.1/src/catapult/tree/TreeNode.cpp#L51
まず、prefixをつけます。leaf nodeならば20か3、そうでないなら00か1。leaf nodeかつaligned pathが偶数ニブルの場合は20で奇数ニブルの場合は3、branch nodeかつaligned pathが偶数ニブルの場合は00で奇数ニブルの場合は1です。
3
そしてaligned pathをくっつけます。
3ca198418d698a7205e10957385ff4a9a29f68cbfa2e489abd3b090f382e565f
そしてvalueをくっつけます。
3ca198418d698a7205e10957385ff4a9a29f68cbfa2e489abd3b090f382e565f290ec8c44899e1aa719a9552ba3118bb3cf184e43a2a3a1d732831068c4a3b97
これのsha3をとれば完成です。
sha3(3 + aligned path + value) =
f3b26af59d6b46c87ba6a41f2756c6b6795390d041d3ba87aedf4fef1edbe5dd
RocksDBのpatricia_treeのレコードのkeyには、ハッシュが入っていたというのがわかります。
Branch Node
はい。
branch nodeにvalueがあるのですが、patricia treeに挿入するデータのkeyが固定長なので、branch nodeがvalueを持つことは決してないはずなので、value欄を消します。
branch nodeであることを示すためにprefixをつけます。
挿入されたデータのkey(=hashed mosaic id)の先頭ニブルに共通の箇所があれば、branch nodeにもaligned pathをもつこととなります。今回はeとfから始まり、共通部分がなかったのでこの箇所はなく、ないことを示すために長さを00とします。
0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,fそれぞれに0を入れるのはデータが大きくなるため、どの箇所に「●」があるのかを示すためのlinksを挿入します。
ビットのフラグで表したとき、eとfにフラグをたてるため、0b 0000 0000 0000 0011となるでしょう。これを逆転し0b 1100 0000 0000 0000とすると0xc000となり、リトルエンディアンで0x00c0になるという予想です。データの状態からつじつま合わせをすると、こうなるような気がします。
そして、eとfの箇所にはleaf nodeへのポインタが入ります。ポインタはleaf nodeのhashのことです。最終的にこのような形になります。
そして、これをつなぎ合わせるとRocksDBのpatricia_treeのレコードのvalueに相当します。
では、RocksDBのpatricia_treeのレコードのkeyはどうなるでしょうか。
これは、branch nodeのハッシュが入っています。
計算方法はここらへんに書いてありますので、やってみます。
https://github.com/nemtech/catapult-server/blob/v0.4.0.1/src/catapult/tree/TreeNode.cpp#L116
まず、prefixをつけます。leaf nodeならば20か3、そうでないなら00か1。leaf nodeかつaligned pathが偶数ニブルの場合は20で奇数ニブルの場合は3、branch nodeかつaligned pathが偶数ニブルの場合は00で奇数ニブルの場合は1です。
00
そして、0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,fそれぞれのポインタを32バイト分にしてつなぎ合わせます。
00 +
0000000000000000000000000000000000000000000000000000000000000000 + //0
0000000000000000000000000000000000000000000000000000000000000000 + //1
0000000000000000000000000000000000000000000000000000000000000000 + //2
0000000000000000000000000000000000000000000000000000000000000000 + //3
0000000000000000000000000000000000000000000000000000000000000000 + //4
0000000000000000000000000000000000000000000000000000000000000000 + //5
0000000000000000000000000000000000000000000000000000000000000000 + //6
0000000000000000000000000000000000000000000000000000000000000000 + //7
0000000000000000000000000000000000000000000000000000000000000000 + //8
0000000000000000000000000000000000000000000000000000000000000000 + //9
0000000000000000000000000000000000000000000000000000000000000000 + //a
0000000000000000000000000000000000000000000000000000000000000000 + //b
0000000000000000000000000000000000000000000000000000000000000000 + //c
0000000000000000000000000000000000000000000000000000000000000000 + //d
f3b26af59d6b46c87ba6a41f2756c6b6795390d041d3ba87aedf4fef1edbe5dd + //e
bc7c6886f9625f0f7b413f79fd460d4981cb042a3d0899036308d046759682e0 //f
このハッシュをとると
1ca8f8ab2c2513b1adfe050ab85c91d648837a52b82a19a69a9dbfcc78405b51
これと一致します。
このbranch nodeはpatricia treeの頂上なので、この値がsubCacheMerkleRootになり、この値と一致します。
おわりに
もういちど全体像をのせておきます。
1b41e76ad7bfec2a : 1b41e76ad7bfec2a406603010000000001000000000000007f78559c556642fe132616910b1c9f2c36bc144d2d3a9e909092d64a0d0de0de01000000030000000000000003000000000000000000000000000000
58279b1e66159e11 : 58279b1e66159e1180fbdbca73f91f0001000000000000007f78559c556642fe132616910b1c9f2c36bc144d2d3a9e909092d64a0d0de0de01000000020000000000000006000000000000000000000000000000
root : 1ca8f8ab2c2513b1adfe050ab85c91d648837a52b82a19a69a9dbfcc78405b51
1ca8f8ab2c2513b1adfe050ab85c91d648837a52b82a19a69a9dbfcc78405b51 : 000000c0f3b26af59d6b46c87ba6a41f2756c6b6795390d041d3ba87aedf4fef1edbe5ddbc7c6886f9625f0f7b413f79fd460d4981cb042a3d0899036308d046759682e0
bc7c6886f9625f0f7b413f79fd460d4981cb042a3d0899036308d046759682e0 : ff3f66127864c906993852d957db4001a0e95108a92e7f9dbe194ac3971933ad9d708bf2854520124aec81e224f4047043ea08ffe7f9e31e592a6d0cdfa2b83811c6
f3b26af59d6b46c87ba6a41f2756c6b6795390d041d3ba87aedf4fef1edbe5dd : ff3fca198418d698a7205e10957385ff4a9a29f68cbfa2e489abd3b090f382e565f0290ec8c44899e1aa719a9552ba3118bb3cf184e43a2a3a1d732831068c4a3b97
理解するのに何日もかかりました。とりあえず、すべてのデータのつじつまがあったのでほっとしています。
シリーズ
State Hash その１ subCacheMerkleRootsからstateHashの計算