こんにちは、Gincoの永田(@nagatkaz116)です。

皆さんはZilliqaという暗号通貨をご存知でしょうか？ シャーディングという手法を用いることで高いトランザクションスループットを実現し、なおかつスマートコントラクトのプラットフォームも提供するZilliqaは、今非常に期待されている暗号通貨の一つです。

そんなZilliqaですが、Zilliqaの公式チームからホワイトペーパーの翻訳について許可を頂いたので、本日はホワイトペーパー全文を以下に翻訳したいと思います。一部、ホワイトペーパーから仕様変更がありますが、オリジナルのホワイトペーパーにも目を通したいという方は是非参考にして頂ければと思います。

なお、本ホワイトペーパーはこちらからpdf版を閲覧・ダウンロード可能です。「出力して勉強に用いたい」「輪読会したい」といった方はぜひご活用ください。

Zilliqaテクニカルホワイトペーパー

要約

既存の暗号通貨とスマートコントラクトプラットフォームはスケーラビリティ問題を持つことで知られる。 つまり、秒間に処理することのできるトランザクション数は限られており、大抵の場合10より少ない。 パブリックな暗号通貨とスマートコントラクトプラットフォームを利用したアプリケーションが増えるにつれて、秒間に数百とか数千のオーダーでトランザクションを処理できることが要求される。

我々はZilliqaを提案する。 これはトランザクションレートにおいてスケールするように設計された新しいブロックチェーンプラットフォームである。 Zilliqaのマイナーが増えるにつれて、トランザクションレートの増加が期待される。 現在イーサリアムのネットワークは30,000マイナーほどの規模であるが、同規模のネットワークならZilliqaの場合イーサリアムの約1000倍のトランザクションレートで処理することができる。 Zilliqa設計において非常に重要な概念がシャーディングである。 マイニングネットワークをシャードと呼ばれる小さなグループに分割し、それぞれがトランザクションを並列に処理する。

さらにZilliqaは革新的であり特定の目的に適したスマートコントラクト記述言語と実行環境を提案し、Zilliqaアーキテクチャを利用して大規模かつ高効率な計算プラットフォームを提供する。 Zilliqaのスマートコントラクト記述言語は並列処理を簡単に行うことのできるような大規模計算に適したデータフロープログラミング形式に従っている。 例えば、検索、並び替え、線形代数計算のような単純な計算からニューラルネットワークの学習やデータマイニング、科学計算のような複雑な計算も可能だ。 一般的にMapReduceタスクなら何でも処理することができる。

第１章　導入

暗号通貨やスマートコントラクトプラットフォームは共有の計算リソースになりつつある。 こうしたプラットフォームを何千ものコンピューターが同時に動く新世代のコンピューターと捉えることもできる。 しかし、既存の暗号通貨やスマートコントラクトプラットフォームはスケーリングについてよく知られた限界が存在する。 ビットコイン[1]、イーサリアム[2]や関連する暗号通貨の平均トランザクションレートは秒間10を下回る（大抵3から7程度）。 パブリックな暗号通貨とスマートコントラクトプラットフォームを利用したアプリケーションが増えるにつれて、秒間に数百のオーダーでトランザクションを処理できることが要求される。 世界規模の決済ネットワークの場合は秒間何万ものトランザクションレートが要求される。 それほどの処理能力を持つ非中央集権的でオープンなブロックチェーンプラットフォームを開発することはできるのか？

既存プロトコルのスケーラビリティ問題は幾分根本的な問題で、コンセンサスプロトコルとネットワークプロトコルの設計に根付く問題である。 よって、例えばビットコインやイーサリアムといった既存のプロトコルのパラメータ（例えばブロックサイズやブロックレート）を変更したところで、多少は速度が上がるだろうが、秒間何千ものトランザクションレートを必要とするようなアプリケーションをサポートするなら基礎となるプロトコルを最初から考え直さなければならない。

我々はトランザクションレートにおいてスケールするよう設計された新しいブロックチェーンプラットフォームであるZilliqaを提案する。 Zilliqaのマイナーが増えるにつれてトランザクションレートも増えることが期待される。 具体的には、数百のノードがネットワークに加わるたびにトランザクションレートはおおよそ倍になるよう設計されている。 執筆時点で、イーサリアムのマイニングネットワークは30,000ノード以上であるが、同程度の規模ならZilliqaはイーサリアムの約1000倍のトランザクションレートで処理することができるはずだ。

Zilliqaは最初から再設計され、2年以上研究開発が行われてきた。 Zilliqaの設計において非常に重要な概念はシャーディングである。 これは、マイニングネットワークをシャードと呼ばれる小さなグループに分割し、それぞれがトランザクションを並列に処理するというものだ。 例えば、Zilliqaのマイニングネットワークに8000マイナーいるとして、Zilliqaは自動的にそれぞれ800マイナーのサブネットワークを10個作成する。 この時、信頼すべき調整者が存在しないような非中央集権的な方法でサブネットワークが作成される。 ここで、一つのサブネットワークで１エポックにつき仮に100トランザクションの同意が得られたとすると、10のサブネットワークで合計すると1000トランザクションの合意が得られたことになる。 各サブネットワークから安全にトランザクションを集めるためには各サブネットワークが二重支払いなどの重複なしで異なるトランザクションを処理していることを保証するのが重要だ。

前提条件は既存のブロックチェーンベースの解決策に似ている。 マイニングネットワークには一部悪意を持ったノード・アイデンティティが存在し、その計算能力の合計はネットワーク全体の計算能力の1/4より少ないと仮定している。 標準的なPoWのスキームに基づいているが、新しい２層ブロックチェーン構造を持ち、シャードを処理するために高度に最適化されたコンセンサスアルゴリズムを持つ。

さらにZilliqaは革新的であり特定の目的に適したスマートコントラクト記述言語と実行環境を提案し、Zilliqaアーキテクチャを利用して大規模かつ高効率な計算プラットフォームを提供する。 Zilliqaにおけるスマートコントラクト記述言語はデータフロープログラミング形式に従っており、スマートコントラクトは有向グラフで表すことができる。 そのグラフにおけるノードはオペレーションや関数であり、二つのノード間の弧は１つ目のノードの出力と２つ目のノードへの入力を意味する。 ノードはそのノードへの入力全てが有効になるとアクティブになる（つまり実行可能になる）ことから、データフローコントラクトは本質的に並列であり、Zilliqaのような非中央集権的システムに適しているのだ。

シャードを用いたアーキテクチャーは並列化が容易な大規模処理を行うのに非常に適している。 例えば、検索、並び替え、線形代数計算のような単純な計算から、ニューラルネットワークの学習やデータマイニング、科学計算のような複雑な計算も可能だ。 一般的にMapReduceタスクなら何でも処理することができる。

この文書ではZilliqaブロックチェーンプロトコルの技術設計について述べる。Zilliqaは新しく、概念的に簡潔でモジュール化された設計を持ち、６つの層で構成される。暗号層（第３章）、データ層（第４章）、ネットワーク層（第５章）、コンセンサス層（第６章）、スマートコントラクト層（第７章）、インセンティブ層（第８章）である。各層について説明する前に、まずはシステム設定、前提、脅威モデルについて第２章で議論する。

第２章　システム設定と前提

エンティティ
Zilliqaにはユーザーとマイナーという２つのエンティティが存在する。 ユーザーはZilliqaのインフラを使って送金したりスマートコントラクトを実行する外部のエンティティである。 マイナーはZilliqaのコンセンサスプロトコルを実行し報酬を得るネットワーク内のノードである。 このホワイトペーパーでは今後マイナーとノードを同じ意味で用いる。

Zilliqaのマイニングネットワークはさらにシャードと呼ばれるより小さな複数のネットワークに分割される。 マイナーはDSノードと呼ばれるマイナーのグループによってシャードに割り振られる。 このDSノードのグループをDSコミッティーと呼ぶ。 各シャードとDSコミッティーにはリーダーが存在する。 リーダーはZilliqaのコンセンサスプロトコルとネットワークの全体的な機能において重要な役割を担う。

各ユーザーは電子署名スキームのための公開鍵と秘密鍵のペアを持ち、各マイナーはアイデンティティとしての役目を持つIPアドレスと公開鍵を持つ。

ネーティブトークン
ZilliqaにはZillingと呼ばれるネーティブトークン（短縮してZIL）を持つ。 ユーザーはZillingを保有することでトランザクション処理やスマートコントラクトの実行に対して手数料を払うことができるため、ZillingはZilliqaプラットフォームにおけるある種の使用権利と言える。 このホワイトペーパーでは、全ての金額はZILに基づくことを前提としている。

脅威モデル
マイニングネットワークにはいかなる時も一部のビザンチンノード・アイデンティティが存在し、その合計計算能力はネットワーク全体の計算能力の1/4より小さいことを前提としている。 1/4という数字は1/3から離れている任意の定数であり、合理的な数字として選ばれている。 さらに、正直なノードはプロトコルを実行している間信頼できると前提を置いており、ブロック生成に失敗したり接続が切れるノードはビザンチンノードに含むとする。

ビザンチンノードはプロトコルを守らず、メッセージを削除・修正したり、異なるメッセージを正直なノードに送ることができる。 さらに全てのビザンチンノードは共謀することもできる。ビザンチンノードの合計計算能力は標準的な暗号学的前提である確率的多項式時間に基づくと限定する。

我々は（ネットワーク分断がないとして）正直なノードからのメッセージは正直なノードへある一定の時間待てば伝わるという前提をおいているが、この「一定の時間」は時間と共に変化する。 この変数はライブネスを保証するものであり安全性を保証するものではない[3]。 そのようなタイミングと接続の前提を満たさないとき、ビザンチンノードがメッセージを大幅に遅延させたり、もっと悪ければネットワークを「失墜」させることができるようになる[4]。ネットワーク分断がある時には、CAP理論でも述べられているように、一貫性と可用性のどちらかを選ぶしかない[5]。Zilliqaでは、一貫性をとり可用性を犠牲にする。

第３章　暗号層

暗号層はZilliqaで使われる低レベルの汎用暗号アルゴリズムを定義する。 他のいくつかのブロックチェーンプラットフォームと同様に、Zilliqaは電子署名に楕円曲線暗号を用い、PoWにメモリーハードハッシュ関数を用いる。

このホワイトペーパーでは設計を説明するにあたり広くSHA3ハッシュ関数[6]を用いる。 SHA3はもともと特にイーサリアムをはじめとする様々なブロックチェーンプラットフォームに使われているKeccak[7]に基礎を置く。 近い将来、他のプラットフォームとの相互運用性をより高めるためにKeccakに切り替える可能性がある。

A. シュノア署名

Zilliqaは楕円曲線シュノア署名アルゴリズム（EC-Schnorr）[8]を署名アルゴリズムとして採用している。カーブにはsecp256k1[9]を用いている。このカーブはビットコインやイーサリアムでも使われているがECDSA という異なる署名アルゴリズムを用いている。ECDSAではなくEC-Scnorrを用いると次のような利点がある。

1) 頑強性

俗な言い方をすると、頑強性とはある秘密鍵を使って得られたあるメッセージへの署名があった時に、悪意を持った第三者がその対応する公開鍵で有効だと認められる新しい署名を作成することが困難であることを意味する。ECDSAと違いEC-Shnorrは頑強性を持つと証明されている[10]。

2) マルチシグネチャー

マルチシグネチャーを用いると複数の署名者によるあるメッセージに対する署名を集めて一つの署名にすることができる。 その署名は、権限を持つ人たちの鍵を集約した一つの公開鍵で認証することができる。 EC-Schnorrは元々マルチシグネチャースキームであるのに対して[11]、ECDSAはマルチシグネチャーを作ることは一応できるが柔軟性は低い。

Zilliqaはあるメッセージに対して複数の署名が求められる時に署名のサイズを減らすべくEC-Schnorrをベースとしたマルチシグネチャーを用いている。 複数の参加者が署名をすることであるデータについて合意する必要のある我々のコンセンサスプロトコルでは、署名のサイズが小さいということは特に重要だ。

3) 速度

ECDSAは大きい数に対するモジュラ逆数を計算する必要があるのでEC-Shnorrの方がECDSAより速い。 EC-Schnorrでは逆数演算は必要ない。

EC-Shnorrの正確な鍵生成、署名、検証の手続きは付録Aに掲載する。付録ではEC-Schnorrがどのようにマルチシグネチャースキームとして使うことができるかも示している。

B. PoW

Zilliqaはシビル攻撃を防ぎノードアイデンティティを生成するためだけにPoWを用いる。 これはPoWが分散コンセンサスを得るために使われている多くの既存ブロックチェーンと対照的である（特にビットコイン[1]やイーサリアム[12]）。 Zilliqaはイーサリアム1.0で用いられているPoWアルゴリズムであるEthash[13]を採用している。

EthashはGPUでマイニングするのを簡単にするがASICのような特定の計算ハードウェアでは難しくなるように設計されているメモリーハードハッシュ関数である。 これを達成するためにEthashの計算には関数が特定の計算ハードウェアでは並列処理できないように大量のメモリとI/O帯域幅を必要とする。

大まかに説明すると、Ethashはデータ（例えばブロックヘッダー）と64ビットのnonceを入力として受け取り256ビットのハッシュを生成する。 アルゴリズムは順番に計算される４つのサブルーチンで成り立つ。

  1. Seed generation
    シードはエポックと呼ばれる毎30,000ブロックおきに生成されるSHA3-256ハッシュである。 最初のエポックについては全て0でサイズ32のバイト列のSHA3-256ハッシュとする。 それ以降は、常に前エポックのシードのSHA3-256ハッシュとする。
  2. Cache generation
    シードはSHA3-512を用いて擬似乱数キャッシュを生成するのに用いられる。 キャッシュのサイズはエポック数と共に線形に増えていく。 最初のキャッシュサイズは16MBである。
  3. Dataset generation
    キャッシュはデータセットを生成するのに用いられる 。ここでデータセット内の各項目はキャッシュ内のごくわずかのアイテムに依存している。 マイナーが頻繁にデータセットに変更を加えなくても良いように各エポック１回だけデータセットが更新される。 データセットのサイズもエポックと共に線形に増えていく。 最初のサイズは1GBである。
  4. Mining and Verification
    マイニングではデータセット内のランダムな部分セットを取り出し、それのハッシュを生成する。 検証ではハッシュを計算するのに必要なデータセット内の特定の部分セットを再生成するのにキャッシュを用いる。

第４章　データ層

一般的にデータ層はZilliqaのグローバル状態を構成するデータを定義する。 さらにはZilliqaの様々なエンティティがグローバル状態を更新するために必要なデータも定義する。

A. アカウント、アドレス、状態

Zilliqaはイーサリアム同様アカウントベースのシステムである。 ２種類のアカウントが存在し、ノーマルアカウントとコントラクトアカウントだ。 ノーマルアカウントはEC-Schnorrの秘密鍵を生成することで作られる。 コントラクトアカウントは他のアカウントによって作られる。

各アカウントはアドレスで特定されるが、アカウントの種類によってその導出方法は異なる。 ノーマルアカウントのアドレスはそのアカウントの秘密鍵から導出される。 秘密鍵が与えられた時、アドレスは次の計算式から導かれる160ビットの値である。

equation

ここで、は入力の右側160ビットを返す関数であり、は入力の秘密鍵に対応する公開鍵を返す関数である。 コントラクトアカウントのアドレスはその作成者のアドレスとaccount nonceという作成者のアカウントがこれまでいくつのトランザクションを送ってきたかから計算される。

equation

ここで、は作成者のアカウントアドレスであり、は作成者のnonceである。

各アカウントは（ノーマルアカウントでもコントラクトアカウントでも）アカウント状態と結びついている。 アカウント状態はキーと値によるストレージであり、次のようなキーを含む。

  1. account nonce（64ビット）
    ノーマルアカウントから送られたトランザクションの数を数えるカウンターである（初期値は0）。 コントラクトアカウントの場合は、そのアカウントによって作られたコントラクトの数を数える。
  2. balance（128ビット）
    非負の値。アカウントが別のアカウントからトークンを受け取ると受取額がアカウント残高に加算される。 アカウントが別のアカウントにトークンを送ると残高は適切な額だけ減る。
  3. code hash（256ビット）
    コントラクトコードのSHA3-256ハッシュを保存する。 普通アカウントに対しては空の文字列に対するSHA3-256ハッシュである。
  4. storage root（256ビット）
    先述の通り、各アカウントはキーと値のストレージを持つが、storage rootはこのストレージを表すSHA3-256ハッシュだ。 例えば、このストレージがトライ木なら、storage rootはこのトライ木のルートである。

Zilliqaのグローバル状態はアカウントアドレスとアカウント状態のマッピングである。 トライ木のようなデータ構造を用いて実装されている。

B. トランザクション

