シンプル・シリアライゼーション(SSZ)

シンプル・シリアライゼーション(SSZ)とは、ビーコンチェーンで使用されているシリアライゼーション方法です。 これは、ピア検出プロトコルを除くコンセンサスレイヤー全体の実行レイヤーで使われたRLPシリアライゼーションに取って代わるものです。 SSZは決定的であり、効率的にマークル化するように設計されています。 SSZには、次の2つのコンポーネントがあると見なすことができます。シリアライゼーション・スキームと、シリアル化されたデータ構造を効率的に処理するように設計されたマークライゼーション・スキームです。

シンプル・シリアライゼーション(SSZ)

シリアライゼーション

シンプル・シリアライゼーション(SSZ)は自己記述型ではなく、むしろ事前に知らされているスキーマに依存するシリアライゼーション・スキームです。 SSZシリアル化の目的は、任意の複雑なオブジェクトをバイト列で表すことです。 「基本型」の場合は、非常に簡単な処理です。 エレメントは、単に16進数のバイトに変換されます。 基本型には、次のものがあります。

• 符号なし整数型
• ブール型

複雑な「複合型」の場合は、異なる型やサイズ、その両方を持つ可能性のある複数の要素を含むため、シリアライゼーションがより煩雑になります。 これらのオブジェクトがすべて固定長(すなわち、要素のサイズは実際の値に関係なく常に一定)である場合、シリアライゼーションは単に、複合型の各要素をリトルエンディアンのバイト文字列に変換することで、 これらのバイト文字列が結合されます。 シリアル化されたオブジェクトは、デシリアル化されたオブジェクトに現れるのと同じ順序で、固定長の要素がバイトリストで表現された内容になっています。

可変長の型では、実データは、シリアル化されたオブジェクトの要素の位置である「オフセット」値によって置き換えます。 実データは、シリアル化されたオブジェクトの最後のヒープに追加されます。 オフセット値は、ヒープ内の実データの開始を示すインデックスであり、関連するバイトへのポインターとして機能します。

以下の例で、固定長と可変長の要素をもつコンテナのオフセットの仕組みを説明します。

1
2    struct Dummy {
3
4        number1: u64,
5        number2: u64,
6        vector: Vec<u8>,
7        number3: u64
8    }
9
10    dummy = Dummy{
11
12        number1: 37,
13        number2: 55,
14        vector: vec![1,2,3,4],
15        number3: 22,
16    }
17
18    serialized = ssz.serialize(dummy)
19
すべて表示

serializedは、次のような構造になります。 ここでは、4ビットにしていますが、実際は32ビットに付け足されます。また、分かりやすくするために int(整数型)で表しています。

1[37, 0, 0, 0, 55, 0, 0, 0, 16, 0, 0, 0, 22, 0, 0, 0, 1, 2, 3, 4]
2------------  -----------  -----------  -----------  ----------
3      |             |            |           |            |
4   number1       number2    offset for    number 3    value for
5                              vector                   vector
6

次は、分かりやすくするために改行を加えています。

1[
2  37, 0, 0, 0,  # little-endian encoding of `number1`.
3  55, 0, 0, 0,  # little-endian encoding of `number2`.
4  16, 0, 0, 0,  # The "offset" that indicates where the value of `vector` starts (little-endian 16).
5  22, 0, 0, 0,  # little-endian encoding of `number3`.
6  1, 2, 3, 4,   # The actual values in `vector`.
7]

上記は、まだ単純化されています。上のコードにある整数とゼロは、実際には次のようなバイトリストとして格納されます。

1[
2  10100101000000000000000000000000  # little-endian encoding of `number1`
3  10110111000000000000000000000000  # little-endian encoding of `number2`.
4  10010000000000000000000000000000  # The "offset" that indicates where the value of `vector` starts (little-endian 16).
5  10010110000000000000000000000000  # little-endian encoding of `number3`.
6  10000001100000101000001110000100   # The actual value of the `bytes` field.
7]

可変長型の実際の値は、シリアル化されたオブジェクトの末尾にあるヒープに格納され、オフセット値はフィールドの順序付けられたリストの正しい位置に格納されます。

また、特別な対応が必要となる特殊ケースもあります。例えば、BitList型のように、シリアル化時に長さの上限を追加し、デシリアル化時に削除する必要があるような型です。 詳細については、SSZの仕様(opens in a new tab)を参照してください。

