Skip to main content

Selecting Chunk and Block Producers

Background

Near is intended to be a sharded blockchain. At the time of writing (March 2021), challenges (an important security feature for a sharded network) are not fully implemented. As a stepping stone towards the full sharded solution, Near will go through a phase called "Simple Nightshade". In this protocol, block producers will track all shards (i.e. validate all transactions, eliminating the need for challenges), and there will be an additional type of participant called a "chunk-only producer" which tracks only a single shard. A block includes one chunk for each shard, and it is the chunks which include the transactions that were executed for its associated shard. The purpose of this design is to allow decentralization (running a node which supports a chunk-only producer should be possible for a large number of participants) while maintaining security (since block producers track all shards). For more details on chunks see the subsequent chapter on Transactions. Note: the purpose of the "chunk-only" nomenclature is to reduce confusion since block producers will also produce chunks some times (they track all shards, so they will be able to produce chunks for any shard easily); thus the key distinction is that chunk-only producers only produce chunks, i.e. never produce blocks.

Near is a permissionless blockchain, so anyone (with sufficient stake) can become a chunk-only producer, or a block producer. In this section we outline the algorithm by which chunk-only producers and block producers are selected in each epoch from the proposals of participants in the network. Additionally, we will specify the algorithm for assigning those chunk-only producers and block producers to be the one responsible for producing the chunk/block at each height and for each shard.

There are several desiderata for these algorithms:

  • Larger stakes should be preferred (more staked tokens means more security)
  • The frequency with which a given participant is selected to produce a particular chunk/block is proportional to that participant's stake
  • All participants selected as chunk/block producers should be selected to produce at least one chunk/block during the epoch
  • It should be possible to determine which chunk/block producer is supposed to produce the chunk/block at height hh, for any hh within the epoch, in constant time
  • The block producer chosen at height hh should have been a chunk producer for some shard at height h1h - 1, this minimizes network communication between chunk producers and block producers
  • The number of distinct chunk-only/block producers should be as large as is allowed by the scalability in the consensus algorithm (too large and the system would be too slow, too small and the system would be too centralized) ^{\dagger}

\dagger Note: By "distinct block producers" we mean the number of different signing keys. We recognize it is possible for a single "logical entity" to split their stake into two or more proposals (Sybil attack), however steps to prevent this kind of attack against centralization are out of scope for this document.

Assumptions

  • The maximum number of distinct chunk-only producers and block producers supported by the consensus algorithm is a fixed constant. This will be a parameter of the protocol itself (i.e. all nodes must agree on the constant). In this document, we will denote the maximum number of chunk-only producers as MAX_NUM_CP and the maximum number of block producers by MAX_NUM_BP.
  • The minimum number of blocks in the epoch is known at the time of block producer selection. This minimum does not need to be incredibly accurate, but we will assume it is within a factor of 2 of the actual number of blocks in the epoch. In this document we will refer to this as the "length of the epoch", denoted by epoch_length.
  • To meet the requirement that any chosen validator will be selected to produce at least one chunk/block in the epoch, we assume it is acceptable for the probability of this not happening to be sufficiently low. Let PROBABILITY_NEVER_SELECTED be a protocol constant which gives the maximum allowable probability that the chunk-only/block producer with the least stake will never be selected to produce a chunk/block during the epoch. We will additionally assume the chunk/block producer assigned to make each chunk/block is chosen independently, and in proportion to the participant's stake. Therefore, the probability that the block producer with least stake is never chosen is given by the expression (1(smin/S))epoch_length(1 - (s_\text{min} / S))^\text{epoch\_length}, where smins_\text{min} is the least stake of any block producer and SS is the total relevant stake (what stake is "relevant" depends on whether the validator is a chunk-only producer or a block producer; more details below). Hence, the algorithm will enforce the condition (1(smin/S))epoch_length<PROBABILITY_NEVER_SELECTED(1 - (s_\text{min} / S))^\text{epoch\_length} < \text{PROBABILITY\_NEVER\_SELECTED}.

Algorithm for selecting block producers