トランザクションは常にノーマルアカウントのアドレスから送られ、Zilliqaのグローバル状態を更新する。 トランザクションは次のフィールドを持つ。

  1. version（32ビット）
    現在のバージョン。
  2. nonce（64ビット）
    あるトランザクションの送信者によって送られたトランザクションを数えるカウンター。
  3. to（160ビット）
    送信先のアカウントアドレス。トランザクションが新しいコントラクトアカウントを作成する時には、このフィールドは空の文字列のSHA3-256の右側160ビットである。
  4. amount（128ビット）
    送信先のアドレスに送られたトランザクション金額
  5. gas price（128ビット）
    ガスは計算の最小単位として定義される。gas priceとはトランザクション処理の中で起きる計算に対して送信者が払うガス単価のことを指す。
  6. gas limit（128ビット）
    トランザクションを処理していている間に使っても良い最大ガス量。
  7. code（無制限）
    コントラクトコードを表す拡張可能なバイト列。新しいコントラクトアカウントを作成する時のみ存在すする。
  8. data（無制限）
    トランザクションを処理する際に用いられるデータを表す拡張可能なバイト列。あるアドレスに対してコントラクトを呼び出すトランザクションの時のみ存在する。
  9. pubkey（264ビット）
    署名を検証するために使われるEC-Schnorrの公開鍵。pubkeyからそのトランザクションの送信者アドレスも決まる。
  10. signature（512ビット）
    データ全体に対するEC-Schnorr署名。

各トランザクションはtransaction IDと呼ばれるsignatureフィールドを除いたトランザクションデータに対するSHA3-256ハッシュでユニークに特定することができる。

C. ブロック

Zilliqaプロトコルは２種類のブロックを導入する。transaction block（TX-Block）とdirectry servise block（DS-Block）である。TX-Blockはユーザーに送られたトランザクションを含むのに対して、DS-Blockはコンセンサスプロトコルに参加しているマイナーに関するメタデータを含む。

1) DS-Block

DS-Blockはheaderとsignatureから構成される。 header部分は次のようなフィールドで構成される。

  1. version（32ビット）
    現在のバージョン。
  2. previous hash（256ビット）
    親ブロックのヘッダーに対するSHA3-256ハッシュ。
  3. pubkey（264ビット）
    そのブロックヘッダーに対してPoWを行ったマイナーの公開鍵。
  4. difficulty（64ビット）
    前のブロックのディフィカルティとブロック番号から計算できる。PoWのディフィカルティを保存する。
  5. number（256ビット）
    そのブロックよりも前に存在するブロックの数。ジェネシスブロックはブロック番号0である。
  6. timestamp（64ビット）
    ブロックが生成された時のUnix時刻。
  7. mixHash（256ビット）
    nonceから計算されるハッシュで、DoS攻撃を検知することができる。
  8. nonce（64ビット）
    PoWの解。

signature部分は次の２つのフィールドで構成される。

  1. signature（512ビット）
    DS-Blockヘッダーに対してDSノードによって行われるEC-Schnorrマルチシグネチャー。
  2. bitmap（1024ビット）
    どのDSノードがマルチシグネチャーに参加したかを記録する。 ビットマップをビットベクトルと表し、番目のノードが署名していればで、していなければ。

DSブロックはDSブロックチェーンを構成する。

2) TX-Block

先述の通りDS-Blockはトランザクションのコンセンサスに達したノードに関する情報を含む。 TX-BlockはDS-Block内のノードによってどのトランザクションが合意に達したのかについての情報を含む。 各DS-Blockは複数のTX-Blockと結びついている。TX-Blockはheader、data、signatureの３つの部分から構成される。 headerは以下のフィールドで成り立つ。

  1. type（8ビット）
    TX-Blockには２種類あり、マイクロブロック(0x00)と最終ブロック(0x01)である。詳細は第５章Dで述べる。
  2. version（32ビット）
    現在のバージョン。
  3. previosu hash（256ビット）
    親ブロックヘッダーのSHA3-256ハッシュ。
  4. gas limit（128ビット）
    ブロックあたりのガス消費限度量。
  5. gas used（128ビット）
    そのブロックに含まれるトランザクションで消費された合計ガス量。
  6. number（256ビット）
    そのブロックよりも前に存在するブロックの数。ジェネシスブロックはブロック番号0である。
  7. timestamp（64ビット）
    ブロックが生成された時のUnix時刻。
  8. state root（256ビット）
    全てのトランザクションが実行されファイナライズした後のグローバル状態を表すSHA3-256ハッシュ。グローバル状態がトライ木として保存されるのであれば、state rootはそのトライ木のルートハッシュである。
  9. transaction root（256ビット）
    そのブロック内の全てのトランザクションを保存するマークルツリーのルートを表すSHA3-256ハッシュ。
  10. tx hashes（各256ビット）
    トランザクションのSHA3-256ハッシュを集めたリスト。シグネチャー部分も含む。
  11. pubkey（264ビット）
    ブロックを提案したリーダーのEC-Schnorr公開鍵。
  12. pubkey micro blocks（無制限）
    EC-Schnor公開鍵のリスト（各264ビット）。リストにはトランザクションを提案したリーダー達の公開鍵を含む。最終ブロックの時のみ存在する。
  13. parent block hash（256ビット）
    前のfinal blockヘッダーのSHA3-256ハッシュ。
  14. parent ds hash（256ビット）
    親DS-BlockヘッダーのSHA3-256ハッシュ。
  15. parent ds block number（256ビット）
    親DS-Block番号。

data部分はトランザクションセットを含み、次のフィールドで構成される。

  1. tx count（32ビット）
    そのブロック内に含まれるトランザクション数。
  2. tx list（無制限）
    トランザクションリスト。

signature部分はEC-Schnorrマルチシグネチャーを含む。 次の２つのフィールドで構成される。

  1. signature（512ビット）
    複数のノードによってTX-Blockヘッダーに対して行われたEC-Schnorrマルチシグネチャー。 署名はそのブロックがマイクロブロックなのか最終ブロックなのかで異なるノード群によって生成される。 署名に関する詳細は第５章Dで説明する。
  2. bitmap（1024ビット）
    どのノードがマルチシグネチャーに参加したかを記録する。 ビットマップをビットベクトルと表し、番目のノードが署名していればで、していなければ。

最終ブロックがトランザクションブロックチェーンを構成する。 トランザクションブロックチェーンにはマイクロブロックは含まれない。

第５章　ネットワーク層

Zilliqaはトランザクションレートにおいてスケールするように設計された。 主要なアイデアはシャーディングであり、つまりマイニングネットワークを小さなシャードに分割し、それぞれが並列にトランザクションを処理できる。 この章ではネットワークシャーディングとトランザクションシャーディングについて説明する。

A. ネットワークシャーディング

ネットワークシャーディング、つまりマイニングネットワークを小さなシャードに分割することは２段階の処理である。 まずDSコミッティーと呼ばれる特殊ノード群を選び、次にネットワークをシャードに分割してノードを割り振る。 このプロセスを以下に説明する。

1) Directory Service Comittee

ネットワークシャーディングを行うためにまずDSノードと呼ばれるノード群を選ぶ。 DSノード群はDSコミッティーを形成する。 DSノードの選出はPoWに基づいており、これをと呼ぶ。 アルゴリズムを以下に示す。

PoW1_algorithm

他のノードよりも早くに対して有効なnonceを求めたノードは新しいDS-Blockのheaderを提案する。 先述の通り、DS-Blockはheader部分とsignature部分を持つが、その内header部分しか生成しないのだ。 ヘッダーはDSコミッティー内のノードにマルチキャストされる。 DSコミッティーは提案されたDS-Blockのheaderに関する合意形成を行いsignature部分をつくる。 2/3のDSノードがDS-Blockのheaderに対して署名をするとDSブロックチェーンにコミットされる。

ブートストラッピングフェーズが完了したのちは、どんなときもDSノードの数はあらかじめ決められた定数で一定である。 DS-Blockのマイニングに成功した最新のノードがDSコミッティーを形成する。

DS-Block間の平均時間をDS-epochと呼ぶ。 DS-epochは２つのブロックが競合する可能性を最小化するように決められる。 DS-epochの最初に新しいDSノードが参加し最も古いDSノードがDSコミッティーから抜ける。 この仕組みによってDSコミッティーの大きさは常にである。 最も新しいDSノードがリーダーになり、そのエポックの間コンセンサスプロトコルを取り仕切る（コンセンサスプロトコルについては第６章を参照）。 またこれによって、DSコミッティーのメンバーは厳密に順番がつけられている。

もしDSコミッティーのサイズが十分大きければ（例えば800以上）、コミッティーののノードの内せいぜい1/3は高い確率でビザンチンであることを示すことができる。

