Block and chunk producer selection algorithm in simple nightshade

Staking
1

This post primarily focuses on how block and chunk producers will be selected once sharding is enabled.

Background

Due to the complex nature of challenges, we decide to enable sharding first with all block producers tracking all shards and we call this version The Simple Nightshade. Naturally it implies that block producers will have to run more expensive hardware, which harms the decentralization of the network. Fortunately, not everyone who stakes will have to track all shards — chunk producers, who are solely responsible for producing chunks in some shard, will only need to track one shard and therefore can run with the same hardware requirement as what we require today. Furthermore, we can have a large set of chunk producers to increase the number of validators, thereby improving the decentralization of the network.

Proposal

To ground the proposal in concrete numbers, let’s say we have up to 100 block producers and up to 300 chunk producers (these numbers are subject to change). When validators stake, they specify whether they would like to become a block producer or a chunk producer. At the end of each epoch, the proposals are collected and we calculate the new block and chunk producer set by

  • If there are N proposals for block producers, the top min(100, N) proposals are selected.
  • If there are M proposals for chunk producers, then we pool the proposals for block producers and chunk producers together, order them by their stake in decreasing order, and take the first min(100 + 300, N + M) proposals to be chunk producers.

We will not discuss in this post how block and chunk producers map to each height. There is already an existing proposal on this topic and we can mostly follow the same proposal. Some important things to note here:

  • Each shard should have at least a few different chunk producers so that even if a chunk producer is offline, the shard can still keep operating.
  • As we can see from the selection process mentioned above, block producers can and in most cases will be chunk producers as well.
  • Those who stake to become chunk producers should only be responsible for one shard so that there is no unpredicted increase in hardware requirement. On the other hand, block producers are free to be chunk producers in multiple shards since they already track every shard and it takes very little extra effort to produce chunks.

The total reward will be split equally between block producers and chunk producers, i.e, block producers will together earn 50% of the reward and the same with chunk producers. For each individual block producer, their reward will be calculated as

total_block_producer_reward * adjusted_online_ratio * validator_stake / total_block_producer_stake

Similarly, for each individual chunk producer, their reward will be calculated as

total_chunk_producer_reward * adjusted_online_ratio * validator_stake / total_chunk_producer_stake

where adjusted_online_ratio is computed as

min((online_ratio - 0.9) / (0.99 - 0.9), 1)

Notice that in the majority of cases total_chunk_producer_stake will be the same as the sum of all stakes between block producers and chunk producers. Therefore for someone with a large amount of stake, per capita return is strictly better if they stake for block producer.

Drawbacks

  • Implementation requires adding a new action StakeForChunkProducer. Because of this, the current staking pool implementation will not work directly for chunk producers and there needs to be a separate staking pool implementation. However, in the longer term this may not be a huge concern since chunk producers will likely not require a lot of tokens and they may be able to stake their own tokens without needing to pool tokens from other token holders.
9 Likes
2

Perhaps this should be cross-posted in http://gov.near.org/c/gov/6

1 Like
3

Discussed with @birchmd and Misha yesterday again about this. We realized that

  • The scheme that I proposed above will burn some reward due to the way total chunk producer stake is computed, which is not ideal.
  • We want to incentive people with enough stake to become block producers to ensure the security of the entire system. This means that if the per capita return is the same for both chunk producers and block producers, since chunk producers run cheaper hardware, they would be more profitable.
  • In the proposal above chunk producers are chunk producers for only one shard. This is to reduce the complexity of the overall design. However, Misha pointed out that it may be desirable to incentivize chunk producers to validate some number of shards that is roughly proportional to their stake.

@eatmore I remember when we discussed this during one of the chain syncs, you had some ideas as well. Do you mind sharing your thoughts here?

1 Like
4

Can you explain why the reward gets burnt, and how much approximately?

