翻訳: The ZILLIQA Technical Whitepaper

Abstract

既存の暗号通貨及びスマートコントラクトプラットフォームはスケーラビリティの問題を抱えている。すなはち、1秒間に処理できるトランザクションの数が制限されており、通常 10 未満であることが知られている。パブリック暗号通貨およびスマートコントラクトプラットフォームを利用するアプリケーションの数が増えるにつれ、数百から数千 Tx/s オーダーの高いトランザクションレートを処理することに対する需要が高まっている。

この研究ではトランザクションレートがスケールするように設計された新しいブロックチェーンプラットフォームである ZILLIQA を紹介する。ZILLIQA の採掘者の数が増えるにつれてそのトランザクションレートは増加すると予想される。現在の Ethereum のネットワークサイズは 30,000 の採掘者だが、ZILLIQA は Ethereum のトランザクションレートの約 1,000 倍の処理を見込んでいる。ZILLIQA の設計の礎は sharding - 採掘ネットワークを、トランザクションを並行して処理できる小さい shard に分割するというアイディアである。

さらに ZILLIQA では大規模で高効率の計算プラットフォームを提供するために基盤のアーキテクチャを活用して、革新的な特殊用途のスマートコントラクト言語と実行環境を提案している。ZILLIQA のスマートコントラクト言語は容易に並列でき大規模な計算を実行するのに理想的なデータフロープログラミングスタイルに基づいている。例として、検索、ソート、線形代数計算などの単純な計算から、ニューラルネットワークのトレーニング、データマイニング、金融モデリング、科学計算などのより複雑な計算、そして一般的な MapReduce タスクを含んでいます。

I. Introduction

暗号通貨とスマートコントラクトプラットフォームは共有の計算リソースになりつつあります。これらのプラットフォームは何千もの個別のコンピュータを同期させる新世代のコンピュータと見なすことができます。しかし、既存の暗号通過およびスマートコントラクトプラットフォームはスケーリングにおける制限が広く認識されている。Bitcoin[1], Ethereum[2] および関連する暗号通貨の平均トランザクションレート (Tx/s) は 1 秒あたり 10 (通常 3～7) トランザクションに制限されている。パブリック暗号通貨およびスマートコントラクトプラットフォームを利用す®アプリケーションの数が増えるにつれて、数百 Tx/s オーダーの高いトランザクションレートを処理することに対する需要が増大している。世界規模のペイメントネットワークでは、数万 Tx/s のキャパシティが必要となるだろう。その規模で処理できる分散型のオープンブロックチェーンプラットフォームを構築できるだろうか?

既存のプロトコルをスケールアップする制限はやや根本的である - それらはコンセンサスとネットワークプロトコルの設計を根源としている。したがって、例えば Bitcoin や Ethereum などの既存のプロトコルパラメータ (例えばブロックサイズやブロックレート) を再設計してもある程度高速化される可能性があるが、数千 Tx/s の処理が必要なアプリケーションをサポートするには基礎プロトコルのゼロからの再考が必要である。

我々は ZILLIQA、トランザクションレートを調整するように設計された新しいブロックチェーンプラットフォームを紹介する。ZILLIQA は採掘者の数が増えるにつれてそのトランザクションレートも上がると想定している。具体的には ZILLIQA のデザインではネットワークに数百のノードが追加されるごとにトランザクションレートがおよそ 2 倍となる。これを書いている時点で Ethereum の採掘ネットワークは 30,000 ノードを超えている。現在の Ethereum のキャパシティで、ZILLIQA は Ethereum の約 1000 倍の処理を予想している。

ZILLIQA はゼロからの再設計であり 2 年以上にわたり研究開発されている。ZILLIQA の設計の礎は sharding - 採掘ネットワークを、それぞれトランザクションを並行に処理できる shard と呼ばれる小さなコンセンサスグループに分割するというアイディアである。ZILLIQA は、採掘ネットワークが 8000 の採掘者であると仮定すると、trusted なコーディネータが必要のない decentralized 方式で、採掘者を自動的に 800×10 個のサブネットワークを作成する。ここで、1 つのサブネットワークが 1 回のエポックで (例えば) 100 トランザクションのセットに合意することができる場合、10 のサブネットワークは合計で 1000 トランザクションに合意することができる。安全に集約するためのカギは、サブネットワークが二重支払なしに (重複することなく) 異なるトランザクションを処理することを保証することです。

想定は既存のブロックチェーンベースのソリューションと似ている。我々は、採掘ネットワークがネットワーク全体の数分の一 (<1/4) となる総計算能力を持つわずかな悪意ノード/アイデンティティを持つことを想定している。これは標準の proof-of-work スキームに基づいているが、新しい 2 層ブロックチェーン構造を持っている。それは shard を処理するために高度に最適化されたコンセンサスアルゴリズムを特徴とする。

さらに ZILLIQA は大規模で高効率な計算プラットフォームを提供ために基礎となるアーキテクチャを活用し、革新的な特殊用途のスマートコントラクト言語と実行環境を備えている。ZILLIQA のスマートコントラクト言語はスマートコントラクトを有効グラフとして表すことができるデータフロープログラミングスタイルに基づいている。グラフ内のノードは操作または関数を表し、2 つのノード間の円弧は最初のノードの出力と次のノードの入力を表している。すべての入力が有効になるとすぐにノードは活性化 (または操作可能) となるため、データフローコントラクトは本質的に並列であり、ZILLIQA のような分散システムに適している。

shard 化アーキテクチャは大規模な計算資源を簡単に並列化実行するのに理想的である。例としては、検索、ソート、線形代数計算などの単純計算から、ニューラルネットワークの訓練、データマイニング、金融モデリング、科学計算などのようなより複雑な計算、そして一般的には MapReduce タスクなどがある。

この文書は ZILLIQA ブロックチェーンプロトコルの技術設計の概要を説明する。ZILLIQA は概念的にクリーンでモジュール式の新しいデザインを採用している: 暗号化層 (セクション III)、データ層 (セクション IV)、ネットワーク層 (セクション V)、スマートコントラクト層 (セクション VII)、インセンティブ層 (セクション VIII) の 6 層が存在する。様々なレイヤーを提示する前に、まずセクション II においてシステム設定や基礎となる前提、および脅威モデルについて説明する。

II. System Setting and Assumptions

ZILLIQA のエンティティ: ZILLIQA にはユーザと採掘者という 2 つの主要なエンティティが存在する。ユーザは ZILLIQA のインフラストラクチャを利用して資金を送金したりスマートコントラクトを実行する外部エンティティである。採掘者は ZILLIQA のコンセンサスプロトコルを実行し、それらにサービスに対する報酬を得るネットワーク内のノードである。このホワイトペーパーにおいて以後は採掘者とノードを同じ意味で使用する。

ZILLIQA の採掘ネットワークはさらに shard と呼ばれるいくつかのネットワークに分割されている。ある採掘者は DS ノードと呼ばれるいくつかの採掘者によって shard に割り当てられる。この DS ノードのセットは DS committee とも呼ばれる。それぞれの shard と DS committee にはリーダーが存在する。リーダーは ZILLIQA のコンセンサスプロとkるとネットワーク全体の機能において重要な役割を果たす。

各ユーザはデジタル署名方式のために公開鍵と秘密鍵のペアを持ち、ネットワーク内の各採掘者は関連付けられた IP アドレスと ID として機能する公開鍵を持つ。

組み込みトークン: ZILLIQA には Zillings または ZIL と呼ばれる組み込みトークンが存在する。Zillings はトランザクション処理の支払いやスマートコントラクトの実行にプラットフォームを使用する権利をユーザに付与する。このホワイトペーパーでは amount, value, balance または payment に関する言及は ZIL 換算であると想定すべきである。

敵対的モデル: 我々は、任意の時点での採掘ネットワークが最大でも全ネットワークの \(f \lt \frac{n}{4}\) の総計算能力を持つビザンティンノード/アイデンティティを有すると仮定している。ここで \(0 \le f \lt 1\) であり \(n\) なネットワークの合計サイズである。係数 \(\frac{1}{4}\) は、合理的な定数パラメータをもたらすように選択された \(\frac{1}{3}\) から制限された任意の定数である。さらに、我々は、正常なノードがプロトコルの実行中に信頼できると仮定し、障害が発生したノードや切断されたノードはビザンティン比率でカウントする。

ビザンティンノードはプロトコルに違反してメッセージを削除または改ざんし、正常なノードに不正なメッセージを送信することができる。さらに、すべてのビザンティンノードは共謀することができる。我々はビザンティン敵対者の層計算能力が依然として確立的多項式時間敵対者 (probabilistic polynomial-time adversaries) の標準的な暗号の仮定に限定されると想定する。

