🏠

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

Date: 2021-01-16 19:39

Author: Yasushi Sakai

Created: 2021-01-22 Fri 13:13