EC with multiple leaders

[sternhenri]

How to do multiple leader election in EC? @ZenGround0 recently pointed out an issue that has been vastly overlooked in doing multiple leaders in EC.

Currently election validation is specced here but this code needs to be updated (along with the md file) to explicit how multiple leaders is done.

(In this issue, we use expected_number_of_leaders_per_round = e.)

The straw-man solution would have us do something simple, namely:

• check that power_fraction * e < electionProof.Output

However, as @ZenGround0 points out this has unintended consequences, namely:

• There is no incentive to build power beyond 1/e of the network without creating another sybil (that may be fine)
• can get guaranteed wins (rather than probabilistic) with enough power
• Returns on investment are no longer linear
  e.g. a 25% miner will deterministically win at every round for e >= 4.

Perhaps the intended system should be closer to running e independent leader elections, thereby making a 25% miner 68% likely to win at least once (1-(1-.25)^4)). But this also has issues:

• More complex to implement (basically implement @jzimmerman's virtual sybils idea)
• Harder to reason about miner behavior accordingly
• Defeats purpose (in terms of bw) of having multiple winners if same miner wins multiple times (per @nikkolasg)

Two questions follow:

• What is the exact intended behavior we should seek
• How do we achieve it specifically for EC.

I am in favor of retaining the straw man at this time but this is a core question that has a wide impact on occurrence of null rounds as well as incentives and winning distribution, so I wanted to bring you in to opine before moving this to spec (by this Friday Nov 1).

[ZenGround0]

Proposed behaviors:

• Fairness -- miners win in proportion to storage power
• Tipset size -- we want to be able to fix the expected number of blocks
• Election process doesn't unduly pressure miners to sybil -- the 25% example above is maybe ok because its such a huge portion of network power but if all miner's have a clear incentive to never grow a miner actor above 0.001% or something that's a problem.

Places to look that have solutions we could rework

• Algorand
• Spacemint 3.5 proof quality sampling

Throwaway idea

• Elections could output some number of wins easy to derive from election proof (I think algorand works more like this). TIpset reward is then split proportionally by dividing one miner's number of wins / total.

[nikkolasg]

I would propose something simple:

• one block per miner per round

The idea is that by authorizing multiple blocks per miner in a given round naively (1) changes the dynamics of the power table as shown in this issue and (2) from the chain perspective, when a miner wins two blocks in a given round, it's equivalent to having a double sized block from same miner. Which I believe is not what we'd like, we'd like a distribution of (single sized) block issuer according to the distribution of the power table --> the "behavior" i'm aiming at is: *at each round, each miner has a pr. of winning one block ("fixed" size) w.r.t. to his power".

[sternhenri]

Both above comments are great.

Adding comments from @Kubuxu :

• Idea 1: What if there were e ticket slots? Ticket for each slot is derived by sha256(slotN..vrfout), and the ticket being in a slot results in mining reward for this slot.
  Miner having a ticket in any of the slots is allowed to publish a block (just one).
  • I think this would amplify selfish mining rewards.
• Idea 2: reward is related to how good the ticket is (where on the scale of 0 to power_fraction * e it falls).
  More generally what do we want miner behavior to be?

=== back to HS, restating nikkolasg and zenground0's points: my sense of intended behavior is

What is the intended behavior?

• 0. why higher e?
  • it should help the bw scale: specifically this is better than just bigger block size since blocks will be found across the network (in a dense graph leads to better link utilization)
  • this means there should be more miners winning rather than just more blocks produced.
  • Note that accordingly sybils should be disincentivized since they counter the above goal
• 1. block rewards earned should be proportional to power
  • this is the linear rewards argument

Proposal:
I think the point in either case is we should be careful to keep rewards and block production distinct here and not try and solve both problems. In the interim my original recommendation stands: as @nikkolasg states max 1 block per miner per round is easiest both to reason about and implement. It is commonly found in the literature (and done in eg. spacemesh, spacemint, etc).

Thereafter we may want to consider having some sort of quality metric for rewards as either @Kubuxu or @ZenGround0 discuss.
Note that if e grows far too large (e.g. e >10) we may want to revisit this design, and specifically it may be time to implement @jzimmerman 's virtual sybil idea.

[sternhenri]

The alternate proposal would just have us append an attempt number to the election to have e elections, so you would run this input through the VRF:

input | round number | i for i in [1, e].

Every miner would publish one block regardless of how many times they win, but would earn block rewards proportional to number of wins. This would lead to fewer blocks per round than e on expectation, but disincentivizes sybiling.

[nikkolasg]

So if we're going on with the "1 block per miner per round" idea, but haven't fixed on the block reward yet, we might want to make sure we include the information early on "how much time have you been elected". This relates to the "quality metric rewards" but I find it much simpler to reason about a concrete number (if you've been elected 5 times, you get 5x rewards).
Algorand seems to have a nice way to derive such a number without computing e times the VRF. Each user computes only once, and then divides the result spaces into different buckets, and then you count in which bucket your VRF output falls. Clearly, you should read Algorand section 5 and 5.1 to know about how're they doing.

I'm not sure about the block reward, didn't find it in the paper, but the idea of explicitly broadcasting the number of times an elected miner has been selected can allows us to try many variations of the block rewards (de/incentivizes sybils, etc)

[zixuanzh]

It will be a cleaner interface to the rest of the system if total block reward in a particular Epoch remains independent of e. If you mine more blocks, you get a bigger share of the total.

I like multiple elections more than one single election multiplied by e. It seems fishy to have guaranteed winning when miner size exceeds 1/e. Multiple elections are basically binomial coin flips and the expectation on the times of winning is e * p where p is the fraction of total power.

[nikkolasg]

It will be a cleaner interface to the rest of the system if total block reward in a particular Epoch remains independent of e. If you mine more blocks, you get a bigger share of the total.

Yeah but that's a biased way to see this since "if you mine more blocks" depends on e already. I can turn things around and say "if you have won more, you get a bigger share of the total", that's the same reasoning, but both depend on e anyway.

Given that (the fact that rewards depends on e), running only once a VRF avoids changing the statistics (see @sternhenri first post; basically gives you more chance to be selected), enables to fully utilize the network and more miners (more involvement since more chance to win a block compared to multiple block per miner), as well I'm afraid it increases the grinding surface - but it's just a fear, nothing concrete ^^) and is clear and simple.
How to adjust the block reward can be done via @Kubuxu idea or re-using Algorand's splitting idea.

Just saying my opinion on the matter ;)