しかし、我々は正常なノードからのメッセージは (ネットワーク分断が存在しない場合には) 一定の境界 \(\delta\) 後に正しい宛先に配信されると想定しているが、\(\delta\) は時間変化することができる。境界 \(\delta\) は死活を確保するために使用されるが、安全性には使用されない[3]。このようなタイミング及び接続性の想定が満たされない場合、ビザンティンノードがメッセージに深刻な遅延をもたらす (計算能力のゲインをシミュレートして)、またはネットワークを "eclipse" 悪化させられるようになる可能性がある。CAP 定理によって規定されているように、ネットワーク分断の場合には一貫性と可用性のどちらかしか選択することができない[5]。ZILLIQA では可用性を犠牲にして一貫性を保つことを選択した。

III. Cryptographic Layer

暗号化レイヤーは ZILLIQA で使用される暗号化プリミティブを定義する。他の幾つかのブロックチェーンプラットフォームと同様に、ZILLIQA はデジタル署名のために楕円曲線暗号と proof-of-work (PoW) のためのメモリハードハッシュ関数に依存している。

このホワイトペーパーでは SHA3[6] ハッシュ関数を使用して設計を表現している。SHA3 は元々 Keccak[7] に基づいており、様々なブロックチェーンプラットフォーム、特に Ethereum で広く使用されている。近い将来、我々は他のプラットフォームとのより良い相互運用を可能にするため Keccak に切り替えるかもしれない。

A. Schnorr Signature

ZILLIQA は基本の署名アルゴリズムに Elliptic Curve Based Schnorr Signature Algorithm (EC-Schnorr)[8] を採用している。我々は secp256k1 曲線[9]でこのスキームを具体化する。同じ曲線が現在 Bitcoin と Ethereum で使用されているが、ECDSA と呼ばれる署名アルゴリズムが異なる。ECDSA ではなく ECSchnorr を選択することには以下で説明する幾つかの利点が存在する。

1) 非順応性 (non-malleability): ざっくり言えば、非順応性とは、秘密鍵を使用してメッセージ上に作成された署名のセットが与えられたとき、攻撃者が、公開鍵に対応する有効な同じメッセージに対して新しい署名を作成することが困難であることを意味する。順応性のある ECDSA とは異なり、EC-Schnorr は非順応性であることが証明されている[10]。

2) マルチシグネチャ (multisignature): マルチシグネチャは、複数の署名者が作成した特定のメッセージ上の署名を、認証の当事者全ての「集約した」鍵である単一の公開鍵で認証することができる単一の署名に「集約」する事ができる。は本来マルチシグネチャスキームである EC-Schnorr に対して ([11] 参照)、ECDSA もマルチシグネチャを作成できるがそれほど柔軟ではない。

ZILLIQA は EC-Schnorr ベースのマルチシグネチャを使用してメッセージに複数のシグネチャが必要な場合にシグネチャサイズを節約する。より小さな署名は複数の当事者がデータに署名することで同意する必要がある我々のコンセンサスプロトコルにおいて特に重要である。

3) 速度: ECDSA が大量の逆モジュロ演算を必要とすることから EC-Schnorr の方が高速である。EC-Schnorr では反転は必要ない。

正確な EC-Schnorr 鍵生成、署名、検証手順は APPENDIX A に記載する。付録には我々が EC-Schnorr をマルチシグネチャスキームとして使用する方法も示している。

B. Proof of Work

ZILLIQA は Sybil 攻撃を防ぎノード識別情報を生成するために PoW を使用する。これは、分散合意に達するために多くのブロックチェーンプラットフォーム (特に Bitcoin[1] と Ethereum[12]) が PwO を使用しているのとは対照的である。ZILLIQA は Ethereum 1.0 で使用されている PoW アルゴリズムである Ethash[13] を使用している。

Ethash は GPU で容易に採掘できるように設計されているが、ASIC などの特殊な計算ハードウェアでは難しいメモリハードハッシュ関数である。此を達成するために Ethash 演算は、その機能が特殊な計算ハードウェア上で並列して呼び出すことができないようにかなりのメモリ量 (GB) と I/O 帯域幅を必要とする。

大まかに、Ethash はデータ (例えばブロックヘッダ) と 64bit の nonce を入力として受け取り、256bit のダイジェストを生成する。このアルゴリズムは以下の順序で実行される 4 つのサブルーチンで校正されている:

1) シード生成: シードは epoch と呼ばれる 30000 ブロックごとに後進される SHA3-256 ダイジェストである。最初の epoch では 32 バイトゼロの SHA3-256 ハッシュである。それ以外の全ての epoch は常に前のシードの SHA3-256 ハッシュである。

2) キャッシュ生成: シードは SHA3-512 を使用して擬似ランダムキャッシュを生成するために使用される。キャッシュサイズは epoch とともに線形に増加する。キャッシュの初期サイズは 16MB である。

3) データセットの生成: キャッシュを使用してデータセットを生成する。データセット内の各「アイテム」はキャッシュ内の少数のアイテムのみに依存する。採掘者はデータセットを頻繁に更新する必要がないように epoch ごとに更新する。データセットのサイズも epoch ごとに線形に増加する。データセットの初期サイズは 1GB である。

4) 採掘および検証: 採掘は採掘はデータセットのランダムスライスとそれらを一緒にハッシュ化することを含む。検証ではハッシュを計算するために必要なデータセットの特定の部分を再生制するためにキャッシュを使用する。

IV. Data Layer

大まかに、データ層は ZILLIQA のグローバル状態を校正するデータを定義する。さらに ZILLIQA の様々なエンティティがそのグローバル状態を更新するために必要なデータも定義する。

A. Accounts, Addresses and State

ZILLIQA は (Ethereum のような) アカウントベースのシステムである。アカウントにはノーマルアカウントとコントラクトアカウントがある。ノーマルアカウントは ECSchnorr 秘密鍵を生成することで作成される。コントラクトアカウントは別のアカウントによって作成される。

それぞれのアカウントはそのタイプに応じて異なる方法で派生したアドレスによって識別される。ノーマルアカウントのアドレスはアカウントの秘密鍵から参照される。特定の秘密鍵 \(sk\) に対してアドレス \(A_{\rm normal}\) は \[ A_{\rm normal} = {\sf LSB}_{160} ({\tt SHA3\_256}({\sf PubKey}(sk))) \] で算出される 160bit 値である。ここで \({\sf LSB}_{160}(\cdot)\) は入力の右 160bit を返し、\({\sf PubKey}(\cdot)\) は入力の秘密鍵に対応する公開鍵を返す。コントラクトアカウントのアドレスは、その作成者のアドレスと、作成者アカウントが送信したトランザクションの数、いわゆるアカウント nonce (後述) から計算される: \[ A_{\rm contract} = {\sf LSB}_{160}({\tt SHA3\_256}({\tt address}||{\tt nonce})) \] ここで \({\tt address}\) は作成者アカウントのアドレス、\({\tt nonce}\) は作成者の nonce 値である。

ノーマルアカウントまたは契約アカウントはアカウント状態に関連づけられている。アカウント状態は key-value ストアであり次のキーで校正されている。

1. account nonce: (64bit) ノーマルアカウントから送信されたトランザクション数である (初期値 0 の) カウンター。コントラクトアカウントの場合、そのアカウントによって作られたコントラクトの作成数がカウントされる。
2. balance: (128bit) 非負値。アカウントが別のアカウントからトークンを受け取る度に、受け取った金額がアカウントの残高としてカウントされる。アカウントが別のアカウントにトークンを送信すると balance は適切な金額だけ減額される。
3. code hash: (256bit) コントラクトコードの SHA3-256 ダイジェストを保存する。ノーマルアカウントでは空の文字列に対する SHA3-256 ダイジェスト。
4. storage root: (256bit) 各アカウントには 256bit のキーと 256bit の値を持つ key-value ストアとなるストレージが存在する。storage root はこのストレージを表す SHA3-256 ダイジェストである。例えばストレージがトライ木の場合、storage root はトライ木のルートのダイジェストである。

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

B. Transactions

C. Blocks

V. Network Layer

ZILLIQA はトランザクションレートをスケールするように設計されている。主なアイディアは sharding、すなはち採掘ネットワークをトランザクションを並行して処理できる小さな shard に分割することである。このセクションではネットワークとトランザクションの分割のアイディアを示す。

A. Network Sharding

ネットワーク sharding、すなはち採掘ネットワークをより小さい shard に分割するには 2 段階のプロセスがある。まずディレクトリサービス committee (DS committee) と呼ばれる専用のノードセットが選択され、それがネットワークを shard 化し、それらの shard にノードを割り当てる。以下にこれらのプロセスをさらに詳細に提示する。

1) Directory Service Committee: ネットワークの sharding を容易にするために、最初にディレクトリサービス (DS) ノードと呼ばれるノードのグループを選出する。DS ノードは DS committee を形成する。DS ノードの選択は PoW₁ と呼ばれる proof-of-work パズルに基づいている。PoW₁ アルゴリズムを Algorithm 1 に示す。

首尾良く他のノードよりも早く PoW₁ に対して有効な nonce を生成したノードは新しい DS-Block のためのヘッダを提案する。DS-Block はヘッダと署名部分からなる。ノードが PoW₁ を実行するとき、それは DS-Block ヘッダを生成するのみである。その後ブロックは DS committee のノードにマルチキャストされれ、DS committee は提案された DS-Block ヘッダについて合意をとり署名部分を生成する。\(2f\) の DS ノードが DS-Block ヘッダに署名すると DS ブロックチェーンにコミットされる。

ブートストラップフェーズが成功すると、DS ノードの構成はサイズ \(n_0\) の事前定義ウィンドウによって規定される。DS-Block の採掘に成功した最新の \(n_0\) 個のノードが DS committee を構成する。

2 つの連続 DS-Block を採掘する平均時間を DS-epoch と呼ぶ。DS-epoch の値は 2 つの競合ブロックが発生する可能性を最小化するように設定される。DS-epoch の開始時、新しい DS ノードが DS committee に参加し、DS committee の最も古いメンバーが解任される。これにより DS-epoch 中の DS committee のサイズは \(n_0\) に固定される。その後、DS committee の最新メンバーがリーダーとなり epoch の間のコンセンサスプロトコルを主導する (コンセンサスプロトコルについては Section VI 参照)。さらにこれは DS committee メンバーに厳格な命令を含む。

DS committee の規模が十分に大きい場合 (概ね 800 以上)、\(n_0\) の committee のうちで最大 \(\frac{1}{3}\) が高い確率でビザンチンであることが分かる。

2) Resolving Conflicts: 我々の (セクション VI で提示される) コンセンサスプロトコルは DS-Block のフォークを許さない。複数のノードがほぼ同時にパズルを解くときフォークが発生する可能性がある。競合を解決するため、各 DS ノードは受信したヘッダから nonce フィールドを取り出し、それらを昇順にソートする。このときの \(i\) 番目の DS ノードを \(n^i_{\rm max}\) と仮定する。

DS committee のリーダーは (それが発見した最も大きい nonce に対応する) それ自身のヘッダを提案し、DS-Block ヘッダに同意するためにコンセンサスプロトコルを実行する。次いで \(i\) 番目の DS ノードは、対応する nonce が \(n^i_{\rm max}\) 以上である場合に限り、提案されたヘッダを受け入れることに合意する。合意に達すると DS-Block の署名部分が構築され合意を受けた勝者がリーダーとなる。

3) Generating Shards: DS committee が選出されるとネットワークの実際の sharding を開始する事ができる。ノードが基礎となるコンセンサスプロトコルに参加するためには proof-of-work (PoW₂) を実行しなければならない。sharding プロトコルは全ての DS-epoch 開始時に繰り返されている。PoW₂ のアルゴリズムは Algorithm 2 のように示される。

PoW₂ で算出された有効な nonce (および mixhash) は DS committee にマルチキャストされる。DS ノードは I 個のコンセンサス committees または shards に分割するのに十分な数の PoW 解をまとめて受け入れ、それぞれは \(n_0\) 個のノードでコンセンサスを実行する。DS committee リーダーに十分な数の PoW₂ 解が受け入れられると、リーダーは有効な PoW₂ 解のセットについて合意するためにコンセンサスプロトコルを開始する。コンセンサスプロトコルの最後にリーダーは DS ノードによって署名された EC-Schnorr マルチシグネチャを生成する。課程を進めるためには DS ノードの 2/3 以上が受け入れ可能な PoW₂ 解のセットに合意していなければならない。

sharding は決定論的関数を用いてノードを shard に割り当てる。それぞれが \(n_0\) 個のノードを持つ \(\ell\) 個の shard が必要だと仮定する。このとき nonce 値は昇順にソートされ、最初の \(n_0\) 個のノードが最初の shard に、次の \(n_0\) 個が次のシャードへと順に割り当てられる。shard の中で最大の nonce 値を提案した採掘者のアイデンティティがそのリーダーとして宣言される。これにより shard のメンバーには厳密な順序付けも導入される。

