アルゴリズムとかオーダーとか

仕事で勉強したことなどをまとめてます

SSZのMerkleization

前回に引き続きSSZ(Simple Serialize)について解説する。今回はSSZのMerkleizationについてまとめる。

前回の記事はこちら。
y-nakajo.hatenablog.com

Merkleizationについては、引き続きSSZの仕様を参考にした。
github.com

概要

Eth1.0ではPatricia Merkle Trieを採用していたが、sszではよりシンプルにするために、Binary Merkle Treeを採用した。
さらにhashアルゴリズムもより汎用性を高めるためにkeccak256ではなく、広く利用されているsha256を採用した。
また、SSZではSchema構造を維持したままMerkleizeされる。これにより、Schemaの一部のデータのみをProofと共に共有することが可能となっている。

例えば次に示すDepositDataスキーマをMerkleizeする場合は、下図のtreeが構成され、root hashが求まる。

class DepositData(Container):
    pubkey: BLSPubkey # (= Bytes48)
    withdrawal_credentials: Bytes32
    amount: Gwei # (= Uint64)
    signature: BLSSignature  # Signing over DepositMessage (= Bytes96)
DepositDataのMerkleization

以降、Merkleization方法の各ステップを詳しく解説する。

基本の処理の流れ

Merkleizationについては基本的に以下のアルゴリズムでroot hashを求める。
1. 32byteを1chunkとして、データをchunkにフィットさせる。 => pack処理
2. chunkの数を2の累乗値にする。ex) 1 => 1, 2 => 2, 3 => 4, 5 => 8, 12 => 16。増えたchunkはall 0 のempty chunkで埋める。
3. Binary Merkle Treeを構築してhash_tree_root(= root hash)を求める。ただし、chunk数が1の場合はhashをせずに、pack値それ自身がhash_tree_rootとなる。

上記の処理をSSZの各Type毎に具体的に説明する。

Basic Typeの場合

Basic TypeはUintN(N=8,16,32,64,128,256)とBoolean。

pack 処理
1. serializeする。
2. 32byteになるまで0をright paddingする。

1chunkしかないので、pack値がそのままhash_tree_rootとなる。

ex) 赤字がpaddingで追加された部分。UintNのserializeはlittle endianなのに注意。

32: Uint8 => 0x20 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
32768: Uint16 => 0x00 80 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
32: Uint64 => 0x20 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
true: Boolean => 0x01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

Vector[B, N]

B = Basic Type

pack 処理
1. Bのbyte数 * N + 31 / 32 個の初期値ALL0のchunk bufferを準備。
2. 要素を先頭から順番にserializeする。
3. 2の結果を順番にchunk にコピーしていく。

例えば、Vector[Uint32, 32]の場合は、4 * 32 = 4 chunksとなる。

chunk数 == 1 の場合は、pack結果の値がhash_tree_root
chunk数 > 1 の場合は、Binary Merkleize処理を行う。

Binary Merkleize
4. chunk 数を2の累乗個に拡張。
5. Binary Treeを構築。
6. root hashを算出

root hashの値がhash_tree_rootとなる。
ex) 赤字がpadding byte

[1, 2, 3, 4, 5, 6]:Vector[Uint8, 6] => 0x01 02 03 04 05 06 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x6520084850420d1dfb4432a929dfcc5632bfda9930b58031465b314a326a565bf3d66bd66e8d997cfe4d358ae2e248f0: Vector[Uint8, 48] =>
[ 
  0x6520084850420d1dfb4432a929dfcc5632bfda9930b58031465b314a326a565b,
  0xf3d66bd66e8d997cfe4d358ae2e248f000000000000000000000000000000000
]
最終的なhash値 => 0x6835da9546c724babbba884a17fa90a08f88d61e8f9cbe8be8b044b66272c1d5

List[B, N]

B = Basic Type

pack 処理
1. Bのbyte数 * N + 31 / 32 個の初期値ALL0のchunk bufferを準備。
2. 要素を先頭から順番にserializeする。
3. 2の結果を順番にchunk にコピーしていく。

