Skip to content

Instantly share code, notes, and snippets.

@correosdelbosque

correosdelbosque/blockchain.md

Forked from kuenishi/blockchain.md
Created November 13, 2017 06:47
Show Gist options
  • Save correosdelbosque/d7f701d43e947ceee5ca67810e78b731 to your computer and use it in GitHub Desktop.
Save correosdelbosque/d7f701d43e947ceee5ca67810e78b731 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
blockchain.md

ブロックチェーン勉強会２

ブロックチェーンとは

ある事実なり履歴を改竄できない形で複製して保持する技術の総称

  • 高可用性、耐故障性
  • （ものによっては）匿名性
  • ？？？ 性能

過去の履歴もMerkle Treeでまとめることによってデータの改竄を検出しやすくしている

Block generation

H(k) = Hash(T(k-1), PublicKey(k)), 
T(k) = (PublicKey(k), H(k), Sign(H(k), PrivateKey(k)))
Block(n) = (T(k-i), ..., T(k), Hash(Block(n-1), Nonce)

Nonce

Hash(Block(n), Nonce(n)) ~ 0000001xxxxxx
                           ^^^^^^ first x bits of the hash

電子署名をどんどん追加するタイプの追記型データ構造 があればブロックチェーンなのでは？？→昔からあった

電子署名の問題点は、署名そのものが正しいかどうかが自明でない

$ gpg --key-gen
...
$ gpg -u [email protected] --clearsign hello.py
$ gpg -d hello.py.asc
print("Hello Python!")
gpg: Signature made Sun May 22 11:53:10 2016 JST using RSA key ID 1EB41214
gpg: Good signature from "Kota UENISHI (nope) <[email protected]>"
$ echo $?
0
$ gpg -d hello.py.asc.cracked
print("Hello Ruby!")
gpg: Signature made Sun May 22 11:53:10 2016 JST using RSA key ID 1EB41214
gpg: BAD signature from "Kota UENISHI (nope) <[email protected]>"
$ echo $?
1

改竄してから署名してしまえばよい

$ gpg -d hello.py.cracked.asc
print("Hello Ruby!")
gpg: Signature made Sun May 22 11:57:01 2016 JST using RSA key ID 1EB41214
gpg: Good signature from "Kota UENISHI (nope) <[email protected]>"
$ echo $?
0

BitCoinにおける合意（といわれているやつ）

TL;DR 分散システムでいうところの合意ではない

Block(n) が合意されるか

  • Termination (Liveness) ... (全てのプロセスはブロックを生成できる)
  • Validity ... 全てのプロセスがvを提案したら全員がvに決定する
  • Integrity ... 全てのプロセスは１つだけブロックを選ぶ(????)
  • Agreement ... 全てのプロセスは同じvを選ぶ(????)

反例 ... あるチェーンAが伸びてから、あとからより長いBを渡されたケース

-o-o-o-o-o-o-o-o-A

          b
-o-o-o-o-o+o-o-o-A
          |
          +o-o-o-o-o-o-o-o-o-o-o-o-o-o-B

あとから長いBを生成するためのクラシックな理論でいうと、あるNonceを計算 する計算量を O(N) とすると、ブランチした点 b から A までの計算にかかっ たコストはおよそ O(N * (A-b)) で、 B の計算にかかるコストは O(N * (B-b)) なので、履歴の改竄にかかるコストは、改竄対象のチェーンを作った コストの O(N * (B-b)/(A-b)) 倍程度になる。

その程度のコストを支払える計算機があれば合意（？）された値を変更できる。

AltCoins

バリエーションは沢山ある、暗号化や署名のアルゴリズム、通貨としての利用 や交換形態、通貨じゃないやつ、Public or Private, 運営や開発の主体、分 岐したチェーンの破棄方法、実装やパラメータなど様々な分類軸がある

ここでは分岐したチェーンの破棄方法を主な観点にする

PoW => PoS => DPoS => QDPoS
        +=> Stellar

メジャーな攻撃方法

  • 51% attack
  • Sybil attack
  • Network partition attack

Proof of Work

BitCoinと同様、Nonceの計算を競う早い者勝ちのプロトコル。より早くNonce を見つけるためには、より多くのコンピュータがあった方がよい。

  • Pros: フェア
  • Cons: エコじゃない, network attack で分岐する, 計算力の集中化が進んでいる, higher latency

Proof of Stake

投票によりより多くのコインを集めたBlockが正しいものになる。

  • Pros: PoWよりはエコ, attacker は過半数に近いコインを集める必要がある, lower latency
  • Cons: Richer get richer, "The Monopoly problem"

Monopoly => Double spending, denying service

  • Nothing at Stake: 全てのForkに投票する（PoWと違って投票はチープだか ら）
  • Stake Grinding: まずいくらかStakeを確保して、過去の歴史を遡って自分 が過半数をとれるブロックを探す。見つかったら、そこから歴史を今まで改 竄する。
"Both benevolent and malevolent monopoly are potentially profitable,
so there are reasons to suspect that an entrepreneurial miner might
attempt to become a monopolist at some point. Due to the Tragedy of
the Commons effect, attempts at monopoly become increasingly likely
over time."

現実的には需要と供給の関係によって、独占するには $20M必要と見積もられ ている（PoWなら$10M)。独占すると通貨価値がなくなるので独占したがる奴は いない、らしい etc, etc

バリエーションがいくつかある

  • Randomized block selection (Nxt, BlackCoin)
  • Coin age based selection (PPCoin)
  • Velocity based selection (PoSV, Reddcoin)
  • Voting based selection

他

Major AltCoins

Ripple: proof of work, TRUST?

  • Heuristics, to assume some limitations on network latency
  • The Ripple protocol can achieve consensus in the face of (n-1)/5 failures +several other desirable features
  • Q. is this for a fixed node set? <= given there's "n"
  • Stellar: Stellar consensus protocol (TRUST)
  • Etherium: PoW (rather a Smart Contracts platform)
  • Heavily centralized
  • Uncle Mining flaw
  • Casper; GHOST (Greedy Heaviest-Observed Sub-Tree)
  • BitShares: DPOS (Delegated PoS)
  • Nxt: Proof of Stake, w/ leased forging
  • NEM: Ripple Consensus

References

Omake

$ gpg -u [email protected] --clearsign hello.py.2

You need a passphrase to unlock the secret key for
user: "Kota UENISHI (nope) <[email protected]>"
4096-bit RSA key, ID 1EB41214, created 2016-05-22

$ gpg -d hello.py.2.asc
print("Hello Python, 2")
print("MD5 (hello.py.asc) = a1b90918efe7ce659b919a76b29e4eca")
gpg: Signature made Sun May 22 14:22:16 2016 JST using RSA key ID 1EB41214
gpg: Good signature from "Kota UENISHI (nope) <[email protected]>"

hello.py => hello.py.asc => hello.py.2 => hello.py.2.asc => ... => hello.py.$n => hello.py.$n.asc => ...

Misc

BitShares / ビットシェアズ

Bitsharesの基軸通貨はBTSと呼ばれます。このBTSの発行上限は約37億BTSであり、スタート時にはそのうち約25億が配布されました。残りの約12億は、取引の承認者に支払われる報酬金などの用途のため、準備金プール(Reserve Pool)と呼ばれる、誰もコントロールできない資産としてブロックチェーン上に保管されています。Bitsharesにおける取引手数料の20%はこの準備金プールへと送られます。 Bitsharesにおける取引承認のシステムは、DPOS(Delegated Proof of Stake、代表者によるProof of Stake)と呼ばれています。DPOSにおける取引の承認者はwitness(立会人)と呼ばれています。witnessには誰でも立候補することができ、BTS保有者の投票により選ばれ、また、投票によりwitnessの座から下ろすことも可能です。この投票権は、全BTS保有者に保有量に応じて割り当てられており、他人に投票権を渡すこともできます。 選ばれたwitnessは、一定時間ごとにシャッフルされて承認の順番が割り当てられ、順に取引・ブロックを承認していきます。承認をしなかったwitnessは順番が飛ばされ次のwitnessが承認を行います。承認を行うごとに、witnessはBTS保有者の投票により定められた一定の報酬(現在は1ブロック1.5BTS)がもらえます。この報酬は先の準備金プールから支払われます。 かつては、101人がwitnessに選出されていましたが、さらに少ない人数でもセキュリティ的には十分であることや、多すぎるとwitnessに支払う総報酬が多くなりコストがかさむ問題や投票者がwitness一人一人を評価することが困難になる問題などがあるため、現在では20人前後となっています。

Others

  • 20 MINS INTRO TO CONSENSUS
  • Byzantine Fault Tolerance Algorithmes, Practical Byzantine Fault Tolerance, 1999 Castro, Liskov
  • Random Oracles in Constantinople: Practical Asynchronous Byzantine Agreement using Cryptography, 2000 Cachin, Kursawe, Shoup
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment