はじめに
そろそろ避けていたものに手を付けなければ
今回は、要素が1つだけの単純なPatricia Treeについてみてみます。
Patricia Tree
subCacheMerkleRootsはどこからきているのでしょうか。その１では、subCacheMerkleRootsは残高やモザイクなどのステートを表しているということを書きました。
例えばモザイクの場合、登録されたモザイクの情報をもとにしているはずです。そして、その情報をもとにPatricia Treeという構造をつくり、そのルートハッシュがモザイクのsubCacheMerkleRootsになります。
Patricia Treeについては以下の記事が参考になると思います。
計算してみる
要素が1つだけの場合というタイトルなので、モザイクが1つのみ登録されている状態を用意します。
モザイクの情報はこんな感じ。
[mosaic>cat:currency]
divisibility = 6
duration = 0
supply = 8'999'999'998'000'000
isTransferable = true
isSupplyMutable = false
以下は、モザイクID0x3692'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フォルダがあります。
この中のstatedbのMosaicCacheの中を見ます。
これはRocksDBのファイルになっていて、それ用のソフトで見ることができます。
FastNoSQLを使ってみました。
keyが文字列化されているのでわかりにくいですが、0x3692'FF95'2D89'DD45のモザイクIDだと思います。
抜き出してみます。
key: 45dd892d95ff9236
value: 010045dd892d95ff923680fbdbca73f91f000100000000000000db06e6c3f6976324ba215d7d1f2d4c69d7353afe1d6050a606bc61eda13e1c3c01000000020000000000000006000000000000000000000000000000
valueはMosaicEntryというカタチで保存されているみたいです。
可能な限り分解してみました。0x3692'FF95'2D89'DD45の情報と一致していると思います。
0100 ?
45dd892d95ff9236 id
80fbdbca73f91f00 supply
0100000000000000 height
db06e6c3f6976324ba215d7d1f2d4c69d7353afe1d6050a606bc61eda13e1c3c pubkey
01000000 revision
0200000000000000 flag (Transferable)
0600000000000000 divisibility
0000000000000000 duration
ここからどのようにState Hashを計算するのかをいろいろ聞いて回った結果、次のように理解しました。
prefixについてですが、keyが偶数ニブルかつleaf nodeの場合、0x20になります。
そして、leaf nodeをsha3する方法は、単純に全部つなげてsha3すればよいです。
sha3(20 + 14979A1134C38C8A5C7C7E3669CE7AA98C2D46225F77645A1FC6E7A30FF5C5DA + B6BCAE57D970E08BC94701A8333F081B633554FE5282AB2D841D17F9B93E9B2D)
= 5D8EEAD5907130D297C322698F3D201A78D629CAC87487A0F4F890C1277B250C
subCacheMerkleRootsの3番目と一致しました。
おわりに
subCacheMerkleRootsについて、要素が1つだけの場合のモザイクのものを導出しました。Patricia Treeにハッシュの情報しか入っていないため、ステートの保存場所というよりは、ステートに変更があった場合に高速に処理ができるためにあるような気がします。また、ツリー構造を使っているため、ある時点で確かに特定のモザイクやアカウントの残高が存在したことを証明するということができると思います。
シリーズ
State Hash その１ subCacheMerkleRootsからstateHashの計算