すべての人にマークルパトリシアツリーの力を


今回はSymbol form NEMのREST APIで取得できるようになったマークルパトリシアツリーについて検証したいと思います。

マークルパトリシアツリーについては目指せ北海道さんのこちらの記事を参考にしてください。
[【NEM技術勉強会】4.3 マークルパトリシアツリー【Symbol白書】- nemlog](https://nemlog.nem.social/blog/38406)
なお、今回の記事はplanethoukiさんの助言と記事を数多く参考させていただき、完成することができました。この場を借りて御礼申し上げます。

では、マークルパトリシアツリーを使用してブラウザ上に表示されたアカウント情報の検証を行ってみましょう。

まず固定値の指定とライブラリのインポートします。

```js
const NODE = 'http://api-01.ap-southeast-1.0.10.0.x.symboldev.network:3000';
const GENERATION_HASH = '6C1B92391CCB41C96478471C2634C111D9E989DECD66130C0430B5B8D20117CD';

const nem = require("/node_modules/symbol-sdk");
const op = require("/node_modules/rxjs/operators");
const rxjs = require("/node_modules/rxjs");
const sha3_256 = require('/node_modules/js-sha3').sha3_256;
```

symbol-sdkはbrowserify化したsymbol-sdk-0.22.2.jsを使用します。
https://github.com/xembook/nem2-browserify/blob/master/symbol-sdk-0.22.2.js


##### インスタンス生成

```js
const repo = new nem.RepositoryFactoryHttp(NODE, nem.NetworkType.TEST_NET,GENERATION_HASH);
const accountRepo = repo.createAccountRepository()
const blockRepo = repo.createBlockRepository()
const stateProofService = new nem.StateProofService(repo);
```

今回主役となるのが**StateProofService**です。

##### アカウント生成

```js
const alice = nem.Account.createFromPrivateKey(
  "F153F89498331537CB9436965DBE2F41660FBEFA911BD61635ADF3DE15ECD367",
  nem.NetworkType.TEST_NET
);
```

生成したaliceアカウントに対して、アカウントのアドレス(RawAddress)とアカウント情報(AccountInfo)を取得してそのハッシュ値を求めます。

##### アカウントアドレスのハッシュ値取得

```js
hasher = sha3_256.create();
aliceHash = hasher.update(
  nem.RawAddress.stringToAddress(alice.address.plain())
).hex().toUpperCase();
console.log("Raw Address Hash:" + aliceHash);
```

![スクリーンショット 2021-01-06 23.18.42.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/29187/2fd4a526-e7f3-9ee8-82aa-966e8b473c42.png)

使用するのはプレーンアドレスではなく、Rawアドレスを16進数化したものを使用します。

##### アカウント情報のハッシュ値取得

```js
hasher = sha3_256.create();
accountRepo.getAccountInfo(alice.address)
.subscribe(aliceInfo =>{
	aliceInfoHash = hasher.update(aliceInfo.serialize()).hex().toUpperCase();
	console.log(aliceInfo)
	console.log("AccountInfo Hash:" + aliceInfoHash);
})
```

アカウント情報を出力するとこのような情報が取得できます。
![スクリーンショット 2021-01-06 23.26.03.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/29187/e7508710-26f4-632b-a466-348a588b3292.png)

このアカウント情報をシリアライズしたものをハッシュ化して使用します。

![スクリーンショット 2021-01-06 23.27.34.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/29187/e80f4566-1ff0-a0e8-04c4-9e040194ecf4.png)

これらの２つの情報が埋め込まれたマークルパトリシアツリーを取得します。取得したツリーにはブロックヘッダーの情報が含まれるので、現在の最新ブロックヘッダーも同時に取得します。

##### ブロックヘッダーからステートハッシュ値を取得

```js
blockRepo.search({order: nem.Order.Desc})
.subscribe(x=>{
  console.log("Block State Hash:" + x.data[0].stateHashSubCacheMerkleRoots[0])
})
```

最新のブロックヘッダーとして以下のような情報を取得できました。
![スクリーンショット 2021-01-06 23.38.06.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/29187/7b508374-19d5-1aeb-5d72-1accc0930aa0.png)

このうちアカウント情報を集約したステートハッシュ値は
stateHashSubCacheMerkleRootsの0番目に集約されることになります。

![スクリーンショット 2021-01-06 23.42.18.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/29187/38d4faf8-b9f0-599e-fc5f-f66d89ba7649.png)


##### マークルツリー取得

```js
stateProofService.accountById(alice.address)
.subscribe(proof=>{
	console.log(proof);

	bit = "";
	link = proof.merkleTree.leaf.leafHash;
	merkle = proof.merkleTree
	merkleBranches = merkle.branches.reverse();
	for(let i = 0; i < merkleBranches.length; i++){
	    merkleTreeBranchLink = merkleBranches[i].links.find(x=>x.link === link)
	    link = merkleBranches[i].branchHash;
	    bit =  merkleTreeBranchLink.bit + bit;
	}
	addressHash = "bits:" + bit + "+path:"+ merkle.leaf.path;
	console.log(addressHash);
})
```

aliceアドレスでアカウント情報のマークルパトリシアツリーを取得すると以下のような情報が表示されます。

![スクリーンショット 2021-01-06 23.45.52.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/29187/c8b132b5-c087-e267-38b5-f0f576640854.png)

図で表現するとこんな感じです。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/29187/4ce17be0-7b92-0c96-cee9-74047cc60f68.png)