デシリアライゼーション

このオブジェクトをデシリアライズするには、スキーマが必要になります。 スキーマに、シリアル化されたデータの正確なレイアウトを定義することで、特定の各要素をバイトのブロブ(blob)から適切な型、値、サイズ、位置を持つ意味のあるオブジェクトにデシリアル化できるようにします。 どれがオフセット値でどれが実際の値であるか伝えるのは、デシリアライザーです。 全フィールド名は、オブジェクトがシリアル化されたときに消えますが、スキーマによりデシリアライゼーション時に再インスタンス化されます。

SSZに関するインタラクティブな説明については、ssz.dev(opens in a new tab)を参照してください。

マークライゼーション(Merkleization)

このSSZでシリアル化されたオブジェクトは、次にマークル化でき、つまり同データをマークルツリー表現に変換できます。 最初に、シリアル化されたオブジェクトの32バイトのチャンク数が決定されます。 これらは、ツリー (木) の「リーフ (葉) 」です。 リーフの合計数が、2の冪乗でなければなりません。これにより、リーフをまとめてハッシュ化すると、最終的に単一のハッシュ・ツリー・ルートが生成されます。 2の冪乗にならない場合は、32バイトのゼロを持つリーフが追加されます。 図式化すると次のようになります。

1        hash tree root
2            /     \
3           /       \
4          /         \
5         /           \
6   hash of leaves  hash of leaves
7     1 and 2         3 and 4
8      /   \            /  \
9     /     \          /    \
10    /       \        /      \
11 leaf1     leaf2  leaf3     leaf4
すべて表示

また、上の例のように自然にツリーのリーフが均等とならない場合があります。 例えば、リーフ4 (leaf4)が複数の要素を持ちマークルツリーに「深さ」を追加する必要があるコンテナだとすると、不均一なツリーになる場合があります。

これらのツリーの要素をリーフX(leaf X)やノードX(node X)などと呼ぶ代わりに、ルートを1(root=1)として開始し、左から右へ各レベルごとにカウントする一般化インデックスを付与することができます。 先で述べたインデックスが、この一般化インデックスです。 シリアル化されたリストの各要素は、2**depth + idxに等しい一般化インデックスを持ちます。ここで、idxは、シリアル化されたオブジェクトのゼロインデックスの位置です。深さはマークルツリーのレベル数で、要素(リーフ)の数である2を底とする対数として決定することができます。

一般化インデックス

一般化インデックスは、各ノードが2 ** depth + index in rowに一般化したインデックスを持つ二分マークルツリーのノードを表す整数です。

1        1           --depth = 0  2**0 + 0 = 1
2    2       3       --depth = 1  2**1 + 0 = 2, 2**1+1 = 3
3  4   5   6   7     --depth = 2  2**2 + 0 = 4, 2**2 + 1 = 5...
4

この説明では、マークルツリーの各データのノードインデックスを生成しています。

マルチプルーフ

特定の要素を表す一般化インデックスのリストを提供することで、ハッシュ・ツリー・ルートに対して検証することができます。 このルートは、受け入れられた真実のバージョンです。 提供されたすべてのデータは、(一般化インデックスによって決定された)マークルツリー内の適切な場所に挿入し、ルートが一定のままであることを確認することで、真実性に対して検証することができます。 こちら(opens in a new tab)の仕様書に、一般化インデックスの特定のセットの内容を検証するために必要なノードの最小セットを計算する方法として、関数が示されています。

例えば、下記のツリーのインデックス9のデータを検証する場合、インデックス8、9、5、3、1のデータのハッシュが必要です。 (8,9)のハッシュは、(4)のハッシュと等しい必要があり、これは5とハッシュして2を生成し、3とハッシュしてツリールート1を生成します。 もし、9に誤ったデータが提供された場合、ルートが変更されることになります。これを検知し、ブランチの検証が失敗します。

1* = data required to generate proof
2
3                    1*
4          2                      3*
5    4          5*          6          7
68*     9*   10    11   12    13    14    15
7

参考文献

• イーサリアムのアップグレード: SSZ(opens in a new tab)
• イーサリアムのアップグレード: マークライゼーション(opens in a new tab)
• SSZの実装(opens in a new tab)
• SSZ計算器(opens in a new tab)
• SSZ.dev(opens in a new tab)