State transition helpers

paulhauner commented 5 years ago

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 #88.
~~is_active_validator: returns a true if a validator should be considered "active".~~ Split into #139
~~get_active_validator_indices: filters the set of validators down to only those which are "active".~~ Split into #139
~~get_shard_committees_at_slot: given a slot, returns the ShardAndCommittees for each shard.~~ Split into #147
~~get_block_root: returns a hash from the state.~~ Split into #147
~~get_beacon_proposer_index: returns the index of the beacon block proposer for a given slot.~~ Split into #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 #147
~~get_fork_version: gets the version from some ForkData.~~ Split into #147
~~get_domain: returns a "domain" used for replay protection across forks/chains.~~ Split into #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 #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 #151

ralexstokes commented 5 years ago

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 commented 5 years ago

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

chronaeon commented 5 years ago

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

Nice touch!

paulhauner commented 5 years ago

Description has been updated to match the current spec.

ralexstokes commented 5 years ago

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 commented 5 years ago

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 commented 5 years ago

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 commented 5 years ago

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

johnsBeharry commented 5 years ago

@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 commented 5 years ago

@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 commented 5 years ago

looks like @drozdziak1 is gonna tackle this one: get_attestation_participants

drozdziak1 commented 5 years ago

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

paulhauner commented 5 years ago

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

ralexstokes commented 5 years ago

@paulhauner refer this comment for integer_squareroot: https://github.com/sigp/lighthouse/issues/104#issuecomment-452477141

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

sigp / lighthouse