Input

  • MAX_NUM_BP: u16 (see Assumptions above for definition)
  • epoch_length: u64
  • PROBABILITY_NEVER_SELECTED: Ratio<u128>
    • Ratio<u128> means a fraction where the numerator and denominator are represented by unsigned 128-bit numbers
  • block_producer_proposals: Vec<ValidatorStake> (proposed stakes for the next epoch from nodes sending staking transactions)
    • Note: there are separate actions to propose to be a chunk-only producer or a block producer. Here only block producer proposals are considered.

Output

  • block_producers: Vec<ValidatorStake> (chosen block producers for the next epoch)
  • block_producer_sampler: WeightedIndex
    • Data structure to allow O(1)O(1) sampling from the block producers with probability proportional to their stake
    • This structure will be based on the WeightedIndex implementation (see a description of Vose's Alias Method for details)

Steps

sorted_proposals =
sorted_descending(block_producer_proposals, key=lambda v: (v.stake, v.account_id))

# smallest value of s_min / S such that
# (1 - (s_min / S))^epoch_length < PROBABILITY_NEVER_SELECTED
min_stake_fraction =
1 - PROBABILITY_NEVER_SELECTED^(1/epoch_length)

total_stake = 0

block_producers = []
for v in sorted_proposals[0:MAX_NUM_BP]:
total_stake += v.stake
if (v.stake / total_stake) > min_stake_fraction:
block_producers.append(v)
else:
break

block_producer_sampler = WeightedIndex([v.stake for v in block_producers])

return (block_producers, block_producer_sampler)

Algorithm for assigning chunk producers to shards

Note: no algorithm for assigning block producers to shards is needed because we are working within "Simple Nightshade" where block producers track all shards.

Input

  • chunk_producers: Vec<ValidatorStake>
  • num_shards: usize
  • min_validators_per_shard: usize

Output

  • validator_shard_assignments: Vec<Vec<ValidatorStake>>
    • ii-th element gives the validators assigned to shard ii

Steps

  • While any shard has fewer than min_validators_per_shard validators assigned to it:
    • Let cp_i be the next element of chunk_producers (cycle back to the beginning as needed)
      • Note: if there are more shards than chunk producers, then some chunk producers will be assigned to multiple shards. This is undesirable because we want each chunk-only producer to be a assigned to exactly one shard. However, block producers are also chunk producers, so even if we must wrap around a little, chunk-only producers may still not be assigned multiple shards. Moreover, we assume that in practice there will be many more chunk producers than shards (in particular because block producers are also chunk producers).
    • Let shard_id be the shard with the fewest number of assigned validators such that cp_i has not been assigned to shard_id
    • Assign cp_i to shard_id
  • While there are any validators which have not been assigned to any shard:
    • Let cp_i be the next validator not assigned to any shard
    • Let shard_id be the shard with the least total stake (total stake = sum of stakes of all validators assigned to that shard)
    • Assign cp_i to shard_id
  • Return the shard assignments

In addition to the above description, we have a proof-of-concept (PoC) on GitHub. Note: this PoC has not been updated since the change to Simple Nightshade, so it assumes we are assigning block producers to shards. However, the same algorithm works to assign chunk producers to shards; it is only a matter of renaming variables referencing "block producers" to reference "chunk producers" instead.

Algorithm for selecting chunk producers

Input

  • MAX_NUM_BP: u16
  • MAX_NUM_CP: u16
  • epoch_length: u64
  • PROBABILITY_NEVER_SELECTED: Ratio<u128>
  • num_shards: usize
  • min_validators_per_shard: usize
  • block_producers_proposals: Vec<ValidatorStake>
  • chunk_only_producer_proposals: Vec<ValidatorStake>

Output

  • chunk_producers: Vec<ValidatorStake> (chosen chunk producers for the next epoch)
  • validator_shard_assignments: Vec<Vec<ValidatorStake>>
    • ii-th element gives the validators assigned to shard ii
  • chunk_producer_sampler: Vec<WeightedIndex>

Steps

# Group both sets of proposals together since all block producers
# can also serve as chunk producers.
validator_proposals = block_producers_proposals + chunk_only_producer_proposals
sorted_proposals =
sorted_descending(validator_proposals, key=lambda v: (v.stake, v.account_id))

# smallest value of s_min / S such that
# (1 - (s_min / S))^epoch_length < PROBABILITY_NEVER_SELECTED
min_stake_fraction =
1 - PROBABILITY_NEVER_SELECTED^(1/epoch_length)

# we assume the stake from chunk producers will be roughly
# evenly distributed among all the shards, so the stake fraction
# we care about is really smaller than the quantity above.
min_stake_fraction /= num_shards

chunk_producers = []
total_stake = 0
for v in sorted_proposals[0:(MAX_NUM_BP + MAX_NUM_CP)]:
total_stake += v.stake
if (v.stake / total_stake) > min_stake_fraction:
chunk_producers.append(v)
else:
break

chunk_producers.sort_descending(key=lambda v: (v.stake, v.account_id))
# using the algorithm above to assign shards
validator_shard_assignments =
assign_chunk_producers(chunk_producers, num_shards, min_validators_per_shard)

chunk_producer_sampler = [
WeightedIndex([v.stake for v in shard_cps]) for shard_cps in validator_shard_assignments
]

return (chunk_producers, validator_shard_assignments, chunk_producer_sampler)

Algorithm for sampling validators proportional to stake

This algorithm is applied using both chunk-only producers and block producers in the subsequent algorithms for selecting a specific block producer and chunk producer at each height.

Input

  • rng_seed: [u8; 32]
    • See usages of this algorithm below to see how this seed is generated
  • validators: Vec<ValidatorStake>
  • sampler: WeightedIndex

Output

  • selection: ValidatorStake

Steps

# The seed is used as an entropy source for the random numbers.
# The first 8 bytes select a block producer uniformly.
uniform_index = int.from_bytes(rng_seed[0:8], byteorder='little') % len(validators)

# The next 16 bytes uniformly pick some weight between 0 and the total
# weight (i.e. stake) of all block producers.
let uniform_weight = int.from_bytes(rng_seed[8:24], byteorder='little') \
% sampler.weight_sum()

# Return either the uniformly selected block producer, or its "alias"
# depending on the uniformly selected weight.
index = uniform_index \
if uniform_weight < sampler.no_alias_odds[uniform_index] \
else sampler.aliases[uniform_index]

return validators[index]

Algorithm for selecting producer of block at height hh

Input

  • h: BlockHeight
    • Height to compute the block producer for
    • Only heights within the epoch corresponding to the given block producers make sense as input
  • block_producers: Vec<ValidatorStake> (output from above)
  • block_producer_sampler: WeightedIndex
  • epoch_rng_seed: [u8; 32]
    • Fixed seed for the epoch determined from Verified Random Function (VRF) output of last block in the previous epoch

Output

  • block_producer: ValidatorStake

Steps

# Concatenates the bytes of the epoch seed with the height,
# then computes the sha256 hash.
block_seed = combine(epoch_rng_seed, h)

# Use the algorithm defined above
return select_validator(rng_seed=block_seed, validators=block_producers, sampler=block_producer_sampler)

Algorithm for selection of chunk producer at height hh for all shards

Input

  • (same inputs as selection of block producer at height h)
  • num_shards: usize
  • chunk_producer_sampler: Vec<WeightedIndex> (outputs from chunk-only producer selection)
  • validator_shard_assignments: Vec<Vec<ValidatorStake>>

Output

  • chunk_producers: Vec<ValidatorStake>
    • ith element gives the validator that will produce the chunk for shard i. Note: at least one of these will be a block producer, while others will be chunk-only producers.

Steps

bp = block_producer_at_height(
h + 1,
block_producers,
block_producer_sampler,
epoch_rng_seed,
)

result = []
for shard_id in range(num_shards):
# concatenate bytes and take hash to create unique seed
shard_seed = combine(epoch_rng_seed, h, shard_id)
# Use selection algorithm defined above
cp = select_validator(
rng_seed=shard_seed,
validators=validator_shard_assignments[shard_id],
sampler=chunk_producer_sampler[shard_id]
)
result.append(cp)

# Ensure the block producer for the next block also produces one of the shards.
# `bp` could already be in the result because block producers are also
# chunk producers (see algorithm for selecting chunk producers from proposals).
if bp not in result:
# select a random shard for the block producer to also create the chunk for
rand_shard_seed = combine(epoch_rng_seed, h)
bp_shard_id = int.from_bytes(rand_shard_seed[0:8], byteorder='little') % num_shards
result[bp_shard_id] = bp

return result