get_new_shuffling: optimizing allocations

[paulhauner]

I have been looking into the get_new_shuffling() function from the v2.1 spec and I wanted to highlight something I noticed whilst testing.

I will first describe my understanding of the function, then present a scenario where the output of the function does not match my understanding. I'll then close with a single question.

High-level function description

From a conceptual level (i.e., not exactly as it's implemented in Python) the process of the function is roughly to:

1. Psuedo-randomly shuffle the validator indices.
2. Form the validators into committees (with respect to min_committee_size).
3. Assign those committees to shards (with respect to the crosslinking_start_shard).
4. With knowledge of the composition of the committees and number of shards, create ShardAndCommittee objects in each slot, based on some allocation requirements (see below).

Allocation requirements:

• Wherever possible, each slot should contain the same number of validators (viz., evenly distribute the validators across the cycle).
• The number of shards attested to in a cycle should be maximized (viz., attest to all the shards).
• Each validator must appear exactly once in a cycle (viz., everyone gets one vote).
• The highest shard index not attested to in the previous cycle should be the first shard attested to in this cycle. (viz., do round-robin shard allocation)

Where it doesn't meet the allocation requirements

What I am not seeing in the present implementation is "attest to all the shards". I have written a script here that runs get_new_shuffling() with the presented scenario and produces the following statement:

Scenario:

CYCLE_LENGTH=64
MIN_COMMITTEE_SIZE=128
SHARD_COUNT=1024
VALIDATOR_COUNT=131072

It's possible to make 1024 shard attestations, 
but get_new_shuffling() produces 576 with an 
average committee size of 227.56.

With 131072 validators and a minimum committee 
size of 128, it should be possible to create a committee
for each of the 1024 shards. 

Final question

Is my understanding of the requirements incorrect, or does the function not operate optimally?

Thanks, looking forward to feedback :)

[paulhauner]

This was discussed in the Eth 2.0 implementer call on 13/9.

It turns out that my understanding of the requirements is incorrect -- @vbuterin stated that the intention is in fact to target a committee size of 2 * min_committee_size.

I am going to close this issue, with the intention of producing some other document that describes the functional requirements of the get_new_shuffling fn to allow us to test the performance of the function.