\(n_0\) が十分に大きい場合 (800 以上など)、各 shard 内で最大 \(\frac{1}{3}\) が高い確率でビザンティンであることも分かるだろう。

B. Public Channel

DS ノードは DS ノードのアイデンティティと接続情報、各 shard のノードリスト、またトランザクションの sharding ロジック (Section V-D で説明) を含むパブリックチャンネル上の特定の情報を公開する。パブリックチャンネルは trusted ではなく全てのノードからアクセス可能であると仮定する。

承認のためにトランザクションを送信したい我々のブロックチェーンのユーザは、そのトランザクション処理する責任を shard に依頼するために sharding に関する情報を確認ことができる。パブリックチャンネルで公開された情報はどのようなノードもしくはユーザでも検証できるように 2/3 以上の DS ノードによって署名されていることが期待される。

C. New Nodes Joining ZILLIQA

新しいノードがネットワークに参加するには、PoW₁ を解いて DS ノードになるか PoW₂ を解いて shard のメンバーになることができる。そのためにはブロックチェーンから PoW₁ または PoW₂ に要求されるランダム性に関する情報を取得する必要がある。ランダム性情報を取得すると新しいノードはそれを解き DS committee に送信することができる。

D. Transaction Sharding and Processing

Section V-A に示されるように、ネットワーク sharding はそれぞれトランザクションを並行して処理できる shard を作成する。このセクションでは、特定のトランザクションがどのように shard に割り当てられるのか、そしてそのトランザクションがどのように処理されるのかを説明する。このために我々は以下のような抽象化を使用する: \(A \xrightarrow{\text{n}} B\) は送信者のアカウント \(A\) から受信者のアカウント \(B\) へ \(n\) ZIL のトランザクションを示す。

1) Transaction Assignment: どのようなトランザクションでも \(A \xrightarrow{\text{n}} B\) は単一の shard で処理される。\(0\) から \(\ell - 1\) まで順序づけられた \(\ell\) 個の shard を仮定したとき、トランザクションは送信者アドレス、つまりこの例ではアカウント \(A\) のアドレスの右端 \(\lfloor \log_2 \ell \rfloor + 1\) bit で識別される shard に割り当てられる。アカウントアドレスは 160bit 整数であることから \(\ell\) の境界は: \[ \lfloor \log_2 \ell \rfloor + 1 \leq 160 \] しかし実際には \(\ell\) は 100 よりも小さくなるだろう。

割り当てられた shard が識別されると、トランザクションは shard 内の幾つかのノードにマルチキャストされ、さらにそのノードからブロードキャストされる。トランザクションが割り当てられた shard のリーダーに到達すると、それを TX ブロックに含めコンセンサスプロトコルを実行する。

二重送金 (またはリプレイ攻撃) は全てのトランザクションに存在する nonce を使用して簡単に検出することができる。各トランザクションには、送信者のアカウントから送信されたトランザクション数のカウントである nonce が含まれている。トランザクションがトランザクションブロックチェーンに入ると、nonce はアカウントの状態、つまりグローバルの state で更新される。グローバル state の現在値以下の nonce を持つトランザクションは採掘者によって拒否される。

送信者のアカウントアドレスに基づいてトランザクションを sharding することで、送信者からの全てのトランザクションが同じ shard 内で処理されるため shard のメンバーが二重送金を検出できるようになる。

2) Transaction Processing: committee 内の全てのノードがトランザクションを提案することができる。これらのトランザクションは、次の TX-Block を形成するトランザクションのセットとして、コンセンサスプロトコルを実行するためにリーダーに送信される。各 shard によって提案されたブロックは (タイプマーカー 0x00 によって識別される) マイクロブロックと呼ばれる。マイクロブロックには shard から \(\frac{2}{3}\) ノード以上による EC-Schnorr マルチシグネチャを含んでいる。リーダーは署名者の公開鍵を識別するビットマップ \(B\) も構築する。shard の \(i\) 番目のメンバーが TX-Block ヘッダに署名した場合 \(B[i] = 1\) である。shard が TX-Block で合意に達すると、そのリーダーはブロックの header と signature を幾つかの DS ノードにマルチキャストする。そして DS ノードはそれを DS committee 内にブロードキャストし、ブロックはそのリーダーに到達する。ブロックの data 部分はノードに非同期で送信される。

