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

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

SSZ - Simple Serialize

本記事では、現在のConsensus-Layer(旧Beacon Chain)で採用されているシリアル化アルゴリズムのSimple Serialize、通称sszについてまとめる。

sszについてまとめるにあたり、以下のサイトを参考にした。

github.com
ethereum.org
eth2book.info

導入の理由

そもそも、Ethereum1.0の時から利用されてきたシリアル化アルゴリズムであるRLPについては、過度に複雑であるとみなされていた。
参考にしたサイトには理由が記載されていなかったが、筆者としては以下の3点が複雑とみなされた理由ではないかと考える。

1. RLP(※)ではデータの長さが分かるが、利用するためには結局data schemaが必要。
2. RLPではシリアライズデータから部分データにアクセスすることができない。
3. シリアル化、デシリアライズが複雑

※RLPについてはGBEC動画で解説しているので、詳しい説明はそちらを参照してほしい。
goblockchain.network


そのため、新しいシリアル化の導入が以前から議論されていた。その中で新たに作成されたのが、Simple Serializeである。
Simple Serializeは以下の特徴を持つ。
1. シリアル化、デシリアライズにはdata schemaが必要
2. シリアル化されたデータから、部分データを抜き出すことが可能
3. Merkleizationが可能なため、データの真偽を判別可能

とくに3番目の特徴が重要で、最終的にsszを採用することを決定づけたものとなる。なお、シリアル化手法の導入については、Protocol Bufferなどのサードパーティー製のものも検討されていたが、外部ライブラリを利用すると、意図しない仕様変更が発生するなど好ましくない状況となるため、最終的には内製のアルゴリズムを利用することになった。

sszで定義されている型

sszで定義されている型は非常に少ない。それぞれ紹介する。

基本型(basic type)

基本型は以下の7種類のみ

名前 バイト数
Uint8 1byte
Uint16 2byte
Uint32 4byte
Uint64 8byte
Uint128 16byte
Uint256 32byte
Boolean true or false

複合型(composite type)

複合型は以下の4つに分類される。

Container
  • 複数のparameterを持つ型。いわゆるstructだったりJSON的なもの。

例:

class ExampleContainer(Container):
 val1: Uint32,
 val2: Uint32,
 vec3: Vector
}
Vector

例:

vector1: Vector =[ 1, 2, 3, 4]
vector2: Vector = [65536, 48002, 0, 1]
List
  • 最大要素数が決まった型。要素数自体は可変

例:

list1:List = [1, 2, 3, 4]
list2:List = [65537]
Bitvector
  • booleanを集めたvector型。Vectorとは区別される。理由はserializationの違いから。詳細は後述

例:

bitvector1: BitVector[4] = [true, false, false, true]
Bitlist
  • booleanを集めたlist型。Listとは区別される。こちらも理由は後述

例:

bitlist1: BitList[8] = [true, false]
Union
  • いわゆるunion。共用体。複数の型表現が可能。
  • 多分現在のBeacon Chainではまだ利用されてないと思われる?

例:

