Zilliqa white paper memo

調べる点

付録A EC-Shnorrについて

すごいところ

PoWをアイデンティティの確立に使い、シャーディングのグループを作っている

あやしいところ

悪意をあるノードが1/4の計算能力を保有しているというところ

割と性善説感あり

nonceの値によって、優先するやり方は本当に良いのか？

なんか高い値から調べたほうが期待値あがるとか（ぱっと思いつかないけど・・・）

シャード割り振りロジックで送信者のアドレスを使うが、それは問題ないか？

特定のシャードで割り当てられるので、賄賂とかでインセンティブを書き換えられる可能性がる

メモ

概要

シャーディングを使ってスケーラビリティを上げているのが肝

各サブネットワークが2重支払いなどの重複なしで異なるトランザクションを処理していることを保証するのが重要

仮定として、全体の1/4より悪意のあるノードは少ない

スマコン言語はデータフロープログラミング形式で有向グラフ

グラフにおける２つのノード間の出力と入力は一致する

データフローコントラクトは本質的に並列

MapReduceタスクなら何でも処理できる

Ziliqaは6つの層でこうせい

暗号

データ

ネットワーク

コンセンサス

スマコン

インセンティブ

システム設定と前提

エンティティ

ユーザーとマイナー

マイニングネットワークはシャードに分けれられる

DSノードと呼ばれるマイナーのグループによってシャードい分けられる

このDSノードのグループをDSコミッティ

各マイナーはアイデンティティとしてIPアドレスと公開鍵を持つ

ネイティブトークン

Zilling！！（ZIL）

脅威モデル

ビザンチンはいることは確定

1/4はビザンチンだとしていいる前提

Zilliqaは一貫性をとり、可用性を犠牲にする

↑つまり、ビザンチンの振る舞いによってネットワークが詰まる可能性がある

暗号層

低レベルの汎用暗号アルゴリズム

電子署名に楕円曲線暗号

PoWにメモリーハードハッシュ関数

Ethereumとかで使われているKeccakに切り替える可能性もあり

A. シュノア署名

EC-Schnorrを署名アルゴリズムとして採用

ECDSAではなくEC-Scnorrを用いる利点

頑強性

署名を改ざんして新しい署名を作成することが困難なこと

マルチシグネチャー

複数の人の鍵を集約した1つの公開鍵で認証することができる

複数の参加者が署名をすることで、あるデータについて合意する必要があるZilliqaにとっては重要

速度

ECDSAより早い

B. PoW

シビル攻撃防ぐためにアイデンティティを生成するのにPoWを用いる

Ethereum1.0で使われた、Ethashを採用

GPUマイニングは簡単だが、ASICとか専用機器は使えないアルゴリズム

大量メモリとI/O帯域幅が必要なため

データ層

A. アカウント

アカウントべース

ノーマルとコントラクトアカウント

基本的に、Ethereumと同じしくみでアドレス生成している

アカウントの状態もEthと同じそう

B. トランザクション

ノーマルのアカウントからトランザクションは送られる

フィールドも割とethとかに近い

EC-Schnorrの公開鍵と署名があるのが違いか

signatureフィールドを覗いてSHA3-256ハッシュを求めるとトランザクションIDを求められる

C. Block

２種類のブロック！！

TXブロックとDSブロック（directry servise）

TXブロックはユーザに送られたトランザクションを含む

DSブロックはコンセンサスプロトコルに参加しているマイナーに関するメタデータも含む

DS-Block

header

version

previous hash

pubkey

PoWを行ったマイナーの公開鍵

difficulty

number

timestamp

mixHash

nonce

signature

signature

DS-Blockヘッダーに対してDSノードによって行われるEC-Schnorrマルチシグネチャー

bitmap

どのDSノードあマルチシグネチャーに参加したかを記録する

DSブロックはそれら自体でDSブロックチェーンを構成

TXブロック

DSブロックはコンセンサスに達したノードに関する情報を含む

TX-BlockはDS-Block内のノードによってどのトランザクションが合意に達したのかについての情報を含む

各DSブロックは複数のTXブロックと紐づく

field

type

マイクロブロック or 最終ブロックか

version

previous hash

gaslimit

gasused

number

timestamp

stateroot

transaction root

tx hashes

pubkey

ブロックを提案したリーダーのEC-Schnorr公開鍵

pubkey micro blocks

EC0Schnor公開鍵のリスト

リストにはトランザクションを提案したリーダーたちの公開鍵を含む

最終ブロックのときのみ

parent block hash

前の最終ブロックのヘッダー

parent ds hash

親DS-Blockヘッダーのハッシュ

parent ds block number

親DSブロック番号

ネットワーク

ネットワークシャーディングとトランザクションシャーディング

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

マイニングネットワークを小さなシャードに分割すること

2段階の処理

DSコミッティーの選択

ノードをシャードに割り振る

1. DS コミッティー

DSコミッティーの選出はPoWに基づいている

他のノードよりも早くPoWに対して有効なnonceを求めたノードは新しいheaderを提案

headerはマルチキャストされ、DSコミッティ内で合意形成を行い2/3のDSノードがheaderに署名されるとDSブロックチェーンへコミットされる

DSコミッティーの数は一定

DSブロックの生成に成功した一定数のノード郡がDSコミッティー

FIFOの仕組みで抜けたり入ったり

また、最も新しいDSノードがリーダー

2. 衝突の解決

DSブロックチェーンはフォークだめ絶対