chunk数 == 1 の場合は、pack結果の値がhash_tree_root
chunk数 > 1 の場合は、Binary Merkleize処理を行う。

Binary Merkleize
4. chunk 数を2の累乗個に拡張。
5. Binary Treeを構築。
6. root hashを算出

with length
7. hash_tree_root値とUint256(length).hash_tree_rootをBinary Merkleizeする。

この結果が最終的な hash_tree_rootとなる。
ex) 赤字がpadding byte

[1, 2, 3, 4, 5, 6]: List[Uin64, 32] 
=>
[
  0x0100000000000000 0200000000000000 0300000000000000 0400000000000000,
  0x0500000000000000 0600000000000000 0000000000000000 0000000000000000,
  0000000000000000 0000000000000000 0000000000000000 0000000000000000,
  0000000000000000 0000000000000000 0000000000000000 0000000000000000,
  0000000000000000 0000000000000000 0000000000000000 0000000000000000,
  0000000000000000 0000000000000000 0000000000000000 0000000000000000,
  0000000000000000 0000000000000000 0000000000000000 0000000000000000,
  0000000000000000 0000000000000000 0000000000000000 0000000000000000
]
=>
[
0x699b0bc30f88313a8f6e95c016cc2bda673268dab2ac902251eb9b47ba45d6c3,  // hash_tree_root
0x0600000000000000000000000000000000000000000000000000000000000000 // Uint256(length).hash_tree_root
]
最終的なhash値 => 0x54d47e781fdf8bb9ae416971f40ff1c6d0ab183646b7da551225933d6fdb4cea

Bitvector[N]

1. N + 255 / 256 個のchunk Bufferを用意する。
2. serializeする。
3. 2の結果をchunk Bufferにコピーする。

chunk数 == 1 の場合は、pack結果の値がhash_tree_root
chunk数 > 1 の場合は、Binary Merkleize処理を行う。

Binary Merkleize
4. chunk 数を2の累乗個に拡張。
5. Binary Treeを構築。
6. root hashを算出

with length
7. hash_tree_root値とUint256(length).hash_tree_rootをBinary Merkleizeする。

ex)

[1, 0, 0, 1]: Bitlist[256] => 0x0900000000000000000000000000000000000000000000000000000000000000

Bitlist[N]

流れはBitvectorと同じである。最後にListと同様にwith length処理を行う。

1. N + 255 / 256 個のchunk Bufferを用意する。
2. serializeする。
3. 2の結果をchunk Bufferにコピーする。

chunk数 == 1 の場合は、pack結果の値がhash_tree_root
chunk数 > 1 の場合は、Binary Merkleize処理を行う。

Binary Merkleize
4. chunk 数を2の累乗個に拡張。
5. Binary Treeを構築。
6. root hashを算出

with length
7. hash_tree_root値とUint256(length).hash_tree_rootをBinary Merkleizeする。

ex)

[1, 0, 0, 1]: Bitlist[256] => 0x0900000000000000000000000000000000000000000000000000000000000000
=> [
  0x0900000000000000000000000000000000000000000000000000000000000000,
  0x0400000000000000000000000000000000000000000000000000000000000000
]
最終的なhash値 => 0x53de69c30b9c07be9cba006e32db34dc1e4ebfe649bc94aa7c8aae0ef419aeed

Union

Unionの場合は最終的に選択されたTypeのindex値とのhashを取ります。Listでlengthとのhashを取ったのと似た形となります。

1. 要素のserializeサイズに合わせて、chunk Bufferを用意する。
2. 要素のroot_hash_treeを取得する。
3. 2の結果をchunk Bufferにコピーする。

with selector index
7. hash_tree_root値とUint256(selector index).hash_tree_rootをBinary Merkleizeする。
※selector indexはUnionが取り得る型リストのうち、実際に選択した型のindex値。例えば、Union[Nonde, Uint8, Uint32]が定義され、実際の型としてUint8が選択された場合はselector index = 1 となる。

ex)

