Consensus Algorithms
90-年代 -> 無作為的故障(omissive)
fault tolerance (堅牢性)
1 Paxos lamport2019part
単一の値に対して合意する。古代ギリシアのパクソス等の官僚は皆パートタイムで事件簿やそのほか台帳を分散的に管理していた。その考古学的な方法を元にランポートが説明している。
2 Raft ongaro2014search
Paxos 難しすぎて実装・メンテがキツすぎるという批評からもっと簡単な合意アルゴリズムを開発。どれだけ学生が理解したかを指標にしているところが面白い。Raft はイカダ。ログの寄せ集めだから。数珠繋ぎになっているログに対する合意形成。リーダーと過半数を使っている。
そのほか分散システムについては MIT の分散システムの授業が良い。
—
blockchain stuff, Byzantine fault lamport2019byzantine
ビザンチン将軍
comission
作為的も含める
—
3 Proof of Work
import hashlib prev = f'000000: origin' prev_hash = hashlib.sha256(bytes(prev,'utf-8')).hexdigest() print('origin: '+ prev) prefix = prev_hash[:6] n = 0; while n < 5: nonce = 0; while True: cur = f'{prefix}: data:"new transaction" no: "{n}" nonce:"{nonce}"' cur_hash = hashlib.sha256(bytes(cur,'utf-8')).hexdigest() if prev_hash > cur_hash: # if this is smaller prev = cur prev_hash = cur_hash prefix = prev_hash[:6] print(f'next block: {prefix} nonce: {nonce}') print(f' hash: {cur_hash}') print(f' data: {cur}') n += 1 break else: nonce += 1 # the nonce can be anything to solve the sha puzzle
origin: 000000: origin next block: 46f7d8 nonce: 4 46f7d85d73104873bfb44c3bcad288c690e7aa9fbaea6409360202773fc1eb98 79a198: data:"new transaction" no: "0" nonce:"4" next block: 058b27 nonce: 6 058b2702c1d37b83b2071702894bb712b0daf853e2d85b22a8fc040926b2f0ab 46f7d8: data:"new transaction" no: "1" nonce:"6" . . . 0165517dbccd44850442e8b2d3998fb4e24b735a7c77ac64c449fe15b87d5038 032ce1: data:"new transaction" no: "3" nonce:"29" next block: 003a8c nonce: 254 003a8c9d01188d9e2cef6039140e81b0891b9e94cd53450f0899559da6d6c654 016551: data:"new transaction" no: "4" nonce:"254"
note the hash is getting smaller making the sha256
puzzle harder to solve.
The node that chooses the right data - nonce pair gets to append to the next chain.
4 Proof of Stake
import random import numpy as np alice = 'alice' bob = 'bob' charlie = 'charlie' # alice holds three stakes a = [alice, alice, alice] # bob holds two stakes b = [bob, bob] # charlie holds one stake c = [charlie] bag = a + b + c winners = '' prev_win = random.choice(a+b+c) winners += prev_win for i in range(5): cur_win = random.choice(bag) if cur_win == prev_win: # prevents too much consecutive wins cur_win = random.choice(bag) winners += f', {cur_win}' bag.append(cur_win) prev_win = cur_win print(winners) a = np.array(bag) unique, counts = np.unique(a, return_counts=True) print(dict(zip(unique, counts)))
alice, alice, charlie, alice, bob, charlie {'alice': 5, 'bob': 3, 'charlie': 3}
5 分散プロトコル
- internet
- secure scuttlebutt
- blockstack (gaia, pki)
- decentralized identities
Bibliography
- [lamport2019part] @incollectionlamport2019part, title = The part-time parliament, author = Lamport, Leslie, booktitle = Concurrency: the Works of Leslie Lamport, pages = 277-317, year = 2019
- [ongaro2014search] Ongaro & Ousterhout, In search of an understandable consensus algorithm, 305-319, in in: 2014 $\$USENIX$\$ Annual Technical Conference ($\$USENIX$\$$\$ATC$\$ 14), edited by (2014)
- [lamport2019byzantine] @incollectionlamport2019byzantine, title=The Byzantine generals problem, author=Lamport, Leslie and Shostak, Robert and Pease, Marshall, booktitle=Concurrency: the Works of Leslie Lamport, pages=203-226, year=2019