ツリーは複数階層からなるブランチと末端のリーフで構成されます。
それぞれのハッシュ値を計算すると、一階層上の構成要素になっていることが分かります。
（リーフは末端ブランチ、最上位ブランチはルートハッシュ）

##### ブランチのハッシュ値計算

```js
function getBranchHash(encodedPath, links){
    const branchLinks = Array(16).fill(nem.Convert.uint8ToHex(new Uint8Array(32)));
    links.forEach((link) => {
        branchLinks[parseInt(`0x${link.bit}`, 16)] = link.link;
    });
    hasher = sha3_256.create();
    return hasher.update(nem.Convert.hexToUint8(encodedPath + branchLinks.join(''))).hex().toUpperCase();
}
```

##### リーフのハッシュ値計算
 
```js
function getLeafHash(encodedPath, leafValue){
    hasher = sha3_256.create();
    return hasher.update(nem.Convert.hexToUint8(encodedPath + leafValue)).hex().toUpperCase();
}
```



最後に、rootHash、stateHash、merkleTree.branchesのbit値とleaf.valueに注目します。
stateHashがaccountInfoのハッシュ値と一致、
rootHashがブロックヘッダーのstateHashSubCacheMerkleRoots[0]と一致、
RawAddressの文字が以下の計算で出力される値と一致

```js
link = proof.merkleTree.leaf.leafHash;
merkle = proof.merkleTree
merkleBranches = merkle.branches.reverse();
for(let i = 0; i < merkleBranches.length; i++){
  merkleTreeBranchLink = merkleBranches[i].links.find(x=>x.link === link)
  link = merkleBranches[i].branchHash;
  bit =  merkleTreeBranchLink.bit + bit;
}
bit + merkle.leaf.path
```

これらの３つが一致することで、取得したマークルパトリシアツリー内にアドレスをkeyとしたアカウント情報のハッシュ値valueが存在し、ツリーのルートハッシュがブロックヘッダーに含まれていることが確認できました。




### これは何を意味するの？

ブロックチェーンにマークルパトリシアツリーのルートが保存されていることで、ブロックチェーンがツリーの存在を認知していることがわかります。そしてそのツリーは、アカウントアドレスをキー値、アカウント情報をバリュー値とした探索可能なツリーであることが証明されます。
ブロックチェーンは本来、トランザクションの署名検証は簡単に行えるのですが、その結果としてのアカウント情報を検証できるような仕組みではありません。そこでマークルパトリシアツリーのルートハッシュをブロックヘッダーに含めることで、”トランザクションによる更新の蓄積結果としてのデータベース”の状態を検証可能にしています。このデータベースはブロックチェーンの外部に保存されていても検証可能です。


### これが何に使えるの？

まず、本来の目的としてノード間でそれぞれがチェーン外部に持つデータが改ざんされずに保存されていることを確認するために使います。イーサリアムもこのような目的でフル活用されていると思います。

ここから一歩進めて活用方法を考えてみましょう。

NEMでは不特定多数がアクセスできるREST APIでマークルパトリシアツリーが提供されています。つまり、**ノード間検証の対話**のために設計されたものが、NEMでは**ブロックチェーンとユーザの対話**と置き換えてアプリケーション設計に利用することが可能です。

アカウント情報などのチェーン外部に保存されたデータも含めてノードであることを確認できるということは、ファイナライズされたブロックヘッダーを別経路で取得できれば、相手がだれであっても、途中でどんなエージェントやキャリアが経由しても、マークルパトリシアツリーが記録する範囲でノードと対話していると考えても問題ないということを意味します。


たとえばnemlogを考えてみましょう。

[nemlog - 暗号通貨 nemを使用した寄付機能付きブログコミュニケーションブログコミュニケーションプラットフォーム](https://nemlog.nem.social/)

nemlogでやり取りされるXEMが、改ざんできないことはご存じのとおりです。これはトランザクションが送信者の署名によって検証できるからです。それではnemlogで表示されているXEM残高についてはどうでしょうか？これはnemlogを信用するしかありません。nemlogが信用できるとしてもブラウザの拡張機能が悪さする場合もあるでしょう。表示される情報というのは人間の目に届くまでは改ざんの余地はあるのです（目に届いた情報を検証することは可能です）。

今のところ、たとえnemlogが嘘の残高を表示していたとしても、送金できる量、取引所で買い取ってくれる金額に変わりはないので大きな問題にはならないかもしれません。しかし、ブロックチェーンの社会実装が進み、取引所が扱わない価値をアカウントが持ち出したらどうなるでしょうか？それはトークンだけとは限りません。信頼できる組織からの証明メッセージ、価値を生み出す仲間からのマルチシグ、そしてそれらを根拠として経済が動き出した時、金融庁などははたしてこれらのすべての価値の管理や表示についてまで監督を行うでしょうか？

ブロックチェーンを利用したシステムが巷にあふれたとしても、私たちがその情報にアクセスするのはブラウザやアプリケーションを経由して見やすく整えられ可視化された情報です。つまり良くも悪くも誰かに操作されているのです。その場合でも、ノードが他のノードを信頼するように、Symbol from NEMではユーザがアプリケーションを信頼するための手がかりをREST APIを通じて提供してくれます。マークルパトリシアツリーがブロックチェーンと表示されている情報との架け橋となることができるのです。

マークルパトリシアツリーはそんな時代がきた時に、私たちに情報の信頼の仕方を教えてくれる重要な鍵となるでしょう。

### すべての人にマークルパトリシアツリーの力を

##### 後記：こちらもお読みください
https://qiita.com/nem_takanobu/items/37a488e5f47a67420e13