[zixuanzh]

@nikkolasg Not sure if we are on the same page, what im saying is that the total reward, say B, allocated for each Epoch should be independent of the number of miners who mined a block in that Epoch. If 10 miners mine a block, then each of them gets (B / 10) FIL but only B in aggregate. If 5 miners mine a block, then each of them gets (B / 5) FIL and B in aggregate. Individual reward at an Epoch still depends on e but the total doesnt.

[sternhenri]

I think these are orthogonal points. You agree I believe :b

[nikkolasg]

Oh right, yes, no problem for doing that sorry for the confusion.
The point up for discussion here I believe is how to compute B. Either by saying "multiple blocks per miner per round" => then B is the total number of blocks, or "one block per miner per round, with information on how many times did one miner win" => then B is the total number of wins in a round, not the number of blocks.

[sternhenri]

To sum up, a few options (from @nikkolasg):

1. Multiple leader elections:

• ticket | round | i for i in [1, e]
  • a: each miner publishes at most one block: include up to e valid electionProofs in the block, earn numElectionProofs/totalElectionProofs share of epoch's reward
  • b: each miner can publish multiple blocks: each with a separate valid electionProof. Earn numBlocks/totalBlocks share of epoch's reward

2. Single leader election

• a: Use algorand sortition (see 5, 5.1 of paper, replacing token ownership with minimal storage unit / total storage.
  , reward based on number of wins (total)
• b: Multiply power_fraction by e (as stated above)
• c: Reward based on some notion of quality (e.g. value of hash output)

2a and 2b seem the most straightforward solutions that effectively separate rewards and sortition.

• 2a has the advantage of not incentivizing sybils. It is an effective solution to @jzimmerman 's virtual sybil idea.
• 2b is far simpler to analyze and understand but means miners can win with certainty rather than probabilistically (though they are the same on expectation), and that in order to avoid earning less than their share of power, they must sybilize if they have more than 1/e power (note that they will not earn more than their share of power by sybilizing).

[jzimmerman]

I think we can achieve the benefits of virtual Sybils without complicating the protocol by having multiple winning blocks per miner -- essentially, we would use the virtual Sybils to determine the number of "virtual blocks", which determines the miner's share of the epoch's total block reward; but in terms of actual blocks, there would still be at most one per miner. More precisely:

• Let R be the total expected block reward for a given epoch (a tunable parameter).
• Suppose miner M_i has K_i units of power (e.g., K_i sectors; or in general, a unit as finely divisible as possible), and the total power in the network is K = sum(K_i).
• For each miner M_i, the VRF is used to sample a value W_i from Poisson(e * K_i / K). This is the number of "virtual blocks" won by the miner. (In expectation, W = sum(W_i) = sum(e * K_i / K) = e.)
• If W_i > 0, the miner is eligible to publish exactly one block, but their reward for doing so is R * W_i / e. (In expectation, the total reward then is sum(R * W_i / e) = R, as desired.)

The analysis of the expectation holds not only for the whole network, but also for any would-be coalition; thus I believe the construction would not yield any advantage to coalitions, or conversely to Sybils, in terms of the expected return. Does that seem reasonable?

[sternhenri]

Yes, this is what is proposed in 2a above using binomial instead of Poisson, and effectively what Algorand does.

[Kubuxu]

I propose a variant of 2b/c.

Miner's eligibility for publishing a block is defined by:

h(vrfout)/2^256 < e * minerPower/totalPower // fractional function
h(vrfout) * totalPower < e * minerPower * 2^256 // integer function

Then after the miner won election, reward is defined by:

draw = h(vrfout)/2^256
req = e * minerPower/totalPowe
rewCount = ceil(req - draw)
reward = rewCount * targetRewardPerEpoch/e

This counts how many times over the miner has won the election.

It can be simulated using very simple matlab script:

e = 10;
power = 0.15;
N = 100000;

draws = rand(N, 1);
req = e * power;

wins = max(ceil(req-draws),0); % if draw < req { win++; draw+=1 }

mean(wins)

[nikkolasg]

@Kubuxu Can't you do something similar without the e in the eligibility check as well ? (and keeping the e in the reward function). From what I see, you derived yet another way to count how many times one has won (other ways are algorand, or using Joe's poisson dist. etc). That's cool because it seems simpler than the other ways. But if we have that, do we still need to multiply by e during the eligibility check ?

