forked from chronaeon/beigepaper
-
Notifications
You must be signed in to change notification settings - Fork 12
/
beigepaper.tex
1275 lines (1098 loc) · 78.5 KB
/
beigepaper.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
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
\documentclass[10pt,letterpaper,leqno,bibliography=totoc]{scrartcl}
\usepackage[utf8]{inputenc}
\usepackage{lastpage} %Prints total pages
\usepackage[left=1.3cm,right=1.3cm,top=1.8cm,bottom=4.0cm]{geometry}
\usepackage{amsmath}
\usepackage{amssymb} % Required to include mathematical symbols
\usepackage{makecell}
\usepackage{forest}
\usepackage{boldline}
\usepackage{beton}
\usepackage{booktabs}
\usepackage[T1]{fontenc}
\usepackage[normalem]{ulem}
\usepackage{array}
\usepackage[colorlinks]{hyperref}
\usepackage{graphicx}
\usepackage{multicol}
\usepackage{setspace}
\usepackage[title,titletoc]{appendix}
\usepackage{mathtools}
\usepackage{subfig}
\usepackage{ragged2e}
\usepackage[singlelinecheck=false]{caption}
\usepackage{wrapfig}
\usepackage{IEEEtrantools}
\usepackage{lipsum}
\usepackage[english]{babel}
\usepackage{blindtext}
\usepackage{pgf}
\usepackage{tikz}
\usetikzlibrary{mindmap,arrows,automata,shadows}
\usepackage{epigraph}
\usepackage{tabularx}
\usepackage[perpage]{footmisc}
\usepackage[style=ieee,
backref=true
]{biblatex}
\usepackage{etoolbox}
\usepackage{framed,color}
\usepackage[framemethod=tikz]{mdframed}
\usepackage{minitoc}
\usepackage{fancybox}
\usepackage{tablefootnote}
\usepackage{datatool}
\usepackage{footnote}
\usepackage{pgfkeys}
\usepackage{pgf}
\usepackage{microtype}
\usepackage{enumitem}
\usepackage[acronyms,toc,section=section]{glossaries}
\usepackage{endnotes}
\usepackage{dirtytalk}
\usepackage{pdfpages}
\usepackage{supertabular}
\usepackage{listings}
\usepackage{marginnote}
\usepackage{makeidx}
\makeindex
\usepackage[totoc]{idxlayout}
\usepackage{longtable}
\usepackage{fancyhdr}
\usepackage{array}
\newcolumntype{P}[1]{>{\centering\arraybackslash}p{#1}}
\pagestyle{fancy}
\fancyhf{}
\fancyhead[C]{Beigepaper}
\fancyhead[L]{\rightmark}
\fancyhead[R]{\today--Version 0.7.3}
\fancyfoot[C]{\thepage}
\renewcommand{\headrulewidth}{0.5pt}
\renewcommand{\footrulewidth}{0.5pt}
\renewcommand{\sectionmark}[1]{\markright{\thesection.\ #1}}
\glstoctrue
\newmdenv[shadow=true,shadowcolor=black,font=\sffamily,rightmargin=8pt]{shadedbox}
\definecolor{beige}{RGB}{245,245,220}
\definecolor{lightblue}{RGB}{173,216,230}
\definecolor{aliceblue}{RGB}{240,248,255}
\newcount\n
\n=0
\def\tablebody{}
\makeatletter
\loop\ifnum\n<100
\advance\n by1
\protected@edef\tablebody{\tablebody
\textbf{\number\n.}& shortText
\tabularnewline
}
\repeat
\makeatletter
\let\mcnewpage=\newpage
\newcommand{\TrickSupertabularIntoMulticols}{%
\renewcommand\newpage{%
\if@firstcolumn
\hrule width\linewidth height0pt
\columnbreak
\else
\mcnewpage
\fi
}%
}
\makeatother
%╔═══════════════════DELETED TERMS═════════════════════╗
%║Design Pattern ║
%║Object-Oriented Programming ║
%║External Actor ║
%║Abstract Machine ║
%║Hacker Ethic ║
%╚═════════════════════════════════════════════════════╝
\makenoidxglossaries
\setacronymstyle{long-short}
\newacronym{EVM}{EVM}{Ethereum Virtual Machine}
\newacronym{ERE}{ERE}{Ethereum Runtime Environment}
\newacronym{RLP}{RLP}{Recursive Length Prefix}
\newglossaryentry{serialization}{name={serialization}, description={Serialization is the process of converting an object into a stream of bytes in order to store the object or transmit it to memory, a database, or a file. Its main purpose is to save the machine state of an object in order to be able to recreate it when needed}}
\newglossaryentry{state database}{name={state database},description={A database stored off-chain, [i.e. on the computer of some user running an Ethereum client] which contains a radix tree mapping bytearrays (organized chunks of binary data) to other bytearrays. The \textsl{relationships} between each node on this trie constitutes a \textsc{mapping} of Ethereum's state}}
\newglossaryentry{transaction}{name={transaction}, description={A piece of data, signed by an External Actor. It represents either a Message or a new Autonomous Object. Transactions are recorded into each block of the blockchain}}
\newglossaryentry{Cryptographic hashing functions}{name={Cryptographic hashing functions}, description={Hash functions make secure blockchains possible by establishing universal inputs for which there are limited, usually only one, possible output yet that output is unique}}
\newglossaryentry{state machine}{name={state machine}, description={The term \textsl{State Machine} is reserved for any simple or complex process that moves deterministically from one discrete state to the next}}
\newglossaryentry{addresses}{name={addresses}, description={20 character strings, specifically the rightmost 20 characters of the \texttt{Keccak-256} hash of the RLP-derived mapping which contains the sender's address and the nonce of the block}}
\newglossaryentry{EVM Code}{name={EVM Code}, description={The bytecode that the EVM can natively execute. Used to formally specify the meaning and ramifications of a message to an Account}}
\newglossaryentry{EVM Assembly}{name={EVM Assembly}, description={The human readable version of EVM code}}
\newglossaryentry{Storage State}{name={Storage State}, description={The information particular to a given account that is maintained between the times that the account's associated EVM Code runs}}
\newglossaryentry{Message}{name={Message}, description={Data (as a set of bytes) and Value (specified in Wei) that is passed between two accounts}}
\newglossaryentry{Gas}{name={Gas}, description={The fundamental network cost unit; gas is paid for exclusively by ether}}
\newglossaryentry{Contract}{name={Contract}, description={A piece of EVM Code that may be associated with an Account or an Autonomous Object}}
\newglossaryentry{Ethereum Runtime Environment}{name={Ethereum Runtime Environment}, description={The environment which is provided to an Autonomous Object executing in the EVM. Includes the EVM but also the structure of the world state on which the relies for certain I/O instructions including CALL \& CREATE}}
\newglossaryentry{beneficiary}{name={beneficiary}, description={The 20-character (160-bit) address to which all fees collected from the successful mining of a block are transferred}}
\newglossaryentry{block header}{name={block header}, description={All the information in a block besides transaction information}}
\newglossaryentry{storage root}{name={storage root}, description={One aspect of an \textsc{account's state}: this is the hash of the trie\footnote{A particular path from root to leaf in the state database} that decides the \textsc{storage contents} of the account}}
\newglossaryentry{account state}{name={account state}, description={The state of a particular account--a section of the total world state. Comprises: the \texttt{nonce}, \texttt{balance}, \texttt{storage root}, and \texttt{code hash} of the account}}
\addbibresource{References.bib}
\setcounter{tocdepth}{3}
\setcounter{secnumdepth}{2}
%\makeatletter
%\patchcmd{\footnotetext}{\footnotesize}{\small\sffamily}{}{}
%\makeatother
\def\thesection{\arabic{section}}
%\renewcommand\thesubsection{\thesection\arabic{subsection}}
\setlength\bibitemsep{1.5\itemsep}
\newcommand{\sortitem}[1]{%
\DTLnewrow{list}% Create a new entry
\DTLnewdbentry{list}{description}{#1}% Add entry as description
}
\newenvironment{sortedlist}{%
\DTLifdbexists{list}{\DTLcleardb{list}}{\DTLnewdb{list}}% Create new/discard old list
}{%
\DTLsort{description}{list}% Sort list
\DTLforeach*{list}{\theDesc=description}{%
\item \theDesc}% Print each item
}
\newenvironment{alphafootnotes}
{\par\edef\savedfootnotenumber{\number\value{footnote}}
\renewcommand{\thefootnote}{\alph{footnote}}
\setcounter{footnote}{0}}
{\par\setcounter{footnote}{\savedfootnotenumber}}
\setlength{\columnseprule}{0pt}
\setlength{\columnsep}{5mm}
\hfuzz=0.84074pt
\setcounter{secnumdepth}{3}
\author{\large{\textbf{Micah Dameron}}}
\date{}
\title{\LARGE{Beigepaper: \\ An Ethereum Technical Specification}}
\lstset{linewidth=\columnwidth}
\lstset{backgroundcolor=\color{lightblue}}
\lstset{basicstyle=\ttfamily}
\makeindex
\begin{document}
\setstretch{1.15}
\begin{alphafootnotes}
\pagecolor{beige}
\maketitle
\begin{center}\textbf{Abstract}\end{center}\par
\abstract{The Ethereum Protocol is a deterministic but practically unbounded state-machine with two basic functions; the first being a globally accessible singleton state, and the second being a virtual machine that applies changes to that state. This paper explains the individual parts that make up these two factors.}
\index{pseudocode}
\index{abstract state-machine}
\index{Yellowpaper}
\index{deterministic}
\index{singleton}
\index{virtual machine}
\begin{multicols*}{2}
\TrickSupertabularIntoMulticols
\begin{justify}
\section{Imagining Bitcoin as a Computer}
Ethereum utilizes the distributed ledger model that originated with Bitcoin and repurposes it to model a virtual computer, giving machine level opcodes the same level of certainty as Bitcoin transactions. Just as sure as you can be certain that Bitcoin's ledger is accurate and that timestamps are correct through the Bitcoin \textit{consensus mechanism}, just so sure is it that machine instructions initiated on Ethereum \textit{will} execute.
\index{Bitcoin}
\index{ledger}
\index{opcodes}
\index{certainty}
\index{balance}
\index{timestamped}
\index{machine instructions}
\index{ledger}
In other words, programs executed on the Ethereum Blockchain are \textit{basically} unstoppable. This doesn't mean that Ethereum programs can't have bugs. This means that Ethereum programs can be trusted to execute without any interference from \textit{external} non-network forces. This property arises from the inherent security of the blockchain which is built by, and maintained upon, cryptographic proofs.
\index{unstoppable}
\index{trusted}
\index{executed}
\subsection{Native Currency}
Because Ethereum strives not primarily at the currency application, but at all applications, there is a fundamental \textsl{network cost unit} used to mitigate the possibility of abusing the network with excessive computational expenditures. This is called gas, and is explained fully in \S3. Gas is paid for exclusively in ether. The smallest unit of currency in Ethereum is the Wei, which is equal to $\Xi10^{-18}$, where $\Xi$ stands for 1 ether. All currency transactions in Ethereum, at the machine level, are counted in Wei. There is also the Szabo, which is $\Xi10^{-6}$, and the Finney, which is $\Xi10^{-3}$.
The Ethereum network is subservient to others in terms of one thing only: \textbf{ether}, the native currency for Ethereum. Everything the system can do is bounded up in its ability to expend ether in exchange for gas, which buys a particular amount of system performance in some desired direction.
\index{native currency}
\index{mining}
\index{Wei}
\index{Szabo}
\index{Finney}
\index{ether}
\end{justify}
\raggedright
\begin{tabular}{llr}
\toprule
\textbf{Unit} & \textbf{Ether} & \textbf{Wei} \\
\midrule
\scriptsize{Ether} & \scriptsize{$\Xi$\textbf{1}.000000000000000000} & \scriptsize{1,000,000,000,000,000,000} \\
\scriptsize{Finney} & \scriptsize{$\Xi$0.00\textbf{1}000000000000000} & \scriptsize{1,000,000,000,000,000} \\
\scriptsize{Szabo} & \scriptsize{$\Xi$0.00000\textbf{1}000000000000} & \scriptsize{1,000,000,000,000} \\
\scriptsize{Wei} & \scriptsize{$\Xi$0.00000000000000000\textbf{1}} & \scriptsize{1} \\
\bottomrule
\end{tabular}
\justify
\section{Memory and Storage}
\subsection{World State}
The \textit{world state} is divided by blocks; each new block representing a new world state. The structure of the world state is a mapping of two things:
\begin{enumerate}
\item addresses
\item account states
\end{enumerate}
through the use of the recursive length prefix standard (RLP). This information is stored as a merkle patricia tree in a \textsc{database backend}.\footnote{The database backend is accessed by users through an external application, most likely an Ethereum client; see also: \gls{state database}} that maintains a mapping of bytearrays to bytearrays.\footnote{A bytearray is specific set of bytes [data] that can be loaded into memory. It is a structure for storing binary data, e.g. the contents of a file.}\footnote{This permanent data structure makes it possible to easily recall any previous state with its root hash keeping the resources off-chain and minimizing on-chain storage needs.}As a whole, the state is the sum total of database relationships in the \textbf{ \gls{state database}}.
\index{world state}
\index{mapping}
\index{RLP}
\index{account states}
\index{account addresses}
\subsubsection{Merkle Patricia Trees}
merkle patricia trees are modified merkletrees where nodes represent individual characters from hashes rather than each node representing an entire hash. This allows the state data structure itself to represent not only the intrinsically correct paths in the data, but also the requisite cryptographic proofs which go into making sure that a piece of data was valid in the first place. In other words, it keeps the blockchain valid by combining the structure of a standard merkletree with the structure of a Radix Tree. Since all searching and sorting algorithms in Ethereum must be filtered through this stringently correct database, accuracy of information is guaranteed. \par
\index{merkletrees}
\index{merkle-patricia trees}
\index{merkle-patricia tries}
\index{modified merkletrees}
\index{tree database}
\index{trie database}
\index{data structure}
The following is a search tree beginning with hexadecimal values \texttt{a} and \texttt{4}: \\
\begin{forest}
for tree={
circle,
black,
draw,
fill=blue!40,
}
[{}
[{}, edge label={node [midway, left] {a}}
[{}, edge label={node [midway, left] {2}}
[{}, edge label={node [midway, left] {c}}
[{}, edge label={node [midway, left] {7}}, label=below:a2c7
]
[,phantom]
]
[{}, edge label={node [midway, right] {b}}
[{}, edge label={node [midway, left] {6}}, label=below:a2b6
]
[,phantom]
]
[,phantom]
]
[{}, edge label={node [midway, right] {6}}
[,phantom]
[{}, edge label={node [midway, right] {2}}, label=below:a62
]
]
]
[{}, edge label={node [midway, right] {4}}
[,phantom]
[{}, edge label={node [midway, right] {9}}
[,phantom]
[{}, edge label={node [midway, right] {7}}
[,phantom]
[{}, edge label={node [midway, right] {f}}
[,phantom]
[{}, edge label={node [midway, right] {f}}, label=below:497ff
]
]
]
]
[{}, edge label={node [midway, above right] {a}}
[,phantom]
[{}, edge label={node [midway, right] {c}}
[,phantom]
[{}, edge label={node [midway, right] {9}}
[,phantom]
[{}, edge label={node [midway, right] {5}}, label=below:4ac95
[,phantom]
]
]
]
]
]
]
\end{forest}
\subsection{Tree Terminology\supercite{wiki:xxx}}
\begin{enumerate}[label=\textbf{\alph*})]
\item \textbf{Root Node} -- The top (first) node in a tree.
\item \textbf{Child Node} -- A node directly connected to another node when moving away from the Root.
\item \textbf{Parent Node} -- The converse notion of a child.
\item \textbf{Sibling Nodes} -- A group of nodes with the same parent.
\item \textbf{Descendant Node} -- A node reachable by repeated proceeding from parent to child.
\item \textbf{Ancestor Node} -- A node reachable by repeated proceeding from child to parent.
\item \textbf{Leaf Node} -- A node with no children.
\item \textbf{Branch Node} -- A node with at least one child.
\item \textbf{Degree} -- The number of subtrees of a node.
\item \textbf{Edge} -- The connection between one node and another.
\item \textbf{Path} -- A sequence of nodes and edges connecting a node with a descendant.
\item \textbf{Level} -- The level of a node is defined by 1 + (the number of connections between the node and the root).
\item \textbf{Node Height} -- The height of a node is the number of edges on the longest path between that node and a leaf.
\item \textbf{Tree Height} -- The height of a tree is the height of its root node.
\item \textbf{Depth} -- The depth of a node is the number of edges from the tree's root node to the node.
\item \textbf{Forest} -- A forest is a set of n $\geq 0$ disjoint trees.
\end{enumerate}
\index{root node}
\index{child node}
\index{parent node}
\index{sibling node}
\index{descendant node}
\index{ancestor node}
\index{leaf node}
\index{branch node}
\index{tree degree}
\index{tree edge}
\index{tree path}
\index{tree level}
\index{node height}
\index{tree height}
\index{node depth}
\index{forest}
\hfill
\\
\subsubsection{Recursive Length Prefix Encoding}
Recursive Length Prefix Encoding (RLP) imposes a structure on data that intrinsically considers a prefixed hex value to position the data in the state database tree. This hex value determines the depth of a certain piece of data. There are two types of fundamental items one can encode in RLP:\supercite{jnnk}
\begin{enumerate}
\item Strings of bytes
\item Lists of other items \end{enumerate}
RLP encodes arrays of nested binary data to an arbitrary depth; it is the main serialization method for data in Ethereum. RLP encodes structure of data only, so it does not pay heed to the particular types of data being encoded.
\index{RLP}
\index{nested binary data}
\index{tree arbitrary depth}
Positive RLP integers are represented with the most significant value stored at the lowest memory address (big endian) and without any leading zeroes. As a result, the RLP integer value for \texttt{0} is represented by an empty byte-array. If a non-empty deserialized integer begins with leading zeroes it is invalid.\supercite{EF2017}
\index{RLP integers}
\index{big endian}
\index{no leading zeroes}
\index{empty byte-array}
\index{non empty deserialized integer}
The global state database is encoded as RLP for fast traversal and inspection of data. RLP encoding creates a mapping between \textit{addresses} and \textit{account states}. Since it is stored on node operator's computers, the tree can be indexed and searched without network delay. RLP encodes values as byte-arrays, or as sequences of further values, which are subsequently encoded as byte-arrays. \supercite{Wood2017}
\index{global state database}
\index{speedy traversal of data}
\index{inspection of data}
\index{mapping between addresses}
\index{mapping between account states}
\index{node operator computer}
\index{RLP encodes as byte-arrays}
% The below code demonstrates use of the tabular package to emulate the verbatim, or code listings environment.
%-----------------------------------------------------------------------
% This means that an RLP
% \\
%
% \texttt{%
% \begin{tabular}{ r l c l }
% if & rlp(x) & = & bytearray \\
% then & rlp(bytearray) & = & true \\
% elif & rlp(x) & = & value \\
% then & rlp(value) & = & true \\
% elif & rlp(x) & = & null \\
% then & rlp(x) & = & false \\
% \end{tabular}
% }
% \\~\\
%----------------------------------------------------------------------
\subsection{The Block}
A block is made up of 17 different elements. The first 15 elements are part of what is called the \textsl{block header}.
\index{block composition}
\index{block header}
\subsubsection{The Block Header}
\paragraph{Description}: The information contained in a block besides the transactions list. This consists of:
\begin{enumerate}
\item \textbf{Parent Hash} -- This is the Keccak-256 hash of the parent block's header.
\item \textbf{Ommers Hash} -- This is the Keccak-256 hash of the ommer's list portion of this block.
\item \textbf{Beneficiary} -- This is the 20-byte address to which all block rewards are transferred.
\item \textbf{State Root} -- This is the Keccak-256 hash of the root node of the state trie, after a block and its transactions are finalized.
\index{parent hash}
\index{ommers hash}
\index{beneficiary}
\index{state root}
\index{keccak 256}
\index{block rewards}
\item \textbf{Transactions Root} -- This is the Keccak-256 hash of the root node of the trie structure populated with each transaction from a Block's transaction list.
\item \textbf{Receipts Root} -- This is the Keccak-256 hash of the root node of the trie structure populated with the receipts of each transaction in the transactions list portion of the block.
\item \textbf{Logs Bloom} -- This is the bloom filter composed from indexable information (log address and log topic) contained in the receipt for each transaction in the transactions list portion of a block.
\item \textbf{Difficulty} -- This is the difficulty of this block -- a quantity calculated from the previous block's difficulty and its timestamp.
\index{transactions root}
\index{receipts root}
\index{logs bloom}
\index{difficulty}
\index{keccak 256}
\item \textbf{Number} -- This is a quantity equal to the number of ancestor blocks behind the current block.
\item \textbf{Gas Limit} -- This is a quantity equal to the current maximum gas expenditure per block.
\item \textbf{Gas Used} -- This is a quantity equal to the total gas used in transactions in this block.
\item \textbf{Timestamp} -- This is a record of Unix's time at this block's inception.
\index{number}
\index{gas limit}
\index{gas used}
\index{timestamp}
\index{keccak 256}
\item \textbf{Extra Data} -- This byte-array of size 32 bytes or less contains extra data relevant to this block.
\item \textbf{Mix Hash} -- This is a 32-byte hash that verifies a sufficient amount of computation has been done on this block.
\item \textbf{Nonce} -- This is an 8-byte hash that verifies a sufficient amount of computation has been done on this block.
\item \textbf{Ommer Block Headers} -- These are the same components listed above for any ommers.
\index{extra data}
\index{mix hash}
\index{nonce}
\index{ommer block headers}
\end{enumerate}
\subsubsection{Block Footer}
\item \textbf{Transaction Series} -- This is the only non-header content in the block.
\subsubsection{Block Number and Difficulty}
Note that is the difficulty of the genesis block. The Homestead difficulty parameter, is used to affect a dynamic homeostasis of time between blocks, as the time between blocks varies, as discussed below, as implemented in EIP-2. In the Homestead release, the exponential difficulty symbol, causes the difficulty to slowly increase (every 100,000 blocks) at an exponential rate, and thus increasing the block time difference, and putting time pressure on transitioning to proof-of-stake. This effect, known as the “difficulty bomb”, or “ice age”, was explained in EIP-649 and delayed and implemented earlier in EIP-2, was also modified in EIP-100 with the use of x, the adjustment factor, and the denominator 9, in order to target the mean block time including uncle blocks. Finally, in the Byzantium release, with EIP-649, the ice age was delayed by creating a fake block number, which is obtained by substracting three million from the actual block number, which in other words reduced the time difference between blocks, in order to allow more time to develop proof-of-stake and preventing the network from “freezing” up.\supercite{Wood2017}
\index{block number}
\index{genesis difficulty}
\index{homestead difficulty parameter}
\index{dynamic difficulty homeostasis}
\index{exponential difficulty increase}
\index{difficulty bomb}
\index{byzantium}
\index{ice age}
\index{homestead}
\index{EIP 2}
\index{EIP 100}
\index{EIP 649}
\subsubsection{Account Creation}
Account creation definitively occurs with contract creation. Is related to: \texttt{init}. Lastly, there is the \texttt{body} which is the EVM-code that executes if/when the account containing it receives a message call.
\index{account creation}
\index{contract creation}
\index{account init}
\index{account body}
\subsubsection{Account State}
The account state contains details of any particular account during some specified world state. The account state is made up of four variables:
\index{account state}
\begin{enumerate}
\item \textbf{nonce} The number of transactions sent from this address, or the number of contract creations made by the account associated with this address.
\item \textbf{balance} The amount of \textbf{Wei} \textsc{owned} by this account. Stored as a key/value pair inside the state database.
\item \textbf{storage\_root} A 256-bit (32-byte) hash of the root node of a Merkle Patricia Tree that encodes the storage contents of the account.\footnote{A particular path from root to leaf in the \textbf{\gls{state database}\index{state database}}}
\item \textbf{code\_hash} The hash of the EVM code of this account's contract. Code hashes are \textsc{stored} in the \textbf{\gls{state database}}. Code hashes are permanent and they are executed when the address belonging to that account \textsc{receives} a message call.
\end{enumerate}
\index{account nonce}
\index{account balance}
\index{account storage root}
\index{account code hash}
\index{account balance}
\index{wei}
\index{256 bit}
\index{root node}
\index{leaf node}
\index{state database}
\subsubsection{Bloom Filter}
The Bloom Filter is composed from indexable information (logger address and log topics) contained in each log entry from the receipt of each transaction in the transactions list.
\subsubsection{Transaction Receipts}
\section{Processing and Computation}
\subsection{The Transaction}
The basic method for Ethereum accounts to interact with each other. The transaction is a single cryptographically signed instruction sent to the Ethereum network. There are two types of transactions: \textsc{message calls} and \textsc{contract creations}. Transactions lie at the heart of Ethereum, and are entirely responsible for the dynamism and flexibility of the platform. Transactions are the bread and butter of state transitions, that is of block additions, which contain all of the computation performed in one block. Each transaction applies the execution changes to the \textit{machine state}, a temporary state which consists of all the required changes in computation that must be made before a block is finalized and added to the world state.
\index{transaction}
\index{state transition}
\index{machine state}
\subsubsection{Transactions Root}
\paragraph{Notation}: \texttt{listhash}
\paragraph{Alternatively:} Transactions Root
\paragraph{Description}: The \texttt{Keccak-256} hash of the root node that precedes the \texttt{transactions} in the \texttt{transactions\_list} section of a Block.
\begin{enumerate}
\item \textbf{Nonce} -- The number of transactions sent by the sender.
\item \textbf{Gas Price} -- The number of Wei to pay the network for unit of gas.
\item \textbf{Gas Limit} -- The maximum amount of gas to be used in while executing a transaction.
\item \textbf{To} -- The 20-character recipient of a message call.\footnote{In the case of a contract creation this is 0x000000000000000000.}
\item \textbf{Value} The number of Wei to be transferred to the recipient of a message call.\footnote{In the case of a contract creation, an endowment to the newly created contract account.}
\item \textbf{v, r, s}
\end{enumerate}
\subsection{State Transition Function}
State Transitions come about through the State Transition Function; this is a high-level abstraction of several operations in Ethereum which comprise the overall act of taking changes from the \textit{machine state} and adding them to the world state.
\index{gas price}
\index{gas limit}
\index{to}
\index{value}
\subsection{Mining}
The \texttt{Block Beneficiary} is the 160-bit (20-byte) address to which all fees collected from the successful mining of a block are transferred. \texttt{Apply Rewards} is the third process in \texttt{block\_finalization} that sends the mining reward to an account's address. This is a scalar value corresponding to the difficulty level of a current block.
\subsection{Verification}
The process in The EVM that verifies Ommer Headers
\index{EVM}
\index{verification}
\index{160 bit}
\index{apply rewards}
\index{block beneficiary}
\index{block reward}
\subsection{Sender Function} A description that maps transactions to their sender using \texttt{ECDSA} of the SECP-256k1 curve,
\subsection{Serialization/Deserialization}
This function expands a positive-integer value to a big-endian byte-array of minimal length. When accompanied by a $\cdot$ operator, it signals sequence concatenation. The \texttt{big\_endian} function accompanies RLP serialization and deserialization.
\index{serialization}
\index{deserialization}
\subsection{Ethereum Virtual Machine}
The EVM has a simple stack-based architecture. The word size of the machine and thus size of stack is 256-bit. This was chosen to facilitate the Keccak-256 hash scheme and elliptic-curve based computation. The memory model is a simple word-addressed byte-array. The memory stack has a maximum size of 1024-bits. The machine also has an independent storage model; this is similar in concept to the memory but rather than a byte array, it is a word-addressable word array. Unlike memory, which is volatile, storage is non-volatile and is maintained as part of the system state.
\index{stack based architecture}
\index{stack based}
\index{word size}
\index{256 bit}
\index{memory}
\index{memory size}
\index{keccak 256}
\index{hash scheme}
\index{elliptic curve cryptography}
\index{elliptic curve }
\index{elliptic curve computation}
\index{memory model}
\index{word addressed}
\index{byte array}
\index{memory stack}
\index{machine storage}
\index{storage model}
\index{word array}
\index{word addressable}
\index{memory model volatility of}
\index{system state}
All locations in both storage and memory are well-defined initially as zero. The machine does not follow the standard von Neumann architecture. Rather than storing program code in generally-accessible memory or storage, it is stored separately in a virtual ROM interactable only through specialized instructions.
\index{well defined storage}
\index{well defined memory}
\index{non-standard architecture}
\index{virtual ROM}
The machine can have exceptional execution for several reasons, including stack underflows and invalid instructions. Like the out-of-gas exception, they do not leave state changes intact. Rather, the machine halts immediately and reports the issue to the execution agent (either the transaction processor or, recursively, the spawning execution environment) which will deal with it separately.
\index{exceptional halt}
\index{stack underflow}
\index{invalid instruction}
\index{out-of-gas}
\index{state unchanged}
\index{machine halt}
\index{report exception}
\subsubsection{Fees} Fees (denominated in gas) are charged under \textsc{three} distinct circumstances, all three as prerequisite to the execution of an operation.\supercite{Wood2017} The \textbf{first} and most common is \textsl{the fee intrinsic to the computation of the operation}. \textbf{Secondly}, gas may be deducted \textsl{in order to form the payment for a subordinate message call or contract creation}; this forms part of the payment for the CREATE, CALL and CALLCODE operations. \textbf{Finally}, \textsl{gas may be paid due to an increase in the usage of the memory.}
\index{fees}
\index{gas}
\index{execution}
\index{computation of operation}
\index{gas deducted}
\index{payment}
\index{message call}
\index{gas paid for increased use of memory}
Over an account’s execution, the total fee for memory-usage payable is proportional to smallest multiple of 32 bytes that are required such that all memory indices (whether for read or write) are included in the range. This is paid for on a just-in-time basis; as such, referencing an area of memory at least 32 bytes greater than any previously indexed memory will certainly result in an additional memory usage fee. Due to this fee it is highly unlikely that addresses will trend above 32-bit bounds.\supercite{Wood2017}
\index{total fee}
\index{memory usage fee}
Implementations must be able to manage this eventuality. Storage fees have a slightly nuanced behaviour to incentivize minimization of the use of storage (which corresponds directly to a larger state database on all nodes), the execution fee for an operation that clears an entry in the storage is not only waived, a qualified refund is given; in fact, this refund is effectively paid up-front since the initial usage of a storage location costs substantially more than normal usage. \supercite{Wood2017}
\index{gas price}
\index{minimize storage use}
\index{gas refund clearing space}
\subsection{Execution}
The execution of a transaction defines the state transition function: \texttt{stf}. However, before any transaction can be executed it needs to go through the initial tests of intrinsic validity.
\index{intrinsic validity}
\subsubsection{Intrinsic Validity}
The criteria for intrinsic validity are as follows:
\begin{itemize}
\item The transaction follows the rules for \textsl{well-formed RLP} (recursive length prefix.)
\item The \textsl{signature} on the transaction is valid.
\item The \textsl{nonce} on the transaction is valid, i.e. it is equivalent to the sender account's current nonce.
\item The \texttt{gas\_limit} is greater than or equal to the \texttt{intrinsic\_gas} used by the transaction.
\item The sender's account balance contains the cost required in up-front payment.
\end{itemize}
\index{well-formed RLP}
\index{transaction signature}
\index{transaction nonce}
\index{gas limit}
\index{sender account}
\index{upfront payment}
\subsubsection{Transaction Receipt}
While the amount of gas used in the execution and the accrued log items belonging to the transaction are stored, information concering the result of a transaction's execution is stored in the transaction receipt \texttt{tx\_receipt}. The set of log events which are created through the execution of the transaction, \texttt{logs\_set} in addition to the bloom filter which contains the actual information from those log events \texttt{logs\_bloom} are located in the transaction receipt. In addition, the post-transaction state \texttt{post\_transaction(state)} and the amount of gas used in the block containing the transaction receipt post(gas\_used) are stored in the transaction receipt. As a result, the transaction receipt is a record of any given \texttt{execution}.
\index{gas used}
\index{transaction receipt}
\index{log items}
\index{log events}
\index{transaction execution}
\index{post transaction state}
A valid transaction execution begins with a permanent change to the state: the nonce of the sender account is increased by one and the balance is decreased by the \texttt{collateral\_gas}\footnote{Designated ``\texttt{intrinsic\_gas}'' in the Yellowpaper} which is the amount of gas a transaction is required to pay prior to its execution. The original transactor will differ from the sender if the message call or contract creation comes from a contract account executing code.
After a transaction is executed, there comes a \textsc{provisional state}, which is a pre-final state. Gas used for the execution of individual EVM opcodes prior to their potential addition to the \texttt{world\_state} creates:
\begin{itemize}
\item provisional state
\item \texttt{intrinsic gas}, and
\item an associated substate
\end{itemize}
\begin{itemize}
\item The accounts tagged for self-destruction following the transaction's completion. \texttt{self\_destruct(accounts)}
\item The \texttt{logs\_series}, which creates checkpoints in EVM code execution for frontend applications to explore, and is made up of the\texttt{logs\_set} and \texttt{logs\_bloom} from the \texttt{tx\_receipt}.
\item The refund balance.\footnote{The \textsc{sstore} operation increases the amount refunded by resetting contract storage to zero from some non-zero state.}
\end{itemize}
Code execution always depletes \texttt{gas}. If gas runs out, an out-of-gas error is signaled (\texttt{oog}) and the resulting state defines itself as an empty set; it has no effect on the world state. This describes the transactional nature of Ethereum. In order to affect the \textsc{world state}, a transaction must go through completely or not at all.
\subsubsection{Code Deposit}
If the initialization code completes successfully, a final contract-creation cost is paid, the code-deposit cost, \textsc{c}, proportional to the size of the created contract's code.
\subsubsection{Execution Model}
\paragraph{Basics}: The stack-based \textsl{virtual machine} which lies at the heart of the Ethereum and performs the actions of a computer. This is actually an instantial runtime that executes several substates, as EVM computation instances, before adding the finished result, all calculations having been completed, to the final state via the \texttt{finalization function}.
In addition to the \texttt{system state} and the \texttt{remaining gas} for computation there are several pieces of important information used in the execution environment that the execution agent must provide:
\index{system state}
\index{remaining gas}
\index{stack based}
\index{virtual machine}
\index{instantial runtime}
\index{substates}
\index{evm computation instances}
\index{finalization function}
\index{execution environment}
\begin{itemize}
\item \texttt{account\_address}, the address of the account which owns the code that is executing.
\item \texttt{sender\_address} the sender address of the transaction that originated this execution.
\item \texttt{originator\_price} the price of gas in the transaction that originated this execution.
\item \texttt{input\_data}, a byte array that is the input data to this execution; if the execution agent is a transaction, this would be the transaction data.
\item \texttt{account\_address} 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.
\item \texttt{newstate\_value} the value, in Wei, passed to this account if the execution agent is a transaction, this would be the transaction value.\supercite{Wood2017}
\item \texttt{code array} the byte array that is the machine code to be executed.\supercite{Wood2017}
\item \texttt{block\_header} the block header of the present block.
\item \texttt{stack\_depth} 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).\supercite{Wood2017}
\end{itemize}
\index{account address}
\index{sender address}
\index{originator price}
\index{input data}
\index{account address}
\index{newstate value}
\index{code array}
\index{block header}
The execution model defines the \texttt{state\_transition function}, which can compute the \texttt{resultant state}, the \texttt{remaining\_gas}, the \texttt{accrued\_substate} and the \texttt{resultant\_output}, given these definitions. For the present context, we will define it where the accrued substate is defined as the tuple of the \texttt{self-destructs\_set}, the \texttt{log\_series}, the \texttt{touched\_accounts} and the \texttt{refunds}.\supercite{Wood2017}
\index{execution model}
\index{state transition function}
\index{resultant state}
\index{remaining gas}
\index{accrued substate}
\index{resultant output}
\index{self-destructs set}
\index{log series}
\index{touched accounts}
\index{refunds}
\subsubsection{Execution Overview} The \texttt{execution\_function}, in most practical implementations, \textbf{will be modeled as an iterative progression of the pair comprising the full \texttt{system\_state} and the \texttt{machine\_state}.} It's defined recursively with the \texttt{iterator\_function}, which defines the result of a single cycle of the state machine, together with the \texttt{halting\_check} function, which determines if the present state is an exceptional halting state of the machine and \texttt{output\_data} of the instruction if the present state is a \texttt{controlled\_halt} of the machine. An empty sequence/series indicates that execution should halt, while the empty set indicates that execution should continue.
\index{execution function}
\index{iterative progression}
\index{iterator function}
\index{state machine cycle}
\index{halting function}
\index{halting state}
When evaluating execution, we extract the remaining gas from the resultant machine state. It is thus cycled (recursively or with an iterative loop) until either \texttt{exceptional\_halt} becomes true indicating that the present state is exceptional and that the machine must be halted and any changes discarded or until H becomes a series (rather than the empty set) indicating that the machine has reached a controlled halt.
\index{extract remaining gas}
\index{exceptional halt}
The machine state is defined as the tuple which are the \textbf{gas available}, \textbf{the program counter}, \textbf{the memory contents}, \textbf{the active number of words in memory} (counting continuously from position 0), \textbf{and the stack contents}. The memory contents are a series of zeroes of size $2^{256}$.\supercite{Wood2017}
\subsubsection{The Execution Cycle} Stack items are added or removed from the left-most, lower-indexed portion of the series; all other items remain unchanged: The gas is reduced by the instruction’s gas cost and for most instructions, the program counter increments on each cycle, for the three exceptions, we assume a function J, subscripted by one of two instructions, which evaluates to the according value: otherwise In general, we assume the memory, self-destruct set and system state don’t change: however, instructions do typically alter one or several components of these values.
\paragraph{Provisional State}
A smaller, temporary state that is generated during transaction execution. It contains three sets of data.\footnote{The final state is reached after deleting all accounts that either appear in the self-destruct list or are touched and empty.}
\subsubsection{Message Calls}
A message call can come from a transaction or internally from contract code execution. It contains the field \textsc{data}, which consists of user data input to a message call. Messages allow communication between accounts (whether contract or external.) Messages can come in the form of \texttt{msg\_calls} which give output data. If it is a contract account, this code gets executed when the account receives a message call. Message calls and contract creations are both \textsl{transactions}, but contract creations are never considered the same as message calls. Message calls always transfer some amount of value to another account. If the message call is an account creation transaction then the value given takes on the role of an endowment towards the new account. Every time an account receives a message call it returns the \texttt{body}, something which is triggered by the \texttt{init} function. User data input to a \texttt{message\_call}, structured as an unlimited size byte-array.
\index{init}
\index{message call}
\paragraph{Universal Gas}Message calls always have a universally agreed-upon cost in gas. There is a strong distinction between contract creation transactions and message call transactions. Computation performed, whether it is a contract creation or a message call, represents the currently legal valid state. There can be no invalid transactions from this point. \supercite{Wood2017} There is also a message call/contract creation \textit{stack}. This stack has a depth, depending on how many transactions are in it. Contract creations and message calls have entirely different ways of executing, and are entirely different in their roles in Ethereum. The concepts can be conflated. Message calls can result in computation that occurs in the next state rather than the current one. If an account that is currently executing receives a message call, no code will execute, because the account might exist but has no code in it yet. To execute a message call transactions are required:
\index{universal gas}
\index{contract creation transactions}
\index{message call transactions}
\index{computation}
\index{valid state}
\begin{itemize}
\item \texttt{sender}
\item \texttt{transaction originator}
\item \texttt{recipient}
\item \texttt{account} (usually the same as the recipient)
\item \texttt{available gas}
\item \texttt{value}
\item \texttt{gas price}
\item An arbitrary length byte-array. \texttt{arb array}
\item \texttt{present depth} of the message call/contract creation stack.
\end{itemize}
\index{sender}
\index{transaction originator}
\index{recipient}
\index{account}
\index{available gas}
\index{value}
\index{gas price}
\index{arbitrary length byte-array}
\index{present depth}
\index{contract creation stack}
\index{message call}
\subsubsection{Contract Creation}
To initiate contract creation you need to send transaction to \texttt{nothing}. This executes \textsc{init} and returns the \textsc{body}. Init is executed only once at \textsc{account\_creation}, and permanently discarded after that.
\index{contract creation}
\index{init}
\index{body}
\index{account creation}
\index{empty byte-sequence}
\subsubsection{Execution Environment}
The Ethereum Runtime Environment is the environment under which Autonomous Objects execute in the EVM: the EVM runs as a part of this environment.
\index{ere}
\index{ethereum runtime environment}
\index{autonomous objects}
\subsubsection{Big Endian Function} This function expands a positive-integer value to a big-endian byte array of minimal length. When accompanied by a $\cdot$ operator, it signals sequence concatenation. The \texttt{big\_endian} function accompanies RLP serialization and deserialization.
\index{big endian function}
\index{positive integer}
\index{sequence concatenation}
\index{rlp}
\index{serialization}
\index{deserialization}
\subsection{Gas}
Gas is the fundamental network cost unit converted to and from ether as needed to complete the transaction while it is sent. Gas is arbitrarily determined at the moment it is needed, by the block and according to the total network's miners decision to charge certain fees. Each miner choose individually which gas prices they want to accept and which they want to reject.
\index{miner choice}
\index{arbitrarily determined}
\index{gas}
\index{network cost unit}
\subsubsection{Gas Price/Gas Limit}
\texttt{Gas price} is a value equal to the current limit of gas expenditure per block, according to the miners. Any unused gas is refunded to the sender. The canonical gas limit of a block is expressed and is stabilized by the \texttt{time\_stamp} of the block.
\index{value}
\index{gas expenditure per block}
\index{miners}
\index{unused gas}
\index{refunded}
\index{canonical gas}
\index{time stamp}
\index{block}
\paragraph{Gas Price Stability}
Where \texttt{new\_header} is the new block’s header, but without the nonce and mix-hash components, d being the current DAG, a large data set needed to compute the mix-hash, and PoW is the proof-of-work function this evaluates to an array with the first item being the mix-hash, to prove that a correct DAG has been used, and the second item being a pseudo-random number cryptographically dependent on it. Given an approximately uniform distribution in the range the expected time to find a solution is proportional to the difficulty.\supercite{Wood2017}
\index{DAG}
\index{mix hash}
\index{correct DAG}
\index{difficulty}
This is the foundation of the security of the blockchain and is the fundamental reason why a malicious node cannot propagate newly created blocks that would otherwise overwrite (“rewrite”) history. Because the nonce must satisfy this requirement, and because its satisfaction depends on the contents of the block and in turn its composed transactions, creating new, valid, blocks is difficult and, over time, requires approximately the total compute power of the trustworthy portion of the mining peers. Thus we are able to define the block header validity function.
\index{block header validity function}
\index{nonce}
\index{block contents}
\paragraph{Gasused}
A value equal to the total gas used in transactions in this block.
\index{gas used}
\subsubsection{Machine State}
The machine state is a tuple consisting of five elements:
\begin{enumerate}
\item \texttt{gas\_available}
\item \texttt{program\_counter}
\item \texttt{memory\_contents} A series of zeroes of size $2^{256}$
\item \texttt{memory\_words.count}
\item \texttt{stack\_contents}
\end{enumerate}
\index{machine state}
\index{gas available}
\index{program counter}
\index{memory contents}
\index{memory word count}
\index{stack contents}
There is also, \texttt[to\_execute]: the current operation to be executed
\index{to execute}
\subsubsection{Exceptional Halting}
An exceptional halt may be caused by four conditions existing on the stack with regard to the next opcode in line for execution:
\begin{verbatim}
if
out_of_gas = true
or
bad_instruction = true
or
bad_stack_size = true
or
bad_jumpdest = true
then throw exception
else exec opcode x
then init control_halt
\end{verbatim}
Exceptional halts are reserved for opcodes that fail to execute. They can never be caused through an opcode's actual execution.
\begin{itemize}
\item The amount of remaining gas in each transaction is extracted from information contained in the \texttt{machine\_state}
\item A simple iterative recursive loop\supercite{Wood2017} with a Boolean value:
\begin{itemize}
\item\textbf{true} indicating that in the run of computation, an exception was signaled
\item\textbf{false} indicating in the run of computation, no exceptions were signaled. If this value remains false for the duration of the execution until the set of transactions becomes a series (rather than an empty set.) This means that the machine has reached a controlled halt.
\end{itemize}
\end{itemize}
\index{controlled halt}
\index{transaction series}
\index{empty set}
\paragraph{Substate}
A smaller, temporary state that is generated during transaction execution and runs parallel to \texttt{machine state}. It contains three sets of data:
\begin{itemize}
\item The accounts tagged for self-destruction following the transaction's completion. \texttt{self\_destruct(accounts)}
\item The \texttt{logs\_series}, which creates checkpoints in EVM code execution for frontend applications to explore, and is made up of the\texttt{logs\_set} and \texttt{l
ogs\_bloom} from the \texttt{tx\_receipt}.
\item The refund balance.\footnote{The \textsc{sstore} operation increases the amount refunded by resetting contract storage to zero from some non-zero state.}
\end{itemize}
\index{tagged for self destruction}
\index{logs series}
\index{checkpoints}
\index{logs set}
\index{logs bloom}
\index{transaction receipt}
\subsubsection{EVM Code}
The bytecode that the EVM can natively execute. Used to explicitly specify the meaning of a message to an account. A \texttt{contract} is a piece of EVM Code that may be associated with an Account or an Autonomous Object. \textbf{EVM Assembly} is the human readable version of EVM Code.
\index{EVM code}
\index{natively execute}
\index{EVM assembly}
\index{explicitly specify meaning}
\subsection{Blocktree to Blockchain}
The canonical blockchain is a path from root to leaf through the entire block tree. In order to have consensus over which path it is, conceptually we identify the path that has had the most computation done upon it, or, the heaviest path. Clearly one factor that helps determine the heaviest path is the block number of the leaf, equivalent to the number of blocks, not counting the unmined genesis block, in the path. The longer the path, the greater the total mining effort that must have been done in order to arrive at the leaf. This is akin to existing schemes, such as that employed in Bitcoin-derived protocols. Since a block header includes the difficulty, the header alone is enough to validate the computation done. Any block contributes toward the total computation or total difficulty of a chain. Thus we define the total difficulty of \texttt{this\_block} recursively by the difficulty of its parent block and the block itself.
\index{canonical blockchain}
\index{heaviest path}
\index{block number}
\index{genesis block}
\index{mining effort}
\index{totaly difficulty}
The jobs of miners and validators are as follows: \texttt{Validate (or, if mining, determine) ommers; validate (or, if mining, determine) transactions; apply rewards; verify (or, if mining, compute a valid) state and nonce.}
\index{compute valid state}
\index{compute valid nonce}
\subsection{Ommer Validation} The validation of ommer headers means nothing more than verifying that each ommer header is both a valid header and satisfies the relation of Nth-generation ommer to the present block. The maximum of ommer headers is two.
\index{ommer validation}
\index{ommer headers}
\index{valid header}
\subsection{Transaction Validation} The given gasUsed must correspond faithfully to the transactions listed, the total gas used in the block, must be equal to the accumulated gas used according to the final transaction.
\index{transaction validation}
\index{gas used}
\index{transactions}
\index{total gas used}
\index{accumulated gas used}
\subsection{Reward Application} The application of rewards to a block involves raising the balance of the accounts of the beneficiary address of the block and each ommer by a certain amount. We raise the block’s beneficiary account; for each ommer, we raise the block’s beneficiary by 1 an additional 32 of the block reward and the beneficiary of the ommer gets rewarded depending on the block number. This constitutes the \texttt{block\_finalization state\_transition\_function.} If there are collisions of the beneficiary addresses between ommers and the block two ommers with the same beneficiary address or an ommer with the same beneficiary address as the present block,
\index{apply rewards}
\index{beneficiary address}
\index{ommer}
\index{block reward}
\index{block number}
\index{block finalization state transition function}
\index{collisions}
additions are applied cumulatively. The block reward is three ether per block.
/paragraph{State \& Nonce Validation} The function that maps a block B to its initiation state, that is,the hash of the root node of a trie of state x. This value is stored in the state database trivial and efficient since the trie is by nature a resilient data structure. And finally define the \texttt{block\_transition\_function}, which maps an incomplete block to a complete block with a specified dataset. As specified at the beginning of the present work, the \texttt{state\_transition\_function}, which is defined in terms of, the \texttt{block\_finalisation\_function} and, the \texttt{transaction\_evaluation\_function}. As previously detailed, there is the nth corresponding status code, logs and cumulative gas used after each transaction, the fourth component in the tuple, has already been defined in terms of the logs).
\index{nonce validation}
\index{incomplete block}
\index{complete block}
\index{status code}
\index{cumulative gas}
\paragraph{}The nth state is given from applying the corresponding transaction to the state resulting from the previous transaction (or the block’s initial state in the case of the first BYZANTIUM VERSION 3475aa8 -- 2018-01-26 14 such transaction): otherwise in certain cases there is a similar approach defining each item as the gas used in evaluating the corresponding transaction summed with the previous item (or zero, if it is the first), giving us a running total: the function is used that was defined in the transaction execution function. Finally \texttt{new state} exists in the context of the \texttt{block reward function} applied to the final transaction’s \texttt{resultant state}, thus the complete block-transition mechanism, less PoW, the proof-of-work function is defined.
\index{transaction execution function}
\index{block reward function}
\subsection{Mining Proof-of-Work} Proof that a certain amount of mining has been done exists as a cryptographic probability statement which asserts beyond reasonable doubt that a particular amount of computation has been expended in the determination of some token value \texttt{pow\_token}. It is utilised to enforce the security of the blockchain. Since mined blocks produce a reward, the proof-of-work also serves as a wealth distribution mechanism. For this reason, the proof of work function is designed to be as accessible as possible to as many people as possible.
\index{proof-of-work}
\index{probability statement}
A very basic application of this principle of accessibility is found in combining the traditional Proof-of-Work function with a \textit{Memory-Hardness function}. By forcing the hashing algorithm to use memory as well as CPU, miners are more likely to use computers than ASICs, meaning that ASIC efficiency will not obsolete the person who wants to mine on their home computer from participating in the mining process. To make the Ethereum Blockchain ASIC resistant, the Proof-of-Work mechanism has been designed to be sequential and memory-hard. This means that the nonce requires high amounts of memory and bandwidth such that the memory cannot be used in parallel to discover multiple nonces simultaneously. Therefore, the proof-of-work function takes the form of $2^{256}$ the new block’s header but without the nonce and mix-hash components. There is the \texttt{header\_nonce}, and \texttt{data\_set} which are required to compute the mix hash and \texttt{block\_difficulty}, the difficulty value of the new block. The proof-of-work function evaluates to an array with the first item being the mix hash and the second item being a pseudorandom number which is cryptographically dependent on the \texttt{header\_nonce} and the \texttt{data\_set}. The name for this algorithm is \textbf{Ethash}.
\subsubsection{Ethash: Seed$\rightarrow$Cache$\rightarrow$Dataset$\rightarrow$Slice}
\index{asic resistant}
\index{ethash}
\index{mix hash}
Ethash is the Proof-of-Work algorithm which was used to launch the Ethereum network and bring it through its first few releases. It is in the process of being gradually phased out and replaced with a Proof-of-Stake model. For now it is the latest version of Dagger-Hashimoto, introduced by Vitalik Buterin. The general route that the algorithm takes is as follows: There exists a seed which can be computed for each block by scanning through the block headers up until that point. From the seed, one can compute a pseudorandom \texttt{cache}, that is \textsc{cache\_init} bytes in initial size. Light clients store the cache. From the cache, a dataset is generated, \texttt{dataset\_size} bytes in initial size, with the property that each item in the dataset depends on only a small number of items from the cache. Full clients and miners store the dataset. The dataset grows linearly with time. Mining involves grabbing random slices of the dataset and hashing them together. Verification can be done with low memory by using the cache to regenerate the specific pieces of the dataset that you need, so you only need to store the cache. The large dataset is updated once every 1 \textsc{epoch} (10,000) blocks, so the vast majority of a miner’s effort is spent on reading the dataset, rather than on making changes to it.
\index{seed}
\index{cache}
\index{dataset}
\index{slice}