union1: Union[None, Uint64, Uint32] = None (or Uint64(33333)

alias

specの中では、よりわかりやすくするために、sszの型のエイリアスも定義されている。以下に一部抜粋する。

なお、本記事の中でもこれらのエイリアスを利用する。

alias type
Bit Boolean
Byte Uint8
BytesN Vector
ByteList[N] List

初期値(Default Value)

初期値はspecにある通り。ここにも掲載する。

Type 初期値
Uint8~256 0
Boolean false
Container default(type) for type in container
Vector [default(type) * N]
List []
Bitvector [false * N]
Bitlist []
Union[type_0, type_1 ...] default(type_0)

Serialization

シリアル化はSolidityで利用しているABI Encodingに非常によく似ている。大きな違いはvariable typeのpositionがUint32で表現されることだ。

シリアル化ではfixed-partとvariable-partで構成される。fixed-partはfixed sizeの要素のバイト表現をとvariable sizeのbody部分のpositionをUint32のserialize表現を結合して構成される。variable-partはvariable sizeの要素の本体部分で構成される。

fixed size と variable size

List, Bitlist, Unionと、これらの型を1つでも含むcomposit typeがvariable sizeとなる。それ以外はすべてfixed sizeである。

以下に、いくつか例を挙げる。

  • fixed sizeの例
    • bytes: Bytes32 (Vector なので、fixed type)
    • uint32: Uint32
    • long_bytes: Bytes96 (Bytesはどれだけ長くてもfixed type)
    • FixedContainer { uint8: Uint8, uint32: Uint32, bytes8: Bytes8 } (containerでもparamがすべてfixed sizeであればfixed size)
  • variable sizeの例
    • list1: ByteList[256] (Listの場合は常にvariable type)
    • VariableContainer { uint8: Uint8, list: List } (list型など、variable typeを含んでいる場合はfixed type)

basic serialization

まず、basic typeについては以下のルールでシリアル化される。

  • Uint8 ~ 256
    • little-endianのbyte表現。例えば、258をUint16, Uint32, Uint64で表現するとそれぞれ、0x0201(Uint16), 0x02010000(Uint32), 0x0201000000000000(Uint64)となる。
  • Boolean
    • true => 0x01, false => 0x00
    • Booleanは1byteにserializeされるので、VectorよりもBitvectorのほうがシリアライズ後のデータサイズが小さくなる。

composit typeについては、それぞれの要素をserializeして定義された順番に結合したものとなる。が、variable sizeのものについてはposition位置とbody部分を分けて結合する。

詳しくは以下の具体例で示す。

具体例

Beacon Chainのオブジェクトである、IndexedAttestationを例にしてserializationの流れを説明する。

IndexedAttestationの定義

定義については、Beacon Chainのspecのリンクを記載するのでそちらを参照。
github.com
Custom typeの定義についてはこちら。
github.com

serializeするインスタンス

今回は以下のインスタンスをserializeする。

attesting_indices: [14836584338896001841, 5644513999730246312, 5390719578532468900]
data:
  slot: 15812246900578746673
  index: 2764935407589719959
  beacon_block_root: '0x7c7b89bb2766f117cf553e005764ef0e99ab4b8b270d3f8a81f81120043123eb'
  source: {epoch: 13478911193707197911, root: '0xa901742fadec276872af72edfee8ae39baeccdba31049f09ac8a196311c38452'}
  target: {epoch: 3510360685719591030, root: '0xf362b5b18e0a00572dcdefa99668a86d781e82d0fe2aca2df9ee37554310e807'}
signature: '0x2061dd283483a7a8f549f9fb3768278f511a2124e84a7c66aa4656ea45a9dacd4fd7961051b12356ad58880347242cd83b58137575e2639742c2c477826a0bcc6b0a4aca055cbdad6488631f345081db218f9b5d520e453fa525d72bba2bccd1'
||

*** serialize結果
結果だけ先に提示すると、次のbyte列となる。サイズは252byte。
>||
e40000003181c479c76270db97ff489c1a065f267c7b89bb2766f117cf553e005764ef0e99ab4b8b270d3f8a81f81120043123ebd735f4fb50b60ebba901742fadec276872af72edfee8ae39baeccdba31049f09ac8a196311c384527618d0e9714eb730f362b5b18e0a00572dcdefa99668a86d781e82d0fe2aca2df9ee37554310e8072061dd283483a7a8f549f9fb3768278f511a2124e84a7c66aa4656ea45a9dacd4fd7961051b12356ad58880347242cd83b58137575e2639742c2c477826a0bcc6b0a4aca055cbdad6488631f345081db218f9b5d520e453fa525d72bba2bccd1311b0540d922e6cda802a4ab9357554ea4d82b3ae5aecf4a
詳細説明

上記byte列はfixed-partとvariable-partに分割される。
IndexedAttestationではvariable typeは`attesting_indices: List[ValidatorIndex, MAX_VALIDATORS_PER_COMMITTEE]`の1つのみなので、variable-partにはこのListの要素が配置される。それ以外はすべてfixed-partに配置されている。

fixed-partとvariable-partをさらに分解すると以下となる。

  • fixed-part(228byte = 4byte + 128byte + 96byte)
    • 最初の4byteはattesting_indicesのbody部分が配置されているpositionを示す、Uint32のserialize表現
e4000000

これは228の4byte little-endian表現と一致する。つまり、attesting_indicesの要素はこのserializeされたデータの228byte以降に配置されていることを示している。

    • 次の128byteはdataのserialize表現(128byte = 8byte + 8byte + 32byte + 40byte(8+32) + 40byte(8+32))
3181c479c76270db97ff489c1a065f267c7b89bb2766f117cf553e005764ef0e99ab4b8b270d3f8a81f81120043123ebd735f4fb50b60ebba901742fadec276872af72edfee8ae39baeccdba31049f09ac8a196311c384527618d0e9714eb730f362b5b18e0a00572dcdefa99668a86d781e82d0fe2aca2df9ee37554310e8072061dd283483a7a8f549f9fb3768278f511a2124e84a7c66

AttestationDataはすべてfixed sizeの要素で構成されているためAttestationDataもfixed sizeだ。そのためdataの各要素が順番にserializeされて結合される。

    • 最後の96byteはsignatureのserialize表現
aa4656ea45a9dacd4fd7961051b12356ad58880347242cd83b58137575e2639742c2c477826a0bcc6b0a4aca055cbdad6488631f345081db218f9b5d520e453fa525d72bba2bccd1311b0540d922e6cda802a4ab9357554ea4d82b3ae5aecf4a
  • variable-part(24byte = 8byte * 3 elements)
    • attesting_indicesの3つの要素。(24byte = 8byte * 3)
311b0540d922e6cda802a4ab9357554ea4d82b3ae5aecf4a

これはそれぞれUint64であり、以下に示すようにそれぞれの数値の8byte little-endian 表現と一致する。

    • 14836584338896001841 => 0x311b0540d922e6cd
    • 5644513999730246312 => 0xa802a4ab9357554e
    • 5390719578532468900 => 0xa4d82b3ae5aecf4a


以上がsszのserialize方法の具体例を交えた説明となる。

Decode方法

decode方法は上記説明を逆に実行するだけである。serializeでもわかる通り、sszではdata schemaが与えられないとdecodeはできない。

参照実装

ここまで説明したserializeについて理解するためにtypescriptで実装した。リポジトリを共有するので興味のある人は是非試してみてほしい。
github.com