つまりファイナリティがある

ファイナリティを確立させるため、nonceを取り出し昇順に並び替え最も大きんnonceを使うようにする

各ノードとリーダーが大きいnonceのヘッダーを決め、それが各ノードが決めたものより大きい or 等しければ合意！！

3. シャード生成

DSコミッティーが選出されるとシャーディング開始

あるノードがコンセンサスに参加するためにはPoW2を行う

シャーディングプロトコルもDS-epochごとに行われる

PoW2のナンスはDSコミッティーにマルチキャスト

DSリーダーが十分な量の回を受け取ると有効な解を探すためにコンセンサスプロトコルを始める

B. パブリックチャネル

DSノードのアイデンティティや接続情報、各シャードのノードリスト等を流す場所

基本的に信用はされていない場所で、全てのノードがアクセスできる

パブリックチャネルから、自分のトランザクションがどのシャードで処理されているかやDSコミッティーに署名（ファイナリティ）されてるかとかがわかる

C. 新規ノードの参加

PoW1 or PoW2をとけば良い

前者はDSコミッティー、後者はシャードメンバー

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

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

A->BへnZILをくる場合、このトランザクションは1つのシャードで処理

シャードが決まると、トランザクションはそのシャード内のノードにマルチキャストされ、そこからブロードキャストされる

シャードリーダーまで届けば、TX-Blockに入れてコンセンサスプロトコルを実行

二重支払いはそのシャードにしか送られてこないので、nonceを見れば一発でわかる

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

コミッティー内の全てのノードはトランザクションを提案できる

リーダが最終的には集めてTX-Blockに取り込むか考える

各シャードによって提案されたブロックはマイクロブロックと呼ばれる（TX-Blockの一種）

マイクロブロックはそのシャードの2/3超のノードによるEC-Schnorrマルチシグネチャー入り

リーダーは誰が署名したかわかるようにビットマップも作る

TX-Blockの合意がえられたら、DSノードへマルチキャストする

最終的には最終ブロックがDSコミッティー内で作られる

これも2/3のノードから署名を受ける

コンセンサス層

PBFT

PBFTがコンセンサスプロトコルの中核

＋EC-Schnorrを採用している

コミュニケーションコストO(n^2) -> O(1)

署名サイズO(n) -> O(1)

コンセンサスグループはシャードとDSコミッティー

3つのフェーズ

1. Pre-prepare phase

グループが次に合意すべきTXblockをリーダーがアナウンスする

2. Prepare phase

pre-prepareメッセージから各ノードその正確性を検証し、prepareメッセージをほかのノーでへマルチキャスト

3. Commit phase

2/3を超えるprepareメッセージを受け取るとノードはcommitメッセージをグループにマルチキャスト

リーダーが各フェーズを始め、十分な量の票数を得られたときにプロセスが始まることに頼っている

リーダーがビザンチンの場合はプロトコルが止まり、リーダーを別のリーダーに置き換えるようにしている

これも2/3の不信任投票が必要

prepare/commitフェーズではマルチキャストするので、普通だとO(n^2)

効率性の向上

通常のPBFTは認証のためにMACを用いる

各ノードのペアで共有される秘密鍵が必要なので、O(n^2)

MAC -> 電子署名に変えるとO(n)

要はn回署名すれば全体のコンセンサスを得られるので

EC-Schnorrマルチシグネチャーを使えば複数の署名をO(1)のサイズに集約可能

ただし、↑は全体の署名が必須になる（2/3の署名とかはできない）

そのため、だれが署名をしたかという印をつければよく、それはビットマップで表している

Zilliqaコンセンサス

1. Pre-prepare phase

TXブロックの配布

2. Prepare phase

すべてのノードはTXブロックを検証し、リーダーへ返す

これにはEC-Schnorr署名がされていて、マルチシグネチャーを生成される

＋ビットマップがあるので、だれが検証したかがわかる

3. Commit phase

↑の署名を検証する

リーダーの変更

リーダーに悪意があったりした場合はペナルティを与える

スマートコントラクト層

シャードのアーキテクチャは計算コストの高いタスクを効率的に行うのに適している

計算シャーディング

コントラクトを有向グラフとして表せるデータフロープログラミング形式

フォン・ノイマン型の実行モデルとは対照的

メリットは同時に複数の命令を実行できる

MapReduce形式の計算に適している

1. 全体でグローバルに共有されている仮想メモリ領域で実行

2. 実行の間メモリ領域の中の中間セルをロック

3. 中間結果は逐次確認

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

計算リソースのシャーディングによって、計算を行うコンセンサスグループのサイズを決めれる

つまり、全体が同じ結果だったらOK？か3/4同じだったらOKかとか

ユースケースにあった、方法で計算力をたかめるか？セキュリティを高めるかをユーザー側が選べる

eg. DLしたいのに、全ノードで同じ処理しても意味ないとか

Zilliqaにあったアプリケーション

並列可能な計算

大規模なデータ使うとか

NNの学習

複雑で高い制度が求められるアプリケーション

計算結果がずれてはいけないもの

コンセンサスグループを大きくしてクロスチェックすれば

インセンティブ層

トークン供給

有限な総発行量

TXブロックの生成で新しいトークンがブロック報酬として付与される

10年で空にする予定

それ以降はgas feeオンリー

TXブロックが提案されるとgas feeとブロック報酬が提案した各シャードのリーダーとDSコミッティーのリーダーへ均等に分けられる