2) 衝突の解決

我々のコンセンサスプロトコル（第６章で詳述）はDSブロックチェーンにおいてフォークを認めない。 フォークは複数のノードがおおよそ同時にPoWを解いた時に起こりうる。 衝突を解決するために各DSノードは受け取ったヘッダーからnonceを取り出し昇順に並び替える。 番目のDSノードにとっての最も大きいnonceをとする。

DSコミッティーのリーダーは自分自身のheaderを提案し（リーダーが見た中で最も大きいnonce）、DS-Blockのheaderについてのコンセンサスプロトコルを実行する。 番目のDSノードは提案されたヘッダーのnonceがより大きいか等しければ同意する。 コンセンサスが得られるとDS-Blockの署名が作られ合意の結果勝者となったノードがリーダーになる。

3) シャード生成

DSコミッティーが選出されるとネットワークのシャーディングが始まる。 あるノードがコンセンサスプロトコルに参加するためにはを行なわなければいいけない。 シャーディングプロトコルは毎DS-epochの最初に行なわれる。 アルゴリズムは次の通り。

PoW2_algorithm

に対して計算された有効なnonce（とmixhash）はDSコミッティーにマルチキャストされる。 DSノードは各ノードからなる個のシャードを作るのに必要なだけ解を受け入れる。 DSコミッティーのリーダーが十分な量の解を受け取ると、に対して有効な解に関して合意形成を行うべくコンセンサスプロトコルを始める。 コンセンサスプロトコルの最後にリーダーはDSノードによって署名されたEC-Schnorrマルチシグネチャーを生成する。 次のステップに進むにはDSノードの2/3超が合意する必要がある。

シャーディングではノードをシャードに割り振るのに決定論的関数を用いる。 各ノードからなる個のシャードが必要だとしよう。 nonceは昇順に並び替えられ最初のノードが最初のシャードに割り振られ、次のノードが次のシャードに割り振られるというのを繰り返す。 各シャード内で最も大きいnonceを提案したマイナーがリーダーとなる。 シャード内のメンバーは厳密に順番がつけられている。

もしDSコミッティーのサイズが十分大きければ（例えば800以上）、コミッティーののノードの内せいぜい1/3は高い確率でビザンチンであることを示すことができる。

B. パブリックチャネル

DSノードはDSノードのアイデンティティや接続情報、各シャード内のノードリスト、トランザクションのシャーディングロジック（第５章Dで説明）といったパブリックチャネルに関する情報を流す。 パブリックチャネルは信用されておらず全てのノードがアクセスできると前提を置いている。 我々のブロードキャストではそうしたパブリックチャネルを実装している。

承認を求めてトランザクションを送るブロックチェーンのユーザーはシャーディングの情報をチェックして自分のトランザクションを処理しているシャードがどれか知ることができる。 パブリックチャネルで流れる情報はDSノードの2/3超に署名されることが期待されており、それはノードやユーザーなら誰でも検証することができる。

C. 新規ノードの参加

新しいノードがネットワークに参加するにはDSノードになるべくを解こうとするか、シャードメンバーになるべくを解こうとすれば良い。 そのためにやに求められるランダム性の情報をブロックチェーンから取得する必要がある。 その情報を取得すれば、新しいノードはDSコミッティーに解を提出することができる。

D. トランザクションのシャーディングと処理

第５章Aで説明したように、ネットワークシャーディングによって並列にトランザクションを処理することのできるシャードを作る。 このセクションではあるトランザクションがどのようにシャードに割り振られ処理されるのか説明する。 ここで、アカウントAからアカウントBに ZIL送金するトランザクションをと表す。

1) トランザクションのシャード割り振り

例えばのようなどんなトランザクションも一つのシャードで処理される。 シャードが個存在し、それぞれにからまでの番号が振られているとする。 トランザクションは送信者のアドレスの右側 ビットから特定されるシャードに割り振られる。この場合アカウントAのアドレスとなる。 アカウントアドレスは160ビットの整数なので、には次のような制約が存在する。

equation

実際は、は100より小さい。

シャードが決まると、トランザクションはそのシャード内のノードにマルチキャストされ、そこからさらにブロードキャストされる。 トランザクションがそのシャードのリーダーに届くと、リーダーはそのトランザクションをTX-Blockに入れてコンセンサスプロトコルを実行する。

二重支払い（リプレイアタック）は各トランザクションに含まれるnonceによって簡単に検知することができる。 先述の通り、各トランザクションにはnonceという送信者のアカウントから送られたトランザクションを数えるカウンターが含まれる。 トランザクションはトランザクションブロックチェーンに取り込まれると、アカウントの状態とグローバル状態においてnonceが更新される。 グローバル状態におけるnonce以下のnonceを含むトランザクションはマイナーによって弾かれる。

トランザクションは送信者のアカウントアドレスに基づいてシャードに割り振られることで、同一の送信者から送られたトランザクションは同じシャードで処理されるので、二重支払いを検知することができる。

2) トランザクション処理

コミッティー内の全てのノードはトランザクションを提案することができる。 これらのトランザクションはリーダーに集められどのドランザクションを次のTX-Blockに取り込むかに関するコンセンサスプロトコルを実行する。 各シャードによって提案されたブロックはマイクロブロック（タイプマーカー0x00）と呼ばれる。 マイクロブロックにはそのシャードの2/3超のノードによるEC-Shnorrマルチシグネチャーが含まれる。 このときリーダーはビットマップも作る。 もし番目のノードがそのTX-Blockヘッダーに署名していたらである。 TX-Blockについての同意が得られたら、リーダーはそのheaderとsignatureをいくつかのDSノードにマルチキャストする。 さらにDSノードはリーダーに届くようにDSコミッティー内でブロードキャストする。 TX-Blockのdata部分は非同期的に送られる。

DSコミッティーはシャードから送られた全てのブロックを集め、最終ブロックに関する合意を得るためにさらにコンセンサスプロトコルを実行する。 最終ブロックのタイプマーカーは0x01である。 最終ブロックにはDSコミッティー内の2/3超のノードから得られたEC-Schnorrマルチシグネチャーが含まれている。 DSコミッティーのリーダーはこの時ビットマップも作る。 もしDSコミッティーの番目のノードがそのTX-Blockヘッダーに署名していたらである。 その後、最終ブロックのheaderとsignatureは各シャードのいくつかのノードにマルチキャストされる。 TX-Blockの実際のdata部分はDSノードによっては送られない。

各シャード内で最終ブロックを処理するために次のようなステップで処理が進む。

  1. シャード内の各ノードはDSノードの公開鍵を使ってEC-Schorrマルチシグネチャーを検証する。 ビットマップで表されている2/3超のDSノードの公開鍵に対して署名が有効であると判明した場合、次のステップへ進む。
  2. 最終ブロックheaderに含まれる各トランザクションハッシュについて、それに対応するトランザクションデータが利用可能かチェックする。 もしそのトランザクションがそのノードが所属するシャードで提案されたトランザクションである場合、トランザクションデータのハッシュを最終ブロックheaderに含まれるハッシュと比較する。 もしそのトランザクションが別のシャードで提案されたものである場合、トランザクションデータは非同期的にシャード間で共有される。
  3. トランザクションデータが利用可能である場合、最終ブロックのdata部分が再構築されTX-Blockはローカルのトランザクションブロックチェーンに追加される。 それに応じてアカウント状態とグローバル状態も更新される。
  4. もしトランザクションデータが利用可能でない場合、ローカルのトランザクションデータがグローバル状態と一致するまでそのアカウントから送られる他のペンディングトランザクションを弾くために、ローカルでそのアカウントを一時的に無効化する。 そのようにはじかれたトランザクションはそれを送ってきたノードによって再送信されなければならない。

第6章　コンセンサス層

先述の通り、各シャードとDSコミッティーはマイクロブロックと最終ブロックについてのコンセンサスプロトコルを実行しなければならない。 この章では、各シャードとDSコミッティーで実行されるコンセンサスプロトコルを定義するコンセンサス層について説明する。 今後、シャードとDSコミッティーのことをまとめてコンセンサスグループと呼ぶ。

A. PBFT（Practical Byzantine Fault Tolerance）

Zilliqaのコンセンサスプロトコルの中核はCastroとLiskov[3]によって提案されたPBFTである。 しかし我々は[14][15]で提案されたようにPBFTでEC-Schnorrマルチシグネチャーを採用することでその効率性を向上させる。 EC-Schnorrマルチシグネチャーを用いることで標準的なケースにおいてコミュニケーションレイテンシーをからに下げ、署名サイズをからに減らすことができる。 ここではコンセンサスグループのサイズである。 これからPBFTの概要を説明する。

