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

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

Attestation

今回はBeaconChainのAttestationについて学んだことを整理するために記事にする。
なお、Attestationの仕様については基本的に以下の公式のspecを参照した。
github.com

基礎知識

Beacon Chainではepochとslotという２つの時間の単位が存在する。1epoch = 32 slotであり、1 slot = 12 secである。slotが最小の時間単位となる。
また、ValidatorはCommitteeに割り当てられ、Committeeはslotに割り当てられる。

1 slotに割り当てられるCommitteeの数は最大64個であり、1 Committeeに含まれるValidatorの数は Active Validator / (32 * 64)となる。現在はActive Validatorが411,865なので、1つのCommitteeに大体201のValidatorが割り当てられている。

slotに割り当てられたValidatorの中から一人だけがBlock Proposerとして選出される。それ以外のValidatorはそのslotに対するvoteを行うAttestatorとなる。

Attestationとは

Eth 2.0において、ブロックに正当性を与えるための投票のことをAttestationと呼ぶ。
AttestationにはEth2.0で採用されている２つのコンセンサスルールである、LMD-GHOSTとCasper FFGの２つの投票を含む。

Attestationの構造

class Attestation(Container):
    aggregation_bits: Bitlist[MAX_VALIDATORS_PER_COMMITTEE]
    data: AttestationData
    signature: BLSSignature
  • aggregation_bits: Attest(=Vote)を行ったvalidatorのbit表現
  • data: voteの内容
  • signature: 集約したBLS署名

Attestationは重複したattest(=vote)の内容を集約したものである。集約については後述する。

AttestationDataの構造