4: Union[Uint8] (Union[None, Uint8, Uint32]) =>0x0400000000000000000000000000000000000000000000000000000000000000
=> [
  0x0400000000000000000000000000000000000000000000000000000000000000,
  0x0100000000000000000000000000000000000000000000000000000000000000
]
最終的なhash値 => 7063e9add4fb20ab4aee17f218b851e7c814f14ca5c8ec09208d34fe2865cd86

Vector[Composit Type, N]

例えば、Vector[Bytes48, 4] 等。Bytes48 = Vector[Uint8, 48]なので、Vector[Vector[Uint8, 48], 4]と、Composite Typeを要素に持つVector

1. N個のchunk Bufferを用意する。
2. 要素の先頭から順番にroot_tree_hashを計算する。
3. 2の結果を順番にchunk にコピーしていく。

chunk数 == 1 の場合は上記の結果がhash_tree_rootとなる。
chunk数 > 1 の場合は、Binary Merkleize処理を行う。

Binary Merkleize
4. chunk 数を2の累乗個に拡張。
5. Binary Treeを構築。
6. root hashを算出

root hashの値がhash_tree_rootとなる。
例は割愛。

List[Composit Type, N]

例えば、List[Bytes48, 2048] 等。Bytes48 = Vector[Uint8, 48]なので、List[Vector[Uint8, 48], 2048]と、Composite Typeを要素に持つList
1. N個のchunk Bufferを用意する。
2. 要素の先頭から順番にroot_tree_hashを計算する。
3. 2の結果を順番にchunk にコピーしていく。

chunk数 == 1 の場合は上記の結果がhash_tree_rootとなる。
chunk数 > 1 の場合は、Binary Merkleize処理を行う。

Binary Merkleize
4. chunk 数を2の累乗個に拡張。
5. Binary Treeを構築。
6. root hashを算出

with length
7. hash_tree_root値とUint256(length).hash_tree_rootをBinary Merkleizeする。

例は割愛。

Container

各fieldのhash_tree_rootをBinary Merkleizeしていく。
1. field数分のchunk Bufferを用意する。
2. 各fieldを定義の順番通りにroot_tree_hashを計算する。
3. 2の結果を順番にchunk にコピーしていく。

chunk数 == 1 の場合は上記の結果がhash_tree_rootとなる。
chunk数 > 1 の場合は、Binary Merkleize処理を行う。

Binary Merkleize
4. chunk 数を2の累乗個に拡張。
5. Binary Treeを構築。
6. root hashを算出

以下のschemaで具体例を示す。
schema

class DepositData(Container):
    pubkey: BLSPubkey # (= Bytes48)
    withdrawal_credentials: Bytes32
    amount: Gwei # (= Uint64)
    signature: BLSSignature  # Signing over DepositMessage (= Bytes96)
|<

ex)
>|
DepositData = {
  pubkey: '0x6520084850420d1dfb4432a929dfcc5632bfda9930b58031465b314a326a565bf3d66bd66e8d997cfe4d358ae2e248f0',
  withdrawal_credentials: '0xac16207efbbae531fa3355f9ffc079cc1372194dc973cfa8faa4bc52699fb25c',
  amount: 1778195238878610085,
  signature: '0xcfd0fd3c4620e890ea79b3854bbb25f514c21aa70955fc78314c9c7fd151710e60680ad90be70177688f40f25b9e5c642b6f9e233f2ba5df64c63d0da6ccb43f34a6324b27ad5d4b392ac771e648bc64a6aabd5298d25e3f02b2bffd40b85f34'
}

=> [
0x6835da9546c724babbba884a17fa90a08f88d61e8f9cbe8be8b044b66272c1d5,
0xac16207efbbae531fa3355f9ffc079cc1372194dc973cfa8faa4bc52699fb25c,
0xa582a602266bad18000000000000000000000000000000000000000000000000,
0x5a31ad01f804bc3b426ecb4139205142d95374454b41a4d59d88d2259e0de0f4
]
最終的なhash値 =>  0x4384fb4f2351bf205cd59a0421860d6ecaa7029e8935b57d241b13256b64c665
|<