Memo on Block Chain Study Group meeting #2

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

## ブロックチェーンとは

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

  • 高可用性、耐故障性

  • （ものによっては）匿名性

  • ？？？ 性能

過去の履歴も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 kuenishi@gmail.com --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) <kuenishi@gmail.com>"
$ 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) <kuenishi@gmail.com>"
$ 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) <kuenishi@gmail.com>"
$ 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

TODO: O(N) じゃない、Nonceを求める計算量？

あとから長い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 - 計算能力の51% をとって常にRewardを独占

  • 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を確保して、過去の歴史を遡って自分 が過半数をとれるブロックを探す。見つかったら、そこから歴史を今まで改 竄する。

Stake Grinding:

"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

他

GHOST Protocol

[Accelerating Bitcoin’s Transaction Processing - Fast Money Grows on Trees, Not Chains](https://eprint.iacr.org/2013/881.pdf)

1. Bitcoinのやつだとブランチしやすい→アタックを受けた時などにスループットが頭打ちになる（らしい 1. Branch selection 戦略を変える 1. “Greedy Heaviest-Observed Sub-Tree (GHOST)” protocol を提案

maintains the threshold of hash power needed to successfully pull off
a 50% attack at 50%, even if the network suffers from extreme delays
and the attacker does not.

B の子ブロックのうち、サブツリーに一番沢山ブロックを持っている子ブロックを正当なツリーとして認める 戦略

他にも、論文中では

  • Bitcoin/GHOSTのスループットの理論値を計算 (Bitcoinでは <1.0tps だったのに特定条件下で200を超えるように

  • レイテンシの理論値の評価 etc, etc, …

ところが… => Casper

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

    1. is this for a fixed node set? <= given there’s “n”

  • [Ripple Consensus Algorithm](https://ripple.com/files/ripple_consensus_whitepaper.pdf)

UNL (Unique Node List) を各クライアントでもって、それの 4/5 の合意がとれればOK（えー

### Etherium: PoW (rather a Smart Contracts platform)

Public な open ledger で、 Smart Contracts といわれる、チューリング完 全なプログラミング言語 (Solidity) とその処理系（EVM）がノード上に実装されている。

脆弱性もあり、Uncle Miningなどの設計が難しいので将来的に PoS に移行する => Casper

Casper is a security-deposit based economic consensus protocol.

  • Security-deposit based security and authentication ‘bonded validators’

  • Gambling on Consensus: ‘if on the other hand they do not quickly agree, they re-earn less of their deposit’

  • By-height Consensus: ‘Casper forfeits their security deposit.’

  • Transaction Finality: ???

  • Recovery from netsplits: ???

  • [ETHEREUM: A SECURE DECENTRALISED GENERALISED TRANSACTION LEDGER](http://gavwood.com/paper.pdf)

  • [Ethereum入門](http://book.ethereum-jp.net/)

Stellar: Stellar consensus protocol (TRUST)

  • Federated Byzantine Agreementというプロトコルを開発し、 PoW, PoS の問題を全て解決したと主張

  • Byzantine General Problem を限定的な状況について効率的に解いたとのこと

  • Quorum set とかいう不思議な概念で、このset毎に合意をとる（模様）→なぜか全体で上手くいく

BitShares: DPOS (Delegated PoS)

  • [Delegated Proof-of-Stake](https://bitshares.org/technology/delegated-proof-of-stake-consensus/):

    • Block Production by Elected Witnesses, which produce blocks and get

    • paid; netsplitもするよ

    • Each account is allowed one vote per share per witness, a process known as approval voting. The top N witnesses by total approval are selected. The number (N) of witnesses is defined such that at least 50% of voting stakeholders believe there is sufficient decentralization.

// * [Announcing BitShares 2.0](https://bitshares.org/blog/2015/06/08/announcing-bitshares-2.0/) // * [The History of Graphene](https://bitshares.org/blog/2015/06/15/the-history-of-graphene/)

詳しいものを発見できてない

Qointum; QDPoS

QueueにDelegate (これからサインするブロック候補）を積んで、それを blockchain entropy を使ってランダムに振り分けていく→より広範囲に分散 できてスケールできる

Consensusは [Maximally Vetted Delegate Chain](https://wiki.qointum.com/design/dev/#maximally-vetted-delegate-chain) の長さで決まる

References

# Omake

手作りの温かみのあるブロックチェーン (ブランチ選択なし）:

$ gpg -u kuenishi@gmail.com --clearsign hello.py.2

You need a passphrase to unlock the secret key for
user: "Kota UENISHI (nope) <kuenishi@gmail.com>"
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) <kuenishi@gmail.com>"

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

Misc

[BitShares / ビットシェアズ](http://jpbitcoin.com/bitcoin2/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