The initial proposal explicitly says that it is more beneficial to be a block producer, and here you assume that it is not. I find the argument in the original proposal sound, why here you assume it might not be more beneficial to be a block producer if one has sufficient stake to be one?

What is the advantage of making chunk producers validate proportional to their stake?

5

First some nomenclature:

  • block producers (BPs) produce blocks
  • chunk producers (CPs) produce chunks (for some shard)

I will assume all BPs are also CPs for all shards (I think that makes the most sense). There also exist chunk-only producers (COPs) (that is the whole point of this proposal). I think it is important to distinguish BPs and COPs, and note that CPs = BPs \union COPs.

The reason some is burned is because the “chunk producer” reward is really the reward for COPs, but the total stake used in the denominator is the total CP stake (i.e. including both COPs and BPs). This was done on purpose to ensure that BPs always earn more reward per unit stake.

We are not assuming Bowen’s proposal does not make it correct to always be a BP if possible, I think that it does. The only point is that whatever scheme we choose must have this property, otherwise we will not have enough block producers.

I think having a correlation between hardware and stake is a nice property. Already we want BPs to have more hardware than COPs, and also more stake too. Now, if the minimum stake to become a BP is T, and I have T-1 staked as a COP, then I am in an awkward position where I could probably become a BP if I wanted to (getting a little bit more stake is likely possible), and it should improve my net return (assuming the rewards scheme is working properly). But I must upgrade my hardware first from something that can do one shard all of a sudden to something that can do all shards. That feels like a discontinuity which could be smoothed out if we had COPs with very high stake validating for multiple shards.

Another nice feature is being able to unify BP and COP proposals. All proposals would be to be a CP for some number of shards. BPs are those that are CPs for all shards. It is not clear exactly how this would work in terms of how proposals are accepted/prioritized, but I think could be a nice foundation for a clean solution.

6

If total_chunk_producer_stake includes the stake of block producers, then block producers should also receive chunk producer reward, in addition to block producer reward, and then no stake is burnt.

What’s wrong with this discontinuity, though?

With the model in which I am explicitly stating whether I want to validate all shards, or just one, I know exactly what hardware I need as a pool. If the shards are assigned to me proportional to the stake, then I need to be constantly upsizing / downsizing my hardware with delegations coming and going.

7

The way I understand Bowen’s proposal is the following, in pseudocode:

struct Proposal {
   account_id: AccountId,
   want_to_be_bp: bool,
   stake: Balance,
}

fn get_block_producers(proposals: Vec<Proposal>) {
  proposals.filter(|x| x.wants_to_be_bp).sort(stake).reverse().take(100)
}

fn get_chunk_producers(proposals: Vec<Proposal>) {
  proposals.sort(stake).reverse().take(400)
}

// here `block_producers` is the top 100 based on `get_block_producers`
fn compute_block_producer_reward(block_producers: Vec<Proposal>, total_reward: Balance) {
  let total_stake = block_producers.map(|x| x.stake).sum();
  let total_bp_reward = total_reward / 2;
  block_producers.map(|x| x.stake * total_bp_reward / total_stake)
}

// here `chunk_producers` is the top 400 based on `get_chunk_producers`
fn compute_chunk_producer_reward(chunk_producers: Vec<Proposal>, total_reward: Balance) {
  let total_stake = chunk_producers.map(|x| x.stake).sum();
  let total_cp_reward = total_reward - total_reward / 2;
  chunk_producers.map(|x| x.stake * total_cp_reward / total_stake)
}

It doesn’t appear that any stake gets burnt, the hardware requirements are known in advance, and block producers get significantly higher reward that chunk producers.

1 Like
8

The concern with allowing BPs to “double-dip” by also getting reward from the chunk producer side is that there will be no incentive for anyone to be chunk producers. In Bowen’s proposal the fraction of reward going to BPs and COPs is capped so that there is an incentive for both roles to be filled. If there are all BPs and no COPs then half the reward is unclaimed, creating an incentive to have COPs. On the other hand, if there are many COPs, and not very many BPs then upgrading a large-stake COPs to a BP could increase its reward per unit staked.

