-
Notifications
You must be signed in to change notification settings - Fork 24
/
Copy pathYPCheatSheet.tex
231 lines (207 loc) · 14.3 KB
/
YPCheatSheet.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
\documentclass[9pt,oneside]{amsart}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage[a4paper,width=170mm,top=18mm,bottom=22mm,includeheadfoot]{geometry}
\usepackage{booktabs}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{longtable}
\usepackage{array}
\definecolor{lightyellow}{rgb}{1,0.98,0.9}
\begin{document}
\pagecolor{lightyellow}
\section{Conventions}
\center
\newcolumntype{L}[1]{>{\raggedright\let\newline\\\arraybackslash\hspace{0pt}}p{#1}}
\begin{tabular}{L{0.25\linewidth}L{0.25\linewidth}L{0.3\linewidth}}
\toprule
\textbf{Item} & \textbf{Convention} & \textbf{Examples} \\
\midrule
Top level structures & Lower case bold Greek & $\boldsymbol{\sigma}$, the world state\newline $\boldsymbol{\mu}$, the machine state. \\
\midrule
Functions on highly structured values & Upper case Greek & $\Upsilon$, the Ethereum state transition function. \\
\midrule
Most functions & Upper case letters, possibly subscripted & $C$, the general cost function\newline $C_\text{\tiny SSTORE}$, the cost function for the {\tiny SSTORE} operation. \\
\midrule
Specialised functions & Typewriter & $\texttt{KEC}$, the Keccak-256 hash\newline $\texttt{KEC512}$, the Keccak-512 hash function. \\
\midrule
Tuple & Upper case letter & $T$, a transaction. \\
\midrule
Component of a Tuple & Subscripted upper-case letter.\newline A capital subscript refers to a component that is a tuple. & $T_n$, the transaction nonce\newline $I_H$, The header of the current block (a tuple). \\
\midrule
Scalars, fixed size byte sequences/arrays & Usually a lower-case letter Sometimes Greek & $n$, a transaction's nonce\newline $\delta$, the number of stack items required. \\
\midrule
Arbitrary length sequences & Bold lower-case & $\mathbf{o}$, output data of message call. \\
\midrule
Sets & Double struck capitals & $\mathbb{P}_{256}$, positive integers less than $2^{256}$\newline $\mathbb{B}_{32}$, byte sequences of length $32$. \\
\midrule
Components or subsequences of sequences & Square brackets & $\boldsymbol{\mu}_\mathbf{s}[0]$, the first item on the stack\newline $\boldsymbol{\mu}_\mathbf{m}[0..31]$ the first $32$ items in memory. \\
\midrule
Modified (and utilisable) value & Prime mark & $g'$ gas remaining. \\
\midrule
Intermediate values & Asterisk superscripts & $g^*$ gas to be refunded\newline $g^{**}$ available gas remaining after code execution.\\
\midrule
Element-wise transformations & Asterisk superscript on a function & $f^*\big((x_0, x_1, ...) \big) \equiv \big( f(x_0), f(x_1), ... \big)$ for any function $f$. \\
\bottomrule
\end{tabular}
\endcenter
\vspace{7pt}
\section{Symbols}
\begin{longtable}{p{0.10\linewidth}p{0.85\linewidth}}
\toprule
Name & Description \\
\midrule
\endhead
\multicolumn{2}{l}{\textbf{High level constructs}} \\*[5pt]
$\boldsymbol{\sigma}$ & The world-state, comprising all accounts' nonces, balances, storage and code. \\
$\boldsymbol{\sigma}_t$ & World-state at time $t$. \\
$\boldsymbol{\mu}$ & Machine-state tuple, $(g, pc, \mathbf{m}, i, \mathbf{s})$, which are gas, program counter, memory, memory size, stack. \\
$T$ & An Ethereum transaction \\
$T_0$, $T_1$, ... & Individual transactions within a block \\
$B$ & A block: $B \equiv (..., (T_0, T_1, ...) )$ \\
$\Upsilon$ & The Ethereum state transition function: $\boldsymbol{\sigma}_{t+1} \equiv \Upsilon(\boldsymbol{\sigma}_t, T)$ \\
$\Omega$ & The block-finalisation state transition function (pays out the mining reward). \\
$\Pi$ & The block-level state-accumulation function: $\Pi(\boldsymbol{\sigma}, B) \equiv \Omega(B, \Upsilon(\Upsilon(\boldsymbol{\sigma}, T_0), T_1) ...)$ \\
\vspace{5pt} \\
\midrule
\multicolumn{2}{l}{\textbf{World state}} \\*[5pt]
$\boldsymbol{\sigma}[a]$ & The account state of account $a$, being a tuple of (nonce, balance, storageRoot, codeHash). \\
$\boldsymbol{\sigma}[a]_n$ & The nonce of account $a$. \\
$\boldsymbol{\sigma}[a]_b$ & The balance of account $a$. \\
$\boldsymbol{\sigma}[a]_s$ & A 256-bit hash of the root node of a Merkle Patricia tree that encodes the storage contents of account $a$. Note that $\texttt{\small TRIE}\big(L_I^*(\boldsymbol{\sigma}[a]_\mathbf{s})\big) \equiv \boldsymbol{\sigma}[a]_s$ \\
$\boldsymbol{\sigma}[a]_c$ & The hash of the EVM code of account $a$. Equal to $\texttt{\small KEC}(\mathbf{b})$ where $\mathbf{b}$ is the account's code.\\
\vspace{5pt} \\
\midrule
\multicolumn{2}{l}{\textbf{Machine state}} \\*[5pt]
$\boldsymbol{\mu}_g$ & The gas available. \\
$\boldsymbol{\mu}_{pc}$ & The program counter. \\
$\boldsymbol{\mu}_\mathbf{m}$ & The memory contents. \\
$\boldsymbol{\mu}_i$ & The number of memory words allocated. \\
$\boldsymbol{\mu}_\mathbf{s}$ & The stack. \\
$\boldsymbol{\mu}_\mathbf{s}[n]$ & Item at stack depth $n$. \\
\vspace{5pt} \\
\midrule
\multicolumn{2}{l}{\textbf{Substate}} \\*[5pt]
$A$ & A Transaction substate during execution: $A \equiv (A_\mathbf{s}, A_\mathbf{l}, A_\mathbf{t}, A_r) \equiv (\mathbf{s}, \mathbf{l}, \mathbf{t}, r)$. \\
$A_\mathbf{s}$ & The self-destruct set. These accounts will be discarded following the transaction's completion. \\
$A_\mathbf{l}$ & The log series. \\
$A_\mathbf{t}$ & The set of touched accounts. Empty ones are deleted at the end of the transaction.\\
$A_r$ & The gas refund balance. Can partially offset execution costs.\\
$A^0$ & The empty substate: $A^0 \equiv (\varnothing, (), \varnothing, 0)$. \\
\vspace{5pt} \\
\midrule
\multicolumn{2}{l}{\textbf{Execution environment}} \\*[5pt]
$I$ & Tuple of the following items provided to the execution environment. \\
$I_a$ & The address of the account which owns the code that is executing. \\
$I_o$ & The sender address of the transaction that originated this execution. \\
$I_p$ & The price of gas in the transaction that originated this execution. \\
$I_\mathbf{d}$ & The byte array that is the input data to this execution; if the execution agent is a transaction, this would be the transaction data. \\
$I_s$ & The address of the account which caused the code to be executing; if the execution agent is a transaction, this would be the transaction sender. \\
$I_v$ & The value, in Wei, passed to this account as part of the same procedure as execution; if the execution agent is a transaction, this would be the transaction value. \\
$I_\mathbf{b}$ & The byte array that is the machine code to be executed. \\
$I_H$ & The block header of the present block. \\
$I_e$ & The depth of the present message-call or contract-creation (i.e. the number of {\small CALL}s or {\small CREATE}s being executed at present). \\
$I_w$ & Flag for permission to make modifications to the state. See EIP-214, STATICCALL \\
\vspace{5pt} \\
\multicolumn{2}{l}{Execution} \\*[5pt]
$\Xi$ & The code execution function $(\boldsymbol{\sigma}', g', A, \mathbf{o}) \equiv \Xi(\boldsymbol{\sigma}, g, I)$. \\
$\mathbf{o}$ & The output data of a message call, $\mathbf{o} \equiv H(\boldsymbol{\mu}, I)$.\newline At contract creation, the contract bytecode to be deployed. \\
$\mathbf{i}$ & The initialisation EVM code for newly deployed contract (contract constructor). \\
$H(\boldsymbol{\mu}, I)$ & The normal halting function, usually the value provided by the RETURN or REVERT opcodes, or empty in the case of STOP. \\
$Z(\boldsymbol{\sigma}, \boldsymbol{\mu}, I)$ & The exceptional halting function. \\
$w$ & The current operation to be executed: $w \equiv I_\mathbf{b}[\boldsymbol{\mu}_{pc}]$ if $\boldsymbol{\mu}_{pc} < \lVert I_\mathbf{b} \rVert$, and \small{STOP} otherwise. \\
\vspace{5pt} \\
\midrule
\multicolumn{2}{l}{\textbf{Blocks}} \\*[5pt]
$B$ & A block: $B \equiv (B_H, B_\mathbf{T}, B_\mathbf{U}).$ \\
$B_H$ & The block's header. \\
$B_\mathbf{T}$ & The block's transactions. \\
$B_\mathbf{U}$ & Headers of ommer/uncle blocks of this block. \\
$B_\mathbf{R}$ & Transaction receipts. \\
$D(H)$ & The difficulty of the block with header $H$. \\
$P(H)$ & The parent block of the block with header $H$. \\
$V(H)$ & The block header validity function. \\
\vspace{5pt} \\
\multicolumn{2}{l}{Block header} \\*[5pt]
$H_p$ & \textbf{parentHash}: The Keccak 256-bit hash of the parent block's header, in its entirety. \\
$H_o$ & \textbf{ommersHash} The Keccak 256-bit hash of the ommers list portion of this block. \\
$H_c$ & \textbf{beneficiary} The 160-bit address to which all fees collected from the successful mining of this block be transferred. \\
$H_r$ & \textbf{stateRoot} The Keccak 256-bit hash of the root node of the state trie, after all transactions are executed and finalisations applied. \\
$H_t$ & \textbf{transactionsRoot} The Keccak 256-bit hash of the root node of the trie structure populated with each transaction in the transactions list portion of the block. \\
$H_e$ & \textbf{receiptsRoot} The Keccak 256-bit hash of the root node of the trie structure populated with the receipts of each transaction in the transactions list portion of the block. \\
$H_b$ & \textbf{logsBloom} The Bloom filter composed from indexable information (logger address and log topics) contained in each log entry from the receipt of each transaction in the transactions list. \\
$H_d$ & \textbf{difficulty} A scalar value corresponding to the difficulty level of this block. \\
$H_i$ & \textbf{number} A scalar value equal to the number of ancestor blocks. The genesis block has a number of zero. \\
$H_l$ & \textbf{gasLimit} A scalar value equal to the current limit of gas expenditure per block. \\
$H_g$ & \textbf{gasUsed} A scalar value equal to the total gas used in transactions in this block. \\
$H_s$ & \textbf{timestamp} A scalar value equal to the reasonable output of Unix's time() at this block's inception. \\
$H_x$ & \textbf{extraData} An arbitrary byte array containing data relevant to this block. This must be 32 bytes or fewer. \\
$H_m$ & \textbf{mixHash} A 256-bit hash which proves combined with the nonce that a sufficient amount of computation has been carried out on this block. \\
$H_n$ & \textbf{nonce} A 64-bit hash which proves combined with the mix-hash that a sufficient amount of computation has been carried out on this block. \\
\vspace{5pt} \\
\midrule
\multicolumn{2}{l}{\textbf{Transactions}} \\*[5pt]
$T_n$ & Transaction nonce. \\
$T_p$ & Gas price for the transaction. \\
$T_g$ & The maximum gas for a transaction. \\
$T_t$ & The ``to'' address for the transaction. \\
$T_v$ & The value to be transferred by the transaction. \\
$T_w$, $T_r$, $T_s$ & The $v$, $r$, $s$ values of the transaction signature. \\
$T_\mathbf{i}$ & EVM-code for account initialisation (i.e. contract deployment). \\
$T_\mathbf{d}$ & Input data of a message call. \\
$S(T)$ & Sender function---recovers the sender address from the transaction: \newline $S(T) \equiv \mathcal{B}_{96..255}\big(\mathtt{KEC}\big( \mathtt{ECDSARECOVER}(h(T), T_w, T_r, T_s) \big) \big).$ \\
\vspace{5pt} \\
\multicolumn{2}{l}{Transaction Receipt} \\*[5pt]
$R$ & A transaction receipt: $R \equiv (R_z, R_u, R_b, R_\mathbf{l})$ \\
$R_z$ & The status code of the transaction. \\
$R_u$ & The cumulative gas used so far in the block. \\
$R_b$ & The bloom filter composed from the information in the transaction logs. \\
$R_\mathbf{l}$ & The log entries created by the transaction, $(O_0, O_1, ...)$. \\
$O$ & A log entry: $O \equiv (O_a, ({O_\mathbf{t}}_0, {O_\mathbf{t}}_1, ...), O_\mathbf{d})$. \\
$O_a$ & The logger's address. \\
$O_\mathbf{t}$ & A 32-byte log topic. \\
$O_\mathbf{d}$ & The log data for this entry. \\
$\Upsilon^g$ & The total gas used in this transaction. \\
$\Upsilon^\mathbf{l}$ & The logs created by this transaction. \\
$\Upsilon^z$ & The status code of this transaction, $z$. \\
\vspace{5pt} \\
\midrule
\multicolumn{2}{l}{\textbf{Miscellaneous functions}} \\*[5pt]
$\ell(\mathbf{x})$ & The last item in sequence $\mathbf{x}$: $\ell(\mathbf{x}) \equiv \mathbf{x}[\lVert \mathbf{x} \rVert - 1]$ \\
$L(n)$ & The ``all but one 64th'' function: $L(n) \equiv n - \lfloor n / 64 \rfloor$.\\
$L_I\big( (k, v) \big)$ & Representation of key--value pairs in the trie: $L_I\big( (k, v) \big) \equiv \big(\texttt{KEC}(k), \texttt{RLP}(v)\big)$ \\
$L_R$ & TODO \\
$L_S$ & World-state collapse function. TODO: expand. Seems to have a different function in computing the message hash.\\
$L_T$ & TODO \\
$M(s, f, l)$ & Memory expansion function. $s$ is the current top of memory; $f$ is the start of writing; $l$ is the number of bytes to be written. \\
$\mathcal{B}$ & Bit reference function such that $\mathcal{B}_j(\mathbf{x})$ equals the bit of index $j$ (indexed from 0) in the byte array $\mathbf{x}$ \\
$\mathtt{EMPTY}(\boldsymbol{\sigma}, a)$ & An account $a$ is \textit{empty} when it has no code, zero nonce and zero balance, $\boldsymbol{\sigma}[a]_c = \texttt{\small KEC}\big(()\big) \wedge \boldsymbol{\sigma}[a]_n = 0 \wedge \boldsymbol{\sigma}[a]_b = 0$. \\
$\mathtt{DEAD}(\boldsymbol{\sigma}, a)$ & An account $a$ is \textit{dead} when its account state is non-existent or empty: $\varnothing \vee \mathtt{EMPTY}(\boldsymbol{\sigma}, a)$. \\
$\mathtt{TRIE}$ & The root hash of the Merkle Patricia tree constructed from its arguments. \\
$\mathtt{KEC}$ & TODO \\
$\mathtt{RLP}$ & TODO \\
$\mathtt{PoW}$ & TODO \\
\vspace{5pt} \\
\midrule
\multicolumn{2}{l}{\textbf{Operators and symbols}} \\*[5pt]
$\lVert ... \rVert$, $| ... |$ & Length of a sequence. These seem to be used interchangeably, but I may have missed something. \\
$\wedge$ & Logical ``And''. \\
$\vee$ & Logical ``Or''. \\
$\varnothing$ & The empty set. \\
$\cdot$ & Concatenation, $(a, b, c, d) \cdot e \equiv (a, b, c, d, e)$, or scalar multiplication depending on context. \\
\vspace{5pt} \\
\midrule
\multicolumn{2}{l}{\textbf{Todo}} \\*[5pt]
$\mathbb{B}$ & The set of all sequences of bytes. \\
$\mathbb{B}_n$ & The set of all byte sequences of length $n$ bytes: $\mathbb{B}_n = \{ B: B \in \mathbb{B} \wedge \lVert B \rVert = n \}$ \\
$\mathbb{P}$ & The set of positive integers [what's wrong with $\mathbb{N}$??? Grrr...]. \\
$\mathbb{P}_n$ & The set of all positive integers smaller than $2^n$: $\mathbb{P}_n = \{ P: P \in \mathbb{P} \wedge P < 2^n \}$ \\
$M_{3:2048}$ & Specialised Bloom filter. \\
$\Lambda(...)$ & Contract creation function. \\
$\Theta(...)$ & ``Message call''/contract execution function? Not very clearly defined anywhere, but used extensively. \\
$\Gamma(B)$ & The ``initiation state'' of block $B$. Usually $\boldsymbol{\sigma}_i: \mathtt{TRIE}(L_S(\boldsymbol{\sigma}_i)) = {P(B_H)_H}_r$. \\
$\Psi(B)$ & A block transition function that maps an incomplete block $B$ to a complete block $B'$ (adds in mixHash, nonce, stateRoot). \\
$r(...)$ & Calculates stateRoot? Used once but not defined. \\
\textit{etc.} \\
\bottomrule
\end{longtable}
\end{document}