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

# はじめに

そろそろ避けていたものに手を付けなければ

今回は、要素が1つだけの単純なPatricia Treeについてみてみます。

# Patricia Tree

subCacheMerkleRootsはどこからきているのでしょうか。その１では、subCacheMerkleRootsは残高やモザイクなどのステートを表しているということを書きました。

例えばモザイクの場合、登録されたモザイクの情報をもとにしているはずです。そして、その情報をもとにPatricia Treeという構造をつくり、そのルートハッシュがモザイクのsubCacheMerkleRootsになります。

Patricia Treeについては以下の記事が参考になると思います。

https://github.com/ethereum/wiki/wiki/%5BJapanese%5D-Patricia-Tree

https://easythereentropy.wordpress.com/2014/06/04/understanding-the-ethereum-trie/

# 計算してみる

要素が1つだけの場合というタイトルなので、モザイクが1つのみ登録されている状態を用意します。

モザイクの情報はこんな感じ。

```:block-properties-file.properties
[mosaic>cat:currency]

divisibility = 6
duration = 0
supply = 8'999'999'998'000'000
isTransferable = true
isSupplyMutable = false
```

以下は、モザイクID`0x3692'FF95'2D89'DD45`のみ発行されているネメシスブロックの各種ステート情報です。

```
           Height: 1
  Generation Hash: 5ABBD9F7894EE7E5D4C3CDA934245396AEFCD1CB0426F265AC81F4F3450AB6DD
Transactions Hash: 111461D150B90EBF58A87AB2FA2493DCB716F83E7EE584369820D6CA10DE5E52
    Receipts Hash: A207227B111F4242DE80FC87E722B86077931B483883EA65E06A24340176A047
       State Hash: BDCAF08330E29EBC7F18A1A9E6C7C60E4CFF99B100FC583FCDBAFA6F875F5DCF
--- Components (7) ---
 + 779F9E5BCEFB8267C084B14F8C2CB981683E6715BAFF4DC3B39BC133AFBEDD1B
 + 7BA3B37CDF34608C3B98BE572C7A743FEAC8B6909654AF21B8E0F4381EFD9164
 + 5D8EEAD5907130D297C322698F3D201A78D629CAC87487A0F4F890C1277B250C
 + 0000000000000000000000000000000000000000000000000000000000000000
 + 0000000000000000000000000000000000000000000000000000000000000000
 + 0000000000000000000000000000000000000000000000000000000000000000
 + 0000000000000000000000000000000000000000000000000000000000000000
```

subCacheMerkleRootsの3つ目がモザイクで、`0x3692'FF95'2D89'DD45`のモザイク情報からPatricia Treeを作ると
5D8EEAD5907130D297C322698F3D201A78D629CAC87487A0F4F890C1277B250C
が導出できるはずです。

では、Patricia Treeの要素となるデータはどこにあるのか。

これは、RocksDBの中に格納されているようです。

カタパルトを動かしたときにできるdataフォルダがあります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/172833/28dca187-ebff-a0eb-ee01-9579cfc70244.png)

この中のstatedbのMosaicCacheの中を見ます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/172833/6d3d7bfe-fca8-8a06-39a3-05db8ee755e3.png)

これはRocksDBのファイルになっていて、それ用のソフトで見ることができます。

[FastNoSQL](https://fastonosql.com/)を使ってみました。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/172833/05a26477-6bd4-642d-afde-2897052a3aa0.png)

keyが文字列化されているのでわかりにくいですが、`0x3692'FF95'2D89'DD45`のモザイクIDだと思います。

抜き出してみます。

key: 45dd892d95ff9236
value: 010045dd892d95ff923680fbdbca73f91f000100000000000000db06e6c3f6976324ba215d7d1f2d4c69d7353afe1d6050a606bc61eda13e1c3c01000000020000000000000006000000000000000000000000000000

valueはMosaicEntryというカタチで保存されているみたいです。

https://github.com/nemtech/catapult-server/blob/master/plugins/txes/mosaic/src/state/MosaicEntry.cpp

可能な限り分解してみました。`0x3692'FF95'2D89'DD45`の情報と一致していると思います。

```
0100				?
45dd892d95ff9236	id
80fbdbca73f91f00	supply
0100000000000000	height
db06e6c3f6976324ba215d7d1f2d4c69d7353afe1d6050a606bc61eda13e1c3c	pubkey
01000000			revision
0200000000000000	flag (Transferable)
0600000000000000	divisibility
0000000000000000	duration
```

ここからどのようにState Hashを計算するのかをいろいろ聞いて回った結果、次のように理解しました。

![patricia_tree (2).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/172833/790d2653-3561-1f1a-cda2-56a661c45fce.png)

prefixについてですが、keyが偶数ニブルかつleaf nodeの場合、0x20になります。

そして、leaf nodeをsha3する方法は、単純に全部つなげてsha3すればよいです。

sha3(20 + 14979A1134C38C8A5C7C7E3669CE7AA98C2D46225F77645A1FC6E7A30FF5C5DA + B6BCAE57D970E08BC94701A8333F081B633554FE5282AB2D841D17F9B93E9B2D)

= 5D8EEAD5907130D297C322698F3D201A78D629CAC87487A0F4F890C1277B250C

subCacheMerkleRootsの3番目と一致しました。

# おわりに

subCacheMerkleRootsについて、要素が1つだけの場合のモザイクのものを導出しました。Patricia Treeにハッシュの情報しか入っていないため、ステートの保存場所というよりは、ステートに変更があった場合に高速に処理ができるためにあるような気がします。また、ツリー構造を使っているため、ある時点で確かに特定のモザイクやアカウントの残高が存在したことを証明するということができると思います。

# シリーズ

[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)