その後、DS committee は shard から送信された全てのブロックを集約し、最後のブロックについて合意するために自分たちの間で別のラウンドの合意プロトコルを実行する。ファイナルブロックはタイプマーカー 0x01 で識別される TX-Block である。ファイナルブロックは DS committee から \(\frac{2}{3}n_0\) ノードを超える EC-Schnorr マルチシグネチャが含まれている。DS committee のリーダーは署名者の公開鍵を識別するビットマップ \(B\) も作成する。DS committee の \(i\) 番目のメンバーが TX-Block ヘッダに署名した場合 \(B[i] = 1\) である。ファイナルブロック header と signature は、各 shard 内の幾つかのノードにマルチキャストされる。実際の TX-Block data は DS ノードによっては送信されない。

各 shard 内でファイルなるブロックを処理するために以下のステップが行われる:

1. shard 内の各ノードは DS ノードの公開鍵を使用して EC-Schnorr マルチシグネチャを検証する。署名がビットマップによって表される \(\frac{2}{3}n_0\) を超える公開鍵に対して有効である場合、ノードは次のチェックを実行する。
2. ファイナルブロックヘッダに含まれる各トランザクションハッシュに対して、ノードはそれに対応するトランザクション内容が有効かをチェックする。対応するトランザクションが、ノードが属する shard によって提案されたものである場合、トランザクションデータのハッシュはファイナルブロックヘッダに含まれるハッシュと比較される。トランザクションが別の shard によって提案された場合、トランザクションは shard 間で非同期に共有される。
3. トランザクションデータ利用可能であれば、ファイナルブロックのデータ部分が再構築され、TX-Block がローカルトランザクションブロックチェーンに追加される。アカウント状態とグローバル state はそれに応じて更新される。
4. トランザクション内容が利用可能でない場合、ノードはローカルのアカウントビューでそのトランザクションの送信アカウントを一時的に無効化し、ローカルトランザクションコンテンツがグローバル状態と同期するまでこのアカウントに対する保留中の全てのトランザクションを拒否する。そのような拒否されたトランザクションは送信側ノードによって再試行される必要がある。

VI. Consensus Layer

前述のように各 shard と DS committee はそれぞれマイクロブロックと最後のブロックとでコンセンサスプロトコルを実行しなければならない。このセクションでは各 shard と DS committee 内で実行されるコンセンサスプロトコルを定義するコンセンサス層を提示する。これ以降の説明では shard と DS committee を総称してコンセンサスグループと呼ぶ。

A. Practical Byzantine Fault Tolerance

ZILLIQA コンセンサスプロトコルの中核は Castro と Liskov [3] によって提案された practical byzantine fault tolerance (PBFT) に基づいている。しかしながら、我々は [14][15] で開発されたように PBFT プロトコルにおいて EC-Schnorr マルチシグネチャを使用するアイディアを使ってその効率を改善する。EC-Schnorr マルチシグネチャを使用すると通常の場合の通信遅延が \(O(n^2)\) から \(O(n)\) に低減し、署名サイズも \(O(n)\) から \(O(1)\) に減少する。ここで \(n\) はコンセンサスグループのサイズである。このセクションでは PBFT の概要を説明する。

PBFT ではコンセンサスグループ内の全てのノードが順番に並べられ、1つのプライマリノード (またはリーダー) が存在し、それ以外のノードはバックアップノードと呼ばれる。以下に述べるように PBFT のラウンドは 3 つのフェーズがある。

1. Pre-prepare phase: このフェーズではリーダーはグループが合意すべき次のレコード (我々の場合は TX-Block) をアナウンスする。
2. Prepare phase: pre-prepare メッセージを受信すると、各ノードはその正当性を検証し他の全てのノードに prepare メッセージをマルチキャストする。
3. Commit phase: \(\frac{2}{3}n\) を超える prepare メッセージを受信すると、ノードはグループに commit メッセージをマルチキャストする。最後に、ノードは十分な数のノードが同じ決定を下した事を確認するために \(\frac{2}{3}\) を超える commit メッセージを待つ。これにより全ての正常なノードは同じ有効なレコードを受け入れる。