PBFTではコンセンサスグループ内の全てのノードは順番がつけられており、１つのプライマリーノード（つまりリーダー）とその他のバックアップノードから成る。PBFTの各ラウンドは次のような3つのフェーズで構成される。

  1. Pre-prepare phase
    このフェーズではグループが次に合意すべきレコード（我々の場合TX-Block）をリーダーがアナウンスする。
  2. Prepare phase
    pre-prepareメッセージを受け取ると、各ノードその正確性を検証し、prepareメッセージを他の全てのノードにマルチキャストする。
  3. Commit phase
    2/3超のprepareメッセージを受け取ると、ノードはcommitメッセージをグループにマルチキャストする。 最後に十分な数のノードが同じ決定をしたことを確認するために2/3超のcommitメッセージが来るまで待機する。 よって、全ての正直なノードは同じ有効なレコードを受け入れることになる。

PBFTは正しいリーダーが各フェーズを始め、十分な量の票数を得られた時にプロセスを進めることに頼っている。 リーダーがビザンチンの場合、コンセンサスプロトコル全体を停止させることができる。 この課題を解決すべく、PBFTはビザンチンなリーダーを別のリーダーに置き換えるようなビューチェンジプロトコルを持つ。 もしノードが制限時間内に進捗を得られなかった場合、独立してリーダーを変えたい旨を宣言することができる。 2/3超のノードがリーダーの不信任票を投じた場合、次のリーダーが予め決められた段取りで引き継ぐ。

各ノードがprepare/commitフェーズでマルチキャストするので、PBFTにおける通信複雑性は普通のケースだとである。

B. 効率性の向上

従来のPBFTはノード間の認証済み通信にMAC（Messeage Authentication Code）を用いる。 MACは各ノードのペアで共有されている秘密鍵が必要なため、コンセンサスグループのノードは同じレコードについて合意を得る時の通信複雑性はである。 2次の複雑性を持つので、コミッティーが20より多くのノードを持つ時PBFTは実用的でなくなる。

効率性を向上させるために、ByzCoin[15]から着想を得たアイデアを用いる。

  1. 通信複雑性をに効果的に減らすためにMACを電子署名に置き換える。
  2. 他のノードが合意について検証できるようにする典型的な方法は正直なノードから署名を集めて合意成果物に追加することだが、そうすると合意成果物のサイズがコンセンサスグループのサイズに対して線形に増えていく。 これを改善するために、EC-Schnorrマルチシグネチャーを採用して複数の署名をのサイズのマルチシグネチャーに集約する。

ところが、従来のEC-SchnorrマルチシグネチャーをPBFTで直接使うことはできない。 これは従来のEC-Schnorrでは全ての署名者があるメッセージに対して署名することを認め、全ての署名者が署名をした時のみ有効であると想定しているからだ。 PBFTではコンセンサスグループの2/3超のノードが署名すれば良い。 主な修正点の一つは、誰が署名プロセスに参加しているかを表すビットマップを保持するということだ。 番目のノードが署名に参加した場合、であり、それ以外は0である。 ビットマップはリーダーによって作られる。 ビットマップは署名の検証を行うために全ての検証者が使える。 詳細なプロトコルは付録Bで説明している。

C. Zilliqaコンセンサス

Zilliqでは基本的なコンセンサスプロトコルとしてPBFTを用い、その中で二度のEC-Schnorrマルチシグネチャーをprepareフェーズとcommitフェーズの代わりに採用している。 PBFTからの修正点は以下の通り。

  1. Pre-prepare phase
    PBFTと同様にリーダーはコンセンサスグループ内の全てのノードに（リーダーの署名つきの）TX-Blockを配布する。
  2. Prepare phase
    全ての正直なノードはTX-Blockが有効かどうかを確認し、リーダーは2/3超のノードから返事を集める。 これによってリーダーに提案されたTX-Blockが安全で過去のデータと一貫性のあるものであることが保証される。 署名はEC-Schnorrマルチシグネチャーを用いて生成される。 リーダーはTX-Blockに署名したノードのビットマップも作成する。
  3. Commit phase
    2/3超のノードがTX-Blockを検証したということを2/3超のノードが知っていることを保証するために、２回目のEC-Schnorrマルチシグネチャーを行う。 署名対象は前回生成されたマルチシグネチャーである。

３つのフェーズを経てリーダーに提案されたTX-Blockに関するコンセンサスに達する。

D. リーダーの変更

我々のコンセンサスプロトコルでは、リーダーが正直である場合、コンセンサスグループ内のノードを取り仕切って新しいトランザクションセットに関する合意を得る。 しかし、リーダーがビザンチンである場合、わざと正直なノードからのメッセージを遅らせるもしくは消すことができるしプロトコルを遅くすることができる。 そうした悪いリーダーに罰則を与えるために　定期的に各シャードやDSコミッティーのリーダーを変更する。 これによってビザンチンなリーダーがコンセンサスプロトコルを無限時間止めることはできなくなる。 全てのノードは順番がつけられているので、交代交代（ラウンドロビン）に次のリーダーが選ばれる。

実際、シャードのリーダーはマイクロブロック毎に変わり、DSコミッティーのリーダーは最終ブロック毎に変わる。 コンセンサスグループのサイズがnだとすると、DS-epoch内で最終ブロックは最大n個まで許容し、各最終ブロックはシャードにつき最大1個のマイクロブロックを集める。

第7章　スマートコントラクト層

Zilliqaには革新的な特別目的のスマートコントラクト記述言語とその実行環境が存在する。 それらは大規模かつ高効率な計算プラットフォームを提供するためにZilliqaアーキテクチャーを利用する。 この章ではデータフロープログラミングアーキテクチャーを採用したスマートコントラクト層について説明する。

A. データフローパラダイムを用いた計算シャーディング

Zilliqaのスマートコントラクト記述言語とその実行環境はZilliqaのネットワークシャーディングとトランザクションシャーディングのアーキテクチャーを利用するように設計されている。 シャードのアーキテクチャーは計算コストの高いタスクを効率的に行うのに適している。 キーとなるアイデアはシャードのようなネットワークの一部だけが計算を行う、というものだ。我々はこのアプローチを計算シャーディングと呼ぶ。

（イーサリアムのような）既存のスマートコントラクトアーキテクチャーと比較すると、Zilliqaの計算シャーディングはコントラクトを処理するのに全く異なるアプローチを取る。 イーサリアムでは計算の結果を検証しグローバル状態を更新するために、全てのフルノードが同じ計算を行う必要がある。 そうした冗長なプログラミングモデルは安全ではあるが、並列化が容易な大規模計算をするにはコストが高すぎる。 例えば、検索、並び替え、線形代数計算といったシンプルな計算からニューラルネットの学習、データマイニング、金融モデリングといった複雑なものが計算可能だ。

Zilliqaのシャーディングを用いた計算アプローチでは、チューリング完全ではないものの、アプリケーション数の増大に対してスケールするような独自のスマートコントラクト記述言語を採用している。 Zilliqaにおけるスマートコントラクト記述言語はデータフロープログラミング形式[16][17]に倣っている。 データフロー実行モデルではコントラクトは有効グラフで表せる。 グラフのノードは命令やオペレーションを表す。 ２つのノード間の弧は、１つ目のノードからの出力と２つ目のノードへの入力という風に、オペレーション間のデータ依存関係を表す。 ノードはその全ての入力が有効になるとアクティブ（実行可能）になる。 これは（イーサリアムで採用している）従来のフォンノイマン型実行モデルとは対照的だ。 ノイマン型モデルでは、ある命令が前もって実行できるかは関係なく、プログラムカウンターが到達した時のみ命令が実行される。

データフロープログラミングを採用する主なメリットは同時に複数の命令を実行することができることだ。 グラフにおける複数のノードが同時にアクティブになった時、並列に処理される。 こうしたシンプルなルールのおかげで大規模な並列計算を行うポテンシャルを持つ。 次の図のような単純なプログラムを具体例として説明する。 (a)には３つの命令が示されており(b)にはそのデータフロー変数が示されている。 ノイマン型モデルではまずAを計算し、次にB、Cと順番に計算するので、合計３回分の計算時間を要する。 このモデルではAとBが独立に計算できることを考慮していない。 データフロープログラミングでは、AとBを並列計算し、加算を行うノードはAとBが利用可能になるとすぐにアクティベートされる。

dataflow_programming

図１　データフロープログラムの例