class AttestationData(Container):
    slot: Slot
    index: CommitteeIndex
    # LMD GHOST vote
    beacon_block_root: Root
    # FFG vote
    source: Checkpoint
    target: Checkpoint
  • slot: このAttestationを行ったvalidatorが割り当てられているslot
  • index: このAttestationを行ったvalidatorが所属するcommitteeのindex
  • beacon_block_root: 現在のepoc内の投票するブロックのRoot値(LMD GHOSTのvote)
  • source: このAttestationを行ったvalidatorが正当と信じているjustifyされたepoch
  • target: このAttestationで正当とみなすepoch(通常は現在のepoc）

ValidatorはこのDataに対してBLS署名を付けてブロードキャストする。

Attestationが有効とみなされる条件

1. AttestationがAttestationData.slotと同一のepochのブロックに対しての投票であること。
1. Attestationの対象が、AttestationData.slotより前のブロックに対する投票であること
1. AttestationData.slotが現在のslotより32slot以内であること

３番目の条件を少し詳しく説明すると、つまりはValidatorはAttestationをブロードキャストするタイムリミットがあるということ。

enable attestation

遅すぎる投票（33slot以上の時間が経過したもの）は無効とされる。また、後述するが有効であっても、投票が遅い場合はrewardが減る。

Attestationの集約（Aggregation）

voteはその構造上、ほとんどの場合、同一の内容、つまり同一の対象に対しての投票で埋め尽くされる。
正常にblockが生成されている間は、常に、同じCommitteeのvalidatorはbeacon_block_rootに１つ前のブロックを指定し、sourceにはcurrent - 1のepochを、targetには現在のepochを指定することになる。
このように、attesteは重複した内容が大量に存在するため、ネットワーク帯域やBlockデータの節約のために集約されたAttestationに変換して、最終的にブロックに格納される。

また、Attestationに集約できるvoteの最大数は１つのCommitteeの参加人数と同じである。同じAttestationDataを持つvoteは１つのAttestationに集約される。

attest aggregation

1slotのCommitteeは最大で64グループが割り当てられるため、ブロックに格納されるAttestationの数は余裕をもって128までとなっている。
正常にBlockが生成されている間は１つのブロックにすべてのvoteが格納できる計算となる。

ただし、以前起きた7blockのreorgなどが発生すると、blockに格納しきれないvoteが発生する。1つのcommittee内で2つのblockへのvoteが発生する場合はギリギリ128個のAttestationに集約可能だが、1つのCommittee内で3つ以上のblockに対してvoteした場合は、64 * 3 = 192以上の種類のvoteが存在することになり、blockに格納可能なAttestation数を超えてしまうからである。

Attestationに対する報酬とペナルティ

正しいvoteを行ったvalidatorには条件に応じて BaseReward * n の報酬が与えられる。BaseRewardの計算は少しややこしいので、下記サイトを参照。
kb.beaconcha.in

報酬とペナルティの組み合わせは以下の４パターン

rewards and penarlties
  • source に指定したepochが最後にjustifyされたepochと一致していればBaseRewardの報酬。間違っていたらBaseRewardのペナルティ
  • targetに指定したepochが(自分が割り当てられたslotに対して)現在のepochと一致していればBaseRewardの報酬。間違っていたらBaseRewardのペナルティ
  • block_rootに指定したblockが自分の割り当てられたslotのblockと一致していればBaseRewardの報酬。間違っていたらBaseRewardのペナルティ
  • Attestationがblockに格納されたら7/8 * BaseRewardの報酬。ただし、自分のvoteが格納されたblockのslotより遅延していた場合は遅延に応じて報酬が除算される。つまり、自分のAttestationを含んだblockのslotが40で、自分の割り当てられたslotが38の場合は、inclusion delayが2となるので、 7/8 * BaseReward * 1/2が報酬となる。

すべてばｘになるパターンは、つまりvoteをしていない場合。つまり、non-activeな場合である。ここで上げているペナルティとはスラッシュとは別のもの。
基本的に、Validatorは次のslotのblockが作られるまでの間に、自分のslotのブロックに対するvoteを行うと報酬が最大となる。

なお、Block Proposerはtarget epochが有効なvoteごとにBaseReward * 1/8の報酬が得られる。(AttesterとProposerで報酬を分けあうことになる）。そのため、Block Proposerはできるだけ多くのAttestationを含めるインセンティブがある。

LMDとFFGの判定タイミング

LMDはAttestationが到達したタイミングで判定される。そのため、各nodeでは微妙にブロックに集まっている投票数が異なっている可能性があると思われる。

FFGの判定タイミングはepochが切り替わった瞬間である。また、この時に報酬も計算される。そのため、voteのtargetが一致していれば必ずinclusion rewardはもらえる。
FFGはAttestationを受け取った時とepochが切り替わった時の2回判定される。また、この時に報酬も計算される。そのため、voteのtargetが一致していれば必ずinclusion rewardはもらえる。（※2022/08/09追記）

Attestationのslashing条件

同一epoch内で異なる２つのブロックに対してvoteしたらslash対象となる。voteを行わない、いわゆるnon-activeな状態ではslash対象とはならない。間違ったブロックに投票してももちろんslash対象にはならない。あくまで、2つのブロックに投票したときのみslash対象となる。

疑問点

LMDの重みがリアルタイムと過去とで異なる

Attestationはblockに含まれたものだけが、BeaconStateに保存される。そのため、リアルタイムで見えているブロックの重みと最終的に有効となるブロックの重みには微妙な差異が生まれると思われる。(beacon-chain.mdのprocess_attestationとfork-choice.mdのon_attestationから判断)

実際大きな差異が発生することは少ないと思うが、これは結構問題な気もする。もし間違っていれば指摘してほしい。

Block Proposerがblockを提案しなかったら、attestorの報酬は減ってしまうのか？

報酬とペナルティの仕組みを見るとblock rootが現在のslotと一致しない場合は報酬が減額される。そうなると、proposerがブロックを提案しなかった場合も減額されるのかな？と思った。

上記疑問をもとにspecを見直してみると、headのチェックをする対象は下記の処理で決まっている。blockが提案されない場合はその１つ前のblock(というか、最後に有効とみなされたblock)が該当slotのheadとして格納されるので、blockがmissの場合は１つ前のslotのblockに対して投票すればよいことが分かる。

def process_slot(state: BeaconState) -> None:
    # Cache state root
    previous_state_root = hash_tree_root(state)
    state.state_roots[state.slot % SLOTS_PER_HISTORICAL_ROOT] = previous_state_root
    # Cache latest block header state root
    if state.latest_block_header.state_root == Bytes32():
        state.latest_block_header.state_root = previous_state_root
    # Cache block root
    previous_block_root = hash_tree_root(state.latest_block_header)
    state.block_roots[state.slot % SLOTS_PER_HISTORICAL_ROOT] = previous_block_root

参考

github.com
kb.beaconcha.in