PBFT は、各フェーズを開始し、十分な投票が存在するときに処理を進めることを正常なリーダーに頼っている。リーダーがビザンティンである場合、全体の合意プロトコルをストールさせる可能性がある。この課題に取り組むために、PBFT はビザンティンのリーダーを他と取り替える view change プロトコルを提供する。制限時間内に進捗が見られない場合、ノードたちはリーダーを変更する要求を提示することができる。\(\frac{2}{3}n\) を超えるノードがリーダーに障害があると判断した場合、よく知られたスケジュールとして次のリーダーが引き継ぐ。

prepare/commit フェーズにおける全てのノードのマルチキャストのために、通常のケースで PBFT の通信複雑度は \(O(n^2)\) である。

B. Improving Efficiency

古典的な PBFT はノード間の認証された通信に message authorization code (MAC) を使用する。MAC は 2 つのノードごとに共有される秘密鍵を必要とするため、1 つのコンセンサスグループ内のノードは、ノードあたり \(O(n^2)\) の通信複雑度で同一のレコードに対して同意することができる。この 2 次の複雑さにより、PBFT は committee が 20 ノードを超えると実用的ではなくなる。

効率を改善するために ByzCoin[15] から発想を得たアイディアを使用する:

1. 通信オーバーヘッドを \(O(n)\) まで削減するために MAC をデジタル署名に置き換える。
2. さて、他のノードが合意を検証できるようにするための一つの典型的な方法は、正常な多数から署名を収集してそれらに合意を追加することである。それによって合意サイズはコンセンサスグループのサイズに比例した線形になる。これを改善するために EC-Schnorr マルチシグネチャを使用して幾つかのシグネチャを \(O(1)\) サイズのマルチシグネチャに集約する。

ただし PBFT の設定では、従来の EC-Schnorr マルチシグネチャスキームを直接使用することができない。これは、古典的な設定では、全ての署名者が特定のメッセージの署名し、署名は全て署名者がメッセージに署名したときのみ有効であるためだ。PBFT の設定ではコンセンサスグループ内の \(\frac{2}{3}n\) ノードを超えるノードでメッセージに署名することだけを要求する。必要とされる主な変更の一つは署名プロセスに参加している署名者のビットマップ \(B\) を維持することである。\(i\) 番目のノードがプロセスに参加した場合、\(B[i] = 1\) であり、そうでなければ \(0\) である。このビットマップはリーダーによって作成される。そしてビット間婦破署名を検証するために任意の検証者によって使用される。最終的なプロトコルは Appendix B に残されている。

C. ZILLIQA Consensus

D. Leader Change

VII. Smart Contract Layer

A. Computational Sharding using Dataflow Paradigm

B. Smart Security Budgeting

C. Scalable Applications: Examples

VIII. Incentive Layer

A. Token Supply

B. Incentivizing Miners

IX. Related Work

X. Future Research Directions

XI. Conclusion

References

1. [1] S. Nakamoto, “Bitcoin: A peer-to-peer electronic cash system, http://bitcoin.org/bitcoin.pdf,” 2008.
2. [2] E. Foundation, “Ethereum’s white paper,” https://github.com/ethereum/ wiki/wiki/White-Paper, 2014.
3. [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. [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. [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. [6] NIST, “Sha-3 standard: Permutation-based hash and extendable-output functions,” 2015.
7. [7] B. Guido, D. Joan, P. Michael, and V. A. Gilles, “The Keccak Reference ¨ ,” 2011.
8. [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
9. [10] A. Poelstra, “Schnorr Signatures are Non-Malleable in the Random Oracle Model,” 2014.
10. [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.
11. [12] G. Wood, “Ethereum: A secure decentralised generalised transaction ledger,” http://gavwood.com/paper.pdf, 2014.
12. [13] “Ethash,” https://github.com/ethereum/wiki/wiki/Ethash, Accessed on June 27, 2017., version 23.
13. [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.
14. [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.
15. [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.
16. [17] A. L. Davis and R. M. Keller, “Data flow program graphs,” Computer, vol. 15, no. 2, pp. 26–41, Feb. 1982.
17. [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.
18. [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.
19. [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.
20. [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.
21. [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.
22. [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.
23. [24] BSI, “Technical Guideline TR-03111 Elliptic Curve Cryptography,” Federal Office for Information Security, Tech. Rep., 01 2012.
24. [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
25. [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.

APPENDIX A: Schnorr Digital Signature Algorithm

A. EC-Schnorr (Single Signer) Scheme

B. EC-Schnorr Multisignature Scheme

APPENDIX B: Multisignature for PBFT

参考文献

1. The ZILLIQA Technical Whitepaper (原文)