Zilliqaのネットワークで実行する際には、データフロープログラムの各ノードが一つのシャードもしくはシャード内のさらに小さいノード群に割り当てられる。 MapReduce形式の計算では、あるノードはマッピングタスクを行う一方で別のノードはリデューサーとして各マッパーが行ったタスクを集約する。 我々のアーキテクチャーはMapReduce形式の計算には非常に適している。 データフロープログラムを実行するためにZilliqaのスマートコントラクト記述言語は次のような特徴を持つ。

  1. ブロックチェーン全体でグローバルに共有されている仮想メモリー領域上で実行する。
  2. 実行の間、仮想共有メモリ領域の中の中間セルをロックする。
  3. ブロックチェーンに取り込まれる処理を行っている間は中間結果を確認する。

B. スマートセキュリティバジェッティング

データフロー計算モデルによる並列計算のメリットとは別に、Zilliqaはさらにフレキシブルなセキュリティバジェッティング機能を提供する。 コンセンサスプロセス上のオーバーレイからブロックチェーンネットワーク内の計算リソースをシャーディングすることでこの機能を使うことができる。 計算シャーディングによってZilliqaもしくはZilliqa上で走っているアプリケーションのユーザーは各サブタスクの計算を行うコンセンサスグループサイズを指定することができる。 各コンセンサスグループ内のノードは同じサブタスクを計算し結果を出力するが、このときユーザーは結果を受け入れる条件を指定することができる。 例えば、コンセンサスグループ内の全てのノードが同じ結果を出力するとか、3/4が同じ結果を出力するという風に。

Zilliqa上で動いているアプリケーションのユーザーは計算と安全性にそれぞれいくらまで金額をかけたいのか予算を指定することができる。 例えば、特定のディープラーニングのアプリケーションを実行するユーザーは多くのノードに同じタスクを計算させるよりも、より多くのニューラルネットワークのタスクを実行するのにガス手数料を払うかもしれない。 その場合、ユーザーは各ニューラルネットワークの計算を行う、より小さなコンセンサスグループを指定することができる。 一方でかなりの正確さを要する複雑な金融モデリングアルゴリズムの場合は、より大きなコンセンサスグループに重要な部分を計算させて潜在的な結果の改ざんに対する耐性を持たせるかもしれない。

C. スケーラブルなアプリケーション例

Zilliqaはデータマイニング、機械学習、金融モデリングといった様々な領域でスケーラブルな計算を行うためのプラットフォームを提供する。 チューリング完全なプログラムの効率的なシャーディングをサポートするのは非常に難しい上、イーサリアムのようにチューリング完全なスマートコントラクトをサポートするパブリックブロックチェーンは存在するのでZilliqaは今日満たされていない要求を持つ特定のアプリケーションに集中する。

  1. 並列処理可能な計算
    大規模なデータに対する科学計算は大量の分散計算能力を必要とする典型例だ。 さらに、こうした計算のほとんどは並列処理可能で、例えば大数を扱う線形代数計算、大量のデータ検索、大規模なデータを扱うシミュレーションなどがその例だ。 Zilliqaを用いるとそうした計算を廉価に高速で行うことができる。 また、計算シャーディングやセキュリティバジェッティングにおいて適切なインセンティブを与えることでZilliqaはそうした高負荷な計算を即座に行うことのできる高信頼のリソースとなるだろう。
  2. ニューラルネットの学習
    機械学習（特にディープラーニング）の人気と活用例が高まりつつある中で大規模なデータセットを用いてディープラーニングのモデルで学習を行えるインフラを提供することはマストだ。 大規模なデータセットに対する学習はモデルの正確性にとって重要であることはよく知られている。 Zilliqaの計算シャーディングとデータフロー言語は機械学習アプリケーションを構築するのに便利だ。 勾配計算、活性化関数、損失計算などの多様な計算をシャードに独立して行わせることでテンソルフローのようなツールを動かすインフラとして役立つだろう。
  3. 複雑で高い精度が求められるアプリケーション
    先述のようなアプリケーションとは異なり、金融モデルの計算のようなアプリケーションは高い正確性を必要とする。 少しでも計算がずれていると投資で大損失を被るかもしれない。 そうしたアプリケーションは大規模なコンセンサスグループに計算結果を互いにクロスチェックさせることができる。 金融モデリングアルゴリズムのような計算タスクをZilliqaのようなパブリックプラットフォームに行わせることのキーとなる課題はデータプライバシーと知的財産の問題だ。 我々はそうした計算の内、ある程度は効率と安全性を求めてZilliqaが使われると予想している。 また、将来的な研究開発によってデータプライバシーや知的財産の保護が強化されていくだろう。

第８章　インセンティブ層

A. トークン供給

Zilliqaのトークン供給は有限であり、210億ZILの供給を持つ。 小単位はZILである。 各最終TX-Blockが生成されると新しいトークンが生成されブロック報酬が付与される。 ブロック報酬は10年間与えられ、時間とともに減少していく。 最初の４年間で約８０％のトークンをマイニングし、残りの２０％を６年間でマイニングするつもりだ。 ブロック報酬が急激に減少しないという意味でトークンの新規発行は「滑らか」だ。ブロック報酬が滑らかな減少するので、 ネットワークのハッシュレートは報酬が減るにつれて安定するだろう。

１０年後、ネットワークのノード数という意味でもトランザクションを実行するユーザー数という意味でも大きくスケールしているだろう。 その時までに、報酬として新規のトークンを発行することなく、ネットワークが持続するように、トランザクション手数料が安定しているだろう。

B. マイナー報酬

マイナーはトランザクションに関する合意形成を行い、それを処理し、スマートコントラクトの計算を行い、グローバル状態を更新する。 マイナーは各トランザクションの送信者にガス手数料を払ってもらうことでインセンティブを得る。 ここで、最終TX-Blockは各シャードからせいぜい１つのマイクロブロックを集めることを思い出して欲しい。 各マイクロTX-Blockにはブロック内の全てのトランザクション手数料であるgas usedフィールドが存在する。 各最終TX-Blockも同様にgas usedフィールドを持つが、これは各マイクロTX-Blockのgas usedの合計である。 TX-Blockが提案されるとgas usedとブロック報酬はマイクロブロックを提案した各シャードのリーダーとDSコミッティーのリーダーに均等に分けられる。 均等に分けられない時は、ややDSコミッティーのリーダーに傾斜をつける。 もし報酬がでその報酬のステークホルダーがだとすると各シャードのリーダーはの報酬を受け取り、DSコミッティーのリーダーはの報酬を受け取る。

各シャードのリーダーは新しいマイクロブロックが提案されると毎回変わるので、シャード内の全てのメンバーが報酬を得ることができる。 同様にDSコミッティーのリーダーも最終ブロックが提案される毎に変わるのでDSコミッティー内の全てのメンバーが報酬を受け取ることができる。

第９章　関連研究

ZilliqaはBitcoin-NG[18]、collective signing（CoSi）[14]、ByzCoin[15]、Elastico[19]、OmniLedger[20]のアイデアに基づいて開発されている。

Bitcoin-NGはビットコインの内部でリーダー選出とブロック提案を分離することを最初に提案した。 まず、リーダーはキーブロックをマイニングすることで選出され、リーダーは10分のブロック間隔の間にたくさんマイクロブロックを生成することができる。 このアイデアはByzCoin[15]でさらに応用されている。

ビットコインのようなシステムにおけるネットワークシャーディングとトランザクションシャーディングのアイデアは[19]で最初に提案された。 しかし、ネットワーク・トランザクションシャーディングだけではスケーラビリティ問題を解決することはできない。 これは、各シャードがTX-Blockにに署名する必要があり、署名者の数に応じて線形に署名の数が増えるためである。 結局、ブロックサイズが大きくなり、ブロードキャストもしくはマルチキャストをする時にボトルネックになるのだ。

マルチシグネチャー[11]がこの問題を解決する。 CoSi[14]はcollective signingのためのプロトコルを設計するのにEC-Schnorrマルチシグネチャーを採用している。 CoSiはビザンチンノードが存在するようなパブリックブロックチェーンよりも悪意を持った人が少ない環境で作動するよう提案されている。 我々はCoSiのスキームを大きく改善することで安全なスキームを開発しZilliqaに応用した。

