アルゴリズムとかオーダーとか

仕事で勉強したことなどをまとめてます

コードから読み解くCasper FFG

Casper Casper FFG Ethereum

github.com
Casper FFGの実装をVyperからSolidityに変換するProjectを実行していました。（一人で。。。）
今回はこの作業の中で理解したCasperの仕組みについてまとめていきます。
ちなみに、理解に合わせて疑問もでてきているのでその辺も合わせて書いていきたいと思います。

epoch について

initialize_epochは誰が叩くのか？

epoch = checkpointであり、checkpointに投票されるとminnerにも報酬が入るのでminnerがepoch生成すると思う。
これはプロトコロルとしてmining処理の１つとなるのか？minner任せでもいい気はする。

checkpointのfinalityについて

2/3のvalidatorの投票が必要

2/3のvalidatorが投票したcheckpointはjustifyされる（2/3以上のvalidatorが知っている ＝ main chainにこのブロックがある）

    # If enough votes with the same source_epoch and hash are made,
    # then the hash value is justified
    two_thirds_curdyn: bool = current_dynasty_votes >= self.total_curdyn_deposits * 2.0 / 3.0
    two_thirds_prevdyn: bool = previous_dynasty_votes >= self.total_prevdyn_deposits * 2.0 / 3.0
    enough_votes: bool = two_thirds_curdyn and two_thirds_prevdyn

    if enough_votes and not self.checkpoints[target_epoch].is_justified:
        self.checkpoints[target_epoch].is_justified = True
        self.last_justified_epoch = target_epoch
        self.main_hash_justified = True

https://github.com/ethereum/casper/blob/master/casper/contracts/simple_casper.v.py#L738-L747

連続するepochがjustifyされた時に初めてfinalizeされる

        # If two epochs are justified consecutively,
        # then the source_epoch finalized
        if target_epoch == source_epoch + 1:
            self.checkpoints[source_epoch].is_finalized = True
            self.last_finalized_epoch = source_epoch
            # Log source epoch status update
            log.Epoch(source_epoch, self.checkpoint_hashes[source_epoch], True, True)

https://github.com/ethereum/casper/blob/master/casper/contracts/simple_casper.v.py#L752-L758

式で書くとこんな感じ

checkpoint(N-1).is_justified && checkpoint(N).is_justified then checkpoint(N-1).is_finalized = True;

これは、１つ前のcheckpointについてまず2/3のvalidatorが自分はこのblockがmain chanにあることを信じてますと表明し、その次のepochにおいてさらに2/3のvalidatorがsource_epochとしてこのブロックがmain chainにあるのを知ってるよって表明することで、十分なvalidatorにそのblockがmain chainに存在していることが周知されたためfinalizeに十分な認知率を突破したとみなすことができるため。
逆に言えば、連続するepochがjustifyされなければfinality checkpointは作られない。

nothing at stakeへの防御策としてのslashingについて

２重投票やsource_epochとtarget_epochがクロスするような投票を行った場合はslashされる。このチェックは簡単。

    double_vote: bool = target_epoch_1 == target_epoch_2
    surround_vote: bool = (
        target_epoch_1 > target_epoch_2 and source_epoch_1 < source_epoch_2 or
        target_epoch_2 > target_epoch_1 and source_epoch_2 < source_epoch_1
    )

https://github.com/ethereum/casper/blob/master/casper/contracts/simple_casper.v.py#L416-L420

[補足]２重投票のやり方

  • まだ自分が投票したというtxが伝搬していないネットワークに繋げて再度投票する。

基本的にブロックチェーンは分散処理系で、かつデータの伝搬が非常に遅いで「２重な状態」は簡単に作れることに注意しないといけない。

slashによるdepositの減額

slashされるとwithdrawした時のdeposit額が減額されます。この時、ある一定範囲のepochで発生したslashに対して、不正を行った全員が責任を負う形になっています。

        recently_slashed: wei_value = self.total_slashed[withdrawal_epoch] - self.total_slashed[base_epoch]
        fraction_to_slash: decimal = convert(convert(recently_slashed * self.SLASH_FRACTION_MULTIPLIER, "int128"), "decimal") / \
                                     convert(convert(self.validators[validator_index].total_deposits_at_logout, "int128"), "decimal")

        # can't withdraw a negative amount
        fraction_to_withdraw: decimal = max((1.0 - fraction_to_slash), 0.0)

        deposit_size: wei_value = self.ONE_WEI_UINT256 * convert(
            floor(self.validators[validator_index].deposit * self.deposit_scale_factor[withdrawal_epoch]),
            "uint256"
        )
        withdraw_amount = self.ONE_WEI_UINT256 * convert(
            floor(
                convert(convert(deposit_size, "int128"), "decimal") * fraction_to_withdraw
            ),
            "uint256"
        )

    send(self.validators[validator_index].withdrawal_addr, withdraw_amount)

https://github.com/ethereum/casper/blob/master/casper/contracts/simple_casper.v.py#L668-L686

