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

# はじめに

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

今回は、モザイクを２つ定義して、MosaicCacheのPatricia Treeを理解していこうと思います。

（前回は１つだったので、とてもシンプルでした。）

# モザイク情報

以下の２つを設定しました。

## 2AECBFD76AE7411B

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/172833/bf112c55-3693-7f8b-6853-8817042848f4.png)

config-network.propertiesでは、以下のように設定されます。
`harvestingMosaicId = 0x2AEC'BFD7'6AE7'411B`

## 119E15661E9B2758

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/172833/577d5500-2bf0-c69e-03b7-36f24cdd2a8f.png)

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
```

# 全体像

まずは全体像です。
![patricia_tree-Page-2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/172833/8c1302d3-80eb-e4b9-68e4-0f164008debb.png)

# RocksDB

MosaicCacheのRocksDBを見てみます。

defaultには、keyがモザイクIDでvalueが発行数とかのモザイクエントリーであるレコードがあります。
![patricia_tree-Page-2 (2).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/172833/85880f1c-5fae-f6e5-4560-55c219f04eb4.png)
モザイクは2つ作ったので、モザイクIDがkeyとなっているレコードが2つあります。

patricia_treeには、ツリーのmerkle rootとtree nodeに対応するレコードがあります。
![patricia_tree-Page-2 (3).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/172833/ebdeec21-4e89-650c-60b7-71f10ed81144.png)
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に挿入し、さらにものすごく単純化して表示するとこんな感じ。
![patricia_tree-Page-2 (5).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/172833/44a01c29-5879-1a11-f2e1-16789692eecb.png)
それぞれのleaf nodeのkeyは、先頭の1文字が欠けています。これは、branch nodeがその情報を持っているので、必要ないというわけです。

では、それぞれのnodeを見ていきます。

# Leaf Node

ひとつ抜き出してみます。
![patricia_tree-Page-2 (6).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/172833/758d1cc5-9547-ed61-44df-f472af1bbeb0.png)
まず、これがbranch nodeなのかleaf nodeなのかを判別するために、prefixがつきます。branch nodeならば00、leaf nodeならffです。
![patricia_tree-Page-2 (7).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/172833/f1f740a6-b391-ce02-b445-12b1f020fd7d.png)
そしてKeyのサイズは可変なのでサイズを加えます。またKeyの名前をAligned Pathに変えます。
![patricia_tree-Page-2 (8).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/172833/819fb1c7-b4f6-0b75-0296-1fe0f8975198.png)
そして、aligned pathが奇数ニブルの場合、バイトに合わせるために0を最後に加えます。
![patricia_tree-Page-2 (9).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/172833/5dba4938-7296-e007-b85e-81b1ef903b1f.png)
というのが、このあたりに書いてあります。
https://github.com/nemtech/catapult-server/blob/v0.4.0.1/src/catapult/tree/PatriciaTreeSerializer.cpp#L49

これをつなぎ合わせたものが、RocksDBのpatricia_treeのレコードのvalueに相当します。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/172833/765634da-bc48-376f-2e93-5f10552c9691.png)

では、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には、ハッシュが入っていたというのがわかります。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/172833/4b90cf60-4582-37ef-0ef4-8dc9abbd7df3.png)

# Branch Node

はい。
![patricia_tree-Page-2 (10).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/172833/1483da0a-5516-4d73-e931-aa950ce6a042.png)
branch nodeにvalueがあるのですが、patricia treeに挿入するデータのkeyが固定長なので、branch nodeがvalueを持つことは決してないはずなので、value欄を消します。
![patricia_tree-Page-2 (11).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/172833/96afc39e-6f4a-0dec-0cbe-24ecb19707f2.png)
branch nodeであることを示すためにprefixをつけます。
![patricia_tree-Page-2 (12).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/172833/1c50b42a-10c9-cdd3-87ca-41e38dadcc7a.png)
挿入されたデータのkey(=hashed mosaic id)の先頭ニブルに共通の箇所があれば、branch nodeにもaligned pathをもつこととなります。今回はeとfから始まり、共通部分がなかったのでこの箇所はなく、ないことを示すために長さを00とします。
![patricia_tree-Page-2 (13).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/172833/d51319f5-3262-aa01-b467-7091606988bd.png)
0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,fそれぞれに0を入れるのはデータが大きくなるため、どの箇所に「●」があるのかを示すためのlinksを挿入します。
![patricia_tree-Page-2 (14).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/172833/c5d137b5-656b-8b93-b27f-4f64ac234da2.png)
ビットのフラグで表したとき、eとfにフラグをたてるため、`0b 0000 0000 0000 0011`となるでしょう。これを逆転し`0b 1100 0000 0000 0000`とすると`0xc000`となり、リトルエンディアンで`0x00c0`になるという予想です。データの状態からつじつま合わせをすると、こうなるような気がします。

そして、eとfの箇所にはleaf nodeへのポインタが入ります。ポインタはleaf nodeのhashのことです。最終的にこのような形になります。
![patricia_tree-Page-2 (15).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/172833/a48b5190-88fe-b068-d107-9f2149fdfcb6.png)
そして、これをつなぎ合わせるとRocksDBのpatricia_treeのレコードのvalueに相当します。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/172833/c9155fd4-2deb-ad4c-3862-fcec66a75be6.png)

では、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
```
これと一致します。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/172833/7eb50808-a11d-c662-72c8-584f7a1061e9.png)
このbranch nodeはpatricia treeの頂上なので、この値がsubCacheMerkleRootになり、この値と一致します。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/172833/fc336eda-8d71-200a-04af-0c1ee4f2d3d9.png)