既存のブロックチェーンプロトコルの本質的なスケーラビリティ問題を回避すべく、他にもいくつかの手法が提案された。 例えば、元々のブロックチェーンプロトコルのパラメーターを調節したり（例えばブロックサイズを増やす）、計算をオフチェーンに移したり（例えばマイクロペイメントチャネルやライトニングネットワーク）、ブロックチェーンに階層構造を作る（サイドチェーン）といった手法である。 これらはどれもブロックチェーンプロトコル自体を直接スケーラブルにするものではない。 Zilliqaはスケーラビリティ問題の本丸に焦点を当てた。ブロックチェーンそのものである。

Zilliqaはいくつか安全性とパフォーマンスの最適化を行いByzCoinとOmniLedgerを拡張したものと見ることができる。 ZilliqaはByzCoinやOmniLedgerでは使用できなかったスマートコントラクトプラットフォームも提案している。

Zilliqaのスマートコントラクトプラットフォームはイーサリアムと比べると異なるアプローチを採用している。 ZilliqaのスマートコントラクトプラットフォームはZilliqaのシャーディングアーキテクチャーを利用し、データフロープログラミングに基づく。 データフロープログラムのメリットは多い。 元々並列処理に適していること、計算が正しいかどうかを判断しやすいこと、関数やプログラムを構成しやすいことなどだ。

第１０章　将来的な研究の方向性

以下、Zilliqaを改善するためにこれから行おうとしている研究について述べる。

  • 状態シャーディング
    Zilliqaのユーザーベースが増え、トランザクションスループットが高まると、次のような課題が発生するだろう。 それはグローバル状態を更新するブロックが継続して生成されるのをどのように効率よく扱うかだ。 これは文字通り状態シャーディングと呼ばれる。 状態シャーディングによってフルノードは全てのブロックとトランザクションを保存したり受け取らなくてもよくなる。 こうしてノードにかかるストーレジと通信の負荷が軽減されるので、スループットがさらに向上する。 しかし、安全で効率的な状態シャーディングを設計するのは簡単なことではない。 というのも、状態シャーディングに必要なシャード間通信を実装するのは、それから得られるパフォーマンスの向上を上回るくらい大変なのだ。 そうした複雑な追加実装を行うためにもっと研究する必要がある。
  • Secure Proof-of-Stake（SPoS）
    我々が知る限り安全なPoSスキームを提案している論文は存在しないので、我々はZilliqaのブロック生成においてPoWスキームを用いている。 しかし、PoSをコンセンサスアルゴリズムに採用することで得られるパフォーマンス向上を考えると、Zilliqaに適した安全で効率的なPoSスキームを求めてPoSの枠組みをもっと調査する価値はある。
  • ストレージ剪定
    我々はストレージ要件を下げ、新しいノードがプロセスに参加しやすくするために、ブロックチェーンに保存された過去のブロックを安全に剪定する方法を模索している。 可能な解決策としてブロックとトランザクションの圧縮を行うマルチグレードストレージを考えるかもしれない。
  • クロスチェーンサポート
    Zilliqaは他のブロックチェーンを補い、エンドユーザーに幅広いプラットフォームの選択肢を提供する健全なエコシステムを築こうとしている。 それを達成するためにクロスチェーン通信をサポートしクロスチェーンアプリケーションを潜在的に可能にする技術的解決策を検討するだろう。
  • プライバシーを保護する計算
    特に金融モデリングといったいくつかのアプリケーションではZilliqaを実行する際にプライバシーと知的財産を強固に保護することが望ましい。 暗号化されたデータへのアクセスパターンを秘匿するOblivious RAM[21]、プログラムへの入力を秘匿するZK-SNARK[22]、コントラクトのビジネスロジックを秘匿するPFE（Private Function Evaluation）に基づく解決策も調査している。

第１１章　結論

このホワイトペーパーでは、マイニングネットワークがトランザクションを並列に処理し高いスループットに到達することを可能にするZilliqaのシャーディングアーキテクチャーについて説明した。 また、そのシャーディングアーキテクチャーを利用し、データフロープログラミングに則ったユニークなスマートコントラクトプラットフォームをZilliqaは備えている。 新しいスマートコントラクト記述言語は効率的に計算コストの高いタスクを処理するのに非常に適している。

参考文献

  1. S. Nakamoto, “Bitcoin: A peer-to-peer electronic cash system, http://bitcoin.org/bitcoin.pdf ,” 2008.
  2. E. Foundation, “Ethereum’s white paper,” https://github.com/ethereum/wiki/wiki/White-Paper, 2014.
  3. M. Castro and B. Liskov, “Practical Byzantine Fault Tolerance,” in Proceedings of the Third Symposium on Operating Systems Design and Implementation, ser. OSDI ’99. Berkeley, CA, USA: USENIX Association, 1999, pp. 173–186.
  4. E. Heilman, A. Kendler, A. Zohar, and S. Goldberg, “Eclipse Attacks on Bitcoin’s Peer-to-Peer Network,” in 24th USENIX Security Symposium (USENIX Security 15). Washington, D.C.: USENIX Association, 2015, pp. 129–144.
  5. S. Gilbert and N. Lynch, “Brewer’s Conjecture and the Feasibility of Consistent Available Partition Tolerant Web Services,” in In ACM SIGACT News, 2002, p. 2002.
  6. NIST, “Sha-3 standard: Permutation-based hash and extendable-output functions,” 2015.
  7. B. Guido, D. Joan, P. Michael, and V. A. Gilles, “The Keccak Reference,” 2011.
  8. C. Schnorr, “Efficient signature generation by smart cards,” J. Cryptology, vol. 4, no. 3, pp. 161–174, 1991.
  9. C. Research, “SEC 2: Recommended Elliptic Curve Domain Parameters,” 2000. [Online]. Available: http://www.secg.org/download/aid-386/sec2-final.pdf
  10. A. Poelstra, “Schnorr Signatures are Non-Malleable in the Random Oracle Model,” 2014.
  11. S. Micali, K. Ohta, and L. Reyzin, “Accountable-subgroup Multisignatures: Extended Abstract,” in Proceedings of the 8th ACM Conference on Computer and Communications Security, ser. CCS ’01. New York, NY, USA: ACM, 2001, pp. 245–254.
  12. G. Wood, “Ethereum: A secure decentralised generalised transaction ledger,” http://gavwood.com/paper.pdf, 2014.
  13. “Ethash,” https://github.com/ethereum/wiki/wiki/Ethash, Accessed on June 27, 2017., version 23.
  14. E. Syta, I. Tamas, D. Visher, D. I. Wolinsky, P. Jovanovic, L. Gasser, N. Gailly, I. Khoffi, and B. Ford, “Keeping authorities ”honest or bust” with decentralized witness cosigning,” in IEEE Symposium on Security and Privacy, SP 2016, San Jose, CA, USA, May 22-26, 2016, 2016, pp. 526–545.
  15. E. Kokoris-Kogias, P. Jovanovic, N. Gailly, I. Khoffi, L. Gasser, and B. Ford, “Enhancing Bitcoin Security and Performance with Strong Consistency via Collective Signing,” in 25th USENIX Security Symposium, USENIX Security 16, Austin, TX, USA, August 10-12, 2016., 2016, pp. 279–296.
  16. Arvind and D. E. Culler, “Annual review of computer science vol. 1, 1986,” J. F. Traub, B. J. Grosz, B. W. Lampson, and N. J. Nilsson, Eds. Palo Alto, CA, USA: Annual Reviews Inc., 1986, ch. Dataflow Architectures, pp. 225–253.
  17. A. L. Davis and R. M. Keller, “Data flow program graphs,” Computer, vol. 15, no. 2, pp. 26–41, Feb. 1982.
  18. I. Eyal, A. E. Gencer, E. G. Sirer, and R. van Renesse, “Bitcoinng: A scalable blockchain protocol,” in 13th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2016, Santa Clara, CA, USA, March 16-18, 2016, 2016, pp. 45–59.
  19. L. Luu, V. Narayanan, C. Zheng, K. Baweja, S. Gilbert, and P. Saxena, “A secure sharding protocol for open blockchains,” in Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, October 24-28, 2016, 2016, pp. 17–30.
  20. E. Kokoris-Kogias, P. Jovanovic, L. Gasser, N. Gailly, and B. Ford, “Omniledger: A secure, scale-out, decentralized ledger,” IACR Cryptology ePrint Archive, vol. 2017, p. 406, 2017.
  21. E. Stefanov, M. van Dijk, E. Shi, C. W. Fletcher, L. Ren, X. Yu, and S. Devadas, “Path ORAM: An Extremely Simple Oblivious RAM Protocol,” in 2013 ACM SIGSAC Conference on Computer and Communications Security, CCS’13, Berlin, Germany, November 4-8, 2013, 2013, pp. 299–310.
  22. E. Ben-Sasson, A. Chiesa, E. Tromer, and M. Virza, “Succinct NonInteractive Zero Knowledge for a von Neumann Architecture,” in Proceedings of the 23rd USENIX Security Symposium, San Diego, CA, USA, August 20-22, 2014., 2014, pp. 781–796.
  23. P. Mohassel, S. S. Sadeghian, and N. P. Smart, “Actively Secure Private Function Evaluation,” in Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 7-11, 2014, Proceedings, Part II, 2014, pp. 486–505.
  24. BSI, “Technical Guideline TR-03111 Elliptic Curve Cryptography,” Federal Office for Information Security, Tech. Rep., 01 2012.
  25. D. J. Bernstein, “Multi-user Schnorr Security, Revisited,” IACR Cryptology ePrint Archive, vol. 2015, p. 996, 2015. [Online]. Available: http://eprint.iacr.org/2015/996
  26. M. Michels and P. Horster, “On the Risk of Disruption in Several Multiparty Signature Schemes,” in Proceedings of the International Conference on the Theory and Applications of Cryptology and Information Security: Advances in Cryptology, ser. ASIACRYPT ’96. London, UK, UK: Springer-Verlag, 1996, pp. 334–345.

付録A　シュノア電子署名アルゴリズム

A. EC-Schnorr（シングルサイナー）スキーム

EC-Schnorrは離散対数の計算をするのが困難な群の上で機能する[8][24][25]。 Zilliqaではsecp256k1曲線上に定義された楕円曲線群を用いる。 曲線群を定義するパラメーターセットをと表す。 ここで、は素体を指定する素数、は曲線の基準点、（素数）はの位数である。 EC-Schnorrは暗号学的ハッシュ関数も必要で、我々はSHA3-256[6]を用いている。

EC-Schnorrはこれから説明する３つのアルゴリズム、、、で構成される。 以下のアルゴリズムでは、任意のスカラーと点に対してスカラー倍の演算をと表記する。


  1. 曲線のパラメータセットを入力にとり、公開鍵（）と秘密鍵（）のペアを生成する。

    KeyGen


  2. 署名者によって実行される。曲線パラメータセット、公開鍵と秘密鍵のペア、署名するメッセージを入力にとり、署名を返す。

    Sign


  3. 署名の有効性を確認したい検証者によって実行される。曲線パラメーターセット、署名、公開鍵、メッセージ署名を入力に取り、署名が有効なら1、無効なら0を返す。

    Verify

B. EC-Schnorrマルチシグネチャースキーム

1) 設定と前提

EC-Schnorrはマルチシグネチャースキームとして使うこともできる[11]。 マルチシグネチャースキームでは、人の署名者とアグリゲーターと検証者が存在する。 署名者はメッセージに署名する。 アグリゲーターはファシリテーターの役割を持ち、各署名者から送られてきた署名を集める。 検証者は集められた署名を検証する。 アグリゲーターと検証者は同じエンティティであっても良い。

各署名者はシングルサイナースキームのEC-Schnorr鍵ペアを持つ。 公開鍵をと表記する。 また、ある公開メッセージは全てのエンティティが知っているとする。 その公開メッセージはアプリケーションシナリオに特有で次のような形式をとるかもしれない。 「I know the private key for my public key for the session id: XXXX.」。 このメッセージの目的はある種の攻撃[26] を根絶するためのものだ。

2) マルチシグネチャープロトコル

マルチシグネチャーは署名者、アグリゲーター、検証者の間で相互に行われるプロトコルだ（スキームの概要は下図を見て欲しい）。 プロトコルは６つのステップで構成される。

  1. (One-Time) Identity Setup
    このステップは各参加者と検証者の間で行われる。 プロトコルの最初に各署名者は別の署名プロトコルに参加していなければメッセージについてEC-Schnorr署名を生成する。 は検証者にを送る。 検証者は次のようなチェックを行う。
    a) を確認。 確認できなければ検証を中断する。
    b) 各がとに対して有効なEC-Schnorr署名であることをで確認。 いずれかの署名に対して0を返した場合、検証を中断する。 全ての署名が有効であれば次のステップへ進む。
    もし検証者がのの内、どれかの署名を受け取らなかった場合も中断する。 から署名を受け取ったかどうかを確認するために、ビットマップを用いる。 アイデンティティセットアップは一度だけ実行されるプロセスである。 セットアップが成功した時のみ、次のステップを始めることができる。
  2. Commitment Generation
    各署名者は乱数を生成し、を計算する。 ここで、は楕円曲線の基準点で、はの位数である。 はアグリゲーターにを送る。
  3. Challenge Generation
    まずアグリゲーターは集約キーを計算する。 また、前回のステップで受け取ったからを計算する。 次にを計算して各にを送る。
  4. Response Generation
    各署名者は前のステップで受け取ったの整合性をチェックする。 具体的にはを再計算して受け取ったと一致するか確認する。 合わなければ中断する。 合っていればを計算し、アグリゲーターにを送る。
  5. Response Aggregation
    アグリゲーターは集約されたレスポンスを計算し、集約されたシグネチャーを作る。 そして検証者にを送る。
  6. Signature Verification
    検証者は署名が有効かどうか確認する。 次の手順を踏む。
    a) の公開鍵を集約してとする。
    b) がと公開鍵に対して有効なEC-Schnorr署名であるか確認する。 を計算して出力を返す。
    EC-Schnorr multisignature

    図２　EC-Schnorrを用いたマルチシグネチャー

付録B　PBFTにおけるマルチシグネチャー

付録Aで説明したような従来のEC-Schnorrマルチシグネチャープロトコルは参加者全員の署名が必要だ。 よって、少なくとも2/3超のノードがメッセージに署名すれば良いPBFTで、EC-Schnorrマルチシグネチャーを直接使うことはできない。 この章では[14]に着想を得て行ったプロトコルの微調整について説明する。 プロトコルへの参加状況を記録する２つのビットマップを用いる。 修正されたプロトコルの概要は下図を参照。

  1. (One-Time) Identity Setup
    このステップは付録Aで説明した従来のEC-Schnorrマルチシグネチャープロトコルを全く同じだ。 セットアップが成功した時のみ次のステップに移る。
  2. Commitment Generation
    このステップは従来のEC-Schnorrマルチシグネチャープロトコルとほとんど同じだ。 唯一異なるのは、各参加者がアグリゲーターに対してと一緒に公開鍵も送るということだ。
  3. Challenge Generation
    このステップでは、アグリゲーターがまずビットマップを0で初期化する。 前のステップでを受け取るたびに、アグリゲーターはを1にする。 アグリゲーターはネットワークの遅延に対処するために一定の時間待機し、次の計算を行う。
    a) 集約キーを計算する。 つまり、受け取ったに対応する公開鍵を足していく。
    b) を計算する。
    c) を計算して各にを送る。
  4. Response Generation
    このステップは従来のEC-Schnorrマルチシグネチャープロトコルとほとんど同じである。 唯一の違いは各参加者がアグリゲーターに対してと一緒に公開鍵も送るということだ。
  5. Response Aggregation
    このステップではアグリゲーターがまずビットマップを0で初期化する。 前のステップでを受け取るたびに、を計算して、が受け取ったと等しいことを確認して、が有効かチェックする。 もし有効ならを1にする。 このステップによって任意のを送ってDoS攻撃を行う参加者を検知することができる。 アグリゲーターはネットワークの遅延に対処するために一定の時間待機し、次の計算を行う。
    a) もしビットマップとが等しければ各参加者がcommitment generationステップとresponse generationステップの両方でアグリゲーターにメッセージを送ったことになる。 アグリゲーターは集約されたレスポンスを計算して、集約された署名を作る。 検証者にを送る。
    b) もし２つのビットマップが異なればある参加者はを送ったが、を送らなかったことを意味する。 アグリゲーターはとの差集合、つまり、を受け取ったが、を受け取らなかった公開鍵セットを計算する。 この公開鍵セットはブラックリストに載る。 アグリゲーターはを再び0で初期化して、にはとの共通集合を保存する。 challenge generationステップに戻って同じ手順を踏む。
  6. Signature Verification
    検証者はまず2/3超の参加者が署名したかを確認して、マルチシグネチャーが有効かどうか確認する。 あとは従来のEC-Schnorrマルチシグネチャーと同じだ。
    EC-Schnorr multisignature in PBFT

    図３　PBFTにおけるEC-Schnorrを用いたマルチシグネチャー

Tip us!

エンジニアチームのブログを書くモチベーションが上がります 💪

address

0xd6d478dCe4585a394834690158cf83581223C08f