はじめに

かなり説明がつらいです。

今回は、モザイクを２つ定義して、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です。

そして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です。

そして、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の計算

State Hash その２要素が1つだけの場合のsubCacheMerkleRootsの計算

State Hash その２追記

State Hash その３要素が2つの場合のPatricia Tree