COMPSCI 711 Byzantine Theory radu/2020
BYZANTINE AGREEMENT – A FEW THEORETICAL RESULTS.
1.21
COMPSCI 711
Byzantine Theory
radu/2020
NUMBER OF PROCESSES FOR BYZ – LEMMA 6.26
2
1 3 1:0
3: 0
?
0
2: 0
Thought experiment
1’: 1
2’: 1
1
Hypothetical protocol for n=3, f=1.
3’: 1
Conclusion: no algorithm for n=3, f=1. 2.21
COMPSCI 711
Byzantine Theory radu/2020
for 3 n 3f
o 3 “subnets” with at most f processes in each
o we assume that there is an algorithm that can solve the Byz agreement for such an n, and we construct an algorithm that can solve the problem for 3 processes,
o contradiction (with lemma 6.26)
THEOREM 6.27
No solution for 2 n 3f
n=2 YN
TF TF
3.21
TT
COMPSCI 711 Byzantine Theory radu/2020
Proof by contradiction
o We assume that the n “small” processes can solve the Byz problem, if at most f are faulty –
regardless how these f faulty nodes are distributed
o These “small” processes are totally unaware that they are now clustered into 3 “large”
nodes, connected by 3 “large” channels
TF TT
FT
4.21
COMPSCI 711 Byzantine Theory radu/2020
o Replacing an arbitrary one “large” node by a “large” Byzantine node is tantamount to replacing its content by the same number of “small” faulty nodes (w/ their channels)
o Not doing this will be easily detected, by the others, as wrongly formatted messages TF
TF
TT
5.21
COMPSCI 711 Byzantine Theory radu/2020
AN EIG TREE WITH N=4 (# OF PROCESSES) AND L=2 (LEVELS)
6.21
o Level #1 : 1 group with N=4 siblings
o Level #2 : 4 groups with N-1=3 siblings each
o Level #L : each group has N-L+1 siblings o For Byz agreement, L=F+1, here F=1, L=2
o Observe the node labelling scheme
o The nodes will be filled level-by-level
o First, top-down, by L messaging rounds o Then, bottom-up, after the messaging end
λ
1234
1.4
2.4
3.4
4.3
1.3
2.3
3.2
4.2
1.2
2.1
3.1
4.1
o Consider that process #1 is “faulty” o but #2, #3, #4 are “non-faulty”
o Observe the distribution of labels ending in one of 2,3,4
o a majority at leaves, if LF+1
o at least 1 along each path, if LF+1 ▪ therefore at least 1 “cut” across
o These arguments will play a role in the proof
COMPSCI 711 Byzantine Theory radu/2020
Tree nodes with labels ending in the number of a non-faulty process play a critical role! o Examples (prev. slide): 2, 1.2, 2.3, 2.4, …
The number of levels, L, is a well-chosen critical number!
o If L F+1, then each root-to-leaves branch contains at least one such tree node
Except λ, there are F+1 tree nodes (in each branch), but only F faulty processes (and labels cannot contain duplicates)
o If L F+1, then each sibling group (including at the last level) has a strict majority of such tree nodes
The smallest sibling group (at the leaves level), has N-L+1 tree nodes, thus N-L+1 = N-(F+1)+1 = N-F 3F+1-F = 2F+1 tree nodes at least,
out of which at most F can end in numbers of faulty processes
o The algorithm chooses L = F+1!
7.21
COMPSCI 711 Byzantine Theory radu/2020
COMMON NODES
(THOSE ON WHICH A
COMMON DECISION
IS TAKEN)
DEFINITION:
A tree node with label x is common if it has the same newval() across all non-faulty processes, i.e.,
newval(x)i = newval(x)j for all i, j that are non-faulty processes Note: val(x)i and val(x)j may or may not be equal
o A set of tree nodes which contains at least one tree node on each (root-to-leaves) path is called a path covering.
o The red “cut” across the previous sample EIG tree is a path covering.
o A is a where all tree nodes are .
o As we will see, the red “cut” across the previous sample EIG tree is also a common path covering.
common path covering
path covering
common
8.21
COMPSCI 711
Byzantine Theory
THE ESSENCE OF THE PROOF – BIRD’S EYE VIEW
radu/2020
#i
xk: v,v
same v↓, v↑
#j
xk: v,v
#i
x: _,v
same v↑
#j
x: _,v
9.21
COMPSCI 711
Byzantine Theory radu/2020
THE ESSENCE OF THE PROOF – MORE DETAILS
o All nodes above a
path covering are , because all their children are common – although these may have different newval()’s.
o Thus the root is also .
common
common
common
o all nodes are common
xk common path covering
xk common path covering xk
o All xk nodes are common because they have a strict majority of xkl xkl’ … children sharing the
val() and newval()
common
same
common
common
o xk … nodes o other nodes o non-common nodes
xk
??
10.21
COMPSCI 711 Byzantine Theory radu/2020
TOP-DOWN MESSAGING IN THE EIG PROTOCOL (RECALL)
Process i x:v
Process j
xi:v
Process k
xij:v
assume that x does not contain i, j
11.21
COMPSCI 711
Byzantine Theory
radu/2020
LEMMA 6.15
k
x:v xk:v
ij
Assuming that all processes here, i.e., k, i, j, are non-faulty v = val(x)k = val(xk)k = val(xk)i = val(xk)j
x:? xk:v
x:? xk:v
12.21
COMPSCI 711 Byzantine Theory radu/2020
LEMMA 6.16
All nodes with labels of the form xk, where k is number of a non-faulty process, have the same val()
and newval() across all non-faulty processes, i.e.,
newval(xk)i = val(xk)i = val(xk)j = newval(xk)j for all i, j that are non-faulty processes
As a corollary, all such nodes are common!
In fact, they are “more than common”, as their val() attributes are also equal, to the same value
The proof follows on next slides
As we will further see:
o The condition of lemma 6.16 is not necessary, i.e., there could also be other common nodes with
labels of the form xk’, where k’ is a faulty process.
o All first level nodes are common! This result ensures a common decision at the root .
13.21
COMPSCI 711 Byzantine Theory
radu/2020
o Assuming that all processes here, i.e., k, i, j, are non-faulty v = val(x)k = val(xk)k = val(xk)i = val(xk)j =
= newval(xk)k = newval(xk)i = newval(xk)j by the definition for leaves: newval() = val()
LEMMA 6.16 FOR LEAVES
k
x:v xk:v, v
ij
x:? xk:v, v
x:? xk:v, v
14.21
o Assuming all processes here, i.e., k, l, i, j, are non-faulty v = val(x)k = val(xk)k = val(xk)i = val(xk)j =
= newval(xk)k = newval(xk)i = newval(xk)j
by induction on the height of node xk, and the def of newval() for nodes when there is a majority voting for the same v
l
LEMMA 6.16 FOR NON-LEAVES
k
ij
o A of the children of xk have the form xkl where l is a number of a non-faulty process: same val(xkl) = val(xk) = val(x)k.
o The induction hypothesis holds for these nodes (less height):
same newval(xkl)
majority
kk
COMPSCI 711
Byzantine Theory
radu/2020
x:v
xk:v, v xkl:v, v
x:?
x :v,v
xkl:v, v
x:? xk:v, v
xkl:v,v
x:?
x :v,v
xkl:v, v
15.21
COMPSCI 711
Byzantine Theory radu/2020
LEMMA 6.18
i
There is a the whole EIG tree! o How to build such a common path covering?
o Top down on each branch, until we find a
o Labels that end with k, where k is a non- faulty process (there is such a label on each branch)
o As we have seen, all such tree nodes have common newval()
o Thus, this is common path covering of the EIG tree!
tree
node
which ends with the label of a non-faulty process
common path covering
x
k
16.21
COMPSCI 711 Byzantine Theory radu/2020
LEMMA 6.19 – FOR LEAVES
ij
o A node that has a
(“cutting”) its is itself (regardless how its label ends)
common path covering
subtree
common
x:-, v
x:-, v
i
o Base case for leaves
o The subtree of a leaf x is the leaf itself.
o Thus any leaf x which is part of the common path covering… is common, qed.
x
17.21
COMPSCI 711
Byzantine Theory
radu/2020
LEMMA 6.19 – FOR NON-LEAVES
i
i
x
x xl
o If is itself part of the
, then,
well, it is , qed.
x
common path covering
common
o Otherwise, all its children – such as (no matter if l is or not faulty) will be common by (height-1)
o And then x will be common by the definition of newval()
induction
xl
18.21
COMPSCI 711 Byzantine Theory radu/2020
LEMMA 6.20 i
o All nodes a the tree are also
including the root .
,
above
common path covering
o Thus, they have the same newval() across all non- faulty processes
o Agreement!
common
xk
xk
o We proved that the EIG algorithm solves the Byz agreement problem. o We have now the agreement
o What is still missing?
almost
19.21
COMPSCI 711 Byzantine Theory radu/2020
o is straightforward: the protocol stops after messaging rounds
o What else?
Termination
F+1
20.21
COMPSCI 711 Byzantine Theory radu/2020
!
Assume that all non-faulty processes start with the same initial value v
Validation
LEMMA 6.17
Proof – using LEMMA 6.16
newval(xk)i = val(xk)i = val(xk)j = newval(xk)j, for all non-faulty k, i, j
In particular
newval(k)i = val(k)i = val(k)j = newval(k)j = v, for all non-faulty k, i, j
Thus, all first level nodes corresponding to non-faulty processes share the same newval() = v And they form a strict majority, so the root decision will be v – validity !
THEOREM 6.21 The EIG algorithm solves the Byz agreement problem!
21.21