ここで溜まっていくdepositってどうなるんだろうか？
あとSLASH_FRACTION_MULTIPLIERとslashされた人の割合によるペナルティー分布図みたいなのってどこかにないのかなぁ？

Fork Choice rule

@public
@constant
def highest_justified_epoch(min_total_deposits: wei_value) -> uint256:
    epoch: uint256
    for i in range(1000000000000000000000000000000):
        epoch = self.current_epoch - convert(i, "uint256")
        is_justified: bool = self.checkpoints[epoch].is_justified
        enough_cur_dyn_deposits: bool = self.checkpoints[epoch].cur_dyn_deposits >= min_total_deposits
        enough_prev_dyn_deposits: bool = self.checkpoints[epoch].prev_dyn_deposits >= min_total_deposits

        if is_justified and (enough_cur_dyn_deposits and enough_prev_dyn_deposits):
            return epoch

        if epoch == self.START_EPOCH:
            break

    # no justified epochs found, use 0 as default
    # to 0 out the affect of casper on fork choice
    return 0


@public
@constant
def highest_finalized_epoch(min_total_deposits: wei_value) -> int128:
    epoch: uint256
    for i in range(1000000000000000000000000000000):
        epoch = self.current_epoch - convert(i, "uint256")
        is_finalized: bool = self.checkpoints[epoch].is_finalized
        enough_cur_dyn_deposits: bool = self.checkpoints[epoch].cur_dyn_deposits >= min_total_deposits
        enough_prev_dyn_deposits: bool = self.checkpoints[epoch].prev_dyn_deposits >= min_total_deposits

        if is_finalized and (enough_cur_dyn_deposits and enough_prev_dyn_deposits):
            return convert(epoch, "int128")

        if epoch == self.START_EPOCH:
            break

    # no finalized epochs found, use -1 as default
    # to signal not to locally finalize anything
    return -1

https://github.com/ethereum/casper/blob/master/casper/contracts/simple_casper.v.py#L451-L490

あるdeposit金額を満たすchainの中でfinalized or justifiedな一番最新のepochを返す関数です。clientはこの関数を使って、どのチェーンに所属するのかを決めます。

これは、ブロックチェーンは分散環境で動いているため、あるタイミングにおいては複数のネットワークでcheckpointがfinalizeされる可能性があります。block replecateにおいてそういった２つのブロックが取り込まれた時に、そのノードがどちらのブロックを正当とみなすのかを判別するための関数として用意されています。

最終的にはこれはnode実装の中に含まれて、かつnodeを実行するときのパラメータとかになるのかな？と予想。この辺に関係するPRってgo-ethereumに対してでてるのかな？まだ調べ切れてないです。

vote

voteの条件

    if already_voted:
        return False
    # Check that the vote's target epoch and hash are correct
    if target_hash != self.recommended_target_hash():
        return False
    if target_epoch != self.current_epoch:
        return False
    # Check that the vote source points to a justified epoch
    if not self.checkpoints[source_epoch].is_justified:
        return False

https://github.com/ethereum/casper/blob/master/casper/contracts/simple_casper.v.py#L504-L513
とあり、さらにrecommended_target_hash()は

@public
@constant
def recommended_target_hash() -> bytes32:
    return blockhash(self.current_epoch*self.EPOCH_LENGTH - 1)

https://github.com/ethereum/casper/blob/master/casper/contracts/simple_casper.v.py#L435-L438
とあります。

つまり、validatorは好きなblockに投票できるのではなく、投票先のminnerが知っているblockにしか投票できません。これはCasper FFGではPoW + PoSのhybrid-PoSであり、最初のblock生成がPoWで行われる以上、block自体は頻繁にforkします。そのため、投票準備中に見えていたblockが実際に投票が取り込まれた時にforkして存在してなくなり、validatorが意図しないblockへ投票を行わないための処置がされているのだと思います。

まとめ

ホワイトペーパーを読んでるだけでは見えてこなかった細かい部分が、やはりプログラムを通してみるとはっきりと理解できます。
ただ、Casper FFGの実装はまだ完了しているわけではなく、Castastrophic Crashes対策のinactivity leakあたりの実装が見当たりませんでした。
特にCasperではWithheldを抑えるために、投票をしていないvalidatorの数に合わせて全体的にwithdrawのときの返却レートが徐々に減っていく。みたいな仕組みになっています。それに従い、depositの時とwithdrawの時、及び各epoch間でのETHに対する内部保有量の比率が微妙に違っているのをそのまま扱うような複雑な処理になっています。
そのため、この辺りの計算式がふくざつで、まだinactivity leakが実装できていないのかなぁ？とか考えています。

現在、Casperの開発は Casper + Sharding v2に移行しており、Casper FFGの開発は現在のところでストップしているのですが、Casper v2を理解するためにはやはりCasper FFGの理解も必要なので、復習をかねて過去の実装も調べていく必要があります。

参考