Yes, I agree this is an unfortunate feature of stake and hardware having no intrinsic relationship. It could be that there is not an elegant way to have it work well.

9

there will be no incentive for anyone to be chunk producers.

Technically, we don’t need an incentive to be a chunk producer: someone becomes a chunk producer if they don’t have enough stake to be a block producer, so they don’t really have a choice.

But it does matter when it comes to delegating: delegating to those who can’t be a block producer will be most certainly less profitable than to someone who can be a block producer.

Why not have total_chunk_producer_stake only include those who doesn’t want to be a block producer? It appears to create a natural market in which approximately the same stake will end up in both buckets, with a smaller number of larger pools as block producers, and a larger number of smaller pools as chunk producers?

10

Yes, the delegation is an important piece. If there is no incentive to be a COP, then rather than several token holders each create a COP, they could pool their resources to create one BP (e.g. via out-of-band cooperation or via delegation), and this could be a more profitable configuration, which would be bad for decentalization.

If the COP reward were only divided among COPs (and none of it burned), and there was equal stake in both BP and COP roles, then the reward per unit staked would be equal on both sides. However, there is greater overhead on the BP side because they need to run more expensive hardware to validate all shards, thus the profit on the BP side is lower. Therefore, it may be more profitable for some BPs to become COPs.

I suppose it’s not clear how many BPs could switch to COPs and be more profitable. It could be that it is acceptable to have there be more stake on the COP side as long as sufficient stake remains on the BP side. Maybe I should try to estimate what the equilibrium stake distribution looks like under some assumptions of cost overhead.

11

@alexatnear

Edit: I realized I made a mistake in my approximate calculation yesterday. The simple result (still using unrealistic assumptions like zero variance in stake distribution) is that the stake fraction is equal to the cost fraction (i.e. 10% higher cost for BPs means 10% more stake on the COP side). I’ll still do a more detailed calculation today.

Here is an approximate calculation of the equilibrium stake fraction (COP over BP) as a function of the increased hardware cost (BP over COP), assuming that COPs get all the total_chunk_producer_stake, as you suggested. It is only approximate because it makes a variety of bad assumptions, such as the variance of the stake distribution being zero. I’ll do a more precise calculation tomorrow, but I thought I would share this preliminary result.

When the hardware costs are the same the stake ratio is 1 (i.e. equal total stake for both COP and BP), as expected. But this changes very rapidly. Even with a 10%-20% increase in hardware cost, there is ~100x more stake on the COP side. This seems unacceptable to me because the stake on the BP side is what provides security to the network.

It will be interesting to see if a more precise calculation changes these results significantly.

12

In your model what percentage of the pool profits go towards offsetting hardware costs? That sounds like an important parameter (e.g. if it’s a negligible amount, naturally the ratio will remain 1).

Also note that block producers can set a higher fee (for example it’s not infeasible to expect that BPs will average 10-15%, and CPs will average 1-5% fees).

13

Sorry, I updated the post to fix a mistake I made yesterday. The stake fraction is much less extreme now.

I’m currently assuming a profit of 0 (i.e. return = cost). But we could sub in something closer to reality here.

This is a good point. The model currently does not include delegation (i.e. I am assuming BPs and COPs get full return from their share of the stake).

14

Another way we can tune things to make the stake fraction equal is to not split the rewards evenly. If f is the fraction of the reward allocated to BPs and x is the multiplicative factor increasing the BP hardware cost (i.e. COPs pay C and BPs pay xC), then the simple model predicts there is the same amount of BP and COP stake when f = x / (x + 1) or equivalently x = f / (1 - f). E.g. when f = 0.5 then x = 1, which makes sense since this corresponds to equal sharing of rewards, so they must have equal costs. E.g. If x = 1.2 (BPs pay 20% more in hardware) then we set f = 6 / 11 (i.e. BPs get ~55% of the reward instead of 50%) to obtain an equal amount of stake in both BP and COP roles.

