Casper Chainの v2 仕様
Shardingのv1 specはこちら
TBD
beacon chainの実装
wshino.icon<ステーキングは1500ETH→32ETHに変更
wshino.icon<Casperと一緒に実装。Main chainとは別のbeacon chainに実装する
wshino.icon<今まで考えられていたよりもさらに多段になり、Main chainへの変更を減らす
wshino.icon<RANDAOとは複数のユーザーが任意のインプットを行うことでより安全な乱数を得られるようにする仕組み、 This is the work-in-progress document describing the specification for the Casper+Sharding chain, version 2. Unlike the earlier version, which heavily relied on the existing Ethereum PoW chain as a central chain, this spec uses as its base a full proof of stake chain based on a RANDAO beacon, attestations and the Casper FFG mechanism, with a relatively simple tie to the main PoW chain, including block referencing and one-way deposits.
これは、Casper + Shardingチェーンのバージョン2の仕様を記述した作業中の文書です。既存のEthereum PoWチェーンを中心にして大きく依存していた以前のバージョンとは異なり、この仕様では、RANDAOビーコン、アテステーション、キャスパーFFGメカニズムに基づくステークチェーンの完全な証拠を基盤として使用し、ブロックの参照や片方向の預金を含む主なPoWチェーンとの比較的単純な結びつきがあります。
Broad description of structure
There is a central PoS chain which stores and manages the current set of active PoS validators. The only mechanism available to become a validator initially is to send a transaction on the existing PoW main chain containing 32 ETH. When you do so, as soon as the PoS chain processes that block, you will be queued, and eventually inducted as an active validator until you either voluntarily log out or you are forcibly logged out as a penalty for misbehavior.
構造の大まかな説明
アクティブなPoS validatorの現在のセットを格納および管理する中央PoSチェーンがあります。最初にバリデーターになる唯一のメカニズムは、32 ETHを含む既存のPoWメインチェーン上でトランザクションを送信することです。そうすると、PoSチェーンがそのブロックを処理するとすぐに、あなたは自発的にログアウトするか、強制的にログアウトして不正行為のペナルティを受けるまで、キューに入れられ、最終的には有効なバリデータとして入金されます。
The primary source of load on the PoS chain is cross-links. A cross-link is a special type of transaction that says “here is the hash of some recent block on shard X. Here are signatures from at least 2/3 of some randomly selected sample of M validators (eg. M = 1024) that attest to the validity of the cross-link”. Every shard (eg. there might be 4000 shards total) is itself a PoS chain, and the shard chains are where the transactions and accounts will be stored. The cross-links serve to “confirm” segments of the shard chains into the main chain, and are also the primary way through which the different shards will be able to talk to each other.
PoSチェーンの負荷の主な原因はcross-linkです。cross-linkは、「シャードXの最近のブロックのハッシュがここにあります。M個のバリデータのランダムに選択されたサンプルの少なくとも2/3のシグネチャがあります(M = 1024など)。クロスリンクの妥当性を証明する」。すべてのシャード(例えば、4000個のシャードがあるかもしれない)自体がPoSチェーンであり、シャードチェーンはトランザクションとアカウントが格納される場所です。クロスリンクは、シャードチェーンのセグメントをメインチェーンに「確認」する役目を果たし、また、異なるシャードが互いに話すことができる主要な方法です。
wshino.icon<cross-linkでお互いに異なるshardが会話できる
Terminology
Validator - a participant in the Casper/sharding consensus system. You can become one by depositing 32 ETH into the Casper mechanism.
Active validator set - those validators who are currently participating, and which the Casper mechanism looks to produce and attest to blocks, cross-links and other consensus objects.
Notary - a signer of a cross-link
Committee - a (pseudo-) randomly sampled subset of the active validator set. When a committee is referred to collectively, as in “this committee attests to X”, this is assumed to mean “some subset of that committee that contains enough validators that the protocol recognizes it as representing the committee”.
Proposer - the validator that creates a block
Attester - a validator that is part of a committee that needs to sign off on a block.
Beacon chain - the central PoS chain that is the base of the sharding system.
Shard chain - one of the chains on which transactions take place and account data is stored.
Main chain - used here to refer to the existing PoW chain, though note that this is temporary; in the long run the beacon chain will be the main chain.
Cross-link - a set of signatures from a committee attesting to a block in a shard chain, which can be included into the beacon chain. Cross-links are the main means by which the beacon chain “learns about” the updated state of shard chains.
Epoch - a period of 100 blocks.
SHARD_COUNT - a constant referring to the number of shards. Currently set to 1024.
NOTARIES_PER_CROSSLINK - a constant referring to the size of the notary set for a crosslink. Currently set to 1024.
用語
Validator - Casper / shardingコンセンサスシステムの参加者。 32 ETHをキャスパー機構に預けることで、あなたは1つになることができます。
Active validator set - 現在参加しており、キャスパーメカニズムがブロック、クロスリンクおよびその他のコンセンサスオブジェクトを生成し、それを証明するように見えるバリデータです。
Notary - クロスリンクの署名者
Committee - アクティブバリデータセットの(疑似)ランダムにサンプリングされたサブセット。 「この委員会がXに証明する」のように、委員会がまとめて言及された場合、これは、議定書が委員会を代表すると認める十分な検証者を含む委員会の一部のサブセットを意味するとみなされる。
Proposer - ブロックを作成するバリデータ
Attester - Committeeの一部であり、ブロックでサインオフする必要があるバリデーター。
Beacon chain - シャーディングシステムのベースとなる中央PoSチェーン。
Shard chain - トランザクションが発生し、アカウントデータが格納されているチェーンの1つ。
Main chain - ここでは既存のPoWチェーンを指すために使用されますが、これは一時的なものです。長期的にはビーコンチェーンが主要なチェーンになります。
Cross-link - ビーコンチェーンに含めることができるシャードチェーンのブロックを証明する委員会からの署名のセット。クロスリンクは、ビーコンチェーンが更新されたシャードチェーンの状態を「知る」ための主な手段です。
Epoch - 100ブロックの期間。
SHARD_COUNT - シャード数を示す定数です。現在は1024に設定されています。
NOTARIES_PER_CROSSLINK - クロスリンクの公証人のサイズを参照する定数。現在は1024に設定されています。
Main chain changes
This PoS/sharding proposal can be implemented separately from the main chain. Only two changes to the main chain are required (and the second one is technically not strictly necessary).
On the main chain a contract is added; this contract allows you to deposit 32 ETH; the deposit function also takes as arguments (i) pubkey (bytes), (ii) withdrawal_shard_id (int), (iii) withdrawal_addr (address) and (iv) randao_commitment (bytes32)
Main chain clients will implement a method, prioritize(block_hash, value). If the block is available and has been verified, this method sets its score to the given value, and recursively adjusts the scores of all descendants. This allows the PoS beacon chain’s finality gadget to also implicitly finalize main chain blocks.
Main chainの変更
このPoS / Shardingプロポーザルは、メインチェーンとは別に実装できます。Main chainへの2nつの変更のみが必要です(2番目は主に厳密には必要ありません)。 Main chainにはContractが追加されています。このContractにより、32 ETHを入金することができます。デポジット関数はまた、(i)pubkey(バイト)、(ii)withdrawal_shard_id(int)、(iii)withdrawal_addr(アドレス)および(iv)randao_commitment(bytes32) 主チェーンクライアントは、優先順位付け(block_hash、value)のメソッドを実装します。ブロックが使用可能であり、検証されている場合、このメソッドはスコアを指定された値に設定し、すべての子孫のスコアを再帰的に調整します。これにより、PoSビーコンチェーンの最終ガジェットが暗黙的にメインチェーンブロックをファイナライズすることができます。
Beacon chain
The beacon chain is the “main chain” of the PoS system. The beacon chain’s main responsibilities are:
Store and maintain the set of active, queued and exited validators
Process cross-links (see above)
Process its own block-by-block consensus, as well as the FFG finality gadget
Beacon chain
Beacon chainは、PoSシステムの「Main chain」である。Beacon chainの主な責務は次のとおりです。 アクティブな、キューに入れられた、および終了したバリデータのセットを保存し、維持する クロスリンクを処理する(上記参照) FFGファイナリティガジェットと同様に、ブロックごとのコンセンサスを処理する
Here are the fields that go into every beacon chain block:
すべてのBeacon chainブロックに入るフィールドは次のとおりです。
code:javascript
fields = {
# Hash of the parent block
'parent_hash': 'hash32',
# Number of skips (for the full PoS mechanism)
'skip_count': 'int64',
# Randao commitment reveal
'randao_reveal': 'hash32',
# Bitfield of who from the attestation committee participated
'attestation_bitfield': 'bytes',
# Their aggregate sig
# Shard aggregate votes
# Reference to main chain block
'main_chain_ref': 'hash32',
# Hash of the state
'state_hash': 'bytes',
# Signature from proposer
}
The beacon chain state is split into two parts, crystallized state and active state. Active state changes every block, whereas crystallized state changes only every epoch (100 blocks). Here’s active state:
beacon chainのstateは、crystallized stateとactive stateの2つの部分に分割される。active stateはブロックごとに変化しますが、crystallized stateはエポック(100ブロック)ごとに変化します。以下はactive stateです
code:javascript
fields = {
# Block height
'height': 'int64',
# Global RANDAO beacon state
'randao': 'hash32',
# Which validators have made FFG votes this epoch (as bitfield)
'ffg_voter_bitfield': 'bytes',
# Block attesters in the last epoch
# Storing data about crosslinks-in-progress in this epoch
# Total number of skips (used to determine minimum timestamp)
'total_skip_count': 'int64',
# Block proposers in the last epoch
}
Each PartialCrosslinkRecord is an object containing information about crosslinks that are being put together during this epoch:
各PartialCrosslinkRecordは、このエポック中に一緒に置かれているクロスリンクに関する情報を含むオブジェクトです。
code:javascript
fields = {
# What shard is the crosslink being made for
'shard_id': 'int16',
# Hash of the block
'shard_block_hash': 'hash32',
# Which of the eligible voters are voting for it (as bitfield)
'voter_bitfield': 'bytes'
}
Each RecentProposerRecord is an object containing information about recent block proposers:
各RecentProposerRecordは、最近のブロック提案者に関する情報を含むオブジェクトです。
code:javascript
fields = {
# Proposer index
'index': 'int24',
# New RANDAO commitment
'randao_commitment': 'hash32',
# Balance delta
'balance_delta': 'int24'
}
And here’s the crystallized state:
そしてここにcrystallized stateがあります
code:javascript
fields = {
# List of active validators
# List of joined but not yet inducted validators
# List of removed validators pending withdrawal
# The permutation of validators used to determine who
# cross-links what shard in this epoch
# The current epoch
'current_epoch': 'int64',
# The last justified epoch
'last_justified_epoch': 'int64',
# The last finalized epoch
'last_finalized_epoch': 'int64',
# The current dynasty
'dynasty': 'int64',
# The next shard that cross-linking assignment will start from
'next_shard': 'int16',
# The current FFG checkpoint
'current_checkpoint': 'hash32',
# Records about the most recent crosslink for each shard
# Total balance of deposits
'total_deposits': 'int256',
# Used to select the committees for each shard
'crosslink_seed': 'hash32',
# Last epoch the crosslink seed was reset
'crosslink_seed_last_reset': 'int64'
}
Each ValidatorRecord is an object containing information about a validator:
各ValidatorRecordは、バリデーターに関する情報を含むオブジェクトです。
code:javascript
fields = {
# The validator's public key
'pubkey': 'int256',
# What shard the validator's balance will be sent to
# after withdrawal
'withdrawal_shard': 'int16',
# And what address
'withdrawal_address': 'address',
# The validator's current RANDAO beacon commitment
'randao_commitment': 'hash32',
# Current balance
'balance': 'int64',
# Dynasty where the validator can
# (be inducted | be removed | withdraw their balance)
'switch_dynasty': 'int64'
}
And a CrosslinkRecord contains information about the last fully formed crosslink to be submitted into the chain:
また、CrosslinkRecordには、最後に完全に形成されたクロスリンクに関する情報がチェーンに送信されます。
code:javascript
fields = {
# What epoch the crosslink was submitted in
'epoch': 'int64',
# The block hash
'hash': 'hash32'
}
The state root is equal to the concatenation of blake(serialize(crystallized_state)) and blake(serialize(active_state)). Note that this means that most of the time, when the crystallized state is not changed, it does not need to be re-hashed. The active state is generally relatively small (eg. ~1 MB at the theoretical max of 4M validators, ~100kb realistically), and the crystallized state is larger, reaching into the tens of megabytes.
state rootはblake(serialize(crystallized_state))とblake(serialize(active_state))の連結に等しい。これは、ほとんどの場合、crystallized stateが変化しない場合、再ハッシュ化する必要がないことに留意されたい。active stateは一般的に比較的小さい(例えば、4Mバリデーターの理論的最大値で約1MB、現実的には約100kb)、crystallized stateはより大きく、数十メガバイトに達する。
Beacon chain processing
Processing the beacon chain is fundamentally similar to processing a PoW chain in many respects. Clients download and process blocks, and maintain a view of what is the current “canonical chain”, terminating at the current “head”. However, because of the beacon chain’s relationship with the existing PoW chain, and because it is a PoS chain, there are differences.
For a block on the beacon chain to be processed by a node, three conditions have to be met:
The parent pointed to by the parent_hash has already been processed and accepted
The main chain block pointed to by the main_chain_ref has already been processed and accepted
The node’s local clock time is greater than or equal to the minimum timestamp as computed by GENESIS_TIME + height * PER_HEIGHT_DELAY + total_skips * PER_SKIP_DELAY
If these three conditions are not met, the client should delay processing the block until the three conditions are all satisfied.
Block production is significantly different because of the proof of stake mechanism. Every time the client changes its view of the head (see the section on fork choice below for how the head is defined), they should compute the proposers of the block for all skip_count values from 0 to M for some reasonably large M (see below for algorithms). Let i be the skip_count where the client is selected. When the timestamp reaches minimum_timestamp(head) + PER_HEIGHT_DELAY + i * PER_SKIP_DELAY, and if the head has not changed by then, then the client should publish a new block.
When a client changes its view of the head, they should also compute the list of attesters (a set of validators that need to sign off on the head; see below for details), and immediately publish an attestation for that block, signing the serialized form of the parent block with their key.
Beacon chain processing
Beacon chainの処理は、多くの点でPoWチェーンの処理と基本的には似ています。クライアントはブロックをダウンロードして処理し、現在の「頭部」で終了している現在の「標準的なチェーン」のビューを維持します。しかし、ビーコンチェーンと既存のPoWチェーンとの関係、およびPoSチェーンであるために、違いがあります。 ビーコンチェーン上のブロックがノードによって処理されるためには、次の3つの条件を満たす必要があります。 parent_hashが指す親はすでに処理され、受け入れられています main_chain_refが指すメインチェーンブロックは、すでに処理され、受け入れられています ノードのローカルクロック時間は、GENESIS_TIME + height * PER_HEIGHT_DELAY + total_skips * PER_SKIP_DELAYで計算された最小タイムスタンプ以上です これらの3つの条件が満たされない場合、クライアントは3つの条件がすべて満たされるまでブロックの処理を遅らせる必要があります。 ブロック生産は、ステークメカニズムの立証のために大きく異なっている。クライアントがヘッドの見え方を変えるたびに(ヘッドがどのように定義されているかについてのフォーク選択のセクションを参照)、適度に大きいMの場合、0からMまでのすべてのskip_count値に対するブロックの提案者を計算する必要がありますアルゴリズムのために)。クライアントを選択したskip_countをiとします。タイムスタンプがminimum_timestamp(head)+ PER_HEIGHT_DELAY + i * PER_SKIP_DELAYに達し、ヘッドがそれまでに変更されていない場合、クライアントは新しいブロックを公開する必要があります。 クライアントがヘッドの見方を変更すると、アテスタのリスト(ヘッドでサインオフする必要がある一連のバリデータ、詳細は以下を参照)を計算し、そのブロックのアテステーションを即座に発行し、シリアライズされた親ブロックのフォームをそのキーで置き換えます。
wshino.icon<main chainで承認されているエポックのみshardingで処理されるってことかな
Beacon chain fork choice rule
When the beacon chain becomes a standalone PoS system, then the fork choice rule is a simple highest-scoring-block rule, where the score is the same as in Casper FFG:
score = last_justified_epoch + height * ε
While it is implemented as a tag-along for the PoW chain, then the fork choice rule is a dependent fork choice rule: the head of the beacon chain is the highest-scoring beacon chain block with a main_chain_ref that is inside the highest-scoring main chain.
Because of an additional validity condition that requires the main_chain_ref of a beacon block to be equal to or a descendant of that of its parent, this implies that the main_chain_ref of every block in this beacon chain is inside the highest-scoring main chain). This ensures that the beacon chain follows along the actual canonical main PoW chain.
This can be “updated online” using the following algorithms. First, it’s important to keep track of not just the head of the main and beacon chains, but also the block at every height. This can be maintained by the following algorithm, to be run at every change of the head:
Beacon chain fork choice rule
Beacon chainがスタンドアロンのPoSシステムになると、フォーク選択ルールはスコアがキャスパーFFGと同じである単純な最高得点ブロックルールになります。 スコア= last_justified_epoch + height *ε それがPoWチェーンのためのタグ・アウェイとして実装されている間、フォーク選択ルールは従属フォーク選択ルールです:ビーコン・チェーンの先頭は、スコアが最も高いビーコン・チェーン・ブロックで、main_chain_refが最高スコア内にあります主鎖。 ビーコンブロックのmain_chain_refがその親のそれの子孫またはそれの子孫であることを必要とする付加的な妥当性条件のために、これはこのビーコンチェーンにおける各ブロックのmain_chain_refが最高得点のMain chainの内側にあることを意味する)。これにより、ビーコンチェーンが実際のカノニカルなMain PoWチェーンに沿っていることが保証される。 これは、以下のアルゴリズムを使用して「オンラインで更新する」ことができます。まず、メインとビーコンチェーンのヘッドだけでなく、すべての高さでブロックを追跡することが重要です。これは、以下のアルゴリズムによって維持され、ヘッドのあらゆる変更時に実行される。
code:javascript
def update_head(chain, old_head, new_head):
a, b = old_head, new_head
while a.height > b.height:
a = get_parent(a)
while b.height > a.height:
b = get_parent(b)
while a != b:
a, b = get_parent(a), get_parent(b)
b = new_head
new_chain = []
while b.height > a.height:
new_chain = b + new_chain b = get_parent(b)
When receiving a new beacon chain block, change the head only if its score is an improvement over that of the head and the new block’s main_chain_ref is in the main chain:
新しいビーコン・チェーン・ブロックを受け取ったとき、そのスコアがヘッドのそれを上回る改善であり、新しいブロックのmain_chain_refがメイン・チェーンにある場合にのみ、ヘッドを変更します。
code:python
def should_I_change_head(main_chain, old_beacon_head, new_beacon_block):
return get_score(new_beacon_block) > get_score(old_beacon_head) and \
new_beacon_block.main_chain_ref in main_chain
After a reorg of the main chain, also reorg the beacon chain:
Main chainの再編成の後、Beacon chainを再編成する
code:python
def reorg_beacon_chain(main_chain, beacon_chain):
old_head = beacon_chain-1 while beacon_chain-1.main_chain_ref not in main_chain: beacon_chain.pop()
new_head = beacon_chain-1 while len(queue) > 0:
b = queue.pop(0)
for c in get_children(b):
if c.main_chain_ref in main_chain:
if get_score(c) > get_score(new_head):
new_head = c
queue.append(c)
update_head(beacon_chain, old_head, new_head)
wshino.icon<beacon chainを投票し、今の奴よりも大きく、main chainに存在するブロックの参照を持っている場合にのみforkが可能
Beacon chain state transition function
We now define the state transition function. At the high level, the state transition is made up of two parts:
The epoch transition, which happens only if active_state.height % SHARD_COUNT == 0, and affects the crystallized state and the active state
The per-block processing, which happens every block (if during an epoch transition block, it happens after the epoch transition), and affects the active state only.
The epoch transition generally focuses on changes to the validator set, including adjusting balances and adding and removing validators, as well as processing cross-links and setting up FFG checkpoints, and the per-block processing generally focuses on saving temporary records relating to the in-block activity in the active state.
Beacon chainの状態遷移関数
ここで状態遷移関数を定義する。高レベルでは、状態遷移は2つの部分で構成されます。 エポックトランジションは、active_state.height%SHARD_COUNT == 0の場合にのみ発生し、結晶状態とアクティブ状態に影響します ブロックごとの処理は、ブロックごとに行われます(エポック遷移ブロックの場合はエポック遷移後に行われます)、アクティブ状態のみに影響します。 エポックの移行は一般に、残高の調整やバリデータの追加と削除、クロスリンクの処理、FFGチェックポイントの設定など、バリデータセットの変更に重点を置いています。ブロック単位の処理では、active stateのブロック活動。
wshino.icon<1024%1024==0の時にエポックは更新される
Helper functions
We start off by defining some helper algorithms. First, an algorithm for pseudorandomly shuffling the validator set based on some seed:
Helper 関数
まず、いくつかのヘルパーアルゴリズムを定義します。最初に、いくつかのシードに基づいてバリデータセットを擬似乱数的にシャッフルするアルゴリズム:
code:python
def get_shuffling(seed, validator_count):
assert validator_count <= 16777216
rand_max = 16777216 - 16777216 % validator_count
o = list(range(validator_count)); source = seed
i = 0
while i < validator_count:
source = blake(source)
for pos in range(0, 30, 3):
remaining = validator_count - i
if remaining == 0:
break
if validator_count < rand_max:
replacement_pos = (m % remaining) + i
i += 1
return o
This algorithm will be used to select shard committees and to select proposers and attesters for blocks. Here’s the application of the method to choose the attester set for a given block and the proposer for the N-skip child of that block.
このアルゴリズムは、shard comitteeを選択し、ブロックの提案者と審査員を選択するために使用されます。ここでは、与えられたブロックとそのブロックのNスキップの子の提案者を選択する方法の適用があります。
code:python
def get_attesters_and_proposer(crystallized_state, active_state, skip_count):
attestation_count = min(len(crystallized_state.active_validators), ATTESTER_COUNT)
indices = get_shuffling(active_state.randao, len(crystallized_state.active_validators))
For shard crosslinks, the process is somewhat more complicated. First, we choose the set of shards active during each epoch. We want to target some fixed number of notaries per crosslink, but this means that since there is a fixed number of shards and a variable number of validators, we won’t be able to go through every shard in every epoch. Hence, we first need to select which shards we will be crosslinking in some given epoch:
シャード・クロスリンクの場合、プロセスはやや複雑です。まず、各エポック時にアクティブなシャードのセットを選択します。私たちは一定の数のnotaryをクロスリンクごとに対象にしたいと考えていますが、これは一定数のシャードとバリデーターが存在するため、各エポックごとにすべてのシャードを通過することはできません。したがって、我々は最初に、ある特定の時期に架橋するシャードを選択する必要があります:
code:python
def get_crosslink_shards(crystallized_state):
start_from = crystallized_state.next_shard
count = len(crystallized_state.active_validators) // NOTARIES_PER_CROSSLINK
if start_from + count <= SHARD_COUNT:
return list(range(start_from, start_from + count))
else:
return list(range(start_from, SHARD_COUNT)) + list(range(start_from + count - SHARD_COUNT))
Then we compute the notary set for any one of those shards:
次に、これらのshardのいずれかのnotary setを計算します。
code:python
def get_crosslink_notaries(crystallized_state, shard_id):
crosslink_shards = get_crosslink_shards(crystallized_state)
if shard_id not in crosslink_shards:
return None
all = len(crystallized_state.current_shuffling)
start = all * crosslink_shards.index(shard_id) // len(crosslink_shards)
end = all * (crosslink_shards.index(shard_id)+1) // len(crosslink_shards)
return crystallized_state.current_shufflingstart: end The current_shuffling is recalculated at the start of a dynasty transition.
current_shufflingは、dynasty移行の開始時に再計算されます。
Per-block processing
The per-block processing is broken down into three parts.
Checking attestation signatures
The expected number of attesters for a block is min(len(crystallized_state.active_validators), ATTESTER_COUNT); let this value be attester_count. Check that the attestation_bitfield as a bytearray of length (attester_count + 7) // 8. Interpret it as a list of bits going left to right (eg. bit 0 is attestation_bitfield0 >> 7, bit 9 is attestation_bitfield1 >> 6, etc). Check that any bits after attester_count-1 are all zero. Check that the total number of attesters (ie. the total number of one bits) is at least attester_count / (2 + block.skip_count). Interpret the one bits in the bitfield as a subset of the attesters sampled with get_attesters_and_proposer (see above); extract the indices of the attesters and then from crystallized_state.active_validators extract their public keys. Add up these public keys to make an aggregate key. BLS verify the attestation_aggregate_sig in the block using the aggregate key as a pubkey, and the serialized parent block as a message. Make sure that the verification passes.
Add a ProposerRecord to the recent_proposers list storing the proposer index, the proposer’s new RANDAO preimage and the number of attesters whose signatures they included. Add the indices of the attesters (in the order in which they appear in the bitfield) to recent_attesters.
ブロック単位の処理 ブロックごとの処理は3つの部分に分かれています。 アテステーションシグネチャの確認 ブロックの予想アテスタ数はminです(len(crystallized_state.active_validators)、ATTESTER_COUNT)。この値をattester_countにします。 attestation_bitfieldがlength(attester_count + 7)//8の長さであることを確認します。左から右に向かうビットのリストとして解釈します(例えば、ビット0はattestation_bitfield 0 >> 7、ビット9はattestation_bitfield 1 >> 6など)。 attester_count-1の後のビットがすべてゼロであることを確認してください。 attesterの総数(つまり、1ビットの合計数)が少なくともattester_count /(2 + block.skip_count)であることを確認します。 ビットフィールドの1ビットを、get_attesters_and_proposer(上記参照)でサンプリングされたアテスタのサブセットとして解釈します。 attestersのインデックスを抽出し、次にcrystallized_state.active_validatorsから公開鍵を抽出します。これらの公開鍵を追加して集約鍵を作成します。 BLSは、集約キーをpubkeyとして、シリアライズされた親ブロックをメッセージとして使用して、ブロック内のattestation_aggregate_sigを検証します。検証に合格することを確認します。 提案者の索引、提案者の新しいRANDAOの事前イメージ、およびそれらが含まれている署名者の数を格納しているrecent_proposersリストにProposerRecordを追加します。 attestersのインデックスをビットフィールドに表示される順序でrecent_attestersに追加します。 Checking partial crosslink records
A block can have 0 or more AggregateVote objects, where each AggregateVote object has the following fields:
部分的なcorsslinkレコードの確認
ブロックには0個以上のAggregateVoteオブジェクトがあり、各AggregateVoteオブジェクトには次のフィールドがあります。
code:python
fields = {
'shard_id': 'int16',
'shard_block_hash': 'hash32',
'notary_bitfield': 'bytes',
}
For each one of these votes:
Use get_shard_attesters to get the crosslink attester index list. Verify the aggregate sig against the notary bitfield in the same way as done for the block attesters above.
If a PartialCrosslinkRecord object already exists for the same shard ID and hash, add into its voter_bitfield the local indices of the validators that participated in the AggregateVote (that is, voter_bitfield |= AggregateVote.notary_bitfield). If a PartialCrosslinkRecord does not yet exist, create one.
Also add the indices of the voters into the active_state.ffg_voter_bitfield
Add a balance delta giving the block proposer a reward of n if there are n total voters that have not yet voted.
Save the new list of PartialCrosslinkRecord objects in order sorted by shard_block_hash.
これらの票のそれぞれについて: crosslink attesterインデックスリストを取得するには、get_shard_attestersを使用してください。上記のブロックアテスタの場合と同じように、公証ビットフィールドに対する集合sigを検証します。 PartialCrosslinkRecordオブジェクトが既に同じシャードIDとハッシュ存在する場合、そのvoter_bitfieldにAggregateVote(| = AggregateVote.notary_bitfieldつまり、voter_bitfield)に参加したバリデータのローカルインデックスを追加します。 PartialCrosslinkRecordがまだ存在しない場合は、作成します。 また、投票者のインデックスをactive_state.ffg_voter_bitフィールドに追加します n投票者がまだ投票していない場合、ブロック提案者にnの報酬を与える残高デルタを追加します。 PartialCrosslinkRecordオブジェクトの新しいリストをshard_block_hashでソートされた順に保存します。
Miscellaneous
Increase height by 1
Verify the signature on the block itself, using the block with the signature set to all zero bytes as signing data
Increase the total skip count by the block’s skip count
Verify that the block’s RANDAO reveal is the hash preimage of the proposer’s saved RANDAO commitment. XOR the block’s RANDAO reveal into the active RANDAO state, and set the RANDAO reveal to be the proposer’s new commitment
その他
高さを1増加させる すべてのゼロバイトが署名データとして設定されたブロックを使用して、ブロック自体の署名を検証する ブロックのスキップ数で合計スキップ数を増やす ブロックのRANDAO公開が、提案者が保存したRANDAOコミットメントのハッシュプリイメージであることを確認します。ブロックのRANDAO公開をアクティブなRANDAO状態にXORし、RANDAO公開を提案者の新しいコミットメントに設定する
Epoch transitions
When the current block height (ie. the height in the active state) is 0 mod SHARD_COUNT, we execute an epoch transition, which breaks down into several parts:
Calculate rewards for FFG votes
Compute the total deposits of every validator who participated in the last epoch (according to the FFG voter bitfield in the active state). If this value is >= 2/3 of the total deposits of all validators, set crystallized_state.justified_epoch to equal crystallized_state.current_epoch (note: this is still the previous epoch at this point in the computation). If this happens, and the justified epoch was previously crystallized_state.current_epoch - 1, set the crystallized_state.finalized_epoch to equal that value.
Compute the online_reward and offline_penalty based on the Casper FFG incentive and quadratic leak rules (not yet fully specified)
Add the online_reward to every validator who participated in the last epoch, and subtract the offline_penalty from everyone who did not
エポック遷移
現在のブロックの高さ(すなわち、アクティブ状態の高さ)が0 mod SHARD_COUNTのとき、私たちはいくつかの部分に分かれているエポック遷移を実行します:
FFG投票に対する報酬を計算する 最後のエポックに参加したすべてのバリデータの合計預金額を計算する(アクティブ状態のFFG投票者ビットフィールドに従って)。この値がすべてのバリデータの総デポジットの2/3より大きい場合は、crystallized_state.justified_epochをcrystallized_state.current_epochに等しく設定します(注:これはまだ計算のこの時点で前のエポックです)。これが起こり、正当化されたエポックが以前にcrystallized_state.current_epoch - 1だった場合、crystallized_state.finalized_epochをその値に等しく設定します。 Casper FFGインセンティブと二次漏れルール(まだ完全には指定されていない)に基づいてonline_rewardとoffline_penaltyを計算する 最後のエポックに参加したすべてのバリデータにonline_rewardを追加し、最後のエポックに参加したすべてのバリデータにonline_rewardを追加し、
Calculate rewards for crosslinks
Repeat for every shard:
Calculate the online_reward and offline_penalty for that crosslink.
Take the partial crosslink with the most votes (breaking ties by order of checkpoint hash). Reward any validator that participated in that partial crosslink; penalize any validator that did not.
If any crosslink reaches >=2/3 of its sample, weighted by total deposits (not including any balance deltas that are part of this epoch transition), save it as the most recent crosslink
クロスリンクの報酬を計算する すべてのシャードについて繰り返す: そのクロスリンクのonline_rewardとoffline_penaltyを計算します。 部分的なクロスリンクを最大の票数で行います(チェックポイントハッシュの順序で結びつける)。その部分架橋に参加したバリデーターには報酬を与えます。そうしなかったバリデータにはペナルティを科す。 いずれかの架橋がサンプルの2/3以上に達すると、全堆積物(このエポック転移の一部であるバランスデルタを含まない)で重み付けされ、最新の架橋として保存する
Process balance deltas
Increment the balance of everyone in recent_attesters by 1. Increment the balance of everyone in recent_proposers by the balance_delta in the RecentProposerRecord object.
プロセスバランスデルタ recent_attesters内の全員のバランスを1ずつ増やします。RecentProposerRecordオブジェクトのbalance_deltaでrecent_proposersの全員のバランスを増やします。
Crosslink seed-related calculations
If current_epoch - crosslink_seed_last_reset is an exact power of two, then using temp_seed = blake(crosslink_seed + bytes(log2(current_epoch - crosslink_seed_last_reset))), set current_shuffling = get_shuffling(temp_seed, len(new_active_validators)). Note that all of the temp committees are predictable from the crosslink_seed, but their positioning stretches out exponentially (eg. 10001 to 10002, 10002 to 10004, 10004 to 10008, 10008 to 10016…). The exponential backoff ensures that, if there has not been a crosslink for N epochs, the next committee will have ~N/2 epochs to process through and verify the ~N epochs worth of history for that shard, so the amount of work per second that the committee nodes need to perform is bounded.
クロスリンクシード関連の計算 current_epoch-crosslink_seed_last_resetが2の正確な累乗である場合、temp_seed = blake(crosslink_seed + bytes(log2(current_epoch-crosslink_seed_last_reset)))を使用して、current_shuffling = get_shuffling(temp_seed、len(new_active_validators))を設定します。臨時委員会はすべてcrosslink_seedから予測可能ですが、その配置は指数関数的に伸びています(例:10001〜10002,10002〜10004,10004〜10008,10008〜10016 ...)。 指数バックオフにより、N個のエポックのクロスリンクがない場合、次の委員会は〜N / 2個のエポックを持ち、そのシャードの〜N個のエポックに相当する履歴を確認するので、1秒あたりの作業量委員会ノードが実行する必要があるものは限定されています。 Dynasty transition
If the following two conditions are both true:
The last two epochs were both justified
The height of the most recent recorded crosslink for every shard is greater than or equal to crosslink_seed_last_reset
Then:
Set crystallized_state.dynasty += 1
Set crosslink_seed = active_state.randao
Go through all queued_validators, in order from first to last. Any validators whose switch_dynasty is equal to or earlier than the new dynasty are immediately added to the end of active_validators (setting switch_dynasty to the highest possible integer), up to a maximum of (len(crystallized_state.active_validators) // 30) + 1 (notice that because queued_validators is sorted, it suffices to check the queued validators at the beginning until either you’ve processed that many, or you reach one whose switch_dynasty is later than the current dynasty)
Go through all active_valdidators, and move any with either (i) balance equal to <= 50% of their initial balance, or (ii) switch_dynasty equal to or less than the new current dynasty, to exited_validators, moving up to a maximum of (len(crystallized_state.active_validators) // 30) + 1 validators
王朝移行 以下の2つの条件が両方とも真である場合: 最後の2つの時代はどちらも正当化された すべてのシャードの最新の記録されたクロスリンクの高さは、crosslink_seed_last_reset以上です 次に: crystallized_state.dynasty + = 1を設定する crosslink_seed = active_state.randaoを設定する すべてのqueued_validatorsを最初から最後の順に実行します。 switch_dynastyが新しい王朝と等しいかそれより前のバリデータは、直ちにactive_validatorsの最後に追加されます(switch_dynastyを可能な限り高い整数に設定します)。最大(len(crystallized_state.active_validators)// 30)+ 1 queueed_validatorsがソートされているので、キューに入れられたバリデータを処理したか、switch_dynastyが現在のダイナストよりも遅いものに達するまで、最初にキューに入れられたバリデータをチェックすれば十分です) すべてのactive_valdidatorsを通過し、(i)初期残高の<= 50%の残高、または(ii)新しい現在の王朝以下のswitch_dynastyを持つ移動先をexited_validatorsに移動し、最大( len(crystallized_state.active_validators)// 30)+ 1バリデーター
Miscellaneous
Increment the current epoch
Set the current_checkpoint to the hash of the previous block
Reset the balance deltas, FFG voter bitfield and partial crosslink list
Update the active validators’ RANDAO commitments based on the RecentProposerRecord values.
その他
現在のエポックをインクリメントする current_checkpointを前のブロックのハッシュに設定する 残高デルタ、FFG有権者ビットフィールド、部分的なクロスリストをリセットする RecentProposerRecord値に基づいて、アクティブバリデータのRANDAOコミットメントを更新します。
Overhead Analysis
With one validator per 32 ETH, we can look at three cases:
31250 validators (1M ETH), minimal case
312500 validators (10M ETH), average case
4000000 validators (assuming 128M ETH as a supply cap), worst case: literally everyone stakes
間接費分析
32 ETHあたり1つのバリデータを使用すると、3つのケースを見ることができます。 31250バリデーター(1M ETH)、最小限のケース 312500のバリデーター(10M ETH)、平均的なケース 4000000バリデーター(供給キャップとして128M ETHを仮定)、最悪の場合:文字どおりすべてのステークス
The size of the active state is:
アクティブ状態のサイズは次のとおりです。
code:python
'height': 8 bytes
'randao': 32 bytes,
'ffg_voter_bitfield': 1/8 bytes per validator,
'recent_attesters': 3 bytes/attesters, ~130 attesters/block, 100 blocks/epoch:
39000 bytes
'partial_crosslinks': PartialCrosslink * (validator count / 1024)
'total_skip_count': 8 bytes
'recent_proposers': (3 + 32 + 3) bytes per RecentProposerRecord *
100 proposers = 3800 bytes
The partial crosslinks add:
部分的なcrosslinkを以下を追加します
code:python
'shard_id': 2 bytes,
'shard_block_hash': 32 bytes,
'voter_bitfield': 1/8 bytes/validator * 1024 validators = 128 bytes
Each crosslink is thus 162 bytes, and the fixed data is 42848 bytes. Per validator, we get 1/8 bytes in the FFG bitfield, and 162/1024 ~= 0.158 bytes per validator in the partial crosslink,a total of ~0.283 bytes per validator. Hence, we get as the total active state size:
1M ETH: 42848 + 31250 * 0.283 = 51692 bytes
10M ETH: 42848 + 312500 * 0.283 = 131286 bytes
128M ETH: 42848 + 31250 * 0.283 = 1174848 bytes
したがって、各架橋は162バイトであり、固定データは42848バイトである。バリデータごとに、FFGビットフィールドでは1/8バイト、部分的なクロスリンクではバリデータごとに162/1024〜= 0.158バイト、合計でバリデータあたり〜0.283バイトが得られます。したがって、アクティブ状態の合計サイズは次のようになります。
1M ETH:42848 + 31250 * 0.283 = 51692バイト
10M ETH:42848 + 312500 * 0.283 = 131286バイト
128M ETH:42848 + 31250 * 0.283 = 1174848バイト
The size of the crystallized state is:
crystallized stateのサイズは、
code:python
'current_shuffling': 3 bytes per validator,
'current_epoch': 8 bytes,
'last_justified_epoch': 8 bytes,
'last_finalized_epoch': 8 bytes,
'dynasty': 8 bytes,
'next_shard': 2 bytes,
'current_checkpoint': 32 bytes,
'total_deposits': 32 bytes,
'crosslink_seed': 32 bytes,
'crosslink_seed_last_reset': 8 bytes
That’s a fixed cost of 141 bytes, not including the crosslinks and validators.
A ValidatorRecord contains:
これは141バイトの固定コストで、クロスリンクとバリデータは含まれていません。 ValidatorRecordには以下が含まれます:
code:python
'pubkey': 32 bytes,
'withdrawal_shard': 2 bytes,
'withdrawal_address': 20 bytes,
'randao_commitment': 32 bytes,
'balance': 8 bytes,
'switch_dynasty': 8 bytes
That’s 102 bytes in total. We’ll assume that the queued and exited sets are empty for simplicity and focus on the active set.
A CrosslinkRecord is just:
合計で102バイトです。ここでは、単純化とアクティブセットに焦点を当てるために、キューに入れられたセットとエグジットされたセットは空であると仮定します。 CrosslinkRecordは単なるです
code:python
'epoch': 8 bytes,
'hash': 32 bytes
So the crosslink_records list is just 40 bytes per shard. The total number of shards is determined by the maximum number of validators: 128 million / 32 / 1024 ~= 4000 shards, so crosslink_records would take up 160000 bytes.
Hence, with a fixed cost of 160141 bytes and a variable cost of 102 bytes per validator, we get as the total crystallized state size:
1M ETH: 160141 + 102 * 31250 = 3347641 bytes
10M ETH: 160141 + 102 * 312500 = 32035141 bytes
128M ETH: 160141 + 102 * 4000000 = 408160141 bytes
So in even the most extreme case, the beacon chain state can fit into even a relatively old computer’s RAM. Blake hashing 400 MB only takes ~1.0 seconds when tested on my machine (Thinkpad X270), a very acceptable worst-case result for something that is expected to only happen once per 100 blocks, though we can increase efficiency here further with judicious use of Merkle trees.
したがって、crosslink_recordsリストは1つのシャードあたり40バイトです。シャードの総数は、1282万個/ 32個/ 1024個〜4000個のシャードであるため、crosslink_recordsは160000バイトを占めます。 したがって、160141バイトの固定コストとバリデータあたり102バイトの可変コストで、我々は合計の結晶化状態サイズとなります: 1M ETH:160141 + 102 * 31250 = 3347641バイト 10M ETH:160141 + 102 * 312500 = 32035141バイト 128M ETH:160141 + 102 * 4000000 = 408160141バイト したがって、最も極端な場合でも、ビーコンチェーンの状態は比較的古いコンピュータのRAMにも適合します。 Blake hashing 400 MBは私のマシン(Thinkpad X270)でテストしたときに〜1.0秒しかかかりません。これは、100ブロックに1回しか起こらないと思われるものに対しては最悪の場合ですが、ここでさらに効率を上げることができます。メルクルの木。
A block contains:
ブロックは以下を含みます
code:python
'parent_hash': 32 bytes,
'skip_count': 8 bytes,
'randao_reveal': 32 bytes,
'attestation_bitfield': 1/8 byte per participant, so 16 bytes,
'attestation_aggregate_sig': 64 bytes,
'main_chain_ref': 32 bytes,
'state_hash': 64 bytes,
'sig': 64 bytes
An AggregateVote is:
集合投票は
code:python
'shard_id': 2 bytes,
'shard_block_hash': 32 bytes,
'notary_bitfield': 1/8 bytes/validator * 1024 validators,
'aggregate_sig': 64 bytes
A block without aggregate votes sums up to 312 bytes. Each aggregate vote is 226 bytes; we expect validator count / 1024 aggregate votes per epoch (and 1/100 that per block), so we get as the average block size:
1M ETH: 312 + 31250 * 226 / 1024 / 100 = 380 bytes
10M ETH: 312 + 312500 * 226 / 1024 / 100 = 1002 bytes
128M ETH: 312 + 4000000 * 226 / 1024 / 100 = 9140 bytes
Block processing requires:
Re-hashing active state
Re-hashing crystallized state (in an epoch transition only)
Verifying 1 BLS signature for the block, plus 1 for the attestations, plus 1 for each crosslink record. Best case: 2.30 per block, average case 5 per block, worst case: 41 per block
2 ECADD operations per epoch (ie. 0.02 per block) per validator for aggregate sig verification, plus a fixed ~128 ECADD operations per block. Best case ~753 (equivalent to <1 ECDSA sig), average case ~6378 (~5-10 ECDSA sigs), worst case ~80128 (~50-100 ECDSA sigs)
Many relatively cheap operations involving looping over validators, filling in bitfields, etc etc.
集計のないブロックは合計312バイトです。各集計投票は226バイトです。私たちはバリデータ数/ 1024エポックあたりの総投票数(ブロックあたり1/100)を期待しているので、平均ブロックサイズとして取得します。 1M ETH:312 + 31250 * 226/1024/100 = 380バイト 10M ETH:312 + 312500 * 226/1024/100 = 1002バイト 128M ETH:312 + 4000000 * 226/1024/100 = 9140バイト ブロック処理には、 再アクティブ化アクティブ状態 再結晶化状態の再ハッシング(エポック遷移のみ) ブロックの1つのBLSシグネチャを確認し、アテステーションの場合は1、クロスリンクレコードの場合は1を加えます。最良の場合:ブロックあたり2.30、ブロック当たり平均ケース5、最悪の場合:ブロックあたり41 集合SIG検証のバリデータ1エポックあたり2 ECADD演算(すなわち、ブロックあたり0.02)、ブロック当たり固定128 ECADD演算。最悪ケース〜80128(〜50-100 ECDSAシグナリング) バリデータのループ、ビットフィールドの埋め込みなどを含む比較的安価な操作
Note: this is ~80% complete. Main sections missing are:
Logic for the formats of shard chains, who proposes shard blocks, etc (in an initial release, if desired we could make cross-links just be Merkle roots of blobs of data; in any case, one can philosophically view the whole point of the shard chains as being a coordination device for choosing what blobs of data to propose as crosslinks)
Logic for inducting queued validators from the main chain
Slashing conditions
Logic for withdrawing deposits to shards
Per-validator proofs of custody
Convenience link to Full Casper chain v2 spec