シンプル・シリアライズ (Simple serialize)

シンプル・シリアライズ (SSZ) は、ビーコン・チェーンで使用されるシリアライゼーション手法です。ピア・ディスカバリー・プロトコルを除き、コンセンサス・レイヤー全体で、実行レイヤーで使用されるRLPシリアライゼーションに代わるものです。RLPシリアライゼーションの詳細については、再帰的長さプレフィックス (RLP)を参照してください。SSZは、決定論的であり、効率的にマークル化 (Merkleize) できるように設計されています。SSZは、シリアライゼーション・スキームと、シリアライズされたデータ構造で効率的に機能するように設計されたマークル化スキームの2つのコンポーネントで構成されていると考えることができます。

SSZの仕組み

シリアライゼーション

SSZは自己記述型ではないシリアライゼーション・スキームであり、事前に把握しておく必要があるスキーマに依存しています。SSZシリアライゼーションの目的は、任意の複雑さを持つオブジェクトをバイト列として表現することです。これは「基本型 (basic types)」にとっては非常にシンプルなプロセスです。要素は単に16進数のバイトに変換されます。基本型には以下が含まれます。

符号なし整数
ブール値

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

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

以下の例は、固定長要素と可変長要素の両方を持つコンテナでオフセットがどのように機能するかを示しています。


    struct Dummy {

        number1: u64,
        number2: u64,
        vector: Vec<u8>,
        number3: u64
    }

    dummy = Dummy{

        number1: 37,
        number2: 55,
        vector: vec![1,2,3,4],
        number3: 22,
    }

    serialized = ssz.serialize(dummy)

serialized は次のような構造になります (ここではわかりやすくするために4ビットにパディングしていますが、実際には32ビットにパディングされ、int 表現を維持しています)。

[37, 0, 0, 0, 55, 0, 0, 0, 16, 0, 0, 0, 22, 0, 0, 0, 1, 2, 3, 4]
------------  -----------  -----------  -----------  ----------
      |             |            |           |            |
   number1       number2    vectorの      number 3    vectorの
                           オフセット                    値

わかりやすくするために行に分割すると、次のようになります。

[
  37, 0, 0, 0,  # `number1` のリトルエンディアン・エンコーディング。
  55, 0, 0, 0,  # `number2` のリトルエンディアン・エンコーディング。
  16, 0, 0, 0,  # `vector` の値が始まる場所を示す「オフセット」 (リトルエンディアンの16)。
  22, 0, 0, 0,  # `number3` のリトルエンディアン・エンコーディング。
  1, 2, 3, 4,   # `vector` の実際の値。
]

これもまだ簡略化されたものです。上記の図式にある整数とゼロは、実際には次のようなバイトリストとして保存されます。

[
  10100101000000000000000000000000  # `number1` のリトルエンディアン・エンコーディング
  10110111000000000000000000000000  # `number2` のリトルエンディアン・エンコーディング。
  10010000000000000000000000000000  # `vector` の値が始まる場所を示す「オフセット」 (リトルエンディアンの16)。
  10010110000000000000000000000000  # `number3` のリトルエンディアン・エンコーディング。
  10000001100000101000001110000100   # `bytes` フィールドの実際の値。
]

したがって、可変長の型の実際の値は、シリアライズされたオブジェクトの最後にあるヒープに保存され、そのオフセットは順序付けられたフィールドリストの正しい位置に保存されます。

また、シリアライゼーション時に長さの上限を追加し、デシリアライゼーション時に削除する必要がある BitList 型など、特別な処理を必要とする特殊なケースもいくつかあります。詳細については、SSZ仕様 (opens in a new tab)を参照してください。

デシリアライゼーション

このオブジェクトをデシリアライズするには、スキーマが必要です。スキーマはシリアライズされたデータの正確なレイアウトを定義しており、各特定の要素をバイト列から、正しい型、値、サイズ、位置を持つ意味のあるオブジェクトへとデシリアライズできるようにします。デシリアライザに対して、どの値が実際の値で、どの値がオフセットであるかを指示するのはスキーマです。オブジェクトがシリアライズされるとすべてのフィールド名は消滅しますが、デシリアライゼーション時にスキーマに従って再インスタンス化されます。

マークル化

このSSZでシリアライズされたオブジェクトは、その後マークル化 (merkleized) することができます。つまり、同じデータのマークル・ツリー表現に変換されます。まず、シリアライズされたオブジェクト内の32バイトのチャンクの数が決定されます。これらがツリーの「葉 (leaves)」になります。葉を一緒にハッシュ化して最終的に単一のハッシュ・ツリー・ルート (hash-tree-root) を生成できるように、葉の総数は2の累乗でなければなりません。自然にそうならない場合は、32バイトのゼロを含む追加の葉が追加されます。図で表すと次のようになります。

ハッシュ・ツリー・ルート
            /     \
           /       \
          /         \
         /           \
     葉1と2の        葉3と4の
     ハッシュ        ハッシュ
      /   \            /  \
     /     \          /    \
    /       \        /      \
  葉1       葉2     葉3       葉4

上記の例のように、ツリーの葉が自然に均等に分布しない場合もあります。たとえば、葉4が複数の要素を持つコンテナであり、マークル・ツリーに追加の「深さ (depth)」を追加する必要があり、不均等なツリーが作成される可能性があります。

これらのツリー要素を葉X、ノードXなどと呼ぶ代わりに、ルート = 1から始まり、各レベルに沿って左から右に数える一般化インデックス (generalized indices) を与えることができます。これが上記で説明した一般化インデックスです。シリアライズされたリスト内の各要素は、2**depth + idx に等しい一般化インデックスを持ちます。ここで、idxはシリアライズされたオブジェクト内のゼロから始まるインデックス位置であり、深さ (depth) はマークル・ツリーのレベル数です。これは、要素 (葉) の数の2を底とする対数として決定できます。

一般化インデックス

一般化インデックスは、バイナリ・マークル・ツリー内のノードを表す整数であり、各ノードは 2 ** depth + index in row という一般化インデックスを持ちます。

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

この表現により、マークル・ツリー内の各データに対するノード・インデックスが得られます。

マルチプルーフ

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

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

* = 証明の生成に必要なデータ

                    1*
          2                      3*
    4          5*          6          7
8*     9*   10    11   12    13    14    15