# おわりに

もういちど全体像をのせておきます。
![patricia_tree-Page-2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/172833/8c1302d3-80eb-e4b9-68e4-0f164008debb.png)
![patricia_tree-Page-2 (2).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/172833/85880f1c-5fae-f6e5-4560-55c219f04eb4.png)

```
1b41e76ad7bfec2a : 1b41e76ad7bfec2a406603010000000001000000000000007f78559c556642fe132616910b1c9f2c36bc144d2d3a9e909092d64a0d0de0de01000000030000000000000003000000000000000000000000000000
58279b1e66159e11 : 58279b1e66159e1180fbdbca73f91f0001000000000000007f78559c556642fe132616910b1c9f2c36bc144d2d3a9e909092d64a0d0de0de01000000020000000000000006000000000000000000000000000000
```
![patricia_tree-Page-2 (3).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/172833/ebdeec21-4e89-650c-60b7-71f10ed81144.png)

```
root : 1ca8f8ab2c2513b1adfe050ab85c91d648837a52b82a19a69a9dbfcc78405b51
1ca8f8ab2c2513b1adfe050ab85c91d648837a52b82a19a69a9dbfcc78405b51 : 000000c0f3b26af59d6b46c87ba6a41f2756c6b6795390d041d3ba87aedf4fef1edbe5ddbc7c6886f9625f0f7b413f79fd460d4981cb042a3d0899036308d046759682e0
bc7c6886f9625f0f7b413f79fd460d4981cb042a3d0899036308d046759682e0 : ff3f66127864c906993852d957db4001a0e95108a92e7f9dbe194ac3971933ad9d708bf2854520124aec81e224f4047043ea08ffe7f9e31e592a6d0cdfa2b83811c6
f3b26af59d6b46c87ba6a41f2756c6b6795390d041d3ba87aedf4fef1edbe5dd : ff3fca198418d698a7205e10957385ff4a9a29f68cbfa2e489abd3b090f382e565f0290ec8c44899e1aa719a9552ba3118bb3cf184e43a2a3a1d732831068c4a3b97
```

理解するのに何日もかかりました。とりあえず、すべてのデータのつじつまがあったのでほっとしています。

# シリーズ

[State Hash その１ subCacheMerkleRootsからstateHashの計算](https://qiita.com/planethouki/items/4e411a9b157e723327ee)

[State Hash その２ 要素が1つだけの場合のsubCacheMerkleRootsの計算](https://qiita.com/planethouki/items/a905c543829dba2331d3)

[State Hash その２追記](https://qiita.com/planethouki/items/03cc5ac3b655f7bd1f45)

[State Hash その３ 要素が2つの場合のPatricia Tree](https://qiita.com/planethouki/items/3f7a235de3fb347bcb4d)