ブロック内のトランザクションにコミットするblockTransactionsHash

# はじめに

カタパルトから、ブロックのAPIレスポンスに`blockTransactionsHash`というものが追加されていました。

参考：[ビットコインのマークルツリー](https://en.bitcoin.it/wiki/Protocol_documentation#Merkle_Trees)

これは、下記URLの`2) Merkle state transition proofs`のところの図がわかりやすいです。

https://blog.nem.io/catapult-bison-update/

緑色のトランザクションがブロックにあることを証明するには、青色の４つを使ってマークルルートを算出し、ブロックに刻まれている値と一致するかを確認すればよいのです。

ただ、ブロックチェーンの種類によっては、使うハッシュ関数が違っていたり、エンディアンが変わっていたり、結合する順序が変わっていたりします。

MIJIN_TESTのカタパルトはどうやっているのかを理解するために、簡単なマークルツリーを構成してみようと思います。

# 計算してみる

## トランザクション２個の場合

ブロックの`blockTransactionsHash`は`5D22～`

```json:block
{
  "block": {
    "signature": "0920CCC9096BAF897D6D1B9C54607792BEE6CA12F38FC20931889027C48447A77D48076AA68E2DB123A937E2B2E500D8EEF54302F253386FA4417DC98C039401",
    "signer": "F6791558F86AF5822400B648442EF7D39C92BFD5A453D1D8AE472D5A10988262",
    "version": 36867,
    "type": 33091,
    "previousBlockHash": "C8E49B7541E797663AC2342440D277D52349BA9B06F62093FCEDA89F8870789F",
    "blockTransactionsHash": "5D22A8ACADA723C02E6DD747681BF249405BC09A8747808C8711DC4B4B6FCF58",
    "stateHash": "EBBABBC9A3DFFE2FBF241207776767E079EAC502F373E0FCF5255E1C9E3AF0DF"
  }
}
```

トランザクションハッシュは`6F23～`と`7B9F～`

```json:transactions
[
  {
    "meta": {
      "hash": "6F233A4FE7DD46A3A665281899F70DF735A2EB37726D04EBA9A00B9A8CF717B2",
      "merkleComponentHash": "6F233A4FE7DD46A3A665281899F70DF735A2EB37726D04EBA9A00B9A8CF717B2",
      "index": 0,
      "id": "5C4DAE7EDC3AE7000178AF89"
    },
  },
  {
    "meta": {
      "hash": "7B9F05E7689EB1483BCAD89986082EB7D77BB8CAFAE5BC25F65914C5E5D3E4D5",
      "merkleComponentHash": "7B9F05E7689EB1483BCAD89986082EB7D77BB8CAFAE5BC25F65914C5E5D3E4D5",
      "index": 1,
      "id": "5C4DAE7EDC3AE7000178AF8A"
    },
  }
]
```

![Untitled Diagram.png](https://qiita-image-store.s3.amazonaws.com/0/172833/4a40847b-f76b-7b03-924b-a25d633f8e7d.png)


sha3( 6F233A4FE7DD46A3A665281899F70DF735A2EB37726D04EBA9A00B9A8CF717B2
+ 7B9F05E7689EB1483BCAD89986082EB7D77BB8CAFAE5BC25F65914C5E5D3E4D5)
\= 5D22A8ACADA723C02E6DD747681BF249405BC09A8747808C8711DC4B4B6FCF58

sha3は、keccakではないsha3です。+は、文字列結合を表します。

`blockTransactionsHash`と一致しました。

## トランザクション３個の場合

このブロックの場合、`numTransactions = 3`となりました。この場合は、リーフノードが奇数となるため、余ってしまいます。

`blockTransactionsHash`は`31D6～`

```json:block
{
  "meta": {
    "hash": "D12FFFD3D096B05284A49C8C9DD0971319BD0EE73F3BFD67655C3A8BE78E6872",
    "generationHash": "639465FB8FBB2BE090A56463CDA105C62E581A04EB46B33CAF4403D34BAC7461",
    "numTransactions": 3,
    "subCacheMerkleRoots": [
      "5DC9832FB01E08DC4A0D7BD9B1FE6486AE7CC249960830567EFB4FC4D0B899E9",
      "B37369BE244872C6D2D8BD1C7D2B2BD70EEF06978E2FDFA4E05F323FAE964AC9",
      "543738F9C0CDF60FFF0C82D5AC7A9C3B365AC0D5BBE87A230FB16A3C7E98B567",
      "0000000000000000000000000000000000000000000000000000000000000000",
      "0000000000000000000000000000000000000000000000000000000000000000",
      "0000000000000000000000000000000000000000000000000000000000000000",
      "0000000000000000000000000000000000000000000000000000000000000000"
    ]
  },
  "block": {
    "previousBlockHash": "FD23A3EA75A0DF33EDBD8227F48BAA7B073CFC2A01DC1114593F667CFC6AE7E0",
    "blockTransactionsHash": "31D69FD9A40ABF38E1A4865AC2A703D391AFCE921819928F51495415B7E4FB78",
    "stateHash": "D9521B328885CE58991743D1EF78795EB9D55E2F2786DDBA1AFFFF4F7B856C97"
  }
}
```

トランザクションハッシュは`35DB～`と`7FE8～`と`EC05～`

```json:transactions
[
  {
    "meta": {
      "hash": "35DBFA25870A9FF01AEF4DC5DC45C4542E53F216B71A82B8A54CA5720CD9BB2A",
      "merkleComponentHash": "35DBFA25870A9FF01AEF4DC5DC45C4542E53F216B71A82B8A54CA5720CD9BB2A",
      "index": 0,
      "id": "5C4DB9E2DC3AE7000178B04B"
    },
    "transaction": {}
  },
  {
    "meta": {
      "hash": "7FE8E29BD606CC4C99FDE600104A910E8049690CA1AB917B7DF15276E7F6C262",
      "merkleComponentHash": "7FE8E29BD606CC4C99FDE600104A910E8049690CA1AB917B7DF15276E7F6C262",
      "index": 2,
      "id": "5C4DB9E2DC3AE7000178B04C"
    },
    "transaction": {}
  },
  {
    "meta": {
      "hash": "EC05B0867C9843109B3B0FDD605AD4AA83DC6E6569435BF9FF4A9FC8F54CAB79",
      "merkleComponentHash": "EC05B0867C9843109B3B0FDD605AD4AA83DC6E6569435BF9FF4A9FC8F54CAB79",
      "index": 1,
      "id": "5C4DB9E2DC3AE7000178B04D"
    },
    "transaction": {}
  }
]
```

端で相手がいなくなったリーフは、図のように同じものをコピーして、同じように計算していきます。

![Untitled Diagram (1).png](https://qiita-image-store.s3.amazonaws.com/0/172833/ea6620f4-0a61-d30c-db82-b8ee0e6395aa.png)

sha3(35DBFA25870A9FF01AEF4DC5DC45C4542E53F216B71A82B8A54CA5720CD9BB2A
+ EC05B0867C9843109B3B0FDD605AD4AA83DC6E6569435BF9FF4A9FC8F54CAB79)
\= 2CE7C51021C3551B5A8EA7135C5FDDA38E75769401554103D5E8DA5888466A1A

sha3(7FE8E29BD606CC4C99FDE600104A910E8049690CA1AB917B7DF15276E7F6C262
+ 7FE8E29BD606CC4C99FDE600104A910E8049690CA1AB917B7DF15276E7F6C262)
\= 421C391E922DA4B3FD8A941CCE75258BEB23399A511AC744DFE7BC5194782F35

sha3(2CE7C51021C3551B5A8EA7135C5FDDA38E75769401554103D5E8DA5888466A1A
+ 421C391E922DA4B3FD8A941CCE75258BEB23399A511AC744DFE7BC5194782F35)
\= 31D69FD9A40ABF38E1A4865AC2A703D391AFCE921819928F51495415B7E4FB78

sha3は、keccakではないsha3です。+は、文字列結合を表します。

`blockTransactionsHash`と一致しました。

# おわりに

同じような感じで、トランザクションが何個あってもマークルツリーが構成できます。

トランザクションがブロックに入っていることの検証をするときに、マークルツリーを使うことによって、計算量オーダーが変わります。