15

Are you assuming that the per capita return is the same here? If so, why would delegators choose block producers with a much higher fee? Is it because they think block producers are more reliable?

16

Without doing any models or math, my gut feeling is that if you separate BP and CP rewards completely, it will settle on something along the lines of there being 10% more stake staked to Chunk Producers, but Block Producers having ~15% fees compared to Chunk Producers having ~5% fees, thus (a) making it approximately the same yield for the delegators, and (b) Block Producers having the extra fees offsetting higher hardware costs.

17

I don’t think delegation is very important when it comes to computing how much stake ends up in each role. Delegators have the same choice as anyone running a node (do I put my stake behind a block producer or a chunk-only producer?), and if BPs do have higher fees then the setup is even similar where the overhead for backing a BP is higher than backing a COP (the difference of course is the overhead is a fraction of the earnings rather than a constant amount). So then a similar model would apply and we would end up with a similar distribution of stakes. So for now I am going to ignore delegation, but if you feel strongly about it then I can try including it.

I’ll write up and post the model + calculations once I am finished with them. Then others can double check my work, point out any too outlandish assumptions, etc.

18

I’ve completed all the analysis I think can be done with a simple model. The full write up (including the assumptions and calculations) is here.

The main result is the following:
Let f be the fraction of the total reward given to block producers and x be the multiplicative factor on the block producers’ hardware cost over chunk-only producers (i.e. if COPs pay C then BPs pay xC). The entirety of the BP reward fraction is split among BPs (as in @Bowen 's proposal) and the entirety of the COP reward fraction (1 - f) is split among COPs (with no burn, as in @alexatnear 's modification of the proposal). Then the ratio of total COP stake to total BP stake is bounded as follows

(1-f)/f <= (total COP stake) / (total BP stake) <= x (1-f)/f

From this I conclude:

  • f = 0.5 (as in the original proposal) is not an acceptable value since this will skew the stake away from BPs
  • f will need to be tuned depending on the value of x
  • f should be a protocol parameter so that it can be tuned even after we ship this feature

Overall, though, I think @alexatnear 's modification of the proposal is a good one so long as we tune f appropriately. I like that we do not need to burn reward as in Bowen’s original proposal and I like that the parameter f gives us explicit control over the security (total BP stake) vs decentralization (total CP stake) trade off.

19

Sounds good. I believe x also depends on the number of shards we have and maybe there is a way to dynamically adjust the value of x based on overall system load, but we can go with a protocol level constant for now.

20

To summarize the discussion that just happened on the Chain sync:

Michael’s model concludes that, assuming that CPs and BPs stake their own assets, the ration of |CPs| to |BPs| will be between (1-f)/f and x(1-f)f where f is the percentage of stake that goes to BPs, and x is the price difference in hardware. Thus, with f= 0.5, the ratio will be between 1 and x. Assuming x is somewhat high, the ratio might get pretty high.

I claim that if we incorporate the delegation fees, the ratio will get very close to (f-1)/f. Specifically, see my comment above:

In this model say f is 50%, so the same reward is paid to the block producers and the chunk producers. Say the total stake of BPs is bs and the total stake of CPs is cs, and their fees are correspondingly bf and cf. Say my stake, as a delegator, is negligibly small compared to b and c. Then if I delegate to one of the BPs, I will receive half_reward * (1 - bf) / bs, and if I delegate to one of the CPs, I will receive half_reward * (1 - cf) / cs. Correspondingly, the stakes will converge to values such that bs / cs = (1 - bf) / (1 - cf), and with my assumed rates of 15% and 5% it converges to the ratio of 0.89, which is acceptable, while block producers receive almost 3x more reward (0.89 x 3 specifically).