[Kubuxu]

We want e block producers per round (on average), to make sure that blocks are produced on a uniform interval, if e=1 (e eliminated from eligibility check) then there is ~30% chance that there won't be any blocks produced in a given round (assuming semi-uniform distribution of power). This would result in a null block and increased block interval and reduced network transaction throughput.

[Kubuxu]

This is the same reason algorand is using \tau in their Sortition function. They want \tau producers on average.

[sternhenri]

I understand your point @nikkolasg: you keep the deterministic aspect with this solution.

My question is why do we need rewCount = ceil(req - draw) rather than just have rewCount = req? This doesn't solve your issue but it's a straightforward "win based on e*power_fraction" with rewards proportional to power fraction, which rids us of the sybil issue.

[Kubuxu]

@sternhenri if we don't do rewCount = ceil(req - draw) then miner that has 5% of the power, wins in 50% of the epochs (with e=10) and gets 5% reward in each case, which means he gets only 2.5% of total distributed reward.

@nikkolasg I will look at it.

[Kubuxu]

We have to adjust for the fact that the first lottery has run, a miner was able to submit the block. Small miners should get the full reward for that, big miners might have a guaranteed reward + some.

[sternhenri]

quoting from @Kubuxu "
The 5% miner will always get 100% reward (if he is selected), his draw will always be lower than req if he was selected to mine a block.then, req-draw > 0 , then ceil(req-draw) == 1

We can think of the result of it previously being set at 1. The ceil(req-draw) adjusts only when someones req > 1 , so he has more then 1/e power."

Put another way:

• a miner with f < 1/e power will always get 1/e rewards when they win (f% of the time), leading to f/e rewards on expectation.
• a miner with f' > 1/e power will get at least 1/e rewards when they win, and one more f' - e% of the time (in buckets based on how much power they have). They win every time, so they will get their fair share of rewards.

Take a miner with 12%, e = 10;

• req = 1.2
• draw uniformly drawn bet 0 and 1, so
  • rewCount = 1 80% of the time (for draw > .2)
  • rewCount = 2 20% of the time (for draw <= .2)
    meaning the miner will earn their fair share of reward 1.2 = .8 + 2*.2 = .8 + .4

[sternhenri]

edit:
the below is wrong, while it is true that with large miners we will have fewer than e blocks per round on average, rewrads will track rewardsPerEpoch regardless.

---

It is worth noting that with
reward = rewCount * targetRewardPerEpoch/e

there could be more or less than targetRewardPerEpoch doled out in any given round, but targetRewardPerEpoch on expectation, with the exception that if there are enough large (> 1/e) miners there will be fewer than e blocks put out per round yielding less than targetRewardPerEpoch rewards per round.

A fix would be to do:
reward = rewCount * targetRewardPerEpoch/blocksInTipset

pro:

perfectly predictable and equal rewards per round
con:
an incentive to drop other miners' blocks

con:

an incentive to drop other miners' blocks

I believe we should not do this.

cc @zixuanzh

[zixuanzh]

@sternhenri Yes, i realized what i said yesterday was flawed but forgot to comment because it creates incentives to drop other miners' block or withhold blocks and only publish them later when the miner is confident that fewer miners have found a block at that Epoch so that they can get a bigger share. Similarly, we might not want to do targetRewardPerEpoch/blocksInTipset either. A potential fix will be every block winning miner earns the same reward per block (will leave out the discussion if a miner can produce multiple blocks per round).

Lets define the following,
targetRewardPerEpoch: block reward allocated per Epoch
e: expected number of winners per Epoch
rewardPerEpochPerWinner: targetRewardPerEpoch / e

So in terms of realization, block reward per block will not always stay at targetRewardPerEpoch but on expectation, we should be fine. I want to do an incentive compatibility analysis on publishing blocks as soon as you find them.

[sternhenri]

Closing in favor of #610