Ethereum yellow paper メモ

調査項目

GHOSTプロトコル

Abstract

暗号学的に保護されたトランザクションに関連するブロックチェーンのバラダイムは何個ものプロジェクトを通してその有効性を実証してきた

最も注目されたものはBitcoin

シンプルな非中央集権なアプリケーションとして見られているが、実施はシングルトンなコンピュータリソースである

著者らはこのパラダイムをtransactional singleton machine with shard-stateと読んでいる

Ethereumはこのパラダイムを一般的化された方法で実装する

さらに、Ethereumは複数のリソースをもたらす

1. 明確な状態

2. Operating code

しかし、メッセージ通過フレームワークを通して他のものとインタラクションを取ることができる

著者らはその設計、問題、もたらす機会、想像する未来に関して議論する

Introduction

インターネットは世界中に普及しており、どこでも安く利用することができる

ビットコインのような技術の根幹の動向はインターネットを非中央集権な価値の移転システムへと変えることを可能とする

価値の移転システムは世界中とバーチャルな手数料を使うことでシェアされる価値の移転システム

このシステムはトランザクションベースのステートマシンで暗号学的な保護のとてもスペシャルなバージョンである

Nameコインのような上記であげたシステムはこのオリジナルな「通貨アプリケーション」を適応した

↑シンプルなアプリケーションではあるが、他のアプリケーションへとこのテクノロジーで

Ethereumはこういったテクノロジーの一般化を作るための試みるプロジェクトである

こういったテクノロジーとはすべてのトランザクションベースなステートマシンのコンセプトを作れるかもしれない技術

また、Ethereumはend-developerへソフトウェアをビルドするためのしっかりと結合したe2eなシステムを提供することも目的である

↑これまでメインストリーム上のよくわからなかったコンピュータパラグラ上で構築するソフトウェア

1.1 Driving Factors

たくさんのゴールがある

そのなかでも重要な一つとしては、お互いが信用していない他の人とでも、トランザクションを発行（取引）することを促進すること

豊かで、曖昧な言葉を通してステートチェンジマシンをを指定し、私達が合理的に自動で強制されるような合意を予測できるようなシステムを構築することによって、この方法を提供することができる（Ethereum？）

提案したシステム上での取引をすることは現実の世界ではあまり見つからない属性をいくつか持つだろう

発見することが難しいジャッジの腐敗は無益なアルゴリズムのインタプリタから導かれる

透明性や正確に状態か判定を見ることができるようにすることはTxログとルールもしくは教育的なコードを通して起きる

決して人間ベースのシステムで起きることはない

自然言語は必然的に曖昧で、情報が欠損し、普通の古い偏見（常識は）は覆しにくいため

まとめると、Ethereumの開発者らは（GAVIN WOOD CTO of Ethereum）下記のようなシステムを提供することを望んでいる

ユーザーが他の個人、システム、組織などに対するとインタラクトすることは問題なく、彼らは発生しうる結果の上で絶対的信頼を起くことができ、それらの結果がどのようになるかを保証されることが可能

1.2 Previous Work

Vitalikは2013, Nov. にこの研究のコアを最初に提案した

今は様々な方法で進化されたが、チューリング完全と内部TXのストレージ容量が圧迫しないような効率性を持つブロックチェーンのキーとなる機能は残っていて変わらない

Dwork and Naorはある提案した

計算学的支出の暗号学的証明の使用法に関する研究（PoW）

インターネットを通り、value signalを送信するという意味がある

Value signalはこの研究でも利用された、

すべての通貨の種類で必要なものではなくスパムを抑止するメカニズムとして

しかし、Value signalは批判的に可能性を実証した

可能性とはstrong economic signalをもたらす可能性

また、信頼に頼ることなく、物理的なアサーションを作るために受診者を許可することができた（トラストレスに正しいデータを認識することができた）

通貨をセキュアにするためにstrong economic signalとしてPoW使われた最初の例は2003のもの

この場合では、トークンはP2Pファイルで取引履歴をチェックし、保持されて使われた

サービスのサプライヤにマイクロペイメントを実現する機能をコンシューマへ提供する

PoWによって与えられたこのセキュリティモデルは電子署名と台帳によって増強された

この台帳は歴史的な記録が破損できないようにすることや攻撃者が偽装した決済やサービス提供に関する不平な主張をすることをできないようにすることを保証するためのもの

5年後、Satoshi Nakamtoは2008でもう一つのPoWが使われたセキュアな価値トークンを提案した

このプロジェクト、Bitcoinの果実（すごいところとかの意味かな？）ははじめてのグローバルな分散的取引台帳の広い採用になった

他のプロジェクトはビットコインの成功によって作られたアルトコインは他のプロトコルを通して多数の他の通貨を提案した

よく知られたいくつかのものは、LitecoinとPrimecoinである（2013）

他のプロジェクトはそのプロトコルのコアな価値となるメカニズムを模索された

Aron（2012）は下記について議論した

分散的な名前解決システムを提供することを目的としたNamecoinプロジェクトについて

他のプロジェクトはまだ、Bitcoinネットワーク自体の上で構築することを目的としている

システムとコンセンサスメカニズムによってもたらされる莫大な計算量の上に位置する価値のほとんどを活用することによって

Mastercoinプロジェクトは2013に提案された

これは、リッチなプロトコルを構築することを目的としている

↑コアプロトコルに多くの補助的なパーツをつけ、ビットコインプロトコルの上に多くの付加されたハイレベルな機能を関与させることによって

