State transition helpers

[paulhauner]

Description

This is a "mega issue" which contains multiple discreet tasks. Mega issues exist to avoid cluttering the issues page a multitude of small tasks.

If you wish to work on one of these tasks, comment below and a maintainer will break the task out into a separate issue.

Mega Issue Tasks

The beacon chain state transition function Helper functions section defines a series of small functions that assist in state transitions.

Where exactly each function should be implemented (e.g., a new crate, existing crate, etc) varies and should be addressed on a case-by-case basis.

Tasks are split into difficulties for your convenience.

Very Easy

• integer_squareroot: a common function that does a deterministic square root on integers.

Completed/split-off

The following helpers have already been implemented or split out into another issue:

• hash: digest some bytes.
• hash_tree_root Addressed in [WIP] Tree hash #88.
• is_active_validator: returns a true if a validator should be considered "active". Split into Add active validator helpers #139
• get_active_validator_indices: filters the set of validators down to only those which are "active". Split into Add active validator helpers #139
• get_shard_committees_at_slot: given a slot, returns the ShardAndCommittees for each shard. Split into Alex's transition helper bouquet #147
• get_block_root: returns a hash from the state. Split into Alex's transition helper bouquet #147
• get_beacon_proposer_index: returns the index of the beacon block proposer for a given slot. Split into Alex's transition helper bouquet #147
  - merkle_root: merkleize a list of values. Split into #146
• get_effective_balance: returns the validators "effective balance". This balance can never be higher that MAX_DEPOSIT (32 ETH presently). Split into Alex's transition helper bouquet #147
• get_fork_version: gets the version from some ForkData. Split into Alex's transition helper bouquet #147
• get_domain: returns a "domain" used for replay protection across forks/chains. Split into Alex's transition helper bouquet #147
• verify_slashable_vote_data: verify the signatures on some SlashableVoteData. Split into #149
• is_double_vote: determines if two attestations are a slashable "double vote". Split into #150
• is_surround_vote: determines if two attestations are a slashable "surround vote". Split into #150
• bls_verify
• bls_verify_multiple
• bls_aggregate_pubkeys
  - get_attestation_participants: returns the indices of the validators that
  are indicated as participating in attestation bitfields. Flagged as difficult as it will have many error conditions and will require lots of testing. Split into Implement get_attestation_participants #145
• shuffle: a primitive function that pseudo-randomly shuffles a list. Implemented.
• split: splits a list into n smaller lists in a deterministic and fail-safe manner.
  Implemented.
• get_shuffling: allocates a list of validators to committees that will attest to a shard. Split out into Implement/update get_shuffling #151

[ralexstokes]

i'll likely be tackling most of this as I handle #31 .

feel free to reach out for status as we can likely parallelize :)

[paulhauner]

Great stuff! Let me know as you progress through them and I'll keep this updated.

[chronaeon]

Mega issues exist to avoid cluttering the issues page a multitude of small tasks.

Nice touch!

[paulhauner]

Description has been updated to match the current spec.

[ralexstokes]

btw -- we just had a call where ppl are looking for good first issue -- i can take a pass by end of today at splitting this up into multiple functions

[ralexstokes]

also for the integer_squareroot above i suggest we use this: https://crates.io/crates/integer-sqrt

i started on a generic fn using the num crate but like the above crate better

[ralexstokes]

i would suggest we divide this issue into multiple issues to implement helpers so that it isn't all blocked on one or a few people; i'll put each chunk of related functions imo into a separate code block:

* is_active_validator: returns a true if a validator should be considered "active".
* get_active_validator_indices: filters the set of validators down to only those which are "active".

* get_shard_committees_at_slot: given a slot, returns the ShardAndCommittees for each shard.
* get_block_root: returns a hash from the state.
* get_beacon_proposer_index: returns the index of the beacon block proposer for a given slot.

* get_effective_balance: returns the validators "effective balance". This balance can never be higher that MAX_DEPOSIT (32 ETH presently).

* get_fork_version: gets the version from some ForkData.
* get_domain: returns a "domain" used for replay protection across forks/chains.

* merkle_root: merkleize a list of values.

* verify_slashable_vote_data: verify the signatures on some SlashableVoteData.

* is_double_vote: determines if two attestations are a slashable "double vote".
* is_surround_vote: determines if two attestations are a slashable "surround vote".

[paulhauner]

Good call @ralexstokes. I'll split this up :)

[johnsBeharry]

@paulhauner @ralexstokes

For merkle_root from what I've gathered there's a few other functionalities that are required to get this root hash:

add_leaf
get_leaf
make_tree
get_root_hash

Would this be correct?

[ralexstokes]

@johnsBeharry you would just need to translate this code into Rust for inclusion in our repo: https://github.com/ethereum/eth2.0-specs/blob/master/specs/core/0_beacon-chain.md#merkle_root

it isn't typed but values is something like a &[Hash32] in Rust and you just need to compute the root given the flat array as input.

seems like it would be a great way to get acquainted with Rust, Lighthouse and even the spec if you wanna go look at how it is used!

[ralexstokes]

looks like @drozdziak1 is gonna tackle this one: get_attestation_participants

[drozdziak1]

Yup, @paulhauner please assign me when you find the time to make the split

[paulhauner]

The only function left in here is integer_squareroot. I have some vague recollection of @ralexstokes working on this?

[ralexstokes]

@paulhauner refer this comment for integer_squareroot: #104 (comment)

i looked at implementing it ourselves and all things considered i now prefer to just use that crate as needed