-
Notifications
You must be signed in to change notification settings - Fork 3
/
Copy pathspec.html
2181 lines (1816 loc) · 84.1 KB
/
spec.html
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
<!DOCTYPE html>
<html>
<head>
<meta charset='utf-8'>
<title>EBFT Consensus Algorithm Specification v1</title>
<script
src='https://www.w3.org/Tools/respec/respec-w3c-common'
class='remove'></script>
<style>
table, th, td {
border: 1px solid black;
border-collapse: collapse;
}
th, td {
padding: 5px;
}
code {
font-family: georgia, serif;
color: black;
font-size: 105%;
}
</style>
</head>
<body>
<section id='abstract'>
This document, the EBFT Consensus Algorithm Specification, describes a
<a>Proof of Authority</a> (PoA) <a>Byzantine Fault Tolerant</a> (BFT) blockchain
consensus protocol suited for eventually synchronous networks.
The Enterprise Byzantine Fault Tolerant (EBFT) protocol builds on the IBFT
blockchain consensus protocol ([[IBFT]] and [[Quorum]]), retaining all of its
original features, plus addresses safety and liveness limitations described in a
previous work [[IBFT-Analysis]].
</section>
<section id='sotd'>
*This section describes the status of this document at the time of its
publication. Newer documents might supersede this document.*
This is an editors' draft of the EBFT Consensus Algorithm Specification
version 1, with a number of items still to be addressed, including, but limited
to:
- Add pseudocode for the algorithm to determine the validator set.
- Add pseudocode for the algorithm to the block proposer.
- Replace abstract data structures with concrete data structures, if possible.
- Integrate the agreed improvements in the EEA protocol specification.
Extra para.
</section>
<section id="sec-introduction" class="informative">
<h2>Introduction</h2>
The EBFT protocol is a <a>Proof of Authority</a> (PoA)
<a>Byzantine Fault Tolerant</a> (BFT) blockchain consensus protocol enabling
consortium networks to leverage on the capabilities of
<a>Ethereum smart contracts</a>. The protocol:
- Ensures <a>immediate finality</a>.
- Is <a>robust</a> in an <a>eventually synchronous network</a> model.
- Features a <a>dynamic validator set</a>.
The EBFT protocol builds on the IBFT protocol ([[IBFT]] and [[Quorum]]),
inheriting all its properties while addressing the following limitations
described by Saltini [[IBFT-Analysis]]:
<ul>
<li>
<a>Persistence</a> is not guaranteed:
<ul>
<li>
One Byzantine <a>validator</a> is potentially able to remove a transaction or
change the position of a finalized transaction.
</li>
<li>
In a network of six <a>validators</a>, even if all <a>validators</a> are honest,
a network partitioning can cause the blockchains maintained by two sets of three
<a>validators</a> each to diverge. After the partitioning is resolved,
<a>validators</a> have to choose one chain, which means removing or reordering
transactions of the other chain.
</li>
<li>
The IBFT protocol does not guarantee that a transaction added to the local
blockchain of one <a>validator</a> is eventually added to the local blockchain
of all other nodes.
</li>
</ul>
</li>
<li>
<a>Liveness</a> is not guaranteed. Specifically, the IBFT protocol might reach a
state where no new blocks can be added to any local blockchain, which means that
no new transactions can be added to the distributed ledger.
</li>
</ul>
</section>
<section id="conformance">
</section>
<section id="sec-terminology" class="informative">
<h2>Terminology</h2>
This section outlines the terminology used to describe the EBFT protocol.
<dl>
<dt><dfn data-lt="validator">Validators</dfn></dt>
<dd>
Multiple nodes participating in the EBFT protocol to finalize blocks on
the chain.
</dd>
<dt><dfn data-lt="proposers">Proposer</dfn></dt>
<dd>
A <a>validator</a> that proposes a block. Only one node acts as a proposer for
any given <a>round</a> and <a>height</a>.
</dd>
<dt><dfn data-lt="standard nodes|node|nodes">Standard node</dfn></dt>
<dd>
A node that does not propose or validate blocks.
</dd>
<dt>Blockchain consensus protocol</dt>
<dd>
Blockchains are the most widely-adopted implementations of <em>distributed
ledgers</em>, which are append-only databases of transactions that are
replicated across multiple participants and where the trust and responsibility
for maintaining the database is spread across all, or a subset of, the
participants.<br>
This is in contrast to traditional centralized systems where full trust is given
to a central authority responsible for maintaining the database. One issue with
this traditional approach is that the central authority has the power to alter
the database unilaterally. The decentralisation aspect of distributed ledger
technology makes it well suited in situations where the central authority is
either adding costs to the system or undermining trust in the system itself.
Blockchains implement distributed ledgers by batching transactions into blocks
and cryptographically linking each block to the previous one forming a chain of
blocks. Consensus protocols play a fundamental role in the blockchain technology
as they responsible for ensuring that the chain of blocks replicated amongst the
participants is consistent. The type of network and environment assumptions made
when designing a consensus protocol influence how the blockchain performs after
it is deployed in a real environment and network. Some of the key performance
metrics that are heavily influenced by consensus protocols are:
<ul>
<li>
<dfn>Throughput</dfn>. For example, the number of transactions per second.
</li>
<li>
<dfn>Latency</dfn>. That is, time taken from when a transaction is submitted to
the system to when the transaction is included in a block.
</li>
<li>
<a>Robustness</a>. That is, what type of attacks the protocol can withstand.
</li>
</ul>
</dd>
<dt><dfn data-lt="ethereum smart contract">Ethereum smart contracts</dfn></dt>
<dd>
Compared to Bitcoin, which was the first widely adopted blockchain and mainly
allows transferring values between participants, the Ethereum blockchain
specifies a Turing-complete language that can be used to build small distributed
programs, called <em>smart contracts</em>. Smart contracts are executed on a
sandboxed runtime on any participant on execution of transactions. The
availability of a Turing-complete language allows users to specify a custom set
of rules and behavior associated with any transaction referring a specific smart
contract.
</dd>
<dt><dfn data-lt="bft">Byzantine fault tolerant</dfn> (BFT)</dt>
<dd>
Byzantine fault tolerant, or BFT, specifies the type of participant fault mode
that the consensus protocol can cope with. Specifically, BFT identifies a class
of consensus protocols that ensure blockchain consistency despite some of the
participants, referred to as Byzantine, being malicious and acting arbitrarily.
The term <dfn>Byzantine</dfn> is used to identify malicious nodes, and dates
back to the "The [[Byzantine-Generals-Problem]]" paper. The Byzantine failure
mode is the strongest failure mode considered in the consensus protocol
literature. Another common, but weaker, failure mode is fail-stop failure mode,
which only considers participants that stop communicating, but never acting
maliciously.
</dd>
<dt><dfn data-lt="poa">Proof of Authority</dfn> (PoA)</dt>
<dd>
Another way to classify consensus protocols is by the technique used to prevent
Sybil attacks. A Sybil attack is where a participant is able able to gain power
in the system by creating multiple pseudonymous identities. Typically, creating
a new digital identity that can be used to interact with a blockchain is
relatively cheap because it only requires generating a random private key and
the related public key, which can be done in a matter of seconds on any modern
personal computer.<br>
One of the most widely used and famous techniques for preventing Sybil attacks
is Proof of Work ([[PoW]]), which was originally pioneered by Dwork et al., and
gained subsequent publicity by its employment in Bitcoin. PoW requires
participants to spend computing effort in solving a hard cryptographic puzzle
before being able to propose a block to be added to the blockchain.
<dfn data-lt="pos">Proof of Stake</dfn> (PoS) is another well known technique
where the right to propose new blocks is given by the amount of stake owned.
In contrast, PoA prevents Sybil attacks by conferring the right to create new
blocks only to a defined set of identities.
</dd>
<dt>Consortium blockchains</dt>
<dd>
Compared to permissionless, or public, blockchains, like Bitcoin or Ethereum,
where anybody can join the network and participate in the protocol, in
consortium blockchains permissioning exists, which enables only a set of
participants to propose new blocks and to participate in the consensus
protocol.<br>
PoA type consensus protocols, like EBFT, are well suited to this type of
permissioning. While not every participant can propose new blocks, some
consortium blockchains allow any valid blockchain identity to read data from the
blockchain. EBFT also allows for this type of configuration.
</dd>
<dt><dfn>Immediate Finality</dfn></dt>
<dd>
A transaction is deemed to be <em>final</em> after it is included in the
blockchain and it cannot be removed, except if the environment is compromised. A
compromise can occur, for example, if the number of Byzantine participants is
higher than the maximum number the protocol can withstand.<br>
Immediate finality means that as soon as a transaction is included in a block,
the protocol guarantees that the transaction will not be removed.
By comparison, the PoW consensus protocol in Bitcoin and Ethereum only
guarantees eventual probabilistic finality, where the deeper a transaction is in
the blockchain, the less probable that the transaction can be removed or have
its position changed. Casper FFG, the Ethereum 2.0 PoS consensus protocol,
provides eventual non-probabilistic finality, where transactions eventually
reach a state where they cannot be removed or have their position changed, but
this does not necessarily happen at every block.
</dd>
<dt>Robust in an eventually synchronous network</dt>
<dd>
<dfn data-lt="robust">Robustness</dfn> refers to two important properties that
any blockchain consensus protocol must provide:
<ul>
<li>
<dfn>Persistence</dfn>, which ensures consistency of the blockchain amongst all
participants.
</li>
<li>
<dfn>Liveness</dfn>, which ensures that transactions submitted to participants
will eventually be included in the blockchain.
</ul>
</ul>
An <dfn>eventually synchronous network</dfn> identifies a network model under
which <a>robustness</a> of the protocol can be assured. In literature, there are
three main network models that were considered, which differ on the assumptions
made on transmission latency:
<ul>
<li>
Synchronous networks. The maximum latency (the time required for a message to
reach its recipient) is bounded and known.
</li>
<li>
Asynchronous networks. The maximum latency is unknown and messages might never
be delivered.
</li>
<li>
Partially synchronous networks. This model lies in between synchronous and
asynchronous. Specifically, there are two possible definitions of partial
synchronous networks:
<ul>
<li>
Messages are guaranteed to be delivered, but the maximum latency is unknown. To
the best of our knowledge, no specific name is defined for this model.
</li>
<li>
Eventually synchronous networks where there exists a point in time, called
global stabilisation time (GST) after which the message delay is bounded by a
finite and constant value.
</li>
</ul>
</li>
</ul>
The model with the weakest assumptions is the asynchronous network model,
followed by the partially synchronous network model and then the synchronous
network model, in this order. Between the two definitions of partial synchronous
networks, eventual synchrony is the one with the weaker assumptions. As proved
by Fischer et al. [[One-Faulty-Process]] in 1985, no consensus protocol that
aims to tolerate at least one fail-stop participant is guaranteed to terminate
in the model with the weakest assumptions (asynchronous network model). This
means that the <a>liveness</a> property introduced above would be impaired in
this model. There exist solutions that operate in the asynchronous network
model, but the termination is only guaranteed probabilistically. The EBFT
protocol is therefore <a>robust</a> in the network model with the weakest
assumptions coming after the asynchronous network model.
</dd>
<dt><dfn>Dynamic validator set</dfn></dt>
<dd>
Compared to classic (non-blockchain) consensus protocols where the set of
participants is known in advance and never changes, EBFT, like Clique,
allows participants to add and remove <a>validators</a> by a voting mechanism.
</section>
<section id="eea-protocol-overview">
<h2>EBFT Protocol Overview</h2>
As is common to any blockchain implementation, each EBFT node maintains a local
copy of the blockchain where the first block, the <dfn>genesis block</dfn>, is
the same for all nodes.
Each block $B$ added to the blockchain must be cryptographically linked to
another block in the blockchain, $B_p$, which is defined as the
<dfn>parent</dfn> of block $B$. Conversely, $B$ is defined as the
<dfn>child</dfn> of $B_p$.
In EBFT, starting from the <a>genesis block</a>, the next block to be added to
the local blockchain maintained by a node is the <a>child</a> of the block that
was previously added to the blockchain. In this way, the EBFT blockchain can be
modelled as a linked list of blocks, instead of a tree, like in the public
Ethereum blockchain. In alignment with common terminology used in literature,
the <dfn>height</dfn> of a block in a blockchain is defined as the number of
parent links separating the block from the genesis block. The
<a>genesis block</a> has therefore height 0.
The EBFT protocols can be modelled as running sequential instances of what are
called the <em>EBFT-block-finalization-protocol</em>, where the objective of the
$h$-th instance of the EBFT-block-finalization-protocol is to decide which
Ethereum block, and consequently which set of transactions, are to be added at
height $h$ of the blockchain maintained by any EBFT node.
Only a subset of the entire set of EBFT nodes can participate in the $h$-th
instance of the block finalization protocol. This set of nodes are called the
<em><a>validators</a></em> for height/instance h</em> and refer to each member
of this set as a <em><a>validator</a> for height/instance h</em>. All of the
nodes not included in the <a>validator</a> set for height/instance
$h$ are referred to as <a>standard nodes</a>. In statements about
<a>validators</a> where it is clear from the context, we often omit
<em>for height/instance h</em>. The set of <a>validators</a> for each instance
$h$ of the EBFT-block-finalization-protocol is deterministically computed as a
function of the chain of blocks from the <a>genesis block</a> to the block with
height $h-1$.
Each instance of the EBFT-block-finalization-protocol is organized in
<dfn data-lt="round">rounds</dfn>. In each round, one of the <a>validators</a>
(referred to as the <a>proposer</a>)
is responsible for proposing an Ethereum block for the height associated with
the specific instance of the EBFT-block-finalization-protocol that the
<a>validators</a> is running. After agreement is reached, the
EBFT-block-finalization-protocol creates a finalized block, which includes
the Ethereum block and additional information that allows any node, even nodes
that did not participate in the EBFT-block-finalization-protocol, to verify
that agreement on the Ethereum block included in the finalized block was
correctly added.
In practice, each EBFT node adds finalized blocks to its local blockchain.
In this way, any node joining the
network at any point in time, when synching its local blockchain with its peers,
receives all the information required to verify that agreement was reached
correctly on each block that it receives, even on those created before it joined
the network.
Each Ethereum block can carry a vote, cast by the proposer of that block, to add
a <a>validator</a> to or remove a <a>validator</a> from the <a>validator</a>
set. When more than half of the <a>validators</a> cast a consistent vote to add
or remove a <a>validator</a> to or from the <a>validator</a> set, the
<a>validator</a> is added or removed from the validator set starting from the
next block and all of the votes targeting this <a>validator</a> are discarded.
<p class="note">The exact definition of the algorithm for calculating the
validator set is missing from the current version of this specification and
must be added at some point before finalization of the document.</p>
</section>
<section id="eea-protocol-specification">
<h2>EBFT Protocol Specification</h2>
This section provides a detailed specification of the EBFT protocol.
<section id="algorithm-convensions">
<h3>Algorithm Conventions</h3>
The EBFT protocol algorithms are textually described in Sections
<a href="#algorithm-1-description"></a> and
<a href="#ibft2-block-finalization-protocol"></a>, and by the pseudocode in
Section <a href="#algorithm-pseudocode"></a>. The following
conventions are used:
<ul>
<li>
Statements are expressed in a mathematical form, but with standard
mathematical symbols replaced by their English equivalent. For example,
$\mathbf{in}$ instead of $\in$, $\mathbf{and}$ instead of $\land$,
$\mathbf{there\;exists}$ instead of $\exists$, and so on. The intent is to
provide an unambiguous definition of the protocol that can be understood by
people not familiar with standard mathematical notation.
</li>
<li>
Comments identified by
<code style="color:green;">text in green typewriter font</code> are used to
provide a natural language description of pseudocode statements that might not
be immediately obvious.
</li>
<li>
For brevity of notation, using individual existential quantifiers
(for example, $\exists$ in mathematical notation and $\mathbf{there\;exists}$ in
English notation) for message fields is avoided, but instead expressed as
existential quantifiers on the entire message. An overhead line (for example
$\overline{var}$) is used to indicate message fields that, if the extensive
notation was used, then they should be expressed using an
existential quantifier. For example, $\mathbf{there\;exists}$
$\langle{f_1,}\overline{f_2}\rangle$ $\mathbf{in}$ ${receivedMessages_v}$
stands for $\mathbf{there\;exists}$ $f_2$ $\mathbf{such\;that\;there\;exists}$
$\langle{f_1,f_2}\rangle\in{receivedMessages_v}$.
</li>
<li>
Each of the $\mathbf{upon}$ blocks in the pseudocode is assumed to be executed
atomically when the condition specified after the $\mathbf{upon}$ keyword is
satisfied.
</li>
<li>
All functions in <code>typewriter font</code> are defined in the remainder of
this section.
</li>
<li>
All functions in ${italic\;font}$ are defined in the pseudocode.
</li>
<li>
${receivedMessages_v}$ corresponds to the set of all messages received by node
$v$.
</li>
<li>
$\mathtt{peers}_v$ corresponds to the set of DEVp2p Gossip protocol peers of
$v$;
</li>
<li>
$\{m\in{V}$ $\mathbf{such\;that}$ $P(m)\}$ corresponds to the set of all the
elements of $V$ for which predicate $P$ is true.
</li>
<li>
$\{F(m)$ $\mathbf{such\;that}$ $m\in{V}$ $\mathbf{and}$ $P(m)\}$ corresponds
to the set obtained by applying the function $F$ to all the elements of $V$ for
which predicate $P$ is true.
</li>
<li>
$\mathtt{allSubSetsOf}(M)$ corresponds to the set of all of the subsets of
$M$, which is usually called the power set of $M$. For example,
$\mathtt{allSubSetsOf}(\{m_1,m_2,m_3\})$ corresponds to the set
$\{\{\},\{m_1\},\{m_2\},\{m_3\},\{m_1,m_2\},\{m_1,m_3\},\{m_2,m_3\},\{m_1,m_2,m_3\}\}$.
</li>
<li>
The symbol $*$ denotes any value.
</li>
<li>
<span style="color:darkred">Dark red color</span> denotes messages used only
for modelling purposes and that do not have an immediate one-to-one relationship
with the messages of the $\texttt{eth}$ sub-protocol [[Ethereum-Wire-Protocol]].
The mapping between the abstract model and the concrete messages is provided in
Section <a href="data-structures"></a>.
</li>
<li>
Black color when applied to messages denotes EBFT specific messages not
included in the current $\texttt{eth}$ sub-protocol [[Ethereum-Wire-Protocol]].
</li>
<li>
$T:(t_1,...,t_n)$ indicates a tuple $(t_1,...,t_n)$ that is thereafter referred
to as $T$.
</li>
<li>
${\pi_m}(T)$ corresponds to the $m$-th element of the tuple $T$ where the
first element has index 1. For example, ${\pi_2}((t_1,t_2,t_3))$ corresponds to
$t_2$.
</li>
<li>
$\mathtt{blockHeight}(EB)$ is defined as the height of the Ethereum block
$EB$.
</li>
<li>
$\mathtt{sizeOf}(M)$ indicates the size of the set $M$. That is,
$\mathtt{sizeOf}(M)\equiv\lVert{M}\rVert$.
</li>
<li>
$\mathtt{EthAddressRecover}(H,signature)$ corresponds to the Ethereum address
whose signature of the hash $H$ corresponds to $signature$.
</li>
<li>
Each <a>validator</a> $v$ stores its local blockchain in $chain_v$.
</li>
<li>
$chain_v[n]$ corresponds to the finalized block with height $n$, while
$chain_v[n:m]$ corresponds to a sub-chain including all of the finalized blocks
from height $n$ to height $m$ included.
</li>
<li>
$chain_{EB_v}[n]$ corresponds to the Ethereum block included in the finalized
block with height $n$, while $chain_{EB_v}[n:m]$ corresponds to a sub-chain
including all of the Ethereum blocks included in the finalized blocks from
height $n$ to height $m$ included.
</li>
<li>
The blockchain height is defined as the height of the last finalized block
added to the blockchain.
</li>
<li>
$\mathtt{validators}(chain_v[0:h-1])$ represents the set of authorized
<a>validators</a> for instance $h$ of the EBFT-block-finalization-protocol.
</li>
<li>
$\mathtt{n}(chain_v[0:h-1])$ represents the number of <a>validators</a> for
instance $h$ of the EBFT-block-finalization-protocol. That is,
$\mathtt{n}(chain_v[0:h-1])\equiv\mathtt{sizeOf}(\mathtt{validators}(chain_v[0:h-1]))$.
</li>
<li>
For the purpose of this section, $\mathtt{isValidBlock}(EB,EB_p)$ is defined to
be true if and only if block $EB$ is a valid Ethereum block with parent $EB_p$
where $\mathtt{isValidBlock}(EB,EB_p)$ only verifies the following fields of the
standard Ethereum header:
<ul>
<li>
<code>parentHash</code>
</li>
<li>
<code>stateRoot</code>
</li>
<li>
<code>transactionsRoot</code>
</li>
<li>
<code>receiptsRoot</code>
</li>
<li>
<code>logsBloom</code>
</li>
<li>
<code>number</code>
</li>
<li>
<code>gasLimit</code>
</li>
<li>
<code>gasUsed</code>.
</li>
</ul>
For a detailed description of the validation performed by $\mathtt{isValidBlock}$
see Section <a href="#sec-block-header-validation"></a>.
</li>
<li>
Each EBFT finalized block $FB$ is modelled by the tuple $(FB_{EB},FB_{FP})$ where:
<ul>
<li>
$FB_{EB}$ is the Ethereum block to be added to the blockchain.
</li>
<li>
$FB_{FP}$ is the proof that agreement was correctly reached on the position in
the chain of the block $FB_{EB}$.
</li>
</ul>
</li>
<li>
Each finalization proof $FP$ is modelled by the tuple $(FB_r,FB_{CS})$ where:
<ul>
<li>
$FB_r$ is the round number of the EBFT-block-finalization-protocol, during the
execution of which, agreement on the block inclusion in the blockchain was
reached.
</li>
<li>
$FB_{CS}$ is a list of signatures on both the Ethereum block and the round
proving that agreement was reached by a correct execution of the
EBFT-block-finalization-protocol. For more information about how this list of
signatures, called <dfn data-lt="commit seal">commit seals</dfn>, are
computed, see Section 3.1 of the [[IBFT2-Gray-Paper]].
</li>
</ul>
</li>
</ul>
</section>
<section id="algorithm-1-description">
<h3>Description of the EBFT protocol (Algorithm 1)</h3>
The overarching structure of the EBFT protocol is essentially specified by the
$\mathbf{upon}$ block at line 10 of Algorithm 1, which states that when a new
finalized block is received by a node $v$, $v$ executes the following operations:
<ol>
<li>
Verifies if the finalized block received is for the next expected chain height.
That is, $h_v$.
</li>
<li>
If so, it verifies if the finalized block received is a valid finalized block.
</li>
<li>
If both verifications pass, then:
</li>
<ol type="a">
<li>
$v$ adds the finalized block to its local blockchain.
</li>
<li>
If $v$ is a <a>validator</a> for the current instance of the
EBFT-block-finalization-protocol, then $v$ stops that instance.
</li>
<li>
$v$ advances the next expected block height, $h_v$, by 1.
</li>
<li>
If $v$ is a <a>validator</a> for the EBFT-block-finalization-protocol instance
for the new value of $h_v$, then $v$ starts that instance.
</li>
</ol>
</ol>
As described by the function $isValidFinalizationBlock(FB,v)$ at line 3, an
EBFT finalized block $FB$ is defined valid if and only if all of the following
conditions are met:
- It contains at least $Quorum(n)\equiv\left\lceil\frac{2n}{3}\right\rceil$
different commit seals, where $n$ is the number of <a>validators</a> for
instance $h$ of the EBFT-block-finalization-protocol. That is,
$n\equiv\mathbf{n}(chain_v[0:h-1])$.
- Each commit seal corresponds to the signature of one of the <a>validators</a>
over the Ethereum block and the round number included in the finalization proof.
Finalized blocks are delivered to nodes using the standard $\texttt{eth}$
[[RLPx]] sub-protocol [[Ethereum-Wire-Protocol]]. In the pseudocode the actual
$\texttt{eth}$ sub-protocol is abstracted and models the reception of a
finalized block $FB$ with the reception of a
<span style="color:darkred">$\langle\mathsf{FINALIZED-BLOCK},FB\rangle$</span>
message. No such message actually exists in the concrete EBFT protocol. As per
the standard $\texttt{eth}$ sub-protocol, a block can be received either using
an unsolicited NewBlock message or using the pair of messages
GetBlockHeaders/BlockHeaders followed by the pair of messages
GetBlockBodies/BlockBodies [[Ethereum-Wire-Protocol]].
As specified by the $\mathbf{upon}$ block at line 19, when a node $v$ receives
an EBFT message (Proposal, Prepare, Commit or Round-Change message) including a
height $h_m$ with value $\ge$ than the next expected height $h_v$, if the sender
of the message is one of the DEVp2p peers of $v$, then $v$ starts asking the
peer for finalized blocks with height between the $v$'s current height $h_v$ and
the height $h_m$ included in the EBFT message received. This is modeled with the
transmission of a
<span style="color:darkred">$\langle\mathsf{GET-BLOCKS},h_v,h_m\rangle$</span>
message. The peer's response to this request is modeled as a
<span style="color:darkred">$\langle\mathsf{FINALIZE-BLOCK},FB\rangle$</span>
message. As stated previously, this is not an exact description of the real
messages sent by the implementation. It is a modelling of the DEVp2p behavior
useful in this context for specifying the EBFT protocol at a high level. In
modelling of this protocol, $\mathbf{expectedHeight}_v[v']$ is used to express
that Get-Blocks messages are sent only the first time an EBFT message with a
height higher than $h_v$ is received.
</section>
<section id="ibft2-block-finalization-protocol">
<h3>Description of the EBFT-block-finalization-protocol (Algorithm 2)</h3>
This section describes a generic $h$ instance of the
EBFT-block-finalization-protocol for a <a>validator</a> $v$, as detailed in
Algorithm 2 in Section <a href="#algorithm-pseudocode"></a>.
The EBFT-block-finalization-protocol is organized in rounds, starting from round
0, where <a>validators</a> progress to the next round after they suspect that in
the current round they cannot decide on the block to be included at height $h$
of the blockchain. Both in Algorithm 2 and in this description, the current
round for the $h$-th instance of the EBFT-block-finalization-protocol for
<a>validator</a> $v$ is denoted as $r_{h,v}$.
For each round, one of the <a>validators</a> is selected to play the role of
block proposer. The selection is operated by the evaluation of
$\mathbf{proposer}(chain_v[0:h-1],r_{h,v})$ where
$\mathbf{proposer}(\cdotp,\cdotp)$ is a deterministic function of the chain of
blocks from the genesis block until the block with height $h-1$ and the current
round number.
The pseudocode at lines 2 to 4 introduces the following macros:
- $n_{h,v}$, which is the number of <a>validators</a> for the $h$-th instance of
the EBFT-block-finalization-protocol for <a>validator</a> $v$.
- $\mathbf{validators}_{h,v}$, which is the <a>validators</a> for the $h$-th
instance of the EBFT-block-finalization-protocol for <a>validator</a> $v$.
- $\mathbf{proposer}_{h,v}(r_{h,v})$, which is the proposer for round
$r_{h,v}$ of the $h$-th instance of the EBFT-block-finalization-protocol for
<a>validator</a> $v$.
These macros are used both in the pseudocode and in this section to simplify the
notation when describing the $h$-th instance of the
EBFT-block-finalization-protocol for <a>validator</a> $v$. The term,
<em>non-proposing <a>validators</a> for round r and instance h</em>, is used to
indicate all of the <a>validators</a> for round $r$ and instance $h$ with the
exclusion of the proposer for round $r$ and instance $h$.
The proposer selection function ensures that all of the <a>validators</a> for
the $h$-th instance of the EBFT-block-finalization-protocol are selected for any
sequence of $n_{h,v}$ consecutive rounds. Also, the proposer for round 0
corresponds to the proposer of the proposer selection sequence that comes after
the proposer of the block included in the previous finalized block.
<p class="note">
The specification and description of the exact algorithm used for the proposer
selection function is currently not included in this specification and must be
added at some point before finalization of the document.
</p>
As specified by the initialization block (line 9), if $v$ is the selected block
proposer for the first round, that is, round 0, then $v$ multicasts a <a>Proposal message</a>
$\langle\langle\mathsf{PROPOSAL},h,0,\mathbf{KEC}(PB)\rangle_{\sigma_v},PB,\bot\rangle$
to all <a>validators</a> (including itself) that comprises the message
$\langle\langle\mathsf{PROPOSAL},h,0,\mathbf{KEC}(PB)\rangle_{\sigma_v}$
signed by $v$, the proposed block $PB$ and a Round-Change-Certificate, which for
round 0 is empty (that is, $\bot$). More detail on how the
Round-Change-Certificate is assembled is provided further down in this section
when discussing how <a>validators</a> move to a different round.
The proposed block $PB$ is modelled here as a tuple where the first element is a
standard Ethereum block and the second element is the current round number at
which the Ethereum block was created, which at initialization is 0.
$\mathbf{KEC}(\cdotp)$ represents the Keccak hash function. The pseudocode uses
$\mathbf{createNewProposedBlock}(h,v)$ to represent the creation of a new block
with height $h$ by <a>validator</a> $v$. Honest <a>validators</a> employee a
fair transaction selection algorithm to decide which transactions to include in
the next block. The definition of such algorithm is outside the scope of this
document.
As specified by lines 31 to 32, a <a>validator</a> $v$ accepts a <a>Proposal message</a>
$\langle\langle\mathsf{PROPOSAL},h_{pp},r_{pp},H\rangle,PB:(EB,r_{EB}),*\rangle$
if and only if all of the following conditions are met:
- $v$ is currently running the EBFT-block-finalization-protocol instance
$h_{pp}$. That is, $h_{pp}=h$.
- $v$ is in round 0. That is, $r_{pp}=r_{h,v} = 0$.
- The signed portion of the message, $\langle\mathsf{PROPOSAL},h_{pp},r_{pp},H\rangle$,
is signed by the selected proposer for round $r_{h,v} = 0$ and instance $h$ of
the EBFT-block-finalization-protocol.
- $v$ has not already accepted a <a>Proposal message</a> for round $r_{h,v} = 0$
in the $h$-th instance of the EBFT-block-finalization-protocol. That is,
$acceptedPB = \bot$.
- The Ethereum block $EB$ included in the proposed block $PB$ is a valid block
for height $h$.
- The round number included in the prepared block $PB$ matches the current round
number. That is, $r_{h,v} = r_{EB} = 0$.
- $H$ corresponds to the Keccak hash of the proposed block $PB$.
When a <a>validator</a> $v$ accepts a <a>Proposal message</a>, it:
- Marks the <a>Proposal message</a> as accepted by setting the state variable
$acceptedPB$ to the proposed block included in the <a>Proposal message</a> (see
line 16).
- Multicasts a <a>Prepare message</a>
$\langle\mathsf{PREPARE},h,r_{h,v},H\rangle_{\sigma_v}$ (see line 17) to all
<a>validators</a> (including itself).
The $\mathbf{upon}$ block at line 36 is executed the first time all of the
following conditions are met by <a>validator</a> $v$:
- $v$ has accepted a <a>Proposal message</a> for the proposed block $PB$. That
is, $acceptedPB_{h,v} = PB$.
- $v$ has received, from non-proposing <a>validators</a> for the current round,
at least $Quorum(n_{h,v})-1$ <a>Prepare message</a> for the current instance of
the EBFT-block-finalization-protocol, current round, and with digest $H$
corresponding to the Keccak hash of the accepted proposed block $PB$.
When all of the conditions listed above are met for the first time, then:
- $v$ multicasts a <a>Commit message</a>
$\langle\mathsf{COMMIT},h,r_{h,v},H,CS(PB,v)\rangle_{\sigma_v}$ to all
<a>validators</a> (including itself), where $CS(PB,v)$, called
<em>commit seal</em>, corresponds to the signature of $v$ over the proposed
block $PB$ and the current round number.
- $v$ sets $latestPreparedProposedBlock_{h,v}$ to the proposed block $PB$;
- $v$ sets $latestPC_{h,v}$ to a set including the signed portion of the
accepted <a>Proposal message</a> and all of the <a>Prepare message</a> sent by
non-proposing <a>validators</a> for the current round targeting the current
instance of the EBFT-block-finalization-protocol, current round and with
digest $H$ corresponding to the Keccak hash of the accepted proposed block $PB$.
The pseudocode uses the state variable $commitSent_{h,v}$ to indicate that the
<a>Commit message</a> is sent only the first time that all of the conditions
listed above are met. $commitSent_{h,v}$ is set to $true$ at line 39 and reset
to $false$ in the $StartNewRound$ procedure at line 26. Borrowing from the PBFT
terminology, when a <a>validator</a> meets the conditions indicated in the
$\mathbf{upon}$ block at line 36, then $v$ is said to be $prepared$ at round
$r_{h,v}$. Borrowing again from the PBFT terminology, $latestPC_{h,v}$ is the
latest Prepared-Certificate and the protocol is designed so that
$latestPC_{h,v}$ always holds at least the minimum number of messages required
to prove that $v$ $prepared$ in round $r_{h,v}$ on a proposed block with Keccak
hash $H$. A Prepared-Certificate is said to be for round $r$ and instance $h$
if and only if the Prepared-Certificate only includes signed
<a data-lt="proposal message">Proposal</a> and
<a data-lt="prepare message">Prepare</a> messages for round $r$ and height $h$.
$latestPC_{h,v}$ always holds the Prepared-Certificate for the latest round in
the current instance $h$ where $v$ is $prepared$. $latestPC_{h,v} = \bot$ only
if $v$ has never $prepared$ in the current instance $h$.
The $\mathbf{upon}$ block at line 44 is executed the first time all of the
following conditions are met by <a>validator</a> $v$:
- $v$ has accepted a <a>Proposal message</a> for the proposed block $PB$. That
is, $acceptedPB_{h,v} = PB$.
- $v$ has received, from at least different $Quorum(n_{h,v})$ <a>validators</a>
for the current instance of the EBFT-block-finalization-protocol, a
<a>Commit message</a> for the current instance of the
EBFT-block-finalization-protocol, current round, with digest $H$ corresponding
to the Keccak hash of the accepted proposed block $PB$ and commit seal signed by
the sender of the <a>Commit message</a>.
When all of the conditions listed above are met for the first time, then:
- $v$ creates a block finalization proof modelled as a tuple comprising the
current round number and the commit seals included in all the
<a>Commit messages</a> that satisfy the condition on <a>Commit messages</a>
stated above.
- $v$ creates a finalized block modelled as a tuple comprising the Ethereum
block included in the proposed block and the finalization proof.
- $v$ broadcasts the finalized block to all nodes.
The pseudocode uses the state variable $finalizedBlockSent_{h,v}$ to trigger the
transmission of a finalized block only the first time the conditions listed
above are met. $finalizedBlockSent_{h,v}$ is set at line 50 and reset in the
$StartNewRound$ procedure at line 12.
In alignment with PBFT, the EBFT protocol relies on a round change
sub-protocol to detect whether the selected proposer might be Byzantine and
causing the protocol to never terminate. As specified at lines 21 to 22,
whenever a <a>validator</a> $v$ starts a new round, it starts a round timer with
a duration exponential to the round number (see line 8).
When <a>validator</a> $v$'s round timer for the current round expires (line 51),
$v$ starts the round $r_{h,v} + 1$ and multicasts a
$\langle\langle\mathsf{ROUND-CHANGE},h,r_{h,v} + 1,latestPC_{h,v}\rangle,latestPreparedProposedBlock_{h,v}\rangle$
message for the new round to all <a>validators</a> (including itself). Note that
the <a>Round Change message</a> includes the latest Prepared-Certificate and the
proposed block associated with the latest Prepared Certificate.
The $\mathbf{upon}$ block at line 55 describes under which conditions a
<a>Proposal message</a> for a new round is multicast and how the
<a>Proposal message</a> is assembled. Specifically, the $\mathbf{upon}$ block is
executed only if $v$ has received at least $Quorum(n_{h,v})$
<a>Round Change messages</a> for the current EBFT-block-finalization-protocol
instance such that:
<ul>
<li>
All messages are for the same round number $r_{rc}$ and $r_{rc}$ is higher than
the current round.
</li>
<li>
All messages are sent by distinct <a>validators</a> for the current instance of
the EBFT-block-finalization-protocol.
</li>
<li>
All messages contain a valid Prepared-Certificate. A Prepared-Certificate is
considered valid either if it is empty ($\bot$) or if it contains one
<a>Proposal message</a> and at least $Quorum(n_{h,v}) - 1$
<a>Prepare messages</a> for the same round $r'$ such that:
<ul>
<li>
$r'\lt$ than the the round number of the <a>Round Change messages</a>, $r_{rc}$.
</li>
<li>
The <a>Proposal message</a> is signed by the selected proposer for round $r'$.
</li>
<li>
The <a>Prepare messages</a> are sent by non-proposing validators for the $h$-th
instance of the EBFT-block-finalization-protocol and round $r'$ and they are
all for the current instance $h$ of the EBFT-block-finalization-protocol,
round $r'$ and same hash as the one included in the <a>Proposal message</a>.
</li>
</ul>
</li>
<li>
The Keccak hash of the $proposedBlock$ included in each of the
<a>Round Change messages</a> considered matches the hash included in the
<a data-lt="proposal message">Proposal</a> and
<a data-lt="prepare message">Prepare</a> message of the Prepared-Certificate.
</li>
</ul>
Any set meeting these conditions is a valid Round-Change-Certificate for round
$r'$ where round $r'$ is the round included in all of the
<a>Round Change messages</a> included in the Round-Change-Certificate. When all
of the conditions listed above are met, then:
<ul>
<li>
$v$ moves to the round number included in one of the Round-Change-Certificates
with the highest round number, lets $RCC$ be the chosen Round-Change-Certificate
and lets $r_h$ be the round number of $RCC$.
</li>
<li>
If $v$ was not already in $r_h$, then $v$ starts the round timer for round $r_h$.
</li>
<li>
If $v$ is the selected proposer for round $r_h$, $v$ sends a
<a>Proposal message</a> for the new round including the selected
Round-Change-Certificate ($RCC$) and a proposed block calculated as follows:
<ul>
<li>
If all of the Prepared-Certificates included in the
<a>Round Change message</a> are empty, that is $=\bot$, then the proposed block
must be a tuple including any valid Ethereum block for height $h$ and the
current round number, which must match the round number of the
<a>Proposal message</a>.
</li>
<li>
Otherwise, the Ethereum block included in the tuple constituting the proposed
block must match the proposed block received as part of one of the
<a>Round Change messages</a> including a Prepared-Certificate for the highest
round amongst the rounds of all the other Prepared-Certificates included in the
Round-Change-Certificate.
</li>
</ul>
</li>
</ul>
As specified by the $\mathbf{upon}$ block at line 71, a <a>Proposal message</a>
$\langle\langle\mathsf{PROPOSAL},h,r_{pp},H\rangle_{\sigma_{sender}},PB;RCC\rangle$
for a round higher than 0 is accepted only if all of the following conditions
are met:
<ul>
<li>
$v$ is currently running the EBFT-block-finalization-protocol instance
$h_{pp}$. That is, $h_{pp}=h$.
</li>
<li>
The round number $r_{pp}$ of the <a>Proposal message</a> is either higher than
the current round or equal to the current round provided that $v$ has not
accepted any <a>Proposal message</a> for the current round. That is,
$acceptedPB = \bot$.
</li>
<li>
$H$ corresponds to the Keccak hash of the proposed block $PB$.
</li>
<li>
The signed portion of the message is signed by the selected proposer for round
$r_{pp}$ and instance $h$ of the EBFT-block-finalization-protocol.
</li>
<li>
The Round-Change-Certificate $RCC$ includes at least $Quorum(n_{h,v})$
<a>Round Change messages</a> for round $r_pp$ and height $h$.
</li>
<li>
If each of the <a>Round Change messages</a> included in the
Round-Change-Certificate $RCC$ includes either an invalid Prepared-Certificate
or an empty Prepared-Certificate, then the:
<ul>
<li>
Ethereum block $EB$ included in the proposed block $PB$ must be a valid block
for height $h$.
</li>
<li>
Round number $r_{EB}$ included in the prepared block $PB$ must match the current
round number. That is, $r_{h,v} = r_{EB}$.
</li>
</ul>
</li>
<li>
Otherwise, the Keccak hash of the tuple composed of the Ethereum block included
in $PB$ and the highest round number of all Prepared-Certificated included in
$RCC$ must match the hash included in any of the messages that are part of the
Prepared-Certificates with the highest round number amongst all of the
Prepared-Certificates included in the Round-Change-Certificate $RCC$.
</li>
</ul>
The effect of accepting a <a>Proposal message</a> for a round $r_{pp} \gt 0$ is
essentially the same as accepting the <a>Proposal message</a> for round 0 with
the addition of moving to round $r_{pp}$. Specifically, $v$: