Cyrus Flag

flag{S0_bangbang_7ha7_u_f1nd_h3r3}

WIP-分布式入门2:从 BFT 到 PBFT

0x01 拜占庭将军问题

(TODO

0x02 BFT OM 算法(口头协议算法)

(TODO

代码实现如下:

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
DEFAULT_MESSAGE = "DEFAULT_MESSAGE"

class Commander:
cid = -1
ctotal = -1
cevil = False
cconfirms = []
cresult = None

def __init__(self, id, total, evil_status = False):
self.cid = id
self.ctotal = total
self.cevil = evil_status

def add_confirm(self, message):
self.cconfirms.append(message)

def clean_confirm(self):
self.cconfirms = []

def majority(self):
l = {}
for i in self.cconfirms:
try:
l[str(i)] += 1
except:
l[str(i)] = 1
max_n = 0
max_v = []
for i in l:
if l[i] > max_n:
max_n = l[i]
max_v = [i,]
elif l[i] == max_n:
max_n = l[i]
max_v.append(i)
if len(max_v) != 1:
print("Error: too many evils, commander %d cannot judge majority" % self.cid)
print("[-] list = " + str(l))
print("[-] majority = " + str(max_v))
return None
else:
return max_v[0]

def set_result(self, result_message):
self.cresult = result_message

def BFT(n, evil_list):
commanders = []
leaders = []
m = len(evil_list)

if n < 3*m+1:
cmd = input("Warning: too many evil, continue? [y/n] ")
if cmd != "y" and cmd != "":
print("Skipped. (n=%d, m=%d)" % (n,m))
return 2

for i in evil_list:
if i >= n:
print("Error: evil id illegal.")
return

for i in range(n):
if i in evil_list:
commanders.append(Commander(i, m, True))
else:
commanders.append(Commander(i, m))

print("Initial commenders:")
for commander in commanders:
print("\tCreate commander %d (%s evil)" % (commander.cid, commander.cevil))

print("Start:")
total = [0]
def OM(leader, this_commander, round_id, message):

if round_id < 0: # leader is doing round 0
if this_commander.cevil:
print("\t"*(m-round_id) + "[+] [Commander %d] returns \"%s\"" % (this_commander.cid, DEFAULT_MESSAGE))
leader.add_confirm(DEFAULT_MESSAGE)
else:
print("\t"*(m-round_id) + "[+] [Commander %d] returns \"%s\"" % (this_commander.cid, message))
leader.add_confirm(message)

else:
print("\t"*(m-round_id) + "[Commander %d] is doing [Round %d]" % (this_commander.cid, round_id))
leaders.append(this_commander)
this_commander.clean_confirm()
this_commander.add_confirm(message)
for commander in commanders:
if commander not in leaders:
print("\t"*(m-round_id+1) + "Ask [Commander %d] to comfirm \"%s\"" % (commander.cid, message))
flag = OM(this_commander, commander, round_id - 1, message)
if flag != 0:
return flag
if this_commander.cevil:
majority_message = DEFAULT_MESSAGE
else:
majority_message = this_commander.majority()
if majority_message is None:
return 1
if leader is not None:
print("\t"*(m-round_id) + "[+] [Commander %d] returns \"%s\"" % (this_commander.cid, majority_message))
total[0] += 1
this_commander.set_result(majority_message)
leader.add_confirm(majority_message)
leaders.pop()

return 0

flag = OM(None, commanders[0], m, "shit")

if flag == 0:
print("Result:")
for commander in commanders:
print("\tCommander %d did %s (%s evil)" % (commander.cid, commander.cresult, commander.cevil))
print("Total:", total[0],"[=(%d-1)^%d]" % (n,m))

if __name__ == "__main__":
BFT(7, [4,5,6])
cmd = input("\nContinue? [Enter]")
BFT(7, [5,6])
print("\nDone.")

0x03 BFT SM 算法(签名协议算法)

(TODO

0x04 PBFT 算法

(TODO

0x05 参考

CSDN - BFT OM:一个图文并茂(然而有点乱)的说明