Coloured Coins（2012）はMastercoinに似ているがもっとシンプルな戦略を撮っている

↑トランザクションのルールを装飾することによって

↑Bitcoinの基礎通貨の代替性を壊すため

特殊なウォレットプロトコルでトークンの生成とトラックを許可するため

他の研究としては、Ripple

通貨取引所のための連合システムを作ることが求められた

効率的に新しいクリアな金融システムを作るために

これは実施された

スマートコントラクトに関する前の研究ではは1997に提案された

90sには、それは明確になっていた

どのようにかというと合意をアルゴリズムな強制することは人間の会社に対して重大になる

そのような特定のシステムは提案されていないが、それは提案された

↑法律の未来は、そのようなシステムによって大きく影響を与えるだろうと考えられた

この光のなかで、Ethereumはcrypto lawシステムのような一般的な実装になるかもしれない

The Blockchain paradigm

全体としてEthereumはトランザクションベースのステートマシンと見られることができる

私達はgenesisステートではじめ、最後のステートに変わるために徐々にトランザクションを実行する

著者らはEthereumの世界の標準的なバージョンとして、この最後の状態を受け入れる

ステートはある情報を含むことができる

情報とは、アカウントのバランス、評判、信頼契約？、実世界の情報に対する関連データ

要するに、現在にコンピュータによって表現されるすべては容認できる

したがって、トランザクションは2つの状態の遷移を表現する

検証の部分は重要である

はるかに無効な状態が存在する

不正な状態への変化は例えば、他の場所を増加させ、全体での均衡を保つことなくアカウントの残高を減らすようなことかもしれない

検証されたステート遷移はトランザクションを通ってもたらせる

$ \sigma_{t+1} = \gamma(\sigma_t, T)

トランザクションはブロック内に集められる

ブロックは暗号学的ハッシュ値を参照とするような方法と一生にチェーンのように繋がれる

前のブロックと最後の状態の識別子（全体を保存するのは大きすぎて無理）と一緒にトランザクションの連なりを記録するジャーナルとしてのブロック関数

それらはまた、トランザクションシリーズを区切る

↑どんなトランザクションシリーズかといいうと、マイニングすることによってインセンティブを与えることが関連した

このインセンティブは指定されたアカウントに価値を追加し、状態遷移関数として起こる

マイニングは努力を捧げるプロセスである

↑努力とは、ブロックのシリーズが他の潜在的な競合ブロックに比べて強化される

暗号学的セキュアな証明のおかげでこの目的を達成できる

このスキーマはPoWとして知られていて、section 11.5で詳細について議論している

定式化すれば

この関数は指定したパーティに報酬を与える

いくつかの他のコンポーネントとの間でトランザクションの連なりを含む

これはブロックチェーンパラダイムの基本となっている、

どんなパラアイムかというと、Ethereumだけでなく現在までのすべての分散的な合意形成トランザクションシステムのバックボーンを形式化するモデル

2.1 Value

ネットワーク内で計算量にインセンティブを与えるために、値を伝えることに合意する方法が必要である

この問題を扱うために、Ethereumは固有の通貨を持っている

Etherと呼ばれ、ETHと表記

最も小さなEtherの単位はWeiで表され、Wei単位のintegerで表される

2.2 Witch History?

システムが非中央集権的ですべてのパーティがすでにあるブロックのあとに新しいブロックを作る機会があるので、得られた構造はブロックのtreeが必要とされる

genesisブロックから現在のブロックまでのどのパスが正しいかに関する合意を形式化するためには、合意するスキーマがなければならない。

ルートから末端までのパスでどれがベストなブロックチェーンかのようにノード間で不一致がある場合、フォークが発生する

これは、ブロックによって与えられた過去はそのシステムの複数の状態として共存するかもしれない

いくつかのノードは標準的なトランザクションを含むあるブロックであると信じている

標準的な他のブロックを信じている他のノードは根本的に異なるもしくは互換性のないトランザクションを潜在的に含んでいる

これは不確実性のようにすべてのコストで避けることである。

↑どのような不確実性かというと、システム全体ですべての信頼を殺すようなことを続ける不確実性

著者らが合意を生成するために使うこのスキーマはGHOSTプロトコル（2013）というバージョンのシンプルなものである

このプロセスはセクション10で説明される

たまに、特定のブロック高から新しいプロトコルでメインチェーンのパスが適用される。

このドキュメントはこのプロトコルのあるバージョンについて記述する

3. Conventions

正規記法のための多数の表記規則を使う、このうちのいくつかはこの研究ではかなり特殊

トップレベルとステートバリューから構成される高次の２つの集合は太字の小文字で表示される

関数はギリシャ大文字で表すよ

よく使う関数に関しては、英語の大文字

外部の一般的な処理を関数として表す場合はその手法の名前について

スカラや固定サイズのバイトは普通の小文字で表す

特殊なギリシャ文字もある

任意の長さのシークエンスは一般的に太字の小文字

全面的に、スカラーは非負な整数で、自然数の集合に属する

また、長さを制限した場合は下付き文字にする

[]はインデックスを表す

存在する変数を考慮する場合、著者らはルールを記した

ルールとは、与えられた定義のスコープ内の

最後のアイテムを表す

$ l(x) = x[|x| - 1

4. Blocks, State And Transactions

イーサリアム背後にあるベーシックなコンセプトに関して紹介する

トランザクション、ブロック、ステート

4.1. ワールドステート

ワールドステートはアドレスとアカウントのステート間でのマッピングである

ブロックチェーンに保存はしないで、修正マークルパトリシアツリーとして保存する

このマークルツリーはシンプルなデータベースで提供できる

著者らはこのDBをステートDBと呼んでいる

何個も利点がある

ルートノードはすべての内部データに暗号学的に依存する

このハッシュはシステム全体のステートとしてセキュアなアイデンティティとして使われる

イミュータブルなデータ構造であることはすべての前の状態を許可する

ルートハッシュに応じてシンプルに変わることによって再度コールされる前の状態

そのため、全てのルートハッシュを残している

ナンス

スカラーでトランザクションをそのアドレスが何個送ったか

$ \bold{\sigma}(a)_n

バランス

Weiの残高

$ \bold{\sigma}(a)_b

sotrageRoot

256bitのルートハッシュ

ストレージのコンテンツがエンコードされて保存されたマークルパトリシアツリー

256ビットのintキーのKeccak 256ハッシュ値とRLPエンコードした256ビットの値

$ \bold{\sigma}(a)_s

codeHash

このアカウントのEVMのコードのハッシュ

このアドレスがメッセージを呼び出しを受信される場合に実行されるコード

これは普遍で、他のフィールドとは異なり、チェンジすることができない

すべてのコードの断片はあとで検索するために関連するハッシュ値でステートデータベースに含まれる

私達は望む

ルートハッシュを参照するのではなく、内部に保存されているキーバリューペアの根底にあるものを参照すること

$ \bold{TRIE}(L_1^* (\bold{\sigma} (a)_s)) = \bold{\sigma}(a)_s

$ L_1((k,v)) = (\bold{KEC}(k), \bold{RLP}(v))

$ where

$ k \in \mathbb{B}_{32} \land v \in \mathbb{N}

ときどきノンコントラクトアカウントとして表される

$ L_S(\sigma) = (p(a):\sigma(A) \neq \empty)

$ where

$ p(a) = (\bold{KEC}(a), \bold{RLP}((\sigma(a)_n, \sigma(a)_b, \sigma(a)_s, \sigma(a)_c)))

$ \forall a: \sigma(a) = \empty \lor (a \in \mathbb{B}_{20} \land v(\sigma(a)))

$ v(x) = x_n \in \mathbb{N}_{256} \land x_b \in \mathbb{N}_{256} \land x_s \in \mathbb{N}_{32} \land x_c \in \mathbb{N}_{32}

コードを持たない、ゼロナンス、ゼロバランス場合はアカウントが空である

$ \bold{EMPTY(\sigma, a) = \sigma(a)_c = KEC(())\land \sigma(a)_n = 0 \land \sigma(a)_b = 0}

コンパイル前の呼ぶことができるコントラクトは空アカウントステートを持つことができる

これはそれらのアカウントステートは一般的にコントラクトの振る舞いを記述したコードを含まないためである

アカウントステートが存在しないもしくは空の場合、アカウントは死んでいる

$ \bold{DEAD}(\bold{\sigma}, a) = \sigma(a) = \empty \lor \bold{EMPTY(\sigma, a)}

The Transaction

トランザクションは単一の暗号学的な署名された命令である

↑この命令はイーサリアムのスコープの範囲外でアクター（ユーザーとか）によって構築された

究極の外部的なアクターが自然での人間であると仮定されている場合、ソフトウェア・ツールはその作成と普及に使われる。

２種類のTxがある

メッセージコールでの結果と関連するコードと一緒に新しいアカウントを作るTx

Txフィールド

スカラーバリューで、senderによって送られたトランザクションの何個目かというものを表す：

スカラーバリュー

Wei / gas

gasはトランザクションの実行結果を得るためのすべての計算コストに使用するもの

スカラー

トランザクションを実行するガスの総量

このメッセージの受取人で160bitのアドレス

相手に送るWei

コントラクションを作る場合新しいアカウントを作ることへの寄付

Appendix F参考

コントラクト生成のみ対象

サイズの制限がないバイト列

アカウントを初期化する処理のときにEVMコードによって特定する

initはEVMコードの一部で、ボディを返す

↑ボディとは２つめのコードの一部で、コードとはアカウントがメッセージをコールした毎に実行する内容が示されたもの

initはアカウントが作られるとき一回だけ実行され、その後破棄される

対象的にメッセージTxには↓が含まれている

制限がないバイト列でメッセージのインプットデータが含まれている

↑はトランザクションと送信者をマッピングする

また、SECP-256k1曲線のECDSAから起きる

署名するデータとして、トランザクションのハッシュ値が使われることによって

$ L_T(T) =

$ (T_n, T_p, T_g, T_t, T_v, T_\bold{i}, T_w, T_r, T_s): T_t = \empty

全てのコンポーネントはRLPによって解釈される

$ T_* \in \mathbb{N}_{256}:(* = n,v,p,g,r,s)

$ T_w \in \mathbb{N}_{5}

$ T_d, T_i \in \mathbb{B}

where

これは、20バイトのアドレスハッシュか、コントラクトの生成Txかによる違いがあるため

$ T_t \in

4.3. The Block

イーサリアムのブロックは情報の関連するピースの集まり（ブロックヘッダー）である

と一緒にトランザクションの情報を含み、他のブロックヘッダーの情報を含む

ブロックヘッダーはいくつかの情報から構成される

Keccak 256bitのハッシュで親のブロックヘッダー

Keccak 256bitのハッシュでおじ（祖父の兄弟とかも）とかの関係に位置するブロック

160bit address

このブロックのマイニングが成功した人（報酬をもらうために送られる）

ステートツリーのルートノードのKeccak 256bitハッシュ

すべてのトランザくsyんが実行されたあとに、このルートになる

そのブロックのトランザクションリストによるマークルツリーのルートノードのKeccak 256ビットのハッシュで

Keccac256

ブロックに含まれるトランザクションのレシートのツリーのルートノードのハッシュ

ブルームフィルタ

トランザクションリスト内のそれぞれのトランザクションのレシートから得られるログエントリを含む情報からインデックスすることが可能となる

ブロック生成難易度

ジェネシスブロックを0としたときのブロックナンバー

ガスリミット

現在の1ブロックあたりのガスリミット

このブロックのトランザクションでどの程度ガスが使われたか

合理的なUnixtimetamp

任意のバイトデータ

32バイト以下

256bitのハッシュ

このブロックの上で十分な計算を実施されたかを証明するナンスを含む

64bit value

mix-hashと混ざる

ほかの2つのコンポーネントはシンプルにommerブロックヘッダーとトランザクションのシリーズである

$ B = (B_H, B_{\bold{T}}, B_{\bold{U}})

4.3.1 Transaction Rceipt

ゼロ知識証明を使いインデキシングや検索を便利にすることに関連するトランザクションについての情報をエンコードするために、著者らはトランザクションのレシートエンコードする

↑のトランザクションは明らかに実行結果から得られる情報を含む

↑レシートはインデックスのキーとしてツリーに位置する

トランザクションのレシート、Rは4つのアイテムのタプルである

トランザクションが実行された直後、トランザクションのレシートを含むブロック使用された蓄積したガス

$ R_u

トランザクションの実行中に作られたログの集合

$ R_{\bold{l}}

これらのログの情報から構成されたブルームフィルタ

$ R_{b}

トランザクションのステータスコード

$ R_z

$ R = (R_u, R_b, R_{\bold{l}}, R_z)

RLPシリアライズを用いて

$ L_R(R) = (0 \in \mathbb{B}_{256}, R_u, R_b, R_{\bold{l}})

ステータスコード

使用済み蓄積ガス量は非負整数、ログのブルームフィルタは2048ビットのハッシュ

$ R_u \in \mathbb{N} \land R_b \in \mathbb{B_{256}}

$ O = (O_a, (O_{\bold{t}0}, O_{\bold{t}1}, \cdots), O_{\bold{d}})

$ O_a \in \mathbb{B}_{20} \land \forall_{x\in (O_a) \bigcup O_{\bold{t}}:x \in\mathbb{B}_{32}} \land O_{\bold{d}} \in \mathbb{B}

$ M(O) = \bigvee_{x \in (O_a) \bigcup O_{\bold{t}}}(M_{3:2048}(x))

↑与えられた任意のバイト列から2048のうち３ビットを設定する

これはバイトシーケンスのkec, cak-256ハッシュで、最初の3ペアのバイトのそれぞれ下位11ビットを取ることによってこれを行う

$ \forall_{i\in(0,2,4)} : \bold{\beta}_{m(\bold{x},i)}(\bold{y}) = 1

$ m(\bold{x}, i) = \bold{KEC}(\bold{x})(i,i+1) \mod 2048

4.3.2 Holistic Validity

ブロックの有効性について述べる

いくつかの条件を満たすことで

それは内部的にommerブロックとの整合性が取れてなければならない

$ H_r = \bold{TRIE}(L_S(\Pi(\sigma, B))) \land

$ H_o = \bold{KEC}(\bold{RLP}(L_S^*(B_U))) \land

$ H_t = \bold{TRIE}((\forall i < ||B_{\bold{T}}||, i\in \mathbb{N}:p(i,L_T(B_{\bold{T}}(i))))) \land

$ H_e = \bold{TRIE}((\forall i < ||B_{\bold{R}}||, i\in \mathbb{N}:p(i,L_R(B_{\bold{R}}(i))))) \land

$ H_b = \bigvee_{r\in B_{\bold{R}}}(\bold{r}_b)

$ p(k,v) = (\bold{RLP}(k),\bold{RLP}(v))

さらに

$ \bold{TRIE}(L_S(\sigma)) = P(B_H)_{H_{r}}

トランザクションの計算からブロックしているバリュー特にトランザクションのレシピは定義される

↑トランザクション状態蓄積関数として

$ \Pi(\sigma_t,B) = \sigma_{t+1}

ワールドステートがブロックによって遷移する

$ L_S(\sigma) = (p(a):\sigma(a)\neq\empty)

$ p(a) = (\bold{KEC}(a), \bold{RLP}((\sigma(a)_n, \sigma(a)_b, \sigma(a)_s, \sigma(a)_c)))

すべてのワールドステート内のアドレスを、KECがキーでRLPシリアライズのバリュー形式にした集合

$ \bold{TRIE}(L_I^*(\sigma(a)_s)) = \sigma(a)_s

その、TRIEのハッシュ

ommerブロックのヘッダーをKEC, RLPのKVにして、シリアライゼーションして、KECでハッシュする

要は、ommerブロックのヘッダーをまとめている

$ L_T(T) =

$ (T_n, T_p, T_g, T_t, T_v, T_\bold{i}, T_w, T_r, T_s): T_t = \empty

つまり、ブロック内のトランザクションのKEC・RLPのKVをトランザクションをマークルパトリシアツリーとしたときのルートハッシュ

$ L_R(R) = (0 \in \mathbb{B}_{256}, R_u, R_b, R_{\bold{l}})

つまり、ブロック内のレシートのKEC・RLPのKVをレシートのマークルツリーとしたときのルートハッシュ

4.3.3 Serialisation

$ L_H(H) = (H_*): * = p,o,c,r,h,e,b,d,i,l,g,s,x,m

$ L_B(B)=(L_H(B_H),L_T^*(B_\bold{T}),L_H^*(B_\bold{U}))

$ \bold{where}

$ f^*((x_0,x_1,\ldots)) = (f(x_0),f(x_1),\ldots)

正式なブロックの生成には厳しい条件を備えている

RLP関数は標準メソッドを提供する

↑どんな標準かというと、ある構造をバイト列に変換する標準

↑どんなバイト列かというとワイヤーorローカルストレージに送信する準備ができたもの

4.3.4 Block Header Validity

$ P(H) = B' : \bold{KEC}(\bold{RLP(B'_H)}) = H_p

ブロックナンバーは親ブロックに1足すだけ

$ H_i = P(H)_{H_i} + 1

標準的なディフィカリティ

$ D(H) =

$ where

$ D_0 = 131072

$ x = \lfloor\frac{P(H)_{H_d}}{2048}\rfloor

$ \varsigma_2 = \max(y - \lfloor \frac{H_S - P(H)_{H_S}}{9} \rfloor, -99)

$ y =

$ \epsilon = \lfloor 2^{\lfloor H_i'\div100000 \rfloor -2} \rfloor

$ H_i' = max(H_i - 3000000, 0)

↑ブロック間に時間についてはEIP2で議論されている

ブロック時間の差を増加する

proof of stakeへの時間的圧力になる

この影響はdifficulty bombもしくはice ageはとして知られている

EIP-649で説明されている

修正要素として分母の9を

↑unkcleブロックを平均時間とするために

標準的なガスリミットは下記の関係を満たす

$ H_l < P(H)_{H_l} + \lfloor \frac{P(H)_{H_l}}{1024} \rfloor \land

$ H_l > P(H)_{H_l} - \lfloor \frac{P(H)_{H_l}}{1024} \rfloor \land

$ H_l >= 5000

タイムスタンプは下記を満たす

$ H_s > P(H)_{H_s}

このメカニズムはブロック間の時間を安定させる

２つのブロックの間がより短い期間はディフィカリティのレベルが上がる結果になる

ゆえに、追加の計算量が必要になり、次の期間までが長くなる

逆に、もしピリオドが長すぎる場合は、ディフィカリティは減少し、次のブロックができる時間も減る

ナンスは下記を満たす

$ n <= \frac{2^{256}}{H_d} \land m = H_m

$ \bold{with} : (n,m) = \bold{PoW}(H_{n^*}, H_n, \bold{d})

↑PoWは評価する

1つめのアイテムはミックスハッシュ

正しいDAGかを証明するためのもの

２つめのアイテムは擬似乱数

これはブロックチェーンのセキュリティの財団であり、基本的な理由である

↑のりゆうとは、なぜ攻撃ノードが新しいブロックを作り伝搬できないのかという理由

過去を改変するようなブロック

なぜなら、ナンスは上記条件をみたさなけらばならない

また、この条件はブロックの内容に依存し、それら（トランザクション、新しく作ったブロック、ディフィカリティ、オーバータイム）を変えるならは莫大な計算パワーが必要になる

ゆえに、ブロックヘッダーのバリデーションは下記のように定義できる

$ V(H) =

$ n <= \frac{2^{256}}{H_d} \land m = H_m \land

$ H_d = D(H) \land

$ H_g <= H_l \land

$ H_l < P(H)_{H_l} + \lfloor \frac{P(H)_{H_l}}{1024} \rfloor \land

$ H_l > P(H)_{H_l} - \lfloor \frac{P(H)_{H_l}}{1024} \rfloor \land

$ H_l >= 5000 \land

$ H_s > P(H)_{H_s} \land

$ H_i = P(H)_{H_i} + 1 \land

$ ||H_x|| <= 32

5. GAS AND PAYMENT

ネットワークの乱用問題を防ぐために、すべてのプログラマブルな計算には手数料が発生する

この手数料のスケジュールはガスの単位で特定される

ゆえに、プログラマブルな計算の一部は普遍的に同意されるコストとなる

コントラクトの生成、メッセージコール

すべてのトランザクションは特定のガスの量を持っている

↑のガスはGaslimitに関連する

これは、ガスの量である

↑送信者のバランスから買われたガスの量である

アカウントのbランスが買うことにサポートされない場合は、トランザクションは不正であると考えられる

トランザクションの最後でのすべての未使用ガスは払い戻しされるので、これはガスリミットと呼ばれる

ガスはトランザクションの実行の外では存在しない

ゆえに、トラストなコードに関連するアカウントいとっては、比較的高いガスリミット設定したほうがよいかもしれない

一般的に、イーサはガスを買うために使われる

受診者アドレスへ届けるわけでなく

↑のアカウントのアドレスは通常マイナーの制御下にある

トランザクションの発行者はただである

すべてのガス価格を特定するために

↑トランザクションが選ばれるのを無視するために、マイナーがただだとしても

トランザクション上の高いガスはセンダーのコストになる

より高いEtheを支払わなければならないので

ゆえに、マイナーによってより選ばれやすくなる

マイナーは一般的に、最小のガス価格について宣伝することを選択し、取引者は自由にその価格を決めることができる

最小の承認されるガスプライスの分布が存在するので、トランザクターはトレードオフを保つ必要がある

トレードオフとはガスを低い価格にするか？トランザクションがマイナーによってすぐにブロックにいれられるか

6. Transaction execution

トランザクションの実行はイーサリアムのプロトコルの中でも最も難しいパート

最初に実行されたトランザクションはすべて、本質的妥当性の初期テストに合格すると想定される

下記を含む

トランザクションが整形されたRLPフォーム

トランザクションの署名が正しい

トランザクションのナンスが正しい（送信者のナンスと等しい）

ガスリミットを超えていない

送信者のバランスが最低限ある

トランザクションの実行の定式化

$ \sigma' = \gamma(\sigma, T)

6.1substate

実行中のトランザクションでは、私達は特定の情報を蓄積する

↑情報とは関連するトランザクションがすぐに行動された

$ A = (A_{\bold{s}}, A_{\bold{l}}, A_{\bold{t}}, A_{r})

$ A_{\bold{s}}

自己破壊集合？（self-destruct set）

特定のアカウントの集合

↑のアカウントとはトランザクションの完了後に破棄されるもの

$ A_{\bold{l}}

ログのシリーズ

これはVMコードの実行中でアーカイブしインデックスできるチェックポイントのシリーズ

↑この実行は、Ethereumの世界の外の見物者も追跡することが簡単になるためにコントラクトのコールを許可をする（DappsのFEとか）

$ A_{\bold{t}}

タッチしたアカウントの集合

からのそれらはトランザクションの最後に削除される

$ A_r

払い戻し残高

↑はSSTORE命令を実行することによって増加する

↑コントラクトのストレージを0以外の値から0にリセットするために

すぐには返金されないが、すべての実行コストを部分的にオフセットを持たすことを許す

self-destructs、log、touchedアカウント、払い戻し残高がなにも持っていないために↑を定義した

$ A^0 = (\empty,(),\empty,0)

6.2 Execution

内在的なガスは下記のように定義できる

$ g_0 =

$ + G_{transaction}

↑はコントラクトを作成するトランザクションかメッセージコールかどうかに依存する

$ v_0 = T_g T_p + T_{\bold{v}}

下記のように検証する

$ T_g \leq B_{H1} - l(B_{\bold{R}})_u

トランザクション検証の実行は取り消し不可能で始まる

↑取り消し不可能とはステートを変更すること

コントラクト生成やメッセージコールの計算はステートでの結果となる

↑合法的に現在のステートと等しくなる

この変化は決定的で決して間違えない

$ (\sigma_P,g', A, z) =

gはトランザクションが存在することに対して支払うのに必要なガスを排除した残りのガス

$ g = T_g - g_0

↑EVMのコードから実行されたトランザクションによって直接トリガーされていないメッセージコールやコントラクト生成では送信者が異なる可能性があるため

メッセージコールやコントラクト生成の処理後、リファウンドカウンター（余ったガスとかを再分配）はアカウントに追加しなくてはならない

$ A'_r = A_r + \sum_{i\in A_s}R_{selfdestruct}

そして、ステートはリファウンドさえる量がきまることによって、ファイナライズされる

$ g^* = g' + \min(\lfloor \frac{T_g-g'}{2} \rfloor, A'_r)

ガスのためのEtherはマイナーに与えられる

$ \sigma^*(S(T))_b = \sigma_P(S(T))_b + g^*T_P

$ \sigma^*(m)_b = \sigma_P(m)_b + (T_g-g^*)T_p

$ m = B_{H_c}

$ \sigma' = \sigma^*

$ \forall i \in A_S : \sigma'(i) = \empty

最終的には

$ \gamma^g(\sigma, T) = T_g-g^*

$ \gamma^{\bold{l}}(\sigma, T) = A_{\bold{l}}

$ \gamma^z(\sigma, T) = z

これらはトランザクションのレシートを定義するのを助けるために使われ、最新のステートとナンスのバリデーションに用いられもする

7. Contract Creation

アカウントを作るときに使われる内在敵パラメータはいくつかある

↑から新しいステートとかを生成する

$ (\sigma', g',A,z,\bold{o}) = \Lambda(\sigma, s, o, g, p,v, \bold{i}, e, w)

新しいアカウントのアドレスは送信者と送信者のナンスのRLPエンコーディング＋KECハッシュにした一番左の160ビットである

$ a = B_{96..255}(\bold{KEC}(\bold{RLP}((s, \sigma(s)_n-1))))

最初は

アカウントナンス：１

残高：送られてきた値

storage：空

code hash：空文字のkeccak 256

式（78）〜（82）

送信された後のステート

最終的には初期化EVMコードの実行によってアカウントは初期化される

Sec. 9!

（83）は初期化EVMコードによって、アカウントが初期化されることを表している

(84)〜(92)は初期化コード実行時のパラメータ

インプットのデータはない

コードの実行でガスを使い果たした場合

out-of-gas（OOG）エクセプションが発生すると著者らは呼んでいる

評価されるステートはから集合で定義され、操作全体がステートに対して影響を与えることはない

初期化コードが成功した場合、最終的なコントラクト生成コストはコードデポジットコストを払う（作成したコントラクトのコードのサイズに比例）

もし、ガスが十分でない場合、OOG例外

OOGの場合では、トランザクションのバリューは中止されたコントラクトへ送信されない

OOGが発生しない場合は、残ったガスはコントラクト作成者に再分配される。

(94)〜(97)はガス、最終的なステート、ステータスコードがコントラクト作成後にどうなるかの定式化

ガスは初期化コードからコード実行で使われたコストからコントラクトを生成するコスト（データの永続化）に使用されるガスを引いた分

ステートはアカウントがある場合、コードのハッシュが保存

7.1 Subtleties

初期化コード実行中は新しいアカウントは作られるが、コードはない

ゆえにその最中はなにもメッセージを受け付けても実行できない

もし、初期化コードが実行の終了に自己崩壊がしてしまった場合は、トランザクションを完了する前に、アカウントを削除してしまう。

↑ゾンビアカウントになってしまうので、残っているバランスとかは永久にロックされてしまう。

8. Message Call

メッセージコールの場合は下記パラメータが必要

センダー

トランザクションのオリジン発行者

レシート

実行されるためのコードのアカウント

可能なガス

バリュー

インプットデータ

現在のメッセージコールやコントラクト生成のスタックの深さ

ステートを修正するパーミッション

メッセージコールはアウトプットが追加のコンポーネントとしてある

(98)はメッセージコールによってステートが変化することを表した定式化

(99)は最初のステートにsenderからのレシートを受け取ったステート

(100)〜(105)は↑の仮定も取り入れた式

コントラクト生成と一緒で、例外的な方法でメッセージコールの処理が止まった場合は、ガスは返金されない

(106)〜(120)はメッセージコール実行後のステとの変化に関する式

Ethreumでは、8つの一般的な評価方法で分けられている

↑はprecompiled contractsと呼ばれる

1. 楕円曲線公開鍵復活関数

2. SHA2 256ハッシュスキーマ

3. RIPEMD 160ハッシュスキーマ

4. アイデンティティ関数

5. 冪剰余（べき乗したあとのmで割ったあとのあまり）

6. 楕円曲線の拡張

7. 楕円曲線のスカラー乗算

8. 楕円曲線のペアチェック

9. Execution Model

実行モデルはどのようにシステムのステートは与えられたデータからどのように変化されるのかを特定する

EVM

準チューリッヒ完全

準になっている理由はガスによって計算量が制限されるところから来ている

9.1 Basic

EVMはシンプルなスタックベースアーキテクチャ

word: 256bit

Keccak256、ECDSAに合わせたため

メモリもシンプルなワードアドレスバイトアレイモデル

1024 max

メモリに似ているストレージモデルもある

システムステートの一部を維持している

EVMは一般のノイマン型コンピューターではない

プログラムコードとかはvirtual ROMで保存される

例外時はステートをそのままにはしない

動作止めて、問題をエージェントへレポートする

9.2 Fee Overview

手数料は3パターンで請求される

計算量

支払いとかをするときに早く処理されたい場合

メモリーを拡張する

32バイトごとにメモリのガスフィーを払う

ストレージに関しては払い戻しがされる

ストレージの容量を圧迫することを防ぐために（全額ではないけどね）

9.3 Execution Environment

システムステートと計算ガスの残りかすはの他に実行エージェントは重要なものをもたらす

（121）はシステムステートとガスと↑の要素を実行モデルで実行したあとの結果を表す

9.4 Execution Overview

（123）〜（135）は実行によるステートの遷移について

Xが再帰関数となっており、Oはイテレータ関数

Zは例外時かを判定する

例外判定されない場合まで or Hがマシンが終了するところまで達したことを示す連なりになる場合まで、Xは再帰的に実行される

9.4.1 Machine State

マシーンステート

使用可能ガス

プログラムカウンタ

次の命令を実行するアドレス

メモリ content

メモリー上アクティブなアドレス

0〜

stack content

9.4.2 Exceptional Halting

例外ストップ関数Zを（１３７）は表している

条件としては

ガス量が十分でない

命令が不正

不正なスタックアイテム

JUMP or JUMPIの先が不正

新しいスタックサイズが1024より大きくなってしまう

9.4.3 Jump Destination Validity

アドレスのジャンプ先が正しいか検証する関数

9.4.4 Normal Halting

RETURN、REVERTは特殊

あとは空とかを返す

9.5 The Execution Cycle

Stackのアイテムは左から足されたり消えたり

（143）〜（146）は状態を更新するイテレータ関数

ガスを命令で使うガス分だけ減らす、各ステップで

Self-destructの場合はシステムステートに変化はない

10. Blocktree to blockchain

正規のブロックチェーンはルートリーフを通り全体のブロックツリーのパスを構成する

コンセンサスを得るためにはこの中でも最も重い（計算量のかかった）パスを選ぶ必要あり

blockヘッダーにdifficultyが含まれるので、その合計が最も高いチェーン

11. Block finalisation

4つのステージ

1. オマーブロックの検証

2. トランザクションの検証

3. 報酬の適用

4. ステートとブロックナンスの検証

11.1 Ommer Validation

オマーヘッダーのバリデーションは最大6個前までの関係を検証する

（155）〜(157)

オマーヘッダーは最大で2まで

11.2 Transaction Validation

gasUsedが全てのガスと一致するか

11.3 Reward Application

アプリケーションの報酬はブロックとそれぞれのommerによって決まる

生成しブロックの1/32もらえる

11.4 State & Nonce Validation

ステートのハッシュを求めて、ナンスのバリデーション

11.5 PoW

多くの人がマイニングできないと配布に型月がでるので、２つの特性を保つ必要がある

多くの人が実行可能であること

ASICとかの耐性

super linearではないべき

初期の障壁が高くなるため

ハッシュパワーの偏りがでてしまうため

ASICの耐性は２つある

多くのメモリを必要とする

12. Implementing contracts

12.1 Data Feeds

data feed contractはEthereumの外側とつながることを許可する

12.2 Random Number

13. Future directions

Appendix B Recursive Length Prefix

任意のバイナリデータのエンコーディングのためのserialisationの方法

$ \mathbb{T} = \mathbb{L} \bigcup \mathbb{B}

$ \mathbb{L} = (t:t=(t_0, t_1, \cdots) \land \forall_{n<|t|}t_n \in \mathbb{T} )

$ \mathbb{B} = (b:b=(b_0, b_1, \cdots) \land \forall_{n<|b|}b_n \in \mathbb{O} )

↑１つの葉ではなく

２つのサブ関数で構成されている

1. 値がバイト配列の場合か

2. それ以外の場合

$ \bold{RLP}(x) =

もし、引数がバイト配列の場合、RLPシリアライゼーションは3つの形式のうち１つを取る

1. もしバイト配列が1つのバイトでその値が128以下の場合、インプットとアウトプットは等しい

2. バイト配列が56バイト以下の場合は、そのアウトプットはバイト配列の長さに128を加えたもので始まる＋インプットに等しい

3. それ以外の場合は、出力はインプットにプレフィックスをつけたもの

↑プレフィックスとは、入力のバイト配列の長さと等しいビッグインディアンに解法された最小長

$ R_b(\bold{x}) =

$ \bold{BE}(x) = (b_0, b_1, \cdots):b_o\neq0 \land x = \sum^{n<||\bold{b}||}_{n=0} b_n\cdot 256^{||\bold{b}||-1-n}

$ R_l(x) =

$ s(\bold{x}) = \bold{RLP}(\bold{x}_0)\cdot \bold{RLP}(\bold{x}_1)\cdots

もし、RLPをスカラーに対して使った場合は、ビッグエンディアン解釈の特定の短いバイトになる

ゆえに、いくつかの非負整数では下記のように定義されるRLPは

$ \bold{RLP}(i:i\in\mathbb{N})=\bold{RLP}(\bold{BE}(i))

RLP解釈をする場合、もし、予測された断片がスカラとしてデコードされ、先頭のゼロがバイト配列から発見された場合、クライアントはそれが非標準であることを考慮する必要があり、そうでなければ無効なRLPのデータとして扱う

署名や浮動小数点特定のための標準なエンコードフォーマットはない

Apendix D Modified Markle Patricia Tree

意味わからない

修正版マークルパトリシアツリーは永続的なデータ構造を提供する

↑永続的なデータ構造とは、任意の長さのバイナリデータ間のマッピングをするためのもの

256ビットのバイナリ断片と任意の長さのバイナリデータの間でマッピングするために変更可能なデータ構造の観点で定義される

一般的にはデータベースとして実装される

ツリーのコアは、プロトコルの特定の唯一の要件は一つの値を提供すること

↑一つの値とは与えられたキーバリューの集合を識別するためのもの

↑キーバリューのペアは32バイトのシークエンスか空のバイトシークエンスになるかもしれない

それはプロトコルの効率的かつ効果的な実用を許す方法でツリー構造を保存し、維持するたの実装の考慮事項として残ります

$ \bold{J} = ((\bold{k}_0\in\mathbb{B},\bold{v}_0\in\mathbb{B}),(\bold{k}_1\in\mathbb{B},\bold{v}_1\in\mathbb{B}),\cdots)

シークエンスを考える場合、私達は一般的な記法をすれば下記のようになる

$ \forall_{\bold{I}\in\bold{J}}I = (I_0,I_1)

ビッグエンディアンを想定したもの

$ y(\bold{J}) = ((\bold{k}_0'\in\mathbb{B},\bold{v}_0\in\mathbb{B}),(\bold{k}_1'\in\mathbb{B},\bold{v}_1\in\mathbb{B}),\cdots)

$ \forall_n \forall_{i:i<2||\{bold{k}_n||} \bold{k}_n'(i) =

著者らはTRIEを定義する

↑この構造でエンコードされたとき、この集合を表すツリーのルートを定式化

$ TRIE(\bold{J}) = KEC(c(\bold{J,0}))

また関数nについても定義

↑はツリーのノードのキャパシティの関数

nodeが作られているとき、その構造をエンコードするためにRLPを使う

ストレージの複雑さをへらす手段として、構築されたRLPが32バイト未満のノードに関しては、そのRLPを直接保存する

しかし、それ以外の場合はKeccakハッシュが参照するバイト配列の優先度とする

基数木と同様の方法で、ツリーがルートから葉へ移動する場合、それは一つのキーバリューのペアとなるかもしれない

キーはその道筋を通り蓄積され、ルートからそれぞれの葉ノードの一つのnibleを取得する

radix treeでないような点は、同じプレフィックスでシェアされる複数のキーのケースかユニークなsuffixを持つシングルなキーのケースで２つのノードで最適化されている

ゆえに、横断する場合、あるものはそれおぞれから複数のニブルを潜在的に取得できるかもしれない

Leaf: ２つのアイテム構造

１つそのキーのニブルに対応する

キーの累積とルートから横断されたブランチによってすでに占領されていない

16進数のプレフィックスエンコーディング方法が仕様され、関数の２番めのパラメータはtrue

Extension

２つのアイテムで構築

１つは２以上のサイズのニブルの配列に対応し、ニブルのキーの